Garbage collection in storage devices based on flash memories

• US 20080282045A1
• Filed: 05/09/2007
• Published: 11/13/2008
• Est. Priority Date: 05/09/2007
• Status: Active Grant

• Current Assignee: SK Hynix Inc.
• Original Assignee: STMicroelectronics Pvt Ltd. (STMicroelectronics NV), STMicroelectronics SRL (STMicroelectronics NV)
• Inventors: Di Sena, Angelo, Biswas, Sudeep, Manna, Domenico
• Granted Patent: US 7,991,942 B2
• Time in Patent Office: Days
• US Class Current: 711/159
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 2212/1032 Reliability improvement, data loss prevention, degraded operation etc
• CPC Class Codes: G06F 2212/7201 Logical to physical mapping or translation of blocks or pages
• CPC Class Codes: G06F 2212/7205 Cleaning, compaction, garbage collection, erase control
• CPC Class Codes: G11C 29/76 using address translation or modifications
• CPC Class Codes: G11C 29/88 with partially good memories

Abstract

A solution for managing a storage device based on a flash memory is proposed. A corresponding method starts with the step for mapping a logical memory space of the storage device (including a plurality of logical blocks) on a physical memory space of the flash memory (including a plurality of physical blocks, which are adapted to be erased individually). The physical blocks include a set of first physical blocks (corresponding to the logical blocks) and a set of second—or spare—physical blocks (for replacing each bad physical block that is unusable). The method continues by detecting each bad physical block. Each bad physical block is then discarded, so to prevent using the bad physical block for mapping the logical memory space.

Claims

1. A method for managing a storage device based on a flash memory, the method including the steps for:

mapping a logical memory space of the storage device, including a plurality of logical blocks, on a physical memory space of the flash memory, including a plurality of physical blocks adapted to be erased individually, the physical blocks including a set of first physical blocks corresponding to the logical blocks and a set of second physical blocks for replacing each bad physical block being unusable,

detecting each bad physical block, and

discarding each bad physical block to prevent using the bad physical block for mapping the logical memory space.

2. The method according to claim 1, wherein the step for detecting each bad physical block includes:

storing a bad block structure into the flash memory, the bad block structure including an indication of the bad physical blocks, and

loading a further bad block structure into a working memory of the storage device at an initialization of the storage device, the further bad block structure being loaded by adding an indication of each bad physical block included in the bad block structure.

3. The method according to claim 2, wherein the step for detecting each bad physical block further includes:

detecting each new bad physical block during operation of the storage device in response to a failure of a corresponding erase operation, and

adding an indication of each new bad physical block to the further bad block structure.

4. The method according to claim 3, wherein the bad block structure is stored during a format operation of the flash memory attempting to erase all the physical blocks,

the step for detecting each new bad physical block including asserting a bad block indicator into the new bad physical block, and

the step for loading the further bad block structure at the initialization of the storage device including adding an indication of each new bad physical block, the new bad physical block being identified according to the corresponding bad block indicator.

5. The method according to claim 1, wherein each logical block includes a plurality of logical sectors adapted to be written repeatedly, and wherein each physical block includes a plurality of physical sectors adapted to be programmed once, consecutive versions of the logical sectors of each logical block being stored in succession in the physical sectors of a root physical block and at least one child physical block when the root physical block is full.

6. The method according to claim 5, wherein a number of the second physical blocks is at least equal to 2.

7. The method according to claim 6, further including the steps for:

verifying whether the flash memory satisfies a correctness condition, wherein the number of the second physical blocks minus the number of the bad physical blocks is lower than 2,

verifying whether the flash memory satisfies a recovery condition, wherein the number of empty logical blocks having no logical sector being written is at least equal to 2 plus the number of the bad physical blocks minus the number of the second physical blocks, in response to the correctness condition being not satisfied,

selecting a minimum number of the empty logical blocks required to satisfy the recovery condition in response to the recovery condition being satisfied, and

