Alokacja i dealokacja pamięci dla jądra (mm/slab.c)

Idea jego działania opiera się na spostrzeżeniu, że obiekty alokowane przez jądro często są tego samego typu (a co za tym idzie, rozmiarów), co umożliwia grupowanie ich razem i powtórne używanie zainicjowanych obiektów, dzięki czemu zyskujemy czas który trzeba byłoby poświęcić na powtórne ich zainicjowanie. Szczegóły implementacji alokatora płytowego zapewniają także efektywne wykorzystanie sprzętowej pamięci podręcznej procesora. Drugą ważną korzyścią ze stosowania alokatora płytowego jest znaczące zmieniejszenie fragmentacji wewnętrznej.

Głowną jednostką zarządzania pamięcią przez alokator płytowy są połączone w listę cache (pamięci podręczne),  zawierające obiekty tego samego typu. Cache jest złożony z tzw. płyt (ang. slab) będących fragmentami pamięci składającymi się z kolejnych stron, gdzie liczba tych stron jest potęgą 2. Przy inicjowaniu jądra tworzone są cache dla różnych rodzajów danych, np. dla deskryptorów cache, dla deskryptorów plików, itp.
Istnieje poza nimi lista cache dla obiektów różnych rozmiarów, od 32 bajtów do 128 kilobajtów, dzięki czemu można łatwo wyszukać odpowiedni cache dla obiektów danego rozmiaru (przechowywane są w struturze cache_sizes).

Płyty służą bezpośrednio do przechowywania obiektów, które są połączone w listę dwukierunkową.
Każda płyta ma wskaźnik do następnej, są one połączone w listę o nastepującym uporządkowaniu: najpierw pełne, potem zapełnione częściowo a na końcu puste.

Typem danych opisującym cache jest kmem_cache_t, najważniejsze jego pola to:

• struct list_head slabs;            lista płyt
• struct list_head *firstnotfull;    pierwsza niepełna płyta na liście
• unsigned int objsize;              rozmiar obiektów w cache
• unsigned int flags;                flagi
• unsigned int num;                  ilość obiektów w płycie
• spinlock_t spinlock;               splinlock
• unsigned int gfporder;             logarytm dwójkowy z ilości stron na płytę
• unsigned int growing;              czy właśnie się zwiększa
• char name[CACHE_NAMELEN];          nazwa cache
• struct list_head next;             następny cache
• cpucache_t *cpudata[NR_CPUS];      dane dotyczące poszczególnych procesorów - tylko w SMP
• unsigned int batchcount;           dla SMP (wyjaśnienie później)
• size_t colour                      maksymalny kolor
• unsigned int colour_off            przesunięcie dla koloru
• unsigned int colour_next;          następny kolor

W celu lepszego wykorzystania sprzętowej pamięci podręcznej procesora stosuje się technikę zwaną kolorowaniem.
Polega ona na stosowaniu, przy alokowaniu obiektów w kolejnych płytach, zmiennego przesunięcia obiektów względem początku płyty. Kolor płyty pomnożony przez colour_off se struktury cache'a oznacza właśnie wyżej wspomniane przesunięcie. Maksymalny kolor zależy od ilości wolnego miejsca na płytach (pole free). Kolor jest zwiększany cyklicznie dla kolejnych płyt.

Drugą ważną strukturą jest slab_t o ważnych polach

• unsigned int inuse                 ilość obiektów w użyciu
• kem_bufctl_t free                  wolne miejsce
• struct list_head list              lista płyt
• usigned long colouroff             kolor - przesunięcie

(!!! TODO !!!)

Opis działania funkcji kmalloc() i kfree()

• void* kmalloc(size_t size, int flags)

Parametr flags może przyjmowac wartości:

• static inline void*__kmem_cache_alloc(kmem_cache_t *cachep, int flags)

kmem_cache_alloc_one(cachep) (makro!)

static inline void* kmem_cache_alloc_one_tail(kmem_cache_t *cachep, slab_t *slabp)

Niestety w przypadku SMP procedura ta nieco się komplikuje.

Jeżeli jądro jest skompilowane dla SMP, to oprócz obiektów trzymanych w głównym cache każde CPU posiada bufor do tymaczasowgo trzymania stworzonych obiektów. Rozmiar tego bufora zależy od rozmiaru obiektów w cache (pole objsize), przy czym im większy obiekt tym mniej jest ich tam trzymanych, a dla obiektów większych niż PAGE_SIZE rozmiar bufora wynosi 0.
W strukturze kmem_cache_t znajduje się tablica cpudata zawierająca elementy typu cpucache_t dla każdego CPU. Pola te zawierają wartość avail - wole miejsce w buforze i limit - graniczenie opisane powyżej.

