METADATA REDUNDANCY SCHEMES FOR NON-VOLATILE MEMORIES

• US 20110072189A1
• Filed: 09/18/2009
• Published: 03/24/2011
• Est. Priority Date: 09/18/2009
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Khmelnitsky, Vadim, Post, Daniel J., Wakrat, Nir J.
• Granted Patent: US 9,063,886 B2
• Time in Patent Office: Days
• US Class Current: 711/103
• CPC Class Codes: G06F 11/1402 Saving, restoring, recovering or retrying
• CPC Class Codes: G06F 11/1666 where the redundant component is memory or memory area
• 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
• CPC Class Codes: G06F 2212/7207 management of metadata or control data

Abstract

Systems and methods are provided for storing data to or reading data from a non-volatile memory (“NVM”), such as flash memory, using a metadata redundancy scheme. In some embodiments, an electronic device, which includes an NVM, may also include a memory interface for controlling access to the NVM. The memory interface may receive requests to write user data to the NVM. The user data from each request may be associated with metadata, such as a logical address, flags, or other data. In response to a write request, the NVM interface may store the user data and its associated metadata in a first memory location (e.g., page), and may store a redundant copy of the metadata in a second memory location. This way, even if the first memory location becomes inaccessible, the memory interface can still recover the metadata from the backup copy stored in the second memory location.

Claims

1. A method of storing data in a non-volatile memory, the method comprising:

receiving a first write request to write first user data to a first logical address;

receiving a second write request to write second user data to a second logical address;

identifying a physical address at which to store the second user data; and

programming the first logical address, the second logical address, and the second user data in the non-volatile memory at the physical address.

2. The method of claim 1, wherein the physical address is a second physical address, and wherein the method further comprises:

determining a first physical address at which to store the first user data; and

programming at least the first logical address and the first user data in the non-volatile memory at the first physical address.

3. The method of claim 2 further comprising selecting the first logical address to program with the second user data based on a geometric relationship between the first and second physical addresses.

4. The method of claim 1 further comprising:

receiving a third write request to write third user data to a third logical address;

identifying an other physical address at which to store the third user data; and

programming the second logical address, the third logical address, and the third user data in the non-volatile memory at the other physical address.

5. The method of claim 1, wherein the non-volatile memory comprises flash memory, and wherein the physical address corresponds to a page of the flash memory.

6. The method of claim 1 further comprising:

saving the first logical address in a buffer responsive to receiving the first write request; and

reading the first logical address from the buffer for the programming.

7. The method of claim 1 further comprising:

receiving a third write request to write third user data to a third logical address, wherein the programming further comprises programming the third logical address at the physical address.

8. The method of claim 1 further comprising:

computing first metadata associated with the first user data; and

computing second metadata associated with the second user data, wherein the programming further comprises programming the first metadata and the second metadata at the physical address with the first logical address, the second logical address, and the second user data.

9. A memory interface for accessing a non-volatile memory, the memory interface comprising:

a bus controller for communicating with the non-volatile memory; and

control circuitry configured to direct the bus controller to store first user data and metadata in a first memory location of the non-volatile memory, wherein the metadata comprises;

first metadata associated with the first user data, and

second metadata associated with second user data stored at a second memory location of the non-volatile memory.

10. The memory interface of claim 9, wherein:

the first metadata comprises at least one of a first logical address, flags, and data associated with the first user data, and

the second metadata comprises a second logical address, flags, and data associated with the second user data.

11. The memory interface of claim 9, wherein the control circuitry is further configured to select the second metadata for storage in the first memory location based on a geometric relationship between the first and second memory locations.

12. The memory interface of claim 9, wherein the metadata further comprises third metadata associated with third user data stored at a third memory location of the non-volatile memory.

13. The memory interface of claim 9, wherein the non-volatile memory comprises a flash memory, wherein the first memory location comprises a first page of the flash memory, and wherein the second memory location comprises a second page of the flash memory.

14. The memory interface of claim 13, wherein the flash memory comprises a plurality of super blocks, wherein each of the super blocks comprises a sequence of blocks, wherein the first memory location and the second memory location are located in adjacent blocks of one of the super blocks, and wherein the first memory location and the second memory location correspond to pages having a same page number in their respective block.

15. The memory interface of claim 13, wherein the flash memory comprises a plurality of blocks, wherein each of the super blocks comprises a sequence of pages, and wherein the first memory location and the second memory location are located in adjacent pages of one block of the plurality of blocks.

16. An electronic device comprising:

a non-volatile memory; and

control circuitry operating under the control of a plurality of modules, the modules comprising;

a file system configured to issue a first write command to write first user data to the non-volatile memory; and

a memory interface configured to store first metadata at a plurality of memory locations of the non-volatile memory, wherein the first metadata is associated with the first user data.

17. The electronic device of claim 16, wherein the file system is further configured to request that the first user data be stored at a first logical address, and wherein the first metadata comprises the first logical address.

18. The electronic device of claim 16, wherein the memory interface is further configured to store the first user data with the first metadata at a first memory location of the plurality of memory locations.

19. The electronic device of claim 18, wherein:

the file system is further configured to issue a second write command to write second user data to the non-volatile memory; and

the memory interface is further configured to store second metadata and the second user data with the first metadata at a second memory location of the plurality of memory locations, wherein the second metadata is associated with the second user data.

20. The electronic device of claim 16, wherein the control circuitry is implemented on a system-on-a-chip.

21. A method of recovering a logical address from a non-volatile memory, the method comprising:

determining whether first data stored at a first memory location of the non-volatile memory is accessible, wherein the first data comprises first user data and a first logical address associated with the first user data;

in response to determining that the first data is inaccessible, reading second data from a second memory location of the non-volatile memory; and

extracting the first logical address from the second data.

22. The method of claim 21 further comprising, in response to determining that the first data is accessible, extracting the first logical address from the first data.

23. The method of claim 21, wherein the determining comprises:

reading the first data from the first memory location of the non-volatile memory;

applying error detection or correction to the first data; and

determining that the first data is inaccessible based on the applying.

24. The method of claim 21, wherein the determining comprises:

reading the first data from the first memory location of the non-volatile memory; and

determining whether the non-volatile memory returns a vector signaling a failed read operation responsive to the reading.

25. The method of claim 21 further comprising determining whether the second data stored at the second memory location is accessible, wherein the extracting is performed responsive to the determining that the second data is accessible.

26. The method of claim 25, wherein the second data comprises the first logical address, second user data, and a second logical address associated with the second user data.

27. A memory interface for accessing a non-volatile memory, the memory interface comprising:

a bus controller for communicating with the non-volatile memory; and

control circuitry configured to;

direct the bus controller to read from a first memory location to obtain first user data;

determine that the first user data is not accessible from the first memory location; and

direct the bus controller to read second data from a second memory location, wherein the second data comprises first metadata associated with the first user data.

28. The memory interface of claim 27, wherein the second data further comprises second user data and second metadata associated with the second user data.

29. The memory interface of claim 27, wherein the first metadata comprises at least one of a logical address, flags, and data associated with the first user data.