# US 2011/0238886 A1 · Garbage collection schemes for index block

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

- Number: US 2011/0238886 A1
- Document ID: US20110238886A1
- Status: Published application
- Kind: A1
- Application number: 12/729,556
- Filed: 2010-03-23
- Published: 2011-09-29
- Earliest claimed: 2010-03-23
- Assignees: Apple Inc.
- Inventors: Daniel J. Post; Vadim Khmelnitsky
- Web page: https://patentgrep.com/patent/US20110238886A1

## CPC

- G06F 12/0246: {in block erasable memory, e.g. flash memory}
- G06F 2212/1032: Reliability improvement, data loss prevention, degraded operation etc
- G06F 2212/7201: Logical to physical mapping or translation of blocks or pages
- G06F 2212/7205: Cleaning, compaction, garbage collection, erase control
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Systems and methods are provided for handling uncorrectable errors that may occur during garbage collection of an index page or block in non-volatile memory.

## Claims

### Claim 1

A method for performing garbage collection of an index block, the index block including index pages that store logical-to-physical mappings of data pages, the method comprising:
determining that an index page has an uncorrectable error during garbage collection of the index block, the uncorrectable error preventing the logical-to-physical mapping contained in the index page from being reconstructed in a new index block;
accessing a data structure in volatile memory to determine if the data structure contains the logical-to-physical mapping of the index page; and
if the data structure has the logical-to-physical mapping of the index page, reconstructing the index page using the logical-to-physical mapping from the data structure in a new index block.

### Claim 2 (depends on 1)

The method of claim 1, wherein if the data structure does not have the logical-to-physical mapping of the index page, performing a restore operation to obtain the logical-to-physical mapping of the index page; and
using the logical-to-physical mapping obtained from the restore operation to reconstruct the index page in the new index block.

### Claim 3 (depends on 2)

The method of claim 2, wherein the restore operation is a reboot operation.

### Claim 4 (depends on 2)

The method of claim 2, wherein the restore operation is a page specific restore operation or a block restore operation.

### Claim 5 (depends on 1)

The method of claim 1, wherein the data structure is a tree that stores physical addresses of pages in a compressed form.

### Claim 6 (depends on 1)

The method of claim 1, wherein the determining comprises:
determining the index page number of the index page;
translating the index page number into a logical address by taking the product of the index page number and an index page ratio; and
using the logical address to access at least one node in the data structure, the at least one node potentially containing the logical-to-physical mapping of the index page.

### Claim 7 (depends on 1)

The method of claim 1, wherein the data structure is a tree data structure, and wherein the determining comprises performing an exhaustive search of the tree data structure to locate the logical-to-physical mapping of the index page.

### Claim 8

A memory interface for accessing a non-volatile memory, the non-volatile memory comprising index blocks, each index block comprising index pages that map logical-to-physical addresses of data pages, the memory interface comprising:
a bus controller for communicating with the non-volatile memory; and
control circuitry operative to direct the bus controller to perform a garbage collection operation on an index block, the control circuitry further operative to:
determine which index pages in the index block are valid index pages;
for a valid index page, determine whether a data structure held in volatile memory has the logical-to-physical mappings of the valid index page;
if the data structure has the logical-to-physical mappings of the valid index page, reconstruct the valid index page in a new index block using the logical-to-physical mappings from the data structure.

### Claim 9 (depends on 8)

The memory interface of claim 8, wherein the control circuitry is operative to:
if the data structure does not have the logical-to-physical mapping of the valid index page, determine if the valid index page can be read; and
if the valid index page can be read, reconstruct the valid index page in the new index block.

### Claim 10 (depends on 9)

The memory interface of claim 9, wherein if the valid index page cannot be read, perform a restore operation to obtain the logical-to-physical mapping of the index page; and
use the logical-to-physical mapping obtained from the restore operation to reconstruct the index page in the new index block.

### Claim 11 (depends on 9)

The memory interface of claim 9, wherein the data structure includes a tree of a logical-to-physical mapping.

### Claim 12 (depends on 10)

The method of claim 10, wherein the restore operation is a reboot operation.

### Claim 13 (depends on 10)

The method of claim 10, wherein the restore operation is a page specific restore operation or a block restore operation.

### Claim 14

A method for performing garbage collection of an index block, the index block including index pages that store logical-to-physical mappings of data pages, the method comprising:
determining a number of valid index pages in a first index block;
determining, based on the number of valid index pages, whether to reconstruct the valid index pages by first accessing a tree data structure held in volatile memory or to reconstruct the valid index pages by first reading data in the valid index pages.

### Claim 15 (depends on 14)

The method of claim 14, further comprising reconstructing the valid index pages by first accessing the tree structure if the number of valid index pages is less than or equal to a predetermined number of valid index pages.

### Claim 16 (depends on 14)

The method of claim 14, further comprising reconstructing the valid index pages by first reading data in the valid index pages if the number of valid index pages is greater than the predetermined number of index pages.

### Claim 17 (depends on 14)

The method of claim 14, wherein the data structure is a tree data structure holding physical addresses of pages in a compressed form.

### Claim 18 (depends on 14)

The method of claim 14, wherein the determination whether to reconstruct by first accessing the data structure or by first reading the valid index pages is performance determination.
