System plików

Podręczna pamięć buforowa katalogów

Krzysztof Sikora

1. Wstęp

W systemie Linux nie tylko pliki posiadają podręczną pamięć buforową, która pozwala minimalizować częstość transmisji danych z urządzeń fizycznych takich jak dyski, posiadają ją także katalogi. Pozwala ona przyspieszyć dostęp do pozycji katalogowych.

2. Lokalizacja

Większość algorytmów zaimplementowanych jest w pliku fs/dcache.c, natomiast struktury danych są zdefiniowane w include/linux/dcache.h.

3. Opis realizacji

W pamięci operacyjnej znajduje się tablica mieszająca dentry_hashtable, której elementami są dwukierunkowe, cykliczne listy (Rysunek 1). Elementami list są struktury dentry, które przechowują pozycje katalogowe, a tym samym reprezentują obiekty dyskowe w pamięci. Ponadto pozycje zorganizowane są w dwie listy LRU (Rysunek 2). Do listy pierwszego poziomu są wstawiane odczytywane z dysku dane katalogowe (np. po wykonaniu polecenia ls). Natomiast w liście drugiego poziomu przechowywane są pozycje, których używamy częściej (np. nazwy plików, na których wykonaliśmy wc, cat). Element migrują z pierwszej listy do drugiej, jeśli odwołaliśmy się do niego (oznacza to, że prawdopodobnie będziemy go także potrzebować także w przyszłości). Tak zaprojektowany mechanizm pozwala uniknąć usuwania często używanych pozycji przez pozycje rzadko używane, co zdarzyłoby się gdyby istniała tylko jedna lista LRU. Wyobraźmy sobie, że w pamięci podręcznej katalogów mamy tylko pozycje, do których się bardzo często odwoływaliśmy i odczytujemy zawartość katalogu, w którym jest dużo plików. Pozycje katalogowe tych plików jako świeższe "wypchną" z listy LRU te, które już tam były. Jest to sytuacja niepożądana, ponieważ usunęliśmy pozycje często używane, a zbuforowaliśmy takie, które prawdopodobnie nie będą nam już potrzebne.
W listach LRU elementy najczęściej używane są na końcu. Listy będące elementami tablicy haszującej są przeszukiwane liniowo.

Rysunek 1: Tablica mieszająca podręcznej pamięci buforowej katalogów

Rysunek 2: Listy LRU podręcznej pamięci buforowej katalogów

4. Pozycje katalogów - reprezentacja katalogów w systemie plików ext2

W systemie Linux katalogi to specjalny rodzaj plików. Zamiast danych w blokach przechowywane są tak zwane pozycje katalogowe. Są to struktury ext2_dir_entry_2, których polami są:

numer i-węzła
długość pozycji katalogowej
długość nazwy
typ pliku
- nieznany
- zwykły plik
- katalog
- urządzenie znakowe
- urządzenie blokowe
- kolejka FIFO czyli łącze nazwane
- gniazdo
- dowiązanie symboliczne
nazwa, której długość jest ograniczona przez stałą EXT2_NAME_LEN (w jądrze 2.4.7 równą 255)

5. Funkcje

Lista niektórych funkcji zarządzających pamięcią buforowa katalogów:

d_add - dodaje pozycje do struktury
d_delete - usuwa pozycje ze struktury
d_lookup - szuka pozycji o zadanej nazwie i nadkatalogu

6. Struktury

Opis niektórych struktur i ich ważniejszych pól używanych przez pamięć podręczną katalogów.

struct qstr { const unsigned char * name;/* nazwa */ unsigned int len;/* długość nazwy */ unsigned int hash; };

#define DNAME_INLINE_LEN 16 struct dentry { atomic_t d_count;/* liczba korzystających procesów */ ... struct inode * d_inode;/* i-węzeł katalogu */ struct dentry * d_parent;/* nadkatalog */ struct list_head d_hash;/* tablica mieszająca zwierająca katalog */ struct list_head d_lru;/* lista LRU pozycji aktualnie nieużywanych (d_count = 0) */ struct list_head d_child;/* lista podkatalogów nadkatalogu */ struct list_head d_subdirs;/* lista podkatalogów */ ... struct qstr d_name;/* nazwa */ struct dentry_operations *d_op;/* operacje na strukturze */ ... unsigned char d_iname[DNAME_INLINE_LEN];/* krótka nazwa */};