# SO Lista 8

## Zadanie 1

### Jakie są wady stosowania sbrk do zarządzania rozmiarem sterty przez biblioteczny algorytm zarządzania pamięcią malloc(3)?
sbrk pushuje więcej bajtów na stos więc nie możemy zwolnić tego co jest niżej. (Dosłownie robimy push dodatkowe bajty)

### Jak można to poprawić przy pomocy mmap i munmap? Kiedy procedura free może zwrócić pamięć do jądra?
Możemy zwalniać pamięć niezależnie od tego gdzie się znajduje (jak niżej)

### Kiedy procedura free może zwrócić pamięć do jądra?
Kiedy określona ilość wolnej, ciągłej pamięci zostanie przekroczona. (libc ma coś takiego jak M_TRIM_TRESHOLD i M_MAP_THRESHOLD)



## Zadanie 2

### Fragmentacja wewnętrzna
kiedy mamy duży wolny blok, ale po zaalokowaniu w nim pamięci requestowanej, duża część tego bloku jest marnowana (bo np. był request 0x20B, a blok miał 0x30B)
### Fragmentacja zewnętrza
kiedy mamy wolne bloki gotowe do alokacji, ale nie możemy ich wziąć do zaalokownia requestu programu (bo np. był za duży) <!-- `that's what she said` -->
### Kompaktowanie
`Doczytaj`
### Czemu algorytm malloc nie można stosować kompaktowania?
Bo wskaźniki w programie byłyby pomieszane

### Na podstawie [6, §2.3] opowiedz o dwóch głównych przyczynach występowania fragmentacji zewnętrznej.
#### Problem 1
Wolne obszary pamięci których sąsiedzi nie są wolni. Kiedy alokujemy i zwalniamy pamięć nie w tym samym czasie, tzn jeden blok żyje dłużej od drugiego
#### Problem 2
Kiedy w pewnym okresie alokujemy i zwalniamy dużo małych bloków, a potem dużo dużych lub na zmianę małe i duże bloki. Tzn algorytm musi być odporny na zmianę pracy programu.


## Zadanie 3

### 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 [6, §2.4].
#### Polityka ramps
programy akumulują struktury monotonicznie przez jakiś czas i trzymają, aż nie będzie potrzebna (zazwyczaj szybko zwalniają)

#### Polityka peaks
program gwałtownie alokuje dużo pamięci, wykonuje każdą(?) czynność, a następnie zwalnia pamięć. Zostaje parę bloków które reprezentują rezultat pracy

#### Polityka plateaus
szybko alokują, ale nie zwalniają (czasem aż do końca programu)

### Na podstawie paragrafu zatytułowanego „Exploiting ordering and size dependencies” wyjaśnij jaki jest związek między czasem życia bloku, a jego rozmiarem?
Okazuję się, że często jest tak, że jeśli zaalokujemy obkiety w tym samym czasie, o tym samym rozmiarze, to jest duże prawdopodobieństwo, że razem zostaną zwolnione

Również 2 bloki różnych rozmiarów będą prawdopodobnie służyć do czegoś innego i zostaną zwolnione osobno

### Polityki
#### first-fit
zobacz liste free bloków i weź pierwszy który pasuje
#### next-fit
jak first-fit, ale zacznij szukać od miejsca, gdzie poprzednio skończyliśmy
#### best-fit
znajdź taki który zmarnuje najmniej miejsca

### Na podstawie [6, §3.4] wymień ich słabe i mocne strony.
| polityka | plusy | minusy |
| ---------|-------|--------|
|first-fit| jeśli będziemy wrzucać free do listy posortowane po adresie gdzie są to możemy to wykorzystać w ich złączeniu |słabo się skaluje ze względu na np. ciągłe splitwanie dużego bloku na małe requesty, co wydłuża czas wyszukiwania kiedy będziemy chcieli większy blok |
|next-fit|możliwie najszybszy|1. psuje lokalność <br/>2.powoduje więcej fragmentacji od pozostałych |
|best-fit|minimalizuje zmarnowane miejsce|1. może być tak, że zmarnowanie miejsce będzie tak małe że później go nie użyjemy <br/>2. trzeba przeszukać całą listę, więc jest większa złożoność|


## Zadanie 4
### gorliwe złączanie
próbuje od razu połączyć blok "za" i "przed" nim

Mam nadzieję że miro będzie stało xD
https://miro.com/welcomeonboard/bHBEUUVzQ2lBTE8wWDRsbTk1TDVRbVJ6SXAxdmRvbkVGVDFQM2dCZTRlRmhlbGhiY2YxMGs5N2xPUDR3b2F6anwzMDc0NDU3MzY2MTIxOTk2Mzg5fDI=?share_link_id=409832454772
## Zadanie 5
### Jak przebiegają operacje malloc i free?
#### Free
kiedy blok jest zwalniany trafia na koniec kubełka z odpowiednim rozmiarem. (oczywiście najpierw złączmy później wsadamy)
#### malloc
sprawdzamy tylko kubły w których rozmiarach mieści się request (pierwszy lepszy)

