Two worlds of virtual machines

Virtual Unlike most fashionable computer words, this concept usually corresponds to its dictionary definition when it comes to hardware or software. The Dictionary “Random House College Dictionary” defines “virtual” as “manifesting the properties and effects of something, but not being such”.

Original

Virtual. It usually refers to hardware or software. The vocabulary of the vocabulary defines “virtual” as “being such a force or effect, although not actually or expressly such.” [4]

For the last few years, at the beginning of each semester, I give students definitions of the main terms used in my course: simulation , emulation, and virtualization . And every time I say that my words do not take for one hundred percent truth. The fact is that in some areas of technical knowledge these terms are often interpreted contrary to what is commonly used in others. Difficult this thing - to give definitions.

Apparently, this problem was noticed not only by me. In their book, Software and System Development using Virtual Platforms , published last year, my colleagues Jakob Engblom and Daniel Aarno introduce the concepts of simulation and emulation in the first chapter and note the ambiguity of their interpretation in the areas of software development and hardware design.

I understood for myself the disorder in the interpretation of these two terms and seemed to be reconciled. There remains one more concept, for more than ten (actually fifty ) years not losing popularity - this is “virtualization”. During its existence in the category «buzzword» it began to be combined with many other words. Recently, I realized that the term “virtual machine” (VM) is actually used to mean two, though related, but different entities. In this article I will talk about two classes: language and system virtual machines. I will show the similarities and differences between them, their purpose, classification, common and particular features in their practical implementation.
')


Broadly speaking, a virtual machine is a program whose task is to implement the specifications of a specific computing device or class of devices. This is its main difference from the "just" physical machine that implements the same thing, but in hardware. Any specification (computer architecture) most often includes the definition of device interfaces and a description of transitions between machine states. However, the definition of an interface, as is well known, should not impose restrictions on how it is implemented.

Many of us probably don’t notice how often they are confronted daily with both types of machines - virtual and real. For example, the simplest calculator has two implementations - as a specialized device and as a program:



Both the hardware on the left and the virtual machine on the right provide the same interface — the buttons and the screen — and implement the same functions — arithmetic, logical, and trigonometric operations on the numbers displayed on the screen.

A virtual calculator is an example of a virtual machine - a software copy of what originally existed only in the form of hardware, a physical machine, a very specific and tangible system . We will return to the system VM later.

Language VMs

Another case is when a program is created for something “unreal” from the very beginning, for example, for a programming language or runtime environment. In this case, such a language virtual machine will be a way to implement the specification of a language or environment.


Language VMs are usually designed to execute one guest application (sometimes multi-threaded) in one copy of the virtual environment. In other words, they do not assume the functions of access control to resources typical for a multiuser / multitasking operating system. The task of a language VM is to provide the program with an environment that is not directly dependent on the details (and to some extent restrictions) of the underlying physical system, such as the processors used in the latter, RAM and disk volumes, presence and features of peripheral devices, etc.

Of course, and here not to do without holivar about terminology. I will also refer to what is called a process virtual machine and what is called a managed runtime environment (MRE) as a language VM (language VMs).

Two families of language VMs

A language VM is in the middle of a path: from high-level languages ​​to the computer codes of the computer on which it is executed. Therefore, when creating a new language VM architecture, two factors should be taken into account: the convenience of converting selected input languages ​​and the speed of execution on specific hardware systems. From the first will depend on the versatility and extensibility of the created environment, and from the second - the upper limit of the speed of programs for this VM.

