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

• US 6,256,642 B1
• Filed: 01/29/1992
• Issued: 07/03/2001
• Est. Priority Date: 01/29/1992
• Status: Expired due to Fees

• 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:
  US07/828,763
• Time in Patent Office: 3,443 Days
• Field of Search: 395/600, 370/82, 707/205
• 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 memory management of a block-erasable flash-EProm. The system comprises a FEProm manager and a file system. The FEProm manager manages memory allocation and deallocation of the FEProm. The file system is a hierarchical directory system and uses the FEProm manager to allocate and deallocate memory. In a preferred embodiment, the FEProm manager of the present invention provides for allocation of free space, deallocation of allocated space, and reclamation of deallocated space in a block-erasable FEProm. Each block of the FEProm contains a block allocation structure, data regions, and free space. The block allocation structure contains an allocation array which describes the allocation of the data region.

Claims

1. A manager for a computer memory comprising:

a block allocation routine, the memory divided into blocks of memory locations, each block having an allocation table and a data region divided into data areas, each allocation table having entries corresponding to region data areas, the block allocation routine for selecting a block in which to store data;

a data area allocation routine for selecting a data area within the data region for the selected block in which to store data, for selecting an allocation table entry to correspond to the selected data area, and for setting the selected allocation table entry to correspond to the selected data area and to an allocated state; and

a storage routine for storing data in the selected data area.

2. The manager for a computer memory of claim 1 further comprising:

a data area deallocation routine for setting an allocation table entry that is in the allocated state to a deallocated state; and

a block reclamation routine for reclaiming data areas corresponding to allocation table entries that are in that deallocated state.

3. The manager for a computer memory of claim 1 further comprising:

an initialization routine, each block having header information, the initialization routine for gathering information from the headers and from the allocation tables and storing the gathered information in a memory cache.

4. A method of reclaiming deallocated space in a block-eraseable, programmable, read-only memory, the memory having blocks, the method comprising the steps of:

identifying data regions as deallocated or allocated in a block to be reclaimed;

erasing a spare block; and

copying allocated data regions from the block to be reclaimed to the spare block whereby a memory area corresponding to the deallocated data region is reclaimed for allocation.

5. The method of claim 4 wherein the allocated data regions are copied into contiguous memory locations in the spare block.

6. A method of addressing a data region in a computer memory device, the memory divided into blocks, each block having a physical block number, the method comprising the steps of:

storing an allocation table in each block, the allocation table having entries that indicate an offset of a data region within the block and that have an entry index;

storing a logical block number in each block;

identifying a data region by logical block number and allocation table entry index; and

generating an address to the identified data region based on the logical block number and the allocation table entry index.

7. The method of claim 6 wherein the step of generating an address includes the steps of:

determining the physical block number from the logical block number, each block having a corresponding start address;

retrieving the offset from the allocation table entry in the determined physical block number that is indexed by the allocation table entry index; and

adding the retrieved offset to the start address of the block with the determined physical block number to generate the address of the identified data region.

8. The method of claim 6 or 7 wherein the computer memory device is a block-erasable, programmable, read-only memory.

9. A method of leveling block erasures in a block-erasable, programmable, read-only memory, the method comprising the steps of:

identifying a first block that has been erased;

identifying a second block that has been erased a fewer number of times than the first block; and

swapping the data in the first block with the data in the second block.

10. A method of managing memory in a block-erasable, programmable, read-only memory, the memory being divided into blocks of memory locations, each block having an allocation table and a data region divided into data areas, each allocation table having entries corresponding to region data areas, the method comprising the steps of:

selecting a block in which to store data;

selecting a data area within the data region for the selected block in which to store data;

selecting an allocation table entry to correspond to the selected data area;

setting the selected allocation table entry to correspond to the selected data area and to an allocated state; and

storing data in the selected data area.

11. The method of claim 10, further comprising the steps of:

setting an allocation table entry that is in the allocated state to a deallocated state; and

reclaiming data areas corresponding to allocation table entries that are in that deallocated state.

12. The method of claim 10, each block having header information, further comprising the steps of:

gathering information from the headers and from the allocation tables; and

storing the gathered information in a memory cache.

13. A method of managing memory in a block-erasable, programmable, read-only memory, the memory being divided into blocks of memory locations, each block have a table and a data region divided into data areas, each table having entries corresponding to the data areas, the method comprising the steps of:

selecting a block in which to store data;

selecting a data area within the data region for the selected block in which to store data;

selecting a table entry to correspond to the selected data area;

setting the selected table entry to correspond to the selected data area and to indicate that the data area contains data; and

storing data in the selected data area.