Memory device with pointer structure to map logical to physical addresses

• US 6,839,826 B2
• Filed: 02/06/2002
• Issued: 01/04/2005
• Est. Priority Date: 02/06/2002
• Status: Expired due to Term

• Current Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Original Assignee: SanDisk Corporation (Western Digital Corporation)
• Inventors: Cernea, Raul-Adrian
• Primary Examiner(s): NGUYEN, THAN VINH
• Application Number:
  US10/071,795
• Publication Number:
  US 20030149856A1
• Time in Patent Office: 1,063 Days
• Field of Search: 711/103, 711202-207
• US Class Current: 711/202
• 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
• CPC Class Codes: G06F 3/0614 Improving the reliability of storage systems
• CPC Class Codes: G06F 3/064 Management of blocks
• CPC Class Codes: G06F 3/0679 Non-volatile semiconductor memory device, e.g. flash memory, one time programmable memory [OTP]
• CPC Class Codes: G11C 15/00 Digital stores in which information comprising one or more characteristic parts is written into the store and in which information is read-out by searching for one or more of these characteristic parts, i.e. associative or content-addressed stores

Abstract

A pointer structure on the storage unit of a non-volatile memory maintains a correspondence between the physical and logical address. The controller and storage unit transfer data on the basis of logical sector addresses with the conversion between the physical and logical addresses being performed on the storage unit. The pointer contains a correspondence between a logical sector address and the physical address of current data as well as maintaining one or more previous correspondences between the logical address and the physical addresses at which old data is stored. New and old data can be kept in parallel up to a certain point. When combined with background erase, performance is improved. In an exemplary embodiment, the pointer structure is one or more independent non-volatile sub-arrays, each with its own row decoder. Each pointer has a flag to indicate if it is active in addition to storing the current correspondence between a logical address and a physical address and one or more previous correspondences. When new data is written, it is written to an available, empty memory sector and the pointer is concurrently updated. Defective sectors can be removed from the pool of available sectors in a row redundancy scheme. A random, binary, or other search technique can be used to find the available erased sectors.

Claims

1. A non-volatile memory system comprising:

a controller for externally transferring data identified by logical sector addresses; and

a memory connected to the controller, comprising;

an array comprised of a plurality of sectors, wherein each sector contains a plurality of data storage elements and is identified by a physical address; and

a pointer structure storing correspondences between logical sector addresses and physical sector addresses, wherein the pointer structure concurrently maintains a first correspondence between a logical sector address and a first physical sector address at which currently valid data identified by the logical sector address is stored and a second correspondence between the logical sector address and a second distinct physical sector address at which previously valid data identified by the logical sector address has been stored.

2. The non-volatile memory system of claim 1, wherein said correspondences are stored in non-volatile storage elements of the pointer structure.

3. The non-volatile memory system of claim 2, further comprising read and write circuitry coupled to the array and the pointer structure, wherein the array and the pointer structure have distinct decoder structures.

4. The non-volatile memory system of claim 2, wherein said correspondences are stored in binary non-volatile storage elements and the data storage elements are multi-state.

5. The non-volatile memory system of claim 1, wherein said controller and said memory are formed on separate integrated circuits.

6. The non-volatile memory system of claim 1, wherein memory concurrently maintains the currently valid data identified by the logical sector address and the previously valid data identified by the logical sector address.

7. The non-volatile memory system of claim 1, wherein the controller can access the previously valid data identified by the logical sector address in response to a command.

8. The non-volatile memory system of claim 1, said memory comprising:

write circuitry coupled to the memory array and the pointer structure, wherein during a write process new data corresponding to a specified logical sector address is written into the array at a new physical sector address of the array concurrently with a new correspondence between the specified logical sector address and the new physical sector address being stored in the pointer structure.

9. The non-volatile memory system of claim 8, said memory further comprising:

erase circuitry coupled to the array whereby said previously valid data is erasable in a background erase process.

10. The integrated circuit of claim 8, wherein each sector of the array has an associated flag bit, the integrated circuit further comprising:

a determination circuit connected to the write circuitry and the array, whereby an available sector is determined for the new physical sector address based on the associated flag bits.

11. An integrated circuit comprising:

a non-volatile memory array comprised of a plurality of sectors, each containing a plurality of data storage elements and each identified by a physical address;

an interface connected to the memory array for transferring externally to the integrated circuit data identified by logical sector addresses; and

a pointer connected to the interface to receive said logical sector addresses, said pointer storing correspondences between the logical sector addresses and physical sector addresses, wherein the pointer structure concurrently maintains a first correspondence between a first logical sector address and a first physical sector address at which currently valid data identified by the first logical sector address is stored and a second correspondence between the first logical sector address and a second distinct physical sector address at which previously valid data identified by the first logical sector address has been stored.

12. The integrated circuit of claim 11, wherein said pointer is comprised of non-volatile storage elements.

13. The integrated circuit of claim 12, wherein said data storage elements are multi-state storage units and the storage elements of the pointer are binary storage elements.

14. The integrated circuit of claim 12, further comprising read and write circuitry coupled to the array and the pointer structure, wherein the array and the pointer structure have distinct decoder structures.

