Patent Description:
Computers, phones, and other electronic devices often use non-volatile storage devices to store data. Typically, one or more subsystems manage access to the storage devices to allow data to be stored and retrieved. <CIT> refers to a method of live migration between two host computers. When a guest system software accesses a guest physical page that is mapped to a machine memory page that has yet to be copied to the destination host, a guest physical page fault occurs. The guest physical page fault is handled by a guest physical page fault handler portion of virtualization software, which sends a request for the faulted page, referenced by its guest physical page number, to the source host. The source host receives the request for the faulted page, and responds to the request from the destination host with the requested page data, so that the fault on the destination host can be cleared and guest execution resumed with the access to the requested guest physical page.

The present invention relates to a method according to claim <NUM>, an apparatus according to claim <NUM> and a non-transitory computer readable memory according to claim <NUM>.

Other potential features, aspects, and advantages of the subject matter will become apparent from the description, the drawings, and the claims.

<FIG> is a block diagram that illustrates an example of a system <NUM> for managing storage devices. The system <NUM> includes a storage device <NUM>, a host <NUM>, a guest <NUM>, and an application <NUM>. The storage device <NUM> permits other devices to store and retrieve data from, for example, non-volatile memory in the storage device <NUM>. The storage device <NUM> may be a solid-state drive (SSD) including NAND flash memory, or the storage device <NUM> may be another form of storage module. The host <NUM> is a computer system that manages the storage device <NUM>. In some implementations, the host <NUM> is a virtualization server that provides processing and storage resources to one or more virtual machines or virtual environments. The guest <NUM> and the application <NUM> are examples of additional modules that may have access to the storage device <NUM>. As described further below, the storage device <NUM> is configured to cooperate with the host <NUM> to perform data storage, data retrieval, maintenance tasks, and other management of the storage device <NUM>.

The storage device <NUM> provides both a physical interface and a logical interface for access to memory. The physical interface provides access using physical addressing of the memory of the storage device <NUM>. For example, each physical address in the physical address space may correspond to a specific storage location in memory. Generally, the assignment of the physical addresses to the actual data storage circuits in the memory does not change during use of the storage device <NUM>. The logical interface provides access using logical addressing of the memory of the storage device <NUM>. For example, a logical address may be an address where certain data appears to reside from the perspective of an executing program or external system, but the logical address does not permanently correspond to any particular memory circuit or storage location. As data is written to the storage device <NUM>, logical addresses are mapped and remapped to different storage locations having different physical addresses. As described further below, the storage device <NUM> maintains a logical-to-physical mapping that indicates which physical addresses correspond to which logical addresses, and these mappings often change as the storage device <NUM> is used. In general, logical addressing abstracts details of where data is physically stored on memory devices, while physical addressing allows commands to refer specific physical storage locations of the memory devices.

The physical interface to the storage device <NUM> is provided through a physical interface <NUM>. An event interface <NUM> is used with the physical interface to allow greater control of the storage device <NUM>. The physical interface <NUM> and the event interface <NUM> allow customized management by the host <NUM> and allow the storage device <NUM> to offload many of a memory controller's typical functions to the host <NUM>. Logical access to the storage device <NUM> is provided through a logical interface <NUM>, which allows systems to communicate with the storage device <NUM> using standardized protocols. For example, the logical interface <NUM> may allow access using standards such as NVMe, AHCl, single root I/O virtualization (SR-IOV), and/or other communication methods. To systems that access the storage device <NUM> using the logical interface <NUM>, the storage device <NUM> appears to be a standard drive, even though the host <NUM> provides custom management for the storage device <NUM>.

The logical interface <NUM>, the event interface <NUM>, and the physical interface <NUM> may each be implemented as a queue pair, e.g., a bidirectional interface including an input queue for incoming messages received at the storage device <NUM> and an output queue for outgoing messages sent by the storage device <NUM>. For example, in one queue of the physical interface <NUM>, the storage device <NUM> may receive commands that refer to specific physical pages or blocks of memory devices. In the other queue of the physical interface <NUM>, the storage device <NUM> may provide acknowledgements, error messages, data, or other information.

The host <NUM> includes a management module <NUM> that controls and performs maintenance of the storage device <NUM>. The management module <NUM> may be a kernel driver, application, or other software module running on the host <NUM>. The management module <NUM> communicates with the storage device <NUM> using the event interface <NUM> and the physical interface <NUM>. In some implementations, the physical interface <NUM> and the event interface <NUM> are implemented using a peripheral component interconnect express (PCIe) connection to the host <NUM>.

The storage device <NUM> sends events to the management module <NUM> over the event interface <NUM>, for example, to notify the host <NUM> actions or conditions that require input from the host <NUM>. The storage device <NUM> may send a read event to indicate receipt of a request to read data from the storage device <NUM>, and may send a write event to indicate a request to write data to the storage device <NUM>.

The management module <NUM> sends commands to the storage device <NUM> and receives confirmations from the storage device <NUM> using the physical interface <NUM>. The commands that the management module <NUM> provides over the physical interface <NUM> use physical addressing to refer to specific, physical data storage locations in the memory of the storage device <NUM>. Examples of commands that the management module <NUM> may provide include, for example, read commands, write commands, copy commands, and erase commands. The commands may specify operations relating to particular pages or blocks of memory. As examples, one command may request that data be written to particular physical pages, and another command may request that a particular physical block be erased.

As discussed above, the physical interface <NUM> may a queue pair, for example, a request queue for the management module <NUM> to send commands and a completion queue for the storage device <NUM> to send operation completion notifications. The commands are instructions that indicate which operations the storage device <NUM> should perform. Some of the commands can result in data transfer to or from the storage device <NUM>. Data transfer typically does not occur directly over the queue pair, but occurs through a bulk DMA operation instead. For example, a physical read command may provide a buffer pointer to the host memory, e.g., host DRAM. The storage device <NUM> may transfer the requested data via bulk DMA to the buffer indicated by the pointer, and then send a completion notification over the completion queue to indicate completion of the operation.

