Metadata rebuild in a flash memory controller following a loss of power
First Claim
Patent Images
1. 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.
11 Assignments
0 Petitions
Accused Products
Abstract
A method of rebuilding metadata in a flash memory controller following a loss of power. The method includes reading logical address information associated with an area of flash memory, and using time stamp information to determine if data stored in the flash memory area is valid.
156 Citations
32 Claims
-
1. 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 26)
-
-
15. A flash memory controller comprising a non-volatile storage medium, wherein the non-volatile storage medium comprises:
-
a processor; a first set of instructions for execution by the processor, the first set of instructions when executed causing the flash memory controller to perform a first method for carrying out power loss recovery comprising; copying a first metadata table from flash memory to volatile memory within the flash memory controller, the first metadata table relating to a first group of flash memory blocks and containing logical addresses for each of a sequence of physical locations in flash memory; reading one or more valid bits and flags from the first metadata table, the valid bits and flags relating to a status of the first group at the time of power loss, wherein the one or more valid bits and flags from the first metadata table include one or more indicia indicating whether the first group was open for writing or closed for writing at the time of power loss; if the valid bits and flags indicate that the first group contained valid data and had been closed for writing at the time of power loss, reading from the first metadata table first information relating to a portion of the first group, and using the first information to identify a first entry in a second metadata table contained in volatile memory within the flash memory controller, the second metadata table containing physical location information in flash memory for each of a sequence of logical addresses; if the second metadata table first entry contains valid information, comparing a first time stamp with a second time stamp and overwriting the second metadata table first entry if the first time stamp is later than the second time stamp wherein the first time stamp is updated when the first group of flash memory blocks is closed for writing and the second time stamp is updated when a group of flash memory blocks related to the second metadata table is closed for writing; and a second set of instructions for execution by the processor, the instructions when executed causing the flash memory controller to perform a second method for carrying out power loss recovery comprising; copying a third metadata table from flash memory to volatile memory within the flash memory controller, the third metadata table relating to a second group of flash memory blocks; reading one or more valid bits and flags from the third metadata table, the valid bits and flags relating to a status of the second group at the time of power loss, wherein the one or more valid bits and flags from the third table include one or more indicia indicating whether the second group was open for writing or closed for writing at the time of power loss; if the valid bits and flags indicate that the second group contained valid data and had been closed for writing at the time of power loss, reading from the third metadata table second information relating to a portion of the second group, and using the second information to identify a second entry in the second metadata table; if the second metadata table second entry contains valid information, comparing a third time stamp with a fourth time stamp and overwriting the second metadata table second entry if the third time stamp is later than the fourth time stamp. - View Dependent Claims (16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 27)
-
-
28. A system including a flash memory controller comprising a flash memory interface for coupling to a flash memory, a system memory interface for coupling to a system memory, a host interface for coupling to a host, and a plurality of flash memory devices, the flash memory controller comprising:
-
a processor; a non-volatile storage medium, the non-volatile medium further storing a first set of instructions for execution by the processor, the first set of instructions when executed causing the flash memory controller to perform a first method for carrying out power loss recovery comprising; copying a first metadata table from flash memory to volatile memory within the flash memory controller, the first table relating to a first group of flash memory blocks and containing logical addresses for each of a sequence of physical locations in flash memory; reading one or more valid bits and flags from the first table, the valid bits and flags relating to a status of the first group at the time of power loss, wherein the one or more valid bits and flags from the first table include one or more indicia indicating whether the first group was open for writing or closed for writing at the time of power loss; if the valid bits and flags indicate that the first group contained valid data and had been closed for writing at the time of power loss, reading from the first table first information relating to a portion of the first group, and using the first information to identify a first entry in a second metadata table contained in volatile memory within the flash memory controller, the second metadata table containing physical location information in flash memory for each of a sequence of logical addresses; if the second metadata table first entry contains valid information, comparing a first time stamp with a second time stamp and overwriting the second metadata table first entry if the first time stamp is later than the second time stamp;
whereinthe first time stamp is updated when the first group of flash memory blocks is closed for writing and the second time stamp is updated when a group of flash memory blocks related to the second metadata table is closed for writing. - View Dependent Claims (29, 30, 31, 32)
-
Specification