Method and system for file system management using a flash-erasable programmable, read-only memory

• US 5,634,050 A
• Filed: 06/07/1995
• Issued: 05/27/1997
• Est. Priority Date: 01/29/1992
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Rajagopalan, Sriram, Krueger, William J.
• Primary Examiner(s): AMSBURY, WAYNE P
• Application Number:
  US08/473,763
• Time in Patent Office: 720 Days
• Field of Search: 395/600
• US Class Current: 1/1
• CPC Class Codes: G06F 11/1435 using file system or storage system metadata
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 16/10 File systems; File servers
• CPC Class Codes: G06F 16/9017 using directory or table look-up use of a directory or look-up table in file systems G06F16/13
• CPC Class Codes: G06F 2212/7205 Cleaning, compaction, garbage collection, erase control
• CPC Class Codes: Y10S 707/99956 File allocation

Abstract

A method and system for managing memory in a block-erasable, flash-erasable, programmable, read-only memory. The system comprises a block-erasable FEProm with a block header, a block allocation table, a data storage area, a block allocation routine for selecting a block in which to store data, a data area allocation routine for selecting an entry in the block allocation table and a portion of the data storage area, and a storage routine for storing the data. The system includes a file manager to implement a file system for the block-erasable FEProm.

Claims

1. A block-erasable, write-once, multiple-read memory device, the memory device having one or more blocks, comprising:

a data region area in each block, the data region area divided into a plurality of data regions for storing data; and

a block structure stored in each block, the block structure having a header and an allocation array, the header containing block-specific information, the allocation array containing an entry corresponding to each data region, each entry containing information relating to the corresponding data region.

2. The memory device of claim 1 wherein the header contains a logical block number, a block status, and a block erase count.

3. The memory device of claim 1 wherein an allocation array entry contains a pointer to the corresponding data region, a length indicating the length of the corresponding data region, and an allocation array entry status.

4. The memory device of claim 1 wherein the memory device is a block-erasable, programmable, read-only memory.

5. A method of memory management in a block-erasable, programmable, read-only memory, the memory comprising a plurality of blocks, method comprising the steps of:

storing block header information in each block;

storing an allocation table in each block; and

storing data in a data storage area in each block.

6. The method of claim 5 wherein the block header information includes a logical block number, a block status, and a block erase count.

7. The method of claim 5 wherein the allocation table contains entries corresponding to portions of the data storage area, the entries containing a pointer to the corresponding portion of the data storage area, a length indicating the length of the corresponding portion of the data storage area, and a status indicating the status of the entry.

8. A method of managing a block-erasable, write-once, read-many memory in a computer, the memory being divided into blocks of memory locations, each block including an allocation array, data regions, and free space, the allocation array with entries corresponding to the data regions, the method comprising the steps of:

receiving a request to store data in the memory, the request including the data to be stored;

selecting a block in the memory with sufficient free space to store the data and to store a corresponding entry in the allocation array; and

allocating a new data region in the free space of the block in which to store the data by;

selecting an allocation array entry to correspond to the new data region;

selecting the new data region;

setting the selected allocation array entry to contain a reference to the new data region within the block and to indicate that the new data region is allocated; and

storing the data in the new data region, thereby completing the allocation of the new data region.

9. The method of claim 8 wherein the allocation array and the data regions are located at opposite ends of the block and as new data regions and allocation array entries are selected, the allocation array and the data regions grow towards each other.

10. The method of claim 8 wherein each block has an erase count that indicates the number of times the block has been erased and wherein the step of selecting a block in the memory further comprises the step of selecting the block in the memory based on the erase count.

11. The method of claim 8, further comprising the step of deallocating a data region in the block by setting the corresponding allocation array entry to indicate that the data region is deallocated.

12. The method of claim 11, further comprising the step of reclaiming deallocated data regions in the block by:

selecting a spare block in the memory;

erasing the spare block; and

for each allocation array entry,

determining whether the corresponding data region is allocated or deallocated;

when the corresponding data region is allocated, copying the corresponding data region to the spare block and setting the allocation array entry of the spare block to contain a reference to the data region within the spare block and to indicate that the data region is allocated; and

when the corresponding data region is deallocated, setting the allocation array entry of the spare block to indicate that the corresponding data region is free, thereby reclaiming the deallocated data regions.

13. The method of claim 12 wherein each block has an erase count that indicates the number of times the block has been erased and wherein the step of selecting a spare block in the memory further comprises the step of selecting the spare block in the memory based on the erase count.

