Managing the fetching and replacement of cache entries associated with a file system

• US 5,390,318 A
• Filed: 05/16/1994
• Issued: 02/14/1995
• Est. Priority Date: 06/29/1990
• Status: Expired due to Term

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Digital Equipment Corporation (HP Inc.)
• Inventors: Ramakrishnan, Kadangode K., Biswas, Prabuddha
• Primary Examiner(s): Dixon, Joseph L.
• Assistant Examiner(s): Nguyen, Hiep T.
• Application Number:
  US08/243,041
• Time in Patent Office: 274 Days
• Field of Search: 395/600, 395/425, 364/200 MS File, 364/900 MS File
• US Class Current: 711/158
• CPC Class Codes: G06F 12/0802 Addressing of a memory level in which the access to the desired data or data block requires associative addressing means, e.g. caches
• CPC Class Codes: G06F 12/0862 with prefetch
• CPC Class Codes: G06F 12/0866 for peripheral storage systems, e.g. disk cache
• CPC Class Codes: G06F 12/128 adapted to multidimensional cache systems, e.g. set-associative, multicache, multiset or multilevel
• CPC Class Codes: G06F 16/902 using more than one table in sequence, i.e. systems with three or more layers

Abstract

Information needed by application programs from a secondary storage is cached in a cache memory which is organized in multiple levels, each level having multiple entries, the entries of each level receiving information of a predetermined category, each entry being accessible independently. Links are defined between entries of one level of the cache memory and entries at another level of the cache memory, the links corresponding to information relationships specified by a user of information stored in the secondary storage. In response to a request to a file system from an application for needed information, the needed information is fetched into the cache, and in connection with fetching the needed information, other information is prefetched from the system of files which is not immediately needed. Quotas are established on information which may be fetched from a secondary storage into the cache, the quotas being applicable to file contents within a file and to the number of files within a directory. Upon a request from an application program to open a file, an entry is created in a cache corresponding to the file, the entry including file header information. The file header information is retained in the cache so long as the file remains open, whether or not any file contents of the file remain in cache. The entries of three level of the cache respectively receive directory information, file header information, and file contents information.

Claims

1. A method for managing the use and re-use of entries of a cache, said entries containing data retrieved from a mass storage into said cache to be thereafter available for use by a computer system, comprising the computer system

grouping entries;

assigning each entry a priority for storage relative to other entries of the same group;

identifying at least a first entry and a second entry belonging to different respective said groups which are related in a system of files in said mass storage; and

selecting one of said entries of said cache for re-use according to the priority for storage assigned to said entry and the priority for storage assigned to identified related entries.

2. The method of claim 1 further comprising

storing pointers in said cache linking said identified related entries.

3. The method of claim 2 wherein the step of assigning entries priority for storage comprises assigning each said entry a priority for storage relative to other entries within its group by the following steps:

when the data contained in a first entry of a first group is used by said computer system, said first entry is assigned the highest priority for storage within the entries of said first group, and

when a second entry, which is related by a pointer to said first entry, is assigned the highest priority for storage of a second group, said first entry is assigned the highest priority for storage within the entries of said first group.

4. The method of claim 3 wherein the step of selecting an entry for re-use comprises

selecting one said group of entries that contain data of a type corresponding to the type of data to be stored in the re-used entry, and

selecting the entry of the selected group which has the lowest priority for storage,

whereby the selected entry has the lowest priority for storage of the selected group and all entries related to the selected entry have the lowest priority for storage of their respective groups.

5. The method of claim 3 further comprising

removing from said cache entries which are not used by said computer system for a given duration of time.

6. The method of claim 2 wherein re-use of an entry results in re-use of a related entry.

7. The method of claim 2, further comprising prefetching data into said cache when data required by said computer system is retrieved from said mass storage, said prefetching comprising

retrieving said required data into a first entry,

placing said first entry into a first group,

identifying a second entry in a second group which is related to said first entry,

storing a pointer linking said first entry to said second entry,

identifying other data in said mass storage which is related to the data contained in said second entry in a similar manner as said required data,

