# US 7,610,437 B2 · Data consolidation and garbage collection in direct data file storage memories

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 7,610,437 B2
- Document ID: US7610437B2
- Status: Granted
- Kind: B2
- Application number: 11/461,997
- Filed: 2006-08-02
- Published: 2007-02-08
- Granted: 2009-10-27
- Earliest claimed: 2005-08-03
- Assignees: SanDisk Corporation
- Inventors: Alan W. Sinclair; Barry Wright
- Web page: https://patentgrep.com/patent/US7610437B2

## CPC

- G06F 12/0246: {in block erasable memory, e.g. flash memory}
- G06F 3/0605: {by facilitating the interaction with a user or administrator}
- G06F 3/0608: {Saving storage space on storage systems}
- G06F 3/0613: {in relation to throughput}
- G06F 3/064: {Management of blocks}
- G06F 3/0643: {Management of files}
- G06F 3/0644: {Management of space entities, e.g. partitions, extents, pools}
- G06F 3/0652: {Erasing, e.g. deleting, data cleaning, moving of data to a wastebasket}
- G06F 3/0679: {Non-volatile semiconductor memory device, e.g. flash memory, one time programmable memory [OTP]}
- G06F 16/1847: {specifically adapted to static storage, e.g. adapted to flash memory or SSD}
- G06F 2212/7202: Allocation control and policies
- G06F 2212/7205: Cleaning, compaction, garbage collection, erase control
- G11C 16/0483: {comprising cells having several storage transistors connected in series}
- G11C 16/102: {External programming circuits, e.g. EPROM programmers; In-circuit programming or reprogramming; EPROM emulators}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- G11C: STATIC STORES (semiconductor memory devices H10B)

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

## Claims

### Claim 1

For a re-programmable non-volatile memory system having a plurality of blocks of memory cells that are individually erased prior to data being written therein and that operates with an inventory of a minimum number of erased blocks ready to have data stored therein, a method of operation, comprising:
receiving data of files logically addressed by unique file identifiers and offsets within the files, wherein said unique file identifiers and offsets within the files are used by the memory system for logically addressing the files,
storing the received data of a first file as pages within one or more of the erased blocks that only partially fill a first one of the erased blocks, thereby leaving erased data storage capacity within the first partially filled block, and storing the received data of a second file as pages within one or more of the erased blocks that only partially fill a second one of the erased blocks, thereby leaving erased data storage capacity within the second partially filled block, and
postponing consolidating valid data from the partially filled first and second blocks into another one of the erased blocks until at least the inventory of the number of erased blocks is deemed insufficient to maintain the minimum number.

### Claim 2 (depends on 1)

The method of claim 1, additionally comprising, in response to a need to provide another erased block, consolidating valid data from the first file and second file into another one of the erased blocks and thereafter erasing at least one of the first and second blocks, thereby to add another erased block to the inventory.

### Claim 3 (depends on 1)

The method of claim 1, additionally comprising, in response to receiving a command to delete the first file, marking all the data of the first file in at least the first partially filled block as obsolete, thereby eliminating any valid data from the first file in at least the first partially filled block, whereby no consolidation of data of the first file in the first partially filled block is necessary.

### Claim 4 (depends on 1)

The method of claim 1, additionally comprising maintaining a plurality of records that identify groups of variable amounts of data making up the first file, wherein the individual groups have both contiguous logical offset addresses and contiguous physical addresses of data within the group.

### Claim 5 (depends on 1)

The method of claim 1, wherein the unique file identifiers and offsets within the files are stored in the memory system.

### Claim 6 (depends on 5)

The method of claim 5, wherein the unique file identifier of the first file and offset within the first file are maintained within the memory system without the use of any intermediate logical addresses or a virtual address space for the memory system.

### Claim 7

A method of operation of a re-programmable non-volatile memory system having a plurality of blocks of memory cells that are individually erased prior to data being written therein and which receive data having logical addresses of unique file identifiers and offsets within the individual files, wherein:
valid data from a first group of two or more blocks partially programmed with data of two or more files are occasionally consolidated into another block, said first group of two or more partially programmed blocks containing erased data storage capacity and no obsolete data,
blocks containing valid data from a second group of one or more blocks that also contain obsolete data are occasionally garbage collected,
only one of the data consolidation or garbage collection is carried out at one time, and
priority is given to garbage collection over data consolidation.

### Claim 8 (depends on 7)

The method of claim 7, wherein,
in response to at least some of the data of the second group of one or more blocks becoming obsolete, any remaining valid data in the second group of one or more blocks are copied into a third group of one or more blocks,
in response to the first group of the two or more partially programmed blocks having erased storage capacity, valid data are copied from the first group of the two or more partially programmed blocks into a fourth group of one or more blocks, and
priority is given to the above-recited copying of valid data from the second group of one or more blocks into the third group of one or more blocks over the above-recited copying of valid data from the first group of two or more partially programmed blocks into the fourth group of one or more blocks.

### Claim 9 (depends on 8)

The method of claim 8, wherein at least one of the third or fourth group of one or more blocks includes an erased block into which the copied data are written.

### Claim 10 (depends on 8)

The method of claim 8, wherein data copied into the third or fourth group are those of a first or second file, and at least one of the third or fourth group contains data of a third file different from the first and second files at the time the copied data are copied.

### Claim 11 (depends on 8)

The method of claim 8, additionally wherein a plurality of records that identify groups of variable amounts of data making up the individual files are maintained, wherein the groups individually have both contiguous logical offset addresses and contiguous physical addresses of data within the group.