Memory Mapping Restore and Garbage Collection Operations

• US 20090198947A1
• Filed: 08/18/2008
• Published: 08/06/2009
• Est. Priority Date: 02/04/2008
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Khmelnitsky, Vadim, Wakrat, Nir Jacob
• Granted Patent: US 8,397,014 B2
• Time in Patent Office: Days
• US Class Current: 711/202
• 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:

determining if a block table of contents (TOC) exists in a page of a block of non-volatile memory;

if the block TOC does not exist,

reading the entire block;

updating an index table in non-volatile memory, the index table for storing page addresses for mapping logical sectors of a read or write request to pages of the block;

writing the index table to non-volatile memory;

generating an index TOC in volatile memory using the index table;

if the block TOC exists,

updating the index table using the block TOC;

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 block of non-volatile memory.

4. The method of claim 1, further comprising:

updating a valid page count for the 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 the block is obtained from a sorted list of blocks.

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

7. A method comprising:

reading a block table of contents (TOC) from a page of a candidate block to obtain information describing the candidate block;

determining invalid pages in the candidate block using the information; and

updating a valid page count for the candidate block, where the valid page count is used to determine a best candidate block for a subsequent garbage collection (GC) operation.

8. The method of claim 7, further comprising:

reading valid page counts associated with a number of candidate blocks for the GC operation; and

determining a best candidate block for GC operation based on the valid page counts.

9. The method of claim 7, where the information includes logical sector numbers.

10. The method of claim 9, where determining invalid pages further comprises:

sorting the logical sector numbers; and

cross-referencing the sorted logical sector numbers with index table pages to determine invalid pages in the candidate block.

11. A system comprising:

non-volatile memory;

a controller coupled to the non-volatile memory and operable for determining if a block table of contents (TOC) exists in a page of a block of non-volatile memory;

if the block TOC does not exist,

reading the entire block;

updating an index table in non-volatile memory, the index table for storing page addresses for mapping logical sectors of a read or write request to pages of the block;

writing the index table to non-volatile memory;

generating an index TOC in volatile memory using the index table;

if the block TOC exists,

updating the index table using the block TOC;

writing the index table to non-volatile memory; and

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

12. The system of claim 11, further comprising:

releasing the index table in volatile memory.

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

14. The system of claim 11, further comprising:

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

15. The system of claim 11, where the block is obtained from a sorted list of blocks.

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

17. A system comprising:

non-volatile memory; and

a control coupled to the non-volatile memory and operable for reading a block table of contents (TOC) from a page of a candidate block to obtain information describing the candidate block;

determining invalid pages in the candidate block using the information; and

updating a valid page count for the candidate block, where the valid page count is used to determine a best candidate block for a subsequent garbage collection (GC) operation.

18. The system of claim 17, further comprising:

reading valid page counts associated with a number of candidate blocks for the GC operation; and

determining a best candidate block for GC operation based on the valid page counts.

19. The system of claim 17, where the information includes logical sector numbers.

20. The system of claim 19, where determining invalid pages further comprises:

sorting the logical sector numbers; and

cross-referencing the sorted logical sector numbers with index table pages to determine invalid pages in the candidate block.