Solid state drive power safe wear-leveling

• US 8,090,899 B1
• Filed: 03/04/2009
• Issued: 01/03/2012
• Est. Priority Date: 03/04/2009
• Status: Expired due to Fees

• Current Assignee: Western Digital Technologies Incorporated (Western Digital Corporation)
• Original Assignee: Western Digital Technologies Incorporated (Western Digital Corporation)
• Inventors: Syu, Mei-Man L.
• Primary Examiner(s): Elmore, Reba I
• Application Number:
  US12/398,093
• Time in Patent Office: 1,035 Days
• Field of Search: 711/103, 711/156, 711/166
• 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

A solid state drive includes a plurality of flash memory devices, and a memory controller coupled to the plurality of flash memory devices. The memory controller is configured to logically associate blocks from the plurality of flash memory devices to form zip codes, the zip codes associated with corresponding erase counters. The solid state drive further includes a processor and a computer-readable memory having instructions stored thereon. The processor may perform a wear-leveling operation by determining that blocks in a first zip code have been erased and incrementing a first erase counter associated with the first zip code. It may then be determined that a second erase counter associated with a second zip code is low relative to at least one other erase counter, and based on this determination, data from blocks in the second zip code may be written to new blocks as part of a wear-leveling operation.

Claims

1. A solid state drive comprising:

a first flash memory device logically divided into a first plurality of blocks, each of the first plurality of blocks being logically divided into addressable pages;

a second flash memory device logically divided into a second plurality of blocks, each of the second plurality of blocks being logically divided into addressable pages;

a memory controller coupled to the first flash memory device and the second flash memory device, the memory controller configured to logically associate a first block of the first plurality of blocks with a second block of the second plurality of blocks to form a first zip code, the first zip code associated with a first erase counter, and configured to logically associate a first source block of the first plurality of blocks with a second source block of the second plurality of blocks to form a second zip code, the second zip code associated with a second erase counter;

a processor coupled to the memory controller and operable to execute instructions; and

a computer-readable memory having instructions stored thereon that are executable by the processor in order to cause the processor to perform a wear-leveling operation, by;

determining that the first block and the second block in the first zip code have been erased;

based at least in part on the determination, incrementing the first erase counter associated with the first zip code;

after incrementing the first erase counter, determining that the second erase counter associated with the second zip code is low relative to at least one other erase counter; and

based at least in part on determining that the second erase counter is low, writing data from the first source block and the second source block in the second zip code to a first target block of the first plurality of blocks and a second target block of the second plurality of blocks as part of the wear-leveling operation.

2. The solid state drive of claim 1, wherein the computer-readable memory has further instructions stored thereon that are executable by the processor in order to cause the processor to perform the wear-leveling operation, by:

writing a header to the first flash memory device, the header including information indicative of the first source block, the second source block, the first target block, and the second target block;

suspending the wear-leveling operation; and

based at least in part on suspending the wear-leveling operation, writing a footer to at least one of the first flash memory device and the second flash memory device, the footer including information indicative of progress made on the wear-leveling operation prior to the suspension.

3. The solid state drive of claim 2, wherein the computer-readable memory has further instructions stored thereon that are executable by the processor in order to cause the processor to perform the wear-leveling operation, by:

storing information indicative of current locations on the first flash memory device and the second flash memory device in which the header and the footer are written in a non-volatile memory separate from the first flash memory device and the second flash memory device, the current locations comprising at least one warehouse zip code.

4. The solid state drive of claim 2, wherein the computer-readable memory has further instructions stored thereon that are executable by the processor in order to cause the processor to perform the wear-leveling operation, by:

reading the data from the first source block and the second source block to a volatile memory buffer before writing the header.

5. The solid state drive of claim 2, wherein writing the data from the first source block and the second source block in the second zip code to the first target block and the second target block comprises:

after writing the header, writing a first page of the first source block to the first target block and writing a second page of the second source block to the second target block;