14. The method of claim 8, including the step of, before setting the selected allocation array entry to contain a reference to the new data region, setting the selected allocation array entry to allocation-in-process wherein the step of setting the selected allocation array entry to allocated occurs after the data is stored in the new data region so that if an error occurs when storing the data, the selected allocation array entry will not falsely indicate that the data has been correctly stored in the new data region.

15. The method of claim 8 wherein the step of selecting an allocation array entry selects an entry that was set to free indicating that its corresponding data region was reclaimed.

16. A method of referencing a data region in a block-erasable, write-once, read-many memory, the memory being divided into blocks of memory locations, each block having a logical block number and a physical block number, each block including an allocation array and data regions, the allocation array with entries corresponding to the data regions, the method comprising:

storing an allocation array in blocks of the block-erasable, write-once, read-only memory, each allocation array entry containing an offset of the corresponding data region within the block and having an index;

storing a logical block number and a corresponding physical block number and physical start address for each block in a block translation cache;

specifying a data region in a block of the block-erasable, write-once, read-only memory by logical block number and allocation array entry index; and

generating a physical address of the specified data region by;

determining the physical block number of the block from the logical block number using the block translation cache;

determining the physical start address of the block from the determined physical block number;

retrieving from the allocation array entry index the offset of the specified data region within that block within the block with the determined physical block number; and

adding the retrieved offset to the physical start address of the block, thereby generating the physical address of the specified data region.

17. A method of referencing a block in a block-erasable, write-once, read-many memory, the memory being divided into blocks of memory locations, each block having a logical block number and a physical block number, each block including an allocation array and data regions, the allocation array with entries corresponding to the data regions, the method comprising:

storing a logical block number in each block of the block-erasable, write-once, read-only memory;

at initialization, reading the logical block number in each block and storing the logical block number and a corresponding physical block number for each block in a block translation cache;

specifying a block of the block-erasable, write-once, read-only memory by logical block number; and

generating a physical address of the specified block by;

determining the physical block number of the block from the logical block number using the block translation cache; and

determining a physical start address of the block from the determined physical block number.

18. A method of leveling erase counts in a block-erasable, write-once, read-many memory, the memory being divided into blocks of memory locations, each block having an erase count that indicates the number of times the block has been erased, the method comprising the steps of:

identifying a first block of the block-erasable, write-once, read-only memory that has an erase count;

identifying a second block of the block-erasable, write-once, read-only memory that has a lower erase count than the first block;

copying the data in the first block to a spare block;

erasing the first block;

incrementing the erase count for the first block;

storing the incremented erase count for the first block in the first block;

copying the data from the second block to the first block;

erasing the second block;

incrementing the erase count for the second block;

storing the incremented erase count for the second block in the second block; and

copying the data from the spare block to the second block.

19. A method for reclaiming memory within a source block in block-erasable, write-once, read-many memory device, the source block having an allocation array and data regions, each data region being allocated or not allocated, the allocation array having entries that reference a data region, each data region being identifiable by an index within the allocation array of the entry that references the data region, the method comprising:

for each entry in the allocation array,

determining whether the referenced data region is allocated;

when the referenced data region is allocated, copying the referenced data region to a data region within a spare block and setting an entry in an allocation array of the spare block to reference the copy of the data region, the entry in the allocation array of the spare block having the same index within the allocation array of the spare block as the entry within the allocation array of the source block so that the data region in the spare block is identifiable by the same index by which the data region of the source block is identifiable, whereby data regions that are not allocated are not copied to the spare block.

20. The method of claim 19, including:

when the referenced data region is not allocated, setting an entry in the allocation table of the spare block to free so that the entry may be used to reference a newly allocated data region of the spare block after completion of reclamation.

21. The method of claim 20 wherein a data region that is not allocated is a data region that has been deallocated.

22. The method of claim 20 wherein a data region that is not allocated is a data region that has been superseded by another data region within the source block.

23. The method of claim 19, including, after copying each allocated data region of the source block, erasing the source block.

24. The method of claim 19 including after copying each allocated data region of the source block, directing each access for data of a data region to the spare block.

25. A method for reclaiming memory within a block in block-erasable, write-once, read-many memory device, the block having an allocation array and data regions, each data region being allocated or not allocated, the allocation array having entries that reference a data region, each data region being identifiable by an index within the allocation array of the entry that references the data region, the method comprising:

copying the allocated regions and the entries that reference the allocated regions from the block to a temporary memory;

erasing the block; and

for each entry copied,

copying the data region referenced by that entry from the temporary memory to a data region within the erased block and setting an entry in an allocation array of the erase block to reference the copy of the data region, the entry in the allocation array of the erased block having the same index within the allocation array of the erased block as the entry within the allocation array of the block before being erased so that the data region is identifiable by the same index after reclamation.

26. A block erasable, write-once, read-many memory device with a plurality of blocks, containing within a block:

a plurality of data regions; and

an allocation array with an entry for each data region, each entry having a reference to the data region.

27. The memory device of claim 26 wherein the reference is an offset of the start of the data region.

28. The memory device of claim 27 wherein the data regions are variable length and an entry contain the length of the data region.

29. The memory device of claim 26 wherein a block further contains a logical block number.

30. The memory device of claim 26 wherein a block further contains an erase count.

31. The memory device of claim 26 wherein a block further contains a write count.

32. The memory device of claim 26 wherein an entry contains an indication of state that is either allocated, deallocated, superseded, or free.

33. The memory device of claim 26 wherein a block contains an indication of state that is either spare, erased, or ready.

34. A computer-readable medium containing instruction for causing a computer system to reclaim memory within a source block in block-erasable, write-once, read-many memory device, the source block having an allocation array and data regions, each data region being allocated or not allocated, the allocation array having entries that reference a data region, each data region being identifiable by an index within the allocation array of the entry that references the data region, by the method of:

for each entry in the allocation array,

determining whether the referenced data region is allocated;

when the referenced data region is allocated, copying the referenced data region to a data region within a spare block and setting an entry in an allocation array of the spare block to reference the copy of the data region, the entry in the allocation array of the spare block having the same index within the allocation array of the spare block as the entry within the allocation array of the source block so that the data region in the spare block is identifiable by the same index by which the data region of the source block is identifiable, whereby data regions that are not allocated are not copied to the spare block.

35. The computer-readable medium of claim 34, including:

when the referenced data region is not allocated, setting an entry in the allocation table of the spare block to free so that the entry may be used to reference a newly allocated data region of the spare block after completion of reclamation.

36. The computer-readable medium of claim 35 wherein a data region that is not allocated is a data region that has been deallocated.

37. The computer-readable medium of claim 35 wherein a data region that is not allocated is a data region that has been superseded by another data region within the source block.

38. The computer-readable medium of claim 34, including, after copying each allocated data region of the source block, erasing the source block.

39. The computer-readable medium of claim 34 including after copying each allocated data region of the source block, directing each access for data of a data region to the spare block.

40. A computer-readable memory containing instruction for causing a computer system to manage a block-erasable, write-once, read-many memory in a computer, the memory being divided into blocks of memory locations, each block including an allocation array, data regions, and free space, the allocation array with entries corresponding to the data regions, by the steps of:

selecting a block in the memory with sufficient free space to store data and to store a corresponding entry in the allocation array; and

allocating a new data region in the free space of the block in which to store the data by;

selecting an allocation array entry to correspond to the new data region;

selecting the new data region;

setting the selected allocation array entry to contain a reference to the new data region within the block and to indicate that the new data region is allocated; and

storing the data in the new data region, thereby completing the allocation of the new data region.

41. The computer-readable memory of claim 40 wherein the allocation array and the data regions are located at opposite ends of the block and as new data regions and allocation array entries are selected, the allocation array and the data regions grow towards each other.

42. The computer-readable memory of claim 40 wherein each block has an erase count that indicates the number of times the block has been erased and wherein the step of selecting a block in the memory further comprises the step of selecting the block in the memory based on the erase count.

43. The computer-readable memory of claim 40, further comprising the step of deallocating a data region in the block by setting the corresponding allocation array entry to indicate that the data region is deallocated.

44. The computer-readable memory of claim 40, including the step of, before setting the selected allocation array entry to contain a reference to the new data region, setting the selected allocation array entry to allocation-in-process wherein the step of setting the selected allocation array entry to allocated occurs after the data is stored in the new data region so that if an error occurs when storing the data, the selected allocation array entry will not falsely indicate that the data has been correctly stored in the new data region.

45. The computer-readable memory of claim 40 wherein the step of selecting an allocation array entry selects an entry that was set to free indicating that its corresponding data region was reclaimed.