INDEX CACHE TREE

• US 20110022819A1
• Filed: 07/24/2009
• Published: 01/27/2011
• Est. Priority Date: 07/24/2009
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Khmelnitsky, Vadim, Post, Daniel Jeffrey, Wakrat, Nir Jacob
• Granted Patent: US 8,516,219 B2
• Time in Patent Office: Days
• US Class Current: 711/207
• 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 tree that contains compressed data mapping logical addresses to physical addresses of data in the non-volatile memory;

translating the associated logical address into the corresponding physical address by traversing the accessed index 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 tree is located in volatile memory.

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

4. The method of claim 1, wherein the index 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 a indicator that the requested physical address is not contained in the index tree.

9. The method of claim 4 further comprising, starting at a root node of the index 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.

10. The method of claim 9, wherein the identified entry of the root node contains a pointer to a second node of the index 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 that receives 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, wherein the controller is operable for determining the corresponding physical address by accessing an index tree that contains compressed data mapping logical addresses to physical addresses of data in stored in the non-volatile memory and by translating the associated logical address into the corresponding physical address using the accessed index tree, where the associated logical address is translated into the corresponding physical address by traversing the accessed index 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 tree.

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

15. The system of claim 12, wherein the index 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 tree that maps logical addresses to physical addresses of data in the non-volatile memory, the index tree comprising a plurality of nodes organized into a hierarchical structure, wherein each of the plurality of nodes comprises a plurality of entries, wherein 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 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 identifying further comprises:

starting at a root node of the index 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 tree.

20. The system of claim 19, wherein identifying 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.