# US 11,307,995 B1 · Storage device with geometry emulation based on division programming and decoupled NAND maintenance

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

- Number: US 11,307,995 B1
- Document ID: US11307995B1
- Status: Granted
- Kind: B1
- Application number: 17/506,598
- Filed: 2021-10-20
- Granted: 2022-04-19
- Earliest claimed: 2014-09-09
- Assignees: Radian Memory Systems, Inc.
- Applicants: Radian Memory Systems, Inc.
- Inventors: Robert Lercari; Alan Chen; Mike Jadon; Craig Robertson; Andrey V. Kuzmin
- Web page: https://patentgrep.com/patent/US11307995B1

## CPC

- G06F 12/1009: using page tables, e.g. page table structures
- G06F 3/0616: {in relation to life time, e.g. increasing Mean Time Between Failures [MTBF]}
- G06F 3/064: {Management of blocks}
- G06F 3/0688: {Non-volatile semiconductor memory arrays}
- G06F 12/0207: {with multidimensional access, e.g. row/column, matrix}
- G06F 12/0246: {in block erasable memory, e.g. flash memory}
- G06F 12/109: for multiple virtual address spaces, e.g. segmentation (G06F12/1036 takes precedence)
- G06F 3/0659: {Command handling arrangements, e.g. command buffers, queues, command scheduling}
- G06F 3/0662: {Virtualisation aspects}
- G06F 2212/1016: Performance improvement
- G06F 2212/7201: Logical to physical mapping or translation of blocks or pages
- G06F 2212/7202: Allocation control and policies
- G06F 2212/7205: Cleaning, compaction, garbage collection, erase control
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

This disclosure provides techniques hierarchical address virtualization within a memory controller and configurable block device allocation. By performing address translation only at select hierarchical levels, a memory controller can be designed to have predictable I/O latency, with brief or otherwise negligible logical-to-physical address translation time. In one embodiment, address transition may be implemented entirely with logical gates and look-up tables of a memory controller integrated circuit, without requiring processor cycles. The disclosed virtualization scheme also provides for flexibility in customizing the configuration of virtual storage devices, to present nearly any desired configuration to a host or client.

## Claims

### Claim 1

A storage device comprising:
flash memory having physical erase units; and
circuitry to, for each of incoming data write requests:
derive, from incoming address information, a first address portion, a second address portion and a third address portion,
identify an addressed block device from the first address portion,
identify an addressed segment within the addressed block device from the second address portion, and
identify an addressed storage location within the addressed segment from the third address portion,
wherein the circuitry is to use a division operation on at least one of the incoming address information or information derived therefrom, to identify a logical erase unit within the addressed segment, and
wherein the circuitry is to identify one of the physical erase units that corresponds to the identified logical erase unit, and
program associated data into the identified one of the physical erase units;
wherein the storage device also comprises circuitry to:
maintain metadata for each physical erase unit which contains data, the metadata representing a time since data was programmed in the respective erase unit,
copy data from a first one of the physical erase units for which the maintained metadata meets at least one criterion to a second one of the physical erase units, and
remap a correspondence of a logical erase unit which corresponds to the first one of the physical erase units to instead correspond to the second one of the physical erase units.

### Claim 2 (depends on 1)

The storage device of claim 1 wherein:
in connection with the copy of data from the first one of the physical erase units to the second one of the physical erase units, the storage device is to copy all valid data from the first one of the physical erase units to the second one of the physical erase units; and
the storage device is to generate the metadata for the second one of the physical erase units so as to correspond to the copy of the valid data from the first one of the physical erase units to the second one of the physical erase units.

### Claim 3 (depends on 2)

The storage device of claim 2 wherein the storage device is further to automatically erase the first one of the physical erase units in connection with the copy of all valid data from the first one of the physical erase units to the second one of the physical erase units.

### Claim 4 (depends on 3)

