Static Wear Leveling

• US 20100268865A1
• Filed: 04/20/2009
• Published: 10/21/2010
• Est. Priority Date: 04/20/2009
• Status: Active Grant

• Current Assignee: Kingston Digital, Inc. (Kingston Technology Corporation)
• Original Assignee: Imation Corporation (Glassbridge Enterprises, Inc.)
• Inventors: Ramiya Mothilal, Arunprasad
• Granted Patent: US 8,065,469 B2
• Time in Patent Office: Days
• US Class Current: 711/103
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 2212/7211 Wear leveling

Abstract

Methods for extending the service life of a data storage device and devices operable to perform those methods are presented. A master lookup table block may comprise lookup table blocks and store an erase count indicator for each lookup table block. Each lookup table block may be associated with a logical zone of a memory and comprise entries. Each entry may be associated with a logical block and comprise an erase count for a physical block corresponding to that logical block. A physical block erasure may be performed on a first physical block in the memory. The physical block erasure may be tracked by incrementally increasing a first erase count. An actual erase count may be determined for the first physical block. The entry for a logical block corresponding to the first physical block may be exchanged with another entry within a different lookup table block when the actual erase count for the first physical block exceeds a threshold. The different lookup table block may have a lower erase count indicator relative to that of the lookup table block comprising the entry for the logical block corresponding to the first physical block.

Claims

1. A method for extending the service life of a data storage device, the method comprising:

performing a physical block erasure on a first physical block in a memory, wherein the memory comprises a plurality of logical zones, and each logical zone comprises a plurality of physical blocks;

tracking the physical block erasure by incrementally increasing a first erase count, wherein a master lookup table block comprises a plurality of lookup table blocks and stores an erase count indicator for each lookup table block, each lookup table block being associated with a logical zone and comprising a plurality of entries, and each entry being associated with a logical block and comprising an erase count for a physical block corresponding to that logical block;

determining an actual erase count for the first physical block; and

exchanging the entry for a logical block corresponding to the first physical block with another entry within a different lookup table block when the actual erase count for the first physical block exceeds a threshold, the different lookup table block having a lower erase count indicator relative to that of the lookup table block comprising the entry for the logical block corresponding to the first physical block.

2. The method of claim 1, wherein determining the actual erase count for the first physical block is based on the first erase count and an absolute erase count for the lookup table block that includes the entry associated with the first physical block.

3. The method of claim 1, further comprising incrementally increasing an erase cycle count for a lookup table block when an erase count of an entry within that lookup table block reaches a limit.

4. The method of claim 1, further comprising resetting an erase count for a logical block when that erase count reaches a limit.

5. The method of claim 1, wherein the erase count indicator for each lookup table block is associated with an average erase count of the entries of that lookup table block.

6. The method of claim 1, further comprising screening the physical blocks of the memory to identify an inoperable physical block.

7. The method of claim 6, further comprising preventing an entry from being exchanged when the entry is for a logical block that corresponds to the inoperable physical block.

8. A data storage device comprising:

a memory for storing data, the memory comprising a plurality of logical zones, each logical zone comprising a plurality of physical blocks; and

a controller communicatively coupled with the memory, the controller including;

a logic module executable by the controller for managing a master lookup table block, the master lookup table block comprising a plurality of lookup table blocks and storing an erase count indicator for each lookup table block, each lookup table block being associated with a logical zone and comprising a plurality of entries, and each entry being associated with a logical block and comprising an erase count for a physical block corresponding to that logical block;

a deletion module executable by the controller for performing a physical block erasure on a first physical block in the memory; and

a scheduler module executable by the controller for tracking the physical block erasure by incrementally increasing a first erase count, determining an actual erase count for the first physical block, and exchanging the entry for a logical block corresponding to the first physical block with another entry within a different lookup table block when the actual erase count for the first physical block exceeds a threshold, the different lookup table block having a lower erase count indicator relative to that of the lookup table block comprising the entry for the logical block corresponding to the first physical block.

9. The data storage device of claim 8, wherein the scheduler module is further executable by the controller for incrementally increasing an erase cycle count for a lookup table block when an erase count of an entry within that lookup table block reaches a limit.

10. The data storage device of claim 8, wherein the scheduler module is further executable by the controller for resetting an erase count for a logical block when that erase count reaches a limit.

11. The data storage device of claim 8, wherein the memory comprises two or more chips, each chip comprising a different portion of the plurality of logical zones.

12. The data storage device of claim 11, wherein the different lookup table block is associated with a logical zone included in a different chip.

13. The data storage device of claim 8, wherein the data storage device is a portable USB storage device.

14. The data storage device of claim 8, wherein the memory comprises single level cell flash memory.

15. The data storage device of claim 8, wherein the memory comprises multi level cell flash memory.

16. The data storage device of claim 8, wherein each entry further comprises one or more of a physical block indicator, a physical chip select indicator, or a logical zone indicator.

17. The data storage device of claim 8, wherein the controller further comprises a power loss recovery module executable by the controller for reconstructing lookup table blocks after a loss of power to the data storage device.

18. The data storage device of claim 8, wherein the controller further comprises a bad block management module executable by the controller for screening the physical blocks of the memory to identify an inoperable physical block, and informing the scheduler module of the inoperable physical block.

19. The data storage device of claim 18, wherein the scheduler module is further executable by the controller for preventing an entry from being exchanged when the entry is for a logical block that corresponds to the inoperable physical block.

20. A computer readable storage medium having a program embodied thereon, the program executable by a processor to perform a method for extending the service life of a data storage device, the method comprising:

performing a physical block erasure on a first physical block in a memory, wherein the memory comprises a plurality of logical zones, and each logical zone comprises a plurality of physical blocks;

tracking the physical block erasure by incrementally increasing a first erase count, wherein a master lookup table block comprises a plurality of lookup table blocks and stores an erase count indicator for each lookup table block, each lookup table block is associated with a logical zone and comprises a plurality of entries, and each entry is associated with a logical block and comprises an erase count for a physical block corresponding to that logical block;

determining an actual erase count for the first physical block; and

exchanging the entry for a logical block corresponding to the first physical block with another entry within a different lookup table block when the actual erase count for the first physical block exceeds a threshold, the different lookup table block having a lower erase count indicator relative to that of the lookup table block comprising the entry for the logical block corresponding to the first physical block.