retrieving said other data into one or more additional entries,

placing said additional entries into said first group, and

storing pointers linking said additional entries to said second entry.

8. The method of claim 7 further comprising

limiting the number of additional entries which are prefetched into said cache upon retrieval of said required data.

9. The method of claim 2 further comprising

limiting the number of entries in one group in said cache.

10. The method of claim 2 further comprising

for each group, limiting the number of entries which are related to the same entry in another group.

22. The method of claim 2 further comprising

when an entry is added to a given level or when the information stored in a given entry at a given level is used by an application program:

(4) one or more entries of said given level which are related to the entry of said higher level which was moved in step (2) are moved, as a group and maintaining the ordering within the group, to a position next to said added or used entry at said end of said given level'"'"'s list, and

(5) one or more groups of entries of said lower level which are related to the entry of said given level which was moved in step (4) are moved, as groups and maintaining the ordering within and between the groups, to positions next to the entries moved in step (3) at said end of said lower level'"'"'s list.

11. A method for caching information retrieved by application programs from files organized in a file system in mass storage, comprising

organizing a cache in at least two levels having multiple cache entries, including an upper level comprising directory entries storing directory file information and representing directories in said file system, and a lower level comprising file header entries storing file header information and representing files in said file system,

identifying file header and directory entries related such that the identified directory entry represents the directory containing the file represented by the identified file header entry, and storing pointers in the cache linking the related entries,

assigning each entry a priority for storage relative to the other entries in the same level, and

managing use and re-use of said cache entries according to the priority for storage assigned to said entries.

12. The method of claim 11 wherein said cache includes a third lowest level comprising file contents entries storing file contents information and representing file contents in said file system, and further comprising

identifying file contents and file header entries related such that the identified file header entry represents the file containing the file contents represented by the identified file contents entry, and storing pointers in the cache linking the related entries.

13. The method of claim 12, wherein each cache level may have been new entries added, further comprising

adding new entries in a given level of said cache by the steps of

searching for an unused entry in said given level, and

where an unused entry is located, adding said unused entry to the entries of said given level, or

where an unused entry is not located, replacing an entry of said given level.

14. The method of claim 13 further comprising

when an entry is added to a given level, or when the information stored by an entry of a given level is used by an application program, said entry is indicated as the most-recently-used entry of said given level.

15. The method of claim 14 further comprising

when said entry is indicated as the most-recently-used entry of said given level, an entry related to said entry is indicated as the most-recently-used entry of the related entry'"'"'s level.

16. The method of claim 15 wherein replacing an entry from a given level comprises selecting the least-recently-used entry in said given level,

whereby

if the replacing entry is a directory entry, the replaced entry is the entry which contained the directory file of the least-recently-used directory,

if the replacing entry is a file header entry, the replaced entry is the entry which contained the header of the least-recently-used file of the least-recently-used directory;

or

if the replacing entry is a file contents entry, the replaced entry is the entry which contained the least-recently-used file contents of the least-recently-used file of the least-recently-used directory.

17. The method of claim 16 wherein each said entry contains a replacement value used for selecting an entry for replacement.

18. The method of claim 17 wherein

said replacement value is a time stamp, and

when an entry is added or when the information stored in an entry is used by an application program, the replacement value of said entry is updated to a current time stamp value.

19. The method of claim 18 further comprising

when an entry is added to a given level or when the information stored in an entry at a given level is used by an application program, updating the replacement value of a related entry of a higher level to a current time stamp value.

20. The method of claim 19 wherein

replacing a selected entry from a given level comprises selecting the entry of said given level containing the least recent time stamp value, and

if said replaced entry is the only entry of said given level which is related to a second entry in a higher level, replacement of said replaced entry entails removal of said second entry from said higher level.

21. The method of claim 16 wherein

the entries of each said level are organized as a list, and

when an entry is added to a given level or when the information stored in a given entry at a given level is used by an application program:

(1) said added or used entry is moved to an end of said given level'"'"'s list,

(2) an entry of a higher level which is related to said added or used entry is moved to an end of said higher level'"'"'s list, and

