Systems and methods for recovering data from failed portions of a flash drive

• US 9,021,333 B1
• Filed: 05/22/2012
• Issued: 04/28/2015
• Est. Priority Date: 05/22/2012
• Status: Active Grant

• Current Assignee: Ip Gem Group, LLC
• Original Assignee: PMC-Sierra Incorporated (Microchip Technology Incorporated)
• Inventors: Northcott, Philip L.
• Primary Examiner(s): Blair, April Y
• Assistant Examiner(s): GANDHI, DIPAKKUMAR B
• Application Number:
  US13/477,601
• Time in Patent Office: 1,071 Days
• US Class Current: 714/766
• CPC Class Codes: G06F 11/073 in a memory management context, e.g. virtual memory or cache management memory management G06F12/00; testing of static memory units G11C29/00
• CPC Class Codes: G06F 11/0793 Remedial or corrective actions recovery from an exception in an instruction pipeline G06F9/3861; by retry G06F11/1402; for recovering from a failure of a protocol instance or entity H04L69/40

Abstract

Apparatus and methods provide relatively low uncorrectable bit error rates, low write amplification, long life, fast and efficient retrieval, and efficient storage density such that a solid-state drive (SSD) can be implemented using relatively inexpensive MLC Flash for an enterprise storage application.

Claims

1. A method of recovering data from a failed page of flash memory, the method comprising:

reading contents of flash pages of a page grid containing the failed page, wherein tertiary parity symbols are distributed among the pages of a last page stripe of the page grid, wherein each of the pages of the page grid have ECC codewords stored therein;

(a) performing error correction on each page stripe of the page grid according to a gear with which the page stripe was encoded;

(b) arranging the data of the page grid to form tertiary codewords;

(c) marking symbols of the tertiary codewords that are associated with the failed page as erasures;

(d) performing error correction decoding using mixed error and erasure decoding on the tertiary codewords to update the tertiary codewords;

(e) arranging the updated tertiary codewords to generate corrected versions of the page stripes;

(f) performing error correction on page stripes of the page grid according to the gear with which each page stripe was encoded;

performing one or more iterations of (b) through (f) until a stopping criterion is reached or a determination that the recovered data has been recovered without error; and

releasing the recovered data to a requester based at least partly on the determination that the recovered data has been recovered without error;

wherein at least (a) is performed in an integrated circuit.

2. The method of claim 1, wherein the determination that the recovered data has been recovered without error is determined probabilistically to a high confidence.

3. The method of claim 1, wherein (a) and (f) include performing error correction on the primary on tertiary parity codewords of each page of a last page stripe.

4. The method of claim 1, wherein the tertiary ECC is a Reed-Solomon code.

5. The method of claim 1, further comprising, prior to (c):

(g) performing error correction decoding on tertiary codewords of the page grid to update the tertiary codewords;

(h) arranging the updated tertiary codewords to generate corrected versions of the page stripes;

(i) performing error correction on page stripes of the page grid according to the gear with which each stripe was encoded;

performing one or more iterations of (g), (h), (i) until a stopping criterion is reached or a determination is made that the recovered data has been recovered without error; and

releasing the recovered data to the requestor based at least partly on the determination that the recovered data has been recovered without error.

6. The method of claim 1, further comprising identifying the failed page by:

retrieving fingerprints from among the pages of the page grid, wherein the fingerprints are based at least partly on physical addresses for the pages; and

calculating and selecting a page having the largest magnitude difference between the stored fingerprint and an expected fingerprint as the failed page, so long as that difference exceeds a predetermined threshold.

7. The method of claim 1, further comprising identifying the failed page by counting the number of uncorrectable primary codewords associated with each page, and selecting a page having the most uncorrectable primary codewords as the failed page.

8. An apparatus comprising:

a first circuit configured to read contents of flash pages of a page grid containing a failed page of flash memory, wherein tertiary parity symbols are distributed among the pages of a last page stripe of the page grid, wherein each of the pages of the page grid have ECC codewords stored therein;

a second circuit configured to (a) perform error correction on each page stripe of the page grid according to a gear with which the page stripe was encoded;

the first circuit configured to (b) arrange the data of the page grid to form tertiary codewords;

the first circuit configured to (c) mark symbols of the tertiary codewords that are associated with the failed page as erasures;

the second circuit configured to (d) perform error correction decoding with mixed error and erasure decoding on the tertiary codewords to update the tertiary codewords;

the first circuit configured to (e) arrange the updated tertiary codewords to generate corrected versions of the page stripes;

