Efficient error handling mechanisms in data storage systems

• US 9,208,020 B2
• Filed: 12/23/2014
• Issued: 12/08/2015
• Est. Priority Date: 06/26/2012
• Status: Active Grant

• Current Assignee: JP Morgan Chase Bank, N.A. (JP Morgan Chase & Co)
• Original Assignee: Western Digital Technologies Incorporated (Western Digital Corporation)
• Inventors: Lam, Johnny A.
• Primary Examiner(s): Tabone, Jr., John J
• Application Number:
  US14/581,846
• Publication Number:
  US 20150121165A1
• Time in Patent Office: 350 Days
• Field of Search: 714/799, 714/773, 714/763, 714/768, 714/702, 714/718, 714/723, 714/742, 714/6.24, 714/48, 711/202, 711/206, 711/103, 707/813, 707/824, 702/59, 702/117, 702/118
• US Class Current: 1/1
• CPC Class Codes: G06F 11/0703 Error or fault processing not based on redundancy, i.e. by taking additional measures to deal with the error or fault not making use of redundancy in operation, in hardware, or in data representation
• 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/1016 Error in accessing a memory location, i.e. addressing error
• CPC Class Codes: G06F 11/1068 in sector programmable memories, e.g. flash disk G06F11/1072 takes precedence
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 12/0292 using tables or multilevel address translation means G06F12/023 takes precedence; address translation in virtual memory systems G06F12/10
• CPC Class Codes: G06F 12/06 Addressing a physical block of locations, e.g. base addressing, module addressing, memory dedication G06F12/08 takes precedence
• CPC Class Codes: G06F 12/0802 Addressing of a memory level in which the access to the desired data or data block requires associative addressing means, e.g. caches
• CPC Class Codes: G06F 12/0873 Mapping of cache memory to specific storage devices or parts thereof
• CPC Class Codes: G06F 12/10 Address translation
• CPC Class Codes: G06F 12/1027 using associative or pseudo-associative address translation means, e.g. translation look-aside buffer [TLB]
• CPC Class Codes: G06F 12/1054 the data cache being concurrently physically addressed
• CPC Class Codes: G06F 13/404 with address mapping
• CPC Class Codes: G06F 2212/1016 Performance improvement
• 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/7207 management of metadata or control data
• CPC Class Codes: G06F 2212/7211 Wear leveling
• CPC Class Codes: G06F 3/061 Improving I/O performance
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/0644 : Management of space entities, e.g. partitions, extents, pools
• CPC Class Codes: G06F 3/0655 : Vertical data movement, i.e. input-output transfer; data movement between one or more hosts and one or more storage devices
• CPC Class Codes: G06F 3/0685 : Hybrid storage combining heterogeneous device types, e.g. hierarchical storage, hybrid arrays
• CPC Class Codes: G06F 3/0688 : Non-volatile semiconductor memory arrays
• CPC Class Codes: G06F 8/441 : Register allocation; Assignment of physical memory space to logical memory space
• CPC Class Codes: G11C 11/5628 : Programming or writing circuits; Data input circuits
• CPC Class Codes: G11C 2029/4402 : Internal storage of test result, quality data, chip identification, repair information
• CPC Class Codes: G11C 29/00 : Checking stores for correct operation ; Subsequent repair; Testing stores during standby or offline operation
• CPC Class Codes: G11C 29/52 : Protection of memory contents; Detection of errors in memory contents
• CPC Class Codes: G11C 29/76 : using address translation or modifications
• CPC Class Codes: G11C 8/06 : Address interface arrangements, e.g. address buffers

Abstract

A data storage system configured to efficiently search and update system data is disclosed. In one embodiment, the data storage system can attempt to correct errors in retrieved data configured to index system data. Metadata stored along with user data in a memory location can be configured to indicate a logical address associated in a logical-to-physical location mapping with a physical address at which user data and metadata are stored. The data storage system can generate modified versions of logical address indicated by the metadata and determine whether such modified versions match the physical address in the logical-to-physical mapping. Modified versions of the logical address can be generated by flipping one or more bits in the logical address indicated by the metadata. Efficiency can be increased and improved performance can be attained.

Claims

1. A non-volatile data storage system, comprising:

a non-volatile memory array comprising a plurality of physical addresses; and

a controller configured to;

maintain a mapping associating a set of physical addresses of the plurality of physical addresses in the non-volatile memory array with a set of logical addresses,

the set of physical addresses including at least a first physical address and a second physical address different from each other, the first physical address storing at least a first user data and a first metadata,

the set of logical addresses including at least a first logical address and a second logical address different from each other,

