Patent ID: 12254209

Skilled artisans will appreciate that elements in the figures are illustrated for simplicity and clarity and have not necessarily been drawn to scale. For example, the dimensions of some of the elements in the figures may be exaggerated relative to other elements to help to improve understanding of implementations of the present disclosure.

The apparatus and method components have been represented where appropriate by conventional symbols in the drawings, showing those specific details that are pertinent to understanding the implementations of the present disclosure so as not to obscure the disclosure with details that will be readily apparent to those of ordinary skill in the art.

DETAILED DESCRIPTION OF THE INVENTION

The following detailed description of example implementations refers to the accompanying drawings. The same reference numbers in different drawings may identify the same or similar elements.

FIG.1is a schematic block diagram of an example system in accordance with some implementations. System100includes a host102and a storage device104. Host102and storage device104may be in the same physical location as components on a single computing device or on different computing devices that are communicatively coupled. Storage device104, in various embodiments, may be disposed in one or more different locations relative to the host102. System100may include additional components (not shown in this figure for the sake of simplicity).

Storage device104may include a random-access memory (RAM)106, a controller108, and one or more non-volatile memory devices110a-110n(referred to herein as the memory device(s)110). Storage device104may be, for example, a solid-state drive (SSD), and the like. RAM106may be temporary storage such as a dynamic RAM (DRAM) that may be used to store information such as L2P entries.

Controller108may interface with host102and process foreground operations including instructions transmitted from host102. For example, controller108may read data from and/or write to memory device110based on instructions received from host102. Controller108may also erase data from memory device110based on instructions received from host102. Controller108may further execute background operations to manage resources on memory device110. For example, controller108may monitor memory device110and may execute garbage collection and other relocation functions per internal relocation algorithms to refresh and/or relocate the data on memory device110.

Memory device110may be flash based. For example, memory device110may be a NAND flash memory that may be used for storing host and control data over the operational life of memory device110. Memory device110may be included in storage device104or may be otherwise communicatively coupled to storage device104.

When host102wants to perform a format operation on storage device104, host102may issue different configurations of erase commands. For example, host102may issue a single erase command wherein the erase command may instruct controller108to invalidate all L2P entries on storage device104. Host102may also issue several erase commands for one format operation, wherein each erase command may instruct storage device104to invalidate a range of L2P entries associated with a chunk of data, and when all of the erase commands are executed, all the L2P entries on storage device104may be invalidated. For example, each erase command may be to invalidate a range of L2P entries associated with 10 gigabytes (GB) of data. As the format operation is carried out using one or more standard erase commands, controller108may have to determine when an erase command received from host102is associated with a format operation or when the erase command is issued to erase a subset amount of data from storage device104.

Host102may have a stringent format timeout period to, for example, ensure its users are not waiting for long periods for the format operation to complete. In some cases, host102may send a format time, i.e., the time that host102expects a in format operation to be completed to storage device104. In some cases, controller108may use the format time provided by a storage device specification or may use another predefined time as the format time. If storage device104does not complete the format operation within the format time, host102may reboot and/or generate an error which may indicate that storage device104is unusable or inaccessible.

Controller108may also dynamically calculate the format time associated with executing a format operation. Consider an example where controller108uses the format time provided by the storage device specification. If the format operation fails before the format time expires (i.e., if host102reboots and/or returns an error before the format time expires), controller108may reduce the format time provided by the storage device specification and execute the format operation. For example, if the format time provided by the storage device specification is two minutes and if the format operation fails before the two minutes expire, controller108may reduce the format time to one minute and execute the format operation. If the format operation again fails before the format time expires, controller108may continue to reduce the format time until it can successfully execute the format operation within a reduced format time. When controller108is able to successfully complete the format operation within a reduced format time, controller108may assign the reduced format time as the format time needed to execute format operations for host102.

