Restore index page

• US 8,468,293 B2
• Filed: 07/24/2009
• Issued: 06/18/2013
• Est. Priority Date: 07/24/2009
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Wakrat, Nir Jacob, Khmelnitsky, Vadim
• Primary Examiner(s): Elmore, Reba I
• Application Number:
  US12/509,071
• Publication Number:
  US 20110022780A1
• Time in Patent Office: 1,425 Days
• Field of Search: 711/103, 711/154, 711/207
• US Class Current: 711/103
• 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

Abstract

Techniques for restoring index pages stored in non-volatile memory are disclosed where the index pages map logical sectors into physical pages. Additional data structures in volatile and non-volatile memory can be used by the techniques for restoring index pages. In some implementations, a lookup table associated with data blocks in non-volatile memory can be used to provide information regarding the mapping of logical sectors into physical pages. In some implementations, a lookup table associated with data blocks and a range of logical sectors and/or index pages can be used.

Claims

1. A method comprising:

receiving a request to restore at least a portion of an index that maps logical sectors to physical pages of memory in a flash memory device;

reading first metadata associated with a block of memory in the device, wherein the first metadata maps physical pages of the block to logical sectors;

identifying that a page of the block mapped by the first metadata corresponds to the requested portion of the index; and

writing an entry corresponding to the identified page to the requested portion of the index.

2. The method of claim 1, further comprising:

identifying the block of memory from a plurality of blocks of memory based upon how recently each of the plurality of blocks of memory was accessed, wherein the identified block of memory was accessed most recently.

3. The method of claim 1, further comprising:

identifying the block of memory from a plurality of blocks of memory based upon second metadata that provides a range for each of the plurality of blocks, wherein a range for the identified block of memory corresponds to the requested portion of the index.

4. The method of claim 3, wherein the range provided by the second metadata comprises, for each of the plurality of blocks, a range of logical sectors stored by a block of memory.

5. The method of claim 3, wherein the range provided by the second metadata comprises, for each of the plurality of blocks, a range of index pages that correspond to a block of memory.

6. The method of claim 3, wherein the second metadata is store stored in volatile memory.

7. The method of claim 1, further comprising:

scheduling a remaining part of the requested portion of the index to be restored when the flash memory device is idle.

8. The method of claim 1, further comprising:

reading, repeatedly, the first metadata, identifying a logical sector, and writing the identified page until the requested portion of the index has been restored.

9. The method of claim 1, further comprising:

determining that memory associated with the entry written to the requested portion of the index has been deleted by cross-referencing the entry with a file system that stores information regarding deleted memory; and

rewriting the entry to the requested portion of the index to indicate the memory associated with the entry has been deleted.

10. The method of claim 1, further comprising:

allocating a new block of memory; and

transferring data from a block of memory associated with the index to the allocated new block of memory.

11. A method comprising:

receiving a request to restore at least a portion of a first index page that maps logical sectors to physical pages of memory in a flash memory device, wherein the first index page is part of a super block that associates the first index page with a second index page and a metadata page;

determining data for the requested portion of the index by combining at least a portion of the second index page and at least a portion the metadata page; and

writing the determined data to the requested portion of the index.

12. The method of claim 11, wherein the first index, the second index, and the metadata are stored on physically different dies of the flash memory device.

13. The method of claim 11, wherein the portion of the second index page and the portion of the metadata page are combined using an exclusive-or (XOR) operation to determine the data for restoring the requested portion of the index.

14. The method of claim 11, wherein the metadata comprises parity information that was previously generated by combining the first index page with the second index page using an XOR operation.

15. A system comprising:

a non-volatile memory;

a controller coupled to the non-volatile memory and configured to;

receive a request to restore at least a portion of an index that maps logical sectors to physical pages of the non-volatile memory;

read first metadata associated with a block of the non-volatile memory, wherein the first metadata is stored in non-volatile memory and maps logical physical pages of the block to logical sectors;

identify that a page of the block mapped by the first metadata corresponds to the requested portion of the index; and

write an entry corresponding to the identified page to the requested portion of the index.

16. The system of claim 15, wherein the controller is further configured to:

identify the block of memory from a plurality of blocks of memory based upon how recently each of the plurality of blocks of memory was accessed, wherein the identified block of memory accessed was most recently.

17. The system of claim 15, wherein the controller is further configured to

identify the block of memory from a plurality of blocks of memory based upon second metadata that provides a range for each of the plurality of blocks, wherein a range for the identified block of memory corresponds to the requested portion of the index.

18. The system of claim 17, wherein the range provided by the second metadata comprises, for each of the plurality of blocks, a range of logical sectors stored by a block of memory.

19. The system of claim 17, wherein the range provided by the second metadata comprises, for each of the plurality of blocks, a range of index pages that correspond to a block of memory.

20. The system of claim 17, further comprising

volatile memory that stores the second metadata.

21. A memory controller for a system including a non-volatile memory, the memory controller comprising:

a host interface; and

a control unit coupled to the host interface, wherein the control unit is configured to;

receive a request from a host through the host interface to restore at least a portion of an index that maps logical sectors to physical pages of the non-volatile memory;

read first metadata associated with a block of the non-volatile memory, wherein the first metadata is stored in non-volatile memory and maps logical physical pages of the block to logical sectors;

identify that a page of the block mapped by the first metadata corresponds to the requested portion of the index; and

write an entry corresponding to the identified page to the requested portion of the index.

22. The system of claim 21, wherein the volatile memory is configured to store an index table cache, an index table of contents (TOC), and a block table.

23. The system of claim 22, wherein the processor is further configured to create a memory map dependent upon physical address information stored in the index table cache.