Managing file structures for a flash memory file system in a computer

• US 5,682,497 A
• Filed: 04/08/1996
• Issued: 10/28/1997
• Est. Priority Date: 09/28/1993
• Status: Expired due to Term

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Robinson, Kurt B.
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): HOMERE, JEAN RAYMOND
• Application Number:
  US08/629,762
• Time in Patent Office: 568 Days
• Field of Search: 395/430, 395/497.01, 395/462, 395/612, 395/621, 395/622, 364/DIG. 1
• US Class Current: 711/103
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 2003/0697 device management, e.g. handlers, drivers, I/O schedulers
• CPC Class Codes: G06F 3/0601 Interfaces specially adapted for storage systems
• CPC Class Codes: G06F 3/0664 at device level, e.g. emulation of a storage device or system

Abstract

A method for compressing a set of file structures in a flash memory subsystem is disclosed. During a clean-up operation, a sibling chain of the file structures stored in a logical block of the flash memory subsystem is traversed. If a file structure is followed by deleted file structures in the sibling chain, then the file structure is transferred to a spare logical block and the sibling pointer of the file structure is programmed bypass the deleted file structures. If a deleted file structure in the sibling chain is referenced by a previous file structure in the sibling chain, then the deleted file structure is transferred to the logical block and recycled.

Claims

1. A method of cleaning up a logical block of a flash memory subsystem, the method comprising the steps of:

transferring information from block allocation structures and file structures of a first logical block of a flash memory subsystem having a first logical block identifier to corresponding block allocation structures and file structures of a second logical block of the flash memory subsystem having a second logical block identifier, the block allocation structures in each logical block storing physical address offsets for the file structures, the file structures including directory entry structures that specify directories, file entry structures that specify files, and file information structures with corresponding extent blocks that store file data, the directory entry and file entry data structures forming a linked list file structure that defines a file system hierarchy, and the file information structures linking the extent blocks to the file system hierarchy;

compressing the file structures into the second logical block by discarding deleted file information structures and extent blocks and modifying the linked list hierarchy to eliminate deleted file entry and directory entry structures;

reprogramming the logical block identifier of the second logical block to reflect the logical block identifier of the first logical block;

erasing the first logical block; and

programming the logical block identifier of the first logical block to reflect a cleaned up status.

2. The method of claim 1 wherein the step of compressing the file structures comprises the steps of:

accessing a current file structure by traversing a sibling chain of the file structures stored in the first logical block in the flash memory subsystem, the sibling chain specified by a sibling pointer stored in each file structure;

if the current file structure is not deleted, accessing a next undeleted file structure from the file structures by traversing ahead through the sibling chain, then transferring the current file structure to the second logical block and programming the sibling pointer of the current file structure in the second logical block to point to the next undeleted file structure in the sibling chain;

if the current file structure is deleted, then transferring the current file structure to the second logical block and setting a child pointer of the current file structure in the second logical block to null, such that the null child pointer is programmable without prior erasure.

3. The method of claim 2, wherein the step of transferring the current file structure to the second logical block further comprises the step of transferring a child file structure corresponding to the current file structure from the first logical block to the second logical block.

4. The method of claim 3, wherein the child file structure corresponding to the current file structure is specified by a child pointer stored in the current file structure.

5. The method of claim 4, wherein if the current file structure is one of the directory entry structures, the child file structure is one of the file entry structures.

6. The method of claim 4, wherein if the current file structure is one of the directory entry structures, the child file structure is a child directory entry structure containing a set of child directory parameters that define a child directory.

7. The method of claim 4, wherein if the current file structure is one of the file entry structures, the child file structure comprises a file information structure specifying an extent block.

8. The method of claim 7, further comprising the step of transferring the extent block specified by the file information structure from the first logical block to the second logical block.

9. The method of claim 8, wherein the extent block is specified by an extent pointer stored in the file information structure.

10. The method of claim 9, further comprising the step of transferring a child file information structure specified by the file information structure from the first logical block to the second logical block.

11. The method of claim 10, wherein the child file information structure is specified by a child file information pointer stored in the file information structure.

12. An apparatus for cleaning up a logical block of a flash memory subsystem, the apparatus comprising:

means for transferring information from block allocation structures and file structures of a first logical block of a flash memory subsystem having a first logical block identifier to corresponding block allocation structures and file structures of a second logical block of the flash memory subsystem having a second logical block identifier, the block allocation structures in each logical block storing physical address offsets for the file structures, the file structures including directory entry structures that specify directories, file entry structures that specify files, and file information structures with corresponding extent blocks that store file data, the directory entry and file entry data structures forming a linked list file structure that defines a file system hierarchy, and the file information structures linking the extent blocks to the file system hierarchy;

means for compressing the file structures into the second logical block by discarding deleted file information structures and extent blocks and modifying the linked list hierarchy to eliminate deleted file entry and directory entry structures;

