Zgodnie z poczatkowymi zalozeniami UNIX'a dynamiczny przydzial pamieci dla jadra nie byl przewidziany. Jadra posiadalo zarezerwowane tablice o stalych rozmiarach, ktorych polami gospodarowalo w zaleznosci od potrzeb. Linux, ktory bazuje na UNIX'ie, posiada organizacje mieszana. Pozostalo wiekszosc tablic np. tablica procesow, jednoczesnie czesc struktur jest alokowana dynamicznie, korzystajac z wolnej pamieci dostepnej dla systemu.
Procedury obslugujace przydzial pamieci dla jadra znajduja sie w pliku 'linux/mm/kmalloc.c'. Sa to:
void *kmalloc( size_t size, /* rozmiar szukanej pamieci */
int priority /* rodzaj pamieci (DMA lub dowolna) */
void kfree( void *__ptr /* adres zwalnianego obszaru */ )
Jest to specyficzny rodzaj przydzialu pamieci, pamiec zorganizowana za pomoca stron o ustalonym rozmiarze jest dodatkowo dzielona na bloki o wielkosciac odpowiadajacych potedze dwojki, tak ze kazda strona zawiera jednorozmiarowe bloki. Zadanie przydzialu jest zaokraglane do minimalnego bloku, w ktorym sie miesci. Maksymalnie jadro moze jednorazowo zarzadac przydzielenia dla siebie 5 (pieciu) stron o rozmiarach zazwyczaj 4 lub 8 kB.
Kazdy obszar (jedna lub wiecej stron, gdy blok nie miesci sie w stronie) dolaczany do jadra posiada pole (struct page_descriptor) identyfikujace go, znajdujace sie zawsze na poczatku takiego obszaru. Pole to zajmuje 16 bajtow.
Podobnie kazdy blok posiada pole identyfikacyjne (struct block_header), rowniez znajdujace sie na jego poczatku i zajmujace 8 bajtow. Dzieki takiej organizacji jadro majac adres poczatku wolnego bufora pamieci moze szybko dotrzec do jego pol identyfikacyjnych.
struct page_descriptor {
struct page_descriptor *next;
struct block_header *firstfree; /* pierwszy wolny blok */
int order; /* liczba wymaganych stron na blok */
int nfree; /* liczba wolnych blokow w stronie */
};
struct block_header {
unsigned long bh_flags; /* flagi okreslajace m.in. czy zajety */
union {
unsigned long ubh_length; /* dlugosc bloku, gdy zajety */
struct block_header *fbh_next; /* nastepny blok, gdy wolny */
} vp;
};
Do przechowywania danych o wolnych buforach sluzy struktura size_descriptor.
struct size_descriptor {
struct page_descriptor *firstfree;
/* strony zawierajace bloki dostepne dla jadra */
struct page_descriptor *dmafree;
/* j.w. tylko pamiec z dostepem DMA np. uzywana przez urzadzenia zewnetrzne */
int nblocks;
/* ilosc blokow w stronie */
int nmallocs;
int nfrees;
/* ilosc wolnych blokow */
int nbytesmalloced;
int npages;
unsigned long gfporder;
/* liczba stron potrzebnych do stworzenia jednego bloku (gdy blok jest wiekszy
od strony) */
};
Kazdemu rozmiarowi bloku odpowiada pole (w tablicy sizes[ ]) zawierajace liste stron dostepnych dla blokow o danej wielkosci
struct size_descriptor sizes[ ]
Kazda pozycja w p.w. tablicy oznacza bloki o rozmiarach kolejno (rozmiar wraz z deskryptorem) 32, 64, 128, 252(!), 508(!), itd.
1. znajdz odpowiednia pozycje w tablicy sizes[ ] (tj. minimalny rozmiar bloku wystarczajacy na przydzial pamieci rozmiaru size).
2. jesli size zbyt duzy zakoncz bledem.
3. jesli brak strony na liscie stron odpowiedniego pola idz 7 (no_bucket_page)
4. jesli brak wolnego bloku na stronie idz 11 (not_free_on_freelist)
5. zmniejsz liczbe blokow na stronie, ewentualnie przejdz do nastepnej strony na liscie (gdy brak wolnych blokow), zamarkuj blok.
6. zwroc adres wolnej pamieci.
7. (no_bucket_page) zaalokuj jedna lub odpowiednio wiecej stron z przestrzeni dostepnej dotychczas dla programow uzytkownika.
8. jesli brak wolnych stron w pamieci idz 10 (no_free_page)
9. dopisz strone z jej wolnymi blokami do odpowiedniej pozycji w tablicy sizes[ ], idz 5.
10. (no_free_page) przeszukaj bufor zwalnianych przez jadro stron w poszukiwaniu jakiejkolwiek (uwaga1. strona zwalniana przez jadro nie musi byc odrazu oddana do przestrzeni uzytkownika, ale moze byc najpierw przekazywana do tablicy kmalloc_cache[MAX_CACHE_ORDER=3]. Dopiero po zapelnieniu pamieci podrecznej kolejne strony sa oddawane dla uzytkownika), jezeli znaleziono odpowiednia liczbe stron idz 9, wpp. wyjdz z bledem.
11. (not_free_on_freelist) zglos blad w tablicy sizes[ ] (niewytlumaczalny), wyjdz.
1. jesli _ptr==NULL wyjdz z bledem.
2. sprawdz czy istnieja pola identyfikacyjne bloku i strony dla tego obszaru pamieci oraz czy sa sensowne, jesli nie - wyjdz z bledem.
3. dopisz wolny blok do odpowiadajecej mu strony (listy wolnych blokow danej strony).
4. znajdz odpowiadajaca mu pozycje w tablicy sizes[ ].
5. jezeli na stronie nie bylo wczesniej wolnych blokow oraz nie jest jeszcze zupelnie pusta dopisz ja do listy wolnych stron (sizes[ ]->firstfree/dmafree), wyjdz z procedury.
6. jezeli strona jest zupelnie pusta zwolnij ja (patrz uwaga1).
7. wyjdz.