Katalog w UNIXie podobnie jak zwykly plik sklada sie z ciagu bajtow. Od zwyklego pliku rozni go, oprocz pola typu pliku zapisanego i-wezlie (i_mode), sposob zapisu informacji. W katalogu jest on scisle okreslony i stanowi ciag struktor o nastepujacej budowie(opisane w linux/fs/ext2/dir.c)
struct ext2_dir_entry{
_u32 inode /* numer i-wezla */
_u16 rec_len /* dlugosc pozycji katalogowej */
_u16 name_len /* dlugosc nazwy */
char name[EXT2_NAME_LEN] /* nazwa */
}
W przeciwienstwie do tego co pisze Bach rozmiar pozycji nie jest ustalony z gory. Kazda ma rozmiar okreslony przez dlugosc nazwy zaokroglona do 4n bajtow i wlasnie ta wielkosc jest wpisana w polu rec_len. Informacja o faktycznej dlugosci pozycji znajduje sie w polu name_len. Nazwa pliku jest ograniczona do 255 znakow (stala EXT2_NAME_LEN). W zaleznosci od ustawienia flagi NO_TRUNCATE nazwy dluzsze moga byc obcinane lub traktowane jako bledne.
Na poczatku kazdego katalogu znajduja sie pozycje o nazwach "." i ".." oznaczajace odpowiednio katalog biezacy i macierzysty. W katalogu bedacym korzeniem drzewa systemu plikow ww. pozycje maja numer i-wezla systemu plikow.
W katalogu moga znajdowac sie pozycje, ktore maja numer i-wezla rowny 0. Taka sytuacja powstaje w momencie usuwania pozycji z katalogu. Dodawanie pliku jest na zasadzie przeszukiwania liniowego do pierwszej struktory, w ktorej numer i-wezla jest rowny 0 i jest odpowiednio duzo miejsca. Jezeli nie zostanie ona znaleziona nowy plik dopisywany jest na koncu.
Z kazdym katalogiem, jak ze zwyklym plikiem, zwiazane sa prawa dostepu, jednak dla katalogu ich znaczenie jest nieco inne:
Wszystkie procesy maja potencjalna mozliwosc odczytu katalogu jako pliku, jednak zapisywac katalog moze tylko jadro, co gwarantuje poprawnosc danych.
Aby przyspieszyc dostep do pozycji katalogowych czesc z nich przechowywana jest w pamieci. Dlugosc nazwy takiej pozycji nie moze przekraczac jednak 15 znakow (stala DCACHE_NAME_LEN), gdyz zbytnio obciazyloby to pamiec. Wykorzystuje sie tu dwie struktury danych(opisane w linux/fs/dcache.c)
struct hash_list{
dir_cache_entry * next /* nastepny w kolejce haszujacej */
dir_cache_entry * prev /* poprzedni w kolejce haszujacej */
}
struct dir_cashe_entry {
hashlist * h
k_devt dc_dev /* numer urzadzenia */
unsigned long dir /*numer i-wezla katalogu, w ktorym znajduje sie pozycja */
unsigned long version /* wersja katalogu */
unsigned long inode /* numer i-wezla pozycji */
unsigned char name_len /* dlugosc nazwy */
unsigned char * name[DCACHE_NAME_LEN] /* nazwa */
dir_cashe_entry * lru_head /* wskaznik na kolejke lru w ktorej
znajduje sie pozycja */
dir_cache _entry * nextlru,
* prevlru /* wskazniki na poprzedni i nastepny
w kolejce lru */
}
Przy ich pomocy utworzono tablica jedniekierunkowych list cyklicznych
struct hash_list hash_table[DCACHE_HASH_QUEUES]
dpowiedzialna za implementacje kolejek mieszajacych (stala DCACHE_HASH_QUEUES wynosi 32)
Funkcja haszujaca zalerzy od :
i ma nastepujaca postac:
#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]
}
Do obslugi tej tablicy sluza nastepujace funkcje:
void remove_hash (struct dir_cache_entry * de)
usuwa de z tablicy haszujacej
void add_hash (struct dir_cache_entry * de,struct hash_list *hash)
dodaje de na poczatek listy hash
struct dir_cache_entry * find_entry (struct inode * dir,const char * name, int len, struct hash_list * hash)
znajduje w kolejce hash pozycje z katalogu dir nazwie name
( musza zgadzac sie numer urzadzenia ,wersja katalogu,numer
iwezla katalogu,dlugosc nazwy pozycji i nazwa pozycji).
Jezeli nie ma takiej pozycji to zwraca null.
Kazda z pozycji katalogowych znajdujach sie w tablicy haszujacej umieszczona jest ponadto na jednej z jednokierunkowych cyklicznych kolejek lru o ustalonej (po zanicjowaniu tych kolejek i tablicy mieszajacej, czyli wywolaniu funkcji cashe_init) dlugosci rownej 128 (stala DCACHE_SIZE)
Sa to kolejki :
dir _cashe_entry level1_cashe [DCASHE_SIZE]
dir_cashe_entry level2_cashe [DCASHE_SIZE]
Wskazniki dir_cashe_entry * level1_head, *level2_head wskazuja na pierwsze elementy w tych kolejkach.
Operacje na tych kolejkach wykonywane sa 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)
Jezeli element old_de znajduje sie juz w kolejce level2_cache ,
to przesuwa go na jej koniec wywolujac update_lru . W przeciwnym przypadku
usuwa z tablicy haszujacej pierwszy element z level2_cache (czyli wskazywany
przez level2_head ), kopiuje do niego dane (numer iwezla katalogu, nazwe
itp.) z old_de, wstawia go ponownie do tablicy haszujacej
i przesuwa wskaznik level2_head na nastepny w kolejce.Tak wiec nowa pozycja
znajdzie sie na koncu kolejki level2_head .
Poniewaz sa to kolejki o stalej dlugosci, wiec operacje remove_lru i add_lru zawsze nastepuja bezposrednio po sobie i w powyzszej kolejnosci .
Roznice pomiedzy level1 i level2 mozna zaobserwowac rozpatrujac dwie funkcje dcashe_lookup i dcashe_add .
Funkcja dcache_lookup
DEFINICJA: int dcache_lookup(struct inode * dir,const char * name,
int len,unsigned long *ino)
/* dir - i-wezel katalogu */
/* name,len - nazwa i dlugosc nazwy pozycji katalogowej
WYNIK:1 w przypadku sukcesu
0 w przypadku porazki
numer i-wezla na ino
{
if(dlugosc nazwy wieksza od DCACHE_NAME_LEN )
return(0);
znajdz odpowiednia kolejke mieszaja;
wywolaj find_entry, aby znalezc szukana pozycje w tablicy haszujacej;
if(nie ma szukanej pozycji w pamieci -find_entry zwrocilo null)
return(0);
przenies pozycje ktora zwrocilo find_entry na koniec kolejki level2_cache
-czyli wywolaj move_to_level2);
mc przypisz na ino numer i-wezla ze znalezionej pozycji;
zwroc 1;
}
Funkcja dcache_add
DEFINICJA:void dcache_add (structure inode *dir, const char * name ,
int len, unsigned long *ino )
/* dir - i-wezel katalogu
/* name,len,ino -nazwa, dlugosc nazwy ,numer i-wezla pozycji katalogowej
{
if(dlugosc nazwy wieksza od DCACHE_NAME_LEN)
wyjdz z funkcij;
znajdz odpowiednia kolejke haszujaca;
wywolaj find_entry,aby sprawdic czy dana pozycja jest w tablicy haszujacej
if(pozycja jest juz w tablicy haszujacej find_entry nie zwrocilo nulla)
{
wpisz do pozycji jako numer i-wezla wejsciowy numer;
przesun pozycje na koniec kolejki (tej w ktorej juz jest) wywolujac
update_lru;
return;
}
usun pierwszy element w kolejki level1-cache (wskazywany przez level1_head)
z tablicy haszujacej;
przypisz zmiennej pomocniczej de wskanik level1_head;
przesun wskaznik level1_head na nastepny w kolejce;
wpisz do elementu wskazywanego przez de dane dotyczace nowej pozycji(numer
iwezla katalogu, wersja katalogu ,nazwa pozycji itp.);
wstaw pozycje wskazywana przez de do kolejki haszujacej;
}
Widac wiec ,ze pozycja wstawiana do tablicy haszujacej umieszczana jest w level1_cache i dopiero wywolanie funkcji dcache_lookup, czyli odwolanie sie do tej pozycji, powoduje wstawienie jej kopi do level2_cache .
Warto zauwazyc, ze po wywolaniu ktorej kolwiek z powyzszch funkcji pozycja znajdzie sie na koncu odpowiedniej kolejki . Na poczatku kazdej z nich znajduja sie wiec elementy do ktorych odwolywano sie najdawniej i to one zostana usuniete jako pierwsze .
Przy dokladnym przyjzeniu sie funkcji dcache_lookup mozna znalezc instrukcje pozornie zbyteczna . Otoz po znalezieniu szukanej pozycji w tablicy haszujacej wpisuje sie do niej numer i-wezla, ktory juz powinien sie tam znajdowac . Wynika to z tad, ze ostatni parametr funkcji dcache_add -numer i-wezla moze byc rowny 0, co oznacza ze pozycja tak naprawde nie istnieje w danym katalogu . Jezeli uzytkowinik (po sprawdzeniu ze danej pozycjia nie istnieje) stwozy ja, to dzieki przechowywaniu pozycji z 0 jako numerem i-wezla , wstawienie jej do tablicy haszujacej wymagalo bedzie tylko wpisania numeru i-wezla .
Autor:Malgorzata Guziak