@Sztakler

# SO Lista 7

## Zadanie 1

### Definicje


**Odwzorowanie plików w pamięć** (ang. *memory-mapped file*) -- mapowanie fragmentów pliku lub zasobu plikopodobnego między pamięcią fizyczną a wirtualną w sposób bezpośredni, bajt po bajcie. Strony są ładowane z pliku w sposób leniwy, gdy zajdzie taka potrzeba ze strony programu.
**Odwzorowanie pamięci anonimowej** (ang. *anonymous mapping*) -- mapowanie adresów fizycznych na wirtualne, któremu nie odpowiada żaden plik. Strony są inicjalizowane zerami.


**Odwzorowanie prywatne** (ang. *MAP_PRIVATE*) -- wszelkie modyfikacje zmapowanej pamięci są lokalne, widoczne jedynie dla danego procesu, a zmiany nie są zapisywane w pliku. Pozostałe procesy, które odnoszą się do danego zasobu nie widzą tych zmian. Odwzorowanie prywatne jest wykonywane przez **kopiowanie przy zapisie** (ang. *Copy On Write -- COW*). Przy próbie modyfikacji zawartości strony przez pewien proces jądro systemu tworzy kopię strony przypisaną temu procesowi, a wszelkie modyfikacje są wprowadzane tylko na tej kopii. Rozwiązanie to eliminuje problem występujący w sytuacji, gdy kilka procesów próbuje modyfikować zawartość jednego fragmentu pamięci.
**Odwzorowanie dzielone** (ang. *MAP_SHARED*) -- modyfikacje wprowadzane na odwzorowanym fragmencie pamięci są widoczne dla wszystkich dzielących go procesów i zapisywane do pliku.

### Jaką wartością jest wypełniana pamięć wirtualna należąca do tych odwzorowań

Jest wypełniana zerami.

### Czym różni się odwzorowanie prywatne od dzielonego

Odwzorowanie prywatne przypisuje nową kopię fragmentu pamięci dla danego procesu. Wszelkie modyfikacje tego fragmentu są widoczne jedynie dla tego procesu i nie są zapisywane na oryginalnym pliku.

W odwzorowaniu dzielonym wszystkie procesy pracują na orginalnym fragmencie i wprowadzone przez nie modyfikacje są zapisywane do pliku.


### Czy pamięć obiektów odwzorowanych prywatnie może być współdzielona

Zanim proces, który posiada odwzorowanie prywatne, spróbuje wykonać modyfikację danej strony, współdzieli ją z innymi procesami. Dopiero po próbie zapisu jądro dokonuje przypisania mu kopii danej strony.

Rodzic może dzielić obiekt odwzorowany prywatnie ze swoim dzieckiem (utworzonym przez `fork`).

### Czemu można tworzyć odwzorowania plików urządzeń blokowych w pamięć, ale plików znakowych już nie

Urządzenia blokowe są przeszukiwalne, tzn. możemy ustalić pozycję kursora w pliku, iterować się po nim. Urządzenia znakowe nie pozwalają na to, można je czytać tylko sekwencyjnie.

## Zadanie 2

[Rozdz. 49] https://mwatler.github.io/unx511/The%20Linux%20Programming%20Interface%20-%20A%20Linux%20and%20UNIX%20System%20Programming%20Handbook.pdf#G40.1106170

### Scenariusze użycia prywatnych i dzielonych odzworowań plików w pamięć albo do pamięci anonimowej

