Method and apparatus for validating a directory in a storage system

A method and a corresponding apparatus are described, where the method includes storing, in a processing system, an information set that includes a plurality of items in hierarchical relationships, each of the items containing information. The plurality of items are grouped to form a plurality of subsets of the information set. One of the plurality of subsets is identified, for which a known memory availability limit will not be exceeded when a predetermined test is subsequently performed on the identified subset. The predetermined test is then performed on the identified subset. The identification of a subset and performing of the predetermined test may be repeated for different subsets of the information set, so that all of the subsets in the information set have been tested.

FIELD OF THE INVENTION

At least one embodiment of the present invention pertains to storage systems, and more particularly, to a method and apparatus for testing a directory in a storage system.

BACKGROUND

A storage server is a special-purpose processing system which is used to store and retrieve data on behalf of one or more client processing systems (“clients”). A storage server can be used for many different purposes, such as to provide multiple users with access to shared data or to back up mission critical data.

A file server is one example of a storage server. A file server operates on behalf of one or more clients to store and manage shared files in a set of mass storage devices, such as magnetic or optical storage based disks or tapes. The mass storage devices are typically organized into one or more volumes of Redundant Array of Inexpensive Disks (RAID).

A file server typically includes a file system, which is software that keeps track of all of the data stored by the file server and manages read/write operations on the data. The term “file system” can also be used to refer to the actual structure of the stored data. The files within a file server are generally stored within a hierarchy of directories. A directory is simply a software-based entity which can contain information, such as one or more files, other directories and/or other data, and which is used to organize stored information.

Any data stored in a computer system has the potential to become corrupted, including the data which represents the directory structure in a file system. Undetected errors in the directory structure of a storage server can cause critical loss of data and/or downtime. Therefore, in storage servers, particularly those which store data on a very large-scale, it is desirable to have a way to test the directories in the file system for errors, to allow correction of such errors before significant damage can occur.

A storage server, such as a file server, can keep track of stored data by using inodes. An inode is a data structure, stored in an inode file, that keeps track of which logical blocks of data in a storage pool are used to store a file. In certain file servers, each stored file is represented by a corresponding inode. A directory is, at its most fundamental level, a mapping between filenames and inode indices.

For example, if a user has created a file called “hello” within a directory and later tries to read that file, the file system has to know that “hello” is stored in, for example, inode #36in the inode file. Likewise, if the user creates a subdirectory called “private”, then the file system has to know that the subdirectory is stored in, for example, inode #122in the inode file. The directory structure maintains these mappings. A file server generally includes many such directories.

In one prior art file server, each directory is stored in the form of one or more 4-kbyte blocks, stored in various places in the storage pool. To create the directory structure, each of those 4-kbyte blocks are divided into two 2-kbyte “segments”. There are two types of segment: name segments and tree segments. Each directory has at least one name segment and at least one tree segment. Name segments contain the basic mappings between filenames and inode numbers, while tree segments are used to accelerate filename lookups. Each tree segment points to some number of name segments and, in some cases, to one or more other tree segments. Two 2-kbyte segments fit into every 4-kbyte block. Note the distinction here between a directory and the information (e.g., files) contained in the directory: what is being described here is the manner in which the directory itself is represented in the storage pool, not the information contained in the directory.

A directory has at least one tree segment and at least one name segment. The tree segment or segments of the directory form a hierarchical structure referred to as a radix tree. The radix tree is a device used to accelerate lookups of filenames in the directory. As shown in example ofFIG. 1, multiple tree segments2can make up a radix tree1of a directory. The radix tree of a directory always includes at least a root tree segment T1and may also include one or more other tree segments2. The root tree segment T1references the other tree segments2either directly or indirectly. Each tree segment2refers to some number of name segments (not shown).

A directory can become very large, so as to be represented on disk by a very large radix tree with many segments. Large directories can present problems, however, for purposes of directory testing and validation, especially in a very large storage pool. One known prior art file server uses a directory structure such as described above (radix trees of name segments and tree segments) and includes a software utility to perform testing and validation of directories. The prior art testing algorithm generally batches together all of the name segments under a given tree segment, performs validation on those names, then repeats the process for each tree segment in the directory, and then further repeats this process for each directory in the storage pool.

