# Lista 8
###### 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:|:white_check_mark:||||

:heavy_check_mark:
:::

## Zadanie 1

* ### Jakie są wady stosowania `sbrk` do zarządzania rozmiarem sterty przez biblioteczny algorytm zarządzania pamięcią `malloc(3)`?
`sbrk` może przesuwać `program break` tylko w górę i w dół, więc jeżeli przesuniemy `program break` w górę żeby zaalokować zmienną x, a później jeszcze raz przesuniemy w górę by zaalokować zmienną y i zmienna x przestanie być potrzebna to nie możemy przesunąć program break w dół bo stracilibyśmy zmienną y.


* ### Jak można to poprawić przy pomocy `mmap` i `munmap`?
Używanie `mmap` i `munmap` daje nam możliwość na dostęp (usuwanie itp) "starych" bloków, więc większe struktury danych możemy zaallokować w innym miejscu niż tym dostępnym przez `sbrk`

* ### Kiedy procedura `free` może zwrócić pamięć do jądra?
`free` można używać na pamięci z `malloca`

    free()
           The  free() function frees the memory space pointed to by ptr, which must have been returned by
           a previous call to malloc() or related functions.  Otherwise, or if ptr has already been freed,
           undefined behavior occurs.  If ptr is NULL, no operation is performed.

[FreeBSD MAN](https://www.freebsd.org/cgi/man.cgi?query=sbrk&sektion=2)


## Zadanie 2

* ### Wyjaśnij różnicę między `fragmentacją wewnętrzną` i `zewnętrzną`.
* fragmentacja wewnętrzna
polega na podziale wewnetrznym jedego bloku np. jeden blok na rozmiar

* fragmentacja zewnętrzna
znawisko to zachodzi gdy mamy odpowiednią ilość wolnej pamięci ale nie możemy jej użyć ze względu na jej rozrzucenie po całej pamięci(wiele małych bloków)

* ### Czemu algorytm malloc nie można stosować `kompaktowania`?
* W przypadku przeprowadzeina kompaktowania przesuwalibyśmy miejsca w pamięci, a w wielu miejscach programu możemy mieć w tym czasie wskaźniki na to miejsce, więc musilibyśy wszystkie te wskaźniki podmienić
* malloc musbu być cały czas dostępny i odrazu odpowiadać na żądania bez kolejkowania

* ### Opowiedz o dwóch głównych przyczynach występowania `fragmentacji zewnętrznej`.

* czas życia zamiennych
* program zmienia zachowanie najpierw małe zmienne potem duże

## Zadanie 3

* ### Opowiedz o trzech wzorcach przydziału pamięci występujących w programach.

* ### Wyjaśnij jaki jest związek między czasem życia bloku, a jego rozmiarem?
* Obiekty zaalokowane w tym samym czasie z dużym prawdopodobieństwem umrą w tym samym czasie
* Obiekty o róznych typach służą do innych zastosowań, zatem prawdopodobnie umrą w innym czasie
:::spoiler

---
:::

* ### Wyjaśnij różnice między politykami znajdowania wolnych bloków i wymień ich mocne i słabe strony:
* `first-fit`
* `next-fit`
* `best-fit `

## Zadanie 4

* ### Wykonaj krokową symulację algorytmu przydziału pamięci dla poniższego ciągu żądań.

* Start
* `alloc(4)`
* `alloc(8)`
* `alloc(4)`
* `alloc(4)`
* `alloc(10)`
* `alloc(6)`
* `free(C)`
* `free(B)`
* `free(F)`

* `alloc(6)`
* best-fit
* first-fit
* `free(D)`
* best-fit
* first-fit

* `alloc(18)`
* best-fit
* first-fit
Nie udało się :(

## Zadanie 5

* ### Porównaj go z algorytmem, który zarządza jedną listą wolnych bloków zgodnie ze strategią `best-fit`.

* ### Jak przebiegają operacje `malloc` i `free`?

* ### Co robi `malloc`, gdy na danej liście nie ma wolnego bloku żądanego rozmiaru?
Przechodzi do listy o większym rozmiarze znajduje miejsce i odpowiednio ją dzieli.

* ### Gdzie należałoby przechowywać `węzeł strażnik` (ang. `sentinel node`) każdej z list wolnych bloków?

* ### Rozważ zastosowanie `leniwego złączania` wolnych bloków w algorytmie kubełkowym przydziału pamięci – jakie problemy zauważasz?


Problem rozwiazywany przez leniwe zlaczania: musielibysmy czesciej szukac duzych blokow i je rozbijac na mniejsze, zamiast uzywac blokow odpowiednich rozmiarow jesli bysmy uzywali czesto podobnych rozmiarow obiektow
Problem spowodowany przez leniwe zlaczania: nadmierna fragmentacja
:::spoiler

Deferred Coalescing
:::

## Zadanie 6

#include "csapp.h"
#include "arena.h"

#define MAX_LENGTH 126
#define MAX_BLKSZ (MAX_LENGTH + 1)

#define DEBUG_LEVEL 2

static arenalist_t arenas = STAILQ_HEAD_INITIALIZER(arenas);
static arena_t *cur_arena = NULL;
static unsigned cur_offset;

static void init_chunk(void *ar) {
  uint8_t *data = ar;
  unsigned offset = sizeof(arena_t);

  while (offset + MAX_BLKSZ < ARENA_SIZE) {
    data[offset] = -MAX_BLKSZ;
    offset += MAX_BLKSZ;
  }

  data[offset] = -(ARENA_SIZE - 1 - offset);
  data[ARENA_SIZE - 1] = 0;
}

#define BLOCK_HEADER(data) (data[cur_offset])
#define END_OF_CHUNK(data) (BLOCK_HEADER(data) == 0)
#define BLOCK_USED(data) (BLOCK_HEADER(data) > 0)
#define BLOCK_SIZE(data) (abs(BLOCK_HEADER(data)))

#define NEXT_BLOCK_HEADER(data) (data[cur_offset + BLOCK_SIZE(data)])
#define NEXT_BLOCK_FREE(data) (NEXT_BLOCK_HEADER(data) < 0)
#define NEXT_BLOCK_SIZE(data) (abs(NEXT_BLOCK_HEADER(data)))

#define MOVE_NEXT(data) cur_offset += BLOCK_SIZE(data)
#define CURRENT_PTR(data) (data + cur_offset + 1)

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 split = BLOCK_SIZE(data)-len;
      BLOCK_HEADER(data) = len;
      NEXT_BLOCK_HEADER(data)=-split;
      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 merge=BLOCK_SIZE(data)+NEXT_BLOCK_SIZE(data);
      BLOCK_HEADER(data)=-merge;
    } else {
      /* TODO: merge two free blocks and allocate with split */
      int8_t merge=BLOCK_SIZE(data)+NEXT_BLOCK_SIZE(data);
      int8_t second_block_size=merge-len;
      BLOCK_HEADER(data)=len;
      if(second_block_size!=0){
        NEXT_BLOCK_HEADER(data)=-second_block_size;
      }
      result=CURRENT_PTR(data);
      break;
    }
  }
  return result;
}

