Method, apparatus and computer program product for file system referrals

[0002] 1. Field of the Invention

[0003] The present invention relates to file systems, and more particularly to storing file system referrals.

[0004] 2. Related Art

[0005] Computer based information storage systems, such as databases and file systems have been widely utilized by users to access, store, modify and update persistent data. For many companies, the information storage system is considered to be a strategic capital asset that is deployed to make everyday business decisions. Persistent data may include computer files such as source code, word processing documents, data elements and information such as employee records, customer records, and content of web pages.

[0006] In a computer system, a file system defines the manner in which files are named and placed logically for storage and retrieval. Generally many file systems provide a hierarchical (tree) structure for managing files. A file is placed in a directory (or a folder or subdirectory) at the desired place in the tree structure. In the file system that is organized as a hierarchy, the root directory may include sub-directories that may include other sub-directories. Typically, a tree file system has only one root. In many operating systems, the root directory has no name. A special character that separates directories in a file system typically represents the root directory. For example, in UNIX-based systems, the root directory is represented simply as: /, and in Windows operating system, the root directory is represented as: \.

[0007] A path is the route from the root directory of a file system to a particular file. A pathname (or path name) is the specification of that path. A file system also includes a format for specifying a path to a file through the structure of directories. Well known examples of file systems include UNIX file system (“UFS”), Windows NT file system (“NTFS”), Distributed File System (“DFS”), Network File System (“NFS”) and the Andrew file system (“AFS”).

[0008] Referring to FIG. 1, a referral object 105, or simply “referral”, is used to link together multiple file system trees into a single global name space. Referral 105 is a special object in a referring file system, e.g., file system FS1110, which includes information to identify a referred file system, e.g., file system FS2120. The information included in referral 105 may describe a server location and the path of the referred file system, and it may describe the information that a user application may need in order to access the referred file system, e.g., root of FS2120. In some cases, the information included in referral 105 may include a key into a database, which then provides the server location and path of the referred file system. In a client/server architecture, referral 105 is used to redirect a client's request to another server. Referring to FIG. 2, referral 105 is replaced for the user application by the root of the referred file system, e.g., root of FS2120, when accessed by a user application 210. A global single name space 200 is formed when the replacement is made.

[0009] It is often the case that file systems need to support looking up parent directories of a specified object, e.g., lookup the directory that includes the specified object. One example of the use of a lookup function is to construct an absolute path name for the specified object. The absolute path name is determined by climbing up the name space hierarchy using successive parent directory lookups until reaching the root of the name space. As another example, a server complying with NFS v4 functionality has a need to lookup the parent of an object when processing a LOOKUPP remote procedure call.

[0010] When global name space 200 is formed by using referrals, the parent directory of the root of a file system, as viewed by user application 210, may be located in a different file system, perhaps even on a different server. In addition, multiple referrals may refer to the same file system thus, when looking up a parent directory, the system should return a unique name. It is desirable that the name of the root directory be preferably returned as the name of the referral object referring to the root directory.

[0011] The foregoing need is addressed by the present invention. According to one form of the invention, in a method for making file systems accessible, a referring file system attribute is created, responsive to a first file system having a referral object referring to a second file system. An “attribute” may be a field of a database record in a database context, for example, a property of an object in an object-oriented programming context, or an attribute of an element in a markup language context. A “data element” may be a record, for example, an object, or an element.

[0012] The referring file system attribute describes referring file system identification for the first file system. A path attribute is created, responsive to the first file system having the referral object, describing a path from a root of the first file system to the referral object. A referred file system attribute is created, responsive to the first file system having the referral object, describing a referred file system identification for the second file system. A parent attribute is created, responsive to the first file system having the referral object, describing a parent flag for the second file system.

[0013] In another aspect, the file systems are accessible within a global name space. Data elements having the attributes are configured for respective referral objects within the global name space and stored in a database. A dummy data element, describing a dummy referral to a root file system of the global name space, is stored in the database.

