3. Algorytmy, czyli jak to działa




Jądro wykonuje na Przestrzeni Adresowej procesu następujące wysokopoziomowe operacje:

Zanim przejdziemy do ich omówienia, zajmiemy się grupą kilku niższych funkcji pomocniczych. Pozwoli to na nabranie pewnego pojęcia o tym, jak wyglądają operacje wykonywane na Przestrzeni Adresowej, oraz ułatwi zrozumienie bardziej specjalizowanych funkcji.



2.1 Funkcje obsługi Przestrzeni Adresowej



2.2 Operacje na Przestrzeni Adresowej

Przejdziemy teraz do omówienia implementacji poszczególnych wysokopoziomowych operacji na przestrzeni adresowej procesu:


2.2.1 Alokacja i dealokacja zakresu adresów liniowych

Zaczniemy od operacji alokacji i dealokacji zakresu adresów liniowych. Te dwie operacje realizowane są w całości przez funkcje do_mmap() i do_munmap():

static inline unsigned long do_mmap(struct file *file, unsigned long addr, unsigned long len, unsigned long prot, unsigned long flag, unsigned long offset)
int do_munmap(struct mm_struct *mm, unsigned long addr, size_t len)


2.2.1.1 static inline unsigned long do_mmap(struct file *file, unsigned long addr, unsigned long len, unsigned long prot, unsigned long flag, unsigned long offset)

Funkcja do_mmap służy do alokowania nowego przedziału adresów o zadanej długości len. Tworzy ona i inicjuje nowy Region Pamięci dla bieżącego procesu.

Parametry:

Algorytm:
  1. Sprawdź wartości parametrów:
    1. Jeżeli addr + len lub po prostu len przekraczają PAGE_OFFSET (zahaczają o część Przestrzeni Adresowej przeznaczoną dla jądra), to porażka: -EINVAL
    2. Jeżeli proces przekroczyłby dozwoloną liczbę przydzielonych Regionów Pamięci: mm->map_count > max_map_count, to porażka: -ENOMEM
    3. Jeżeli wypadkowe flagi dla Regionu Pamięci mm->def_flags okreslają, że strony nowo alokowanych Regionów mają być zablokowane w pamięci (VM_LOCKED), natomiast liczba zablokowanych przez proces stron przekroczyłaby dozwoloną wartość okresloną przez pole rlim Deskryptora Procesu (current->rlim[RLIMIT_MEMLOCK].rlim_cur), to porażka: -EAGAIN
    4. Jeżeli nowo-alokowany Region ma odwzorowywać dany plik, to:
      • Jeżeli strony mają móc być współdzielone (MAP_SHARED), to:
        • Jeżeli proces ma móc zapisywać do Regionu, ale nie ma praw zapisu do odwzorowywanego pliku, to porażka: -EACCES
        • Jeżeli plik można tylko appendować (dopisywać na koniec), ale prawa zwykłego zapisu do niego również są włączone, to -EACCES
      • Jeżeli strony mają być prywatne (MAP_PRIVATE), ale proces nie ma praw odczytu z pliku, to -EACCES
  2. Zaalokuj nowy obszar:
    1. Jeżeli nowo alokowany obszar ma być 'anonymous', tzn. nie ma być odwzorowaniem pliku ani przestrzeni I/O jakiegoś urządzenia, to spróbuj przedluzyć istniejący obszar (wyznaczany przez addr, a więc nie dowolny), o ile jego prawa dostępu są zgodne. Jeśli to się uda - zakończ.
      (to jest wlaśnie owo lączenie sąsiadujących ze sobą Regionów Pamięci, których prawa dostępu są zgodne)
    2. W przeciwnym przypadku, lub gdy powyższe się nie powiedzie:
    3. O ile flaga MAP_FIXED nie jest włączona we flags, znajdź odpowiednio duży obszar (get_unmapped_area(addr, len)). Nie ma -> -ENOMEM
    4. Jeżeli zaś flaga MAP_FIXED była włączona we flags, to spróbujemy użyć zadanej wartości addr jako pierwszego adresu nowo alokowanego obszaru
    5. Pobierz nowy Region Pamięci (struct vm_area_struct) z Alokatora Plytowego: kmem_cache_alloc(vm_area_cachep, SLAB_KERNEL). Nie udało się -> -ENOMEM
    6. Zainicjalizuj Region tak, aby poprawnie opisywał nowo alokowany obszar (zakresy, flagi)
  3. Sprawdź, czy wszystko poszło dobrze:
    1. Jeżeli nowo alokowany Region [ addr .. addr + len ] ma część wspólną z jakimś istniejącym Regionem (mogło się tak zdarzyc w przypadku użycia flagi MAP_FIXED), to porażka: zwolnij nowo zaalokowany Region i zwróć -ENOMEM
    2. Jeżeli wielkość (w stronach) Przestrzeni Adresowej procesu (mm->total_vm) przekracza ograniczenie zapisane w Deskryptorze Procesu (current->rlim[RLIMIT_AS].rlim_cur), to porażka: zwolnij nowo zaalokowany Region i zwróć -ENOMEM
    3. Jeżeli flaga MAP_NORESERVE nie była ustawiona we flags, Region ma zawierać prywatne, zapisywalne strony, natomiast ilość wolnej pamięci jest zbyt mała, to również porażka: zwolnij nowo zaalokowany Region i zwróć -ENOMEM
  4. Końcowe ustawienia:
    1. Wstaw nowo zaalokowany Region na listę (drzewo AVL) Regionów w Deskryptorze Pamięci bieżącego procesu (insert_vm_struct())
    2. W przypadku MAP_LOCKED (strony maja byc zablokowane w pamięci) fizycznie zaalokuj strony. Gdy flaga MAP_LOCKED jest zgaszona, strony beda sukcesywnie alokowane w miare potrzeby (p. "stronicowanie na żądanie")
    3. Zwróć pierwszy adres z nowego Regionu Pamięci