The storage device of claim 3 wherein:
the flash memory comprises multiple planes; and
the storage device is to, in connection with the automatic erase, automatically and concurrently erase a physical erase unit in each of the multiple planes.

### Claim 5 (depends on 4)

The storage device of claim 4 wherein:
for at least one of the multiple planes, the storage device is further to maintain metadata for each given physical erase unit which represents a number of times the given physical erase unit has been erased; and
in connection with the erase of the first one of the physical erase units, the storage device is to update the metadata for the first one of the physical erase units to reflect an additional instance that the first one of the physical erase units has been erased.

### Claim 6 (depends on 1)

The storage device of claim 1 wherein:
the storage device further comprises circuitry to compare the metadata to at least one threshold and, responsive to detection that specific metadata has satisfied the at least one threshold, to transmit information to a host wherein such transmitted information conveys address information for data stored at a physical storage location associated with the specific metadata; and
the copy of data by the storage device from the first one of the physical erase units to the second one of the physical erase units is dependent on the transmitted information.

### Claim 7 (depends on 1)

The storage device of claim 1 wherein the storage device is also to detect a failure condition of the physical erase units and is to remap each logical erase unit which corresponds to one of the physical erase units for which the failure condition is detected to instead correspond to one of the physical erase units for which the failure condition has not been detected and is to utilize the remapped correspondence to service one or more incoming data access requests.

### Claim 8 (depends on 1)

The storage device of claim 1 wherein:
each said circuitry comprises at least one processor; and
the storage device further comprises instructions stored on at least one physical non-transitory storage medium, said instructions when executed to control the at least one processor so as to operate as special purpose circuitry.

### Claim 9 (depends on 8)

The storage device of claim 8 wherein the storage device is to store the metadata in nonvolatile memory which is resident on said storage device, said nonvolatile memory being one of said flash memory or another memory.

### Claim 10 (depends on 1)

The storage device of claim 1 wherein:
the storage device is to receive a maintenance request from a host which addresses a block device and a segment within the block device addressed by the maintenance request; and
the storage device comprises circuitry to erase, in association with execution of the maintenance request, one or more of the physical erase units which are mapped to the segment addressed by the maintenance request.

### Claim 11 (depends on 10)

The storage device of claim 10 wherein the storage device is further to track for each given physical erase unit second metadata representing a number of times the given erase unit has been erased and is to update, in connection with execution of the maintenance request, the second metadata for each physical erase unit that is erased in association with execution of the maintenance request.

### Claim 12 (depends on 11)

The storage device of claim 11 wherein the storage device further comprises circuitry to selectively transmit to the host information which is dependent upon the second metadata.

### Claim 13 (depends on 11)

The storage device of claim 11 wherein:
the flash memory comprises multiple planes; and
the storage device is to, in connection with execution of the maintenance request, automatically and concurrently erase a physical erase unit in each of the multiple planes.

### Claim 14 (depends on 1)

The storage device of claim 1 wherein:
the flash memory is to have block devices, including the addressed block device; and
the storage device comprises circuitry to, in connection with an incoming data read request, identify a block device, retrieve a look-up table specific to the block device addressed by the incoming data read request, and identify a physical storage location in the flash memory dependent on the look-up table.

### Claim 15 (depends on 1)

The storage device of claim 1 wherein:
the storage device further comprises circuitry to track additional metadata for the addressed segment, where said additional metadata indicates an extent to which memory comprising at least one of the physical erase units mapped to the addressed segment can continue to receive additional write data without being erased; and
the storage device further comprises circuitry to transmit information to a host dependent on said tracked additional metadata.

### Claim 16 (depends on 1)