The physical interface <NUM> may allow commands to: (<NUM>) write the contents of a buffer to a physical address, (<NUM>) copy data at a first physical address to a second physical address, and (<NUM>) erase data at a physical address. Generally these three commands would not result in a DMA data transfer between the host <NUM> and the storage device <NUM>. By using the copy operation, the management module <NUM> may perform garbage collection without transferring data off the storage device <NUM>. As indicated above, the physical interface <NUM> may also include commands to erase data at certain physical addresses.

For debugging, completeness, and legacy support reasons, the physical interface <NUM> may also support commands to read data at a physical address, write data to a buffer, and other debugging related commands. The commands to read data from a physical address and write data to buffer would typically result in a bulk DMA operation by the storage device <NUM>.

Various devices and modules can access data storage through the logical interface <NUM> provided by the storage device <NUM>. Access to the storage device <NUM> over the logical interface <NUM> may occur simultaneously with access over the physical interface <NUM>. That is, the host <NUM> is connected to the storage device <NUM> at the same time that one or more other systems are connected through the logical interface <NUM>.

The logical interface <NUM> may allow command operations including read, write, and trim. The trim command may be used, for example, to indicate that an address is available to be erased or reclaimed through garbage collection. The logical interface <NUM> may also allow other operations, for example, such as NVMe housekeeping operations to create and destroy logical queue pairs, and so on.

Examples of systems that communicate over the logical interface <NUM> include the guest <NUM>, the application <NUM>, and a kernel block device <NUM>. The described <NUM> represents a guest operating system, e.g., an operating system running in a virtual environment managed by the host <NUM>. The application <NUM> may be an application that has access to the logical interface <NUM>, either directly or through a virtualized connection. The kernel block device <NUM> represents a driver module of the host <NUM>, showing that the host <NUM> may also store and retrieve data through the logical interface <NUM> using standard storage device drivers and protocols. For example, although the host <NUM> manages the storage device <NUM> using the physical interface <NUM>, the operating system of the host <NUM> may additionally access the storage device <NUM> to support the kernel file system of the host <NUM>.

The normal runtime operations performed by the host's management module <NUM> over the physical interface <NUM> generally will not result in any data transfer or bulk DMA operations. The applications and other systems that interact with the storage device <NUM> using the logical interface <NUM> generally initiate data transfers. Logical read and write operations typically result in DMA transfers to and from the storage device <NUM>. As discussed further below, the storage device <NUM> provides the management module <NUM> with notification of logical write requests, as well as the buffer IDs for buffers in which data has already been transferred through bulk DMA. To complete a logical write, the management module <NUM> may issue, over the physical interface <NUM>, a command for the storage device <NUM> to write the contents of the appropriate buffer to a specified physical address. This command may cause the storage device <NUM> to take the data already within the storage device's <NUM> buffers and store it in flash memory.

In addition to the queue pairs illustrated, the logical interface <NUM> and the physical interface <NUM> each have an implicit ability to access at least some memory addresses of the host <NUM> provided using a bulk DMA mechanism. As a result, the storage device <NUM> can, for example, perform a bulk DMA transfer of data from an application or virtual machine, outside of the queue pairs of the logical interface <NUM>. Bulk DMA data transfers and queue pairs may operate using the same hardware link, such as a PCle interface with the host <NUM>. In addition, the commands and completions notifications sent through queue pairs, as well as bulk DMA data transfers, may be performed as DMA operations that directly read or write to system DRAM.

Typically, each guest virtual machine or application has access to only a subset of host DRAM. PCle virtualization may use an input/output memory unit (IO-MMU), implemented in system hardware, to limit DMA transfers on behalf of an application or virtual machine to the portions of host DRAM that they own. To implement these controls, logical queues pairs may be associated with a PCIe virtual function. Each DMA operation issued on behalf of a logical queue pair may be tagged with that queue pair's virtual function. When host hardware is processing device DMA operations, both for bulk DMA transfer and queue access operations, the IO-MMU hardware uses the virtual function of the DMA to consult a virtual-function-specific address mapping and permission table to determine if the DMA operation is valid for the application and/or virtual machine. By contrast, the physical queue pair is not restricted to a virtual function. As a result, DMA operations issued to process commands on the physical queue pair have access to all of host DRAM.

<FIG> is a block diagram that illustrates an example of a storage device <NUM>. The storage device <NUM> may include, for example, a memory controller <NUM>, random access memory (RAM) <NUM>, and non-volatile storage device(s) <NUM>.

The memory controller <NUM> may include one or more processors that are configured to process data from the various interfaces <NUM>, <NUM>, <NUM> of the storage device <NUM>, and to perform other functions as described further below. The functions of the memory controller <NUM> may be implemented using hardware, firmware, software, or a combination thereof.

The non-volatile storage device(s) <NUM> may be NAND flash chips or other data storage components. Typically, the storage device <NUM> includes multiple non-volatile storage device(s) <NUM>, and the memory controller <NUM> includes multiple channels to access multiple non-volatile storage device(s) <NUM> in parallel.

The RAM <NUM> may include volatile dynamic random access memory (DRAM), which may be used to store data buffers <NUM> and a logical-to-physical (L2P) mapping <NUM>. For example, the memory controller <NUM> may allocate portions of the RAM <NUM> to serve as data buffers <NUM> for temporary storage of data received over the logical interface <NUM>, before the data is written to non-volatile storage.

