APPARATUS, SYSTEM, AND METHOD FOR BAD BLOCK REMAPPING

• US 20090282301A1
• Filed: 04/06/2009
• Published: 11/12/2009
• Est. Priority Date: 04/05/2008
• Status: Active Grant

• Current Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Original Assignee: Fusion-IO Incorporated (Western Digital Corporation)
• Inventors: Trasser, John, Flynn, David, Atkisson, David, Thatcher, Jonathan, Zappe, Michael, Aune, Joshua, Vigor, Kevin
• Granted Patent: US 8,156,392 B2
• Time in Patent Office: Days
• US Class Current: 714/710
• CPC Class Codes: G06F 11/006 Identification G06F11/2289 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/1435 using file system or storage system metadata
• CPC Class Codes: G06F 11/1666 where the redundant component is memory or memory area
• 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/1032 Reliability improvement, data loss prevention, degraded operation etc
• CPC Class Codes: G06F 2212/7205 Cleaning, compaction, garbage collection, erase control
• CPC Class Codes: G06F 2212/7207 management of metadata or control data
• CPC Class Codes: G11C 29/76 using address translation or modifications

Abstract

An apparatus, system, and method are disclosed for bad block remapping. A bad block identifier module identifies one or more data blocks on a solid-state storage element as bad blocks. A log update module writes at least a location of each bad block identified by the bad block identifier module into each of two or more redundant bad block logs. A bad block mapping module accesses at least one bad block log during a start-up operation to create in memory a bad block map. The bad block map includes a mapping between the bad block locations in the bad block log and a corresponding location of a replacement block for each bad block location. Data is stored in each replacement block instead of the corresponding bad block. The bad block mapping module creates the bad block map using one of a replacement block location and a bad block mapping algorithm.

Claims

1. An apparatus to map bad blocks in solid-state storage, the apparatus comprising:

a bad block identifier module that identifies one or more data blocks as bad blocks, each bad block comprising a block determined to be inappropriate for data storage, each bad block on a solid-state storage element in an array of solid-state storage elements;

a log update module that writes at least a location of each bad block (“

bad block location”

) identified by the bad block identifier module into each of two or more redundant bad block logs, wherein, for at least one of the bad block logs, the log update module writes the one or more bad block locations into a page of a block comprising the bad block log, the page being free of previously written bad block location information; and

a bad block mapping module that accesses at least one bad block log during a start-up operation to create in memory a bad block map comprising a mapping between the bad block locations in the bad block log and a corresponding location of a replacement block (“

replacement block location”

) for each bad block location, wherein data is stored in each replacement block instead of the corresponding bad block, the start-up operation comprising making operational a controller for the solid-state storage from a non-operational state, wherein the bad block mapping module creates the bad block map using one of

a replacement block location stored with each bad block location in each of the bad block logs; and

a bad block mapping algorithm that uses a storage order of the bad block locations in a bad block log to pair each bad block location with a replacement block location.

2. The apparatus of claim 1, further comprising a table updater module that updates the bad block map by mapping a replacement block location to a bad block location, the table updater module storing the mapping in the bad block map.

3. The apparatus of claim 1, further comprising a log compactor module that one of reads, in a block comprising a bad block log, each page storing one or more bad block locations, erases the pages storing bad block locations, and stores at least the bad block locations read from the pages together into one or more pages in the block comprising the bad block log (“

compacted bad block pages”

); and

erases pages storing bad block locations and stores the bad block map in one or more pages of the block comprising the bad block log as compacted bad block pages.

4. The apparatus of claim 3, wherein the log update module, subsequent to the log compactor module storing bad block locations into the one or more compacted bad block pages, stores each additional bad block location corresponding to a bad block, subsequently identified by the bad block identifier module, in a separate page and in a page different than the one or more compacted bad block pages.

5. The apparatus of claim 4, wherein the log compactor module reads one or more compacted bad block pages and other pages storing a bad block location and stores the bad block locations in one or more compacted bad block pages.

6. The apparatus of claim 3, wherein the log compactor module reads pages and stores bad block locations in one or more compacted bad block pages in response to one or more of

reaching a threshold of number of pages with bad block location information;

and

each available page in a bad block log having one or more bad block locations.

7. The apparatus of claim 1, further comprising a bad block recovery module that recovers valid data stored in an identified bad block and stores the data in a replacement block mapped to the bad block, wherein the bad block recovery module recovers the valid data using one of

error correcting code (“

ECC”

);

a spare die or chip from which the valid data can be covered; and

data stored in a stripe of a redundant array of independent drives (“

RAID”

).

8. The apparatus of claim 1, further comprising a log consistency module that compares the two or more bad block logs and, if available, the bad block map and determines if the bad block logs and bad block map are consistent.

9. The apparatus of claim 8, wherein the log consistency module determines consistency of the bad block logs and bad block map in response to one or more of

