Systems and methods for reclaiming flash blocks of a flash drive

• US 8,793,556 B1
• Filed: 05/22/2012
• Issued: 07/29/2014
• 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., Geiger, Peter Dau, Sadowsky, Jonathan
• Primary Examiner(s): TU, CHRISTINE TRINH LE
• Application Number:
  US13/477,845
• Time in Patent Office: 798 Days
• Field of Search: 714/763, 714/773, 714/768, 714/758
• US Class Current: 714/773
• 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/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 2212/1016 Performance improvement
• CPC Class Codes: G06F 2212/7205 Cleaning, compaction, garbage collection, erase control
• CPC Class Codes: G06F 2212/7208 Multiple device management, e.g. distributing data over multiple flash devices

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 reclaiming flash blocks of a flash array, the method comprising:

selecting a block grid for reclamation, wherein block grids contain complete page grids;

for valid data stored in the block grid, reading, performing error correction, and journaling into available page stripes of the flash array, wherein valid data includes valid allocation blocks, wherein an ECC decoder used for performing error correction generates an indication as to whether or not correction for at least the valid data from the flash array has met criteria indicating that a different gear to be selected;

erasing the blocks of the block grid;

updating gear settings for the page stripes of the block grid based at least partly on corresponding indications from the ECC decoder; and

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

wherein at least selecting and making are performed by an integrated circuit.

2. The method of claim 1, further comprising reading page stripes of the selected block grid irrespective of whether the page stripes contain valid data, wherein the criteria for selecting a different gear are evaluated based on error correction decoding of a complete page stripe.

3. The method of claim 2, 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.

4. The method of claim 3, 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.

5. The method of claim 3, wherein the page stripes of a page grid are assigned to the highest gear setting of any page stripe in the page grid.

6. An apparatus comprising:

a first circuit configured to select a block grid for reclamation, wherein block grids contain complete page grids;

an ECC decoder;

for valid data stored in the block grid, the first circuit is further configured to read, the ECC decoder is configured to perform error correction, and the first circuit is further configured to journal into available page stripes of a flash array, wherein valid data includes valid allocation blocks, wherein the ECC decoder generates an indication as to whether or not correction for at least the valid data from the flash array has met criteria indicating that a different gear to be selected;

the first circuit further configured to erase the blocks of the block grid;

the first circuit further configured to update gear settings for the page stripes of the block grid based at least partly on corresponding indications from the ECC decoder; and

the first circuit further configured to make the page stripes of the block grid available for writing.

7. The apparatus of claim 6, wherein the first circuit is further configured to:

read page stripes of the selected block grid irrespective of whether the page stripes contain valid data; and

evaluate criteria for selecting a different gear based on error correction decoding of a complete page stripe.

8. The apparatus of claim 7, wherein the first 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.

9. The apparatus of claim 8, 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.

10. The apparatus of claim 8, wherein the page stripes of a page grid are assigned to the highest gear setting of any page stripe in the page grid.

11. An apparatus for reclaiming flash blocks of a flash array, the apparatus comprising:

a means for selecting a block grid for reclamation, wherein block grids contain complete page grids;

a means for reading;

a means for ECC decoding;

a means for journaling;

for valid data stored in the block grid, the reading means further reading, the ECC decoding means further performing error correction, and the journaling means further journaling into available page stripes of the flash array, wherein valid data includes valid allocation blocks, wherein the ECC decoding means is configured to generate an indication as to whether or not correction for at least the valid data from the flash array has met criteria indicating that a different gear to be selected;

a means for erasing the blocks of the block grid;

a means for updating gear settings for the page stripes of the block grid based at least partly on corresponding indications from the ECC decoder; and

a means for making the page stripes of the block grid available for writing.

12. The apparatus of claim 11, further comprising:

a means for reading page stripes of the selected block grid irrespective of whether the page stripes contain valid data; and

a means for evaluating criteria for selecting a different gear based on error correction decoding of a complete page stripe.

13. The apparatus of claim 12, further comprising:

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

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

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

14. The apparatus of claim 13, 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.

15. The apparatus of claim 13, wherein the page stripes of a page grid are assigned to the highest gear setting of any page stripe in the page grid.