The L2P mapping <NUM> provides a mapping between logical addresses, e.g., addresses used by external application or operating system to represent storage locations, and physical addresses, e.g., addresses for the physical regions of the non-volatile storage device(s) <NUM> where the data is actually stored. For example, the L2P mapping <NUM> may be implemented as a table <NUM> that maps logical addresses <NUM> to physical addresses <NUM>. In the illustrated example, logical address "x3517" corresponds to physical address "x0132," logical address "x3518" corresponds to physical address "x8356," and logical address "x3519" corresponds to physical address "x9435.

<FIG> is a block diagram that illustrates a system <NUM> for managing storage devices. <FIG> illustrates interactions of the storage device <NUM>, the guest <NUM>, and the management module <NUM> of <FIG>. <FIG> also illustrates a flow of data, indicated by stages (A) through (I). The example of <FIG> illustrates an example of how the hybrid design of the storage device <NUM> allows communication over the logical interface <NUM> as well as the physical interface <NUM>. In the example, the storage device <NUM> provides the logical interface <NUM> to the guest <NUM> (e.g., a guest operating system in a virtual machine) while also providing a physical interface to a host <NUM>.

In the example of <FIG>, the guest <NUM> initiates a write operation using the logical interface <NUM>. The storage device <NUM> and the host <NUM> interact to carry out the write operation, with the management module <NUM> designating the physical location(s) of the storage device <NUM> where the data is stored. The interactions of the storage device <NUM> and the host <NUM> allow the host <NUM> to manage the write operation without transferring data to be written between the storage device <NUM> and the host <NUM>.

During stage (A), the guest <NUM> sends a logical write request <NUM> to the storage device <NUM> over the logical interface <NUM>. The logical write request <NUM> indicates a logical address at which to write data to the non-volatile storage device(s) <NUM>. In the illustrated example, the logical write request <NUM> indicates that data should be stored at a destination logical address of "x1234. " The logical write request <NUM> also indicates a source address, e.g., "SourceAddress" from which the data to be written can be accessed.

During stage (B), in response to receiving the logical write request <NUM>, the memory controller <NUM> allocates a data buffer <NUM> to store the data associated with the logical write request <NUM>, e.g., the data that the guest <NUM> requests to be written. The data buffer <NUM> may be located in volatile memory, such as the RAM <NUM> shown in <FIG>. After allocating the data buffer <NUM>, the memory controller <NUM> transfers the data to be written to the data buffer <NUM>. For example, the memory controller <NUM> transfers the data to the data buffer <NUM> via a direct memory access (DMA) transfer from the guest <NUM>.

During stage (C), the memory controller <NUM> updates the L2P mapping <NUM> so that the logical address indicated by the write request <NUM> corresponds to (e.g., maps to) the data buffer <NUM> storing the data from the guest <NUM>. In the illustrated example, the L2P mapping <NUM> is updated so that, for the logical address "x1234," the corresponding physical address is indicated to be the data buffer <NUM>, e.g., "Buffer1.

In some implementations, after storing the data from the guest <NUM> in the data buffer <NUM>, the memory controller <NUM> can optionally provide an acknowledgement to the guest <NUM> indicating that the write operation has been completed. If the guest <NUM> attempts to read data from the logical address "x1234" before the write to non-volatile storage is complete, the memory controller <NUM> can provide the data from the data buffer <NUM> that stores the data. However, since the data is currently stored in volatile RAM <NUM>, the data is not persistent in the event of loss of power to the storage device <NUM>.

During stage (D), in response to receiving the logical write request <NUM>, the memory controller <NUM> sends a write request event <NUM> to the management module <NUM> over the event interface <NUM>. The write request event <NUM> notifies the management module <NUM> that a write operation has been requested. Since the management of writes is handled by the management module <NUM>, the write request event <NUM> signals to the management module that input is needed to complete the write operation. The write request event <NUM> indicates a type of operation (e.g., a write operation), a logical address associated with the operation (e.g., "x1234"), and a buffer identifier for the data buffer <NUM> that stores the data to be written (e.g., "Buffer1"). The write request event <NUM> may include any or all of the information in the write request <NUM>. The memory controller <NUM> provides the write request event <NUM> to the management module <NUM> without sending the data to be written, e.g., the data stored in the data buffers <NUM>, to the management module <NUM>.

The logical write request <NUM> and/or the write request event <NUM> may indicate a size for the write request, e.g., an amount of data to be written. For example, this information may be provided through an NVMe interface. In some implementation, write buffers have of fixed size (e.g., <NUM> kilobytes). As a result, for a write having a size that is of the fixed size or less, the memory controller <NUM> may send a single write request event <NUM> to the management module <NUM>. When a guest system requests a logical write that is larger than the fixed write buffer size, the memory controller <NUM> allocates multiple write buffers for the data and the memory controller <NUM> sends multiple write request events <NUM> to the management module <NUM>. If a fixed size is used for all write events from the memory controller <NUM>, then the write request events <NUM> may omit an indication of the size of data to be written, since both the memory controller <NUM> and the management module <NUM> know in advance that the event represents a write having the fixed size. In some implementations, variable sized write buffers are used, so that a logical write from the guest system <NUM> always results in the memory controller <NUM> sending a single write request event <NUM> to the host management module <NUM>. The write request event <NUM> may indicate the particular size of the buffer storing data associated with the write request event <NUM>.

During stage (E), in response to receiving the write request event <NUM>, the management module <NUM> identifies storage locations of the non-volatile storage device(s) <NUM> where the data from the guest <NUM> should be stored. For example, the management module <NUM> may identify specific physical pages of the non-volatile storage device(s) <NUM> where the data should be written. For example, the management module <NUM> can identify physical pages that represent free space, e.g., previously erased memory locations. The management module <NUM> may perform other actions to select storage locations, such as determining whether garbage collection is needed, performing wear leveling analysis, and so on. Once the management module <NUM> has identified the storage locations that should be used for the write operation, the management module <NUM> sends the information to the memory controller <NUM> in a physical write command.

