Write buffer linking for easy cache reads
The present disclosure generally relates to improved optimization of a cache lookup operation by structuring the write cache buffers differently using a link-list. Rather than executing a read command first and then executing a write command only after the read command is executed, this disclosure suggests reordering the command executions. A device waits before executing the read command giving the opportunity to obtain the overlap write command. The device then reorders the command execution and executes first the write command and then executes the read command by accessing the write cache instead of the NAND. When two write commands need to be executed consecutively, the link-list operation is used. The controller finds the relevant buffer in the cache that is needed and overwrites the buffer with the new data. The new data is then written to the cache without accessing the cache multiple times.
1. A data storage device, comprising:
a memory device; and
a controller coupled to the memory device, wherein the controller is configured to:
receive a read command for a first LBA, wherein the first LBA is a LBA in the memory device;
scan a submission queue (SQ) for write commands for the first LBA after receiving the read command for the first LBA;
retrieve a first write command for the first LBA from the SQ;
reorder the first write command and the read command;
execute the first write command to write the first LBA to cache and update an overlap table;
scan the SQ for write commands for the first LBA after executing the first write command;
retrieve a second write command from the SQ, wherein the second write command is for the first LBA and a second LBA:
execute the second write command by overwriting the first LBA in the cache and writing the second LBA to the cache and update the overlap table:
determine that an overlap exists by scanning the overlap table;
parse a pointer from the overlap table;
determine whether the pointer is not an exact pointer for the read command;
scan a link list table and fetch a next buffer, wherein the link list table is separate and distinct from the overlap table;
repeat the determining and scanning the link list table until finding the exact pointer; and
execute the read command by reading the first LBA from the cache instead of the memory device, wherein executing the read command occurs after executing the second write command and after the repeating.
2. The data storage device of claim 1 , wherein executing the first write command comprises:
allocating a first data buffer;
updating the overlap table; and
transferring data to the first data buffer.
3. The data storage device of claim 2 , wherein executing the first write command further comprises:
determining whether an additional buffer is needed;
allocating the additional buffer; and
linking the first data buffer to the additional buffer.
4. The data storage device of claim 3 , wherein linking the first data buffer to the additional buffer comprises adding a pointer in a header of the first data buffer, wherein the pointer points to the additional buffer.
5. The data storage device of claim 2 , wherein the overlap table comprises a pointer to the first data buffer.
6. The data storage device of claim 1 , wherein executing the read command further comprises:
issuing an overlap table lookup;
determining whether an overlap is detected;
search buffers in cache; and
read data from cache.
7. The data storage device of claim 6 , wherein executing the read command further comprises parsing a pointer from the overlap table to a first buffer.
8. The data storage device of claim 7 , wherein executing the read command further comprises:
fetching a first buffer associated with the pointer;
determining whether the first buffer comprises the data to be read;
fetch the next buffer; and
read the data from the next buffer.
9. The data storage device of claim 8 , wherein executing the read command further comprises retrieving a pointer to the next buffer from a heading in the first buffer.
10. The data storage device of claim 1 , wherein executing the first write command comprises:
allocating a first data buffer;
updating the overlap table with a pointer to the first data buffer for the first LBA; and
transferring data to the first data buffer.
11. The data storage device of claim 10 , wherein executing the second write command comprises transferring data to the first data buffer.
12. The data storage device of claim 11 , wherein the overlap table remains unchanged during the execution of the second write command.
13. The data storage device of claim 12 , wherein executing the second write command comprises writing the first LBA from the second write command to the memory device.
14. The data storage device of claim 1 , wherein executing the second write command results in at least a portion of data from the first write command remaining unchanged in one or more buffers.
15. The data storage device of claim 1 , wherein the first LBA from the first write command in cache is not written to the memory device.