# Lista 7
###### tags: `SO2022`


:::spoiler

:::

## Deklaracja
:::spoiler

| Zadanie | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|-----------|---|---|---|---|---|---|---|---|
|Deklaracja |:heavy_check_mark:|:heavy_check_mark:|:heavy_check_mark:|:heavy_check_mark:|:heavy_check_mark:|?|:heavy_check_mark:|:heavy_check_mark:|
:::

## Zadanie 1

* ### Wyjaśnij słuchaczom różnicę między
* **odwzorowanie plików w pamięć** (ang. memory-mapped files)
* pliki są ładowane do pamięci na żądanie
* strony są pobierane z pliku

* **odwzorowaniami pamięci anonimowej** (ang. anonymous mappings)
* nie ma odpowiadającego pliku
* strony są inicjalizowane zerami

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

* **prywatne** - modyfikacja zawartości nie jest widoczna dla innych procesów (najpierw przed modyfikacją jest widoczna, potem dzięki COW jest przenoszona do oddzielnej kopii strony)
* **dzielone** - modyfikacja zawartości jest wudoczna dla innych procesów

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

Dzięki CoW istnieje taka możliwość, na początku (np. po Forku) procesy współdzielą pamięć prywatną, a dopiero podczas zapisu do tej pamięci tworzą prywatne kopie niewidoczne dla innych

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

Chodzi o to, że urządzenia znakowe są abstrakcją nad prostą transmisją strumieniową, więc podpięcie ich pod pamięć nie ma żadnej oczywistej interpretacji

## Zadanie 2

* ### Podaj scenariusze użycia prywatnych i dzielonych odwzorowań plików w pamięć albo pamięci anonimowej.

* **Prywatne mapowanie plików**
Inicjowane z pliku, wiele procesów dzieli to mapowanie, a dzięki CoW nie widzą zmian wprowadzonych przez inne procesy
:::spoiler
:::

* **Prywatne anonimowe mapowanie**
Inicjowane przez mmap(), prywatne dla procesu, w przypadku Fork uruchamiana jest procedura CoW
:::spoiler
:::
* **Dzielone mapowanie plików**
Wszystkie procesy dzielą to samo mapowanie i automatycznie widzą zmiany wprowadzane do pliku, Jest to alternatywa do używania read() i write()
:::spoiler
:::

* **Dzielone anonimowe mapowanie**
Wszystkie procesy dzielą to samo mapowanie i mogą zobaczyć wszystkie zmiany wprowadzane przez inne procesy
:::spoiler
:::

* ### Pokaż jak je utworzyć z użyciem wywołania `mmap(2)`.

* **addr** - NULL lub miejsce w którym chcemy umieścić mapowanie, zasadniczo używa się NULL aby to jądro mogło wybrać odpowiednie miejsce
* **length** - rozmiar mapowania w bajtach, nie musi być wielokrotnością rozmiaru strony, jądro zaokrągli automatycznie
* **prot** - prawa dostępu do pamięci PROT_NONE (brak) lub dowolna kombinacja pozostałych trzech
* **flags** Jedna z tych dwóch flag musi być zawarta: MAP_PRIVATE lub MAP_SHARED

:::spoiler **Przykłady użycia**

**map_private anon mapping**

**map_shared anon mapping**
:::

* ### Co się dzieje z odwzorowaniami po wywołaniu fork(2)?
Za pomocą mechanizmu CoW dbamy o to, aby oba procy nie widziały swoich zmian, a jednocześnie nie powielamy mapowania gdy nie jest to konieczne

* ### Czy wywołanie execve(2) tworzy odwzorowania prywatne czy dzielone?


* ### W jaki sposób jądro systemu automatycznie zwiększa rozmiar stosu do ustalonego limitu?

* ### Kiedy jądro wyśle sygnał SIGBUS do procesu posiadającego odwzorowanie pliku w pamięć?
Gdy allokujemy pamięć i poprosimy o za dużą jej ilość względem rozmiaru pliku, strona która jest częściowo zajęta zostanie dopełniona zerami,
natomiast pozostałem strony zostaną zarezerwowane, jednak odwołanie do niej spowoduje wysłanie SIGBUS

:::spoiler


:::

## Zadanie 3

* ### Przy pomocy polecenia `cat /proc/$(pgrep Xorg)/status | egrep 'Vm|Rss'` wyświetl zużycie pamięci procesu wykonującego kod X-serwera.
:::spoiler

