Algoryytmy ialloc i ifree sluza do przypisania i-wezla plikowi przy jego tworzeniu oraz uaktualniaja dane w pamieci i w bloku identyfikacyjnym przy kasowaniu pliku.
Algorytm ialloc sluzy do przydzialu i-wezla dyskowego nowo tworzonemu plikowi. W Linuxie 2.0 jest on zaimplementowany w funkcji ext2_new_inode i znajduje sie w pliku fs/ext2/ialloc.c.
Sa dwa rodzaje postepowania aby zaalokowac i-wezel. Jesli i-wezel jest katalogiem to szukana jest grupa, która ma liczbe wolnych i-wezlow wieksza od sredniej dla wszystkich grup. I w tej grupie znajdowany jest wolny i-wezel. Jesli i-wezel nie jest katalogiem, to szuamy pierwszej znalezionej grupy, ktora ma wolne i-wezly. Szukanie wolnego i-wezla zaczynamy od grupy blokow, w ktorej umieszczony jest katalog do ktorego plik ma nalezec.
Uwaga !!! Niektore funkcje uzywane przez ponizszy algorytm opisane sa tu.
Implementacja algorytmu ialloc w funkcji ext2_new_inode.
DEFINICJA: struct inode* ext2_new_inode (const struct inode *dir, int
mode, int *err)
/* dir - wskaznik do i-wezla katalogu w ktorym ma byc umieszczony plik,*/
/* dla ktorego ma byc zaalokowany i-wezel */
/* mode - flaga opisujaca typ pliku np. czy katalog, lub plik specjalny
*/
/* err - wskaznik do zmiennej przekazujacej rodzaj bledu funkcji */
WYNIK: i-wezel ktory ma byc przypisany nowemu plikowi
{
if (lista i-wezlow na dysku jest pusta) return NULL;
else /* funkcja get_empty_inode */
pobierz nowy i-wezel i zaznacz, ze jest uzywany;
if (jest blokada na bloku identyfikacyjnym)
czekaj na odblokowanie super bloku;
zablokuj dla siebie super blok;
while (nie_zrobione)
{
if (mode=="katalog")
{
wylicz srednia liczbe wolnych i-wezlow na grupe;
znajdz grupe, w ktorej liczba wolnych i-wezlow jest
wieksza od wyliczonej sredniej
}
else szukaj grupy, w ktorej jest wolny i-wezel;
if (nie znalaziono grupy z wolnymi i-wezlami)
{
odblokuj super blok;
zwolnij i-wezel (algorytm iput);
return NULL;
}
znajdz w znalezionej grupie pierwszy wolny i-wezel;
zaznacz, ze dokonano zmian w systemie plikow;
if (i-wezel mimo wszystko nie jest wolny) /* czy to mozliwe
*/
continue; /* wroc na poczatek petli */
else nie_zrobione=0;
}
if (indeks znalezionego i-wezla jest poza ustalonymi granicami)
return NULL;<
zmiejsz w danej grupie liczbe wolnych i-wezlow;
if (mode=="katalog") zwieksz liczbe katalogow w grupie;
zaznacz, ze zmienila sie zawartosc grupy;
wypelnij inicjalnie i-wezel;
wstaw i-wezel na poczatek kolejki mieszajacej; /* insert_inode_hash
*/
zaznacz, ze zmienily sie dane w bloku identyfikacyjnym;
odblokuj super blok;
zwroc otrzymany i-wezel
}
W pierwszym punkcie algorytmu funkcja get_empty_inode zaznacza, ze i-wezel jest uzywany. Miedzy innymi ustawiony jest licznik i-wezla i_count na 1. Jest to konieczne dla poprawnosci dzialania algorytmu, gdyz jest mozliwosc wyscigu miedzy procesami (ang. race condition). Do takiego wyscigu moze dojsc, gdy kilka procesow zmienia wspolne struktury danych. Mogloby sie zdarzyc, ze proces dostanie (i zacznie modyfikowac) uzywany i-wezel.
Algorytm ifree sluzy do zwalniania i-wezla. O ile w algorytmie iput zwalnianie i-wezla jest w momencie, gdy proces nie potrzebuje tego i-wezla (chociaz byc moze ten i-wezel jest wykorzystany przez inny proces), to w algorytmie ifree jest to definitywne zwalnianie. Wywolywane moze byc tylko, gdy zaden proces nie korzysta z niego i nie jest juz dowiazany do zadnego pliku. W Linuxie 2.0 algorytm ifree jest zaimplementowany w funkcji ext2_free_inode w pliku fs/ext2/ialloc.c.
W przeciwienstwie do tego, co mozna przeczytac w ksiazce Bacha nie ma czegos takiego, ze algorytm uzaleznia swoje dzialanie od zalozonej blokady super bloku. Sam ja zaklada (ewentualnie musi czekac na swoja kolej). Zmienia wszystko co trzeba w super bloku i deskryptorze grupy. Nie ma wiadomosci, ktora moglaby sie pojawic w super bloku a nie pojawila sie. Na poczatku algorytm sprawdza, czy mozna zwolnic i-wezel. Powody dla ktorych nie mozna zwolnic to: brak i-wezla, brak urzadzenia, liczba dowiazan do i-wezla jest za duza.
Implementacja algorytmu ifree w funkcji ext2_free_inode.
DEFINICJA: void ext2_free_inode (struct inode * inode)
/* inode - wskaznik i-wezla, ktory chcemy zwolnic */
{
sprawdz, czy mozna zwolnic i-wezel, jesli nie to wyjdz;
zablokuj super blok;
wylicz do ktorej grupy nalezy i-wezel i na ktorym miejscu w grupie sie znajduje;
zaznacz w grupie, ze pojawil sie wolny i-wezel;
jesli i-wezel inode byl katalogiem zmniejsz liczbe katalogow;
zaznacz, ze grupa byla modyfikowana;
zwieksz liczbe wolnych i-wezlow w super bloku;
"wyczysc" i-wezel;
zaznacz, ze modyfikowano super blok;
odblokuj super blok
}
Do zaznaczenia, ze grupa i super blok byly modyfikowane uzywa sie funkcji mark_buffer_dirty. "Czyszczenie" i-wezla nastepuje przy wykonywaniu funkcji clear_inode. Po wyliczeniu numeru grupy korzystamy z funkcji get_group_desc. Troche wiecej o tych funkcjach mozna sie dowiedziec w nastepnym rozdziale.
Opis funkcji get_empty_inode oraz clear_inode mozna znalezc w rozdziale zwiazanym z algorytmami iget i iput. Takze o funkcji insert_inode_hash mozna sie troche dowiedziec przy okazji i-wezlow (zobacz tu), zatem nie bede tych trzech funkcji opisywac. Kilka slow o pozostalych funkcjach:
get_group_desc - Funkcja ta (zaimplementowana w pliku fs/ext2/ialloc.c Pobiera deskryptor grupy blokow o podanym numerze. Najpierw wyliczany jest numer grupy deskryptorow i numer kolejny w tej grupie. Nastepnie za pomoca pola s_group_desc w super bloku i wyliczonego numeru grupy deskryptorow znajdujemy deskryptor "grupy" deskryptorow. Teraz po dodaniu otrzymanej wartosci i numeru w grupie deskryptorow otrzymujemy wynik funkcji - deskryptor grupy blokow.
load_inode_bitmap- Funkcja ta (zaimplementowana w pliku fs/ext2/ialloc.c) laduje do pamieci mape bitowa i-wezlow w danej grupie blokow. Najpierw funkcja sprawdza, czy nie podalismy niewlasciwych parametrow. Nastepnie jest sprawdzane, czy ta mapa bitowa nie jest juz zaladowana. Jesli tak to funkcja konczy dzialanie. W przeciwnym razie za pomoca funkcji read_inode_bitmap i bread wczytuje do pamieci szukana mape bitowa.
find_first_zero_bit- Jest to funkcja napisana w asemblerze, ktora bardzo szybko znajduje w ciagu znakow pierwsze zero. (jak sama nazwa wskazuje)
mark_buffer_dirty - Zaznacza, ze bufor zostal zmodyfikowany (ustawia odpowiednia flage)