# Systemy operacyjne 2020 - listy zadań 7-9

## Lista zadań nr 7

Przed rozwiązywaniem zadań warto się zapoznać z podrozdziałami 3.3, 3.5, 10.7 z *Modern Operating Systems*, podrozdziałem 8.11 z *APUE* oraz z rozdziałami 38, 49 z *Linux Programming Interface*.

### Zadanie 1

:::info
Próba otworzenia [`open(2)`]() pliku wykonywalnego do zapisu, kiedy ten plik jest załadowany i wykonywany w jakimś procesie, zawiedzie z błędem `ETXTBSY`. Podobnie, nie możemy załadować do przestrzeni adresowej [`execve(2)`]() pliku, który jest otwarty do zapisu. Co złego mogłoby się stać w systemach implementujących **stronicowanie na żądanie** *(ang. demand paging)*, gdyby system operacyjny pozwolił modyfikować plik wykonywalny, który jest uruchomiony?
:::

**Stronicowanie na żądanie** *(ang. demand paging)* to sposób implementacji pamięci wirtualnej. Polega ono na sprowadzaniu stron do pamięci operacyjnej tylko wtedy, gdy jest ona potrzebna, dzięki czemu zmniejszana jest liczba operacji *I/O* oraz zapotrzebowanie na pamięć operacyjną, ponieważ nie są sporwadzane niepotrzebne strony.

W Linuxie pliki wykonywalne są stronicowane na żądanie w razie potrzeby. Plik wykonywalny na dysku staje się wtedy "pamięcią zapasową" dla procesu. Oznacza to, że nie można modyfikować pliku wykonywalnego na dysku, gdyż wpłynęłoby to na działanie uruchomionej aplikacji. Jeśli spróbowalibyśmy użyć `open(2)` na pliku wykonywalnym, który jest aktualnie uruchomiony, to zwrócony zostałby błąd `ETXTBSY` (text file busy). Podobnie w przypadku próby uruchomienia `exec(2)`, ten sam błąd może zostać zwrócony.

Gdyby system operacyjny stosujący stronicowanie na żądanie pozwolił na modyfikację uruchomionego pliku wykonywalnego, to niepotrzebne na początku strony nie byłyby ładowane do pamięci. Później, po wykonaniu zmian na uruchomionym programie, zostałyby wczytywane strony po modyfikacji, które prawdopodobnie kolidowałyby ze sobą, przez co program stałby się niezdatny do użytku, gdyż w każdym momencie mógłby się wywalić.

### Zadanie 2

:::info
Na podstawie §49.1 wyjaśnij słuchaczom różnicę między **odwzorowaniami plików w pamięć** *(ang. memory-mapped files)* i **odwzorowaniami pamięci anonimowej** *(ang. anonymous mappings)*. Jaką zawartością wypełniana jest pamięć wirtualna należąca do tychże odwzorowań? Czym różni się odwzorowanie **prywatne** od **dzielonego**? W jakim celu odwzorowania prywatne wykorzystują technikę **kopiowania przy zapisie**? Czemu odwzorowanie prywatne plików urządzeń blokowych ma niewiele sensu?

***Wskazówka:** Urządzenie blokowe to na przykład: pamięć karty graficznej albo partycja dysku.*
:::

**Odwzorowanie plików w pamięć** *(ang. memory-mapped files)* to zmapowanie obszaru pliku lub zasobu plikopodobnego do pamięci wirtualnej procesu. Po zmapowaniu można bezpośrednio się dostać do zawartości poprzez operowanie na jego bajtach w odpowiadającym obszarze pamięci. Strony są automatycznie ładowane z pliku, gdy zajdzie taka potrzeba.

**Odwzorowanie pamięci anonimowej** *(ang. anonymous mappings)* to mapowanie, które nie ma odpowiadającego pliku, a strony mapowania są zainicjalizowane zerami.

**Odwzorowanie prywatne (`MAP_PRIVATE`)** działa tak, że modyfikacje zawartości odwzorowania nie są widoczne dla innych procesów, a dla odwzorowań plików w pamięć - nie są zapisywane do pliku. Jądro dokonuje tego poprzez **kopiowanie przy zapisie**, a więc przy próbie modyfikacji zawartości strony przez proces, jądro tworzy nową, oddzielną kopię tej strony dla procesu. Ta technika wykorzystywana jest w bardzo prostym celu - zmiany nie mogą być widoczne dla innych procesów, a więc dopóki nie są wykonywane żadne zapisy, nie ma potrzeby kopiowania pamięci, a gdy jakiś proces spróbuje coś zapisać, zmiany będą widoczne tylko dla niego (na własnej kopii).

**Odwzorowanie dzielone (`MAP_SHARED`)** sprawia, że modyfikacje zawartości odwzorowania są widoczne dla innych procesów dzielących to odwzorowanie oraz w przypadku odwzorowań plików w pamięć, są zapisywane do plików. Pamięć odzworowana może być dzielona z odwzorowaniami w innych procesach (wpisy tabeli stron każdego procesu wskazują na to samo miejsce w pamięci RAM) na dwa sposoby: dwa procesy odwzorowują ten sam obszar pliku lub poprzez `fork(2)` (dziecko dziedziczy wszystkie odwzorowania rodzica).

Odwzorowanie prywatne plików urządzeń blokowych nie ma zbyt dużego sensu, gdyż chcemy aby zmiany wykonywane w plikach były widoczne np. na dysku (partycji).

### Zadanie 3

:::info
Na podstawie opisu do 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)`](). Co się z nimi dzieje po wywołaniu [`fork(2)`]()? Czy wywołanie [`execve(2)`]() tworzy odwzorowania prywatne czy dzielone? Jeśli wystartujemy $n$ instancji danego programu to ile razy jądro załaduje jego plik ELF do pamięci? Które z wymienionych odwzorowań mogą wymagać użycia **pamięci wymiany** *(ang. swap space)* i kiedy?
:::


Scenariusze użycia odwzorowań:

* **Prywatne odwzorowanie pliku**: 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.
* **Prywatne odwzorowanie anonimowe**: alokacja nowej pamięci (pustej, tzn. wypełnionej zerami) dla procesu, np. używając `malloc(3)`, który wykorzystuje `mmap(2)`.
* **Dzielone odwzorowanie pliku**:
1. przy *I/O* dla plików dostarczana jest alternatywa dla używania `read(2)` oraz `write(2)`,
2. umożliwienie szybkiej komunikacji międzyprocesowej (IPC) dla procesów niepowiązanych ze sobą
* **Dzielone odzworowanie anonimowe**: umożliwienie szybkiej komunikacji międzyprocesowej (IPC) dla procesów powiązanych ze sobą

Aby stworzyć odwzorowanie, należy użyć procedury `mmap(2)`. Zleca ona zmapowanie `length` bajtów przesuniętych o `offset` bajtów (`0` dla pamięci anonimowej) pliku zadanego przez deskryptor `fd` (`-1` dla pamięci anonimowej) do pamięci pod adres `addr` (jednak ten adres jest tylko propozycją i zwykle jest przekazywany jako `0`). Argument `prot` opisuje oczekiwany sposób ochrony pamięci (nie może być sprzeczny z trybem otwarcia pliku). Może on być równy `PROT_NONE` lub alternatywą jednego lub więcej znaczników `PROT_*`: `PROT_EXEC`, `PROT_READ`, `PROT_WRITE`, `PROT_NONE`. Parametr `flags` określa rodzaj mapowanego obiektu, opcje mapowania oraz czy modyfikacje powinny być prywatne czy współdzielone. Są to odpowiednio flagi `MAP_FIXED`, `MAP_SHARED`, `MAP_PRIVATE`, jednak sam Linux obsługuje jeszcze znaczniki niestandardowe (których jest znacznie więcej). Poniżej sygnatura funkcji, jak i sposób tworzenia odwzorowań:

// sygnatura funkcji
void *mmap(void *addr, size_t length, int prot, int flags,
           int fd, off_t offset);
           
// prywatne odwzorowanie pliku
void *private_file = mmap(NULL, [size], [prot], MAP_PRIVATE | MAP_FILE, [fd], [offset]);
// prywatne odwzorowanie anonimowe
void *private_anon = mmap(NULL, [size], [prot], MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
// dzielone odwzorowanie pliku
void *shared_file = mmap(NULL, [size], [prot], MAP_SHARED | MAP_FILE, [fd], [offset]);
// dzielone odwzorowanie anonimowe
void *shared_anon = mmap(NULL, [size], [prot], MAP_SHARED | MAP_ANONYMOUS, -1, 0);

Po wywołaniu `fork(2)` wszystkie odwzorowania są dziedziczone na zasadzie kopiowania przy zapisie. Z podręcznika `execve(2)` wiemy, że odzworowania pamięci nie są zachowywane.

Unix współdzieli pliki wykonywalne i biblioteki współdzielone, ponieważ ich obrazy w pamięci są dzielone między wszystkimi użytkownikami. Załóżmy, że uruchamiamy dwie instancje `bash`, a w jednej z nich `vim`'a. Będziemy wtedy mieli po jednej kopii `bash` i `vim` w pamięci (oraz jedną kopię `libc`, gdyż programy te korzystają z biblioteki języka C). Jeśli uruchomimy $n$ instancji wybranego programu, tylko jeden plik ELF będzie załadowany do pamięci, gdyż wszystkie `mmap(2)`'y wskazują na jeden obszar pamięci. Informacje zaczerpnięte z [tego posta na Unix StackExchange](https://unix.stackexchange.com/questions/491681/are-text-sections-shared-between-loaded-elf-executables).

**Pamięć wymiany** *(ang. swap space)* to miejsce na dysku, w którym system przechowuje strony, które nie mieszczą się fizycznie w pamięci RAM. Może być ona wymagana w przypadku używania prywatnych odwzorowań plików z prawami do pisania, gdyż zmiany w odwzorowaniu prywatnym nie są zapisywane do faktycznego pliku. W przypadku stron tylko do odczytu, nie ma potrzeby przechowywania ich w pamięci wymiany, podobnie w przypadku mapowań dzielonych plików, gdyż wtedy sam plik zachowuje się jak swój *swap space*. Anonimowe mapowania mogą wymagać użycia pamięci wymiany. W systemach Uniksowych wspierana jest flaga `MAP_NORESERVE`, dzięki której można ustalić, czy należy zarezerować miejsce w pamięci wymiany dla tworzonego mapowania.

### Zadanie 4

:::info
Na podstawie slajdów do wykładu wyjaśnij w jaki sposób system Linux obsługuje błąd stronicowania. Kiedy jądro wyśle procesowi sygnał `SIGSEGV` z kodem `SEGV_MAPERR` lub `SEGV_ACCERR`? W jakiej sytuacji wystąpi **pomniejsza usterka strony** *(ang. minor page fault)* lub **poważna usterka strony** *(ang. major page fault)*? Jaką rolę pełni **bufor stron** *(ang. page cache)*? Kiedy wystąpi błąd strony przy zapisie, mimo że pole `vm_prot` pozwala na zapis do **obiektu wspierającego** *(ang. backing object)*? Kiedy jądro wyśle `SIGBUS` do procesu posiadającego odwzorowanie pliku w pamięć (§49.4.3)?
:::


Błąd strony może wystąpić gdy proces próbuje czytać z nieistniejącej strony, dostać się do strony nieznajdującej się jeszcze w pamięci lub dostać się do strony bez odpowiednich uprawnień.

Aby obsłużyć błąd strony, należy przekazać kontrolę do jądra, który zapisze kontekst, a następnie sprawdzi która strona wywołała błąd. Jeżeli adres wirtualny jest poprawny, to system wczytuje odpowiednią ramkę strony, a jeśli trzeba ją zapisać, to na czas tej akcji *I/O* jądro przekazuje kontrolę innemu procesowi. Jeżeli adres nie jest poprawny (np. `NULL`), bądź strona nie ma odpowiednich uprawnień do wykonywanej akcji (np. zapis do strony *read-only*), to jądro wysyła procesowi sygnał `SIGSEGV`.

Sygnał `SIGSEGV` może być wysłany z kodem `SEGV_MAPERR`, który mówi o tym, że strona nie była zmapowana w przestrzeni adresowej procesu lub `SEGV_ACCERR`, gdy strona nie miała odpowiednich uprawnień.

Błędy stron możemy podzielić na dwa rodzaje:

* **Pomniejsza usterka strony** *(ang. minor page fault)* występuje, gdy strona jest załadowana do pamięci, ale nie jest oznaczona jako załadowana przez MMU. Taką stronę jądro musi tylko oznaczyć jako załadowaną. Do *minor page fault*a może dojść w sytuacji, gdy pamięć jest dzielona przez różne procesy i strona została już załadowana dla któregoś z procesów lub gdy strona została usunięta ze zbioru roboczego procesu, lecz nie została zapisana na dysk ani usunięta.
* **Poważna usterka strony** *(ang. major/hard page fault)* występuje, gdy strona nie znajduje się w pamięci. Występuje przez to, że system odracza ładowanie danych do pamięci aż do momentu, w którym te dane są potrzebne, a więc do pierwszego dostępu.

Nazwy *minor* (drobny) oraz *major* (kosztowny) odnoszą się do tego jak bardzo kosztowne pod względem czasu jest obsłużenie usterek strony.

**Bufor stron** *(ang. page cache)* to fragment pamięci RAM, którego zadaniem jest przyspieszenie odczytów i zapisów na dysku. Przy zapisach zmiany zostają dokonane jedynie w buforze stron (zamiast zapisów bezpośrednio na dysk), w którym zmienione strony są oznaczone bitem *dirty*. Zmiany na dysk są regularnie zapisywane na dysk przy użyciu `sync(2)` lub `fsync(2)`. Zwiększa się też szybkość odczytów, gdyż kolejne żądania wczytania tej samej strony mogą odbyć się przez bufor stron, o ile ta strona nadal się w nim znajduje.

Błąd strony przy zapisie może wystąpić wtedy, gdy plik został otworzony z flagą `O_WRONLY`, pomimo że pole `vm_prot` jest ustawione na `PROT_WRITE`. Dzieje się tak ze względu na to, iż część architektur sprzętu nie pozwala na dostęp *write-only* do stron. `PROT_WRITE` implikuje użycie `PROT_READ` na tych architekturach, a więc jeśli można zapisywać do stron, to mogą być one również odczytywane, jednak operacja odczytu jest niezgodna z flagą `O_WRONLY`, która zapobiega ujawnieniu zawartości pliku.

Jądro może wysłać sygnał `SIGBUS` do procesu posiadającego odwzorowanie pliku w pamięć, gdy proces próbuje uzyskać dostęp do części pamięci, która nie pasuje do pliku (np. dostęp poza EOF, włącznie z przypadkiem gdy inny proces uciął część pliku).

### Zadanie 5

:::info
Program `forksort` wypełnia tablicę $2^{26}$ elementów typu `long` losowymi wartościami. Następnie na tej tablicy uruchamia hybrydowy algorytm sortowania, po czym sprawdza jeden z warunków poprawności wyniku sortowania. Zastosowano algorytm sortowania szybkiego *(ang. quick sort)*, który przełącza się na sortowanie przez wstawianie dla tablic o rozmiarze mniejszym niż `INSERTSORT_MAX`.

Twoim zadaniem jest taka modyfikacja programu `forksort`, żeby oddelegować zadanie sortowania fragmentów tablicy do podprocesów. Przy czym należy tworzyć podprocesy tylko, jeśli rozmiar nieposortowanej części tablicy jest nie mniejszy niż `FORKSORT_MIN`. Zauważ, że tablica elementów musi być współdzielona między procesy – użyj wywołania [`mmap(2)`]() z odpowiednimi argumentami.

Porównaj **zużycie procesora** *(ang. CPU time)* i **czas przebywania w systemie** *(ang. turnaround time)* przed i po wprowadzeniu delegacji zadań do podprocesów. Na podstawie [prawa Amdahla](https://pl.wikipedia.org/wiki/Prawo_Amdahla) wyjaśnij zaobserwowane
różnice. Których elementów naszego algorytmu nie da się wykonywać równolegle?
:::

**Zużycie procesora** *(ang. CPU time)* to czas jaki procesor spędził na wykonywaniu instrukcji procesów, dla procesów wielowątkowych (lub zadań wieloprocesowych) wartość może przekroczyć 100% (a więc czas procesora będzie większy, niż czas rzeczywisty). **Czas przebywania w systemie** *(ang. turnaround time)* to czas od początku do zakończenia działania procesu.

Kod programu `forksort.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;

  /* TODO: If there is more to sort than FORKSORT_MIN start a subprocess. */
  bool should_fork = (right - left >= FORKSORT_MIN);
  if (should_fork) {
    if ((pid = Fork()))
      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);

      /* TODO: Wait for possible children and exit if created a subprocess. */
      (void)pid_left;   // leave these 2 lines to allow compiling in "older" version
      (void)pid_right;  

      if (pid_left != -1)
        Waitpid(pid_left, NULL, 0);

      if (pid_right != -1)
        Waitpid(pid_right, NULL, 0);

      if (should_fork)
        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);

  /* TODO: Allocate table... */
  int prot = PROT_READ | PROT_WRITE;
  int flags = MAP_SHARED | MAP_ANONYMOUS;
  long *table = Mmap(NULL, size, prot, flags, -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;
}

