Granted Patent B2

US 9,639,461 · App. 13/839,128 · Granted May 2, 2017

Abstract

Claims (73)

1. A method comprising:

in a data storage device including a controller and a memory, performing:

receiving a request to write data to a location in the memory corresponding to a logical address;

generating a signature of the data;

searching a signature table in a controller memory of the controller to determine if the generated signature matches a particular signature in the signature table, wherein the particular signature is associated with a physical address of stored data; and

writing information to an entry in a logical mapping table responsive to determining that the generated signature matches the particular signature in the signature table, wherein the information points to a signature table entry, in the signature table, that includes the particular signature,

wherein the logical mapping table includes a logical address field and a mapping field, wherein the mapping field of the entry of the logical mapping table includes the information that points to the signature table entry, and wherein the mapping field of a second entry of the logical mapping table includes second information that points to a second physical address.

2. The method of claim 1 , wherein the stored data is stored in the memory, and further comprising:

generating a data structure that identifies at least one frequently modified logical address;

determining that the logical address comprises a frequently modified logical address; and

updating the data structure to identify the logical address as a frequently modified logical address.

3. The method of claim 1 , further comprising:

storing the logical mapping table in the controller memory that includes random access memory; and

incrementing a count value in a count field in the signature table entry based on the generated signature.

4. The method of claim 3 , wherein the signature table includes a second signature table entry corresponding to second stored data stored in the memory, the second signature table entry comprising a second signature of the second stored data and the second physical address of the second stored data, and further comprising:

receiving a second request to write the second stored data to a location in the memory, the location corresponding to the logical address;

determining that a generated second signature corresponding to the second stored data matches the second signature; and

writing third information to the entry in the logical mapping table to point to the second signature table entry.

5. The method of claim 4 , further comprising:

in response to writing the third information to the entry of the logical mapping table:

incrementing a second count value in a second count field in the second signature table entry; and

decrementing the count value in the signature table entry.

6. The method of claim 3 , wherein, when the entry in the logical mapping table is associated with the logical address, the signature table entry is maintained in the signature table and the stored data is maintained in the memory independent of the count value.

7. The method of claim 1 , further comprising:

in response to determining that the generated signature matches the particular signature:

reading the stored data from the memory based on the physical address retrieved from the signature table entry; and

comparing the read data to the data corresponding to the request; and

in response to the read data not matching the data:

writing the data to a particular location in the memory; and

writing to the entry in the logical mapping table to indicate the particular location in the memory.

8. The method of claim 1 , wherein, when the signature table entry has a count value of zero, no entries of the logical mapping table are linked to the signature table entry.

9. The method of claim 1 , further comprising, in response to determining that the generated signature is not in the signature table, determining whether to update the signature table to include a new entry, wherein determining whether to update the signature table to include the new entry is based on at least one of available space in the signature table and a priority of the data.

10. The method of claim 1 , further comprising:

in response to determining that the generated signature is not in the signature table, determining whether to update the signature table to include a new entry; and

in response to determining to update the signature table to include the new entry:

writing the generated signature into the new entry in the signature table;

setting a count field of the new entry to one;

writing the data to a particular location in the memory; and

writing the physical address of the particular location to a physical address field of the new entry.

11. The method of claim 1 , further comprising:

in response to determining that the generated signature is not in the signature table, determining whether to update the signature table to include a new entry; and

in response to determining to not update the signature table to include the new entry:

writing the data to a particular location in the memory; and

writing the entry to the logical mapping table to indicate the particular location in the memory.

12. A data storage device comprising:

a controller including a signature table and a logical mapping table; and

a non-volatile memory coupled to the controller,

wherein the signature table includes a signature table entry that contains a signature field and a physical address field, wherein the signature field is configured to store a signature that corresponds to a data element stored in the non-volatile memory, and wherein the physical address field is configured to store a physical address of the data element, and

wherein the controller is configured to:

receive a request to write data to the non-volatile memory, the request including a logical address;

generate a signature of the data;

determine that the generated signature matches a particular signature in the signature field of the signature table entry;

read the stored data element from the memory based on the physical address retrieved from the signature table entry; and

responsive to the read data element matching the data, write mapping information to an entry in the logical mapping table corresponding to the logical address, wherein the mapping information points to the signature table entry,

wherein the logical mapping table includes a logical address field and a mapping field, wherein the mapping field of the entry of the logical mapping table includes the mapping information that points to the signature table entry, and wherein the mapping field of a second entry of the logical mapping table includes second mapping information that points to a second physical address.

13. The data storage device of claim 12 , wherein the signature table entry further includes a count field, and wherein a count value of the count field corresponds to a number of logical addresses of the logical mapping table that are linked to the signature table entry.

14. The data storage device of claim 12 , wherein the signature table is stored in a controller memory, and wherein the controller memory comprises a random access memory (RAM).

15. The data storage device of claim 12 , wherein the controller further includes a memory management engine, a signature searching engine, and a signature generator, and wherein the logical address is identified as a frequently modified address in response to a first data value corresponding to the logical address being repeatedly written to the memory during a period of time.

16. The data storage device of claim 15 , wherein the first data value is a logical one value, the logical one value corresponding to the signature table entry, and wherein a second data value is a logical zero value, the logical zero value corresponding to a second signature table entry included in the signature table.

17. The data storage device of claim 12 , wherein the mapping field is linkable to the signature table entry.

18. The data storage device of claim 12 , wherein the controller is configured to maintain signature table entries corresponding to data elements that have been mapped to the logical address in response to the logical address being identified as a frequently modified address.

19. The data storage device of claim 12 , wherein the signature table includes a first set of multiple entries and the logical mapping table includes a second set of multiple entries.

20. The data storage device of claim 12 , wherein more than one entry in the logical mapping table is mapped to a single entry in the signature table, and wherein the data is received from a host processor.

21. The data storage device of claim 12 , wherein the controller is configured, during a write operation, to read the signature prior to storing second data to the non-volatile memory, wherein the non-volatile memory comprises a flash memory, and wherein the controller includes a data structure of frequently modified logical addresses.

22. The data storage device of claim 12 , wherein the data structure of frequently modified logical addresses comprises a list of one or more frequently written to logical addresses.

23. An apparatus comprising:

means for storing a signature table, wherein the signature table includes a signature table entry that contains a signature field and a physical address field, wherein the signature field is configured to store a signature that corresponds to a data element stored in a non-volatile memory, and wherein the physical address field is configured to store a physical address of the data element;

means for receiving a request to write data to the non-volatile memory, the request including a logical address;

means for determining that a generated signature of the data matches a particular signature in the signature field of the signature table entry;

means for reading the stored data from the memory based on the physical address retrieved from the signature table entry; and

means for writing mapping information to an entry in a logical mapping table corresponding to the logical address responsive to the read data matching the data, wherein the mapping information points to the signature table entry,

wherein the logical mapping table includes a logical address field and a mapping field, wherein the mapping field of a first entry of the logical mapping table includes the mapping information that points to the signature table entry, and wherein the mapping field of a second entry of the logical mapping table includes mapping information that points to a second physical address.

24. The apparatus of claim 23 , further comprising means for determining that the read data matches the data.

Assignments (12)