Metadata rebuild in a flash memory controller following a loss of power

• US 20090172262A1
• Filed: 04/08/2008
• Published: 07/02/2009
• Est. Priority Date: 12/27/2007
• Status: Active Grant

• Current Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Original Assignee: Pliant Technology, Inc. (Western Digital Corporation)
• Inventors: Olbrich, Aaron K., Prins, Douglas A.
• Granted Patent: US 8,621,137 B2
• Time in Patent Office: Days
• US Class Current: 711/103
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 13/1657 Access to multiple memories
• CPC Class Codes: G06F 13/28 using burst mode transfer, e.g. direct memory access DMA, cycle steal G06F13/32 takes precedence
• CPC Class Codes: G06F 2212/7201 Logical to physical mapping or translation of blocks or pages
• CPC Class Codes: G06F 2212/7203 Temporary buffering, e.g. using volatile buffer or dedicated buffer blocks
• CPC Class Codes: G06F 2212/7205 Cleaning, compaction, garbage collection, erase control
• CPC Class Codes: G06F 3/0604 Improving or facilitating administration, e.g. storage management
• CPC Class Codes: G06F 3/0659 Command handling arrangements, e.g. command buffers, queues, command scheduling
• CPC Class Codes: G06F 3/0679 Non-volatile semiconductor memory device, e.g. flash memory, one time programmable memory [OTP]
• CPC Class Codes: G11C 16/10 Programming or data input circuits
• CPC Class Codes: G11C 7/1051 Data output circuits, e.g. read-out amplifiers, data output buffers, data output registers, data output level conversion circuits
• CPC Class Codes: G11C 7/1063 Control signal output circuits, e.g. status or busy flags, feedback command signals

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.

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.

2. The method as in claim 1, in which step (d)(3) also includes writing physical address-related information to volatile memory, the address-related information relating to the location of the first data in the flash memory.

3. The method as in claim 2, in which:

the physical address-related information is associated in the volatile memory with logical address information.

4. The method as in claim 1, in which:

steps (a)-(e) are carried out with respect to a first flash memory group made up of a plurality of flash memory devices, and

the same steps are independently carried out with respect to a second flash memory group made up of a plurality of flash memory devices, the steps on the first flash memory group and the steps on the second flash memory group overlapping in time.

5. The method as in claim 4, in which:

steps (a)-(e) are independently carried out with respect to third, fourth, fifth, sixth, seventh and eighth flash memory groups made up of a plurality of flash memory devices, the steps on all eight flash memory groups overlapping in time.

6. The method as in claim 4, in which:

each area of flash memory includes memory locations on a plurality of separate flash memory devices.

7. The method as in claim 6, in which:

each area of flash memory is erasable as a unit by the flash memory controller.

8. The method as in claim 7, in which:

each subarea includes separate memory locations on a plurality of separate flash memory devices.

9. The method as in claim 8, in which:

each separate subarea memory location consists of a flash page.

10. The method as in claim 3, in which:

following the step (e) population of the first table, performing steps (d)(1)-(4) for each subarea of the first area.

11. The method as in claim 4, further including:

(f) copying from flash memory to volatile memory a third table containing metadata regarding a second area of flash memory;

(g) based on one or more indicators, determining whether the second area of flash memory was open, closed or erased at the time of power loss;

(h) if the second area was erased, placing an identifier of the second area in the memory structure that contains identifications of flash memory areas that may be written to;

(i) if the second area was closed, performing the following substeps for each of a plurality of flash memory subareas, each such subarea being a part of the second flash memory area, the third table containing metadata for each such subarea;

(1) reading from the third table a logical address;

(2) determining whether an entry corresponding to the logical address is stored in the second table;

(3) if no such entry is found, setting a fifth indicator in volatile memory to a state indicating that third data stored in the subarea is valid;

(4) if such an entry is found, performing the following sub-substeps;

i. reading from the third table a sixth indicator relating to the relative time when the third data was written to the subarea;

ii. comparing the sixth indicator to a seventh indicator stored in volatile memory, the seventh indicator relating to the relative time when fourth data was written to a different flash memory area and/or flash memory subarea;

iii. if the comparison indicates that the third data was written earlier, setting the fifth indicator to a state indicating that the third data is invalid;

