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

Claim 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.

Claim 6

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.

Claim 7

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.

Claim 10

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.

Claim 11

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.

Claim 19

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.

Claim 20

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.

Claim 21

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.

Claim 22

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.

Claim 23

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.

Claim 24

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.

Claim 25

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.

Claim 31

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.