Systems and methods for reclaiming memory for solid-state memory

• US 9,208,018 B1
• Filed: 03/15/2013
• Issued: 12/08/2015
• Est. Priority Date: 03/15/2013
• Status: Active Grant

• Current Assignee: Ip Gem Group, LLC
• Original Assignee: PMC-Sierra Incorporated (Microchip Technology Incorporated)
• Inventors: Northcott, Philip Lyon, Graumann, Peter, Bates, Stephen
• Primary Examiner(s): Rizk, Sam
• Assistant Examiner(s): Kabir, Enamul M
• Application Number:
  US13/844,486
• Time in Patent Office: 998 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 11/1008 in individual solid state devices G06F11/1004 takes precedence
• CPC Class Codes: G06F 11/1048 using arrangements adapted for a specific error detection or correction feature
• CPC Class Codes: G06F 11/1072 in multilevel memories

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 reliably implemented using various types of memory cells, including relatively inexpensive multi-level cell flash. One embodiment intelligently coordinates remapping of bad blocks with error correction code control, which eliminates the tables used to avoid bad blocks.

Claims

1. An electronically-implemented method of reclaiming a flash block of a flash array, the method comprising:

selecting a block grid for reclamation,

wherein block grids comprise a plurality of page grids, wherein page grids comprise a plurality of page stripes, wherein page stripes comprise a plurality of pages or integer fractions thereof,

wherein a block of pages comprises a smallest erasable unit of memory such that the plurality of page grids comprising a block grid are related by having pages belonging to the same blocks;

wherein a host accesses data using logical block addresses, wherein the logical blocks are stored in journaling cell slots, wherein valid data comprises data stored in journaling cell slots that the host expects to be able to access;

wherein a plurality of gears indicative of a journaling cell capacity and error correction coding scheme include at least a first gear, a second gear, and a gear zero, wherein page stripes associated with the first gear have a first non-zero integer journaling cell slot capacity and a first error correction coding scheme protective of data stored in the journaling cells of the first page stripe, wherein page stripes associated with the second gear have a second non-zero integer journaling cell slot capacity different from the first non-zero journaling slot capacity and a second error correction coding scheme protective of data stored in the journaling cells of the second page stripe, wherein page stripes associated with gear zero have a zero journaling cell slot capacity and no parity bits of the second error correction code;

wherein for valid data stored in the block grid, the method further comprises;

reading data from corresponding one or more journaling cell slots;

performing error correction on the read data to generate corrected data;

evaluating a condition of a page stripe based at least partly on the error correction decoding of the data within the journaling cell slots of the page stripe;

storing the corrected data into one or more journaling cell slots of page stripes of a different block grid;

updating one or more tables with new associations between logical block addresses and journaling cell slots;

erasing the blocks of the block grid;

updating gear settings for the page stripes of the block grid based at least partly on the evaluation conditions for the page stripes; and

making the page stripes of the block grid available for writing;

wherein at least selecting, reading, and storing are performed by an integrated circuit.

2. The method of claim 1, wherein performing error correction decoding on the read data to generate corrected data further comprises performing a second error correction decoding using parity data stored in reserved journaling cell slots of a page grid, wherein decoding of the second error correction is performed only when a first error correction using data stored within the page stripe is insufficient to correct the data with a probability of an incorrect decoding of less than 1E-15.

3. The method of claim 1, wherein updating gear settings further comprises selecting an error correction code method from a predetermined list having a known correction capability corresponding to the evaluated condition of the page stripe.

4. The method of claim 1, wherein updating gear settings further comprises selecting an error correction code method having a highest code rate that retains an error correction likelihood of 1E-15 or less given the evaluated condition of the page stripe.

5. The method of claim 1, wherein updating gear settings further comprises selecting an error correction code method having a highest code rate that retains an error correction likelihood of 1E-15 or less given the evaluated condition of the page stripe.

6. The method of claim 1, wherein updating gear settings further comprises determining a page stripe capacity counted in integer multiples of journaling cell slots based on the error correction code method selected.

7. The method of claim 1, wherein journaling cell slots contain a predetermined fixed amount of information, wherein page stripes, page grids, and block grids vary in cell slot capacity to accommodate a changing condition of pages of memory within page stripes, page grids, and block grids.

8. The method of claim 1, further comprising updating gear settings such that gear zero having zero journaling cell slot capacity is selected for a page stripe of a block grid based on at least one of the following:

the page stripe having pages from a block marked as unusable during manufacturing test, a decode latency for the page stripe exceeding a threshold, a page stripe having a condition for which no ECC scheme available in the device retains an error correction likelihood of 1E-15 or less, or a page stripe having pages from a die, plane, or block that has been determined to have failed.

9. The method of claim 1, further comprising:

updating gear settings such that gear zero having zero journaling cell slot capacity is selected for the page stripe of the block grid based on a decision to convert multi-level cells to quasi single-level cells by retiring a first half of paired pages of the page stripe; and

increasing the journaling cell capacity of the second half of the paired pages from a previous setting.

10. The method of claim 1, further comprising reading data from portions of page stripes of the selected block grid even if the portions do not contain valid data such that the condition of the page stripe can be assessed, wherein the criteria for selecting a different gear are evaluated based on error correction decoding of a complete page stripe.

