Patent ID: 12210448

DETAILED DESCRIPTION

Aspects of the present disclosure are directed to virtual indexing in a memory device and, in particular to memory sub-systems that include virtual indexing circuitry. The virtual indexing circuitry can control organization of data entries in a data structure that can be stored within one or more memory resources that are associated with the memory sub-system and the consolidation of multiple such data structures into one or more indices (e.g., virtual indices). A memory sub-system can be a storage system, storage device, a memory module, or a combination of such. An example of a memory sub-system is a storage system such as a solid-state drive (SSD). Examples of storage devices and memory modules are described below in conjunction withFIG.1, et alibi. In general, a host system can utilize a memory sub-system that includes one or more components, such as memory devices that store data. The host system can provide data to be stored at the memory sub-system and can request data to be retrieved from the memory sub-system.

A memory device can be a non-volatile memory device. One example of non-volatile memory devices is a negative-and (NAND) memory device (also known as flash technology). Other examples of non-volatile memory devices are described below in conjunction withFIG.1. A non-volatile memory device is a package of one or more dice. Each die can consist of one or more planes. Planes can be grouped into logic units (LUN). For some types of non-volatile memory devices (e.g., NAND devices), each plane consists of a set of physical blocks. Each block consists of a set of pages. Each page consists of a set of memory cells (“cells”). A cell is an electronic circuit that stores information. A block hereinafter refers to a unit of the memory device used to store data and can include a group of memory cells, a word line group, a word line, or individual memory cells. For some memory devices, blocks (also hereinafter referred to as “memory blocks”) are the smallest area that can be erased. Pages cannot be erased individually, and only whole blocks can be erased.

Each of the memory devices can include one or more arrays of memory cells. Depending on the cell type, a cell can store one or more bits of binary information, and has various logic states that correlate to the number of bits being stored. The logic states can be represented by binary values, such as “0” and “1”, or combinations of such values. There are various types of cells, such as single level cells (SLCs), multi-level cells (MHLCs), triple level cells (TLCs), and quad-level cells (QLCs). For example, a SLC can store one bit of information and has two logic states.

Some NAND memory devices employ a floating-gate architecture in which memory accesses are controlled based on a relative voltage change between the bit line and the word lines. Other examples of NAND memory devices can employ a replacement-gate architecture that can include the use of word line layouts that can allow for charges corresponding to data values to be trapped within memory cells based on properties of the materials used to construct the word lines.

During operation, data is written to, and retrieved from the memory sub-system. Some data are written to persistent memory devices within the memory sub-system for long-term storage, while other data are written to non-persistent memory devices within the memory subsystem for quick, short-term retrieval. Still other data are written to various memory resources (or portions of memory resources) and/or caches of the memory sub-system to assist with performance of operations involving the memory sub-system. For example, various memory resources and/or caches can be utilized during operation of the memory sub-system to provide read caching, write-through caching, write-back caching, and/or write-around caching. In addition, some memory resources and/or caches of the memory sub-system can be allocated to store various tables that are utilized during operation of the memory sub-system. One such example is a logical-to-physical (L2P) table that is used to map logical addresses utilized by a host system to physical addresses of the memory sub-system where data is physically stored. Another such example is a physical valid table (PVT) that is used to record that each logic block address (LBA) written to a physical block (e.g., physical virtual block (VB)) or to a super block (e.g., multiple LUNs) is valid or invalid. An invalid LBA may be unmapped, written to another physical position by a new host write command, or written for the first time by a host write command.

When a garbage collection operation is triggered the garbage collection operation copies all valid LBAs from a source VB to a destination VB. A SSD with DRAM uses physical to LBA (P2L) table and gets the LBA of each physical position of the source VBs. If the physical position of the source VBs is the same with respect to the physical address of the LBA in the L2P table then the LBA is valid. In contrast, if the physical position of the source VBs with respect to the L2P table, the LBA may be considered to be invalid.

However, some mobile device technology features architectures that may not include DRAM (or may include a limited amount of DRAM) to read the L2P table from table blocks due to space constraints associated with mobile device (e.g., smartphone, tablet, phablet, etc.) form factors. In general, when a garbage collection operation is triggered the operation requests that all LBAs from the PVT (e.g., valid and invalid) are read; however, generally the valid LBAs are copied from the source VB to a destination VB. If the LBA is invalid, the read of the L2P table is unnecessary and consumes time and resources available to the memory sub-system. Additionally, some approaches require that closed VBs associated with the PVT are updated as part of performance of a garbage collection operation. For example, after the host writes an LBA to the NAND the PVT of the VB is marked and the L2P table is updated. If the precondition is sequential write, several VB PVT updates result from random write and if the precondition is random write, several VB PVT updates result from both sequential and random write causing overhead in the memory sub-system that may be mitigated utilizing the techniques of the present disclosure.

