Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2001-06-28
2004-07-27
Metjahic, Safet (Department: 2171)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000
Reexamination Certificate
active
06768993
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Technical Field
The present invention relates to managing extended file attributes. More particularly, the present invention relates to a system and method for locking file system pages when using file system extended attributes.
2. Description of the Related Art
Operating systems, such as the UNIX operating system, use a file system for managing files. UNIX uses a hierarchical directory structure for organizing and maintaining files. Access permissions correspond to files and directories. The UNIX operating system organizes files into directories which are stored in a hierarchical tree-type configuration. At the top of the tree is the root directory which is represented by a slash (/} character. The root directory contains one or more directories. These directories, in turn, may contain further directories containing user files and other system files.
The fundamental structure that the UNIX operating system uses to store information is the file. A file is a sequence of bytes. UNIX keeps track of files internally by assigning each file a unique identification number. These numbers, called I-node numbers, are used only within the UNIX kernel itself. While UNIX uses i-node numbers to refer to files, it allows users to identify each file by a user-assigned name. A file name can be any sequence of characters and can be up to fourteen characters long.
There are three types of files in the UNIX file system: (1) ordinary files, which may be executable programs, text, or other types of data used as input or produced as output from some operation; (2) directory files, which contain lists of files in directories outlined above; and (3) special files, which provide a standard method of accessing input/output devices.
Internally, a directory is a file that contains the names of ordinary files and other directories and the corresponding i-node numbers for the files. With the i-node number, UNIX can examine other internal tables to determine where the file is stored and make it accessible to the user. UNIX directories themselves have names, examples of which were provided above, and can be up to fourteen characters long.
UNIX maintains a great deal of information about the files that it manages. For each file, the file system keeps track of the file's size, location, ownership, security, type, creation time, modification time, and access time. All of this information is maintained automatically by the file system as the files are created and used. UNIX file systems reside on mass storage devices such as disk drives and disk arrays. UNIX organizes a disk into a sequence of blocks. These blocks are usually either 512 or 2048 bytes long. The contents of a file are stored in one or more blocks which may be widely scattered on the disk.
An ordinary file is addressed through the i-node structure. Each i-node is addressed by an index contained in an i-list. The i-list is generated based on the size of the file system, with larger file systems generally implying more files and, thus, larger i-lists. Each i-node contains thirteen 4-byte disk address elements. The direct i-node can contain up to ten block addresses. If the file is larger than this, then the eleventh address points to the first level indirect block. Addresses
12
and
13
are used for second level and third level indirect blocks, respectively, with the indirect addressing chain before the first data block growing by one level as each new address slot in the direct i-node is required.
In addition to the standard information maintained by the file system for a particular file, metadata, or extended attributes, about the file are often needed by an application that uses the file. Because extended attributes vary greatly, depending on the type of application and the type of metadata to be maintained, this information is typically stored outside the standard i-node attribute data area. For example, a word processing application may need to store information regarding the document, such as profile information entered by a user. While this information is not stored with the document file, it needs to be in a related storage area for efficient processing by the application. Traditionally, extended attributes are stored in specific fields that are allocated for the attributes. The fields may store the actual extended attribute data or may store a pointer to another storage area containing attribute data that will not fit in the allocated space.
One challenge found in traditional systems is that a fixed allocated space for the extended data limits the amount of data that can be stored. When more extended data is needed, a pointer is stored in the allocated space which points to a separate data stream. Updating data stored in a separate data stream is inefficient because the separate extended attribute data stream is reconstructed in response to a change in the size of the attribute data. A further challenge exists in retrieving summary information regarding the extended attributes. Summary information is gathered by analyzing each substring within the extended attribute data stream causing further file processing inefficiencies.
What is needed, therefore, is a way of efficiently adding, modifying, or deleting extended attribute data without needing to reconstruct complex data streams each time the extended attribute size is modified. Placing extended attribute data in extended attribute pages that correspond to dinode attribute pages, however, creates additional challenges.
Files with information stored in a particular dinode page need not have any relationship or similarities other than being maintained within a common dinode page by the file system. Because the dinode page corresponds to a particular extended attribute page it is possible for two dinodes in the same dinode page to each create a dinodex (extended attribute) page at virtually the same time. In addition, if two dinodes attempt to delete their extended attributes at virtually the same time it is possible that neither dinode will realize that the dinodex page is empty and should be released. Other permutations are also possible that create additional challenges when unrelated dinodes share a common dinode page and a common dinodex page.
What is needed, therefore, is a concurrency control algorithm to ensure cooperation between dinodes in using common extended attribute pages in a multi-process, multi-threaded environment.
SUMMARY
It has been discovered that an additional field lock applied to the extended attribute address field maintained in a dinode page provides two level cooperation between dinodes. In a dinode data area, one field is used to store extended attribute summary information. This extended attribute summary information includes an address of a dinodex page that corresponds to the dinode. If the dinode does not have extended attribute data its extended attribute page address is zero. On the other hand, if the dinode has extended attribute data, its address is the address of the dinodex page. Each dinode within the same dinode page that uses extended attribute data will have the same dinodex page address because one dinodex page corresponds with the dinode page.
A new page lock (called an “EA Lock”) is implemented for each dinode page. Insertion, deletion, or update of the extended attribute data requires the dinode to acquire the EA Lock before the operation is performed. The EA Lock does not effect other dinode page operations, such as reading and writing dinodes in the same dinode page for fields other than the EA address field. Limiting the operations that involve the EA Lock provides for a small lock granularity so that few activities are blocked by the lock and system throughput is adequately maintained.
The foregoing is a summary and thus contains, by necessity, simplifications, generalizations, and omissions of detail; consequently, those skilled in the art will appreciate that the summary is illustrative only and is not intended to be in any way limiting. Other aspects, inventive features, and advantages of the pres
Chang Joon
Shi Amy Yi-mei
Goddard Brian
Leeuwen Joseph T. Van
Roberts Diana L.
LandOfFree
System and method for file system cooperation in a... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for file system cooperation in a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for file system cooperation in a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3237616