Systems and methods for mapping for solid-state memory

• US 9,009,565 B1
• Filed: 03/15/2013
• Issued: 04/14/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): ABRAHAM, ESAW T
• Application Number:
  US13/844,448
• Time in Patent Office: 760 Days
• Field of Search: 714/718, 714/704, 714/773
• US Class Current: 714/763
• CPC Class Codes: G06F 11/10 Adding special bits or symbols to the coded information, e.g. parity check, casting out 9's or 11's
• CPC Class Codes: G06F 11/1004 to protect a block of data words, e.g. CRC or checksum G06F11/1076 takes precedence; security arrangements for protecting computers or computer systems against unauthorized activity G06F21/00
• CPC Class Codes: G06F 11/1008 in individual solid state devices G06F11/1004 takes precedence
• CPC Class Codes: G06F 11/1012 using codes or arrangements adapted for a specific type of error G06F11/1048 takes precedence
• CPC Class Codes: G06F 11/1068 in sector programmable memories, e.g. flash disk G06F11/1072 takes precedence
• CPC Class Codes: G06F 11/108 Parity data distribution in semiconductor storages, e.g. in SSD
• CPC Class Codes: G06F 12/0253 Garbage collection, i.e. reclamation of unreferenced memory
• CPC Class Codes: G11C 2029/0411 Online error correction
• CPC Class Codes: G11C 29/00 Checking stores for correct operation ; Subsequent repair; Testing stores during standby or offline operation
• CPC Class Codes: G11C 29/42 using error correcting codes [ECC] or parity check

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 organizing memory for a mass-storage device for redundancy, the method comprising:

organizing the memory into a plurality of block grids, wherein a block grid comprises a plurality of page grids, wherein a page grid comprises a plurality of page stripes, wherein a page stripe comprises a plurality of pages or integer fractions thereof;

distributing a first plurality of N journaling cell slots among the page stripes of a first page grid,

wherein a journaling cell slot comprises an area of memory for a journaling cell;

wherein the N journaling cell slots further comprise N1 journaling cell slots for user data and N2 journaling cell slots for grid parity data, wherein both N1 and N2 are integers,

wherein the page stripes of the first page grid comprise at least a first page stripe associated with a first gear such that the first page stripe has a first non-zero integer journaling cell slot capacity for data and a first capacity for parity bits of a first error correction code protective of data stored within the first page stripe, a second page stripe associated with a second gear such that the second page stripe has a second non-zero integer journaling cell slot capacity different from the first non-zero journaling slot capacity and a second capacity for parity bits of the first error correction code protective of data stored within the second page stripe, at least a third page stripe associated with a gear zero such that the third page stripe has a zero journaling cell slot capacity and has no parity bits;

wherein grid parity data comprises a set of parity bits of a second error correction code protective over the first page grid, wherein the second error correction code is of an erasure code type such that decoding of the grid parity data is capable of rebuilding data of at least one failed page stripe of the first page grid; and

mapping a logical block address to a journaling packet, which is mapped to one or more journaling cell slots of the N1 journaling cell slots.

2. The method of claim 1, wherein the size of the information part is configured based at least on the size of the block to be stored;

and wherein the size of the journaling cell is configured based at least on the size of pages in the media used; and

wherein the ECC is configured to accommodate these configurations.

3. The method of claim 1, wherein a value for N2 is predetermined, and wherein a value for N1 corresponds to a number of journaling cell slots remaining after reserving N2 journaling cell slots for the grid parity data.

4. The method of claim 1, wherein a decrease in a capacity of journaling cell slots for a page stripe results in more memory space remaining for the primary parity bits of the first error correction code such that the error correction capacity is increased over a different page stripe with a larger capacity of journaling cell slots.

5. The method of claim 1, further comprising:

determining an amount of memory space to allocate for parity bits for an error correction code protective of data stored within a page stripe; and

