File system for nonvolatile memory

• US 7,711,696 B2
• Filed: 07/02/2003
• Issued: 05/04/2010
• Est. Priority Date: 02/14/2000
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Monsen, Robert Charles, Mamillaplli, Sudhakar
• Primary Examiner(s): Trujillo; James
• Assistant Examiner(s): Black; Linh
• Application Number:
  US10/614,070
• Publication Number:
  US 20040019784A1
• Time in Patent Office: 2,498 Days
• Field of Search: 707 1-1041
• US Class Current: 711/103
• CPC Class Codes: G06F 16/10 File systems; File servers
• CPC Class Codes: Y10S 707/99948 Application of database or data structure, e.g. distributed, multimedia, or image
• CPC Class Codes: Y10S 707/99953 Recoverability

Abstract

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.

Claims

1. A method comprising:

scanning a nonvolatile memory medium with a processor to find a first memory block containing a header indicating that the first memory block is the first memory block of an existing file stored on the nonvolatile memory medium and

finding a next memory block using a next block pointer stored in the header of the first memory block, if the existing file comprises more memory blocks than the first memory block, the existing file being opened upon completion of the finding, the header including a flag that comprises a first bit that is set if the first memory block is a first block of a file, a second bit that is set if the first memory block is a last block of the file, and a third bit that is set if the first memory block is part of a secure file.

2. The method of claim 1, further comprising repeating the finding step until either all memory blocks comprising the file have been found or an error condition occurs.

3. A method comprising:

scanning a nonvolatile memory medium with a processor in sizes of one predetermined logical block, the nonvolatile memory medium storing an existing file;

for each logical block, reading a block header containing a magic number;

testing the magic number to determine whether the logical block is a valid block or a free block, and if the logical block is a valid block, performing a comparison of a file name encoded within the block header with a specified file name to be opened;

testing a flag within the block header to determine whether the logical block is the first block of the existing file, if the comparison produces a match; and

returning to the scanning step with the next logical block until either the comparison produces a match or all the blocks have been tested, thereby indicating an error condition, the existing file being opened if the comparison produces a match, the header including a flag that comprises a first bit that is set if the logical block is a first block of a file, a second bit that is set if the logical block is a last block of the file, and a third bit that is set if the logical block is part of a secure file.

4. A method comprising:

scanning a nonvolatile memory medium with a processor in sizes of one predetermined-sized logical block, the nonvolatile memory medium for storing a new file;

for each logical block, reading a block header containing a magic number;

testing the magic number to determine whether the logical block is a valid block or a free block, and if the logical block is a free block, modifying its block header to comprise a valid magic number, the name of the new file to be opened, and flags indicating whether the logical block is either the first block or the last block of the new file; and

returning to the scanning step with the next logical block until either the testing step has identified a free block or all the blocks have been tested, thereby indicating an error condition, the new file being opened if the testing step has identified a free block, the header including a flag that comprises a first bit that is set if the logical block is a first block of a file, a second bit that is set if the logical block is a last block of the file, and a third bit that is set if the logical block is part of a secure file.

5. A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform a method, the method comprising:

scanning a nonvolatile memory medium to find a first memory block containing a header indicating that the first memory block is the first memory block of an existing file stored on the nonvolatile memory medium; and

finding a next memory block using a next block pointer stored in the header of the first memory block, if the existing file comprises more memory blocks than the first memory block, the existing file being opened upon completion of the finding, the header including a flag that comprises a first bit that is set if the first memory block is a first block of a file, a second bit that is set if the first memory block is a last block of the file, and a third bit that is set if the first memory block is part of a secure file.

6. A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform a method, the method comprising:

scanning a nonvolatile memory medium in sizes of one predetermined logical block the nonvolatile memory medium storing an existing file;

for each logical block,

reading a block header containing a magic number;

testing the magic number to determine whether the logical block is a valid block or a free block, and if the logical block is a valid block, performing a comparison of a file name encoded within the block header with the specified file name to be opened;

testing a flag within the block header to determine whether the logical block is the first block of the specified file, if the comparison produces a match; and

returning to the scanning step with the next logical block until either the comparison produces a match or all the blocks have been tested, thereby indicating an error condition, the existing file being opened if said comparison produces a match, the header including a flag that comprises a first bit that is set if the logical block is a first block of a file, a second bit that is set if the logical block is a last block of the file, and a third bit that is set if the logical block is part of a secure file.

