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 the following steps:
- (a) copying from flash memory to volatile memory a first table containing metadata regarding a first area of flash memory;
(b) based on one or more indicators, determining whether the first area of flash memory was open, closed or erased at the time of power loss;
(c) if the first area was erased, placing an identifier of the first area in a memory structure that contains identifications of flash memory areas that may be written to;
(d) if the first area was closed, performing the following substeps for each of a plurality of flash memory subareas, each such subarea being a part of the first flash memory area, the first table containing metadata for each such subarea;
(1) reading from the first table a logical address;
(2) determining whether an entry corresponding to the logical address is stored in a second table in volatile memory;
(3) if no such entry is found, setting a first indicator in volatile memory to a state indicating that first data stored in the subarea is valid;
(4) if such an entry is found, performing the following sub-substeps;
i. reading from the first table a second indicator relating to the relative time when the first data was written to the subarea;
ii. comparing the second indicator to a third indicator stored in volatile memory, the third indicator relating to the relative time when second data was written to a different flash memory area and/or flash memory subarea;
iii. if the comparison indicates that the first data was written earlier, setting the first indicator to a state indicating that the first data is invalid;
iv. if the comparison indicates that the first data was written later, setting a fourth indicator in volatile memory to a state indicating that the second data is invalid;
(e) if the first area was open, reading from the first flash memory area metadata associated with each subarea within the first flash memory area, 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.
-
Citations
25 Claims
-
1. A method of rebuilding metadata used in a flash memory controller following a loss of power, comprising the following steps:
-
(a) copying from flash memory to volatile memory a first table containing metadata regarding a first area of flash memory; (b) based on one or more indicators, determining whether the first area of flash memory was open, closed or erased at the time of power loss; (c) if the first area was erased, placing an identifier of the first area in a memory structure that contains identifications of flash memory areas that may be written to; (d) if the first area was closed, performing the following substeps for each of a plurality of flash memory subareas, each such subarea being a part of the first flash memory area, the first table containing metadata for each such subarea; (1) reading from the first table a logical address; (2) determining whether an entry corresponding to the logical address is stored in a second table in volatile memory; (3) if no such entry is found, setting a first indicator in volatile memory to a state indicating that first data stored in the subarea is valid; (4) if such an entry is found, performing the following sub-substeps; i. reading from the first table a second indicator relating to the relative time when the first data was written to the subarea; ii. comparing the second indicator to a third indicator stored in volatile memory, the third indicator relating to the relative time when second data was written to a different flash memory area and/or flash memory subarea; iii. if the comparison indicates that the first data was written earlier, setting the first indicator to a state indicating that the first data is invalid; iv. if the comparison indicates that the first data was written later, setting a fourth indicator in volatile memory to a state indicating that the second data is invalid; (e) if the first area was open, reading from the first flash memory area metadata associated with each subarea within the first flash memory area, 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)
-
-
15. Programming stored in a flash memory controller, including the following:
-
first power loss recovery programming that; copies a first metadata table from flash memory to volatile memory within the flash controller, the first table relating to a first group of flash memory blocks; reads one or more indicators from the first table, the indicator(s) relating to the status of the first group at the time of power loss; if the indicator(s) indicate that the first group contained valid data and had been closed for writing at the time of power loss, reads from the first table first information relating to a portion of the first group, and uses the first information to identify a first entry in a second metadata table contained in volatile memory within the flash controller; if the second metadata table first entry contains valid information, compares a first time stamp with a second time stamp and overwrites the second metadata table first entry if the first time stamp is later than the second time stamp; and second power loss recovery programming that; copies a third metadata table from flash memory to volatile memory within the flash controller, the third table relating to a second group of flash memory blocks; reads one or more indicators from the third table, the indicator(s) relating to the status of the second group at the time of power loss; if the indicator(s) indicate that the second group contained valid data and had been closed for writing at the time of power loss, reads from the third table second information relating to a portion of the second group, and uses the second information to identify a second entry in the second metadata table; if the second metadata table second entry contains valid information, compares a third time stamp with a fourth time stamp and overwrites 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)
-
Specification