Do spisu treści tematu 4

4.4 Stronicowane plików


Spis treści

  • Wprowadzenie
  • Struktury wykorzystywane przez stronicowanie plików
  • do_munmap()
  • generic_filemap()
  • Operacje na stronach
  • filemap_nopage()
  • filemap_swapout()
  • filemap_swapin()
  • Funkcja swapująca: shrink_mmap()
  • Bibliografia

  • Wprowadzenie

    Stronicowanie plików jest mechanizmem pozwalającym przypisać ciąg danych, zawarty w pliku, pewnym stronom pamięci wirtualnej procesu, najcześciej stanowiącym jej spójny obszar. Istotną cechą systemu zarządzania pamięcią w Linuxie, która w zasadzie stanowi o efektywności mechanizmu stronicowania (mapowania) jest ta, iż strona obecna w pamieci wirtualnej, tak na prawdę nie musi znajdować się w pamięci operacyjnej a może być do niej przywołana, gdy zajdzie potrzeba operacji na danych. Z tego powodu w strukturach pamięci wirtualnej muszą znajdować się informacje pozwalające szybko odnaleźć potrzebny fragment odpowiadającego danej stronie pliku na właściwym urządzeniu zewnętrznym.


    Struktury wykorzystywane przez stronicowanie plików

    Spójne obszary pamięci wirtualnej sa reprezentowane przez struktury vm_area_struct. Każdy proces pamięta w strukturze mm_struct ( przypisanej do task_struct ) wskaźniki do posortowanej kolejki oraz drzewa AVL tych struktur. Z punktu widzenia stronicowania plików szczególnie ważne są następujące elementy vm_area_struct :

  • - używane tylko przy mapowaniu plików :
  • struct inode *inode : i-węzeł stronicowanego pliku
  • unsigned long vm_offset : przesunięcie w pliku wyznaczające początek mapowanego obszaru
  • struct vm_operations_struct *vm_ops : funkcje obsługujące stronicowanie
  • - używane przy stronicowaniu plików i pamięci dzielonej :
  • struct vm_area_struct vm_next_share vm_prev_share : dwukierunkowa kolejka zawierająca wszystkie obszary pam. wirt. przypisane do danego pliku.
  • Ponieważ vm_area_struct funkcjonuje na wysokim, niezależnym od sprzętu poziomie a Linux obsługuje wiele systemów plików, twórcy systemu operacyjnego umieścili wszystkie opercje wymagające odwołania do specyficznego urządzenia dyskowego w jednej strukturze : vm_operations_struct. Owe funkcje obsługi są przypisywane przez funkcję mmap odpowiadąjacą plikowi, który jest mapowany do pamięci.( patrz : Operacje przypisywane do vm_ops).

    Z opisanymi powyżej operacjami związana jest jeszcze jedna struktura, mianowicie "page_cache" która jest kombinacją tablicy haszujacej struct page *page_hash_table[PAGE_HASH_SIZE] oraz przypisanych do niej stron ( pola page->next_hash page->prev_hash) .W strukturze tej, są umieszczone obecne w pamięci strony mapowanych plików, co pozwala uniknać wczytywania tych samych danych przez kilka procesów .


    Funkcje obsługi stronicowania

    Opis funkcji do_mmap(..)

    do_mmap jest funkcją służącą o tworzenia nowych obszarów pamięci wirtualnej, pozwalającą jednocześnie na stronicowanie plików.

    unsigned long do_mmap(struct file *file, unsigned long addr, unsigned long len, unsigned long prot, unsigned long flags, unsigned logn off)

    Znaczenie parametrów wywołania:
  • - file : wskaźnik do struktury file pliku, który chcemy mapować. Wartoscią tego parametru może być NULL, w tym wypadku przydzielona pamięć wirtualna nie będzie związana z żadnym plikiem. Naturalną konsekwencją są wtedy wartości vm_ops ==NULL, inode==NULL a wartość offset staje się nieistotna. Ograniczeniem przy wywołaniu funkcji z parametrem NULL, jest konieczność ustawienia flagi MAP_PRIVATE. Przy fladze MAP_SHARED zostanie zwrócony błąd niewłaściwego argumentu.
  • addr : życzenie co do poczatku mapowanego obszaru pamięci wirtualnej
  • len : dłlugość mapowanego obszaru
  • prot : flagi związane z prawami do czytania, zapisu i wykonywania na stronach należących do przydzielanego obszaru
  • flags: przekazywane tym parametrem flagi decydują o wlaściwościach stronicowania:
  • MAP_SHARED i MAP_PRIVATE : sa to wykluczające się flagi określające, czy zmiany na stronach mają charakter prywatny, czy też są dzielone. W tym drugim wypadku, obsługa stron jest bardziej złożona, co wymusza przypisanie większej ilości funkcji do struktury vm_ops. Warto zauważyć, iż obszar z ustawioną flagą VM_SHARED, jednocześnie przypisany do pliku do którego nie ma praw zapisu nie wymaga złożonych operacji na pamięci dzielonej. W tym wypadku ustawiana jest flaga VM_PRIVATE .
  • MAP_FIXED : ustawienie tej flagi oznacza iż funkcja musi przydzielić dokładnie obszar pamięci wirtualnej zaczynający się od "addr", a poprzednie stronicowania na nim zostaną usunięte. Oczywiście addr musi być wtedy wielokrotnoscią strony - warunek ten jest sprawdzany i gdy nie jest spełniony powoduje zwrócenie blędu "-EINVAL" (niewłasciwy argument).Gdy flaga nie jest ustawiona a podany obszar jest zajety, wywoływana funkcja get_unmapped_area() przegląda listę zajętych obszarów w poszukiwaniu fragmentu wolnej pamięci większej lub równej od wyznaczonej, po czym właśnie tam dokonuje się mapowania.
  • off : offset, określający początek stronicowanego obszaru pliku.Wartość ta nie musi być wielokrotnoscią rozmiaru strony.
  • Działanie funkcji do_mmap():

    Funkcja wpierw sprawdza poprawność przekazanych argumentów, następnie wybiera właściwy obszar pamięci wirtualnej (patrz : flaga MAP_FIXED ). Dalej, rezerwuje pamięć dla kolejnej struktury vm_area_struct i wypełnia jej pola:

  • vm_start, vm_end : początek i koniec obszaru pamięci;
  • vm_flags : flagi ustawiane na podstawie informacji w prot , flags, mm->def_flags a także flag pliku ( o ile przekazano plik );
  • vm_page_prot : ustawia flagi ochrony stron na podstawie ostatnich 4 bitów zmiennej vm_flags
  • vm_offset : przekazany offset w pliku pozostałe pola są zerowane.
  • Później, o ile dokonywane jest mapowanie pliku, wywoływana jest właściwa dla danego systemu plików funkcja file->f_op->mmap() która kończy wypełnianie pól struktury vm_area_struct o wartości charakterystyczne dla stronicowania pliku, w szczególności przypisuje wartość vm_inode i własciwe operacje ( *vm_ops ). Dalej pozostaje już tylko umieścić nowo powstalą strukturę na liście i drzewie AVL w danych procesu, sprawdzić czy przyłączony obszar nie styka się z innym odnoszącym się do tego samego pliku (można je wtedy połączyć w jedną strukturę ) i uaktualnić pola procesu:

  • mm->total_mm : (całkowita ilość przydzielonej pamięci)
  • mm->locked_vm : (całkowita ilość zablokowanej pamięci o ile ustawiona jest flaga VM_LOCKED : def_flags ).
  • Jeżeli z stronicowanym plikiem są związane jeszcze inne mapowania (jest dowiązanie do vm_inode->i_mmap), to przy dołączaniu obszaru do struktur procesu, jest on dodatkowo umieszczany na liście i_mmap a także pola vm_next_share i vm_prev_share sa ustawiane na elementy tej listy. (nazwa vm_prev/next_share jest trochę myląca: także strony z flagą VM_PRIVATE są umieszczane na tej liście o ile wskazują na ten sam fragment pliku).


    opis funkcji file->f_op->mmap() :

    Funkcja ta wywoływana jest wewnątrz funkcji do_mmap() i ma za zadanie wykonać akcje charakterystyczne dla danego systemu plików, przy stronicowaniu.W większości systemów plików do wskaźnika na mmap() przypisana jest funkcja generic_file_mmap(). Do nielicznych wyjątkow należą np. FAT , NCPFS , system NFS natomiast, wywołuje generic_file_mmap() wewnątrz własnej funkcji przypisanej na mmap().


    opis funkcji generic_file_mmap()

    int generic_file_mmap(struct inode * inode, struct file *file, struct vm_area_struct *vma)

    opis parametrów wywołania :
  • inode : wskaźnik na odpowiednią strukturę inode
  • file : wskaźnik na strukturę stronicowanego pliku
  • vma : struktura vm_area_struct do której mapujemy, jest ona częściowo wypełniona co pozwala przekazać dodatkowe parametry.
  • opis działania funkcji:

    Jeżeli w vm->vm_flags ustawiona jest flaga VM_SHARED oraz mozliwość zapisu, za operacje w vm_ops przypisywane są operacje charakterystyczne dla pamięci dzielonej (Dodatkowym warunkiem jest, aby przesunięcie w pliku było wielokrotnością rozmiaru strony) w przeciwnym wypadku funkcja przypisuje operacje odnoszace sie do pamięci prywatnej. Następnie sprawdzana jest poprawność elementóow struktury inode, zwiekszany licznik inode->i_count zliczający obszary mapujace odpowiadający i-węzłowi plik a vma->vm_inode przypisywana jest wartość i-węzła .


    opis funkcji do_munmap()

    Funkcja do_munmap() pozwala na usunięcie fragmentu pamięci wirtualnej przypisanej danemu procesowi.

    int do_munmap(unsigned long addr, size_t len)

    opis parametrów wywołania:
  • addr : początek obszaru pamięci wirtualnej do usunięcia;
  • len : długość tego obszaru;
  • opis działania funkcji;

    Po sprawdzeniu poprawności argumentów, funkcja wyszukuje kolejne struktury vma_area_struct do których należy wyrzucany obszar, usuwa je ze struktur procesu i umieszcza na specjalnej liście. Później, dla każdego elementu vma tej listy, usuwa go z cyklicznej listy vm_next_share/vm_prev_share a także modyfikuje wartość w vma->vm_inode->i_mmap jeśli ta wskazuje na owe vma . Wyrzuca z pamięci fizycznej strony dowiązane do pamięci wirtualnej vma i wywołuje funkcje unmap_fixmap(). Unmap_fixmap() zmienia zasięg obszaru vma uaktualniając również odpowiednie pola struktury procesu ( na przykład mm->total_vm : łączna ilość zajętej pamięci wirtualnej), o ile zachodzi taka potrzeba, unmap_fixmap() może też wyrzucić fragment pamięci leżący wewnątrz obszaru przypisanego do vma, tworząc nowe vm_area_struct dla pozostałości po obu stronach "dziury".


    Operacje przypisywane do vm_ops

    W znacznej większości systemów plików, wśród operacji umieszczonych w strukturze vm_operations_struct, tylko do kilku z nich jest przypisywana rzeczywista funkcja, reszta natomiast wskazuje na wartość NULL, co oznacza iż specyficzna akcja w ich wypadku nie jest konieczna. W najprostszym domyślnym przypadku, kiedy vm_area_struct określa obszar z flaga VM_PRIVATE (zmiany mają charakter prywatny) podłączana jest tylko jedna funkcja: filemap_nopage. Gdy zmiany zawartości obszaru są dzielone, potrzebne są dodatkowo funkcje synchronizujace zawartość strony z plikiem (gdy zajdzie zmiana na stronie), a także obsługujące swapowanie.

    Opis funkcji filemap_nopage()

    unsigned long filemap_nopage(struct vm_area_struct *area, unsigned long address, int no_share)

    opis parametrów wywołania:

  • area : odpowiednia struktura vma;
  • address : adres przy którym nastapił błąd braku strony
  • no_share : wartość tej zmiennej wskazuje na to czy można jako wynik zwrócić adres strony która już istnieje w pamięci i korzysta z niej inny proces czy też wymagane jeat aby obecny proces miał własną kopię strony.
  • opis działania funkcji:

    filemap_nopage() korzysta w istotny sposób z mechanizmu "cache page" (patrz: Struktury wykorzystywane przy stronicowaniu plików). W cache page umieszczane są strony które już znajdują się w pamięci opercyjnej lub zostaly do niej sprowadzone niejako przy okazji, gdy istnieje duże prawdopodobieństwo że będą potrzebne.

    Na początku funkcja sprawdza, czy strona jest obecna właśnie w page cache. Jeżeli tak i jej zawartość jest aktualna, to pobiera jej adres i przechodzi do znacznika success. W przeciwnym wypadku (nie ma strony w page cache ) rezerwuje pamięć na stronę , jeszcze raz sprawdza czy strona się nie pojawiła w page cache (proces mogł zasnąć podczas pobierania pamięci na stronę) a następnie umieszcza stronę w page cache (dla innych procesow) i wczytuje stronę nastepną (heurystyka pozwalająca niewielkim narzutem wczytać dodatkową stronęe : wiadomo, że pliki przetwarza się zazwyczaj sekwencyjnie) i również przechodzi do znacznika success.

    sucess: mamy stronę którą można zwrócić. Pozostaje jedynie problem ze zmienną no_share :jeżeli jest różna od zera, strona musi być wyłączna dla procesu : aktualna strona kopiowana jest do nowej a następnie zwalniana. Nowa strona jest wynikiem działania funkcji.

    Inne funkcje, wykorzystywane tylko przy stronach dzielonych :

    int filemap_swapout(struct vm_area_struct *vma, unsigned long offset, pte_t *page_table )

    opis parametrów wywołania :

  • vma : właściwa struktura vm_area_struct
  • offset : offset w pliku do którego funkcja zapisze stronę
  • pte_t : wskaźnik na tablicę stron
  • funkcja przed zwolnieniem strony zostawia w tablicy stron informację o numerze własnie zwalnianej strony. Pozwoli to w razie potrzeby odwołać się do strony przez funkcje filemap_swapin() podczas operacji wymiany. Po operacji informacja ta zostaje wymazana : strona została usunięta.

    int filemap_swapin(struct vm_area_struct *vma, unsigned long offset, unsigned long entry)

    opis parametrów wywołania:

  • vma : własciwa struktura vm_area_struct
  • offset : offset w pliku
  • entry : zawiera informacje na temat strony, która własnie jest swapowana, zakodowane za pomocą funkcji SWAP_ENTRY podczas działania funkcji filemap_swapout();
  • działanie funkcji jest bardzo proste : rozkodowuje informacje zawartą w entry: odnajduje odpowiednią stronę, przywraca jej odpowiednie flagi i zwiększa licznik stron.

    int filemap_sync(struct vm_area_struct *vma, unsigned long address, size_t size, unsigned int flags)

    opis parametrów wywołania :

  • vma : wlaściwa struktura vma
  • address : adres początkowy obszaru do synchronizacji
  • size : rozmiar : długość obszaru
  • flags : zmienna ta musi przyjmować jedną z flag MS_SYNC - odwołanie synchroniczne, MS_ASYNC - odwołanie do strony jest asynchroniczne - dokonuje się poza procesorem lub MS_INVALIDATE
  • Funkcja dokonuje synchronizacji zawartości obszaru pamięci z odpowiednimi fragmentami dysku. Wywołuje ona kaskadowo analogiczne funkcje na poziomie katalogu tablic stron i tablic stron aż wreszcie na poziomie pojedynczej strony, gdzie sprawdza czy strona była już przywołana do pamięci,wartość flag oraz to czy strona była zmieniana. Jeśli była, dokonuje zapisu strony na dysk.


    Funkcja shrink_mmap()

    Stronicowanie plików charakteryzuje się specyficzną funkcją obsługi wymiany strony, wywoływaną przez try_to_swap_out(), mianowicie shrink_mmap()

    int shrink_mmap(int priority, int dma, int free_buf)

    opis parametrów wywołania :

  • priority : przekazywany priorytet pomaga określić, ile stron trzeba przejrzeć w celu usunięcia.
  • dma : właściwy kanał dma
  • free_buf : parametr określający dostępność buforów
  • Najpierw funkcja określa maksymalną ilość stron, które ma przejrzeć w celu znalezienia właściwej do wyrzucenia, a także maksymalną ilość przeglądanych stron posiadających bufory. Później, zaczynając od miejsca, na którym skończyła ostatnio przeglądanie, rozpoczyna szukanie właściwej strony. Odrzucane są strony zablokowane i pod niewłaściwym kanałem dma. Jeśli strona ma bufory to ich ich bity wieku są zerowane. Dalej , o ile do strony jest przypisany jeden proces ( strona jest prywatna ), funkcja sprawdza wiek strony (dla priority >3) wiek nie ma znaczenia :pewną stronę koniecznie trzeba usunąć. O ile strona przypisana jest do pliku, zostaje usunięta z kolejki "page cache" lub z "bufor cache". Jeżeli do strony odwołuje się więcej niż jeden proces, to oznacza iż strona jest dzielona i nie można jej usunąć.


    Bibliografia

    Pliki źródłowe Linuxa
  • include/linux/mm.h
  • include/linux/fs.h
  • include/linux/pgtable.h
  • mm/mmap.c
  • mm/filemap.c


  • Autor : Piotr Kozłowski