Zadanie 1: Konwerter plików binarnych ¶

Data ogłoszenia: 28.02.2023

Termin oddania: 28.03.2023 (ostateczny 11.04.2023)

Materiały dodatkowe ¶

przykład działania: example.tar.gz
testy: z1_test.tar.gz

ARM jest powszechny w smartfonach i IoT. Ostatnio jednak zyskuje na popularności także w innych zastosowaniach: komputerach (Apple M1/M2) oraz serwerach chmurowych. Ponieważ istnieje wiele oprogramowania przeznaczonego na x86-64, przydatne są mechanizmy uruchamiania takiego oprogramowania na ARMie. Takich mechanizmów dostarczają emulatory o różnych możliwościach i wydajności, na przykład QEMU, które konwertuje instrukcje pomiędzy architekturami metodą just-in-time, i Rosetta, która konwertuje cały kod przed uruchomieniem programu.

Zadanie ¶

Napisać konwerter plików ET_REL x86-64 w pliki ET_REL AArch64.

Założenia ¶

Wejściem do procesu konwersji jest 1 (jeden) plik binarny w formacie ET_REL o architekturze EM_X86_64.
Wyjściem z procesu konwersji powinien być 1 (jeden) plik binarny w formacie ET_REL o architekturze EM_AARCH64.
Plik ET_REL może zawierać:
- sekcje o nazwie .note.gnu.property lub *.eh_frame (na przykład .eh_frame, .rela.eh_frame) - należy je usunąć (również z tablicy nazw sekcji)
- jedną sekcję z symbolami (typu SHT_SYMTAB), a w niej:
  
  symbole typu STT_NOTYPE, STT_FUNC i STT_OBJECT
  
  dla własnych symboli należy dostosować ich wartość (i rozmiar w przypadku STT_FUNC) zgodnie z ich położeniem w sekcji wyjściowego pliku
  
  zewnętrzne symbole należy pozostawić bez zmian
  
  można założyć, że nie ma symboli zdefiniowanych wewnątrz funkcji
  
  symbole typu STT_SECTION i STT_FILE - należy je pozostawić bez zmian
- sekcje z relokacjami (typu SHT_RELA), a w nich:
  
  relokacje typu R_X86_64_PC32, R_X86_64_PLT32, R_X86_64_32, i R_X86_64_32S wewnątrz funkcji - należy je przekonwertować zgodnie z wytycznymi konwertowania instrukcji poniżej
  
  relokacje typu R_X86_64_64 poza funkcjami - należy je przekonwertować na relokacje typu R_AARCH64_ABS64
  
  Można założyć, że nie będzie wielu relokacji dotyczących tego samego położenia w tej samej sekcji.
- inne sekcje: każdą funkcję występującą w sekcji (według tablicy symboli) należy zastąpić funkcją przekonwertowaną na AArch64 zgodnie z wytycznymi poniżej (jeśli w sekcji nie ma funkcji, należy pozostawić jej zawartość bez zmian)
Nie trzeba obsługiwać następujących funkcjonalności:
- symboli w “sekcji” SHN_COMMON bądź innych specjalnych sekcjach
- innych typów symboli i relokacji niż podane powyżej
- instrukcji i relokacji w instrukcjach innych niż wymienione w opisie konwertowania funkcji

Konwertowanie funkcji ¶

Prolog i epilog ¶

Zakładamy, że każda funkcja x86-64 zaczyna się od następującego prologu:

endbr64
push rbp
mov rbp, rsp

a kończy następującym epilogiem:

leave
ret

Zakładamy również, że ten epilog jest jedynym punktem powrotu z funkcji.

Prolog należy przekonwertować na:

stp x29, x30, [sp, #-16]!
mov x29, sp

a epilog na:

mov x0, x9
add sp, x29, #16
ldp x29, x30, [sp, #-16]
ret

W AArch64 adres powrotu nie jest odkładany na stos, tylko zachowywany w rejestrze x30 (zwany też lr). x29 (zwany też fp) jest natomiast odpowiednikiem rbp. Przekonwertowany prolog, oprócz naśladowania prologu x86-64, odkłada na stos rejestr x30, tworząc tym samym na stosie taką samą ramkę jak w x86-64. Epilog, oprócz działania symetrycznego do prologu, umieszcza wynik funkcji w odpowiednim rejestrze (patrz kolejna sekcja).

Mapowanie rejestrów ¶

Rejestry 64-bitowe x86-64 należy mapować na rejestry AArch64 w następujący sposób:

# Caller-saved:
rdi -> x0 # 1. argument
rsi -> x1 # 2. argument
rdx -> x2 # 3. argument
rcx -> x3 # 4. argument
r8 -> x4 # 5. argument
r9 -> x5 # 6. argument
rax -> x9
r10 -> x10
r11 -> x11
# Callee-saved:
rbp -> x29 # fp
rbx -> x19
r12 -> x20
r13 -> x21
r14 -> x22
r15 -> x23
rsp -> sp

Rejestry 32-bitowe, z wyjątkiem esp, należy mapować analogicznie na 32-bitowe rejestry AArch64, które mają prefiks w zamiast x (więc na przykład edi powinien być mapowany na w0). sp w AArch64 nie jest rejestrem ogólnego przeznaczenia, przez co nie ma 32-bitowej wersji i można go używać tylko w niektórych instrukcjach. Zakładamy, że rejestry 16- i 8-bitowe nie będą używane.

Przy konwertowaniu instrukcji będziemy używali dodatkowych rejestrów na wartości tymczasowe, oznaczonych przez {tmp1} i {tmp2}. Oznaczają one odpowiednio x12/w12 i x13/w13 w zależności od rozmiaru operandów instrukcji x86-64. W przypadkach, gdy należy zawsze użyć rejestru 64-bitowego, oznaczamy to przez sufiks .64.

Takie mapowanie zachowuje rejestry caller-saved i callee-saved oraz rejestry używane do przekazywania pierwszych 6 argumentów, dzięki czemu o ile wołane funkcje mają mniej niż 6 argumentów (co zakładamy w tym zadaniu), zachowanie mapowania w każdej instrukcji zapewnia zachowanie prawidłowego przekazywania argumentów. Jest jednak jedna różnica: w AArch64, inaczej niż w x86-64, ten sam rejestr służy do zwracania wyniku funkcji i przekazywania pierwszego argumentu. Stąd konieczność umieszczenia wyniku w prawdiłowym rejestrze w epilogu.

Operandy pamięciowe ¶

W niektórych instrukcjach mogą pojawić się operandy pamięciowe. Należy założyć, że taki operand jest zawsze adresowany za pomocą bazy i przesunięcia, a bez indeksu (czyli zawsze jest postaci [reg + imm]). Gdy wytyczne konwertowania instrukcji nakazują odczytać operand pamięciowy {op} do rejestru {reg}, należy postąpić następująco:

Jeśli baza to rip, należy założyć, że przesunięcie ma relokację typu R_X86_64_PC32 lub R_X86_64_PLT32. Należy przekonwertować ją na relokację typu R_AARCH64_LD_PREL_LO19 i wygenerować następujący kod (znak @ oznacza komentarz):
```
ldr {reg}, #0 @ przesunięcie jest relokowane
```

W przeciwnym wypadku należy wygenerować następujący kod:

mov {tmp1.64}, {op.displacement} @ umieść przesunięcie w rejestrze, ponieważ ldr reg, [reg, imm] pozwala tylko na nieujemne przesunięcia
ldr {reg}, [{op.base}, {tmp1.64}]

Relokacje ¶

W AArch64 wszystkie instrukcje mają rozmiar 32 bitów, przez co nie mają miejsca na 32-bitowe wartości, które byłyby relokowane. Z tego powodu istnieją różne relokacje dla różnych instrukcji, w zależności od tego, które bity instrukcji są przeznaczone na relokowaną wartość. Adres tych relokacji jest zawsze równy adresowi odpowiedniej instrukcji. Ponadto przesunięcia w instrukcjach (np. w skokach) są liczone względem adresu instrukcji. Dzięki temu we względnych relokacjach nie jest potrzebna poprawka, tak jak ma to miejsce na przykład w instrukcji call w x86-64.

Konwertowanie instrukcji ¶

W poniższych opisach {op1} i {op2} odnoszą się do kolejnych operandów instrukcji x86-64, w razie potrzeby zmapowanych jeśli są rejestrami. Nie wszystkie założenia konieczne, by poniższa konwersja była poprawna zostały tutaj opisane, lecz w rozwiązaniu nie należy się tym przejmować.

`add reg, reg/imm`¶

Należy wygenerować następujący kod:

add {op1}, {op1}, {op2}

`sub reg, reg/imm`¶

Należy wygenerować następujący kod:

sub {op1}, {op1}, {op2}

`cmp`¶

`cmp mem, reg/imm`¶

Należy wygenerować następujący kod:

{odczytaj op1 do rejestru tmp1}
cmp {tmp1}, {op2}

`cmp reg, mem`¶

Należy wygenerować następujący kod:

{odczytaj op2 do rejestru tmp1}
cmp {op1}, {tmp1}

`cmp reg, reg/imm`¶

Należy wygenerować następujący kod:

cmp {op1}, {op2}

`call imm`¶

Należy założyć, że przesunięcie wywołania ma relokację typu R_X86_64_PC32 lub R_X86_64_PLT32. Należy przekonwertować ją na relokację typu R_AARCH64_CALL26 i wygenerować następujący kod:

bl #0 @ przesunięcie jest relokowane
mov x9, x0 @ umieść wynik funkcji w rejestrze, na który mapuje się rax

`mov`¶

`mov reg, mem`¶

Należy wygenerować następujący kod:

{odczytaj op2 do rejestru op1}

`mov mem, reg/imm`¶

Jeśli baza operandu pamięciowego to rip, należy założyć, że przesunięcie ma relokację typu R_X86_64_PC32 lub R_X86_64_PLT32. Należy przekonwertować ją na relokację typu R_AARCH64_ADR_PREL_LO21 i wygenerować następujący kod:

adr {tmp1.64}, #0 @ umieść adres docelowy w rejestrze, ponieważ w AArch64 nie ma instrukcji str pc-relative (przesunięcie jest relokowane)
mov {tmp2}, {op2} @ potrzebne gdy op2 to immediate, dla uproszczenia robimy tak również gdy jest to rejestr
str {tmp2}, [{tmp1.64}] @ zapisz wartość

W przeciwnym wypadku:

Jeśli drugi operand to immediate mający relokację typu R_X86_64_32 lub R_X86_64_32S, należy przekonwertować ją na typ R_AARCH64_ADR_PREL_LO21 i wygenerować następujący kod:

adr {tmp1.64}, #0 @ przesunięcie jest relokowane
mov {tmp2.64}, #{op1.displacement} @ umieść przesunięcie w rejestrze, ponieważ str reg, [reg, imm] pozwala tylko na nieujemne przesunięcia
str {tmp1}, [{op1.base}, {tmp2.64}] @ zapisz wartość

W przeciwnym wypadku należy wygenerować następujący kod:

mov {tmp1}, {op2} @ potrzebne gdy op2 to immediate, dla uproszczenia robimy tak również gdy jest to rejestr
mov {tmp2.64}, #{op1.displacement} @ umieść przesunięcie w rejestrze, ponieważ str reg, [reg, imm] pozwala tylko na nieujemne przesunięcia
str {tmp1}, [{op1.base}, {tmp2.64}] @ zapisz wartość

`mov reg, reg/imm`¶

Jeśli drugi operand to immediate mający relokację typu R_X86_64_32 lub R_X86_64_32S, należy przekonwertować ją na typ R_AARCH64_ADR_PREL_LO21 i wygenerować następujący kod:
```
adr {op1.64}, #0 @ przesunięcie jest relokowane
```
W przeciwnym wypadku należy wygenerować następujący kod:
```
mov {op1}, {op2}
```

Skoki ¶

Przesunięcie każdego skoku należy dostosować do przekonwertowanego kodu - tak, by skakał do instrukcji, do których została przekonwertowana jego pierwotna instrukcja docelowa. W opisie generowanego kodu to dostosowanie jest oznaczone przez {adjust(op1)}. Można założyć, że skoki odbywają się zawsze w obrębie funkcji.

`jmp imm`¶

Należy wygenerować następujący kod:

b {adjust(op1)}

`j<cc> imm` (skok warunkowy)¶

Należy wygenerować nastepujący kod:

b.{cc} {adjust(op1)}

Mapowanie warunków w skokach warunkowych jest następujące:

a -> hi
ae -> hs
b -> lo
be -> ls
e -> eq
g -> gt
ge -> ge
l -> lt
le -> le
na -> ls
nae -> lo
nb -> hs
nbe -> hi
ne -> ne
ng -> le
nge -> lt
nl -> ge
nle -> gt
no -> vc
nz -> ne
o -> vs
z -> eq

W x86-64 istnieją też warunki niemające odpowiednika w AArch64, ale można założyć, że się nie pojawią.

Uruchamianie kodu AArch64 ¶

Do uruchomienia przekonwertowanego kodu można użyć QEMU i tego obrazu. Można użyć następującej komendy:

qemu-system-aarch64 -m 2G -M virt -cpu max \
  -bios /usr/share/qemu-efi-aarch64/QEMU_EFI.fd \
  -drive if=none,file=debian-11-nocloud-arm64-20230124-1270.qcow2,id=hd0 -device virtio-blk-device,drive=hd0 \
  -device e1000,netdev=net0 -netdev user,id=net0,hostfwd=tcp:127.0.0.1:2222-:22 \
  -nographic

By połączyć się z tą maszyną przez SSH, należy w niej najpierw wykonać ssh-keygen -A w katalogu /etc/ssh. Przydatne może być również ustawienie następujących opcji w /etc/ssh/sshd_config:

PermitRootLogin yes
PasswordAuthentication yes
PermitEmptyPasswords yes

Po wprowadzeniu tych zmian trzeba wykonać systemctl start sshd lub zrestartować maszynę.

Forma rozwiązania ¶

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

dowolną liczbę plików źródłowych z kodem rozwiązania w języku C, C++ lub Python
jeśli rozwiązanie jest napisane w języku kompilowanym, 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ęć

Rozwiązanie (po ew. kompilacji) powinno znajdować się w pliku wykonywalnym o nazwie converter. Program powinien mieć następujący interfejs:

./converter <plik ET_REL> <docelowy plik ET_REL>

Konwerter będzie uruchamiany wewnątrz qemu uruchomionego z obrazem z pierwszych zajęć. Polecamy sprawdzenie, czy rozwiązania kompilują się w tym obrazie. Przekonwertowane pliki będą natomiast uruchamiane wewnątrz qemu uruchomionego z wymienionym wyżej obrazem AArch64.

Rozwiązania prosimy nadsyłać na adres a.jackowski@mimuw.edu.pl z kopią do w.ciszewski@mimuw.edu.pl.

Zasady oceniania ¶

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

wynik automatycznych testów (od 0 do 10 punktów)
ocena kodu rozwiązania (od 0 do -10 punktów)

Wskazówki ¶

Do deasemblacji polecamy bibliotekę Capstone, a do asemblacji - Keystone. Wbrew instrukcjom na podlinkowanych stronach do instalacji do użytku w Pythonie wystarczające zdaje się:

pip install capstone keystone-engine

Zadanie 1: Konwerter plików binarnych ¶

Materiały dodatkowe ¶

Wprowadzenie ¶

Zadanie ¶

Założenia ¶

Konwertowanie funkcji ¶

Prolog i epilog ¶

Mapowanie rejestrów ¶

Operandy pamięciowe ¶

Relokacje ¶

Konwertowanie instrukcji ¶

`add reg, reg/imm`¶

`sub reg, reg/imm`¶

`cmp`¶

`cmp mem, reg/imm`¶

`cmp reg, mem`¶

`cmp reg, reg/imm`¶

`call imm`¶

`mov`¶

`mov reg, mem`¶

`mov mem, reg/imm`¶

`mov reg, reg/imm`¶

Skoki ¶

`jmp imm`¶

`j<cc> imm` (skok warunkowy)¶

Uruchamianie kodu AArch64 ¶

Forma rozwiązania ¶

Zasady oceniania ¶

Wskazówki ¶

Table of Contents

Previous topic

Next topic

This Page