determining an integer number for the journaling cell slot capacity of the page stripe based at least partly on an amount of memory space remaining within the page stripe.

6. The method of claim 5, further comprising:

determining an estimated raw bit error rate (RBER) for the page stripe;

selecting a characteristic for the error correction code based at least partly on the RBER; and

determining a usable memory capacity for the page stripe based at least partly on the selected characteristic.

7. The method of claim 1, further comprising storing an indication to set a journaling cell slot capacity of a page stripe to zero upon an occurrence of at least one of the following:

the page stripe is resident on a die, a plane, or a block that is known to have failed during operation;

the page stripe is resident on a block that is marked as a bad block via a manufacturing test process;

a determined raw bit error rate (RBER) for the page stripe exceeds a predetermined threshold rate, wherein the predetermined threshold rate is associated with a highest error correction capability associated with a gear of non-zero integer journaling cell slot capacity;

no physical memory exists at the memory address associated with the page stripe;

or

the physical memory at the memory address associated with a first page stripe is also assigned to a second page stripe, wherein the second page stripe has been assigned a non-zero journaling cell capacity.

8. The method of claim 1, wherein underlying pages of the first page grid comprise pages having the same block and page address, but spanning one or more planes and 3 or more dice.

9. The method of claim 1, wherein each page stripe comprises pages that are programmed in parallel and share a common page address.

10. The method of claim 1, wherein the page stripes of the first page grid are each on separate die.

11. The method of claim 1, wherein the page stripes of the first page grid are each on non-overlapping dice, wherein each page stripe comprises 2 pages from 2 planes of a first die and 2 pages from 2 planes of a second die.

12. The method of claim 1, wherein the logical address corresponds to a logical block address (LBA), and wherein an amount of data corresponding to each LBA is between 512 bytes and 4240 bytes.

13. The method of claim 12, further comprising storing LBAs, corresponding references to page grid and journaling cell slots in a lookup table, wherein the lookup table is indexed by the LBAs.

14. The method of claim 13, further comprising storing corresponding references to page stripes in the lookup table, wherein the journaling cell slots are referenced within corresponding page stripes.

15. The method of claim 1, further comprising handling retirement of a particular page stripe by resizing a capacity of journaling cell slots of the particular page stripe to zero, thereby also resizing a capacity of a corresponding page grid.

16. The method of claim 1, wherein the mass-storage device comprises non-volatile solid state memory.

17. The method of claim 1, wherein the mass-storage device comprises NAND flash memory.

18. An electronically-implemented method of mapping memory for a mass-storage device, the method comprising:

grouping flash pages into page grids, wherein pages of a page grid have the same block and page address, wherein the page grid spans one or more planes and 3 or more dice;

subgrouping the page grid into page stripes, wherein a page stripe of the page grid comprises at least two pages from different planes of a first die;

adaptively selecting a data storage capacity of the page stripe corresponding to an integer multiple of journaling cell slots and a characteristic of a first error correction code stored within the page stripe, wherein the first error correction code is protective of data and stored within the page stripe, wherein a journaling cell slot comprises an area of memory for a journaling cell; and

reserving a pre-determined number of journaling cell slots of the page grid for storage of a second error correction code protective of data stored within journaling cell slots and the corresponding first error correction code across the page grid.

19. The method of claim 18, wherein the pages of the page stripe comprise pages from different planes of the first die such that the pages of the page stripe are programmed at least partly in parallel.

20. The method of claim 18, wherein the pages of the page stripe comprise pages from different planes of more than one die, but no two page stripes of a page grid address the same die such that the pages of the page grid are programmed at least partly in parallel.

21. The method of claim 18, wherein the pre-determined number of journaling cell slots for grid parity comprise the last journaling cell slots of the page grid to be written.

22. The method of claim 18, further comprising:

estimating media error properties of the page stripe from error correction decoding results, wherein estimating includes counting at least one of a number of errors corrected or a number of processing steps used for error correction decoding;

