Logical block addressing range collision crawler

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.

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.

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.

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.