Filesystem having a filename cache

• US 20080228843A1
• Filed: 03/13/2007
• Published: 09/18/2008
• 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
• Granted Patent: US 7,908,276 B2
• Time in Patent Office: Days
• US Class Current: 707/205
• 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 having variable size filename entries. The filename entries may include a filename header section and a name section storing an entire filename of a corresponding file.

Claims

1. A system comprising:

a processor;

a data storage device accessible by the processor; and

filesystem software executable by the processor to organize files on the data storage device, where the filesystem software is executable to maintain a filename cache having variable size filename entries, and where the variable size filename entries include a filename header section and a name section storing an entire filename of a corresponding file.

2. The system of claim 1, where the filename cache is stored in a ring-type buffer.

3. The system of claim 1, where the filename header section comprises information corresponding to a length of the filename in the name section.

4. The system of claim 1, where the filename header section comprises information uniquely identifying a file associated with the filename in the name section.

5. The system of claim 1, where the filename header section comprises information for indexing into a filename hash table.

6. The system of claim 5, where the filename header section comprises information indicative of whether the variable size filename entry corresponds to a first entry in the filename hash table for a particular namesum value.

7. The system of claim 1, where the filename header section comprises information indicative of whether the filename in the respective name section is not locatable on the system.

8. The system of claim 1, where the filename header section comprises an index to a next name in the filename cache buffer having a same namesum value.

9. A system comprising:

a filename cache; and

filesystem software organizing the filename cache into variable size filename entries, where the variable size filename entries include a filename header section and a name section storing an entire filename of a corresponding file.

10. The system of claim 9, where the filename cache comprises a ring-type buffer.

11. The system of claim 10, where the filename cache comprises dummy filename entries to compensate for wrap-around writing of filename entries to the ring-type buffer.

12. The system of claim 9, where the filesystem software calculates a namesum using a filename of a requested file.

13. The system of claim 12, where the filesystem software uses the namesum to generate an index into a hash table.

14. The system of claim 13, where the filesystem software uses the index into the hash table to obtain an initial pointer from the hash table that directs the filesystem software to a first variable size filename entry in the filename cache having the calculated namesum.

15. The system of claim 14, where the filesystem software compares the requested filename to the filename stored in the name section of the first variable size filename entry for a match.

16. The system of claim 15, where the filename header section of the first variable size filename entry comprises information corresponding to a parent directory of the corresponding file.

17. The system of claim 16, where the filesystem software compares parent directory information of the requested file to the parent directory information of the filename header section of the first variable size filename entry to determine whether there is a match between the requested file and the file corresponding to the first variable size filename entry.

18. The system of claim 9, where the filename header section comprises information corresponding to a length of the filename in the name section.

19. The system of claim 9, where the filename header section comprises information uniquely identifying a file associated with the variable size filename entry.

20. The system of claim 9, where the filename header section comprises information for indexing into a filename hash table.

21. The system of claim 20, where the filename header section comprises information indicative of whether the variable size filename entry corresponds to a first entry in the filename hash table for a particular namesum.

22. The system of claim 9, where the filename header section comprises information indicative of whether the filename in the respective name section is not locatable on the system.

23. The system of claim 9, where the filename header section comprises an index to a next name in the filename cache buffer having a same namesum value.

24. The system of claim 9, where the filesystem software generates a variable size filename entry in the filename cache for a requested file when the filename cache does not include an entry for the requested file and the requested file is located by the filesystem software.

25. The system of claim 9, where the filesystem software updates one or more bits of a variable size filename entry to indicate that a filename stored in the name section of the variable size filename entry cannot be located by the filesystem software.

26. The system of claim 25, where the filesystem software checks the one or more bits to discontinue further searching for a filename that has been previously searched and not found by the filesystem software.

27. The system of claim 25, where the one or more bits are stored in the header section of the variable size filename entry.

28. The system of claim 9, where the filesystem software removes a variable size filename entry for a corresponding file when the corresponding file is deleted from the system.

29. A method for operating a filesystem comprising:

allocating storage space to a filename cache; and

organizing the filename cache into variable size filename entries, where the variable size filename entries include a filename header section and a name section storing an entire filename of a corresponding file.

30. The method of claim 29, where the allocated storage space for the filename cache comprises a ring-type buffer.

31. The method of claim 30, further comprising adding dummy filename entries to compensate for wrap-around writing of variable size filename entries to the ring-type buffer.

32. The method of claim 29, further comprising calculating a namesum using a filename of a requested file.

33. The method of claim 32, further comprising using the calculated namesum to generate an index into a hash table.

34. The method of claim 33, further comprising:

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

using the initial pointer to access a first variable size filename entry in the filename cache having the calculated namesum.

35. The method of claim 34, further comprising comparing the requested filename to the filename stored in the name section of the first variable size filename entry for a match.

36. The method of claim 35, where the filename header section of the first variable size filename entry comprises information corresponding to a parent directory of the corresponding file.

37. The method of claim 36, further comprising comparing parent directory information of the requested file to the parent directory information of the filename header section of the first variable size filename entry to determine whether there is a match between the requested file and the file corresponding to the first variable size filename entry.

38. The method of claim 29, further comprising generating a variable size filename entry in the filename cache for a requested file when the filename cache does not include an entry for the requested file and the requested file is located by the filesystem.

39. The method of claim 29, further comprising updating one or more bits of a variable size filename entry to indicate that a filename stored in the name section of the variable size filename entry cannot be located by the filesystem.

40. The method of claim 39, further comprising checking the one or more bits to discontinue further searching for a filename that has been previously searched and not found by the filesystem.

41. The method of claim 40, where the one or more bits are stored in the header section of the variable size filename entry.

42. The method of claim 29, further comprising removing a variable size filename entry when the corresponding file is deleted from the filesystem.

43. A storage medium comprising code adapted to execute a method for operating a filesystem comprising:

allocating storage space to a filename cache; and

organizing the filename cache into variable size filename entries, where the variable size filename entries include a filename header section and a name section storing an entire filename of a corresponding file.

44. The storage medium of claim 43, where the storage space allocated for the filename cache by the method comprises a ring-type buffer.

45. The storage medium of claim 44, where the method further comprises adding dummy filename entries to compensate for wrap-around writing of variable size filename entries to the ring-type buffer.

46. The storage medium of claim 43, where the method further comprises calculating a namesum using a filename of a requested file.

47. The storage medium of claim 46, where the method further comprises using the calculated namesum to generate an index into a hash table.

48. The storage medium of claim 47, where the method further comprises:

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

using the initial pointer to access a first variable size filename entry in the filename cache having the calculated namesum.

49. The storage medium of claim 48, where the method further comprises comparing the requested filename to the filename stored in the name section of the first variable size filename entry for a match.

50. The storage medium of claim 49, where the filename header section of the first variable size filename entry employed by the method comprises information corresponding to a parent directory of the corresponding file.

51. The storage medium of claim 50, where the method further comprises comparing parent directory information of the requested file to the parent directory information of the filename header section of the first variable size filename entry to determine whether there is a match between the requested file and the file corresponding to the first variable size filename entry.