* *Private file mapping* -- inicjalizuje mapowany region zawartością pliku. Na początku różne procesy mapujące ten sam plik dzielą ze sobą fizyczne strony w pamięci, ale przy próbie zapisu mechanizm *COW (copy on write)* przydziela zapisującemu procesowi kopię, niewidoczną dla innych procesów. Ta forma mapowania jest używana do inicjalizacji regionu z pamięci za pomocą zawartości pliku, np. przy inicjalizacji segmentów *text* i *data* danego pliku wykonywalnego albo biblioteki współdzielonej.
* *Private anonymous mapping* -- każde wywołanie `mmap()` tworzy nowe mapowanie, nie dzielące fizycznych stron z innymi anonimowymi mapowaniami procesu (niekoniecznie tego samego). Chociaż dziecko utworzone przez `fork()` dzieli ze swoim rodzicem mapowania, to mechanizm *COW* zapewnia, że nie będą one widziały nawzajem zmian wprowadzonych w pliku przez drugi proces. Główną rolą tego mapowania jest alokowanie nowej (wypełnionej zerami) przestrzeni w pamięci dla danego procesu, np. podczas użycia `malloc()` przy alokowaniu dużych bloków pamięci.
* *Shader file mapping* -- wszystkie procesy mapujące ten sam obszar w pliku współdzielą fizyczne strony pamięci, inicjalizowane zawartością pliku. Wszelkie modyfikacje pliku są w nim zapisywane. Pozwala to na *memory-mapped I/O*, tzn. plik jest załadowany do pamięci wirtualnej procesu, a wszelkie zmiany w pliku są w nim natychmiastowo zapisywane. Można użyć tych własności do implementacji alternatywnych operacji I/O na pliku względem standardowych `read()` i `write()`. Innym użyciem tej metody mapowania jest umożliwienie niespokrewnionym ze sobą procesom dzielenia fragmentu pamięci w celu wykonywania bardzo szybkich operacji IPC.
* *Shared anonymous mapping* -- każde wywołanie `mmap()` tworzy nowe mapowanie, które nie dzieli stron pamięci z żadnym innym mapowaniem. W odróżnieniu od prywatnego mapowania anonimowego strony nie są kopiowane przy zapisie, co sprawia, że kiedy dziecko dziedziczy mapowanie przy `fork()`, zaczyna dzielić pewne strony pamięci ze swoim rodzicem i zmiany wprowadzone przez jeden z tych procesów są widczne dla drugiego. Ta metoda mapowania pozwala na operacje IPC, ale wyłącznie między spokrewnionymi procesami.

### Jak utworzyć za pomocą `mmap(2)` dane odwzorowanie

Używamy procedury `mmap()`.

#include <sys/mman.h>

void *mmap(void *addr, size_t length, int prot, int flags,
           int fd, off_t offset);

* `addr` -- adres w pamieci wirtualnej, pod którym ma zostać umieszczone mapowanie (jeśli ustawione jako NULL, wtedy jądro samo wybiera odpowiedni adres; jest to preferowane rozwiązanie),
* `length` -- określa długość mapowania w bajtach. Nie musi być wielokrotnością rozmiaru strony, ale jądro i tak zaokrągli tę wartość w górę do najbliższej wielokrotności.
* `prot` -- maska przechowująca uprawnienia dla mapowania. Jest to albo `PROT_NONE` albo alternatywa bitowa `PROT_READ`, `PROT_WRITE` i `PROT_EXEC`.
* `flags` -- maska bitowa, ustalająca rodzaj mapowania. Może to być `MAP_PRIVATE` lub `MAP_SHARED` dla mapowania prywatnego lub dzielonego. Może być również alternatywą powyższych i innych flag.
* `fd` -- deksryptor mapowanego pliku. Ignorowany dla mapowania anonimowego.
* `offset` -- ustala pozycję w pliku, od którego zaczyna sie mapowanie. Jeśli ustawiony na 0, a `length` jest równy rozmiarowi pliku, wtedy zmapujemy cały plik. Ignorowany dla mapowania anonimowego.

### Co się dzieje z odwzorowaniem po forku

Dziecko dziedziczy mapowanie po swoim rodzicu. W przypadku mapowania prywatnego mechanizm *COW* zapewnia, że oba procesy nie będą widziały wzajemnie zmian wprowadzanych na swoich kopiach mapowania. Przy mapowaniu dzielonym procesy współdzielą zmapowane strony pamięci.

### Jakiego typu odwzorowania tworzy execve
https://stackoverflow.com/questions/64048588/why-execve-function-map-private-areas

`execve()` tworzy odwzorowania prywatne. Ma to uchronić system przed sytuacją, gdzie dwa osobne programy (rodzic i dziecko po `execve()`) mają dostęp do tej samej pamięci.

### Jak jądro automatycznie zwiększa rozmiar stosu do ustalonego limitu?

https://unix.stackexchange.com/questions/63742/what-is-automatic-stack-expansion

Jeśli proces odwoła się do pamięci stosu, która nie jest zaalokowana, wywoła `pagefault`. Jądro spróbuje rozszerzyć stos tak, żeby następna próba dostępu zakończyła się sukcesem. Jeśli przy rozszerzaniu jądro dotrze do górnego limitu stosu, wtedy nie jest w stanie go rozszerzyć.


Prawdopodobnie za pomocą wywołania systemowego `setrlimit`.
https://linux.die.net/man/2/setrlimit

int getrlimit(int resource, struct rlimit *rlim);
int setrlimit(int resource, const struct rlimit *rlim); 

