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

• US 9,152,556 B2
• Filed: 12/11/2013
• Issued: 10/06/2015
• Est. Priority Date: 12/27/2007
• Status: Active Grant

• Current Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Original Assignee: SanDisk Enterprise IP LLC (Western Digital Corporation)
• Inventors: Olbrich, Aaron K., Prins, Douglas A.
• Primary Examiner(s): Tseng, Cheng-Yuan
• Assistant Examiner(s): Mercado, Ramon A
• Application Number:
  US14/103,026
• Publication Number:
  US 20140101378A1
• Time in Patent Office: 664 Days
• Field of Search: 711/103, 711/5, 711/14, 711/147, 711/169, 710/317
• US Class Current: 1/1
• 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 is provided. 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 are valid.

Claims

1. A method of rebuilding metadata used in a flash memory controller following a loss of power, comprising:

copying metadata information from flash memory to volatile memory, the metadata information including metadata regarding a first block in flash memory and logical addresses for a sequence of physical locations in flash memory;

in accordance with the copied metadata information, storing a plurality of metadata tables in the volatile memory, the plurality of metadata tables including;

a first table containing metadata concerning one or more respective blocks, including the first block, and logical addresses for the sequence of physical locations in flash memory, and

a second table containing metadata that includes physical location information in flash memory for each of a sequence of logical addresses;

in accordance with metadata in the first table, determining whether the first block in flash memory was closed when the power loss occurred; and

in accordance with a determination that the first block was closed when the power loss occurred;

reading from the first table a logical address for the first block;

determining from the second table whether the logical address corresponds to a second block that is a different block than the first block;

in accordance with a determination that the logical address corresponds to a second block that is a different block than the first block, comparing time stamps related, respectively, to the first block and the second block;

in accordance with a determination, based on the comparison, that data in the first block was written earlier than data in the second block, setting a first valid bit in the plurality of metadata tables to a state indicating that the data in the first block is invalid, and

in accordance with a determination, based on the comparison, that the data in the first block was written later than data in the second block, setting a second valid bit in volatile memory to a state indicating that data in the second block is invalid.

2. The method of claim 1, further including, in accordance with a determination that the logical address does not correspond to a second block that is a different block than the first block, setting the first valid bit to a state indicating that the data in the first block is valid.

3. The method of claim 1, further including:

in accordance with metadata in the first table, determining whether the first block in flash memory was erased when the power loss occurred; and

in accordance with a determination that the first block was erased when the power loss occurred, placing an identifier of the first block in a memory structure that contains identifications of flash memory blocks that may be written to.

4. The method of claim 1, further including:

in accordance with metadata in the first table, determining whether the first block in flash memory was open when the power loss occurred; and

in accordance with a determination that the first block was open when the power loss occurred;

reading from the first block metadata associated with one or more pages within the first block; and

using the metadata regarding the first block to populate the first table.

5. The method of claim 1, wherein:

the logical address for the first block pertains to a respective page in the first block;

determining whether the logical address corresponds to the second block further comprises determining whether the logical address corresponds to a respective page in a second block; and

in accordance with a determination that the logical address corresponds to a respective page in a second block, the operation of comparing time stamps related, respectively, to the first block and the second block further comprises comparing a first time stamp relating to the respective page of the first block and a second time stamp relating to the respective page of the second block.

6. The method of claim 5, wherein:

the first valid bit pertains to validity of the respective page of the first block; and

the second valid bit pertains to validity of the respective page of the second block.

7. The method of claim 5, wherein the first block includes memory locations on a plurality of separate flash memory die.

8. The method of claim 7, wherein the respective page of the first block includes memory locations on a plurality of separate flash memory die.

9. The method of claim 1, further including:

determining a count of valid bits having a state indicating that data in the first block is invalid; and

in accordance with the count of valid bits, performing a garbage collection operation on the first block.

10. A memory controller comprising:

one or more processors, each including an arithmetic logic unit and control logic that controls operations of the arithmetic logic unit (ALU);

memory;

instructions, stored in memory and configured to be executed by the one or more processors, that when executed by the one or more processors cause the non-volatile memory controller to;

copy metadata information from flash memory to volatile memory, the metadata information including metadata regarding a first block in flash memory and logical addresses for a sequence of physical locations in flash memory;

in accordance with the copied metadata information, store a plurality of metadata tables in the volatile memory, the plurality of metadata tables including;

a first table containing metadata concerning one or more respective blocks, including the first block, and logical addresses for the sequence of physical locations in flash memory, and

a second table containing metadata that includes physical location information in flash memory for each of a sequence of logical addresses;

in accordance with metadata in the first table, determine whether the first block in flash memory was closed when the power loss occurred; and

in accordance with a determination that the first block was closed when the power loss occurred;

read from the first table a logical address for the first block;

determine from the second table whether the logical address corresponds to a second block that is a different block than the first block;

in accordance with a determination that the logical address corresponds to a second block that is a different block than the first block, compare time stamps related, respectively, to the first block and the second block;

in accordance with a determination, based on the comparison, that data in the first block was written earlier than data in the second block, set a first valid bit in the plurality of metadata tables to a state indicating that the data in the first block is invalid, and

in accordance with a determination, based on the comparison, that the data in the first block was written later than data in the second block, set a second valid bit in volatile memory to a state indicating that data in the second block is invalid.

11. The memory controller of claim 10, wherein the instructions further cause the one or more processors to, in accordance with a determination that the logical address does not correspond to a second block that is a different block than the first block, set the first valid bit to a state indicating that the data in the first block is valid.

12. The memory controller of claim 10, wherein the instructions further cause the one or more processors to:

in accordance with metadata in the first table, determine whether the first block in flash memory was erased when the power loss occurred; and

in accordance with a determination that the first block was erased when the power loss occurred, place an identifier of the first block in a memory structure that contains identifications of flash memory blocks that may be written to.

13. The memory controller of claim 10, wherein the instructions further cause the one or more processors to:

in accordance with metadata in the first table, determine whether the first block in flash memory was open when the power loss occurred; and

in accordance with a determination that the first block was open when the power loss occurred;

read from the first block metadata associated with one or more pages within the first block; and

use the metadata regarding the first block to populate the first table.

14. The memory controller of claim 10, wherein:

the logical address for the first block pertains to a respective page in the first block;

determining whether the logical address corresponds to the second block further comprises determining whether the logical address corresponds to a respective page in a second block; and

in accordance with a determination that the logical address corresponds to a respective page in a second block, the operation of comparing time stamps related, respectively, to the first block and the second block further comprises comparing a first time stamp relating to the respective page of the first block and a second time stamp relating to the respective page of the second block.

15. The memory controller of claim 14, wherein:

the first valid bit pertains to validity of the respective page of the first block; and

the second valid bit pertains to validity of the respective page of the second block.

16. The memory controller of claim 14, wherein the first block includes memory locations on a plurality of separate flash memory die.

17. The memory controller of claim 16, wherein the respective page of the first block includes memory locations on a plurality of separate flash memory die.

18. The memory controller of claim 10, wherein the instructions further cause the one or more processors to:

determine a count of valid bits having a state indicating that data in the first block is invalid; and

in accordance with the count of valid bits, perform a garbage collection operation on the first block.