Data Integrity Enhancement to Protect Against Returning Old Versions of Data

• US 20160147651A1
• Filed: 02/24/2015
• Published: 05/26/2016
• Est. Priority Date: 11/21/2014
• Status: Active Grant

• Current Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Original Assignee: SanDisk Enterprise IP LLC (Western Digital Corporation)
• Inventors: Desai, Girish B., Guthrie, William L.
• Granted Patent: US 9,817,752 B2
• Time in Patent Office: Days
• CPC Class Codes: G06F 11/1004 to protect a block of data words, e.g. CRC or checksum G06F11/1076 takes precedence; security arrangements for protecting computers or computer systems against unauthorized activity G06F21/00
• CPC Class Codes: G06F 11/34 Recording or statistical evaluation of computer activity, e.g. of down time, of input/output operation ; Recording or statistical evaluation of user activity, e.g. usability assessment
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 12/1009 using page tables, e.g. page table structures
• CPC Class Codes: G06F 2212/1008 Correctness of operation, e.g. memory ordering
• CPC Class Codes: G06F 2212/1032 Reliability improvement, data loss prevention, degraded operation etc
• CPC Class Codes: G06F 2212/7201 Logical to physical mapping or translation of blocks or pages
• CPC Class Codes: G06F 2212/7205 Cleaning, compaction, garbage collection, erase control
• CPC Class Codes: G06F 2212/7209 Validity control, e.g. using flags, time stamps or sequence numbers

Abstract

Systems, methods and/or devices are used to enhance data integrity to protect against returning old versions of data. In one aspect, a method includes (1) receiving a write request from a host that specifies write data for a set of logical block addresses, (2) mapping, using a mapping table, the set of logical block addresses to a set of physical addresses, where the mapping table includes a plurality of subsets, and (3) performing operations for each subset of the mapping table that includes at least one entry corresponding to a logical block specified by the set of logical block addresses, including: (a) generating metadata for the subset, the metadata including a version number for the subset, (b) calculating a Cyclic Redundancy Check (CRC) checksum for the subset, and (c) storing the version number for the subset and the CRC checksum for the subset in a version data structure.

Claims

1. A method of enhancing data integrity, the method comprising:

receiving, at a storage device, a write request from a host, wherein the write request specifies write data for a first set of one or more logical block addresses in a logical address space of the host;

mapping, using a mapping table, the first set of one or more logical block addresses associated with the write request to a first set of one or more physical addresses of the storage device, wherein the mapping table includes a plurality of subsets, each subset having entries corresponding to a group of contiguous logical blocks in the logical address space of the host; and

performing one or more operations for each subset of the mapping table that includes at least one entry corresponding to a logical block specified by the first set of one or more logical block addresses, including;

generating metadata for the subset, the metadata including a version number for the subset;

calculating a first Cyclic Redundancy Check (CRC) checksum for the subset; and

storing the version number for the subset and the first CRC checksum for the subset in a version data structure.

2. The method of claim 1, wherein performing one or more operations for each subset of the mapping table that includes at least one entry corresponding to a logical block specified by the first set of one or more logical block addresses further comprises:

in accordance with a determination that at least one entry of the subset is modified;

obtaining an updated version number for the subset;

calculating an updated CRC checksum for the subset; and

storing the updated version number for the subset and the updated CRC checksum for the subset in the version data structure.

3. The method of claim 2, wherein obtaining an updated version number for the subset comprises:

reading the version number for the subset from the version data structure; and

incrementing the version number for the subset.

4. The method of claim 1, further comprising:

receiving, at the storage device, a read request from the host, wherein the read request specifies a second set of one or more logical block addresses in the logical address space of the host from which to read;

mapping, using the mapping table, the second set of one or more logical block addresses associated with the read request to a second set of one or more physical addresses corresponding to one or more physical pages of the storage device; and

performing one or more operations for each subset of the mapping table that includes at least one entry corresponding to a logical block specified by the second set of one or more logical block addresses, including;

reading the first CRC checksum for the subset from the version data structure;

calculating a second CRC checksum for the subset;

comparing the second CRC checksum for the subset with the first CRC checksum for the subset; and

in accordance with a determination that the second CRC checksum is not equivalent to the first CRC checksum, initiating one or more recovery actions; and

in accordance with a determination that, for all the subsets that include at least one entry corresponding to a logical block specified by the second set of one or more logical block addresses, the second CRC checksum is equivalent to the first CRC checksum, returning data from the second set of one or more logical block addresses to the host.

5. The method of claim 1, wherein the mapping table is stored independently from the version data structure.

6. The method of claim 1, wherein the storage device comprises one or more flash memory devices.

7. A storage device, comprising:

a storage medium;

memory distinct from the storage medium, the memory storing a mapping table, the mapping table including information for mapping logical addresses in a logic address space of a host to physical addresses in a physical address space of the storage system; and

a storage controller having one or more processors configured to execute instructions in one or more programs, wherein the storage controller is configured to perform operations comprising;

receiving, at the storage device, a write request from a host, wherein the write request specifies write data for a first set of one or more logical block addresses in a logical address space of the host;