Aspects of the present disclosure address the above and other deficiencies by recording whether each LBA is valid or invalid in a dedicated index of the memory sub-system. For example, in some embodiments, a L2P table index of a written LBA can be recorded in a physical to index (P2I) table. Once the P2I is full the P2I is dumped to NAND, for example during performance of a media management operation such as a garbage collection operation. Prior to the P2I being full, the L2P table index does not need to be recorded again into the P2I table if the L2P table index has been recorded in the P2I table. For example, embodiments described herein provide that the L2P table index of a LBA written by the host is not recorded into the P2I table again if the LBA (e.g., an indication corresponding to the LBA corresponding to valid data) had previously been recorded in the same P2I table.

When a garbage collection operation is triggered, the L2P table recorded in the P2I table of the source VB can be read one by one. All data in one L2P table can be copied from the source VB to the destination VB. For example, data which physical address belongs to the source VB (e.g., all LBAs that belong to the VB) can be copied to the destination VB and the L2P can be updated at the same time. As such, the possibility that all data in the L2P table in the source VB is invalid or becomes invalid is significantly reduced over previous approaches and methods. Therefore, the present disclosure allows for time and resources spent on reading invalid locations to be reduced and/or minimized. In addition, because the possibility that at least some of the locations are valid, aspects of the present disclosure acknowledge that the use of time and resources is better allocated reducing a quantity of invalid data that is read and therefore seek to improve resource allocation in performance of media management operation over previous methods.

For example, in some embodiments, a closed VB's P2I is not modified reducing overhead for later host writes. Additionally, the L2P table update frequency can be reduced thereby improving performance of the memory sub-system in which aspects of the present disclosure operate. As described in more detail herein, if the source VB is written by sequential writes, the P2I table may have several L2P table indices. If the source VB is written by random write, there can be several LBAs belonging to one L2P table, significantly reducing the number of recorded L2P table indices in comparison to previous approaches.

FIG.1illustrates an example computing system100that includes a memory sub-system110in accordance with some embodiments of the present disclosure. The memory sub-system110can include media, such as one or more volatile memory devices (e.g., memory device140), one or more non-volatile memory devices (e.g., memory device130), or a combination of such.

A memory sub-system110can be a storage device, a memory module, or a hybrid of a storage device and memory module. Examples of a storage device include a solid-state drive (SSD), a flash drive, a universal serial bus (USB) flash drive, an embedded Multi-Media Controller (eMMC) drive, a Universal Flash Storage (UFS) drive, a secure digital (SD) card, and a hard disk drive (HDD). Examples of memory modules include a dual in-line memory module (DIMM), a small outline DIMM (SO-DIMM), and various types of non-volatile dual in-line memory modules (NVDIMMs).

The computing system100can be a computing device such as a desktop computer, laptop computer, server, network server, mobile device, a vehicle (e.g., airplane, drone, train, automobile, or other conveyance), Internet of Things (IoT) enabled device, embedded computer (e.g., one included in a vehicle, industrial equipment, or a networked commercial device), or such computing device that includes memory and a processing device.

The computing system100can include a host system120that is coupled to one or more memory sub-systems110. In some embodiments, the host system120is coupled to different types of memory sub-system110.FIG.1illustrates one example of a host system120coupled to one memory sub-system110. As used herein, “coupled to” or “coupled with” generally refers to a connection between components, which can be an indirect communicative connection or direct communicative connection (e.g., without intervening components), whether wired or wireless, including connections such as electrical, optical, magnetic, and the like.

The host system120can include a processor chipset and a software stack executed by the processor chipset. The processor chipset can include one or more cores, one or more caches, a memory controller (e.g., an SSD controller), and a storage protocol controller (e.g., PCIe controller, SATA controller). The host system120uses the memory sub-system110, for example, to write data to the memory sub-system110and read data from the memory sub-system110.