[0014] In yet another aspect of the invention a method to locate a parent directory of a second referral object includes receiving a request to locate the parent directory, the second referral object being located in a second referred file system. The database is searched for an entry matching the second referred file system. An entry matching the second referred file system is selected, wherein the entry has the parent attribute set to a true status.

[0015] Objects, advantages and other forms of the invention will be apparent upon reading the following detailed description and referring to the accompanying drawings.

[0016] FIG. 1, described above, is a block diagram illustrating a referral object used to link together multiple file system trees, according to the prior art.

[0017] FIG. 2, described above, is a block diagram illustrating replacement of the referral object by the root of the referred file system, according to the prior art.

[0018] FIG. 3A is a data element having a plurality of attributes, according to an embodiment of the present invention.

[0019] FIG. 3B is a flow chart illustrating a method for making a number of file systems accessible, according to an embodiment of the present invention.

[0020] FIG. 4 is a flow chart illustrating a method of preparing a database for facilitating the accessibility of the number of file systems, according to an embodiment of the present invention.

[0021] FIGS. 5A, 5B and 5C illustrate an example of creating a database that facilitates accessing a number of file systems included in global name space, according to an embodiment of the present invention.

[0022] FIG. 6 is a flow chart illustrating a method a flow chart illustrating a method of managing the database, according to an embodiment of the present invention.

[0023] FIG. 7 illustrates a computer system to implement method or apparatus aspects of the present invention, according to an embodiment.

[0024] The claims at the end of this application set out novel features which applicant believes are characteristic of the invention. The invention, a preferred mode of use, objectives and advantages, will best be understood by reference to the following detailed description of an illustrative embodiment read in conjunction with the accompanying drawings.

[0025] Referring to FIG. 3A, a data element 350 is illustrated, according an embodiment of the present invention. This data element 350 is created (or defined) to facilitate access to a number of file systems. Data element 350 has a number of attributes, e.g., a referring file system attribute 360, a path attribute 370, a referred file system attribute 380, a parent attribute 390.

[0026] Referring to FIG. 3B, a flow chart is shown illustrating a method for making a number of file systems accessible, in accordance with the present invention.

[0027] In block 310, referring file system attribute 360 of data element 350 is created in response to referral object 105, e.g., a first one of the file systems having a first referral object referring to a second one of the file systems. Referring file system attribute 360 describes a first referring file system identifier, e.g., FS1100, for the first one of the file systems. The first referring file system identifier uniquely identifies the first referring file system in global name space 200.

[0028] In block 320, path attribute 370 of data element 350 is created, responsive to the first one of the file systems having the first referral object. Path attribute 370 describes a first path information for the first referral object. The first path information describes a path from the first one of the file systems root to the first referral object.

[0029] In block 330, referred file system attribute 380 of data element 350 is created, responsive to the first file system having the first referral object. Referred file system attribute 380 describes a first referred file system identifier, e.g., FS2120, for the second one of the file systems. The first referred file system identifier uniquely identifies the first referred file system in global name space 200.

[0030] In block 340, parent attribute 390 of data element 350 is created, responsive to the first file system having the first referral object. Parent attribute 390 describes a first parent flag for the second one of the file systems. Parent attribute 390 is assigned a binary value, e.g., true or false, depending on the parent/child relationship between the first referring file system, e.g., FS1110, and the first referred file system, e.g., FS2120. For example, a true status for the first parent flag indicates that the first referring file system is the principal parent of the first referred file system. The parent flag is created to provide a unique, distinguished parent, by analogy with a biological parent, for the root of the file systems in case more than one referral exists for a file system.

[0031] Blocks 310-340 described above are combinable into a single block 300 for creating data element 350 structure having a plurality of attributes. In one embodiment, data element 350 may include additional attributes such as time of referral object creation, or an identification of the user who created the referral. Additional blocks may be added to blocks 310-340 to create these attributes.

[0032] Referring now to FIG. 4, a flow chart illustrating a method of preparing a database for facilitating the accessibility of the number of file systems, in accordance with the present invention, is shown. The number of file systems in global name space 200 includes a plurality of referral objects.