W przypadku SMP w kmem_cache_alloc nie jest wywoływane bezpośrednio kmem-cache_alloc_one, tylko nastepujące czynności (przerwania wyłączone):
 

1. jeżeli nie ma przydzielonegu bufora dla aktualnego procesora, to wywołaj kmem_cache_alloc_one
2. w przeciwnym przypadku jeżeli jest miejce w buforze (avail > 0), to (uwaga!) pzrydzielane jest miejsce z niego
3. w przeciwnym przypadku wywoływana jest funkcja kmem_cache_alloc_batch, która używając kmem_cache_alloc_one_tail przenosi cachep->batchcount (które jest ustawiane na połowę limitu bufora dla procesora) obiektów do głównego cache, zwiększając przy tym avail, po czym przydziela miejsce w buforze dla aktualnego procesora.

Do zwalniania pamięci wykorzystuję się funkcję kfree
 

Funkcja zwalniająca poprzednio zaalokowaną pamięć. Należy uważać, żeby zwalniać tylko pamięć przydzieloną przez kmalloc, inaczej działanie jej jest niekreślone.

Przebieg działanie jest nastepujący:

1. na zablokowanych przerwaniach z pomocą makra GET_PAGE_CACHE odnajduje cache do którego należy strona zajmowana przez obiekt
2. wywołuje __kmem_cache_free dla znalezionego cache i danego obiektu

1. z pomocą makra GET_PAGE_SLAB sprawdza w której płycie zawarty jest obiekt
2. uwzględniając rozmiar obiektu w cache, rozmiar płyt i przesunięcie obiektów względem początku płyty oblicza numer obiektu w płycie
3. wstawia na początek listy wolnych obiektów obiekt o wyliczonym numerze
4. jeśli trzeba, przenosi odpowiednio deskryptor płyty w liście desktyptorów tak, aby zachowana była kolejność puste-częsciowe-pełne

I znowu sutuacja dla SMP komplikuje się.
Zmienia się przebieg działania funckji __kmem_cache_free, dla SMP działa nastepująco

1. jeżeli nie ma bufora obiektów przydzielonego do aktualnego procesora, to używając funkcji free_block (dostającej jako parametry listę obiektów, i ich ilość) zwalnia podany obiekt
2. w.p.p. sprawdza, czy avail < limit, jeżeli tak, to wstawia do bufora dla aktywnego procesora wskaźnik do obiektu (uwaga, usunięcie nastąpi z opóźnieniem)
3. jeżeli nie ma wolnego miejsca w buforze, to korzystając z free_block zwalnia drugą połowę (czyli batchcount) zawartości bufora obiektów przydzielonego do aktywnego procesora

Obsługa urządzeń wymiany (mm/swapfile.c, mm/page_io.c)

W systemie Linux dyskowa pamięć pomocnicza może być realizowana na dwa sposoby

• jako zwykły plik, w dowolnym systemie plików
• jako urządzenie blokowe, zwykle osobna partycja na dysku

Tych wad nie ma urządenie blokowe, służy ono wyłącznie do obsługi pamięci wymiany i zapewnia szybki, chociaż i tak wiele razy wolniejszy od dostepu do pamięci opracyjnej RAM (rzędu 100+ razy wolniej), bezpośredni dostęp.
Pamięć wymiany jest więc (konieczną) ostatecznoscią i nie powinno się liczyć na nią jeśli najwazniejsza jest
wydajność, chociaż dzięki zrzuceniu nieużywanych danych na dysk, a także zabezpieczeniu przed brakiem wolnej pamięci uzywanie jest przyności wymierne korzyści.

W systemie może być aktywne więcej niż jedno urządznie wymiany, jednak ich ilość jest ograniczona przez stałą MAX_SWAP_FILES (linux/swap.h, w linuxie 2.4.7 równą domyślnie 8).

Informacja o urządzeniach wymiany zawarta jest w tablicy swap_info o elementach typu swap_info_struct.

Ważne pola tego typu to:

• unsigned int flags;           /* flagi: SWP_USED || SWP_WRITEOK /*
• kdev_t swap_device;           /* numer urządzanie blokowego */
• spinlock_t sdev_lock;         /* spinlock dla urządzenia */
• struct dentry * swap_file;    /* wskażnik do i-node'a uzrądznia */
• unsigned short * swap_map;    /* mapa stron obszaru wymiany /*
• int prio;                    /* priorytet */
• int pages;                   /* liczba stron na urzadzeniu */
• unsigned long max;
• int next;                    /* następny w liście */

