MEMORY MAPPING TECHNIQUES

• US 20090198902A1
• 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,417,893 B2
• Time in Patent Office: Days
• US Class Current: 711/135
• 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:

obtaining a read request associated with one or more logical sectors corresponding to a first page address of non-volatile memory;

determining if the first page address is contained in an index table cache in volatile memory;

if the first page address is contained in the index table cache;

reading the first page address from the index table cache;

performing the read operation using the first page address;

if the first page address is not contained in the index table cache,

obtaining from an index table of contents (TOC) in the volatile memory, a second page address of an index table entry in non-volatile memory storing the first page address;

reading the first page address from the index table entry; and

performing the read operation using the first page address.

2. The method of claim 1, further comprising:

storing the first page address in the index table cache in volatile memory.

3. The method of claim 1, further comprising:

dynamically configuring the volatile memory based on memory availability, one or more trigger events or one or more operational modes.

4. A method comprising:

obtaining a write request associated with one or more logical sectors;

determining if a current data block is full;

if a current data block is full,

writing a block table of contents (TOC) to a page of the current data block;

if the current data block is not full,

writing one or more pages into the current data block;

updating current block TOC; and

updating a valid page count for the current data block.

5. The method of claim 4, if the current data block is full, further comprising:

determining if a free block is available;

if a free block is available,

allocating the free block as the current data block; and

if a free block is not available,

performing a garbage collection operation to generate a free block.

6. The method of claim 4, if the current data block is not full, further comprising:

determining if an index table cache contains an index page associated with a written logical sector; and

if the index table cache contains an index page associated with a written logical sector,

updating the valid page count.

7. The method of claim 6, if the index table cache does not contain an index page associated with a written logical sector, further comprising:

determining if there is free space in the index table cache; and

if there is free space in the index table cache,

reading an index page using a location stored in the index table cache; and

if there is no free space in the index table cache,

flushing older pages from the index table cache.

8. The method of claim 4, where the block TOC is written to a last page of the current data block.

9. A memory system, comprising:

volatile memory storing an index table cache and an index table of contents;

non-volatile memory storing an index table storing page addresses corresponding to logical sectors;

a controller coupled to the volatile memory and non-volatile memory and operable for;

obtaining a read request associated with a logical sector;

determining if a first page address associated with the logical sector is stored in the index table cache;

if the first page address is stored in the index table cache,

reading the first page address from the index table cache; and

performing the read operation using the first page address.

if the first page address is not cached in the index table cache, the controller is operable for;

obtaining from an index table of contents in the volatile memory, a second page address of an index table entry in non-volatile memory storing the first page address;

reading the first page address from the index table entry; and

storing the first page address in the index table cache.

10. The memory system of claim 9, wherein the controller is operable to store the first page address in the index table cache in volatile memory.

11. The memory system of claim 9, wherein the controller is operable to:

dynamically configure the volatile memory based on memory availability, one or more trigger events or one or more operational modes.

12. A memory system, comprising:

volatile memory storing an index table cache and an index table of contents;

non-volatile memory storing an index table with entries storing page addresses corresponding to logical sectors;

a controller coupled to the volatile memory and non-volatile memory and operable for;

obtaining a write request associated with one or more logical sectors;

determining if a current data block is full;

if a current data block is full,

writing a block table of contents (TOC) to a page of the current data block;

if the current data block is not full,

writing one or more pages into the current data block;

updating current block TOC; and

updating a valid page count for the current data block.

13. The memory system of claim 12, if the current data block is full, further comprising:

determining if a free block is available;

if a free block is available,

allocating the free block as the current data block; and

if a free block is not available,

performing a garbage collection operation to generate a free block.

14. The memory system of claim 12, if the current data block is not full, further comprising:

determining if an index table cache contains an index page associated with a written logical sector; and

if the index table cache contains an index page associated with a written logical sector,

updating the valid page count.

15. The memory system of claim 14, if the index table cache does not contain an index page associated with a written logical sector, further comprising:

determining if there is free space in the index table cache; and

if there is free space in the index table cache,

reading an index page using a location stored in the index table cache; and

if there is no free space in the index table cache,

flushing older pages from the index table cache.

16. The memory system of claim 12, where the block TOC is written to a last page of the current data block.