The storage device of claim 1 wherein:
the storage device further comprises circuitry to compare the metadata to at least one threshold and, responsive to detection that specific metadata has satisfied the at least one threshold, to transmit information to a host wherein such transmitted information conveys address information for data stored at a physical storage location associated with the specific metadata;
the copy of data by the storage device from the first one of the physical erase units to the second one of the physical erase units is dependent on such transmitted information and receipt from the host of a request to copy; and
the request to copy is to designate destination address information corresponding to the second physical one of the physical erase units, wherein the storage device is to identify from the destination address information a destination block device and an addressed segment within the destination block device; and
the second one of the physical erase units corresponds to the addressed segment within the destination block device.

### Claim 17 (depends on 16)

The storage device of claim 16 wherein the storage device is to identify from the destination address information a destination logical erase unit and is to select the second one of the physical erase units in dependence on the identified destination logical erase unit.

### Claim 18 (depends on 1)

The storage device of claim 1 wherein the storage device is to store information identifying a number of structures in the flash memory and is to transmit the information identifying the number of structures to a host, wherein the host is to issue at least one request to the storage device in which the at least one request is dependent on the information transmitted to the host identifying the number of structures, and wherein the storage device comprises circuitry to fulfill the at least one request by issuing commands to the flash memory that each operate on a quantum of flash memory which is dependent on the information transmitted to the host identifying the number of structures.

### Claim 19 (depends on 18)

The storage device of claim 18 wherein the information transmitted to the host identifying the number of structures identifies an amount of flash memory that is to be erased as a unit.

### Claim 20 (depends on 1)

The storage device of claim 1 wherein the addressed segment corresponds to an integer number of physical erase units for which a failure condition has not been detected, and the third address portion specifies a location within a sequential range of locations that correspond to the integer number of physical erase units.

### Claim 21 (depends on 1)

The storage device of claim 1 wherein the storage device further comprises circuitry to compare the metadata to at least one threshold and, responsive to detection that specific metadata has satisfied the at least one threshold, to transmit information to a host wherein such transmitted information conveys address information for data stored in a physical storage location associated with the specific metadata prior to the copy of the data to the second one of the physical erase units.

### Claim 22 (depends on 1)

The storage device of claim 1 wherein:
the storage device further comprises circuitry to receive a query, issued by a host, and, for each such query,
derive a first address portion, a second address portion and a third address portion,
identify an addressed block device from the first address portion,
identify an addressed segment within the block device addressed by the query from the second address portion, and
identify an addressed storage location within the segment addressed by the query from the third address portion; and
the circuitry to receive the query is further to
use a division operation to identify a logical erase unit within the segment addressed by the query,
identify one of the physical erase units from the logical erase unit identified from the query,
identify the metadata representing the time since data was programmed into the one of the physical erase units identified from the query, and
transmit information to the host dependent on the identified metadata.

### Claim 23 (depends on 1)

The storage device of claim 1 wherein the storage device further comprises circuitry to receive a query, issued by a host, and, responsive to the query, to compare the metadata to at least one threshold, to identify specific metadata, and transmit information to the host wherein such transmitted information conveys address information for data stored at a physical storage location associated with the specific metadata.

### Claim 24 (depends on 1)

The storage device of claim 1 wherein:
the metadata is first metadata;
the flash memory is to have block devices, including the addressed block device; and
the storage device further comprises circuitry to
store second metadata on an independent basis for each one of the block devices, wherein the second metadata represents an erase count of associated physical memory space, and
receive a query, issued by a host, wherein said query is specific to one of the block devices, and responsive to the query, identify specific second metadata, associated with the specified one of the block devices, and transmit information to the host dependent on the specific second metadata.

### Claim 25 (depends on 1)

The storage device of claim 1 wherein:
the metadata is first metadata;
the flash memory is to have block devices, including the addressed block device; and
the storage device further comprises circuitry to
store second metadata on an independent basis for each one of the block devices, wherein the stored second metadata represents an erase count of associated physical memory space, and
compare the second metadata to at least one threshold, and
responsive to detection that specific second metadata has satisfied the at least one threshold, transmit information to a host wherein such transmitted information conveys address information for data stored at a physical storage location associated with the specific second metadata.

### Claim 26 (depends on 1)

