Patent Description:
The growing use of machine virtualization has led to increased demand for understanding the execution of a VM, analyzing performance, maintaining a record of a VM's computing activity, and debugging execution of a VM and/or its guest software. VM execution tracing is one technique that has suggested for these purposes. Execution tracing involves tracing the execution activities of a VM and storing the execution trace for later analysis. An execution trace can be used for detailed post-execution analysis and debugging of VM execution. Ideally, an execution trace is deterministic and "replayable", i.e. it has sufficient information to enable playback features commonly found in software debugging tools such as stepwise execution of statements, reverse playback, detailed stack and symbol analysis before and after each statement, etc..

Although VM execution tracing has been recognized as desirable, previous attempts have had shortcomings in implementation and performance. One approach has been to force a VM to execute in a single thread of execution, which facilitates determinism but is difficult to implement and limits performance. For many types of guest software for which parallelism is critical, this limitation prohibits production use. Another approach has been to capture all of a VMs memory, but this carries startup and storage costs. Yet another approach has been to use complex run-time monitoring of memory states to maintain trace determinism, but this is difficult to implement correctly, has high overhead, and can significantly impact the performance of some workloads. Instrument guest software with trace-enabling instructions is another possibility but this has the practical drawback of requiring recompiling and deploying new executable code. Others have tried to interpose trace logic between a VM and a hypervisor, but with mixed success and many platform specificities.

What is needed are techniques for replayable VM execution tracing that are convenient to implement at the virtualization layer, have a low impact on VM performance, maintain causality for concurrent multiprocessing VMs, and can be used with or without VM visibility or actions.

<CIT> describes technologies which pertain to performing time travel debugging. A computer-executable program can be executed. The computer-executable program can be executable under control of a virtual machine. The virtual machine can interact with a browser system during execution of the computer-executable program. Moreover, nondeterministic events can be logged via an interrogative virtual machine interface (VMI) during the execution of the computer-executable program. The nondeterministic events can be logged as part of event logs. Moreover, the interrogative VMI is between the virtual machine and the browser system. Further, snapshots of the virtual machine can be captured during the execution of the computer-executable program. The snapshots can be captured via the interrogative VMI. At least a portion of the execution of the computer-executable program can be replayed based at least in part on a snapshot and at least a portion of the event logs.

<NPL> describes that happen-before causal partial orders have been widely used in concurrent program verification and testing. The paper presents a parametric approach to happen-before causal partial orders. Existing variants of happen-before relations can be obtained as instances of the parametric framework. A causal partial order, called sliced causality, is then defined also as an instance of the parametric framework, which loosens the obvious but strict happen-before relation by considering static and dynamic dependence information about the program.

Many of the attendant features will be explained below with reference to the following detailed description considered in connection with the accompanying drawings.

The present description will be better understood from the following detailed description read in light of the accompanying drawings, wherein like reference numerals are used to designate like parts in the accompanying description.

Embodiments discussed below relate to tracing execution of virtual machines (VMs) in ways that are efficient, accurately reflect causality. Execution tracing is provided by a trace component within the virtualization layer. The trace component is able to trace parallel VM execution in a way that produces replayable execution traces. A VM may be traced with or without involvement of the guest software within executing within the VM. A trace may be flexibly scoped in terms of when tracing occurs and which VMs or guest software are effectively traced. Several techniques may be used to secure guest data.

<FIG> shows an example virtualization environment that includes a known type of hypervisor <NUM>. A computer <NUM> has hardware <NUM>, including a central processing unit (CPU) <NUM>, memory <NUM>, a network interface <NUM>, non-volatile storage <NUM>, and other components not shown, such as a bus, a display and/or display adapter, etc. The hypervisor <NUM> manages and facilitates execution of virtual machines (VMs) <NUM>, <NUM>. Each virtual machine <NUM>, <NUM> typically has virtualized devices including a virtual disk within which a guest/host operating system <NUM>, <NUM> is stored. Machine or system virtualization is provided by the hypervisor <NUM> cooperating with a host operating system <NUM> that executes in a privileged VM <NUM>.

