Garbage collection in storage devices based on flash memories

Patent metadata

Field	Value
Publication number	US-8954649-B2
Application number	US-201113196820-A
Country	US
Kind code	B2
Filing date	Aug 2, 2011
Priority date	May 9, 2007
Publication date	Feb 10, 2015
Grant date	Feb 10, 2015

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.

First claim

What is claimed is:

1. A method for managing a storage device based on a flash memory, the method comprises:
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, the set of second physical blocks being unreserved ones of the physical blocks in the physical memory space and being indistinguishable from the set of first physical blocks, detecting each bad physical block, and
discarding each bad physical block to prevent using the bad physical block for mapping the logical memory space;
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;
wherein a number of the second physical blocks is at least equal to 2; and
wherein the method further comprises:
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 greater than or equal to 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.

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 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.

6. The method according to claim 1 , 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.

7. The method according to claim 1 , further including the steps:
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.

8. The method according to claim 7 , 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.

9. The method according to claim 8 , 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.

10. The method according to claim 7 , 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.

11. The method according to claim 1 , 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.

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

13. A software program product including a non-transitory computer-readable storage medium embodying a software program, the computer-readable storage 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 .

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

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

16. A data processing system including at least one storage device according to claim 14 .

Assignees

• Biswas Sudeep
• Di Sena Angelo
• Manna Domenico
• Sk Hynix Inc

Inventors

• Biswas Sudeep
• Di Sena Angelo
• Manna Domenico

Classifications

• G11C29/88

  with partially good memories · CPC title

• G06F2212/1032

  Reliability improvement, data loss prevention, degraded operation etc · CPC title

• G06F12/0246 Primary

  in block erasable memory, e.g. flash memory · CPC title

• G11C29/76

  using address translation or modifications · CPC title

• G06F2212/7201

  Logical to physical mapping or translation of blocks or pages · CPC title