# SO Lista 7
## Zadanie 1
### Memory-mapped files
Tworzymy region w pamięci i wklejamy tam content jakiegoś pliku albo jego część
### Anonymous mappings
pusty szablon inicjalizowany 0
### Czym się różni odwzorowanie prywatne od dzielonego?
#### Prywatne
niewidoczne dla innych procesów. Dalej dzielą tą samą pamięć ale kernel nic nie robi póki nie spróbujemy do niej pisać. Wtedy kopiuje mapping i ustawia rw- (COW)
#### Dzielona
zmieniamy widoczność dla innych procesów ztym samym mappingiem
### Czy pamięć obiektów odwzorowanych prywatnie może być współdzielona?
Tak, np. po forku
### Czemu można tworzyć odwzorowania plików urządzeń blokowych w pamięć, a znakowych nie?
Bo przy urządzeniach blokowych to ma sens.
Np. mamy odpaloną grę i w jej procesie mamy odwzorowanie w pamięci karty graficznej i możemy z tego korzystać do szybkiego IPC (Inter process communication).
Znakowe to są urządzenia transmisji więc nie ma sensu.
Nie wiadomo jak zinterpretować odwzorowanie transmisji w pamięci.
## Zadanie 2
1. <b>Private mapping file</b>
głównym zastosowaniem jest zainicjalizowanie obszaru pamięci z zawartości pliku, np. inicjalizacja sekcji text lub data procesu z pliku wykonywalnego lub biblioteki współdzielonej.
2. <b>Private mapping anonymous</b>
alokacja nowej pamięci (pustej, tzn. wypełnionej zerami) dla procesu, np. używając malloc(3), który wykorzystuje mmap(2).
3. <b>Shared mapping file</b>
<ul>
<li>przy I/O dla plików dostarczana jest alternatywa dla używania read(2) oraz write(2)</li>
<li>umożliwienie szybkiej komunikacji międzyprocesowej (IPC) dla procesów niepowiązanych ze sobą</li>
</ul>
4. <b>Shared mapping anonymous</b>
umożliwienie szybkiej komunikacji międzyprocesowej (IPC) dla procesów powiązanych ze sobą
### Jak je utworzyć z użyciem nmap(2)?
1. MAP_PRIVATE i fd do pliku
2. MAP_PRIVATE | MAP_ANONYMOUS (fd jest ignorowany)
3. MAP_SHARED i fd do pliku
4. MAP_SHARED | MAP_ANONYMOUS
### Co się dzieje z odwzorowaniami po wywołaniu fork(2)?
Każdy segment w parent i child jest ustawiany jako read only, copy-on-write. Kiedy wleci protection fault, handler zobaczy że <u>cow</u> `(rw-)?` jest ON więc stworzy nowy mapping i przepisze page table entries na niego
### Czy wywołanie execve(2) tworzy odwzorowania prywatne czy dzielone?
private COW (CSAPP 874 pdf) (ale w sumie shared jednak też)
### W jaki sposób jądro systemu automatycznie zwiększa rozmiar stosu do ustalonego limitu?
Patrz man nmap MAP_GROWSDOWN
RLIMIT_STACK -> max rozmiar stacka
### Kiedy jądro wyśle sygnał SIGBUS do procesu posiadającego odwzorowanie pliku w pamięć?
Kiedy wyjdziemy poza zmapowany blok, ale wciąż będziemy w zmapowanym segmencie. Np. kernel ostrzeże nas, że tam już nie ma pliku który odwzorowaliśmy.
## Zadanie 3
### Przy pomocy polecenia wyświetl zużycie pamięci procesu wykonującego kod X-serwera.
`cat /proc/$(pgrep Xorg)/status | egrep -E 'Vm|Rss'`
### Na podstawie podręcznika proc(5) wyjaśnij znaczenie poszczególnych pól.
Odpal man proc i pokaż pola z komendy
### Przypomnij jaka jest różnica między zbiorem roboczym i rezydentnym procesu.
#### Zbiór roboczy
zbiór adresów na którym aktualnie pracuje program
#### Zbiór rezydentny
część address space procesu która aktualnie znajduje się w pamięci np. skasowane pliki, fork() itd. Więc pamięć zostanie policzona wielokrotnie
### Algos
```python=
import subprocess
import os
def get_values(path):
print(path)
res1 = subprocess.check_output(f'cat {path} | grep VmSize', shell=True).decode('utf-8')
res2 = subprocess.check_output(f'cat {path} | grep VmRSS', shell=True).decode('utf-8')
return int(res1.split()[1]), int(res2.split()[1])
all_vm_size, all_vm_rss = 0, 0
for p in os.listdir('/proc/'):
try:
r1, r2 = get_values(f'/proc/{p}/status')
all_vm_size += r1
all_vm_rss += r2
except:
continue
print(f'\n\nVmSize = {all_vm_size}kb\nVmRSS = {all_vm_rss}kb')
```
### Czemu ta druga wartość nie pokrywa się z rozmiarem używanej pamięci raportowanym przez polecenie «vmstat -s»?
Różnice wynikają z tego, że zbiory rezydentne nie są rozłączne
## Zadanie 4
### Opisz page fault
### W jakiej sytuacji wystąpi pomniejsza usterka strony (ang. minor page fault) lub poważna usterka strony (ang. major page fault)?
#### Minor page fault
Kiedy kernel szuka strony o którą prosi proces, ale strona jest juz w pamięci, bo inny proces już ją sprowadził
#### Major page fault
Kiedy strona musi zostać sprowadzona z dysku
### Jakie informacje musi dostarczyć procesor, żeby można było wykonać procedurę obsługi błędu stronicowania?
1. virtual address (który wywołał page fault)
2. adres instrukcji
3. typ accesu (r/w), czy to instruction fetch itd.
### Do czego służą struktury jądra «mm_struct::pgd» i «mm_struct::mmap»
#### «mm_struct::pgd»
pointer na tablicę stron, tablica stron jest tworzona na podstawie opisu segmentów z mmap
#### «mm_struct::mmap»
pointer na listę segmentów pamięci procesu, każdy segment jest typu `vm_area_struct`
### Kiedy jądro wyśle procesowi sygnał SIGSEGV z kodem «SEGV_MAPERR» lub «SEGV_ACCERR»?
#### «SEGV_MAPERR»
Kiedy odwołamy się do niezmapowanego segmentu pamięci
#### «SEGV_ACCERR»
Kiedy nie mamy uprawnień żeby coś zrobić np. nadpisać .text
### Jaką rolę pełni w systemie bufor stron (ang. page cache)?
cache dla stron znajdujących się w nieużywanych częściach RAM. Motywacja jest taka, że dyski są wolne i lepiej jest już podpiąc stronę, która jest już w ramie. Daje nam to nie tylko szybszy handling page faultów, ale też zapis. Brudne storny są oznaczane bietm dirty.
## Zadanie 5
### Kopiowanie przy zapisie
technika która mówi o tym, żeby prywatne mappingi były współdzielone z innymi, ale kopiowane w chwili kiedy próbujemy wykonac do niej zapis
### Co jądro przechowuje w strukturze «vm_area_struct»?
<ul>
1. <b>«vm_prot» -></b> uprawnienia dostępu r/w
2. <b>«vm_flags» -></b> różne flagi dotyczące np. czy mapping jest shared czy private.
3. <b>«vm_start/vm_end» -></b> początek/koniec mappingu
4. <b>«vm_nex/vm_prev» -></b> następny/poprzedni mapping
5. <b>pgd -></b> pointer na tablicę stron
</ul>
### Jak jądro zmodyfikuje «mm_struct::pgd»?
#### w trakcie pierwszego odczytu ze strony p należącej do D
Read spowoduje page fault i pod podane PTE w pgd podepniemy tę stronę
#### w trakcie pierwszego zapisu
Write wywoła protection fault, bo CPU będzie miał w PTE read only. Wezwie kernel, a ten zobaczy, że jest COW w stronie (w danym segmencie), więc skopiuje ją, wstawi w PTE R/W i przepisze tak, żeby wskazywała na nowo utworzoną stronę.
### Co jądro musi zrobić z tablicą stron procesu, który zawołał fork(2)?
W dziecku i rodzicu wszystkie strony ustawia na read only. Tablice stron obu procesów wskazują na to samo, ale jest też ustawiony COW, więc i tak będzie to kopiowane przy write
## Zadanie 6
### Stronnicowanie na żądanie
leniwe sprowadzanie stron z dysku/cache
### Czy mamy gwarancję, że program nie zobaczy modyfikacji zawartości pliku, które zostaną wprowadzone po utworzeniu tego odwzorowania?
Nie, bo dopiero przy dostępie do mappingu sprowadzimy plik z dysku, ale między wywołaniem i dostępem możemy doniego pisać. Plik może być tez w cache, wtedy nie zobaczymy zmian.
Nie jest powiedziane, że będziemy ściągać cały plik naraz, możemy brać tylko fragment (ja chyba nie rozumiem ocb, że jak będziemy brać fragmenty to mogą być modyfikacje? Za dużo myślenia)
### Co złego mogłoby się stać, gdyby system operacyjny pozwolił modyfikować plik wykonywalny, który jest uruchomiony?
Zauważmy, że jak jakiś proces zmapuje plik, ale nie cały np. część segmentu .text, to moglibyśmy zmodyfikować jakąś funckję w tym programie i narobić szkód.
Np. crash, wykonanie swojego kodu(jako root), nieprzewidywalne zachowanie programu
## Zadanie 7
```c
...
/* TODO: If there is more to sort than FORKSORT_MIN start a subprocess. */
if(right - left + 1 > FORKSORT_MIN){
if((pid = Fork())) return pid;
}
if (left < right) {
...
int status;
/* TODO: Wait for possible children and exit if created a subprocess. */
if(pid_left > 0) Waitpid(pid_left, &status, 0);
if(pid_right > 0) Waitpid(pid_right, &status, 0);
if(pid == 0) exit(EXIT_SUCCESS);
}
}
return pid;
}
...
/* TODO: Allocate table... */
long *table = Mmap(NULL, size, PROT_READ | PROT_WRITE, MAP_ANONYMOUS | MAP_SHARED, -1, 0);
...
```
> forksort simple to po prostu forksort bez fork'a, więc wszystko się dzieje w jednym procesie.
>
forksort_simple:
```c
...
/* TODO: If there is more to sort than FORKSORT_MIN start a subprocess. */
/*
if(right - left + 1 > FORKSORT_MIN){
if((pid = Fork())) return pid;
}*/
if (left < right) {
...
int status;
/* TODO: Wait for possible children and exit if created a subprocess. */
if(pid_left > 0) Waitpid(pid_left, &status, 0);
if(pid_right > 0) Waitpid(pid_right, &status, 0);
if(pid == 0) exit(EXIT_SUCCESS);
}
}
return pid;
}
...
/* TODO: Allocate table... */
long *table = Mmap(NULL, size, PROT_READ | PROT_WRITE, MAP_ANONYMOUS | MAP_SHARED, -1, 0);
...
```
różnice widać od razu. turnaround time to czas pomiędzy wejściem procesu a jego wyjściem, czyli po prostu real time, a cpu time to zgaduję że user i sys (proszę mnie sprawdzić).
```c
#include "csapp.h"
#define ENT_LENGTH 48
#define DB_MODE (S_IWUSR | S_IRUSR | S_IRGRP | S_IROTH)
#define DB_PROT (PROT_READ | PROT_WRITE)
typedef enum { DB_QUERY, DB_INSERT } op_t;
typedef char entry_t[ENT_LENGTH];
typedef struct db {
entry_t *entry;
ssize_t size;
char *name;
} db_t;
static bool db_action(db_t *db, const char *str, op_t op) {
/* Do not insert empty strings. Database doesn't store them. */
if (*str == '\0')
return op == DB_INSERT;
size_t len = strnlen(str, ENT_LENGTH);
int chain_len = max((db->size >> 14) - 1, 3);
uint32_t chain = jenkins_hash(str, len, HASHINIT);
for (int c = 0; c < chain_len; c++) {
size_t idx = (chain + c) % db->size;
if (!db->entry[idx][0] && op == DB_INSERT) {
strncpy(db->entry[idx], str, ENT_LENGTH);
printf("db->entry[%ld] db_action: %s\n",idx,db->entry[idx]);
return true;
}
if (strncmp(str, db->entry[idx], ENT_LENGTH) == 0)
return true;
}
return false;
}
#define db_query(db, key) db_action(db, key, DB_QUERY)
#define db_maybe_insert(db, key) db_action(db, key, DB_INSERT)
/* 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->name = (char *)malloc(strlen(name)+1);
strcpy(db->name,name);
db->size = size;
Ftruncate(fd,db->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);
}
/* Remove DB memory mapping and release associated memory. */
static void db_close(db_t *db) {
Munmap(db->entry, db->size * sizeof(entry_t));
free(db->name);
}
/* 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. */
db_close(new);
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;
}
/* Insert key into database and possibly increase DB size. */
static void db_insert(db_t *db, const char *str) {
while (!db_maybe_insert(db, str)) {
size_t size = db->size;
do {
size *= 2;
fprintf(stderr, "db_rehash: %ld -> %ld\n", db->size, size);
} while (!db_rehash(db, size));
}
}
/* Read a key from buffer and perform `mode` operation of the database. */
static char *consume_line(char *buf, db_t *db, op_t mode) {
/* Terminate string at new line character. */
char *end = strchr(buf, '\n');
if (end) {
if (buf < end && end[-1] == '\r')
end[-1] = '\0';
*end++ = '\0';
}
/* Skip if line is empty. */
if (*buf) {
if (mode == DB_INSERT)
db_insert(db, buf);
else if (mode == DB_QUERY)
puts(db_query(db, buf) ? "YES" : "NO");
}
/* Return pointer to next line or NULL. */
return end;
}
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. */
if (isatty(STDIN_FILENO)) {
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. */
struct stat file;
int n=0,i=0;
char buf[ENT_LENGTH + 1];
Fstat(STDIN_FILENO,&file);
char *stdin_mmap = Mmap(NULL,file.st_size,PROT_READ,MAP_PRIVATE,STDIN_FILENO,0);
while(stdin_mmap[n]!='\0'){
if(stdin_mmap[n]=='\n'){
buf[i] = '\0';
consume_line(buf,&db,mode);
i = 0;
}
else
buf[i++] = stdin_mmap[n];
n++;
}
Munmap(stdin_mmap,file.st_size);
}
msync(db.entry,db.size*sizeof(entry_t),MS_SYNC);
db_close(&db);
}
static noreturn void usage(int argc, char **argv) {
app_error("Usage: %s [-i|-q] [FILE]", argv[0]);
}
int main(int argc, char **argv) {
op_t mode = -1;
int opt;
while ((opt = getopt(argc, argv, "iq")) != -1) {
if (opt == 'i')
mode = DB_INSERT;
else if (opt == 'q')
mode = DB_QUERY;
else
usage(argc, argv);
}
if (optind >= argc || mode == -1)
usage(argc, argv);
doit(argv[optind], mode);
return 0;
}
```
Sign in with Wallet
Connect another wallet