Oryginalna wersja programu `forksort` działa tylko w jednym procesie, więc czas działania jest dłuższy, niż w przypadku wersji z oddelegowanymi podprocesami. Pokazują to wyniki:

*** pierwotna wersja forksort ***
$ time ./forksort
./forksort  9.17s user 0.21s system 99% cpu 9.375 total

*** po dodaniu delegacji podprocesów ***
$ time ./forksort
./forksort  9.69s user 0.54s system 275% cpu 3.710 total

Widzimy więc, że czas działania `user` był zbliżony, jednak łączny czas jest $\frac{9.375}{3.710} \approx 2.53$ krótszy w przypadku wersji z delegacją podprocesów.

Aby sprawdzić różnice w wydajności, skorzystałem z programu `perf` do analizy wydajności. Poleceniem `perf record ./forksort` mierzę wydajność, a następnie `perf record` wypisuje zmierzone wartości.

Pierwotna wersja `forksort`, w raporcie widać, że wiele zadań można było liczyć równolegle (stąd oddelegowanie podprocesów w ulepszonej wersji). Około $72.17\% + 8.24\% + 6.51\% + 1.22\%$ to operacje, na które mamy wpływ.

Samples: 37K of event 'cycles:uppp', Event count (approx.): 28062695037
Overhead  Command   Shared Object     Symbol
  72.17%  forksort  forksort          [.] Partition
   8.24%  forksort  forksort          [.] InsertionSort
   6.51%  forksort  forksort          [.] SwapElem
   5.42%  forksort  libc-2.28.so      [.] __memmove_avx_unaligned_erms
   2.47%  forksort  libc-2.28.so      [.] __random_r
   2.07%  forksort  libc-2.28.so      [.] __random
   1.22%  forksort  forksort          [.] QuickSort
   1.00%  forksort  forksort          [.] main
   0.34%  forksort  [unknown]         [k] 0xffffffff8d600ae7
   0.30%  forksort  forksort          [.] memmove@plt
   0.26%  forksort  forksort          [.] random@plt
   0.00%  forksort  ld-2.28.so        [.] strcmp

Ulepszona wersja `forksort` zawierająca oddelegowanie podprocesów. W tym przypadku operacje wywoływane przez zdefiniowane przez nas funkcje zajmują około $88.47\%$ całego programu.

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

Jak można zauważyć, około $88.5\%$ czasu spędzane jest na zadaniach, które można wykonywać równolegle. Prawo Amdahla mówi o tym, że jeśli $P$ jest proporcją programu, która może ulec zrównolegleniu i $(1 - P)$ jest proporcją części, która nie może zostać zrównoleglona, wówczas przy użyciu $N$ procesorów można uzyskać maksymalne przyspieszenie równe

$$
\frac{1}{(1-P) + \frac{P}{N}} = \frac{1}{(1-0.885) + \frac{0.115}{4}} = 2.97
$$

Przyspieszenie uzyskane przez zrównoleglenie procedury `QuickSort` dało nam około $2.53$-krotne przyspieszenie, a maksymalne możliwe do uzyskania, wyliczone z prawa Amdahla to $2.97$. Niestety nie jesteśmy w stanie zrównoleglić procedur `Partition`, `InsertionSort` oraz `SwapElem`, gdyż 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.

### Zadanie 6

:::info
Nasz serwis internetowy stał się celem ataku hakerów, którzy wykradli dane milionów użytkowników. Zostaliśmy zmuszeni do zresetowania haseł naszych klientów. Nie możemy jednak dopuścić do tego, by użytkownicy wybrali nowe hasła z listy, którą posiadają hakerzy. Listę pierwszych 10 milionów skompromitowanych haseł można pobrać poleceniem `make download`.

Program `hashdb` został napisany w celu utworzenia bazy danych haseł i jej szybkiego przeszukiwania. Pierwszym argumentem przyjmowanym z linii poleceń jest nazwa pliku bazy danych haseł. Program wczytuje ze standardowego wejścia hasła oddzielone znakami końca linii i działa w dwóch trybach: dodawania haseł do bazy (opcja `-i`) i wyszukiwania (opcja `-q`). Żeby utworzyć bazę danych z pliku zawierającego hasła należy wywołać polecenie `./hashdb -i badpw.db < passwords.txt`. Program można uruchomić w trybie interaktywnego odpytywania bazy danych: `./hashdb -q badpw.db`.

Implementacja wykorzystuje tablicę mieszającą przechowywaną w pamięci, która odwzorowuje plik bazy danych haseł. Używamy adresowania liniowego i [funkcji mieszającej Jenkinsa]() `lookup3.c`. Hasło może mieć maksymalnie `ENT_LENGTH` znaków. Baza danych ma miejsce na $2^k$ wpisów. Jeśli w trakcie wkładania hasła do bazy wykryjemy konflikt kluczy, to wywołujemy procedurę `db_rehash`. Tworzy ona na nową bazę o rozmiarze $2^{k+1}$ wpisów, kopiuje klucze ze starej bazy do nowej i atomowo zastępuje stary plik bazy danych.

Twoim zadaniem jest uzupełnić kod procedur `db_open`, `db_rehash` i `doit` zgodnie z poleceniami zawartymi w komentarzach. Przeczytaj podręcznik systemowy do wywołania systemowego [`madvise(2)`]() i wyjaśnij słuchaczom co ono robi. Należy użyć odpowiednich funkcji z biblioteki `libcsapp` opakowujących wywołania: [`unlink(2)`](), [`mmap(2)`](), [`munmap(2)`](), [`madvise(2)`](), [`ftruncate(2)`](), [`rename(2)`]() i [`fstat(2)`]().
:::