The storage device of claim 1 wherein:
the flash memory comprises multiple planes; and
the storage device is to, for each one of a set of the incoming data access requests having sequential addressing, write data accompanying the set of incoming data access requests concurrently into respective ones of the multiple planes.

### Claim 27 (depends on 1)

The storage device of claim 1 wherein the division operation is applied to subdivide the third address portion into respective first and second bit fields.

### Claim 28 (depends on 1)

The storage device of claim 1 wherein:
for each of the incoming data write requests, the circuitry is to write data into a specific physical storage location within the identified one of the physical erase units and is to identify an address value corresponding to the specific physical storage location;
the storage device further comprises circuitry to transmit the address value to a host;
the storage device is also to receive incoming data read requests, each accompanied by an associated read address; and
for each of the incoming data read requests which is directed to the data storage at the specific physical storage location, the associated read address is dependent on the address value which was transmitted to the host.

### Claim 29

A storage device comprising:
flash memory having physical erase units; and
circuitry to, for address information provided in association with each of incoming data write requests:
derive from the incoming address information a first address portion, a second address portion and a third address portion,
identify an addressed block device from the first address portion,
identify an addressed segment within the addressed block device from the second address portion, and
identify an addressed storage location within the addressed segment from the third address portion,
wherein the circuitry is to subdivide the address information into bit fields, is to identify from a first one of the bit fields a logical erase unit within the addressed segment, and is to identify the addressed storage location dependent on the second one of the bit fields, and
wherein the circuitry is to identify one of the physical erase units that corresponds to the identified logical erase unit, and
program associated data into the identified one of the physical erase units at a location selected dependent on the addressed storage location;
wherein the storage device also comprises circuitry to:
maintain metadata for each physical erase unit which contains valid data, the metadata representing a time since data was programmed in the respective erase unit,
copy data from a first one of the physical erase units for which the maintained metadata meets at least one criterion to a second one of the physical erase units, and, in association with said copy of the data, generate the metadata for the second one of the physical erase units so as to correspond to the copy of the data from the first one of the physical erase units to the second one of the physical erase units; and
remap a correspondence of a logical erase unit which corresponds to the first one of the physical erase units to instead correspond to the second one of the physical erase units.

### Claim 30

A storage device comprising:
flash memory, the flash memory to have one or more block devices at a hierarchically-superior level, segments within each of the block devices at a hierarchically-intermediate level, and addressable storage locations within each of the segments at a hierarchically-inferior level, each segment including a mutually exclusive set of one or more logical erase units that each map to a physical erase unit, each segment being associated with only one of the block devices, each logical erase unit being associated with only one of the segments; and
circuitry to, for each of incoming data write requests:
derive, from incoming address information, a first address portion, a second address portion and a third address portion,
identify an addressed one of the one or more block devices from the first address portion,
identify an addressed one of the segments within the addressed block device from the second address portion, and
identify an addressed storage location within the addressed one of the segments from the third address portion,
wherein the circuitry is to use a division operation on at least one of the incoming address information or information derived from the incoming address information, to identify a logical erase unit within the addressed one of the segments, and
wherein the circuitry is to identify one of the physical erase units that corresponds to the identified logical erase unit, and
program associated data into the identified one of the physical erase units;
wherein the storage device also comprises circuitry to:
maintain metadata for each physical erase unit which contains data, the metadata representing a time since data was programmed in the respective erase unit,
copy data from a first one of the physical erase units for which the maintained metadata meets at least one criterion to a second one of the physical erase units, and, in association with said copy of the data, generate the metadata for the second one of the physical erase units so as to correspond to the copy of the data; and
remap a correspondence of a logical erase unit which corresponds to the first one of the physical erase units to instead correspond to the second one of the physical erase units; and
wherein the storage device is to generate the metadata for the second one of the physical erase units so as to correspond to a time that the data was copied from the first one of the physical erase units to the second one of the physical erase units.