Jeśli wywołanie to przyjmie `resouce = RLIMIT_STACK`, wtedy ustawi `rlimit` jako limit pamięci dla stosu.


### Kiedy jądro wysyła sygnał `SIGBUS` do procesu
https://www.man7.org/linux/man-pages/man2/mmap.2.html

Jądro wysyła do procesu posiadającego mapowanie w pamięć sygnał `SIGBUS`, kiedy zażąda on dostępu do strony w buforze, która leży za końcem zmapowanego pliku. Jądro może zareagować na ten sygnał, np. przez próbę rozszerzenia pliku.

https://mwatler.github.io/unx511/The%20Linux%20Programming%20Interface%20-%20A%20Linux%20and%20UNIX%20System%20Programming%20Handbook.pdf#G40.1106170

## Zadanie 3

### Działanie polecenia

$ cat /proc/$(pgrep Xorg)/status | egrep 'Vm|RSS'
VmPeak:	 1309784 kB
VmSize:	 1196492 kB
VmLck:	       0 kB
VmPin:	       0 kB
VmHWM:	  208272 kB
VmRSS:	  131208 kB
VmData:	  115876 kB
VmStk:	     132 kB
VmExe:	    1852 kB
VmLib:	  112492 kB
VmPTE:	     720 kB
VmSwap:	   20744 kB

### Znaczenie poszczególnych pól

* *VmPeak* -- największy rozmiar pamięci wirtualnej,
* *VmSize* -- obecny rozmiar pamięci wirtualnej,
* *VmLck* -- rozmiar pamięci zablokowanej,
* *VmPin* -- rozmiar przypiętej pamięci (strony, które nie mogą zostać przeniesione, ponieważ coś wymaga bezpośredniego dostępu do fizycznej pamięci, na którą wskazują),
* *VmHWM* -- maksymalny rozmiar zbioru rezydentnego,
* *VmRSS* -- rozmiar zbioru rezydentnego, jest sumą:
* RssAnon -- odwzorowana anonimowo,
* RssFile -- odwzorowana z pliku,
* RssShmem -- dzielona część zbioru rezydentnego, dokładniej dzielone odwzorowania anonimowe, tmpfs (temporary file system) i pamięci dzielonej System V,
* *VmData* -- rozmiar danych (nie są to dokładne dane -- lepiej /proc/[pid]/statm),
* *VmStk* -- rozmiar stosu (nie są to dokładne dane -- lepiej /proc/[pid]/statm),
* *VmExe* -- rozmiar segmentu `text` (nie są to dokładne dane -- lepiej /proc/[pid]/statm),
* *VmLib* -- rozmiar kodu biblioteki współdzielonej,
* *VmPTE* -- rozmiar tablicy stron,
* *VmSwap* -- rozmiar pamięci wirtualnej zeswapowanej przez anonimowe strony prywatne (nie są to dokładne dane -- lepiej /proc/[pid]/statm).


### Zbiór roboczy i rezydentny

**Zbiór rezydentny** -- strony, które dany proces przechowuje w pamięci operacyjnej. Można uzyskać do nich dostęp bez wywoływania `page fault`.
**Zbiór roboczy** -- podzbiór zbioru rezydentnego, potrzebny do wykonywania procesu.

Rozmiar zbioru roboczego jest trudny do dokładnego ustalenia. System przybliża jego rozmiar rozmiarem zbioru rezydentnego.

### Łączny rozmiar VmRSS i VmSize

from glob import glob
from re import findall

path = "/proc/*"
directories = glob(path)

VmRSS_total_size = 0
VmSize_total_size = 0

for directory in directories:
    # print(directory)
    
    try:
        file = open(f"{directory}/status", "r")
        file_content = file.read()

        
    except:
        # print(f"read: {directory}: is not a directory.")
        continue

    for line in file_content.split("\n"):
        if "VmRSS" in line:
            VmRSS_total_size  += int(findall(r'\d+', line)[0])
        if "VmSize" in line:
            VmSize_total_size += int(findall(r'\d+', line)[0])

print(f"Total VmSize: {VmSize_total_size} kB\nTotal VmRSS:  {VmRSS_total_size} kB")

Wydruk programu:
Total VmSize: 879348788 kB
Total VmRSS:  8118176 kB

