Zadanie 1: Kalkulator Wyborczy

Data ogłoszenia: 21.03.2019

Termin oddania: 11.04.2019 (ostateczny 25.04.2019)

Materiały dodatkowe

Kalkulator Wyborczy

W ostatnim czasie wygraliśmy przetarg na organizację wyborów. Aby nie było konieczne ręczne liczenie głosów, postanowiliśmy utworzyć stosowny program – Kalkulator Wyborczy. Jego realizacją zajęli się oczywiście studenci w ramach Zespołowego Projektu Programistycznego.

Studentom udało się z powodzeniem zaprojektować i napisać program. Niestety, przy wdrożeniu nastąpił powien problem – program został nam dostarczony jako 32-bitowy program binarny, używający profesjonalnego systemu baz danych Wróżbita® (Enterprise Edition). Nasza licencja nie pozwala natomiast na użycie 32-bitowych bibliotek klienckich do tego systemu – mamy tylko i wyłącznie biblioteki 64-bitowe. Nie byliśmy też w stanie zdobyć 64-bitowej wersji programu ani jego źródeł (autorzy z jakiegoś powodu nie odpisują na nasze maile od kiedy obronili pracę licencjacką).

Oczywistym rozwiązaniem jest więc napisanie biblioteki, która pozwoli na łączenie 32-bitowego i 64-bitowego kodu w jednym procesie. Jesteśmy przekonani, że biblioteka ta pozwoli na bezproblemowe uruchomienie naszego programu i płynne przeprowadzenie uczcziwych wyborów.

Zadanie

Napisać bibliotekę pozwalającą na załadowanie 32-bitowego programu w formacie ELF do 64-bitowego procesu i wywoływanie 64-bitowych funkcji z 32-bitowego kodu.

Interfejs biblioteki

Biblioteka powinna dostarczać jedną funkcję, która powoduje załadowanie i uruchomienie 32-bitowego programu w osobnym procesie:

enum type {
        TYPE_VOID,
        TYPE_INT,
        TYPE_LONG,
        TYPE_LONG_LONG,
        TYPE_UNSIGNED_INT,
        TYPE_UNSIGNED_LONG,
        TYPE_UNSIGNED_LONG_LONG,
        TYPE_PTR,
};

struct function {
        const char *name;
        const enum type *args;
        int nargs;
        enum type result;
        void *code;
};

int crossld_start(const char *fname, const struct function *funcs, int nfuncs);

Pierwszym parametrem do funkcji crossld_start jest nazwa pliku zawierającego 32-bitowy program, który powinien zostać załadowany. Drugi parametr jest tablicą (64-bitowych) funkcji, które załadowany program powinien móc wywołać. Trzeci parametr jest rozmiarem tej tablicy.

Funkcja powinna wykonać następujące czynności:

  1. Otworzyć podany plik i zweryfikować, że rzeczywiście jest 32-bitowym programem na architekturę i386 w formacie ELF.

  2. Wczytać nagłówki programu i załadować program do pamięci używając stosownych wywołań mmap.

  3. Dla każdej funkcji w liście przekazanej jako drugi parametr stworzyć odpowiadający fragment 32-bitowego kodu (trampolinę), który:

    • przełączy się w tryb 64-bitowy

    • przekonwertuje przekazane argumenty na 64-bitową konwencję wywołań

    • wywoła 64-bitową wersję funkcji (podaną w strukturze function)

    • przejdzie z powrotem do trybu 32-bitowego

    • przekonwertuje wynik funkcji na 32-bitową konwencję wywołań

    • wróci do wywołującego 32-bitowego kodu

  4. Przeczytać strukturę _DYNAMIC programu, znaleźć tabelę relokacji i powstawiać w odpowiednie miejsca adresy wytworzonych przed chwilą funkcji.

  5. Zaalokować nowy stos w zakresie adresów dostępnym z trybu 32-bitowego i przełączyć się na niego.

  6. Przełączyć się w tryb 32-bitowy.

  7. Skoczyć do punktu wejścia zadanego programu.

