Zgodnie z początkowymi założeniami UNIX'a dynamiczny przydział pamięci
dla jądra nie był przewidziany. Jądro posiadało zarezerwowane tablice o
stałych rozmiarach, których polami gospodarowało w zależności od potrzeb.
Linux, który bazuje na UNIX'ie został od razu napisany z dynamicznym
przydziałem pamięci dla jądra. Początkowo przydzielać można było tylko
obszary nie większe od systemowej ramki, ale bład ten naprawiono i od 1994
roku ta cześć kodu nie była modyfikowana. Jednocześnie obok dynamicznej
alokacji pozostały niektóre stałe tablice np. tablica procesów.
Wszystkie procedury obsługujące przydział pamięci dla jądra znajdują się w pliku 'linux/mm/kmalloc.c', najważniejsze z nich to kmalloc() i kfree().
By zapewnić w miarę optymalne wykorzystanie pamięci przy często małych alokacjach (dużo mniejszych od strony) stosuje się następującą strategię. Jądro dzieli każdą alokowaną dla swoich potrzeb stronę na bloki o wielkościach odpowiadających w przybliżeniu potęgom dwójki, tak że każda strona zawiera jednowymiarowe bloki. Żądanie przydziału jest zaokrąglane do minimalnego bloku w jakim się mieści. Maksymalnie jądro może jednorazowo zażądać przydzielenia dla siebie 2^5 (czyli 32) ramek o rozmiarach w zależnosci od komputera 4 lub 8 kB (w obecnej wersji tylko z takimi ramkami może pracować Linux).
Informacja (struct block_header) o każdym bloku m.in. czy jest wolny i jego długość znajduje się zawsze na jego początku i zajmuje dokładnie 8 bajtów. Każda strona (lub obszar, gdy blok nie mieści się w stronie) dołączany do jądra posiada pole (struct page_descriptor) identyfikujące go, znajdujące się zawsze na początku takiego obszaru. Zawiera ono m.in. listę i ilość wolnych bloków. Bezpośrednio po polu page_descriptor znajduje się pierwszy blok na danej stronie wraz z opisem (block_header). Dzięki takiej organizacji jądro mając adres początku wolnego bufora pamięci może szybko dotrzeć do jego pól identyfikacyjnych.
Bloki są pogrupowane według wielkości, a informacja o nich jest przechowywana w tablicy sizes[]. Każde pole tej tablicy jest strukturą size_descriptor i zawiera dane dotyczące jednowymiarowych bloków np. dowiązania do pierwszej wolnej strony zawierającej wolny blok, z uwzględnieniem wymagania dostępu przez kanaly DMA, ilość bloków mieszczących się w ramce (potrzebne przy inicjalizacji nowych ramek) itp.
Jądro przydziela sobie ramki z przestrzeni dostępnej dla innych procesów funkcją __get_free_pages(priority,order,dma). Dla zabezpieczenia przed zbyt częstymi niepowodzeniami znalezienia wolnej strony zaimplementowano kmalloc_cache[MAX_CACHE_ORDER=3]. Przechowuje ono po jednym obszarze wielkości 1,2 i 4 ramek pamięci niedostępnej przez DMA. Zwalniana przez jądro ramka (ale nie DMA) jest oddawana właśnie do kmalloc_cache, a dopiero po jego zapełnieniu ramki są zwracane do przestrzeni użytkownika.
Procedury udostępniane na zewnątrz.
Funkcja przydzielająca pamięć.
void *kmalloc( size_t size, /* rozmiar w bajtach */ int priority /* parametr jest podobny jak we wszystkich procedurach przydziału ramki * np.__get_free_pages(priority,order,dma), okresla m.in. jakiego * rodzaju ma być pamięć */ );kmalloc() zwraca NULL w przypadku niepowodzenia, a może się to zdarzyć gdy żądanie przydziału będzie większe od 2^5 stron lub nie uda się wyrwać odp. liczby ramek z przestrzeni dostępnej dla innych procesów. Algorytm działania kmalloc() jest prosty. Po sprawdzeniu poprawności wywołania, znajduje ono w tablicy sizes[] grupę bloków odpowiadającą danej alokacji i korzystając z listy dowiązań do wolnych stron znajduje pierwszą z wolnym blokiem. Blok jest markowany i odłączany z lokalnej listy wolnych. Zwracany zostaje adres wolnej pamięci znajdujacy się w bloku bezpośrednio po jego cześci opisowej (struct block_header).
void kfree( void *__ptr /* adres zwalnianego obszaru */ );
Bilbliografia
Pliki źródłowe Linux'a: