.. _z1-elf: ============================== Zadanie 1: Kalkulator Wyborczy ============================== Data ogłoszenia: 21.03.2019 Termin oddania: 11.04.2019 (ostateczny 25.04.2019) .. contents:: .. toctree:: :hidden: Materiały dodatkowe =================== - :download:`crossld.h` - :download:`z1-hello-world.tar` - :download:`z1-test.tar` - :download:`switch_64_32.c` - :download:`z1_tests.tar.gz` (aktualizacja: poprawione budowanie) .. - :ref:`z1-elf-en` 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 11. 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: :download:`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``.