The tasks of virtualization may be distributed among the hypervisor <NUM> and the host operating system <NUM> in a number of ways. In some cases, the host operating system <NUM> might consist only of minimal virtualization elements such as tools and user interfaces for managing the hypervisor <NUM>. In other cases, the host operating system <NUM> might include one or more of: device virtualization management, inter-VM communication facilities, running device drivers, starting or stopping other VMs, tools for interactive VM management, and others. In short, the guest operating system <NUM> can potentially handle any virtualization tasks outside core functions of a hypervisor such as CPU and memory sharing. As used herein, "virtualization layer" will refer to any combination of hypervisor and guest VM that collectively provide machine virtualization. The term also refers to virtualization systems that do not use a privileged VM to provide virtualization functionality.

<FIG> shows a virtualization layer <NUM> configured for VM execution tracing. The virtualization layer <NUM> includes a trace component <NUM> and ring buffer <NUM>. Generally, the trace component <NUM> operates as follows. When a virtual processor <NUM> of the virtual machine <NUM> is scheduled for processing time by backing physical processors of the CPU <NUM>, a context switch occurs for the corresponding guest execution unit (e.g., a thread) and processor instructions of that execution (execution stream <NUM>) are processed by the backing physical processor (the term "physical processor" as used herein refers to both physical cores and logical cores in the case of hyperthreaded CPUs). The instructions of the execution stream <NUM> issued by software in the virtual machine are captured by the trace component <NUM> as they are received or executed and stored in the ring buffer <NUM>. In one embodiment, instructions are captured using hardware-based trace features of the CPU. In another embodiment, the virtualization layer implements processor emulation and the instruction capturing is built into the processor emulator. In most cases, all instructions are captured when execution tracing is in effect. Execution trace data in the ring buffer <NUM> may be selective or continuously stored as a persistent execution trace <NUM> in some local (e.g., a privileged VM's filesystem) or network storage.

Although a ring buffer is convenient and provides certain advantages, other types of buffers may be used. Full tracing likely will not require a circular buffer. As discussed below, buffering can be useful for selective tracing where a particular scope of execution is to be traced (e.g., certain modules, processes, threads, VMs, etc.).

In addition to capturing instructions the execution trace will include data in memory that is touched by the execution of the thread or other execution unit. This involves, instead of copying all memory of the VM <NUM>, copying each piece of memory as it is accessed by the execution being traced; conceptually, the inputs and outputs of the instructions are captured as they are being consumed. (perhaps with compression). Accessed register contents are also captured. Each thread generally consumes its own memory in its own way, and what the other threads do is irrelevant. If a kernel call or another thread modifies the traced thread's memory then those external memory modifications can be captured by the trace component <NUM>. For additional details see <CIT>), and <CIT>).

In one embodiment, all of the execution of a target VM is traced. Because the virtualization layer <NUM> knows when the CPU is executing instructions from the target VM, the virtualization layer <NUM> knows when to perform tracing (when the target VM is executing) and when not to. Thus, the generated trace includes only the activities of the target VM. Even if the target VM has multiple virtual processors (VPs) the virtualization layer <NUM>, which handles CPU scheduling, knows when a VP is executing code for the target VM and traces accordingly. Each thread or execution unit of the target virtual machine is recorded as a separate respective trace set and contains the instructions, memory/registers consumed by same, etc. Post-trace symbol analysis (e.g., during later debugging) can be enabled by recording information that associates each traced instruction with an identifier indicating the executable file or object model or the like that provided the instruction. This allows later reconstruction of symbols from the trace in the same way debuggers provide symbol information.

Most traced execution will have some non-deterministic events that will have to be handled. Non-deterministic instructions are instructions whose output depends on information outside the information that is being tracked for tracing. A first step handling on-deterministic instructions is identifying instructions as such. Once a non-deterministic instruction is detected, the side effects thereof are recorded in the trace and the side effects are reproduced during replay. For example, if an instruction is found to generate a random number, that may be hard to replay with the precision of the original instruction result, so one solution is to record the side effects (in this example, the value of the registry where the random number is located) and at replay time we that number is placed in the appropriate register instead of (or after) executing the original instruction. Another example would be a trace of instruction to read a processor timer. If this is not fully tracked then the side effect can be placed in the trace and at replay time the side effect is used instead of reading the processor timer.

Tracing multiple concurrent threads/VPs presents issues of ordering and causality. If two threads of execution of a traced VM are executing concurrently they can potentially overlap. In order to enable reasoning through causalities in the traces of the respective threads, order of execution is important to consider. While it is possible to include a rich set of trace information to strictly order threads among themselves in a deterministic way, a less burdensome approach is to model trace access to memory in a way that enables sufficient relative ordering for causality without requiring strict ordering relative to all instructions. This can be done by implementing modelling memory for tracing such that reading from memory has acquire semantics and writing to memory has release semantics and ordering and recording those corresponding events. See the aforementioned patent applications for additional details. Because the tracing is done at the virtualization layer the threads/VPs are traced from a common view of causality at the virtualization layer. This same approach can be used not only to order execution of threads of a given VM, but also to order execution of threads of concurrent VMs relative to each other.

Because tracing occurs at the virtualization layer or hypervisor, threads are threads and can be traced regardless of VM execution since memory can be ordered across any two threads. Thus, causality-preserving tracing across machines is possible. This can enable new types of debugging not previously possible. The interactions between software on two different machines (albeit virtual) can be closely correlated.

<FIG> shows a process for ordering thread traces at the virtualization layer. At step <NUM> tracing begins for whichever VM threads start executing. At step <NUM> execution tracing is performed as discussed above; thread instructions, memory accesses, registers, etc. are recorded as executed in sets for each respective thread. At step <NUM> a context switch is detected. Each time a context switch is detected, an ordering marker is inserted into the corresponding thread and an incremented value of the inserted ordering marker is stored and then similarly used the next time an ordering marker is needed. Not that an ordering marker may be inserted into a swapped-in thread, a swapped-out thread, or both. This continues for each thread until it ends at step <NUM>.

<FIG> shows ordering markers <NUM> inserted into traces <NUM> of respective threads. Each trace segment <NUM> (shaded portion) represents a segment of traced instructions and corresponding input/output data that occurs in a same processor context. While strict ordering might not be guaranteed among instructions in a trace segment <NUM>, ordering among the trace segments <NUM> (with respect to each other) is guaranteed by the ordering markers <NUM>. The context switches represented by the ordering markers <NUM> may be a switch due to a guest switching threads, CPU scheduling (timeslicing) by the virtualization layer, etc. The ordering markers may be numbers in any monotonically increasing sequence. The markers might be a global value that increments once for each context switch. For some CPUs, the markers might be timestamp counters provided by the CPU (consistent across all CPU cores). Although all instructions of a trace of a VM or a thread might not be fully ordered, partial ordering and causality is assured, including among VMs if multiple VMs are being traced. Note that the degree to which causality is assured may depends on the memory model that is selected and the amount of analysis a user is willing to do on the trace.

Using the trace techniques described above, a variety of trace control functions (described below) may be implemented by the virtualization layer and/or by a privileged VM that provides virtualization functionality as discussed above. The trace control functions control when and/or how tracing is performed or stored. The trace control functions may be implemented by combinations of hypervisor hypercalls, virtualization interfaces exposed by a privileged VM, etc. Although, guests may be instrumented to take advantage of any trace control functions, the trace control functions may instead be invoked by a privileged VM to control tracing for un-instrumented guests. The trace functions described next may be invoked by an instrumented guest or for an un-instrumented by the privileged VM. If the virtualization layer and/or privileged VM provide an interface for invoking trace functions, such interfaces might be in the form of a user interface provided by the privileged VM, through a REST API (Representational State Application Programming Interface), a virtual device driver, a network port, or any other mechanism to communicate with the virtualization layer to control tracing.

Before describing the trace functions, the use of the ring buffer <NUM> will be explained. The ring buffer is a buffer for storing a forward moving window of execution traces. In some embodiments, the ring buffer may be in continuous use but without persisting the trace data stored in the buffer. The buffer stores trace data in case tracing is invoked during execution of a target VM. The ring buffer is also useful for buffering data that might be needed for capturing trace data. For instance, tracing a non-deterministic event might require access to buffered data that would not otherwise be available at the time of the event. The ring buffer may use keyframes to handle wrapping. For example, a keyframe might be added at every <NUM>% chunk of the buffer so that only <NUM>% of the buffer is lost as each new piece of data is added. The ring buffer is also a useful place for performing compression (see above-referenced patent applications) and/or for performing encryption (discussed below).

One of the trace functions is a simple on/off function for turning tracing on or off. The on/off function may have a variety of parameters. One parameter may be the target to be traced. The target may be one or more identified individual VMs or the calling VM (implicit). The target might be an individual process or set of processes. Another parameter may be time extents of the trace. The time might be defined as a time range, for instance, a duration (including possibly backward in time as permitted by how far back the contents of the ring buffer go).

Another trace function is a periodic trace function. Tracing can be activated for periods of time to sample trace data. For example, tracing might be captured <NUM> second per minute, <NUM> minutes once per hour, etc. The ring buffer may be in effect for sufficient encompassing time periods to enable the sampling.

Yet another trace function is event-based tracing. Tracing can be linked to identified events such as hypercalls, interrupts, system events (e.g., a process crash) or the like to automatically trace data at times linked to the identified events. Note that any of the trace functions above can potentially be scoped in the same way as the on/off function. That is, any type of trace control may be scoped to a particular process, VM, particular processes on any VMs, a defined VM set, etc. Event-based tracing and other functions for ad hoc trace recording may require that tracing is being performed in the ring buffer and trace data from the ring buffer is only persisted when needed.

Still another trace function is trace encryption. Because VMs may be in different security domains and cross-VM data leaks would be considered security breaches, it is possible for the virtualization layer to encrypt trace data from memory (i.e., instruction inputs and outputs, as well as registers) before it is stored for later post-processing analysis. If the virtualization layer has a key that is private to a VM, the key can be used to encrypt at least the data of a trace of that VM. A debugger configured with a decryption module can potentially use the key to perform debugging on the encrypted trace data. In one embodiment, encryption is used when a non-instrumented VM is traced at the request of another VM. That is, security measures can be triggered based on the relative security levels of the traced VM and the trace-requesting VM.

It should be noted that the trace techniques described herein do not require that the virtualization layer run directly on hardware. Nested VMs can use the same techniques without modification. In other words, a virtualization layer executing within a VM may itself perform tracing of its VMs. If CPU hardware tracing is to be used, the CPU trace features may be used whenever the nested virtualization layer has a slice of CPU time.

<FIG> shows details of the computing device <NUM> on which embodiments described above may be implemented. The technical disclosures herein will suffice for programmers to write software, and/or configure reconfigurable processing hardware (e.g., field-programmable gate arrays (FPGAs)), and/or design application-specific integrated circuits (ASICs), etc., to run on the computing device <NUM> to implement any of the features or embodiments described herein.

The computing device <NUM> may have one or more displays <NUM>, a network interface <NUM> (or several), as well as storage hardware <NUM> and processing hardware <NUM>, which may be a combination of any one or more: central processing units, graphics processing units, analog-to-digital converters, bus chips, FPGAs, ASICs, Application-specific Standard Products (ASSPs), or Complex Programmable Logic Devices (CPLDs), etc. The storage hardware <NUM> may be any combination of magnetic storage, static memory, volatile memory, non-volatile memory, optically or magnetically readable matter, etc. The meaning of the term "storage", as used herein does not refer to signals or energy per se, but rather refers to physical apparatuses and states of matter. The hardware elements of the computing device <NUM> may cooperate in ways well understood in the art of machine computing. In addition, input devices may be integrated with or in communication with the computing device <NUM>. The computing device <NUM> may have any form-factor or may be used in any type of encompassing device. The computing device <NUM> may be in the form of a handheld device such as a smartphone, a tablet computer, a gaming device, a server, a rack-mounted or backplaned computer-on-a-board, a system-on-a-chip, or others.

Claim 1:
A method for operating a virtualization layer (<NUM>) comprising a hypervisor (<NUM>), wherein the method is operated on a virtual machine (<NUM>; <NUM>) comprising
a guest operating system (<NUM>; <NUM>), wherein the guest operating system comprises a guest kernel, and
virtual processors (<NUM>) managed by the virtualization layer, wherein the guest kernel is configured to issue guest instructions to the virtual processors; wherein
the method performed by the virtualization layer comprises:
capturing and storing (<NUM>), into a trace file, indicia of whichever guest instructions are issued by the guest kernel to the virtual processors,
wherein the trace file (<NUM>) comprising sets (<NUM>) of instruction indicia, each set comprising chunks (<NUM>),
wherein instructions within each set preserve causality of the executed guest instructions,
wherein the chunks within a set preserve causality with respect to each other due to monotonically increasing markers between context switches, and
wherein at least two sets respectively correspond to traces of two execution units concurrently executed by the virtualization layer.