Maszyny wirtualne – interpretery. Część II – Implementacja

W tym artykule zajmiemy się implementacją maszyny wirtualnej, zgodnej z postawionymi w poprzedniej części założeniami oraz architekturą. Implementację zrealizujemy w języku programowania C. Kod będzie napisany w taki sposób, aby możliwe było uruchomienie maszyny na PC oraz mikrokontrolerach.

Interpreter będzie składał się z dwóch plików: źródłowego i nagłówkowego. Oba te pliki będzie można dołączyć do dowolnego projektu.

Plik nagłówkowy

Plik ten zawiera:

• definicje typów,
• makra,
• interfejsy wirtualnej maszyny.

Ze względu na to, że interpreter posiada 16 rejestrów roboczych oraz 3 sterujące, poniższe makra ułatwią nawigację po nich.

#define VM_REG_GENERAL_COUNT    16
#define VM_REG_CONTROL_COUNT    3	/* DO NOT change number of registers. */
#define VM_REG_TOTAL_COUNT      (VM_REG_GENERAL_COUNT + VM_REG_CONTROL_COUNT)

#define VM_REG_PC               (VM_REG_GENERAL_COUNT + 0)
#define VM_REG_SR               (VM_REG_GENERAL_COUNT + 1)
#define VM_REG_SP               (VM_REG_GENERAL_COUNT + 2)

Pierwsze makro odpowiada za określenie ilości dostępnych rejestrów ogólnego przeznaczenia, natomiast drugie określa ilość rejestrów kontrolnych. Ilość rejestrów kontrolnych nie powinna być zmieniana ze względu na implementację oraz określone przeznaczenie.

Na podstawie zadanej ilości rejestrów, określane są kolejno numery rejestrów: PC, SR i SP.

W pliku nagłówkowym zdefiniowano również poszczególne bity rejestru statusu SR za pomocą typu wyliczeniowego:

enum {
    VM_REG_SR_Z           = 0x001,	/** Zero flag. */
    VM_REG_SR_NZ          = 0x002,	/** Not zero flag. */
    VM_REG_SR_EQ          = 0x004,	/** Equal flag. */
    VM_REG_SR_NE          = 0x008,	/** Not equal flag. */
    VM_REG_SR_GT          = 0x010,	/** Greater than flag. */
    VM_REG_SR_LT          = 0x020,	/** Less than flag. */
    VM_REG_SR_ME          = 0x040,	/** Memory error flag. */
    VM_REG_SR_DZ          = 0x080,	/** Division by zero flag. */
    VM_REG_SR_CMP_MASK    = 0x03F,	/** Comparison mask. */
};

Definicja ta jest przydatna podczas implementacji maszyny oraz wywołań systemowych po stronie klienta. Z rejestru statusu korzystają instrukcje porównań (cmp i cmps).

Jednym z założeń architektury jest możliwość uruchomienia dowolnej ilości interpreterów. W tym celu został utworzony typ danych vm_t, który to przechowuje stan maszyny wirtualnej. Każdy interfejs dostępny z poziomu klienta musi przekazywać wskaźnik na obiekt interpretera. Podejście to wprowadza elastyczność oraz niezależność wykonywanych zadań. Typ ten jest zdefiniowany następująco:

typedef struct vm_s {
    uint32_t regs[VM_REG_TOTAL_COUNT];
    void     (*read) (struct vm_s *vm, uint32_t address, uint8_t *data, uint8_t size);
    void     (*write)(struct vm_s *vm, uint32_t address, const uint8_t *data, uint8_t size);
    uint32_t (*sys)  (struct vm_s *vm, uint32_t arg0, uint32_t arg1);
    void *user;
} vm_t;

Na pierwszy rzut oka można tutaj zauważyć pole regs. Odpowiedzialne jest za przechowywanie wartości poszczególnych rejestrów. Na tych danych będą wykonywane wszelakie operacje arytmetyczne, logiczne itp. Następnymi elementami są interfejsy interpretera – kolejno: do pobierania danych z pamięci (read), zapisywania danych do pamięci (write) oraz wywołania funkcji systemowej (sys).

