Method and apparatus for performing erase operations transparent to a solid state storage system

• US 5,953,737 A
• Filed: 07/07/1998
• Issued: 09/14/1999
• Est. Priority Date: 03/31/1997
• Status: Expired due to Term

• Current Assignee: Micron Technology, Inc.
• Original Assignee: Lexar Media Incorporated (Micron Technology, Inc.)
• Inventors: Estakhri, Petro, Iman, Berhanu
• Primary Examiner(s): BRAGDON, REGINALD GLENWOOD
• Application Number:
  US09/111,414
• Time in Patent Office: 434 Days
• Field of Search: 711/5, 711/103, 711/156, 711/158, 711/172, 711/171
• US Class Current: 711/103
• CPC Class Codes: G06F 11/1068 in sector programmable memories, e.g. flash disk G06F11/1072 takes precedence
• CPC Class Codes: G06F 12/023 Free address space management
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 3/061 Improving I/O performance
• CPC Class Codes: G06F 3/0613 in relation to throughput
• CPC Class Codes: G06F 3/064 Management of blocks
• CPC Class Codes: G06F 3/0652 Erasing, e.g. deleting, data cleaning, moving of data to a wastebasket
• CPC Class Codes: G06F 3/0679 Non-volatile semiconductor memory device, e.g. flash memory, one time programmable memory [OTP]
• CPC Class Codes: G11C 16/08 Address circuits; Decoders; Word-line control circuits
• CPC Class Codes: G11C 16/102 External programming circuits, e.g. EPROM programmers; In-circuit programming or reprogramming; EPROM emulators
• CPC Class Codes: G11C 29/765 in solid state disks
• CPC Class Codes: G11C 29/82 for EEPROMs

Abstract

In a digital system having a host, a controller device and at least one nonvolatile memory integrated circuit, such as a flash memory chip, a method and apparatus is disclosed for storing digital information, provided by the host, in the nonvolatile memory under the direction of the controller in an efficient manner so as to significantly improve system performance. The nonvolatile memory is organized into sequentially-numbered blocks. Each nonvolatile integrated circuit is assigned a predetermined number of sequential blocks and when a free block is solicited for storage of digital information provided by the host, the nonvolatile integrated circuit rather than the entire nonvolatile memory is searched for the free block. When the information stored in a block is being updated by the host, the nonvolatile integrated circuit assigned to that block is excluded from the search for the free block. Moreover, the nonvolatile integrated circuit having the greatest number of free blocks is used for searching of the free block and storing of the host-provided information to allow for equal use of the nonvolatile integrated circuits.

Claims

1. A method of storing information in a digital information storage system having a controller device, a memory unit having a plurality of nonvolatile memory devices, and a host for storing digital information in the memory unit under the direction of the controller, the memory unit being organized into blocks, each block identified by the controller using a logical block address (LBA) and being identified within the memory unit by a corresponding physical block address (PBA), comprising:

(a) assigning a predetermined number of blocks to each of the nonvolatile memory devices, each block being identified by an LBA;

(b) finding a number of free memory device blocks that are available for storage of digital information;

(c) receiving a write command including host-provided data and host-provided location information for identifying the host-provided data and storing the same in the memory unit;

(d) developing a current LBA using the host-provided location information;

(e) determining which of the nonvolatile memory devices has the greatest number of free memory device blocks;

(f) finding a free block available for storage of information within the nonvolatile memory device having the greatest number of free memory device blocks, the free block being identified by a free PBA; and

(g) storing the host-provided data in the free block identified by the free PBA within the memory unit,

wherein searching the entire memory unit to find the location of a free block is reduced to searching only within a nonvolatile memory device having the greatest number of free blocks.

2. A method of storing information as recited in claim 1 wherein the predetermined number of blocks assigned to each nonvolatile memory device is in sequential order.