Algorytm z jedną listą po prostu bierze i wrzuca do tej samej listy

### Co robi malloc, gdy na danej liście nie ma wolnego bloku żądanego rozmiaru?
Zagląda do następnej listy i tam szuka. Następnie splituje ten blok, jesli tam go nie ma, szuka dalej itd. (wydaje mi się, że ten zesplitowany wrzuca do kubełka niżej)

### Gdzie należałoby przechowywać węzeł strażnik każdej z list wolnych bloków?
w liście między pierwszym i ostatnim blokiem

### Rozważ zastosowanie leniwego złączenia wolnych bloków w algorytmie kubełkowym przydziału pamięci - jakie problemy zauważasz?
Jeśśli nie mamy boundary tagów, to musielibyśmy szukać po wielu listach, żeby znaleźć blok, który jest obok naszego

Może dojść do fragmentacji, bo requestując duży blok od razu szukamy w dużych kubełkach, kiedy best-fitem mogłoby być złączenie dwóch mniejszych bloków w innych listach

## UWAGA

## Zadanie 6

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 */
      *data &=0xef;
      BLOCK_HEADER(data) = len;
      assert(BLOCK_HEADER(data) > 0);
      result = CURRENT_PTR(data);
      break;
    } else if (BLOCK_SIZE(data) > len) {
      /* TODO: free block is too large */
      uint8_t blksize = BLOCK_SIZE(data);
      BLOCK_HEADER(data) = len;
      NEXT_BLOCK_HEADER(data) = blksize - len;
      assert(BLOCK_HEADER(data) > 0);
      assert(NEXT_BLOCK_HEADER(data) > 0);
      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 */
      BLOCK_HEADER(data) = BLOCK_SIZE(data) + NEXT_BLOCK_SIZE(data);
      assert(BLOCK_HEADER(data) < 0);
    } else {
      /* TODO: merge two free blocks and allocate with split */
      uint8_t totalsize = BLOCK_SIZE(data) + NEXT_BLOCK_SIZE(data);
      BLOCK_HEADER(data) = len;
      NEXT_BLOCK_HEADER(data) = totalsize - len;
      assert(BLOCK_HEADER(data) > 0);
      assert(NEXT_BLOCK_FREE(data));
      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 */
  *sstr |=0x80;
  assert(*sstr < 0);
}

## Zadanie 7
https://man.netbsd.org/bitstring.3

#include "csapp.h"
#include "bitstring.h"

typedef struct
{
  int data[8]; /* contents does not matter, sizeof(...) = 32 */
} object_t;

#define ARENA_EXTRA                               \
  struct                                          \
  {                                               \
    size_t nitems;    /* number of items */       \
    size_t nfree;     /* number of free items */  \
    void *items;      /* pointer to first item */ \
    bitstr_t *bitmap; /* bitmap of free items */  \
  }

#include "arena.h"

static arenalist_t arenas = STAILQ_HEAD_INITIALIZER(arenas);

static arena_t *init_arena(arena_t *ar)
{
  /* TODO: Calculate nitems given ARENA_SIZE, size of arena_t and object_t. */
  size_t nitems = (ARENA_SIZE - sizeof(arena_t)) / sizeof(object_t);

  ar->bitmap = bit_alloc(nitems);
  bit_nclear(ar->bitmap, 0, nitems - 1);

  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(ar->bitmap, ar->nitems, &index);
  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. */
  if (ptr != NULL)
  {
    if(bit_test(ar->bitmap,index)) ar->nfree++;
    bit_clear(ar->bitmap, index);
  }
}

static void *objalloc(void)
{
  /* Find arena with at least one free item. */
  arena_t *ar = NULL;
  STAILQ_FOREACH(ar, &arenas, arenalink)
  {
    if (ar->nfree > 0)
      return alloc_block(ar);
  }
  /* If none found then allocate an item from new arena. */
  return alloc_block(init_arena(alloc_after_arena(&arenas, NULL)));
}

static void objfree(void *ptr)
{
  if (ptr == NULL)
    return;
  arena_t *ar = find_ptr_arena(&arenas, ptr);
  assert(ar != NULL);
  free_block(ar, ptr);
}

static void objmemcheck(void)
{
  arena_t *ar;
  STAILQ_FOREACH(ar, &arenas, arenalink)
  {
    /* Check if nfree matches number of cleared bits in bitmap. */
    size_t nused = 0;
    for (int i = 0; i < ar->nitems; i++)
      nused += bit_test(ar->bitmap, i) ? 1 : 0;
    assert(nused == ar->nitems - ar->nfree);
  }
}

/* The test */

#define MAX_PTRS 10000
#define CYCLES 100

static void *alloc_fn(int *lenp)
{
  *lenp = sizeof(object_t);
  return objalloc();
}

#define free_fn objfree
#define memchk_fn objmemcheck

#include "test.h"

## Zadanie 8