The host system120can be coupled to the memory sub-system110via a physical host interface. Examples of a physical host interface include, but are not limited to, a serial advanced technology attachment (SATA) interface, a peripheral component interconnect express (PCIe) interface, universal serial bus (USB) interface, Fibre Channel, Serial Attached SCSI (SAS), Small Computer System Interface (SCSI), a double data rate (DDR) memory bus, a dual in-line memory module (DINM) interface (e.g., DIMM socket interface that supports Double Data Rate (DDR)), Open NAND Flash Interface (ONFI), Double Data Rate (DDR), Low Power Double Data Rate (LPDDR), or any other interface. The physical host interface can be used to transmit data between the host system120and the memory sub-system110. The host system120can further utilize an NVM Express (NVMe) interface to access components (e.g., memory devices130) when the memory sub-system110is coupled with the host system120by the PCIe interface. The physical host interface can provide an interface for passing control, address, data, and other signals between the memory sub-system110and the host system120.FIG.1illustrates a memory sub-system110as an example. In general, the host system120can access multiple memory sub-systems via the same communication connection, multiple separate communication connections, and/or a combination of communication connections.

The memory devices130,140can include any combination of the different types of non-volatile memory devices and/or volatile memory devices. The volatile memory devices (e.g., memory device140) can be, but are not limited to, random access memory (RAM), such as dynamic random-access memory (DRAM) and synchronous dynamic random access memory (SDRAM).

Some examples of non-volatile memory devices (e.g., memory device130) include negative-and (NAND) type flash memory and write-in-place memory, such as three-dimensional cross-point (“3D cross-point”) memory device, which is a cross-point array of non-volatile memory cells. A cross-point array of non-volatile memory can perform bit storage based on a change of bulk resistance, in conjunction with a stackable cross-gridded data access array. Additionally, in contrast to many flash-based memories, cross-point non-volatile memory can perform a write in-place operation, where a non-volatile memory cell can be programmed without the non-volatile memory cell being previously erased. NAND type flash memory includes, for example, two-dimensional NAND (2D NAND) and three-dimensional NAND (3D NAND).

Each of the memory devices130,140can include one or more arrays of memory cells. One type of memory cell, for example, single level cells (SLC) can store one bit per cell. Other types of memory cells, such as multi-level cells (MLCs), triple level cells (TLCs), quad-level cells (QLCs), and penta-level cells (PLC) can store multiple bits per cell. In some embodiments, each of the memory devices130can include one or more arrays of memory cells such as SLCs, MLCs, TLCs, QLCs, or any combination of such. In some embodiments, a particular memory device can include an SLC portion, and an MLC portion, a TLC portion, a QLC portion, or a PLC portion of memory cells. The memory cells of the memory devices130can be grouped as pages that can refer to a logical unit of the memory device used to store data. With some types of memory (e.g., NAND), pages can be grouped to form blocks.

Although non-volatile memory components such as three-dimensional cross-point arrays of non-volatile memory cells and NAND type memory (e.g., 2D NAND, 3D NAND) are described, the memory device130can be based on any other type of non-volatile memory or storage device, such as, read-only memory (ROM), phase change memory (PCM), self-selecting memory, other chalcogenide based memories, ferroelectric transistor random-access memory (FeTRAM), ferroelectric random access memory (FeRAM), magneto random access memory (MRAM), Spin Transfer Torque (STT)-MRAM, conductive bridging RAM (CBRAM), resistive random access memory (RRAM), oxide based RRAM (OxRAM), negative-or (NOR) flash memory, and electrically erasable programmable read-only memory (EEPROM).

The memory sub-system controller115(or controller115for simplicity) can communicate with the memory devices130to perform operations such as reading data, writing data, or erasing data at the memory devices130and other such operations. The memory sub-system controller115can include hardware such as one or more integrated circuits and/or discrete components, a buffer memory, or a combination thereof. The hardware can include digital circuitry with dedicated (i.e., hard-coded) logic to perform the operations described herein. The memory sub-system controller115can be a microcontroller, special purpose logic circuitry (e.g., a field programmable gate array (FPGA), an application specific integrated circuit (ASIC), etc.), or other suitable processor.

The memory sub-system controller115can include a processor117(e.g., a processing device) configured to execute instructions stored in a local memory119. In the illustrated example, the local memory119of the memory sub-system controller115includes an embedded memory configured to store instructions for performing various processes, operations, logic flows, and routines that control operation of the memory sub-system110, including handling communications between the memory sub-system110and the host system120.

