Simple Virtual Machine #1

Category: 

Virtuelle Maschinen dienen als Schnittstelle zwischen virtuellen Instruktionen und der tatsächlichen Maschine. Grundsätzlich gibt es verschiedene Einsatzmöglichkeiten für sie. Beispielsweise kann man eine Scriptengine darauf aufbauen und somit (Spiel-)logik in Assets auslagern und ggf. auch zur Laufzeit ändern. Weiterhin kann man natürlich auch eine Sandbox aufbauen und Code in der VM Code ausführen, welcher aus Sicherheitsgründen nicht direkt auf der echten Maschine ausgeführt werden sollte.

Dieser Artikel ist Teil der Serie: Simple Virtual Machine
#1 Einstieg
#2 Prototyp
#3 Bedingte Sprünge
#4 Funktionen
#5 OOP
#6 Globale Variablen und Java Funktionen
#7 Operator overloading
#8 Details & Loading from File
#9 Bonus: Assemblercode

Zielsetzung

Ziel dieser Tutorialserie ist es, eine eigene, kleine virtuelle Maschine zu programmieren. Diese soll in der Lage sein, speziellen Bytecode auszuführen. Wie dieser Bytecode aussehen soll, liegt natürlich ganz bei uns. Die VM kann dabei relativ nah an realen Maschineninstruktionen sein oder auch abstrakter bleiben.

Stack vs Register

Bevor es losgeht, müssen wir uns ein paar Gedanken über die Architektur machen. Im Allgemeinen unterscheidet man zwischen zwei Implementierungen: Stack basiert und Register basiert.
Stack basierte VMs sind zum Beispiel die Java Virtual Machine und die .Net CLR. Register basierte VMs sind unter anderem Lua und Googles Dalvik VM. Der Grundlegende Unterschied besteht in der Art und Weise wir Operanden und ihre Ergebnisse geholt und gespeichert werden.

Register based VM

Der register basierte Ansatz arbeitet auf einer festen Anzahl an Registern. Verschiedene Operationen bearbeiten direkt den Inhalt dieser Register. Wenn man beispielsweise zwei Zahlen addieren möchte (z.B. 40+2), so wird dazu eine einzelne Instruktion genutzt:

add 2, 16, 3

Diese verweist dabei auf die beiden Register aus denen gelesen werden soll (2 und 16), sowie das Register in welches das Ergebnis geschrieben werden soll (Register 3).

Im Allgmeinen haben sämtliche Befehle exakt die gleiche Länge und enthalten sämtliche notwendigen Informationen. Die Lua VM nutzt beispielsweise 32 Bit lange Instruktionen, welche in drei Kategorien unterteilt werden:

Der OpCode gibt dabei immer an um welchen Befehl es sich genau handelt und somit auch um welches Format (iABC, iABx oder iAsBx) es sich handelt. Die Add-Operation hat beispielsweise den OpCode 12 und verwendet das iABC Format. Dabei sind A, B und C jeweils Register Indizes. Format iABx enthält einen Register Index, sowie eine 18 Bit vorzeichenlose Ganzzahl. Bei dem iAsBx Format ist die 18 Bit Zahl vorzeichenbehaftet.
Da sämtliche Informationen in einer Instruktion kodiert sind, sind Registermaschinen äußerst effizient, allerdings sind ihre Compiler auch entsprechend komplizierter. Denn immerhin muss die begrenzte Anzahl der Register optimal ausgenutzt werden.

Stack based VM

Hier ist die zentrale Datenstruktur ein Stack, welcher nach dem LIFO (Last In First Out) Prinzip arbeitet. Wenn man bei dieser Architektur zum Beispiel eine einfache Rechnung (z.B. 40+2) ausführen möchte, so würde der entsprechende (Pseudo)Assemblercode so aussehen:

push 40
push 2
add

Zuerst wird der Wert 40 und dann der Wert 2 auf den Stack gelegt. Anschließend wird die Add-Operation ausgeführt, welche die beiden obersten Werte entfernt, addiert und das Ergebnis zurück auf den Stack legt.