:::

* ### Na podstawie podręcznika `proc(5)` wyjaśnij znaczenie poszczególnych pól.
* VmPeak Największy osiągniety rozmiar pamięci wirtualnej.
* VmSize Aktualny rozmiar pamięci.
* VmLck Pamięć która musi być trzymana w RAM, zakaz zrzucania na dysk.
* VmPin Jak VmLck, ale nie może być przenoszona
* VmHWM Największy osiągnięty poziom pamięci w RAM
* VmRSS Aktualna ilość pamięci w RAM
* RssAnon Rozmiar pamięci anonimowej w RAM
* RssFile Rozmiar plików zmapowanych do RAM
* RssShmem Rozmiar współdzielonej pamięci w RAM
* VmData Rozmiar segmentu data
* VmStk Rozmiar segmentu stack
* VmExe Rozmiar segmentu text
* VmLib Rozmiar współdzielonego kodu
* VmPTE Rozmiar tablicy stron
* VmSwap Rozmiar danych przeniesionych do swap

* ### Przypomnij jaka jest różnica między zbiorem roboczym i rezydentnym procesu.

* Zbiór rezydentny - fragment programu aktualnie załadowany do RAMu
* Zbiór roboczy - cały program razem z fragmentami aktualnie niezaładowanymi do pamięci, w pliku na dysku

* ### Napisz krótki skrypt (np. w języku Python lub `awk(1)`), który wyznaczy sumę `VmSize` i osobno sumę `VmRSS` wszystkich procesów.

    #!/bin/bash

    VMRSS_TOTAL=0
    VMSIZE_TOTAL=0

    PIDS=($(ps -eo pid))
    for PID in ${PIDS[@]:1}
    do
        #echo "PID: $PID"
        VMRSS=$(cat /proc/$PID/status | grep -E VmRSS)
        VAL_RSS=$(echo $VMRSS | awk '{print $2}')
        #echo "RSS: $VAL_RSS"
        ((VMRSS_TOTAL+=VAL_RSS)) 

        VMSIZE=$(cat /proc/$PID/status | grep -E VmSize)
        VAL_SIZE=$(echo $VMSIZE | awk '{print $2}')
        #echo "SIZE: $VAL_SIZE"
        ((VMSIZE_TOTAL+=VAL_SIZE)) 
    done

    echo "Total VmRss: $VMRSS_TOTAL kB"
    echo "Total VmSize: $VMSIZE_TOTAL kB"

* ### Czemu ta druga wartość nie pokrywa się z rozmiarem używanej pamięci raportowanym przez polecenie `vmstat -s`?
:::spoiler
:::

Do każdego procesu jest wliczana cała pamięć do której ma dostęp,
z uwagi że spora ilość jest spółdzielona w naszym programie wielokrotnie liczymy tą samą pamięć

## Zadanie 4

* ### Na podstawie slajdów do wykładu opisz algorytm obsługi błędu stronicowania w systemie Linux.

1. Sprawdzamy czy adres wirtualny jest legalny, tzn. czy znajduje się pomiędzy vm_start i vm_end jednej ze struktur, a jeśli nie wysyłany jest Segmentation fault i proces jest kończony
2. Sprawdzamy czy mamy uprawnienia do danej strony, jeśli nie dostajemy SEGFAULT ze specjalną flagą Protection exception
3. Strona nie jest załadowana do pamięci, zatem handler ładuje ją do pamięci i po powrocie z handlera próbujuemy ponownie przeczytać stronę

* ### Jakie informacje musi dostarczyć procesor, żeby można było wykonać procedurę obsługi błędu stronicowania?

* ### Do czego służą struktury jądra `mm_struct::pgd` i `mm_struct::mmap` zdefiniowane w pliku `include/linux/mm_types.h`?
* `mm_struct::pgd` - piewszy poziom mapowania pamięci na adres fizyczny
* `mm_struct::mmap` - zawiera listę vm_area_struct która opisuje całą przestrzeń adresową programu

* ### Kiedy jądro wyśle procesowi sygnał `SIGSEGV` z kodem `SEGV_MAPERR` lub `SEGV_ACCERR`?
* `SEGV_MAPERR` - Adres nie jest mapowany na żaden objekt
* `SEGV_ACCERR` - Niepoprawne uprawnienia do mapowanego objektu