detecting an error while updating one or more of the bad block logs;

the bad block mapping module creating the bad block map during a start-up operation;

after an interruption while updating the two or more bad block logs;

an ECC data correction failure;

a periodic scrubbing;

expiration of a period of time; and

a command by a user.

10. The apparatus of claim 8, further comprising a log recovery module that uses a bad block log that is determined to be correct or the bad block map that is determined to be correct to correct a bad block log that is determined to be in error.

11. The apparatus of claim 8, wherein determining that two or more bad block logs are inconsistent comprises determining that a number of bad block locations in a bad block log or the bad block map are different than a number of bad block locations in at least one other bad block log.

12. The apparatus of claim 11, wherein the bad block log with a higher number of bad block locations is determined to be the bad block log with valid bad block location data unless the bad block log with a higher number of bad block locations is determined to contain invalid data using ECC checking.

13. The apparatus of claim 1, wherein a replacement block comprises a physical block within a retired logical block, the retired logical block comprising

two or more physical blocks wherein at least one physical block is a physical block other than the replacement block and is a bad block;

and

a logical block available to store data that is marked as a retired logical block such that physical blocks in the logical block are available as replacement blocks.

14. The apparatus of claim 1, wherein a block comprising a bad block log comprises a logical block spanning two or more solid-state storage elements wherein error correcting code (“

ECC”

) protects the logical block.

15. The apparatus of claim 1, wherein the bad block mapping module accesses at least one bad block log by accessing the block comprising the bad block log at a known physical location within the solid-state storage array, wherein the known physical location comprises one of a first block, a last block, a block of a predetermined number, and a block at a known offset into the solid-state storage array.

16. The apparatus of claim 1, further comprising a bad block log replacement module that;

determines that a block comprising a bad block log is in a condition to be replaced;

selects a block within a pool of blocks designated for bad block data storage; and

writes bad block data into the selected block that is consistent with one of another bad block log and the bad block map.

17. The apparatus of claim 1, wherein the log update module further stores one or more of a time indicator and error data with the bad block location, the time indicator comprising a point in time or a point in a sequence, the point in time and point in sequence each associated with identification of the bad block.

18. The apparatus of claim 1, wherein a solid-state storage element comprises one of a solid-state storage chip and a solid-state storage die.

19. The apparatus of claim 1, wherein a block comprises an erase block.

20. A system to map bad blocks in solid-state storage, the system comprising:

a solid-state storage array comprising two or more solid-state storage elements;

a solid-state storage controller that controls the solid-state storage array;

a bad block identifier module that identifies one or more data blocks as bad blocks, each bad block comprising a block determined to be inappropriate for data storage, each bad block on a solid-state storage element in the solid-state storage array;

a log update module that writes at least a location of each bad block (“

bad block location”

) identified by the bad block identifier module into each of two or more redundant bad block logs, wherein, for at least one of the bad block logs, the log update module writes the one or more bad block locations into a page of a block comprising the bad block log, the page being free of previously written bad block location information; and

a bad block mapping module that accesses at least one bad block log during a start-up operation to create in memory a bad block map comprising a mapping between the bad block locations in the bad block log and a corresponding location of a replacement block (“

replacement block location”

) for each bad block location, wherein data is stored in each replacement block instead of the corresponding bad block, the start-up operation comprising making operational a controller for the solid-state storage from a non-operational state, wherein the bad block mapping module creates the bad block map using one of

a replacement block location stored with each bad block location in each of the bad block logs; and

a bad block mapping algorithm that uses a storage order of the bad block locations in a bad block log to pair each bad block location with a replacement block location.

21. The system of claim 20, further comprising a computer that includes the solid-state storage array.

22. A computer program product comprising a computer readable medium having computer usable program code executable to perform operations for mapping bad blocks in solid-state storage, the operations of the computer program product comprising:

identifying one or more data blocks as bad blocks, each bad block comprising a block determined to be inappropriate for data storage, each bad block on a solid-state storage element in an array of solid-state storage elements;

writing at least a location of each identified bad block (“

bad block location”

) into each of two or more redundant bad block logs, wherein, for at least one of the bad block logs, the one or more bad block locations are written into a page of a block comprising the bad block log, the page being free of previously written bad block location information; and

accessing at least one bad block log during a start-up operation to create in memory a bad block map comprising a mapping between the bad block locations in the bad block log and a corresponding location of a replacement block (“

replacement block location”

) for each bad block location, wherein data is stored in each replacement block instead of the corresponding bad block, the start-up operation comprising making operational a controller for the solid-state storage from a non-operational state, wherein creating the bad block map comprises using one of

a replacement block location stored with each bad block location in each of the bad block logs; and

a bad block mapping algorithm that uses a storage order of the bad block locations in a bad block log to pair each bad block location with a replacement block location.