Wydruk vmstat -s
Pamięć razem:                    8058112 K
Pamięć użyta:                    6087952 K
Pamięć aktywna:                  5615216 K
Pamięć nieaktywna:               1495460 K
Pamięć wolna:                     310872 K
Pamięć buforów:                    49048 K
Pam. podr. obsz. wymiany:        1610240 K
Obszar wymiany razem:            1818096 K
Obszar wymiany użyty:             659200 K
Obszar wymiany wolny:            1158896 K
Cykli CPU użytk. zwykłych:       1801052
Cykli CPU użytk. z nice:            5045
Cykli CPU systemowych:            633648
Cykli CPU bezczynności:         19300685
Cykli CPU oczek. na we/wy:          6364
Cykli CPU w IRQ:                       0
Cykli CPU w softirq:              215982
Cykli CPU skradzionych:                0
Stron wczytanych z dysku:        5756720
Stron usuniętych z pam.:         7091221
Stron z pamięci wymiany:            8770
Stron do pamięci wymiany:         172912
Przerwań:                       71134535
Przełączeń kontekstu CPU:      388083889
Czas rozruchu:                1637572395
Odgałęzień procesów:               48065

Różnice między napisanym programem, a wynikiem `vmstat -s` wynikają z faktu, że zbiory rezydentne procesu nie zawsze są rozłączne. Część pamięci jest dzielona między procesami i w takim wypadku program w pythonie policzy ją wielokrotnie.

### Zadanie 4

### Jak jądro obsługuje błąd stronicowania


Błąd obsługi stronicowania występuje w trzech sytuacjach:
* próbujemy dostać się do nieistniejącej strony (segfault),
* próbujemy dostać się do strony, która nie istnieje w RAMie (page fault),
* próbujemy dostać się do strony, do której nie mamy uprawnień (segfault).

Algorytm sprawdza, który z powyższych przypadków ma miejsce. Jeśli jest to pierwszy z nich, wtedy jądro nie jest w stanie naprawić tego błędu i zabija proces sygnałem `SIGSEGV`.

W drugim scenariuszu jądro wykrywa `pagefault` i próbuje wydobyć z dysku do RAMu odpowiednią stronę. Postępuje w sposób omawiany na wcześniejszych ćwiczeniach.

Ostatni scenariusz również nie może zostać naprawiony. Proces zostaje zabity przez `SIGSEGV`.

`SIGSEGV` występuje w dwóch smakach:

https://elixir.bootlin.com/linux/latest/source/include/uapi/asm-generic/siginfo.h#L224

### Jakie dane procesor musi dostarczyć, żeby umożliwić obsługę błąd stronicowania

Procesor przekaże jądru cztery wartości:

`fault_addr` -- adres strony, którą próbowaliśmy odczytać,
`fault_pc` -- adres instrukcji, która wywołała błąd,
`fault_size` -- ile bajtów próbowano odczytać,
`_prot` -- maska zawierająca uprawnienia, z którymi próbowano dostępu.

### Do czego służą struktury `mm_struct::pgd` i `mm_struct::mmap` z `include/linux/mm_types.h`

https://elixir.bootlin.com/linux/latest/source/include/linux/mm_types.h

`mmap` -- zawiera listę wszystkich segmentów odwzorowanych w przestrzeń adresową procesu (vm_area_struct). Każda struktura w tej liście zawiera adres początku i końca zmapowanego fragmentu, jego flagi, uprawnienia, itd.
`pgd` -- wskaźnić na tablicę stron procesu.

### Kiedy jądro wyśle procesowi sygnał `SIGSEGV` z kodem `SEGV_MAPPER`, a kiedy z kodem `SEGV_ACCERR`


There are two common kinds of SEGV, which is an error that results from an invalid memory access:

    A page was accessed which had the wrong permissions. E.g., it was read-only but your code tried to write to it. This will be reported as SEGV_ACCERR.
    A page was accessed that is not even mapped into the address space of the application at all. This will often result from dereferencing a null pointer or a pointer that was corrupted with a small integer value. This is reported as SEGV_MAPERR.

### Kiedy występują pomniejsze usterki strony (ang. *minor page fault*), a kiedy poważne usterki strony (ang. *major page fault*)

Poważna usterka występuje w sytuacji, gdy strona, do której usiłujemy uzyskać dostęp nie znajduje się w pamięci. Jądro musi znaleźć wolne miejsce w pamięci (lub je zwolnić), a następnie wczytać stronę do pamięci, dodać dotyczące jej wpis w MMU i oznaczyć ją jako wczytaną.

Pomniejsze usterki pojawiają sie, gdy strona jest już załadowana do pamięci w momencie pojawienia się błędu, ale nie została jeszcze oznaczona w MMU (Memory Management Unit) jako wczytana. Jądro naprawia tę usterkę poprzez dodanie wpisu w MMU o tej stronie i oznaczenie jej jako wczytaną. Nie musi wczytywać strony do pamięci.

