owned this note
owned this note
Published
Linked with GitHub
# Architektury systemów komputerowych - machine level programming
## Lista zadań nr 4
### Zadanie 1
Mając wartości typu `long` mamy podać wartości operandów źródłowych.
| Adres |Wartość |Rejestr |Wartość |
|:-------:|:------:|:------:|:-------:|
| `0x100` | `0xFF` | `%rax` | `0x100` |
| `0x108` | `0xAB` | `%rcx` | `1` |
| `0x110` | `0x13` | `%rdx` | `3` |
| `0x118` | `0x11` | - | - |
Skorzystamy z notatek z wykładu, dokładniej z 29. slajdu prezentacji "Machine‐Level Programming I: Basics". W poniższych wzorach $D$ oznacza przesunięcie o stałą liczbę bajtów, $Rb$ i $Ri$ to rejestry do których się odwołujemy, a $S$ to skala (rozmiar danej):
* $\text{D(Rb, Ri, S) = Mem[Reg[Rb]+S*Reg[Ri]+D]}$
* $\text{(Rb, Ri) = Mem[Reg[Rb]+Reg[Ri]]}$
* $\text{D(Rb, Ri) = Mem[Reg[Rb]+Reg[Ri]+D]}$
* $\text{(Rb, Ri, S) = Mem[Reg[Rb]+S*Reg[Ri]]}$
Rozwiązanie:
1. `%rax` zwraca `0x100`
2. `0x110` zwraca `0x13`
3. `$0x108` zwraca `0x108` - jakaś stała
4. `(%rax)` zwraca `0xFF` - dereferencja wskaźnika, tzn. bierzemy wartość `%rax` jako adres
5. `8(%rax)` zwraca `(%rax + 8) = (0x108) = 0xAB` - jak wyżej
6. `21(%rax, %rdx)` zwraca `(%rax + %rdx + 21) = (0x100 + 3 + 21) = (0x100 + 0x18) = (0x118) = 0x11`
7. `0xFC(, %rcx, 4)` zwraca `(4 * %rcx + 0xFC) = (0x4 + 0xFC) = (0x100) = 0xFF`
8. `(%rax, %rdx, 8)` zwraca `(0x100 + 8 * %rdx) = (0x100 + 24) = (0x100 + 0x18) = (0x118) = 0x11`
9. `265(%rcx, %rdx, 2)` zwraca `(%rcx + 2 * %rdx + 265) = (0x1 + 0x6 + 0x109) = (0x110) = 0x13`
### Zadanie 2
Używając tabelki z 1. zadania mamy obliczyć wartości obliczone przez wybrane instrukcje oraz podać adres wyniku. Do rozwiązania używam notacji podanej na wykładzie, tj. przyjmowanymi argumentami są source oraz destination (w podanej kolejności).
| Instrukcja | Adres / Rejestr | Wartość |
| ----------------------------- | --------------- | ----------------------------------------------------- |
| `addq %rcx, (%rax)` | `0x100` | `0xFF + 0x1 = 0x100` |
| `subq 16(%rax), %rdx` | `%rdx` | `3 - (16 + 0x100) = 3 - (0x110) = 0x3 - 0x13 = -0xF0` |
| `shrq $4,%rax` | `%rax` | `0x100 >> 4 = 0x10` |
| `incq 16(%rax)` | `(%rax + 0x10) = (0x100 + 0x10) = (0x110)` | `0x13 + 0x1 = 0x14` |
| `decq %rcx` | `%rcx` | `0x1 - 0x1 = 0x0` |
| `imulq 8(%rax)` |`R[%rdx]:R[%rax]`| Adres operandu:`(%rax + 0x8) = (0x100 + 0x8) = (0x108)`, więc `0xAB * 0x100 = 0xAB00` |
| `leaq 7(%rcx, %rcx, 8), %rdx` | `%rdx` | `(%rcx + 8 * %rcx + 7) = (0x10) => 0x10` |
| `leaq 0xA(, %rdx, 4), %rdx` | `%rdx` | `(%rdx * 4 + 0xA) = (0xC + 0xA) = (0x16) => 0x16` |
W przykładzie `imulq 8(%rax)` występuje tylko jeden operand, dlatego używany jest drugi operand przechowywany w `%rax`. Skoro mnożymy dwie liczby 64-bitowe, to wynik może się nie zmieścić - aby tego uniknąć, jest on zapisywany w dwóch rejestrach w formacie `R[%rdx]:R[%rax]`, tzn. najbardziej znaczące 64 bity są w `%rdx`, a pozostałe w `%rax`.
### Zadanie 3
W `%rdi` i `%rsi` są przechowywane wartości zmiennych `x` oraz `y`, porównujemy je instrukcją `cmp %rsi, %rdi`. Aby skoczyć do etykiety `label` należy użyć instrukcji:
* dla $x \geq y$ jest to `jge label` lub `jnl label`. W semantyce bitów w rejestrze flag wyrażeniu odpowiada `~(SF ^ OF)`
* dla $x < y$ jest to `jl label` lub `jnge label`, czyli `SF ^ OF`
* dla $x > y$ jest to `jg label` lub `jnle label`, czyli `~(SF ^ OF) & ~ZF`
W rejestrze mamy następujące flagi, ich działanie przedstawić możemy dla prostej operacji zapisanej w C jako `t = a + b`, gdzie zmienne są typu `int`.
* `CF`, tzn. carry flag, mówi ona o tym, czy w najnowszej operacji doszło do nadmiaru (tylko dla `unsigned`): `(unsigned)t < (unsigned)a`,
* `ZF` czyli zero flag mówi o tym, czy najnowsza operacja zwróciła $0$: `(t == 0)`
* `SF`, czyli sign flag, mówi o tym, czy w ostatnim wyrażeniu otrzymano wartość ujemną: `(t < 0)`
* `OF`, czyli overflow flag, mówi o tym, czy ostatnia operacja spowodowała nadmiar (obojętnie czy negative czy positive) dla liczb zapisywanych w systemie uzupełnień do dwóch: `(a < 0 == b < 0) && (t < 0 != a < 0)`
### Zadanie 4
Implementacja konwersji między little-endian a big-endian w asemblerze x86-64 dla liczby typu `uint32_t`. Argument otrzymujemy w `%edi`, a zwracany wynik ma być w `%eax`.
Kod w C do przetłumaczenia:
```c=
uint32_t func(uint32_t x)
{
uint32_t a = x & 0xff00ff00;
uint32_t b = x & 0x00ff00ff;
a = (a << 8) | (a >> 32-8);
b = (b >> 8) | (b << 32-8);
return a | b;
}
```
Odpowiadający kod w Asemblerze:
```=
movq %rdi, %r8
movq %rdi, %r9
andq $0xFF00FF00, %r8
andq $0x00FF00FF, %r9
rol %r8d, 8
ror %r9d, 8
orq %r9, %r8
movq %r8, %rax
```
Lub krótszy:
```=
movl %edi, %eax ; 1234
rol $8, %ax ; 1243
rol $16, %eax ; 4312
rol $8, %ax ; 4321
```
Implementacja funkcji `rol` oraz `ror` w C:
```c=
uint32_t rol(uint32_t val, uint32_t shift)
{
return (val << shift) | (val >> (32 - shift));
}
uint32_t ror(uint32_t val, uint32_t shift)
{
return (val >> shift) | (val << (32 - shift));
}
```
Funkcje te przesuwają bity w wybraną stronę, jednocześnie zawijając je - można to porównać do przesuwania ciągu znaków po okręgu, tzn. dla liczby `x = 0xA1B2C3D4` funkcja `rol(x, 8)` zwróci `0xB2C3D4A1`, a `ror(x, 8)` zwróci `0xD4A1B2C3`.
### Zadanie 5
Implementacja operacji `x + y` dla `int128_t x, y`, tzn. zmienne te nie mieszczą się w rejestrach maszynowych. `x` jest przekazywany przez `%rdi` (starsze bity) oraz `%rsi` (młodsze), a `y` przez `%rdx` i `%rcx`, wynik zwracany jest w rejestrach `%rdx` i `%rax`.
Do rozwiązania możemy wykorzystać operację `adc`, która normalnie dodaje wartości, jednak wykorzystuje ona jeszcze flagę przeniesienia `CF`. Więcej o tym [tutaj](https://stackoverflow.com/questions/4153852/assembly-adc-add-with-carry-to-c).
```=
addq %rsi, %rcx
adc %rdi, %rdx
movq %rcx, %rax
```
### Zadanie 6
Mnożenie liczb 128-bitowych. Wiemy, że $x = x_1 \cdot 2^{64} + x_0$ oraz $y = y_1 \cdot 2^{64} + y_0$. Wtedy $x*y = (x_1 \cdot 2^{64} + x_0)\cdot (y_1 * 2^{64} + y_0) = x_1\cdot y_1\cdot 2^{128} + (x_1\cdot y_0 + x_0\cdot y_1)\cdot 2^{64} + x_0\cdot y_0$. Wartość $x_1\cdot y_1\cdot 2^{128}$ jest za duża, aby ją pamiętać, więc nie musimy jej obliczać.
```=
mov %rdx, %rax
mul %rsi // x0 * y1
mov %rax, %r8
mov %rdi, %rax
mul %rcx // x1 * y0
add %rax, %r8
mov %rsi, %rax
mul %rcx // x0 * y0
add %r8, %rdx
```
### Zadanie 7
Implementacja procedury `addu(x, y)` zwracającej $\text{ULONG_MAX}$ dla $x+y\geq \text{ULONG_MAX}$ lub $x+y$ w przeciwnym wypadku. Zmienne `x` i `y` są typu `uint64_t`, przekazywane są w rejestrach `%rdi` oraz `%rsi`, wynik zwracany jest do `%rax`.
Możliwe rozwiązania:
* ze skokiem warunkowym sprawdzamy, czy dla sumy $x + y$ występuje overflow, a więc czy flaga `CF` zmieniła się na $1$. Jeżeli nie, to przeskakujemy wstawienie $\text{ULONG_MAX}$ do rejestru `%rdi`.
```=
add %rdi, %rsi
jae notoverf
mov $ULONG_MAX, %rdi
notoverf: mov %rdi, %rax
```
* bez skoku warunkowego mamy kilka sposobów: pierwszy z nich wykorzystuje instrukcję `cmovb` (move if below), wstawiamy wtedy $\text{ULONG_MAX}$ do `%rdi` tylko wtedy, gdy w działaniu $x+y$ dochodzi do nadmiaru (a więc `CF` jest zapalone). Drugim sposobem jest użycie instrukcji `cmovnc` (move if not carry), w tym przypadku wstawiamy sumę $x+y$ do rejestru `%rax` tylko wtedy, gdy `CF` jest zgaszone - omijamy użycie drugiego rejestru i zmniejszamy liczbę operacji. Trzeci sposób polega na użyciu instrukcji `sbb` (subtract with borrow) - suma $x+y$ ustawia flagę CF, a następnie wynikiem instrukcji `sbb %rax, %rax` będzie $\%rax = \%rax - (\%rax + CF)$, które może przyjąć wartość $0$ dla `CF` zgaszonego lub $-1$ w przeciwnym przypadku. W instrukcji `or %rdi, %rax` otrzymamy wtedy `or %rdi, $0` mające wartość `%rdi` lub `or %rdi, $-1`, które zwróci $\text{ULONG_MAX}$.
```=
add %rsi, %rdi
mov $-1, %r8
cmovb %r8, %rdi
mov %rdi, %rax
```
```=
movq $-1, %rax
addq %rsi, %rdi
cmovnc %rdi, %rax
```
```=
add %rsi, %rdi
sbb %rax, %rax ; z tego powstanie 0 lub -1
or %rdi, %rax
```
### Zadanie 8
Deasemblacja procedury `long decode(long x, long y)` daje kod przedstawiony poniżej, wiemy również, że `x` jest w rejestrze `%rdi`, a `y` w `%rsi`.
```=
decode: leaq (%rdi,%rsi), %rax
xorq %rax, %rdi
xorq %rax, %rsi
movq %rdi, %rax
andq %rsi, %rax
shrq $63, %rax
ret
```
Zadaniem jest napisanie funkcji w C, która będzie obliczać to samo co powyższy kod w asemblerze. Mamy więc:
```c=
long decode(long x, long y)
{
long w = x + y; // leaq (%rdi,%rsi), %rax
x = w ^ x; // xorq %rax, %rdi
y = w ^ y; // xorq %rax, %rsi
w = x & y; // movq %rdi, %rax
// andq %rsi, %rax
w = w >> 63; // shrq $63, %rax
return w; // ret
}
```
Zwięźlej możemy zapisać tę funkcję jako:
```c=
long decode(long x, long y)
{
return ((x ^ (x + y)) & (y ^ (x + y))) >> 63;
}
```
### Zadanie 9
Jak w zadaniu 8, mamy przedstawiony poniższy kod w asemblerze, a zadaniem jest napisanie funkcji `int puzzle(long x, unsigned n)` w C, zakładając, że dane `n` jest nie większe niż 64.
```=
puzzle: testl %esi, %esi # rownoznaczne z cmp %esi, 0
je .L4
xorl %edx, %edx
xorl %eax, %eax
.L3: movl %edi, %ecx
andl $1, %ecx
addl %ecx, %eax
sarq %rdi
incl %edx
cmpl %edx, %esi
jne .L3
ret
.L4: movl %esi, %eax
ret
```
Funkcja `puzzle` oblicza sumę $n$ mniej znaczących bitów liczby $x$.
```c=
int puzzle(long x, unsigned n)
{
if(n == 0)
return 0;
int sum = 0;
for (int i = 0; i != n; i++)
{
sum += x & 1;
x = x >> 1;
}
return sum;
}
```
## Lista zadań nr 5
### Zadanie 1
Implementacja w asemblerze x86-64 procedury `long cmp(uint64_t x, uint64_t y)`, która zwraca $-1$ dla $x < y$, $1$ dla $x > y$ oraz $0$ dla $x = y$. Zmienna `x` jest przechowywana w `%rdi`, a `y` w `%rsi`.
```=
subq %rsi, %rdi ; x := x - y, ustawienie flagi CF dla (x < y)
sbb %rax, %rax ; %rax - (%rax + CF)
neg %rdi ; x := -x, neg zapala CF dla liczb różnych od 0
adc %rax, %rax ; %rax + (%rax + CF)
ret
```
Rozpatrzmy więc przypadki na podstawie powyższego kodu:
1. $x > y$: `subq` nie ustawia `CF`, `sbb` ustawia `%rax` na $0$, `neg` ustawia `CF` na $1$, `adc` ustawia `%rax` na $1$.
2. $x < y$: `subq` ustawia `CF`, więc `sbb` ustawia `%rax` na $-1$, `neg` zapala `CF`, z `adc` mamy $-1 + (-1 + 1) = -1$.
3. $x = y$: `subq` nie ustawia `CF`, `sbb` ustawia `%rax` na $0$, `neg` nie ustawia `CF`, `adc` ustawia `%rax` na $0$.
### Zadanie 2
Przetłumaczenie kodu z assemblera na C, wyznaczenie bloków podstawowych i graf przepływu sterowania.
```=
puzzle2:
movq %rdi, %rax // B1
.L3: movb (%rax), %r9b // B2
leaq 1(%rax), %r8
movq %rsi, %rdx
.L2: movb (%rdx), %cl // B3
incq %rdx
testb %cl, %cl
je .L4
cmpb %cl, %r9b // B4
jne .L2
movq %r8, %rax // B5
jmp .L3
.L4: subq %rdi, %rax // B6
ret
```
```graphviz
digraph g {
START->B1;
B1->B2;
B2->B3;
B3->B6;
B3->B4;
B4->B3;
B4->B5;
B5->B2;
B6->END;
}
```
```C=
// char *t1 -> %r9b, char *t2 -> %r8, char *t3 -> %rdx, char t4 -> %cl
long puzzle2(char *s, char *d)
{
char *result = s;
while (true)
{
char t1 = *result;
char *t2 = result+1;
char *t3 = d;
char t4;
do
{
t4 = *t3;
t3++;
if (t4 == 0)
{
result -= s;
return (long)result;
}
} while (t1 != t4);
result = t2;
}
}
```
Funkcja `puzzle2` sprawdza długość najdłuższego prefixu s, w którym wszystkie elementy występują w słowie d.
### Zadanie 3
Podobnie jak w powyższym zadaniu.
```=
puzzle3:
movq %edi, %edi #B1
salq $32, %rsi
movl $32, %edx
movl $0x80000000, %ecx
xorl %eax, %eax
.L3: addq %rdi, %rdi #B2
movq %rdi, %r8
subq %rsi, %%r8
js .L2
orl %ecx, %eax #B3
movq %r8, %rdi
.L2: shrl %ecx #B4
decl %edx
jne .L3
ret #B5
```
```graphviz
digraph g{
START->B1;
B1->B2;
B2->B3;
B2->B4;
B3->B4;
B4->B2;
B4->B5;
B5->END;
}
```
```c=
uint32_t puzzle3(uint32_t n, uint32_t d)
{
int edi = ((n<<32)>>32);
long new_d = d<<32;
long new_n = n;
int edx = 32;
int ecx = 0x80000000;
int eax = 0;
do
{
new_n += new_n;
long r8 = n;
r8 -= new_d;
if(r8 >= 0)
{
eax |= ecx;
new_n = r8;
}
ecx >>= 1;
edx--;
} while (edx != 0)
return eax;
}
```
```c=
uint32_t puzzle3(uint32_t n, uint32_t d)
{
uint64_t nowe_d = d<<32;
uint64_t nowe_n = n;
uint32_t wyn = 0;
for(uint32_t mask = 0x80000000; mask > 0; mask >>= 1)
{
nowe_n *= 2;
if(nowe_n >= nowe_d)
{
wyn |= mask;
nowe_n -= nowe_d;
}
}
return wyn;
}
```
Funkcja liczy $\lfloor\frac{n}{d}\rfloor$ używając dzielenia pisemnego.
### Zadanie 4
Jak poprzednie zadania, jednak tu mamy do czynienia z procedurą rekurencyjną.
```=
puzzle4:
movq %rcx, %rax #B1
subq %rdx, %rax
shrq %rax
addq %rdx, %rax
cmpq %rdx, %rcx
jb .L5
movq (%rdi,%rax,8), %r8 #B2
cmpq %rsi, %r8
je .L10
cmpq %rsi, %r8 #B3
jg .L11
leaq 1(%rax), %rdx #B4
call puzzle4
.L10: ret #B10
.L11: leaq -1(%rax), %rcx #B11
call puzzle4
ret
.L5: movl $-1, %eax #B5
ret
```
```graphviz
digraph g{
L1 [label="B1\nmovq %rcx, %rax\nsubq %rdx, %rax\nshrq %rax\naddq %rdx, %rax\ncmpq %rdx, %rcx\njb .L5"]
L2 [label="B2\nmovq (%rdi,%rax,8), %r8\ncmpq %rsi, %r8\nje .L10"]
L3 [label="B3\ncmpq %rsi, %r8\njg .L11"]
L4 [label="B4\nleaq 1(%rax), %rdx\ncall puzzle4"]
L10 [label="B10\n.L10:\nret"]
L11 [label="B11\n.L11:\nleaq -1(%rax), %rcx\ncall puzzle4\nret"]
L5 [label="B5\n.L5:\nmovl $-1, %eax\nret"]
START
END
L1 -> L2
L2 -> L3
L3 -> L4
L1 -> L5
L2 -> L10
L3 -> L11
L4 -> L10
START -> L1
L5 -> END
L10 -> END
L11 -> END
}
```
```c=
int puzzle4(long *a, long v, uint64_t s, uint64_t e)
{
uint64_t pos = s + (e - s) / 2;
if(e < s)
return -1;
long mid = a[pos];
if(mid == v)
return pos;
if(mid > v)
e = pos-1;
else
s = pos+1;
return
puzzle4(a, v, s, e);
}
```
Funkcja `puzzle4` to wyszukiwanie binarne w tablicy.
### Zadanie 5
Zapisanie kodu w C jakiejś tam funkcji `switch_prob`.
```c=
long switch_prob(long x, long n)
{
switch(n)
{
case 60:
case 61:
return x * 8;
case 64:
return x >> 3;
case 62:
x *= 15;
case 65:
x *= x;
default:
return x + 75;
}
}
```
### Zadanie 6
Poniżej zamieszczono kod procedury o sygnaturze `struct T puzzle8(long *a,long n)`. Na jego podstawie podaj definicję typu `struct T`. Przetłumacz tę procedurę na język C, po czym jednym zdaniem powiedz co ona robi. Gdyby sygnatura procedury nie była wcześniej znana to jaką należałoby wywnioskować z poniższego kodu?
```c=
struct T {
long min, max, avg;
};
struct T puzzle8(long *a /* %rsi */, long n /* %rdx */) {
/* mamy ukryty pierwszy argument w %rdi - wskaźnik, gdzie umieścić wynik */
long max /* %r8 */ = LONG_MIN;
long min /* %r9 */ = LONG_MAX;
long sum /* %rax */ = 0;
for (long i /* %r10d */ = 0; i < n; i++) {
long ai = a[i];
sum += ai;
if (ai < min) min = ai;
if (ai > max) max = ai;
}
struct T result = { min, max, sum / n };
return result;
}
// wywnioskować moglibyśmy
// long* puzzle8(long*, int64_t*, uint64_t)
```
## Lista zadań nr 6
### Zadanie 1
A **stack frame** *(pol. rekord aktywacji)* is a frame of data that gets pushed onto the stack. In the case of a call stack, a stack frame would represent a function call and its argument data.
**Caller-saved registers** (AKA **volatile registers**, or **call-clobbered**) are used to hold temporary quantities that need not be preserved across calls. For that reason, it is the caller's responsibility to push these registers onto the stack or copy them somewhere else if it wants to restore this value after a procedure call. It's normal to let a `call` destroy temporary values in these registers, though.
**Callee-saved registers** (AKA **non-volatile registers**, or **call-preserved**) *(pol. rejestry zapisane przez funkcję wołaną)* are used to hold long-lived values that should be preserved across calls. When the caller makes a procedure call, it can expect that those registers will hold the same value after the callee returns, making it the responsibility of the callee to save them and restore them before returning to the caller. Or to not touch them.
```=
puzzle:
push %rbp
xorl %eax, %eax
mov %rsi, %rbp
push %rbx
mov %rdi, %rbx
sub $24, %rsp
test %rdi, %rdi
jle .L1
lea 8(%rsp), %rsi
lea (%rdi,%rdi), %rdi
call puzzle
add 8(%rsp), %rax
add %rax, %rbx
.L1: mov %rbx, (%rbp)
add $24, %rsp
pop %rbx
pop %rbp
ret
```
* Callee-saved registers: %rbx, %rbp
* Zmienne lokalne: tmp
* Adres powrotu: %rsp
|Rekord aktywacji|Rozmiar|
|----------------|-------|
|Adres powrotu | 8 |
|%rbp | 8 |
|%rbx | 8 |
|empty | 8 |
|tmp | 8 |
|empty | 8 |
```c=
long puzzle(long n, long *p)
{
long result = 0; //3
if(n > 0) //8, 9
{
long tmp; //10
result = puzzle(2*n, &tmp); //11, 12
result += tmp; //13
n += result; //14
}
*p = n; //15
return result; //19
}
```
### Zadanie 2
```=
000000000000066a <aframe>:
push %rbp
mov %rsp,%rbp
sub $0x10,%rsp
mov %fs:0x28,%rax
mov %rax,-0x8(%rbp)
xor %eax,%eax
lea 0x0(,%rdi,8),%r9
lea 0x1e(%r9),%rax
and $0xfffffffffffffff0,%rax
sub %rax,%rsp
lea 0xf(%rsp),%r8
and $0xfffffffffffffff0,%r8
mov %r8,%rcx
lea -0x10(%rbp),%rax
mov %rax,-0x8(%r8,%r9,1)
movq $0x0,-0x10(%rbp)
jmp 6bc <aframe+0x52>
mov %rdx,(%rcx,%rax,8)
addq $0x1,-0x10(%rbp)
mov -0x10(%rbp),%rax
cmp %rdi,%rax
jl 6b3 <aframe+0x49>
mov (%r8,%rsi,8),%rax
mov (%rax),%rax
mov -0x8(%rbp),%rsi
xor %fs:0x28,%rsi
jne 6dd <aframe+0x73>
leaveq
retq
callq 540 <__stack_chk_fail@plt>
```
Funkcja `alloca` alokuje pamięć, która jest zwalniana automatycznie. Jest to alokacja pamięci dla rekordu aktywacji dla funkcji wywołującej (caller). Ta pamięć tymczasowa jest zwalniana w momencie, gdy kończy się wywołana funkcja. `alloca` zwraca wartość początku zaalokowanej pamięci. Jeśli alokacja spowodowała by stack overflow to zachowanie programu jest niezdefiniowane. Pamięć nie jest zwalniana jeśli jest używana poza miejscem jej zaalokowania (poza funkcją/blokiem).
Miejsca, w których w kodzie maszynowym jest zrealizowany przydział/zwalnianie pamięci to po prostu miejsca, w których przesuwamy rejestr `%rsp` (dodajemy/odejmujemy od niego jakąś wartość). Ponadto tymi miejscami są wywołania instrukcji `push`/`pop` (przesuwanie `%rsp` o długość słowa maszynowego).
Funkcja `leave` przesuwa rejestr `%rsp` do `%rbp` (usuwa ramkę stosu), a następnie przywraca wartość `%rbp` z funkcji wołającej zdejmując tę wartość ze stosu.
### Zadanie 3
```asm=
puzzle5:
subq $24, %rsp
movq %rsp, %rdi
call readlong
leaq 8(%rsp), %rdi
call readlong
movq (%rsp), %rax
cqto
idivq 8(%rsp)
xorl %eax, %eax
testq %rdx, %rdx
sete %al
addq $24, %rsp
ret
```
|Stack frame |rozmiar|
|---------------------------------|-------|
|return address |8 |
|empty |8 |
|long (readlong z param. 8(%rsp)) |8 |
|long (readlong z param. %rsp) |8 |
```c=
void readlong(long *x);
long puzzle5(void){
long a, b;
readlong(&a);
readlong(&b);
return a%b == 0;
}
```
### Zadanie 4
`-mno-sse` wyłącza instrukcje SSE, czyli rejestry zmiennoprzecinkowe nie będą potrzebne.
```c=
typedef struct {
// offset następnego zapisanego rejestru do wczytania
unsigned int gp_offset;
unsigned int fp_offset;
// tu jest najwyższy niewczytany argument na stosie
void *overflow_arg_area;
// tu zapisujemy argumenty podane w rejestrach
void *reg_save_area;
} va_list[1];
```
```c=
/* dodaje n argumentów */
long puzzle7(long n, ...) {
va_list args;
va_start(args, n);
long result = 0;
for ( ; n > 0; n--) {
result += va_arg(args, long);
}
va_end(args);
return result;
}
```
Stack frame składa się (w kolejności pushowania) z adresu powrotu, argumentów `%r9`-`%rsi` i struktury `va_list`.
## Lista zadań nr 7
### Zadanie 1
Na podstawie kodu w C i odpowiadającego mu kodu w assemblerze należy wywnioskować wartość stałych $A$ i $B$.
```c=
typedef struct {
int x[A][B];
long y;
} str1;
typedef struct {
char array[B];
int t;
short s[A];
long u;
} str2;
void set_val(str1 *p, str2 *q) {
long v1 = q->t;
long v2 = q->u;
p->y = v1 + v2;
}
```
```asm=
set_val:
movslq 8(%rsi), %rax
addq 32(%rsi), %rax
movq %rax, 184(%rdi)
ret
```
Na podstawie instrukcji `movq %rax, 184(%rdi)` i `p->y = v1 + v2` możemy wywnioskować, że $4\cdot A\cdot B + x_1 = 184$, gdzie $x_1$ jest offsetem, aby `long y` było dopasowane w pamięci do 8 bajtów, a stąd mamy, że $177 < 4\cdot A\cdot B \leq 184$. Są to wszystkie informacje, jakie możemy uzyskać ze `struct str1`.
Rozpatrzmy teraz instrukcje `movslq 8(%rsi), %rax` oraz `long v1 = q->t` - stąd można łatwo wywnioskować, że $4 < B \leq 8$. Następnie rozpatrzmy `addq 32(%rsi), %rax` i `long v2 = q->u`. Pomocna nam będzie wiedza, że tablica `short s[A]` zajmuje w pamięci bajty od $12$ do $24$ oraz ewentualnie padding do $32$ bajtów. Uzyskujemy dzięki temu $5 < A \leq 12$.
Po podsumowaniu wszystkich informacji znalezione wartości stałych to $A=9, B=5$.
Możemy to sprawdzić podstawiając te wartości do struktur, a następnie porównać z instrukcjami assemblera:
* `int x[9][5]` zajmie $180$ bajtów, a więc `long y` rozpocznie się na $184.$ bajcie (przez padding), zgadza się to więc z instrukcją `movq %rax, 184(%rdi)`,
* `char array[5]` zajmie $5$ bajtów, a więc `int t` będzie od $8.$ bajtu - zgadza się to z instrukcją `movslq 8(%rsi), %rax`. Następnie mamy `short s[9]` zajmujące $18$ bajtów, po którym występuje `long u` rozpoczynające się na $32.$ bajcie - to również się zgadza z instrukcją `addq 32(%rsi), %rax`.
### Zadanie 2
Jak wyżej, musimy wywnioskować wartości stałych $R, S, T$.
```c=
long A[R][S][T];
long store_elem(long i, long j, long k, long *dest){
*dest = A[i][j][k];
return sizeof(A);
}
```
```=
store_elem:
leaq (%rsi,%rsi,2), %rax # %rax = 3j
leaq (%rsi,%rax,4), %rax # %rax = j + 12j = 13j
movq %rdi, %rsi # %rsi = i
salq $6, %rsi # %rsi = 2^6*i = 64i
addq %rsi, %rdi # %rdi = 65i
addq %rax, %rdi # %rdi = 65i + 13j
addq %rdi, %rdx # %rdx = 65i + 13j + k
movq A(,%rdx,8), %rax # %rax = A + 8 * (65i + 13j + k)
movq %rax, (%rcx) # %rax = *dest
movq $3640, %rax # %rax = sizeof(A)
ret
```
Bezpośrednio z kodu możemy wyciągnąć informacje na temat wielkości `long A[R][S][T]`, gdyż funkcja `store_elem` zwraca nam tę wartość - odpowiada temu assemblerowa instrukcja `movq $3640, %rax`. Skoro `A` zajmuje $3640$ bajtów, to przechowywane jest w niej $\frac{3640}{8} = 455$ wartości typu `long`.
Adres wartości przechowywanej w `A[i][j][k]` (tzn. `&A[i][j][k]`) jest równy
$A + (i\cdot S \cdot T \cdot 8 + j\cdot T \cdot 8 + k\cdot 8) = A + 8\cdot (i\cdot S \cdot T + j\cdot T + k)$, całe wyrażenie w nawiasie możemy podstawić do równania $(i\cdot S \cdot T + j\cdot T + k) = (65i + 13j + k)$, skąd uzyskamy $T=13$, a następnie z $i\cdot S \cdot T = 65i$ dostaniemy $S = 5$. Ostatnim krokiem jest odczytanie wartości $R = \frac{455}{5\cdot 13}=7$.
### Zadanie 3 TEGO NIE DEKLARUJE
Należy znaleźć wartość stałej $CNT$ oraz wywnioskować definicje struktury `a_struct`.
```c=
typedef struct {
int first;
a_struct a[CNT];
int last;
} b_struct;
void test (long i, b_struct *bp) {
int n = bp->first + bp->last;
a_struct *ap = &bp->a[i];
ap->x[ap->idx] = n;
}
```
```=
test:
movl 0x120(%rsi), %ecx # %ecx = *(%rsi+0x120) // n = bp->last
addl (%rsi), %ecx # %ecx = %ecx + *%rsi // n += bp->first
leaq (%rdi,%rdi,4), %rax # %rax = 5 * i
leaq (%rsi,%rax,8), %rax # %rax = %rsi + 8*5*i = %rsi + 40i
# tu %rax trzyma a_struct
movq 0x8(%rax), %rdx # %rdx = *(%rsi + 40i + 8)
movslq %ecx, %rcx # (int)(%rcx) czyli (int)n
movq %rcx, 0x10(%rax,%rdx,8) # *(8 * %rdx + %rax + 10) = n
retq
```
Z instrukcji funkcji `test` możemy wywnioskować, że definicją szukanej struktury jest
```c=
typedef struct {
int idx;
int x[];
} a_struct;
```
### Zadanie 4
Wyznaczenie rozmiaru unii `elem` oraz przepisanie procedury `proc` na kod w C.
```c=
union elem {
struct {
long *p; // wskaźnik: 8 bajtów
long y; // long: 8 bajtów
} e1; // cały struct e1: 16 bajtów
struct {
long x; // long: 8 bajtów
union elem *next; // wskaźnik: 8 bajtów
} e2; // cały struct e2: 16 bajtów
}; // unia elem: 16 bajtów
```
```=
proc: # union elem* proc2(union elem* arg)
movq 8(%rdi), %rax # union elem* result = arg->e2.next;
movq (%rax), %rdx # long *tempPtr = result->e1.p;
movq (%rdx), %rdx # long temp = *(tempPtr);
subq 8(%rax), %rdx # temp -= result->e1.y;
movq %rdx, (%rdi) # arg->e2.x = temp;
ret # return result;
```
Prześledźmy po kolei instrukcje i stwórzmy kod w C odpowiadający funkcji `proc`:
* `movq 8(%rdi), %rax` - stąd uzyskujemy informacje na temat typu funkcji oraz argumentu, jako że do `%rax` wysyłamy adres, to funkcja będzie typu `union elem*`, podobnie jak jej argument, a sama instrukcja odpowiada `union elem* result = arg->e2.next`
* `movq (%rax), %rdx` - odpowiada to instrukcji `long *tempPtr = result->e1.p`
* `movq (%rdx), %rdx` - `long temp = *(tempPtr);`, w assemblerowym kodzie linijki 3/4 odpowiadają instrukcji z linijki 13 w C.
Po assemblerowym kodzie możemy wywnioskować z którą strukturą pracujemy tylko przez to, czy odwołujemy się do wartości, czy adresów: zauważmy, że pierwszym elementem `struct e1` jest wskaźnik, a drugim wartość, a w `struct e2` jest odwrotnie.
```c=11
union elem* proc(union elem* arg){
union elem* result = arg->e2.next;
long temp = *(result->e1.p);
temp -= result->e1.y;
arg->e2.x = temp;
return result;
}
```
## Lista zadań nr 8
Bieżąca lista jest o reprezentacji programów, konsolidacji i ładowaniu, poniższe komendy przydadzą się do uzyskania plików potrzebnych w zadaniach.
* uzyskanie pliku assemblera `main.s` z pliku `main.c`:
```
$ gcc -s main.c
```
* uzyskanie pliku relokowalnego `main.o` z pliku `main.c` (z linkowaniem):
```
$ gcc -o main.o main.c
```
* uzyskanie plików wykonywalnych `a.out` lub `[nazwa]` z pliku `main.c`:
```
$ gcc main.c
$ gcc -Og -o nazwa main.c
```
* uzyskanie pliku `main.o` z pliku `main.c` bez linkowania:
```
$ gcc -c main.c
```
* wydruk tablicy symboli i nagłówków sesji:
```
$ readelf -t -s [nazwa].o
```
* deasemblacja sekcji z pliku relokowalnego:
```
$ objdump -d -j [nazwasekcji] [nazwa].o
```
### Zadanie 1
Należy wygenerować **plik relokowalny** `swap.o`, po czym na podstawie wydruku polecenia `readelf -t -s swap.o` dla każdego elementu tablicy symboli podać:
* adres symbolu względem początku sekcji (Value w `.symtab`),
* typ symbolu, tj. `local`, `global`, `extern` (Type oraz Bind),
* rozmiar danych, na które wskazuje symbol (Size),
* numer i nazwę sekcji, tj. `.text`, `.data`, .`bss`, do której odnosi się symbol (NDX w Section Headers).
Co przechowują sekcje `.strtab` oraz `.shstrtab`?
**Plik relokowalny** to plik generowany przez kompilator lub assembler podczas komplikacji pliku z kodem źródłowym, może on zostać również utworzony przez konsolidator w wyniku połączenia kilku plików relokowalnych. Są one przeznaczone do późniejszego przetwarzania przez konsolidator w celu uzyskania pliku wykonywalnego lub biblioteki dynamicznej. Mają one rozszerzenie `.o`, a generowane są poleceniem `gcc -o [nazwa].o [nazwa].c`.
Plik `swap.c`:
```c=
extern int buf[];
int *bufp0 = &buf[0];
static int *bufp1;
static void incr() {
static int count = 0;
count++;
}
void swap() {
int temp;
incr();
bufp1 = &buf[1];
temp = *bufp0;
*bufp0 = *bufp1;
*bufp1 = temp;
}
```
Wydruk polecenia `readelf -t -s swap.o`:
```
There are 9 section headers, starting at offset 0x1f8:
Section Headers:
[Nr] Name
Type Address Offset Link
Size EntSize Info Align
Flags
[ 0]
NULL NULL 0000000000000000 0000000000000000 0
0000000000000000 0000000000000000 0 0
[0000000000000000]:
[ 1] .text
PROGBITS PROGBITS 0000000000000000 0000000000000040 0
000000000000001e 0000000000000000 0 1
[0000000000000006]: ALLOC, EXEC
[ 2] .rela.text
RELA RELA 0000000000000000 0000000000000148 6
0000000000000060 0000000000000018 1 8
[0000000000000040]: INFO LINK
[ 3] .data
PROGBITS PROGBITS 0000000000000000 0000000000000060 0
0000000000000008 0000000000000000 0 8
[0000000000000003]: WRITE, ALLOC
[ 4] .rela.data
RELA RELA 0000000000000000 00000000000001a8 6
0000000000000018 0000000000000018 3 8
[0000000000000040]: INFO LINK
[ 5] .bss
NOBITS NOBITS 0000000000000000 0000000000000068 0
0000000000000004 0000000000000000 0 4
[0000000000000003]: WRITE, ALLOC
[ 6] .symtab
SYMTAB SYMTAB 0000000000000000 0000000000000068 7
00000000000000c0 0000000000000018 5 8
[0000000000000000]:
[ 7] .strtab
STRTAB STRTAB 0000000000000000 0000000000000128 0
000000000000001b 0000000000000000 0 1
[0000000000000000]:
[ 8] .shstrtab
STRTAB STRTAB 0000000000000000 00000000000001c0 0
0000000000000036 0000000000000000 0 1
[0000000000000000]:
```
Sekcje do których się będziemy odnosić są zapisane w kolumnie NDX, mają one numery 1, 3 oraz 5, są to:
* `.text` - kod programu
* `.data` - zainicjowane zmienne globalne
* `.bss` - niezainicjowane zmienne
```
Symbol table '.symtab' contains 8 entries:
Num: Value Size Type Bind Vis Ndx Name
0: 0000000000000000 0 NOTYPE LOCAL DEFAULT UND
1: 0000000000000000 0 SECTION LOCAL DEFAULT 5
2: 0000000000000000 4 OBJECT LOCAL DEFAULT 5 count.1960
3: 0000000000000000 0 SECTION LOCAL DEFAULT 1
4: 0000000000000000 0 SECTION LOCAL DEFAULT 3
5: 0000000000000000 30 FUNC GLOBAL DEFAULT 1 swap
6: 0000000000000000 8 OBJECT GLOBAL DEFAULT 3 bufp0
7: 0000000000000000 0 NOTYPE GLOBAL DEFAULT UND buf
[ADRES SYMBOLU] [ROZM][TYP I ZAKRES] [SEKCJA]
```
Sekcja `.strtab` (string table) przechowuje tablice stringów dla wszystkich referencji, tzn. stringi reprezentujące nazwy symboli. Sekcja `.shstrtab` (section header string table) przechowuje nazwy sekcji.
### Zadanie 2
Dlaczego po uruchomieniu program drukuje ciąg znaków i kończy działanie bez zgłoszenia błędu, skąd pochodzi ta wartość?
```c=
/* mismatch-a.c */
void p2(void); // symbol silny
int main() { // symbol silny
p2();
return 0;
}
```
```c=
/* mismatch-b.c */
#include <stdio.h>
char main; // symbol słaby
void p2() { // symbol silny
printf("0x%x\n", main);
}
```
Nie pokazuje się żaden błąd, gdyż linker wybiera zawsze silny symbol, tzn. w `mismatch-a.c` mamy zainicjowany `main` oraz jest on globalny, czyli jest silny, a w `mismatch-b.c` nie jest on zainicjowany, więc jest słaby.
Gdybyśmy chcieli przypisać wartość pod zmienną globalną `main` w pliku `mismatch-b.c`, to otrzymalibyśmy błąd `multiple definition of 'main'`, natomiast gdy chcemy przypisać wartość zmiennej `main` w ciele funkcji `p2`, to program skompiluje się poprawnie, jednak po uruchomieniu go otrzymamy `Segmentation fault`.
Wartość zwracana `0x50` jest pierwszą instrukcją w main, można to zobaczyć deasemblując program `mismatch` instrukcją:
```
$ gdb -batch -ex "disassemble/rs main" mismatch
```
Otrzymamy wtedy poniższy kod:
```
Dump of assembler code for function main:
0x000000000040158c <+0>: 50 push %rax
0x000000000040158d <+1>: e8 cb 05 00 00 callq 0x401b5d <p2>
0x0000000000401592 <+6>: 31 c0 xor %eax,%eax
0x0000000000401594 <+8>: 5a pop %rdx
0x0000000000401595 <+9>: c3 retq
End of assembler dump.
```
### Zadanie 3
Zapoznanie się znarzędziami `objdump`, `readelf` i `ar`. `objdump` jest programem analizującym pliki obiektowe (z rozszerzeniem `.o`), podobnie `readelf`, natomiast `ar` jest programem do obsługi archiwów.
Ile plików zawierają biblioteki `libc.a` oraz `libm.a` z katalogu `/usr/lib/x86_64-linux-gnu`?
Liczbę plików w bibliotekach można znaleźć za pomocą polecenia:
```
$ ar t /usr/lib/x86_64-linux-gnu/libc.a | wc -l
```
Flaga `t` dla programu `ar` odpowiada za wyświelenie zawartości archiwum, a `wc -l` liczy ilość linii. Jak widać na screenie poniżej, miałem problem z plikiem `limb.a`, więc w zamian odczytałem zawartość `libm-2.28.a`.
Czy wywołanie kompilatora z opcją `-Og` generuje inny kod wykonywalny niż `-Og -g`?
* Krótka odpowiedź: Tak, flaga `-Og` nie implikuje użycia flagi `-g`.
* Dłuższa odpowiedź: Flaga `-Og` służy do optymalizacji w trakcie debugowania, optymalizuje ona wszystko, co nie koliduje z debugowaniem, może być ona użyta wraz z flagą `-g` służącą do włączania symboli debugowania w GDB.
Więcej do poczytania tutaj:
https://gcc.gnu.org/onlinedocs/gcc/Debugging-Options.html
https://gcc.gnu.org/onlinedocs/gcc/Optimize-Options.html
Z jakich blibliotek współdzielonych korzysta interpreter języka Python (plik `/usr/bin/python`)?
Polecenie (będąc w /usr/bin):
```
$ readelf -d python
```
Flaga `-d` wyświetla sekcje dynamiczną (o ile istnieje), wywołanie powyżej przedstawionego polecenia wyświetla dość dużo informacji, nas jednak interesują linijki zawierające współdzielone biblioteki, a więc te oznaczone przez "shared library":
```
Dynamic section at offset 0x30dad0 contains 31 entries:
Tag Type Name/Value
0x0000000000000001 (NEEDED) Shared library: [libpthread.so.0]
0x0000000000000001 (NEEDED) Shared library: [libdl.so.2]
0x0000000000000001 (NEEDED) Shared library: [libutil.so.1]
0x0000000000000001 (NEEDED) Shared library: [libz.so.1]
0x0000000000000001 (NEEDED) Shared library: [libm.so.6]
0x0000000000000001 (NEEDED) Shared library: [libc.so.6]
0x000000000000000c (INIT) 0x4e000
0x000000000000000d (FINI) 0x1fd280
0x0000000000000019 (INIT_ARRAY) 0x30da10
0x000000000000001b (INIT_ARRAYSZ) 8 (bytes)
0x000000000000001a (FINI_ARRAY) 0x30da18
0x000000000000001c (FINI_ARRAYSZ) 8 (bytes)
0x000000006ffffef5 (GNU_HASH) 0x308
0x0000000000000005 (STRTAB) 0xc998
0x0000000000000006 (SYMTAB) 0x2c00
0x000000000000000a (STRSZ) 28128 (bytes)
0x000000000000000b (SYMENT) 24 (bytes)
0x0000000000000015 (DEBUG) 0x0
0x0000000000000003 (PLTGOT) 0x30f000
0x0000000000000002 (PLTRELSZ) 6960 (bytes)
0x0000000000000014 (PLTREL) RELA
0x0000000000000017 (JMPREL) 0x4b7e0
0x0000000000000007 (RELA) 0x145e0
0x0000000000000008 (RELASZ) 225792 (bytes)
0x0000000000000009 (RELAENT) 24 (bytes)
0x000000006ffffffb (FLAGS_1) Flags: PIE
0x000000006ffffffe (VERNEED) 0x144a0
0x000000006fffffff (VERNEEDNUM) 6
0x000000006ffffff0 (VERSYM) 0x13778
0x000000006ffffff9 (RELACOUNT) 9370
0x0000000000000000 (NULL) 0x0
```
### Zadanie 4
Rozważamy program składający się z dwóch plików źródłowych, jednak po uruchomieniu otrzymujemy błąd dostępu do pamięci (segmentation fault). Dlaczego to się dzieje, gdzie została umieszczona stała znakowa "Hello, world!"? Należy poprawić program - gdzie wtedy znajduje się ciąg znaków?
```c=
/* str-a.c */
#include <stdio.h>
char *somestr(void);
int main(void) {
char *s = somestr();
s[5] = '\0';
puts(s);
return 0;
}
```
```c=
/* str-b.c */
char *somestr(void) {
return "Hello, world!";
}
```
Na samym początku stała znakowa `"Hello, world!"` została umieszczona w sekcji `.rodata` (read-only data), a następnie przypisana do zmiennej `*s`. Błąd dostępu do pamięci występuje przy instrukcji `s[5] = '\0'`, jako że zmieniona miałaby zostać stała znakowa z sekcji `.rodata`, która może zostać tylko odczytana.
Po zmianie na wersję widoczną poniżej zmienna znakowa będzie przechowywana w sekcji `.data`, gdyż wartość przypisywana do zmiennej `char *s` będzie już zainicjalizowaną zmienną.
```c=
char *somestr(void) {
static char text[] = "Hello, world!";
return text;
}
```
### Zadanie 5
Po wpisaniu poleceń:
```
$ objdump -h bar.o
$ objdump -h foo.o
```
otrzymujemy poniższe informacje o rozmiarach sekcji `.data` oraz `.bss`:
| Plik | `.data` | `.bss` |
| ------- | ------- | ------ |
| `bar.o` | `0x4` | `0x1E` |
| `foo.o` | `0x8` | `0x11` |
Z wydruku poleceń
```
readelf -s -t bar.o
readelf -s -t foo.o
```
wyczytujemy, że wszystkie symbole mają offset `0`.
`bar` jest w `.data` i ma rozmiar `4`,
`dead` jest w `.bss` i ma rozmiar `30`,
`foo` jest w `.data` i ma rozmiar `17`,
`code` jest w `.bss` i ma rozmiar `8`.
Flaga `-fno-common` odnosi się do położenia niezainicjalizowanych zmiennych globalnych (symboli słabych). Powoduje ona, że te zmienne są alokowane w `.bss` zamiast w `COMMON`, więc tak samo nazwane zmienne w różnych plikach nie będą traktowane jako ten sam obiekt, tylko będzie dochodzić do błędu wielokrotnej definicji w czasie konsolidacji. Od GCC 10 `-fno-common` jest flagą domyślną.
**Częściowa konsolidacja** (ang. partial linking) to konsolidacja plików relokowalnych w plik relokowalny (służący do kolejnej konsolidacji) zamiast w plik wykonywalny/bibliotekę dynamiczną.
Podczas tworzenia `merge-1.o` linker otrzymuje `foo.o bar.o` w tej kolejności,
a podczas tworzenia `merge-2.o` otrzymuje `bar.o foo.o`.
Z `diff merge-1.map merge-2.map` wyczytujemy:
| | `merge-1.map` | `merge-2.map` |
|:---------------:|:-------------:|:-------------:|
| | | |
| Rozmiar `.data` | 0xc | 0x10 |
| Offset `bar` | 0x8 | 0x0 |
| Offset `foo` | 0x0 | 0x8 |
| | | |
| Rozmiar `.bss` | 0x3e | 0x31 |
| Offset `dead` | 0x20 | 0x0 |
| Offset `code` | 0x0 | 0x20 |
Sekcje mają swój alignment, co można wyczytać w `readelf -s -t` i dlatego otrzymujemy taki wynik.
### Zadanie 6
Plik wykonywalny powstały w wyniku kompilacji poniższych plików źródłowych powinien być nie dłuższy niż 1KiB. Na podstawie nagłówka pliku ELF wskaż w zdezasemblowanym pierwszą instrukcję, którą wykona procesor po wejściu do programu. Na podstawie nagłówków programu wskaż pod jaki adres wirtualny zostanie załadowany segment z sekcją `.text`. Zapoznaj się ze skryptem konsolidatora w pliku `main.lds`. Na podstawie [dokumentacji](https://sourceware.org/binutils/docs/ld/Scripts.html) wyjaśnij jak skrypt kieruje procesem konsolidacji poszczególnych sekcji i tworzeniem nagłówków programu.
```c=
/* start.c */
int is_even(long);
void _start(void) {
asm volatile(
"syscall"
: /* no output */
: "a" (0x3c), "D" (is_even(42)));
}
```
```c=
/* even.c */
int is_odd(long n);
int is_even(long n) {
if (n == 0)
return 1;
else
return is_odd(n - 1);
}
```
```c=
/* odd.c */
int is_even(long n);
int is_odd(long n) {
if (n == 0)
return 0;
else
return is_even(n - 1);
}
```
**Nagłówkiem pliku ELF** nazywamy pierwszą instrukcję wykonywaną przez procesor po wejściu do programu, otrzymujemy ją z poniższego polecenia w wierszu *Entry point address*:
```
$ readelf -h main
```
```
ELF Header:
Magic: 7f 45 4c 46 02 01 01 00 00 00 00 00 00 00 00 00
Class: ELF64
Data: 2's complement, little endian
Version: 1 (current)
OS/ABI: UNIX - System V
ABI Version: 0
Type: EXEC (Executable file)
Machine: Advanced Micro Devices X86-64
Version: 0x1
Entry point address: 0x401023
Start of program headers: 64 (bytes into file)
Start of section headers: 4472 (bytes into file)
Flags: 0x0
Size of this header: 64 (bytes)
Size of program headers: 56 (bytes)
Number of program headers: 3
Size of section headers: 64 (bytes)
Number of section headers: 6
Section header string table index: 5
```
**Nagłówkiem programu** nazywamy adres wirtualny, pod jakim zostanie załadowany segment z sekcją `.text`, otrzymujemy go z poniższego polecenia w wierszu *Section headers: .text, Address*:
```
$ readelf -S main
```
```
There are 6 section headers, starting at offset 0x1178:
Section Headers:
[Nr] Name Type Address Offset
Size EntSize Flags Link Info Align
[ 0] NULL 0000000000000000 00000000
0000000000000000 0000000000000000 0 0 0
[ 1] .note.gnu.propert NOTE 00000000004000e8 000000e8
0000000000000020 0000000000000000 A 0 0 8
[ 2] .text PROGBITS 0000000000401000 00001000
0000000000000039 0000000000000000 AX 0 0 1
[ 3] .symtab SYMTAB 0000000000000000 00001040
00000000000000d8 0000000000000018 4 3 8
[ 4] .strtab STRTAB 0000000000000000 00001118
0000000000000028 0000000000000000 0 0 1
[ 5] .shstrtab STRTAB 0000000000000000 00001140
0000000000000034 0000000000000000 0 0 1
```
**Skrypt konsolidatora `main.lds`** łączy poszczególne sekcje plików relokowalnych w jedną sekcje o tej samej nazwie. Nazwa segmentu jest na końcu każdej sekcji, po dwukropku.
### Zadanie 7
Na podstawie kilku paragrafów z *Computer Systems: A programmer's perspective* opowiedzieć jakie dane przechowują sekcje `.rel.text` oraz `.rel.data`. Czy możliwe jest, aby asembler utworzył sekcje `.rel.bss`? Czym się różnią relokacje typu `R_X86_64_PC32` od `R_X86_64_32`? Zreferuj algorytm relokacji.
**Relocation entries** to struktury danych w relokowalnych modułach obiektowych, których zadaniem jest poinformowanie konsolidatora jak zmodyfikować referencję do obiektu, którego lokalizacji nie zna, kiedy łączy plik obiektowy w plik wykonywalny.
Sekcja `.rel.text` przechowuje *relocation entries* dla kodu, czyli przechowuje tablice relokacji dla sekcji `.text`. Sekcja `.rel.data` przechowuje *relocation entries* dla danych. Czyli przechowuje tablicę relokacji dla danych, do których odwołujemy się w module.
Nie jest to możliwe, by asembler utworzył sekcję `.rel.bss`, ponieważ w sekcji `.bss` są niezainicjalizowane zmienne, czyli tak naprawdę `0`. Zatem linker nie przydzieli adresu takiej zmiennej, gdyż nie musi ona okupywać pamięci dysku.
Relokacja typu **R_X86_64_PC32** relokuje referencje do adresów, które są obliczane na podstawie przesunięcia aktualnej wartości PC o dany offset. A aktualna wartość PC to zawsze adres następnej instrukcji w pamięci, natomiast **R_X86_64_32** relokuje referencje do adresów, które są *absolutne*, czyli bierzemy *surowy* adres zakodowany w instrukcji i przekształcamy na efektywny bez modyfikowania go w żaden sposób.
Kod algorytmu relokacji:
```text=
// s to tablica bajtów
// r to struktura typu Elf64_rela zdefiniowana poniżej
foreach section s {
foreach relocation entry r {
refptr = s + r.offset; /* ptr to reference to be relocated */
/* Relocate a PC-relative reference */
if (r.type == R_X86_64_PC32) {
refaddr = ADDR(s) + r.offset; /* ref’s run-time address */
*refptr = (unsigned) (ADDR(r.symbol) + r.addend - refaddr);
}
/* Relocate an absolute reference */
if (r.type == R_X86_64_32)
*refptr = (unsigned) (ADDR(r.symbol) + r.addend);
}
}
```
```c=
typedef struct {
long offset; /* Offset of the reference to relocate */
long type:32, /* Relocation type */
symbol:32; /* Symbol table index */
long addend; /* Constant part of relocation expression */
} Elf64_Rela;
```
Ponadto zakładamy, że podczas algorytmu linker już wybrał adresy dla każdej sekcji `(ADDR(s))` i każdego symbolu `(ADDR(r.symbol))`.
Algorytm relokacji:
* dla każdej sekcji s patrzymy na jej *relocation entry* `r` i obliczamy adres referencji do zrelokowania (linie 1,2)
* obliczamy adres w tablicy `s` dla każdej 4-bajtowej referencji, która porzebuje alokacji (linia 3)
* jeśli adres jest PC-relative to dodajemy do niego offset i relokujemy (linie 5-9)
* w przeciwnym wypadku jeśli adres jest ostateczny, to po prostu relokujemy go (linie 11-13)
### Zadanie 8
Na podstawie wydruku polecenia `objdump -r -d` wskaż w kodzie źródłowym z zadania 6 miejsca występowania relokacji. Następnie pokaż jak relokacje zostały wypełnione w pliku wykonywalnym. Wydrukuj tabele relokacji poszczególnych plików konsolidowalnych, a także fragment mapy konsolidacji opisujący złączoną sekcję `.text`. Następnie oblicz wartości, które należy wpisać w miejsce relokacji, zgodniez algorytmem z poprzedniego zadania.
**Relokacja** to proces polegający na łączeniu modułów wejściowych i nadawaniu adresów wykonania wszystkim symbolom. Przebiega on w dwóch krokach: relokacja sekcji i definicji symboli a następnie relokacja referencji do innych symboli.
```
$ objdump -r -d start.o even.o odd.o
```
```text=
0000000000000000 <_start>:
0: 48 83 ec 08 sub $0x8,%rsp
4: bf 2a 00 00 00 mov $0x2a,%edi
9: e8 00 00 00 00 callq e <_start+0xe> # relokacja
a: R_X86_64_PC32 is_even-0x4
e: 89 c7 mov %eax,%edi
10: b8 3c 00 00 00 mov $0x3c,%eax
15: 0f 05 syscall
17: 48 83 c4 08 add $0x8,%rsp
1b: c3 retq
0000000000000000 <is_even>:
0: 48 85 ff test %rdi,%rdi
3: 75 06 jne b <is_even+0xb>
5: b8 01 00 00 00 mov $0x1,%eax
a: c3 retq
b: 48 83 ec 08 sub $0x8,%rsp
f: 48 83 ef 01 sub $0x1,%rdi
13: e8 00 00 00 00 callq 18 <is_even+0x18> # relokacja
14: R_X86_64_PC32 is_odd-0x4
18: 48 83 c4 08 add $0x8,%rsp
1c: c3 retq
0000000000000000 <is_odd>:
0: 48 85 ff test %rdi,%rdi
3: 75 06 jne b <is_odd+0xb>
5: b8 00 00 00 00 mov $0x0,%eax
a: c3 retq
b: 48 83 ec 08 sub $0x8,%rsp
f: 48 83 ef 01 sub $0x1,%rdi
13: e8 00 00 00 00 callq 18 <is_odd+0x18> # relokacja
14: R_X86_64_PC32 is_even-0x4
18: 48 83 c4 08 add $0x8,%rsp
1c: c3 retq
```
```
$ objdump -r -d main
```
```text=
00000000004000e8 <.text>:
4000e8: 48 85 ff test %rdi,%rdi
4000eb: 75 06 jne 0x4000f3
4000ed: b8 01 00 00 00 mov $0x1,%eax
4000f2: c3 retq
4000f3: 48 83 ec 08 sub $0x8,%rsp
4000f7: 48 83 ef 01 sub $0x1,%rdi
4000fb: e8 05 00 00 00 callq 0x400105 # wypełniona relokacja z is_even
400100: 48 83 c4 08 add $0x8,%rsp
400104: c3 retq
400105: 48 85 ff test %rdi,%rdi
400108: 75 06 jne 0x400110
40010a: b8 00 00 00 00 mov $0x0,%eax
40010f: c3 retq
400110: 48 83 ec 08 sub $0x8,%rsp
400114: 48 83 ef 01 sub $0x1,%rdi
400118: e8 cb ff ff ff callq 0x4000e8 # wypełniona relokacja z is_odd
40011d: 48 83 c4 08 add $0x8,%rsp
400121: c3 retq
400122: 48 83 ec 08 sub $0x8,%rsp
400126: bf 2a 00 00 00 mov $0x2a,%edi
40012b: e8 b8 ff ff ff callq 0x4000e8 # wypełniona relokacja z procedury _start
400130: 89 c7 mov %eax,%edi
400132: b8 3c 00 00 00 mov $0x3c,%eax
400137: 0f 05 syscall
400139: 48 83 c4 08 add $0x8,%rsp
40013d: c3 retq
```
```
$ readelf -r start.o even.o odd.o
```
```text=
File: start.o
Relocation section '.rela.text' at offset 0x158 contains 1 entry:
Offset Info Type Sym. Value Sym. Name + Addend
00000000000a 000700000002 R_X86_64_PC32 0000000000000000 is_even - 4
File: even.o
Relocation section '.rela.text' at offset 0x158 contains 1 entry:
Offset Info Type Sym. Value Sym. Name + Addend
000000000014 000700000002 R_X86_64_PC32 0000000000000000 is_odd - 4
File: odd.o
Relocation section '.rela.text' at offset 0x158 contains 1 entry:
Offset Info Type Sym. Value Sym. Name + Addend
000000000014 000700000002 R_X86_64_PC32 0000000000000000 is_even - 4
```
```
$ cat main.map
```
```text=
Name Origin Length Attributes
.text 0x00000000004000e8 0x56
(.text .text.)
.text 0x00000000004000e8 0x1d even.o
0x00000000004000e8 is_even
.text 0x0000000000400105 0x1d odd.o
0x0000000000400105 is_odd
.text 0x0000000000400122 0x1c start.o
0x0000000000400122 _start
```
Obliczenia dla wypełniania relokacji z `is_even`:
```text=
r.offset = 0x14
r.symbol = is_odd
r.type = R_X86_64_PC32
r.addend = -0x4
ADDR(s) = ADDR(.text) = 0x4000e8
ADDR(r.symbol) = ADDR(is_odd) = 0x400105
refaddr = ADDR(s) + r.offset = 0x4000e8 + 0x14 = 0x4000fc
*refptr = (unsigned) (ADDR(r.symbol) + r.addend - refaddr) =
= (unsigned) (0x400105 + (-0x4) - 0x4000fc) =
= (unsigned) (0x05)
```
Obliczenia dla wypełniania relokacji z `is_odd`:
```text=
r.offset = 0xa
r.symbol = is_even
r.type = R_X86_64_PC32
r.addend = -0x4
ADDR(s) = ADDR(.text) = 0x400105
ADDR(r.symbol) = ADDR(is_even) = 0x4000e8
refaddr = ADDR(s) + r.offset = 0x400105 + 0x14 = 0x400119
*refptr = (unsigned) (ADDR(r.symbol) + r.addend - refaddr) =
= (unsigned) (0x4000e8 + (-0x4) - 0x400119) =
= (unsigned) (-0x35)
```
Obliczenia dla wypełniania relokacji z `_start`:
```text=
r.offset = 0xa
r.symbol = is_even
r.type = R_X86_64_PC32
r.addend = -0x4
ADDR(s) = ADDR(.text) = 0x400122
ADDR(r.symbol) = ADDR(is_even) = 0x4000e8
refaddr = ADDR(s) + r.offset = 0x400122 + 0xa = 0x40012C
*refptr = (unsigned) (ADDR(r.symbol) + r.addend - refaddr) =
= (unsigned) (0x4000e8 + (-0x4) - 0x40012C) =
= (unsigned) (-0x48)
```
## Lista zadań nr 9
### Zadanie 1
W trakcie tłumaczenia kodu z C na asembler kompilator umieścił tablicę skoków dla instrukcji przełączania w sekcji `.rodata`. Dla sekcji `.text` oraz `.rodata` należy określić gdzie znajdują się relokacje, a następnie podać zawartość tablicy relokacji `.rela.text` i `.rela.rodata`, tzn. listę rekordów składających się z przesunięcia relokacji względem początku sekcji, typu relokacji oraz nazwy symbolu i przesunięcia względem początku symbolu. W wyniku konsolidacji pliku wykonywalnego zawierającego procedurę `relo3`, została ona umieszczona pod adresem `0x1000`, a tablica skoków pod `0x2000`. Obliczyć wartości, które należy wstawić w miejsca relokacji.
```c=
/* relo3.c */
int relo3(int val) {
switch (val) {
case 100:
return val;
case 101:
return val + 1;
case 103:
case 104:
return val + 3;
case 105:
return val + 5;
default:
return val + 6;
}
}
```
```
0000000000000000 <relo3>:
0: 8d 47 9c lea -0x64(%rdi), %eax
3: 83 f8 05 cmp $0x5, %eax
6: 77 15 ja 1d <relo3+0x1d>
8: 89 c0 mov %eax, %eax
a: ff 24 c5 00 00 00 00 jmpq *0x0(,%rax,8)
11: 8d 47 01 lea 0x1(%rdi), %eax
14: c3 retq
15: 8d 47 03 lea 0x3(%rdi), %eax
18: c3 retq
19: 8d 47 05 lea 0x5(%rdi), %eax
1c: c3 retq
1d: 8d 47 06 lea 0x6(%rdi), %eax
20: c3 retq
21: 89 f8 mov %edi,%eax
23: c3 retq
```
Relokacje znajdziemy używając pierwszego polecenia, a zawartość tablicy relokacji drugim lub trzecim:
```
$ objdump -r -D relo3.o
$ readelf -r relo3.o
$ objdump -r relo3.o
```
```
relo3.o: file format elf64-x86-64
Disassembly of section .text:
0000000000000000 <relo3>:
0: 8d 57 9c lea -0x64(%rdi),%edx
3: 89 f8 mov %edi,%eax
5: 83 fa 05 cmp $0x5,%edx
8: 77 11 ja 1b <relo3+0x1b>
a: ff 24 d5 00 00 00 00 jmpq *0x0(,%rdx,8)
d: R_X86_64_32S .rodata
11: 83 c0 03 add $0x3,%eax
14: c3 retq
15: b8 6e 00 00 00 mov $0x6e,%eax
1a: c3 retq
1b: 83 c0 06 add $0x6,%eax
1e: c3 retq
1f: b8 66 00 00 00 mov $0x66,%eax
24: c3 retq
Disassembly of section .rodata:
0000000000000000 <.rodata>:
...
0: R_X86_64_64 .text+0x24
8: R_X86_64_64 .text+0x1f
10: R_X86_64_64 .text+0x1b
18: R_X86_64_64 .text+0x11
20: R_X86_64_64 .text+0x11
28: R_X86_64_64 .text+0x15
```
```
RELOCATION RECORDS FOR [.text]:
OFFSET TYPE VALUE
000000000000000d R_X86_64_32S .rodata
RELOCATION RECORDS FOR [.rodata]:
OFFSET TYPE VALUE
0000000000000000 R_X86_64_64 .text+0x0000000000000024
0000000000000008 R_X86_64_64 .text+0x000000000000001f
0000000000000010 R_X86_64_64 .text+0x000000000000001b
0000000000000018 R_X86_64_64 .text+0x0000000000000011
0000000000000020 R_X86_64_64 .text+0x0000000000000011
0000000000000028 R_X86_64_64 .text+0x0000000000000015
```
Relokacje dla `relo3`:
```
ADDR(r.symbol)=0x2000
r.addend=0x0
*refptr = (unsigned) (ADDR(r.symbol) + r.addend) =
= (unsigned) (0x2000 + 0x0) = (unsigned) (0x2000)
```
Relokacje dla `.rodata`:
```
ADDR(r.symbol)=0x1000
r.addend=0x21
*refptr = (unsigned) (ADDR(r.symbol) + r.addend) =
= (unsigned) (0x1000 + 0x21) = (unsigned) (0x1021)
r.addend=0x11
*refptr = (unsigned) (ADDR(r.symbol) + r.addend) =
= (unsigned) (0x1000 + 0x11) = (unsigned) (0x1011)
r.addend=0x1d
*refptr = (unsigned) (ADDR(r.symbol) + r.addend) =
= (unsigned) (0x1000 + 0x1d) = (unsigned) (0x101d)
r.addend=0x15
*refptr = (unsigned) (ADDR(r.symbol) + r.addend) =
= (unsigned) (0x1000 + 0x15) = (unsigned) (0x1015)
r.addend=0x15
*refptr = (unsigned) (ADDR(r.symbol) + r.addend) =
= (unsigned) (0x1000 + 0x15) = (unsigned) (0x1015)
r.addend=0x19
*refptr = (unsigned) (ADDR(r.symbol) + r.addend) =
= (unsigned) (0x1000 + 0x19) = (unsigned) (0x1019)
```
### Zadanie 2
Język C++ pozwala na przeciążanie funkcji (ang. function overloading), tj. dopuszcza stosowanie wielu funkcji o tej samej nazwie, ale różnej sygnaturze. Wiemy, że konsolidator nie przechowuje w tabeli symboli informacji o typach z języka programowania. Powstaje zatem problem unikatowej reprezentacji nazw używanych przez język C++. Wytłumacz na czym polega **dekorowanie nazw** (ang. name mangling)? Które elementy składni podlegają dekorowaniu?
**Dekorowanie nazw** służy do tego, aby odróżnić implementację różnych funkcji (o różnych sygnaturach) mających taką samą nazwę. Jest to oczywiście potrzebne w C++, ponieważ możemy przeciążać funkcje. Funkcja dekorująca jest różnowartościowa.
W `Intel C++ 8.0 for Linux` udekorowane symbole zaczynają się od `_Z`.
Następnie mamy literę `N` mówiącą o tym, czy mamy jakieś `namespace`'y, czy nie.
1. Jeśli nie ma `N` to od razu po `Z` kodujemy nazwę podając najpierw liczbę liter wchodzących w skład nazwy, a następnie pełną nazwę.
2. Jeśli jest `N` to podajemy kolejne `namespace`'y na tej samej zasadzie co powyżej a po podaniu nazwy funkcji mamy literę `E`.
Następnie przechodzimy do argumentów funkcji. Tutaj mamy:
1. `P` oznacza `*`
2. `K` oznacza `const`
3. `R` oznacza `&`
4. `i` oznacza `int`, podobnie `d` oznacza `double` itd.
Przykłady z zadania:
- `_Z4funcPKcRi` $\rightarrow$ `func(char const*, int&)`
Ten przykład jest omówiony powyżej.
- `_ZN3Bar3bazEPc` $\rightarrow$ `Bar::baz(char*)`
Ten przykład również mieści się w opisie powyżej.
- `_ZN3BarC1ERKS_` $\rightarrow$ `Bar::Bar(Bar const&)`
`C1` mówi nam o tym, że jest to konstruktor (analogicznie `D1` dałoby destruktor `~Bar`),
`S_` to typ pierwszego argumentu. Typy kolejnych argumentów są kodowane `S0_`, `S1_` itd.
- `_ZN3foo6strlenER6string` $\rightarrow$ `foo::strlen(string&)`
Ten przykład ma nietypowy typ argumentu, ponieważ nie jest to typ prosty, lecz złożony `string`. Stąd trzeba było użyć notacji takiej, w której najpierw podajemy długość nazwy typu, a potem nazwę.
### Zadanie 3
Podglądając wyjście z kompilatora języka C pokaż jak korzystając dyrektyw asemblera opisanych w [GNU as: Assembler Directives](https://github.com/hjl-tools/x86-psABI/wiki/x86-64-psABI-1.0.pdf):
- zdefiniować globalną funkcję foobar,
- zdefiniować lokalną strukturę podaną niżej:
```c=
static const struct {
char a[3];
int b;
long c;
float pi;
} baz = { "abc", 42, -3, 1.4142 };
```
- zarezerwować miejsce dla tablicy long array[100].
Wyjaśnij znaczenie poszczególnych dyrektyw. Pamiętaj, że dla każdego zdefiniowanego symbolu należy uzupełnić odpowiednio tabelę `.symtab` o typ symbolu i rozmiar danych, do których odnosi się symbol.
**Dyrektywa asemblera** (assembler directive, pseudo-op) to fraza w języku asemblera, która określa działanie asemblera i nie tłumaczy się bezpośrednio na kod maszynowy. Pozwalają m. in. definiować stałe, oddzielać sekcje, używać makr. Pełnią funkcję podobną do `pragma` spotykanej w wielu językach, zwykle zaczynają się kropką.
Kompilujemy kod C do kodu assemblera używając `gcc -S -fverbose-asm`. Globalną funkcję `foobar` definiujemy w następujący sposób, podobnie do tych, które wystąpiły na listach zadań programistycznych z assemblera:
```=
.text
.globl foobar
.type foobar, @function
foobar:
# cialo funkcji
ret
.size foobar, .-foobar
```
W wyrazie `.-foobar` kropka oznacza obecny adres, a `-` odejmowanie, a więc uzyskujemy dzięki temu rozmiar funkcji.
Lokalną strukturę definiujemy następująco:
```
.section .rodata
.align 16
.type baz, @object
.size baz, 24
baz:
.ascii "abc" # a
.zero 1 # padding
.long 42 # b
.quad -3 # c
.long 1068827777 # pi
.zero 4 # padding
```
Miejsce dla tablicy `long array[100]` rezerwujemy poprzez dodanie symbolu w common o rozmiarze `800` (`100 * long`) i alignie `32`:
```
.comm array,800,32
```
Google Drive
Gist
Clipboard
Sign in with Wallet