The basic unit of execution for a VM is a machine instruction . Each such instruction should determine the operation performed on the data, as well as the location of the data itself. Naturally, the set of operations is highly dependent on the specific VM and can vary widely. The “iron” instruction sets are much more limited in this [I'm still waiting for a processor with hardware malloc () and free (), and better with a hardware garbage collector] .
On the other hand, in approaches to the organization of the processed data among VM there is not so much variety. In fact, there are two well-established concepts - to store data on the stack (s) and use a dedicated set of registers.

Stacked VM

Such VMs store all or almost all of the data in one or more stacks. Addressing them is done by addressing the relative position of the desired cell from the current top of the stack. If an operation has a result, then it is pushed onto the stack, becoming its new top. In addition to the data, addresses that are used when returning from called subprocedures to callers can be stored on the stack. Alternatively, the addresses may be in a separate stack.
About stack machines known and written a lot, and I will not try to describe here everything that I know and what I do not know. I will highlight only some key facts.

I note the advantages of stack language VM:

• Ease of translating expressions from infix notation (expressions with parentheses: a + b * (c / (d - f)) ) to the stack representation (reverse Polish notation).
• Compact encoding instructions. Most machine instructions do not require explicit arguments, since they work with the top of the stack.

The only important exception in practice is the transfer to the process of calculating literals - constants. It is easier to transfer them entirely in the flow of instructions than to try to "construct" from the good already stored on the stack. But if you wish, you can make a VM without it: start the operation “put a unit on the stack”, and then continue to fold it with you until you get the desired number.
It is impossible to say that in the stack VM there can be no allocated registers at all. You must have at least two cells: one for the pointer of the current command, and another for the pointer to the top of the stack. However, they are not always available for direct manipulation in the program, i.e. not every machine makes them architecturally visible.

Since we are now talking only about software systems, I will not go into particular hardware stack machines, with their strengths and weaknesses, such as interrupt handling, memory access speed, interaction with various processor nodes, opportunities for parallelization, etc. I recommend a good Wikipedia article as a starting point.

Examples

I do not hide the truth, saying that for all the time all sorts of language virtual machines have been created a lot. Trying to describe them all is a hopeless undertaking. Therefore, I further mention only some of them as examples.

Historical important examples of stack language VMs

SECD is an abstract machine that appeared in the 1960s and influenced the development of functional languages, including LISP.

P-code is the language of the virtual machine into which the first Pascal compiler of the University of California transmitted programs. Thanks to the p-code portability and the “bootstrapping” approach of the compiler, it was possible to quickly get a working Pascal compiler on new computers, which, when there were no standards for the environment (no POSIX for you in the 70s) and a huge number of incompatible architectures The computer was an important factor in gaining popularity in the language.

Forth - in general, Forth cannot be called just a language VM. For some, this is a high-level procedural language, for some it is an object-oriented language, for someone it is a functional language, for someone it is machine-language, and for some it is a Thinking Forth system design philosophy. However, it is the Fort that comes to my mind when someone says the words “programming” and “stack” in the same sentence.

Actual language VM

Java VM - bytecode for the well-known “compile once, run everywhere” Java language (as well as for Scala, Clojure, etc.) runs on a stack VM. The stack itself stores the scalar data of the running methods, the arguments of instructions, including references to objects and arrays, which are stored in a separate heap area.

Microsoft's Common Intermediate Language is the foundation of the .NET framework. C #, F #, VB.NET and many other less popular high-level languages ​​are translated into it. Bytecode is executed on a stack VM. The structure of both the runtime environment and the CIL bytecode differs significantly from the JVM; in [1], their comparison is given, including their similarities between themselves and differences from conventional hardware instruction sets.

Thus, the two most popular runtime environments use stack language VMs. Perhaps the reader has a question: if the code from bytecode most often ends up being translated into a real machine code of the host system, whose architecture contains registers, and not just the stack (who reads these lines from the display of the machine with stack architecture, raise your hands!) , why do the two most popular language VMs use stack representation? The following argument is given in [1]: “... a stack is amenable to platform independence (ISA)” - “the stack facilitates platform independence (the host platform can have any number of registers in its recruitment teams) ".

Register VMs

An alternative approach to storing the processed data is to use a dedicated set of memory cells with fixed name numbers — registers . The instructions mainly operate on the data on the registers, if necessary, loading the missing values ​​from the memory or unloading unnecessary values ​​into the memory.
In some register architectures, the stack is also usually available. However, it does not play a central role in the work of the VM, but is used to support the procedural mechanism (in which case it is not necessarily directly available to programs).

The features of register VMs are easiest to see by comparing them with stack ones.

• Their machine instructions are longer, because they have to encode operands. In stack VMs, operands are implicitly specified.
• When the VM is running, fewer memory accesses occur. Stacked VMs are constantly forced to shift data on the stack, since the lifetime of the latter is short (most often the operation “eats” the input values ​​from the top of the stack and replaces them with its result). The value placed in the register lives until its rewriting. For example, it allows you to get rid of the constant computation or loading from the memory of values ​​for cyclic invariants - they are simply placed in registers.
• The need to use register allocation algorithms for broadcasting from high-level languages. For nontrivial programs, there will always be a situation of register shortages (their number is limited) to accommodate all the data used in the calculation. At the same time, it is necessary to keep track of which register is at each moment of time. Whereas in the case of stack VMs, the top of the stack is one, and it is always “available”. These circumstances can significantly complicate the logic of the tools for the register VM.

The most interesting question is whether the VM type — stack or register — executes programs faster. There is currently no clear answer; data from some researchers prove the advantage of the first type, while others argue the opposite. An interesting experiment is described in [3] - the authors of the article use a register VM for execution, the code for which is obtained using an optimized translation from Java bytecode, and compares the performance.

Examples

Parrot VM is a long - term VM developed for over 10 years and serving as the main execution environment for the Perl 6 language.

Dalvik from Google is a registered VM used to execute applications written in Java. Interestingly, the stack JVM bytecode (* .class) is converted to register VM bytecode (* .dex). Currently, Dalvik fades into the background in Android, giving way to ART - the mechanism of direct compilation into the machine code of the host system.

LLVM bitcode is one of the representations of the source program used when translating programs using LLVM-based tools and partly the VM input language using the three-instruction format of instructions with registers. Unusual in this VM is that the instructions are expressed in the so-called. SSA (single static assignment) form, i.e. they use a potentially unlimited number of virtual registers. The allocation of VM registers to physical ones occurs later in the process of translation into machine code or interpretation.

MIX and MMIX are virtual machines used (or planned for use in future editions) by D. Knut in his series The Art of Programming to illustrate the implementation of algorithms. MIX is made in the spirit of the 1960s: a dedicated register-battery, 6-bit bytes, a binary-decimal number format, no stack, and a tendency to use self-modifying code. MMIX is already a sane RISC with a generous number (256) and a width (64 bits) of registers.

Exotic VM

Beware of the Turing tar pit, in which everything is possible, but none of the interesting is achievable.

Original

It is an easy way to get around. Alan Perlis, "Epigrams on Programming"

Finally, the third approach to building a VM is to break all the rules and create an architecture that is unlike anything “standard”. On the one hand, this is very exciting: to invent a new concept where everything seems to be invented. On the other hand, the benefits of such systems are limited, often because of their (addictive) extreme impracticality.

printf () as a virtual machine is not exactly exotic, I just want to show a familiar thing to many things from a new angle. After all, if you take a closer look, the specification line that comes with the first argument to the standard functions of the C printf family is a program whose instructions are characters, and the data are the remaining arguments of the function. Most of the instructions of this VM simply output one character that matches the code of the instruction itself; but the % instruction has much more complex semantics, depending on the characters following it. Not surprisingly, some vulnerabilities in software are based on passing a specially selected string to interpret it in printf and executing unauthorized code.

OISC . The most fascinating and mysterious (for me) class of languages ​​of an exotic type is OISC (one instruction set computer) - systems containing exactly one machine instruction and at the same time not being completely trivial. Some of them are equivalent to the Turing machine, i.e. quite complex algorithms can be programmed on them. The best known of OISC is subleq (subtract and branch unless positive).
It should be noted that OISC is often hidden in a completely familiar set of machine instructions; for example, MOV in a PDP-11 or # PF / # DF with Intel ® IA-32 ; The last machine can be called zero instruction set computer, because formally the execution of IA-32 instructions during exception handling does not occur.

Dis - VM for distributed OS Inferno, created at Bell Labs by people who were at the beginnings of Plan 9 OS. This machine has memory-to-memory addressing, which is rather unusual by modern standards (the last time in hardware was in Motorola 68000), and lack of architecturally visible registers. I cannot think of the advantages of such an approach either over register systems or stack systems; rather, he collects in himself all their faults.

Execution methods

After determining the type of VM and architecture details, it is time to create a program that implements the VM functionality. After choosing a programming language and other little things, you need to decide how the instructions will be processed. And there are at least three ways:



Interpretation is the main and initial technique for both language and system VM. I described its basic principle in my previous articles. The question of building the most efficient interpreter is not as simple as it seems, and is of great practical value due to the wide popularity and prevalence of dynamic languages ​​that use interpretation at various stages of their work. And it's not always enough to write switch (...) {case ... case ... case ...} . I plan to describe in more detail the problems leading to the low speed of work for such a naive approach, and the existing solutions in one of my subsequent articles.

Dynamic translation is a technique that is generally superior to interpretation in terms of both speed and complexity of implementation. It is based on the fact that the code executed inside the VM forms cycles, and the instructions within them will perform the same actions with each interpretation. If the blocks of the VM code are translated into equivalent sections of the machine code of the physical system before execution, you can save on decoding and interpretation. The more iterations will be carried out in a loop, the greater will be the effect of the use of translation. I described one of the ways to build a simple template translator in a previous article .

Static translation - in the case when all the code to be executed is known in advance (that is, in the course of VM operation, loading of new blocks with instructions is not expected), then it is possible to use classical compilation — once to convert the machine instructions of the original VM into machine instructions of the physical system, This optionally applying a variety of optimizations.

If I am interested in the design and implementation of language VMs, I can advise the book [2], the author of which describes the theory and gives practical examples of the implementation of stackable, register VMs, as well as the “exotic” VM version for an event-oriented system.

System VMs

System virtual machines, as a rule, are created according to specifications for which “iron” implementations already exist. This brings its own features to the process of creating such VMs. The architecture of this equipment is limited more than a purely software, “speculative” VM: requirements affect performance, power consumption, the physical dimensions of the crystal that can accommodate the implementation, compatibility with external devices, etc.

Often, the goal of creating a system VM is to launch unmodified (neglect para-virtualization for simplicity) operating systems inside it that provide multitasking and controlled access to system resources for guest user applications. Unlike language VMs designed for a single process, the system VM should provide a fairly complete environment from a large number of peripheral models, simulation of working with physical memory cards, correct interrupt and exception processing, monotonous and uniform virtual time, etc.

Unlike the creators of language VMs, who often have quite a lot of freedom in choosing machine parts, the programmers implementing system VMs are bound by the need to clearly follow the hardware specifications, which are usually not easy to change. Significant efforts have to be spent on effective support for idiosyncrasies (or simply crutches) of the chosen machine language. After a long evolution and numerous extensions, some architectures look like a solid crutch fence ... but I got distracted. In any case, when creating a system VM, more attention is paid to the issues of creating a correct and fast program than to the hassle of input machine language.

Classification of system VMs

System VMs are primarily classified according to what type of guest processor is being modeled. There are many classifications of processors, and they are described in some detail in various sources, so here I only briefly summarize the most common things. According to the architecture of the CPU command set, there are CISC — complex instructions that do many things at once, including loading data from memory, and RISC — the simplest instructions in which memory access and operations on data in registers are clearly separated; VLIW stand somewhat apart, in which several different operations are combined into one machine word. It is also possible to classify instruction sets based on the variability of the instruction length: systems with variable command lengths and systems with a fixed length. In truth, the truly constant length of instructions is rare - always or something does not fit into the machine word (for example, 32-bit literals in ARC and 64-bit in IA-64), or the creators try to save money by assigning to frequently used instructions are shorter sequences (16-bit ARCompact or ARM Thumb commands).

When creating a system VM, an important classification feature is the presence / absence of a “relationship” between the host and guest architectures. According to the degree of relationship, the simulated and modeling systems can be: completely heterogeneous (for example, Zilog Z80 and PowerPC), similar (Intel IA-32 and Intel 64, or Intel 8086 and Intel IA-32) or the same ( X and X , where X - your favorite architecture).

In the case when the guest and the host are different, the task of the system VM is to provide the ability to run applications written and compiled for the “alien” architecture on the host system without the need to recompile them or make any other modifications. Ideally, the VM software layer may be completely invisible to the end user. It is obliged to work correctly, quickly enough and not require additional configuration.

Such an approach can help companies transfer users with their favorite programs from their old architecture to a new one (of course, excellent in everything, but incompatible with the old one), or even lure users of a competitor’s system to their own. The system VM should eliminate the loop: a new architecture — no applications — no users — no developers — no popularity — no applications .
Examples of this application VM weight. Let me give you some known to me.

• Digital Company: Digital FX! 32 for launching IA-32 applications on Alpha, VEST - for launching VAX programs on Alpha, mx - Ultrix MIPS on Alpha.
• IBM: PowerVM Lx86 for running IA-32 on POWER processors.
• Apple used system VMs twice: when switching from a Motorola 680x0 to a PowerPC in 1996; Apple Rosetta to translate from PowerPC to IA-32 in 2006.
• IA-32 «».
• Intel IA-32 Execution Layer IA-32 Intel Itanium.
• NTVDM (NT virtual DOS machine) 32- Microsoft Windows DOS-, 8086 MS-DOS.
• Intel: Android, ARM, Intel Atom, , .

Of course, this list goes on.

In cases of coincidence of architectures of guest and host systems, the system VMs also find application. Running a guest OS inside a VM running the monitor allows you to control its resource consumption, execute simultaneously with other systems, freeze, restore from images, clone, migrate from one place to another and generally perform various tricks that are difficult to turn with an OS running directly on the hardware .

For VM creators, the “virtualizability” of the instruction set becomes critical. It depends on how easy it is to implement a virtual machine monitor for it, as well as how much slowdown (in relation to working on bare hardware), does it satisfy whether the selected machine instruction architecture satisfies the sufficient conditions of Goldberg-Popek. Intel IA-32 / Intel 64 before the advent of Intel VT-x extensions belonged to the first category of hard-to-virtualizable systems, but at present it is easy to write effective monitors for it (if this word is applicable to the development of core modules for instruction set with almost half a century evolution ).

Execution methods

From the point of view of software implementation, system VMs have much in common with linguistic ones. This is not surprising - the basic unit of execution in both cases is the machine instruction.



Interpretation - and again this word! In the case when you need to make the most easily portable system VM without special consideration for speed, the interpreter will be the natural first choice. Bochs is probably the most famous open source project of this type. I emphasize again the lack of order in terminology - on the official page of Bochs is presented as a “PC emulator”, and not a simulator or a virtual machine.

Dynamic translation - as described earlier, a group of technologies that promise a higher speed. But static translation, applicable for language VMs, is not very convenient for creating system VMs — in full-platform models, it’s extremely rare for all code to be available and known in advance, before the start of the simulation. The purely dynamic translators include the previously mentioned IA-32 Execution Layer.

Hardware support — for architectures that support hardware virtualization, this is the most efficient method. However, it is also the most “capricious”, because it only works if the guest and host architectures coincide. Often, even relatively small differences between the sets of extensions of the selected systems may make it impractical to attempt to create a VM of this type. Most modern commercial hypervisors for IA-32 actively rely on the presence of VT-x in their work.

Interested in the design and implementation of system VMs I want to advise the book [1]. Not interested, too, I would venture to advise her - it explains in an accessible way many important features of computer architecture, it is written in quite understandable language.

Results

In this article, I tried to describe two classes of software systems, called virtual machines, to show the differences and similarities between them, known variations of the used architectures and their software implementations. The total classification of




VMs is as follows: Language virtual machines are primarily distinguished by the organization of data access. System VMs are primarily characterized by the features of the hardware architecture of the implemented guest. Very often the script implemented in practice implies the coincidence of the host and guest architectures. In this case, the most important property from the point of view of the designer of the VM monitor is the satisfaction of the conditions of effective virtualizability.

Whew, as always, I wanted to write a couple of lines, but I got a long post-sheet.Of course, the scope of questions about the structure, performance and development of virtual machines is immense. I was planning to write more about a couple of moments in the work of the creators of VM, but, perhaps, I will postpone them for the next time.
Thanks for attention!

Literature

1. James E. Smith, Ravi Nair, Virtual Machines: Versatile Platforms For Systems And Processes - Morgan Kaufmann - 2005. ISBN 1-55860-910-5
2. Craig, Iain D. Virtual Machines - Springer - 2006. ISBN 1-85233-969-1
3. Yunhe Shi, Kevin Casey, M. Anton Ertl, and David Gregg. Virtual Machine Showdown: Stack Versus Registers - USENIX - 2008. www.usenix.org/events/vee05/full_papers/p153-yunhe.pdf
4. Bob DuCharme. Fake Your Way Through Minis and Mainframes (formerly, “The Operating System Hand-book”) - Part 5: VM / CMS - 2001. www.snee.com/bob/opsys/part5vmcms.pdf