15. The integrated circuit of claim 11, wherein said memory array concurrently maintains the currently valid data identified by the first logical sector address and the previously valid data identified by the first logical sector address.

16. The integrated circuit of claim 11, said memory further comprising:

write circuitry coupled to the memory array and the pointer, wherein during a write process new data corresponding to a specified logical sector address is written into the array at a new physical sector address of the memory array concurrently with a new correspondence between the specified logical sector address and the new physical sector address being stored in the pointer.

17. The integrated circuit of claim 16, further comprising:

erase circuitry coupled to the array whereby said previously valid data is erasable in a background erase process.

18. The integrated circuit of claim 16, wherein each sector of the memory array has an associated flag bit, the integrated circuit further comprising:

a determination circuit connected to the write circuitry and the memory array, whereby an available sector is determined for the new physical sector address based on the associated flag bits.

19. The non-volatile memory system of claim 11, wherein the previously valid data identified by the first logical sector is accessible in response to an external command.

20. A method of operating a memory system comprising a controller and a memory, the memory including a pointer structure and an array comprised of a plurality of sectors, wherein each sector is identified by a physical address and contains a plurality of non-volatile data storage elements, the method comprising:

receiving at the controller unit from a host a first data set and a logical sector address whereby the host identifies the first data set;

transferring the first data set and the logical sector address from the controller to the memory;

storing the first data set at a first physical sector address of the array;

storing a first correspondence between the logical sector address and the first physical sector address in the pointer structure;

subsequent to said storing the first data set and said storing the first correspondence, receiving at the controller from the host a second data set to be stored at the logical sector address;

transferring the second data set from the controller to the memory;

storing the second data set at a second physical sector address of the array; and

storing a second correspondence between the logical sector address and the second physical sector address in the pointer structure, wherein the memory retains the first data set at the first physical sector address and the first correspondence in the pointer structure subsequent to said storing the second data set and said storing the second correspondence.

21. The method of claim 20, wherein said first correspondence and said first data set are stored concurrently, and wherein said second correspondence and said second data set are stored concurrently.

22. The method of claim 20, further comprising:

subsequent to said storing the second data set and the second correspondence, erasing the first physical sector.

23. The method of claim 22, wherein said erasing is performed in a background process.

24. The method of claim 20, wherein the pointer structure is non-volatile.

25. The method of claim 20, further comprising:

subsequent to said storing the second data set and the second correspondence, receiving at the controller a request from the host for data stored at the logical sector address;

providing the request from the controller to the memory in terms of the logical sector address; and

providing the second data set from the memory to the controller in response to the memory receiving the request in terms of the logical sector address.

26. The method of claim 20, further comprising:

subsequent to said storing the second data set and the second correspondence, receiving at the memory a request for data stored at the first physical sector address; and

providing the first data set from the memory to the controller in response to the memory receiving the request.

27. The method of claim 20, further comprising:

prior to said storing the first data set, selecting the first physical sector address from a set of available sector addresses; and

prior to said storing the second data set, selecting the second physical sector address from the set of available sector addresses.

28. The method of claim 20, wherein said set of available sector addresses corresponds to only good physical sectors.

29. A method of operating a non-volatile memory comprising a pointer structure and an array having a plurality of sectors each containing a plurality of storage element, the method comprising:

writing a first data set accessible external to the memory by a logical sector address into a first physical sector;

storing a first correspondence between the logical sector address and the first physical sector in the pointer structure;

subsequent to said writing the first data set and storing the first correspondence, writing a second data set accessible external to the memory by the logical sector address into a second physical sector; and

storing a second correspondence between the logical sector address and the second physical sector in the pointer structure, wherein the first data set is retained in the first physical sector address and the first correspondence is retained in the pointer subsequent to writing the second data set and storing the second correspondence.

30. The method of claim 29, wherein said first correspondence is stored concurrently with said writing the first data set, and wherein said second correspondence is stored concurrently with said writing the second data set.

31. The method of claim 29, further comprising:

subsequent to said writing the second data set and said storing the second correspondence, erasing the first physical sector.

32. The method of claim 31, wherein said erasing is performed in a background process.

33. The method of claim 29, wherein the pointer structure is non-volatile.

34. The method of claim 29, further comprising:

subsequent to said writing the second data set and said storing the second correspondence, receiving at the memory an external request for data stored at the logical sector address; and

providing the second data set externally to the memory in response to the request.

35. The method of claim 29, further comprising:

subsequent to said writing the second data set and said storing the second correspondence, receiving at the memory an external request for data stored at the first physical sector; and

providing the first data set externally to the memory in response to the request.

36. The method of claim 29, further comprising:

prior to said writing the first data set, selecting the first physical sector from a set of available sectors; and

prior to said writing the second data set, selecting the second physical sector from the set of available sectors.

37. The method of claim 29, wherein said set of available sectors contains only good sectors.

38. A method of operating a non-volatile memory system comprising a controller and a memory, wherein data is stored in the memory based on physical address, the method comprising:

transferring data between a host and the controller based on a logical sector addresses;

transferring data between the controller and the memory based on the logical sector address;

converting on the memory the logical sector address into a corresponding physical sector address; and

accessing data stored in the memory at the corresponding physical address.