One problem with this approach is that many directories are too large to store in main memory in their entirety (i.e., including all of their name segments). Consequently, many disk read operations (“I/Os”) are required to access the directory information (segments) on disk during directory validation. Disk I/Os tend to involve high latency in comparison to accessing main memory. This problem is exacerbated by very large directories and very large storage pools. As a result of disk I/O latency, the process of testing and validating all directories can take hours or even days for a very large storage pool.

SUMMARY OF THE INVENTION

The present invention includes a method and a corresponding apparatus, where the method includes storing, in a processing system, an information set that includes a plurality of items in a hierarchy, each of the items containing information. The plurality of items are grouped to form a plurality of subsets of the information set, based on an amount of memory required to perform a predetermined test on each subset. One of the plurality of subsets is selected, and then the predetermined test is performed on only the selected subset.

The selection of a subset and performing of the predetermined test may then be repeated for different subsets of the information set, until all of the subsets in the information set have been processed in this way.

Other aspects of the invention will be apparent from the accompanying figures and from the detailed description which follows.

DETAILED DESCRIPTION

A method and apparatus for validating a directory of information stored in a storage server are described. To facilitate description, it is assumed that the validation technique is implemented in a file server. A file server122in which the invention can be implemented is shown inFIGS. 12 and 13and is described below.

To facilitate description, it is further assumed that the validation technique is applied to a storage pool in which each directory is stored in the manner described above. That is, each directory is stored as one or more 4-kbyte blocks, stored in various places in the storage pool. Each of the 4-kbyte blocks is divided into two 2-kbyte segments, including at least one name segment and at least one tree segment. Name segments contain the basic mappings between filenames and inode numbers. A filename always resides entirely within a single name segment. Tree segments point to name segments and, in some cases, other tree segments, and are used to accelerate filename lookups. A directory has at least one tree segment and at least one name segment. The tree segments of the directory form a hierarchical structure referred to as a radix tree, an example of which is shown inFIG. 1, which is used to accelerate lookups of filenames in the directory.

As a result of disk I/O latency, for a very large storage pool the process of validating all directories can take hours or even days. The technique introduced herein addresses this problem. In accordance with embodiments of the invention, a specified validation test is to be performed on each name in a directory (a specific example of such a test is described below). The types of input information needed to perform this test for each name are known. From this knowledge, the maximum amount of memory required to store that information for each name can also be readily determined, as described further below. It is further assumed that the amount of space available in main memory for storing such information of the file server is also known.

In accordance with embodiments of the invention, therefore, each directory's radix tree is divided up (logically) to define one or more subsets of the radix tree. Each subset is defined as one or more of the radix tree's tree segments. The subsets are defined based on the number of names under each tree segment. More specifically, the subsets are defined so that, for each subset, all of the information required to perform the validation test on all names within the subset can be stored at one time in main memory of the file server (considering the amount of memory space available). The validation test involves verifying that the tree segments' indexing of information stored in the name segments agrees with the information actually stored in the name segments.

To perform the test, for each subset the required input information is first placed into a special object for each name in the subset, called a name info object, which is stored in main memory. A separate name info object is created for each name which should be hashed under that subset. The validation test is then performed on all of the names in the subset from the corresponding name info objects stored in main memory, without having to perform any further disk I/Os to test the names in that subset.

This approach reduces the number of disk I/Os required when testing a directory, resulting in an overall reduction in latency. For very large storage pools, this approach can yield a substantial reduction in the overall time required to test all directories in the file system.

Before describing this validation technique in greater detail, it is useful to further describe an approach to implementing directories. Referring first toFIG. 2, each directory in a storage pool is represented as one or more 4-kbyte blocks22. The first 4-kbyte block includes one name segment followed by one tree segment. A newly-created directory has exactly this one block and is, therefore, 4 kbytes in size. Thereafter, the directory21can be extended by adding additional 4-kbyte blocks22when necessary: either two name segments or two tree segments (i.e., one block) are added at a time. Every segment in a directory is assigned an index: for example, the first name segment23is segment #0, the first tree segment41is segment #1, the second name segment is segment #3, and so on.

