Efficient error handling mechanisms in data storage systems

Patent metadata

Field	Value
Publication number	US-9626118-B2
Application number	US-201514961856-A
Country	US
Kind code	B2
Filing date	Dec 7, 2015
Priority date	Jun 26, 2012
Publication date	Apr 18, 2017
Grant date	Apr 18, 2017

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 do increased and improved performance can be attained.

First claim

What is claimed is:

1. A non-volatile data storage system, comprising:
a non-volatile memory array comprising a plurality of physical locations configured to store user data and metadata; and
a controller configured to:
maintain a mapping associating a set of physical addresses corresponding to the plurality of physical locations in the non-volatile memory array with a set of logical addresses, the mapping indexed by the set of logical addresses;
process first user data stored at a first physical location of the plurality of physical locations;
determine in the mapping that a first logical address of the set of logical addresses read from metadata stored at the first physical location is not associated with a first physical address of the set of physical addresses corresponding to the first physical location;
generate a second logical address of the set of logical addresses by performing one or more error corrections of a plurality of error corrections on the first logical address read from the metadata stored at the first physical location, the second logical address determined in the mapping to be associated with the first physical address; and
update the mapping at the second logical address based on the processed first user data.

2. The non-volatile data storage system of claim 1 , wherein the controller is configured to perform the one or more error corrections of the plurality of error corrections on the first logical address in a predetermined order.

3. The non-volatile data storage system of claim 2 , wherein the predetermined order is based on an error likelihood.

4. The non-volatile data storage system of claim 2 , wherein the plurality of error corrections comprise a first set of error corrections flipping m-bits of the first logical address, where m is a natural number.

5. The non-volatile data storage system of claim 4 , wherein the plurality of error corrections further comprise a second set of error corrections flipping m+1 bits of the first logical address.

6. The non-volatile data storage system of claim 1 , wherein the controller is configured to process the first user data by moving the first user data to a second physical location of the plurality of physical locations, and
wherein the controller is configured to update the mapping to associate the second logical address with a second physical address corresponding to the second physical location.

7. The non-volatile data storage system of claim 1 , wherein the controller is configured to process the first user data by determining the first user data is unrecoverable from the first physical location, and
wherein the controller is configured to update the mapping to disassociate the second logical address from the first physical address.

8. A method comprising:
maintaining a mapping associating a set of physical addresses corresponding to a plurality of physical locations in a non-volatile memory array with a set of logical addresses, the mapping indexed by the set of logical addresses;
processing first user data stored at a first physical location of the plurality of physical locations;
determining in the mapping that a first logical address of the set of logical addresses read from metadata stored at the first physical location is not associated with a first physical address of the set of physical addresses corresponding to the first physical location;
generating a second logical address of the set of logical addresses by performing one or more error corrections of a plurality of error corrections on the first logical address read from the metadata stored at the first physical location, the second logical address determined in the mapping to be associated with the first physical address; and
updating the mapping at the second logical address based on the processed first user data.

9. The method of claim 8 , wherein the one or more error corrections of the plurality of error corrections on the first logical address are performed in a predetermined order.

10. The method of claim 9 , wherein the predetermined order is based on an error likelihood.

11. The method of claim 9 , wherein the plurality of error corrections comprise a first set of error corrections flipping m-bits of the first logical address, where m is a natural number.

12. The method of claim 11 , wherein the plurality of error corrections further comprise a second set of error corrections flipping m+1 bits of the first logical address.

13. The method of claim 8 , wherein processing the first user data comprises moving the first user data to a second physical location of the plurality of physical locations, and
wherein updating the mapping comprises updating the mapping to associate the second logical address with a second physical address corresponding to the second physical location.

14. The method of claim 8 , wherein processing the first user data comprises determining the first user data is unrecoverable from the first physical location, and
wherein updating the mapping comprises updating the mapping to disassociate the second logical address from the first physical address.

15. A controller for a non-volatile storage system, the controller configured to:
maintain a mapping associating a set of physical addresses corresponding to a plurality of physical locations in a non-volatile memory array with a set of logical addresses, the mapping indexed by the set of logical addresses;
process first user data stored at a first physical location of the plurality of physical locations;
determine in the mapping that a first logical address of the set of logical addresses read from metadata stored at the first physical location is not associated with a first physical address of the set of physical addresses corresponding to the first physical location;
generate a second logical address of the set of logical addresses by performing one or more error corrections of a plurality of error corrections on the first logical address read from the metadata stored at the first physical location, the second logical address determined in the mapping to be associated with the first physical address; and
update the mapping at the second logical address based on the processed first user data.

16. The controller of claim 15 , wherein the controller is further configured to perform the one or more error corrections of the plurality of error corrections on the first logical address in a predetermined order.

17. The controller of claim 16 , wherein the predetermined order is based on an error likelihood.

18. The controller of claim 16 , wherein the plurality of error corrections comprise a first set of error corrections flipping m-bits of the first logical address, where m is a natural number.

19. The controller of claim 18 , wherein the plurality of error corrections further comprise a second set of error corrections flipping m+1 bits of the first logical address.

20. The controller of claim 15 , wherein the controller is further configured to process the first user data by moving the first user data to a second physical location of the plurality of physical locations, and
wherein the controller is further configured to update the mapping to associate the second logical address with a second physical address corresponding to the second physical location.

21. The controller of claim 1 , wherein the controller is further configured to process the first user data by determining the first user data is unrecoverable from the first physical location, and
wherein the contro

Assignees

• Western Digital Tech Inc

Inventors

• Lam Johnny A

Classifications

• G06F12/0246 Primary

  in block erasable memory, e.g. flash memory · CPC title

• G06F12/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 title

• G06F3/0619 Primary

  in relation to data integrity, e.g. data losses, bit errors · CPC title

• G11C29/76

  using address translation or modifications · CPC title

• G06F8/441

  Register allocation; Assignment of physical memory space to logical memory space · CPC title