# US 2019/0317700 A1 · Recovery of validity data for a data storage system

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

- Number: US 2019/0317700 A1
- Document ID: US20190317700A1
- Status: Published application
- Kind: A1
- Application number: 16/455,569
- Filed: 2019-06-27
- Published: 2019-10-17
- Earliest claimed: 2016-12-30
- Assignees: Western Digital Technologies, Inc.
- Applicants: Western Digital Technologies, Inc.
- Inventors: Caesar Cheuk-Chow CHEUNG; Haining LIU; Subhash Balakrishna PILLAI
- Web page: https://patentgrep.com/patent/US20190317700A1

## CPC

- G06F 12/1009: using page tables, e.g. page table structures
- G06F 3/0604: {Improving or facilitating administration, e.g. storage management}
- G06F 3/0631: {by allocating resources to storage systems}
- G06F 3/0679: {Non-volatile semiconductor memory device, e.g. flash memory, one time programmable memory [OTP]}
- G06F 12/0246: {in block erasable memory, e.g. flash memory}
- G06F 2212/1008: Correctness of operation, e.g. memory ordering
- G06F 2212/1056: Simplification
- G06F 2212/202: Non-volatile memory
- G06F 2212/657: Virtual address space management
- 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
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

The subject technology provides for recovering a validity table for a data storage system. A set of logical addresses in a mapping table is partitioned into subsets of logical addresses. Each of the subsets of logical addresses is assigned to respective processor cores in the data storage system. Each of the processor cores is configured to check each logical address of the assigned subset of logical addresses in the mapping table for a valid physical address mapped to the logical address, for each valid physical address mapped to a logical address of the assigned subset of logical addresses, increment a validity count in a local validity table associated with a blockset of the non-volatile memory corresponding to the valid physical address, and update validity counts in a global validity table associated with respective blocksets of the non-volatile memory with the validity counts in the local validity table.

## Claims

### Claim 1

A machine-implemented method for a data storage system, comprising:
partitioning a set of logical addresses in a mapping table into a plurality of subsets of logical addresses, wherein the mapping table maps logical addresses of the set of logical addresses to respective physical addresses of a memory;
verifying each logical address in the plurality of subsets of logical addresses for a valid physical address mapped to the logical address;
for each valid physical address mapped to a logical address of the plurality of subsets of logical addresses, incrementing a validity count in a local validity table associated with a blockset of the memory corresponding to the valid physical address; and
updating validity counts in a global validity table associated with respective blocksets of the memory with the validity counts in the local validity table, wherein the global validity table is different from the local validity table, and the global validity table exists concurrently with the local validity table.

### Claim 2 (depends on 1)

The machine-implemented method of claim 1, comprising:
assigning each of the plurality of subsets of logical addresses to a respective processor core in the data storage system,
wherein a number of partitions of the logical addresses corresponds to a number of processor cores, and
wherein the machine-implemented method comprises: determining a number of available processor cores in the data storage system, wherein the number of processor cores is the number of available processor cores.

### Claim 3 (depends on 1)

The machine-implemented method of claim 1,
wherein the mapping table is indexed by the set of logical addresses arranged sequentially, and
wherein the machine-implemented method comprises: identifying a respective starting index and a respective ending index from the set of logical addresses corresponding to a respective subset of logical addresses assigned to each processor core of the data storage system.

### Claim 4 (depends on 1)

The machine-implemented method of claim 1, wherein the memory comprises a plurality of memory devices, and wherein each of the blocksets comprises a respective physical block from a corresponding one of the plurality of memory devices.

### Claim 5 (depends on 4)

The machine-implemented method of claim 4, wherein each physical address identifies a physical data unit, and wherein each physical block comprises a plurality of physical data units.

### Claim 6 (depends on 1)

The machine-implemented method of claim 1, comprising detecting a prior abnormal shutdown of the data storage system, wherein the partitioning is performed in response to detecting the prior abnormal shutdown.

### Claim 7