As shown inFIG. 2, each name segment23includes a name segment header24followed by a number (N) of name segment entries (NSEs)25. Each NSE25can contain at least a portion of a name (and NSE25can contain an entire name if the name is small enough to fit in the NSE). Hence, each name segment23can potentially store up to N names. In certain embodiments of the invention, there are 63 NSEs in each name segment. In some such embodiments, each NSE25is 32 bytes and is split into two halves: a 16-byte NSE header26and a 16-byte text area27for storing at least a portion of a filename. Although a filename always resides entirely within a single name segment23, depending on its length it may be distributed amongst multiple NSEs25within a name segment23.

The name segment header24includes: a field28indicating the number of NSEs25in use in that name segment; a field29indicating the first free NSE in that name segment; and a bitmap30of starting entries, indicating which NSE(s) in that name segment include the beginning of a new filename. The NSE header26in a NSE25includes a field31containing the inode number of the file whose name is contained in this name segment; a field32containing the length of the filename; a field33indicating the next used NSE in this name segment (if applicable); a field34indicating the next free NSE in this name segment (if applicable), and a next-in-hash field35(if applicable).

An example of how this structure is used will now be provided. Assume someone creates a new directory, then creates a file named “my beautiful new file.txt” within it. If the new file is assigned inode #99, then the first name segment's contents will appear as follows:

The filename in this example is too long to store in a single NSE25, so the first 16 bytes of filename (“my beautiful new”) were stored in one NSE25, and the remaining text (“file.txt”) was stored in another NSE25. A filename can be up to 1000 characters in length in this embodiment, and so can consume all 63 NSEs25in a name segment23. Thus, a filename always resides entirely within a single name segment23, but can be split between NSEs25in a given name segment23.

At any time a given NSE25in a name segment23may or may not be in use. In order to add a new filename to a name segment23, the file system must be able to quickly find all of the NSEs25in that name segment that are unused. The file system does this by maintaining a free list pointer (“first free NSE”)29in the name segment header24of each name segment23. The free list pointer29is a value which is the index of the first unused NSE25within that name segment23. Further, each unused NSE25has, in its NSE header26, a pointer34to the next unused NSE, thus forming a chain of free NSEs25. When the file system needs to allocate one or more new NSEs25, it pulls them from the head of this free chain and then adjusts the name segment header's free list pointer29to skip those entries. Conversely, when removing a name from the directory, the file system simply adds the NSE(s)25which contained the name to the head of the free NSE chain.

In a typical directory21in a file server, there are many name segments23, which are in various states of being full of names or empty or somewhere in between. When the file system needs to add a new filename, it first has to find a name segment23(quickly) that can hold the filename. Therefore, in at least one embodiment of the invention, there are four free lists36-39, shown inFIG. 3, which keep track of which name segments23have some space available for storing filenames. If a name segment23is entirely full, it will not to appear on any of these four free lists; otherwise, it should show up on exactly one free list. The four free lists36-39include a first free list, “free-48”, representing name segments that have 48 or more free NSEs, a second free list, “free-24”, representing name segments that have 24 or more free NSE, a third free list, “free-4”, representing name segments that have four or more free NSEs, and a fourth free list, “free-1”, representing name segments that have at least one free NSE.

So for example, when adding a 45-character filename to a directory, the file system will require three NSEs (45/16, rounded up). Therefore, the file system accesses the first name segment23on the free-4 name segment free list; the file system knows that any name segments23on this free list have at least four free NSEs25(which is plenty for this example, since only three are needed). If the file system needed 18 NSEs, it would instead look at the free-24 free list, and so on.

Assume the file system found a name segment with six free NSEs: this name segment would have been listed on the free-4 free list (since it had at least four free NSEs, but less than 24 free NSEs). The file system consumes three NSEs to write the new filename, after which there are only three free NSEs left in that name segment. The name segment no longer qualifies, therefore, to be listed on the free-4 free list, so it is removed and reinserted at the front of the free-1 free list. The directory header also has a free list40, which threads together all the tree segments that are unused, so that it can quickly allocate a new tree segment later whenever it needs to.

FIG. 4shows an example of the format of a tree segment. The one or more tree segments41of a directory collectively form a radix tree, an example of which is shown inFIG. 9. The radix tree is an information set that is used to accelerate lookups of filenames in the directory. In certain embodiments of the invention, the radix tree for any directory has a maximum depth of three elements. The first tree segment41in a directory21is the root of the tree, and is designated as T1. Until the directory21becomes large, the root tree segment T1will be the only node in the tree.

