Temat główny: ZARZĄDZANIE PAMIĘCIĄ
Podtematy: Zajmowanie bloków pamięci - get_free_pages, Zwalnianie bloków pamięci - free_pages
Autor: Robert Popławski, nr indeksu: 181287

1 `get_free_pages()` - przydzielanie spójnych obszarów pamięci

1.1 Algorytm bliźniaków

Aby zminimalizować fragmentację zewnętrzną Linuks implementuje algorytm bliźniaków (zwany również algorytmem "buddy"). Ten algorytm operuje jedynie blokami pamięci o rozmiarach będących potęgami 2, ponadto w systemie bliźniaków dla każdego takiego obszaru istnieje dokładnie jeden obszar o tym samym rozmiarze, zwany obszarem bliźniaczym. Jeśli przyjmiemy, że nasza pamięć to blok 2^i stron i zaczniemy ją dzielić na dwie równe części (i te części dalej dzielić w ten sam sposób - aż otrzymamy bloki o rozmiarze jednej strony) to za każdym razem dzieląc blok o rozmiarze 2^j stron będziemy otrzymywać dwa bloki o rozmiarze 2^(j-1) stron - te dwa bloki to właśnie bloki bliźniacze. Oto algorytm przydzielania pamięci:

Przydziel blok pamięci o rozmiarze 2 ^ ORDER:

1:  na liście wolnych bloków znajdź najmniejszy blok BLOK o rozmiarze nie mniejszym niż 2 ^ ORDER i usuń go z listy wolnych bloków
2:  while (rozmiar(BLOK) > 2 ^ ORDER) do
3:  {
4:     BLIZNIAK = pierwsza_połowa(BLOK);
5:     BLOK = druga_połowa(BLOK);
6:     dodaj BLIZNIAK do listy wolnych bloków
7:  }
8:  zwróć BLOK jako wynik

1.2 Specyfikacja funkcji i struktur pomocniczych

Oto nagłówek funkcji __get_free_pages() (mm/page_alloc.c):

unsigned long __get_free_pages(int gfp_mask, unsigned long order)

Funkcja ta przyjmuje rozmiar bloku (2 ^ order) jaki ma przydzielić, oraz rodzaj bloku (gfp_mask). Jako wynik zwraca adres początku przydzielonego bloku lub 0 jeśli alokacja się nie powiodła. Ważniejsze wartości gfp_mask to:

GFP_DMA - przydzielony obszar musi nadawać się dla DMA
GFP_WAIT - proces żądający pamięci może zostać wstrzymany - np. po to aby korzystniej przydzielić pamięć

W Linuksie 2.4.7 pamięć jest zorganizowana w strefy, na PC jest ich 3: ZONE_DMA - do 16MB, ZONE_NORMAL - od 16 do 896MB, ZONE_HIGHMEM - powyżej 896MB (include/linux/mmzone.h):

#define MAX_NR_ZONES 3 typedef struct zonelist_struct { zone_t * zones [MAX_NR_ZONES+1]; } zonelist_t;

Tak wygląda struktura opisująca strefę (include/linux/mmzone.h):

typedef struct zone_struct { spinlock_t lock; unsigned long free_pages; unsigned long inactive_clean_pages; unsigned long inactive_dirty_pages; unsigned long pages_min, pages_low, pages_high; struct list_head inactive_clean_list; free_area_t free_area[MAX_ORDER]; struct pglist_data *zone_pgdat; struct page *zone_mem_map; unsigned long zone_start_paddr; unsigned long zone_start_mapnr; char *name; unsigned long size; } zone_t;

Ważniejsze pola:
lock - do synchronizowania operacji na strefie
free_pages - liczba wolnych stron
inactive_clean_pages - liczba stron, które wprawdzie są zajęte ale można je wyrzucić z pamięci gdyż na dysku znajduje się ich kopia
inactive_clean_list - lista stron typu inactive_clean
pages_min, pages_low, pages_high - te liczby po porównaniu z free_pages pozwalają stwierdzić ile mamy stron (dużo, mało,...)
free_area - to kluczowe pole (jest to tablica) dla systemu bliźniaków, na i-tej pozycji tej tablicy znajdują się bloki o rozmiarach 2^i
zone_mem_map - adres pierwszej strony należącej do strefy

Tablica free_area jest typu free_area_t:

typedef struct free_area_struct { struct list_head free_list; unsigned long *map; } free_area_t;
free_list - to lista wolnych bloków o ustalonym rozmiarze, dla zwiększenia wydajności na liście trzymamy tylko pierwszą stronę wolnego bloku (blok składa się z 2^i stron)
map - mapa bitowa wolnych bloków, po jednym bicie na każdą parę bliźniaczych bloków, bit jest ustawiony wtedy i tylko wtedy gdy z odpowiadających mu bliźniaczych bloków dokładnie jeden jest na liście free_list