### Rola bufora stron w systemie (ang. *page cache*)

Kąkuter nie lubi marnować zasobów, dlatego woli przeznaczyć nieużywany RAM na bufor stron. Dyski są względnie powolne, operacje odczytu i zapisu trwają nieporównywalnie dłużej niż w przypadku RAMu, stąd pomysł na przechowywanie części już wczytanych danych z dysku w pamięci.

By przyspieszyć odczyt i zapis danych na dysku część stron jest przechowywanych we fragmencie RAMu -- buforze stron. Wszystkie zapisy są zapisywane tylko w buforze, a informacja o zmodyfikowane strony są oznaczone bitem `dirty`. Zapis na dysk następuje przy `sync()` lub `fsync()`, *brudne* strony są do niego przepisywane.

Takie rozwiązanie przyspiesza odczyty i zapisy z danej strony, ponieważ nie ma już konieczności wydobywania jej za każdym razem z dysku, co jest bardzo powolną operacją, ale z RAMu -- znacznie szybszej pamięci.

![Uploading file..._e14w5lxxg]()

## Zadanie 5

### Co jądro przechowuje w strukturze `vm_area_struct`

https://linux-kernel-labs.github.io/refs/heads/master/labs/memory_mapping.html

* vm_start, vm_end - the beginning and the end of the memory area, respectively (these fields also appear in /proc/<pid/maps);
* vm_file - the pointer to the associated file structure (if any);
* vm_pgoff - the offset of the area within the file;
* vm_flags - a set of flags `unsigned long vm_flags; /* Flags, see mm.h. */`;
* vm_ops - a set of working functions for this area
* vm_next, vm_prev - the areas of the same process are chained by a list structure
* `pgprot_t vm_page_prot; /* Access permissions of this VMA. */` protection flags for this mapping

### Jak jądro zmodyfikuje `mm_struct` w trakcie pierwszego odczytu ze strony `p` należącej do `D`, a jak w trakcie póżniejszego pierwszego zapisu do `p`.

Strony są odczytywywane leniwie, więc jeżeli dana strona nie występuje w RAMie, wtedy wystąpi `pagefault` i jądro spróbuje wydobyć stronę z dysku.

Pierwszy zapis zakończy się `pagefaultem`, ponieważ nowy proces posiada tylko uprawnienia `read only`. Jądro następnie musi sprawdzić, czy dany segment na dysku ma uprawnienia `read` i `write` oraz ustawioną flagę `copy on write`. Jeśli tak, wtedy tworzy kopię strony i przypisuje ją do procesu. Wykonanie zapisu do kopii zakończy się powodzeniem, ponieważ będzie miała prawidłowe uprawnienia -- `read` i `write`.

### Co jądro musi zrobić z tablicą stron procesu podczas `fork()`

Wszystkie strony tablicy stron rodzica zostają przepisane do dziecka, ale z uprawnieniami `read only`. Oba procesy ustawiają na stronach flagę `copy on write`.

### Czemu jądro nie musi kopiować tablicy stron z rodzica do dziecka

Skoro mamy odwzorowanie prywatne, zatem procesy mogą początkowo współdzielić tablice stron odwzorowania. Zostaną one zamienione na nowe dla danego procesu dopiero, gdy spróbuje on wprowadzić zmiany w danej stronie (*copy on write*).


## Zadanie 6

### Definicje

**Stronicowanie na żądanie** (ang. *demang paging*) -- strony są ładowane z dysku do RAMu dopiero, gdy dany proces spróbuje odczytać lub zapisać dane do tej strony.

### Czy mamy gwarancję, że program nie zobaczy modyfikacji zawartości pliku dokonanych po utworzeniu prywatnego odwzorowania pliku w pamięć

Nie mamy takiej gwarancji. Pewien fragment mapowanego pliku może nie zostać od razu wciągnięty do pamięci. Jeśli w tym czasie wprowadzimy w nim zmiany, a następnie spróbujemy sprowadzić z dysku, wtedy program zobaczy jego zmodyfikowaną wersję.

### Co złego mogłoby się stać, gdyby system operacyjny pozwolił modyfikować plik wykonywalny, który jest uruchomiony

