Reclaiming data storage capacity in flash memory systems

• US 7,558,905 B2
• Filed: 05/08/2006
• Issued: 07/07/2009
• Est. Priority Date: 08/03/2005
• Status: Active Grant

• Current Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Original Assignee: SanDisk Corporation (Western Digital Corporation)
• Inventors: Sinclair, Alan W., Wright, Barry
• Primary Examiner(s): Thomas; Shane M
• Application Number:
  US11/382,235
• Publication Number:
  US 20070033330A1
• Time in Patent Office: 1,156 Days
• Field of Search: 711/103, 711/154, 707/206, 365/185.33
• US Class Current: 711/103
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 16/1847 specifically adapted to static storage, e.g. adapted to flash memory or SSD
• CPC Class Codes: G06F 2212/7202 Allocation control and policies
• CPC Class Codes: G06F 2212/7205 Cleaning, compaction, garbage collection, erase control
• CPC Class Codes: G06F 3/0605 by facilitating the interaction with a user or administrator
• CPC Class Codes: G06F 3/0608 Saving storage space on storage systems
• CPC Class Codes: G06F 3/0613 in relation to throughput
• CPC Class Codes: G06F 3/064 Management of blocks
• CPC Class Codes: G06F 3/0643 Management of files
• CPC Class Codes: G06F 3/0644 Management of space entities, e.g. partitions, extents, pools
• 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/0483 comprising cells having several storage transistors connected in series
• CPC Class Codes: G11C 16/102 External programming circuits, e.g. EPROM programmers; In-circuit programming or reprogramming; EPROM emulators

Abstract

Host system data files are written directly to a large erase block flash memory system with a unique identification of each file and offsets of data within the file but without the use of any intermediate logical addresses or a virtual address space for the memory. Directory information of where the files are stored in the memory is maintained within the memory system by its controller, rather than by the host. A type of memory block is selected to receive additional data of a file that depends upon the types of blocks into which data of the file have already been written. Blocks containing data are selected for reclaiming any unused capacity therefrom by a process that selects blocks in order starting with those containing the least amount of valid data.

Claims

1. A reprogrammable non-volatile memory system, comprising:

blocks of non-volatile memory cells characterized by being erased prior to rewriting data therein, and

a controller functionally connected with the blocks and that operates to select a block having a portion of its storage capacity not occupied by valid data to be reclaimed for use to store valid data on the basis of a combination of a relative amount of valid data stored and a relative amount of erased capacity remaining in individual ones of at least a plurality of the blocks, and then causes the valid data of the selected block to be copied to another block, wherein the controller further operates to select the block to be reclaimed on the basis of no obsolete data being contained in individual ones of the at least a plurality of the blocks.

2. The memory system of claim 1, wherein the controller further operates to select the block to be reclaimed on the basis of the least amount of valid data stored in individual ones of the at least a plurality of the blocks.

3. The memory system of claim 1, wherein the controller further operates to select the block to be reclaimed on the basis of the least amount of erased capacity remaining in individual ones of the at least a plurality of the blocks for the storage of data therein.

4. The memory system of claim 1, wherein the controller further operates to select the block to be reclaimed by comparing the amounts of valid data stored in some of the at least a plurality of the blocks by a pre-set relationship between the amounts of valid data and erased capacity of others of the at least a plurality of blocks.

5. A reprogrammable non-volatile memory system, comprising:

an array of non-volatile memory cells organized into blocks of memory cells that are simultaneously erasable, and

a controller operably connected with the array that operates to;

maintain a first list including any blocks that individually contain an amount of valid data plus obsolete data but without erased data storage capacity,

determine whether one or more blocks exist on the first list and, if so, identify a first block from the first list that has the least amount of valid data of the blocks thereon,

maintain a second list including any blocks that individually contain an amount of valid data plus some erased data storage capacity,

determine whether one or more blocks exist on the second list and, if so, identify a second block from the second list that has the least amount of valid data of the blocks thereon,

select either the first or second block on the basis of the amount of valid data contained in them after adjusting the amount of valid data in the second block for the amount of erased data storage capacity in the second block, and

copy the valid data from the selected block into another block, and

thereafter erase the selected block.