the second circuit configured to (f) perform error correction on page stripes of the page grid according to the gear with which each page stripe was encoded;

wherein the first circuit and the second circuit are configured to iterate performance of (b) through (f) until a stopping criterion is reached or a determination that the recovered data has been recovered without error; and

the first circuit configured to release the recovered data to a requester based at least partly on the determination that data has been recovered without error.

9. The apparatus of claim 8, wherein the determination that the recovered data has been recovered without error is determined probabilistically to a high confidence.

10. The apparatus of claim 8, wherein the second circuit is further configured to perform error correction on the primary on tertiary parity codewords of each page of a last page stripe.

11. The apparatus of claim 8, wherein the tertiary ECC is a Reed-Solomon code.

12. The apparatus of claim 8:

the second circuit is configured to (g) perform error correction decoding on tertiary codewords of the page grid to update the tertiary codewords prior to (c);

the first circuit is configured to (h) arrange the updated tertiary codewords to generate corrected versions of the page stripes prior to (c);

the second circuit is configured to (i) perform error correction on page stripes of the page grid according to the gear with which each stripe was encoded prior to (c);

wherein the first circuit and the second circuit are configured to iterate performance of (g), (h), and (i) until a stopping criterion is reached or a determination is made that the recovered data has been recovered without error; and

releasing the recovered data to the requestor based at least partly on the determination that the recovered data has been recovered without error.

13. The apparatus of claim 8, wherein the first circuit is further configured to:

retrieve fingerprints from among the pages of the page grid, wherein the fingerprints are based at least partly on physical addresses for the pages; and

calculate and select a page having the largest magnitude difference between the stored fingerprint and an expected fingerprint as the failed page, so long as that difference exceeds a predetermined threshold.

14. The apparatus of claim 8, wherein the first circuit is further configured to count the number of uncorrectable primary codewords associated with each page, and select a page having the most uncorrectable primary codewords as the failed page.

15. An apparatus for recovering data from a failed page of flash memory, the apparatus comprising:

a means for reading contents of flash pages of a page grid containing the failed page, wherein tertiary parity symbols are distributed among the pages of a last page stripe of the page grid, wherein each of the pages of the page grid have ECC codewords stored therein;

a means for recovering data, the recovering data means further;

(a) performing error correction on each page stripe of the page grid according to a gear with which the page stripe was encoded;

(b) arranging the data of the page grid to form tertiary codewords;

(c) marking symbols of the tertiary codewords that are associated with the failed page as erasures;

(d) performing error correction decoding using mixed error and erasure decoding on the tertiary codewords to update the tertiary codewords;

(e) arranging the updated tertiary codewords to generate corrected versions of the page stripes;

(f) performing error correction on page stripes of the page grid according to the gear with which each page stripe was encoded;

wherein the recovering data means further performing one or more iterations of (b) through (f) above until a stopping criterion is reached or a determination that the recovered data has been recovered without error; and

a means for releasing the recovered data to a requester based at least partly on the determination that the recovered data has been recovered without error.

16. The apparatus of claim 15, wherein the determination that the recovered data has been recovered without error is determined probabilistically to a high confidence.

17. The apparatus of claim 15, wherein the recovering data means is further configured to perform error correction on the primary on tertiary parity codewords of each page of a last page stripe.

18. The apparatus of claim 15, wherein the tertiary ECC is a Reed-Solomon code.

19. The apparatus of claim 15, the recovering data means further:

(g) performing error correction decoding on tertiary codewords of the page grid to update the tertiary codewords prior to (c);

(h) arranging the updated tertiary codewords to generate corrected versions of the page stripes prior to (c);

(i) performing error correction on page stripes of the page grid according to the gear with which each stripe was encoded prior to (c);

the recovering data means further performing one or more iterations of (g), (h), (i) until a stopping criterion is reached or a determination that the recovered data has been recovered without error; and

the releasing means further releasing the recovered data to the requestor based at least partly on the determination that the recovered data has been recovered without error.

20. The apparatus of claim 15, further comprising a means for identifying the failed page, the identifying means further:

retrieving fingerprints from among the pages of the page grid, wherein the fingerprints are based at least partly on physical addresses for the pages; and

calculating and selecting a page having the largest magnitude difference between the stored fingerprint and an expected fingerprint as the failed page, so long as that difference exceeds a predetermined threshold.

21. The apparatus of claim 15, further comprising a means for identifying the failed page, the identifying means further counting the number of uncorrectable primary codewords associated with each page, and selecting a page having the most uncorrectable primary codewords as the failed page.