wstep





6.6.2 Katalogi w pamieci

Spis treści



Opis

Przyklad struktury danych

Bibliografia



KATALOGI W PAMIECI

W celu przyspieszenia dostępu do pozycji
katalogowych, cześć z nich jest przechowywana w pamięci. Pozycje które
są przechowywane, mają długość ograniczoną przez stałą DCACHE_NAME_LEN.
Ograniczenie to zostało wprowadzone w celu nie obciążania pamięci. Pozycje
katalogowe o nazwach dłuższych niż powyższa stała, nie są przechowywane
w pamięci.

Ogólnie rzecz ujmując w pamięci przechowywana jest tablica
mieszająca (hash_table) . Pozycjami tej tablicy są wskaźniki (struct hash_list)
do dwukierunkowych, cyklicznych list haszujących w których są przechowywane
informacje ( struct dir_cash_entry) o pozycjach katalogowych. Rozmiar
tej tablicy jest okreslony przez stałą DCACHE_HASH_QUEUES.

Funkcja mieszająca (hashfn) zależy od:
- numeru i-węzła katalogu
- długosci nazwy pozycji
- nazwy pozycji, oraz
- numeru urządzenia

Tablica haszująca odpowiada za szybki dostęp do elementu jesli tylko
jest on zapisany w pamięci.
Algorytm postępowania przy wyszukiwaniiu opisuje nam funkcja dcache_lookup(),
natomiast przy dodawaniu nowych pozycji funkcja dcache_add.

Na elementach list haszujących zbudowane są jednocześnie dwie
kolejki lru - level1_cache i level2_cache.

W level1 znajdują się elementy, nowo wstawiane do tablicy haszującej.
Natomiast w level2 znajdują się te elementy do których już się odwoływano
(przy pomocy funkcji dcache_lookup).
W pierwszej przechowujemy te elemety, które mogą nam się przydać, czyli
na przykład wpisane do pamięci podczas odczytywania pozycji katalogowych,
być może z niektórych z nich bedziemy korzystać, wtedy te "używane"
zostaną przeniesione do drugiej. Otrzymujemy dwupoziomowy mechanizm klasyfikacji
elementów, w którym ostatnio "używane" elementy zostaną usunięte
w ostatniej kolejnosci.

Wstawienie polega na: usunięciu z początku jednego elementu
, zapisaniu na jego miejscu nowego i przesunięciu wskaźnika( na głowę kolejki)
o jeden do przodu. W ten oto sposób otrzymujemy sytuację w której najdawniej
"używane" elementy są na początku kolejki (i są w pierwszej kolejności
usuwane).





Przykładowy schemat struktury
danych przechowującej pozycje katalogowe w pamięci





Legenda
hl - struct hash_list
dce - struct dir_cash_entry
Strzałka: - zielona - wskaźnik h w strukturze dce
- czerwona - przykładowa kolejka level1_cashe (zaznaczono
przebieg tylko w jedną
stronę, ale jest to kolejka dwukierunkowa)

- niebieska - przykładowa kolejka level2_cashe (uwaga
jak wyżej)

na czerwono i niebiesko zaznaczono te struktury dce, które są
pierwszymi elementami w kolejkach (odpowiednio: level1 i level2) i na te
wlasnie struktury wskazują zmienne (odpowiednio) level1_head i level2_head.


Na rysunku nie uwzględniono tablic wskaźników do elementów (kolejek level1
i level2).




Opis algorytmów dzialania
 

Struktury danych:


struct hash_list


struct dir_cashe_entry

Funkcje obsługujące tablicę:


remove_hash


add_hash


find_entry

Funkcje operujące na kolejkach:


remove_lru


add_lru


update_lru


move_to_level2

Funkcje do odwoływania się do pamięci:


dcache_lookup


dcache_add

Inne:


inicjuje kolejki lru1 i lru2 oraz tablicę haszującą name_cash_init