after writing the first page and the second page, determining if the wear-leveling operation is complete and determining if the wear-leveling operation should be suspended; and

if the wear-leveling operation is not complete and should not be suspended, writing a third page of the first source block to the first target block and writing a fourth page of the second source block to the second target block.

6. The solid state drive of claim 5, wherein the computer-readable memory has further instructions stored thereon that are executable by the processor in order to cause the processor to perform the wear-leveling operation, by:

if the wear-leveling operation is complete, writing a completion footer including information indicative of completion of the wear-leveling operation and erasing the first source block and the second source block.

7. The solid state drive of claim 2, wherein the computer-readable memory has further instructions stored thereon that are executable by the processor in order to cause the processor to perform the wear-leveling operation, by:

after a powering-up of the solid state drive, reading the footer to determine the progress made on the wear-leveling operation prior to the suspension; and

resuming the wear-leveling operation based at least in part on the footer.

8. The solid state drive of claim 7, wherein the computer-readable memory has further instructions stored thereon that are executable by the processor in order to cause the processor to perform the wear-leveling operation, by, after reading the footer:

accessing the header associated with the footer;

reading the header to identify the first source block, the second source block, the first target block, and the second target block; and

resuming the wear-leveling operation based at least in part on the footer and the header.

9. The solid state drive of claim 2, wherein the first flash memory device and the second flash memory device support internal data copies, and wherein writing the data from the first source block and the second source block in the second zip code to the first target block and the second target block comprises:

after writing the header, causing the first flash memory device to copy a first page of the first source block to the first target block and causing the second flash memory device to copy a second page of the second source block to the second target block;

after causing the first flash memory device and the second flash memory device to copy the first page and the second page, respectively, determining if the wear-leveling operation is complete and determining if the wear-leveling operation should be suspended; and

if the wear-leveling operation is not complete and should not be suspended, causing the first flash memory device to copy a third page of the first source block to the first target block and causing the second flash memory device to copy a fourth page of the second source block to the second target block.

10. The solid state drive of claim 1, wherein the computer-readable memory has further instructions stored thereon that are executable by the processor in order to cause the processor to perform the wear-leveling operation, by:

after a powering-up of the solid state drive, searching for footers including information indicative of progress made on wear-leveling operations;

if no footer is found, searching for headers including information indicative of source blocks and target blocks associated with wear-leveling operations; and

if a header associated with the wear-leveling operation is found, erasing any partially programmed target blocks associated with the header, and writing a completion footer including information indicative of completion of the wear-leveling operation; and

re-scheduling the wear-leveling operation based at least in part on the header.

11. A solid state drive comprising:

a flash memory device logically divided into a plurality of blocks, each of the plurality of blocks being logically divided into addressable pages;

a memory controller coupled to the flash memory device;

a processor coupled to the memory controller and operable to execute instructions; and

a computer-readable memory having instructions stored thereon that are executable by the processor in order to cause the processor to perform a wear-leveling operation, by;

determining that an erase counter associated with a source block of the plurality of blocks is low relative to at least one other erase counter;

based at least in part on the determination, writing a header to the flash memory device, the header including information indicative of the source block and a target block of the plurality of blocks;

based at least in part on the determination, writing data from the source block to the target block as part of the wear-leveling operation;

suspending the wear-leveling operation; and

based at least in part on suspending the wear-leveling operation, writing a footer to the flash memory device, the footer including information indicative of progress made on the wear-leveling operation prior to the suspension.

12. The solid state drive of claim 11, wherein writing the data from the source block to the target block comprises:

after writing the header, writing a first page of the source block to the target block;

after writing the first page, determining if the wear-leveling operation is complete and determining if the wear-leveling operation should be suspended; and

if the wear-leveling operation is not complete and should not be suspended, writing a second page of the source block to the target block.

13. The solid state drive of claim 12, wherein the computer-readable memory has further instructions stored thereon that are executable by the processor in order to cause the processor to perform the wear-leveling operation, by:

if the wear-leveling operation is complete, writing a completion footer to the flash memory device, the completion footer including information indicative of completion of the wear-leveling operation and erasing the source block.

14. The solid state drive of claim 11, wherein the computer-readable memory has further instructions stored thereon that are executable by the processor in order to cause the processor to perform the wear-leveling operation, by:

after a powering-up of the solid state drive, reading the footer to determine the progress made on the wear-leveling operation prior to the suspension; and

resuming the wear-leveling operation based at least in part on the footer.

15. The solid state drive of claim 14, wherein the computer-readable memory has further instructions stored thereon that are executable by the processor in order to cause the processor to perform the wear-leveling operation, by:

accessing the header associated with the footer;

reading the header to identify the source block and the target block; and

resuming the wear-leveling operation based at least in part on the footer and the header.

16. The solid state drive of claim 11, wherein the computer-readable memory has further instructions stored thereon that are executable by the processor in order to cause the processor to perform the wear-leveling operation, by:

after a powering-up of the solid state drive, searching for footers including information indicative of progress made on wear-leveling operations;

if no footer is found, searching for headers including information indicative of source blocks and target blocks associated with wear-leveling operations;

if the header is found, erasing any partially programmed target blocks associated with the header, and writing a completion footer including information indicative of completion of the wear-leveling operation before re-scheduling the wear-leveling operation; and

re-scheduling the wear-leveling operation based at least in part on the header.

17. The solid state drive of claim 11, wherein the computer-readable memory has further instructions stored thereon that are executable by the processor in order to cause the processor to perform the wear-leveling operation, by:

storing information indicative of current locations on the flash memory device in which the header and the footer are written in a non-volatile memory separate from the flash memory device.

18. A method of operating a solid state drive having a first flash memory device logically divided into a first plurality of blocks, each of the first plurality of blocks being logically divided into addressable pages, a second flash memory device logically divided into a second plurality of blocks, each of the second plurality of blocks being logically divided into addressable pages, and a memory controller coupled to the first flash memory device and to the second flash memory device, the method comprising:

logically associating a first block of the first plurality of blocks with a second block of the second plurality of blocks to form a first zip code, the first zip code associated with a first erase counter;

logically associating a first source block of the first plurality of blocks with a second source block of the second plurality of blocks to form a second zip code, the second zip code associated with a second erase counter;

determining that the first block and the second block in the first zip code have been erased;

based at least in part on the determination, incrementing the first erase counter associated with the first zip code;

after incrementing the first erase counter, determining that the second erase counter associated with the second zip code is low relative to at least one other erase counter; and

based at least in part on determining that the second erase counter is low, writing data from the first source block and the second source block in the second zip code to a first target block of the first plurality of blocks and a second target block of the second plurality of blocks as part of a wear-leveling operation.

19. The method of claim 18, further comprising:

writing a header to the first flash memory device, the header including information indicative of the first source block, the second source block, the first target block, and the second target block;

suspending the wear-leveling operation; and

based at least in part on suspending the wear-leveling operation, writing a footer to at least one of the first flash memory device and the second flash memory device, the footer including information indicative of progress made on the wear-leveling operation prior to the suspension.

20. The method of claim 19, further comprising:

storing information indicative of current locations on the first flash memory device and the second flash memory device in which the header and the footer are written in a non-volatile memory separate from the first flash memory device and the second flash memory device, the current locations comprising at least one warehouse zip code.

21. The method of claim 19, further comprising:

reading the data from the first source block and the second source block to a volatile memory buffer before writing the header.

22. The method of claim 19, wherein writing the data from the first source block and the second source block in the second zip code to the first target block and the second target block comprises:

after writing the header, writing a first page of the first source block to the first target block and writing a second page of the second source block to the second target block;

after writing the first page and the second page, determining if the wear-leveling operation is complete and determining if the wear-leveling operation should be suspended; and

if the wear-leveling operation is not complete and should not be suspended, writing a third page of the first source block to the first target block and writing a fourth page of the second source block to the second target block.