static char *stralloc(size_t len) {
  assert(len <= MAX_LENGTH);

  if (len == 0)
    return NULL;

  if (cur_arena == NULL) {
    /* there are no arenas yet */
    init_chunk(alloc_first_arena(&arenas));
    cur_arena = STAILQ_FIRST(&arenas);
    cur_offset = sizeof(arena_t);
  }

  arena_t *ar = cur_arena;
  char *ptr;

  while (!(ptr = alloc_block((int8_t *)ar, len + 1))) {
    /* no space left on the current arena, move to the next one */
    ar = STAILQ_NEXT(ar, arenalink);
    cur_offset = sizeof(arena_t);

    /* that was the last arena, move to the first one */
    if (ar == NULL)
      ar = STAILQ_FIRST(&arenas);

    if (ar == cur_arena) { /* we've checked all arenas on the list. */
      init_chunk(alloc_after_arena(&arenas, ar));
      ar = STAILQ_NEXT(ar, arenalink);
    }
  }

  cur_arena = ar;
  return ptr;
}

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

static void strmemcheck(void) {
  arena_t *ar;
  STAILQ_FOREACH(ar, &arenas, arenalink) {
    const int8_t *data = (const int8_t *)ar;
    unsigned offset = sizeof(arena_t);
    while (offset != ARENA_SIZE - 1) {
      assert(offset < ARENA_SIZE);
      assert(data[offset] != 0);
      offset += abs(data[offset]);
    }
    assert(data[offset] == 0);
  }
}

/* The test */

#define MAX_PTRS 10000
#define MAX_LEN 100
#define CYCLES 100

static void *alloc_fn(int *lenp) {
  *lenp = rand() % (MAX_LEN + 1);
  return stralloc(*lenp);
}

#define free_fn(ptr) strfree(ptr)
#define memchk_fn() strmemcheck()

#include "test.h"

## Zadanie 7

## Zadanie 8