# US 2015/0149692 A1 · Efficient reuse of segments in nonoverwrite storage systems

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

- Number: US 2015/0149692 A1
- Document ID: US20150149692A1
- Status: Published application
- Kind: A1
- Application number: 14/088,265
- Filed: 2013-11-22
- Published: 2015-05-28
- Earliest claimed: 2013-11-22
- Assignees: Apple Inc.
- Applicants: Apple Inc.
- Inventors: Wenguang Wang; John Garvey; Richard Paul Spillane
- Web page: https://patentgrep.com/patent/US20150149692A1

## CPC

- G06F 12/0246: {in block erasable memory, e.g. flash memory}
- G06F 3/06: Digital input from, or digital output to, record carriers {, e.g. RAID, emulated record carriers or networked record carriers}
- G06F 3/0608: {Saving storage space on storage systems}
- G06F 3/0613: {in relation to throughput}
- G06F 3/0619: {in relation to data integrity, e.g. data losses, bit errors}
- G06F 3/0643: {Management of files}
- G06F 3/0679: {Non-volatile semiconductor memory device, e.g. flash memory, one time programmable memory [OTP]}
- G06F 11/14: Error detection or correction of the data by redundancy in operations (error detection or correction of the data by redundancy in hardware G06F11/16)
- G06F 11/1441: {Resetting or repowering}
- G06F 11/2082: {Data synchronisation}
- G06F 12/0253: {Garbage collection, i.e. reclamation of unreferenced memory}
- G06F 11/1471: involving logging of persistent data for recovery
- G06F 2212/7205: Cleaning, compaction, garbage collection, erase control
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A non-overwrite storage system, such as a log-structured file system, that includes a non-volatile storage having multiple storage segments, a volatile storage having an unsafe free segments list (UFSL), and a controller for managing storage resources of the non-volatile storage. The controller can be configured to copy page data from used segment(s) of the non-volatile storage, write the copied page data to free segment(s) of the non-volatile storage, index the UFSL with indications of the used segment(s), and thereafter prevent reuse of the used segment(s) while the indications of the used segment(s) remain indexed in the UFSL. In some implementations, the non-overwrite storage system may be associated with flash storage system, and a flash controller can be configured perform a flush track cache operation to clear the indications of the used segment(s) from the UFSL, to enable reuse of segment(s) that were previously indexed to the UFSL.

## Claims

### Claim 1

A method of managing storage resources for a log-structured file system (LFS), the method comprising:
copying write block data from a plurality of used segments of the LFS;
writing the copied write block data to one or more free segments of the LFS;
indexing an unsafe free segments list (UFSL) with indications of the plurality of used segments after copying the write block data; and
preventing reuse of the plurality of used segments while the indications of the plurality of used segments are indexed in the UFSL.

### Claim 2 (depends on 1)

The method of claim 1, further comprising:
in response to performing a scheduled synchronization operation, clearing the indications of the plurality of used segments from the UFSL; and
reusing at least one of the plurality of used segments that was previously indexed to the UFSL.

### Claim 3 (depends on 2)

The method of claim 2, wherein:
the LFS is a flash storage system; and
the scheduled synchronization operation is a flush track cache operation that is scheduled to occur on a periodic basis to update a block manager of the flash storage system with current storage location information.

### Claim 4 (depends on 2)

The method of claim 2, wherein reusing the at least one of the plurality of used segments which was previously indexed to the UFSL comprises:
writing new write block data to the at least one of the plurality of used segments which was previously indexed to the UFSL; and
updating a block manager with a storage location for the new write block data.

### Claim 5 (depends on 2)

The method of claim 2, wherein performing the scheduled synchronization operation comprises mapping one or more logical storage addresses associated with the copied write block data to one or more physical storage addresses where the copied write block data is stored after writing the copied write block data to the one or more free segments of the LFS.

### Claim 6 (depends on 1)

The method of claim 1, further comprising:
receiving new write block data after indexing the UFSL; and
in response to receiving the new write block data, consulting the UFSL to determine which segments of the LFS are indexed in the UFSL as unavailable segments.

### Claim 7 (depends on 6)

The method of claim 6, further comprising:
identifying one or more free segments of the LFS that are not indexed in the UFSL as unavailable segments; and
writing the received new write block data to the identified one or more free segments of the LFS.

### Claim 8

