RAM based directory layer for a flash file system

• US 6,480,864 B1
• Filed: 06/15/1999
• Issued: 11/12/2002
• Est. Priority Date: 06/15/1999
• Status: Expired due to Term

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Fong, Albert Meng, Kathail, Pradeep K.
• Primary Examiner(s): Mizrahi, Diane D.
• Assistant Examiner(s): MOFIZ, APU M
• Application Number:
  US09/334,041
• Time in Patent Office: 1,246 Days
• Field of Search: 707/1-100, 707/200, 707/206, 707/205, 345/716, 345/760, 379/191, 379/193, 379/253, 379/255, 379/284, 717/1, 717/4, 717/11
• US Class Current: 707/824
• CPC Class Codes: G06F 16/10 File systems; File servers
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99956 File allocation

Abstract

A flash file system for use with flash cards and internetwork operating system software is provided. Absolute path names are stored in the name field of existing files on flash cards. When the system is initialized, a directory structure is created and stored in RAM by accessing the absolute path names stored in the name field of each file on the flash cards. Accessing a file on a flash card is then accomplished by traversing the directory structure in RAM, and going directly to the precise location of the file on the flash card, thereby minimizing the amount of information that must be retrieved from the flash cards and greatly increasing the speed of accesses. Additionally, cards designed for use with older, non-modular internetwork operating systems may still be used, as name fields for files in these flash cards may easily be used to store absolute path names.

Claims

1. A method for creating a directory structure for a flash file system, the flash file system having one or more flash cards with files on them, said files each having a name field with an absolute path name, the method comprising:

accessing the name fields of each of the files in one or more of the flash cards of the flash file system during initialization of flash file system;

building a directory having tree structure using the absolute path names in the name fields; and

storing said directory in RAM, wherein said tree structure includes a plurality of nodes, each of said nodes containing a parent field and one or more child fields, said parent field containing a pointer to a parent node if the node has a parent, said one or more child fields containing pointers to child nodes if the node has one or more children, and said one or more child fields containing a pointer to a file on a flash card if the node has no children.

2. The method of claim 1, wherein each of said absolute path names comprises:

information on the directory and any subdirectories in which the file is to be stored; and

the name of the file.

3. A method for maintaining a directory structure for a flash file system, the flash file system having one or more flash cards with files on them, each of the files having a name field, the method comprising:

storing an absolute oath name for each of the files in the name field in each of the files;

accessing the name fields of each of the files in one or more of the flash cards of the flash file system during initialization of flash file system;

building a directory having a tree structure using the absolute oath names in the name fields; and

storing said directory in RAM, wherein said tree structure includes a plurality of nodes, each of said nodes containing a parent field and a next node field, said parent field containing a pointer to a parent node, said next node field containing a pointer to a peer node, if any more exist, said node further having a first child field containing a pointer to a first child node if said node corresponds to a directory containing one or more subdirectories or files, said node further having a leaf location field containing a pointer to the location of the corresponding file if said node is a leaf node, and said node further having a name field containing a name for the directory or file corresponding to said node.

4. The method of claim 3, wherein each of said absolute path names comprises:

information on the directory and any subdirectories in which the file is to be stored; and

the name of the file.

5. A flash file system, including:

one or more flash cards, said flash cards having files on them, said files each having a name field with an absolute path name;

a name field accessor coupled to each of said flash cards;

a directory builder coupled to said name field accessor;

a RAM; and

a directory storer coupled to said directory builder and to said RAM, wherein said directory builder creates a tree structure and said directory storer stores said tree structure in said RAM and wherein said tree structure includes a plurality of nodes, each of said nodes containing a parent field and a next node field, said parent field containing a pointer to a parent node, said next node field containing a pointer to a peer node, if any more exist, said node further having a first child field containing a pointer to a first child node if said node corresponds to a directory containing one or more subdirectories or files, said node further having a leaf location field containing a pointer to the location of the corresponding file if said node is a leaf node, and said node further having a name field containing a name for the directory or file corresponding to said node.

6. The flash file system of claim 5, wherein each of said files includes a name field having an absolute path name.

7. The flash file system of claim 6, wherein each of said absolute path names comprises:

information on the directory and any subdirectories in which the file is to be stored; and

the name of the file.

8. An internetwork operating system, including:

one or more flash cards, said flash cards having files on them, said files each having a name field with an absolute path name;

a name field accessor module coupled to each of said flash cards;

a directory builder module coupled to said name field accessor;

a RAM; and

