Fast LBA/PBA table rebuild by skipping read of metadata of LBA bin that is not mapped

Patent metadata

Field	Value
Publication number	US-12517819-B2
Application number	US-202217987553-A
Country	US
Kind code	B2
Filing date	Nov 15, 2022
Priority date	Nov 15, 2022
Publication date	Jan 6, 2026
Grant date	Jan 6, 2026

Abstract

A method is described. The method includes constructing a bitmap having a first dimension organized into bins of logical block addresses (LBA bins) and a second dimension organized into bins of physical block addresses (PBA bins). Coordinates of the bitmap indicate whether respective physical blocks of non volatile memory within one or more SSDs that fall within a particular PBA bin are being mapped to by an LBA that falls within a particular one of the LBA bins. The method includes using the bitmap during a rebuild of an LBA bin of an LBA/PBA table to avoid reading meta data for physical blocks that are not mapped to by an LBA that falls within the LBA bin.

First claim

The invention claimed is:

1 . An apparatus, comprising:
logic circuitry to:
construct a bitmap having a first dimension organized into bins of logical block addresses (LBA bins) and a second dimension organized into bins of physical block addresses (PBA bins), wherein coordinates of the bitmap indicate whether respective physical blocks of non-volatile memory fall within a particular PBA bin are being mapped to by a logical block address (LBA) that falls within a particular one of the LBA bins,
use the bitmap, during a rebuild of an LBA bin of an LBA/PBA table, to avoid reading meta data, stored in the non-volatile memory, for physical blocks that are not mapped to by an LBA that falls within the LBA bin, and
update the bitmap when a change in the LBA/PBA table results in all physical blocks, in the non-volatile memory, whose respective PBAs fall within a first particular PBA bin to not be mapped to by an LBA that falls within a first particular LBA bin, the update to change a value of the bitmap located in a coordinate of the bitmap that corresponds to the first particular PBA bin and the first particular LBA bin.

2 . The apparatus of claim 1 wherein the logic circuitry is to store the bitmap in the non-volatile memory.

3 . The apparatus of claim 1 wherein the logic circuitry is to store information, for the bitmap, identifies which LBAs are mapping to the respective physical blocks, in the non-volatile memory, whose respective PBAs fall within a particular one of the PBA bins.

4 . The apparatus of claim 3 wherein the information is contained in one or more non-volatile memory pages for each PBA bin.

5 . The apparatus of claim 1 wherein an LBA bin is defined as one or more bands within an SSD.

6 . An apparatus, comprising:
logic circuitry to:
construct a bitmap having a first dimension organized into bins of logical block addresses (LBA bins) and a second dimension organized into bins of physical block addresses (PBA bins), wherein coordinates of the bitmap indicate whether respective physical blocks of non-volatile memory fall within a particular PBA bin are being mapped to by a logical block address (LBA) that falls within a particular one of the LBA bins,
use the bitmap, during a rebuild of an LBA bin of an LBA/PBA table, to avoid reading meta data, stored in the non-volatile memory, for physical blocks that are not mapped to by an LBA that falls within the LBA bin, and
update the bitmap when a change in the LBA/PBA table results in one physical block amongst all physical blocks, in the non-volatile memory, whose respective PBAs fall within a first particular PBA bin to be mapped to by an LBA that falls within a first particular LBA bin, the update to change a value of the bitmap located in a coordinate of the bitmap that corresponds to the first particular PBA bin and the first particular LBA bin.

