# US 12,222,857 B2 · Memory system and information processing system

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

- Number: US 12,222,857 B2
- Document ID: US12222857B2
- Status: Granted
- Kind: B2
- Application number: 18/457,672
- Filed: 2023-08-29
- Published: 2023-12-14
- Granted: 2025-02-11
- Earliest claimed: 2020-10-12
- Assignees: Kioxia Corporation
- Applicants: Kioxia Corporation
- Inventors: Yuki Sasaki; Shinichi Kanno; Takahiro Kurita
- Web page: https://patentgrep.com/patent/US12222857B2

## CPC

- G06F 12/0246: {in block erasable memory, e.g. flash memory}
- G06F 12/0207: {with multidimensional access, e.g. row/column, matrix}
- G06F 12/1009: using page tables, e.g. page table structures
- G06F 2212/651: Multi-level translation tables
- G06F 2212/7201: Logical to physical mapping or translation of blocks or pages
- G06F 2212/7209: Validity control, e.g. using flags, time stamps or sequence numbers
- Y02D 10/00: Energy efficient computing, e.g. low power processors, power management or thermal management
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- Y02D: CLIMATE CHANGE MITIGATION TECHNOLOGIES IN INFORMATION AND COMMUNICATION TECHNOLOGIES [ICT], I.E. INFORMATION AND COMMUNICATION TECHNOLOGIES AIMING AT THE REDUCTION OF THEIR OWN ENERGY USE

## Abstract

According to one embodiment, a memory system includes a non-volatile memory and a data map configured to manage validity of data written in the non-volatile memory. The data map includes a plurality of first fragment tables corresponding to a first hierarchy and a second fragment table corresponding to a second hierarchy higher than the first hierarchy. Each of the first fragment tables is used to manage the validity of each data having a predetermined size written in a range of physical address in the non-volatile memory allocated to the first fragment table. The second fragment table is used for each of the first fragment tables to manage reference destination information for referencing the first fragment table.

## Claims

### Claim 1

A memory system connectable to a host, comprising:
a non-volatile memory; and
a controller configured to:
manage a data map for managing validity of data written in the non-volatile memory; and
update the data map when receiving a command for invalidating data written in the non-volatile memory,
wherein the data map has a hierarchical structure including at least a first hierarchy and a second hierarchy higher than the first hierarchy, and includes a plurality of first fragment tables corresponding to the first hierarchy and a second fragment table corresponding to the second hierarchy,
the plurality of first fragment tables respectively correspond to a plurality of first ranges of physical address of the non-volatile memory and each have a first number of entries,
each of the first number of entries of each of the plurality of first fragment tables has information indicating the validity of data having a first size written within each of the plurality of first ranges of physical address of the non-volatile memory corresponding to the each of the plurality of first fragment tables,
the second fragment table is used to manage reference destination information for referencing each of the plurality of first fragment tables,
the reference destination information has a plurality pieces of address information, each of the plurality pieces of address information is an address where each of the plurality of first fragment tables is stored, and
the controller is further configured to,
when all of a plurality pieces of data written within one of the plurality of first ranges of physical address of the non-volatile memory corresponding to one of the plurality of first fragment tables are invalidated, set invalidity in an entry of the second fragment table corresponding to the one of the plurality of first fragment tables.

### Claim 2 (depends on 1)

The memory system according to claim 1,
wherein the second fragment table
is used to manage the reference destination information when valid data and invalid data are mixed in the plurality pieces of data written within one of the first ranges, and
is used to collectively manage the validity of the plurality pieces of data when all of the plurality pieces of data written within one of the first ranges is valid or invalid.

### Claim 3 (depends on 1)

The memory system according to claim 1,
wherein the second fragment table is one of a plurality of second fragment tables, and the data map further includes a third fragment table corresponding to a third hierarchy higher than the second hierarchy, and
the third fragment table is used for each of the plurality of second fragment tables to manage reference destination information for referencing each of the plurality of second fragment tables.

### Claim 4 (depends on 1)

The memory system according to claim 1, further comprising:
an address translation table configured to manage a correspondence between a logical address used by the host to access the memory system and a physical address of the non-volatile memory,
wherein the address translation table has a hierarchical structure including a plurality of hierarchies, and includes a plurality of fourth fragment tables corresponding to the hierarchies, and
each of the plurality of fourth fragment tables in the address translation table has the same data structure as each of the plurality of first fragment tables and the second fragment table.

### Claim 5 (depends on 4)

The memory system according to claim 4, wherein the first number is N, the number of the data having the first size whose validity is managed in an entry of each of the plurality of first fragment tables is M, and M=y×N{circumflex over ( )}x is satisfied, where x is an integer of 0 or larger, y is an integer of 1 or larger and smaller than N, or a reciprocal of an integer of 1 or larger and smaller than N.

### Claim 6 (depends on 5)

