Struktury danych stosowane przy pamieci buforowej maja na celu:
Dowolny blok w systemie plikow (a takze ewentualny bufor zawierajacy dane z niego) jest jednoznacznie identyfikowany przez numer urzadzenia, na ktorym sie znajduje i numer bloku na tym urzadzeniu. I te dwie wartosci sa argumentami funkcji mieszajacej (w rzeczywistosci makra), zdefiniowanej nastepujaco:
_hashfn(nr_urzadzenia, nr_bloku)=(nr_urzadzenia XOR numer bloku) mod nr_hash
Zatem mamy nr_hash kolejek mieszajacych przechowywanych w tablicy hash_table. Zmienna nr_hash jest zalezna od rozmiaru pamieci i jest inicjowana w funkcji buffer_init razem z tablica hash_table. Przyjmuje wartosci od 997 do 65521. Kolejki mieszajace sa listami prostymi dwukierunkowymi. Wykorzystywane sa w nich skladowe b_prev i b_next naglowka buforu. Praktycznie wszystkie odwolania do tablicy mieszajacej sa realizowane poprzez makro hash(dev,block), zwracajace te liste, ktora moze zawierac dany bufor.
Poniewaz Linux dopuszcza rozne rozmiary buforow (od 0.5 do 8 kB), mamy osobna liste dla kazdego rozmiaru. Kazda z nich jest dwukierunkowa lista cykliczna, wykorzystujaca skladowe b_next_free i b_prev_free naglowka buforu. Zmienna free_list jest tablica indeksowana numerami rozmiarow (szczegoly w pliku buffer.c). Wszystkie bufory na tych listach nie zawieraja danych (pole b_dev ustawione na B_FREE).
Aby moc wybrac uzywany bufor do usuniecia, wszystkie bufory z danymi
sa trzymane w tablicy lru_list, porzadkujacej bufory wzgledem czasu ostatniego
uzycia. Deklaracje:
static struct buffer_head * lru_list[NR_LIST]
#define BUF_CLEAN 0 /* Bufory nie nalezace do zadnej z kategorii nizej
*/
#define BUF_UNSHARED 1 /* Bufory, ktore przestaly byc dzielone */
#define BUF_LOCKED 2 /* Bufory przeznaczone do zapisu */
#define BUF_LOCKED1 3 /* Bufory z danymi specjalnymi*/
#define BUF_DIRTY 4 /* Bufory, ktore trzeba bedzie kiedys zapisac */
#define BUF_SHARED 5 /* Bufory dzielone */
#define NR_LIST 6 /* Liczba list w tablicy */
Mamy tutaj szesc rodzajow, na jakie podzielono bufory z danymi. Bufory
dzielone (lista 5) sa to bufory, ktore zostaly odwzorowane na przestrzen
adresowa jakiegos procesu (Linux robi to zamiast kopiowac ich zawartosc
do przestrzeni adresowej procesow). Powod, dla ktorego bufory BUF_UNSHARED
sa rozrozniane od BUF_CLEAN jest mi nie znany. Danymi specjalnymi (lista
3) sa na przyklad i-wezly.
Tablica lru_list pod kazdym z indeksow trzyma kolejke cykliczna buforow
danego rodzaju. Wskaznikami do bufora nastepnego i porzedniego w buforze
sa pola b_next_free i b_prev_free (te same co dla kolejki buforow wolnych,
zatem nie mozna byc w obu kolejkach na raz). Oprocz tego kazdy bufor w
skladowej b_list przechowuje indeks, pod ktorym znajduje sie jego lista
lru. A raczej pod ktorym indeksem sie powinien znajdowac. Bo zauwazmy,
ze lista BUF_LOCKED jest to lista buforow, ktorych zawartosc jest zapisywana
na dysk. Kiedy operacja zapisu sie skonczy, nalezalo by przeniesc bufor
do innej listy. Ale operacje zwiazane z zakonczeniem zapisu sa dokonywane
przez obsluge przerwania, a ta nie moze zmieniac struktur list (bo przerwanie
moze przyjsc w trakcie na przyklad obchodzenia tej listy). Zatem zmieniane
jest tylko pole b_list i kto inny (proces ktory to wykryje) zajmuje sie
przenoszeniem bufora do innej listy. Sluzy do tego funkcja refile_buffer.
Listy lru sa wykorzystywane przez funkcje refill_freelist.
Deklaracja typow list w pliku include/linux/fs.h
Jak juz stwierdzilem w opisie naglowka buforu nie jest to glowny temat
mojego zainteresowania, dlatego wspominam o tym tylko pobieznie.
Wiekszosc stron pamieci, nie wylaczajac stron zawierajacych bufory,
podlega algorytmowi starzenia (ang. aging), sluzacemu wybraniu "ofiary"
podlegajacej wywlaszczeniu, gdy potrzeba zwolnic miejsce w pamieci. Ale
strony z buforami wymagaja specyficznego traktowania - oczywiscie absurdem
bylby swapping ich na dysk, zamiast tego nalezy upewnic sie, ze wszystkie
bufory sa wolne i zwolnic pamiec. Starzeniem sie buforow zajmuje sie funkcja
age_buffer, korzystajaca
z tablicy next_to_age. Jest to tablica indeksowana numerami list lru i
zawiera wskazniki do buforow z kazdej z tych list. Kiedy wszystkie bufory
na stronie sie zestarzeja i zostanie podjeta decyzja o wywlaszczeniu, sa
one usuwane ze wszystkich struktur i przenoszone do kolejek unused_list
i reuse_list. Wykorzystywane sa wskazniki next_free i prev_free. W kolejce
unused_list sa bufory, ktore mozna juz utracic, a w reuse_list te, na ktorych
maja zostac jeszcze wykonane operacje zapisu (odczyt sie nie moze zdarzyc).
Pozniej sukcesywnie bufory z reuse_list sa przenoszone do unused_list,
az sie oprozni. Te listy mozna budowac dzieki temu, ze wszystkie bufory
na stronie sa polaczone w liste jednokierunkowa za pomoca wskaznikow b_this_page
z naglowka bufora.
Operacjami na unused_list i reuse_list zajmuja sie nastepujace funkcje