As shown inFIG. 4, each tree segment41has a tree segment header42and a number (M) of pointers43, each of which can refer either to a filename (for example, “go to name segment5, NSE12”) or to another tree segment (for example, “go to tree segment72”), thus forming a recursive lookup tree. In certain embodiments of the invention, there are 510 pointers43in each tree segment41. Each pointer43contains a name/tree indicator44indicating whether the pointer43points to an NSE25or to another tree segment41; a segment number45indicating the index of the segment to which the pointer43points; and an offset46representing the NSE index if the pointer43points to an NSE25.

Referring now toFIG. 5, when looking up a filename, the file system first hashes the filename through a hashing function51. This operation produces, from the filename, a number with a high degree of distribution. For example, “hello” might hash to 1923810293, while only a slightly different name “hallo” might hash to412. The hash function51may be, for example, a CRC hash. In accordance with certain embodiments of the invention, the file system splits that resulting hash value52into three multi-bit parts of equal length: the lowest order P bits (where P is a predetermined number), the next-lowest-order P bits, and the highest-order P bits, representing three lookup values. The first lookup value (i.e., the highest-order P bits), “93” in the example ofFIG. 5, is used as an index into the root tree segment, T1(which resides in the first block of the directory). In this example, the root tree segment's pointer #93refers to name segment #5, NSE #12, which contains the filename “hello”. Once the filename is located in this way, the system returns the information the caller wanted for the filename.

It is possible for two filenames to receive the same hash values. For example, assume “hello” has “93” as its first hash value, but so does the filename “Bob”. Assume also that both of these filenames exist in the same directory. In that event, when attempting to look up the filename “Bob”, the root tree segment's pointer #93points to name segment #5, NSE #12, but name segment #5, NSE #12contains “hello”, not “Bob”. However, NSE #12also includes in its NSE header a “next-in-hash” field35(seeFIG. 2), which is a pointer to follow if the desired filename has not found in that NSE. In this example, the next-in-hash pointer in the NSE header for “Hello” points to name segment #6, NSE #7, which is where the filename “Bob” is found, as shown inFIG. 6. Thus, the “next-in-hash” pointers form a hash chain that the file system can follow until the desired filename is found.

Walking through a “hash chain” in this way is typically a very slow process. It is not desirable to have to do this often, because each time it is done it is necessary to jump around to a new name segment, read a name and compare it against the desired name. The radix tree structure of a directory becomes relevant in this regard, as will now be further explained.

A hash chain of names, such as mentioned above, is only allowed to grow to a predetermined depth, such as five names, for example. Thus, when the file system is about to add a sixth filename onto a hash chain, it reconsiders. As illustrated inFIG. 7, if the chain is hanging off the root tree segment T1, then the file system “splits” the hash chain; that is, the file system allocates a new tree segment41(labeled T7in this example), changes the applicable root tree segment's pointer (pointer #93in this example) to point to the new tree segment (T7), and then re-hashes the filenames that previously resided under that pointer. This action changes the radix tree from a single-level tree to a two-level tree (since the tree now includes two tree segments41). All of the filenames that end up using the new tree segment T7have the same first hash value (“93” in this example). Therefore, the second hash value (i.e., the middle-order P bits) is used instead to find these names.

Assume, for example, that the name “hello” has the value “2” as its second hash value—but the name “squee” has the value “55” as its second hash value, as shown inFIG. 7. Hence, in this second tree segment T7these two names do not collide. To look up “Bob” now, the file system will still start at the root tree segment T1. The file system consults pointer #93of tree segment T1, which points to tree segment T7. Therefore, the file system fetches tree segment T7and looks at its pointer #55. This pointer points to name segment #6, NSE #7, which contains the desired filename, “Bob”.

It is also possible to add enough filenames so that the chains on this two-level tree segment will become too long (e.g., more than five names). If that happens, the file system will split those chains in the manner described above to create a third-tier tree segment, keyed by the third hash value (i.e., the lowest-order P bits).

When names are removed from a directory, those names' hash values get removed from the tree segments41and corresponding hash chains. If the last entry from a tree segment41is removed, that tree segment41is then unused. The directory header has a free list40(FIG. 3), as mentioned above, which threads together all the tree segments41that are unused, so that it can quickly allocate a new tree segment41later whenever it needs to.

