1. I-węzły Wprowadzenie.
Każdy plik w linuxie jest reprezentowany przez i-węzeł(ang. inode), który przechowuje informacje o tym pliku.Struktura i-wezla musi więc zawierać wszelkie dane takie jak prawa dostepu, data utworzenia, kto jest włacicielem itp.I-węzły znajdują się na dysku i gdy jakis proces chce skorzystać z pewnego pliku, wczytywany jest do pamięci(oczywiście jeśli jeszcze w pamięci go niema) odpowiedni i-węzeł.I-węzły w pamięci czasami muszą zawierać trochę więcej i nformacji od ich "rówieśników" na dysku. W strukturze i-węzła możemy wyróżnić pola:

unsigned long i_ino;

/* numer struktury i-węzła */

atomic_t i_count;

/* ilość odwołań do i-węzła */

kdev_t i_dev;

/* identyfikator urządzenia */

umode_t i_mode;

/* typ pliku i prawa dostępu */

nlink_t i_nlink;

/* liczba sztywnych dowiązań */

uid_t i_uid;

/* identyfikator właściciela */

gid_t i_gid;

/* identyfikator grupy */

kdev_t i_rdev;

/* identyfikator prawdziwego urządzenia */

loff_t i_size;

/* rozmiar pliku w bajtach(max 2^64) */

time_t i_atime;

/* czas ostatniego dostępu */

time_t i_mtime;

/* czas ostatniej modyfikacji */

time_t i_ctime;

/* czas utworzenia */

unsigned long i_blksize;

/* rozmiar bloku w bajtach */

unsigned long i_blocks;

/* liczba bloków pliku */

struct semaphore i_sem;

/* kontrola dostępu */

struct inode_operations *i_op;

/* odpowiednie operacje */ /* na strukturze i-węzła */

struct file_operations *i_fop; /* former ->i_op->default_file_ops */

/* operacje na plikach takie jak read, write, fsync, llseek itp. */

struct super_block *i_sb;

/* wskaźnik do obiektu superbloku */

wait_queue_head_t i_wait;

/* kolejka oczekiwania i-węzła */

struct file_lock *i_flock;

/* wskaźnik do listy blokad pliku */

struct address_space *i_mapping;

/* wskaźnik do rejonów pamięci odwzorowujących plik */

struct address_space i_data;

unsigned long i_dnotify_mask;

/* Directory notify events */

struct dnotify_struct *i_dnotify;

/* for directory notifications */

unsigned long i_state;

/* flaga statusu i-węzła */

unsigned int i_flags;

/*flaga montowania systemu plików */

unsigned char i_sock;

/* opisuje czy plik jest gniazdem */

unsigned int i_attr_flags;

/* flagi utworzenia pliku */

"unia"

/* która zawiera informacje o zamonotowanym systemie plików. Np. w przypadku systemu Ext2 w polu tym jest struktura ext2_inode_info */

Obiekty i-węzła przechowywane są na trzech dwukierunkowych listach :

Lista nie używanych i-węzłów.

Dostęp do tej listy jest przez zmienną inode_in_use, której pola next i prev wskazują odpowiednio na pierwszy i ostatni element listy.

Lista aktualnie używanych i-węzłów.

Na listę to wskazuję zmienna inode_in_use, której pola next i prev wskazują na pierwszy i ostatni element tej listy.

Lista "brudnych" i-węzłów.

Pole wskazujące na tą listę znajduje się w obiekcie odpowiedniego superbloku (*i_sb->s_dirty). Oczywiście (tak jak w wyżej wymienionych listach) dostęp do pierwszego i ostatniego elementu listy jest poprzez s_dirty->next i s_dirty->prev