*Poniżej umieszczony kod nie został napisany przeze mnie!*

/* 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. */
  Ftruncate(fd, size * sizeof(entry_t));
  db->entry = Mmap(NULL, size * sizeof(entry_t), PROT_READ | PROT_WRITE, MAP_SHARED, fd, 0);
  Madvise(db->entry, size * sizeof(entry_t), MADV_RANDOM);
  db->size = size;
  db->name = strdup(name);

  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. */
      db_close(new);
      Unlink(name);

      return false;
    }
  }

  /* TODO: Replace old database with new one, remove old database. */
  Rename(new->name, db->name); // Zastąpi stary plik, o ile nie ma RENAME_NOREPLACE.
  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 st;
  Fstat(STDIN_FILENO, &st);

  if (!S_ISREG(st.st_mode)) // isatty?
  {
    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, st.st_size, PROT_READ | PROT_WRITE, MAP_PRIVATE, STDIN_FILENO, 0);
    char *end = buf;
    do
    {
      end = consume_line(end, &db, mode);
    } while (end != NULL);
    Munmap(buf, st.st_size);
  }

  db_close(&db);
}

### Zadanie 7

:::info
Wykonywanie zewnętrznego polecenia przez powłokę uniksową ma dwa warianty. Gdy w ścieżce do pliku występuje znak ukośnika `/` to zakładamy, że użytkownik podał ścieżkę względną i uruchamiamy [`execve(2)`]() bezpośrednio. W przeciwnym przypadku musimy odczytać zawartość zmiennej środowiskowej `PATH` przechowującej katalogi oddzielone znakiem dwukropka `:`. Każdą ścieżkę katalogu sklejamy z nazwą polecenia (przyda Ci się procedura `strapp` z pliku `lexer.c`) i wołamy `execve`. Jeśli polecenie nie zostanie znalezione na dysku to `execve` wraca z błędem.

Uzupełnij ciało procedury `external_command` z pliku `command.c` zgodnie z powyższym opisem.

***Wskazówka:** Rozwiązanie wzorcowe liczy 10 wierszy. Do przetwarzania ciągów znakowych użyto funkcji [`strndup(3)`]() i [`strcspn(3)`]().*
:::

Dopóki znajdują się ścieżki w `path` (uzyskane ze zmiennej środowiskowej `PATH`), to szukamy pierwszego wystąpienia `:` dzielącego kolejne ścieżki, następnie korzystając ze `strndup(3)` kopiujemy wszyskie znaki ze ścieżki do `:`, po czym dodajemy do tej ścieżki `/[nazwaprogramu]` dwoma wywołaniami `strapp()`. Na końcu wywołujemy `execve` na tak stworzonej ścieżce.

noreturn void external_command(char **argv) {
  const char *path = getenv("PATH");

  if (!index(argv[0], '/') && path) {
    /* TODO: For all paths in PATH construct an absolute path and execve it. */
    while (true) {
      int chars_to_colon = strcspn(path, ":");
      if (chars_to_colon == 0)
        break;

      char *absolute_path = strndup(path, chars_to_colon);
      strapp(&absolute_path, "/");
      strapp(&absolute_path, argv[0]);
      (void)execve(absolute_path, argv, environ);

      free(absolute_path);
      path += 1 + chars_to_colon;
    }
  } else {
    (void)execve(argv[0], argv, environ);
  }

  msg("%s: %s\n", argv[0], strerror(errno));
  exit(EXIT_FAILURE);
}

### Zadanie 8

:::info
Procedura `do_job` w pliku `shell.c` przyjmuje tablicę tokenów, zawierającą polecenie do uruchomienia i przekierowania, oraz rodzaj tworzonego zadania (pierwszoplanowe lub drugoplanowe). Najpierw sprawdza czy podane polecenie należy do zestawu poleceń wbudowanych *(ang. builtin command)*. Jeśli nie, to przechodzi do utworzenia zadania i wykonania polecenia zewnętrznego. Po utworzeniu podprocesu i nowej grupy procesów, zadanie jest rejestrowane z użyciem `addjob` i `addproc`. Jeśli utworzono zadanie pierwszoplanowe, to należy poczekać na jego zakończenie przy pomocy `monitorjob`.

Uzupełnij ciało procedury `do_job` – wykorzystaj funkcje opakowujące wywołania: [`sigprocmask(2)`](), [`sigsuspend(2)`](), [`setpgid(2)`]() i [`dup2(2)`](). Pamiętaj, że uruchomione zadanie musi prawidłowo reagowaćna sygnały: `SIGTSTP`, `SIGTTIN` i `SIGTTOU`, a powłoka musi zamykać niepotrzebne deskryptory plików.

***Wskazówka:** Rozwiązanie ma około 25 wierszy. Funkcja `monitorjob` konfiguruje terminal przy pomocy [`tcsetpgrp(3)`]().*
:::

/* Execute internal command within shell's process or execute external command
 * in a subprocess. External command can be run in the background. */
static int do_job(token_t *token, int ntokens, bool bg) {
  int input = -1, output = -1;
  int exitcode = 0;

  ntokens = do_redir(token, ntokens, &input, &output);

  if (!bg) {
    if ((exitcode = builtin_command(token)) >= 0)
      return exitcode;
  }

  sigset_t mask;
  Sigprocmask(SIG_BLOCK, &sigchld_mask, &mask);

  /* TODO: Start a subprocess, create a job and monitor it. */
  pid_t pid = Fork();

  if (pid == 0) {
    // allow signals for the subprocess that are by default 
    // turned off for shell, i.e. CTRL+Z etc.
    Signal(SIGTSTP, SIG_DFL);
    Signal(SIGTTIN, SIG_DFL);
    Signal(SIGTTOU, SIG_DFL);

    // possibly open (duplicate) file descriptor that was changed
    // in do_redir call (it could've changed input/output values)
    if (input != -1) {
      Dup2(input, STDIN_FILENO);
      Close(input);
    }

    if (output != -1) {
      Dup2(output, STDOUT_FILENO);
      Close(output);
    }

    // finally call the command (it is surely not builtin)
    external_command(token);
  }

  // create own process group and then a job based on it, take
  // into account whether it is FG/BG process and then add the
  // process to the job
  Setpgid(pid, pid);
  int new_job = addjob(pid, bg);
  addproc(new_job, pid, token);

  // close file descriptors that were possibly opened earlier
  MaybeClose(&input);
  MaybeClose(&output);

  // based on bg value, run the job in bg or fg
  if (bg)
    printf("[%d] running '%s' [do_job called]\n", new_job, jobcmd(new_job));
  else
    monitorjob(&mask);

  Sigprocmask(SIG_SETMASK, &mask, NULL);
  return exitcode;
}

## Lista zadań nr 8

