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

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.