In addition to sending the physical write command <NUM>, the management module <NUM> may send other commands. For example, the management module may instruct the memory controller to erase certain blocks, copy data from one location to another, or otherwise prepare the non-volatile storage device(s) <NUM> to perform the write indicated in the physical write command <NUM>.

During stage (F), the memory controller <NUM> receives the physical write command <NUM> from the management module <NUM> over the physical interface <NUM>. The physical write command <NUM> includes instructions to write the data in the data buffer <NUM> to the non-volatile storage device(s) <NUM>. The physical write command <NUM> indicates (i) the buffer address for the data buffer <NUM> storing the data to be written and (ii) one or more physical addresses (abbreviated as "PA" in the figure) of the non-volatile storage device(s) <NUM> in which to store the data. The one or more physical addresses may indicate specific pages or blocks of the non-volatile storage device(s) <NUM>. The physical write command <NUM> may also indicate the logical address associated with the write, or the memory controller <NUM> may determine the logical address (e.g., based on the buffer identified and the address indicated in the corresponding logical write request <NUM>).

In the illustrated example, the physical write command <NUM> indicates a buffer identifier of "Buffer1," and indicates that the data in the buffer should be written to the storage location having physical address "x9648. " Since the memory controller <NUM> already stores the data to be written in the data buffer <NUM>, the memory controller <NUM> has no need to transfer the data again.

During stage (G), the memory controller <NUM> stores the data in the data buffer <NUM> in the non-volatile storage device(s) <NUM>, at the storage locations (e.g., pages) indicated by the physical address(es) in the physical write command <NUM>. In the illustrated example, the memory controller <NUM> stores data from the data buffer <NUM> designated "Buffer1" in the non-volatile storage device(s) <NUM> at a physical address of "x9648," as indicated by the physical write command <NUM>.

At stage (H), the memory controller <NUM> updates the L2P mapping <NUM> to indicate that the logical address indicated by the logical write request <NUM> corresponds to the physical address where the data is actually stored in the non-volatile storage device(s) <NUM>. In the illustrated example, the memory controller <NUM> updates the L2P mapping <NUM> to indicate that the logical address of "x1234," as indicated by the logical write request <NUM>, corresponds to the physical address of "x9648," as indicated by the physical write command <NUM>. After completing the write operation to non-volatile storage, the memory controller <NUM> deallocates (e.g., clears and frees) the data buffer <NUM>.

At stage (I), if the memory controller <NUM> has not yet indicated completion of the write to the guest <NUM>, the memory controller <NUM> sends an acknowledgement <NUM> to the guest <NUM> indicating that the data is stored by the non-volatile storage device(s) <NUM>.

In addition to the example of the write operation shown in <FIG>, the storage device <NUM> may carry out read operations initiated by the guest <NUM> using the logical interface <NUM>. In some implementations, the storage device <NUM> may provide data in response to a read request without interaction with the management module <NUM> of the host <NUM>.

A logical read request may indicate a logical address from which data should be read from the one or more non-volatile storage device(s) <NUM>. A logical read request may also indicate a destination address of the guest <NUM> where the data associated with the read request should be transferred. The memory controller <NUM> receives the read request from the guest <NUM>, and in response, accesses the L2P mapping <NUM>. The memory controller <NUM> can identify the logical address indicated by the read request within the L2P mapping <NUM> and determine a physical address associated with (e.g., mapped to) the identified logical address.

The memory controller <NUM> can retrieve the data associated with the determined physical address (e.g., as stored by the non-volatile storage device(s) <NUM>). The memory controller <NUM> provides the retrieved data to the destination address of the guest <NUM> (e.g., via DMA) as indicated by the read request from the guest <NUM>. The memory controller <NUM> may also provide an acknowledgement to the guest <NUM> that the read operation associated with the retrieved data is complete. Thus, in some instances, the memory controller <NUM> directly provides access to the data stored by the non-volatile storage device(s) <NUM> in response to a read request from the guest <NUM>, without involvement or assistance by the management module <NUM>.

<FIG> is a block diagram that illustrates a system <NUM> for migrating data between storage devices. The system <NUM> includes a source storage device <NUM> and the storage device <NUM>, referred to as a destination storage device <NUM>. The source storage device <NUM> and the destination storage device <NUM> are both managed by the management module <NUM>. The system also includes the guest <NUM>, which initially accesses the source storage device <NUM>. The management module <NUM> transitions the guest <NUM> from using the source storage device <NUM> to using the destination storage device <NUM>, while allowing read and write access of the guest <NUM> during most of the migration process.

In the example of <FIG>, the management module <NUM> transfers the guest's <NUM> access to the destination storage device <NUM> before migration is complete, e.g., before the destination storage device <NUM> includes a complete copy of the data on the source storage device <NUM>. As a result, there is a possibility that the guest <NUM> may request a read from a logical address of the destination storage device <NUM> when the destination storage device <NUM> does not yet store the data that the guest <NUM> attempts to read. To deal with this scenario, the destination storage device <NUM> stores a code in the L2P mapping <NUM> that indicates logical addresses that have not yet been migrated. When the destination storage device <NUM> determines that a read operation is requested for a logical address associated with the code, the storage devices <NUM>, <NUM> and the management module <NUM> interact to provide the appropriate data from the source storage device <NUM>.

In further detail, during stage (A), the guest <NUM> initially accesses the source storage device <NUM>. The guest <NUM> may send read requests for data stored by the source storage device <NUM>, receive data from the source storage device <NUM>, and send write requests of data to be stored by the source storage device <NUM>.