11. The method of claim 10, further comprising:

journaling complete valid allocation blocks of page stripes of the selected block grid into available page stripes of the flash array;

discarding data of complete invalid allocation blocks of page stripes of the selected block grid; and

retaining in a buffer, a partial allocation block until the next page stripe is read.

12. The method of claim 11, wherein the determination of the gear setting is also based on whether any previous read of the page stripe met criteria indicating that a different gear is to be selected.

13. An apparatus for reclaiming a flash block of a flash array, the apparatus comprising:

a first circuit configured to select a block grid for reclamation,

wherein block grids comprise a plurality of page grids, wherein page grids comprise a plurality of page stripes, wherein page stripes comprise a plurality of pages or integer fractions thereof,

wherein a block of pages comprises a smallest erasable unit of memory such that the plurality of page grids comprising a block grid are related by having pages belonging to the same blocks;

wherein a host accesses data using logical block addresses, wherein the logical blocks are stored in journaling cell slots, wherein valid data comprises data stored in journaling cell slots that the host expects to be able to access;

wherein a plurality of gears indicative of a journaling cell capacity and error correction coding scheme include at least a first gear, a second gear, and a gear zero, wherein page stripes associated with the first gear have a first non-zero integer journaling cell slot capacity and a first error correction coding scheme protective of data stored in the journaling cells of the first page stripe, wherein page stripes associated with the second gear have a second non-zero integer journaling cell slot capacity different from the first non-zero journaling slot capacity and a second error correction coding scheme protective of data stored in the journaling cells of the second page stripe, wherein page stripes associated with gear zero have a zero journaling cell slot capacity and no parity bits of the second error correction code;

a second circuit including an ECC encoder/decoder, wherein the second circuit is configured to, when valid data stored in the block grid;

read data from corresponding one or more journaling cell slots;

perform error correction on the read data to generate corrected data;

evaluate a condition of a page stripe based at least partly on the error correction decoding of the data within the journaling cell slots of the page stripe;

store the corrected data into one or more journaling cell slots of page stripes of a different block grid;

update one or more tables with new associations between logical block addresses and journaling cell slots;

erase the blocks of the block grid;

update gear settings for the page stripes of the block grid based at least partly on the evaluation conditions for the page stripes; and

make the page stripes of the block grid available for writing.

14. The apparatus of claim 13, wherein the ECC encoder/decoder is further configured to perform error correction decoding on the read data to generate corrected data further comprises performing a second error correction decoding using parity data stored in reserved journaling cell slots of a page grid, wherein a decoding of the second error correction is performed only when a first error correction using data stored within the page stripe is insufficient to correct the data with a probability of an incorrect decoding of less than 1E-15.

15. The apparatus of claim 13, wherein the second circuit is further configured to selecting an error correction code from a predetermined list having a known correction capability corresponding to the evaluated condition of the page stripe to update gear settings.

16. The apparatus of claim 13, wherein the second circuit is further configured to select an error correction code apparatus having a highest code rate that retains an error correction likelihood of 1E-15 or less given the evaluated condition of the page stripe to update the gear settings.

17. The apparatus of claim 13, wherein the second circuit is further configured to select an error correction code apparatus having a highest code rate that retains an error correction likelihood of 1E-15 or less given the evaluated condition of the page stripe to update the gear settings.

18. The apparatus of claim 13, wherein the second circuit is further configured to determine a page stripe capacity counted in integer multiples of journaling cell slots based on the error correction code apparatus selected.

19. The apparatus of claim 13, wherein journaling cell slots contain a predetermined fixed amount of information, wherein page stripes, page grids, and block grids vary in cell slot capacity to accommodate a changing condition of pages of memory within page stripes, page grids, and block grids.

20. The apparatus of claim 13, wherein the second circuit is further configured to update gear settings such that gear zero having zero journaling cell slot capacity is selected for a page stripe of a block grid based on at least one of the following:

the page stripe having pages from a block marked as unusable during manufacturing test, a decode latency for the page stripe exceeding a threshold, a page stripe having a condition for which no ECC scheme available in the device retains an error correction likelihood of 1E-15 or less, or a page stripe having pages from a die, plane, or block that has been determined to have failed.

21. The apparatus of claim 13, wherein the second circuit is further configured to:

update gear settings such that gear zero having zero journaling cell slot capacity is selected for the page stripe of the block grid based on a decision to convert multi-level cells to quasi single-level cells by retiring a first half of paired pages of the page stripe; and

increase the journaling cell capacity of the second half of the paired pages from a previous setting.

22. The apparatus of claim 13, wherein the second circuit is further configured to read data from portions of page stripes of the selected block grid even if the portions do not contain valid data such that the condition of the page stripe can be assessed, wherein the criteria for selecting a different gear are evaluated based on error correction decoding of a complete page stripe.

23. The apparatus of claim 22, wherein the second circuit is further configured to:

journal complete valid allocation blocks of page stripes of the selected block grid into available page stripes of the flash array;

discard data of complete invalid allocation blocks of page stripes of the selected block grid; and

retain in a buffer, a partial allocation block until the next page stripe is read.

24. The apparatus of claim 23, wherein the determination of the gear setting is also based on whether any previous read of the page stripe met criteria indicating that a different gear is to be selected.