Kmalloc & Kfree

Wstęp

Ta prezentacja dotyczy mechanizmów wykorzystywanych przez funkcje kmalloc oraz kfree.

Spis treści

• Wstęp
• Alokator płytowy
• Struktury danych
  • cache
  • płyty
  • obiekty
• Kmalloc
• Kfree
• Wieloprocesorowość
• Podsumowanie

Alokator płytowy

Operacje przydziału pamięci dla jądra występują dość często i muszą być w związku z tym wykonywane efektywnie.

Ogólna idea pamięci przydziału pamięci w jądrze opiera się na alokatorze płytowym. Pamięć jest fizycznie alokowana i inicjowana całymi płytami (ang. slab). Wówczas utworzenie i zwolnienie obiektu nie wymaga na ogół fizycznego przydziału pamięci, wystarczy użyć pamięci z płyty.

Struktury danych

Zarządzając swoją pamięcią jądro używa trójpoziomowych struktur danych:

• deskryptor cache
• deskryptor płyty
• deskryptor obiektu

Deskryptor cache

W obrębie jednego cache trzymane są dowiązanie do płyt z obiektami tego samego rozmiaru.

Do przydziału pamięci przez kmalloc używane jest 13 cache - każdy przeznaczony dla obiektów o rozmiarze będącym kolejną potęgą dwójki: 32B, 64B, 128B, 256B, ..., 128kB. W tym rozwiązaniu fragmentacja wewnętrzna nie przekracza nigdy 50%.

Płyty w obrębie jednego cache trzymane są na uporządkowanej liście:

• najpierw płyty całkowicie zapełnione
• potem płyty częściowo zapełnione
• na końcu płyty puste

Ważniejsze pola w strukturze kmem_cache_s:

c_name

Wskazuje na nazwę pamięci podręcznej

c_firstp, c_lastp

Wskazują odpowiednio na pierwszy i ostatni deskryptor płyty w pamięci podręcznej

c_freep

Wskazuje na pole s_nextp pierwszego deskryptora płyty zawierającej przynajmniej jeden wolny obiekt

c_num

Liczba obiektów znajdujących się w jednej płycie (wszystkie płyty z tego cache mają ten sam rozmiar)

c_gfporder

Określa jaki rozmiar mają płyty w obrębie tego cache

c_nextp

Wskazuje na następny deskryptor pamięci podręcznej

Deskryptor płyty

Płyta zarządza ciągłym obszarem pamięci, do którego można wrzucić pewną ilość obiektów o konkretnym rozmiarze j.w.

Ważniejsze pola w strukturze kmem_slab_s:

s_inuse

Liczba aktualnie zaalokowanych obiektów na płycie

s_mem

Wskazuje na pierwszy (zaalokowany lub wolny) obiekt na płycie

s_freep

Wskazuje na pierwszy wolny obiekt (jeżeli taki jest) na płycie

s_nextp, s_prevp

Wskazują odpowiednio na następny i poprzedni deskryptor płyty

Rysunek poniżej przedstawia powiązania pomiędzy cache'ami i płytami.

Deskryptor obiektu

Deskryptory pomagają utrzymywać listę wolnych miejsc na płycie.

Deskryptory obiektów są trzymane w dwóch miejscach w zależności od rozmiaru obiektów przechowywanych na płycie.

• rozmiar < strony_pamięci - deskryptory są trzymane na płycie obok właściwych obiektów
• rozmiar >= strony_pamięci - deskryptory są trzymane w pamięci przydzielonej z osobnego cache ogólnego przeznaczenia

Ważniejsze pola w strukturze kmem_bufctl_s:

buf_next_p

Wskazuje na następny deskryptor obiektu

buf_slabp

Wskazuje na płytę, do której obiekt przynależy

Rysunki poniżej przedstawiają organizację deskryptorów obiektów w zależności od rozmiaru obiektów przechowywanych na płycie.

Kmalloc

• Znajdź cache o rozmiarze odpowiednim dla alokowanego obiektu
• Zobacz czy jest wolne miejsce na którejś płycie
• Jak nie ma to spróbuj przydzielić pamięć dla nowej płyty
• Jak się nie da to zwolnij pamięć zajmowaną przez puste płyty i spróbuj jeszcze raz
• Weź miejsce z wolnej płyty i przydziel to miejsce dla tego żądania

Kfree

• Sprawdź zgrubnie, czy przekazano poprawny wskaźnik
• Znajdź cache z którego pochodzi zwalniana pamięć (na podstawie zawartości strony do której wskazuje wskaźnik)
• Zaznacz, że miejsce na płycie jest od teraz puste

Wieloprocesorowość

Na systemach wieloprocesorowych każdy cache ma krótką tablicę dla poszczególnych procesorów. Większość żądań przydziału i zwalniania pamięci może być obsłużona przy pomocy tej tablicy. Wymiana pomiędzy globalną cache i tą tablicą występuje tylko kiedy tablica się przepełni. W ten sposób ograniczona jest liczba operacji spin-lock (operacji na semaforach).

Podsumowanie

Przedstawiłem:

• jak działa alokator płytowy
• jak są powiązane
  • cache
  • płyty
  • obiekty
• jak to jest wykorzystywane przez kmalloc oraz kfree
• w jaki sposób ograniczona jest liczba operacji spin-lock w systemach wieloprocesorowych

Prezentację można pobrać ze strony http://rainbow.mimuw.edu.pl/~la181249/university/so/kmalloc_and_kfree.html