7. A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform a method, the method comprising:

scanning a nonvolatile memory medium in sizes of one predetermined-sized logical block, the nonvolatile memory medium for storing a new file;

for logical block,

reading a block header containing a magic number;

testing the magic number to determine whether the logical block is a valid block or a free block, and if the logical block is a free block, modifying its block header to comprise a valid magic number, the name of the file to be opened, and flags indicating whether the logical block is either the first block or the last block of said file; and

returning to the scanning step with the next logical block until either the testing step has identified a free block or all the blocks have been tested, thereby indicating an error condition, the new file being opened if said testing step has identified a free block, the header including a flag that comprises a first bit that is set if the logical block is a first block of a file, a second bit that is set if the logical block is a last block of the file, and a third bit that is set if the logical block is part of a secure file.

8. An apparatus comprising:

means for scanning the nonvolatile memory medium to find a first memory block containing a header indicating that the first memory block is the first memory block of an existing file stored on the nonvolatile memory medium; and

means for finding a next memory block using a next block pointer stored in the header of the first memory block, if the existing file comprises more than the first memory block, the existing file being opened upon completion of said finding, the header including a flag that comprises a first bit that is set if the first memory block is a first block of a file, a second bit that is set if the first memory block is a last block of the file, and a third bit that is set if the first memory block is part of a secure file.

9. An apparatus comprising:

scanning means for scanning a nonvolatile memory medium to find a first memory block containing a header indicating that the first memory block is the first memory block of an existing file; and

finding means for finding a next memory block using a next block pointer stored in the header of the first memory block, if the file comprises more than the first memory block, the finding means operating iteratively until either all memory blocks of which the existing file is comprised have been found or an error condition occurs, the existing file being opened if all memory blocks of which the existing file is comprised have been found, the header including a flag that comprises a first bit that is set if the first memory block is a first block of a file, a second bit that is set if the first memory block is a last block of the file, and a third bit that is set if the first memory block is part of a secure file.

10. An apparatus comprising:

scanning means for scanning a nonvolatile memory medium in sizes of one predetermined logical block, the nonvolatile memory medium for storing a new file;

reading means for reading a block header containing a magic number for each logical block;

testing means for testing the magic number to determine whether the logical block is a valid block or a free block, and if the logical block is a valid block, performing a comparison of a file name encoded within the block header with a specified file name to be opened; and

checking means for checking a flag within the block header to determine whether the logical block is the first block of the existing file, if the comparison performed by the testing means produces a match, said scanning means operating iteratively on until either the comparison produces a match or all the blocks have been tested, thereby indicating an error condition, the new file being opened if the comparison produces a match, the header including a flag that comprises a first bit that is set if the logical block is a first block of a file, a second bit that is set if the logical block is a last block of the file, and a third bit that is set if the logical block is part of a secure file.

11. An apparatus comprising:

scanning means for scanning a nonvolatile memory medium in sizes of one predetermined logical block, the nonvolatile memory medium for storing a new file;

reading means for reading a block header containing a magic number for each logical block;

testing means for testing the magic number to determine whether the logical block is a valid block or a free block, and if the logical block is a free block, modifying the block header to comprise a valid magic number, the name of the file to be opened, and flags indicating whether the logical block is either the first block or the last block of the new file, the header including a flag that comprises a first bit that is set if the logical block is a first block of a file, a second bit that is set if the logical block is a last block of the file, and a third bit that is set if the logical block is part of a secure file;

the scanning means operating iteratively on next logical blocks until either the testing means has identified a free block or all the blocks have been tested, thereby indicating an error condition, the new file being opened if said testing means has identified a free block.

12. An apparatus comprising:

nonvolatile memory medium means for storing information in the form of a file;

scanning means for scanning memory blocks of the nonvolatile memory medium means to find a first memory block of a selected file, the first memory block containing a header having an indicator that indicates that it is the first memory block of the selected file; and

finding means for finding a next memory block using a next block pointer stored in the header for selected files having more than one memory block, the selected file being opened upon completion of the finding, the header including a flag that comprises a first bit that is set if the first memory block is a first block of a file, a second bit that is set if the first memory block is a last block of the file, and a third bit that is set if the first memory block is part of a secure file.

13. The apparatus of claim 12, wherein the finding means operates iteratively until either all memory blocks of the selected file have been found or an error condition occurs.