# Ćwiczenia 7, grupa cz. 10-12, 1 grudnia 2022
###### tags: `SO22` `ćwiczenia` `pwit`
## Deklaracje
Gotowość rozwiązania zadania należy wyrazić poprzez postawienie X w odpowiedniej kolumnie! Jeśli pożądasz zreferować dane zadanie (co najwyżej jedno!) w trakcie dyskusji oznacz je znakiem ==X== na żółtym tle.
**UWAGA: Tabelkę wolno edytować tylko wtedy, gdy jest na zielonym tle!**
:::danger
| | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| ----------------------:| ----- | --- | --- | --- | --- | --- | --- | --- |
Miriam Bouhajeb | X | X | X | | | | | |
Kacper Chmielewski | X | X | X | X | | | | |
Jan Jankowicz | X | X | | | | | | |
Jakub Kaczmarek | | | | | | | | |
Jarosław Kadecki | X | X | X | X | | X | | |
Zuzanna Kania | | | | | | | | |
Julia Konefał | X | X | | | | | X | |
Daniel Sarniak | X | X | X | | | | X | |
Paweł Tkocz | X | X | | | | X | | |
Miłosz Urbanik | | | | | | | | |
Tomasz Wołczański | X | X | X | | | X | | |
Radosław Śliwiński | X | X | X | X | | X | | |
:::
:::info
**Uwaga:** Po rozwiązaniu zadania należy zmienić kolor nagłówka na zielony.
:::
## Zadanie 1
:::success
Autor: Miriam Bouhajeb
Odwzorowanie plików w pamięć (memory-mapped files) to odwzorowanie zawartości pliku w pamięci wirtualnej procesu. Zawartość pliku nie jest od razu kopiowana do pamięci operacyjnej, a jedynie dołączana jako nowy obszar do pamięci wirtualnej procesu. Plik może być wtedy traktowany jak ciągły obszar w pamięci procesu, dostępny poprzez bezpośrednie operacje pobrania i podstawienia wartości. Wszystkie modyfikacje dokonane w pamięci są później zapisywane w pliku na dysku.
Odwzorowanie pamięci anonimowej (anonymous mapping) to mapowanie, które nie ma odpowiadającego pliku, a strony mapowania są zainicjalizowane zerami.
Odwzorowanie prywatne - modyfikacje zawartości odwzorowania nie są widoczne dla pozostałych procesów, a dla odwzorowań plików nie są one zapisywane do dysku. Jądro dokonuje tego poprzez kopiowanie przy zapisie. Oznacza to że gdy proces próbuje zmodyfikować pamięć, to jądro tworzy nową kopię tej pamięci dla procesu. Jest to używane, gdyż zmiany nie mogą być widoczne dla innych procesów, więc przy ewentualnych zmianach robi się osobną kopię tylko dla konkretnego procesu.
Odwzorowanie dzielone - modyfikacje zawartości odwzorowania są widoczne dla innych procesów dzielących, ewentualnie są na koniec zapisywane do pamięci.
Pamięć obiektów odwzorowanych prywatnie może być współdzielona jeśli forkujemy proces. I nie widzimy modyfikacji
Urządzenia blokowe jak najbardziej mogą być mapowane do pamięci jak właśnie np partycja lub bufory ramki (część karty graficznej)
Odwzorowanie plików znakowych byłoby bez sensu z urządzeniami znakowymi bo tak naprawdę to korzystają one ze strumieni i powodowałoby to problemy.
:::
## Zadanie 2
:::success
Autor: Jan Jankowicz
:::
> Na podstawie opisu do [3, tabeli 49–1] podaj scenariusze użycia prywatnych i dzielonych odwzorowań plików w pamięć albo pamięci anonimowej. Pokaż jak je utworzyć z użyciem wywołania mmap(2).
**1. Prywatne odwzorowanie pliku**
Może być używane do wczytania pliku, który ma służyć tylko do odczytu. Przykładem takich plików mogą być współdzielone biblioteki.
```c=
int fd;
struct stat sb;
char *addr;
fd = open(file_name, O_RDONLY);
fstat(fd, &sb);
addr = mmap(NULL, sb.st_size, PROT_READ, MAP_PRIVATE, fd, 0);
```
**2.Prywatne odwzorowanie anonimowe**
Może być używane do zarezerwowania dodatkowej pamięci do użytku tylko przez jeden proces.
```c=
char *addr;
addr = mmap(NULL, length, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
```
**3. Dzielone odwzorowanie pliku**
Może być używane do zapisu do pliku, gdyż ewentualne zapisy do tak odwzorowanego pliku są automatycznie synchronizowane z dyskiem. Ponadto dzielone odwzorowanie pliku może służyć do komunikacji pomiędzy niepowiązanymi procesami. Dwa lub więcej procesów, które odwzorują ten sam plik w sposób współdzielony, będą mogły czytać zapisy innych procesów do tego pliku.
```c=
int fd;
struct stat sb;
char *addr;
fd = open(file_name, O_RDWR);
fstat(fd, &sb);
addr = mmap(NULL, sb.st_size, PROT_READ | PROT_WRITE, MAP_SHARED, fd, 0);
```
**4. Dzielone odwzorowanie anonimowe**
Może być używane do komunikacji pomiędzy powiązanymi procesami jak np. rodzic-dziecko, które w wyniku forka współdzielą te same obszary pamięci, w tym tej anonimowej. Przykładowo zapis do takiej pamięci wykonany przez dziecko jest widoczny przez proces rodzica.
```c=
char *addr;
addr = mmap(NULL, length, PROT_READ | PROT_WRITE, MAP_SHARED | MAP_ANONYMOUS, -1, 0);
```
---
> Co się dzieje z odwzorowaniami po wywołaniu fork(2)?
W wyniku wywołania forka dziecko dziedziczy odwzorowania rodzica, które odnoszą się dla obu procesów do tych samych miejsc w pamięci fizycznej.
Dodatkowo w oryginalnym procesie (rodzic) w tablicy stron wszystkie bloki, które należą do segmentów/mapowań prywatnych z uprawnieniami do odczytu i zapisu, zamieniamy na tylko do odczytu, a w obu procesach wszystkie segmenty prywatne zostają oznaczone flagą 'copy on write'.
---
> Czy wywołanie execve(2) tworzy odwzorowania prywatne czy dzielone?
Wywołanie execve tworzy odwzorowania prywatne (np. stos procesu).
---
> W jaki sposób jądro systemu automatycznie zwiększa rozmiar stosu do ustalonego limitu?
Stos jest tworzony mmapem z flagą MAP_GROWSDOWN, która zapewnia automatyczne zwiększanie przydzielonej pamięci.
> MAP_GROWSDOWN
> This flag is used for stacks. It indicates to the kernel
> virtual memory system that the mapping should extend
> downward in memory. The return address is one page lower
> than the memory area that is actually created in the
> process's virtual address space. Touching an address in
> the "guard" page below the mapping will cause the mapping
> to grow by a page. This growth can be repeated until the
> mapping grows to within a page of the high end of the next
> lower mapping, at which point touching the "guard" page
> will result in a SIGSEGV signal.
---
> Kiedy jądro wyśle sygnał SIGBUS do procesu posiadającego odwzorowanie pliku w pamięć?
Załóżmy, że pewien proces posiada odwzorowanie pliku, które wykracza poza jego rozmiar zaokrąglony w górę do wielkości bloku. W takiej sytuacji mamy do czynienia z blokami pamięci, wewnątrz których żaden bajt nie odnosi się do zawartości pliku. Próba odwołania się do obszaru pamięci zawartej w takim bloku spowoduje wysłanie sygnału SIGBUS do procesu posiadającego to odwzorowanie.
## Zadanie 3
:::success
Autor: Daniel Sarniak
VmPeak: Szczytowy rozmiar pamięci wirtualnej.
VmSize: Rozmiar pamięci wirtualnej
VmLck: Zablokowany rozmiar pamięci
VmPin: Są to strony, których nie można przenieść, ponieważ coś musi mieć bezpośredni dostęp do pamięci fizycznej.
VmHWM: Szczytowy rozmiar zestawu rezydentnej
VmRSS:Resident set size
RssAnon: Size of resident anonymous memory
RssFile: Size of resident file mappings
RssShmem: Size of resident shared memory
VmData: Size of data
VmStk: Size of stack
VmExe: Size of text segments
VmLib: Shared library code size.
VmPTE: Page table entries size
VmSwap: Swapped-out virtual memory size by anonymous private pages
**Zbiór rezydentny**
Jest to miara tego, ile pamięci proces zużywa w naszej fizycznej pamięci RAM, aby załadować wszystkie strony po jego wykonaniu.
RSS nie jest dokładną miarą całkowitego zużycia pamięci przez procesy, ponieważ nie obejmuje pamięci zużywanej przez biblioteki. Z drugiej strony te same biblioteki współdzielone mogą być powielane i liczone w różnych procesach.
**Zbiór roboczy**
To ile pamięci potrzebuje program do pracy
```python=
import psutil
def sum_mem():
sumVmSize = 0
sumVmRss = 0
# Iteruje po wszytskich uruchomionych rocesach
for id, proc in enumerate(psutil.process_iter()):
try:
# przykladowa wartosc mem_info: pmem(rss=12709888, vms=34197504, shared=6815744, text=2830336, lib=0, data=7221248, dirty=0)
mem_info = proc.memory_info()
processVmSize = mem_info[1]
processVmRss = mem_info[0]
sumVmSize += processVmSize
sumVmRss += processVmRss
# wypisuje wszystkie procesy w formacie id-pid-name-vmsize-vmrss
# nie potrzebne ale wygodne do sprawdzania
print(id, ": [", proc.pid, "]", proc.name(), " ::: ", "VmSize = ",str(int(processVmSize/1024)) + " K", " VmRSS = ",str(int(processVmRss/1024)) + " K")
except (psutil.NoSuchProcess, psutil.AccessDenied, psutil.ZombieProcess):
pass
ret1 = str(int(sumVmSize/1024)) + " K"
ret2 = str(int(sumVmRss/1024)) + " K"
return {"VmSize" : ret1, "RssSize" : ret2}
if __name__ == "__main__":
print(sum_mem())
```
:::
## Zadanie 4
:::success
Autor: Kacper Chmielewski
1. Jeśli fault_prot == vm_prot, to jest zwracany normalny błąd stronicowania.
2. Jeśli vm_addr != fault_addr to zwracany sie SIGSEGV z flagą SEGV_MAPPER (segmentation fault).
3. Jeśli vm_addr się zgadza, ale vm_prot ma uprawnienia r x, a chcielibyśmy wypisać to jest wywoływany SIGSEGV z flagą SEGV_ACCERR (protection exception).
```c=
struct mm_struct {
struct {
struct vm_area_struct *mmap; /* list of VMAs */
struct rb_root mm_rb;
u64 vmacache_seqnum; /* per-thread vmacache */
#ifdef CONFIG_MMU
unsigned long (*get_unmapped_area) (struct file *filp,
unsigned long addr, unsigned long len,
unsigned long pgoff, unsigned long flags);
#endif
unsigned long mmap_base; /* base of mmap area */
unsigned long mmap_legacy_base; /* base of mmap area in bottom-up allocations */
#ifdef CONFIG_HAVE_ARCH_COMPAT_MMAP_BASES
/* Base addresses for compatible mmap() */
unsigned long mmap_compat_base;
unsigned long mmap_compat_legacy_base;
#endif
unsigned long task_size; /* size of task vm space */
unsigned long highest_vm_end; /* highest vma end address */
pgd_t * pgd;
```
Pomniejsza usterka strony zachodzi gdy pamięc jest dzielona przez różne procesy i strona została już załadowana dla innego procesu albo usunięta ze zbioru roboczego, ale nie została zapisana na dysk.
Poważna usterka strony występuje wtedy, kiedy stronę trzeba pobrać z dysku.
Bufor stron przyspiesza odczyty i zapisy na dysku, w taki sposób, że w momencie zapisu, dane są zmieniane tylko w buforze, a na dysk są przenoszone funkcjami sync i fsync. Odczyt jest przyspieszony w taki sposób, że w tym buforze zapisane są już raz wczytane dane, więc w razie kolejnego wywołania wczytania danych, zostane one wczytane z buforu, a nie dysku.
:::
## Zadanie 5
:::danger
Autor: dodeklarować
:::
## Zadanie 6
:::success
Autor: Jarosław Kadecki
Program nie zobaczy modyfikacji zawartości pliku ponieważ odwzorowanie jest prywatne.
Jeśli w trakcie działania programu niezaładowana strona zostanie zedytowana to w momencie pobrania jej zawartości nasz proces zauważy zmianę.
Dla open(2)
Dla execve(2)
System wykorzystujący stronicowanie na żądanie leniwie pobiera strony, które są potrzebne do wykonania programu. Jeśli mielibyśmy możliwość edycji kodu programu, który nie jest jeszcze wykonywany, mogłoby dojść do pojawienia się sprzeczności w kodzie lub zagrożeń bezpieczeństwa.
:::
## Zadanie 7
:::success
Autor: Julia Konefał
```c=
#include "csapp.h"
static void InsertionSort(long table[], size_t left, size_t right) {
for (size_t pivot = left + 1; pivot <= right; pivot++) {
size_t insert = left;
while ((insert < pivot) && (table[insert] < table[pivot]))
insert++;
if (insert < pivot) {
size_t n = pivot - insert;
long tmp = table[pivot];
memmove(&table[insert + 1], &table[insert], n * sizeof(long));
table[insert] = tmp;
}
}
}
static void SwapElem(long table[], size_t i, size_t j) {
long tmp = table[i];
table[i] = table[j];
table[j] = tmp;
}
static size_t Partition(long table[], size_t begin, size_t end, long pivot) {
size_t left = begin;
size_t right = end;
while (left < right) {
while ((left < right) && (table[left] < pivot))
left++;
while ((left < right) && (table[right] >= pivot))
right--;
if (left < right)
SwapElem(table, left, right);
}
return left;
}
#define INSERTSORT_MAX 32
#define FORKSORT_MIN (1L << 18)
static int QuickSort(long table[], size_t left, size_t right) {
pid_t pid_left = -1, pid_right = -1, pid = -1;
//tutaj
if (right - left > FORKSORT_MIN) {
pid = fork();
}
if (pid > 0) return pid;
if (left < right) {
if (right - left <= INSERTSORT_MAX) {
InsertionSort(table, left, right);
} else {
size_t pivot = left + random() % (right - left + 1);
size_t split = Partition(table, left, right, table[pivot]);
if (left == split) {
SwapElem(table, left, pivot);
split++;
} else {
pid_left = QuickSort(table, left, split - 1);
}
pid_right = QuickSort(table, split, right);
// tutaj
if (pid_left != -1) waitpid(pid_left, NULL, 0);
if (pid_right != -1) waitpid(pid_right, NULL, 0);
if (pid == 0) exit(0);
}
}
return pid;
}
#define NELEMS (1L << 26)
int main(void) {
/* Table size in bytes must be divisible by page size. */
size_t size = NELEMS * sizeof(long);
assert((size & (getpagesize() - 1)) == 0);
/* Initialize PRNG seed. */
struct timeval tv;
gettimeofday(&tv, NULL);
srandom(tv.tv_usec);
// tutaj
long *table;
table = mmap(NULL, NELEMS*sizeof(long),PROT_READ | PROT_WRITE,MAP_ANONYMOUS | MAP_SHARED,-1, 0);
/* ... and fill it in with random elements. */
for (size_t i = 0; i < NELEMS; i++)
table[i] = random();
/* Sort it using hybrid algorithm... */
if (QuickSort(table, 0, NELEMS - 1) > 0)
Wait(NULL);
/* ... and verify if the table is actually sorted. */
long prev = LONG_MIN;
for (size_t i = 0; i < NELEMS; i++) {
assert(prev <= table[i]);
prev = table[i];
}
return 0;
}
```
Prawo to skoncentrowane jest na zwiększeniu wydajności osiągniętej z usprawnienia obliczeń, które wpływają na proporcję P tych obliczeń, gdzie usprawnienie ma wzrost szybkości obliczeń S. Prawo Amdahla stanowi, że całkowity wzrost szybkości po zastosowaniu usprawnienia będzie wynosił:
$$\frac{1}{(1 - P) + \frac{P}{S}}$$
perf record ./forksort
```
Samples: 43K of event 'cycles:uppp', Event count (approx.): 29484544256
Overhead Command Shared Object Symbol
70.33% forksort forksort [.] Partition
9.43% forksort forksort [.] SwapElem
7.63% forksort forksort [.] InsertionSort
5.16% forksort libc-2.28.so [.] __memmove_avx_unaligned_erms
2.23% forksort libc-2.28.so [.] __random_r
2.07% forksort libc-2.28.so [.] __random
1.08% forksort forksort [.] QuickSort
1.05% forksort forksort [.] main
0.56% forksort [unknown] [k] 0xffffffff8d600ae7
0.24% forksort forksort [.] random@plt
0.16% forksort forksort [.] memmove@plt
0.02% forksort libc-2.28.so [.] __run_fork_handlers
0.01% forksort ld-2.28.so [.] _dl_fixup
0.01% forksort libc-2.28.so [.] __run_exit_handlers
0.01% forksort ld-2.28.so [.] _dl_runtime_resolve_xsavec
0.01% forksort ld-2.28.so [.] strcmp
0.00% forksort ld-2.28.so [.] do_lookup_x
0.00% forksort libc-2.28.so [.] _IO_cleanup
0.00% forksort libc-2.28.so [.] __libc_start_main
0.00% forksort libc-2.28.so [.] __waitpid
0.00% forksort libc-2.28.so [.] __libc_fork
0.00% forksort libc-2.28.so [.] __call_tls_dtors
0.00% forksort ld-2.28.so [.] _dl_count_modids
0.00% forksort ld-2.28.so [.] check_match
0.00% forksort ld-2.28.so [.] _dl_fini
0.00% forksort ld-2.28.so [.] _dl_lookup_symbol_x
0.00% forksort libc-2.28.so [.] exit
0.00% forksort forksort [.] exit@plt
0.00% forksort ld-2.28.so [.] _dl_name_match_p
0.00% forksort forksort [.] Waitpid
0.00% forksort [unknown] [k] 0xffffffff8d60015f
```
Nie jesteśmy w stanie zrównoleglić procedur Partition, InsertionSort oraz SwapElem, bo nie są one zdefiniowane rekurencyjnie (w przeciwieństwie do QuickSort), który jest algorytmem dziel i zwyciężaj, więc całe zadanie dzielimy na mniejsze podproblemy.
P = 1 - 0.885 = 0.115
S = 10,594 / 2,801 = 3.78222
$$\frac{1}{(1 - P) + \frac{P}{S}} = \frac{1}{(1 - 0.115) + \frac{0.115}{3.7822}} = \frac{1}{0,915} = 1.092$$
:::
## Zadanie 8
:::success
Autor: Miłosz Urbanik
:::
`madvise(void *addr, size_t length, int advice)` - wywołanie systemowe, służące poprawie wydajności programu poprzez poinformowanie jądra o prawdopodobnym wzorcu użycia pamięci.
Kod zmodyfikowanych funkcji:
```c=
/* Open (`size` = 0) or create (`size` > 0) database from `name` file. */
static void db_open(db_t *db, const char *name, size_t size) {
assert(powerof2(size));
int fd = Open(name, O_RDWR | O_CREAT | (size ? O_EXCL : 0), DB_MODE);
if (size == 0) {
struct stat sb;
Fstat(fd, &sb);
size = sb.st_size / sizeof(entry_t);
if (size == 0)
size = 1;
}
/* TODO: Setup DB structure, set file size and map the file into memory.
Inform OS that we're going to read DB in random order. */
db->size = size;
db->name = strdup(name); // name był utworzony na stosie za pomocą alloca()
Ftruncate(fd, size * sizeof(entry_t));
db->entry = Mmap(NULL, db->size * sizeof(entry_t), DB_PROT, MAP_SHARED, fd, 0);
Madvise(db->entry, db->size * sizeof(entry_t), MADV_RANDOM);
Close(fd);
}
/* Attempt to increase size of database. */
static bool db_rehash(db_t *db, size_t new_size) {
assert(powerof2(new_size));
/* Create new database. */
db_t new[1];
char *name = alloca(strlen(db->name) + sizeof(".reshash") + 1);
strcpy(name, db->name);
strcat(name, ".rehash");
db_open(new, name, new_size);
/* Copy everything from old database to new database. */
/* TODO: Inform OS that we're going to read DB sequentially. */
Madvise(db->entry, db->size * sizeof(entry_t), MADV_SEQUENTIAL);
for (size_t i = 0; i < db->size; i++) {
if (!db_maybe_insert(new, db->entry[i])) {
/* Oops... rehashing failed. Need to increase db size and try again. */
/* TODO: Remove new database, since rehashing failed. */
Unlink(name);
Munmap(new->entry, new->size * sizeof(entry_t));
return false;
}
}
/* TODO Replace old database with new one, remove old database. */
Unlink(db->name);
Rename(new->name, db->name);
Munmap(db->entry, db->size * sizeof(entry_t));
db->entry = new->entry;
db->size = new->size;
free(new->name);
return true;
}
static void doit(const char *path, op_t mode) {
db_t db;
db_open(&db, path, 0);
/* If input file is a terminal device then use standard reading technique. */
/* TODO: Use fstat instead to handle pipes correctly. */
struct stat stat_buf;
Fstat(STDIN_FILENO, &stat_buf);
//isatty returns 0, if fd is a pipe
if (S_ISCHR(stat_buf.st_mode) || S_ISFIFO(stat_buf.st_mode)) {
char buf[ENT_LENGTH + 1];
while (fgets(buf, ENT_LENGTH + 1, stdin))
consume_line(buf, &db, mode);
} else {
/* TODO: Map stdin into memory, and read it line by line. */
void *buf = Mmap(NULL, stat_buf.st_size + 1, PROT_READ | PROT_WRITE,
MAP_PRIVATE, STDIN_FILENO, 0);
char *next_line = (char*) buf;
while((next_line = consume_line(next_line, &db, mode)));
Munmap(buf, stat_buf.st_size);
}
db_close(&db);
}
```
Porównanie wydajności programu, tworzenie bazy danych z pliku 5189454 haseł. CPU Ryzen 2600, 16GB RAM. Niestety z `madvise` jest gorzej.
Wersja z `madvise()`:
```
real 0m1.846s
user 0m1.132s
sys 0m0.706s
```
Bez `madvise()`:
```
real 0m1.596s
user 0m1.087s
sys 0m0.502s
```
Google Drive
Gist
Clipboard
Sign in with Wallet
