Data storage device employing a run-length mapping table and a single address mapping table

• US 8,443,167 B1
• Filed: 12/16/2009
• Issued: 05/14/2013
• Est. Priority Date: 12/16/2009
• Status: Active Grant

• Current Assignee: Western Digital Technologies Incorporated (Western Digital Corporation)
• Original Assignee: Western Digital Technologies Incorporated (Western Digital Corporation)
• Inventors: Fallone, Robert M., Boyle, William B.
• Primary Examiner(s): PORTKA, GARY J
• Application Number:
  US12/639,794
• Time in Patent Office: 1,245 Days
• Field of Search: None
• US Class Current: 711/206
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 2212/7201 Logical to physical mapping or translation of blocks or pages

Abstract

A data storage device is disclosed comprising a non-volatile memory comprising a plurality of memory segments. When a write command comprising a logical block address (LBA) is received, a number of consecutive memory segments to access in response to the write command is determined. When the number of consecutive memory segments to access is greater than a threshold, a new run-length mapping entry in a run-length mapping table (RLMT) is created. When the number of memory segments to access is not greater than a threshold, at least one new single address mapping entry in a single address mapping table (SAMT) is created.

Claims

1. A data storage device comprising:

a non-volatile memory comprising a plurality of memory segments; and

control circuitry operable to;

receive a write command comprising a logical block address (LBA);

determine a number of consecutive memory segments to access in response to the write command;

when the number of consecutive memory segments to access is greater than a threshold of more than one memory segment, create a new run-length mapping entry in a run-length mapping table (RLMT); and

when the number of consecutive memory segments to access is not greater than the threshold, create at least two new single address mapping entries in a single address mapping table (SAMT).

2. The data storage device as recited in claim 1, wherein when the number of consecutive memory segments to access is greater than the threshold, the control circuitry is further operable to:

perform the write command;

determine a number of entries in the SAMT that overlap with the new entry in the RLMT; and

delete the overlapping entries from the SAMT.

3. The data storage device as recited in claim 1, the control circuitry is further operable to:

receive a read command comprising a read LBA

first determine whether the read LBA maps to an entry in the SAMT; and

when the read LBA does not map into the SAMT, use the RLMT to execute the read command.

4. The data storage device as recited in claim 1, wherein:

the non-volatile memory comprises a semiconductor memory array;

the semiconductor memory array comprises a plurality of blocks;

each block comprises a plurality of pages; and

each memory segment corresponds to one of the pages.

5. The data storage device as recited in claim 4, wherein each memory segment corresponds to a part of a page.

6. The data storage device as recited in claim 4, wherein the control circuitry processes the entries in the RLMT to implement page based mapping of the pages in the semiconductor memory array.

7. The data storage device as recited in claim 4, wherein the single address mapping entry comprises a block number identifying a target block and a page offset within the target block.

8. The data storage device as recited in claim 4, wherein the run-length mapping entry comprises a block number identifying a target block, a page offset within the target block, and a number of consecutive pages corresponding to the run-length.

9. The data storage device as recited in claim 1, wherein the control circuitry is further operable to:

coalesce entries in the SAMT into the RLMT; and

delete the coalesced entries from the SAMT.

10. The data storage device as recited in claim 9, wherein the control circuitry is further operable to coalesce entries in the SAMT into the RLMT in response to a write operation.

11. The data storage device as recited in claim 9, wherein the control circuitry is further operable to coalesce entries in the SAMT into the RLMT in response to a garbage collection operation.

12. The data storage device as recited in claim 1, wherein:

the non-volatile memory comprises a disk;

the disk comprises a plurality of tracks;

each track comprises a plurality of data sectors; and

each memory segment corresponds to one of the data sectors.

13. A method of operating a data storage device comprising a non-volatile memory comprising a plurality of memory segments, the method comprising:

receiving a write command comprising a logical block address (LBA);

determining a number of consecutive memory segments to access in response to the write command;

when the number of consecutive memory segments to access is greater than a threshold of more than one memory segment, creating a new run-length mapping entry in a run-length mapping table (RLMT); and

when the number of consecutive memory segments to access is not greater than the threshold, creating at least two new single address mapping entries in a single address mapping table (SAMT).

14. The method as recited in claim 13, wherein when the number of consecutive memory segments to access is greater than the threshold, further comprising:

performing the write command;

determining a number of entries in the SAMT that overlap with the new entry in the RLMT; and

deleting the overlapping entries from the SAMT.

15. The method as recited in claim 13, further comprising:

receiving a read command comprising a read LBA;

first determining whether the read LBA maps to an entry in the SAMT; and

when the read LBA does not map into the SAMT, using the RLMT to execute the read command.

16. The method as recited in claim 13, wherein:

the non-volatile memory comprises a semiconductor memory array;

the semiconductor memory array comprises a plurality of blocks;

each block comprises a plurality of pages; and

each memory segment corresponds to one of the pages.

17. The method as recited in claim 16, wherein each memory segment corresponds to a part of a page.

18. The method as recited in claim 16, further comprising processing the entries in the RLMT to implement page based mapping of the pages in the semiconductor memory array.

19. The method as recited in claim 16, wherein the single address mapping entry comprises a block number identifying a target block and a page offset within the target block.

20. The method as recited in claim 16, wherein the run-length mapping entry comprises a block number identifying a target block, a page offset within the target block, and a number of consecutive pages corresponding to the run-length.

21. The method as recited in claim 13, further comprising:

coalescing entries in the SAMT into the RLMT; and

deleting the coalesced entries from the SAMT.

22. The method as recited in claim 21, further comprising coalescing entries in the SAMT into the RLMT in response to a write operation.

23. The method as recited in claim 21, further comprising coalescing entries in the SAMT into the RLMT in response to a garbage collection operation.

24. The method as recited in claim 13, wherein:

the non-volatile memory comprises a disk;

the disk comprises a plurality of tracks;

each track comprises a plurality of data sectors; and

each memory segment corresponds to one of the data sectors.