Wie man bereits sieht, benötigt man unter Umständen mehr Befehle als bei einer Registermaschine. Allerdings sind die einzelnen Befehle auch meistens kürzer. Viele Operationen haben selbst keine Parameter und können somit mit einem einzelnen Byte repräsentiert werden. Dies führt jedoch auch dazu, dass Instruktionen unterschiedlich lang sein können. Operationen wie Add brauchen keine Parameter, wenn man jedoch einen Wert auf den Stack legen will, wie z.B. mit push, so muss diese Zahl als weiterer Parameter mitgeführt werden. Dementsprechend haben Stack Operationen meistens eine Länge von 1-5 Bytes.

Stackmaschinen sind im Allgemeinen etwas weniger Performant als Registermaschinen, aber dafür leichter zu Implementieren. Insbesondere ist bei ihnen der Compiler einfacher, da dieser sich nicht groß um das Speichermanagement kümmern muss, da der Stack (quasi) Endlos ist.

Stack mit Registern

Anstatt die beiden vorgestellten Architekturen komplett getrennt zu betrachten, kann man sie auch ein wenig kombinieren.
Ein weit verbreiteter Ansatz ist es, eine Stack Architektur zu verwenden und diese um "quasi" Register zu erweitern, welche für lokale Variablen genutzt werden können. Der Grund dafür ist recht offensichtlich, denn betrachten wir mal den folgenden Pseudocode:

function test()
  local a = ...
  local b = 2*a
  local c = 3*a
end

Bei einer reinen Stackmaschine, liegen alle lokalen Variablen auf dem Stack. Was wenn man nun aber eine Variable mehrfach benutzen will? Im Grunde muss man diese dann mehrfach duplizieren und ggf. die Reihenfolge der Elemente mehrfach ändern. Das ist natürlich äußerst umständlich und auch ineffizient. Daher haben Stackmaschinen häufig einen Befehl, um gezielt in den Stack zu greifen. Das ganze kann man dann natürlich noch weiter verbessern, in dem man speziellen Speicher für lokale Variablen bereitstellt. Durch einfache Befehle wie "load index" oder "store index" kann man somit eine lokale Variable auf den Stack legen oder aber das oberste Element als lokale Variable speichern.
Dieser Ansatz wird unter anderem von der JVM verwendet und soll auch in unserer SimpleVM genutzt werden.

Ausführen von Bytecode

Eine weitere wichtige Design Entscheidung ist die Repräsentation des Bytecode im Speicher. Oft wird dazu eine abstrakte Instruktionsklasse definiert, welche eine execute oder auch run Methode besitzt. Die konkreten Instruktionen erben dann von dieser Klasse und stellen die eigentliche Logik bereit. Eine Funktion besteht dann nur noch aus einer Liste von Instruktionen.
Während der Ausführung des Code zeigt dann der sogenannte ProgramCounter (PC), auf die Position der aktuellen Instruktion. Pro "Taktschritt" wird dann die Instruktion aus der Liste geholt, der PC um eins erhöht und schließlich die Instruktion ausgeführt. Dies könnte ganz grob so aussehen:

public class VM {
  public int pc;
  public Stack stack;
  public void run(List<Instruction> instructions) {
    while(pc < instructions.size()) {
      Instruction instr = instructions.get(pc);
      pc++;
      instruction.execute(this);
    }
  }
}

public abstract class Instruction {
  public abstract void execute(VM vm);
}

public class Add extends Instruction {
  public void execute(VM vm) {
    Object b = vm.stack.pop();
    Object a = vm.stack.pop();
    vm.stack.push( a + b);
  }
}

public class Goto extends Instruction {
  public int index;
  public void execute(VM vm) {
    vm.pc = index;
  }
}

Dieser Ansatz ist relativ selbst erklärend und auch einfach zu verstehen. Jedoch sollte einem klar sein, dass eine Funktion mit mehreren hundert Zeilen Code dann auch mehrere hundert Objekte erzeugen muss. Das ganze kostet natürlich auch etwas mehr Speicher und Zeit. Ein "Problem" mit diesem Ansatz ist, dass das Ausführen einer einzelnen Instruktion auch einen extra Methodenaufruf benötigt.

Anstatt den Code als Folge von eigenständigen Instruktionsobjekten zu betrachten, kann man den Code einfach weiterhin als einfaches byte Array betrachten. In jedem "Taktschritt" wird dann das byte an Position PC gelesen und mit einem großen Switch geprüft um welchen OpCode es sich handelt. Im jeweiligen Case Statement wird dann die entsprechende Logik ausgeführt. Der folgende Beispiel Code zeigt den groben Lösungsansatz:

public class VM {
  public int pc;
  public Stack stack;
  public void run(byte[] code) {
    while(pc < code.length) {
      byte opcode = code[pc];
      pc++;
      switch(opcode) {
        case ADD:
          Object b = vm.stack.pop();
          Object a = vm.stack.pop();
          vm.stack.push( a + b);
          break;
        case GOTO:
          int index = code[pc];
          pc = index;
      }
    }
  }
}

Durch diesen Ansatz benötigt man zwar weitaus weniger Klassen, allerdings wird die interpretations Methode zum Ausführen des Bytecode auch dementsprechend größer. Aber wie bereits erwähnt, sparen wir uns somit sehr viele Methodenaufrufe und sind (theoretisch) etwas schneller.

Im Grunde ist es jedem selbst überlassen, welchen Ansatz er verwenden möchte. Dieser Artikel wird sich jedoch auf die zweite Variante beschränken und somit sämtliche Instruktionslogik mit einem großen Switch abhandeln.

Konkrete Zielsetzung

Die grundlegende Architektur soll Stackbasiert sein, mit der kleinen Erweiterung von einem extra Speicherbereich für lokale Variablen. Selbstverständlich wollen wir auch Rechnungen durchführen können, sowie Text ausgeben. D.h. wir benötigen mindestens einen Zahltypen, sowie einen Stringtyp. Im Grunde würde es reichen wenn wir nur Gleitkommazahlen benutzen, aber der vollständigkeithalber wollen wir auch einen ganzzahligen Typen unterstützen.
Im Endeffekt soll die VM objektorientiert arbeiten, daher benötigen wir noch ein allgemeines Typsystem. Das ganze kann natürlich äußerst komplex werden, jedoch kann man es mit einem kleinen Trick relativ einfach halten. Wie genau dieser Trick aussieht, erläutere ich in einem späteren Teil. Jetzt wollen wir uns erstmal nur die Grundlage schaffen.
Neben der Objektorientierung wäre es außerdem schön, wenn wir funktional arbeiten könnten, d.h. dass wir z.B. auch Funktionen als Parameter mitgeben können und ebenso Funktion zurückgeben können.
Hier einmal eine kleine Zusammenfassung der benötigten Datentypen:
  • int - 32 Bit Ganzzahl
  • float - 32 Bit Gleitkommazahl
  • string - Zeichenkette
  • function - ausführbare Funktionen
  • (Objekte/Klassen?)

Weiterhin sollten wir schon einmal klären was wir für Operationen benötigen. Selbstverständlich brauchen wir grundlegende Rechenoperationen, sowie verschiedene Vergleichs- bzw. Sprungoperationen. Diese benötigen wir um Dinge wie If-Abfragen und verschiedene Schleifen zu implementieren. Schließlich wollen wir natürlich auch noch Funktionen aufrufen können.
Hier müssen wir wieder eine große Design Entscheidung treffen. Immer wenn eine Funktion aufgerufen wird, müssen wir irgendwie Speichern wo wir zuletzt waren, damit wir nach einem Return wieder ganz normal weiter arbeiten können. Dazu werden sämtliche Informationen der aktuellen Funktion in einem StackFrame gespeichert. Einerseits muss natürlich gespeichert werden, welche Funktion es überhaupt ist, sowie die Position des ProgramCounters.
Diese Informationen kann man natürlich selber speichern und damit alle Aufrufe virtualisieren oder aber man macht es sich etwas einfacher und nutzt einfach die Boardmittel von Java:

public class VM {
  public int pc;
  public Stack stack;
  public void run(Function function) {
    byte[] code = function.code;
    while(pc < code.length) {
      byte opcode = code[pc];
      pc++;
      switch(opcode) {
        ...
        case CALL:
          fun = stack.pop();
          run(fun);
      }
    }
  }
}

Anstatt uns also selbst die Arbeit zu machen, rufen wir unsere interpreter Methode einfach rekursiv auf und übergeben ihr bloß eine andere Funktion. Wenn diese Funktion abgearbeitet ist, kehren wir automatisch zu dem Punkt zurück, wo wir die Funktion aufgerufen haben.

Abschluss

Und damit sind wir auch am Ende der Einleitung zum Thema "Simple Virtual Machine".
Im nächsten Teil entwickeln wir dann einen ersten kleinen Prototypen, mit dem wir zumindest einfache Bytecode Programme ausführen können.

Hier geht's direkt weiter: #2 Prototyp