Robust index storage for non-volatile memory

• US 20060282644A1
• Filed: 06/08/2005
• Published: 12/14/2006
• Est. Priority Date: 06/08/2005
• Status: Active Grant

• Current Assignee: Micron Technology, Inc.
• Original Assignee: Micron Technology, Inc.
• Inventors: Wong, Wanmo
• Granted Patent: US 7,509,474 B2
• Time in Patent Office: Days
• US Class Current: 711/206
• 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/2022 Flash memory
• CPC Class Codes: G06F 2212/7201 Logical to physical mapping or translation of blocks or pages

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.

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; and

accessing the physical sector address in the non-volatile memory device.

2. The method of claim 1, wherein the hierarchal address translation data structure further comprises:

a Root Table;

one or more Child Tables; and

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

3. The method of claim 2, wherein each of the Root Table'"'"'s one or more address pointers data entries to the one or more Child Tables can be updated one or more times without overwriting the previous pointer data stored in the entry, and each of the one or more Child Table'"'"'s one or more address translation data entries can be updated one or more times without overwriting the previous translation data stored in the entry.

4. The method of claim 2, further comprising an Entry Point data structure, wherein the Entry Point data structure contains an address pointer data entry to the Root Table.

5. The method of claim 4, wherein the Entry Point data structure'"'"'s address pointer data entry to the Root Table can be updated one or more times without overwriting the previous pointer data stored in the entry.

6. The method of claim 1, wherein looking up a logical address of a memory access to the non-volatile memory in a hierarchal address translation data structure further comprises:

traversing the hierarchal data tree of the hierarchal address translation data structure starting from a Root Table;

selecting a Child Table containing an address translation data entry for the accessed logical address; and

reading the address translation data entry for the accessed logical address to translate the logical address to a physical address.

7. The method of claim 6, wherein traversing the hierarchal data tree of the hierarchal address translation data structure starting from a Root Table further comprises retrieving the address to the Root Table from an Entry Point data structure.

8. The method of claim 1, further comprising:

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.

9. The method of claim 1, wherein the hierarchal address translation data structure further comprises a Logical to Physical Erase Block Translation Table.

10. The method of claim 9, further comprising:

translating a logical erase block ID to a physical erase block ID utilizing the Logical to Physical Erase Block Translation Table.

11. The method of claim 1, further comprising:

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.

12. The method of claim 1, wherein looking up a logical 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 further comprises looking up a logical 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 cluster address, wherein each cluster contains one or more consecutively addressed sectors.

13. The method of claim 1, wherein an Entry Point is stored at a known address location or is stored within a defined Control Area of the non-volatile memory device.

14. The method of claim 13, wherein the Entry Point stores one of configuration information or a pointer to configuration information for the non-volatile memory device.

15. A method of translating a logical address to a physical address in a memory device, comprising:

looking up a logical address in a hierarchal address translation data structure to translate the logical address to a physical address, wherein the hierarchal address translation data structure contains two or more Tables/data structures arranged in a hierarchal data tree.

16. The method of claim 15, wherein the hierarchal address translation data structure further comprises:

a Root Table;

one or more Child Tables; and

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

17. The method of claim 16, wherein each of the Root Table'"'"'s one or more address pointers data entries to the one or more Child Tables can be updated one or more times without overwriting the previous pointer data stored in the entry, and each of the one or more Child Table'"'"'s one or more address translation data entries can be updated one or more times without overwriting the previous translation data stored in the entry.

18. The method of claim 16, further comprising an Entry Point data structure, wherein the Entry Point data structure contains an address pointer data entry to the Root Table.

19. The method of claim 18, wherein the Entry Point data structure'"'"'s address pointer data entry to the Root Table can be updated one or more times without overwriting the previous pointer data stored in the entry.

20. The method of claim 18, wherein the Entry Point is stored at known address location or stored within a defined Control Area of a non-volatile memory device.

21. The method of claim 15, wherein looking up a logical address in a hierarchal address translation data structure further comprises:

traversing the hierarchal data tree of the hierarchal address translation data structure starting from a Root Table;

selecting a Child Table containing an address translation data entry for the accessed logical address; and

reading the address translation data entry for the accessed logical address to translate the logical address to a physical address.

22. The method of claim 21, wherein traversing the hierarchal data tree of the hierarchal address translation data structure starting from a Root Table further comprises retrieving the address to the Root Table from an Entry Point data structure.

23. The method of claim 16, wherein the hierarchal address translation data structure further comprises a Logical to Physical Erase Block Translation Table.

24. The method of claim 23, further comprising:

translating a logical erase block ID to a physical erase block ID utilizing the Logical to Physical Erase Block Translation Table.

25. A method of updating a hierarchal address translation data structure containing two or more Tables/data structures arranged in a hierarchal data tree and storing address translation data used to translate a logical address to a physical address, comprising:

traversing up the hierarchal address translation data structure, starting with a Table storing a changed address translation entry, the traversing 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 when 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.