selecting the characteristic of the first ECC from a predetermined list of strengths, wherein each strength has a known correction capability; and

selecting the available ECC with the highest code rate for which the likelihood of requiring grid decoding given the observed error properties is less than a first predetermined acceptable likelihood, and the likelihood of decode failure given the observed error properties is less than a second predetermined acceptable failure likelihood.

23. The method of claim 22 in which the first predetermined acceptable likelihood is chosen to be less than 1/10 the ratio between the average time to read the flash and perform a Primary-only decode, and the average time to read a grid and perform a grid decode.

24. An apparatus for organizing memory for a mass-storage device for redundancy, the apparatus comprising:

an ECC encoder/decoder; and

a circuit configured to;

organize the memory into a plurality of block grids, wherein a block grid comprises a plurality of page grids, wherein a page grid comprises a plurality of page stripes, wherein a page stripe comprises a plurality of pages or integer fractions thereof;

distribute a first plurality of N journaling cell slots among the page stripes of a first page grid,

wherein a journaling cell slot comprises an area of memory for a journaling cell;

wherein the N journaling cell slots further comprise N1 journaling cell slots for user data and N2 journaling cell slots for grid parity data, wherein both N1 and N2 are integers,

wherein the page stripes of the first page grid comprise at least a first page stripe associated with a first gear such that the first page stripe has a first non-zero integer journaling cell slot capacity for data and a first capacity for parity bits of a first error correction code protective of data stored within the first page stripe, a second page stripe associated with a second gear such that the second page stripe has a second non-zero integer journaling cell slot capacity different from the first non-zero journaling slot capacity and a second capacity for parity bits of the first error correction code protective of data stored within the second page stripe, at least a third page stripe associated with a gear zero such that the third page stripe has a zero journaling cell slot capacity and has no parity bits;

wherein grid parity data comprises a set of parity bits of a second error correction code protective over the first page grid, wherein the second error correction code is of an erasure code type such that decoding of the grid parity data is capable of rebuilding data of at least one failed page stripe of the first page grid;

wherein the circuit is configured to map a logical block address to a journaling packet, which is mapped to one or more journaling cell slots of the N1 journaling cell slots.

25. The apparatus of claim 24, wherein the size of the information part is configured based at least on the size of the block to be stored;

and wherein the size of the journaling cell is configured based at least on the size of pages in the media used; and

wherein the ECC is configured to accommodate these configurations.

26. The apparatus of claim 24, wherein a value for N2 is predetermined, and wherein a value for N1 corresponds to a number of journaling cell slots remaining after reserving N2 journaling cell slots for the grid parity data.

27. The apparatus of claim 24, wherein a decrease in a capacity of journaling cell slots for a page stripe results in more memory space remaining for the primary parity bits of the first error correction code such that the error correction capacity is increased over a different page stripe with a larger capacity of journaling cell slots.

28. The apparatus of claim 24, wherein the circuit is further configured to:

determine an amount of memory space to allocate for parity bits for an error correction code protective of data stored within a page stripe; and

determine an integer number for the journaling cell slot capacity of the page stripe based at least partly on an amount of memory space remaining within the page stripe.

29. The apparatus of claim 28, wherein:

the ECC encoder/decoder is further configured to determine an estimated raw bit error rate (RBER) for the page stripe; and

the circuit is further configured to select a characteristic for the error correction code based at least partly on the RBER and determine a usable memory capacity for the page stripe based at least partly on the selected characteristic.

30. The apparatus of claim 24, wherein the circuit is further configured to store an indication to set a journaling cell slot capacity of a page stripe to zero upon an occurrence of at least one of the following:

the page stripe is resident on a die, a plane, or a block that is known to have failed during operation;

the page stripe is resident on a block that is marked as a bad block via a manufacturing test process;

a determined raw bit error rate (RBER) for the page stripe exceeds a predetermined threshold rate, wherein the predetermined threshold rate is associated with a highest error correction capability associated with a gear of non-zero integer journaling cell slot capacity;