(3) one or more entries of a lower level which are related to said added or used entry are moved, as a group and maintaining the ordering within the group, to an end of said lower level'"'"'s list.

23. The method of claim 21 wherein replacing a selected entry from a given level comprises selecting an entry of said given level'"'"'s list which is at an end opposite said end.

24. The method of claim 12 further comprising

in response to a request from an application program requiring that a directory entry be added to said cache, fetching said directory entry into said cache, and in connection with fetching said directory entry, prefetching into said cache file header entries storing headers of files from the directory represented by said directory entry, and

in response to a request from an application program requiring that a file header entry be added to said cache, fetching said file header entry into said cache, and in connection with fetching said file header entry, prefetching into said cache file contents entries storing contents of the file represented by said file header entry.

25. The method of claim 13 further comprising

upon a request from an application program to open a file, determining whether a file header entry storing the header of said file is stored in said cache, and if not adding such an entry.

26. The method of claim 12 further comprising

establishing quotas which limit the number of file header entries which are related to one directory entry, and the number of file contents entries which are related to one file header entry, and

managing the use and re-use of entries in said levels to enforce said quotas.

27. The method of claim 26 wherein said quotas are enforced in accordance with the following step:

when a quota will be exceeded by adding a new entry to a given level, an existing entry from said given level which is related to the same entry in a higher level as said new entry is replaced by said new entry.

28. The method of claim 27 wherein the entry replaced by said new entry is the least-recently-used of the entries of said given level which are related to the same entry in a higher level as said new entry.

29. The method of claim 28 wherein the entry replaced by said new entry is the least-recently-used of the entries of said given level, whereby

if the replacing entry is a directory entry, the replaced entry is the entry which contained the directory file of the least-recently-used directory,

if the replacing entry is a file header entry, the replaced entry is the entry which contained the header of the least-recently-used file of the least-recently-used directory;

or

if the replacing entry is a file contents entry, the replaced entry is the entry which contained the least-recently-used file contents of the least-recently-used file of the least-recently-used directory.

30. The method of claim 26 further comprising

establishing further quotas limiting the total number of entries of each level.

31. The method of claim 30 wherein said quotas are enforced in accordance with the following step:

when a quota described in claim 30 will be exceeded by adding said new entry, an existing entry from said given level is replaced by said new entry.

32. The method of claim 31 wherein the entry replaced by said new entry is the least-recently-used of the entries of said given level, whereby

if the replacing entry is a directory entry, the replaced entry is the entry which contained the directory file of the least-recently-used directory,

if the replacing entry is a file header entry, the replaced entry is the entry which contained the header of the least-recently-used file of the least-recently-used directory;

or

if the replacing entry is a file contents entry, the replaced entry is the entry which contained the least-recently-used file contents of the least-recently-used file of the least-recently-used directory.

33. The method of claim 30 wherein

said quotas are adjusted based on the frequency of use of the entries in said levels, whereby the storage space in said cache that is devoted to each level may be adjusted.

34. The method of claim 33 wherein said quotas are established such that the directory entry level is less likely to reach its quota than is another level.

35. The method of claim 34 further comprising

said quotas are adjusted based on the number of available unused entries, whereby the storage space in said cache that is devoted to each level may be adjusted.

36. The method of claim 35 further comprising

organizing unused entries into one or more levels corresponding to said higher, lower, and lowest levels, and wherein

said quotas are adjusted by reallocating unused entries between said levels.

37. The method of claim 35 wherein adjustments to said quotas are enforced by removing entries from said cache and placing said entries in said unused entry levels.

38. The method of claim 11 further comprising

in response to a request from an application program requiring that an entry be added to a given level of said cache, fetching said needed entry into said cache, and

in connection with fetching said needed entry, prefetching an additional entry into said cache.

39. The method of claim 38 wherein said additional entry is at said given level.

40. The method of claim 38 wherein said additional entry is at a level different from said given level, and

said additional entry is related to said needed entry.

41. The method of claim 38 wherein multiple entries are prefetched, the number of entries being limited by a prefetching quota.