[0033] In block 300, data element 350 structure is defined as described in blocks 310-340 of FIG. 3B. In block 420, data elements are configured for respective referral objects within the global name space. Data element 350 corresponding to each referral object, e.g., referral 105, is said to be configured when each of the attributes described in blocks 310-340 have been assigned a value in response to referral object 105. All data elements are configured for respective referral objects within global name space 200. A dummy data element is configured describing a dummy referral to a root file system of the global name space.

[0034] In block 430, all data elements are stored in a database. The database is indexed by the referring file system, or by the referred file system or by both. In block 440, the database is managed by executing functions such as adding new data elements, deleting existing data elements or modifying existing data elements.

[0035] Referring now to FIGS. 5A, 5B and 5C, an example of creating a database that facilitates accessing a number of file systems included in global name space 200, in accordance with the present invention, is shown. Referring to FIG. 5A, a tree structure of file systems FS1110, FS2120 and FS3130 having a plurality of referrals, e.g., referrals 510, 520 and 530, is shown. In the tree for FS1110, path /B refers to object FS1OB1550. Path /A/C refers to referral object 510, which refers to file system FS3130. Path /A/D refers to referral object 520, which refers to file system FS2120. In the tree for FS2120, path /F refers to object FS2OB1555. Path /E refers to referral object FS3130. In the tree for FS3130, path /G refers to object FS3OB1560, path /H refers to object FS3OB2565 and path /I refers to object FS3OB3570.

[0036] Referring to FIG. 5B, user application 210 accessing a file system included in global name space 200 is shown. FS1110 is the root file system in global name space 200. The root of the referred file system, e.g., FS2120 and FS3130, has replaced referral objects 510 and 520. Referring to FIG. 5C, a database 500 created to describe global name space 200, in accordance with the present invention, is shown. A dummy entry 580 in database 500 is a special entry since it refers to the highest file level of global name space 200, e.g., FS1110. In dummy entry 580, referring file system attribute 360 is described by a special referring file system identifier, e.g., *ROOT*. An identifier for the top-level file system, e.g., FS1110, is entered as the attribute value for referred file system attribute 380. Parent attribute 390 for the dummy entry is set to TRUE. The principal parent flag is used to provide a unique parent for the root of file systems in case more than one referral exists for a file system. Maintaining integrity of the status of parent flag is desirable to provide assurance that each referred file system has one and only one principal parent, e.g., a referral for which the principal parent flag is set to a TRUE status. For example, root of FS3 object has two parents. Object C is a referral from parent object FS1OB2 to root of FS3. Object E is a referral from parent object root of FS2 to root of FS3. Thus root of FS3 object is referred to by multiple file systems. That is, 2 referring file systems, e.g., FS2120 and FS1110, refer to file FS3130. It may be possible that in global name space 200, path /A/C/G and path /A/D/E/G refer to the same object FS3OB1560. However, as described in data element 590, FS1110 is the only principal parent of FS3130 since the parent flag attribute is set to TRUE.

[0037] Referring now to FIG. 6, a flow chart illustrating a method of managing the database, in accordance with the present invention, is shown. In one embodiment, managing the database includes adding a new data element, deleting an existing data element or modifying an existing data element of database 500.

[0038] In block 610, a determination is made whether a data element exists in database 500 for a new referral object. In block 620, a new data element is configured corresponding to the new referral object in response to the new referral object. When a new referral is created, the data element corresponding to the referral is configured as described in block 420 of FIG. 4. The method of configuring and adding new data elements to database 500 may be performed by a special utility program that manipulates referrals.

[0039] In block 630, whenever a referral is configured and added to database 500, a check is made to see if there are other entries in the database that include referrals to the same file system. A determination is made if the referral added is not a first referral to this file system. If it is the first referral, the principal parent flag in the new referral is set to TRUE in block 640. Otherwise it is set to FALSE in block 650.