In some embodiments, the local memory119can include memory registers storing memory pointers, fetched data, etc. The local memory119can also include read-only memory (ROM) for storing micro-code. While the example memory sub-system110inFIG.1has been illustrated as including the memory sub-system controller115, in another embodiment of the present disclosure, a memory sub-system110does not include a memory sub-system controller115, and can instead rely upon external control (e.g., provided by an external host, or by a processor or controller separate from the memory sub-system).

In general, the memory sub-system controller115can receive commands or operations from the host system120and can convert the commands or operations into instructions or appropriate commands to achieve the desired access to the memory device130and/or the memory device140. The memory sub-system controller115can be responsible for other operations such as wear leveling operations, garbage collection operations, error detection and error-correcting code (ECC) operations, encryption operations, caching operations, and address translations between a logical address (e.g., logical block address (LBA), namespace) and a physical address (e.g., physical block address, physical media locations, etc.) that are associated with the memory devices130. The memory sub-system controller115can further include host interface circuitry to communicate with the host system120via the physical host interface. The host interface circuitry can convert the commands received from the host system into command instructions to access the memory device130and/or the memory device140as well as convert responses associated with the memory device130and/or the memory device140into information for the host system120.

The memory sub-system110can also include additional circuitry or components that are not illustrated. In some embodiments, the memory sub-system110can include a cache or buffer (e.g., DRAM) and address circuitry (e.g., a row decoder and a column decoder) that can receive an address from the memory sub-system controller115and decode the address to access the memory device130and/or the memory device140.

In some embodiments, the memory device130includes local media controllers135that operate in conjunction with memory sub-system controller115to execute operations on one or more memory cells of the memory devices130. An external controller (e.g., memory sub-system controller115) can externally manage the memory device130(e.g., perform media management operations on the memory device130). In some embodiments, a memory device130is a managed memory device, which is a raw memory device combined with a local controller (e.g., local controller135) for media management within the same memory device package. An example of a managed memory device is a managed NAND (MNAND) device.

The memory sub-system110can include virtual indexing circuitry113. Although not shown inFIG.1so as to not obfuscate the drawings, the virtual indexing circuitry113can include various circuitry to facilitate recording, in a P2I table, an L2P table index of a written LBA, determining whether the L2P table index of a particular LBA has been previously recorded in the P2I table and, in response to the L2P table index of the particular LBA being previously recorded in the P2I table, refraining from recording the L2P table index of the particular LBA a second time, dumping the P2I table to a NAND when the P2I table is full, and determining whether data written to memory blocks associated with the particular LBA contains valid and/or invalid data. In some embodiments, the virtual indexing circuitry113can include special purpose circuitry in the form of an ASIC, FPGA, state machine, and/or other logic circuitry that can allow the virtual indexing circuitry113to orchestrate and/or perform operations to selectively perform virtual indexing operations for the memory device130and/or the memory device140based on determined valid and invalid data written to memory blocks associated with the LBA.

In some embodiments, the memory sub-system controller115includes at least a portion of the virtual indexing circuitry113. For example, the memory sub-system controller115can include a processor117(processing device) configured to execute instructions stored in local memory119for performing the operations described herein. In some embodiments, the virtual indexing circuitry113is part of the host system110, an application, or an operating system.

In a non-limiting example, an apparatus (e.g., the computing system100) can include virtual indexing circuitry113. The virtual indexing circuitry113can be resident on the memory sub-system110. As used herein, the term “resident on” refers to something that is physically located on a particular component. For example, the virtual indexing circuitry113being “resident on” the memory sub-system110refers to a condition in which the hardware circuitry that comprises the virtual indexing circuitry113is physically located on the memory sub-system110. The term “resident on” can be used interchangeably with other terms such as “deployed on” or “located on,” herein.

The virtual indexing circuitry113can be configured to maintain a table corresponding to L2P mappings of LBAs or a range of LBAs that correspond to data entries written to a plurality of memory blocks. In some embodiments, at least a subset of the plurality of memory blocks comprise virtual memory blocks. As described above, the memory components can be memory dice or memory packages that form at least a portion of the memory device130and/or the memory device140.

