Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2000-02-14
2003-08-12
Robinson, Greta (Department: 2177)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000
Reexamination Certificate
active
06606628
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates in general to memory devices, and more particularly file systems suitable for use with nonvolatile memories.
2. The Background Art
As is known to those skilled in the art, numerous file system implementations have been developed. Most file systems known in the art have been developed with the assumption that the files would be stored on a magnetic disk or—in the case of data networking implementations—on a magnetic disk attached to a network file server (“NFS”). Typically, files are divided into data blocks, and these blocks are laid out on the disk in which the files are to be stored. The layout of the blocks on the disk is typically optimized for minimizing the access time for file blocks stored on these disks. These file systems are normally very large, and hence very efficient file searching strategies have been developed.
Most file systems known in the art assume that a complex directory structure will be imposed on the files, and hence complex data structures have typically been required to handle them. However, other file systems known to those skilled in the art store files in a contiguous fashion. For example, on some types of nonvolatile memory, such as flash memory media, files are typically stored in a contiguous fashion on the flash card containing the flash memory. In such a flash memory medium, there is typically no concept of “file blocks” involved. As known to those skilled in the art, however, flash media has its own peculiarities. For example, flash media typically must be reformatted to regain lost space.
Nonvolatile (sometimes written as “non-volatile”) random access memory (“nvram,” or “NVRAM”) is typically a form of static RAM whose contents are saved when a computer is turned off or loses its external power source. As is known to those skilled in the art, nvram may be implemented in various ways, including by providing static RAM with backup battery power, or by saving its contents and restoring them from an Electrically Erasable Programmable Read Only Memory (“EEPROM”).
The development of nvram enabled files to be stored in a system in a persistent way. However, existing file systems are inadequate for addressing the unique set of challenges presented by the nvram memory storage media. First and foremost, the nvram media is relatively small in terms of memory capacity (typically ranging from a few hundred kilobytes to a few megabytes). Thus, only a relatively small number of files can be stored on the media. Secondly, nvram can be accessed relatively quickly, in comparison to magnetic disks, and hence disk block layout is not a major factor that affects the seek time parameter. Also, no directory structure is typically imposed on the nvram medium.
Moreover, because critical system data is often stored in nvram (e.g., cryptographic keys, system start-up configuration files, or other types of secure files), an nvram file system must be reliable. Specifically, a system “crash” should not corrupt the file system. In order to deal with these problems, a simple but elegant file system storage for the nvram medium is disclosed herein. It provides all the necessary functionality without being burdened by unnecessary details and restrictions imposed by a traditional file system. The main assumptions of the file system design according to embodiments of the present invention are that (1) the file system structure is flat (i.e., does not contain directories), and (2) a relatively small amount of memory space is available. Also, an important design goal is not to have excessive file system information in the nvram memory medium at any given time. Most of the information is kept on the nvram, and based on this, other information may be obtained. Thus, a system crash will not result in loss of vital information which might have been buffered in memory. These and other features and advantages of the present invention will be presented in more detail in the following specification of the invention and in the associated figures.
SUMMARY OF THE INVENTION
A file system for nonvolatile memory media is disclosed, based on the assumptions that the file system structure is flat (i.e., does not contain directories), and that a relatively small amount of memory space is available. The nonvolatile memory medium is divided into logical blocks of predetermined size, depending on the typical file size expected for each particular implementation. Each of these logical blocks includes a header describing the contents of the block. For example, the block header may comprise a magic number indicating whether the block is a valid file system block or a free block, the name of the file to which the current block belongs, a flag indicating whether the current block is the first or last block of the file, the block number of the next block of the current file, if any, and the length of valid data in the present block.
REFERENCES:
patent: 4424565 (1984-01-01), Larson
patent: 5247516 (1993-09-01), Bernstein et al.
patent: 5260933 (1993-11-01), Rouse
patent: 5394394 (1995-02-01), Crowther et al.
patent: 5463754 (1995-10-01), Beausoleil et al.
patent: 5473607 (1995-12-01), Hausman et al.
patent: 5485595 (1996-01-01), Assar et al.
patent: 5598581 (1997-01-01), Daines et al.
patent: 5619691 (1997-04-01), Katada et al.
patent: 5721828 (1998-02-01), Frisch
patent: 5727206 (1998-03-01), Fish et al.
patent: 5740171 (1998-04-01), Mazzola et al.
patent: 5778365 (1998-07-01), Nishiyama
patent: 5816301 (1998-10-01), Stager
patent: 5835036 (1998-11-01), Takefman
patent: 5838614 (1998-11-01), Estakhri et al.
patent: 5907856 (1999-05-01), Estakhri et al.
patent: 5924113 (1999-07-01), Estakhri et al.
patent: 5930815 (1999-07-01), Estakhri et al.
patent: 6021415 (2000-02-01), Cannon et al.
patent: 6034897 (2000-03-01), Estakhri et al.
patent: 6122716 (2000-09-01), Combs
patent: 6128695 (2000-10-01), Estakhri et al.
patent: 6134151 (2000-10-01), Estakhri et al.
patent: 6141249 (2000-10-01), Estakhri et al.
patent: 6243081 (2001-06-01), Goris et al.
patent: 6292868 (2001-09-01), Norman
patent: 6493804 (2002-12-01), Soltis et al.
R.C. Farrow et al, “Mark Detection for alignment and registration in high throughput projection electron lithography Tool”, AT&T Bell Laboratories , Aug. 3, 1992, pp. 2780-2783. ©1992 American Vacuum Society.
Tsuchiya, Paul F., “A Search Algorithm for Table Entries with Non-contiguous Wildcarding”, printed from tsuchiya@thumper.bellcore.com., Jun. 20, 1994, pp. 1-7.
Reginald C. Farrow et al, “Alignment Mark Detection In CMOS Materials with SCALPEL E-Beam Lithography”, Bell Laboratories, Lucent Technologies, pp. 2-11.
Mamillaplli Sudhakar
Monsen Robert Charles
Black Linh
Cisco Technology Inc.
Ritchie David B.
Robinson Greta
Thelen Reid & Priest LLP
LandOfFree
File system for nonvolatile memory does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with File system for nonvolatile memory, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and File system for nonvolatile memory will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3100005