Przykładowa reprezentacja stanu pamięci może wyglądać więc tak (każdy kwadrat oznacza stronę pamięci, czarny kwadrat to strona zajęta, biały - wolna):

1.3 Działanie funkcji
Główny kod wykonuje się w funkcji __alloc_pages(), oto ogólny zarys działania tej funkcji:
Najpierw iterujemy po wszystkich strefach w poszukiwaniu strefy o wysokiej liczbie wolnych stron, jednocześnie dla stref o małej liczbie wolnych stron budzimy wątek kreclaimd(), który zamienia pewną liczbę stron z listy inactive_clean_list na strony wolne - o ile to możliwe (mm/page_alloc.c):

for (;;) { zone_t *z = *(zone++); if (z->free_pages >= z->pages_low) { page = rmqueue(z, order); if (page) return page; } else if (z-<free_pages < z->pages_min && waitqueue_active(&kreclaimd_wait)) { wake_up_interruptible(&kreclaimd_wait); } }

Warto przyjrzeć się bliżej funkcji rmqueue(), która implementuje algorytm bliźniaków (uwaga, ten kod jest w dużym stopniu uproszczony):

static struct page * rmqueue(zone_t *zone, unsigned long order) { free_area_t * area = zone->free_area + order; unsigned long curr_order = order; do { head = &area->free_list; curr = memlist_next(head); if (curr != head) { /* czy jest wolny blok na tym poziomie? */ unsigned int index; page = memlist_entry(curr, struct page, list); memlist_del(curr); /* usuń blok z listy wolnych */ /* uaktualnij licznik wolnych stron: */ zone->free_pages -= 1 << order; page = expand(zone, page, index, order, curr_order, area); return page; } curr_order++; /* przejdź do następnego poziomu */ area++; } while (curr_order < MAX_ORDER); } Powyższy fragment kodu szuka najmniejszego wolnego bloku o rozmiarze nie mniejszym niż żądany (2^order), następnie jeśli taki znajdzie to usuwa go z listy i wykonuje funkcję expand() - ta funkcja kolejno dzieli ten blok na połówki aż do otrzymania bloku o pożądanej wielkości - ten blok zwraca, a pozostałe dodaje do listy wolnych.
Następnie próbuje przydzielić pamięć ze stref o dużej liczbie wolnych stron i stron typu inactive_clean (nie mniejszej niż wartość pages_high), jeśli to się nie powiedzie to próbuje przydzielić pamięć ze stref gdzie zachodzi warunek free_pages + inactive_clean_pages >= pages_low, a jak i to się nie uda to budzi kswapd() w nadziei, że ten rozwiąże problem oraz próbuje przydzielić pamięć ze stref o małej liczbie wolnych stron (free_pages + inactive_clean_pages >= pages_min):

page = __alloc_pages_limit(zonelist, order, PAGES_HIGH, direct_reclaim); if (page) return page; page = __alloc_pages_limit(zonelist, order, PAGES_LOW, direct_reclaim); if (page) return page; wakeup_kswapd(); page = __alloc_pages_limit(zonelist, order, PAGES_MIN, direct_reclaim); if (page) return page;
Na końcu próbujemy przydzielić pamięć ze stref gdzie zachodzi free_pages >= pages_min / 4:

for (;;) { zone_t *z = *(zone++); if (z->free_pages < z->pages_min / 4 && !(current->flags & PF_MEMALLOC)) continue; page = rmqueue(z, order); if (page) return page; }
Jeśli wykonanie funkcji doszło aż tu, to już nic więcej nie możemy zrobić:

  printk(KERN_ERR "__alloc_pages: %lu-order allocation failed.\n", order);   return NULL;
2  free_pages() - zwalnianie spójnych obszarów pamięci

2.1  Algorytm bliźniaków
Funkcja free_pages() implementuje algorytm bliźniaków:

Zwolnij blok BLOK:

1:  while rozmiar(BLOK) < MAKSYMALNY_ROZMIAR_BLOKU do
2:      if blizniak(BLOK) nie należy do WOLNE_BLOKI
3:        break;
4:     else    /* blizniak(BLOK) jest wolny */
5:     {
6:        WOLNE_BLOKI = WOLNE_BLOKI - blizniak(BLOK);
7:        BLOK = BLOK + blizniak(BLOK);
8:     }
9:  WOLNE_BLOKI = WOLNE_BLOKI + BLOK;

2.2  Specyfikacja funkcji i struktur pomocniczych
Nagłowek funkcji free_pages (mm/page_alloc.c):

  void free_pages(unsigned long addr, unsigned long order)