A technique for validating a directory21in accordance with the invention will now be further described with reference toFIGS. 8 through 11.FIG. 8illustrates the overall directory validation process performed by the file server122, according to certain embodiments of the invention. This process is repeated for each directory in the storage pool maintained by the file server122. The process may be initiated by a network administrator, for example, either directly at the file server122or from an administrative console (e.g., through a network). Alternatively, the process may be initiated automatically by the file server122, such as periodically or in response to a predetermined event or condition.

The process begins at block801with an initial scan. The initial scan includes validating all of the names in the directory21(e.g. making sure the filenames include no invalid characters) and building a table in memory to indicate the free list to which each segment is assigned (if any). The initial scan also performs basic testing on each tree segment, for example, to ensure that a tree segment has no pointers with illegal segment indices. The initial scan further builds in-memory counters of the number of names that are expected to hash underneath each tree segment. After the initial scan, the process verifies at block802that each segment is on the proper free list (based on the table created in801and the actual number of free entries in that segment).

At block803, the process tests all tree segments41in the directory21. A major purpose of this test is to determine whether the names in the directory are properly hashed (indexed) into the radix tree. In the prior art, this aspect of validation would be particularly susceptible to accumulated latency due to disk I/Os, as mentioned above. However, described below are further details of this part of the process which, in accordance with the invention, is designed to reduce such disk I/O latency. Also in block803, any “orphan” or duplicate filenames are identified and corrected. An “orphan” filename is a filename which has not yet been assigned a hash value. If any orphan filenames are found, they are hashed and added to a tree segment. Duplicate filenames generally result in rebuilding the directory.

In accordance with embodiments of the invention, during block803, the directory's radix tree is divided up (logically) to define two or more subsets of the radix tree.FIG. 9shows a radix tree91for a directory, which has been divided up to form three subsets92(the name segments to which each tree segment41points are not shown). Each subset92is defined as including one or more tree segments41. The subsets92are defined based on the number of names under each tree segment41. More specifically, the subsets92are defined so that, for each subset92, all of the information required to perform block803of the validation process on all names within that subset, can be stored at one time in main memory of the file server122(considering the amount of space available in main memory). The size and content of each subset92is generally chosen so as to make full use of the available space in main memory, without exceeding that available space.

The term “main memory”, as used herein, means the primary memory from which software currently executing in the file server122is executed or in which data currently being processed by the file server are normally stored. Main memory is normally a form of random access memory (RAM), although it is possible for other types of memory to be used as main memory. Main memory is to be distinguished from secondary storage, e.g., the storage subsystem (e.g., disks) used for the storage pool and/or for long-term storage of software and data.

In accordance with the invention, it is recognized that validating name hashing (in block803of the validation process) does not require the actual names or any portions thereof as input. All that is needed for purposes of this test are, for each name to be tested: the NSE index of the first NSE used by the name, the hash value of the name, and the next-in-hash pointer associated with the name (if applicable). Neither the actual name nor any portion thereof is needed for purposes of verifying the correct hashing. Accordingly, it is unnecessary and wasteful to load an entire name segment into main memory, for purposes of validating the hashing of a particular name.

Accordingly, for each name in a directory21, a special object is created to store the above-mentioned information needed for validating the name's hashing (block803). Each such object is referred to herein as a “name info object”, an example of which is illustrated inFIG. 10. A name info object101includes a distillation of the information about a name which is needed to validate the name's hashing. As shown inFIG. 10, this distillation includes: 1) the NSE index102of the first NSE25used to store the name; 2) the hash value103of the name (that is, the entire hash value generated by the hashing function51, i.e., the highest P bits, the middle P bits and the lowest P bits); and 3) the next-in-hash pointer104of the name (if any). Validation of the hashing of a name involves simply verifying that the hash value103in the name's name info object101matches the hash value of the tree segment under which it resides.

As shown inFIG. 10, a name info object101also contains other information which is used to facilitate other types of testing. This other information includes a second hash value105, referred to as the orthogonal (“ortho”) hash value105, and a flag106. As described further below, the ortho hash value105is used to facilitate detection of duplicate names in a directory. The flag106is used to detect loops in a hash chain and “orphan” filenames.