The memory system according to claim 5, wherein the M is a power of the N.

### Claim 7 (depends on 5)

The memory system according to claim 5, wherein the M corresponds to a calculation bit width in the memory system.

### Claim 8 (depends on 4)

The memory system according to claim 4, wherein the number of hierarchies of the data map is smaller than the number of hierarchies of the address translation table.

### Claim 9 (depends on 1)

The memory system according to claim 1, wherein the controller is further configured to perform a garbage collection using the data map.

### Claim 10 (depends on 1)

The memory system according to claim 1, wherein
the second fragment table corresponds to a second range of physical address of the non-volatile memory,
the second range of physical address of the non-volatile memory includes the plurality of first ranges of physical address of the non-volatile memory,
each of the plurality of first ranges of physical address of the non-volatile memory is managed by each of the plurality of first fragment tables, and
the controller is further configured to discard the plurality of first fragment tables when data written in the second range of physical address of the non-volatile memory is invalid.

### Claim 11

An information processing system comprising:
a host; and
a memory system connected to the host,
the memory system including a non-volatile memory,
wherein the host is configured to:
manage a data map for managing validity of data written in the non-volatile memory; and
update the data map when receiving a command for invalidating data written in the non-volatile memory,
the data map has a hierarchical structure including at least a first hierarchy and a second hierarchy higher than the first hierarchy, and includes a plurality of first fragment tables corresponding to the first hierarchy and a second fragment table corresponding to the second hierarchy,
the plurality of first fragment tables respectively correspond to a plurality of first ranges of physical address of the non-volatile memory and each have a first number of entries,
each of the first number of entries of each of the plurality of first fragment tables has information indicating the validity of data having a first size written within each of the plurality of first ranges of physical address of the non-volatile memory corresponding to the each of the plurality of first fragment tables,
the second fragment table is used to manage reference destination information for referencing each of the plurality of first fragment tables,
the reference destination information has a plurality pieces of address information, each of the plurality pieces of address information is an address where each of the plurality of first fragment tables is stored, and
the host is further configured to,
when all of a plurality pieces of data written within one of the plurality of first ranges of physical address of the non-volatile memory corresponding to one of the plurality of first fragment tables are invalidated, set invalidity in an entry of the second fragment table corresponding to the one of the plurality of first fragment tables.

### Claim 12 (depends on 11)

The information processing system according to claim 11,
wherein the second fragment table
is used to manage the reference destination information when valid data and invalid data are mixed in the plurality pieces of data written within one of the first ranges, and
is used to collectively manage the validity of the plurality pieces of data when all of the plurality pieces of data written within one of the first ranges is valid or invalid.

### Claim 13 (depends on 11)

The information processing system according to claim 11,
wherein the second fragment table is one of a plurality of second fragment tables, and the data map further includes a third fragment table corresponding to a third hierarchy higher than the second hierarchy, and
the third fragment table is used for each of the plurality of second fragment tables to manage reference destination information for referencing each of the plurality of second fragment tables.

### Claim 14 (depends on 11)

The information processing system according to claim 11,
wherein the host further includes an address translation table configured to manage a correspondence between a logical address used by the host to access the memory system and a physical address of the non-volatile memory,
the address translation table has a hierarchical structure including a plurality of hierarchies, and includes a plurality of fourth fragment tables corresponding to the hierarchies, and
each of the plurality of fourth fragment tables in the address translation table has the same data structure as each of the plurality of first fragment tables and the second fragment table.

### Claim 15 (depends on 14)

The information processing system according to claim 14, wherein the first number is N, the number of the data having the first size whose validity is managed in an entry of each of the plurality of first fragment tables is M, and M=y×N{circumflex over ( )}x is satisfied, where x is an integer of 0 or larger, y is an integer of 1 or larger and smaller than N, or a reciprocal of an integer of 1 or larger and smaller than N.

### Claim 16 (depends on 15)

The information processing system according to claim 15, wherein the M is a power of the N.

### Claim 17 (depends on 11)

The information processing system according to claim 11, wherein the host is further configured to perform a garbage collection using the data map.

### Claim 18 (depends on 15)

The information processing system according to claim 15, wherein the M corresponds to a calculation bit width in the memory system.

### Claim 19 (depends on 14)

The information processing system according to claim 14, wherein the number of hierarchies of the data map is smaller than the number of hierarchies of the address translation table.

### Claim 20 (depends on 11)

The information processing system according to claim 11, wherein
the second fragment table corresponds to a second range of physical address of the non-volatile memory,
the second range of physical address of the non-volatile memory includes the plurality of first ranges of physical address of the non-volatile memory,
each of the plurality of first ranges of physical address of the non-volatile memory is managed by each of the plurality of first fragment tables, and
the host is further configured to discard the plurality of first fragment tables when data written in the second range of physical address of the non-volatile memory is invalid.