Funkcja ma za zadanie zwolnić obszar pamięci o rozmiarze 2^order rozpoczynający się w adresie addr. Korzysta ona z tych samych struktur co funkcja get_free_pages(), ponadto używa kilku pól ze struktury page (include/linux/mm.h):

  typedef struct page {      struct list_head list;      struct address_space *mapping;      unsigned long index;      struct page *next_hash;      atomic_t count;      unsigned long flags;      struct list_head lru;      unsigned long age;      wait_queue_head_t wait;      struct page **pprev_hash;      struct buffer_head * buffers;      void *virtual;      struct zone_struct *zone;   } mem_map_t; Oto ważniejsze pola wykorzystywane przez free_pages():
count - ilość procesów, którym ta strona została przyporządkowana
flags - flagi określające stan strony

zone - strefa do której strona należy

2.3 Działanie funkcji

Oto funkcje realizujące zwalnianie bloków pamięci (mm/page_alloc.c):

void __free_pages(struct page *page, unsigned long order) { if (!PageReserved(page) && put_page_testzero(page)) __free_pages_ok(page, order); }

__free_pages() sprawdza czy strona nie jest zarezerwowana oraz czy nie jest przydzielona więcej niż jednemu procesowi, jeśli oba warunki są spełnione to wywołuje __free_pages_ok(). __free_pages_ok() to główna funkcja, która implementuje algorytm bliźniaków. Oto istotniejsze fragmenty jej kodu:

static void __free_pages_ok (struct page *page, unsigned long order)
{
  mask = (~0UL) << order;
  base = zone->zone_mem_map;
  page_idx = page - base;
  index = page_idx >> (1 + order);

  area = zone->free_area + order;

  zone->free_pages -= mask;

  while (mask + (1 << (MAX_ORDER-1))) {

    if (!__test_and_change_bit(index, area->map))
                /* Blok bliźniaczy jest zajęty - nie ma go na liście wolnych */
      break;

                /* Blok bliźniaczy jest na liście wolnych */
    buddy1 = base + (page_idx ^ -mask);
    buddy2 = base + page_idx;

                /* Usuń go więc z listy wolnych, a bloki bliźniacze połącz: */
    memlist_del(&buddy1->list);
    mask <<= 1;
    area++;
    index >>= 1;
    page_idx &= mask;
  }
                /* Dodaj blok do listy wolnych bloków: */
  memlist_add_head(&(base + page_idx)->list, &area->free_list);

}

Uwagi:

jak sprawdzamy czy na liście wolnych bloków jest blok bliźniaczy do aktualnego - makro __test_and_change_bit(index, area->map) testuje stan bitu o numerze index w mapie bitowej dla aktualnego poziomu (area->map)
dzięki przyjętej reprezentacji wolnych bloków łączenie bloków bliźniaczych odbywa się prawie "niezauważalnie" - po prostu przechodzimy na wyższy poziom (area++) i dzielimy index przez 2 (index >>= 1)

3 Przykład
Poniżej znajduje się przykład demonstrujący działanie systemu bliźniaków:

Początkowy stan pamięci:

Stan pamięci po przydzieleniu bloku wielkości 1 (co odpowiada wykonaniu __get_free_pages(gfp_mask, 0)):

Stan po zwróceniu bloku pamięci o rozmiarze 2 i adresie 8 (free_pages(8, 1)):

4 Podsumowanie
System bliźniaków został wprowadzony aby zmniejszyć fragmentację zewnętrzną, jednak jak każdy system nie jest on doskonały. Łatwo podać przykład bardzo niekorzystnego alokowania pamięci:
jeśli na początku cała nasza wolna pamięć to jeden blok wielkości 16 stron (strony mają adresy od 0 do 15) i wywołamy 16 razy żądanie przydzielenia bloku wielkości jednej strony (instrukcją get_free_pages(gfp_mask, 0)), a potem zwolnimy wszystkie bloki o adresach parzystych to znajdziemy się w sytuacji gdzie połowa pamięci jest wolna (8 stron) ale największy blok jaki możemy przydzielić to blok rozmiaru 1 strony.

1 get_free_pages() - przydzielanie spójnych obszarów pamięci

1.1 Algorytm bliźniaków

1.2 Specyfikacja funkcji i struktur pomocniczych

1.3 Działanie funkcji

2 free_pages() - zwalnianie spójnych obszarów pamięci

2.1 Algorytm bliźniaków

2.2 Specyfikacja funkcji i struktur pomocniczych

2.3 Działanie funkcji

3 Przykład

4 Podsumowanie

1 `get_free_pages()` - przydzielanie spójnych obszarów pamięci

2 `free_pages()` - zwalnianie spójnych obszarów pamięci