# ASK 2020 GR. Kraski cz II
### Zadanie 6, lista 8
:::info
**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 zdeasemblowanym 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».
```cpp=
/* start.c */
int is_even(long);
void _start(void) {
asm volatile(
"syscall"
: /* no output */
: "a" (0x3c /* exit */),
"D" (is_even(42)));
}
```
```cpp=
/* even.c */
int is_odd(long n);
int is_even(long n)
if (n == 0)
return 1;
else
return is_odd(n - 1);
}
```
```cpp=
/* odd.c */
int is_even(long n);
int is_odd(long n) {
if (n == 0)
return 0;
else
return is_even(n - 1);
}
```
Zapoznaj się ze **skryptem konsolidatora** w pliku «main.lds». Na podstawie dokumentacji wyjaśnij jak skrypt kieruje procesem konsolidacji poszczególnych sekcji i tworzeniem nagłówków programu.
:::
**plik wykonywalny** - zawiera kod i dane w formacie pozwalającym na bezpośrednie skopiowanie do pamięci i uruchomienie
**nagłówek pliku ELF** - zawiera podstawowe informacje dot. pliku takie jak: sposób zapisu danych (np. U2, little endian), typ pliku (np. relokowalny), entry point address itd.; sprawdzamy poleceniem ```readelf -h nazwa```
```readelf -h main```
```objdump -r -d main```
pierwsza instrukcja: sub $0x8,%rsp
**nagłówek programu** - część pliku ELF, która dla danego segmentu przechowuje informacje takie jak np. offset od początku pliku, adres wirtualny, rozmiar itd.; sprawdzamy poleceniem ```readelf -l nazwa```
```readelf -l main```
0x00000000004000e8
**Konsolidator** jest programem mającym za zadanie łączenie kilku plików obiektowych, realokacje zmiennych oraz powiązanie ze sobą referencji symboli w jednym pliku obiektowym.
**skrypt konsolidatora** - plik skryptu konsolidatora jest zwykłym plikiem tekstowy w którym znajduje się zestaw komend. Każda komenda jest słowem kluczowym po którym może nastąpić argument, lub wartość której można przypisać do zmiennej.
«main.lds»
```C=
UTPUT_FORMAT("elf64-x86-64") //nazywa format pliku wyjsciowego
OUTPUT_ARCH(i386:x86-64)
ENTRY(_start) //ustawia punkt wejscia;
PHDRS //zarządza ustawieniem nagłówków
{
code PT_LOAD FLAGS(5);
rodata PT_LOAD FLAGS(4);
data PT_LOAD FLAGS(6);
}
SECTIONS
{
. = 0x400000 + SIZEOF_HEADERS; /* sets the value of the special symbol ‘.’,
which is the location counter (licznik lokacji). If you do not specify
the address of an output section in some other way, the address is set
from the current value of the location counter. The location counter
is then incremented by the size of the output section. At the start of
the ‘SECTIONS’ command, the location counter has the value ‘0’. */
//The ‘*’ is a wildcard which matches any file name.
//The expression ‘*(.text)’ means all ‘.text’ input
//sections in all input files.
.text :
{
*(.text .text.*)
} : code //output
.rodata :
{
*(.rodata .rodata.*)
} : rodata
.data :
{
*(.data .data.*)
} : data
.bss :
{
*(.bss .bss.*)
*(COMMON) //*(COMMON) by itself refers to all uninitialized data from all input files
} : data
/DISCARD/ : //The special output section name ‘/DISCARD/’ may be used to discard input sections. Any input sections which are assigned to an output section named ‘/DISCARD/’ are not included in the output file.
{
*(.note.gnu.property)
}
}
```
### Zadanie 7, lista 8
:::info
Na podstawie [1, §7.7.1] opowiedz jakie dane przechowują sekcje «.rel.text» i «.rel.data». Czy możliwe jest by asembler utworzył sekcję «.rel.bss»? Czym się różnią relokacje typu «R_X86_64_PC32» od «R_X86_64_32»? Na podstawie [1, §7.7.2] podręcznika zreferuj algorytm relokacji.
:::
.rel.text - wpisy relokacji dla kodu (uzupelnic kod)
.rel.data - wpisy relokacji dla danych (uzupelnienie danych)
.rel.bss nie powinno sie wygenerowac, ale istnieje mozliwosc stworzenia takiej sekcji np. po przez wstawienie kodu ktory odwoluje sie do jakiegos symbolu w sekcji bss (ta sekcja nie powinna trzymac instrukcji, od tego jest .text)
(https://stackoverflow.com/questions/37055896/what-does-an-elf-relocation-in-bss-but-relative-to-bss-mean)
«R_X86_64_PC32» - uzupelniamy adres wzgledem naszego adresu np. +5 albo -5
«R_X86_64_32» - uzupelniamy adres poprzez wstawienie bezwzglednej wartosci adresu
Algorytm relokacji:
```=c
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);
}
}
```
przechodzimy kolejno po kazdej sekcji i dla kazdego wpisu relokacji wyliczamy wartosc adresu na podstawie typu relokacji.
Powyzszy algorytm uwzglednia jedynie dwa najczestsze typy («R_X86_64_PC32» i «R_X86_64_32»)
W pierwszym przypadku wyliczany zostaje adres wzgledem adresu sekcji i miejsca w ktorym jest wpis relokacji w tej sekcji
W drugim nie obchodzi nas adres wzgledem obecnej instrukcji wiec ten krok jest pominiety
### Zadanie 8, lista 8
:::info
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, zgodnie z algorytmem z poprzedniego zadania.
:::
```
$ readelf -r --relocs start.o
Relocation section '.rela.text' at offset 0x150 contains 1 entry:
Offset Info Type Sym. Value Sym. Name + Addend
00000000000a 000700000004 R_X86_64_PC32 0000000000000000 is_even - 4
```
objdump -> a: R_X86_64_PC32 is_even-0x4
```
$ readelf -r --relocs even.o
Relocation section '.rela.text' at offset 0x150 contains 1 entry:
Offset Info Type Sym. Value Sym. Name + Addend
000000000014 000700000004 R_X86_64_PC32 0000000000000000 is_odd - 4
```
objdump -> 14: R_X86_64_PC32 is_odd-0x4
```
$ readelf -r --relocs odd.o
Relocation section '.rela.text' at offset 0x150 contains 1 entry:
Offset Info Type Sym. Value Sym. Name + Addend
000000000014 000700000004 R_X86_64_PC32 0000000000000000 is_even - 4
```
objdump -> 14: R_X86_64_PC32 is_even-0x4
fragment mapy konsolidacji:
```
.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
```
I w koncu relokacje uzupelnione przez konsolidator (widac przy instrukcjach callq) :
```
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
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
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
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
```
Obliczamy odpowiednie wartosci:
ADDR(.text) = 0x4000e8
ADDR(is_even) = 0x4000e8
ADDR(is_odd) = 0x400105
ADDR(_start) = 0x400122
Dla wpisu relokacji w start.o:
refaddr = ADDR(.text) + r.offset = 0x4000e8 + a = 0x4000f2
*refptr = (unsigned) (ADDR(is_even) + (-4) - refaddr) = (unsigned) (-e)
Dla wpisu relokacji w even.o:
refaddr = ADDR(.text) + r.offset = 0x4000e8 + 0x14 = 0x4000fc
*refptr = (unsigned) (ADDR(is_odd) + (-4) - refaddr) = 0x400105 - 0x4 - 0x4000fc = 5
Dla wpisu relokacji w odd.o:
refaddr = ADDR(.text) + r.offset =0x4000e8 + 0x14 = 0x4000fc
*refptr = (unsigned) (ADDR(is_even) + (-4) - refaddr) = 0x4000e8 - 0x4 - 0x4000fc = (unsigned) (-18)
# Lista 9
### Zadanie 1
:::info
W trakcie tłumaczenia poniższego kodu na asembler kompilator umieścił tablicę skoków dla instrukcji przełączania w sekcji «.rodata».
```cpp=
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
```
Dla sekcji «.text» i «.rodata» określ pod jakimi miejscami znajdują się relokacje, a następnie podaj zawartość tablicy relokacji «.rela.text» i «.rela.rodata», tj. listę rekordów składających się z:
• przesunięcia relokacji względem początku sekcji,
• typu relokacji,
• 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. Oblicz wartości, które należy wstawić w miejsca relokacji.
:::
*readelf -r relo3.o* daje nam następujące informacje:
```=
Relocation section '.rela.text' at offset 0x130 contains 1 entry:
Offset Info Type Sym. Value Sym. Name + Addend
00000000000d 00020000000b R_X86_64_32S 0000000000000000 .rodata + 0
Relocation section '.rela.rodata' at offset 0x148 contains 6 entries:
Offset Info Type Sym. Value Sym. Name + Addend
000000000000 000100000001 R_X86_64_64 0000000000000000 .text + 24
000000000008 000100000001 R_X86_64_64 0000000000000000 .text + 1f
000000000010 000100000001 R_X86_64_64 0000000000000000 .text + 1b
000000000018 000100000001 R_X86_64_64 0000000000000000 .text + 11
000000000020 000100000001 R_X86_64_64 0000000000000000 .text + 11
000000000028 000100000001 R_X86_64_64 0000000000000000 .text + 15
```
Powyższy wydruk daje nam w zasadzie wystarczające informacje do obliczenia wartości relokacji, ale dla jasności można jeszcze spojrzeć na wydruk *objdump -r -D 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
```
Tak więc relokacje znajdują się:
* 1 w sekcji .text (w linii ```a: ff 24 d5 00 00 00 00 jmpq *0x0(,%rdx,8)```)
* 6 w sekcji .rodata (nasza tablica skoków)
Procedura relo3 została umieszczona pod adresem 0x1000, czyli adres sekcji .text z relo3.o też ma adres 0x1000. Adres tablicy skoków (czyli również początku sekcji .rodata z relo3.o) wynosi 0x2000.
Najpierw obliczmy adres z sekcji .text:
1. refptr = 0x1000 + 0xD; *refptr = (unsigned) (0x2000)
Teraz adresy z sekcji .rodata:
1. refptr = 0x2000 + 0x0 = 0x2000; *refptr = (un.) (0x1000 + 24 + 0) = 0x1024
2. refptr = 0x2000 + 0x8 = 0x2008; *refptr = (un.) (0x1000 + 1F + 0) = 0x101F
3. refptr = 0x2000 + 0x10 = 0x2010; *refptr = (un.) (0x1000 + 1B + 0) = 0x101B
4. refptr = 0x2000 + 0x18 = 0x2018; *refptr = (un.) (0x1000 + 11 + 0) = 0x1011
5. refptr = 0x2000 + 0x20 = 0x2020; *refptr = (un.) (0x1000 + 11 + 0) = 0x1011
6. refptr = 0x2000 + 0x28 = 0x2028; *refptr = (un.) (0x1000 + 15 + 0) = 0x1015
### Zadanie 2
:::info
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? Przy pomocy narzędzia ``c++filt`` przekształć poniższe nazwy na sygnatury funkcji języka C++ i omów znaczenie poszczególnych fragmentów symbolu. Czy funkcja dekorująca nazwy jest różnowartościowa?
1. _Z4funcPKcRi
2. _ZN3Bar3bazEPc
3. _ ZN3BarC1ERKS_
4. _ZN3foo6strlenER6string
Wskazówka: Szczegółowe informacje na temat kodowania nazw można znaleźć w C++ ABI: External Names.
:::
Dekorowanie nazw – technika stosowana przez kompilatory współczesnych języków programowania w celu wygenerowania unikatowych (czyli funkcja ta jest różnowartościowa) nazw funkcji, struktur, klas oraz innych typów danych.
>> c++filt _Z4funcPKcRi
func(char const*, int&)
>> c++filt _ZN3Bar3bazEPc
Bar::baz(char*)
>> c++filt _ ZN3BarC1ERKS_
Bar::Bar(Bar const&)
>> c++filt _ZN3foo6strlenER6string
foo::strlen(string&)
_Z - początek dekoracji
N ... E - <nested-name> - rekurencyjnie rozkłada obejmujący zasięg, aż do osiągnięcia globalnego zasięgu.
K - const
R - &
C1 - konstruktor
P - wskaźnik
c - char
i - int
S_ - pierwsza nazwa typu (w przypadku powyżej Bar)
cyfry stojące przed nazwami - liczba liter nazwy
### Zadanie 3
:::info
Podglądając wyjście z kompilatora języka C pokaż jak korzystając z dyrektyw asemblera opisanych w GNU as: Assembler Directives:
• zdefiniować globalną funkcję foobar,
• zdefiniować lokalną strukturę podaną niżej:
```cpp=
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.
:::
Spróbujemy wszystkie te czynności wykonać w pliku `task3.c`, a następnie poleceniem `gcc -S task3.c` wygenerować plik *.s i przeanalizować go używając dostępnych środków (link w treści zadania na skos).
**task3.c**
```c
void foobar () { }
static const struct {
char a[3];
int b;
long c;
float pi;
} baz = { "abc", 42, -3, 1.4142 };
long array[100];
```
**task3.s** + opisy dotyczące dyrektyw (posiłkowane [GNU as: Assembler Directives](https://sourceware.org/binutils/docs-2.26/as/Pseudo-Ops.html) i internetem, do którego już nie mam linka)
```asm
.file "task3.c" # informacja z jakiego pliku
.text # dalsze dane będą w sekcji “text” pliku wykonywalnego ELF.
# Informuje „as”, aby zebrać następujące instrukcje na końcu podrozdziału numerowanego, który jest wyrażeniem absolutnym. Jeśli podsekcja zostanie pominięta, użyty zostanie numer zero.
.globl foobar # foobar ma być dostępny dla konsolidatoróœ (globalny)
# .global makes the symbol visible to ld.
.type foobar, @function # ustawia typ symbolu foobar - funkcja
foobar: # CFI - Call Frame Information
.LFB0: # CFA - Canonical Frame Address
.cfi_startproc # początek obszaru związanego z ramką wywołania funkcji
# Jest używany na początku każdej funkcji, w której powinien znajdować się wpis .eh_frame. Inicjuje niektóre wewnętrzne struktury danych.
endbr64
pushq %rbp
.cfi_def_cfa_offset 16 # offset wzgl. rejestru wierzchu stosu
# .cfi_offset rejestr, przesunięcia
# Poprzednia wartość rejestru jest zapisywana z przesunięciem przesunięcia względem CFA.
# Dyrektywa .cfi_def_cfa_offset 16 informuje, że ramka stosu jest przesunięta 16 bajtów.
#
# | Zawartość
#-------+----------------------------
# A | część z danymi wywołującego
# A+8 | adres powrotny
# A+16 | dane foobar
.cfi_offset 6, -16 # adres wierzchu stosu wywołującego będzie w rejestrze 6
movq %rsp, %rbp
.cfi_def_cfa_register 6 # z tego co kojarzę wierzch stosu
# cfi_def_cfa_register modyfikuje regułę obliczania CFA. Od teraz rejestr 6 będzie używany zamiast starego. Przesunięcie pozostaje takie samo.
nop
popq %rbp
.cfi_def_cfa 7, 8
# .cfi_def_cfa rejestr, przesunięcia
# .cfi_def_cfadefiniuje regułę obliczania CFA jako: pobierz adres z rejestru i dodaj do niego przesunięcie .
ret
.cfi_endproc # koniec obszaru
.LFE0:
.size foobar, .-foobar # ustawienie rozmiaru związanego z foobar
# rozmiar nie jest podany wiec zostanie obliczony później
.section .rodata # dyrektywa mówi, aby złożyć następujący kod w sekcję o nazwie .rodata
.align 16 # .align 16 przesuwa licznik lokalizacji, aż będzie wielokrotnością liczby 16. Jeśli już był, to nie trzeba nic robić.
# adresy podzielne przez 16
.type baz, @object # typ baz - object | utworzony symbol
.size baz, 24 # rozmiar 24 bajty
baz:
.ascii "abc" # spodziewa się 0 lub więcej literałów po przecinku
# Składa każdy ciąg (bez automatycznego końcowego bajtu zerowego) w kolejne adresy.
.zero 1 # alias dla .skip
# wypełnia zerem 1 bajt
.long 42 # 32 bitowe słowo
.quad -3 # 64 bitowe słowo
.long 1068827777 # 32-bitowe słowo
.zero 4 # 4 bajty wypełnione zerami
.comm array,800,32 # deklaruje symbol array 0 wielkości 800 = 100 elementów o rozmiarze 8 bajtów
# dyrektywa przyjmuje opcjonalny trzeci argument. Jest to pożądane wyrównanie symbolu określonego dla ELF jako granicy bajtów (na przykład wyrównanie 16 oznacza, że najmniej znaczące 4 bity adresu powinny wynosić zero), a dla PE jako potęgi dwóch (na przykład wyrównanie 5 oznacza wyrównanie do 32-bajtowej granicy).
.ident "GCC: (Ubuntu 9.3.0-10ubuntu2) 9.3.0"
.section .note.GNU-stack,"",@progbits
.section .note.gnu.property,"a"
.align 8
.long 1f - 0f
.long 4f - 1f
.long 5
0:
.string "GNU"
1:
.align 8
.long 0xc0000002
.long 3f - 2f
2:
.long 0x3
3:
.align 8 # wypełnij licznik lokalizacji (w bieżącym podsekcji) do określonej granicy pamięci.
# .align 8 przesuwa licznik lokalizacji, aż będzie wielokrotnością liczby 8. Jeśli już był, to nie trzeba nic robić.
4:
```
generujemy `task3.o` poleceniem `as -o task3.o task3.s`
poprzez wywołanie `objdump -t task3.o` sprawdzamy naszą tablicę symboli.
**Symbol Table**
```
task3.o: file format elf64-x86-64
SYMBOL TABLE:
0000000000000000 l df *ABS* 0000000000000000 task3.c
0000000000000000 l d .text 0000000000000000 .text
0000000000000000 l d .data 0000000000000000 .data
0000000000000000 l d .bss 0000000000000000 .bss
0000000000000000 l d .rodata 0000000000000000 .rodata
0000000000000000 l O .rodata 0000000000000018 baz
0000000000000000 l d .note.GNU-stack 0000000000000000 .note.GNU-stack
0000000000000000 l d .note.gnu.property 0000000000000000 .note.gnu.property
0000000000000000 l d .eh_frame 0000000000000000 .eh_frame
0000000000000000 l d .comment 0000000000000000 .comment
0000000000000000 g F .text 000000000000000b foobar
0000000000000320 O *COM* 0000000000000020 array
```
### Zadanie 4
:::info
Na podstawie rozdziału §7.12 podręcznika „Computer Systems: A Programmer’s Perspective” opisz proces leniwego wiązania (ang. lazy binding) symboli i odpowiedz na następujące pytania:
• Czym charakteryzuje się kod relokowalny (ang. Position Independent Code)?
• Do czego służą sekcje «.plt» i «.got» – jakie dane są tam przechowywane?
• Czemu sekcja «.got» jest modyfikowalna, a sekcje kodu i «.plt» są tylko do odczytu?
• Co znajduje się w sekcji «.dynamic»?
Zaprezentuj leniwe wiązanie na podstawie programu «lazy». Uruchom go pod kontrolą debuggera GDB, ustaw punkty wstrzymań (ang. breakpoint) na linię 4 i 5. Po czym wykonując krokowo program (stepi) pokaż, że gdy procesor skacze do adresu procedury «puts» zapisanego w «.got» – za pierwszym wywołaniem jest tam przechowywany inny adres niż za drugim.
Wskazówka: Wykorzystaj rysunek 7.19. Dobrze jest zainstalować sobie GDB dashboard.
:::
**leniwe linkowanie** - czekanie z linkowaniem adresu procedury, aż zostanie zawołana pierwszy raz
przy uruchamianiu programu, mamy specjalnie przygotowane PLT (Procedure linkage table) oraz GOT (Global offset table)
PLT zawiera puste wpisy, które powodują
rozwiązanie symbolu i poprawienie wpisu w tablicy
tak, że kolejne skoki już są pod właściwy adres
GOT zawiera adresy fragmentu kodu w PLT który poprawi dane pole GOT
Zamiast wołać funkcje bilbioteczne, wołamy odpowiedni dla nich adres w PLT, on skacze do lokalizacji podanej w tablicy GOT pod odpowiednim indexem. Początowo, ten adres to kolejna instrukcja danego PLT. Kolejna instrukcja, powoduje przekazanie odpowiedniego argumentu do dynamicznego linera, i wywołanie PLT[0] czyli fragmentu odpowiedzialnego za zawołanie dynamicznego linkera, przekazujemy mu adres tablicy relokacji (wcześniej przekazaliśmy mu index tego co chemy zrelokować) i wywołujemy go, resztą już zajmnie się dynamiczny linker.
W kolejnych wywołaniach GOT będzie już wskazywał na funkcje
**kod relokowalny** - kod nie zależny od tego w jakim miejscu pamięci jest wykonany, adresy w nim są relatywne do PC
**.plt** sekcja zawierająca tablice procedur relokacyjnych - opisane wyżej
**.got** globalna tablica offsetów - opisane wyżej
**.dynamic** - informacje dotyczące dynamicznego łączenia
przy pierwszym wykonaniu adres to
bnd jmpq *0x2f75(%rip) # 0x555555557fd0 <puts@got.plt>
x 0x555555557fd0 -> 0xf7e3d5a0
przy drugim wykonaaniu jest tak samo
# Lista 10 (21.05.2020)
### Zadanie 1
:::info
Rozważmy dysk o następujących parametrach: 360 obrotów na minutę, 512 bajtów na sektor, 96 sektorów na ścieżkę, 110 ścieżek na powierzchnię. Procesor czyta z dysku całe sektory. Dysk sygnalizuje dostępność danych zgłaszając przerwanie na każdy przeczytany bajt. Jaki procent czasu procesora będzie zużywała obsługa wejścia-wyjścia, jeśli wykonanie procedury przerwania zajmuje 2.5 µs? Należy zignorować czas wyszukiwania ścieżki i sektora.
Do systemu dodajemy kontroler DMA. Przerwanie będzie generowane tylko raz po wczytaniu sektora do pamięci. Jak zmieniła się zajętość procesora?
:::
Dysk posiada 360obr/min czyli w ciągu sekundy ścieżka jest czytana 6 razy.
Mnożymy otrzymaną ilość razy ilość sektorów na ścieżkę (96 x 6) co daje nam 576 sektorów przeczytanych w 1 sekundę. Mnożymy to razy liczbę bajtów (576 x 512) i otrzymujemy 294 912B/s = 0.294912B/us, zatem aby przeczytać 1B potrzebujemy około 3.4 us, po czym zgłaszamy przerwanie, które zajmuję 2.5us.
Aby obliczyć procent zajętości procesora liczymy 2.5/3.4 * 100% = 73.5%
W momencie gdy przerwanie będzie generowane tylko raz po wczytaniu sektora, jeżeli czytamy 576 sektorów w 1s, przeczytanie sektora zajmie nam 1740.8us (Skoro 1B czytamy 3.4us, to cały sektor czytamy w (512 x 3.4us)), czyli
2.5/1740.8 * 100% = 0.14%
### Zadanie 2
:::info
Moduł DMA kontrolera dysku do transferu danych używa techniki podkradania cykli. 32-bitowa szyna ma przepustowość 10 milionów transferów na sekundę. Procesor RISC bez pamięci podręcznej wykonuje 32-bitowe instrukcje, z których 40% to dostępy do pamięci. O ile procent zmieni się liczba wykonywanych instrukcji w wyniku aktywności modułu DMA, jeśli transferujemy z dysku dane z prędkością 2MB/s.
:::
W zadaniu jest napisane "O ile procent zmieni się liczba wykonywanych instrukcji w wyniku aktywności modułu DMA" choć tak na prawdę chodzi o liczbę wykonanych operacji w jednostce czasu.
Szyna 32-bitowa ma przepustowość 10mln transferów na sekundę. Skoro 10mln razy na sekundę wysyła po 32 bity to jej przepustowość to 320000000b/s zatem około 38MB/s. Jeśli aktywuje się moduł DMA i transferuje dane z prędkością 2MB/s to "zabiera" około 5% całkowitej przepustowości szyny. Przez to, że tylko 95% całkowitej przepustowości szyny jest wolne (pozostałe 5% wykorzystuje moduł DMA) to w danej jednostcze czasu dostępy pamięci które wykonuje procesor zwolnią średnio do 95% oryginalnej prędkości (oryginalnej czyli takiej w której modół DMA nic by nie robił). W zadaniu podane jest że procesor wykonuje jakieś operacje z których 40% to dostępy do pamięci. Poza tym procesor musi jeszcze wczytywać z pamięci kolejne instrukcje zatem 60% instrukcji wykona 1 dostęp do pamięci a pozostałe 40% 2 dostępy do pamięci. Zatem 60% operacji które wykonywał procesor zwolni o 2.5% a pozostałe 40% zwolni o 5% zatem całość zwolni do 60%x97.5% + 40%x95% = 96.5% czyli całość zwolni o około 3.5%.
### Zadanie 3
:::info
Nowoczesny procesor x86-64 (np. i7-6700) ma następujące czasy dostępu do poszczególnych poziomów pamięci: L1 cache: 4 cykle; L2 cache: 12 cykli; L3 cache: 40 cykli; pamięć DRAM: 200 cykli. Jaki jest średni czas dostępu do pamięci, jeśli 90% dostępów trafia w cache L1, 95% w cache L2, 98% w cache L3? Jaki jest pesymistyczny czas dostępu do pamięci?
Wskazówka: Dostęp do pamięci o poziomie i+1 zachodzi tylko wtedy, gdy chybiliśmy w pamięć na poziomie i.
:::
Średni czas dostępu:
0,9 * 4+0,1 * (0,95 * 16+0,05 * (0,98 * 56+0,02 * 256)) = 5.42
Pesymistyczny czas dostępu:
200 + 40 + 12 + 4 = 256
### Zadanie 4
:::info
Na podstawie [ 1 , § 2.1.3] i [ 1 , § 2.2] zreferuj protokół komunikacji kontrolera pamięci z modułami pamięci DRAM. Wyjaśnij kroki jakie musi podjąć kontroler by odczytać jedną lub kilka kolejnych komórek pamięci. Wyjaśnij źródło opóźnień t~CAS~ (CL), t~RCD~, t~RP~, t~RAS~ ograniczających wydajność operacji.
Wskazówka: Gdyby źródło [1] okazało się niewystarczające należy zajrzeć do [2, §11.1].
:::
Kontroler rozpoczyna odczyt od zrobienia dostępu adresu rzędu na szynie adresowej i obniżeniu sygnału RAS (Row Address Selection). Wtedy czip RAMu zapamiętuje stan zaadresowanego rzędu. Następnie poprzez zrobienie dostępu na szynie adresowej i obniżeniu sygnału CAS (Column Address Selection) (po opóźnieniu $t_{RCD}$) przekazany zostaje adres kolumny.
Po zakończonym adresowaniu (i opóźnieniu $t_{CAS}$) może nastąpić transfer danych.
Ponadto, możliwe jest wielokrotne wywołanie sygnału CAS, bez uprzedniego RAS, co znacznie usprawnia odczyt.
Przed wczytaniem kolejnego rzędu, musi on najpierw zostać zdeaktywowany. Po podaniu sygnału do naładowania (tu: jednoczesne obniżenie sygnałów WE i RAS) i odczekaniu $t_{RP}$ cykli może nastąpić załadowanie następnego rzędu.
#### Opóźnienia:
$t_{CAS} (CL)$ - minimalny czas między wykonaniem odczytu z kolumny a początkiem transferu danych.
$t_{RCD}$ - czas między wydaniem polecenia wyboru wiersza, a dostępnością danych na wyjściu z układu wzmacniającego.
$t_{RP}$ - czas na przygotowanie innego wiersza na dostęp.
$t_{RAS}$ - minimalny czas między poleceniem wyboru wiersza, a przywróceniem danych w wierszu powykonaniu operacji.
### Zadanie 5
:::info
Blok pamięci podręcznej procesorów x86-64 ma 64 bajty. Dla uproszczenia przyjmijmy, że w jednym cyklu zegarowym między pamięcią a procesorem można przesłać 64 bity danych. Ile nanosekund, w pesymistycznym przypadku, zajmie sprowadzenie bloku pamięci podręcznej z pamięci DRAM dla poniżej scharakteryzowanych modułów:
• DDR4-1600, t~CLK~= 800MHz, t~CAS~ = 10, t~RCD~ = 10, t~RP~ = 10, t~RAS~= 25,
• DDR4-2133, t~CLK~ = 1066.67MHz, t~CAS~ = 15, t~RCD~ = 15, t~RP~ = 15, t~RAS~ = 36.
Powtórz obliczenia zakładając, że pamięć działa w trybie sekwencyjnym (ang. burst mode), tj. podaje na kolejnych zboczach zegara szesnaście 64-bitowych słów bez czekania na polecenie zmiany kolumny.
:::
Pesymistyczny przypadek interpretujemy jako przymus wykonania wszystkich operacji odczytu (w optymistycznym przypadku, mogłoby się przykładowo okazać, że interesująca nas komórka znajduje się już w załadowanym wierszu).
Zatem w pierwszym trybie musimy zlokalizować i wczytać odpowiedni wiersz ($t_{RCD}$), wybrać odpowiednie komórki (za każdym razem odczekując $t_{CAS}$) i transferować kolejne słowa (przesył jednego słowa ($1B$) = 1 cykl). Pamiętając, że wszystkie te operacje nie mogą trwać krócej od $t_{RAS}$ (z fizycznych ograniczeń), ładujemy rząd z powrotem do pamięci.
$t_{s} = max(t_{RAS}, t_{RCD} + 8 \cdot t_{CAS} + 8) + t_{RP}$
Dla trybu sekwencyjnego musimy wczytać wiersz ($t_{RCD}$) oraz ustawić odpowiednią kolumnę ($t_{CAS}$). W tym trybie, nie oczekujemy na polecenie zmiany kolumny i wysyłamy kolejne słowa. Ponieważ odbywa się to na zboczach zegara, to w trakcie 4 cykli możemy wysłać aż 8 słów.
$t_{br} = max(t_{RAS}, t_{RCD} + t_{CAS} + 4) + t_{RP}$
### DDR4-1600
Jeden cykl zegara trwa:
$$
\frac{1}{8 \cdot 10^{8}} \: [\frac{1}{Hz}] = 1,25 [ns]
$$
#### W normalnym trybie:
$$
t_{s} = max(25, 10 + 8 \cdot 10 + 8) + 10 = 108 \: [cykli]
$$
Odczytanie 64-bajtowego bloku zajmuje **$135 [ns]$**.
#### W trybie sekwencyjnym:
$$
t_{br} = max(25, 10 + 10 + 4) + 10 = 35 \: [cykli]
$$
Czyli **$43,75 [ns]$**.
### DDR4-2133
Jeden cykl zegara trwa:
$$
\frac{1}{1,0667 \cdot 10^{9}} \: [\frac{1}{Hz}] \approx 0,94 [ns]
$$
#### W normalnym trybie:
$$
t_{s} = max(36, 15 + 8 \cdot 15 + 8) + 10 = 153 \: [cykli]
$$
Całkowity czas operacji: **$143,82 [ns]$**.
#### W trybie sekwencyjnym:
$$
t_{br} = max(36, 15 + 15 + 4) + 15 = 51 \: [cykli]
$$
Co daje **$47,94 \: [ns]$**.
### Zadanie 6
:::info
Program czyta sekwencyjnie jednowymiarową tablicę o rozmiarze 4GiB położoną pod adresem podzielnym przez 2^20^. W komputerze zainstalowano dwa moduły pamięci DDR4-2133 o parametrach: t~CAS~ = 15, t~RCD~ = 15, t~RP~ = 15, t~RAS~ = 36, maksymalny rozmiar transferu sekwencyjnego to 16 słów, długość wiersza (ang. DRAM page size) wynosi 8KiB. Ile czasu zajmie sprowadzenie danych do procesora? Należy pominąć rozważanie opóźnień wynikających z działania pamięci podręcznej i kontrolera pamięci.
Powtórz obliczenia dla systemu dysponującego pamięcią w konfiguracji dwukanałowej (ang. dual-channel).
:::
Odczyt następuje z pamięci znajdującej się pod adresem podzielnym przez 2^20^, więc zacznie się od początku nowego wiersza.
Jeden cykl zegara trwa:
$$
\frac{1}{1,0667 \cdot 10^{9}} \: [\frac{1}{Hz}] \approx 0,94 [ns]
$$
Obliczamy liczbę wierszy składających się na całą tablicę: 4GiB / 8KiB = 524288
Ponieważ dokonujemy odczytu sekwencyjnie nie musimy wysyłać kolejnych żądań zmiany kolumny 15 razy po ostatnim takim sygnale, a treść pobranych komórek jest wysyłana na zboczach zegara, czyli dwukrotnie w trakcie cyklu - łącznie 16 bajtów.
W jednym wierszu o długości 8KiB mieści się 512 bajtów możliwych do wysłania w ciągu 32 cykli.
Ostatecznie możemy wyliczyć, że oprócz 524288 operacji zmian wiersza dojdzie do 32 operacji ustawienia kolumny w każdym wierszu.
Liczbę cykli potrzebnych na pobranie danych z jednego wiersza poznamy z najstępującego wzoru (32 operacje ustawienia kolumny oraz 32 cykle potrzebne na wysłanie danych):
$t_{br} = max(t_{RAS}, t_{RCD} + 32*t_{CAS} + 32) + t_{RP}$
$t_{br} = max(36, 15 + 32*15 + 32) + 15 = 542 \approx 509 [ns]$
Wynik dla całej pamięci wyniesie:
$542 * 524288 = 284164096 \approx 267114250 [ns] = 0.2671 [s]$
### Zadanie 7
:::info
Nagraj na przenośny dysk USB program memtest86 i uruchom go z poziomu wbudowanego oprogramowania UEFI. Podaj parametry systemu pamięci w swoim komputerze. Jaka jest przepustowość poszczególnych poziomów pamięci podręcznej i pamięci DRAM? Oszacuj, w taktach procesora, średni czas dostępu do pamięci podręcznej L1, L2, L3 i pamięci DRAM.
:::
|type | size | speed |
| ------ | ----- | --------- |
|L1 Cache| 64k | 88408 MB/s|
|L2 Cache| 512K | 88408 MB/s|
|L3 Cache| 8192K |30336 MB/s |
|Memory | 8145M |10079 MB/s |
Chipset: Unknown
Memory type: Unknown
Memory clock: 2400hz
CLK: 3094MHz
| typ | Oszacowany średni czas dostępu (128B) |
|-----|--------------------------------|
|L1 | 4 cykli |
|L2 | 4 cykli |
|L3 | 12 cykli|
|mem | 38 cykli|
# Lista 11 (28.05.2020)
### Zadanie 1
:::info
Rozważmy pamięć podręczną z mapowaniem bezpośrednim adresowaną bajtowo. Używamy adresów 32-bitowych w następującym formacie: (tag, index, offset) = (addr31...10, addr9...5, addr4...0).
• Jaki jest rozmiar bloku w 32-bitowych słowach?
• Ile wierszy ma nasza pamięć podręczna?
• Jaki jest stosunek liczby bitów składujących dane do liczby bitów składujących metadane?
:::
**pamięć podręczna z mapowaniem bezpośrednim** - pamięć podręczna, w której na jeden zbiór przypada tylko jeden wiersz.
**adresowanie bajtowe** - adresowanie, za pomocą którego można uzyskać dostęp do poszczególnych bajtów
• Jaki jest rozmiar bloku w 32-bitowych słowach?
Na offset mamy przeznaczone 5 bitów w adresie, zatem rozmiar bloku w wierszu to
$2^5 = 32$ bajty.
1 bajt = 8 bitów czyli 4 bajty = 32 bity = 1 słowo 32bit, więc po przeliczeniu rozmiar bloku to
8 słów 32bit.
• Ile wierszy ma nasza pamięć podręczna?
Na wybór zbioru przeznaczono w adresie 5 bitów. Wiemy, że w każdym zbiorze jest 1 wiersz, więc liczba wierszy to: $2^5 = 32$.
• Jaki jest stosunek liczby bitów składujących dane do liczby bitów składujących metadane?
Wystarczy że policzymy stosunek dla jednego wiersza.
Na metadane skłądają się bity zawierające informacje o znaczniku i bit valid. Pozostałe (bloki w wierszach) to dane.
valid - 1 bit
znacznik - 22 bity (tyle przeznaczono w adresie na zapis znacznika)
blok - 32 Bajty = $8 * 32 = 256$ bitów.
Stosunek danych do metadanych: 256/23
### Zadanie 2
:::info
Mamy system z pamięcią operacyjną adresowaną bajtowo. Szerokość szyny adresowej wynosi 12. Pamięć podręczna ma organizację sekcyjno-skojarzeniową o dwuelementowych zbiorach, a blok ma 4 bajty. Dla podanego niżej stanu pamięci podręcznej wyznacz, które bity adresu wyznaczają: offset, indeks, znacznik. Wszystkie wartości numeryczne podano w systemie szesnastkowym.
| Indeks | | Znacznik | Valid | B0 | B1 | B2 | B3 | | Znacznik | Valid | B0 | B1 | B2 | B3 |
|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|
| 0 | | 00 | 1 | 40 | 41 | 42 | 43 | | 83 | 1 | FE | 97 | CC | D0 |
| 1 | | 00 | 1 | 44 | 45 | 46 | 47 | | 83 | 0 | – | – | – | – |
| 2 | | 00 | 1 | 48 | 49 | 4A | 4B | | 40 | 0 | – | – | – | – |
| 3 | | FF | 1 | 9A | C0 | 03 | FF | | 00 | 0 | – | – | – | – |
Określ, które z poniższych operacji odczytu wygenerują trafienie albo chybienie i ew. jakie wartości wczytają:
Adres | Trafienie? | Wartość
-|-|-
832 | . . . | . . .
835 | . . . | . . .
FFD | . . . | . . .
:::
W celu pobrania rozkazu lub danej następuje sprawdzenie czy potrzebna informacja jest zapisana w pamięci podręcznej. Jeśli - tak, to mamy do czynienia z trafieniem, jeśli nie - chybieniem.
Blok ma 4 bajty, więc aby zapisać informację do którego bajtu się odwołać potrzebujemy 2 bity. Podobnie index: potrzebujemy 2 bity, ponieważ mamy 4 indexy. Zatem na znacznik pozostaje nam 12 bitów - 2 bity (blok) - 2 bity (index) = 8 bitów.
Adres | Offset | Indeks | Znacznik
-|-|-|-
832 | 0x2 | 0x0 | 0x83
835 | 0x1 | 0x1 | 0x83
FFD | 0x1 | 0x3 | 0xFF
Adres | Trafienie? | Wartość
-|-|-
832 | TAK | CC
835 | NIE | BRAK
FFD | TAK | C0
### Zadanie 3
:::info
Rozważmy pamięć podręczną z poprzedniego zadania. Mamy następującą sekwencję odwołań do czterobajtowych słów pamięci o adresach zadanych liczbami w systemie szesnastkowym:
```
0 4 10 84 E8 A0 400 1C 8C C1C B4 884
```
Załóż, że na początku pamięć podręczna jest pusta. Jak wiele bloków zostało zastąpionych? Jaka jest efektywność pamięci podręcznej (liczba trafień procentowo)? Podaj zawartość pamięci podręcznej po wykonaniu powyższych odwołań – każdy ważny wpis wypisz jako krotkę (tag, index, . . . ). Dla każdego chybienia wskaż, czy jest ono przymusowe (ang. compulsory miss), czy wynika z kolizji na danym adresie (ang. conflict miss) czy ograniczonej pojemności (ang. capacity miss).
:::
0 - tag = 00 s = 0 b = 0 cold miss
4 - tag = 00 s = 1 b = 0 cold miss
10 - tag = 01 s = 0 b = 0 cold miss
84 - tag = 08 s = 1 b = 0 cold miss
E8 - tag = 0E s = 2 b = 0 cold miss
A0 - tag = 0A s = 0 b = 0 conflict miss
400 - tag = 40 s = 0 b = 0 - conflict miss
1C - tag = 01 s = 3 b = 0 cold miss
8C - tag = 08 s = 3 b = 0 cold miss
C1C - tag = C1 s = 3 b = 0 cold miss
B4 - tag = 0B s = 1 b = 0 conflict miss
884 - tag = 88 s = 1 b = 0 conflict miss
przyjmujac ze poswiecamy dane ktore sa w pamieci najdluzej nasza pamiec moze wygladac w ten sposob
S | TT |
|-|-|
0 | 0A |
0 | 40 |
1 | 0B |
1 | 88 |
2 | E8 |
2 | -- |
3 | 08 |
3 | C1 |
efektywnosc = 0%
### Zadanie 4
:::info
Powtórz poprzednie zadanie dla poniższych organizacji pamięci podręcznej. Zakładamy, że bloki są długości dwóch słów pamięci. Ile dodatkowych bitów na linię pamięci podręcznej potrzeba na implementację określonej polityki wymiany (ang. replacement policy ).
• sekcyjno-skojarzeniowa 2-drożna, 16 bloków, polityka NRU (ang. Not Recently Used)
• w pełni asocjacyjna (ang. fully associative), 8 bloków, polityka LRU (ang. Least Recently Used).
:::
Polityka wymiany - algorytm za pomocą którego zarządzamy pamięcią, m. in. stwierdzamy, które wartości chcemy utrzymywać (i zastępować) w cache'u.
• Sekcyjno-skojarzeniowa 2-drożna, 16 bloków, polityka NRU
Mamy 8 zbiorów po 2 linie. Potrzebujemy dodatkowy jeden bit na zbiór, aby reprezentować co usuwamy (pół bitu na linię).
Używamy adresów 12-bitowych w następującym formacie: $(tag, index, offset) = (addr_{11}\dots_4, addr_3\dots_1, addr_0\dots_0)$
| Adres | Adres (rozpisany) | Miss (co zastępujemy) |
|-------|----------------|--------------------|
| 000 | 00000000 000 0 | compulsory miss |
| 004 | 00000000 010 0 | compulsory miss |
| 010 | 00000001 000 0 | compulsory miss |
| 084 | 00001000 010 0 | compulsory miss |
| 0E8 | 00001110 100 0 | compulsory miss |
| 0A0 | 00001010 000 0 | conflict miss (000)|
| 400 | 01000000 000 0 | conflict miss (010)|
| 01C | 00000001 110 0 | compulsory miss |
| 08C | 00001000 110 0 | compulsory miss |
| C1C | 11000001 110 0 | conflict miss (01C)|
| 0B4 | 00001011 010 0 | conflict miss (004)|
| 884 | 10001000 010 0 | conflict miss (084)|
• W pełni asocjacyjna (ang. fully associative), 8 bloków, polityka LRU
Mamy 1 zbiór z 8 liniami. Potrzebujemy dodatkowe $\lceil log_2(8!)\rceil$ na zbiór (więcej w zad. 8), czyli w sumie 16 bitów (po 2 bity na linię).
Używamy adresów 12-bitowych w następującym formacie: $(tag, offset) = (addr_{11}\dots_1, addr_0\dots_0)$
| Adres | Adres (rozpisany) | Miss (co zastępujemy) |
|-------|---------------|---------------------|
| 000 | 00000000000 0 | compulsory miss |
| 004 | 00000000010 0 | compulsory miss |
| 010 | 00000001000 0 | compulsory miss |
| 084 | 00001000010 0 | compulsory miss |
| 0E8 | 00001110100 0 | compulsory miss |
| 0A0 | 00001010000 0 | compulsory miss |
| 400 | 01000000000 0 | compulsory miss |
| 01C | 00000001110 0 | compulsory miss |
| 08C | 00001000110 0 | capacity miss (000) |
| C1C | 11000001110 0 | capacity miss (004) |
| 0B4 | 00001011010 0 | capacity miss (010) |
| 884 | 10001000010 0 | capacity miss (084) |
### Zadanie 5
:::info
Odpowiedz na następujące pytania dotyczące organizacji pamięci podręcznej:
1. Do wyboru zbioru pamięci podręcznej używamy bitów znajdujących się w środku adresu, zaraz przed offsetem bloku. Czemu jest to lepszy pomysł niż używanie najbardziej znaczących bitów adresu?
2. Zdecydowana większość procesorów posiada odrębną pamięć podręczną pierwszego poziomu dla danych i dla instrukcji. Jakie korzyści to przynosi?
:::
1. Programy cechuje lokalność - odwołują się do danych bliskich siebie. Jeśli używalisbyśmy najbardziej znaczących bitów, to dane blisko siebie trafiałyby do tych samych zbiorów, nadpisując się. Zwiększyłoby to liczbę cache miss.
2. Instrukcji (zazwyczaj) się nie nadpisuje, a jedynie je czyta. Pamięć podręczna dla instrukcji może więc być bardziej wyspecjalizowana w czytaniu. Ponadto nowoczesne procesory potrafią czytać z obu tych cachy jednocześnie. Wiele procesorów implementuje też dekodowanie instrukcji i trzymanie ich już zdekodowanych w pamięci podręcznej, co dodatkowo zwiększa wydajność.
### Zadanie 6
:::info
Rozważamy system z dwupoziomową pamięcią podręczną z polityką zapisu write-back z writeallocate. Dodatkowo zakładamy, że blok o określonym adresie może znajdować się tylko na jednym poziomie pamięci podręcznej (ang. exclusive caches). Przy pomocy schematu blokowego przedstaw algorytm obsługi zapisu słowa maszynowego do pamięci. Pierwszym elementem diagramu ma być predykat „Czy słowo jest w L1?”. Pamiętaj o bicie dirty i o tym, że pamięć podręczna może być całkowicie wypełniona! Zakładamy, że pamięć podręczna pierwszego poziomu nie może komunikować się bezpośrednio z pamięcią operacyjną.
:::
Polityka zapisu mowi nam jakie przyjmujemy strategie przy zapisach danych
w cache ( WRITE-HIT i WRITE-MISS )
( STRATEGIE PRZY WRITE-HIT )
WRITE-THROUGH -> od razu update'ujemy pamiec,
w rezultacie CACHE trzyma taka sama wartosc jak pamiec
WRITE-BACK -> Dane poczatkowo zostaja zupdate'owane tylko w cache, dopiero
w momencie gdy pamiec ma byc nadpisana - zapisujemy zmieniona wartosc
w cache nizszego stopnia.
(Przy Write-back kazdy blok musi miec tzw. "dirty bit"
mowiacy o tym czy dane w nim sa odpowiednio:
Dirty -> Nadpisane wzgledem cache nizszego poziomu
Clean -> Nie nadpisane)
( STRATEGIE PRZY WRITE-MISS )
WRITE-ALLOCATE -> Wyciagamy dane z pamieci nizszego stopnia i update'ujemy
tylko w cache do ktorego sciagnelismy ten blok.
WRITE AROUND -> Bezposrednio zapisujemy w pamieci bez wciaganie do cache.
W tym zadaniu przyjmujemy, ze system dziala z polityka WRITE-BACK i WRITE-ALLOCATE ( jest to najczesciej spotykane polaczenie ). Pamiec podreczna jest
dwupoziomowa wiec mamy L1 i L2, a polityka zawierania sie Cache
( Cache Inclusion Policy ) to "Exclusive Cache" czyli nie mozemy trzymac
tego samego bloku na roznych poziomach pamieci podrecznej.
Algorytm obslugi zapisu slowa w schemacie blokowym:
https://drive.google.com/file/d/1uA2OdcU5FNxUuMegIEyCAST4HGWIeMNM/view?usp=sharing
### Zadanie 7
:::info
Załóżmy, że dostęp do pamięci głównej trwa 70ns, a dostępy do pamięci stanowią 36% wszystkich instrukcji. Rozważmy system z pamięcią podręczną o następującej strukturze: L1 – 2 KiB, współczynnik chybień 8.0%, czas dostępu 0.66ns (1 cykl procesora); L2 – 1 MiB, współczynnik chybień 0.5%, czas dostępu 5.62ns. Procesor charakteryzuje się współczynnikiem CPI (ang. clocks per instruction) równym 1.0, jeśli pominiemy instrukcje robiące dostępy do pamięci danych. Odpowiedz na poniższe pytania:
• Jaki jest średni czas dostepu do pamięci dla procesora: tylko z pamięcią podręczną L1, z L1 i L2?
• Procesor wykonuje wszystkie instrukcje, łącznie z dostępami do pamięci danych. Oblicz jego CPI kiedy posiada: tylko pamięć podręczną L1, z L1 i L2.
Uwaga: Zakładamy, że wszystkie instrukcje wykonywane przez program są w pamięci podręcznej L1i.
:::
Mamy:
dostęp do pamięci głównej --- $70ns$
dostępy do pamięci --- $36\%$ wszystkich instrukcji
0.66ns --- 1 cykl procesora
$L1$ :
2 KiB,
współczynnik chybień 8.0% (czyli 92% trafień),
czas dostępu 0.66ns (1 cykl procesora);
$L2$ :
1 MiB,
współczynnik chybień 0.5% (czyli 99,5% trafień),
czas dostępu 5.62ns.
Aby znaleźć średni czas dostępu do pamięci, mamy wzór:
:::warning
$T_{avg} = T_c + h * M$
$h \quad -$ współczynnik chybień
$T_c \quad -$ czas dostępu do informacji z pamięci podręcznej
$M \quad -$ czas dostępu do pamięci głównej
:::
---
stąd:
* Jaki jest średni czas dostepu do pamięci dla procesora:
* tylko z pamięcią podręczną $L1$
$h \space = 0.08$
$T_c \space = 0.66ns$
$M = 70ns$
$T_{avg} = 0.66 + 0.08 * 70 = 6.26\space ns \approx 9,485 \space cykli$
* z $L1$ i $L2$?
$h_1 \space = 0.08$
$h_2 \space = 0.005$
$T_{c_1} \space = 0.66ns$
$T_{c_2} \space = 5.62ns$
$M = 70ns$
:::warning
$T_{avg} = T_{c_1} + h_1 * (T_{c_2} + h_2 * M)$
:::
$T_{avg} = 0.66 + 0.08 * (5.62 + 0.005 * 70) = 1,1376 \space ns \approx 1,72 \space cykli$
---
$CPI$ -- clocks per instructions -- ilość cykli na instrukcję
Gdzie $IC_{i}$ to liczba instrukcji dla danego typu instrukcji $i$, $CC_{i}$ to cykle zegara dla tego typu instrukcji i $IC = \sum_{i} (IC_ {i})$ jest całkowitą liczbą instrukcji.
:::warning
współczynnik $CPI$ równa się $1.0$, a zatem:
$CPI = 1 + T_{avg} * procent\_dostępów\_do\_pamięci$
:::
* Oblicz jego $CPI$ kiedy posiada:
* tylko pamięć podręczną $L1$,
$CPI = 1 + 9,485 * 0.36 = 4,4146$
* z $L1$ i $L2$.
$CPI = 1 + 1,72 * 0.36 = 1,6192$
---
### Zadanie 8
:::info
Dla czterodrożnej sekcyjno-skojarzeniowej pamięci podręcznej implementujemy politykę zastępowania LRU. Masz do dyspozycji dodatkowe $\lceil log_2(4!)\rceil$ bitów na zbiór. Nie można modyfikować zawartości linii w zbiorze, ani zamieniać elementów kolejnością. Jak wyznaczyć kandydata do usunięcia ze zbioru? Jak aktualizować informacje zawarte w dodatkowych bitach przy wykonywaniu dostępów do elementów zbioru?
:::
Z zadania wiemy, że mamy do dyspozycji 5 dodatkowych bitów.
Możemy wykorzystać je w ten sposób, że podzielimy nasze 4 linie pamięci,
na dwie grupy i 1 z tych 5 bitów będzie określał, z której grupy ostatnio korzystaliśmy.
Pozostałe będą nam oznaczać do której linii ostatnio się odnieśliśmy.
W tabelkach
1 - oznacza, że ostatnio korzystaliśmy z tej linii
0 - przeciwny przypadek
Przykład:
- Przykładowy stan
Grupa 0:
| Dane | A | B |
| ------------------- |:-:|:-:|
| Ostatnio użyta linia| 1 | 0 |
Grupa 1:
| Dane | C | D |
| ------------------- |:-:|:-:|
| Ostatnio użyta linia| 1 | 0 |
Ostatnio użyta grupa: 0
-----------------
- Dostęp do B
Grupa 0:
| Dane | A | B |
| ------------------- |:-:|:-:|
| Ostatnio użyta linia| 0 | 1 |
Grupa 1:
| Dane | C | D |
| ------------------- |:-:|:-:|
| Ostatnio użyta linia| 1 | 0 |
Ostatnio użyta grupa: 0
-----------------
- Dostęp do D
Grupa 0:
| Dane | A | B |
| ------------------- |:-:|:-:|
| Ostatnio użyta linia| 0 | 1 |
Grupa 1:
| Dane | C | D |
| ------------------- |:-:|:-:|
| Ostatnio użyta linia| 0 | 1 |
Ostatnio użyta grupa: 1
------------------
- Dostęp do X - ostatnio użyliśmy grupy 1, więc przechodzimy do 0,
a tam ostatni użyliśmy B, więc ofiarą staje się A
Grupa 0:
| Dane | X | B |
| ------------------- |:-:|:-:|
| Ostatnio użyta linia| 1 | 0 |
Grupa 1:
| Dane | C | D |
| ------------------- |:-:|:-:|
| Ostatnio użyta linia| 0 | 1 |
Ostatnio użyta grupa: 0
# Lista 12 (z podręcznika) (04.06.2020)
### Zadanie 5.13
:::info
Suppose we wish to write a procedure that computes the inner product of two vectors u and v. An abstract version of the function has a CPE of 14–18 with x86-64 for different types of integer and floating-point data. By doing the same sort of transformations we did to transform the abstract program combine1 into the more efficient combine4, we get the following code:
```=
/* Inner product. Accumulate in temporary */
void inner4(vec_ptr u, vec_ptr v, data_t *dest)
{
long i;
long length = vec_length(u);
data_t *udata = get_vec_start(u);
data_t *vdata = get_vec_start(v);
data_t sum = (data_t) 0;
for (i = 0; i < length; i++) {
sum = sum + udata[i] * vdata[i];
}
*dest = sum;
}
```
Our measurements show that this function has CPEs of 1.50 for integer data and 3.00 for floating-point data. For data type double, the x86-64 assembly code for the inner loop is as follows:
```=
/*Inner loop of inner4. data_t = double, OP = *
udata in %rbp, vdata in %rax, sum in %xmm0
i in %rcx, limit in %rbx*/
.L15: // loop:
vmovsd 0(%rbp,%rcx,8), %xmm1 // Get udata[i]
vmulsd (%rax,%rcx,8), %xmm1, %xmm1 // Multiply by vdata[i]
vaddsd %xmm1, %xmm0, %xmm0 // Add to sum
addq $1, %rcx // Increment i
cmpq %rbx, %rcx // Compare i:limit
jne .L15 // If !=, goto loop
```
Assume that the functional units have the characteristics listed in Figure:
1. Diagram how this instruction sequence would be decoded into operations and show how the data dependencies between them would create a critical path of operations, in the style of Figures
2. For data type double, what lower bound on the CPE is determined by the critical path?
3. Assuming similar instruction sequences for the integer code as well, what lower bound on the CPE is determined by the critical path for integer data?
4. Explain how the floating-point versions can have CPEs of 3.00, even though the multiplication operation requires 5 clock cycles.
:::
1. Diagram how this instruction sequence would be decoded into operations and show how the data dependencies between them would create a critical path of operations.
2. For data type double, what lower bound on the CPE is determined by the critical path?
Ścieżka krytyczna utworzona jest poprzez operacje dodawania na zmiennej `sum`. Zatem dolna granica CPE to równowartość kosztu dodawania na liczbach zmiennoprzecinokowych podwójnej precyzji.
3. Assuming similar instruction sequences for the integer code as well, what lower bound on the CPE is determined by the critical path for integer data?
Ponieważ ścieżka krytyczna pozostaje niezmienna to dolna granica CPE to 1.0.
4. Explain how the floating-point versions can have CPEs of 3.00, even though the multiplication operation requires 5 clock cycles.
Ponieważ operacja mnożenia nie leży na ścieżce krytycznej to może zostać przetworzona potokowo (mogła zacząć się wykonywać podczas poprzedniej iteracji).
### Zadanie 5.14
:::info
Write a version of the inner product procedure described in Problem 5.13 that uses 6 × 1 loop unrolling. For x86-64, our measurements of the unrolled version give a CPE of 1.07 for integer data but still 3.01 for both floating-point data.
1. Explain why any (scalar) version of an inner product procedure running on an Intel Core i7 Haswell processor cannot achieve a CPE less than 1.00.
2. Explain why the performance for floating-point data did not improve with loop unrolling.
:::
```c=
//////6x1
void inner4(vec_ptr u,vec_ptr v,data_t *dest)
{
long i=0;
long length=vec_length(u);
//od limitu odejmujemy 5 zeby nie wyjsc poza tablice
long limit=length-5;
data_t* udata=get_vec_start(u);
data_t* vdata=get_vec_start(v);
data_t sum=(data_t)0;
//jedna iteracja na 6 elementow tablicy wynikowej
for(i=0;i<limit;i+=6)
{
sum+=udata[i]*vdata[i];
sum+=udata[i+1]*vdata[i+1];
sum+=udata[i+2]*vdata[i+2];
sum+=udata[i+3]*vdata[i+3];
sum+=udata[i+4]*vdata[i+4];
sum+=udata[i+5]*vdata[i+4];
}
for(;i<length;i++)
{
sum+=udata[i]*vdata[i];
}
*dest=sum;
}
```
6 × 1 loop unrolling jest technika ktora pozwala zoptymalizowac branch misprediction i usprawnia potokowane operacje. Zamiast jednej operacji na iteracje robimy ich az 6, dzieki czemu nasz algorytm ma 6 razy mniej skokow warunkowych.
Niestety kazde kolejne dodawanie jakie robimy wciaz jest zalezne od wyniku poprzedniego dodawania.
:::info
1. Explain why any (scalar) version of an inner product procedure running on an Intel Core i7 Haswell processor cannot achieve a CPE less than 1.00.
:::
Dzieje sie tak poniewaz na naszej "sciezce krytycznej" wciaz kazde dodawanie jest zalezne od wyniku poprzedniego ( co widac na diagramie ), dlatego nie mozemy przekroczyc lower bound CPE dodawania (ktore dla liczb calkowitych jest rowne 1.00 a dla zmienno przecinkowych 3.00).
:::info
2. Explain why the performance for floating-point data did not improve with loop unrolling.
:::
Poprzednia wersja dla liczb zmienno przecinkowych osiagnela juz lower bound CPE, a wiec loop unrolling tego nie zoptymalizuje bardziej.
---
Na grafie zaznaczylem sciezke krytyczna na czerwono, i optymalizacje wzgledem wersji z zadania 5.14 na zielono.
### Zadanie 5.15
:::info
Write a version of the inner product procedure described in Problem 5.13 that uses 6 × 6 loop unrolling. Our measurements for this function with x86-64 give a CPE of 1.06 for integer data and 1.01 for floating-point data.
What factor limits the performance to a CPE of 1.00?
:::
```c=
void fun(vec_ptr u, vec_ptr v, data_t *dest){
long i;
long length = vec_length(u);
data_t *udata = get_vec_start(u);
data_t *vdata = get_vec_start(v);
data_t sum0 = (data_t) 0;
data_t sum1 = (data_t) 0;
data_t sum2 = (data_t) 0;
data_t sum3 = (data_t) 0;
data_t sum4 = (data_t) 0;
data_t sum5 = (data_t) 0;
long limit = length-6;
for (i = 0; i < limit; i+=6) {
sum0 = sum0 + udata[i] * vdata[i];
sum1 = sum1 + udata[i+1] * vdata[i+1];
sum2 = sum2 + udata[i+2] * vdata[i+2];
sum3 = sum3 + udata[i+3] * vdata[i+3];
sum4 = sum4 + udata[i+4] * vdata[i+4];
sum5 = sum5 + udata[i+5] * vdata[i+5];
}
sum0 = sum0 + sum1 + sum2 + sum3 + sum4 + sum5;
for(; i < length; i++){
sum0 = sum0 + udata[i] * vdata[i];
}
*dest = sum;
}
```
What factor limits the performance to a CPE of 1.00?
Throughput bound
### Zadanie 5.16
:::info
Write a version of the inner product procedure described in Problem 5.13 that uses 6 × 1a loop unrolling to enable greater parallelism. Our measurements for this function give a CPE of 1.10 for integer data and 1.05 for floating-point data.
:::
```c=
void inner6x1a(vec_ptr u, vec_ptr v, data_t *dest) {
long i;
long length = vec_length(u);
data_t *udata = get_vec_start(u);
data_t *vdata = get_vec_start(v);
data_t sum = (data_t) 0;
long limit = length - 5;
for (i = 0; i < limit; i+=6) {
sum = sum + (((udata[i] * vdata[i])
+ (udata[i + 1] * vdata[i + 1]))
+ ((udata[i + 2] * vdata[i + 2])
+ (udata[i + 3] * vdata[i + 3]))
+ ((udata[i + 4] * vdata[i + 4])
+ (udata[i + 5] * vdata[i + 5])));
}
for (; i < length; i++)
sum += udata[i] * vdata[i];
*dest = sum;
}
```
# Lista 13 (25.06.2020)
### Zadanie 1
:::info
Sprzętowa **translacja adresów** umożliwiła systemom operacyjnym wydajną implementację **izolacji procesów**, **stronnicowania na żądanie** (ang. demand paging), **wymiany do pamięci drugorzędnej** (ang. swapping) i **współdzielenia pamięci**. Jakie korzyści przynosi stosowanie powyższych mechanizmów? Przekonaj prowadzącego i słuchaczy posługując się przykładami. Należy użyć pojęć: **zbiór rezydentny** (ang. resident set) i **zbiór roboczy** (ang. working set).
:::
**translacja adresów** - proces w ktorym adres wirtualny jest tlumaczony na adres fizyczny.
**izolacja procesow** - metody zapewniajace, ze dany fragment pamieci nalezy do konkretnego procesu i zabraniajace innym procesom robienia do nich dostepow. Jest to bardzo wazny aspekt dla cyberbezpieczenstwa
**stronicowanie na żądanie** - strony sa wciagniete do pamieci dopiero w momencie kiedy sa 'dotkniete'. To znaczy, ze w momencie alokacji pamieci nie wciagamy jeszcze swiezo zaalokowanych stron do pamieci, czekamy z tym do momentu zrobienia dostepu. Jest to bardzo wazne poniewaz pozwala na ograniczenie danych wciagnietych przez proces do pamieci do zbioru roboczego bedacego malym podzbiorem calej pamieci przydzielonej dla programu.
**wymiana do pamieci drugorzednej** - fragmenty pamieci ktore nam sie juz nie przydadza zostaja przeniesione do pamieci drugorzednej, tym samym zwalniajac miejsce dla innych stron.
**wspoldzielenie pamieci** - korzystanie z tego samego bloku pamieci przez wiele roznych programow. Dzieki temu kazdy proces korzystajacy np. z libc nie musi wprowadzac do pamieci swojej instancji tego kodu. Kazdy proces moze korzystac z jednej i tej samej.
**zbiór rezydentny** - Pamiec przydzielona dla programu.
**zbiór roboczy** - Pamiec z ktorej program faktycznie korzysta. ( podzbior zbioru rezydentnego )
### Zadanie 2
:::info
Zakładamy taki sam model podsystemu pamięci jak na slajdach do wykładu „Virtual Memory: Systems” (strony 9–16). Powtórz proces translacji adresów i adresowania pamięci podręcznej dla adresów: 0x027c, 0x03a9 i 0x0040 zakładając poniższy stan **TLB**, pamięci podręcznej i **tablicy stron**.
Zawartość TLB:
Zbiór | | Tag | PPN | V | | Tag | PPN | V | | Tag | PPN | V | | Tag | PPN | V |
-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|
0 | | - | - | 0 | | 09 | 0D | 1 | | - | - | 0 | | 07 | 02 | 1 |
1 | | 03 | 2D | 1 | | - | - | 0 | | 02 | 17 | 1 | | - | - | 0 |
2 | | - | - | 0 | | - | - | 0 | | - | - | 0 | | - | - | 0 |
3 | | - | - | 1 | | 03 | 0D | 1 | | 0A | 34 | 1 | | - | - | 0 |
Zawartość pamięci podręcznej:
Idx | | Tag | V | | B0 | B1 | B2 | B3
-|-|-|-|-|-|-|-|-|
0 | | 19 | 1 | | 99 | 11 | 23 | 11
1 | | - | 0 | | - | - | - | -
2 | | 1B | 1 | | 00 | 02 | 04 | 08
3 | | - | 0 | | - | - | - | -
4 | | 32 | 1 | | 43 | 6D | 8F | 09
5 | | 0D | 1 | | 36 | 72 | F0 | 1D
6 | | - | 0 | | - | - | - | -
7 | | 16 | 1 | | 11 | C2 | DF | 03 |
8 | | 24 | 1 | | 3A | 00 | 51 | 89
9 | | - | 0 | | - | - | - | -
A | | 2D | 1 | | 93 | 15 | DA | 3B
B | | - | 0 | | - | - | - | -
C | | - | 0 | | - | - | - | - |
D | | 16 | 1 | | 04 | 96 | 34 | 15
E | | 13 | 1 | | 83 | 77 | 1B | D3
F | | 09 | 1 | | DE | 01 | C4 | 32
Zawartość tablicy stron:
VPN | PPN | V
-|-|-
00 | 28 | 1
01 | - | 0
02 | 33 | 1
03 | 02 | 1
04 | - | 0
05 | 16 | 1
06 | - | 0
07 | - | 0
08 | 13 | 1
09 | 17 | 1
0A | 09 | 1
0B | - | 0
0C | - | 0
0D | 2D | 1
0E | 11 | 1
0F | 0D | 1
:::
* 0x027c
0x027c = $00001001111100_2$
VPN - $00001001_2$ = 0x09
VPO - $111100_2$ = 0x3C
TLBI - $01_2$ = 0x1 (set)
TLBT - $000010_2$ = 0x02 (tag)
TLB Hit? Y
PPN - 0x17
Physical adress - $10111111100_2$
CO - $00_2$ = 0x0 (bajt)
CI - $1111_2$ = 0xF (indeks)
CT - $10111_2$ = 0x17 (tag)
MISS
* 0x03a9
0x03a9 = $00001110101001_2$
VPN - $00001110_2$ = 0x0E
VPO - $101001_2$ = 0x29
TLBI - $10_2$ = 0x2
TLBT - $000011_2$ = 0x03
TLB Hit? N
Page Fault? N
PPN - 0x11
Physical adress - $10001101001_2$
CO - $01_2$ = 0x1
CI - $1010_2$ = 0xA
CT - $10001_2$ = 0x11
MISS
* 0x0040
0x0040 = $00000001000000_2$
VPN - $000000001_2$ = 0x01
VPO - $000000_2$ = 0x00
TLBI - $01_2$ = 0x1
TLBT - $0000000_2$ = 0x00
TLB Hit? N
Page Fault? Y
### Zadanie 3
:::info
W tym zadaniu będziemy analizowali w jaki sposób system operacyjny musi aktualizować **tablicę stron** wraz z kolejnymi dostępami do pamięci głównej. Załóż, że strony są wielkości 4KiB, TLB jest **w pełni asocjacyjne** z zastępowaniem LRU. Najwyższa wartość pola LRU koduje najlepszego kandydata na **ofiarę** (ang. victim). Jeśli potrzebujesz **wtoczyć** (ang. swap-in) stronę z dysku użyj następnego numeru **ramki** (ang. page frame) większego od największego istniejącego w tablicy stron.
Dla poniższych danych podaj ostateczny stan TLB i tablicy stron po wykonaniu wszystkich dostępów do pamięci. Dla każdej operacji dostępu do pamięci wskaż czy było to trafienie w TLB, trafienie w tablicę stron, czy też **błąd strony**.
Początkowa zawartość tablicy stron:
VPN | Valid | PPN
-|-|-
00 | 1 | 05
01 | 0 | dysk
02 | 0 | dysk
03 | 1 | 06
04 | 1 | 09
05 | 1 | 0B
06 | 0 | dysk
07 | 1 | 04
08 | 0 | dysk
09 | 0 | dysk
0A | 1 | 03
0B | 1 | 0C
0C | 0 | brak
Początkowa zawartość TLB:
Valid | Tag | LRU | PPN
-|-|-|-
1 | 0B | 0 | 0C
1 | 07 | 1 | 04
1 | 03 | 2 | 06
0 | 04 | 3 | 09
Ciąg dostępów do pamięci:
Adres |
-|
123d |
08b3 |
365c |
871b |
bee6 |
3140 |
c049 |
:::
**tablica stron** - struktura danych używana przez mechanizmy wirtualizacji pamięci do przechowywania sposobu odwzorowania adresów pamięci logicznej (wirtualnej) w adresy pamięci fizycznej.
**TLB w pełni asocjacyjne** - TLB w którym cache każdego adresu możemy zapisać w dowolnym miejscu
**ofiara** (victim) - wpis w tablicy który usuwamy
**wtoczenie** (swap-in) - proces zapisywania strony do pamięci podręcznej po błędzie strony
**ramka**(page frame) - fizyczny blok pamięci trzymający strony
**błąd strony** - próba odczytania strony która nie jest w ramie
Skoro strony mają 4KiB to mamy 4 bity VPN i $log_2(4KiB)=12$ bitów offsetu.
### Dostępy
| Adres | VPN | TLB? | PPN |
|:-----:|:---:|:----:|:-------------------:|
| 123d | 01 | nie | page-fault dysk->0D |
| 08b3 | 00 | nie | 05 |
| 365c | 03 | nie | 06 |
| 871b | 08 | nie | page-fault dysk->0E |
| bee6 | 0B | nie | 0C |
| 3140 | 03 | tak | 06 |
| c049 | 0C | nie | błąd |
### Końcowe wartości
#### Tablica stron
| VPN | Valid | PPN |
|:---:|:-----:|:----:|
| 00 | 1 | 05 |
| 01 | 1 | 0D |
| 02 | 0 | dysk |
| 03 | 1 | 06 |
| 04 | 1 | 09 |
| 05 | 1 | 0B |
| 06 | 0 | dysk |
| 07 | 1 | 04 |
| 08 | 1 | 0E |
| 09 | 0 | dysk |
| 0A | 1 | 03 |
| 0B | 1 | 0C |
| 0C | 0 | brak |
#### TLB:
| Valid | Tag | LRU | PPN |
|:-----:|:---:|:---:|:---:|
| 1 | 0B | 1 | 0C |
| 1 | 03 | 0 | 06 |
| 1 | 00 | 2 | 05 |
| 1 | 01 | 3 | 0D |
### Zadanie 4
:::info
Niech system posługuje się 32-bitowymi adresami wirtualnymi, rozmiar strony ma 4KiB, a rozmiar wpisu tablicy stron zajmuje 4 bajty. Dla procesu, który łącznie używa 1GiB swojej przestrzeni adresowej podaj rozmiar tablicy stron: (a) jednopoziomowej, (b) dwupioziomowej, gdzie katalog tablicy stron ma 1024 wpisy. Dla drugiego przypadku – jaki jest maksymalny i minimalny rozmiar tablicy stron?
:::
#### Jednopoziomowa
Po prostu odcinamy od adresu bity potrzebne na offset i mnożymy ilość wpisów przez ich rozmiar.
$2^{32}/2^{12}*2^{2}=2^{22} = 4MiB$
#### Dwupoziomowa
Ilość wpisów w sumie: $2^{32}/2^{12}=2^{20}$
Ilość wpisów dla jednego poziomu: $2^{10}$
Wielkość wpisów w 1GiB przestrzeni adresowwej: $2^{18}$
##### Maksymalny
Mamy 1024 wpisy w katalogu tablic, czyli $2^{10}$
Zakładając, że układamy wpisy w kolejnych tablicach stron w katalogu, sumujemy rozmiar katalogu z rozmiarem zapełnionych katalogów, czyli (2^{10} + 2^{10}*2^{10}) razy rozmiar jednego wpisu.
Finalnie otrzymujemy działanie $(2^{10} + 2^{10}*2^{10}) * 4B = 4KiB + 4MiB$
##### Minimalny
Bierzemy ponownie rozmiar samych wpisów katalogu: $2^{10} = 4KiB$
W tym przypadku zakładamy, że są wypełnione w najoptymalniejszy spobób. Więc wszystkie zmieszczą się w $2^8$ wpisach w katalogu.
Otrzymujemy wzór $4KiB + 2^{8}*4KiB = 4Kib + 1MiB$
### Zadanie 5
:::info
Wiemy, że pamięć podręczna TLB jest niezbędna do przeprowadzania szybkiej translacji adresów. Czemu, w najogólniejszym przypadku, należy wyczyścić zawartość TLB przy przełączaniu przestrzeni adresowych? Jak można uniknąć tej kosztownej operacji?
Wskazówka: Rozważ wprowadzenie identyfikatorów przestrzeni adresowych (ASID), tak jak w architekturze MIPS.
:::
Zawartość TLB jest czyszczona, ponieważ część dostępów do TLB staje się nieważna.
Na przykład w mikroprocesorze Alpha 21264 korzysta się z numeru przestrzeni adresowej (ASN) i tylko dostępy z ASN pasującym do aktualnego procesu są uznawane za ważne. Natomiast w Intel Pentium Pro flagi PGE (page global enable) w rejestrze kontrolnym CR4 i "global (G) flag of a page-directory or page-table entry" (ciężko mi było przetłumaczyć) pomagają nam ustalić które strony są często używane i uchronić je przed usunięciem.
Źródło:
https://en.wikipedia.org/wiki/Translation_lookaside_buffer#Address-space_switch
### Zadanie 6
:::info
Wyznacz maksymalny rozmiar zbioru roboczego procesu, dla którego nie będzie on generował nowych chybień w TLB (ang. TLB reach)? Rozważ wariant pesymistyczny i optymistyczny dla czterodrożnego TLB o 64 wpisach. Jak zmieni się oszacowanie, jeśli zezwolimy na używanie dużych stron (ang. huge pages) o wielkości 4MiB?
:::
***Zbiór roboczy*** to ta część przydzielonej pamięci adresowej procesu która jest faktycznie wykorzystywana.
skoro TLB jest 4-drożne to w każdym zbiorze znajdują się 4 wpisy tablicy stron, a skoro wszystkich wpisów jest 64 to zbiorów jest $64/4 = 16$.
Strony domyślnie mają po 4KiB.
Optymistyczny warniant to taki, w którym nie mamy żadnych konfliktów i każdy wpis jest używany. Skoro używalibyśmy wszystkich 64 wpisów, a każda strona ma po 4KiB to mamy łącznie $64*4KiB = 256KiB$
Pesymistyczny wariant to taki, w którym wszystko trafiło do jednego zbioru wtedy mamy tylko 4 wpisy, czyli $4*4KiB = 16KiB$
Dla dużych stron strony zamiast 4KiB mają 4MiB
W przypadku optymistycznym mamy
$64*4MiB = 256MiB$
w Pesymistycznym
$4*4MiB = 16MiB$
### Zadanie 7
:::info
Opisz dokładnie pola deskryptorów stron (ang. page table entry ) i deskryptorów katalogów stron (ang. page directory entry ) dla architektury x86-64. Które z bitów pomocniczych:
• opisują politykę zarządzania pamięcią podręczną dla zawartości strony,
• wspomagają algorytmy zastępowania stron pamięci wirtualnej,
• określają uprawnienia dostępu do zawartości strony (w tym tryb pracy procesora).
Wskazówka: Przeczytaj §9.7.1 z podręcznika. Szczegóły można znaleźć w §4.5 wolumenu 3 dokumentacji procesorów Intel.
:::
Page directory entry:
Page table entry:
* Bit opisujący politykę zarządzania pamięcią podręczną: WT
* Bit wspomagający algorytm zastępowania stron: A
* Bity określające uprawnienie dostępu do strony: R/W, U/S, D, XD
### Zadanie 8
:::info
Na wykładzie przyjęliśmy, że translacja adresów jest wykonywana przed dostępem do pamięci podręcznej. Taki schemat określa się mianem pamięci podręcznej indeksowanej i znakowanej adresami fizycznymi (ang. physically-indexed, physically-tagged). Wyjaśnij jak wykonywać równolegle dostęp do TLB i pamięci podręcznej, stosując schemat pamięci indeksowanej wirtualnie i znakowanej fizycznie.
Wskazówka: Posłuż się slajdem 25 do wykładu „Virtual Memory: Systems”, ale wytłumacz to szczegółowo!
:::
W schemacie rozważanym na wykładzie dostęp do pamięci podręcznej L1 wykonywany jest dopiero po translacji adresów. Oznacza to, że płacimy sume czasów tych operacji. Przyspieszymy to, wykonując te operacje jednocześnie.
Aby móc dokonać dostępu do cache bez uprzedniego tłumaczenia adresów, posłużymy się schematem “Virtually indexed, physically tagged”. Użyjemy adresu fizycznego dla tagu. Konkretnie, weźmiemy bity z VPO i użyjemy ich jako offset i index dla pamięci podręcznej. Aby było to możliwe offset i index pamięci cache muszą mieć łącznie tyle samo bitów co PPO, a bity VPO muszą być takie same co bity PPO. Wtedy, kiedy TLB będzie zajmowało się translacją adresów, jednocześnie, bez tłumaczenia, możemy uzyskać dostęp do pamięci podręcznej, co istotnie przyspiesza cały proces.
###### tags: `github` `ask`
Sign in with Wallet
Connect another wallet