Dodano również definicje typów interfejsów maszyny w celu łatwiejsze integracji maszyny:

typedef void     (*vm_read) (vm_t *vm, uint32_t address, uint8_t *data, uint8_t size);
typedef void     (*vm_write)(vm_t *vm, uint32_t address, const uint8_t *data, uint8_t size);
typedef uint32_t (*vm_sys)  (vm_t *vm, uint32_t arg0, uint32_t arg1);

Ostatnimi elementami w pliku nagłówkowym są funkcje interfejsowe, to dzięki nim możliwa będzie interakcja z interpreterem.

extern void vm_init(vm_t *vm, vm_read read, vm_write write, vm_sys sys, void *user);
extern bool vm_step(vm_t *vm);
extern void vm_irq (vm_t *vm, uint32_t address);

Funkcja vm_init() służy do inicjalizacji obiektu maszyny wirtualnej,  vm_step() wykonuje jedną instrukcję, a vm_irq() pozwala na wywołanie przerwania.

Plik źródłowy

W tym punkcie przedstawię implementację poszczególnych funkcji. Nie wszystkie funkcje będą omówione szczegółowo ze względu na ograniczoną długość artykułu. Implementacja maszyny wirtualnej jest do pobrania w załącznikach pod artykułem. Interpreter został zrealizowany przy użyciu około 300 linii kodu (kod + komentarze).

Funkcja vm_init()

Na wstępie przeanalizujemy funkcję vm_init(). Ta funkcja wywoływana jest podczas inicjalizacji obiektu maszyny. Jej zadaniem jest ustawienie poszczególnych pól na odpowiednie wartości. W tym przypadku funkcja ustawia funkcje interfejsowe oraz wskaźnik na dane klienta. Jeśli chodzi o interfejsy – nie ma tutaj raczej zaskoczenia. Jednakże pole user wymaga wyjaśnienia.

Interpreter nie korzysta z tego pola bezpośrednio, jest to parametr opcjonalny, który może zostać wykorzystany na potrzeby implementacji np. w funkcji vm_read() jak parametr konfiguracyjny. Znacząco zwiększa to elastyczność i ułatwia w niektórych przypadkach implementację interfejsów. Funkcja vm_init() przedstawia się następująco:

void vm_init(vm_t *vm, vm_read read, vm_write write, vm_sys sys, void *user)
{
    vm->read = read;
    vm->write = write;
    vm->sys = sys;
    vm->user = user;
}

Funkcja vm_irq()

Kolejną omawianą funkcją jest vm_irq(). Funkcja ta służy do wywoływania przerwania. Aktualnie wykonywany program zostanie przerwany, a interpreter wykona skok do określonego adresu. Adres jest zdefiniowany przez klienta – proponuję tutaj zdefiniowanie odpowiedniej tablicy skoków. Ze względu na to, że przerwania wykorzystują ten sam stos, funkcja obsługi przerwania musi posiadać odpowiednią instrukcję do wyjścia z przerwania. W ogólnym przypadku jest to pop PC.

void vm_irq(vm_t *vm, uint32_t address)
{
    /* push on stack current PC */
    vm->write(vm, vm_sp_reg, (uint8_t*)&vm_pc_reg, sizeof(uint32_t));
    vm_sp_reg += sizeof(uint32_t);
    vm_pc_reg = address;
}

Funkcja vm_step()

Nasza implementacja w zasadzie posiada jeszcze jedną, ostatnią funkcję vm_step(). Jest to najdłuższa i najważniejsza funkcja, ponieważ tutaj dokonują się interpretacje instrukcji (obliczenia, skoki, odłożenie rejestrów na stos etc.). Funkcja ta zostanie omówiona we fragmentach. Po szczegóły odsyłam do załączonego kodu.

Funkcja na początku deklaruje zmienne, po czym przechodzi do odczytu instrukcji z pamięci.