For purposes of validating name hashing (in block803ofFIG. 8), the name info objects101are stored in main memory107of the file server122, and only the name info objects are used to validate name hashing; entire name segments23are not loaded into main memory107from disk for this purpose, nor are the actual names or any portions thereof.

A name info object101consumes a known amount of memory space. Assuming the size of main memory107is known and the minimum available space in main memory107can be reliably predicted for the file server122, it is straightforward to determine the maximum number of names for which block803can be performed at a time (based on the amount of space that would be consumed by their corresponding name info objects101in main memory107). It is possible, therefore, to optimize usage of main memory107while reducing disk I/Os, for purposes of validating name hashing.

Specifically, construction of name info objects101involves performing disk I/Os in order to iteratively enumerate every segment in the directory. Thus, dividing the directory (i.e., the radix tree91) into subsets92would tend to require more disk I/Os (to test all of the subsets) than if the entire directory were loaded into main memory107. To reduce the number of required I/Os, therefore, the radix tree91is divided into as few subsets92as possible, and each subset92is made as large as possible, where the size of each subset92is bounded by the amount of memory required to hold the name info objects for all of the names in that subset. By reducing the number of disk I/Os required to test most directories, therefore, this approach reduces overall disk I/O latency for, and shortens the duration of, the overall validation process.

Referring still toFIGS. 9 and 10, each name info object101is hashed, using a hashing function108, according to the index of the first NSE used to store that name. When performing block803, only one subset92of the radix tree91is tested at a time. The name info objects101of all names belonging to a selected subset92are created and stored in main memory107of the file server, and the test is then performed based on that information, without any need to perform any further disk I/Os to test the names in the selected subset92. When the next subset92is tested, the name info objects101for all the names under that subset92are created and stored in main memory107and then used to perform the test in a similar manner; and so forth, until all subsets92of the radix tree91have been tested. This process can then be repeated for other directories.

As noted above, each name info object101also includes an “ortho” hash value105and a flag106. The ortho hash value105is a hash value which results from applying to the filename a hash function different from hash function51described above. For example, if the filename is hashed using CRC to produce hash value103, then ELF hashing may be used to produce the ortho hash value105. The hash value103and the ortho hash value105are used together to facilitate identifying duplicate filenames, as described further below.

The flag106is used to detect orphaned filenames and to detect loops in the next-in-hash chain, as described below. The flag is set whenever a name's hashing is tested. If the testing process encounters a name info object101whose flag106is already set before the hashing is tested, this indicates a loop exists in the next-in-hash chain.

FIGS. 11A,11B and11C show the process of block803in greater detail, according to certain embodiments of the invention. Initially, at block1101the process counts the number of names under each tree segment in the directory. Next, at block1102the process groups the radix tree of the directory into multiple subsets in the manner described above (i.e., based on the number of names in each tree segment, memory required, and available memory), assuming the directory is large enough to make dividing it up worthwhile. If the directory is very small, it may not be necessary or desirable to break the radix tree into subsets.

The process next selects one of the defined subsets of the radix tree at block1103and, for the selected subset, selects a name in the directory at block1104. The process then hashes the name using the primary hash function at block1105. The process then determines at block1106whether the name belongs to the currently selected subset, based on the name's hash value. If the name belongs to the currently selected subset, the process then builds a name info object for this name in main memory at block1107, and the process then continues from block1108. Otherwise, the process bypasses block1107and continues from block1108. The subprocess represented by blocks1105through1108is then repeated for each name in the directory, until all names in the directory have been processed in this way (see blocks1108and1124).

After all names in the directory have been processed as described above, the process continues from block1109, in which a tree segment in the currently selected subset is selected. Next, at block1110the process selects a pointer in the selected tree segment. If the pointer points to a name (block1111), which can be determined from the name/tree field44(FIG. 4), then the process continues from block1112. If the pointer does not point to a name, then the process loops back to block1110to select the next pointer in the currently selected tree segment.

If the pointer points to a name, then in block1112the process gets the name info object associated with the pointer from main memory (based on the index value of the first NSE of the name, which is stored in the name info object). The process then determines at block1113if the flag106in that name info object is set. If the flag106is set, it means that this name info object has already been seen during this validation testing, which means there is a loop in the current hash chain. In that event, the directory is rebuilt from scratch at block1125, and the process then ends.