To ensure interoperability with hosts using different schemes to send erase commands to format storage device104and to ensure that storage device104returns operations to host102as needed by different format time requirements, storage device104may execute different format operation schemes. In a first format operation scheme, controller108may determine the format time, the capacity of storage device104, and the chunk size associated with an erase command. Controller108may determine the total number of chunks that it may need to erase to format storage device104and may calculate a chunk erase time, i.e., the time to be assigned to erase the chunk of data associated with the erase command. Controller108may perform an erase operation on the chunk of data in the erase command for the chunk erase time, and after the chunk erase time expires, controller108may stop performing the erase operation on that chunk of data. For example, controller108may begin invalidating the L2P entries for the logical block addresses in the chunk of data in the erase command, and when the chunk erase time expires, controller108may stop invalidating the L2P entries for the logical block addresses in that chunk of data. In some cases, controller108may keep track of the logical block addresses in that chunk of data that were not invalidated before the chunk erase time expired and may invalidate the L2P entries for those logical block addresses during background operations.

Consider an example where host102may format storage device104by sending erase commands to erase 10 GB chunks of data. If, for example, controller108determines that host102expects a format operation to be completed in sixty seconds and that the total capacity of storage device104is 1536 GB, controller108may determine the total number of chunks that it may need to erase to format storage device104. For example, controller108may calculate the total number of chunks to erase by dividing the total capacity of the storage drive by the chunk size+1 (i.e., (1536 GB/10 GB)+1=154). Controller108may then divide the format time by the total number of chunks to obtain the chunk erase time (i.e., 60/154)=0.389 sec=389 milliseconds. For each erase command controller108receives, controller108may begin invalidating the L2P entries for the associated logical block addresses in the erase command for the chunk erase time (i.e., 389 milliseconds). After 389 milliseconds, controller108may stop invalidating the L2P entries for the logical block addresses for that 10 GB chunk of data. In some cases, controller108may invalidate the logical block addresses that were not invalidated within the chunk erase time during background operations.

If, for example, host102sends an erase command to erase the total capacity of the drive, controller108may determine that the chunk size is one and that the chunk erase time for that chunk is sixty seconds (i.e., the format erase time). Controller108may begin invalidating the L2P entries for the associated logical block addresses in the erase command, and after sixty seconds, controller108may stop performing the erase operation. Controller108may keep track of the logical block addresses that were not invalidated and may invalidate those logical block addresses during background operations.

In a second format operation scheme, when storage device104receives an erase command from host102, controller108may start an erase timer. Controller108may run the erase timer until it receives another command from host102that is not an erase command or until the format time expires. Using the example where the format time is sixty seconds, when storage device104receives a first erase command from host102, controller108may start the erase timer. If storage device104does not receive another host command that is not an erase command, controller may invalidate L2P entries associated with the logical block addresses in the erase commands for sixty seconds. After the format time expires, controller108may stop performing the erase operation and stop invalidating the L2P entries. Controller108may keep track of the logical block addresses that were not invalidated and may invalidate those logical block addresses during background operations.

Using the example above where host102issues erase commands to erase 10 GB chunks of data, when controller108receives the erase command for the first 10 GB chunk, controller108may start the erase timer. If host102issues 154 erase commands to invalidate the L2P entries for the entire capacity (i.e., 1536 GB), controller108may complete the erase operations, for example, for the first 100 erase commands within the format time. Controller108may thus invalidate all the L2P entries for the logical block addresses in the first 100 erase commands. When the format time expires, controller108may stop processing the erase operations for the remaining fifty-four erase commands and may not invalidate the L2P entries for the logical block addresses in the remaining fifty-four erase commands. Controller108may keep track of the logical block addresses in the remaining fifty-four erase command that were not invalidated and may invalidate those logical block addresses during background operations.

Similar to the first format operation scheme, in the second format operation scheme, when host102issues an erase command for a single chunk including logical block addresses starting from the first logical block address to the last logical block address in the L2P table, controller108may perform the erase operation for sixty seconds (i.e., the format time). Controller108may stop invalidating L2P entries for logical block addresses when the format time expires. Controller108may keep track of the logical block addresses that were not invalidated and may invalidate L2P entries for those logical block addresses during background operations.