reducing the logical memory space by removing the selected empty logical blocks.

8. The method according to claim 7, wherein the logical memory space is adapted to store payload data and meta data describing the payload data, the meta data being stored in a first portion of the logical memory space, the step for selecting the minimum number of the empty logical blocks including:

selecting the minimum number of the empty logical blocks in a second portion of the logical memory space different from the first portion.

9. The method according to claim 7, further including the step for:

locking all the logical blocks in response to the recovery condition being not satisfied for preventing writing each logical block.

10. The method according to claim 5, further including the step for:

forcing a garbage collection procedure on a selected logical block for compacting an old root physical block and at least one old child physical block storing the selected logical block into a new root physical block storing the last versions only of the logical sectors of the selected logical block and attempting to erase the old root physical block and the at least one old child physical block, the garbage collection procedure being forced in response to the flash memory leaving a safe status, wherein the physical memory space ensures the writing of all the logical blocks, in response to each write operation increasing the number of the leaf physical blocks.

11. The method according to claim 10, further including the step for:

determining that the flash memory has left the safe status when the number of the child physical blocks plus 1 is higher than the number of the second physical blocks minus the number of the bad physical blocks.

12. The method according to claim 10, wherein the step for forcing the garbage collection procedure includes:

forcing the garbage collection procedure when the flash memory enters a critical status, wherein the physical memory space only allows performing a single garbage collection procedure, in response to a write operation increasing the number of used physical blocks having at least one physical sector being programmed.

13. The method according to claim 12, further including the step for:

determining that the flash memory has entered the critical status when the number of the used physical blocks plus the number of the bad physical blocks is equal to the number of the physical blocks minus 1.

14. The method according to claim 10, wherein the step for forcing the garbage collection procedure includes:

selecting the at least one child physical block having the minimum number of physical sectors being programmed, and

selecting the logical block associated with the selected at least one child physical block for the garbage collection procedure.

15. The method according to claim 5, further including the step for:

defining a mapping structure for mapping each logical sector on an associated physical sector of a corresponding physical block storing the last version of the logical sector, wherein for each written logical block having at least one logical sector being written the mapping structure includes a sector map having a field for each logical sector of the written logical block, the field storing an indication of the associated physical sector when the logical sector is written or a value equal to the indication of a predefined physical sector of the written logical block when the logical sector is not written, and a further field for storing an indication of the logical sector being written in the predefined physical sector.

16. The method according to claim 1, wherein the flash memory is of the NAND type.

18. A software program product including a medium embodying a software program, the medium being adapted to be used by a control system of a storage device based on a flash memory, wherein the software program when executed on the control system causes the control system to perform the method according to claim 1.

19. A control system for a storage device based on a flash memory, the control system including means for performing the steps for the method according to claim 1.

20. A storage device based on a flash memory including the control system according to claim 19.

21. A data processing system including at least one storage device according to claim 19.

17. A method for managing a storage device based on a flash memory, wherein the storage device emulates a logical memory space, including a plurality of logical blocks each one having a plurality of logical sectors adapted to be written repeatedly, being mapped on a physical memory space of the flash memory, including a plurality of physical blocks adapted to be erased individually each one having a plurality of physical sectors adapted to be programmed once, consecutive versions of the logical sectors of each logical block being stored in succession in the physical sectors of a root physical block and at least one child physical block when the root physical block is full, wherein the method includes the step for:

defining a mapping structure for mapping each logical sector on an associated physical sector of a corresponding physical block storing the last version of the logical sector, wherein for each written logical block having at least one logical sector being written the mapping structure includes a sector map having a field for each logical sector of the written logical block, the field storing an indication of the associated physical sector when the logical sector is written or a value equal to the indication of a predefined physical sector of the written logical block when the logical sector is not written, and a further field for storing an indication of the logical sector being written in the predefined physical sector.