If the flag106is not set, the process continues with block1114. Block1114is where the name's hashing is actually validated. At block1114, the process determines whether the primary hash value103in the selected name info object matches the hash value of the currently selected tree segment. If there is no match, then an error has been detected; in that event the directory is rebuilt from scratch at block1125.

If the hash values match, however, then the hashing for this name is determined to be valid. In that case, at block1115the process then sets the flag106in the name info object in main memory. Any name for which the flag106is not set in its name info object at the end of this process is considered to be an orphan filename. Any orphan filenames are identified and hashed into the radix tree at the end of this process.

After setting the flag106, at block1116the process records an entry for the current name in a data structure, referred to as the duplicates filter, which is used to facilitate detection of duplicate names in a directory, as described further below. The duplicates filter is a table that records the ortho hash values105that have been seen while processing a given hash chain. The duplicates filter is only valid while a particular hash chain is being tested, after which it is discarded (cleared).

The duplicates filter is divided into a number of “buckets” (entries), indexed according to the ortho hash values105of the names that are tested in a given hash chain. Hence, any two name info objects which have the same ortho hash value105will be represented in the same bucket of the duplicates filter. The entry recorded in the duplicates filter at block1116includes the index value of the first NSE of the name being tested. The use of the duplicates filter is described further below.

The subprocess represented by blocks1112through1116is then repeated until all name info objects in the hash chain for the selected pointer have been processed (see blocks1117and1126). This is accomplished by following the next-in-hash pointer104(if any) in the name info object101after checking the hashing of each name.

After each name in the current hash chain has been processed, then at block1118the process transfers information regarding possible duplicate names (if any) from the duplicates filter into another data structure, referred to as the duplicates list. As noted above, any two name info objects from a given hash chain which have the same ortho hash values105will be represented in the same bucket of the duplicates filter. Therefore, at block1118, for any bucket in the duplicates filter which contains more than one NSE index, the NSE indices in that bucket are stored in the duplicates list, after which the duplicates filter is discarded. The duplicates filter is only valid for a particular hash chain, however, the duplicates list may remain valid for the entire directory. The contents of the duplicates list are used in block1122to actually detect duplicate names, as explained below.

After block1118, the aforementioned operations are further repeated until all pointers in the selected tree segment have been processed (see blocks1119and1127), and further until all tree segments in the selected subset have been processed (see blocks1120and1128), and still further until all subsets in the radix tree have been processed (blocks1121and1129).

After all subsets of the radix tree have been processed, at block1122the names corresponding to the entries on the duplicates list (if any) are examined to detect any actual duplicates. This operation requires reading the actual names from disk. Consequently, to minimize the number of required disk I/Os, this operation preferably is done once for the entire directory. If no duplicate names are detected (block1123), the process ends. If any duplicate names are detected (block1123), the directory is rebuilt at block1125, and the process then ends.

As noted above, the above described process further can be performed on other directories in the storage pool.

Also as noted, the above-described directory validation technique can be implemented by a file server122.FIG. 12shows a simple example of a network environment which incorporates the file server122. The file server122is coupled locally to a storage subsystem124which includes a set of mass storage devices, and to a set of clients121through a network123, such as a local area network (LAN). Each of the clients121may be, for example, a conventional personal computer (PC), workstation, or the like. The storage subsystem124contains the storage pool managed by the file server122. The file server122receives and responds to various read and write requests from the clients121, directed to data stored in or to be stored in the storage subsystem124. The mass storage devices in the storage subsystem124may be, for example, conventional magnetic disks, optical disks such as CD-ROM or DVD based storage, magneto-optical (MO) storage, or any other type of non-volatile storage devices suitable for storing large quantities of data.

The file server122may have a distributed architecture; for example, it may include a separate N-(“network”) blade and D-(data) blade (not shown). The N-blade is used to communicate with clients121. The D-blade includes the file system functionality and is used to communicate with the storage subsystem124. The N-blade and D-blade communicate with each other using an internal protocol. Alternatively, the file server122may have a monolithic architecture, such that the network and data components are all contained in a single box. The file server122further may be coupled through a switching fabric to other similar file servers (not shown) which have their own local storage subsystems. In this way, all of the storage subsystems can form a single storage pool, to which any client of any of the file servers has access.