Oprócz wyżej wymienionych list i-węzły mogą się znajdować w tablicy haszującej. Elementami tej tablicy są dwukierunkowe listy i-węzłów, które są na liscie "brudnych" i-węzłów lub używanych(inode_in_use) i-węzłów.Dostęp do tej tablicy jest przez zmienną inode_hashtable.Może się zdarzyć że i-węzeł jest na liście używanych lub "brudnych" i-węzłów, a nie ma go w tablicy haszującej(np. proces otwiera plik ; odłącza go, pole i_nlink może być wówczas równe zero; korzysta dalej z pliku mimo że i-węzeł został już usunięty z tablicy haszującej.

2. Algorytm iget.
Algorytmem pobrania i-węzła z pamięci zajmuje się funkcja iget(). Jest ona w rzeczywistości wywołaniem funkcji iget4() z dwoma ostatnimi parametrami ustawionymi na NULL (iget(sb, ino) == iget4(sb, ino, NULL, NULL). Parametrami funkcji iget4() są wskaźnik do superbloku z którego pochodzi i-węzeł, numer żądanego i-węzła, funkcja szukajaca i-wezla specyficzna dla okreslonego systemu plikow i parametry dla niej. Kod źródłowy tej funkcji znajduje się w pliku fs/inode.c .Funkcja zwraca przy niepowodzeniu NULL w przeciwnym przypadku zwraca wskaźnik do i-węzła.

struct inode *iget4(struct super_block *sb, unsigned long ino, find_inode_t find_actor, void *opaque)

Działanie funkcji.
Funkcja iget4() sprawdza najpierw czy poszukiwany i-węzeł nie został już wcześniej wczytany do pamięci.Gdy by tak było to ten i-węzeł byłby na odpowiedniej liście w tablicy haszującej(inode_hashtable).Wystarczy więc przejrzeć tą listę. Zajmuje się tym funkcja find_inode(), której parametrami są wskaźnik do macierzystego superbloku, numer i węzła, funkcja przeszukująca określony system plików i parametry do niej.W wywołaniu iget() dwa ostatnie parametry funkcji find_inode() ustawione są na NULL.

static struct inode * find_inode(struct super_block * sb, unsigned long ino, struct list_head *head, find_inode_t find_actor, void *opaque)

Powyższa funkcja przegląda listę 'head' i w gdy znajdzie odpowiedni i-węzeł zwraca do niego wskaźnik, w przeciwnym przypadku zwraca NULL.
Jeśli wywołanie funkcji find_inode() nie zwróciło NULL to zwiększamy licznik odwołań do i-węzła (pole i_count) i ewentualnie czekamy na odblokowanie znalezionego i-węzła przez wywołanie funkcji wait_on_inode(), po czym zwracamy uzyskany wcześniej wskaźnik do żądanego i-węzła.
Jeśli wywołanie funkcji find_inode zwróciło NULL to znaczy że musimy wczytać nasz i-węzeł z dysku. W tym celu wywołujemy funkcje get_new_inode() i zwracamy to co zwróci ta funkcja. Parametrami tej funkcji są wskaźnik do superbloku, numer i-węzła, lista i-węzłów wzięta z odpowiedniego miejsca w tablicy haszującej(patrz wyżej) oraz funkcja przeszukująca i parametry dla niej.

static struct inode * get_new_inode(struct super_block *sb, unsigned long ino, struct list_head *head, find_inode_t find_actor, void *opaque)

Funkcja ta przegląda listę 'head' wywołując find_inode(). Robi to dlatego że przed wywołaniem funkcji get_new_inode() lub napoczątku jej wykonywania odpowiedni i-węzeł mógł już zostać wczytany do pamięci przez inny proces. Gdy taki scenariusz miał miejsce zwiększamy licznik odwołań do znalezionego i-węzła(pole i_count) i ewentualnie czekamy na odblokowanie tego i-węzła.
Jeśli jednak nikt nas nie ubiegł i nie ma w tablicy haszującej żądanego i-węzła, to inicjujemy pola wcześniej zaalokowanego i-węzła( alokowanie odbywa się na samym początku funkcji get_new_inode() ).Następnie wczytujemy dane o i-węźle z dysku poprzez wywołanie charakterystycznej dla danego systemu plików funkcji (sb->s_op->read_inode2() lub sb->s_op->read_inode() - niedoskonałość VFS ).
Następnie budzone są procesy, które czekały na dany i-węzeł i funkcja zwraca wskaźnik do i-węzła.

3. Algorytm iput.
Funkcja iput() jest wykonywana przez VFS, wtedy gdy jakiś proces zakończy używanie danego i-węzła(np. zamknie plik).Parametrem tej funkcji jest wskaźnik do wyżej wymienionego i-węzła.

void iput(struct inode *inode)

Działanie funkcji.
Najpierw ,o ile jest zdefiniowana, wykonywana jest funkcja put_inode (inode->i_sb->s_op->put_inode(inode)) dla bloku specjalnego danego i-węzła (inode). Następnie blokujemy operacje na i-węzłach(by nie doprowadzić do niespójności danych) z jednoczesnym zmniejszeniem o 1 ilości odwołań do danego i-węzła.

Jeśli pole dowiązań(i_nlink) do i-węzła jest równe 0 to usuwamy i-węzeł z tablicy haszującej(inode_hashtable), z listy i-węzłów używanych , brudnych lub nieużywanych, jeśli się na którejś znajduje się. Następnie ustawiamy flagę(bit) pola i_state i-węzła na I_FREEING. Zdejmujemy ustawioną wcześniej blokadę i wywołujemy , funkcję delete_inode() dla bloku specjalnego danego i-węzła, o ile jest ona zdefiniowana.Jeśli nie jest wywołujemy clear_inode() (patrz niżej).
W przeciwnym przypadku ( tj. gdy i_nlink != 0)
    jeśli znajduje się w tablicy haszującej wtedy jeśli i-węzeł nie był brudny i zablokowany(ustawione bity I_DIRTY i I_LOCK pola i_state) to umieszczamy i-węzeł na liście i-węzłów nieużywanych i zwalniamy wcześniej założoną blokadę i kończymy funkcje iput().
    W przeciwnym przypadku usuń i-węzeł z listy, o ile na jakiejś się znajduje. Ustaw flage pola i_state na I_FREEING. Zwolnij wcześniej założoną blokadę i wywołaj funkcję clear_inode().
    koniec jeśli
koniec jeśli
Zwróć zajmowaną pamięc przez i-węzeł do systemu.
koniec funkcji iput()

Funkcja clear_inode()
Funkcja clear_inode() jest wywoływana wtedy gdy pewien i-węzeł(będący parametrem tej funkcji) jest już nie użyteczny.

void clear_inode(struct inode *inode)

Przebieg funkcji
Funkcja ta ewentualnie czeka na zwolnienie i-węzłą. Jeśli i-węzeł podlega kontroli przydziałów zasobów (IS_QUOTAINIT()) to uaktualniamy przydziały zasobów (DQUOTA_DROP()).
Wywołuje funkcje clear_inode(), o ile jest ona zdefiniowana, dla bloku specjalnego danego i-węzła ( i_sb->s_op->clear_inode() ). Czyści flagi(bity) pola i_state i-węzła (i_state = I_CLEAR).

4. Algorytm ialloc.
Algorytm ialloc służy do tworzenia nowego i-węzła dyskowego.Algorytmjest opisany na przykładzie implementacji systemu ext2.W linuksie 2.4.7 jest on zaimplementowany w pliku fs/ext2/ialloc.c w postaci funkcji ext2_new_inode(). Funkcja ta zwraca wskaźnik do nowo utworzonego i-węzła lub NULL w przypadku wystąpienia błędu.Pobiera ona dwa argumenty katalog do którego ma być wstawiony nowy i-węzeł oraz parametr określający rodzaj tworzonego i-węzła.

struct inode * ext2_new_inode (const struct inode * dir, int mode)

Działanie funkcji.
Najpierw wywoływana jest funkcja new_inode(), która alokuje nowy obiekt i-węzła i inicjuje pole i_sb i-węzła na adres superbloku dir->sb( parametr funkcji new_inode() ).
Następnie wywoływana jest funkcja lock_super() z jednym argumentem argumentem - wskaźnikiem do superbloku(dir->sb).Funkcja ta blokuje dostęp do tego superbloku innym procesom.
Jeśli nowy i-węzeł to katalog to przydzielamy mu takie miejsce by katalogi były jak najbardziej równomiernie rozłożone pomiędzy częściowo wypełnione grupy bloków.
W przeciwnym przypadku nowy i-węzeł nie jest katalogiem, szukana jest grupa bloków z wolnym i-węzłem.Grupa ta jest wybierana jak najbliżej katalogu nadrzędnego w następujący sposób:
Zaczynamy od grupy bloków w której znajduje się katalog nadrzędny(dir). algorytm przeszukuje log(B) grup bloków, gdzie B to całkowita liczba grup bloków (blok p, (p+1) mod B, (p+1+2) mod B, (p+1+2+4) mod B, ... ) - algorytm quadratic hash.
Gdy takie przeszukiwanie nie da rezultatów to wykonywane jest przeszukiwanie liniowe, które sprawdza każdą grupę bloków.
Następnie wywołujemy funkcje load_inode_bitmap() by pobrać mapę bitową wybranej wcześniej grupy bloków.Wyszukujemy w tej mapie pierwszy wolny bit, uzyskując w ten sposób numer pierwszego wolnego i-węzła dyskowego.
Odznaczamy bufor zawierający mapę bitową jako "brudną", co zpowoduje późniejszy zapis jej na dysk.
Wstawiamy obiekt i-węzła do tablicy haszującej i wywołujemy funkcję mark_inode_dirty(), która to umieszcza i-węzeł na liście i-węzłów "brudnych". Odblokowujemy dostęp do superbloku i zwracamy wskaźnik do nowego obiektu i-węzła.

5. Algorytm ifree.
Algorytm ifree służy do kasowania i-węzła dyskowego.Algorytm jest opisany na przykładzie implementacji systemu plików ext2, wktórym to występuje w postaci funkcji ext2_free_inode(). Jest ona zaimplementowana w pliku fs/ext2/ialloc.c. Parametrem tej funkcji jest wskaźnik do i-węzła , który chcemy skasować. System(jądro) wywołuje tą funkcje po wykonaniu operacji czyszczących na danym i-węźle tzn. gdy i-węzeł zostanie usunięty z tablicy haszującej i-węzła, zostaną usunięte wszelkie sztywne dowiązania w katalogach do tego i-węzła i gdy zostaną odzyskane wszystkie jego bloki danych(skrócenie pliku do rozmiaru 0).

void ext2_free_inode (struct inode * inode)

Działanie funkcji.
Wywołujemy najpierw funkcję lock_super(), by uzyskać wyłączny dostęp do obiektu superbloku danego i-węzła.
Wywołujemy funkcję clear_inode()(patrz funkcja iput()).
Wyliczamy indeks grupy bloków zawierającej i-węzeł dyskowy.
Pobieramy mapę bitową danego i-węzła (funkcja load_inode_bitmap() ).
Zwiększamy pole s_free_inodes_count superbloku i odznaczamy bufor w którym się znajduje jako brudny, a także ustawiamy pole s_dirty superbloku na 1.
Usuwamy odpowiedni bit z mapy bitowej i-węzłów i odznaczamy zawierający ją bufor na "brudny".
Odblokowujemy obiekt superbloku poprzez funkcję unlock_super().