2.2.1.2 int do_munmap(struct mm_struct *mm, unsigned long addr, size_t len)

Funkcja do_munmap służy do zwalniania zakresu adresów z Przestrzeni Adresowej procesu.

Parametry:
Uwaga: zwalniany zakres adresów zwykle nie odpowiada dokładnie pojedyńczemu Regionowi Pamięci. Może być zawarty w którymś Regionie, może też obejmować dowolną liczbę Regionów. Nie musi zaczynać się ani kończyć w żadnym z Regionów.

Algorytm:

  1. Sprawdź wartości parametrów:
    1. Jeżeli addr nie jest wielokrotnością PAGE_SIZE (wielkości strony), to porażka: -EINVAL
    2. Jeżeli zwalniany obszar zachodzi na część Przestrzeni Adresowej procesu przeznaczoną dla jądra, to porażka: -EINVAL
    3. Jeżeli zwalniany obszar po wyrównaniu do granic stron ma zerową długość, to porażka: -EINVAL
  2. Usuń (lub odpowiednio zmniejsz) Regiony Pamięci nakładające się na usuwany zakres adresów:
    1. Znajdź najbardziej na lewo polożony Region, który nakłada się na usuwany przedział (find_vma_prev())
    2. Jeżeli nie ma takiego, to sukces: 0
    3. Wpp., jeżeli usuwany przedział dzieli znaleziony Region na dwie części, a liczba przydzielonych procesowi Regionów Pamięci osiągnęła swoje dozwolone maksimum (max_map_count, standardowo 65536), to (jako że nie możemy rozdzielić tego Regionu na dwa) porażka: -ENOMEM
    4. Zaalokuj jedną nową strukturę Regionu Pamięci (struct vm_area_struct) z Alokatora Płytowego (może być potrzebna do późniejszego usuwania Regionów). Porażka: -ENOMEM
    5. Utwórz listę Regionów Pamięci zachodzących na usuwany przedział. Lista tworzona jest na wskaźnikach vm_next, wskazujących "do tyłu" (na wcześniejsze Regiony)
    6. Po kolei usuń Regiony z listy, zmniejszając przy tym map_count w Deskryptorze Pamięci procesu. Przy każdym usuwanym Regionie:
      1. Jeżeli Region odwzorowywał plik, to usuń go z listy Regionów odwzorowujących ten plik zmniejszając liczbę dowiązań
      2. Zwolnij bloki stronicowe należące do części wspólnej bieżącego Regionu i usuwanego przedziału
      3. Unieważnij pozycje usuniętych bloków w tablicy TLB (Translation Lookaside Buffers)
      4. Jeżeli bieżący Region nie jest w całości pokrywany przez usuwany przedział, to (po usunięciu tegoż Regionu) wstaw z powrotem na listę jego "zmniejszoną" wersję (insert_vm_struct()).
  3. Jeżeli zaalokowana w pkt. 4 struktura vm_area_struct nie została wykorzystana, to ją zwolnij.
  4. Zwolnij tablice stron odpowiadające usuwanemu przedziałowi.


Oprócz mmap() istnieje również inna funkcja, sys_brk(), służąca do alokowania wyłącznie obszarów 'anonymous', tj., jak już wspomnieliśmy, nie związanych z żadnymi plikami ani urządzeniami. Służy ona do zwiększania (lub zmniejszania) sterty procesu, i stanowi po prostu uproszczoną wersję mmap(). Funkcja mmap() - dzięki parametrom prot, flag, file i offset - ma znacznie szersze zastosowanie: za jej pomocą można m.in. alokować pamięc przeznaczoną dla stosu trybu użytkownika, dla przestrzeni I/O urzadzeń, dla pamięci współdzielonej IPC oraz dla plików.



2.2.2 Tworzenie i usuwanie przestrzeni adresowej procesu

Uwaga: przed przeczytaniem tego punktu dobrze jest się zapoznać z techniką "kopiowania przy zapisie".


2.2.2.1 Tworzenie przestrzeni adresowej procesu

Tworzenie przestrzeni adresowej dla nowo powstającego procesu realizowane jest przez funkcję copy_mm z kernel/fork.c. Wywoływana jest ona przez funkcje z rodziny fork: clone(), fork() i vfork(), służące do tworzenia nowych procesów i wątków.

Dzięki technice kopiowania przy zapisie, funkcja copy_mm nie musi robić zbyt wiele:

2.2.2.2 Usuwanie przestrzeni adresowej procesu

Likwidacją przestrzeni adresowej procesu zajmuje się funkcja exit_mm(), wywoływana przez funkcję exit() i pokrewne:
  1. Zawiadom rodzica jeśli czeka na wywołaniu vfork()
  2. Zdekrementuj licznik mm_users w swoim Deskryptorze Pamięci mm_struct,
  3. Zwolnij Lokalną Tablicę Deskryptorów procesu
  4. Zwolnij kolejne Regiony Pamięci "odlinkowując" je od ewentualnie powiązanych z nimi i-node-ów
  5. Zwolnij Globalny Katalog Stron procesu
  6. Zwolnij sam Deskryptor Pamięci