When controller108receives an erase command for a first chunk of data, controller108may start the erase timer and begin invalidating L2P entries associated with the logical block addresses in the erase command. If host102issues another command that is not an erase command before the format time expires, controller108may determine that the erase command is not associated with a format operation and may reset the erase timer.

Continuing with the example where the format time is sixty seconds, the capacity of storage device is 1536 GB, and host102issues erase commands to erase chunks of data (i.e., 10 GB chunks of data), controller108may start the erase timer when it received the first erase command. If, for example, host102issues 154 erase commands to format storage device104, controller108may begin invalidating L2P entries associated with the logical block addresses in the erase commands until the format time expires. If on the other hand, after host102sends the third erase command host102sends a write command, controller108may reset the erase timer when it receives the write command and determine that the three erase commands it received from host102were not associated with a format operation. This scheme may thus enable storage device104to differentiate erase commands that are associated with format operations from those that are not.

In a third format operation scheme, when host102issues an erase command for a single chunk including logical block addresses starting from the first logical block address and ending with the last logical block address in the L2P table, controller108may set a valid fragment count (VFC) for each meta block to zero and erase the control pages, rather than invalidating each logical block address. The VFC may be a counter associated with a meta-block that indicates the number of valid entries in a meta block.

Storage device104may perform these processes based on a processor, for example, controller108executing software instructions stored by a non-transitory computer-readable medium, such as storage component110. As used herein, the term “computer-readable medium” refers to a non-transitory memory device. Software instructions may be read into storage component110from another computer-readable medium or from another device. When executed, software instructions stored in storage component110may cause controller108to perform one or more processes described herein. Additionally, or alternatively, hardware circuitry may be used in place of or in combination with software instructions to perform one or more processes described herein. Thus, implementations described herein are not limited to any specific combination of hardware circuitry and software. System100may include additional components (not shown in this figure for the sake of simplicity).FIG.1is provided as an example. Other examples may differ from what is described inFIG.1.

FIG.2includes block diagrams showing how L2P entries are processed according to a first format operation scheme in accordance with some implementations. Host102may format storage device104with a 1536 GB capacity by sending erase commands. Each erase command may instruct storage device104to erase 10 GB chunks of data. The L2P entries for the logical block addresses in the 10 GB chunk of data associated with the first erase command are shown as entries202-0, the L2P entries for the logical block addresses in the 10 GB chunk of data associated with the second erase command are shown as entries202-1, and so on, with the L2P entries for the logical block addresses in the 10 GB chunk of data associated with the last erase command shown as entries202-153. Entries202-0to202-153are referred to generally herein as entries202. If controller108determines that host102expects a format operation to be completed in sixty seconds, controller108may determine the total number of chunks that it may need to erase to format storage device104(i.e., (1536 GB/10 GB)+1=154) and the chunk erase time (i.e., 60/154)=0.389 sec=389 milliseconds.

L2P table204A shows entries202prior to controller108processing the erase operations according to the first format operation scheme. For demonstration purposes, L2P table204A is divided into 154 blocks, with each block including the L2P entries for 10 GB of data. L2P table204B shows entries202after controller108has processed the erase operations according to the first format operation scheme. For each erase command controller108receives, controller108may invalidate L2P entries for the logical block addresses in the erase command until the chunk erase time (i.e., 389 milliseconds) expires. After the chunk erase time expires, controller108may stop invalidating L2P entries for the logical block addresses in that chunk of data. For example, L2P table204B shows a shaded section in each block, wherein the shaded section may represent L2P entries that were invalidated prior to the expiry of the chunk erase time and the non-shaded sections may represent L2P entries that were not invalided prior to the expiration of the chunk erase time.