means for reprogramming the logical block identifier of the second logical block to reflect the logical block identifier of the first logical block;

means for erasing the first logical block; and

means for programming the logical block identifier of the first logical block to reflect a cleaned up status.

13. The apparatus of claim 12 wherein the means for compressing the file structures further comprises:

means for accessing a current file structure by traversing a sibling chain of the file structures stored in the first logical block in the flash memory subsystem, the sibling chain specified by a sibling pointer stored in each file structure;

means for accessing a next undeleted file structure from the file structures by traversing ahead through the sibling chain, then transferring the current file structure to the second logical block and programming the sibling pointer of the current file structure in the second logical block to point to the next undeleted file structure in the sibling chain if the current file structure is not deleted;

means for transferring the current file structure to the second logical block and setting a child pointer of the current file structure in the second logical block to null, such that the null child pointer is programmable without prior erasure of the current file structure is deleted.

14. The apparatus of claim 13, wherein the means for transferring the current file structure to the second logical block further comprises means for transferring a child file structure corresponding to the current file structure from the first logical block to the second logical block.

15. The apparatus of claim 14, wherein the child file structure corresponding to the current file structure is specified by a child pointer stored in the current file structure.

16. The apparatus of claim 15, wherein if the current file structure is one of the directory entry structures, the child file structure is one of the file entry structures.

17. The apparatus of claim 15, wherein if the current file structure is one of the directory entry structures, the child file structure is a child directory entry structure containing a set of child directory parameters that define a child directory.

18. The apparatus of claim 15, wherein if the current file structure is one of the file entry structures, the child file structure comprises a file information structure specifying an extent block.

19. The apparatus of claim 18, further comprising means for transferring the extent block specified by the file information structure from the first logical block to the second logical block.

20. The apparatus of claim 19, wherein the extent block is specified by an extent pointer stored in the file information structure.

21. The apparatus of claim 20, further comprising means for transferring a child file information structure specified by the file information structure from the first logical block to the second logical block.

22. The apparatus of claim 21, wherein the child file information structure is specified by a child file information pointer stored in the file information structure.

23. A method of cleaning up a logical block of a flash memory subsystem of a computer system, the method comprising the steps of:

detecting an idle time of an operating system executing on a central processing unit in a computer system;

transferring information from block allocation structures and file structures of a first logical block of a flash memory subsystem of the computer system having a first logical block identifier to corresponding block allocation structures and file structures of a second logical block of the flash memory subsystem of the computer system having a second logical block identifier after the idle time is detected, the block allocation structures in each logical block storing physical address offsets for the file structures, the file structures including directory entry structures that specify directories, file entry structures that specify files, and file information structures with corresponding extent blocks that store file data, the directory entry and file entry data structures forming a linked list file structure that defines a file system hierarchy, and the file information structures linking the extent blocks to the file system hierarchy;

compressing the file structures into the second logical block by discarding deleted file information structures and extent blocks and modifying the linked list hierarchy to eliminate deleted file entry and directory entry structures;

reprogramming the logical block identifier of the second logical block to reflect the logical block identifier of the first logical block;

erasing the first logical block; and

programming the logical block identifier of the first logical block to reflect a cleaned up status.

24. The method of claim 23, wherein the step of compressing the file structures further comprises:

accessing a current file structure by traversing a sibling chain of the file structures stored in the first logical block in the flash memory subsystem, the sibling chain specified by a sibling pointer stored in each file structure;

if the current file structure is not deleted, accessing a next undeleted file structure from the file structures by traversing ahead through the sibling chain, then transferring the current file structure to the second logical block and programming the sibling pointer of the current file structure in the second logical block to point to the next undeleted file structure in the sibling chain;

if the current file structure is deleted, then transferring the current file structure to the second logical block and setting a child pointer of the current file structure in the second logical block to null, such that the null child pointer is programmable without prior erasure.

25. The method of claim 24, wherein the step of transferring the current file structure to the second logical block further comprises the step of transferring a child file structure corresponding to the current file structure from the first logical block to the second logical block.

26. The method of claim 25, wherein the child file structure corresponding to the current file structure is specified by a child pointer stored in the current file structure.

27. The method of claim 26, wherein if the current file structure is one of the directory entry structures, the child file structure is one of the file entry structures.

28. The method of claim 26, wherein if the current file structure is one of the directory entry structures, the child file structure is a child directory entry structure containing a set of child directory parameters that define a child directory.

29. The method of claim 26, wherein if the current file structure is one of the file entry structures, the child file structure comprises a file information structure specifying an extent block.

30. The method of claim 29, further comprising the step of transferring the extent block specified by the file information structure from the first logical block to the second logical block.

31. The method of claim 30, wherein the extent block is specified by an extent pointer stored in the file information structure.

32. The method of claim 31, further comprising the step of transferring a child file information structure specified by the file information structure from the first logical block to the second logical block.

33. The method of claim 32, wherein the child file information structure is specified by a child file information pointer stored in the file information structure.