iv. if the comparison indicates that the third data was written later, setting an eighth indicator in volatile memory to a state indicating that the fourth data is invalid;

(j) if the second area was open, reading from the flash memory area metadata associated with each subarea within the second area, and using the metadata to populate the third table.

12. The method as in claim 1, in which:

step (d)(4)(iii) further includes writing physical address-related information to volatile memory, the address-related information relating to the location of the second data in the flash memory.

13. The method as in claim 12, in which:

the physical address-related information is written into the second table.

14. The method as in claim 13, in which:

the second table location into which the physical address-related information is written is a location corresponding to the logical address.

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;

16. Programming as in claim 15, in which:

the first group of flash memory blocks is stored on a first set of flash memory devices and the second group of flash memory blocks is stored on a second set of flash memory devices.

17. Programming as in claim 16, in which:

the first set of flash memory devices stores data associated with a first logical address range and the second set of flash memory devices stores data associated with a second logical address range that does not overlap the first logical address range.

18. Programming as in claim 17, in which:

the first time stamp is stored in the first metadata table, and the third time stamp is stored in the third metadata table.

19. Programming as in claim 17, in which:

the first information is a first logical address and the second information is a second logical address.

20. Programming as in claim 19, in which:

the first entry includes a physical address in the first group of flash memory blocks and the second entry includes a physical address in the second group of flash memory blocks.

21. Programming as in claim 17, in which:

the first power loss recovery programming that 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 the second metadata table and, if the second metadata table entry contains valid information, compares a first time stamp with a second time stamp and overwrites the second metadata table entry if the first time stamp is later than the second time stamp, is part of a first loop that handles a plurality of portions of the first group in sequence, in each case reading from the first table information relating to the portion, using that information to identify an entry in the second metadata table, comparing two time stamps and overwriting a second metadata table entry if one of the time stamps is later than the other.

22. Programming as in claim 21, in which:

each portion of the first group consists of a plurality of flash pages, each page stored on a separate flash memory device from the first set of flash memory devices, and

each portion of the second group consists of a plurality of flash pages, each page stored on a separate flash memory device from the second set of flash memory devices.

23. Programming as in claim 22, in which:

the first loop is part of a second loop which proceeds through a sequence of groups of flash memory blocks, each group being stored in the first set of flash memory devices.

24. Programming as in claim 17, in which:

the first power loss recovery program includes programming that, if the indicator(s) indicate that the first group did not contain valid data, writes an identifier of the first group to a list contained in volatile memory within the flash memory controller, the list constituting a list of groups of flash memory blocks that are available for writing.

25. Programming as in claim 17, further including:

third power loss recovery programming that;

copies a fourth metadata table from flash memory to volatile memory within the flash controller, the fourth table relating to a third group of flash memory blocks;

reads one or more indicators from the fourth table, the indicator(s) relating to the status of the third group at the time of power loss;

if the indicator(s) indicate that the third group contained valid data and had been closed for writing at the time of power loss, reads from the fourth table third information relating to a portion of the third group, and uses the third information to identify a third entry in the second metadata table;

if the second metadata table third entry contains valid information, compares a fifth time stamp with a sixth time stamp and overwrites the second metadata table third entry if the fifth time stamp is later than the sixth time stamp; and

fourth power loss recovery programming that;

copies a fifth metadata table from flash memory to volatile memory within the flash controller, the fifth table relating to a fourth group of flash memory blocks;

reads one or more indicators from the fifth table, the indicator(s) relating to the status of the fourth group at the time of power loss;

if the indicator(s) indicate that the fourth group contained valid data and had been closed for writing at the time of power loss, reads from the fifth table fourth information relating to a portion of the fourth group, and uses the fourth information to identify a fourth entry in the second metadata table;

if the second metadata table fourth entry contains valid information, compares a seventh time stamp with an eighth time stamp and overwrites the second metadata table fourth entry if the seventh time stamp is later than the eighth time stamp;

wherein, the third group of flash memory blocks is stored on a third set of flash memory devices and the fourth group of flash memory blocks is stored on a fourth set of flash memory devices, the third set of flash memory devices stores data associated with a third logical address range, the fourth set of flash memory devices stores data associated with a fourth logical address range, and the first, second, third and fourth logical address ranges do not overlap.