42. The method of claim 41 wherein

said prefetching quota is adjusted based on the number of entries available in all levels.

43. The method of claim 41 further comprising

organizing unused entries into one or more levels corresponding to said higher, lower, and lowest levels, and

each said level has a prefetching quota, and wherein

each level'"'"'s prefetching quota is adjusted based on the number of entries available in said level.

44. The method of claim 38 wherein each said entry contains an old age indicator used for selecting entries for removal, and further comprising

setting the old age indicator of needed entries when placed in said cache,

clearing the old age indicator of prefetched entries when placed in said cache,

when an entry is used by an application program, setting the old age indicator of said entry, and

periodically removing from said cache all entries having cleared old age indicators, and then clearing the old age indicators of all entries which remain in the cache,

whereby prefetched entries which have not been used by an application program in time period after said request may be aged and removed from said cache.

45. The method of claim 11 further comprising

aging and removing from said cache entries which have not been used by an application program over a predetermined time period.

46. The method of claim 45 wherein each said entry contains a old age indicator, and said aging comprises

when an entry is used by an application program, setting the old age indicator of said entry, and

periodically removing from said cache all entries having cleared old age indicators, and then clearing the old age indicators of all entries which remain.

47. The method of claim 13 wherein

replacement or removal of an entry from a given level entails removing all entries or lower levels which are related to said entry.

48. The method of claim 47 wherein

if said replaced or removed entry is the only entry of said given level which is related to a second entry in a higher level, replacement or removal of said replaced or removed entry entails removal of said second entry from said higher level.

49. The method of claim 48 further comprising

retaining a file header entry in said cache as long as said file remains open, whether or not any file contents of said file are stored in said cache.

62. The method of claim 11 further comprising

establishing a quota which limits the number of file header entries in said lower level which are related to one directory entry in said upper level, and

managing the use and re-use of entries in said lower level to enforce said quota.

50. A method comprising

storing in a cache information describing files and directories of files retrieved by application programs from a file system in which files are organized according to user-defined information relationships among said files and directories,

storing in said cache contents of said files

in response to a request to said file system from an application program, fetching needed information into a cache, and

in connection with fetching said needed information, prefetching other information from said file system which is not immediately needed but is related to said needed information through said user-defined relationships among said files and directories.

51. The method of claim 50 wherein the amount of information prefetched is limited by a quota.

52. The method of claim 50 wherein said prefetching comprises prefetching headers of files.

53. The method of claim 50 wherein said needed information is a directory file and said prefetching comprises prefetching headers of files in the directory described by said directory file.

54. The method of claim 50 wherein said needed information is a file header and said prefetching comprises prefetching headers of files in the same directory as said needed file header.

55. The method of claim 54 wherein said prefetching comprises fetching the header of files having symbolic file names which match the symbolic file name of the file associated with the needed header.

56. The method of claim 55 wherein the nature of the similarity between said symbolic file names is determined by the type of application program making said request.

57. The method of claim 56 wherein said application program is a compiler, and said needed and prefetched files are source and object modules of a program being compiled.

58. A method of a managing a cache of information retrieved by application programs from a file system organized according to user-defined information relationships, said information including file contents as well as file headers describing files and directory files describing directories of files, comprising

establishing quotas that set a limit on the amount of information fetched from said mass storage into said cache, said quotas being applicable to the amount of file contents from a given file and the number of file headers from a given directory, and

regulating the fetching of information from mass storage into said cache based on said quotas.

59. The method of claim 58 wherein said quotes may be disabled during operation of specified application programs.

60. The method of claim 59 wherein said quotas are disabled during operation of a backup program.

61. A method for storing in a cache files retrieved from a file system in a computer system, comprising the computer system

storing in a cache, information describing files and directories of files retrieved by application programs from a file system,

storing in said cache, contents of said files

upon a request from an application program to open a file, determining whether an entry storing the header of said file is stored in said cache, and if not creating such an entry, and

retaining said entry in said cache so long as said file remains open, whether or not any said contents of said file are stored in said cache.