Memory mapping restore and garbage collection operations

• US 8,397,014 B2
• Filed: 08/18/2008
• Issued: 03/12/2013
• Est. Priority Date: 02/04/2008
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Khmelnitsky, Vadim, Wakrat, Nir Jacob
• Primary Examiner(s): DOAN, DUC T
• Application Number:
  US12/193,613
• Publication Number:
  US 20090198947A1
• Time in Patent Office: 1,667 Days
• Field of Search: None
• US Class Current: 711/103
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 12/0868 Data transfer between cache memory and other subsystems, e.g. storage devices or host systems
• CPC Class Codes: G06F 2212/1016 Performance improvement
• CPC Class Codes: G06F 2212/1044 Space efficiency improvement
• CPC Class Codes: G06F 2212/466 Metadata, control data
• CPC Class Codes: G06F 2212/7201 Logical to physical mapping or translation of blocks or pages

Abstract

Memory mapping techniques for non-volatile memory are disclosed where logical sectors are mapped into physical pages using data structures in volatile and non-volatile memory. In some implementations, a first lookup table in non-volatile memory maps logical sectors directly into physical pages. A second lookup table in volatile memory holds the physical address of the first lookup table in non-volatile memory. In some implementations, a cache in volatile memory holds the physical addresses of the most recently written logical sectors. Also disclosed is a block TOC describing block content which can be used for garbage collection and restore operations.

Claims

1. A method comprising:

identifying blocks of non-volatile memory that are not free;

reconstructing at least a portion of an index table by performing the following for each of the identified blocks;

determining if a block table of contents (TOC) exists in a page of the identified block of non-volatile memory, wherein the block TOC includes information mapping logical sectors to pages in the identified block;

if the block TOC does not exist,

reading the entire block to identify logical sectors that correspond to the pages of the identified block;

updating the index table in volatile memory using information obtained from reading the entire block, the index table for storing page addresses for mapping logical sectors of a read or write request to pages of the identified block;

if the block TOC exists,

updating the index table using the information contained in the block TOC that maps logical sectors to the pages in the identified block;

after reconstructing the at least a portion of the index table;

writing the index table to non-volatile memory; and

generating an index TOC in volatile memory from the index table.

2. The method of claim 1, further comprising:

releasing the index table in volatile memory.

3. The method of claim 1, where the block TOC is stored in a last page of the identified block of non-volatile memory.

4. The method of claim 1, further comprising:

updating a valid page count for the identified block in volatile memory, where the valid page count is used to determine a best candidate block for garbage collection (GC) operations.

5. The method of claim 1, where identifying the blocks comprises generating a sorted list of the blocks that are not free, wherein each of the identified blocks are examined according to an order of the sorted list.

6. The method of claim 5, where the sorted list of blocks is sorted in increasing order based on block age.

7. A system comprising:

non-volatile memory;

a controller coupled to identify blocks of the non-volatile memory that are not free, and operable to reconstruct at least a portion of an index table by performing the following for each of the identified blocks;

determining if a block table of contents (TOC) exists in a page of the identified block of non-volatile memory, wherein the block TOC includes information mapping logical sectors to pages in the identified block;

if the block TOC does not exist,

reading the entire block to identify logical sectors that correspond to the pages of the identified block;

updating the index table in volatile memory using information obtained from reading the entire block, the index table for storing page addresses for mapping logical sectors of a read or write request to pages of the identified block;

if the block TOC exists,

updating the index table using the information contained in the block TOC that maps logical sectors to the pages in the identified block;

wherein the controller is further configured to perform the following after reconstructing the at least a portion of the index table;

writing the index table to non-volatile memory; and

generating an index TOC in volatile memory from the index table.

8. The system of claim 7, further comprising:

releasing the index table in volatile memory.

9. The system of claim 7, where the block TOC is stored in a last page of the identified block of non-volatile memory.

10. The system of claim 7, further comprising:

updating a valid page count for the identified block in volatile memory, where the valid page count is used to determine a best candidate block for garbage collection (GC) operations.

11. The system of claim 7, where identifying the blocks comprises generating a sorted list of the blocks that are not free, wherein each of the identified blocks are examined according to an order of the sorted list.

12. The system of claim 11, where the sorted list of blocks is sorted in increasing order based on block age.