[0040] In block 660, a determination is made whether the referral object is to be deleted. In block 670, when a referral is deleted from the database, then if the principal flag is set to TRUE, and there are other entries that refer to the same file system, one of those referrals is selected to be the new principal. The selection may be based on criteria such as a chronology of referral creation. Following these procedures will assure that there will always be one and only one principal parent to each referred file system. The special utility program may modify the principal parent flag of file systems. In block 680, an existing data element is modified in response to a change in the referral object.

[0041] Database 500 (FIG. 5C) may be utilized to perform a variety of functions. These functions advantageously facilitate in accessing file systems included in global name space 200. For example, looking up parent directories of the root of a file system in global name space 200 is possible by looking in the database 500, and searching for an entry for a referral that refers to the file system in question. If there is more than one entry that matches the referred site, then the referral, which has the principal parent flag set to a TRUE status, is selected. The database also supports the name resolution of file system roots, which should be returned as the name of the referral object.

[0042] For example, database 500 is accessed to look up the parent of the root of file system FS3130. Two entries 590 and 595, in database 500 match referred site FS3130. However, only one entry 590 has a principal parent flag set to a TRUE status. The referring file system is FS1110 and path is /A/C. Database 500 returns referral object A as the parent of FS3. Referral object C is the name of FS3130 root.

[0043] In one embodiment, database 500 is accessed to allow an administrator or a user to browse and view global name space 200 at the file system level, by visualizing a graph of global name space 200 in which each node is a file system and a directed link between file systems corresponds to a referral. In another embodiment, database 500 is accessed to search for unreachable file systems, e.g., file systems that have no referrals. It may be advantageous to reclaim storage by deleting all nodes that may not be reachable from the root file system. In yet another embodiment, database 500 is accessed to enforce non-circular definitions of referrals. For example, a circular definition may exist when file system A is referred by file system B, which in turn is referred by file system A. In order to prevent an occurrence of an infinite loop while looking up a parent directory, the search may be limited to a finite number of iterations.

[0044] Referring to FIG. 7, a computer system 710 is shown that is generally applicable for the various embodiment described according to the present invention. The system 710 includes a processor 715, a volatile memory 720, e.g., RAM, a keyboard 725, a pointing device 730, e.g., a mouse, a nonvolatile memory 735, e.g., ROM, hard disk, floppy disk, CD-ROM, and DVD, and a display device 705 having a display screen. Memory 720 and 735 are for storing program instructions that are executable by processor 715 to implement various embodiments of a method in accordance with the present invention. Components included in system 710 are interconnected by bus 740. A communications device (not shown) may also be connected to bus 740 to enable information exchange between system 710 and other devices.

[0045] In various embodiments system 710 takes a variety of forms, including a personal computer system, mainframe computer system, workstation, Internet appliance, PDA, an embedded processor with memory, etc. That is, it should be understood that the term “computer system” is intended to encompass any device having a processor that executes instructions from a memory medium. The memory medium preferably stores instructions (also known as a “software program”) for implementing various embodiments of a method in accordance with the present invention. In various embodiments the one or more software programs are implemented in various ways, including procedure-based techniques, component-based techniques, and/or object-oriented techniques, among others. Specific examples include XML, C, C++, Java and Microsoft Foundation Classes (MFC).

[0046] The description of the present embodiments have been presented for purposes of illustration, but are not intended to be exhaustive or to limit the invention to the forms disclosed. Many additional aspects, modifications and variations are also contemplated and are intended to be encompassed within the scope of the following claims. For example, while certain aspects of the present invention have been described in the context of a fully functioning data processing system, those of ordinary skill in the art will appreciate that the processes of the present invention are capable of being distributed in the form of a computer readable medium of instructions in a variety of forms. The present invention applies equally regardless of the particular type of signal bearing media actually used to carry out the distribution. Examples of computer readable media include RAM, flash memory, recordable-type media such as a floppy disk, a hard disk drive, a ROM, CD-ROM, DVD and transmission-type media such as digital and/or analog communication links, e.g., the Internet.

[0047] To reiterate, many additional aspects, modifications and variations are also contemplated and are intended to be encompassed within the scope of the following claims. Moreover, it should be understood that in the following claims actions are not necessarily performed in the particular sequence in which they are set out.