Patent Publication Number: US-8122178-B2

Title: Filesystem having a filename cache

Description:
PRIORITY CLAIM 
     This application is a continuation application of, and claims priority under 35 U.S.C. §120 to, U.S. patent application Ser. No. 12/960,197, “FILESYSTEM HAVING A FILENAME CACHE,” filed Dec. 3, 2010, the entire contents of which are incorporated by reference, which is a continuation application of, and claims priority under 35 U.S.C. §120 to, U.S. patent application Ser. No. 11/717,583, “FILESYSTEM HAVING A FILENAME CACHE,” filed Mar. 13, 2007, the entire contents of which are incorporated by reference, which claims priority to both U.S. Provisional Application No. 60/841,804, filed Sep. 1, 2006, the entire contents of which are incorporated by reference, and U.S. Provisional Application No. 60/840,246, filed Aug. 25, 2006, the entire contents of which are incorporated by reference. 
    
    
     BACKGROUND OF THE INVENTION 
     1. Technical Field 
     This invention is generally directed to a filesystem for use in a computer, embedded controller, processing system, or the like. More particularly, this invention is directed to a filesystem having a filename cache. 
     2. Related Art 
     Computers, embedded controllers, and other microprocessor based systems are typically constructed from a variety of different hardware components. The hardware components may include a processor, I/O devices, human interface devices, and the like. Additionally, such systems use memory storage units to maintain the data used in the system. The memory storage units may take on a variety of different forms including, but not limited to, hard disk drives, floppy disk drives, random access memory, flash memory, and the like. 
     High-level application programs that are executed in such systems must often interact seamlessly with these hardware components, including the memory storage units. To this end, many systems run an operating system that acts as an interface between the application programs and the system hardware. Filesystem software may be included as part of the operating system or it may be provided as an ancillary software component that interacts with the operating system. In either instance, the filesystem software organizes the data within the memory storage units for ready access by the processor and the high-level application programs that the processor executes. 
     The filesystem software may employ a file/directory layer that organizes the contents of files and directories into equal-sized logical blocks of contiguous data. Each logical block has an association with one or more corresponding physical blocks on the storage device where the data is actually retained. The file/directory layer executes updates to the filesystem by identifying every block that needs to be updated in response to a request and rewriting the entire contents of each such block. The file/directory layer reads the contents of files and directories by reading the entire contents of every block that holds a portion of the region of data to be read. 
     The filesystem also may include a storage layer that maps the virtual addresses of filesystem contents to physical blocks of data on the data storage device. The storage layer may execute logical block read requests from the file/directory layer by determining the correct physical block(s) associated with the request and reading its contents from the data storage device. Similarly, the storage layer may execute right requests by either updating contents of an existing physical block(s), or by allocating an unused physical block from the data storage device to the logical block and then updating the contents of the physical block. 
     The filesystem also may be responsible for locating a file in data storage using, for example, a filename associated with the file. Systems such as UNIX employ a filename cache in which a fixed number of bytes are allocated to each filename for this purpose. This system may be wasteful of memory space when the filenames are short and may result in ambiguous hits for long filenames that have been truncated to fit into the fixed byte allocation. Accordingly, there is a need for an improved filename caching system. 
     SUMMARY 
     A system that comprises 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 may be executable to maintain a filename cache having filename entries. The filename entries may include a filename header section and identify a filename of a corresponding file. The filename header section may include a variety of information. The filename header section of each filename entry may include an information item that indicates whether the filename identified in each filename entry is locatable on the system. 
     In one aspect, the filename header section may include information corresponding to a length of the filename identified in the filename entry, information uniquely identifying the file associated with the filename, information for indexing into a filename hash table, and/or information indicative of whether the filename entry corresponds to a first entry in the filename hash table for a particular namesum. Still further, the filename header section may include an index to the next name in the filename cache buffer having the same namesum value to thereby facilitate searches through the filename cache. 
     Other systems, methods, features and advantages of the invention will be, or will become, apparent to one with skill in the art upon examination of the following figures and detailed description. It is intended that all such additional systems, methods, features and advantages be included within this description, be within the scope of the invention, and be protected by the following claims. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       The invention can be better understood with reference to the following drawings and description. The components in the figures are not necessarily to scale, emphasis instead being placed upon illustrating the principles of the invention. Moreover, in the figures, like referenced numerals designate corresponding parts throughout the different views. 
         FIG. 1  is a block diagram of a processing system that may implement a filesystem having a filename cache. 
         FIG. 2  illustrates one manner in which the filesystem software may implement a filename cache. 
         FIG. 3  illustrates one manner of arranging information in the filename header section of each filename entry shown in  FIG. 2 . 
         FIG. 4  is a flow chart showing a number of interrelated operations that may be used by the filesystem software to respond to a filename access request. 
         FIG. 5  is a flow chart showing a number of interrelated operations that may be executed by the filesystem software in responding to a filename cache update request. 
     
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS 
       FIG. 1  illustrates the components that may be employed in an exemplary processing system  100 . As shown, the exemplary system  100  includes a processor  105 , read only memory  110 , and data storage  115 . Processing system  100  also may include random access memory  120 , an I/O interface  125 , and a user interface  130 . The specific components that are used in processing system  100  may be tailored to the particular function(s) that are to be executed by the processing system  100 . Accordingly, the presence or absence of a component may be specific to the design criterion imposed on the processing system  100 . 
     Data storage  115  may include operating system code  135  that controls the interaction between high-level application programs executed by the processor  105  and the various hardware components, including memory  110  and  120 , the data storage  115 , and the interface devices  125  and  130 . The operating system code  135  may include filesystem software for organizing files stored on the data storage  115 . Alternatively, the filesystem software may be provided as a separate software component that merely interacts with the operating system code  135 . In the latter case, the code corresponding to the filesystem software may be stored in read only memory  110 , data storage  115  or the like. When processing system  100  is networked with other computers and/or storage devices through I/O interface  125 , the filesystem software may be stored remotely and downloaded to the processing system  100  as needed.  FIG. 1 , however, illustrates storage of the filesystem software  140  in data storage  115 . 
     The data storage  115  may take on any number of different forms. For example, the data storage  115  may take the form of a hard disk drive, floppy disk drive, etc. It also may be in the form of a non-rotating media device, such as non-volatile memory implemented in an integrated circuit format (e.g., flash memory, and the like). Still further, data storage  115  need not be limited to a single memory structure. Rather, the data storage  115  may include a number of separate storage devices of the same type (e.g., all flash memory) and/or separate storage devices of different types (e.g., one or more flash memory units and one or more hard disk drives). 
     The files stored in the data storage  115  include data that is interpreted in accordance with a predetermined format used by an application program or by the operating system code  135 . For example, the data stored within a file may constitute the software code of an executable program, the ASCII text of a database record, audio media files, video media files, or the like. 
     Storage  115  also includes a metadata file  145  that stores metadata information for the files organized in the file data area  150 . In other system designs, metadata file  145  may be stored in RAM  120 . Access to the metadata information for a file through use of a filename is streamlined using a hash table  155  and filename cache  160 . In the exemplary system shown in  FIG. 1 , both the hash table  155  and the filename cache  160  are stored in RAM  120 . 
       FIG. 2  illustrates one manner in which the filesystem software  140  may implement filename cache  160  and hash table  155 . In this example, filename cache  160  may be in the form of a fixed sized buffer having filename entries  205  of varying size. Each filename entry  205  is comprised of a filename header section  210  and a name section  215 . Except in the case of dummy filename entries, the name section  215  of each filename entry  205  includes the entire filename for a respective file and is variable in size while the filename header section  210  may have a fixed size. 
       FIG. 3  illustrates one manner of arranging information in the filename header section  210 . As shown, the filename header  210  includes a “next cache location” field  305 , a unique file identifier field  310 , a sequence number field  315 , a name length field  320 , a back index field  325 , a missing field  330 , an alias field  335 , and an IsBack field  340 . The “next cache location” field  305  serves as an index/pointer to the next filename entry in the cache  160  that has a filename with the same namesum value. This field is used to search the filename cache for a particular filename while avoiding unnecessary checks of intermediate filename entries that do not have the same namesum value. The unique file identifier field  310  is used to uniquely identify a given file in the filesystem. Here, the unique file identifier field  310  corresponds to the file having the filename in the name section  215  of the filename entry  205  and may be used to differentiate between different files having the same filename but which are stored in different storage locations. The sequence field  315  includes a sequence number that is unique to the filesystem. The name length field  320  of header section  210  provides information on the length of the name section  215 , such as the number of bytes contained in the name section. The back field  325  provides an index into the hash table for the particular filename entry  205 . The missing field  330  is used to identify whether the filename in name section  215  is located on the system. This allows the filesystem software  140  to quickly identify filenames that already have been searched and not located on the system thereby allowing the filesystem software to forgo unnecessary searching for the missing filename. The alias field  335  is used to identify the contents of the name section  215  as an alias name for the file. The IsBack field  340  is used to indicate whether the filename entry  205  corresponds to the first entry in hash table  155  for a particular namesum. 
       FIG. 4  is a flow chart showing a number of interrelated operations that may be used by the filesystem software  140  to respond to a filename access request. In this example, a filename access request is made at block  405 . The request may include the filename and an identification of the parent directory/directories. The filesystem software  140  proceeds to calculate a namesum using the requested filename at block  410 . A hash function is executed on the calculated namesum at block  415  to generate an index into hash table  155 . The hash index is used at block  420  to obtain an initial pointer into the filename cache  160 . If the initial pointer is invalid, then the filesystem software  140  assumes that the filename has not been cached at block  425  and an alternate filename search outside of the filename cache  160  is executed at block  430 . Otherwise, the filesystem software  140  assumes that the filename is in the filename cache  160  and begins searching the filename entries  205  at block  435 . 
     One manner of searching through the filename entries  205  is represented in  FIG. 2 . To this end, the index into hash table  155  obtained at block  415  of  FIG. 4  is shown at arrow  220  and points to a hash table location  225  corresponding to a namesum=y (assuming that the namesum calculated at block  410  of  FIG. 4  is also y.) The data in hash table location  225  serves as an initial pointer that directs the filesystem software  140  to the first entry in the filename cache  160  that has a name section  215  having the same namesum (y) as the filename requested at block  405 . Here, the first entry is designated at  230  and includes filename header section  235  and name section  240 . The filesystem software  140  compares the complete filename received at block  405  of  FIG. 4  to the complete filename stored in name section  240  to determine whether there is a match. If there is no match, the filesystem software  140  checks the next field  305  of filename header section  235  to identify the next entry in the filename cache  160  storing a filename having a namesum=y. In  FIG. 2 , the next filename entry with namesum=y is filename entry  245  having filename header section  250  and name section  255 . Again, the complete filename stored in name section  240  is compared to the complete name received at block  405  to determine whether there is a match. Assuming that there is a match, the unique file identifier  310  of filename header section  250  is obtained at block  440  of  FIG. 4  and used at block  445  to determine whether the file referenced by the unique file identifier is a child of the parent directory provided during the filename access request of block  405 . If it is, the filename has been found as indicated at block  450 . If it is not, the filesystem software checks at block  455  to determine whether all appropriate filename entries having a namesum=y have been searched. If less than all appropriate filename entries have been searched, the search continues at block  460 , where the next field  305  of the current filename entry is used to identify the next filename entry that is to be compared. In  FIG. 2 , the next field  305  of filename header section  250  points to filename entry  260  having filename header section  265  and name section  270 . If all appropriate filename entries have been searched as determined at block  455 , the alternate filename search of block  430  may be executed. 
       FIG. 5  is a flow chart showing a number of interrelated operations that may be executed by the filesystem software  140  in responding to a filename cache update request. As shown, a filename cache update request is received at block  505  and, in the illustrated example, may correspond to one of three different request types: filename found update, filename not on system update, and filename deleted update. In a “filename found update,” the filesystem software  140  is directed to store a filename entry for a corresponding filename in the filename cache  160 . To this end, the information provided to the filesystem software  140  in the request is used to generate a filename header section and name section for the filename entry at block  510 . Since the filename cache  160  is in the form of a fixed buffer, it employs a put pointer  275  (see  FIG. 2 ) that rotates through the cache buffer to indicate where the next filename entry is to be stored. Once the put pointer extends beyond the end of the filename cache  160 , it is rotated back to a beginning portion of the filename cache  160 . As such, filename entries are added to the filename cache  160  in a ring-like manner where newer filename entries in the cache are written over older filename entries. 
     The filename header section and name section for the filename entry generated at block  510  are stored as a filename entry at the put pointer location in the operation shown at block  515 . This operation may overwrite one or more existing filename entries of the filename cache  160  thereby leaving unused space between the end of the new filename entry and the beginning of the next complete filename entry in the filename cache  160 . To reduce problems that might otherwise be associated with this unused space, the unused space may be allocated to a dummy file name entry. To this end, the filesystem software checks at block  520  to determine whether a dummy entry is needed. If needed, the dummy entry is generated and stored after the current filename entry in the operation at block  525 . If no dummy entry is needed, the put pointer  275  is updated to point to the end of the newly added filename entry in the operation at block  530 . Alternatively, if a dummy entry is used at block  525 , the put pointer  275  is updated to point to the end of the newly generated dummy entry. In the operation at block  535 , the hash table  155  is updated to reflect changes to the filename cache buffer. 
     In a “filename not on system” update, the filesystem software  140  is directed to store a filename entry for a corresponding filename in the filename cache  160  and indicate that it is not on the system. To this end, the filename provided at block  505  is used to generate a filename header and name section for the absent filename in the operation shown at block  540 . The missing field  330  of the generated filename header will be set to indicate that the filename is not on the system. This allows the filesystem software  140  to forgo searching the filesystem for a filename that has already been searched and not found on the system. Once the operation at block  540  is complete, the filesystem software  140  may proceed to execute the operations shown in blocks  515  through  535 . 
     In a “filename deleted” update, the filesystem software  140  is directed to remove a filename entry for a corresponding filename from the filename cache  160 . As shown, this is accomplished at block  545 . In the operations at block  545 , one or more bits in the filename header section of the filename entry that is to be removed are changed to indicate removal of the filename. For example, the unique file identifier field  310  may be filled with zeros or another value that is not associated with an actual file and known to be indicative of a removed file. Once the corresponding filename header section has been changed, the hash table is updated in the operations at block  535  to reflect changes to the filename cache  160 . 
     While various embodiments of the invention have been described, it will be apparent to those of ordinary skill in the art that many more embodiments and implementations are possible within the scope of the invention. Accordingly, the invention is not to be restricted except in light of the attached claims and their equivalents.