the mapping indexed by the set of logical addresses; and

when the logical address indicated in the first metadata is not associated with the first physical address, attempt to locate the second logical address corresponding to the first physical address in the mapping based on flipping one or more bits in data read from the first metadata.

2. The non-volatile data storage system of claim 1, wherein, when an m-bit flipped version of the first metadata does not result in locating the second logical address, the controller is further configured to locate the second logical address based on an (m+1)-bit flipped version of the first metadata, where m is a natural number.

3. The non-volatile data storage system of claim 1, wherein, when an m-bit flipped version of the first metadata does not result in locating the second logical address, the controller is further configured to locate the second logical address based on any number of bits of flipped versions of the first metadata in any order, where m is a natural number greater than 1.

4. The non-volatile data storage system of claim 1, wherein the controller is further configured to attempt to locate the second logical address based on flipping two or more bits of data read from the first metadata.

5. The non-volatile data storage system of claim 4, wherein the controller is further configured to selectively use the bit-flipped versions of the first metadata in attempting to locate the second logical address.

6. The non-volatile data storage system of claim 1, wherein the controller is further configured to attempt to locate the second logical address in response to determining that the user data stored at the first physical address is unrecoverable.

7. A non-volatile data storage system, comprising:

a non-volatile memory array comprising a plurality of physical addresses; and

a controller configured to;

maintain a mapping associating a set of physical addresses of the plurality of physical addresses in the non-volatile memory array with a set of logical addresses,

the set of physical addresses including at least a first physical address and a second physical address different from each other, the first physical address storing at least a first user data and a first metadata,

the set of logical addresses including at least a first logical address and a second logical address different from each other, the mapping indexed by the set of logical addresses; and

when the logical address indicated in the first metadata is not associated with the first physical address, modify at least part of data read from the first metadata and attempt to locate the second logical address corresponding to the first physical address in the mapping based on the modified data.

8. The non-volatile data storage system of claim 7, wherein the controller is further configured to generate the modified data based at least in part on an order based on a likelihood of the type of error(s) in the first metadata.

9. The non-volatile data storage system of claim 8, wherein the controller is further configured to attempt to correct more likely errors prior to attempting to correct less likely errors.

10. A controller for a non-volatile data storage system, the controller being configured to:

maintain a mapping associating a set of a plurality of physical addresses stored in a non-volatile memory array with a set of logical addresses,

the set of physical addresses including at least a first physical address and a second physical address different from each other, the first physical address storing at least a first user data and a first metadata,

the set of logical addresses including at least a first logical address and a second logical address different from each other, the mapping indexed by the set of logical addresses; and

when the logical address indicated in the first

metadata is not associated with the first physical address, attempt to locate the second logical address corresponding to the first physical address in the mapping based on flipping one or more bits in data read from the first metadata.

11. The controller of claim 10, wherein, when an m-bit flipped version of the first metadata does not result in locating the second logical address, the controller is further configured to locate the second logical address based on an (m+1)-bit flipped version of the first metadata, where m is a natural number.

12. The controller of claim 10, wherein, when an m-bit flipped version of the first metadata does not result in locating the second logical address, the controller is further configured to locate the second logical address based on any number of bits of flipped versions of the first metadata in any order, where m is a natural number greater than 1.

13. The controller of claim 10, wherein the controller is further configured to attempt to locate the second logical address based on flipping two or more bits of data read from the first metadata, and wherein the controller is further configured to selectively use the bit-flipped versions of the first metadata in attempting to locate the second logical address.

14. The controller of claim 10, wherein the controller is further configured to attempt to locate the second logical address in response to determining that the user data stored at the first physical address is unrecoverable.

15. In a non-volatile data storage system comprising a controller and a non-volatile memory array comprising a plurality of physical addresses, a method of relocating data, the method comprising:

maintaining a mapping associating a set of physical addresses of the plurality of physical addresses in the non-volatile memory array with a set of logical addresses, the set of physical addresses including at least a first physical address and a second physical address different from each other, the first physical address storing at least a first user data and a first metadata, the set of logical addresses including at least a first logical address and a second logical address different from each other, the mapping indexed by the set of logical addresses; and

when the logical address indicated in the first metadata is not associated with the first physical address, attempting to locate the second logical address corresponding to the first physical address in the mapping based on flipping one or more bits in data read from the first metadata,

wherein the method is performed under the control of the controller.

16. The method of claim 15, wherein the attempting comprises generating the modified data based at least in part on flipping one or more bits in the data read from the first metadata.

17. The method of claim 15, wherein the attempting comprises generating the modified data based at least in part on an order based on a likelihood of the type of error(s) in the first metadata.