Non-volatile semiconductor memory storing an inverse map for rebuilding a translation table

• US 8,407,449 B1
• Filed: 02/26/2010
• Issued: 03/26/2013
• Est. Priority Date: 02/26/2010
• Status: Active Grant

• Current Assignee: Sandisk Technologies Incorporated (Western Digital Corporation)
• Original Assignee: Western Digital Technologies Incorporated (Western Digital Corporation)
• Inventors: Colon, Kevin M., Rainey, Charles P. III
• Primary Examiner(s): LANE, JOHN A
• Application Number:
  US12/714,350
• Time in Patent Office: 1,124 Days
• Field of Search: 711/103, 711/154, 711/156, 711/159, 711/165
• US Class Current: 711/206
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 2212/7201 Logical to physical mapping or translation of blocks or pages

Abstract

A non-volatile semiconductor memory is disclosed comprising a non-volatile memory array including a plurality of blocks, each block comprising a plurality of memory segments each assigned a physical address. A logical address is read from a first block, wherein the logical address corresponds to a physical address of one of the memory segments. When the memory segment corresponding to the logical address is valid, a translation table is updated using the logical address, wherein the translation table for mapping logical addresses to physical addresses. When the memory segment corresponding to the logical address is invalid, a dirty table is updated using the logical address. The dirty table is used to perform a garbage collection operation, wherein invalid memory segments are erased without being relocated.

Claims

1. A non-volatile semiconductor memory comprising:

a non-volatile memory array including a plurality of blocks, each block comprising a plurality of memory segments each assigned a physical address; and

control circuitry operable to;

read a logical address from an inverse map stored in the non-volatile memory array, wherein the logical address corresponds to a physical address of one of the memory segments;

when the memory segment corresponding to the logical address is valid, update a translation table using the logical address, wherein the translation table maps logical addresses to physical addresses;

when the memory segment corresponding to the logical address is invalid, update a dirty table using the physical address of the memory segment; and

use the dirty table to perform a garbage collection operation, wherein invalid memory segments are erased without being relocated.

2. The non-volatile semiconductor memory as recited in claim 1, wherein a first block of the non-volatile memory array comprises the logical address of the inverse map and the corresponding memory segment.

3. The non-volatile semiconductor memory as recited in claim 1, wherein a first block of the non-volatile memory array comprises the logical address of the inverse map and a second block of the non-volatile memory array comprises the corresponding memory segment.

4. The non-volatile semiconductor memory as recited in claim 1, wherein the control circuitry is operable to generate substantially the entire translation table by reading logical addresses from the non-volatile memory array.

5. The non-volatile semiconductor memory as recited in claim 4, further comprising a volatile memory for storing the translation table, wherein the translation table is not written to the non-volatile memory array.

6. The non-volatile semiconductor memory as recited in claim 1, wherein the control circuitry is further operable to maintain a chronological write order of the memory segments.

7. The non-volatile semiconductor memory as recited in claim 6, wherein the control circuitry is further operable to generate the translation table in response to the chronological write order.

8. The non-volatile semiconductor memory as recited in claim 7, wherein the control circuitry is further operable to generate the translation table by reading logical addresses from the non-volatile memory array in the chronological write order.

9. The non-volatile semiconductor memory as recited in claim 6, wherein the control circuitry is further operable to generate the dirty table in response to the chronological write order.

10. The non-volatile semiconductor memory as recited in claim 9, wherein the control circuitry is further operable to determine whether the memory segment is invalid based on the chronological write order.

11. A method of operating a non-volatile semiconductor memory comprising a non-volatile memory array including a plurality of blocks, each block comprising a plurality of memory segments each assigned a physical address, the method comprising:

reading a logical address from an inverse map stored in the non-volatile memory array, wherein the logical address corresponds to a physical address of one of the memory segments;

when the memory segment corresponding to the logical address is valid, updating a translation table using the logical address, wherein the translation table maps logical addresses to physical addresses;

when the memory segment corresponding to the logical address is invalid, updating a dirty table using the physical address of the memory segment; and

using the dirty table to perform a garbage collection operation, wherein invalid memory segments are erased without being relocated.

12. The method as recited in claim 11, wherein a first block of the non-volatile memory array comprises the logical address of the inverse map and the corresponding memory segment.

13. The method as recited in claim 11, wherein a first block of the non-volatile memory array comprises the logical address and a second block of the non-volatile memory array comprises the corresponding memory segment.

14. The method as recited in claim 11, wherein substantially the entire translation table is generated by reading logical addresses from the non-volatile memory array.

15. The method as recited in claim 14, further comprising a volatile memory for storing the translation table, wherein the translation table is not written to the non-volatile memory array.

16. The method as recited in claim 11, further comprising maintaining a chronological write order of the memory segments.

17. The method as recited in claim 16, further comprising generating the translation table in response to the chronological write order.

18. The method as recited in claim 17, further comprising generating the translation table by reading logical addresses from the non-volatile memory array in the chronological write order.

19. The method as recited in claim 16, further comprising generating the dirty table in response to the chronological write order.

20. The method as recited in claim 19, further comprising determining whether the memory segment is invalid based on the chronological write order.

21. A method of operating a non-volatile semiconductor memory comprising (1) a non-volatile memory array including a plurality of blocks, each block comprising a plurality of memory segments each assigned a physical address and (2) a volatile memory, the method comprising:

upon a power-up of the non-volatile semiconductor memory, generating, in the volatile memory, a translation table for mapping logical addresses to physical addresses in the non-volatile memory array, the generating comprising;

reading at least one entry comprising a logical address from an inverse map stored in the non-volatile memory array, wherein the logical address corresponds to a physical address of one of the memory segments, and wherein entries in the inverse map correspond to a chronological write order of the memory segments in the non-volatile memory array;

in response to determining that the memory segment corresponding to the logical address is valid, updating the translation table using the logical address when the memory segment corresponding to the logical address is invalid, updating a dirty table using the physical address of the memory segment; and

using the dirty table to perform a garbage collection operation, wherein invalid memory segments are erased without being relocated.

22. A non-volatile semiconductor memory comprising:

a non-volatile memory array including a plurality of blocks, each block comprising a plurality of memory segments each assigned a physical address;

a volatile memory; and

control circuitry operable to;

upon a power-up of the non-volatile semiconductor memory, generate, in the volatile memory, a translation table for mapping logical addresses to physical addresses in the non-volatile memory array, the control circuitry operable to generate by at least;

reading at least one entry comprising a logical address from an inverse map stored in the non-volatile memory array, wherein the logical address corresponds to a physical address of one of the memory segments, and wherein entries in the inverse map correspond to a chronological write order of the memory segments in the non-volatile memory array;

in response to determining that the memory segment corresponding to the logical address is valid, updating the translation table using the logical address when the memory segment corresponding to the logical address is invalid, update a dirty table using the physical address of the memory segment; and

use the dirty table to perform a garbage collection operation, wherein invalid memory segments are erased without being relocated.