During stage (B), the management module <NUM> prepares the destination storage device <NUM> in order to transition access by the guest <NUM> from the source storage device <NUM> to the designation storage device <NUM>. The management module <NUM> modifies the L2P mapping <NUM> of the destination storage device <NUM> (or issues commands for the destination storage device <NUM> to do so) such that each logical address in the L2P mapping <NUM> is associated with a particular code. The code may be, for example, a reserved value, flag, or invalid physical address that indicates that the data associated with the logical address is invalid. For example, the code can be a physical address that does not correspond to any storage location of the one or more non-volatile storage device(s) <NUM>. As a result, a read request that attempts to read the data from a logical address mapped to the code can prompt the memory controller <NUM> to generate an event or error.

In the illustrated example, the physical address value for each logical address of the destination storage device <NUM> is set to "xFFFF," or negative <NUM>, which is not a valid physical address. The invalid address may be one of multiple different invalid addresses that are used to trigger different actions or events by the memory controller <NUM> when a read is attempted. In addition to or as an alternative to storing a code in a physical address field of the L2P mapping <NUM>, a code may be stored as a flag or other value stored in addition to a physical address, or a code stored in another manner.

During stage (C), the management module <NUM> suspends the virtual environment for the guest <NUM> and discontinues access to the source storage device <NUM> by the guest <NUM>.

During stage (D), the management module <NUM> resumes the virtual environment for the guest <NUM> and provides the guest <NUM> access to the destination storage device <NUM>, e.g., over the logical interface <NUM> of the destination storage device <NUM>. From the perspective of the guest <NUM>, there is no indication that one storage device has been substituted for another. The guest <NUM> may continue to issue logical read and write requests to the destination storage device <NUM> as if the source storage device <NUM> were still connected.

After the transition to the destination storage device <NUM>, write requests from the guest <NUM> are directed to the destination storage device <NUM>. Write operations may be performed in the same manner described above with respect to <FIG>. The process of carrying out a write operation to the destination storage device <NUM> involves writing a physical address to the L2P mapping <NUM>. Therefore, any writes to the destination storage device <NUM> will clear the code, e.g., "xFFFF," that indicates that the associated data is invalid. Subsequent reads from these addresses may be performed by the destination storage device in the normal manner. In addition, the process of writing data to the destination storage device <NUM> involves notifying the management module <NUM> of the write, using a write request event as shown in <FIG>. This allows the management module <NUM> to determine that the data being written to the destination storage device <NUM> is more current than the data not yet migrated from the source storage device <NUM>, so that the management module <NUM> can avoid overwriting current data in the destination storage device <NUM> with outdated data from the source storage device <NUM>.

At some point, before or after stage (D), the management module <NUM> may initiate migration of data stored by the source storage device <NUM> to the destination storage device <NUM>. For example, the management module <NUM> may issue commands causing data to be copied from the source storage device <NUM> to the destination storage device <NUM>. In some instances, the data is transferred from the source storage device <NUM> to the destination storage device <NUM> over a network. In some instances, if the storage devices <NUM>, <NUM> are directly attached to the same host system, data may be transferred from the source storage device <NUM> to the destination storage device <NUM> without transfer over a network.

The copying causes the L2P mapping <NUM> of the destination storage device <NUM> to be updated, so that the logical addresses of the destination storage device <NUM> and the source storage device <NUM> map to locations storing the same data. The physical addresses corresponding to a logical address need not be the same in the different L2P mappings, as long as the physical addresses correspond to locations storing the same data. As an example, a logical address of "x1234" may map to a physical address of "x3745" in the source storage device <NUM>, and a physical address of "x7382" in the destination storage device <NUM> if the data stored in the locations specified by the two physical addresses is the same.

In some implementations, in addition to immediately copying the data from the source storage device <NUM> to the destination storage device <NUM>, or instead of immediately copying the data from the source storage device <NUM> to the destination storage device <NUM>, the management module <NUM> can copy data for specific logical addresses as the guest <NUM> requests data to be read from those logical addresses. Thus, copying may progress as the guest <NUM> issues additional read requests to the destination storage device <NUM> for data stored by the source storage device <NUM>. When the guest <NUM> is overwriting a significant amount of data, for example, copying data in response to read requests rather than making a full copy may avoid unnecessary copying of data that is likely to be overwritten.

During stage (E), the guest <NUM> sends a read request <NUM> to the destination storage device <NUM> over the logical interface <NUM>. In the example, the read request <NUM> is sent before migration is complete, and the destination storage device <NUM> does not store the data requested. The read request <NUM> can include a logical address of requested data, e.g., "x2536. " The read request <NUM> may also indicate a destination address of the guest <NUM> in which to store the retrieved data. The guest <NUM> generates the read request <NUM> as if the guest <NUM> were accessing the source storage device <NUM>. Accordingly, the guest <NUM> uses the same logical addresses for the read request <NUM> that were used with the source storage device <NUM>, and the switch is not discernable to the guest <NUM>.

During stage (F), in response to receiving the read request <NUM>, the memory controller <NUM> identifies the logical address indicated by the read request <NUM> within the L2P mapping <NUM> of the destination storage device <NUM>. The memory controller <NUM> determines that the value mapped to the identified logical address is not a valid physical address. Based on the value, the memory controller <NUM> determines that an event that should be issued over the event interface <NUM>. The memory controller <NUM> also determines that the read operation should be halted, and so the memory controller <NUM> suspends or blocks the read operation. In the illustrated example, the memory controller <NUM> determines that for the logical address "x2536," the mapped physical address is a negative value, e.g., "xFFFF. " The memory controller <NUM> may also determine which event or predetermined action is associated with the particular code identified.

In some implementations, the L2P mapping <NUM> includes status fields, separate from the physical addresses, that are associated with logical addresses. The status field can indicate a coded value. In such implementations, the memory controller <NUM> may evaluate the status field associated with the logical address indicated by the read request <NUM> to determine whether to suspend a read and/or issue an event, rather than evaluating the value in a physical address field.