A method of writing page data in a non-overwrite storage system, the method comprising:
determining a number of required segments for writing the page data in the non-overwrite storage system;
consulting an unsafe free segments list (UFSL) to identify which free segments of the non-overwrite storage system should not be written to;
determining whether sufficient free segments are available for writing the page data in the non-overwrite storage system; and
in response to determining that sufficient free segments are available, writing the page data to data blocks of one or more free segments of the non-overwrite storage system.

### Claim 9 (depends on 8)

The method of claim 8, wherein determining whether sufficient free segments are available, further comprises:
comparing the number of required segments for writing the page data in the non-overwrite storage system to a number of available free segments in the non-overwrite storage system, excluding free segments identified in the UFSL; and
determining whether the number of free segments in the non-overwrite storage system, excluding free segments identified in the UFSL, is equal to or exceeds the number of required segments for writing the page data in the non-overwrite storage system.

### Claim 10 (depends on 8)

The method of claim 8, further comprising:
in response to determining that sufficient free segments are not available for writing the page data in the non-overwrite storage system, performing a synchronization operation to clear the UFSL; and
determining whether sufficient free segments are available for writing the page data in the non-overwrite storage system after performing the synchronization operation.

### Claim 11 (depends on 10)

The method of claim 10, wherein:
the non-overwrite storage system is a flash storage system; and
the synchronization operation is a flush track cache operation that is scheduled to occur on a periodic basis to update a block manager of the flash storage system with current storage location information.

### Claim 12 (depends on 10)

The method of claim 10, wherein in response to performing the synchronization operation and determining that sufficient free segments are available for writing the page data in the non-overwrite storage system, writing the page data to data blocks of one or more free segments of the non-overwrite storage system.

### Claim 13 (depends on 10)

The method of claim 10, further comprising:
in response to performing the synchronization operation and determining that sufficient free segments are available for writing the page data in the non-overwrite storage system,
writing the page data to data blocks of one or more free segments which was previously identified in the UFSL.

### Claim 14 (depends on 10)

The method of claim 10, further comprising:
in response to performing the synchronization operation and determining that sufficient free segments are not available for writing the page data in the non-overwrite storage system, performing a garbage collection operation to free up one or more segments of the non-overwrite storage system;
determining whether sufficient free segments are available for writing the page data in the non-overwrite storage system after performing the garbage collection operation; and
in response to performing the garbage collection operation and determining that sufficient free segments are available for writing the page data in the non-overwrite storage system, writing the page data to data blocks of one or more free segments of the non-overwrite storage system.

### Claim 15

A non-overwrite storage system comprising:
a non-volatile storage component having a plurality of storage segments;
a volatile storage component having an unsafe free segments list (UFSL); and
a controller coupled to the non-volatile storage component and to the volatile storage component, wherein the controller is configured to:
copy page data from one or more used segments of the plurality of storage segments;
write the copied page data to one or more free segments of the plurality of storage segments;
index the UFSL with indications of the one or more used segments after copying the page data; and
prevent reuse of the one or more used segments while the indications of the one or more used segments are indexed in the UFSL.

### Claim 16 (depends on 15)

The non-overwrite storage system of claim 15, wherein the controller is further configured to:
perform a synchronization operation that clears the indications of the one or more used segments from the UFSL; and
reuse at least one of the one or more used segments that was previously indexed to the UFSL.

### Claim 17 (depends on 16)

The non-overwrite storage system of claim 16, wherein:
the non-overwrite storage system is a flash storage system; and
the synchronization operation is a flush track cache operation that is scheduled to occur on a periodic basis to update a block manager of the flash storage system with current storage location information.

### Claim 18 (depends on 16)

The non-overwrite storage system of claim 16, wherein, as part of the reuse, the controller is configured to:
write new page data to the at least one of the one or more used segments which was previously indexed to the UFSL; and
update a block manager with a storage location for the new page data.

### Claim 19 (depends on 15)

The non-overwrite storage system of claim 15, wherein the controller is further configured to:
receive new page data after indexing the UFSL; and
in response to receiving the new page data, consult the UFSL to determine which segments of the non-overwrite storage system are indexed in the UFSL as unavailable segments.

### Claim 20 (depends on 19)

The non-overwrite storage system of claim 19, wherein the controller is further configured to:
identify one or more free segments of the non-overwrite storage system that are not indexed in the UFSL as unavailable segments; and
write the received new page data to the identified one or more free segments of the non-overwrite storage system.