Na początku każdego urządzenia znajduje się nagłówek określający rodzaj obszaru wymiany, etykietę urządzenia, wersję, ilość złych stron i ich tablicę.

Opis działania funkcji:

Funkcja ta przyłącza urządzanie o zadanej nawie (np. "/dev/hda2", "/swap.file"). Aby można było przyłączyć urządzenie, musi byc ono wcześnie zainicjowane z przestrzeni użytkownika programem "mkswap".

Flags może mieć maski:

• SWAP_FLAG_PREFER, ustawaniane, jeżeli ma mieć zadany priorytet, jest on ustawiany jako (swap_flags & SWAP_FLAG_PRIO_MASK) >> SWAP_FLAGS_PRIO_SHIFT

1. sprawdza przywileje
2. ustawia odpowiedni priorytet i inicjuje strukturę_swap_info_struct (przy tym, jeśli nie ma ustawionej flagi SWAP_FLAG_PREFER, ustawia priorytet na wartość zmiennej least_priority i zmnijesza ją)
3. znajduje i-węzeł odpowiadający podanej nazwie
4. jeżeli znaleziono urządzenie blokowe to
1. ustawia na nim rozmiar bloku równy rozmiarze strony
2. sprawdza, czy można na nim zapisywać
3. sprawdza, czy podane urządzanie nie zostało jeszcze przyłącznone
5. jeżeli jest zwykłym plikiem
1. sprawdza, czy podane urządzanie nie zostało jeszcze przyłącznone
6. ustawia odpowiednio rozmiar urządzenia
7. na podstawie typu obszaru wymiany (versja 1, lub 2) odpowiednio ustawia pola struktury swap_info_struct
8. po sprawdzniu dodatkowych warunków dodaje urządzenie wymiany, po zablokowniu spinlocka swaplock

Do odłączenia przyłącznonego urządzenia służy funkcja

• asmlinkage long sys_swapoff(const char* specialfile)

1. sprawdza przywileje
2. blokuje jądro (lock_kernel)
3. po znalezieniu i-węzła urządzenia szuka go w liście swap_list
4. blokuje dostep do listy urządzneń (swap_list_lock) listę
5. usuwa urządzenie z listy
6. po odblokowaniu listy urządzeń próbuje zwolnić podane urządzenie poprzez funkcję try_to_unuse, która przenosi strony z obszaru wymiany do pamięci RAM. Funkcja ta ewentualnie wywołuje schedule, gdyż operacja ta może trwać długo, co prz zablokowawanym jądrze spowodwało by zastój.
7. jeśli zwróci ona błąd, tzn, nie udało się zaalokować wszystkich stron z obszaru wymiany, to wstawia spowrotem urządzenie na listę (blokując ją)
8. usuwa urządznie z tablicy
9. odblokowuje jądro

W celu zalokowania pamięci w obszarze wymiany używamy funckji:
(swp_entry ma jedno pole - unsigned long val, linux/shmem_fs.h)

• swp_entry_t __get_swap_page(unsigned short count)

1. jeżeli count (liczb dowiązań do strony) jest większe, niż SWAP_MAP_MAX (linux/swap.h, równe 0x7fff), to zwraca błąd
2. wywołuje swap_list_lock, czyli spin_lock(&swaplock)
3. jeżeli nie ma urządzeń wymiany, lub nie ma wolnych stron zwraca wynik oznaczający brak pamięci
4. dla kolejnych urządzeń na liście, począwszy od swap_list.next, jeśli można na nie zapisywać próbuje, po zablokowaniu ich spinlocka przydzielić miejsce na danym urządzeniu z pomocą funkcji scan_swap_map
5. po przydzieleniu, jeśli nastepne na liści urządzenie ma taki sam priorytet, to przesuwa swap_list.next na nie, jesli nie to ustawia swap_list.next na swap_list.head jeśli tenże ma różny priorytet, dzięki czemu najpierw będą używane urządzenia z początku kolejki
6. odblokowuje listę i zwraca wynik

• static inline int scan_swap_map(struct swap_info_struct *si, unsigned short count)

Operacją przeciwną jest swap_free (i __swap_free)

• void __swap_free(swp_entry_t entry, unsigned short count)

Do zapisu i odczytu z urządzenia wymiany uzywana jest zdefinowana w mm/page_io.c funkcja

• void rw_swap_page(int rw, struct page *page)

• static int rw_swap_page_base(int rw, swp_entry_t entry, struct page *page)