void remove_hash(struct
dr_cache_etry * de)
 {
usuwa element de z tablicy haszującej poprzez przesunięcie wskaźników
w poprzedzającym i następującym po de elementach
}    Powrót.
 


void add_hash(struct
dir_cache_entry * de, struct hash_list * hash)
{
dodaje element wskazywany przez de na początek listy(w tablicy haszującej)
wskazywanej przez hash
}    Powrót.
 


struct dir_cache_entry * find_entry(struct
inode * dir, const char * name, int len, struct hash_list * hash)
{
dla każdej pozycji z listy hash sprawdź
{
czy zgadza się numer urządzenia;
czy zgadza się i-węzeł katalogu macierzystego
czy zgadza się wersja ???
czy zgadza się nazwa
czy zgadza się długoć nazwy
}
jeżeli wszystko się zgadza zwróć wskaźnik na aktualny element;
}    Powrót.
 


void remove_lru(struct
dir_cache_entry * de)
{
usuwamy element wskazywany przez de z kolejki lru w której się znajduje,
poprzez przesunięcie wskaźników u sąsiadów;
}    Powrót.
 


void add_lru(struct
dir_cache_entry * de, struct dir_cache_entry *head)
{
wstawiamy element wskazywany przez de na koniec kolejki wskazywanej
przez head;
}    Powrót.
 


void update_lru(struct
dir_cache_entry * de)
{
jesli(element wskazywany przez de jest na początku kolejki)
{
przesuwamy wskażnik na głowę kolejki o jedną pozycję do przodu;
}
else
{
usuń element wskazywany przez de;
wstaw element wskazywany przez de, do kolejki wskazywanej przez de->lru_head;
}
}    Powrót.
 


void move_to_level2(struct
dir_cache_entry * old_de, struct hash_list * hash)
{
jesli( old_de jest w level2)
{
wywołaj update(old_de);
koniec;
}
przesuń wskaźnik na głowę kolejki o jeden do przodu;
usuń dotychczasowy pierwszy element z tablicy haszującej;  
(remove_hash(de))
skopiuj dane z old_de na miejsce poprzedniego pierwszego elementu (de);
wstaw de do hasz listy (hash) na jej poczatek (add_hash);

// w ten sposób otrzymalimy sytuację, w której element jest na końcu
kolejki level2, zas na początku odpowiedniej listy haszującej(co zapewne
przyspieszy dostęp do tego elementu)
}    Powrót.
 


int dcache_lookup(struct
inode * dir, const char * name, int len, unsigned long * ino)
//Daje w wyniku : 0 - porażka, czyli nie znaleziono
//                         
1 - znaleziono, i-węzeł na zmiennej ino
{
jeżeli(nazwa za długa, czyli większa od EXT2_NAME_LEN) to koniec i
zwróć zero;
znajdź odpowiednią listę haszujaca;
jeżeli(nie ma w niej naszego elementu - szukamy przy pomocy find_entry)
{
koniec i zwróć zero;
}
//a jednak jest
na ino wpisujemy numer i-węzła znalezionej pozycji;
przesuwamy na koniec drugiej kolejki (move_to_level2);
i zwracamy jedynkę
}    Powrót.
 


void dcache_add(struct
inode * dir, const char * name, int len, unsigned long ino)
{
jeżeli(za długa nazwa) to niestety koniec;
//wpp. sprawdzamy czy jest w pamięci
sprawdzamy w której liscie haszującej powinien być (algorytm hashfn);
jeżeli(jest tam -sprawdzamy czy tam jest (find_entry))
{
uaktualniamy i-węzeł;
przesuwamy go na koniec jego kolejki (update_lru);
i koniec;
}
//nie było go więc:
przesuwamy wskaźnik na głowę kolejki level1;
usuwamy pierwszego z level1;
i wstawiamy nasz element na koniec level1;
}


Bibliografia:



plik zrodlowy Linuxa: fs/dcache.c


Sporzadził: Tomasz Chudzik