Przed rozwiązywaniem zadań warto się zapoznać z rozdziałami 1-3 publikacji [Dynamic Storage Allocation: A Survey and Critical Review](http://www.cs.cmu.edu/afs/cs/academic/class/15213-f98/doc/dsa.pdf).

### Zadanie 1

:::info
Systemy uniksowe udostępniają wywołania systemowe [`sbrk(2)`]() oraz parę [`mmap(2)`]() i [`munmap(2)`](). Służą one do przydziału stron na użytek bibliotecznego algorytmu zarządzania pamięcią. Czemu implementacje [`malloc(3)`]() preferują drugą opcję? Wyjaśnij to odwołując się do mapy pamięci wirtualnej procesu.

***Wskazówka:** Rozważ scenariusz, w którym proces zwolnił dużo pamięci przydzielonej na początku jego życia.*
:::

Użycie funkcji `sbrk(2)` przesuwa koniec sterty (*program break* będącym końcem segmentu danych procesu). Niestety jest to nieoptymalne podejście, gdyż jeśli najpierw zaalokujemy $x$ bajtów, później $y$ bajtów, to pomimo chęci zwolnienia pamięci $x$, nie będziemy w stanie tego zrobić, gdyż `brk` działa podobnie do operacji *push/pop* na stosie. Na przedstawionym poniżej schemacie widać to zachowanie - dopóki nie zwolni się używana pamięć (zielona), to nie jesteśmy w stanie zwolnić pamięci zaalokowanej wcześniej (czerwona).


W przypadku `malloc`, który używa `mmap(2)` oraz `munmap(2)` nie występuje taki problem - gdy zaalokowana pamięć przestaje być potrzebna, zwalniamy ją korzystając z funkcji `munmap(2)`. Przedstawia to zachowanie na poniższym schemacie - po zwolnieniu pamięci `p2` usuwana jest wybrana część, którą później możemy wykorzystać. Wykorzystywana wartość `SIZ` to `sizeof(int)`.


### Zadanie 2

:::info
Wyjaśnij różnicę między **fragmentacją wewnętrzną** i **zewnętrzną**. Czemu nie można zastosować **kompaktowania** w bibliotecznym algorytmie przydziału pamięci? Na podstawie §2.3 opowiedz o dwóch głównych przyczynach występowania fragmentacji zewnętrznej.
:::

**Fragmentacja wewnętrzna** *(ang. internal fragmentation)* dotyczy niewykorzystania pamięci wewnątrz przydzielonego bloku i najczęściej jest skutkiem operowania przez system większymi jednostkami, niż dokładność specyfikacji potrzeb ze strony aplikacji lub jądra systemu. Oznacza to więc, że pozostawiany jest niewykorzystany fragment przestrzeni adresowej wewnątrz przydzielonego obszaru - formalnie fragment jest zajęty, jednak w rzeczywistości nie jest wykorzystany.


**Fragmentacja zewnętrzna** *(ang. external fragmentation)* oznacza podział obszaru pamięci na rozłączne części, które nie stanowią ciągłości w przestrzeni adresowej . Występuje, gdy łączna suma wolnej pamięci jest wystarczająco duża do obsłużenia żądania alokacji pamięci, ale żaden z bloków nie jest dostatecznie duży i ich konsolidacja jest niemożliwa. Załóżmy, że w sytuacji przedstawionej poniżej chcielibyśmy użyć `p4 = malloc(7*SIZ)`, jednak byłoby to niemożliwe - jest łącznie 8 wolnych bloków, natomiast najdłuższym ciągłym fragmentem jest 6 bloków.


**Kompaktowanie** to proces konsolidacji pofragmentowanych danych (zaalokowanej pamięci) w taki sposób, aby były obok siebie. Nie możemy kompaktować pamięci przydzielonej przez `malloc(2)`, gdyż wszystkie istniejące wskaźniki by się unieważniły. Być może mamy wskaźnik do tego bloku, który chcemy przenieść, ale algorytm nie zapamiętuje w żaden sposób tego, gdzie są w pamięci wskaźniki wskazujące na ten blok. Wskaźniki wskazywałyby więc na złe miejsca w pamięci, a nie te, na które byśmy chcieli, aby wskazywały.

Głównymi przyczynami występowania fragmentacji zewnętrznej są:

* *Fragmentation is caused by isolated deaths:* krytycznym problemem jest tworzenie wolnych obszarów, których sąsiadujące obszary nie są wolne. Składają się na to dwie rzeczy: które obiekty są umieszczone w sąsiednich obszarach i kiedy te obiekty umierają. Jeśli alokator umieszcza obiekty razem w pamięci i umierają w tym samym czasie, to nie dochodzi do fragmentacji - obiekty żyją w tym samym czasie, używają ciągłej pamięci i gdy umierają, zwalniają ciągłą pamięć. Jeśli jednak obiekty zostaną uwolnione w różnym czasie, to mogą powstać między nimi przerwy.
* *Fragmentation is caused by time-varying behavior:* fragmentacja powstaje w wyniku zmiany sposobu użycia pamięci przez program, np. zwalnianie małych bloków i alokowanie bardzo dużych. Zadaniem alokatora jest wykorzystywanie takich wzorców, aby zminimalizować fragmentacje.

### Zadanie 3

:::info
Posługując się wykresem wykorzystania pamięci w trakcie życia procesu opowiedz o trzech wzorcach przydziału pamięci występujących w programach (§2.4). Na podstawie paragrafu zatytułowanego *„Exploiting ordering and size dependencies”* wyjaśnij jaki jest związek między czasem życia bloku, a jego rozmiarem? Wyjaśnij różnice między politykami znajdowania wolnych bloków: **first-fit**, **next-fit** i **best-fit**. Na podstawie §3.4 wymień ich słabe i mocne strony.
:::

Poniżej przedstawione są trzy wzorce przydziału pamięci występujące w programach na podstawie §2.4 publikacji [Dynamic Storage Allocation: A Survey and Critical Review](http://www.cs.cmu.edu/afs/cs/academic/class/15213-f98/doc/dsa.pdf):

1. Wykres przedstawia użycie pamięci dla GCC w trakcie kompilacji swojego największego pliku z kodu źródłowego - `combine.c`. Sposób ten polega na podzieleniu programu na etapy - pierwszy z nich jest największy, gdyż alokowane są największe obiekty, a każdy kolejny jest coraz mniejszy. Po każdej alokacji dużych obiektów następuje ich dealokacja, a następnie alokacja bardzo wielu małych elementów. Widać również, że przez cały czas działania programu jest praktycznie takie samo użycie pamięci dla obiektów $20$-bajtowych, dodatkowo każdy rozmiar obiektów ma swój własny profil użytkowania.

2. Wykres przedstawia użycie pamięci dla programu Grobnera, który rozkłada skomplikowane wyrażenia na liniowe kombinacje wielomianów (bazy Gröbnera). Ogólnie rzecz biorąc, zużycie pamięci narasta z czasem działania programu mniej więcej w kształt równi pochyłej, z lekkimi odchyłami.

3. Wykres przedstawia użycie pamięci dla symulatora hiperkostki Lindsay'a. Program alokuje bardzo dużo pamięci na samym początku działania, która jest wykorzystywana przez praktycznie cały czas wykonania. W trakcie jego działania alokowana jest bardzo mała liczba obiektów małych, krótkożyjących.

Podsumowując, są trzy wzorce przydziału pamięci:

* *ramps* gromadzący dane przyrostowo (podobnie do funkcji liniowej z małymi odchyłami),
* *peaks* gromadzący dane okresowo, na użytek jakiejś fazy programu, po której zwalniana jest większość danych (szybkie wzrosty i natychmiastowe upadki, formują trójkąty),
* *plateaus* gromadzący dane bardzo szybko na początku działania programu, a następnie używa ich przez prawie cały okres działania programu (prostokąt).

Na podstawie paragrafu *Exploiting ordering and size dependencies* można określić zależność między czasem życia bloku, a jego rozmiarem. Obiekty zaalokowane w tym samym czasie z dużym prawdopodobieństwem umrą w tym samym czasie, więc jeśli zostaną zaalokowane w ciągłym obszarze pamięci, a następnie jednocześnie zwolnione, to zostaną znacznie zmniejszone szanse na rozproszenie obiektów o długiej żywotności pośród tych o krótkiej żywotności. Rozmiar obiektów zwykle jest powiązany z jego typem i zastosowaniem, z tego powodu powinno się unikać przeplatania alokacji obiektów długożyjąch z krótkożyjącymi.

Znajdowanie wolnych bloków odbywa się zgodnie z politykami:

| polityka | zasada działania | zalety | wady |
|:-------------:|:---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------:|:--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------:|:--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------:|
| **first-fit** | Wybierany jest pierwszy wolny blok z listy o rozmiarze wystarczającym na jego przechowanie, a jeśli blok jest za duży - zostaje podzielony. Wyszukiwanie rozpoczyna się na początku listy wolnych bloków. | Prostota działania. | Prowadzi do fragmentacji pamięci, gdyż duże bloki są rozdzielane na początku listy, ponadto duża liczba małych bloków na początku listy powstałych przez rozdzielanie sprawia, że czas wyszukiwania staje się dłuższy.|
| **next-fit** | Wyszukiwanie kontynuowane jest od miejsca, w którym wystąpiła poprzednia alokacja. | Działa szybciej niż *first-fit*, gdyż zapamiętywane jest miejsce poprzedniej alokacji, przez co niepotrzebne bloki są pomijane. Zmniejsza się również ilość małych bloków na początku listy. | Obiekty z tych samych faz programu są rozrzucone w różnych miejscach w pamięci, co sprawia że fragmentacja jest większa, gdy obiekty w różnych fazach mają różne czasy życia - polityka ta jest również niekorzystna dla lokalności przestrzennej. |
| **best-fit** | Wyszukiwany jest najmniejszy blok, który jest wystarczająco duży, aby przechować dane. | Marnowana jest najmniejsza ilość pamięci. | Działa wolniej niż *first-fit* i *next-fit*, bo należy przejrzeć więcej bloków. Nie skaluje się dobrze dla dużych stert z wieloma wolnymi blokami. |

### Zadanie 4

:::info
Algorytm przydziału pamięci udostępnia funkcje o sygnaturach `alloc: words -> @id` i `free: @id -> void` i ma do dyspozycji obszar 50 słów maszynowych. Implementacja używa dwukierunkowej listy wolnych bloków oraz *boundary tags*. Wyszukiwanie wolnych bloków działa zgodnie z polityką *best-fit*. Operacja zwalniania **gorliwie złącza** bloki i wstawia wolne bloki na początek listy. Posługując się diagramem z wykładu wykonaj krokową symulację algorytmu przydziału pamięci dla poniższego ciągu żądań. Należy wziąć pod uwagę miejsce zajmowane przez struktury danych algorytmu przydziału oraz nieużytki.

alloc(5) alloc(12) alloc(15) alloc(8) free(@2) free(@1) free(@3) alloc(10)

***Uwaga:** Funkcja `alloc` zwraca bloki o kolejnych identyfikatorach począwszy od `@1`. Adresy są wyrównane do długości słowa.*
:::

**Gorliwe złączanie** *(ang. immediate coalescing)* polega na złączaniu wolnych bloków tak szybko, jak jest to możliwe, a więc po zwolnieniu pamięci przez `free()`.

Korzystamy z dwukierunkowej listy wolnych bloków oraz znaczników granicznych *(boundary tags)*. Oznacza to, że blok w pamięci wygląda tak, jak na poniższym schemacie.


Podobnie jak na wykładzie, zieloną strzałką będziemy oznaczać pierwszy element listy, a czerwoną ostatni. Kolejne operacje przydzielania i zwalniania pamięci będą się odbywać w następujący sposób. Strzałki nie mieszają się, gdyż mamy zawsze tylko jeden duży blok, więc wskaźniki wskazują na ten sam blok.


### Zadanie 5

:::info
Rozważmy **algorytm kubełkowy** (§3.6) *(ang. segregated-fit)* przydziału pamięci z gorliwym złączaniem wolnych bloków. Jak przebiegają operacje `malloc` i `free`? Co robi `malloc`, gdy na danej liście nie ma wolnego bloku żądanego rozmiaru? Jak poradzić sobie w trakcie złączania wolnych bloków w procedurze `free`, jeśli chcemy usunąć ostatni element z listy? Rozważ zastosowanie **leniwego złączania** wolnych bloków w algorytmie kubełkowym przydziału pamięci – jakie problemy zauważasz?
:::

**Algortym kubełkowy** *(ang. segregated-fit)* polega na przechowywaniu list wolnych bloków w taki sposób, że każda lista przechowuje bloki o wyznaczonym rozmiarze (zwykle najmniejsze wartości mają dedykowane listy, a większe listy przechowujące rozmiary od $2^i + 1$ do $2^{i+1}$). Kiedy wykonywana jest alokacja, wybiera się blok z najmniejszej wystarczającej listy.


Operacja alokacji pamięci poleceniem `malloc(n)` działa następująco: wybierany jest odpowiedni najmniejszy kubełek, w razie gdy ten kubełek zawiera wolny blok, to wolny blok jest usuwany z listy wolnych bloków i oznaczany jako zajęta, na koniec zwracany jest wskaźnik na ten blok. Gdy kubełek jest już cały zajęty, to należy szukać bloku w kolejnym kubełku. W przypadku, gdy wszystkie kubełki są zajęte, alokowana jest nowa strona przeznaczona dla bloków o żądanym rozmiarze. Wtedy dla wolnego bloku wykonywany jest podział, pamięć alokowana, a pozostałe miejsce jest umieszczane na liście wolnych bloków.

Operacja zwalniania pamięci poleceniem `free(ptr)` oznacza najpierw blok jako wolny, a w przypadku gdy sąsiadujący blok jest wolny, są one łączone. Następnie cały wolny blok jest przenoszony do listy wolnych bloków.

Jeśli chcemy zwolnić ostatni element z listy za pomocą `free`, musimy wziąć pod uwagę, że ostatni element zawiera wskaźnik na początek większego kubełka - należy więc przepiąć wskaźniki, jednak nie jest to problematyczne, gdyż do początku kolejnego kubełka i końca poprzedniego możemy się dostać w czasie stałym $O(1)$.

**Złączanie leniwe** *(ang. deferred coalescing)* polega na łączeniu bloków dopiero w momencie, gdy kolejny raz chcemy zaalokować pamięć i nie napotkaliśmy bloku o wystarczająco dużym rozmiarze. Gdybyśmy chcieli leniwie złączać bloki, moglibyśmy zmniejszyć czas wyszukiwania bloków przy małych alokacjach. Problemem wynikającym z tego podejścia jest zwiększenie fragmentacji:

* użycie pamięci przy gorliwym złączaniu:
* użycie pamięci przy leniwym złączaniu:

Powyższe grafiki pochodzą z publikacji [Visualising Dynamic Memory Allocators](https://spiral.imperial.ac.uk/bitstream/10044/1/5766/1/GCspy.pdf).

### Uwagi do kolejnych zadań

:::danger
Dla metod przydziału pamięci użytych w poniższych zadaniach należy być przygotowanym na wyjaśnienie:
* jak wygląda struktura danych przechowująca informację o zajętych i wolnych blokach?
* jak przebiegają operacje `alloc` i `free`?
* jaka jest pesymistyczna złożoność czasowa powyższych operacji?
* jaki jest narzut *(ang. overhead)* pamięciowy **metadanych** (tj. ile bitów lub na jeden blok)?
* jaki jest maksymalny rozmiar **nieużytków** *(ang. waste)*?
* czy w danym przypadku **fragmentacja wewnętrzna** lub **zewnętrzna** jest istotnym problemem?
:::

**Metadane** to informacje przechowywane wraz z blokiem, które go opisują. Mówią o jego rozmiarze, zajętości, przechowują wskaźniki na poprzedni/kolejny element.

**Nieużytyki** *(ang. waste)* to pamięć, która została zaalokowana, lecz nie można jej użyć.

**Fragmentacja wewnętrzna** i **fragmentacja zewnętrzna** zostały opisane w rozwiązaniu zadania 2.

### Zadanie 6

:::info
Program `objpool` zawiera implementację **bitmapowego przydziału** bloków o stałym rozmiarze. Algorytm zarządza pamięcią w obrębie aren przechowywanych na jednokierunkowej liście `arenas`. Pamięć dla aren jest pobierana od systemu z użyciem wywołania [`mmap(2)`](). Areny posiadają nagłówek przechowujący węzeł listy i dodatkowe dane algorytmu przydziału. Za nagłówkiem areny znajduje się pamięć na metadane, a także bloki pamięci przydzielane i zwalniane funkcjami `alloc_block` i `free_block`.

Używając funkcji opisanych w [`bitstring(3)`]() uzupełnij brakujące fragmenty procedur. Metadane w postaci bitmapy są przechowywane za końcem nagłówka areny. Ponieważ odpluskwianie algorytmu może być ciężkie, należy korzystać z funkcji [`assert(3)`]() do wymuszania warunków wstępnych procedur. Twoja implementacja algorytmu zarządzania pamięcią musi przechodzić test wbudowany w skompilowany program `objpool`.
:::

**Bitmapowy przydział** to sposób reprezentacji wolnych i zajętych bloków w tablicy bitów.

Strukturą danych przechowującą informacje o blokach jest tablica bitów typu `bitstr_t`. Aby przechować wszystkie metadane, używane jest `nitems` bitów (zaokrąglone do `object_t`) oraz po $8$ bajtów na `nitems`, `nfree` oraz wskaźnik `*items`.

Operacja alokowania pamięci `alloc` polega na znalezieniu pierwszej areny z wolnymi blokami, następnie znalezieniu indeksu wolnego bloku w znalezionej arenie, zmniejszeniu liczby wolnych bloków i oznaczeniu bloku jako zajętego. Na koniec zwracany jest wskaźnik na blok. Pesymistycznie operacja ta zostanie wykonana w czasie $O(n\cdot m)$, gdzie $n$ to liczba aren, a $m$ to liczba bitów w bitmapie.

Operacja zwalniania pamięci `free` polega na znalezieniu areny o odpowiednim zakresie indeksów (wskaźników), zmiany wskaźnika na indeks bloku w danej arenie a następnie oznaczeniu bloku jako wolny i zwiększeniu liczby wolnych bloków. Pesymistyczny czas działania to $O(n)$, gdzie $n$ to liczba wszystkich aren.

W tym systemie nie powstają żadne nieużytki, gdyż wszystkie bloki są rozmiaru struktury `object_t`. Z tego powodu każdy blok jest "dobry" i może podlegać alokacji. Nietesty stworzone areny nie zostają nigdy zwolnione, więc nawet po zwolnieniu całej pamięci nie zostanie ona oddana systemowi. Fragmentacje nie są problemem, gdyż rozmiar wszystkich bloków jest taki sam.

Kod uzupełnionych funkcji z pliku `objpool.c`:

static arena_t *init_arena(arena_t *ar) {
  /* TODO: Calculate nitems given ARENA_SIZE, size of arena_t and object_t. */
  // We need free space to calculate how much items we can store in the bitmap,
  // for which we use bitstr_size (it returns number of elements of bitstr_t
  // that are necessary to store nbits = (free_space / sizeof(object_t)) bits.
  size_t free_space = ARENA_SIZE - sizeof(arena_t);
  size_t bitmap_size = bitstr_size(free_space / sizeof(object_t));
  size_t nitems = (free_space - bitmap_size) / sizeof(object_t);

  ar->nitems = nitems;
  ar->nfree = nitems;
  /* Determine items address that is aligned properly. */
  ar->items = arena_end(ar) - nitems * sizeof(object_t);
  return ar;
}

static void *alloc_block(arena_t *ar) {
  assert(ar->nfree > 0);
  int index;
  /* TODO: Calculate index of free block and mark it used, update nfree. */
  // bit_ffc is used to store in the location referenced by &index of the
  // first bit not set in the array ar->bitmap of ar->nitems bits and if
  // all bits are set to 1, then the &index is set to -1 (that's why we
  // have to use assert). Then we use bit_set to set the bit index in given
  // array ar->bitmap. Afterwards we decrement number of free arenas.
  bit_ffc(ar->bitmap, ar->nitems, &index);
  assert(index != -1);
  bit_set(ar->bitmap, index);
  ar->nfree--;

  return ar->items + sizeof(object_t) * index;
}

static void free_block(arena_t *ar, void *ptr) {
  int index = (ptr - ar->items) / sizeof(object_t);
  /* TODO: Determine if ptr is correct and mark it free, update nfree. */
  // We have to assure that index we use is in the range of nitems, then
  // test (using bit_test) whether given index bit is set or not. If it is
  // set, then use bit_clear to clear it and increase free arenas' amount.
  assert(index < ar->nitems);
  assert(bit_test(ar->bitmap, index));
  bit_clear(ar->bitmap, index);
  ar->nfree++;
}

### Zadanie 7 (bonusowe) TODO

:::info
Zoptymalizuj procedurę `alloc_block` z poprzedniego zadania. Główną przyczyną niskiej wydajności jest użycie funkcji `bit_ffc`. Należy wykorzystać dwa sposoby na jej przyspieszenie:
1. użycie jednocyklowej instrukcji procesora [`ffs2`](https://en.wikipedia.org/wiki/Find_first_set) wyznaczającej numer pierwszego ustawionego bitu w słowie maszynowym,
2. użycie wielopoziomowej struktury bitmapy, tj. wyzerowany $i$-ty bit w bitmapie poziomu $k$ mówi, że w $i$-tym słowie maszynowym bitmapy poziomu $k + 1$ występuje co najmniej jeden wyzerowany bit.

***Komentarz:** Bardzo dobry algorytm musiałby jeszcze wziąć pod uwagę strukturę pamięci podręcznej procesora.*
:::

### Zadanie 8

:::info
Program `stralloc` implementuje algorytm zarządzania pamięcią wyspecjalizowany pod kątem przydziału miejsca dla ciągów znakowych nie dłuższych niż `MAX_LENGTH`. Ponieważ algorytm wie, że w blokach będą składowane ciągi znakowe, to nie musi dbać o wyrównanie adresu zwracanego przez procedurę `stralloc`.

Podobnie jak w programie `objpool` będziemy zarządzać pamięcią dostępną za nagłówkiem areny. W obszarze tym zakodujemy **niejawną listę** *(ang. implicit list)* jednokierunkową, której węzły są kodowane w pierwszym bajcie bloku. Wartość bezwzględna nagłówka bloku wyznacza jego długość, a znak dodatni i ujemny kodują to czy blok jest wolny, czy zajęty. Nagłówek bloku o wartości zero koduje koniec listy. Ponieważ domyślnie arena ma długość $65536$ bajtów to procedura `init_chunk` musi wypełnić zarządzany obszar wolnymi blokami nie większymi niż `MAX_LENGTH+1`.

Twoim zadaniem jest uzupełnienie brakujących fragmentów procedur `alloc_block` i `strfree`. Pierwsza z nich jest zdecydowanie trudniejsza i wymaga obsłużenia aż pięciu przypadków. Będzie trzeba dzielić bloki *(ang. splitting)*, złączać *(ang. coalescing)* lub zmieniać rozmiar dwóch występujących po sobie wolnych bloków, jeśli nie da się ich złączyć. Druga procedura jest dużo prostsza i zaledwie zmienia stan bloku upewniwszy się wcześniej, że użytkownik podał prawidłowy wskaźnik na blok.

Przed przystąpieniem do rozwiązywania przemyśl dokładnie działanie procedur. Pomyłki będą ciężkie do znalezienia. Jedyną linią obrony będzie tutaj obfite sprawdzanie warunków wstępnych funkcją [`assert(3)`]().

Rozważ następujący scenariusz: program poprosił o blok długości $n$ (zamiast $n + 1$), po czym wpisał tam $n$ znaków i zakończył ciąg zerem. Co się stanie z naszym algorytmem? Czy da się wykryć taki błąd?

***Komentarz:** Celem tego zdania jest przygotowanie Was do implementacji poważniejszego algorytmu zarządzania pamięcią, który będzie treścią drugiego projektu programistycznego. Potraktujcie je jako wprawkę!*
:::

**Niejawna lista** *(ang. implicit list)* to lista, która nie przechowuje wskaźników na kolejne elementy, lecz ich rozmiar oraz to, czy dany blok pamięci jest zajęty czy wolny. Na poniższym schemacie jest widoczna przykładowa niejawna lista. Nagłówki *(ang. headers)* przechowują dwie informacje: rozmiar bloku oraz zajętość. Na biało oznaczone są bloki wolne, na szaro zaalokowane. Pamięć nieużywana przy bloku oznaczonym `4/1` jest opcjonalnym wypełnieniem *(ang. padding)*. Bloki są wyrównane do długości dwóch słów.


Przechowywane dane w zadaniu są w sposób opisany powyżej, więc w jednokierunkowej liście niejawnej. Nagłówek przechowuje długość bloku i niejawnie wskazuje następnika. Metadane zajmują więc $1$ bajt.

Operacja alokacji pamięci `alloc` tworzy arenę, gdy jeszcze żadna nie istnieje, a następnie próbuje alokować pamięć o danym rozmiarze `len` w każdej arenie po kolei. W obrębie jednej areny mamy kilka ścieżek z możliwościami:

1. Jeśli jesteśmy na końcu areny, zwracany jest `NULL`.
2. W przypadku trafienia na zajęty blok, przechodzimy do kolejnego.
3. Jeśli aktualny blok może przechować dane `*data` i jest rozmiaru `len`, to oznaczamy go jako zajęty i zwracamy wskaźnik do niego.
4. Jeśli aktualny blok jest za duży, to dzielimy go na dwie części - jedna wystarczająca do przechowania danych `*data` wielkości `len`, a druga do końca wolnego miejsca. Pierwszy blok oznaczamy jako zajęty i zwracamy wskaźnik do niego.
5. Gdy następny blok jest zajęty lub jest końcem listy (więc nie istnieje), to przechodzimy do kolejnej areny.
6. Gdy dwa bloki obok siebie są wolne, ale i tak niewystarczające do pomieszczenia danych `*data`, to łączymy je i wracamy do punktu 1.
7. Gdy dwa bloki obok siebie są wolne i są wystarczające do pomieszczenia danych, to łączymy je ze sobą i wracamy do punktu 4.

Gdyby nie udało się zaalokować miejsca w arenie, to tworzymy nową i tam alokujemy pamięć. Pesymistyczny czas działania tej operacji to $O(n)$, gdzie $n$ to liczba wszystkich bloków.

Operacja zwalniania pamięci `free` jest znacznie prostsza. Znajdujemy arenę, w której leży wskaźnik, a następnie oznaczamy blok jako wolny. Pesymistyczny czas działania tej operacji to $O(n)$, gdzie $n$ to liczba wszystkich aren.

Maksymalnym rozmiarem nieużytków jest `MAX_LENGTH - 1`, gdyż wtedy pomimo dostępnej pamięci na `MAX_LENGTH - 1` nie będziemy mieli miejsca na przechowanie danych długości `MAX_LENGTH`. W przypadku `stralloc` fragmentacja zewnętrzna już jest problemem, gdyż alokowane bloki mogą mieć różne rozmiary i powstają wolne miejsca. Fragmentacja wewnętrzna nie jest problemem, gdyż wskaźniki nie muszą być wyrównywane.

Kod uzupełnionych funkcji z pliku `stralloc.c`:

static void *alloc_block(int8_t *data, uint8_t len) {
  void *result = NULL;

  while (!END_OF_CHUNK(data)) {
    if (BLOCK_USED(data)) {
      /* TODO: occupied block */
      MOVE_NEXT(data);
    } else if (BLOCK_SIZE(data) == len) {
      /* TODO: free block of exact size */
      BLOCK_HEADER(data) = BLOCK_SIZE(data);
      result = CURRENT_PTR(data);
      break;
    } else if (BLOCK_SIZE(data) > len) {
      /* TODO: free block is too large */
      int8_t free_space = BLOCK_SIZE(data) - len;
      BLOCK_HEADER(data) = len;
      NEXT_BLOCK_HEADER(data) = free_space;
      result = CURRENT_PTR(data);
      break;
    } else if (!NEXT_BLOCK_FREE(data)) {
      /* TODO: next block is occupied or does not exists */
      MOVE_NEXT(data);
    } else if (NEXT_BLOCK_SIZE(data) <= len - BLOCK_SIZE(data)) {
      /* TODO: merge two free blocks, but do not allocate */
      int8_t size = BLOCK_SIZE(data) + NEXT_BLOCK_SIZE(data);
      BLOCK_HEADER(data) = -size;
    } else {
      /* TODO: merge two free blocks and allocate with split */
      int8_t total_size = BLOCK_SIZE(data) + NEXT_BLOCK_SIZE(data);
      int8_t next_block_size = total_size - len;
      BLOCK_HEADER(data) = len;
      NEXT_BLOCK_HEADER(data) = -next_block_size;
      result = CURRENT_PTR(data);
      break;
    }
  }
  return result;
}

static void strfree(char *str) {
  if (str == NULL)
    return;
  int8_t *sstr = (int8_t *)str;
#if DEBUG_LEVEL > 0
  assert(sstr[-1] > 0);
  arena_t *ar = find_ptr_arena(&arenas, str);
  assert(ar != NULL);
#if DEBUG_LEVEL > 1
  int8_t *ptr = (int8_t *)ar + sizeof(arena_t);
  while (ptr < sstr - 1) {
    assert(*ptr != 0);
    ptr += (*ptr > 0 ? *ptr : -*ptr);
  }
  assert(ptr == sstr - 1);
#endif
#endif
  /* TODO: mark block as free */
  assert (*ptr > 0);
  *ptr *= -1;
}

## Lista zadań nr 9

Przed rozwiązywaniem zadań warto się zapoznać z podrozdziałem 11.4 *CS:APP* oraz rozdziały 2, 4, 5 i 8 z *Unix Network Programming: The Sockets Networking API*.

### Zadanie 1

:::info
Na podstawie §2.3 i §2.4 omów różnice między: protokołem [`ip(7)`](), **datagramowym** protokołem [`udp(7)`]() i **połączeniowym** protokołem [`tcp(7)`](). Czym różni się komunikacja półdupleksowa od dupleksowej? Jak TCP radzi sobie z zagubieniem **segmentu** lub zamianą kolejności wysłanych segmentów po stronie odbierającego? Skąd protokół TCP wie kiedy połączenie zostało zerwane? Jaki problem rozwiązuje **sterowanie przepływem** *(ang. flow control)* implementowane przez TCP?

***Wskazówka:** Przy tłumaczeniu właściwości protokołów posłuż się analogią (np. wysyłanie listu, dzwonienie przez telefon, itp.)*
:::

**Protokół internetowy** *(ang. Internet Protocol, IP)* to zbiór ścisłych reguł oraz kroków postępowania, które są automatycznie wykonywane przez urządzenia komunikacyjne w celu nawiązania łączności i wymiany danych. Informacja o IP jest dołączona do każdego pakietu, dzięki czemu router może wysłać dane do odpowiedniego miejsca.

**UWAGA!!** IP to jedyny protokół siciowy, UDP i TCP to protokoły komunikacyjne.

**Datagramowy protokół UDP** *(ang. User/Unreliable Datagram Protocol)* to prosty, bezpołączeniowy protokół. Jego zaletą jest niewielki narzut danych sterujących, dodawanych w procesie enkapsulacji. Bezpołączeniowość UDP polega na tym, iż przed rozpoczęciem procesu komunikacji host źródłowy nie wysyła do hosta docelowego żadnych informacji zestawiających to połączenie. Zasada jest taka, że jeśli urządzenie źródłowe chce rozpocząć transmisję, to robi to bez wcześniejszego ustalenia.

**Połączeniowy protokół TCP** *(ang. Transmission Control Protocol)* to protokół zapewniający połączenie pomiędzy klientem a serwerem. Klient TCP nawiązuje połączenie z danym serwerem, wymienia dane z tym serwerem, a następnie kończy połączenie.

Protokół ten zapewnia niezawodność, tzn. gdy TCP wysyła dane do odbiorcy, to wymaga potwierdzenia dostarczenia ich, a gdy go nie dostanie - TCP ponownie wysyła dane i czeka dłuższy czas na potwierdzenie. Warto zauważyć, że TCP nie gwarantuje dostarczenia danych. Podsumowując: TCP zapewnia niezawodne dostarczenie danych lub niezawodne powiadomienie o niepowodzeniu.

TCP uporządkowuje dane poprzez dołączenie numeru każdego bajtu, który wysła. Załóżmy, że aplikacja pisze 2048 bajtów do gniazda TCP, powodując wysłanie dwóch **segmentów** (pojedyncza paczka danych o pojemności 1024 bajtów) danych przez TCP: pierwszy zawiera dane z numerami 1-1024, a drugi z 1025-2048. Gdy segment zostanie dostarczony w złej kolejności, TCP przestawi je na podstawie wysyłanych numerów, a gdy segment zostanie zagubiony, to zostaje wysłany ponownie.

Wykorzystywane przez TCP **sterowanie przepływem** *(ang. flow control)* mówi o tym, ile danych może zostać odebranych w jednym czasie. Gwarantuje to, że nadający nie może przepełnić bufora. Rozmiar ten zmienia się jednak dynamicznie, więc gdy aplikacja czyta dane z bufora, ten rozmiar może zostać powiększony. Istnieje również możliwość taka, że bufor gniazda TCP zostanie zapełniony, przez co aplikacja zostanie tymczasowo wstrzymana, aby mogła odczytać dane z bufora, a następnie odebrała kolejne dane.

Połączenie TCP jest dupleksowe, oznacza to, że aplikacja może wysyłać i odbierać dane w obu kierunkach w połączeniu o dowolnej porze. Komunikacja półdupleksowa jest ograniczona względem komunikacji dupleksowej, a więc wysyłanie i odbieranie informacji odbywa się naprzemiennie.

Połączenie TCP zostaje zerwane po wysłaniu przez jedną ze stron pakietu z ustawioną flagą `FIN` (od *finished*), wymaga on potwierdzenia flagą `ACK`. Dopuszcza się też awaryjne przerwanie połączenia pakietem z flagą `RST` *(reset)*, taki pakiet nie wymaga potwierdzenia.

**Analogie do właściwości protokołów:**

* IP - aby wysłać komuś list, należy podać jego adres i inne dane w odpowiedniej formie i kolejności, które pomogą dostarczyć list do odpowiedniej osoby.
* TCP - w przypadku komunikacji ludzkiej rozmowa rozpoczęłaby się od słów jednej osoby: "Zacznijmy rozmowę", po czym druga odpowiedziałaby "Zaczynam słuchać!". Podobnie w przypadku dzwonienia przez telefon, jedna osoba dzwoni (informuje o chęci nawiązania połączenia), a druga dopiero po odebraniu może otrzymać informacje.
* UDP - w przypadku komunikacji ludzkiej rozmowa rozpoczęłaby się natychmiastowo, bez wcześniejszego uprzedzenia o chęci przekazania informacji.

### Krótkie wytłumaczenie poleceń

| Funkcja | Działanie |
|:-------------:|:--------------------------------------------------------- |
| `socket(2)` | Stworzenie nowego gniazda (deksryptora gniazda) |
| `connect(2)` | Nawiązanie połączenia z gniazdem |
| `bind(2)` | Powiązanie gniazda z nazwą (czyli adresem IP oraz portem) |
| `listen(2)` | Nasłuchiwanie na połączenia |
| `accept(2)` | Zaakceptowanie połączenia |
| `sendto(2)` | Wysłanie wiadomości (danych) do gniazda |
| `recvfrom(2)` | Odebranie wiadomości (danych) z gniazda |

### Zadanie 2

:::info
Omów diagram 4.1 komunikacji **klient-serwer** używającej protokołu [`tcp(7)`]() przy pomocy interfejsu **gniazd strumieniowych**. W którym momencie następuje związanie gniazda z adresem będącym parą (numer IP, port)? Która ze stron komunikacji używa **portów efemerycznych** *(ang. ephemeral)*? Co specyfikuje drugi argument wywołania systemowego [`listen(2)`]()? Z jakim numerem portu jest związane gniazdo przekazywane do i zwracane z [`accept(2)`]()? Skąd serwer wie, że klient zakończył połączenie?
:::

Komunikacja **klient-serwer** to architektura systemu komputerowego umożliwiająca podział zadań/ról. Polega ona na ustaleniu, że serwer zapewnia usługi dla klientów, zgłaszających do serwera żądania obsługi *(ang. service request)*.

**Gniazda strumieniowe** to gniazda oparte na połączeniach, umożliwiają one sekwencyjny przepływ danych z gwarancją przesłania pakietu i zachowania kolejności.

Diagram komunikacji klient-serwer używający protokołu TCP:

1. Serwer zostaje uruchomiony, tworzy gniazdo (`socket(2)`), wiąże je z jakąś nazwą (`bind(2)`), po czym zaczyna nasłuchiwać połączeń (i je akceptować).
2. Klient zostaje uruchomiony, tworzy gniazdo po czym próbuje się połączyć z serwerem - używa do tego `connect(2)` i jeśli pomyślnie nawiąże połączenie, to gniazdo zostaje związane z adresem IP oraz unikalnym, lokalnym portem, czyli **efemerycznym** *(ang. ephemeral)*. Port efemeryczny, inaczej port ulotny to port istniejący tylko na czas trwania połączenia, który wykorzystuje klient. Po zakończeniu połączenia port jest dostępny do ponownego użycia.
3. Od tego momentu klient może wysyłać żądania do serwera, który mu odpowiada.
4. Po zamknięciu połączenia przez klienta, serwer dostaje informacje o *EOF*, po czym serwer kończy swoje działanie.

Polecenie `int listen(int sockfd, int backlog)` służy do nasłuchiwania (oczekiwania) na połączenia. Pierwszy argument `sockfd` to *id* deskryptora pliku gniazda, a drugi `backlog` to maksymalna liczba połączeń w kolejce dla deskryptora o zadanym `sockfd`. W przypadku, gdy kolejka zostanie zapełniona i zostanie wysłane kolejne żądanie, klient może otrzymać błąd z flagą `ECONNREFUSED` lub żądanie zostanie zignorowane.

Polecenie (serwera) `int accept(int sockfd, struct sockaddr *addr, socklen_t *addrlen)` wykorzystywane jest do zaakceptowania połączenia z gniazdem o danym `sockfd`. Wypełnia ono adres gniazda klienta `*addr` i zwraca podłączony deskryptor, który może być wykorzystany do komunikacji z klientem, używając uniksowych operacji *I/O*. Gniazdo przekazywane do `accept()` jest związane z serwerem, a zwracane z klientem.

Załóżmy, że mamy serwer `192.168.1.1:80` oraz dwóch klientów: `10.0.0.1` i `10.0.0.2`. Klient `10.0.0.1` chce nawiązać połączenie z serwerem na lokalnym porcie `1234` i łączy się. Wtedy serwer ma jedno gniazdo zidentyfikowane jako `10.0.0.1:1234 - 192.168.1.1:80`. Następnie łączy się drugi klient `10.0.0.2` z lokalnym portem `4321`, wtedy serwer ma ma dwa gniazda:

10.0.0.1:1234 -> 192.168.1.1:80 - protocol
10.0.0.2:4321 -> 192.168.1.1:80 - protocol

### Zadanie 3

:::info
Omów diagram 8.1 komunikacji klient-serwer używającej protokołu [`udp(7)`]() przy pomocy interfejsu **gniazd datagramowych**. Czemu, w przeciwieństwie do TCP, serwer może rozpocząć pracę zaraz po wykonaniu funkcji [`bind(2)`]()? Z jakiej przyczyny interfejs [`read(2)`]() i [`write(2)`]() po stronie serwera jest niewystarczający? Przedstaw semantykę operacji [`recvfrom(2)`]() i [`sendto(2)`](). Na podstawie §8.11 zreferuj efekt jaki przynosi wykonanie [`connect(2)`]() na gnieździe klienta.
:::

**Gniazda datagramowe** to gniazda bezpołączeniowe. Oznacza to, że każdy pakiet jest indywidualnie adresowany i przekierowywany. Nie ma również gwarancji, że pakiet zostanie przesłany, ani że kolejność wysyłanych pakietów zostanie zachowana.

Diagram komunikacji klient-serwer używający protokołu UDP:

1. Klient wysyła datagram z żądaniem do serwera używając funkcji `sendto(2)`.
2. Serwer blokuje `recvfrom(2)` do momentu otrzymania datagramu od klienta, następnie żądanie jest odsyłane do klienta poprzez `sendto(2)`.
3. Klient odbiera odpowiedź od serwera za pomocą `recvfrom(2)`, po czym ponownie może wykonywać żądania.

Serwer używający protokołu UDP może rozpocząć swoje działanie zaraz po użyciu `bind(2)`, gdyż nie jest nawiązywane żadne połączenie, więc serwer nie musi na nie oczekiwać. Protokół UDP jest bezpołączeniowy, więc klient nie łączy się z serwerem, a wymiana danych odbywa się za pomocą datagramów.

Interfejs `read(2)` i `write(2)` jest niewystarczający, gdyż w przypadku protokołu UDP należy odczytać adres, z którego przyszły pakiety, a następnie odesłać je do konkretnego adresu. Służą do tego polecenia `recvfrom(2)` oraz `sendto(2)` o sygnaturach:

ssize_t recvfrom(int sockfd, void *buf, size_t len, int flags,
                 struct sockaddr *src_addr, socklen_t *addrlen);
				 
ssize_t sendto(int sockfd, const void *buf, size_t len, int flags,
               const struct sockaddr *dest_addr, socklen_t addrlen);

`recvfrom(2)` to funkcja służąca do odbierania wiadomości. Jako argumenty przyjmuje deskryptor gniazda `sockfd`, wskaźnik `*buf` na miejsce, w którym powinna zostać zapisana wiadomość, długość wiadomości `len`, flagi `flags` specyfikujące odbiór wiadomości, adres struktury `*src_addr`, w którym powinny zostać zapisane informacje o adresie wejściowym, jak i długość tej struktury `*addrlen`. Po pomyślnym odbiorze wiadomości zwracana jest długość otrzymanej wiadomości w bajtach, gdy nie ma żadnej wiadomości do odebrania, zwracane jest `0`, a w pozostałych przypadkach `-1` i ustawiana jest odpowiednia wartość `errno`.

`sendto(2)` to funkcja służąca do wysyłania wiadomości. Jako argumenty przyjmuje deskryptor gniazda `sockfd`, wskaźnik `*buf` na bufor z wiadomością do wysłania, jak i jej długość `len`. Poza nimi są jeszcze flagi `flags`, mówiące o tym jak wiadomość ma zostać wysłana, struktura z adresem odbierającego `*dest_addr`, jak i rozmiar tej struktury `addrlen`. Pomyślne zakończenie `sendto(2)` zwraca liczbę wysłanych bajtów, jednak nie gwarantuje dostarczenia wiadomości. W przypadku błędu zwracane jest `-1` i ustawiana jest odpowiednia wartość `errno`.

Wykonanie `connect(2)` na gnieździe klienta sprawia, że jądro sprawdza, czy nie występują jakieś błędy, np. o nieosiągalnej destynacji, ponadto zapisuje adres IP i port, po czym wraca do procesu, który je wykonał. Od tego momentu nie możemy już ustalić docelowego adresu IP ani portu dla operacji wysyłania. Oznacza to, że nie używamy już `sendto(2)`, tylko `write(2)` lub `send(2)`. Wszystko, co zostanie zapisane do podłączonego gniazda UDP będzie automatycznie wysyłane na adres podany w `connect(2)`. Podobnie, nie możemy używać `recvfrom(2)`, lecz `read(2)`, `recv(2)` lub `recvmsg(2)`.

### Zadanie 4 TODO

:::info
Przyjrzyjmy się warunkom brzegowym, które występują w trakcie używania interfejsu gniazd BSD. Kiedy [`read(2)`]() i [`write(2)`]() na gniazdach strumieniowych zwracają *short counts*? Skąd wiemy, że odebrany datagram nie został obcięty? Z jakich przyczyn należy być przygotowanym na to, że operacje na gniazdach zwrócą `EINTR`? Co się stanie, jeśli klient spróbuje zapisać do gniazda powiązanego z połączeniem, które serwer zdążył już zamknąć? Dlaczego w kodzie funkcji `open_listenfd` użyto wywołania [`setsockopt(2)`]() z opcją `SO_REUSEADDR`? Co by się stało gdyby programista o tym zapomniał?

***Wskazówka:** Zapoznaj się z §5.8 – §5.15 i §7.4.*
:::

`write(2)` może zwrócić *short count* w sytuacji, gdy w buforze gniazda nie ma wystarczająco miejsca, oznacza to że kernel nie mógł skopiować wszystkich danych. Gdy w buforze nie ma w ogóle miejsca, to natychmiastowo zwracany jest wtedy błąd `EWOULDBLOCK`. `read(2)` zwróci *short count*, gdy w buforze nie ma wystarczająco miejsca na odczytanie wszystkich danych. Oba wywołania mogą również zwrócić *short count*, gdy spowodują je ograniczenia wewnętrznego buforowania lub duże opóźnienia sieci.

Datagramy IP, UDP i TCP przechowują w nagłówku informacje o tym, jak dużo informacji jest w nich wysyłanych. Na podstawie tego możemy sprawdzić, czy otrzymany datagram dotarł w pełni, czy ucięty. Inną możliwością jest obliczenie sumy kontrolnej *(ang. checksum)*, a więc pewnej liczby uzyskanej za pomocą specjalnego algorytmu do zapewnienia integralności danych.

W idealnej sytuacji powinniśmy za każdym razem sprawdzać, czy nie został zwrócony błąd `EINTR` w trakcie jakiejś operacji na gniazdach, gdyż może on zostać dostarczony w trakcie wywoływania systemowego. Część *syscall*'i może być bardzo długo, potencjalnie w nieskończoność w przypadku `accept(2)`. Jeżeli takie polecenie zostanie przerwane, to w zależności od ustawionych flag i systemu operacyjnego, może zostać ono uruchomione ponownie lub zakończone z błędem - zwrócona wartość w takim przypadku będzie `-1` i `errno` zostanie ustawione na `EINTR`.

Może się zdarzyć taka sytuacja, że klient spróbuje coś zapisać do gniazda powiązanego z połączeniem, które serwer już zamknął. W takim przypadku klient będzie kilkukrotnie automatycznie ponawiał próby wysłania segmentu. Jeżeli w tym czasie serwer nie zostanie uruchomiony ponownie i wysłanie danych przez klienta nie powiedzie się, to zostanie zwrócony błąd. Jeżeli nie było żadnych odpowiedzi od serwera (a więc potencjalnie scrashował), to błędem będzie `ETIMEDOUT`. Gdy jakiś pośredni router ustalił, że serwer był nieosiągalny i przez ICMP zwrócił mówiącą o tym wiadomość, to błędem będzie `EHOSTUNREACH` lub `ENETUNREACH`.

Czym jest ICMP: *ICMP (ang. Internet Control Message Protocol) to protokół sieciowy służący do diagnostyki sieci i trasowania. Jeżeli coś nie działa poprawnie w TCP/IP, to ICMP przejmuje rolę narzędzia do rozwiązywania problemów i zgłasza błędy łączności między hostami.*

W kodzie funkcji `open_listenfd` użyto wywołania `setsockopt(2)` (służy ono do ustawiania opcji gniazda) z flagą `SO_REUSEADDR`. Opcja ta służy do zezwolenia na ponowne użycie adresu przez inny proces, bez konieczności oczekiwania na jego zwolnienie. Gdyby flaga ta nie była ustawiona, oczekiwanie na zwolnienie adresu mogłoby trwać nawet kilkadziesiąt sekund.

### Zadanie 5

:::info
Zmodyfikuj program `hostinfo.c` w taki sposób, aby wyświetlał adresy IPv4 oraz IPv6 dla danej nazwy serwera. Dodatkowo należy przekształcić nazwę usługi przekazanej jako opcjonalny trzeci parametr programu na numer portu. Poniżej przykład:

# hostinfo www.google.com https
216.58.215.68:443
[2a00:1450:401b:803::2004]:443

Co należałoby zrobić, żeby program rozpoznawał usługę o nazwie `tftp`?
:::

#include "csapp.h"

int main(int argc, char **argv) {
  struct addrinfo *p, *listp, hints;
  char buf[MAXLINE], srv[MAXLINE];
  int rc, flags;

  // strings for arguments given by argv[]
  const char *domain, *service;

  if (argc == 2) { // default ./hostinfo <domain> run
    domain  = argv[1];
    service = NULL;
  } else if (argc == 3) { // handling optional argument
    domain  = argv[1];
    service = argv[2];
  } else {
    app_error("usage: %s <domain name> [service (optional)]\n", argv[0]);
  }

  /* Get a list of addrinfo records */
  memset(&hints, 0, sizeof(struct addrinfo));
  // changed from AF_INET to AF_UNSPEC to handle IPv4 and IPv6 
  hints.ai_family   = AF_UNSPEC;   
  // changed from SOCK_STREAM to handle tftp
  hints.ai_socktype = 0; 
  
  /* Connections only */
  // Changed NULL to service to get info about it
  if ((rc = getaddrinfo(domain, service, &hints, &listp)) != 0)
    gai_error(rc, "getaddrinfo");

  /* Walk the list and display each IP address */
  /* Display address string instead of domain name */
  flags = NI_NUMERICHOST | NI_NUMERICSERV; 
  for (p = listp; p; p = p->ai_next) {
    Getnameinfo(p->ai_addr, p->ai_addrlen, buf, MAXLINE,
	            srv, MAXLINE, flags);
    
    if (service && p->ai_family == AF_INET6) // handle IPv6
      printf("[%s]:%s\n", buf, srv);
    else if (service)
      printf("%s:%s\n", buf, srv);
    else
      printf("%s\n", buf);
  }

  /* Clean up */
  freeaddrinfo(listp);

  return EXIT_SUCCESS;
}

Aby program rozpoznawał usługę `tftp`, należy zmienić `ai_socktype` na `0`. Oznacza to, że zaakceptowany zostanie każdy rodzaj gniazda.

### Zadanie 6

:::info
Zapoznaj się z kodem źródłowym serwera `echoserver.c` i klienta `echoclient.c` usługi podobnej do `echo`. Twoim zadaniem jest taka modyfikacja serwera, by po odebraniu sygnału `SIGINT` wydrukował liczbę bajtów odebranych od wszystkich klientów, po czym zakończył swe działanie.

Używając programu `watch` uruchom polecenie `netstat -ptn`, aby obserwować stan połączeń sieciowych. Wystartuj po jednym procesie serwera i klienta. Wskaż na wydruku końce połączenia należące do serwera i klienta. Następnie wystartuj drugą instancję klienta. Czemu nie zachowuje się ona tak samo jak pierwsza? Co zmieniło się na wydruku z `netstat`?
:::

Zadaniem serwera jest nasłuchiwanie na komunikaty klienta. Program działa podobnie do `echo`, wysłane przez klienta wiadomości są natychmiastowo zwracane przez serwer.

Kod klienta:

#include "csapp.h"
#include "rio.h"

int main(int argc, char **argv) {
  if (argc != 3)
    app_error("usage: %s <host> <port>\n", argv[0]);

  char *host = argv[1];
  char *port = argv[2];

  char buf[MAXLINE];
  rio_t rio;
  int clientfd;

  clientfd = Open_clientfd(host, port);
  rio_readinitb(&rio, clientfd);

  while (Fgets(buf, MAXLINE, stdin) != NULL) {
    Rio_writen(clientfd, buf, strlen(buf));
    Rio_readlineb(&rio, buf, MAXLINE);
    Fputs(buf, stdout);
  }
  Close(clientfd);

  return EXIT_SUCCESS;
}

Kod serwera (uzupełniony):

#include "csapp.h"
#include "rio.h"

#define LISTENQ 1

static size_t nread = 0;

static void sigint_handler(int sig) {
  /* TODO: Change control flow so that it does not return to main loop. */
  safe_printf("\nTotal bytes read: %ld.\n", nread);
  _Exit(0);
}

static void echo(int connfd) {
  size_t n;
  char buf[MAXLINE];
  rio_t rio;

  rio_readinitb(&rio, connfd);
  while ((n = Rio_readlineb(&rio, buf, MAXLINE))) {
    Rio_writen(connfd, buf, n);
    nread += n;
  }
}

int main(int argc, char **argv) {
  if (argc != 2)
    app_error("usage: %s <port>\n", argv[0]);

  Signal(SIGINT, sigint_handler);

  int listenfd = Open_listenfd(argv[1], LISTENQ);

  /* TODO: Print bytes received after SIGINT has been received. */
  // This is done in sigint_handler by printing the value of
  // global variable nread, which gets changed in echo function.

  while (1) {
    socklen_t clientlen = sizeof(struct sockaddr_storage);
    struct sockaddr_storage clientaddr; /* Enough space for any address */
    char client_hostname[MAXLINE], client_port[MAXLINE];
    int connfd = Accept(listenfd, (SA *)&clientaddr, &clientlen);
    Getnameinfo((SA *)&clientaddr, clientlen, client_hostname, MAXLINE,
                client_port, MAXLINE, 0);
    printf("Connected to %s:%s\n", client_hostname, client_port);
    echo(connfd);
    Close(connfd);
  }
}

Aby sprawdzić jak zachowa się dokładnie połączenie sieciowe, należy w kilku okienkach terminala odpalić poniższe polecenia:

[1 terminal] $ ./echoserver 1234 <- ten port przekazujemy do grepa
[2 terminal] $ watch "netstat -ptn | grep 1234"
[3 terminal] $ ./echoclient localhost 1234
[4 terminal] $ ./echoclient localhost 1234

Po podłączeniu pierwszego klienta, serwer powiadomi o pierwszym połączeniu poprzez `Connected to localhost:45054`:

Active Internet connections (w/o servers)
Proto Recv-Q Send-Q Local Address           Foreign Address         State       PID/Program name
tcp        0      0 127.0.0.1:45054         127.0.0.1:1234          ESTABLISHED 21339/./echoclient
tcp        0      0 127.0.0.1:1234          127.0.0.1:45054         ESTABLISHED 21329/./echoserver

Po uruchomieniu drugiego klienta i wysłaniu jakiejś wiadomości przez niego, nie zostanie nic do niego zwrócone przez serwer. Jest to spowodowane tym, że serwer aktualnie jest zajęty obsługą pierwszego klienta, o czym mówi poniższy wydruk:

Active Internet connections (w/o servers)
Proto Recv-Q Send-Q Local Address           Foreign Address         State       PID/Program name
tcp       14      0 127.0.0.1:1234          127.0.0.1:45068         ESTABLISHED -
tcp        0      0 127.0.0.1:45054         127.0.0.1:1234          ESTABLISHED 21339/./echoclient
tcp        0      0 127.0.0.1:1234          127.0.0.1:45054         ESTABLISHED 21329/./echoserver
tcp        0      0 127.0.0.1:45068         127.0.0.1:1234          ESTABLISHED 21465/./echoclient

Po wyłączeniu pierwszego klienta serwer automatycznie połączy się z drugim klientem, o czym poinformuje wysyłając wiadomość `Connected to localhost:45068`. Wszystkie przesłane wiadomości przez klienta nr 2 zostaną automatycznie do niego zwrócone przez serwer.

### Zadanie 7

:::info
Serwer z poprzedniego zadania nie radził sobie ze współbieżną obsługą wielu połączeń. Serwer z pliku `echoclient-fork.c` naprawia to poważne ograniczenie z użyciem wywołania `fork`. Zadaniem głównego procesu jest odbieranie połączeń i delegowanie ich obsługi do podprocesów.

Proces serwera musi zliczać liczbę bajtów odebranych od klientów. W tym celu przydziela dzieloną pamięć anonimową, w której przechowuje tablicę `client`. Przy starcie podprocesu umieszcza w tablicy odpowiedni wpis za pomocą procedury `addclient`. Żeby uniknąć wyścigów każdy podproces zwiększa własny licznik `nread`. Po zakończeniu podprocesu należy wywołać procedurę `delclient`, która doda zawartość prywatnego licznika klienta, do globalnego licznika serwera.

W dowolnym momencie działanie serwera może zostać przerwane przy pomocy sygnału `SIGINT`. Należy wtedy poczekać na zakończenie podprocesów i wydrukować zawartość globalnego licznika serwera. Poniżej przykładowy wydruk z sesji serwera:

# ./echoserver-fork 8000
[9047] Connected to localhost:36846
[9105] Connected to localhost:36850
[9047] Disconnected!
^C
Server received quit request!
[9105] Disconnected!
Server received 22 bytes
#

:::

#include "csapp.h"
#include "rio.h"

#define LISTENQ 10
#define MAXCLIENTS (PAGE_SIZE / sizeof(client_t))

typedef struct client {
  pid_t pid;    /* Client process id */
  size_t nread; /* Numer of bytes received so far */
} client_t;

/* TODO: Need to define context to be used with sigsetjmp & siglongjmp. */
static client_t *client = NULL;
static sig_atomic_t nclients = 0;
static size_t nread = 0; /* number of bytest received on all connections */

static client_t *findclient(pid_t pid) {
  for (int i = 0; i < MAXCLIENTS; i++)
    if (client[i].pid == pid)
      return &client[i];
  return NULL;
}

static client_t *addclient(void) {
  client_t *c = findclient(0);
  if (c) {
    c->pid = -1; /* XXX: must be filled in after fork */
    c->nread = 0;
    nclients++;
  }
  return c;
}

static void delclient(pid_t pid) {
  client_t *c = findclient(pid);
  assert(c != NULL);
  nread += c->nread;
  c->pid = 0;
  nclients--;
}

static void sigchld_handler(int sig) {
  pid_t pid;
  /* TODO: Delete clients as they die. */
  // just go through the list of all clients and if any of them stopped
  // working, print the message and delete the client
  for (int i = 0; i < MAXCLIENTS; i++) {
    pid = client[i].pid;
    if (pid && Waitpid(pid, NULL, WNOHANG)) {
      safe_printf("[%d] Disconnected!\n", pid);
      delclient(pid);
    }
  }
}

static void sigint_handler(int sig) {
  safe_printf("Server received quit request!\n");
  /* TODO: Change control flow so that it does not return to main loop. */
  // we need to wait for all clients to stop working, thus we do not stop
  // the server immediately, but we wait until everyone is disconnected
  sigset_t mask;
  sigfillset(&mask);
  sigdelset(&mask, SIGCHLD);
  Sigprocmask(SIG_SETMASK, &mask, NULL);
  
  while (nclients > 0)
    Sigsuspend(&mask);

  safe_printf("\nTotal bytes read: %ld.\n", nread);
  _Exit(0);
}

static void echo(client_t *c, int connfd) {
  size_t n;
  char buf[MAXLINE];
  rio_t rio;

  rio_readinitb(&rio, connfd);
  while ((n = Rio_readlineb(&rio, buf, MAXLINE))) {
    Rio_writen(connfd, buf, n);
    c->nread += n;
  }
}

int main(int argc, char **argv) {
  if (argc != 2)
    app_error("usage: %s <port>\n", argv[0]);

  sigset_t sig_mask;
  sigemptyset(&sig_mask);
  sigaddset(&sig_mask, SIGCHLD);

  Signal(SIGCHLD, sigchld_handler);
  Signal(SIGINT, sigint_handler);

  client = Mmap(NULL, PAGE_SIZE, PROT_READ | PROT_WRITE, 
	            MAP_ANON | MAP_SHARED, -1, 0);

  int listenfd = Open_listenfd(argv[1], LISTENQ);

  /* TODO: Wait for all clients to quit and print a message with nread. */
  // As in previous exercise, it is done in sigint_handler.

  while (1) {
    socklen_t clientlen = sizeof(struct sockaddr_storage);
    struct sockaddr_storage clientaddr; /* Enough space for any address */
    int connfd = Accept(listenfd, (SA *)&clientaddr, &clientlen);

    static char client_hostname[MAXLINE], client_port[MAXLINE];
    Getnameinfo((SA *)&clientaddr, clientlen, client_hostname, MAXLINE,
                client_port, MAXLINE, 0);

    sigset_t mask;
    Sigprocmask(SIG_BLOCK, &sig_mask, &mask);

    /* TODO: Start client in subprocess, close unused file descriptors. */
    client_t *client = addclient();

    pid_t pid = Fork();
    if (pid == 0) {
      Close(listenfd);
      Signal(SIGINT, SIG_IGN);
      echo(client, connfd);
      Close(connfd);
      _Exit(0);
    }

    client->pid = pid;
    Close(connfd);
    printf("[%d] Connected to %s:%s\n", pid, client_hostname, client_port);

    Sigprocmask(SIG_SETMASK, &mask, NULL);
  }
}