Granted Patent B2

US 10,649,909 · App. 16/137,261 · Granted May 12, 2020

Abstract

Claims (67)

1. A device, comprising:

a controller configured to execute a range crawler algorithm residing in firmware on the controller;

a data table comprising one or more range entries, wherein

each of the one or more range entries is part of a logical block address span associated with a command instruction,

each logical block address span is comprised of one or more logical block address ranges,

each logical block address range is comprised of one or more sequential logical block addresses, and

the data table includes a range entry index of the range entries, a start logical block address for each range entry in the range entry index, a length of the logical block address for each range entry in the range entry index, the next range entry for each range entry in the range entry index, a timestamp for each range entry in the range entry index, and a range collision bitmap for each range entry in the range entry index;

a collision bitmap configured to store data associated with range entry collisions between one or more logical block addresses; and

a command dispatcher configured to release selected logical block address ranges that are not associated with a range entry collision, wherein

the range crawler algorithm is configured to search the data table to detect collisions between the range entries.

2. The device of claim 1 , further comprising multiple range crawler algorithms operating simultaneously.

3. The device of claim 1 , wherein the range crawler algorithm identifies each logical block address range of the command instruction associated with a collision in the collision bitmap.

4. The device of claim 1 , wherein the range crawler algorithm is rerun whenever a range entry is updated.

5. The device of claim 1 , wherein the command instruction is comprised of disjointed logical block address ranges.

6. A device, comprising:

a controller configured to execute a range crawler algorithm residing in hardware on the controller;

a data table configured to store one or more range entries, wherein

each of the one or more range entries is part of a logical block address span associated with a command instruction,

each logical block address span is comprised of one or more logical block address ranges,

each logical block address range is comprised of one or more sequential logical block addresses, and

the data table includes a range entry index of the range entries, a start logical block address for each range entry in the range entry index, a length of the logical block address for each range entry in the range entry index, the next range entry for each range entry in the range entry index, a timestamp for each range entry in the range entry index, and a range collision bitmap for each range entry in the range entry index;

a collision bitmap configured to store data associated with range entry collisions between one or more logical block addresses;

a command dispatcher configured to release selected logical block address ranges that are not associated with a range entry collision, wherein

the range crawler algorithm is configured to search the data table to detect collisions between the range entries; and

means for detecting and responding to collisions between range entries, wherein

the range crawler algorithm is configured to search the data table to detect collisions between the range entries, and

responding to collisions is comprised of dispatching, by the command dispatcher, selected logical block address spans based on the collision bitmap.

7. The device of claim 6 , further comprising multiple range crawler algorithms operating simultaneously, wherein the multiple range crawler algorithms operate when the controller adds a range entry to the data table via a parsed command from the controller.

8. The device of claim 6 , further comprising multiple range crawler algorithms operating simultaneously, wherein the multiple range crawler algorithms operate when the controller adds a range entry to the data table as a result of a data table write command.

9. The device of claim 6 , wherein a given range entry is removed from the data table when a search associated with the logical block address span has been completed.

10. The device of claim 6 , wherein the data table has a reserved range entry value configured to mark a drive-wide logical block address span until the logical block address ranges are received.

11. A device, comprising:

a controller configured to execute a range crawler algorithm residing in hardware separate from the controller;

a data table configured to store one or more range entries, wherein

each of the one or more range entries is part of a logical block address span associated with a command instruction,

each logical block address span is comprised of one or more logical block address ranges,

each logical block address range is comprised of one or more sequential logical block addresses, and

the data table includes a range entry index of the range entries, a start logical block address for each range entry in the range entry index, a length of the logical block address for each range entry in the range entry index, the next range entry for each range entry in the range entry index, a timestamp for each range entry in the range entry index, and a range collision bitmap for each range entry in the range entry index;

a collision bitmap configured to store data associated with range entry collisions between one or more logical block addresses; and

a command dispatcher configured to release selected full and partial logical block address ranges that are not associated with a collision, wherein

the range crawler algorithm is configured to search the data table to detect collisions between the range entries.

12. The device of claim 11 , wherein the controller executes command instructions that are required to be executed without running the range crawler algorithm by marking a full-drive logical block address span associated with that instruction.

13. The device of claim 11 , further comprising multiple range crawler algorithms running simultaneously.

14. The device of claim 11 , wherein the range crawler algorithm is rerun whenever a command instruction containing a partial logical block address range is completed.

15. The device of claim 11 , further comprising the command dispatcher releasing all range entries associated with a collision bitmap comprised of all zeroes.

16. A method for conducting collision management of a storage device, the method comprising:

receiving, from a controller, one or more command instructions, wherein

each command instruction is comprised of a logical block address, and

each logical block address is comprised of multiple ranges;

storing, by a data table, a range entry associated with each logical block address range, wherein the data table includes a range entry index of the range entries, a start logical block address for each range entry in the range entry index, a length of the logical block address for each range entry in the range entry index, the next range entry for each range entry in the range entry index, a timestamp for each range entry in the range entry index, and a range collision bitmap for each range entry in the range entry index:

detecting, by a range crawler algorithm, a collision between two or more range entries;

updating, by the controller, a collision bitmap based on the collision; and

dispatching, by a command dispatcher, selected logical block address ranges to the storage device based on the collision bitmap.

17. The method of claim 16 , further comprising executing multiple range crawler algorithms simultaneously.

18. The method of claim 16 , further comprising releasing range entries associated with a collision bitmap comprised of all zeroes.

19. The method of claim 16 , further comprising releasing range entries to the controller when the range crawler algorithm has finished.

20. The method of claim 16 , further comprising updating range entries as the range crawler algorithm is executing.

21. The method of claim 16 , wherein the range crawler algorithm blocks further command instructions to the logical block address range associated with a current range entry.

22. The method of claim 16 , wherein command instructions that have priority are executed by marking a full-drive logical block address range that is associated with that command instruction.

23. The method of claim 16 , further comprising rerunning the range crawler algorithm whenever a collision is detected.

24. A method of operating a range crawler algorithm for a storage device, the method comprising:

receiving, from a data table, one or more range entries; wherein each range entry contains a logical block address range associated with a command instruction, wherein the data table includes a range entry index of the range entries, a start logical block address for each range entry in the range entry index, a length of the logical block address for each range entry in the range entry index, the next range entry for each range entry in the range entry index, a timestamp for each range entry in the range entry index, and a range collision bitmap for each range entry in the range entry index;

comparing, by the range crawler algorithm, two or more range entries;

detecting, by the range crawler algorithm, a collision between two or more range entries;

updating, by the range crawler algorithm, a collision bitmap based on detecting a collision; and

dispatching selected logical block address ranges based on the collision bitmap.

25. The method of claim 24 , further comprising rerunning the range crawler algorithm whenever a range entry is updated.

Assignments (10)