L2P table206A shows an L2P table stored on storage device104prior to controller108processing an erase operation according to the first format operation scheme. L2P table206A may include L2P entries for the 1536 GB capacity of storage device104. Host102may send an erase command to erase the total capacity of the drive, wherein the erase command may include the starting logical block address ((LBA)0) and the last logical block address (LBA1535) in L2P table206A. Controller108may determine that the chunk size is 1 and that the chunk erase time for that chunk is sixty second which is also the full the format time. Controller108may invalidate L2P entries for logical block addresses in the erase command until the format time (i.e., sixty seconds) expires. After the format time expires, controller108may stop invalidating L2P entries in L2P table206A. For example, L2P table206B shows a shaded section that may represent the L2P entries that were invalidated prior to the expiry of the format time and the non-shaded sections may represent L2P entries that were not invalided prior to the expiration of the format time.FIG.2is provided as an example. Other examples may differ from what is described inFIG.2.

FIG.3includes block diagrams showing how L2P entries are processed according to a second format operation scheme in accordance with some implementations. For demonstration purposes, L2P table302A is divided into 154 blocks, with each block including the L2P entries for 10 GB of data. L2P table302A shows the L2P entries prior to controller108processing the erase operations according to the second format operation scheme. When storage device104receives an erase command from host102at time-T1, controller108may start an erase timer. Controller108may run the erase timer until it receives another command from host102that is not an erase command or until the format time expires at time-TN.

L2P table302B shows the L2P entries after controller108has processed the erase operations according to the second format operation scheme. Controller108may invalidate L2P entries in202-0to202-4for logical block addresses in the erase command until the format time expires. After the format time expires, controller108may stop invalidating L2P entries in202-5to202-153. For example, L2P table302B shows a shaded section that may represent the L2P entries that were invalidated prior to the expiry of the format time and the non-shaded sections may represent L2P entries that were not invalided prior to the expiration of the format time.

L2P table304shows the L2P entries after controller108has processed the erase operations according to the second format operation scheme. Controller108may invalidate L2P entries in202-0to202-2for logical block addresses in erase command(s) until controller108receives another host command that is not an erase command. When controller108receives the other host command at time-T2, even though the format time has not expired, controller108may reset the erase timer. As indicated aboveFIG.3is provided as an example. Other examples may differ from what is described inFIG.3.

FIG.4is a flow diagram of an example process for processing L2P entries according to a first format operation scheme in accordance with some implementations. At410, storage device104may receive erase command(s) from host102. At420, controller108may determine the format time, the capacity of storage device104, and the chunk size associated with an erase command. At430, controller108may calculate the total number of chunks that it may need to erase to format storage device104and a chunk erase time. At440, controller108may perform an erase operation on a chunk of data in the erase command for the chunk erase time, and after the chunk erase time expires, controller108may stop performing the erase operation on that chunk of data. At450, controller108may keep track of the logical block addresses in that chunk of data that were not invalidated before the chunk erase time expired and may invalidate the L2P entries for those logical block addresses during background operations. As indicated aboveFIG.4is provided as an example. Other examples may differ from what is described inFIG.4.

FIG.5is a flow diagram of an example process for processing L2P entries according to a second format operation scheme in accordance with some implementations. At510, storage device104may receive erase command(s) from host102. At520, controller108may start an erase timer. At530, controller108may run the erase timer until it receives another command from host102that is not an erase command or until the format time expires. At540, after the format time expires, controller108may stop performing the erase operation and stop invalidating the L2P entries. At550, controller108may keep track of the logical block addresses that were not invalidated and may invalidate those logical block addresses during background operations. As indicated aboveFIG.5is provided as an example. Other examples may differ from what is described inFIG.5.

FIG.6is a flow diagram of an example process for processing L2P entries according to a third format operation scheme in accordance with some implementations. At610, storage device104may receive erase command from host102for a single chunk including logical block addresses starting from the first logical block address and ending with the last logical block address in the L2P table. At620, controller108may set a valid fragment count (VFC) for each meta block to zero and erase the control pages. As indicated aboveFIG.6is provided as an example. Other examples may differ from what is described inFIG.7.

FIG.7is a diagram of an example environment in which systems and/or methods described herein are implemented. As shown inFIG.7, Environment700may include hosts102-102n(referred to herein as host(s)102), and storage devices104a-104n(referred to herein as storage device(s)104).