3. A method of storing information as recited in claim 2 further including a step of checking for completion of an erase operation and if the erase operation is not complete, awaiting completion thereof.

4. A method of storing information as recited in claim 1 further including a step of determining whether or not any blocks within the memory unit require erasing and if so, starting an erase operation of at least one of those blocks.

5. A method of storing information as recited in claim 1 further including a step of determining whether or not the block identified by the current LBA was written to prior to the last time it was erased.

6. A method of storing information as recited in claim 1 further including a step of determining which nonvolatile memory device is assigned to the current LBA.

7. A method of storing information as recited in claim 5 or 6 wherein if the host-provided location was previously written to, excluding the nonvolatile memory device identified by the host-provided location from the determining step in step (e) such that storage of the host-provided data within the excluded nonvolatile memory device is avoided.

8. A method of storing information as recited in claim 1 further including a step of storing each of the number of free memory device blocks in a free block storage location.

9. A method of storing information as recited in claim 1 wherein the block identified by the current LBA is organized into one more sectors.

10. A method of storing information as recited in claim 9 wherein if the current LBA is associated with a block within the memory unit that is being updated, storing the host-provided data.

11. A method of storing information as recited in claims 9 or 10 wherein if less than all of the sectors of the current LBA block are being updated, moving the sectors of the current LBA block which are not updated to the block within the memory unit identified by a destination PBA.

12. A method of storing information as recited in claim 1 further including providing a volatile memory device for storage of a table addressed by the LBAs for storage of corresponding PBAs and storing the free PBA in a location of the table identified by the current LBA.

13. A method of storing information as recited in claim 12 further including providing flag fields for each LBA in the table for providing information regarding the status of blocks within the memory unit.

14. A machine readable storage device encoding instructions for executing the method as recited in claim 1.

15. In a nonvolatile storage system having a controller device coupled to a host and a memory unit having a plurality of nonvolatile memory devices for storage of digital information provided by the host in the memory unit under the direction of the controller, the memory unit being organized into blocks, each block being identified by the controller using a logical block address (LBA) and being identified within the memory unit, by a corresponding physical block address (PBA) developed by the controller, the controller comprising:

a host interface circuit for receiving a write command from the host including host-provided data and a host-provided location information for identifying the host-provided data and storing the same in the memory unit;

a processor circuit for assigning a predetermined number of blocks to each of the nonvolatile memory devices and for maintaining a number of free memory device blocks available for storage of digital information for each nonvolatile memory device, said processor operative to find the nonvolatile memory device having the greatest number of free blocks;

a space manager unit being responsive to said host-provided location information and being operative to develop a current LBA, said space manager unit further being operative to find a free block within the nonvolatile memory device having the greatest number of free blocks, for storage of said host-provided data therein, and for developing a free PBA for identifying the free block; and

a flash interface circuit for storing the host-provided information in the free block identified by the free PBA within the memory unit,

wherein searching the entire memory unit to find the location of a free block is reduced to searching only within a nonvolatile memory device having the greatest number of free blocks thereby increasing the performance of the storage system.

16. In a nonvolatile storage system as recited in claim 15 wherein the processor includes a free block storage space for storing the greatest number of free blocks for each nonvolatile memory device.

17. In a nonvolatile storage system as recited in claim 16 further including flash interface signals for providing coupling of the host-provided data and free PBA between the flash interface circuit and the memory unit.

18. In a nonvolatile storage system as recited in claim 17 wherein said flash interface signals further include control signals, said control signals being developed by the controller for causing one of the nonvolatile memory devices to be erased while information, provided by the host, is being stored in another nonvolatile memory device.

19. In a nonvolatile storage system, as recited in claim 15, wherein said space manager unit includes a volatile memory device for storage of a table addressed by LBAs for storage of corresponding PBAs.

20. In a nonvolatile storage system, as recited in claim 19, further including flash fields for each LBA in said table for maintaining status information for corresponding blocks of the memory unit.