Compression and caching for logical-to-physical storage address mapping tables
A storage device that maps logical addresses to physical addresses includes a memory that stores machine instructions and a processor coupled to the memory that executes the machine instructions to store a compressed mapping table in the memory. The compressed mapping table correlates logical addresses to locations in a storage. The storage device also stores a bundle of uncompressed mapping table entries starting at a first location in a cache and maps a first logical address associated with the uncompressed mapping table entry to the first location.
1. A storage device for logical-to-physical address mapping, comprising:
a memory that stores machine instructions; and
a processor coupled to the memory and configured to execute the machine instructions, wherein the machine instructions, when executed, cause the processor to:
construct a mapping table comprising a plurality of table entries, wherein the mapping table is indexed by logical addresses and each of the table entries comprises a corresponding physical address in a storage,
replace a first sequence of the plurality of table entries comprising sequential physical addresses with a first compressed mapping table entry and a second compressed mapping table entry to generate a compressed mapping table, the first compressed mapping table entry representing an initial physical address of the sequential physical addresses in a same format as a corresponding table entry of the plurality of table entries, and the second compressed mapping table entry representing a number of incremental addresses in the first sequence;
store the compressed mapping table in the memory,
store a plurality of uncompressed mapping table entries starting at a first location in a cache, and
map a first logical address associated with a first uncompressed mapping table entry to the first location in the cache.
2. The storage device of claim 1 , wherein the machine instructions, when executed, further cause the processor to:
determine a second logical address is not currently mapped to the cache,
retrieve a compressed mapping table entry associated with the second logical address from the compressed mapping table,
decompress the compressed mapping table entry to yield a plurality of uncompressed mapping table entries,
store the plurality of uncompressed mapping table entries starting at a second location in the cache, and
map the second logical address to the second location.
3. The storage device of claim 1 , wherein the machine instructions, when executed, further cause the processor to:
determine the cache lacks sufficient available space,
evict the mapping of the first logical address to the first location,
compress the plurality of uncompressed mapping table entries to yield a compressed mapping table entry, and
update the compressed mapping table with the compressed mapping table entry.
4. The storage device of claim 1 , wherein the machine instructions, when executed, further cause the processor to transfer the compressed mapping table to a nonvolatile memory at power down.
5. The storage device of claim 1 , wherein the machine instructions, when executed, further cause the processor to format the plurality of mapping table entries, each comprising a distribution of bits among a plurality of designations correlated with an organization of the storage.
6. The storage device of claim 1 , wherein the machine instructions, when executed, further cause the processor to maintain a lookup table including a lookup entry corresponding to a bundle space, wherein the lookup entry indicates whether or not an uncompressed mapping table entry spans an additional bundle space.
7. The storage device of claim 1 , wherein the compressed mapping table comprises a plurality of bundle spaces of equal size, each of the uncompressed mapping table entries corresponding to one or more of the bundle spaces.
8. The storage device of claim 1 , wherein the memory comprises a dynamic random access memory, the cache comprises a static random access memory, and the storage comprises a NAND-flash memory.
9. The storage device of claim 8 , wherein the logical addresses comprise logical block addresses received from a host computer and the locations in the storage comprise physical blocks.
10. A method for logical-to-physical address mapping, comprising:
constructing a mapping table comprising a plurality of table entries, wherein the mapping table is indexed by logical addresses and each of the table entries comprises a corresponding physical address in a storage;
replacing a first sequence of the plurality of table entries comprising sequential physical addresses with a first compressed mapping table entry and a second compressed mapping table entry to generate a compressed mapping table, the first compressed mapping table entry representing an initial physical address of the sequential physical addresses in a same format as a corresponding table entry of the plurality of table entries, and the second compressed mapping table entry representing a number of incremental addresses in the first sequence;
storing the compressed mapping table in a memory;
storing a plurality of uncompressed mapping table entries starting at a first location in a cache; and
mapping a first logical address associated with a first uncompressed mapping table entry to the first location in the cache.
11. The method of claim 10 , further comprising:
determining a second logical address is not currently mapped to the cache;
retrieving a compressed mapping table entry associated with the second logical address from the compressed mapping table;
decompressing the compressed mapping table entry to yield a plurality of uncompressed mapping table entries;
storing the plurality of uncompressed mapping table entries starting at a second location in the cache; and
mapping the second logical address to the second location.
12. The method of claim 10 , further comprising:
determining the cache lacks sufficient available space;
evicting the mapping of the first logical address to the first location;
compressing the plurality of uncompressed mapping table entries to yield a compressed mapping table entry; and
updating the compressed mapping table with the compressed mapping table entry.
13. The method of claim 10 , further comprising formatting a plurality of uncompressed mapping table entries, each comprising a distribution of bits among a plurality of designations correlated with an organization of the storage.
14. The method of claim 10 , further comprising transferring the compressed mapping table to a nonvolatile memory at power down.
15. The method of claim 10 , further comprising maintaining a lookup table including a lookup entry corresponding to a bundle space, wherein the lookup entry indicates whether or not an uncompressed mapping table entry spans an additional bundle space.
16. The method of claim 10 , wherein the compressed mapping table comprises a plurality of bundle spaces of equal size, each of the uncompressed mapping table entries corresponding to one or more of the bundle spaces.
17. The method of claim 10 , wherein the memory comprises a dynamic random access memory, the cache comprises a static random access memory, and the storage comprises a NAND-flash memory.
18. The method of claim 17 , wherein the logical addresses comprise logical block addresses received from a host computer and the locations in the storage comprise physical blocks.
19. A non-transitory, computer-readable storage medium encoded with instructions adapted to be executed by a processor to implement:
constructing a mapping table comprising a plurality of table entries, wherein the mapping table is indexed by logical addresses and each of the table entries comprises a corresponding physical address in a storage;
replacing a first sequence of the plurality of table entries comprising sequential physical addresses with a first compressed mapping table entry and a second compressed mapping table entry to generate a compressed mapping table, the first compressed mapping table entry representing an initial physical address of the sequential physical addresses in a same format as a corresponding table entry of the plurality of table entries, and the second compressed mapping table entry representing a number of incremental addresses in the first sequence;
storing the compressed mapping table in a memory;
storing a plurality of uncompressed mapping table entries starting at a first location in a cache; and
mapping a first logical address associated with a first uncompressed mapping table entry to the first location in the cache.
20. The computer-readable storage medium of claim 19 , wherein the instructions are further adapted to implement transferring the compressed mapping table to a nonvolatile memory at power down, wherein the memory comprises a dynamic random access memory, the cache comprises a static random access memory, and the storage comprises a NAND-flash memory.