Robust index storage for non-volatile memory
First Claim
1. A method of operating a non-volatile memory device, comprising:
- looking up a logical sector address of a memory access to the non-volatile memory in a hierarchal address translation data structure to translate the logical sector address to a physical sector address, wherein the hierarchal address translation data structure contains two or more Tables/data structures arranged in a hierarchal data tree;
accessing the logical sector address in a physical sector address of the memory array in reference to a version number stored in a version number data field of the sector; and
accessing the physical sector address in the non-volatile memory device.
8 Assignments
0 Petitions
Accused Products
Abstract
A non-volatile memory data address translation scheme is described that utilizes a hierarchal address translation system that is stored in the non-volatile memory itself. Embodiments of the present invention utilize a hierarchal address data and translation system wherein the address translation data entries are stored in one or more data structures/tables in the hierarchy, one or more of which can be updated in-place multiple times without having to overwrite data. This hierarchal address translation data structure and multiple update of data entries in the individual tables/data structures allow the hierarchal address translation data structure to be efficiently stored in a non-volatile memory array without markedly inducing write fatigue or adversely affecting the lifetime of the part. The hierarchal address translation of embodiments of the present invention also allow for an address translation layer that does not have to be resident in system RAM for operation.
38 Citations
41 Claims
-
1. A method of operating a non-volatile memory device, comprising:
-
looking up a logical sector address of a memory access to the non-volatile memory in a hierarchal address translation data structure to translate the logical sector address to a physical sector address, wherein the hierarchal address translation data structure contains two or more Tables/data structures arranged in a hierarchal data tree; accessing the logical sector address in a physical sector address of the memory array in reference to a version number stored in a version number data field of the sector; and accessing the physical sector address in the non-volatile memory device. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12)
-
-
13. A method of operating a non-volatile memory device, comprising:
-
looking up a logical sector address of a memory access to the non-volatile memory in a hierarchal address translation data structure to translate the logical sector address to a physical sector address, wherein the hierarchal address translation data structure contains two or more Tables/data structures arranged in a hierarchal data tree; accessing the physical sector address in the non-volatile memory device; updating the hierarchal address translation data structure when user data stored in the non-volatile memory device is updated by traversing up the hierarchal address translation data structure, starting with a Table storing the changed address translation entry, the updating further comprising; checking if update space remains in a changed data entry or address pointer data entry in a current Table/data structure of a current level of the hierarchal address translation data structure; updating the changed data entry or address pointer data entry when update space is available, and ending the update of the hierarchal address translation data structure; creating a new Table/data structure when the changed data entry cannot be updated in the current Table/data structure; copying the most-current entries/pointers to the new Table/data structure; ending the update of the hierarchal address translation data structure if the current Table/data structure is at a top level of the hierarchal address translation data structure; traversing up to a next level of the hierarchal address translation data structure if the current Table/data structure is not at the top level of the hierarchal address translation data structure; and repeating updating on a parent Table/data structure of the next level to change an address pointer in the parent Table/data structure from the current to the new Table/data structure.
-
-
14. A method of storing address translation data in a non-volatile memory array, comprising:
-
storing address translation data in a hierarchal address translation data structure of two or more Tables/data structures, where the two or more Tables/data structures are arranged in a hierarchal tree; and updating the hierarchal address translation data structure when user data stored in the non-volatile memory array is updated by traversing up the hierarchal address translation data structure, starting with a Table storing the changed address translation entry, the updating further comprising; checking if update space remains in a changed data entry or address pointer data entry in a current Table/data structure of a current level of the hierarchal address translation data structure; updating the changed data entry or address pointer data entry when update space is available, and ending the update of the hierarchal address translation data structure; creating a new Table/data structure when the changed data entry cannot be updated in the current Table/data structure; copying the most-current entries/pointers to the new Table/data structure; ending the update of the hierarchal address translation data structure if the current Table/data structure is at a top level of the hierarchal address translation data structure; traversing up to a next level of the hierarchal address translation data structure if the current Table/data structure is not at the top level of the hierarchal address translation data structure; and repeating updating on a parent Table/data structure of the next level to change an address pointer in the parent Table/data structure from the current to the new Table/data structure. - View Dependent Claims (15, 16, 17, 18)
-
-
19. A non-volatile memory device, comprising:
-
a non-volatile memory array having a plurality of non-volatile memory cells; and a control circuit, wherein the control circuit is adapted to access a logical address from the memory array by translating the logical address to a physical sector address of the memory array in reference to a hierarchal address translation data structure stored in the non-volatile memory array, wherein the hierarchal address translation data structure comprises; an Entry Point; a Root Table; one or more Child Tables; and wherein the Entry Point contains an address pointer data entry to the Root Table, the Root Table contains one or more address pointer data entries to the one or more Child Tables, and each of the one or more Child Tables contain one or more address translation data entries to translate a logical address to a physical address; and wherein the control circuit is further adapted to update the hierarchal address translation data structure when user data stored in the non-volatile memory array is updated by traversing up the hierarchal address translation data structure, starting with the Child Table storing the changed address translation entry, updating the hierarchal address translation data structure further comprising; checking if update space remains in a changed data entry or address pointer data entry in a current Table/data structure of a current level of the hierarchal address translation data structure; updating the changed data entry or address pointer data entry when update space is available, and ending the update of the hierarchal address translation data structure; creating a new Table/data structure when the changed data entry cannot be updated in the current Table/data structure; copying the most-current entries/pointers to the new Table/data structure; ending the update of the hierarchal address translation data structure if the current Table/data structure is the Entry Point; traversing up to a next level of the hierarchal address translation data structure if the current Table/data structure is not the Entry Point; and repeating updating on a parent Table/data structure of the next level to change an address pointer in the parent Table/data structure from the current to the new Table/data structure. - View Dependent Claims (20, 21, 22, 23, 24, 25, 26, 27)
-
-
28. A non-volatile memory device, comprising:
-
a non-volatile memory array having a plurality of non-volatile memory cells and arranged into a plurality of erase blocks, each erase block containing a plurality of sectors; and a control circuit, wherein the control circuit is adapted to access a logical address from the memory array by translating the logical address to a physical sector address of the memory array in reference to a hierarchal address translation data structure stored in the non-volatile memory array and to access a sector from the non-volatile memory array by translating a logical address of the sector to a physical sector address of the memory array in reference to a version number stored in a version number data field of the sector.
-
-
29. A Flash memory device, comprising:
-
a memory array having a plurality of non-volatile memory cells arranged in a plurality of erase blocks, each erase block containing a plurality of clusters of one or more consecutively addressed sectors; and a control circuit, wherein the control circuit is adapted to access a logical address from the memory array by translating the logical address to a physical sector address of the memory array in reference to a hierarchal address translation data structure stored in the one or more erase blocks of the plurality of erase blocks; and wherein the hierarchal address translation data structure comprises; a Data_Root; a Data_Map Table; one or more consecutive sector group (CSG) Tables or one or more discrete sector group (DSG) Tables; and wherein the Data_Root contains an address pointer data entry to the Data_Map Table, the Data_Map Table contains one or more address pointer data entries to the one or more CSG Tables or one or more DSG Tables, each of the one or more CSG Tables contain one or more address translation data entries to translate a logical address to a physical address of a cluster of consecutively address sectors, and each of the one or more DSG Tables contain one or more address translation data entries to translate a logical address to a physical address of a single sector cluster of a frequently updated sector. - View Dependent Claims (30, 31, 32, 33)
-
-
34. A Flash memory device, comprising:
-
a memory array having a plurality of non-volatile memory cells arranged in a plurality of erase blocks, each erase block containing a plurality of clusters of one or more consecutively addressed sectors; and a control circuit, wherein the control circuit is adapted to access a logical address from the memory array by translating the logical address to a physical sector address of the memory array in reference to a hierarchal address translation data structure stored in the one or more erase blocks of the plurality of erase blocks; and wherein the Flash memory device is adapted to access sectors in the memory array utilizing a version number address translation to retrieve the physical address in the memory array containing the most recent version of the accessed sector.
-
-
35. A system, comprising:
-
a host coupled to a non-volatile memory device, wherein the system is adapted to translate logical addresses to physical addresses in the non-volatile memory device utilizing hierarchal address translation data, where the hierarchal address translation data structure comprises; an Entry Point; a Root Table; one or more Child Tables; and wherein the Entry Point contains an address pointer data entry to the Root Table, the Root Table contains one or more address pointer data entries to the one or more Child Tables, and each of the one or more Child Tables contain one or more address translation data entries to translate a logical address to a physical address; and wherein the system is adapted to update the hierarchal address translation data structure when user data stored in the non-volatile memory array is updated by traversing up the hierarchal address translation data structure, starting with the Child Table storing the changed address translation entry, updating the hierarchal address translation data structure further comprising; checking if update space remains in a changed data entry or address pointer data entry in a current Table/data structure of a current level of the hierarchal address translation data structure; updating the changed data entry or address pointer data entry when update space is available and ending the update of the hierarchal address translation data structure; creating a new Table/data structure when the changed data entry cannot be updated in the current Table/data structure; copying the most-current entries/pointers to the new Table/data structure, ending the update of the hierarchal address translation data structure if the current Table/data structure is the Entry Point;
traversing up to a next level of the hierarchal address translation data structure if the current Table/data structure is not the Entry Point; andrepeating updating on a parent Table/data structure of the next level to change an address pointer in the parent Table/data structure from the current to the new Table/data structure. - View Dependent Claims (36, 37, 38, 39)
-
-
40. A system, comprising:
-
a host coupled to a non-volatile memory device, wherein the system is adapted to translate logical addresses to physical addresses in the non-volatile memory device utilizing a hierarchal address translation data, where the hierarchal address translation data structure comprises; an Entry Point; a Root Table; one or more Child Tables; and wherein the Entry Point contains an address pointer data entry to the Root Table, the Root Table contains one or more address pointer data entries to the one or more Child Tables, and each of the one or more Child Tables contain one or more address translation data entries to translate a logical address to a physical address; and wherein the hierarchal address translation data structure further comprises a Logical to Physical Erase Block Translation Table, where the one or more address translation entries in the one or more Child Tables contain a logical erase block ID, and where the system is adapted to translate the logical erase block ID to a physical erase block utilizing the Logical to Physical Erase Block Translation Table.
-
-
41. A system, comprising:
-
a host coupled to a non-volatile memory device, wherein the system is adapted to translate logical addresses to physical addresses in the non-volatile memory device utilizing hierarchal address translation data; and wherein the non-volatile memory device comprises; a memory array having a plurality of non-volatile memory cells arranged in a plurality of erase blocks, each erase block containing a plurality of sectors; and a control circuit, wherein the control circuit is adapted to access a logical address from the memory array by translating the logical address to a physical sector address of the memory array in reference to a hierarchal address translation data structure stored in the one or more erase blocks of the plurality of erase blocks; and wherein the system is adapted to access a sector from the non-volatile memory device by translating a logical address of the sector to a physical sector address of the memory array in reference to a version number stored in a version number data field of the sector.
-
Specification