a directory storer module coupled to said directory builder and to said RAM, wherein said directory builder module creates a tree structure and said directory storer module stores said tree structure in said RAM and wherein said tree structure includes a plurality of nodes, each of said nodes containing a parent field and a next node field, said parent field containing a pointer to a parent node, said next node field containing a pointer to a peer node, if any more exist, said node further having a first child field containing a pointer to a first child node if said node corresponds to a directory containing one or more subdirectories or files, said node further having a leaf location field containing a pointer to the location of the corresponding file if said node is a leaf node, and said node further having a name field containing a name for the directory or file corresponding to said node.

9. The internetwork operating system of claim 8, wherein each of said files includes a name field having an absolute path name.

10. The internetwork operating system of claim 9, wherein each of said absolute path names comprises:

information on the directory and any subdirectories in which the file is to be stored; and

the name of the file.

11. A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps for creating a directory structure for a flash file system, the flash file system having one or more flash cards with files on them, said files each having a name field with an absolute path name, the method comprising:

accessing the name fields of each of the files in one or more of the flash cards of the flash file system during initialization of flash file system;

building a directory having a tree structure using the absolute path names in the name fields; and

storing said directory in RAM wherein said tree structure includes a plurality of nodes, each of said nodes containing a parent field and a next node field, said parent field containing a pointer to a parent node, said next node field containing a pointer to a peer node, if any more exist, said node further having a first child field containing a pointer to a first child node if said node corresponds to a directory containing one or more subdirectories or files, said node farther having a leaf location field containing a pointer to the location of the corresponding file if said node is a leaf node, and said node father having a name field containing a name for the directory or file corresponding to said node.

12. The program storage device of claim 11, wherein each of said absolute path names comprises:

information on the directory and any subdirectories in which the file is to be stored; and

the name of the file.

13. A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps for maintaining a directory structure for a flash file system, the flash file system having one or more flash cards with files on them, each of the files having a name field, the method comprising:

storing an absolute oath name for each of the files in the name field in each of the files;

accessing the name fields of the files in one or more of the flash cards of the flash file system during initialization of flash file system;

building a directory having a tree structure using the absolute path names in the name fields; and

storing said directory in RAM wherein said tree structure includes a plurality of nodes, each of said nodes containing a parent field and a next node field, said parent field containing a pointer to a parent node, said next node field containing a pointer to a peer node, if any more exist, said node further having a first child field containing a pointer to a first child node if said node corresponds to a directory containing one or more subdirectories or files, said node further having a leaf location field containing a pointer to the location of the corresponding file if said node is a leaf node, and said node further having a name field containing a name for the directory or file corresponding to said node.

14. The program storage device of claim 13, wherein each of said absolute path names comprises:

information on the directory and any subdirectories in which the file is to be stored; and

the name of the file.

15. A flash file system for creating a directory structure for a flash file system, the flash file system having one or more flash cards with files on them, said files each having a name field with an absolute path name, the method comprising:

means for accessing the name fields of each of the files in one or more of the flash cards of the flash file system during initialization of flash file system;

means for building a directory having a tree structure using the absolute path names in the name fields; and

means for storing said directory in RAM wherein said tree structure includes a plurality of nodes, each of said nodes containing a parent field and one or more child fields, said parent field containing a pointer to a parent node if the node has a parent, said one or more child fields containing pointers to child nodes if the node has one or more children, and said one or more child fields containing a pointer to a file on a flash card if the node has no children.

16. The flash file system of claim 15, wherein each of said absolute path names comprises:

information on the directory and any subdirectories in which the file is to be stored; and

the name of the file.

17. A flash file system for maintaining a directory structure for a flash file system, the flash file system having one or more flash cards with files on them, each of the files having a name field, the method comprising:

means for storing an absolute path name for each of the files in the name field in each of the files;

means for accessing the name fields of each of the files in one or more of the flash cards of the flash file system during initialization of flash file system;

means for building a directory having a tree structure using the absolute path names in the name fields; and

means for storing said directory in RAM, wherein said tree structure includes a plurality of nodes, each of said nodes containing a parent field and a next node field, said parent field containing a pointer to a parent node, said next node field containing a pointer to a peer node, if any more exist, said node further having a first child field containing a pointer to a first child node if said node corresponds to a directory containing one or more subdirectories or files, said node further having a leaf location field containing a pointer to the location of the corresponding file if said node is a leaf node, and said node further having a name field containing a name for the directory or file corresponding to said node.

18. The flash file system of claim 17, wherein each of said absolute path names comprises:

information on the directory and any subdirectories in which the file is to be stored; and

the name of the file.