Storage device104may include a controller108to manage the resources on storage device104. Controller108may format storage device104according to different format times and command configurations. Hosts102and storage devices104may communicate via Non-Volatile Memory Express (NVMe) over peripheral component interconnect express (PCI Express or PCIe) standard, the Universal Flash Storage (UFS) over Unipro, or the like.

Devices of Environment700may interconnect via wired connections, wireless connections, or a combination of wired and wireless connections. For example, the network ofFIG.7may include a cellular network (e.g., a long-term evolution (LTE) network, a code division multiple access (CDMA) network, a 3G network, a 4G network, a 5G network, another type of next-generation network, and/or the like), a public land mobile network (PLMN), a local area network (LAN), a wide area network (WAN), a metropolitan area network (MAN), a telephone network (e.g., the Public Switched Telephone Network (PSTN)), a private network, an ad hoc network, an intranet, the Internet, a fiber optic-based network, a cloud computing network, or the like, and/or a combination of these or other types of networks.

The number and arrangement of devices and networks shown inFIG.7are provided as an example. In practice, there may be additional devices and/or networks, fewer devices and/or networks, different devices and/or networks, or differently arranged devices and/or networks than those shown inFIG.7. Furthermore, two or more devices shown inFIG.7may be implemented within a single device, or a single device shown inFIG.7may be implemented as multiple, distributed devices. Additionally, or alternatively, a set of devices (e.g., one or more devices) of Environment700may perform one or more functions described as being performed by another set of devices of Environment700.

FIG.8is a diagram of example components of one or more devices ofFIG.1. In some implementations, host102may include one or more devices800and/or one or more components of device800. Device800may include, for example, a communications component805, an input component810, an output component815, a processor820, a storage component825, and a bus830. Bus830may include components that enable communication among multiple components of device800, wherein components of device800may be coupled to be in communication with other components of device800via bus830.

Input component810may include components that permit device800to receive information via user input (e.g., keypad, a keyboard, a mouse, a pointing device, a microphone, and/or a display screen), and/or components that permit device800to determine the location or other sensor information (e.g., an accelerometer, a gyroscope, an actuator, another type of positional or environmental sensor). Output component815may include components that provide output information from device800(e.g., a speaker, display screen, and/or the like). Input component810and output component815may also be coupled to be in communication with processor820.

Processor820may be a central processing unit (CPU), a graphics processing unit (GPU), an accelerated processing unit (APU), a microprocessor, a microcontroller, a digital signal processor (DSP), a field-programmable gate array (FPGA), an application-specific integrated circuit (ASIC), or another type of processing component. In some implementations, processor820may include one or more processors capable of being programmed to perform a function. Processor820may be implemented in hardware, firmware, and/or a combination of hardware and software.

Storage component825may include one or more memory devices, such as random-access memory (RAM)114, read-only memory (ROM), and/or another type of dynamic or static storage device (e.g., a flash memory, a magnetic memory, and/or optical memory) that stores information and/or instructions for use by processor820. A memory device may include memory space within a single physical storage device or memory space spread across multiple physical storage devices. Storage component825may also store information and/or software related to the operation and use of device800. For example, storage component825may include a hard disk (e.g., a magnetic disk, an optical disk, and/or a magneto-optic disk), a solid-state drive (SSD), a compact disc (CD), a digital versatile disc (DVD), a floppy disk, a cartridge, a magnetic tape, and/or another type of non-transitory computer-readable medium, along with a corresponding drive.

Communications component805may include a transceiver-like component that enables device800to communicate with other devices, such as via a wired connection, a wireless connection, or a combination of wired and wireless connections. The communications component805may permit device800to receive information from another device and/or provide information to another device. For example, communications component805may include an Ethernet interface, an optical interface, a coaxial interface, an infrared interface, a radio frequency (RF) interface, a universal serial bus (USB) interface, a Wi-Fi interface, and/or a cellular network interface that may be configurable to communicate with network components, and other user equipment within its communication range. Communications component805may also include one or more broadband and/or narrowband transceivers and/or other similar types of wireless transceiver configurable to communicate via a wireless network for infrastructure communications. Communications component805may also include one or more local area network or personal area network transceivers, such as a Wi-Fi transceiver or a Bluetooth transceiver.

