2. Struktury danych, czyli "co jest czym czego"




1.1. Deskryptor pamięci


Wszystkie informacje związane z przestrzenią adresową procesu zawarte są w strukturze typu struct mm_struct wskazywanej przez pole mm Deskryptora Procesu:


--> include/linux/sched.h :

struct mm_struct {
        struct vm_area_struct * mmap;            // Lista Regionów Pamięci procesu
        struct vm_area_struct * mmap_avl;        // Drzewo AVL Regionów Pamięci procesu
        struct vm_area_struct * mmap_cache;      // Region Pamięci, z którego proces ostatnio korzystał
        pgd_t * pgd;                             // Globalny Katalog Stron procesu

        atomic_t mm_users;                       // Liczba procesów współdzielących ten Deskryptor Pamięci.
                                                 //   > 1 oznacza, ze mamy do czynienia z kilkoma
                                                 //   wątkami jednego procesu

        atomic_t mm_count;                       // Liczba referencji do tej struktury
        int map_count;                           // Liczba Regionów Pamięci (p. niżej)
        struct semaphore mmap_sem;               // Semafor używany w różnych sytuacjach, m.in.
                                                 //   w procedurze obsługi błędu strony (p. rozdz. 3)
        spinlock_t page_table_lock;

        struct list_head mmlist;

        unsigned long start_code, end_code, start_data, end_data;
        unsigned long start_brk, brk, start_stack;
        unsigned long arg_start, arg_end, env_start, env_end;

        unsigned long rss;                       // Liczba faktycznie przyporządkowanych procesowi bloków stronicowych
        unsigned long total_vm                   // Wielkość przestrzeni adresowej wyrażona w liczbie stron
        unsigned long locked_vm;                 // Liczba "wirtualnych stron" (niekoniecznie faktycznie przydzielonych)
                                                 //   zablokowanych w pamięci RAM (nie swapowalnych)
                                                 //   ( p. "stronicowanie na żądanie" )

        unsigned long def_flags;                 // Wypadkowe flagi dla nowych Regionów Pamięci
        unsigned long cpu_vm_mask;
        unsigned long swap_address;

        mm_context_t context;
};

1.2. Region Pamięci


Przestrzeń adresowa procesu składa się z Regionów Pamięci, wyznaczających rozłączne przedziały adresów liniowych przydzielonych procesowi. Każdy Region Pamięci składa się z całkowitej liczby kolejnych stron pamięci, a więc i granice Regionów są całkowitymi wielokrotnościami wielkości strony (PAGE_SIZE, standardowo 4096). Każdy z tych Regionów opisywany jest przez strukturę typu struct vm_area_struct:


--> include/linux/mm.h :

struct vm_area_struct {
        struct mm_struct * vm_mm;               // Deskryptor pamięci procesu, do którego ten region należy
        unsigned long vm_start;                 // Pierwszy adres liniowy reprezentowanego przedziału
        unsigned long vm_end;                   // Ostatni adres liniowy reprezentowanego przedziału plus jeden (czyli "najmniejszy większy")

                                                // Lista Regionow Pamięci danego procesu, posortowana po vm_start:
        struct vm_area_struct *vm_next;         // Następnik

        pgprot_t vm_page_prot;                  // Początkowe wartości Flag w Tablicach Stron
        unsigned long vm_flags;                 // Flagi charakteryzujące ten Region Pamięci

                                                // Drzewo AVL Regionów Pamięci danego procesu, również posortowane po vm_start
        struct vm_area_struct * vm_avl_left;    // Lewe  dziecko
        struct vm_area_struct * vm_avl_right;   // Prawe dziecko
        short vm_avl_height;                    // Wysokość poddrzewa tegoż drzewa o korzeniu w tym Regionie Pamięci


        /* For areas with an address space and backing store,
         * one of the address_space->i_mmap{,shared} lists,
         * for shm areas, the list of attaches, otherwise unused.
         */
        struct vm_area_struct *vm_next_share;
        struct vm_area_struct **vm_pprev_share;

        struct vm_operations_struct * vm_ops;
        unsigned long vm_pgoff;         /* offset in PAGE_SIZE units, *not* PAGE_CACHE_SIZE */
        struct file * vm_file;
        unsigned long vm_raend;
        void * vm_private_data;         /* was vm_pte (shared mem) */
};