mapping, using the mapping table, the first set of one or more logical block addresses associated with the write request to a first set of one or more physical addresses of the storage device, wherein the mapping table includes a plurality of subsets, each subset having entries corresponding to a group of contiguous logical blocks in the logical address space of the host; and

performing one or more operations for each subset of the mapping table that includes at least one entry corresponding to a logical block specified by the first set of one or more logical block addresses, including;

generating metadata for the subset, the metadata including a version number for the subset;

calculating a first Cyclic Redundancy Check (CRC) checksum for the subset; and

storing the version number for the subset and the first CRC checksum for the subset in a version data structure.

8. The storage device of claim 7, wherein the storage controller includes a version module and a CRC module for generating the version number for the subset and the first CRC checksum for the subset, and for storing the version number for the subset and the first CRC checksum for the subset in the version data structure.

9. The storage device of claim 7, wherein performing one or more operations for each subset of the mapping table that includes at least one entry corresponding to a logical block specified by the first set of one or more logical block addresses further comprises:

in accordance with a determination that at least one entry of the subset is modified;

obtaining an updated version number for the subset;

calculating an updated CRC checksum for the subset; and

storing the updated version number for the subset and the updated CRC checksum for the subset in the version data structure.

10. The storage device of claim 9, wherein obtaining an updated version number for the subset comprises:

reading the version number for the subset from the version data structure; and

incrementing the version number for the subset.

11. The storage device of claim 7, wherein the storage controller is further configured to perform operations comprising:

receiving, at the storage device, a read request from the host, wherein the read request specifies a second set of one or more logical block addresses in the logical address space of the host from which to read;

mapping, using the mapping table, the second set of one or more logical block addresses associated with the read request to a second set of one or more physical addresses corresponding to one or more physical pages of the storage device; and

performing one or more operations for each subset of the mapping table that includes at least one entry corresponding to a logical block specified by the second set of one or more logical block addresses, including;

reading the first CRC checksum for the subset from the version data structure;

calculating a second CRC checksum for the subset;

comparing the second CRC checksum for the subset with the first CRC checksum for the subset; and

in accordance with a determination that the second CRC checksum is not equivalent to the first CRC checksum, initiating one or more recovery actions; and

in accordance with a determination that, for all the subsets that include at least one entry corresponding to a logical block specified by the second set of one or more logical block addresses, the second CRC checksum is equivalent to the first CRC checksum, return data from the second set of one or more logical block addresses to the host.

12. The storage device of claim 7, wherein the mapping table is stored independently from the version data structure.

13. The storage device of claim 7, wherein the storage device comprises one or more flash memory devices.

14. A non-transitory computer-readable storage medium, storing one or more programs configured for execution by one or more processors of a storage device, the one or more programs including instructions for:

receiving, at the storage device, a write request from a host, wherein the write request specifies write data for a first set of one or more logical block addresses in a logical address space of the host;

mapping, using a mapping table, the first set of one or more logical block addresses associated with the write request to a first set of one or more physical addresses of the storage device, wherein the mapping table includes a plurality of subsets, each subset having entries corresponding to a group of contiguous logical blocks in the logical address space of the host; and

performing one or more operations for each subset of the mapping table that includes at least one entry corresponding to a logical block specified by the first set of one or more logical block addresses, including;

generating metadata for the subset, the metadata including a version number for the subset;

calculating a first Cyclic Redundancy Check (CRC) checksum for the subset; and

storing the version number for the subset and the first CRC checksum for the subset in a version data structure.

15. The storage medium of claim 14, wherein performing one or more operations for each subset of the mapping table that includes at least one entry corresponding to a logical block specified by the first set of one or more logical block addresses further comprises:

in accordance with a determination that at least one entry of the subset is modified;

obtaining an updated version number for the subset;

calculating an updated CRC checksum for the subset; and

storing the updated version number for the subset and the updated CRC checksum for the subset in the version data structure.

16. The storage medium of claim 15, wherein obtaining an updated version number for the subset comprises:

reading the version number for the subset from the version data structure; and

incrementing the version number for the subset.

17. The storage medium of claim 14, the one or more programs further comprising instructions for:

receiving, at the storage device, a read request from the host, wherein the read request specifies a second set of one or more logical block addresses in the logical address space of the host from which to read;

mapping, using the mapping table, the second set of one or more logical block addresses associated with the read request to a second set of one or more physical addresses corresponding to one or more physical pages of the storage device; and

performing one or more operations for each subset of the mapping table that includes at least one entry corresponding to a logical block specified by the second set of one or more logical block addresses, including;

reading the first CRC checksum for the subset from the version data structure;

calculating a second CRC checksum for the subset;

comparing the second CRC checksum for the subset with the first CRC checksum for the subset; and

in accordance with a determination that the second CRC checksum is not equivalent to the first CRC checksum, initiating one or more recovery actions; and

in accordance with a determination that, for all the subsets that include at least one entry corresponding to a logical block specified by the second set of one or more logical block addresses, the second CRC checksum is equivalent to the first CRC checksum, returning data from the second set of one or more logical block addresses to the host.

18. The storage medium of claim 14, wherein the mapping table is stored independently from the version data structure.

19. The storage medium of claim 14, wherein the storage device comprises one or more flash memory devices.