* ### W jakiej sytuacji wystąpi pomniejsza usterka strony (ang. minor page fault) lub poważna usterka strony (ang. major page fault)?
* `minor page fault` - pojawia się gdy strona jest już w pamięci i nie ma potrzeby ładowania jej z dysku, ale nie ma jej jeszcze w naszej tablicy stron. Więc jedyne co wystarczy zrobić to dodać ją do naszej tablicy stron.
* `major page fault` - pojawia się gdy musimy pobrać stronę z dysku

* ### Jaką rolę pełni w systemie bufor stron (ang. page cache)?
bufor stron przetrzymuje niedawno ładowane strony lub strony które przewiduje że nidługo zostaną użyte tak aby przyspieszyć ładowanie tych stron.
:::spoiler
:::

## Zadanie 5

* ### Co jądro przechowuje w strukturze `vm_area_struct` opisującej segment D, a w szczególności w polach `vm_prot` i `vm_flags`?
* `vm_prot` - read-only
* `vm_flags` - flaga private copy-on-write
Oznaczenie takie sprawia że przy próbie zapsiu wykonany kopię strony i zmianę jej mapowania

* ### Jak jądro zmodyfikuje `mm_struct::pgd` w trakcie pierwszego odczytu ze strony p należącej do D, a jak w trakcie późniejszego pierwszego zapisu do p?
Podczas czytania jądro nie modyfikuje
Podczas zapisu modyfikuje na nowy adres
Podczas próby zapisu dostaniemy protection_exception które w połączeniu z flagą CoW utworzy nam kopię tej strony z uprawnieniami do zapisu podmieni wpis w tablicy stron i ponownie wykona zapis

* ### Co jądro musi zrobić z tablicą stron procesu, który zawołał `fork(2)`?
Jądro robi kopię mm_struct, wszystkich area_struct oraz tablicy stron. Oznacza każdą stronę procesu jako tylko do odczytu oraz jako CoW w obu procesach (rodzicu i dziecku)

## Zadanie 6
* ### Demand paging

* ### Czy mamy gwarancję, że program nie zobaczy modyfikacji zawartości pliku, które zostaną wprowadzone po utworzeniu tego odwzorowania?
Nie mamy gwarancji niezmodyfikowanego pliku



* ### Co złego mogłoby się stać, gdyby system operacyjny pozwolił modyfikować plik wykonywalny, który jest uruchomiony?
Moglibyśmy osiągnąć samomodyfikujący się kod

## Zadanie 7

#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;
  }
  /* TODO: END */

  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)
        Waitpid(pid_left, NULL, 0);

      if (pid_right != -1)
        Waitpid(pid_right, NULL, 0);
      
      if (pid == 0)
        exit(0);
      /* TODO: END */
    }
  }

  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... */
  long *table = Mmap(NULL, size, PROT_READ | PROT_WRITE, MAP_SHARED | MAP_ANONYMOUS, -1, 0);
  /* TODO: END */

  /* ... 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;
}

## 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. */
  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);
  /* TODO: END */
  Close(fd);
}

/* Remove DB memory mapping and release associated memory. */
static void db_close(db_t *db) {
  Munmap(db->entry, db->size * sizeof(entry_t));
  free(db->name);
}

/* Attempt to increase size of database. */
static bool db_rehash(db_t *db, size_t new_size) {
  assert(powerof2(new_size));

  /* Create new database. */
  db_t new[1];

  char *name = alloca(strlen(db->name) + sizeof(".reshash") + 1);
  strcpy(name, db->name);
  strcat(name, ".rehash");
  db_open(new, name, new_size);

  /* Copy everything from old database to new database. */
  /* TODO: Inform OS that we're going to read DB sequentially. */
  Madvise(db->entry, db->size * sizeof(entry_t), MADV_SEQUENTIAL);
  /* TODO: END */
  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);
      /* TODO: END */
      return false;
    }
  }

  /* TODO Replace old database with new one, remove old database. */
  Rename(new->name, db->name);
  Munmap(db->entry, db->size * sizeof(entry_t));
  /* TODO END */
  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);
  /* TODO: END */
  if (isatty(STDIN_FILENO)) {
    char buf[ENT_LENGTH + 1];
    while (fgets(buf, ENT_LENGTH + 1, stdin))
      consume_line(buf, &db, mode);
  } else {
    /* TODO: Map stdin into memory, and read it line by line. */
    // mapujemy wejście na pamięć
    char *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);
    // usuwamy mapowanie
    Munmap(buf, st.st_size);
    /* TODO: END */
  }

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