Granted Patent B2

US 8,843,691 · App. 12/343,378 · Granted Sep 23, 2014

Abstract

Claims (41)

1. A method for managing memory operations in a flash storage device having a plurality of data blocks, each block comprising a plurality of data segments, the method comprising the steps of:

providing one or more linked lists comprising a plurality of nodes, each of the plurality of nodes indicating the number of valid data segments in a corresponding one of the plurality of data blocks;

ordering the plurality of nodes in the one or more linked lists based upon the number of valid data segments indicated therein;

selecting one of the plurality of data blocks for erasure based on the ordering of the one or more linked lists such that the selected data block corresponds to one of the plurality of nodes indicating a lowest number of valid data segments; and

erasing the selected data block when an available number of pre-erased data blocks falls below a predetermined amount.

2. The method according to claim 1 , wherein the step of selecting one of the plurality of data blocks for erasure further comprises selecting the data block for erasure based upon a number of invalid data segments therein.

3. The method according to claim 1 , wherein the step of erasing comprises copying the valid data segments of the selected data block to another one of the plurality of data blocks.

4. The method according to claim 3 , wherein the other data block is a pre-erased data block.

5. The method according to claim 1 , wherein the data segments in each of the plurality of data segments comprises 4 kB.

6. The method according to claim 1 , wherein each of the plurality of nodes indicates the number of valid data segments in a corresponding one of the plurality of data blocks by indicating a number of invalid data segments in the corresponding one of the plurality of data blocks.

7. The method according to claim 1 , wherein the lowest number of valid data segments corresponds to a predetermined number of valid data segments.

8. The method according to claim 1 , wherein the one or more linked lists comprise a plurality of linked lists, each of the plurality of linked lists indicating a number of valid data segments in each data block of a distinct subset of the plurality of data blocks, each subset of the plurality of data blocks having a predefined range of valid data segments.

9. The method according to claim 1 , wherein the selected one of the plurality of data blocks corresponds to one of the plurality of nodes at an end of one of the one or more linked lists.

10. The method according to claim 1 , further comprising the step of:

updating the one or more linked lists based upon an operation in the flash storage device which changes the number of valid data segments of one of the plurality of data blocks.

11. The method according to claim 1 , wherein the step of selecting one of the plurality of data blocks for erasure is part of a background maintenance task.

12. The method according to claim 1 , wherein the step of selecting one of the plurality of data blocks for erasure is triggered in response to a rewrite operation of the flash storage device.

13. A flash storage device, comprising:

a plurality of data blocks, each block comprising a plurality of data segments; and

a controller configured to:

provide one or more linked lists comprising a plurality of nodes, each of the plurality of nodes indicating the number of valid data segments in a corresponding one of the plurality of data blocks;

order the plurality of nodes in the one or more linked lists based upon the number of valid data segments indicated therein;

select one of the plurality of data blocks for erasure based on the ordering of the one or more linked lists such that the selected data block corresponds to one of the plurality of nodes indicating a lowest number of valid data segments; and

erase the selected data block when an available number of pre-erased data blocks falls below a predetermined amount.

14. The flash storage device according to claim 13 , wherein the controller is configured to erase the one of the plurality of data blocks by erasing the one of the plurality of data blocks based upon a number of invalid data segments therein.

15. The flash storage device according to claim 13 , wherein the controller is further configured to copy the valid data segments of the selected one of the plurality of data blocks to another one of the plurality of data blocks before erasing the selected one of the plurality of data blocks.

16. The flash storage device according to claim 15 , wherein the another one of the plurality of data blocks is a pre-erased data block.

17. The flash storage device according to claim 13 , wherein the data segments in each of the plurality of data segments comprises 4 kB.

18. The flash storage device according to claim 13 , further comprising a machine-readable medium configured to store the one or more linked lists.

19. The flash storage device according to claim 13 , wherein each of the plurality of nodes indicates the number of valid data segments in a corresponding one of the plurality of data blocks by indicating a number of invalid data segments in the corresponding one of the plurality of data blocks.

20. The flash storage device according to claim 13 , wherein the lowest number of valid data segments corresponds to a predetermined number of valid data segments.

21. The flash storage device according to claim 13 , wherein the one or more linked lists comprise a plurality of linked lists, each of the plurality of linked lists indicating a number of valid data segments in each data block of a distinct subset of the plurality of data blocks, each subset of the plurality of data blocks having a predefined range of valid data segments.

22. The flash storage device according to claim 13 , wherein the selected one of the plurality of data blocks corresponds to one of the plurality of nodes at an end of one of the one or more linked lists.

23. The flash storage device according to claim 13 , wherein the controller is further configured to update the one or more linked lists based upon an operation in the flash storage device which changes the number of valid data segments of one of the plurality of data blocks.

24. The flash storage device according to claim 13 , wherein the controller is configured to select one of the plurality of data blocks for erasure as part of a background maintenance task.

25. The flash storage device according to claim 13 , wherein the controller is configured to select one of the plurality of data blocks for erasure in response to a rewrite operation of the flash storage device.

26. A non-transitory machine readable medium storing one or more sequences of instructions for managing memory operations in a flash storage device having a plurality of data blocks, each block comprising a plurality of data segments, wherein execution of the one or more sequences of instructions by one or more processors causes the one or more processors to perform the steps of:

providing one or more linked lists comprising a plurality of nodes, each of the plurality of nodes indicating the number of valid data segments in a corresponding one of the plurality of data blocks;

ordering the plurality of nodes in the one or more linked lists based upon the number of valid data segments indicated therein;

selecting one of the plurality of data blocks for erasure based on the ordering of the one or more linked lists such that the selected data block corresponds to one of the plurality of nodes indicating a lowest number of valid data segments; and

erasing the selected one of the plurality of data blocks when an available number of pre-erased data blocks falls below a predetermined amount.

Assignments (12)