Maszyny wirtualne – interpretery. Część I – Architektura

Postanowiłem pochylić się nad tematem maszyn wirtualnych, a konkretnie interpreterów. Jest to ciekawe zagadnienie ze względu na możliwe zastosowania. Interpreter może zostać uruchomiony niemalże na każdej maszynie, rozpoczynając od mikrokontrolerów, aż po maszyny serwerowe.

Jeśli spojrzymy na zastosowania, jest ich naprawdę sporo. Zaczynając od bardziej klasycznych, czyli wykonywania programów ogólnego przeznaczenia (np. Python, Perl itd.), tworzenie grafiki i dokumentów (np. DVI) lub nawet bezstratna kompresje danych (np. kompresory z rodziny lz). Tak naprawdę, wirtualne maszyny da się wykorzystać wszędzie tam, gdzie jest zdefiniowana stała lista dyrektyw lub rozkazów.

Dodatkową zaletą wirtualnej maszyny jest ujednolicenie środowiska uruchomieniowego. Interpreter wykonuje wyłącznie własne instrukcje, niezależnie na jakiej maszynie fizycznie jest uruchomiony (np. ARM, x86, RISC V ). Można powiedzieć, że niektóre maszyny wirtualne próbują podrabiać w swym działaniu procesory.

Ta seria artykułów skupi się głównie na stworzeniu własnego interpretera oraz kompilatora assemblera do bytecode’u.

W kolejnych częściach stworzymy translator, który będzie tłumaczył język wysokiego poziomu na assembler maszyny.

Trochę teorii dotyczącej maszyn wirtualnych

Pojęcie maszyn wirtualnych jest zagadnieniem ogólnym. Zawiera się w nim wiele różnych technologii oraz rozwiązań. Najczęściej kojarzą się one z oprogramowaniem, które jest w stanie uruchomić cały system operacyjny „obok” już uruchomionego. Temat jest jednak znacznie szerszy.

Rozróżniamy poniższe rodzaje maszyn wirtualnych:

• emulatory,
• kompilatory JIT,
• interpretery.

Emulatory to oprogramowanie, które stawia za cel zasymulowanie w jak najbardziej wierny sposób konkretnego rozwiązania sprzętowego. W tym przypadku emulator odtwarza procesor (układ i funkcje rejestrów, peryferia itd.) oraz inne układy mu towarzyszące np. akceleratory grafiki itp. Cała trudność polega na pokryciu specyficznych zachowań sprzętu (nawet błędów projektowych). Kolejnym wyzwaniem jest zapewnienie odpowiedniej wydajności.

Kompilatory JIT z kolei, stawiają sobie za cel tłumaczenie kodu pośredniego do kodu maszynowego. Celem w tym przypadku jest umożliwienie uruchomienia kodu uniwersalnego (pośredniego) na różnych platformach sprzętowych z jak największą wydajnością. Tak wiec kompilator JIT jest interpreterem i kompilatorem w jednym.

Interpretery, ogólnie mówiąc, stawiają sobie za cel interpretację dyrektyw. Dyrektywy mogą być zapisane w postaci czytelnej dla człowieka, np. przyjmując formę języka programowania lub w postaci kodu pośredniego np. w formie binarnej. Oczywiście stopień skomplikowania obu podejść jest różny. Wszystko zależy od architektury oraz zastosowania.

Interpretery dzieli się na dwie kategorie:

• rejestrowe,
• stosowe.

Interpretery rejestrowe z założenia wykorzystują odpowiedniki rejestrów znane z procesorów do wykonywania operacji logicznych, arytmetycznych itd. Jako przykład może posłużyć maszyna wirtualna Parrot. W przypadku maszyn stosowych wszelkie operacje logiczne, arytmetyczne itd. są wykonywane na stosie. Przedstawicielem tego rozwiązania jest np. Python.

Założenia

Aby możliwa stała się realizacja projektu, zdefiniowałem poniższe założenia:

• Interpreter powinien być zaprojektowany w taki sposób, aby możliwe było łatwe przenośnie go na różne konfiguracje sprzętowe.
• Rozmiar interpretera powinien być jak najmniejszy, tzn. przyjąłem sobie za cel maksymalnie 4 KiB pamięci ROM. Dzięki temu będzie możliwe uruchomienie maszyny na mikrokontrolerach o małych zasobach.
• Potrzebna ilość pamięci RAM do uruchomienie maszyny mniej niż 1 KiB. Chodzi tutaj o pamięć operacyjną samej maszyny, nie pamięć kodu pośredniego.
• Instrukcje interpretera powinny być proste w implementacji, a ich ilość możliwie ograniczona (do sensownego minimum).
• Interpreter musi mieć dostęp do pamięci w sposób liniowy (adresowanie bajtowe).
• Wirtualna maszyną będzie maszyna rejestrowa.
• Interpreter będzie operował na kodzie pośrednim w formie binarnej.
• Operacje na liczbach 32-bitowych całkowitych.
• Instrukcje będą zmiennej szerokości.
• Interpreter nie musi być optymalny, tzn. będzie to zabawka do poszerzenia wiedzy.

Powyższe założenia wymuszają prostotę rozwiązania. Celem tego artykułu jest przekazanie idei.
Kolejnym, nie mniej ważnym, aspektem jest czas realizacji projektu. Przy złożonym projekcie czas potrzebny na analizę, a później na implementację, byłby zbyt długi oraz wymagałby więcej rąk do pracy. Także prostota rozwiązania jest na naszą korzyść w każdym aspekcie.

Architektura

Jak już wiemy, interpreter będzie maszyną wirtualną rejestrową. Wybór ten jest podyktowany bliskością do tego, co większość programistów obserwuje programując mikrokontrolery. Założyłem, ze będzie to prostsze do zrozumienia i bardziej intuicyjne.

Jak każdy wie, większość procesorów posiada pewna określoną pulę rejestrów. Rejestry te pełnią określone funkcje. Tak wiec mamy rejestry:

• ogólnego przeznaczenia,
• kontrolne,
• statusu.

Oczywiście może ich być więcej, ale jest to minimum potrzebne nam do zrealizowania celu.

Podobnie jak w mikrokontrolerach, nasza maszyna będzie posiadać również stos. Jest on przydatny do przechowywania danych oraz wykonywania skoków.

Rejestry

Na początku zajmiemy się rejestrami ogólnego przeznaczenia. Postanowiłem, że będzie ich 16. Rejestry te posłużą do wykonywania różnych operacji: arytmetycznych, logicznych itp. Dla lepszego zobrazowania będziemy je nazywać r0 . . . r15. Oczywiście, nic nie stoi na przeszkodzie, żeby było ich 8, 32 lub więcej.

Kolejną grupą rejestrów jest grupa kontrolująca maszynę. Tutaj znajdziemy rejestr PC (Program Counter), który to wskazuje na aktualny adres pamięci wykonywanego kodu. Następny to SP (Stack Pointer). Jego celem jest wskazanie wierzchołka stosu. Dodatkowym rejestrem jest rejestr statusu SR (Status Register), który służy do przechowywania flag informujących o stanie maszyny lub wykonanej operacji. Tak więc do dyspozycji posiadamy flagi:

Z — wartość rejestru docelowego wynosi 0,
NZ — wartość rejestru docelowego jest różna od 0,
EQ — wartości są równe,
NE — wartości są różne,
GT — argument 1 jest większy od argumentu 2,
LT — argument 1 jest mniejszy od argumentu 2,
ME — błąd pamięci (np. adres poza zakresem),
DZ — błąd dzielenia (dzielenie przez 0).

Tak naprawdę wystarczyłby 3 flagi EQ, GT oraz Z, aby pokryć wszystkie przypadki. Ze względu na prostotę rozwiązania, postanowiłem rozszerzyć listę flag. Pozwoli to w późniejszym etapie uprościć instrukcje skoku warunkowego. Postanowiłem, żeby dostęp do rejestrów ogólnego przeznaczenia i rejestrów kontrolnych maszyny, był jednolity, tzn. znajdował się w tej samej „przestrzeni adresowej”.
Pozwoli to na zmniejszenie ilości instrukcji oraz je uprości.

Zatem, rejestry kontrolne będą przedstawiane jako kolejne rejestry ogólnego przeznaczenia:
r16 (PC), r17 (SP), r18 (SR). Mamy w sumie do dyspozycji 19 rejestrów.

Zostało to zobrazowane w tabeli 1.

Stos

Rejestr SP zwiera adres wierzchołka stosu. Dla uproszczenia interpreter nie będzie posiadał kontroli stosu. Nic jednak nie stoi na przeszkodzie, aby taką funkcjonalność dodać.