no physical memory exists at the memory address associated with the page stripe;

or

the physical memory at the memory address associated with a first page stripe is also assigned to a second page stripe, wherein the second page stripe has been assigned a non-zero journaling cell capacity.

31. The apparatus of claim 24, wherein underlying pages of the first page grid comprise pages having the same block and page address, but spanning one or more planes and 3 or more dice.

32. The apparatus of claim 24, wherein each page stripe comprises pages that are programmed in parallel and share a common page address.

33. The apparatus of claim 24, wherein the page stripes of the first page grid are each on separate die.

34. The apparatus of claim 24, wherein the page stripes of the first page grid are each on non-overlapping dice, wherein each page stripe comprises 2 pages from 2 planes of a first die and 2 pages from 2 planes of a second die.

35. The apparatus of claim 24, wherein the logical address corresponds to a logical block address (LBA), and wherein an amount of data corresponding to each LBA is between 512 bytes and 4240 bytes.

36. The apparatus of claim 35, wherein the circuit is configured to store LBAs, corresponding references to page grid and journaling cell slots in a lookup table, wherein the lookup table is indexed by the LBAs.

37. The apparatus of claim 36, wherein the circuit is configured store corresponding references to page stripes in the lookup table, wherein the journaling cell slots are referenced within corresponding page stripes.

38. The apparatus of claim 24, wherein the circuit is configured to handle retirement of a particular page stripe by resizing a capacity of journaling cell slots of the particular page stripe to zero, thereby also resizing a capacity of a corresponding page grid.

39. The apparatus of claim 24, wherein the mass-storage device comprises non-volatile solid state memory.

40. The apparatus of claim 24, wherein the mass-storage device comprises NAND flash memory.

41. An apparatus for mapping memory for a mass-storage device, the apparatus comprising:

an ECC encoder/decoder; and

a management processor configured to;

group flash pages into page grids, wherein pages of a page grid have the same block and page address, wherein the page grid spans one or more planes and 3 or more dice;

subgroup the page grid into page stripes, wherein a page stripe of the page grid comprises at least two pages from different planes of a first die;

adaptively select a data storage capacity of the page stripe corresponding to an integer multiple of journaling cell slots and a characteristic of a first error correction code stored within the page stripe, wherein the first error correction code is protective of data and stored within the page stripe, wherein a journaling cell slot comprises an area of memory for a journaling cell; and

reserve a pre-determined number of journaling cell slots of the page grid for storage of a second error correction code protective of data stored within journaling cell slots and the corresponding first error correction code across the page grid.

42. The apparatus of claim 41, wherein the pages of the page stripe comprise pages from different planes of the first die such that the pages of the page stripe are programmed at least partly in parallel.

43. The apparatus of claim 41, wherein the pages of the page stripe comprise pages from different planes of more than one die, but no two page stripes of a page grid address the same die such that the pages of the page grid are programmed at least partly in parallel.

44. The apparatus of claim 41, wherein the pre-determined number of journaling cell slots for grid parity comprise the last journaling cell slots of the page grid to be written.

45. The apparatus of claim 41, wherein the management processor is further configured to:

estimate media error properties of the page stripe from error correction decoding results, wherein estimating includes counting at least one of a number of errors corrected or a number of processing steps used for error correction decoding;

select the characteristic of the first ECC from a predetermined list of strengths, wherein each strength has a known correction capability; and

select the available ECC with the highest code rate for which the likelihood of requiring grid decoding given the observed error properties is less than a first predetermined acceptable likelihood, and the likelihood of decode failure given the observed error properties is less than a second predetermined acceptable failure likelihood.

46. The apparatus of claim 45 in which the first predetermined acceptable likelihood is chosen to be less than 1/10 the ratio between the average time to read the flash and perform a primary ECC only decode, and the average time to read a grid and perform a grid decode.