Memory mapping techniques

• US 8,417,893 B2
• Filed: 08/18/2008
• Issued: 04/09/2013
• Est. Priority Date: 02/04/2008
• Status: Expired due to Fees

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Khmelnitsky, Vadim, Wakrat, Nir Jacob
• Primary Examiner(s): Rojas, Midys
• Application Number:
  US12/193,528
• Publication Number:
  US 20090198902A1
• Time in Patent Office: 1,695 Days
• Field of Search: 711/135, 711/202, 711/206, 711/207
• 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 that are mapped to physical pages in non-volatile memory, the read request including a sector address corresponding to a first page address in the non-volatile memory;

checking an index table of contents (TOC) in volatile memory to determine if the first page address is contained in an index table cache in the volatile memory, wherein the index TOC is configured for storing a physical address of an index table that is included in the non-volatile memory for holding physical addresses of data pages, the index TOC including an entry storing (i) a second page address of an index table entry in the non-volatile memory that holds the first page address and (ii) a pointer to an entry in the index table cache that is storing the first page address or to an indicator that the first page address is not stored in the index table cache;

based on determining that the first page address is contained in the index table cache;

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

performing the read operation on the non-volatile memory using the first page address.

2. 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.

3. The method of claim 2, wherein the one or more trigger events include one or more of an increase in read or write disturb being detected, and a Previously Presented bad block being discovered.

4. The method of claim 1, wherein based on determining that the first page address is not included in the index table cache, the method further comprises:

obtaining from the index TOC the second page address of the index table entry in the non-volatile memory storing the first page address;

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

performing the read operation on the non-volatile memory using the first page address.

5. The method of claim 4, further comprising:

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

6. The method of claim 5, wherein the first page address is stored in the index table cache in response to the first page address being read from the index table entry.

7. The method of claim 5, further comprising:

determining whether the index table cache is full; and

based on determining that the index table cache is full, flushing at least a portion of the index table cache to make space available in the index table cache, wherein the first page address is stored in the at least a portion of the index table cache that was flushed.

8. The method of claim 7, further comprising writing data from the at least a portion of the index table cache that is to be flushed to an overflow buffer in volatile memory, wherein the overflow buffer is accessible for translating logical sectors to page addresses in non-volatile memory.

9. A method comprising:

obtaining a write request associated with one or more logical sectors that are mapped to physical pages in non-volatile memory, the write request including a logical sector address corresponding to page addresses in the non-volatile memory;

determining if a current data block is full, wherein the current data block includes a plurality of pages, wherein one page of the plurality of pages is designated to store a block table of contents (TOC) that includes information mapping logical sectors to pages only in the current data block, and wherein the current data block is full when the plurality of pages have been written except for the one page;

based on determining that the current data block is full;

writing the block TOC to the one page of the current data block;

determining if a free block is available; and

upon determining that a free block is not available;

performing a garbage collection operation to generate a free block; and

allocating the generated free block as the current data block.

10. The method of claim 9, wherein based on determining that a free block is available, the method further comprises:

allocating the free block as the current data block.

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

12. The method of claim 9, wherein based on determining that the current data block is not full, the method further comprises:

writing one or more pages into the current data block;

updating the block TOC in the volatile memory; and

updating a valid page count for the current data block.

13. The method of claim 12, further comprising:

determining if an index table cache contains an index page associated with a logical sector that is written to the current data block; and

based on determining that the index table cache contains an index page associated with the logical sector that is written to the current data block, updating the valid page count.

14. The method of claim 13, wherein based on determining that the index table cache does not contain an index page associated with the logical sector that is written to the current data block, the method further comprises:

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

based on determining that there is free space in the index table cache, reading the index page using a location stored in the index table cache.

15. The method of claim 14, wherein based on determining that there is no free space in the index table cache, the method further comprises:

flushing older pages from the index table cache.

16. A memory system, comprising:

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

non-volatile memory storing an index table that is configured for storing physical addresses of data pages corresponding to logical sectors;

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

obtaining a read request associated with a logical sector corresponding to a first page address in the non-volatile memory;

checking the index table of contents to determine if the first page address is stored in the index table cache, wherein the index table of contents includes an entry storing (i) a second page address of an index table entry that holds the first page address and (ii) a pointer to an entry in the index table cache that is storing the first page address or to an indicator that the first page address is not stored in the index table cache;

based on determining that 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 on the non-volatile memory using the first page address.

17. The memory system of claim 16, 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.

18. The memory system of claim 16, wherein based on determining that the first page address is not stored in the index table cache, the controller is operable for performing operations comprising:

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

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

performing the read operation on the non-volatile memory using the first page address.

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

20. 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 addresses of physical pages in the non-volatile memory, the physical pages corresponding to logical sectors;

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

obtaining a write request associated with one or more logical sectors, the write request including a first sector address corresponding to a data block in the non-volatile memory;

determining if a current data block is full, wherein the current data block includes a plurality of pages, wherein one page of the plurality of pages is designated to store a block table of contents (TOC) that includes information mapping logical sectors to pages only in the current data block, and wherein the current data block is full when the plurality of pages have been written except for the one page;

based on determining that the current data block is full;

writing the block TOC to the one page of the current data block;

determining if a free block is available;

upon determining that a free block is not available, performing a garbage collection operation to generate a free block; and

allocating the free block as the current data block.

21. The memory system of claim 20, wherein upon determining that a free block is available, the controller is operable to perform operations comprising:

allocating the free block as the current data block.

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

23. The memory system of claim 20, wherein based on determining that the current data block is not full, the controller is operable for performing operations comprising:

writing one or more pages into the current data block;

updating the block TOC in the volatile memory; and

updating a valid page count for the current data block.

24. The memory system of claim 23, wherein the controller is operable for performing operations further comprising:

determining if an index table cache contains an index page associated with a logical sector that is written to the current data block; and

based on determining that the index table cache contains an index page associated with the logical sector that is written to the current data block, updating the valid page count.

25. The memory system of claim 24, wherein based on determining that the index table cache does not contain an index page associated with a written logical sector, the controller is operable for performing operations further comprising:

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

based on determining that there is free space in the index table cache, reading the index page using a location stored in the index table cache.