26. The method of claim 25, wherein the hierarchal address translation data structure further comprises:

a Root Table;

one or more Child Tables; and

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

27. The method of claim 26, wherein each of the Root Table'"'"'s one or more address pointers data entries to the one or more Child Tables can be updated one or more times without overwriting the previous pointer data stored in the entry, and each of the one or more Child Table'"'"'s one or more address translation data entries can be updated one or more times without overwriting the previous translation data stored in the entry.

28. The method of claim 26, further comprising an Entry Point data structure, wherein the Entry Point data structure contains an address pointer data entry to the Root Table.

29. The method of claim 28, wherein the Entry Point data structure'"'"'s address pointer data entry to the Root Table can be updated one or more times without overwriting the previous pointer data stored in the entry.

30. The method of claim 28, wherein the Entry Point data structure is stored at a known address location or stored within a defined Control Area of a non-volatile memory device.

31. The method of claim 25, further comprising storing a version number with each of the two or more Tables/data structures of the hierarchal address translation data structure, where the version number is changed each time a new Tables/data structures is created.

32. The method of claim 31, further comprising maintaining a selected number of old version number instances of a Table/data structure in the hierarchal address translation data structure when a new instance of the Table/data structure is created.

33. A method of abstracting logical addresses to physical addresses of a memory device utilizing an address translation layer, comprising:

looking up a logical address with an address translation table and translating the logical address to a logical erase block ID; and

translating the logical erase block ID to a physical erase block ID utilizing a Logical to Physical Erase Block Translation Table.

34. The method of claim 33, wherein looking up a logical address with an address translation table and translating the logical address to a logical erase block ID further comprises looking up a logical address with an address translation table and translating the logical address to a logical erase block ID and a local physical address within the logical erase block.

35. The method of claim 33, wherein the address translation layer utilizes one of a hierarchal address translation data structure, an address translation table, and a cluster address translation table.

36. The method of claim 33, further comprising:

updating the Logical to Physical Erase Block Translation Table due to moving or reclaiming an erase block, updating the Logical to Physical Erase Block Translation Table further comprising;

checking if update space remains in a changed erase block translation data entry of the Logical to Physical Erase Block Translation Table;

updating the changed data entry when update space is available and ending the update of the Logical to Physical Erase Block Translation Table;

creating a new Logical to Physical Erase Block Translation Table when the changed data entry cannot be updated in the current Logical to Physical Erase Block Translation Table; and

copying the most-current data entries to the new Logical to Physical Erase Block Translation Table.

37. The method of claim 33, wherein the Logical to Physical Erase Block Translation Table further comprises a hierarchal erase block translation data structure of two or more Tables/data structures, where the two or more Tables/data structures are arranged in a hierarchal tree.

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

39. The method of claim 38, wherein the hierarchal address translation data structure further comprises:

a Root Table;

one or more Child Tables; and

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

40. The method of claim 39, wherein each of the Root Table'"'"'s one or more address pointers data entries to the one or more Child Tables can be updated one or more times without overwriting the previous pointer data stored in the entry, and each of the one or more Child Table'"'"'s one or more address translation data entries can be updated one or more times without overwriting the previous translation data stored in the entry.

41. The method of claim 39, further comprising an Entry Point data structure, wherein the Entry Point data structure contains an address pointer data entry to the Root Table.

42. The method of claim 41, wherein the Entry Point data structure'"'"'s address pointer data entry to the Root Table can be updated one or more times without overwriting the previous pointer data stored in the entry.

43. A method of initiating operation of a non-volatile memory device, comprising:

searching a defined area of the non-volatile memory device to locate an Entry Point data structure; and

loading configuration information for the non-volatile memory device from the Entry Point data structure.

44. The method of claim 43, wherein loading configuration information for the non-volatile memory device from the Entry Point data structure further comprises loading configuration information for the non-volatile memory device from an address location indicated by a pointer stored in the Entry Point data structure.

45. The method of claim 43, wherein loading configuration information for the non-volatile memory device from the Entry Point data structure further comprises loading address translation data from the Entry Point Data structure.

46. The method of claim 45, wherein loading address translation data for the non-volatile memory device from the Entry Point data structure further comprises loading address translation data for the non-volatile memory device from an address location indicated by a pointer stored in the Entry Point data structure.

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

48. The non-volatile memory device of claim 47, 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.

49. The non-volatile memory device of claim 48, wherein the one or more Child Tables are arranged in one or more layers of Tables, where each of the one or more Child Tables in a bottom layer of Child Tables contain one or more address translation data entries to translate a logical address to a physical address and each of the one or more Child Tables in intervening layers of Child Tables contain one or more address pointer data entries to a lower layer of Child Tables.

50. The non-volatile memory device of claim 48, wherein the Entry Point'"'"'s address pointer data entry to the Root Table can be updated one or more times without overwriting the previous pointer data stored in the entry, each of the Root Table'"'"'s one or more address pointers data entries to the one or more Child Tables can be updated one or more times without overwriting the previous pointer data stored in the entry, and each of the one or more Child Table'"'"'s one or more address translation data entries can be updated one or more times without overwriting the previous translation data stored in the entry.