The virtual indexing circuitry113can be further configured to maintain a table corresponding to indices that correspond to logical addresses within the table that correspond to the L2P of the LBAs or a range of LBAs. In some embodiments, the indices corresponding to the logical addresses within the table corresponding to the L2P LBAs or the range of LBAs comprise Boolean logical values (e.g., a logical “1” or a logical “0”), although embodiments are not so limited. The table corresponding to the indices (e.g., a P2I table) can include indices that are determined based on a determined ratio of valid data and invalid data entries written to the plurality of memory blocks. As described above, data entries may be marked as invalid when the data entries comprise entries that have been unmapped or have been written to a different memory block than a memory block in which the data entries were previously written. Additionally, the physical address in the L2P table can me marked invalid when the LBA is written for the first time. As such, the invalid data entries can generally comprise data written to at least one memory block among the plurality of memory blocks that does not have a corresponding LBA associated therewith.

In some embodiments, the virtual indexing circuitry113can be further configured to control performance of a media management operation involving one or more of the plurality of memory blocks. In particular, the virtual indexing circuitry113can be configured to refrain from rewriting particular entries in the L2P table that correspond to the LBAs or the range of LBAs whose indices (e.g., the indices corresponding to the ratio of valid data and invalid data entries written to the plurality of memory blocks) meet a particular criterion. The particular criterion can be a threshold ratio of valid data entries to invalid data entries written to at least one memory block among the plurality of memory blocks.

The virtual indexing circuitry113can be configured to perform a garbage collection operation, folding operation, etc. as part of performance of the media management operation. When the garbage collection operation is triggered the L2P table recorded in the P2I table of the source VB can be read one by one and all data which physical address belongs to the source VB can be copied. At the same time, the virtual indexing circuitry113can update the L2P.

FIG.2is a functional block diagram201corresponding to memory sub-system virtual indexing in accordance with some embodiments of the present disclosure. The system, which can be referred to in the alternative as an “apparatus,” includes a memory sub-system210, a memory sub-system controller215and virtual indexing circuitry213or “control circuitry,” which can be analogous to the memory sub-system110, the memory sub-system controller115, and the virtual indexing circuitry113illustrate inFIG.1, herein. The memory sub-system210includes an LBA table that includes a plurality of address locations241-1,241-2,241-3to241-N (collectively referred to hereinafter as “address locations241”), an L2P table that includes a plurality of address locations243-1,243-2,243-3to243-M (collectively referred to hereinafter as “address locations243”), an INDEX or P2I table that includes a plurality of address locations245-1,245-2,245-3to245-Q (collectively referred to hereinafter as “address locations245”), and a PVT table that includes a plurality of address locations247-1,247-2,247-3to247-X (collectively referred to hereinafter as “address locations247”).

The address location243can be configured to store data entries in a data structure. As used herein, a “data structure” refers to a specialized format for organizing and/or storing data, which may or may not be organized in rows and columns. Examples of data structures include arrays, files, records, tables, trees, linked lists, hash tables, etc. In some embodiments, the data structure can be configured to store a logical block address (LBA) mapping table, a logical-to-physical (L2P) mapping table, a physical-to-index (P2I) mapping table, and/or a physical valid table (PVT), although embodiments are not limited to these particular examples. In general, the P2I table is configured to store indices corresponding to physical indices of the L2P table.

The LBA_0241-1can be referred to as a “first logical address,” a “zeroth address location,” or a “lowermost logical location” of the LBA table, herein. The LBA_N241-N can be referred to as a “last logical address,” an “Nth address location,” or an “uppermost logical location” of the LBA table, herein. The L2P_0243-1can be referred to as a “first physical address,” a “zeroth address location,” or a “lowermost physical location” of the L2P table, herein. The L2P_M243-M can be referred to as a “last physical address,” an “Mthaddress location,” or an “uppermost physical location” of the L2P table, herein. The INDEX_0245-1can be referred to as a “first physical address,” a “zeroth address location,” or a “lowermost physical location” of the INDEX or P2I table, herein. The INDEX_Q245-Q can be referred to as a “last physical address,” an “Qthaddress location,” or an “uppermost physical location” of the INDEX or P2I table, herein. The PVT_0247-1can be referred to as a “first physical address,” a “zeroth address location,” or a “lowermost physical location” of the PVT, herein. The PVT_X247-X can be referred to as a “last physical address,” an “Xthaddress location,” or an “uppermost physical location” of the PVT, herein.