bool vm_step(vm_t *vm)
{
    uint8_t reg = 0xFF;
    uint32_t arg0;
    uint32_t arg1;
    uint8_t opcode;
    uint8_t step = 2;
    bool status = true;

// get opcode
    vm->read(vm, vm_pc_reg, &opcode, sizeof(opcode));
    vm_pc_reg += sizeof(opcode);

    ...
}

Odczyt instrukcji

Odczyt instrukcji dokonywany jest za pomocą interfejsu read(). W zasadzie dokonuje się tutaj odczytu jednego bajtu danych znajdującego się w pamięci pod adresem wskazanym przez rejestr PC. Po operacji odczytu następuje inkrementacja pozycji programu (PC) o 1.

Ze względu na to, że maszyna obsługuje wyłącznie instrukcje jedno- lub dwuargumentowe, pobrany bajt zawiera informacje o ilości argumentów. Na potrzeby implementacji wprowadźmy w opcode dodatkowy bit określający ilość argumentów. Bajt opcode prezentuje się teraz następująco:

Instrukcja jednoargumentowa:

Instrukcja dwuargumentowa:

Dzięki tej zmianie implementacja upraszcza się, ponieważ możliwe stało się ładowanie odpowiednich argumentów w pętli, tak jak pokazano to w kodzie:

bool vm_step(vm_t *vm)
{
    ...

    // number of arguments
    step = (opcode & 0x01) + 1;
    opcode >>= 1;
    // get arguments
    while (step > 0) {
        arg1 = arg0;
        if ((opcode & 0x01) != 0) {
            vm->read(vm, vm_pc_reg, ®, sizeof(reg));
            vm_pc_reg += sizeof(reg);
            arg0 = vm->regs[reg];
        } else {
            vm->read(vm, vm_pc_reg, (uint8_t*)&arg0, sizeof(arg0));
            vm_pc_reg += sizeof(arg0);
        }
        opcode >>= 1;
        step--;
    }

    ...
}

Dalszy kod funkcji jest odpowiedzialny za wykonanie poszczególnych instrukcji. Całość opiera się o warunek wielokrotnego wyboru (switch). Poniższy przykład przedstawia implementację kilku instrukcji arytmetycznych:

bool vm_step(vm_t *vm)
{
    ...

    switch (opcode)
    {
        case VM_OPCODE_NOT: arg0 = ~arg0; break;
        case VM_OPCODE_NEG: arg0 = -arg0; break;
        case VM_OPCODE_ADD: arg0 += arg1; break;
        case VM_OPCODE_SUB: arg0 -= arg1; break;
        case VM_OPCODE_MUL: arg0 *= arg1; break;
        ...
    }
    ...
}

Jak widać, w przypadku tych instrukcji implementacja jest bardzo prosta.

Pozostałe instrukcje

Inne instrukcje, np. porównywanie wartości, są nieco bardziej złożone:

case VM_OPCODE_CMP:
    vm_sr_reg &= ~VM_REG_SR_CMP_MASK;
    if (arg0 == arg1)
        vm_sr_reg |= VM_REG_SR_EQ;
    else
        vm_sr_reg |= VM_REG_SR_NE;

    if (arg0 > arg1)
        vm_sr_reg |= VM_REG_SR_GT;

    if (arg0 < arg1)
        vm_sr_reg |= VM_REG_SR_LT;

    reg = 0xFF;
break;

Ze względu na ilość instrukcji, nie będę omawiał ich wszystkich, odsyłam do załączonego kodu.

Aktualizacja rejestru statusu

Funkcja vm_step() kończy się poniższym kodem:

bool vm_step(vm_t *vm)
{
    ...

    vm_sr_reg &= ~(VM_REG_SR_Z | VM_REG_SR_NZ);
    if (arg0 == 0)
        vm_sr_reg |= VM_REG_SR_Z;
    else
        vm_sr_reg |= VM_REG_SR_NZ;

    if (reg < VM_REG_TOTAL_COUNT)
        vm->regs[reg] = arg0;

    return status;
}

