Bit-level indirection defragmentation

1. A method comprising:

grouping, by a controller of a storage device, sequential logical block addresses of a logical span from a plurality of logical spans of the storage device into a plurality of groups of sequential logical block addresses, wherein each group of sequential logical block addresses from the plurality of groups of sequential logical block addresses includes a same number of logical block addresses, and wherein each logical block address from each group of sequential logical block addresses references a physical location of a physical block on the storage device; and

for each group of sequential logical block addresses from the plurality of groups of sequential logical block addresses:

determining, by the controller, whether at least one logical block address of the group of sequential logical block addresses references a physical location of a physical block that includes valid data;

responsive to determining that the at least one logical block address of the group of sequential logical block addresses references the physical location of the physical block that includes valid data, storing, by the controller, a first value to a field of a bit-level indirection table to indicate that the at least one logical block address of the group of sequential logical block addresses references the physical location of the physical block, wherein the bit-level indirection table includes a number of fields equal to a number of groups of sequential logical block addresses in the plurality of groups of sequential logical block addresses for the logical span; and

responsive to determining that none of the logical block addresses of the group of sequential logical block addresses reference the physical location of the physical block that includes valid data, storing, by the controller, a second value to the field of the bit-level indirection table to indicate that none of the logical block addresses of the group of sequential logical block addresses reference the physical location of the physical block that includes valid data.

2. The method of claim 1 , wherein each respective logical span of the plurality of logical spans is associated with a respective bit-level indirection table.

3. The method of claim 1 , further comprising:

storing, by the controller, an accumulation table, wherein the accumulation table has a number of entries equal to a number of bit-level indirection tables, and wherein each entry of the accumulation equals a sum of respective values for each respective field in a respective bit-level indirection table and the preceding entry in the accumulation table.

4. The method of claim 1 , wherein the first value is one, wherein the second value is zero, and wherein each field of the bit-level indirection table comprises a bit.

5. The method of claim 1 , wherein each group of sequential logical block addresses references a group of physical locations of a group of physical blocks comprising one of 16 k, 32 k, 64 k, 128 k, or 256 k bytes of storage.

6. The method of claim 1 , further comprising:

determining, by the controller and based at least in part on the bit-level indirection table, a logical block address of the logical span that references the physical location of the physical block that includes valid data.

7. The method of claim 1 , further comprising:

determining, by the controller and based at least in part on the bit-level indirection table, a number of logical block addresses of the logical span that reference a respective physical location of a respective physical block that includes valid data.

8. The method of claim 1 , further comprising:

for a group of sequential logical block addresses with at least one logical block address that references the physical location of the physical block that includes valid data and at least one logical block address references the physical location of the physical block that includes either invalid data or no data, storing, by the controller, valid data in the physical location of the physical block referenced by each of the at least one logical block address that includes either invalid data or no data.

9. The method of claim 1 , further comprising:

defragmenting, by the controller, the storage device based at least in part on the bit-level indirection table.

10. The method of claim 9 , wherein defragmenting the storage device comprises:

writing, by the controller, each of the groups of sequential logical block addresses from the plurality of groups of sequential logical block addresses where at least one logical block address of the group of sequential logical block addresses references the physical location of the physical block that includes valid data sequentially in the logical span.

11. A storage device comprising:

at least one storage medium; and

a controller configured to:

group sequential logical block addresses of a logical span from a plurality of logical spans of the storage device into a plurality of groups of sequential logical block addresses, wherein each group of sequential logical block addresses from the plurality of groups of sequential logical block addresses includes a same number of logical block addresses, and wherein each logical block address from each group of sequential logical block addresses references a physical location of a physical block on the storage device; and

for each group of sequential logical block addresses from the plurality of groups of sequential logical block addresses:

determine whether at least one logical block address of the group of sequential logical block addresses references a physical location of a physical block that includes valid data;

responsive to determining that the at least one logical block address of the group of sequential logical block addresses references the physical location of the physical block that includes valid data, store a first value to a field of a bit-level indirection table to indicate that the at least one logical block address of the group of sequential logical block addresses references the physical location of the physical block, wherein the bit-level indirection table includes a number of fields equal to a number of groups of sequential logical block addresses in the plurality of groups of sequential logical block addresses for the logical span; and

responsive to determining that none of the logical block addresses of the group of sequential logical block addresses reference the physical location of the physical block that includes valid data, store a second value to the field of the bit-level indirection table to indicate that none of the logical block addresses of the group of sequential logical block addresses reference the physical location of the physical block that includes valid data.

12. The storage device of claim 11 , wherein each respective logical span of the plurality of logical spans is associated with a respective bit-level indirection table.

13. The storage device of claim 11 , wherein the controller is further configured to:

store an accumulation table, wherein the accumulation table has a number of entries equal to a number of bit-level indirection tables, and wherein each entry of the accumulation equals a sum of respective values for each respective field in a respective bit-level indirection table and the preceding entry in the accumulation table.

14. The storage device of claim 11 , wherein the first value is one, wherein the second value is zero, and wherein each field of the bit-level indirection table comprises a bit.

15. The storage device of claim 11 , wherein each group of sequential logical block addresses references a group of physical locations of a group of physical blocks comprising one of 16 k, 32 k, 64 k, 128 k, or 256 k bytes of storage.

16. The storage device of claim 11 , wherein the controller is further configured to:

determine, based at least in part on the bit-level indirection table, a logical block address of the logical span that references the physical location of the physical block that includes valid data.

17. The storage device of claim 11 , wherein the controller is further configured to:

determine, based at least in part on the bit-level indirection table, a number of logical block addresses of the logical span that reference a respective physical location of a respective physical block that includes valid data.

18. The storage device of claim 11 , wherein the controller is further configured to:

for a group of sequential logical block addresses with at least one logical block address that references the physical location of the physical block that includes valid data and at least one logical block address references the physical location of the physical block that includes either invalid data or no data, store valid data in the physical location of the physical block referenced by each of the at least one logical block address that includes either invalid data or no data.

19. The storage device of claim 11 , wherein the controller is further configured to:

defragment the storage device based at least in part on the bit-level indirection table,

wherein the controller being configured to defragment the storage device comprises the controller being configured to:

write each of the groups of sequential logical block addresses from the plurality of groups of sequential logical block addresses where at least one logical block address of the group of sequential logical block addresses references the physical location of the physical block that includes valid data sequentially in the logical span.

20. A device comprising:

means for grouping sequential logical block addresses of a logical span from a plurality of logical spans of a storage device into a plurality of groups of sequential logical block addresses, wherein each group of sequential logical block addresses from the plurality of groups of sequential logical block addresses includes a same number of logical block addresses, and wherein each logical block address from each group of sequential logical block addresses references a physical location of a physical block on the storage device; and

for each group of sequential logical block addresses from the plurality of groups of sequential logical block addresses:

means for determining whether at least one logical block address of the group of sequential logical block addresses references a physical location of a physical block that includes valid data;

responsive to determining that the at least one logical block address of the group of sequential logical block addresses references the physical location of the physical block that includes valid data, means for storing a first value to a field of a bit-level indirection table to indicate that the at least one logical block address of the group of sequential logical block addresses references the physical location of the physical block, wherein the bit-level indirection table includes a number of fields equal to a number of groups of sequential logical block addresses in the plurality of groups of sequential logical block addresses for the logical span; and

responsive to determining that none of the logical block addresses of the group of sequential logical block addresses reference the physical location of the physical block that includes valid data, means for storing a second value to the field of the bit-level indirection table to indicate that none of the logical block addresses of the group of sequential logical block addresses reference the physical location of the physical block that includes valid data.