As shown inFIG.2, the LBA table, the L2P table, the INDEX or P2I table, and the PVT are resident on the memory sub-system210. In the example ofFIG.2, the LBA table, the L2P table, the INDEX or P2I table, and the PVT can be resident on the memory sub-system210and not resident on any other component of the memory sub-system. Further, in some embodiments, the PVT table can be optional or can be removed from the memory sub-system210. Embodiments are not so limited and although not explicitly illustrated so as to not obfuscate the drawing layout, the LBA table, the L2P table, the INDEX or P2I table, and/or the PVT can be resident (or partially-resident) on any component of the memory subsystem210. For example, the memory sub-system210can be resident on the memory sub-system controller215, the virtual indexing circuitry213, the memory device130, the local media controller135, and/or the memory device140illustrated inFIG.1.

As an illustrative example of the disclosure, an index corresponding to data associated with the L2P table (e.g., the table containing entries243) can be written to the P2I table. The L2P index can correspond to an address written to the L2P table that is associated with a LBA (e.g., as recorded in the table containing the entries241), as mentioned above. The index written to the P2I table can comprise a single bit (e.g., a Boolean logical bit such as a logical “1” or “0”), although embodiments are not so limited. This indication can correspond to, at minimum, a ratio of valid data to invalid data associated with LBAs that are associated to the L2P table.

The indices of the P2I table (e.g., the table containing the entries245) can be read to determine the validity of data entries associated with the L2P table and, consequently, the LBAs to determine whether an index in the L2P table should be updated in response to an alteration in the LBAs. That is, if an entry in the P2I table corresponds to an LBA (e.g., an altered, rewritten, etc. LBA), embodiments herein provide that the L2P index does not need to be rewritten if the P2I table includes a corresponding entry involving such LBAs.

For example, consider an LBA written to the LBA table at241-1(e.g., LBA_0). In a simplified example, a logical-to-physical address corresponding to the LBA241-1can be written to the L2P table at243-1(e.g., L2P_0). An index value (e.g., a logical “1”) can be written at INDEX_0245-1in the P2I table in response to a determination that a VB associated with the LBA, the L2P entry, etc. is closed (e.g., indicating that the L2P entry is generally valid with respect to the index written to the P2I table at245-1). This can mitigate the likelihood that all of the data associated with a VB that is associated to the L2P table can become invalid prior to performance of a media management operation. For example, by determining that a VB is closed in response to the P2I table including an index indicating that the VB is closed, it can be assumed that the LBAs and/or L2P table are unlikely to be updated further, and are therefore probabilistically more likely to remain valid, prior to performance of a media management operation.

In some embodiments, the media management operation can be performed utilizing the closed VBs based on the indices written to the P2I table in an effort to mitigate a frequency of updates incurred by the L2P table in previous approaches. For example, by recording the indices discussed herein in the P2I table, it can become possible to perform media management operations, such as garbage collection operations, folding operations, etc. without further updating the L2P table at least because the P2I table stores indications that VBs associated to the L2P table have been closed and are therefore unlikely to become invalid prior to performance of such media management operations, as discussed above.

In a non-limiting example, an apparatus (e.g., the memory sub-system210) includes the LBA table, the L2P table, the INDEX or P2I table, the PVT and a processing device (e.g., the virtual indexing circuitry213). The apparatus can be a system-on-chip, although embodiments are not so limited. The processing device can write a data entry to an address location241of the LBA table. The data entry can be a new data entry or the data entry can be a data entry that was previously written to a different LBA location. The processing device can map a plurality of LBAs that are associated with a L2P data structure to the L2P table243. Further the processing device can map a plurality of L2P data that are associated with an INDEX or L2I data structure to the INDEX or L2I table245. The PVT247can comprise data, corresponding with the L2P data, marked as invalid (e.g., unmapped data, new data entries, data entries located in a different LBA than a previous entry of the same data) or valid, and as such, corresponding indices can comprise valid data entries and invalid data entries. In some embodiments, the processing device can write, to a first data structure, indices corresponding to address locations of the L2P data structure.

During a media management operation such as a garbage collection operation, the processing device can be configured to read the L2P table243recorded in the INDEX or P2I table245of a source VB one by one. All data in the L2P table243(e.g., including valid data entries and invalid data entries) can be copied to a destination VB.

