Garbage collection in storage devices based on flash memories

摘要

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.

主权项

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, andreducing the logical memory space by removing the selected empty logical blocks.