W tablicy free_area jadro przechowuje kolejki spojnych wolnych obszarow pamieci. free_area[i].list jest poczatkiem cyklicznej listy na ktorej znajduja sie wolne obszary rozmiaru (i+1)*PAGE_SIZE (dla i386 PAGE_SIZE = 4KB). Kazdy obszar ma specjalny bit swiadczacy o tym czy jest wolny czy zajety. Bity te sa przechwywane w obszarze pamieci wskazywanym przez free_area[i].map.
Oto deklaracja struktury free_area_struct oraz tablicy free_area:
#define NR_MEM_LISTS 6
struct free_area_struct {
struct page list;
unsigned int * map;
};
static struct free_area_struct free_area[NR_MEM_LISTS];
Tablica ( jak rowniez zwiazane z nia listy ) sa modyfikowane w momencie zajmowania obszaru pamieci oraz jego zwalniania.
Funkcja odpowiedzialna za wybor wolnego obszaru pamieci jest funkcja:
__get_free_pages(int priority, unsigned long order, int dma)
Rezultat: adress fizyczny do poczatku przydzielonego obszaru, 0 w przypadku niepowodzenia.
Funkcja ta wywoluje makro RMQUEUE(order, dma) ktore wykonuje algorytm wyboru obszaru ( argumenty: order i dma sa argumentami przekazanymi do __get_free_pages(..) ).
Algorytm wyboru ramki:
System zaczyna przegladac liste wolnych obszarow free_area[order] . Jesli znalazl wolny obszar to "wycina" z niego jedna ramke i adres do niej zwraca jako wynik funkcji. Pozostaly wolny obszar dzieli na obszary bedace potega 2 razy PAGE_SIZE a nastepnie wklada je do odpowiednich list free_area[i].list. Np. jesli zostanie znaleziony obszar o wielkosci 8*PAGE_SIZE to pierwsza ramka tego obszaru zostanie zwrocona jako rezultat funkcji a pozostale (zfragmentowane) obszary (7*PAGE_SIZE=(4+2+1)*PAGE_SIZE) beda odpowiednio umieszczone w kolejkach free_area[i] i=0..2.
Funkcja free_pages_ok ma dokladnie odwrotne dzialanie w porownaniu do
funkcji __get_free_pages. Funkcja ta stara sie 'przylepic' zwolniona ramke
do innego wolnego obszaru pamieci przechowywanych na listach free_area,
starajac sie przez to otrzymac wiekszy spojny obszar pamieci. Proces ten
jest defragmentacja dostepnych fragmentow pamieci.
extern mem_map_t * mem_map;
Tablica ta przechwuje informacje o kazdej ramce pamieci bedacej w systemie. Podczas startu systemu jadro zaczyna zajmowac dla siebie miejsce od dolnych adresow pamieci. Po zakonczeniu ladowania systemowych danych i kodu system cala pozostala pamiec dzieli na ramki. W tym momencie jest inicjalizowana tablica mem_map (funkcja: mem_init(..) plik: linux/arch/*/mm/init.c ). Karzdy element mem_map odpowiedzialny jest za obszar rozmiaru PAGE_SIZE (zaleznego od architektury). Co przechowuje system dla kazdej z ramek i do czego informacje te sa wykorzystywane szczegolowo opisalem przy opisie samej struktury page.
Struktura ta przechowuje informacje o kazdej ramce pamieci fizycznej (nie liczac pamieci rezerwowanej przez jadro podczas startu systemu).
Oto definicja struktury page:
typedef struct page {
struct inode *inode;
unsigned long offset;
struct page *next_hash;
atomic_t count;
unsigned flags;
unsigned dirty:16,
age:8;
struct wait_queue *wait;
struct page *next;
struct page *prev;
struct page *prev_hash;
struct buffer_head * buffers;
unsigned long swap_unlock_entry;
unsigned long map_nr; /* page->map_nr == page - mem_map */
} mem_map_t;
Strona moze nalezec do 'inode's memory mapping'. W tym wypadku page->inode jest i-wezlem, a page->offset jest offsetem pliku. Dla stron nalezacych do i-wezlow page->count jest licznikiem przylaczen - plus 1 jesli sa przydzielone bufory na te strony.
Wszystkie strony nalezace do i-wezla posiadaja podwojna liste inode->i_pages uzywajac do tego celu pol page->next i page->prev. Lecz z punktu widzenia zarzadzania ramkami to pole ma rowniez inne, wazniejsze zastosowanie. W przypadku kiedy page->count==0 pola te sa uzywane przez mechanizm zarzadzania wolnymi przestrzeniami pamieci (patrz: free_area) i sluza do tworzenia cyklicznych list wolnych obszarow o danym rozmiarze.
Do szybkiego wyszukiwania stron nalezacych do i-wezlow jadro uzywa kolejki haszujacej. Odpowiednia strone wyszukuje sie majac pare (inode,offset). Pola page->next_hash i page->prev_hash sa wskaznikami do nastepnego i poprzedniago elementu w talicy haszujacej.
Page->wait jest kolejka procesow czekajacych na zakonczenie operacji I/O na tej ramce. Po zakonczeniu takiej operacji procesy oczekujace na jej zakonczenie zostaja obudzone.
Pole to mowi ile procesow, buforow itd. jest przydzielone do danej ramki. Licznik ten sluzy miedzy innymi do stwierdzenia czy dana ramke mozna uznac za wolna. Z pola tego rowniez korzysta mechanizm opoznionego zapisu. Kidy proces prubuje zapisac cos do ramki nalezaca do pamieci dzielonej to dopiero w tym momencie przydzielena jest nowa ramka, kopiowana zawartosc a licznik starej ramki jest zmniejszany o 1.
Ponizej znajduja sie wszystkie flagi uzywane w polu flags. Uwaga: zmiana oraz testowanie wartosci tego pola zazwyczaj jest operacja niepodzielna.
/* Page flag bit values */ #define PG_locked 0 #define PG_error 1 #define PG_referenced 2 #define PG_uptodate 3 #define PG_free_after 4 #define PG_decr_after 5 #define PG_swap_unlock_after 6 #define PG_DMA 7 #define PG_reserved 31
Bit ten sluzy do zakladania blokady na ramce dla ktorej operacja wymiany jeszcze sie nie zakonczyla. Jesli operacja wymiany jest juz kompletna blokada jest zdejmowana, czyli zerowany jest bit PG_locked. Blokada ta jest zabezpieczeniem przed bardzo niekorzystnym zjawiskiem jakim jest "wyscig". Jest to sytuacja w ktorej nadchodzi zadanie operacji I/O na ramce dla ktorej nie zakonczyla sie jeszcze wczesniejsza (synchroniczna !) operacja I/O.
Bit ten informuje o tym czy operacja I/O na ramce zakonczyla sie sukcesem. Jesli podczs tej operacji wystapil blad (np. blad urzadzenia wymiany) bit ten jest rowny 1.
Bit ten jest wykozystywany w procesie wyboru ramki do odeslania na swap'a. Bit ten jest zapalany za kazdym razem kiedy system odwoluje sie do tej ramki poprzez kolejke haszujaca (funkcje: add_page_to_hash_queue oraz find_page plik: pagemap.h). Bit ten jest sprawdzany jek rowniez modyfikowany w funkcji shrink_mmap (plik: mm/filemap.c) ktora odpowiedzialna jest za wybor ramki do zwolnienia. Jesli ramka ma zapalony bit PG_referenced jest on zerowany, a ramka nie jest odsylana do swapa. Zerowy bit PG_referenced jest jednym z warunkow odeslania do swapa.
Bit ten mowi czy zawartosc ramki jest aktualna. Kiedy konczy sie operacja zapisu do ramki ustawia sie ten bit (lub nie ustawia w przypadku wystapienia bledu podczas operacji czytania).
Jesli operacja zapisu I/O zakonczy sie i bit PG_free_after jest rowny 1 to strona zostaje natychmiast zwolniona.
Linux posiada mechanizm synchronicznej i asynchronicznej wymiany ramek. Oznacza to ze w tej samej chwili kilka ramek moze jednoczesnie podlegac wymianie (byc zapisywane na urzadzenie wymiany oraz byc z niego sprowadzane). Jesli operacja I/O na ramce jest wykonywana synchronicznie (czyli nie czekamy na koniec operacji) to bit ten jest ustawiany na 1, a licznik wszystkich synchronicznych operacji I/O (nr_async_pages) jest zwiekszany o jeden. Zawsze po zakonczeniu operacji I/O jesli bit PG_decr_after jest rowny jeden to zmniejszany jest licznik nr_async_pages.
patrz: funkcja brw_page
Ten bit jest ustawiany tylko funkcji rw_swap_page(..) (plik: mm/page_io.c) w przpadku kiedy nie chcemy czekac az skonczy sie operacje I/O na ramce. W tym przypadku sa tez zapalane bity PG_free_after i PG_decr_after oraz zwiekszana jest o jeden ilosc synchronicznych operacji I/O na ramkach: atomic_inc(&nr_async_pages).
Natomiat bit ten jest testowany (i zarazem zerowany) tylko w funkcji after_unlock_page(..) - plik: fs/buffer.c. Funkcja ta jest wywolywana w momencie zakonczenia operacji I/O.
Bit ten jest ustawiny dla ramek ktore leza w zasiegu mechanizmu transferu kanalami DMA. Zasieg ten jest scisle uzalezniny od architektury.
Podczas startu systemy (funkcja: free_area_init plik: mm/page_all.c) bit ten jest ustawiany dla kazdej ramki. Dopiero po tym ( w funkcji mem_init plik: arch/*/mm/init.c ) jesli ramka lezy poza adresem MAX_DMA_ADDRESS bit ten jest zerowany. Na przyklad dla i386 wartosc ta wynosi:
/* The maximum address that we can perform a DMA transfer to on this platform */ #define MAX_DMA_ADDRESS 0x1000000
Flaga ta oznacza ze do tej ramki nie moze byc zadnych odwolan (strona ta moze wogole nie istniec). Uzywanie tej flagi jest w duzym stopniu uzaleznione od architektory procesora. Podczas startu systemu ( start_kernel -> paging_init -> free_area_init ) flaga ta jest ustawiana dla kazdej ramki (nie zaleznie od architektury - plik: mm/page_all.c).
Ramka moze posiadac zaalokowane na sobie bufory. Jesli tak jest to page->buffers jest cykliczna lista tych buforow, jesli tak nie jest to page->buffers==NULL.
To pole bitowe przechwuje informacje dotyczace wieku ramki. W Linuxie stosuje sie liniowe postarzanie (funkcja age_page postarza strone a funkcja touch_page odmladza. Im strona ma mniejsze age tym jest starsza !. MAX_PAGE_AGE, PAGE_ADVANCE i PAGE_DECLINE sa stalymi. Wartosc tych stalych ma kluczowe znaczenie dla dzialania algorytmow decydujacych o wyborze ramki ktora nalezy odeslac do swapa. Zmiana wartosci tych stalych doprowadzi do calkiem innego zachowania systemu.
static inline void touch_page(struct page *page)
{
if (page->age < (MAX_PAGE_AGE - PAGE_ADVANCE))
page->age += PAGE_ADVANCE;
else
page->age = MAX_PAGE_AGE;
}
static inline void age_page(struct page *page)
{
if (page->age > PAGE_DECLINE)
page->age -= PAGE_DECLINE;
else
page->age = 0;
}
Funkcja ta wykonuje operacje I/O pomiedzy pamiecia (ramkami) a urzadzeniem wymiany.
argumenty (niektore):
brw_page od wczesniejszych funkcji oczekuje ze strona ta jest juz zablokowana (czyli zapalony bit PG_locked). Funkcja ta moze sie zakonczyc jeszcze przed zakonczeniem operacji I/O (synchroniczna wymiana stron).
Krotki opis funkcji :
Po zakonczeniu operacji I/O :
static inline void after_unlock_page (struct page * page)
{
if (clear_bit(PG_decr_after, &page->flags))
atomic_dec(&nr_async_pages);
if (clear_bit(PG_free_after, &page->flags))
free_page(page_address(page));
if (clear_bit(PG_swap_unlock_after, &page->flags))
swap_after_unlock_page(page->swap_unlock_entry);
}
Funkcja jest uruchamiana po zakonczeniu kazdej operacji I/O. Jako parametr otrzymuje wskaznik do odpowieniego miejsca w tablicy ramek mem_map. Jesli byl ustawiony bit PG_decr_after zmniejsza licznik synchronicznych operacji I/O na ramkach. Jesli byl ustawiony bit PG_free_after ramka zostaje natychmiast zwolniona.
Wiekszosc funkcji zarzadzajacymi ramkami silnie korzysta ze sprzetowej akceleracji zaleznej od uzytego procesora (procesorow). Pociaga to za soba fakt ze wiele z nich, w zaleznosci od architektory, znacznie sie od siebie rozni. Ze wzgledu na to ze jadro 2.0.0 Linuxa przewidziane jest na kilka platform, trudno bylo mi analizowac zachowanie pewnych funkcji dla kazdej z platform. Tak wiec w opisie funkcji systemowych scisle zwiazanych z rodzajem procesora ograniczalem sie do i386. Na tej stronie staralem sie zaznaczac ktora funkcja jest zalezna od sprzetu, a ktora nie. Przepraszam jesli gdzies zapomnialem dodac ta uwage. Przy niektorych funkcjach dopisywalem plik zrodlowy w ktorym dana funkcja sie znajduje. Z polozenia tego pliku rowniez latwo domyslic sie czy funkcja jest zalezna od platformy czy tez nie.