During stage (G), the memory controller <NUM> sends a read event <NUM> to the management module <NUM> over the event interface <NUM> in response to detecting the code in the L2P mapping <NUM>. In the example, the identified code corresponds to a read event, so the memory controller <NUM> sends a read event <NUM> to the management module <NUM>. The read event <NUM> indicates the logical address of the read request <NUM>. In some implementations, the read event <NUM> also includes the code included in the L2P mapping <NUM>.

During stage (H), the management module <NUM> retrieves the data associated with the read event <NUM> from non-volatile storage device(s) <NUM> of the source storage device <NUM>. For example, in response to receiving the read event <NUM>, the management module <NUM> determines which storage device includes the requested data, and issues read commands to the source storage device <NUM> over a physical interface or logical interface of the source storage device <NUM>. The source storage device <NUM> provides the requested data corresponding to the logical address specified by the management module, e.g., "x2536.

During stage (I), the management module <NUM> transmits a physical write command <NUM> to the destination storage device <NUM> over the physical interface <NUM>. The physical write command <NUM> instructs the memory controller <NUM> to write the retrieved data from the source storage device <NUM> to the non-volatile storage device(s) <NUM> of the destination storage device <NUM>, at a physical address determined by the management module <NUM>. In the illustrated example, the physical write command identifies the physical address "x9648" as the address of the storage location to store the data. Although not illustrated, the write command <NUM> may also indicate the logical address of the destination, and/or a source address for obtaining the data to be written.

During stage (J), the memory controller <NUM> stores the retrieved data in the non-volatile storage device(s) <NUM>, according to the write command <NUM>. The memory controller <NUM> also updates the L2P mapping <NUM> to indicate the physical address of the storage locations mapped to the logical address of the read request <NUM>. In the illustrated example, the L2P mapping <NUM> is updated such that the physical address of "x9648" is associated with the logical address of "x2356.

During stage (K), the memory controller <NUM> unblocks the read request <NUM> of the guest <NUM>, and completes the read using normal procedures. The read request may be unblocked in response to, for example, the write to the logical address that triggered the read operation to be suspended, or in response to a communication from the management module <NUM>. To complete the read operation, the memory controller <NUM> identifies the physical address associated with the logical address of the read request <NUM>, obtains the data stored at the physical address indicated by the updated L2P mapping, and provides the obtained data to the guest <NUM>.

<FIG> is a block diagram that illustrates a system <NUM> for migrating data between storage devices. The system <NUM> includes the source storage device <NUM> and the storage device <NUM>, referred to as a destination storage device <NUM>. The source storage device <NUM> and the destination storage device <NUM> are both managed by the management module <NUM>. The system also includes the guest <NUM>, which initially accesses the source storage device <NUM>. The management module <NUM> transitions the guest <NUM> from using the source storage device <NUM> to using the destination storage device <NUM>, while allowing read and write access of the guest <NUM> during most of the migration process.

In the example of <FIG>, the management module <NUM> migrates data from the source data storage device <NUM> to the destination data storage device <NUM> while maintaining the access of the guest <NUM> to the source data storage device <NUM>. The transfer of the guest's <NUM> access from the source data storage device <NUM> to the destination data storage device <NUM> may be performed after migration is complete, e.g., after the destination storage device <NUM> includes a complete copy of the data on the source storage device <NUM>. While copying is occurring, however, the guest <NUM> may make additional writes to the source storage device <NUM>, causing data previously copied to the destination storage device <NUM> to be outdated. To address this possibility, the management module <NUM> tracks writes made to the source storage device <NUM> and also makes the same writes to the destination storage device <NUM>. As a result, writes to the source storage device <NUM> are propagated to the destination storage device <NUM> as well.

During stage (B), the management module <NUM> initiates migration of data stored by the source storage device <NUM> to the destination storage device <NUM>. The management module <NUM> also initializes a transition table <NUM>, which is stored at the host <NUM>, that allows the management module <NUM> to track which logical addresses the guest <NUM> writes to after the migration of data begins. The transition table <NUM> may include, for example, a first column <NUM> that includes logical addresses and a second column <NUM> that indicates a status of whether the destination storage device <NUM> currently stores the current data associated with the corresponding logical address. In the illustrated example, a status value of "<NUM>" can indicate that the data at the corresponding logical address is current at the destination storage device <NUM>. A status of "<NUM>" can indicate that the data at the corresponding logical address is not current on the destination storage device <NUM>, e.g., the guest <NUM> has written data to the logical address at the source storage device <NUM> that has not been transferred to the destination storage device <NUM>, or the data has not yet been copied from the source storage device <NUM>. In some implementations, at the beginning of migration, the management module <NUM> initializes the transition table <NUM> to indicate that data is outdated at the destination storage device <NUM> for all logical addresses, e.g., all logical addresses would have a status value of "<NUM>" in the example.

During stage (C), the management module <NUM> migrates data from the source storage device <NUM> to the destination storage device <NUM>. As the management module <NUM> copies the data from the source storage device <NUM> to the destination storage device <NUM>, the management module <NUM> updates the transition table <NUM> to indicate that the copied data is valid on the destination storage device <NUM>. For example, after copying the data corresponding to logical address "x2356" from the source storage device <NUM> to the destination storage device <NUM>, the status value corresponding to the logical address "x2356" is updated to "<NUM>" to indicate that the associated data is current.

During stage (D), the guest <NUM> continues to access the source storage device <NUM> during the migration process. The guest <NUM> can provide a read request <NUM> to the source storage device <NUM>, and the data indicated by the read request <NUM> is provided by the source storage device <NUM>. That is, read operations do not affect the destination storage device <NUM>, or the migration process.

