# Ćwiczenia 8, grupa cz. 10-12, 8 grudnia 2022

###### tags: `SO22` `ćwiczenia` `pwit`

## Deklaracje

Gotowość rozwiązania zadania należy wyrazić poprzez postawienie X w odpowiedniej kolumnie! Jeśli pożądasz zreferować dane zadanie (co najwyżej jedno!) w trakcie dyskusji oznacz je znakiem ==X== na żółtym tle.

**UWAGA: Tabelkę wolno edytować tylko wtedy, gdy jest na zielonym tle!**

:::danger
| | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| ----------------------:| ----- | --- | --- | --- | --- | --- | --- | --- |
Miriam Bouhajeb | X | X | X | X | | | | |
Kacper Chmielewski | X | X | X | | | | X | |
Jan Jankowicz | X | X | X | | | | | |
Jakub Kaczmarek | | | | | | | | |
Jarosław Kadecki | X | X | X | X | | | | |
Zuzanna Kania | | X | X | X | | | | |
Julia Konefał | | X | X | | | | | |
Daniel Sarniak | X | X | X | X | | | | |
Paweł Tkocz | X | X | X | X | | | | |
Miłosz Urbanik | X | X | X | X | | X | | |
Tomasz Wołczański | X | X | | X | | X | X | |
Radosław Śliwiński | X | X | X | | | | | |
:::

**Poniej można zadeklarować zadania 5 i 8 z listy 7:**
- zad.8 Miłosz Urbanik
-
-

:::info
**Uwaga:** Po rozwiązaniu zadania należy zmienić kolor nagłówka na zielony.
:::

## Zadanie 1
:::success
Autor: Jan Jankowicz
:::

Problem z użyciem sbrk przez funkcję malloc jest taki, że sbrk może jedynie rozszerzać/zwężać obszar stosu liniowo zaczynając od jego krańca. Alternatywne użycie mmap pozwala na zwiększanie stosu punktowo, tzn. poprzez alokację wybranych obszarów, niekoniecznie przylegających do innych obszarów stosu. Dzięki temu również punktowo możemy zmniejszać stos za pomocą metody munmap. W efekcie zastąpienie funkcji sbrk funkcjami mmap() i munmap pozwala na bardziej elastyczne zarządzanie pamięcią stosu. Poniższe przykłady ilustrują zalety zastosowania mmap i munmap i ograniczenia sbrk w zarządzaniu pamięcią. Pokazują także, kiedy funkcja free może zwrócić wolną pamięć do jądra systemu.



## Zadanie 2
:::success
Autor: Paweł Tkocz



Fragmentacja wewnętrzna – można znaleźć wystarczająco duży wolny blok, zmarnowana zostanie jednak pewna pamięć na jego początku lub końcu. Wewnątrz przydzielonego obszaru mamy więc niewykorzystany fragment pamięci, który znajduje się w zaalokowanym bloku

Fragmentacja zewnętrzna – w sumie, na stercie jest wystarczająco dużo wolnej pamięci, ale nie ma jednego, ciągłego bloku, który byłby wystarczająco duży

Kompaktowanie – przenoszenie zaalokowanych bloków pamięci mające na celu usuniecie niewykorzystanych fragmentów pamięci pomiędzy nimi. Malloc nie może wykonywać kompaktowania, ponieważ unieważniłoby to wskaźnik do pamięci przechowywany przez program. Próba odwołania się do takiego wskaźnika skończyłaby się odwołaniem do pustego obszaru pamięci lub do pamięci zupełnie innej (np. zaalokowanej później).

Dwie główne przyczyny występowania fragmentacji zewnętrznej:
1. Izolowane śmierci - kluczowym aspektem jest tworzenie bloków wolnej pamięci które sąsiadują z blokami zaalokowanymi. Zauważmy, że jeśli alokator zaalokuje w pamięci wiele bloków i wszystkie one umrą (prawie) w tym samym momencie, to nie dojedzie do fragmentacji – program będzie korzystał z ciągłego fragmentu pamięci, a kiedy przestanie jej potrzebować, zwolni ciągły fragment pamięci. Zatem alokator może próbować przewidywać które bloki zostaną zwolnione mniej więcej w tym samym czasie i umieszczając je obok siebie, może w ten sposób zmniejszyć fragmentację zewnętrzną.
2. Zachowanie programu zmieniające się w czasie - w szczególności chodzi o zmiany w sposobie wykorzystania pamięci przez program, np zwalnianie małych bloków pamięci i alokowanie dużych.

:::

