Do spisu tresci tematu 5

5.3.1 I-wezly




Spis tresci

Wprowadzenie i EXT2


System plikow EXT2 rozni sie znacznie od innych, uzywanych w starszych Unixach systemow plikow. Dopuszcza on np. fragmenty, a wiec zapis i odczyt nie calego, ale czesci bloku. Standardowo jednak rozmiar fragmentu jest rowny rozmiarowi bloku i wynosi 1024 bajty (max 4096). Inna nowoscia jest zastosowanie grup, ktore przyspieszaja dostep do i-wezlow i blokow dyskowych. Kazdy system plikow EXT2 sklada sie z grup, bedacych ciagami blokow uporzadkowanych jak w tabelce:

Super
Blok		 Dekryptory
Systemu
Plikow		 Mapa
Zajetosci
Blokow		 Mapa
Zajetosci
I-wezlow		 Tablica
I-wezlow		 Bloki
Danych

gdzie mapy zajetosci sa bitowymi mapami, przechowujacymi informacje o tym, ktore z blokow (i-wezlow) sa wolne - informacja ta jest wykorzystywana przy przydziale nowego bloku (i-wezla).

Nie jest wiec tak, jak opisuje to pan Bach, ale tak, jakby system plikow EXT2 skladal sie z wielu malych systemow plikow, funkcjonujacych razem, ale stanowiacych oddzielne calosci.

Maksymalny rozmiar pojedynczej grupy wynosi 128MB, ale zazwyczaj sa one mniejsze. Grupy nagrywane sa jedna za druga i (za wyjatkiem ostatniej) maja staly rozmiar. Pomimo tego, ze kazda grupa ma swoja kopie superbloku, wykorzystywany przy starcie i ladowany do pamieci jest superblok pierwszej grupy. Superbloki pozostalych grup moga byc uzyteczne w przypadku np. awarii systemu - pozwola odzyskac czesc danych.

Pliki sa reprezentowane w systemie plikow (fs) za pomoca i-wezlow (i-node), ktore zawieraja niezbedne dla systemu dane o pliku. Dane te dotycza takich rzeczy jak typ pliku, jego rozmiar, polozenie danych czy prawa dostepu. Chociaz plik moze miec wiele nazw (links), kazdemu plikowi (takze katalogowi) odpowiada dokladnie jeden i-wezel. Praktycznie przy kazdym korzystaniu z pliku uzywa sie jego i-wezla, nalezy przy tym odroznic operacje na pliku od operacji na i-wezle. Operacjami na pliku sa np. zmiany jego rozmiaru i zawartosci, natomiast zmiana praw dostepu jest juz operacja na i-wezle.

I-wezly na dysku


Informacja o plikach zawarta w i-wezlach jest przechowywana na dysku w postaci liniowej tablicy i-wezlow. W systemie EXT2 kazda grupa ma swoja tablice i-wezlow, znajdujaca sie w blokach dysku poprzedzajacych bloki danych. Ilosc blokow zarezerwowanych na te tablice ustala administrator w czasie instalacji systemu, a standardowo wynosi ona 3072(NR_INODE). Poczatkowe numery i-wezlow sa zarezerwowane, np. i-wezel o numerze 2 (EXT2_ROOT_INO) jest i-wezlem korzenia systemu plikow.

I-wezel na dysku reprezentowany jest przez strukture ext2_inode, ktora znajduje sie w pliku /include/linux/ext2_fs.h. Po obcieciu niektorych pol wyglada ona nastepujaco: 

struct ext2_inode{
    __u16	i_mode;		/* typ pliku -  zwykly, katalog, FIFO, specjalny..., 0 gdy wolny */
    __u16	i_uid;		/* identyfikator wlasciciela pliku */
    __u32	i_size;		/* rozmiar pliku w bajtach - ograniczenie do 4GB*/
    __u32	i_atime;	/* ostatni czas dostepu */
    __u32	i_ctime;	/* czas utworzenia */
    __u32	i_mtime;	/* czas ostatnich zmian */
    __u32	i_dtime;	/* czas skasowania */
    __u16	i_gid;		/* identyfikator grupy wlasciciela pliku */
    __u16	i_links_count;	/* ilosc dowiazan do pliku */
    __u32	i_blocks;	/* ilosc blokow dyskowych zajmowanych przez plik */
    __u32	i_flags;	/* m.in. prawa dostepu do pliku */
    ......
    __u32	i_block[EXT2_N_BLOCKS]; /* adresy blokow na reprezentacje pliku */
}