A data storage system comprising:
means for partitioning a set of logical addresses in a mapping table into a plurality of subsets of logical addresses, wherein the mapping table is configured to map logical addresses of the set of logical addresses to respective physical addresses of a memory;
means for verifying each logical address in the plurality of subsets of logical addresses for a valid physical address mapped to the logical address;
for each valid physical address mapped to a logical address of the plurality of subsets of logical addresses, means for incrementing a validity count in a local validity table associated with a blockset of the memory corresponding to the valid physical address; and
means for updating validity counts in a global validity table associated with respective blocksets of the memory with the validity counts in the local validity table, wherein the global validity table is different from the local validity table, and the global validity table exists concurrently with the local validity table.

### Claim 8 (depends on 7)

The data storage system of claim 7, comprising:
means for assigning each of the plurality of subsets of logical addresses to a respective processor core in the data storage system,
wherein a number of partitions of the logical addresses corresponds to a number of processor cores, and wherein the data storage system comprises: means for determining a number of available processor cores in the data storage system, wherein the number of processor cores is the number of available processor cores.

### Claim 9 (depends on 7)

The data storage system of claim 7, comprising:
means for indexing the mapping table based on the set of logical addresses arranged sequentially; and
means for identifying a respective starting index and a respective ending index from the set of logical addresses corresponding to the respective subset of logical addresses assigned to each processor core.

### Claim 10 (depends on 7)

The data storage system of claim 7, wherein the memory comprises a plurality of memory devices, and wherein each of the blocksets comprises a respective physical block from one of a plurality of memory devices.

### Claim 11 (depends on 10)

The data storage system of claim 10, wherein each physical address is configured to identify a physical data unit, and wherein each physical block comprises a plurality of physical data units.

### Claim 12 (depends on 7)

The data storage system of claim 7, comprising means for detecting a prior abnormal shutdown of the data storage system, wherein the means for partitioning is configured to perform partitioning the set of logical addresses in response to detecting the prior abnormal shutdown.

### Claim 13 (depends on 7)

The data storage system of claim 7, comprising processor cores, wherein one of the processor cores is configured to:
accumulate the validity counts from the respective local validity tables; and
update the validity counts in the global validity table associated with respective blocksets of the memory with the accumulated validity counts.

### Claim 14

A data storage system, comprising:
a memory; and
a controller coupled to the memory, wherein the controller is configured to:
partition a set of logical addresses in a mapping table into a plurality of subsets of logical addresses, wherein the mapping table is configured to map logical addresses of the set of logical addresses to respective physical addresses of the memory;
check each logical address in the plurality of subsets of logical addresses for a valid physical address mapped to the logical address;
for each valid physical address mapped to a logical address of the plurality of subsets of logical addresses, increment a validity count in a local validity table associated with a blockset of the memory corresponding to the valid physical address; and
update validity counts in a global validity table associated with respective blocksets of the memory with the validity counts in the local validity table, wherein the global validity table is different from the local validity table, and the global validity table exists concurrently with the local validity table.

### Claim 15 (depends on 14)

The data storage system of claim 14, wherein the controller is configured to:
assign each of the plurality of subsets of logical addresses to a respective processor core in the data storage system,
wherein a number of partitions of the logical addresses corresponds to a number of processor cores, wherein the controller is configured to determine a number of available processor cores in the data storage system, and wherein the number of processor cores is the number of available processor cores.

### Claim 16 (depends on 14)

The data storage system of claim 14, wherein the controller is configured to:
index the mapping table using the set of logical addresses arranged sequentially; and
identify a respective starting index and a respective ending index from the set of logical addresses corresponding to the respective subset of logical addresses assigned to each processor core.

### Claim 17 (depends on 14)

The data storage system of claim 14, wherein the memory comprises a plurality of memory devices, and wherein each of the blocksets comprises a respective physical block from one of a plurality of memory devices.

### Claim 18 (depends on 17)

The data storage system of claim 17, wherein each physical address is configured to identify a physical data unit, and wherein each physical block comprises a plurality of physical data units.

### Claim 19 (depends on 14)

The data storage system of claim 14, wherein the controller is configured to:
detect a prior abnormal shutdown of the data storage system; and
partition the set of logical addresses in response to detecting the prior abnormal shutdown.

### Claim 20 (depends on 14)

The data storage system of claim 14, wherein the controller comprises processor cores, and wherein one of the processor cores is configured to:
accumulate the validity counts from the respective local validity tables; and
update the validity counts in the global validity table associated with respective blocksets of the memory with the accumulated validity counts.