Struktura function zawiera następujace pola:

  • name: nazwa funkcji (nazwa symbolu, której program 32-bitowy będzie mógł użyć)

  • args: tablica typów argumentów funkcji:

    • TYPE_INT: argument typu int

    • TYPE_LONG: argument typu long

    • TYPE_LONG_LONG: argument typu long long

    • TYPE_UNSIGNED_INT: argument typu unsigned int

    • TYPE_UNSIGNED_LONG: argument typu unsigned long

    • TYPE_UNSIGNED_LONG_LONG: argument typu unsigned long long

    • TYPE_PTR: argument typu void * bądź podobnego

  • nargs: liczba argumentów funkcji

  • result: typ zwracany przez funkcję (takie typy jak przy argumentach, bądź TYPE_VOID jeśli funkcja nie zwraca wyniku)

  • code: wskaźnik na (64-bitową) funkcję, którą należy wywołać

Poza funkcjami użytkownika, opisanymi w drugim parametrze, biblioteka powinna również udostępniać programowi funkcję exit (oczywście 32-bitową):

_Noreturn void exit(int status)

Wywołanie funkcji exit powinno:

  1. Przełączyć się z powrotem w tryb 64-bitowy

  2. Wrócić do oryginalnego stosu (z czasu wywołania crossld_start)

  3. Zwolnić wszystkie zasoby zaalokowane przez crossld_start

  4. Wrócić do kodu, który wywołał crossld_start, zwracając status jako wynik tej funkcji.

Funkcja exit jest opcjonalna – jej brak będzie kosztował 2 punkty.

Jeśli z jakiegoś powodu uruchomienie programu nie uda się (nie jest to plik ELF, niezdefiniowany symbol, itp.), funkcja crossld_start powinna zwrócić -1.

W przypadku błędu podczas konwersji wartości zwracanych (wskaźnik 64-bitowy, który nie mieści się w 32 bitach), biblioteka powinna zakończyć wykonanie 32-bitowego kodu, posprzątać zasoby, po czym zwrócić -1 z funkcji crossld_start (tak jakby została wywołana funkcja exit). Jeśli nasze rozwiązanie nie wspiera funkcji exit, możemy zamiast tego zakończyć proces funkcją abort.

Założenia

Można założyć, że wykonywany program 32-bitowy:

  • jest typu ET_EXEC

  • nie używa TLS (nie ma PT_TLS)

  • nie używa innych relokacji dynamicznych niż R_386_JMP_SLOT

Można zignorować wszystkie wpisy w nagłówkach programów inne niż PT_LOAD i PT_DYNAMIC oraz wszystkie wpisy w tabeli _DYNAMIC inne niż DT_STRTAB, DT_SYMTAB, DT_PLTRELSZ, DT_JMPREL.

Forma rozwiązania

Jako rozwiązanie należy dostarczyć paczkę zawierającą:

  • dowolną liczbę plików źródłowych z kodem rozwiązania

  • plik Makefile kompilujący rozwiązanie, lub odpowiadający plik z innego sensownego systemu budowania (np. cmake)

  • plik readme z krótkim opisem rozwiązania i instrukcjami kompilacji na obrazie qemu z pierwszych zajęć

Kod rozwiązania powinien być napisany w całości w C (ew. C++) i może używać sensownych bibliotek dostępnych w wykorzystywanym na zajęciach systemie Debian. Rozwiązanie powinno kompilować się do biblioteki o nazwie libcrossld.so implementującej interfejs z pliku nagłówkowego. Biblioteka nie powinna eksportować żadnych symboli poza tymi w nagłówku.

Rozwiązania będą testowane wewnątrz qemu, uruchomionego z obrazem z pierwszych zajęć. Polecamy sprawdzenie, czy rozwiązania kompilują się w tym obrazie.

Rozwiązania prosimy nadsyłać na adres p.zuk@mimuw.edu.pl z kopią do mwk@mimuw.edu.pl.

Zasady oceniania

Za zadanie można uzyskać do 10 punktów. Na ocenę zadania składają się trzy części:

  • działanie funkcji crossld_start (od 0 do 8 punktów)

  • działanie funkcji exit (od 0 do 2 punktów)

  • ocena kodu rozwiązania (od 0 do -10 punktów)

Najczęstsze błędy - spis oznaczeń w USOSwebie

  1. Eksport dodatkowych symboli (-0.3)

  2. Brak README (-0.2)

  3. Odwołania do sekcji (-0.8)

  4. Zmienne globalne (-0.8)

  5. Kopiowanie segmentów do pamięci (-0.5)

  6. Brak zamykania pliku (-0.5)

  7. Exit zamiast zwrócenia -1 z crossld_start (-0.8)

  8. Fragile code (-1.0)

  9. Ładowanie całego ELF na stos (-0.5)

  10. Obsługa błędów (-0.2 pkt za usterkę, max -1.5 pkt):

  • brak sprawdzenia wyniku malloc/mmap/etc

  • brak zamykania pliku przy błędzie (o ile nie występuje pkt 6)

  • wycieki pamięci

  1. Nieodtworzenie wymaganego rejestru (-0.2)

Przechodzenie między trybem 32-bitowym a 64-bitowym

W architekturze x86, wybór trybu 32-bitowego bądź 64-bitowego jest dokonywany przez użycie odpowiedniego segmentu kodu. Aby przełączyć się między trybami, musimy użyć jednej z trzech instrukcji, które są w stanie zmienić aktywny segment kodu (i mogą być użyte w trybie użytkownika):

  • jmp far (ljmp w składni AT&T)

  • call far (lcall w składni AT&T)

  • ret far (lret w składni AT&T)

Aby przejść w tryb 32-bitowy, należy użyć jednej z powyższych instrukcji z docelowym selektorem segmentu kodu równym 0x23. Aby przejść w tryb 64-bitowy, należy użyć selektora 0x33. Po przejściu w tryb 32-bitowy należy ponadto ustawić segment danych na 0x2b zanim będziemy mogli odwołać się do pamięci, na przykład w następujący sposób:

pushl $0x2b
popl %ds
pushl $0x2b
popl %es

Należy pamiętać, że przejście w tryb 32-bitowy zniszczy stan rejestrów %r8-%r15 oraz górną część wszystkich rejestrów.

Należy zapewnić, że cały kod 32-bitowy (trampoliny itp.) oraz kod 64-bitowy wywoływany bezpośrednio z kodu 32-bitowego będzie umieszczony w pierwszych 4GB pamięci. To samo dotyczy stosu używanego przez kod 32-bitowy.

Należy pamiętać, że tryby 32-bitowy i 64-bitowy mają różne konwencje wywołań funkcji, w tym zbiór zachowanych rejestrów.

Przykład: switch_64_32.c.

Wskazówki

Wywołując funkcje napisane w C, należy zapewnić odpowiednie wyrównanie stosu. Przed wykonaniem instrukcji call, stos musi być wyrównany do 16 bajtów.

Ponieważ rozwiązanie ma być 64-bitową biblioteką ładowaną dynamicznie, konieczna będzie ręczna relokacja części kodu (trampolin wchodzących i wychodzących z trybu 32-bitowego) do niskich 4GB. Należy w tym celu stworzyć odpowiednie wykonywalne mapowanie z MAP_32BIT.

Ponieważ wywołanie funkcji użytkownika wymaga przekazania parametrów, których liczba nie jest z góry znana, konieczne będzie napisanie funkcji w assemblerze, która dynamicznie przekazuje odpowiednią liczbę argumentów na stosie.

Należy pamiętać, że zbiór zachowanych rejestrów jest inny w trybie 64-bitowym niż w trybie 32-bitowym – funkcja wołająca kod 64-bitowy z 32-bitowego powinna zachować rejestry %esi i %edi.

Należy pamiętać, że wejście w tryb 32-bitowy zniszczy górną część wszystkich rejestrów – implementując crossld_start + exit należy zachować i odtworzyć stan rejestrów %rbx, %rbp, %r12-%r15.