Flash drive fast wear leveling

• US 8,417,881 B1
• Filed: 12/13/2010
• Issued: 04/09/2013
• Est. Priority Date: 09/01/2005
• Status: Active Grant

• Current Assignee: Monterey Research, LLC (Vector Capital Corporation)
• Original Assignee: Cypress Semiconductor Corporation (Infineon Technologies AG)
• Inventors: Kolokowsky, Steve
• Primary Examiner(s): Bradley, Matthew
• Application Number:
  US12/966,338
• Time in Patent Office: 848 Days
• Field of Search: 711/103, 711/156, 365/218
• US Class Current: 711/103
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 2212/1036 Life time enhancement
• CPC Class Codes: G06F 2212/7211 Wear leveling
• CPC Class Codes: G11C 16/349 Arrangements for evaluating degradation, retention or wearout, e.g. by counting erase cycles
• CPC Class Codes: G11C 16/3495 Circuits or methods to detect or delay wearout of nonvolatile EPROM or EEPROM memory devices, e.g. by counting numbers of erase or reprogram cycles, by using multiple memory areas serially or cyclically

Abstract

A system for wear-leveling of a non-volatile memory may include a controller configured to allocate memory blocks in the non-volatile memory, a logical-to-physical table populated with pointers to memory blocks in the nonvolatile memory, and a wear-leveling table configured to store two or more pointers to unallocated memory blocks in the non-volatile memory. The unallocated memory blocks are previously allocated to store data by the controller according to the pointers in the logical-to-physical table. The controller is further configured to identify two or more pointers in the wear-leveling table and to store data to the two or more memory blocks associated with the identified pointers.

Claims

1. A system comprising:

a controller configured to allocate one or more memory blocks in a non-volatile memory for storing data, and to compare a number of identified erased memory blocks and faulty memory blocks to a threshold;

a logical-to-physical table populated with pointers to the memory blocks in the nonvolatile memory, wherein the controller is configured to initially allocate the memory blocks to store data according to the pointers in the logical-to-physical table; and

a wear-leveling table configured to store pointers to unallocated memory blocks in the non-volatile memory, wherein the unallocated memory blocks are previously allocated to store data by the controller according to the pointers in the logical-to-physical table, and wherein the controller is configured to identify one or more pointers in the wear-leveling table and to store data to the memory blocks associated with the identified pointers.

2. The system of claim 1, wherein the controller is configured to erase data stored in one or more of the memory blocks and to populate the wear-leveling table with pointers to the one or more erased memory blocks.

3. The system of claim 2, wherein the controller is configured to prioritize the pointers in the wear-leveling table according to when the memory blocks associated with the pointers were erased.

4. The system of claim 3, wherein the controller is configured to linearly search the wear-leveling table for pointers to unallocated memory blocks that are available to store data.

5. The system of claim 1, wherein the controller is further configured to identify the erased memory blocks in the non-volatile memory, to identify the faulty memory blocks in the non-volatile memory, and to populate the wear-leveling table in response to the comparing or initializing the non-volatile memory with pointers to the memory blocks in response to the comparing.

6. The system of claim 1, wherein the controller initializes the logical-to-physical table with the pointers concurrently with populating the wear-leveling table with pointers to the unallocated memory blocks.

7. The system of claim 6, wherein the controller is configured to allocate the memory blocks associated with the pointers in the logical-to-physical table prior to the controller accessing the wear-leveling table for pointers to the unallocated memory blocks.

8. The system of claim 1, wherein the wear-leveling table does not store pointers to the allocated memory blocks;

and

wherein the unallocated memory blocks were previously erased by the controller.

9. The system of claim 1, wherein the unallocated memory blocks include one or more memory blocks available to store data and one or more faulty memory blocks not available to store data.

10. The system of claim 9, wherein the wear-leveling table is configured to indicate to the controller which of the pointers are associated with the faulty memory blocks.

11. The system of claim 1, wherein the non-volatile memory includes multiple memory zones, each memory zone including a plurality of memory blocks and having a different wear-leveling table, wherein the controller is configured to receive a write command identifying a memory zone to store data, to determine that the wear-leveling table does not correspond to the identified memory zone, and to re-populate the wear-leveling table with pointers to memory blocks corresponding to the identified memory zone.

12. An apparatus, comprising:

a wear-leveling table coupled with a flash memory comprising one or more memory blocks;

a controller coupled with the flash memory, wherein the controller is configured to populate the wear-leveling table with pointers to the one or more memory blocks in the flash memory, wherein the pointers are associated with erased memory blocks or faulty memory blocks, and wherein the controller is further configured to store data to at least one memory blocks associated with at least one identified pointer, wherein the controller is further configured to compare a number of erased memory blocks and faulty memory blocks to a threshold; and

a wear-leveling unit within the controller, wherein the wear-leveling unit is configured to identify the at least one pointer in the wear-leveling table.

13. The apparatus of claim 12, wherein the controller is further configured to erase data stored in one or more of the memory blocks in response to identifying at least one pointer in the wear-leveling table and prior to storing data to the memory block associated with the identified pointer.

14. The apparatus of claim 12, further comprising a priority associated with each of the pointers in the wear-leveling table.

15. The apparatus of claim 14, wherein the priority is based on when the memory blocks associated with the pointers were erased.

16. The apparatus of claim 14, wherein the priority is based on a number of write operations performed on the memory blocks associated with the pointers.

17. The apparatus of claim 14 wherein the wear-leveling unit is further configured to access the wear-leveling table for pointers according to the priority of the pointers.

18. The apparatus of claim 12, further comprising a logical-to-physical table, wherein the controller is further configured to initialize the logical-to-physical table with pointers to the memory blocks in the flash memory concurrently with populating the wear-leveling table with pointers associated with the erased memory blocks.

19. The apparatus of claim 12, wherein the controller is further configured to:

to identify the faulty memory blocks in the flash memory;

identify the erased memory blocks in the flash memory;

and

populate the wear-leveling table in response to the comparing.

20. A non-transitory computer-readable media, comprising instructions executable by a processor to perform operations comprising:

populating a wear-leveling table with pointers to one or more memory blocks in a flash memory, where the pointers are associated with erased memory blocks or memory blocks that are faulty;

receiving a write command identifying a zone of the flash memory to store date;

determining the wear-leveling table does not correspond to the identified zone;

re-populating the wear-leveling table with pointers to memory blocks corresponding to the identified zone;

identifying at least one pointer in the re-populated wear-leveling table associated with an erased memory block; and

storing data to the memory block associated with the identified pointer.

21. The non-transitory computer-readable media of claim 20, comprising:

identifying erased memory blocks and faulty memory blocks in the flash memory;

comparing a number of identified erased memory blocks and faulty memory blocks to a threshold; and

populating the wear-leveling table in response to a result of the comparing.

22. The non-transitory computer-readable media of claim 20, comprising:

identifying erased memory blocks and faulty memory blocks in the flash memory;

comparing a number of identified erased memory blocks and faulty memory blocks to a threshold; and

initializing the flash memory with pointers to the memory blocks in response to a result of the comparing.