FIG.3is flow diagram corresponding to a method340for virtual indexing in a memory device in accordance with some embodiments of the present disclosure. The method360can be performed by processing logic that can include hardware (e.g., processing device, circuitry, dedicated logic, programmable logic, microcode, hardware of a device, integrated circuit, etc.), software (e.g., instructions run or executed on a processing device), or a combination thereof. In some embodiments, the method360is performed by the virtual indexing circuitry113ofFIG.1. Although shown in a particular sequence or order, unless otherwise specified, the order of the processes can be modified. Thus, the illustrated embodiments should be understood only as examples, and the illustrated processes can be performed in a different order, and some processes can be performed in parallel. Additionally, one or more processes can be omitted in various embodiments. Thus, not all processes are required in every embodiment. Other process flows are possible.

At operation361, indices corresponding to address locations of a logical-to-physical (L2P) data structure that maps a plurality of logical block addresses (LBAs) associated with the L2P data structure can be written to a first data structure. In some embodiments, the indices corresponding to the address locations can comprise Boolean logical values. A first index, corresponding to a first range of LBAs, can be written to the first data structure. Additionally, a second index, corresponding to a second range of LBAs, can be written to the first data structure. Embodiments are not so limited, however, and in some embodiments a plurality of indices corresponding to a plurality of ranges of LBAs can be written to the first data structure. In some embodiments, the indices corresponding to address locations of the L2P data structure that maps the plurality of LBAs can be written to the first data structure based on a determined ratio of valid and invalid data written to one or more memory blocks associated with the LBAs.

At operation363, performance of a media management operation involving one or more memory blocks in which data associated with the LBA is written can be initiated. At least one memory block in which the data associated with the LBAs are stored can be a virtual memory block. Valid and invalid data can be written to at least one of the memory blocks or virtual memory blocks associated with the LBAs. In some embodiments, the media management operation can copy valid LBAs from a media management operation source VB to a destination VB. In some embodiments, the media management operation can be a garbage collection operation.

At operation365, particular entries in the L2P table that correspond to LBAs whose index in the first data structure is a particular value can be refrained from being rewritten during performance of the media management operation. In some embodiments, particular entries can be refrained from being rewritten in the L2P table that correspond to LBAs whose indices correspond to a determined ratio of valid data entries to invalid data entries written to one or more memory blocks associated with the LBAs.

In some embodiments, the method360can include virtual indexing address locations of the L2P data structure for a memory sub-system in response to a determined ratio of valid data and invalid data written to one or more memory blocks associated with an LBA associated with the L2P data structure. In some embodiments, the memory sub-system can be analogous to the memory sub-system110illustrated inFIG.1.

FIG.4is a block diagram of an example computer system400in which embodiments of the present disclosure may operate. For example,FIG.4illustrates an example machine of a computer system400within which a set of instructions, for causing the machine to perform any one or more of the methodologies discussed herein, can be executed. In some embodiments, the computer system400can correspond to a host system (e.g., the host system120ofFIG.1) that includes, is coupled to, or utilizes a memory sub-system (e.g., the memory sub-system110ofFIG.1) or can be used to perform the operations of a controller (e.g., to execute an operating system to perform operations corresponding to the virtual indexing circuitry113ofFIG.1). In alternative embodiments, the machine can be connected (e.g., networked) to other machines in a LAN, an intranet, an extranet, and/or the Internet. The machine can operate in the capacity of a server or a client machine in client-server network environment, as a peer machine in a peer-to-peer (or distributed) network environment, or as a server or a client machine in a cloud computing infrastructure or environment.

The machine can be a personal computer (PC), a tablet PC, a set-top box (STB), a Personal Digital Assistant (PDA), a cellular telephone, a web appliance, a server, a network router, a switch or bridge, or any machine capable of executing a set of instructions (sequential or otherwise) that specify actions to be taken by that machine. Further, while a single machine is illustrated, the term “machine” shall also be taken to include any collection of machines that individually or jointly execute a set (or multiple sets) of instructions to perform any one or more of the methodologies discussed herein.

The example computer system400includes a processing device402, a main memory404(e.g., read-only memory (ROM), flash memory, dynamic random access memory (DRAM) such as synchronous DRAM (SDRAM) or Rambus DRAM (RDRAM), etc.), a static memory406(e.g., flash memory, static random access memory (SRAM), etc.), and a data storage system418, which communicate with each other via a bus430.

