Katalogi są plikami, które nadają systemowi plików strukturę hierarchiczną. Strukturę tę można wyobrazić sobie jako drzewo, którego zbiorem wierzchołków jest zbiór plików systemu. Wierzchołki, które nie są liśćmi, to właśnie katalogi. Hierarchia taka pozwala na przechowywanie danych w sposób bardziej "logiczny", wspiera systemy dla wielu użytkowników, itp.

Korzeń drzewa - główny katalog systemu plików - ma nazwę / (ukośnik). Użytkownik odwołuje się do plików systemu podając tzw. ścieżkę dostępu. Składa się ona z ciągu znaków zakończonego zerem. Występujące w tym ciągu ukośniki (/) dzielą ścieżkę na części, z których każda, z wyjątkiem ostatniej, musi być nazwą katalogu. Ścieżka rozpoczynająca się znakiem ukośnika określa drogę w drzewie hierarchii począwszy od korzenia, tzn. każda następna część musi być nazwą pliku, który jest pozycją (patrz dalej) katalogu o nazwie, która jest poprzednią częścią. Ścieżka nie rozpoczynająca się znakiem ukośnika prowadzi nie od korzenia systemu, a od katalogu bieżącego - z każdym procesem związany jest pewien wybrany katalog, który nazywa się katalogiem bieżącym (tego procesu).

Każdy katalog zawiera pliki kropka i kropka-kropka (. i ..), które odpowiadają odpowiednio katalogowi bieżącemu i macierzystemu. W katalogu będącym korzeniem drzewa systemu plikow odpowiednie pozycje mają numer i-węzła systemu plikow (patrz niżej).

Informacja w każdym katalogu (który - przypominam - jest plikem ) zapisana jest w postaci ciągu pozycji o następującej budowie:

struct ext2_dir_entry {

_u32 inode /* numer i-węzła */

_u16 rec_len /* długość pozycji katalogowej */

_u16 name_len /* długość nazwy */

char name[EXT2_NAME_LEN] /* nazwa */

}

Rozmiar pozycji katalogowej nie jest ustalony z góry. Każda ma rozmiar określony przez długość nazwy zaokrąglonej do długości 4n bajtów, która to wielkość jest wpisana w polu rec_len. Informacja o faktycznej długości nazwy pliku znajduje sie w polu name_len. Długość nazwy pliku jest ograniczona do 255 znaków (stała EXT2_NAME_LEN). W zależności od ustawienia flagi NO_TRUNCATE, nazwy dłuższe są obcinane lub traktowane jako błędne.

W katalogu mogą znajdować się pozycje, które mają numer i-węzła równy 0. Taka sytuacja powstaje w momencie usuwania pliku z katalogu. Dodawanie pozycji odbywa się przy pomocy liniowego przeszukiwania katalogu, aż do pierwszej struktury, w której numer i-węzła jest równy 0 oraz jej rozmiar jest wystarczający. Jeżeli takiej pozycji nie uda się znaleźć, to nowa pozycja zostaje dopisana na końcu katalogu.

Z każdym katalogiem, jak ze zwykłym plikiem, związane są prawa dostępu (zapisane w i-węźle), których znaczenie jest następujące:

• prawo czytania - pozwala odczytywac katalog, czyli wyświetlać jego zawartość
• prawo zapisu - pozwala tworzyć i usuwać pozycje katalogowe (funkcje systemowe creat, mknod, link, unlink)
• wykonywania - pozwala przeszukiwac katalog

Procesy mają możliwość odczytu katalogu jako pliku, jednak zapisywać katalog może tylko jądro, co gwarantuje integralność systemu plików.

Pierwszy dostęp procesu (użytkownika) do pliku odbywa się poprzez opisaną wyżej ścieżkę dostępu (lub inaczej: nazwę ścieżkową) - np. funkcje systemowe open, chdir, link. Ponieważ jądro posługuje się wewnętrznie numerami i-węzłów, nie nazwami ścieżkowymi, to należy każdą nazwę ścieżkową przekształcić w numer odpowiedniego i-węzła. Robi to algorytm namei. Z algorytmu tego korzystają następujące funkcje systemowe: open, stat, creat, link, chdir, unlink, chroot, mknod, chow, chmod, mount, umount.

Aby przyspieszyć dostęp do pozycji katalogowych, system plików wspiera ich cache'owanie, przechowując część pozycji w pamięci. Cache'uje się tylko nazwy nie przekraczające 15 znaków (stała DCACHE_NAME_LEN) zakładając, że takie są właśnie "normalne" nazwy i nie ma sensu zajmować się dłuższymi - szkoda pamięci. Wykorzystuje się tu dwie struktury danych: hash_list i dir_cache_entry, opisane niżej.

struct hash_list {

dir_cache_entry * next /* następny w kolejce mieszajacej */

dir_cache_entry * prev /* poprzedni w kolejce mieszajacej */

}

struct dir_cache_entry {

struct hashlist h

kdev_t dc_dev /* numer urządzenia */

unsigned long dir /*numer i-węzła katalogu, w którym znajduje sie pozycja */

unsigned long version /* wersja katalogu */

unsigned long ino /* numer i-węzła pozycji */

unsigned char name_len /* długość nazwy */

unsigned char * name[DCACHE_NAME_LEN] /* nazwa */

dir_cache_entry ** lru_head /* wskaźnik na kolejkę LRU z daną pozycją */

dir_cache _entry * nextlru /* wskaźnik na następny w kolejce LRU */

dir_cache_entry * prevlru /* wskaźnik na poprzedni w kolejce LRU */

}

Przy ich pomocy tworzy się tablicę jednokierunkowych list cyklicznych:

static struct hash_list hash_table[DCACHE_HASH_QUEUES]

odpowiedzialną za implementację kolejek mieszających (DCACHE_HASH_QUEUES jest stałą równą 32).

Klucz funkcji mieszającej zależy od:

• numeru urządzenia (dev)
• nazwy pozycji (name)
• długości nazwy (len)
• numeru i-węzła katalogu (dir)

i ma nastepującą postać:

#define hashfn (dev, dir, namehash) ((HASHDEV(dev)^(dir)^namehash)) % DCACHE_HASH_QUEUES

static inline unsigned long namehash (const char * name, int len) {

return len +((const unsigned char * )name)[0] -

((const unsigned char * )name)[len-1]

}

W obsłudze tej tablicy biorą udział nastepujące funkcje:

void remove_hash (struct dir_cache_entry * de)

- usuwa de z tablicy mieszającej

void add_hash (struct dir_cache_entry * de,struct hash_list *hash)

- dodaje de na początek listy hash

struct dir_cache_entry * find_entry (struct inode * dir,const char * name, int len, struct hash_list * hash)

- znajduje w kolejce hash pozycję z katalogu dir o nazwie name (muszą zgadzać się numer urządzenia, wersja katalogu, numer i-węzła katalogu, długość nazwy pozycji i nazwa pozycji); jeśli nie ma takiej pozycji, to zwraca null.

Każda z pozycji katalogowych znajdująch się w tablicy mieszającej, umieszczona jest ponadto na jednej z jednokierunkowych cyklicznych kolejek LRU o ustalonej (po zanicjowaniu tych kolejek i tablicy mieszajacej, czyli wywołaniu funkcji cache_init) długości, równej 128 (stala DCACHE_SIZE).

Są to kolejki:

dir_cache_entry level1_cache [DCACHE_SIZE]

dir_cache_entry level2_cache [DCACHE_SIZE]

Wskażniki dir_cache_entry * level1_head, *level2_head wskazują na pierwsze elementy w tych kolejkach.

Kolejki te obsługiwane są przez funkcje:

void remove_lru (struct dir_cache_entry * de)

- usuwa element wskazywany przez de z kolejki

void add_lru (struct dir_cache_entry * de, struct hash_list * hash)

- wstawia element de na koniec kolejki wskazywanej przez head

void update_lru (strust dir_cache_entry * de)

- przesuwa element wskazywany przez de na koniec kolejki

void move_to_level2 (struct dir_cache_entry *de, struct hash_list *hash)

- jeśli element old_de znajduje sie w kolejce level2_cache, to przesuwa go na jej koniec wywołując update_lru - w przeciwnym przypadku usuwa z tablicy mieszającej pierwszy element z level2_cache (czyli wskazywany przez level2_head), kopiuje do niego dane (numer i-węzła katalogu, nazwę, itd.) z old_de, wstawia go ponownie do tablicy mieszającej i przesuwa wskaźnik level2_head na następny w kolejce; tak więc nowa pozycja znajdzie się na końcu kolejki level2_head

Ponieważ są to kolejki o stałej długości, więc operacje remove_lru i add_lru zawsze następują bezpośrednio po sobie i w powyższej kolejności.

Różnice pomiędzy level1 i level2 można zaobserwować rozpatrując funkcje dcache_lookup i dcache_add.