During stage (E), the guest <NUM> sends a write request (not shown) to the source storage device <NUM>, as described above with respect to <FIG>. The write operation is made to the source storage device <NUM> as discussed with respect to <FIG>. In addition, in response to the write event that the source storage device <NUM> provides, the management module <NUM> updates the transition table <NUM>. In particular, since the source storage device <NUM> is in the process of being migrated, the management module <NUM> updates the status value associated with the logical address of the write as not being current on the destination storage device <NUM>, e.g., a status value of "<NUM>. " This indicates that the write request by the guest <NUM> supersedes any data that may have been previously copied for the logical address of the write request, even if the data corresponding to the logical address had been current at the destination storage device at one time.

During stage (F), the management module <NUM> continues the migration of data from the source storage device <NUM> to the destination storage device <NUM>. For example, the management module <NUM> continues to issue read commands to the source storage device <NUM> and write commands to the destination storage device <NUM> to copy data for all logical that are have a value of "<NUM>" in the status value table. After data corresponding to a logical address is copied, the status value is updated to "<NUM>" to indicate that the current data resides on the destination storage device <NUM>.

During stage (G), the management module <NUM> determines that the migration of data from the source storage device <NUM> to the destination storage device <NUM> is complete. For example, the management module <NUM> examines the transition table <NUM> and determines that each of the logical addresses, or at least predetermined amount of the logical addresses, have a status value of "<NUM>" in the transition table <NUM>.

During stage (H), the management module <NUM> provides the guest <NUM> with access to the destination storage device <NUM>. For example, the management module <NUM> may briefly stop the virtual environment for the guest <NUM> and then resume the virtual environment after substituting access to the destination storage device <NUM> for access to the source storage device <NUM>. Because the data on the source storage device <NUM> has been transferred to the destination storage device <NUM>, the source storage device <NUM> may be erased or used for another purpose.

During stage (I), the guest <NUM> accesses the destination storage device <NUM>. The guest <NUM> is unaware of the switch of access from the source storage device <NUM> to the destination storage device <NUM>. That is, the change does not affect read and write access by the guest <NUM>, and generally is not discernible to the guest <NUM>.

The migration techniques described with respect to <FIG> and <FIG> may be combined. For example, migration may be initiated with one of the techniques, and may be completed with the other technique. Similarly, invalid physical addresses or other codes may be used in a L2P mapping to avoid reads of invalid data, and a management module <NUM> may also use a transition table or other mechanism to track writes to be applied to one or more storage devices.

The migration technique discussed with respect to <FIG> may be more efficient in scenarios where the guest <NUM> is primarily reading data. When the guest <NUM> workload is focused on read operations, each piece of data may be copied to the destination storage device <NUM> once, since the guest <NUM> is not writing new versions and the data copied to the destination does not become out of date. In addition, read operations may be performed quickly because guest <NUM> is still in communication with the source storage device <NUM>, which includes all of the current data that the guest <NUM> may wish to access.

The migration technique of <FIG> may be more efficient when the guest <NUM> is writing large amounts of data. Large amounts of writes may slow migration using the technique of <FIG>, because previously data from previously copied locations may need to be re-copied to the destination storage device <NUM> as new data is written to the source storage device <NUM>. If the host <NUM> is not able to copy data to the destination drive faster than the guest <NUM> is writing new data to the source storage device <NUM>, the migration process may proceed slowly or stall. The host <NUM> may evaluate the amount or frequency of write requests by the guest <NUM> or the speed that migration is progressing. From this evaluation the host <NUM> may determine to transition to from the migration technique of <FIG> to the technique of <FIG>, allowing access to the source storage device <NUM> to be suspended before a complete copy is made. By using to the technique of <FIG>, access may be transferred to the destination storage device <NUM>, so that the writes are made directly to the destination storage device <NUM> instead of first being made to the source storage device <NUM>. In a write-heavy workload, the need to read data from the source storage device <NUM> will be relatively rare, since the guest <NUM> is primarily generating new data.

<FIG> depicts a flow diagram that illustrates an example of a process <NUM> for managing storage devices. The process <NUM> can be executed using one or more processing devices. For example, the memory controller <NUM> of the storage device <NUM> or another processor may perform the operations of the process <NUM>.

A logical write request is received by a memory controller over a logical interface (<NUM>). The memory controller provides the logical interface for accessing a non-volatile storage device. The logical write request indicates a logical address at which to write data to the non-volatile storage device. The logical write request may be received over a NVMe interface or an AHCl interface.

In some implementations, the data to be written is received through a direct memory access (DMA) transfer. The data may be received from, for example, an application or virtualized operating system, or other system other than the host system that manages the storage device including the memory controller.

In response to receiving the logical write request, the memory controller may allocate a write buffer for storing the data. For example, a write buffer may be allocated in volatile memory, such as DRAM. The memory controller may then store the data in the allocated write buffer. In some implementations, an acknowledgement of the write indicated by the logical write request is provided after storing the data in the allocated write buffer and before storing the data in the non-volatile storage devices.

A write request event is sent by the memory controller to a host system (<NUM>). The write request may be sent in response to receiving the logical write request by the memory controller. In some implementations, the write request event indicates (i) a buffer address for a write buffer storing the data to be written and (ii) the logical address indicated by the logical write request. the write request event may be sent to the host system without sending the data to be written to the host system.

A physical write command is received at the memory controller from the host system over a physical interface (<NUM>). The memory controller provides the physical interface for accessing the non-volatile storage device. The physical write command instructs the memory controller to write the data to the non-volatile storage device. In some implementations, the physical write command indicates (i) the write buffer address for the write buffer storing the data and (ii) one or more physical pages of the non-volatile storage device in which to store the data to be written. For example, the physical write command may indicate physical NAND flash pages in which to write the data. The physical write command may be received by the memory controller without receiving the data to be written from the host system. The physical write command may be received over a PCI-e interface.