FIG. 13is a block diagram showing the architecture of the file server122, according to certain embodiments of the invention. Certain standard and well-known components which are not germane to the present invention may not be shown. The file server122includes one or more processors131and memory132coupled to a bus system133. The bus system133is an abstraction that represents any one or more separate physical buses and/or point-to-point connections, connected by appropriate bridges, adapters and/or controllers. The bus system133, therefore, may include, for example, a system bus, a Peripheral Component Interconnect (PCI) bus, a HyperTransport or industry standard architecture (ISA) bus, a small computer system interface (SCSI) bus, a universal serial bus (USB), or an Institute of Electrical and Electronics Engineers (IEEE) standard 1394 bus (sometimes referred to as “Firewire”).

The processors131are the central processing units (CPUs) of the file server122and, thus, control the overall operation of the file server122. In certain embodiments, the processors131accomplish this by executing software stored in memory132. A processor131may be, or may include, one or more programmable general-purpose or special-purpose microprocessors, digital signal processors (DSPs), programmable controllers, application specific integrated circuits (ASICs), programmable logic devices (PLDs), or the like, or a combination of such devices.

Memory132is or includes the main memory107of the file server122. The memory132represents any form of random access memory (RAM), read-only memory (ROM), flash memory, or the like, or a combination of such devices. Memory132stores, among other things, the operating system134of the file server122, in which the validation techniques introduced above can be implemented.

Also connected to the processors131through the bus system133are one or more internal mass storage devices135, a storage adapter136and a network adapter137. Internal mass storage devices135may be or include any conventional medium for storing large volumes of data in a non-volatile manner, such as one or more disks. The storage adapter136allows the file server122to access the storage subsystem124and may be, for example, a Fibre Channel adapter or a SCSI adapter. The network adapter137provides the file server122with the ability to communicate with remote devices such as the clients121over a network and may be, for example, an Ethernet adapter.

FIG. 14shows an example of the operating system of a file server that may be used to implement techniques described above. As shown, the operating system134of the file server122includes several modules, or layers. These layers include a file system141, which executes read and write operations on the disks in the storage subsystem134in response to client requests, maintains directories of stored data, etc. “Under” the file system1411(logically), the operating system134also includes a network access layer142and an associated media access layer143, to allow the file server2to communicate over a network (e.g., with clients1). The network access142layer may implement any one or more of various protocols, such as NFS, CIFS, HTTP and/or TCP/IP. The media access layer143includes one or more drivers which implement one or more protocols to communicate over the network, such as Ethernet.

Also logically under the file system141, the operating system134includes a storage access layer144and an associated driver layer145, to allow the file server122to communicate with the storage subsystem124. The storage access layer144implements a disk storage protocol such as RAID, while the driver layer145implements a lower-level storage device access protocol, such as Fibre Channel Protocol (FCP) or SCSI. Also illustrated inFIG. 14is the path147of data flow through the operating system134, between a client121and the storage subsystem124. The details of the above-mentioned layers of the operating system134are not necessary for an understanding of the invention and, hence, need not be described herein.

The operating system134further includes a directory utility146, which implements the directory validation functionality described above. The directory utility146has access to the storage subsystem124through the storage driver layer145.

Note that the directory validation technique introduced herein is not limited in application to file servers. For example, the technique can be adapted for use in other types of storage servers, such as block based storage servers or processing systems other than storage servers. Furthermore, the technique introduced herein can be adapted for purposes other than validation of directories. A virtual phone book is one possible example: Fast lookup of a particular name in an electronic phone book could be implemented by using a large radix tree, and the names of individuals in the phone book could be tested to ensure they are properly hashed into the tree by using the algorithm introduced above or an adaptation thereof. It will be recognized that many other applications of the present invention are possible.

Thus, a method and apparatus for testing a directory of information stored in a storage server have been described. Although the present invention has been described with reference to specific exemplary embodiments, it will be recognized that the invention is not limited to the embodiments described, but can be practiced with modification and alteration within the spirit and scope of the appended claims. Accordingly, the specification and drawings are to be regarded in an illustrative sense rather than a restrictive sense.