Device800may perform one or more processes described herein. For example, device800may perform these processes based on processor820executing software instructions stored by a non-transitory computer-readable medium, such as storage component825. As used herein, the term “computer-readable medium” refers to a non-transitory memory device. Software instructions may be read into storage component825from another computer-readable medium or from another device via communications component805. When executed, software instructions stored in storage component825may cause processor820to perform one or more processes described herein. Additionally, or alternatively, hardware circuitry may be used in place of or in combination with software instructions to perform one or more processes described herein. Thus, implementations described herein are not limited to any specific combination of hardware circuitry and software.

The number and arrangement of components shown inFIG.8are provided as an example. In practice, device800may include additional components, fewer components, different components, or differently arranged components than those shown inFIG.8. Additionally, or alternatively, a set of components (e.g., one or more components) of device800may perform one or more functions described as being performed by another set of components of device800.

The foregoing disclosure provides illustrative and descriptive implementations but is not intended to be exhaustive or to limit the implementations to the precise form disclosed herein. One of ordinary skill in the art will appreciate that various modifications and changes can be made without departing from the scope of the present disclosure as set forth in the claims below. Accordingly, the specification and figures are to be regarded in an illustrative rather than a restrictive sense, and all such modifications are intended to be included within the scope of present teachings.

As used herein, the term “component” is intended to be broadly construed as hardware, firmware, and/or a combination of hardware and software. It will be apparent that systems and/or methods described herein may be implemented in different forms of hardware, firmware, and/or a combination of hardware and software.

Even though particular combinations of features are recited in the claims and/or disclosed in the specification, these combinations are not intended to limit the disclosure of various implementations. In fact, many of these features may be combined in ways not specifically recited in the claims and/or disclosed in the specification. Although each dependent claim listed below may directly depend on only one claim, the disclosure of various implementations includes each dependent claim in combination with every other claim in the claim set.

No element, act, or instruction used herein should be construed as critical or essential unless explicitly described as such. Also, as used herein, the articles “a” and “an” are intended to include one or more items and may be used interchangeably with “one or more” Furthermore, as used herein, the term “set” is intended to include one or more items (e.g., related items, unrelated items, a combination of related items, unrelated items, and/or the like), and may be used interchangeably with “one or more.” The term “only one” or similar language is used where only one item is intended. Further, the phrase “based on” is intended to mean “based, at least in part, on” unless explicitly stated otherwise.

Moreover, in this document, relational terms such as first and second, top and bottom, and the like, may be used solely to distinguish one entity or action from another entity or action without necessarily requiring or implying any actual such relationship or order between such entities or actions. The terms “comprises,” “comprising,” “has”, “having,” “includes”, “including,” “contains”, “containing” or any other variation thereof, are intended to cover a non-exclusive inclusion, such that a process, method, article, or apparatus that comprises, has, includes, contains a list of elements does not include only those elements but may include other elements not expressly listed or inherent to such process, method, article, or apparatus. An element proceeded by “comprises . . . a”, “has . . . a”, “includes . . . a”, or “contains . . . a” does not, without more constraints, preclude the existence of additional identical elements in the process, method, article, or apparatus that comprises, has, includes, contains the element. The terms “substantially”, “essentially”, “approximately”, “about” or any other version thereof, are defined as being close to as understood by one of ordinary skill in the art, and in one non-limiting implementation, the term is defined to be within 10%, in another implementation within 5%, in another implementation within 1% and in another implementation within 0.5%. The term “coupled” as used herein is defined as connected, although not necessarily directly and not necessarily mechanically. A device or structure that is “configured” in a certain way is configured in at least that way but may also be configured in ways that are not listed.