Filesystem having a filename cache

• US 8,122,178 B2
• Filed: 06/10/2011
• Issued: 02/21/2012
• Est. Priority Date: 08/25/2006
• Status: Active Grant

• Current Assignee: Malikie Innovations Limited (Key Patent Innovations Limited)
• Original Assignee: QNX Software Systems Limited (Canada) (Blackberry Limited)
• Inventors: Dodge, Dan, van der Veen, Peter
• Primary Examiner(s): Jalil, Neveen Abel
• Assistant Examiner(s): KINSAUL, DANIEL W
• Application Number:
  US13/158,108
• Publication Number:
  US 20110246477A1
• Time in Patent Office: 256 Days
• Field of Search: None
• US Class Current: 711/3
• CPC Class Codes: G06F 16/172 Caching, prefetching or hoarding of files

Abstract

A system comprising a processor, a data storage device that is accessible by the processor, and filesystem software that is executable by the processor to organize files on the data storage device are provided. The filesystem software is executable to maintain a filename cache comprising filename entries. The filename entries may include a filename header section and each filename entry identifies a filename of a corresponding file.

Claims

1. A system comprising:

a processor;

a data storage device accessible by the processor; and

a filesystem software executable by the processor to organize a plurality of files on the data storage device, where the filesystem software is executable to maintain a filename cache comprising a plurality of filename entries, where each filename entry of the plurality of filename entries comprises a filename header section, and each filename entry identifies a filename of a corresponding file,

where the filename header section of each filename entry of the plurality of filename entries comprises an information item indicative of whether the filename identified in each filename entry is locatable on the system,

where the information item of the filename header section corresponding to a filename of a missing file is updated to indicate that the missing file is not located on the system based on a determination that the missing file is not located on the system, and

where the file system software is further executable to receive a request for the missing file and forego a search of the files on the data storage device for the missing file in response to a determination that the information item of the filename header section corresponding to the filename of the missing file indicates the missing file is not located on the system.

2. The system of claim 1, where the filesystem software is further executable to characterize each of the plurality of filename entries based on a namesum value of each of the plurality of filename entries where the namesum value of each of the plurality of filename entries is calculated based on an entire filename of the corresponding file of each of the plurality of filename entries.

3. The system of claim 2, where the filesystem software is further executable to generate an index into a hash table from the namesum value of at least one of the plurality of filename entries, and where data in the hash table at the index directs the file system software to the at least one of the plurality of filename entries having a same namesum value.

4. The system of claim 2, where the filename header section of each of the plurality of filename entries comprises an index to a next entry of the plurality of filename entries characterized by a same namesum value.

5. The system of claim 4, where the filesystem software is further executable to calculate a namesum value of the missing file based on the filename of the missing file, identify a first entry of the plurality of filename entries characterized by the namesum value of the missing file, determine whether the first entry of the plurality of filename entries corresponds to the missing file, and access a second entry of the plurality of filename entries characterized by the namesum value of the missing file, based on the index stored in the filename header section of the first entry of the plurality of filename entries if the first entry of the plurality of filename entries does not correspond to the missing file.

17. The system of claim 1, where the request for the missing file is a second request for the missing file, and where the determination that the missing file is not located on the system is based on a failure to find the missing file in the filename cache in response to a first request for the missing file.

6. A method for operating a filesystem comprising:

organizing a plurality of files on a data storage device;

allocating a storage space to a filename cache;

organizing the filename cache into a plurality of filename entries, where each filename entry of the filename entries comprises a filename header section, and each filename entry identifies a filename of a corresponding file;

including an information item in the filename header section of each filename entry of the plurality of filename entries that indicates whether the filename identified in each filename entry is located on the system;

updating the information item of the filename header section of the filename entry corresponding to a filename of a missing file to indicate that the missing file is not located on the system based on a determination that the missing file is not located on the system;

receiving a request for the missing file; and

determining that the missing file is not located on the filesystem without a search of the files on the data storage device based on a determination that the information item of the filename header section of the filename entry corresponding to the filename of the missing file indicates the missing file is not located on the system.

7. The method of claim 6 further comprising:

characterizing each of the plurality of filename entries based on a namesum value of each of the plurality of filename entries, where the namesum value of each of the plurality of filename entries is calculated based on the filename identified by each of the plurality of filename entries;

generating an index into a hash table from the namesum value of at least one of the plurality of filename entries; and

including a second information item in the at least one of the plurality of filename entries indicative of whether the at least one of the plurality of filename entries corresponds to a first entry in the hash table for the namesum value of the at least one of the plurality of filename entries.

8. The method of claim 7, further comprising calculating a namesum using the filename of the missing file.

9. The method of claim 8, further comprising generating an index from the calculated namesum.

10. The method of claim 9, further comprising:

using the index from the calculated namesum to obtain an initial pointer from the hash table; and

using the initial pointer to access a first filename entry of the plurality of filename entries in the filename cache having the calculated namesum.

11. The method of claim 10, further comprising comparing the filename of the missing file to the filename identified in the first filename entry for a match.

12. The method of claim 11, where the filename header section of the first filename entry comprises a third information item corresponding to a parent directory of the corresponding file.

13. The method of claim 12, further comprising comparing a parent directory information item of the missing file to the third information item of the filename header section of the first filename entry to determine whether there is a match between the missing file and the file corresponding to the first filename entry.

14. The method of claim 6, further comprising:

creating a filename entry in the filename cache for the missing file; and

indicating in the information item included in the filename header section of the filename entry that the missing file is not located on the system when the missing file is not found in a search of the data storage device.

15. A storage medium comprising code configured to execute a method for operating a filesystem with a processor, the method comprising the acts of:

organizing a plurality of files on a data storage device;

allocating a storage space to a filename cache;

organizing the filename cache into a plurality of filename entries, where each filename entry of the filename entries comprises a filename header section, and each filename entry of the filename entries identifies a filename of a corresponding file;

including an information item in the filename header section of each filename entry of the plurality of filename entries that indicates whether the filename identified in each filename entry is located on the system;

updating the information item of the filename header section of a filename entry corresponding to a filename of a missing file to indicate that the missing file is not located on the system in response to a determination that the missing file is not located on the system;

receiving a request for the missing file; and

determining that the missing file is not located on the filesystem without a search of the files on the data storage device based on a determination that the information item of the filename header section of the filename entry corresponding to the filename of the missing file indicates missing file is not located on the system.

16. The storage medium of claim 15, where the method further comprises the acts of:

creating a filename entry in the filename cache for the missing file; and

indicating in the information item included in the filename header section of the filename entry that the missing file is not located on the system, when the missing file is not found in a search of the data storage device.