Autor:

Tomasz Stachowicz
ts181294@zodiac.mimuw.edu.pl
2001.12.19

Spis treści:

• Zarządzanie pamięcią w systemie Linux 2.4:
  • Przydział i zwalnianie pamięci dla jądra
  • Obsługa plików i urządzeń wymiany

Przydział i zwalnianie
pamięci dla jądra

Autor: Jeff Bonwick (Sun Microsystems)
The Slab Allocator: An Object-Caching Kernel Memory Allocator

Obiekt = obszar danych o ustalonym rozmiarze

Problem: częste przydzielanie i zwalnianie obiektów standardowym algorytmem było kosztowne

Rozwiązanie: zamiast niszczenia obiektu - wstawianie go do cache'a, zamiast tworzenia - pobieranie z cache'a

Przydzielanie i zwalnianie obiektów następuje poprzez cache'e.
Każdy cache ma ustalony rozmiar obiektów i typ pamięci.

Dostępne operacje:

tworzenie i niszczenie kmem_cache_create() kmem_cache_shrink() kmem_cache_destroy()

przydział i zwalnianie obiektów kmem_cache_alloc() kmem_cache_free() przydział i zwolnienie pamięci fizycznej kmem_cache_grow() kmem_cache_reap()

Każdy cache zawiera listę tafli (ang. slab).

Tafla to ciągły blok pamięci obejmujący jedną lub kilka ramek, podzielony na obiekty tego samego rozmiaru.

W obrębie jednego cache'a tafle są posortowane według następującej reguły:
    najpierw tafle pełne, potem niepełne, na końcu puste.

Organizacja wewnętrzna tafli zależy od rozmiaru obiektów:

• dla mniejszych niż PAGE_SIZE/8, deskryptory (struktury opisujące) tafli i obiektów znajdują się w tym samym bloku pamięci, co same obiekty,
• wpp - pamięć na deskryptory jest przydzielana niezależnie od tafli.

typedef unsigned int kmem_bufctl_t;

typedef struct slab_s {
  struct list_head    list;
  unsigned long       colouroff;
  void                *s_mem;     wskaźnik do pierwszego obiektu
  unsigned int        inuse;      liczba aktualnie używanych obiektów
  kmem_bufctl_t       free;       indeks pierwszego wolnego obiektu

  kmem_bufctl_t       nextfree[num];   
                        jeśli i-ty obiekt jest używany, to nextfree[i] 
                        zawiera indeks następnego wolnego obiektu     
                        lub BUFCTL_END, gdy jest ostatnim wolnym
} slab_t;

Uwaga! W rzeczywistości w strukturze nie występuje zmienna nextfree (gdyż nie ma z góry ustalonego rozmiaru). Jednak w źródłach Linuksa struktury slab_s używa się tak, jakby ta zmienna w niej występowała i miała rozmiar num ze struktury kmem_cache_s, czyli liczba obiektów w tafli.

struct kmem_cache_s {
    struct list_head    next;            następny deskryptor cache'a
    struct list_head    slabs;           lista tafli w danym cache'u
    struct list_head    *firstnotfull;   pierwsza niepełna tafla    
    unsigned int        objsize;         rozmiar obiektu            
    unsigned int        num;             liczba obiektów w tafli    
    unsigned int        gfporder;        2^gfporder == liczba ramek na taflę
    kmem_cache_t        *slabp_cache;    cache cache'a              
    void                (*ctor)(...);    konstruktor obiektu        
    void                (*dtor)(...);    destruktor obiektu         
};

#define MAX_OBJ_ORDER   5        2^MAX_OBJ_ORDER == maksymalna liczba 
                                                    ramek na obiekt

typedef struct cache_sizes {
        size_t           cs_size;      rozmiar cache'a
        kmem_cache_t    *cs_cachep;    wskaźnik na cache o tym rozmiarze
                                       dla zwykłej pamięci
        kmem_cache_t    *cs_dmacachep; dla pamięci DMA
} cache_sizes_t;

static cache_sizes_t cache_sizes[] = {
    {    32,    NULL, NULL},
    {    64,    NULL, NULL},
        .....
    { 65536,    NULL, NULL},
    {131072,    NULL, NULL},
    {     0,    NULL, NULL}
};

kmalloc(size_t size, int flags)
    w tablicy cache_sizes znajdź pierwszy pasującą pozycję lub zwróć błąd
    z tej pozycji wybierz odpowiedni cache \
      - w zależności od tego, czy flaga GFP_DMA jest w flags
    wywołaj kmem_cache_alloc dla tego cache'a i zwróć wynik

kmem_cache_alloc(kmem_cache_t *cachep, int flags)
    powtarzaj
        zablokuj przerwania
        jeśli jest niepełna tafla, to
            weź adres pierwszego wolnego obiektu w tej tafli
            usuń go z listy wolnych
            odblokuj przerwania
            zwróć adres obiektu
        wpp
            odblokuj przerwania
            spróbuj dodać nową taflę do cache'a
            jeśli się nie udało, to
                zwróć błąd

kfree (const void *objp)
    zablokuj przerwania
    znajdź cache, do którego należy obiekt
    wywołaj kmem_cache_free dla tego cache'a i obiektu
    odblokuj przerwania

kmem_cache_free(kmem_cache_t *cachep, void *objp)
    znajdź taflę zawierającą dany obiekt
    wstaw obiekt do listy wolnych w tej tafli
    przesuń tą taflę na liście tak, by zachowany był porządek: \
      najpierw tafle pełne, później niepełne, na końcu puste

Obsługa plików i urządzeń wymiany

2 rodzaje organizacji:

• plikowa (np. plik o stałym rozmiarze) - wolniejsza
• blokowa (np. partycja) - szybsza

Każde urządzenie wymiany składa się z sekwencji slotów stron (ang. page slots), czyli bloków do przechowywania wymienianych stron.

swap_info - tablica z informacjami o urządzeniach wymiany; max rozmiar określony przez stałą MAX_SWAPFILES (zwykle 8);

Informacje o urządzeniu opisane są stukturą swap_info_struct.

struct swap_info_struct
{
    unsigned int flags;            czy używane i czy można zapisywać
    kdev_t swap_device;            numer urządzenia 
    struct dentry * swap_file;     i-węzeł urządzenia
    unsigned short * swap_map;     wskaźnik do tablicy liczników 
                                   odwołań do slotów stron
    unsigned char * swap_lockmap;  wskaźnik do tablicy blokad 
                                   bitowych slotów stron
    unsigned int lowest_bit;       od tej pozycji należy zacząć 
                                   szukanie wolnego slotu
    unsigned int highest_bit;      na tej pozycji należy zakończyć
    unsigned int cluster_next;     następny slot do sprawdzenia 
                                   przy szukaniu wolnego
    unsigned int cluster_nr;       liczba używanych slotów
    int prio;                      priorytet urządzenia
    int pages;                     ile wolnych slotów na urządzeniu
    unsigned long max;             rozmiar urządzenia wymiany w stronach
    int next;                      następne urządzenie 
                                   na liście priorytetowej
}

nr_swapfiles - maksymalny indeks urządzenia wymiany w tablicy swap_info

nr_swap_pages - całkowita liczba wolnych slotów we wszystkich urządzeniach wymiany

Informacje o urządzeniach wymiany znajdują się na liście uporządkowanej wg priorytetów.
Indeks pierwszego elementu tej listy trzymany jest w zmiennej swap_list typu:

  struct swap_list_t {
      int head;     głowa listy
      int next;     następne urządzenie do rozpatrzenia
                    (patrz: Wybór urządzenia do zrzucenia strony)
  }

int sys_swapon(const char *specialfile, int swap_flags)

specialfile - ścieżka do pliku urządzenia (partycji) lub zwykłego pliku
swap_flags - jeśli ustawiona flaga SWAP_FLAG_PREFER, to najmłodsze 15 bitów określa priorytet urządzenia

Funkcja znajduje pierwszy wolne miejsce w tablicy swap_info, wstawia tam dane urządzenie, inicjuje tablicę liczników i tablicę blokad, zwiększa liczbę wolnych slotów (nr_swap_pages), wstawia urządzenie do listy priorytetowej.

Jeśli w swap_flags bit SWAP_FLAG_PREFER jest zgaszony, to priorytet urządzenia nadawany jest zgodnie z licznikiem least_priority, zmniejszanym po każdym wykorzystaniu.

int sys_swapoff(const char *specialfile)

Funkcja usuwa urządzenie z listy i ustawia mu flagę, że nie można zapisywać. Przy pomocy try_to_unuse() próbuje zwolnić wszystkie strony zrzucone na to urządzenie. Jeżeli się uda, zwalnia odpowiednie pole w tablicy swap_info i ustawia flagę, że urządzenie jest nieużywane. Wpp. wstawia urządzenie z powrotem do listy i wychodzi z błędem.

Wybór urządzenia odbywa się w funkcji
unsigned long get_swap_page(void)
służącej do przydzielenia wolnego slotu strony.

W celu znalezienia urządzenia, funkcja wykonuje dwa przejścia po liście urządzeń. Za pierwszym razem zaczyna od swap_list.next i idzie tak długo, aż zmieni się priorytet lub skończy lista. Następnie rozpoczyna od początku listy (swap_list.head) i idzie aż do końca.
Jeśli w ciągu obu przejść nie znajdzie urządzenia, to znaczy że nie ma wolnego miejsca i wychodzi z błędem. Wpp. zwraca zakodowany numer urządzenia i numer slotu. Pole swap_list.next ustawiane jest na następnik tego urządzenia, chyba że było ono ostatnim o danym priorytecie, wówczas swap_list.next = swap_list.head.