The data is stored by the memory controller according to the physical write command (<NUM>). The data is stored in response receiving the physical write command from the host system. When the physical write command indicates specific physical pages of the non-volatile storage device, e.g., with corresponding physical addresses, the data may be stored in the specified physical pages. After storing the data in the non-volatile storage device, the memory controller may deallocate a write buffer storing the data that was written.

After storing the data in the non-volatile storage device, the memory controller updates the logical-to-physical mapping table managed by the memory controller. The logical address indicated in the logical write request is mapped to the physical address indicated by the physical write command from the host system. An acknowledgment of the write indicated by the logical write request may also be provided after storing the data in the non-volatile storage device.

All of the functional operations described in this specification may be implemented in digital electronic circuitry, or in computer software, firmware, or hardware, including the structures disclosed in this specification and their structural equivalents, or in combinations of one or more of them. The techniques disclosed may be implemented as one or more computer program products, i.e., one or more modules of computer program instructions encoded on a computer-readable medium for execution by, or to control the operation of, data processing apparatus. The computer readable-medium may be a machine-readable storage device, a machine-readable storage substrate, a memory device, a composition of matter affecting a machine-readable propagated signal, or a combination of one or more of them. The computer-readable medium may be a non-transitory computer-readable medium. The apparatus may include, in addition to hardware, code that creates an execution environment for the computer program in question, e.g., code that constitutes processor firmware, a protocol stack, a database management system, an operating system, or a combination of one or more of them. A propagated signal is an artificially generated signal, e.g., a machine-generated electrical, optical, or electromagnetic signal that is generated to encode information for transmission to suitable receiver apparatus.

A computer program (also known as a program, software, software application, script, or code) may be written in any form of programming language, including compiled or interpreted languages, and it may be deployed in any form, including as a standalone program or as a module, component, subroutine, or other unit suitable for use in a computing environment. A program may be stored in a portion of a file that holds other programs or data (e.g., one or more scripts stored in a markup language document), in a single file dedicated to the program in question, or in multiple coordinated files (e.g., files that store one or more modules, sub programs, or portions of code). A computer program may be deployed to be executed on one computer or on multiple computers that are located at one site or distributed across multiple sites and interconnected by a communication network.

The processes and logic flows described in this specification may be performed by one or more programmable processors executing one or more computer programs to perform functions by operating on input data and generating output. The processes and logic flows may also be performed by, and apparatus may also be implemented as, special purpose logic circuitry, e.g., an FPGA (field programmable gate array) or an ASIC (application specific integrated circuit).

Moreover, a computer may be embedded in another device, e.g., a tablet computer, a mobile telephone, a personal digital assistant (PDA), a mobile audio player, a Global Positioning System (GPS) receiver, to name just a few. Computer readable media suitable for storing computer program instructions and data include all forms of non-volatile memory, media and memory devices, including by way of example semiconductor memory devices, e.g., EPROM, EEPROM, and flash memory devices; magnetic disks, e.g., internal hard disks or removable disks; magneto-optical disks; and CD-ROM and DVD-ROM disks.

To provide for interaction with a user, the techniques disclosed may be implemented on a computer having a display device, e.g., a CRT (cathode ray tube) or LCD (liquid crystal display) monitor, for displaying information to the user and a keyboard and a pointing device, e.g., a mouse or a trackball, by which the user may provide input to the computer. Other kinds of devices may be used to provide for interaction with a user as well; for example, feedback provided to the user may be any form of sensory feedback, e.g., visual feedback, auditory feedback, or tactile feedback; and input from the user may be received in any form, including acoustic, speech, or tactile input.

Implementations may include a computing system that includes a back end component, e.g., as a data server, or that includes a middleware component, e.g., an application server, or that includes a front end component, e.g., a client computer having a graphical user interface or a Web browser through which a user may interact with an implementation of the techniques disclosed, or any combination of one or more such back end, middleware, or front end components. The components of the system may be interconnected by any form or medium of digital data communication, e.g., a communication network.

While this specification contains many specifics, these should not be construed as limitations, but rather as descriptions of features specific to particular implementations. Certain features that are described in this specification in the context of separate implementations may also be implemented in combination in a single implementation. Conversely, various features that are described in the context of a single implementation may also be implemented in multiple implementations separately or in any suitable subcombination. Moreover, although features may be described above as acting in certain combinations and even initially claimed as such, one or more features from a claimed combination may in some cases be excised from the combination, and the claimed combination may be directed to a subcombination or variation of a subcombination.

Moreover, the separation of various system components in the implementations described above should not be understood as requiring such separation in all implementations, and it should be understood that the described program components and systems may generally be integrated together in a single software product or packaged into multiple software products.

Claim 1:
A method comprising:
providing, by a host system, a virtual environment to a guest device (<NUM>) and providing the guest device access to a source storage device managed by the host system;
initiating migration of contents of the source storage device (<NUM>) to a destination storage device (<NUM>);
modifying a logical to physical mapping (<NUM>) of the destination storage device such that each logical address in the logical to physical mapping is associated with a particular code that indicates that the data associated with the logical address is invalid;
suspending the virtual environment for the guest device and discontinuing access to the source storage device by the guest;
before completing migration of the source storage device to the destination storage device, resuming the virtual environment for the guest device and providing the guest device access to the destination storage device (<NUM>) instead of the source storage device (<NUM>);
providing the guest device access to the destination storage (<NUM>) device over a logical interface (<NUM>) of the destination storage device; and
directing write requests from the guest device (<NUM>) to the destination storage device (<NUM>), wherein carrying out write operations to the destination storage device (<NUM>) in response to the write requests involves, for each write operation, writing a physical address to the logical to physical mapping (<NUM>) such that the particular code is cleared.