Wprowadzanie zmian w, np. sekcji `.text` pliku wykonywalnego (np. w opisanym wyżej scenariuszu) może skutkować nieoczekiwanymi, trudnymi do zlokalizowania błędami. Co więcej, takie błędy mogą pojawić się dopiero, gdy program załaduje do pamięci zmodyfikowany fragment z dysku, co w niektórych przypadkach może stać się długo po wprowadzeniu zmian w pliku.

Prawdopodobnie napotkamy standardowy zestaw problemów, tzn:
* crashowanie programu,
* nieoczekiwane zachowanie programu,
* podatność na błędy i ataki ze strony użyszkodników.

Tu jest coś napisane:
https://lwn.net/Articles/866493/

https://unix.stackexchange.com/questions/187931/modifying-binary-during-execution

https://unix.stackexchange.com/questions/138214/how-is-it-possible-to-do-a-live-update-while-a-program-is-running

https://unix.stackexchange.com/questions/88487/what-happens-if-you-edit-a-script-during-execution

## Zadanie 7

### Zmodyfikowany kod z tworzeniem podprocesów

#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. */
  if (right - left >= FORKSORT_MIN)
  {
    pid = Fork();
    if (pid > 0)
      return pid;
  }


  if (left < right) {
    if (right - left <= INSERTSORT_MAX) {
      InsertionSort(table, left, right);
    } else {
      size_t pivot = left + random() % (right - left + 1);
      size_t split = Partition(table, left, right, table[pivot]);

      if (left == split) {
        SwapElem(table, left, pivot);
        split++;
      } else {
        pid_left = QuickSort(table, left, split - 1);
      }

      pid_right = QuickSort(table, split, right);

      /* TODO: Wait for possible children and exit if created a subprocess. */

      if (pid_left != -1)             // has left child
        Waitpid(pid_left, NULL, 0);
      if (pid_right != -1)            // has right child
        Waitpid(pid_right, NULL, 0);
      if (!pid)                       // created a subprocess
        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... */
  /* Creating a table using mmap with permission to read and
   * write, shared between processes and located in anonymous 
   * memory
   */
  long* table = Mmap(NULL, size, PROT_READ | PROT_WRITE, MAP_SHARED | MAP_ANONYMOUS, -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;
}

### Czasy dla wersji bez podprocesów

$ /usr/bin/time -p ./forksort
real 20.55
user 20.07
sys 0.48

### Czasy dla wersji z podprocesami

$ /usr/bin/time -p ./forksort
real 6.26
user 27.01
sys 1.39

### Prawo Amdahla

Prawo Amdahla określa granicę wzrostu prędkości przy wprowadzeniu implementacji równoległej algorytmu, względem implementacji szeregowej. Stosując powyższy wzór zauważamy, że dla P (procent programu, który może zostać zrównoleglony) i przy użyciu N procesorów możemy zauważyć wzrost:

Zauważmy, że dla P różnego od 1 (pewna część programu nie może zostać zrównoleglona) wyrażenie będzie dążyło do wartości $\frac{1}{1-P}$ przy wzroście liczby procesorów. Istnieje więc pewna granica przyspieszenia, której nie jesteśmy w stanie przekroczyć i wynika ona z faktu, że pewna część programu nie daje się zrównoleglić.

Z tego powodu w naszym eksperymencie uzyskaliśmy przyspieszenie nieproporcjonalne do liczby zastosowanych podprocesów.

### Których podprocedur nie da się zrównoleglić

Procedura `Partition` oraz `InsertSort` nie nadają się do zrównoleglenia, ze względu na swój charakter (muszą operować na wszystkich elementach podtablicy jednocześnie).

## Zadanie 8


#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);
      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. */
  size_t db_byte_size = size * sizeof(entry_t);
  
  Ftruncate(fd, db_byte_size);

  db->name = strdup(name);  
  db->size  = size;
  db->entry = Mmap(NULL, db_byte_size, PROT_READ | PROT_WRITE, MAP_SHARED, fd, 0);

  // https://man7.org/linux/man-pages/man2/madvise.2.html
  // Informujemy jądro, że będziemy odwoływać się w sposób losowy do pamięci
  // o rozmiarze db->size * sizeof(entry_t) rozpoczynającą się pod adresem db->entry
  Madvise(db->entry, db_byte_size, 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. */
  size_t db_byte_size = db->size * sizeof(entry_t);
  Madvise(db->entry, db_byte_size, 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ępuje stary plik
  Munmap(db->entry, db_byte_size);

  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. */
  struct stat st;
  Fstat(STDIN_FILENO, &st); // zwróci informacje o pliku do struktury buf

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

  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;
}