## Zadanie 3
:::success
Autor: Kacper Chmielewski
Trzy wzorce przydziału pamięci:
- rampy - programy gromadzą pewne struktury danych, monotonicznie w czasie. Dzieje się tak, gdyż zachowują one dziennik zdarzeń lub ich strategia rozwiązywania problemów wymaga budowania dużych reprezentacji, po których rozwiązanie może być szybko znalezione
- szczyty - programy używają pamięci w (bursty patterns), budując relatywnie duże struktury danych, które są używane w trakcie poszczególnych faz, a potem są w wiekszości lub nawet całości wyrzucane.
- płaskowyże - programy budują struktury danych szybko, aby potem używać ich długich okresach czasu (często przez cały czas działania programu).
Obiekty różnych typów umierają w różnych momentach, a obiekty tych samym częściej umierają w tym samym czasie.

1. **first-fit** - przeszukuje listę od początku i używa pierwszego bloku który ma wystarczający rozmiar, aby pomieścić rządaną pamięć. Jeśli blok jest większy niż potrzeba, jest on dzielony i reszta jest umieszczana na wolnej liście.
- plusy: zapamiętywane są adresy sąsiedztwa wolnych bloków
- minus: powstaje dużo małych, wolnych bloków na początku listy, przez co wydłuża się czas znalezienia przy kolejnych przydziałach pamięci.
2. **next-fit** - jest zoptymalizowaną wersją *first-fit*, która zapamiętuje wskaźnik na na miejsce, w którym ostanio zapisał pamięc i nowe przydzielanie zaczyna się od tego momentu.
- plusy: ta metoda znacznie zmniejsza czas przydzielania nowej pamięci
- minusy: obiekty z róźnych programów mogą się przeplatać w pamięci, co może powodować fragmentację
3. **best-fit** - sekwencyjnie dopasowany alokator przeszukuje wolną listę w celu znalezienia najmniejszego bloku, który pomieści wymaganą pamięc.
- plusy: minimalizuje marnowaną przestrzeń wybierając najmniejsze możliwe fragmenty,
- minusy: działa słabo jeśli w dużej stercie jest dużo wolnych bloków, w najgorszym przypadku użycie pamięci jest proporcjonalne do iloczynu wartości przydzielonej pamięci i różnicy pomiędzy największym i najmniejszym elementem.
:::

## Zadanie 4
:::success
Autor: Jarosław Kadecki


Wolny blok potrzebuje miejsca na 4 słowa: Header, wskaźnik next, wskaźnik prev i footer.


:::

:::info
Pozostałe zadania będą do zadeklarowania i prezentacji na ćwiczeniach 15 XII 2022.
:::

## Zadanie 5
:::danger
Autor:
:::

## Zadanie 6
:::success
Autor: Miłosz Urbanik
:::


**niejawna lista bloków** - każdy z bloków zawiera metadane informujące o tym, czy blok jest w użyciu oraz o jego rozmiarze, potencjalnie (nie w tym zadaniu) może zawierać też np. wskaźnik na kolejny blok.

Kod zmodyfikowanych funkcji:

static void *alloc_block(int8_t *data, uint8_t len) {
  void *result = NULL; //pointer to allocated block

  while (!END_OF_CHUNK(data)) {
    if (BLOCK_USED(data)) {
      /* TODO: occupied block */
      MOVE_NEXT(data); //move offset to next block
    } else if (BLOCK_SIZE(data) == len) {
      /* TODO: free block of exact size */
      BLOCK_HEADER(data) = len; //len > 0, block used
      result = CURRENT_PTR(data);
      break;
    } else if (BLOCK_SIZE(data) > len) {
      /* TODO: free block is too large */
      uint8_t excess_size = BLOCK_SIZE(data) - len;
      BLOCK_HEADER(data) = len; //mark used 
      NEXT_BLOCK_HEADER(data) = -excess_size; //mark the rest unused
      result = CURRENT_PTR(data);
      break;
    } else if (!NEXT_BLOCK_FREE(data)) {
      /* TODO: next block is occupied or does not exists */
      MOVE_NEXT(data); //move next block pointer
    } else if (NEXT_BLOCK_SIZE(data) <= len - BLOCK_SIZE(data)) {
      /* TODO: merge two free blocks, but do not allocate */
      uint8_t size = BLOCK_SIZE(data) + NEXT_BLOCK_SIZE(data);
      BLOCK_HEADER(data) = -size; //not allocated, marked as unused
    } else {
      /* TODO: merge two free blocks and allocate with split */
      uint8_t size = BLOCK_SIZE(data) + NEXT_BLOCK_SIZE(data);
      uint8_t excess_size = size - len;
      BLOCK_HEADER(data) = len;
      NEXT_BLOCK_HEADER(data) = -excess_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 */
  *ptr *= -1; //if header < 0, block unused
}

## Zadanie 7
:::success
Autor: Kacper Chmielewski

#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
:::danger
Autor:
:::