23. The method of claim 22, further comprising:

if the wear-leveling operation is complete, writing a completion footer including information indicative of completion of the wear-leveling operation and erasing the first source block and the second source block.

24. The method of claim 19, further comprising:

after a powering-up of the solid state drive, reading the footer to determine the progress made on the wear-leveling operation prior to the suspension; and

resuming the wear-leveling operation based at least in part on the footer.

25. The method of claim 24, further comprising:

accessing the header associated with the footer;

reading the header to identify the first source block, the second source block, the first target block, and the second target block; and

resuming the wear-leveling operation based at least in part on the footer and the header.

26. The method of claim 19, wherein the first flash memory device and the second flash memory device support internal data copies, and wherein writing the data from the first source block and the second source block in the second zip code to the first target block and the second target block comprises:

after writing the header, causing the first flash memory device to copy a first page of the first source block to the first target block and causing the second flash memory device to copy a second page of the second source block to the second target block;

after causing the first flash memory device and the second flash memory device to copy the first page and the second page, determining if the wear-leveling operation is complete and determining if the wear-leveling operation should be suspended; and

if the wear-leveling operation is not complete and should not be suspended, causing the first flash memory device to copy a third page of the first source block to the first target block and causing the second flash memory device to copy a fourth page of the second source block to the second target block.

27. The method of claim 18, further comprising:

after a powering-up of the solid state drive, searching for footers including information indicative of progress made on wear-leveling operations;

if no footer is found, searching for headers including information indicative of source blocks and target blocks associated with wear-leveling operations;

if a header associated with the wear-leveling operation is found, erasing any partially programmed target blocks associated with the header, and writing a completion footer including information indicative of completion of the wear-leveling operation; and

re-scheduling the wear-leveling operation based at least in part on the header.

28. A method of operating a solid state drive having a flash memory device logically divided into a plurality of blocks, each of the plurality of blocks being logically divided into addressable pages, and a memory controller coupled to the flash memory device, the method comprising:

determining that an erase counter associated with a source block of the plurality of blocks is low relative to at least one other erase counter;

based at least in part on the determination, writing a header to the flash memory device, the header including information indicative of the source block and a target block of the plurality of blocks;

based at least in part on the determination, writing data from the source block to the target block as part of a wear-leveling operation;

suspending the wear-leveling operation; and

based at least in part on suspending the wear-leveling operation, writing a footer to the flash memory device, the footer including information indicative of progress made on the wear-leveling operation prior to the suspension.

29. The method of claim 28, wherein writing the data from the source block to the target block comprises:

after writing the header, writing a first page of the source block to the target block;

after writing the first page, determining if the wear-leveling operation is complete and determining if the wear-leveling operation should be suspended; and

if the wear-leveling operation is not complete and should not be suspended, writing a second page of the source block to the target block.

30. The method of claim 29, further comprising:

if the wear-leveling operation is complete, writing a completion footer to the flash memory device, the completion footer including information indicative of completion of the wear-leveling operation and erasing the source block.

31. The method of claim 28, further comprising:

after a powering-up of the solid state drive, reading the footer to determine the progress made on the wear-leveling operation prior to the suspension; and

resuming the wear-leveling operation based at least in part on the footer.

32. The method of claim 31, further comprising:

accessing the header associated with the footer;

reading the header to identify the source block and the target block; and

resuming the wear-leveling operation based at least in part on the footer and the header.

33. The method of claim 28, further comprising:

after a powering-up of the solid state drive, searching for footers including information indicative of progress made on wear-leveling operations;

if no footer is found, searching for headers including information indicative of source blocks and target blocks associated with wear-leveling operations;

if the header is found, erasing any partially programmed target blocks associated with the header, and writing a completion footer including information indicative of completion of the wear-leveling operation; and

re-scheduling the wear-leveling operation based at least in part on the header.

34. The method of claim 33, further comprising:

storing information indicative of current locations on the flash memory device in which the header and the footer are written in a non-volatile memory separate from the flash memory device.