Index cache tree

• US 8,516,219 B2
• Filed: 07/24/2009
• Issued: 08/20/2013
• Est. Priority Date: 07/24/2009
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Post, Daniel Jeffrey, Wakrat, Nir Jacob, Khmelnitsky, Vadim
• Primary Examiner(s): Elmore, Reba I
• Application Number:
  US12/509,267
• Publication Number:
  US 20110022819A1
• Time in Patent Office: 1,488 Days
• Field of Search: 711/103, 711/172, 711/203
• US Class Current: 711/203
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 12/1009 using page tables, e.g. page table structures
• 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 location of the first lookup table in non-volatile memory. An index cache tree in volatile memory holds the physical addresses of the most recently written or accessed logical sectors in a compressed format.

Claims

1. A method comprising:

receiving a request for data associated with a logical address, where the logical address corresponds to a physical address of the requested data in non-volatile memory;

accessing an index cache tree that contains compressed data comprising a predefined number of most recently accessed mappings between logical addresses to physical addresses of data in the non-volatile memory, wherein the predefined number of mappings comprises a subset of all logical address to physical address mappings for the non-volatile memory;

translating the associated logical address into the corresponding physical address by traversing the accessed index cache tree and aggregating at least a portion of the compressed data to represent the associated logical address; and

returning the corresponding physical address of the requested data in non-volatile memory.

2. The method of claim 1, wherein the index cache tree is located in volatile memory.

3. The method of claim 1, wherein the index cache tree is located in non-volatile memory.

4. The method of claim 1, wherein the index cache tree contains a plurality of nodes organized into a hierarchical structure and wherein each node contains a plurality of entries.

5. The method of claim 4 wherein, for each of the plurality of entries, the compressed data comprises a logical address span contained in the entry that corresponds to a length of an associated memory segment.

6. The method of claim 4 wherein, for each of the plurality of entries, the compressed data comprises a flag contained in the entry that indicates a predetermined length for the entry.

7. The method of claim 6, wherein the flag is one or more bits of an entry.

8. The method of claim 4, wherein each of the plurality of entries includes at least one of:

a pointer to a node,

a physical address corresponding to a memory segment, and

an indicator that the requested physical address is not contained in the index cache tree.

9. The method of claim 4 further comprising:

starting at a root node of the index cache tree; and

identifying an entry of the root node that corresponds to the associated logical address by sequentially aggregating logical address spans of the entries of the root node until an aggregate logical address span corresponds to the associated logical address.

10. The method of claim 9, wherein the identified entry of the root node contains a pointer to a second node of the index cache tree.

11. The method of claim 10, further comprising identifying an entry of the second node that corresponds to the associated logical address by sequentially adding logical address spans of the entries of the second node to the aggregate logical address span until the aggregate logical address span corresponds to the associated logical address, wherein the identified entry of the second node contains the physical address for the memory segment.

12. A system comprising:

non-volatile memory storing data that is associated with physical addresses; and

a controller coupled to the non-volatile memory, wherein the controller is configured to receive a request for data associated with a logical address, where the logical address corresponds to a physical address of the requested data in the non-volatile memory, and wherein the controller is further configured to determine the corresponding physical address by;

accessing an index cache tree that contains compressed data comprising a predefined number of most recently accessed mappings between logical addresses to physical addresses of data in stored in the non-volatile memory, wherein the predefined number of mappings comprises a subset of all logical address to physical address mappings for the non-volatile memory; and

by translating the associated logical address into the corresponding physical address using the accessed index cache tree, where the associated logical address is translated into the corresponding physical address by traversing the accessed index cache tree and aggregating at least a portion of the compressed data to represent the associated logical address.

13. The system of claim 12, further comprising volatile memory storing the index cache tree.

14. The system of claim 12, wherein the index cache tree is stored in the non-volatile memory.

15. The system of claim 12, wherein the index cache tree contains a plurality of nodes organized into a hierarchical structure and wherein each node contains a plurality of entries.

16. The system of claim 15 wherein, for each of the plurality of entries, the compressed data comprises a logical address span contained in the entry that corresponds to a length of an associated memory segment.

17. The system of claim 15, wherein, for each of the plurality of entries, the compressed data comprises a flag contained in the entry that indicates a predetermined length for the entry.

18. A method comprising:

receiving a request for data associated with a logical address, where the logical address corresponds to a physical address of the requested data in non-volatile memory;

accessing an index cache tree that contains compressed data comprising a predefined number of most recently accessed mappings between logical addresses to physical addresses of data in the non-volatile memory, wherein the predefined number of mappings comprising a subset of all logical address to physical address mappings for the non-volatile memory, the index cache tree comprises a plurality of nodes organized into a hierarchical structure, where each of the plurality of nodes comprises a plurality of entries and each entry includes a logical address span and either a pointer to a node or a physical address corresponding to the logical address span;

translating the associated logical address into the corresponding physical address of the requested data in the non-volatile memory based upon a physical address stored in an entry of the index cache tree identified as corresponding to the associated logical address; and

returning the identified physical address for the memory segment.

19. The method of claim 18, wherein translating the associated logical address into the corresponding physical address further comprises:

starting at a root node of the index cache tree, identifying an entry of the root node that corresponds to the associated logical address by sequentially aggregating logical address spans of the entries of the root node until an aggregate logical address span corresponds to the associated logical address, wherein the identified entry of the root node contains a pointer to a second node of the index cache tree.

20. The method of claim 19, wherein translating the associated logical address into the corresponding physical address further comprises:

identifying an entry of the second node that corresponds to the associated logical address by sequentially adding logical address spans of the entries of the second node to the aggregate logical address span until the aggregate logical address span corresponds to the associated logical address, wherein the identified entry of the second node contains the physical address of the requested data in non-volatile memory.

21. The method of claim 18, wherein a length of each entry comprises a first number of bits in length or second number of bits in length based upon the logical address span for the entry, and wherein entries of a node are sequentially ordered from least significant logical address to most significant logical address.