The processing device402represents one or more general-purpose processing devices such as a microprocessor, a central processing unit, or the like. More particularly, the processing device can be a complex instruction set computing (CISC) microprocessor, reduced instruction set computing (RISC) microprocessor, very long instruction word (VLIW) microprocessor, or a processor implementing other instruction sets, or processors implementing a combination of instruction sets. The processing device402can also be one or more special-purpose processing devices such as an application specific integrated circuit (ASIC), a field programmable gate array (FPGA), a digital signal processor (DSP), network processor, or the like. The processing device402is configured to execute instructions426for performing the operations and steps discussed herein. The computer system400can further include a network interface device408to communicate over the network420.

The data storage system418can include a machine-readable storage medium424(also known as a computer-readable medium) on which is stored one or more sets of instructions426or software embodying any one or more of the methodologies or functions described herein. The instructions426can also reside, completely or at least partially, within the main memory404and/or within the processing device402during execution thereof by the computer system400, the main memory404and the processing device402also constituting machine-readable storage media. The machine-readable storage medium424, data storage system418, and/or main memory404can correspond to the memory sub-system110ofFIG.1.

In one embodiment, the instructions426include instructions to implement functionality corresponding to a virtual indexing circuitry (e.g., the virtual indexing circuitry113ofFIG.1). While the machine-readable storage medium424is shown in an example embodiment to be a single medium, the term “machine-readable storage medium” should be taken to include a single medium or multiple media that store the one or more sets of instructions. The term “machine-readable storage medium” shall also be taken to include any medium that is capable of storing or encoding a set of instructions for execution by the machine and that cause the machine to perform any one or more of the methodologies of the present disclosure. The term “machine-readable storage medium” shall accordingly be taken to include, but not be limited to, solid-state memories, optical media, and magnetic media.

Some portions of the preceding detailed descriptions have been presented in terms of algorithms and symbolic representations of operations on data bits within a computer memory. These algorithmic descriptions and representations are the ways used by those skilled in the data processing arts to most effectively convey the substance of their work to others skilled in the art. An algorithm is here, and generally, conceived to be a self-consistent sequence of operations leading to a desired result. The operations are those requiring physical manipulations of physical quantities. Usually, though not necessarily, these quantities take the form of electrical or magnetic signals capable of being stored, combined, compared, and otherwise manipulated. It has proven convenient at times, principally for reasons of common usage, to refer to these signals as bits, values, elements, symbols, characters, terms, numbers, or the like.

It should be borne in mind, however, that all of these and similar terms are to be associated with the appropriate physical quantities and are merely convenient labels applied to these quantities. The present disclosure can refer to the action and processes of a computer system, or similar electronic computing device, that manipulates and transforms data represented as physical (electronic) quantities within the computer system's registers and memories into other data similarly represented as physical quantities within the computer system memories or registers or other such information storage systems.

The present disclosure also relates to an apparatus for performing the operations herein. This apparatus can be specially constructed for the intended purposes, or it can include a general purpose computer selectively activated or reconfigured by a computer program stored in the computer. Such a computer program can be stored in a computer readable storage medium, such as, but not limited to, any type of disk including floppy disks, optical disks, CD-ROMs, and magnetic-optical disks, read-only memories (ROMs), random access memories (RAMs), EPROMs, EEPROMs, magnetic or optical cards, or any type of media suitable for storing electronic instructions, each coupled to a computer system bus.

The algorithms and displays presented herein are not inherently related to any particular computer or other apparatus. Various general purpose systems can be used with programs in accordance with the teachings herein, or it can prove convenient to construct a more specialized apparatus to perform the method. The structure for a variety of these systems will appear as set forth in the description below. In addition, the present disclosure is not described with reference to any particular programming language. It will be appreciated that a variety of programming languages can be used to implement the teachings of the disclosure as described herein.

The present disclosure can be provided as a computer program product, or software, that can include a machine-readable medium having stored thereon instructions, which can be used to program a computer system (or other electronic devices) to perform a process according to the present disclosure. A machine-readable medium includes any mechanism for storing information in a form readable by a machine (e.g., a computer). In some embodiments, a machine-readable (e.g., computer-readable) medium includes a machine (e.g., a computer) readable storage medium such as a read only memory (“ROM”), random access memory (“RAM”), magnetic disk storage media, optical storage media, flash memory devices, etc.

In the foregoing specification, embodiments of the disclosure have been described with reference to specific example embodiments thereof. It will be evident that various modifications can be made thereto without departing from the broader spirit and scope of embodiments of the disclosure as set forth in the following claims. The specification and drawings are, accordingly, to be regarded in an illustrative sense rather than a restrictive sense.