51. The non-volatile memory device of claim 50, wherein the control circuit 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; 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.

52. The non-volatile memory device of claim 47, 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 control circuit is adapted to translate the logical erase block ID to a physical erase block utilizing the Logical to Physical Erase Block Translation Table.

53. The non-volatile memory device of claim 47, wherein the non-volatile memory array is further arranged into a plurality of erase blocks, each erase block containing a plurality of sectors.

54. The non-volatile memory device of claim 53, wherein the plurality of sectors are further arranged into clusters of sequential sectors.

55. The non-volatile memory device of claim 53, wherein the control circuit is adapted 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.

56. The non-volatile memory device of claim 47, wherein the Entry Point is stored at known address location or stored within a defined Control Area of the non-volatile memory array.

57. The non-volatile memory device of claim 47, wherein the Entry Point stores one of configuration information or a pointer to configuration information for the non-volatile memory device.

58. The non-volatile memory device of claim 47, wherein the non-volatile memory is one of a NAND Flash memory device, a NOR Flash memory device, a Polymer memory device, a Ferroelectric Random Access Memory (FeRAM) device, an Ovionics Unified Memory (OUM) device, a Nitride Read Only Memory (NROM) device, a Carbon Nanotube Memory device, and a Magnetoresistive Random Access Memory (MRAM) device.

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

60. The Flash memory device of claim 59, 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.

61. The Flash device of claim 60, wherein the Data_Root'"'"'s address pointer data entry to the Data_Map Table can be updated one or more times without overwriting the previous pointer data stored in the entry, each of the Data_Map Table'"'"'s one or more address pointers data entries to the one or more CSG Tables or one or more DSG Tables can be updated one or more times without overwriting the previous pointer data stored in the entry, each of the one or more CSG Table'"'"'s one or more address translation data entries can be updated one or more times without overwriting the previous translation data stored in the entry, and each of the one or more DSG Table'"'"'s one or more address translation data entries can be updated one or more times without overwriting the previous translation data stored in the entry.

62. The Flash memory device of claim 61, wherein the control circuit 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, updating the hierarchal address translation data structure further comprising:

checking if update space remains in an address translation data entry for the changed user data in a current CSG Table or DSG Table;

updating the address translation data entry when update space is available, and ending the update of the hierarchal address translation data structure;

creating a new CSG Table or DSG Table when the changed address translation data entry cannot be updated in the current CSG Table or DSG Table;

copying one or more most-current address translation entries to the new CSG Table or DSG Table;

checking if update space remains in an address pointer to the current CSG Table or DSG Table in the Data_Map Table;

updating the changed address pointer entry when update space is available, and ending the update of the hierarchal address translation data structure;

creating a new Data_Map Table when the changed address pointer entry cannot be updated in the Data_Map Table;

copying one or more most-current pointers to the new Data_Map Table;

checking if update space remains in an address pointer to the Data_Map Table in the Data_Root;

updating the changed address pointer entry when update space is available, and ending the update of the hierarchal address translation data structure;

creating a new Data_Root when the changed address pointer entry cannot be updated in the Data_Root; and

copying one or more most-current pointers to the new Data_Root.

63. The Flash memory device of claim 59, wherein the hierarchal address translation data structure further comprises a Block_ID erase block translation table, where the one or more address translation entries in the one or more CSG Tables or one or more DSG Tables contain a logical erase block ID, and where the control circuit is adapted to translate the logical erase block ID to a physical erase block utilizing the Block_ID Table.

64. The Flash memory device of claim 59, wherein the Flash memory device is one of a NAND Flash memory device and a NOR Flash memory device.

65. The Flash memory device of claim 59, 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.

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

67. The system of claim 66, 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.

68. The system of claim 66, 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.

69. The system of claim 68, wherein the Entry Point'"'"'s address pointer data entry to the Root Table can be updated one or more times without overwriting the previous pointer data stored in the entry, each of the Root Table'"'"'s one or more address pointers data entries to the one or more Child Tables can be updated one or more times without overwriting the previous pointer data stored in the entry, and each of the one or more Child Table'"'"'s one or more address translation data entries can be updated one or more times without overwriting the previous translation data stored in the entry.

70. The system of claim 69, 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; 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.

71. The system of claim 66, 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.

72. The system of claim 67, wherein the system is adapted to access logical sectors of data in the non-volatile memory device utilizing a cluster address translation to retrieve the physical address in the memory array of a cluster of consecutive sectors containing an accessed logical sector.

73. The system of claim 67, 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.

74. The system of claim 66, wherein the non-volatile memory is one of a NAND Flash memory device, a NOR Flash memory device, a Polymer memory device, a Ferroelectric Random Access Memory (FeRAM) device, an Ovionics Unified Memory (OUM) device, a Nitride Read Only Memory (NROM) device, and a Magnetoresistive Random Access Memory (MRAM) device.