Dane na stos będą wrzucane poprzez odpowiednie instrukcje, po czym następować będzie inkrementacja adresu. Odwrotną operacją jest zdejmowanie wartości ze stosu. W tym przypadku adres stosu zostanie najpierw zmniejszony, a następnie wartość zostanie przekazana.

Adresowanie stosu będzie bajtowe. Tak więc, wrzucenie na stos słowa maszyny spowoduje zwiększenie adresu o 4 (32-bit), pobranie niezmniejszenie o 4. Wynika to z założenia, ze pamięć jest liniowa i adresowana bajtowo. Pamięć operacyjna interpretera jest wspólna ze stosem. Rozmiar stosu oraz jego położenie będzie zależne od programisty.

Instrukcje

Generalnie instrukcja będzie kodowana w jednym bajcie danych. Będziemy go nazywać jako opcode. Dodatkowe bajty danych będą już zależne od użytej instrukcji. Ze względu na to, że maszyna wirtualna będzie operować maksymalnie na dwóch operandach, opcode instrukcji będzie zawierać dodatkowe informacje, czy instrukcja odnosi się do rejestru, czy do stałej. Rysunek 1 przedstawia bajt opcode.

Jak przedstawiono, mamy do dyspozycji 6 bitów na kodowanie instrukcji, co daje nam do dyspozycji maksymalnie 64 instrukcje. Oznaczenia arg 0 oraz arg 1 odnoszą się do rodzaju argumentu — rejestr (1) lub stała (0) odpowiednio dla danego operandu. Przykłady przedstawiono w tabeli 2. W przypadku instrukcji, które posiadają tylko jeden argument, wyłącznie jedno pole będzie brane pod uwagę (arg 0).

Jak przedstawiono na przykładzie, instrukcje posiadają różną szerokość, nawet jeśli wykonują tę samą operację. Wynika to z tego, ze interpreter będzie mógł operować bezpośrednio na rejestrach oraz stałych. Stałe wartości są zawsze 4-bajtowe, zapisane w kolejności little endian.

Operacje wykonywane przez maszynę wirtualną

Maszyna wirtualna będzie wykonywała następujące operacje:

• arytmetyczne,
• logiczne,
• transferu danych,
• skoku.

Szczegóły zostały przedstawione w tabelach 3, 4, 5, 6 oraz 7 poniżej.

Instrukcje push oraz pop odpowiedzialne są za umieszczanie oraz pobieranie danych ze stosu. Obie instrukcje posiadają dwa operandy. Każdy z operandów może być rejestrem lub stałą. W zależności od wyboru, instrukcje będą działać nieco inaczej.

Pierwszy argument a0 może przyjąć rejestr lub stałą. W przypadku podania rejestru, instrukcja push lub pop będzie pobierać lub zapisywać wartość rozpoczynając od podanego rejestru, przechodząc przez kolejne rejestry w zależności od zdefiniowanej ilości. Drugi argument a1 zawsze określa ilość elementów, które należy umieścić lub zdjąć ze stosu. Ilość może być zdefiniowana jako wartość dodatnia lub ujemna.

Wartości dodatnie oraz ujemne zawsze określają ilość elementów (co do wartości absolutnej), które należy umieścić lub pobrać ze stosu.

Na przykład push r2 5 spowoduje umieszczenie na stosie kolejno wartości z rejestrów: r2, r3, r4, r5 i r6.

Natomiast ilość ze znakiem „–” spowoduje dekrementacje licznika rejestru, tak jak na przykładzie: push r8 -5, umieści na stosie rejestry: r8, r7, r6, r5 i r4.

W przypadku rejestrów spoza zakresu, wartość poprzednia zostanie wstawiona. Podobna sytuacja dotyczy instrukcji pop z tą różnicaą, że wartości są pobierane ze stosu.
Instrukcje operacji na stosie jako argument a0 mogą przyjąć również stałą. Push umieści na stosie podaną wartość zdefiniowaną ilość razy na stosie. Pop natomiast zdejmie ze stosu bez innych efektów.

Instrukcje te wydają się dość skomplikowane, ale z punktu widzenia implementacji maszyny sprawa wygląda znacznie prościej. Poniższy przykład przedstawia przykładowe użycie instrukcji push i pop:

To wszystko w tej części artykułu. W kolejnej części zajmiemy się implementacją naszej maszyny wirtualnej zgodnej z wymaganiami oraz zdefiniowanymi instrukcjami.