Managing wear leveling and garbage collection operations in a solid-state memory using linked lists

• US 8,713,066 B1
• Filed: 03/29/2010
• Issued: 04/29/2014
• Est. Priority Date: 03/29/2010
• Status: Active Grant

• Current Assignee: Sandisk Technologies Incorporated (Western Digital Corporation)
• Original Assignee: Western Digital Technologies Incorporated (Western Digital Corporation)
• Inventors: Phan, Lan D., Pajaro, Cliff, Lo, Jerry
• Primary Examiner(s): KIM, HONG CHONG
• Application Number:
  US12/749,329
• Time in Patent Office: 1,492 Days
• Field of Search: 707/800, 707/673, 707/722, 707/726, 707/824, 711/103, 711/158, 711/159, 711/170, 711/154
• US Class Current: 707/800
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 2212/1016 Performance improvement
• CPC Class Codes: G06F 2212/214 Solid state disk
• CPC Class Codes: G06F 2212/7205 Cleaning, compaction, garbage collection, erase control
• CPC Class Codes: G06F 2212/7207 management of metadata or control data
• CPC Class Codes: G06F 2212/7211 Wear leveling

Abstract

Embodiments of the invention provide a storage subsystem comprising a non-volatile solid-state memory array and a system operation module for managing memory operations. The system operation module is configured to store system operation data in a data structure that includes linked lists for storing system operation data, with at least some lists including entries referencing blocks in the solid-state memory array belonging to a category. The system operation module is further configured to (1) move a particular entry from a first linked list to a second linked list when a block referenced by the particular entry in the first linked list has met a condition for being classified in a new category that is different from that of the blocks referenced by entries in the first linked list, and (2) update entries within the first and second linked lists so that the dependencies in the linked lists are maintained.

Claims

1. A storage subsystem, comprising:

a non-volatile solid-state memory array; and

a system operation module for managing memory operations, the system operation module configured to;

store system operation data associated with an internal system operation in a data structure, the data structure comprising a plurality of linked lists for storing system operation data associated with the internal system operation, at least some of the lists comprising a plurality of entries referencing blocks in the solid-state memory array belonging to a category;

in response to detecting that a block referenced by a first entry in a first linked list has met a condition for being classified in a new category that is different from that of the blocks referenced by entries in the first linked list, remove the first entry from the first linked list, add the first entry to a second linked list comprising entries referencing blocks belonging to the new category, and designate a block referenced by a second entry as a preferred block for the internal system operation; and

update entries within the first and second linked lists so that the dependencies in the first and second linked lists are maintained.

2. The storage subsystem of claim 1, wherein the system operation module comprises a wear leveling module for managing wear leveling memory operations and the data structure comprises a plurality of linked lists for storing wear level data.

3. The storage subsystem of claim 2, wherein each of the linked lists comprises a plurality of entries referencing blocks in the solid-state memory array belonging to a wear level category and a designated entry referencing a block to be selected in an upcoming wear leveling operation.

4. The storage subsystem of claim 3, wherein the wear leveling module is configured to select, for use in a wear leveling operation, a block referenced by the designated entry of a linked list referencing blocks belonging to a preferred category.

5. The storage subsystem of claim 4, wherein the preferred category is a category of blocks with the lowest wear level.

6. The storage subsystem of claim 3, wherein the block designated as the preferred block is a block to be selected in an upcoming wear leveling operation.

7. The storage subsystem of claim 2, wherein the category is defined by a wear level threshold and the condition comprises meeting a minimum wear level threshold.

8. The storage subsystem of claim 2, wherein the wear level of a block is a composite rating based on an erase count and an erase time.

9. The storage subsystem of claim 2, wherein the wear level of a block is based on one of an erase count and an erase time.

10. The storage subsystem of claim 1, wherein each entry comprises:

a reference to a block within the memory array;

a first pointer pointing to a next entry within the linked list; and

a second pointer pointing to a previous entry within the linked list.

11. The storage subsystem of claim 10, wherein the system operation module is further configured to remove the first entry from the first linked list and add the first entry to the second linked list by updating the first and second pointers of the first entry to point to entries in the second linked list.

12. The storage subsystem of claim 1, wherein the plurality of linked lists is implemented within an array data structure.

13. The storage subsystem of claim 1, wherein the system operation module comprises a garbage collection module and the condition comprises meeting a minimum threshold of invalid pages within a block.

14. A method of managing memory operations in non-volatile solid-state memory:

creating a plurality of linked lists for storing wear level data, at least one list comprising a plurality of entries referencing blocks in the solid-state memory assigned to a category;

in response to detecting that a block referenced by a first entry in a first linked list has met a condition for being assigned to a new category that is different from the assigned category of the blocks referenced by entries in the first linked list, moving the first entry to a second linked list comprising entries referencing blocks assigned to the new category and designating a block referenced by a second entry as a preferred block for wear leveling; and

updating entries within the first and second linked lists so that the dependencies in the first and second linked lists are preserved.

15. The method of claim 14, wherein each of the lists comprises a plurality of entries referencing blocks in the solid-state memory belonging to a wear level category and a designated entry referencing a block to be selected in an upcoming wear leveling operation.

16. The method of claim 15, further comprising selecting, for use in a wear leveling operation, the block referenced by the designated entry of a non-empty linked list referencing blocks with the lowest wear level category.

17. The method of claim 15, wherein the moving further comprises marking the first entry as the designated entry in the second linked list.

18. The method of claim 15, wherein the wear level of a block is a composite rating based on an erase count and an erase time.

19. The method of claim 15, wherein the wear level of a block is based on one of an erase count and an erase time.

20. The method of claim 14, wherein each entry comprises a reference to a block, a first pointer pointing to a next entry within the list, and a second pointer pointing to a previous entry within the list.

21. The method of claim 20, wherein the moving further comprises updating the first and second pointers of the first entry to point to entries in the second linked list.

22. The method of claim 14, wherein the linked lists are doubly linked lists.

23. The method of claim 14, wherein the plurality of linked lists is implemented within an array data structure.

24. The method of claim 14, wherein the condition comprises meeting a minimum wear level threshold.