Patent ID: 8621137

Claim:
A method of rebuilding metadata used in a flash memory controller following a loss of power, comprising: (a) copying from flash memory to volatile memory a first table containing metadata regarding a first block in flash memory, each block comprising a plurality of pages of flash memory, wherein the first table contains logical addresses for each of a sequence of physical locations in flash memory; (b) based on one or more indicators, determining whether the first block in flash memory was open for writing, closed for writing or erased at the time of power loss; (c) if the first block was erased, placing an identifier of the first block in a memory structure that contains identifications of flash memory blocks that may be written to; (d) if the first block was closed for writing, performing the following sub-operations for each of two or more of the flash memory pages of the first block, the first table containing metadata for each such page: (1) reading from the first table a logical address; (2) determining whether an entry corresponding to the logical address and associated with a second block is found in a second table in volatile memory, the second table containing physical location information in flash memory for each of a sequence of logical addresses; (3) if no such entry is found, setting a first valid bit in volatile memory to a state indicating that first data stored in a first page is valid; (4) if such an entry is found, performing the following sub-sub-operations: i. reading from the first table in volatile memory a first time stamp relating to a closing time of the first block; ii. comparing the first time stamp to a second time stamp stored in volatile memory, the second time stamp relating to a closing time of the second block; iii. if the comparison indicates that the first data was written earlier, setting the first valid bit to a state indicating that the first data is invalid; iv. if the comparison indicates that the first data was written later, setting a second valid bit in volatile memory to a state indicating that second data is invalid; (e) if the first block was open for writing, reading from the first block metadata associated with each page within the first block, and using the metadata to populate the first table.