Ten fragment kodu odpowiedzialny jest za aktualizację rejestru statusu. Sprawdzany jest tutaj argument zerowy (tylko flagi Z i NZ). Z punktu widzenia tworzenia programu, informacja ta jest szczególnie istotna. Dzięki niej możliwa jest redukcja ilości użytych instrukcji.

Dla przykładu, podczas kopiowania danych algorytm powinien zakończyć pracę, jeśli ilość elementów pozostałych do skopiowania wynosi 0. Jeśli instrukcja dekrementacji (np. sub) będzie zmniejszać ilość pozostałych elementów do skopiowania, flagi Z i NZ będą się odpowiednio ustawiać w zależności od wyniku operacji odejmowania. Jeśli wartość będzie wynosić 0, wtedy program przerwie operację (przy użyciu instrukcji br).

Jeśli chodzi o implementację maszyny wirtualnej to już wszystko. Zachęcam do przejrzenia plików źródłowych.

Integracja maszyny

Użycie maszyny jest proste. Wystarczy dołączyć do projektu dwa pliki vm.c oraz vm.h. Jednak dołączenie plików nie spowoduje, że maszyna będzie od razu działać. W tym celu należy przeprowadzić integrację. Dodatkowo, należy rozszerzyć funkcjonalność maszyny o możliwość komunikacji ze światem. Bez tego nie będzie możliwa interakcja z maszyną, a co za tym idzie – brak widocznych efektów przetwarzania.

Dołączanie plików nagłówkowych

Na początku zacznijmy od dołączenia potrzebnych plików nagłówkowych:

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include "vm.h"

Póki co – nic szczególnego, standard. Aby możliwa była praca maszyny, musimy zdefiniować obszar pamięci, na której będzie ona operować. Dla przykładu, utworzyłem blok pamięci jako tablicę:

#define MEMORY_SIZE     4096
uint8_t memory[MEMORY_SIZE];

Rozmiar może ulec zmianie, może również być dynamicznie alokowany, wszystko zależy od zastosowania. W niektórych implementacjach bufor taki może okazać się zbędny – np. maszyna może pobierać dane z UART-a lub innego medium. Wszystko zależne jest od przypadku użycia.

Implementacja funkcji interfejsowych

Załóżmy, że nasza maszyna korzysta z bloku pamięci. Aby możliwy stał się dostęp do zasobów, należy zaimplementować dwie funkcje interfejsowe: vm_read() i vm_write().

void memread(vm_t *vm, uint32_t address, uint8_t *data, uint8_t size)
{
    while (size-- > 0) {
        if (address < MEMORY_SIZE) {
            *data++ = memory[address++];
        } else {
            vm->regs[VM_REG_SR] |= VM_REG_SR_ME;
            break;
        }
    }
}

void memwrite(vm_t *vm, uint32_t address, const uint8_t *data, uint8_t size)
{
    while (size-- > 0) {
        if (address < MEMORY_SIZE) {
            memory[address++] = *data++;
        } else {
            vm->regs[VM_REG_SR] |= VM_REG_SR_ME;
            break;
        }
    }
}

Jak widać, obie funkcje korzystają z wcześniej utworzonego bloku pamięci memory. Wystarczy nieco ruszyć wyobraźnią, aby spostrzec, że w zasadzie dane czytane i zapisywane przez interpreter mogą mieć różne źródła. Wszystko zależy od implementacji.

Funkcja vm_syscall()

Podstawowa integracja została zakończona. W zasadzie wystarczyłoby to, aby możliwa była interakcja z maszyną wirtualną, w tym wypadku, tylko poprzez pamięć. Co prawda niezbyt wygodna, ale zawsze jakaś.

Wygodniej jest jednak skorzystać z funkcji: vm_syscall(). Funkcja ta jest dedykowana do wykonywania operacji systemowych. Możemy tutaj podpiąć dowolne operacje, które są niezbędne do interakcji z np. system operacyjnym lub programem głównym.