7 . A computing system, comprising:
a plurality of processors; a main memory controller coupled to the plurality of processors; a main memory coupled to the main memory controller, the main memory to store an LBA/PBA table; an I/O control hub coupled to the main memory controller; a plurality of SSDs coupled to the I/O control hub; and program code stored on a storage medium, the program code to cause at least one of the processors to perform a method, comprising:
constructing a bitmap having a first dimension organized into bins of logical block addresses (LBA bins) and a second dimension organized into bins of physical block addresses (PBA bins), wherein coordinates of the bitmap indicate whether respective physical blocks of memory chips within at least one of the SSDs that fall within a particular PBA bin are being mapped to by a logical block address (LBA) that falls within a particular one of the LBA bins,
using the bitmap, during a rebuild of an LBA bin of an LBA/PBA table, to avoid reading meta data, stored in the non-volatile memory, for physical blocks that are not mapped to by an LBA that falls within the LBA bin, and
updating the bitmap when a change in the LBA/PBA table results in all physical blocks, in the non-volatile memory, whose respective PBAs fall within a first particular PBA bin to not be mapped to by an LBA that falls within a first particular LBA bin, the updating to change a value of the bitmap located in a coordinate of the bitmap that corresponds to the first particular PBA bin and the first particular LBA bin.

8 . The computing system of claim 7 wherein the method further comprises storing the bitmap in an SSD of the plurality of SSDs.

9 . The computing system of claim 7 wherein the method further comprises storing information, for the bitmap, identifies which LBAs are mapping to the respective physical blocks, in the non-volatile memory, whose respective PBAs fall within a particular one of the PBA bins.

10 . The computing system of claim 9 wherein the information is contained in one or more non-volatile memory pages for each PBA bin.

11 . The computing system of claim 7 wherein the PBA bins are bins of host side PBAs and the plurality of SSDs internally translate the host side PBAs to actual PBAs of blocks within the SSDs.

12 . A computing system, comprising:
a plurality of processors; a main memory controller coupled to the plurality of processors; a main memory coupled to the main memory controller, the main memory to store an LBA/PBA table; an I/O control hub coupled to the main memory controller; a plurality of SSDs coupled to the I/O control hub; and program code stored on a storage medium, the program code to cause at least one of the processors to perform a method, comprising:
constructing a bitmap having a first dimension organized into bins of logical block addresses (LBA bins) and a second dimension organized into bins of physical block addresses (PBA bins), wherein coordinates of the bitmap indicate whether respective physical blocks of memory chips within at least one of the SSDs that fall within a particular PBA bin are being mapped to by a logical block address (LBA) that falls within a particular one of the LBA bins,
using the bitmap, during a rebuild of an LBA bin of an LBA/PBA table, to avoid reading meta data, stored in the non-volatile memory, for physical blocks that are not mapped to by an LBA that falls within the LBA bin, and
updating the bitmap when a change in the LBA/PBA table results in one physical block amongst all physical blocks, in the non-volatile memory, whose respective PBAs fall within a first particular PBA bin to be mapped to by an LBA that falls within a first particular LBA bin, the updating to change a value of the bitmap located in a coordinate of the bitmap that corresponds to the first particular PBA bin and the first particular LBA bin.

13 . A non-transitory machine readable storage medium containing program code that when processed by at least one processor causes the at least one processor to perform a method, comprising:
constructing a bitmap having a first dimension organized into bins of logical block addresses (LBA bins) and a second dimension organized into bins of physical block addresses (PBA bins), wherein coordinates of the bitmap indicate whether respective physical blocks of non volatile memory within one or more SSDs that fall within a particular PBA bin are being mapped to by a logical block address (LBA) that falls within a particular one of the LBA bins; using the bitmap, during a rebuild of an LBA bin of an LBA/PBA table, to avoid reading meta data, stored in the non-volatile memory, for physical blocks that are not mapped to by an LBA that falls within the LBA bin; and updating the bitmap when a change

Assignees

• Sk Hynix Nand Product Solutions Corp

Inventors

• Harris James R
• Walker Benjamin
• Kozlowski Mateusz
• Karkra Kapil
• Paszkiewicz Artur

Classifications

• G06F2212/7201

  Logical to physical mapping or translation of blocks or pages · CPC title

• G06F2212/1024

  Latency reduction · CPC title

• G06F2212/1028

  Power efficiency · CPC title

• G06F2212/7208

  Multiple device management, e.g. distributing data over multiple flash devices · CPC title

• G06F12/0246 Primary

  in block erasable memory, e.g. flash memory · CPC title