Self recovery in a solid state drive

• US 9,122,587 B2
• Filed: 03/12/2013
• Issued: 09/01/2015
• Est. Priority Date: 03/06/2013
• Status: Active Grant

• Current Assignee: Seagate Technology LLC (Seagate Technology Holdings Plc)
• Original Assignee: Seagate Technology LLC (Seagate Technology Holdings Plc)
• Inventors: Baryudin, Leonid, Cohen, Earl T., Tang, Alex G.
• Primary Examiner(s): DUDEK JR, EDWARD J
• Application Number:
  US13/796,264
• Publication Number:
  US 20140258587A1
• Time in Patent Office: 903 Days
• Field of Search: 711/103, 711/202, 711/E12.008
• US Class Current: 1/1
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 2212/7201 Logical to physical mapping or translation of blocks or pages
• CPC Class Codes: G06F 2212/7209 Validity control, e.g. using flags, time stamps or sequence numbers

Abstract

An apparatus having a nonvolatile memory and a controller. The memory stores information in multiple pages. The information includes data units and headers. Each data unit is associated with a respective identifier in an address space of the apparatus and a respective location in the memory, has a respective header having the respective identifier, and is associated with a respective time stamp. Multiple headers include ones of the time stamps. The controller is configured to (i) read information stored in the pages, (ii) determine an order in which the data units were written based on the time stamps, (iii) locate based on the order (a) each last-written occurrence of the respective identifiers and (b) the respective locations of the data units associated with the last-written occurrences, and (iv) rebuild a map of the controller according to the respective locations of each last-written occurrence of each respective identifier.

Claims

1. An apparatus comprising:

a memory configured to store a plurality of time stamps associated with a plurality of data units in a plurality of bands, wherein (i) each of the bands comprises a plurality of blocks, (ii) each of the blocks comprises a plurality of memory pages, (iii) the memory pages are configured to store a plurality of host pages, (iv) each of the host pages comprises one or more of the data units, and (v) each of the host pages is associated with a respective identifier in a host address space, a respective location in a physical address space of the memory, and a respective epoch value; and

a controller configured to (i) read the time stamps from the memory, (ii) generate a plurality of lists identifying an order in which the data units were written to the memory based on the time stamps, (iii) perform a sequence of reads of the respective identifiers from the bands based on the lists and the respective epoch values, (iv) locate each last-written occurrence of the respective identifiers based on the sequence of reads and (v) rebuild a map identifying where the data units are stored in the physical address space of the memory according to the last-written occurrences of the respective identifiers.

2. The apparatus according to claim 1, wherein the memory and the controller are part of a solid-state drive.

3. The apparatus according to claim 1, wherein the controller is further configured to store in the map a respective length of the host pages associated with each of the last-written occurrences of each of the respective identifiers.

4. The apparatus according to claim 3, wherein the controller is further configured to store the respective lengths of the host pages in a table recording used space.

5. The apparatus according to claim 3, wherein the respective length of a first of the last-written occurrences differs from the respective length of a second of the last-written occurrences.

6. The apparatus according to claim 1, wherein the controller is further configured to initiate a self recovery automatically in response to a corruption of the map.

7. The apparatus according to claim 1, wherein the controller is further configured to read data from the memory suitable to decrypt one or more of the host pages stored in an encrypted condition.

8. The apparatus according to claim 1, wherein (i) the controller is further configured to initiate a self recovery in response to a signal received from a computer, and (ii) the map is rebuilt in the computer.

9. The apparatus according to claim 1, wherein the controller is further configured to initiate a self recovery automatically in response to encountering one or more discrepancies in metadata stored in the memory.

10. The apparatus according to claim 1, wherein the apparatus is implemented as one or more integrated circuits.

11. A method for self recovery in a memory controller, comprising the steps of:

(A) reading a plurality of time stamps associated with a plurality of data units stored in a plurality of bands in a memory coupled to the memory controller, wherein (i) each of the bands comprises a plurality of blocks, (ii) each of the blocks comprises a plurality of memory pages, (iii) the memory pages are configured to store a plurality of host pages, (iv) each of the host pages comprises one or more of the data units, and (v) each of the host pages is associated with a respective identifier in a host address space, a respective location in a physical address space of the memory, and a respective epoch value;

(B) generating a plurality of lists identifying an order in which the data units were written to the memory based on the time stamps;

(C) performing a sequence of reads of the respective identifiers from the bands based on the lists and the respective epoch values;

(D) locating each last-written occurrence of the respective identifiers based on the sequence of reads; and

(E) rebuilding a map identifying where the data units are stored in the physical address space of the memory according to the last-written occurrences of the respective identifiers.

12. The method according to claim 11, wherein the memory and the memory controller are part of a solid-state drive.

13. The method according to claim 11, further comprising the step of:

storing in the map a respective length of the host pages associated with each of the last-written occurrences of each of the respective identifiers.

14. The method according to claim 13, wherein the respective length of a first of the last-written occurrences differs from the respective length of a second of the last-written occurrences.

15. The method according to claim 11, further comprising the step of:

initiating the self recovery automatically in response to a corruption of the map.

16. The method according to claim 11, further comprising the step of:

reading data from the memory suitable to decrypt one or more of the host pages stored in an encrypted condition.

17. The method according to claim 11, further comprising the step of:

initiating the self recovery in response to a signal received from a computer, wherein the map is rebuilt in the computer.

18. The method according to claim 11, further comprising the step of:

initiating the self recovery automatically in response to encountering one or more discrepancies in metadata stored in the memory.

19. An apparatus comprising:

an interface configured to process a plurality of read/write operations to/from a memory, wherein (i) the memory is configured to store a plurality of time stamps associated with a plurality of data units in a plurality of bands, (ii) each of the bands comprises a plurality of blocks, (iii) each of the blocks comprises a plurality of memory pages, (iv) the memory pages are configured to store a plurality of host pages, (v) each of the host pages comprises one or more of the data units, and (vi) each of the host pages is associated with a respective identifier in a host address space, a respective location in a physical address space of the memory, and a respective epoch value; and

a controller configured to (i) read the time stamps from the memory, (ii) generate a plurality of lists identifying an order in which the data units were written to the memory based on the time stamps, (iii) perform a sequence of reads of the respective identifiers from the bands based on the lists and the respective epoch values, (iv) locate each last-written occurrence of the respective identifiers based on the sequence of reads and (v) rebuild a map identifying where the data units are stored in the physical address space of the memory according to the last-written occurrences of the respective identifiers.

20. The apparatus according to claim 19, wherein the memory and the controller are part of a solid-state drive.