uint32_t vm_syscall(vm_t *vm, uint32_t arg0, uint32_t arg1)
{
    uint32_t ret = 0;

    switch (arg1) {
        case SYSCALL_PUTC:
            putc(arg0, stdout);
            break;
        case SYSCALL_GETC:
            ret = getc(stdin);
            break;
        default:
            break;
    }

    return ret;
}

Funkcja ta przyjmuje 3 argumenty:

• obiekt wirtualnej maszyny,
• argument 0,
• argument 1 (numer wywołania systemowego).

Oba argumenty przekazują wartość, która została przekazana przez instrukcję sys. Zawsze jest to wartość rejestru (nie numer rejestru) lub stałej. Jak widać, zdefiniowaliśmy dwa wywołania systemowe:  SYSCALL_PUTC oraz  SYSCALL_GETC. Definicja kodów poszczególnych wywołań zdefiniowana jest za pomocą typu wyliczeniowego.

enum {
    SYSCALL_PUTC,
    SYSCALL_GETC
};

Oczywiście, numer/kody wywołań systemowych mogą być dowolną liczbą 32-bitową.

Implementacja main()

Teraz przyszedł czas na main(). Implementacja jest stosunkowo prosta:

int main(int argc, char argv[])
{
    vm_t vm;
    
    vm_init(&vm, memread, memwrite, vm_syscall, NULL);
    
    while (vm_step(&vm));
    
    return 0;
}

Aby kompilacja była przyjemniejsza, dodałem skrypt CMake’a:

cmake_minimum_required(VERSION 3.0)
project(vm LANGUAGES C)
add_executable(vm main.c vm.c)

Pierwsze uruchomienie

Aby zbudować przykład, należy w katalogu, w którym znajdują się pliki, utworzyć katalog build. Następnie z katalogu build wywołać Cmake’a i kolejno make. Jak pokazano poniżej:

mkdir build
cd build
cmake ..
make

Jeśli środowisko jest poprawnie skonfigurowane, proces budowania powinien przejść pomyślnie.

W wyniku budowania powstanie plik wykonywalny vm. Można by już uruchomić naszą maszynę, ale jak łatwo się można domyślić, nie będzie żadnego efektu lub efekt będzie losowy (przypadkowe dane w pamięci).

Należy zatem napisać program testowy Hello World!. Problem polega na tym, że, póki co, nie posiadamy kompilatora, który to będzie omawiany w kolejnej części artykułu.

Żeby jednak nie pozostawić czytelników bez wyników uruchomienia naszej wirtualnej maszyny, załączam program testowy w formie binarnej. Sprawdźcie sami, jaki jest wynik:

uint8_t memory[MEMORY_SIZE] = {
    0x8d, 0x06, 0x00, 0x00, 0x00, 0x10, 0x8d, 0x80, 
    0x00, 0x00, 0x00, 0x12, 0x8d, 0x42, 0x00, 0x00, 
    0x00, 0x00, 0x00, 0x18, 0x00, 0x00, 0x00, 0xff, 
    0xd5, 0xff, 0xff, 0xff, 0xff, 0x0f, 0x97, 0x00, 
    0x0f, 0xe9, 0x12, 0x00, 0x00, 0x00, 0x01, 0x00,
    0x00, 0x00, 0xf5, 0x00, 0x00, 0x00, 0x00, 0x0f, 
    0x2d, 0x01, 0x00, 0x00, 0x00, 0x00, 0x2d, 0xe2, 
    0xff, 0xff, 0xff, 0x10, 0xdd, 0x02, 0x00, 0x00, 
    0x00, 0x0f, 0x48, 0x65, 0x6c, 0x6c, 0x6f, 0x20, 
    0x57, 0x6f, 0x72, 0x6c, 0x64, 0x21, 0x0a, 0x00, 
};

Załączniki do pobrania:

Pliki maszyny