Jako że - jak już powiedzieliśmy - Regiony Pamięci są rozłączne, możemy naszkicować relacje między Deskryptorem Pamięci, Regionami Pamięci oraz Przestrzenią Adresową procesu w następujący sposób:



Jak widać, lista Regionów Pamięci jest posortowana rosnąco względem zakresów adresów liniowych reprezentowanych przez jej elementy. Pomiędzy kolejnymi przedziałami adresów istnieją przedziały wolne, nie przydzielone procesowi. Próba odwołania się przez proces do ktoregoś z nieprzydzielonych mu adresów powoduje wyjątek błędu strony, tzw. Page Fault.

Jak już wiemy, w jądrze (include/asm-i386/page.h) istnieje stała PAGE_OFFSET, wyznaczająca adres, na którym kończy się przestrzeń adresowa procesu dostępna z poziomu użytkownika, a zaczyna przestrzeń adresowa tegoż procesu dostępna tylko z poziomu jądra. Najczęściej jest ona równa 0xC0000000, co oznacza podział w stosunku 3/4 (3GB przestrzeni dla użytkownika, 1GB przestrzeni dla jądra).



1.2.1 Pole vm_flags, czyli prawa dostępu do Regionu Pamięci

Oprócz omówionych wcześniej flag związanych z pojedyńczymi stronami (flagi przechowywane w każdej pozycji Tablicy Stron i flagi przechowywane w polu flags każdego Deksryptora Strony), istnieją flagi związane z omawianymi Regionami Pamięci, czyli grupami stron. Są one przechowywane w polu vm_flags deskryptora Regionu Pamięci typu struct vm_area_struct. Używane są następujące flagi:

VM_READ      Strony można czytać
VM_WRITE      Strony mogą być zapisywane
VM_EXEC      Strony mogą być wykonywane
VM_SHARED      Strony mogą być współdzielone przez kilka procesów
VM_MAYREAD      Można ustawić flagę VM_READ
VM_MAYWRITE      Można ustawić flagę VM_WRITE
VM_MAYEXEC      Można ustawić flagę VM_EXEC
VM_MAYSHARE      Można ustawić flagę VM_SHARED
VM_GROWSDOWN      Region można rozszerzać w stronę dolnych adresów
VM_GROWSUP      Region można rozszerzać w stronę górnych adresów
VM_SHM      Strony są używane jako pamięć współdzielona IPC
VM_DENYWRITE      Region odwzorowuje plik, do którego nie można pisać. Przy próbie zapisu zgłaszany jest błąd ETXTBSY
VM_EXECUTABLE      Strony zawierają wykonywalny kod
VM_LOCKED      Strony są zablokowane w pamięci RAM i nie można ich wymieniać
VM_IO      Region odwzorowuje przestrzeń adresową I/O jakiegoś urządzenia
VM_DONTCOPY      Nie powielać tego Regionu podczas wykonania funkcji fork()
VM_DONTEXPAND      /* Cannot expand with mremap() */
VM_RESERVED      /* Don't unmap it from swap_out */

Dozwolone są wszystkie możliwe kombinacje powyższych flag - np. mozliwe jest takie ustawienie, aby można było wykonywać strony danego Regionu Pamięci, ale nie odczytywać. Aby efektywnie realizować ten mechanizm ochrony, związane z Regionem Pamięci prawa muszą być powielone we wszystkich odpowiednich pozycjach tablic stron, tak by sprawdzania ich dokonywała bezpośrednio sprzętowa jednostka stronicowania.

Praw dostępu do Regionu Pamięci jest jednak kilka - dokładnie cztery: VM_READ, VM_WRITE, VM_EXEC, VM_SHARE. Bitów ochrony strony w procesorach Intel jest zaś tylko dwa (flagi User/Supervisor i Read/Write). W dodatku flaga User/Supervisor musi zawsze być ustawiona, w przeciwnym bowiem przypadku proces nigdy nie mógłby uzyskać dostępu do swojej własnej strony z poziomu użytkownika.

Konieczne było zatem wprowadzenie pewnych ograniczeń:

I tak przyjęto następujące założenia (w symbolicznej notacji):

1.2.2 Zachowywane niezmienniki, czyli co umożliwia pole vm_flags

Trzecim - oprócz rozłączności i posortowania - niezmiennikiem zachowywanym przez jądro przy operacjach na Przestrzeniach Adresowych procesów, jest łączenie sąsiadujących ze sobą Regionów Pamięci (takich, ze vm_start jednego jest równe vm_end drugiego), których prawa dostępu są takie same.