W i-wezle nie przechowuje sie nazw dowiazan do pliku !!!


I-wezly w pamieci


Aby przyspieszyc dostep do i-wezlow, pewna ich ilosc ich kopii jest przechowywana w pamieci, przy czym sa one trzymane w tablicy list mieszajacych oraz na liscie wolnych i-wezlow. Tablica ta w Linuxie 2.0 ma rozmiar wyznaczony przez stala NR_IHASH = 512. Wszystkie listy sa organizowane jako dwukierunkowe listy liniowe bez wartownikow. W zwiazku z taka organizacja informacji kopia i-wezla znajdujaca sie w pamieci glownej musi byc rozszerzona o pola informujace o : Pelna struktura kopii i-wezla przechowywanej w pamieci glownej jest zawarta w strukturze inode, ktora znajduje sie w pliku /include/linux/fs.h.

I-wezel jest jednoznacznie identyfikowany przez numer urzadzenia oraz indeks w tablicy i-wezlow na tym urzadzeniu (w EXT2 istotny jest takze numer grupy). W pamieci glownej moze znajdowac sie jedna i tylko jedna kopia i-wezla, stad mozliwosc zalozenia blokady na i-wezel oraz kolejka czekajacych na jej zdjecie - jako rozwiazanie problemu wzajemnego wykluczania. Stosuje sie przy tym metode zwalniania wszystkich czekajacych procesow przy zdjeciu blokady.

Celem tablicy mieszajacej jest przyspieszenie dostepu do i-wezlow. I-wezel znajduje sie w odpowiedniej liscie w tablicy mieszajacej, jezeli zawiera informacje z danego i-wezla na dysku tzn. jezeli jakis proces przedtem tego i-wezla uzywal. W liscie wolnych i-wezlow moze znalezc sie i-wezel, ktorego licznik wcielen (i_count) wynosi 0. Licznik ten jest zwiekszany przy otwieraniu a zmniejszany przy zamykaniu pliku. Zatem liste wolnych i-wezlow mozna traktowac jako pule nieaktywnych i-wezlow, ktore w razie potrzeby mozna przydzielic dowolnemu i-wezlowi na dysku. W Linuxie 2.0 znajduje sie tablica dwukierunkowych list liniowych 
static struct inode_hash_entry {
	struct inode * inode;
	int updating;
} hash_table[NR_IHASH];
odpowiedzialna za implementacje tablicy mieszajacej. Rozmiar tej tablicy (stala NR_IHASH) wynosi 512 w Linuxie 2.0, natomiast funkcja mieszajaca dana jest wzorem:
hash(dev,no)=(dev ^ no) % NR_IHASH
Na tablicy mieszajacej wykonywane sa nastepujace operacje:
UWAGA: Pole updating jest potrzebne, zeby nie mozna bylo skasowac i-wezla jezeli ktos na niego czeka (czeka na zdjecie blokady np.). Inaczej jest to licznik procesow mieszajacych w kolejce mieszajacej. Jest to zabezpieczenie dla spiacego na blokadzie procesu np. w iget(), zeby nikt juz nie zmienil mu niczego w i-wezle, na ktory wskaznik zostal juz pobrany.

Lista wolnych i-wezlow jest dwukierunkowa lista liniowa, ktorej poczatek jest trzymany na globalnej zmiennej first_inode. Na liscie tej wykonywane sa nastepujace operacje:
W systemie istnieje takze globalna kolejka inode_wait, jest to kolejka procesow czekajacych na wolny i-wezel w calym systemie.

Bibliografia


  1. Pliki zrodlowe Linuxa:
  2. Maurice J. Bach "Budowa systemu operacyjnego Unix" - rozdzial 4
  3. Linux Kernel Hackers Guide

    Autor: Tomasz Lasica