Blog literacki, portal erotyczny - seks i humor nie z tej ziemi


Do spisu tresci tematu 5
5.3.1 I-wezly



Spis tresci

Wprowadzenie i EXT2
I-wezly na dysku
I-wezly w pamieci
Bibliografia





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:



SuperBlok
DekryptorySystemuPlikow
MapaZajetosciBlokow
MapaZajetosciI-wezlow
TablicaI-wezlow
BlokiDanych



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 :


logicznym numerze urzadzenia systemu plikow
indeksie w dyskowej tablicy i-wezlow
liczbie aktywnych wcielen pliku, czyli ile razy zostal otwarty(w tym stworzenie pliku)
wskaznikach na inne i-wezly. W pamieci fizycznie znajdowac sie moze tylko jedna kopia i-wezla,
natomiast moze sie ona znajdowac w tablicy mieszajacej i na liscie wolnych i-wezlow
wskaznik na super blok urzadzenia, do ktorego nalezy i-wezel
semafor (byc moze potrzebny w niektorych funkcjach)
struktury zawierajace wskazniki do funkcji operacyjnych,zaleznych od systemu plikow, do ktorego nalezy dany i-wezel,
stanie i-wezla, w tym:

czy ma on zalozona blokade
czy jakis proces czeka na zdjecie blokady (kolejka wait_queue)
czy kopia w pamieci rozni sie od informacji na dysku
czy plik jest plikiem zamontowania - tu wskaznik na i_mount

informacja o grupie, do ktorej nalezy i-wezel

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:

hash(kdev_t, int) - zwraca liste i-wezlow
insert_inode_hash(struct inode *) - wklada na poczatek odp. listy mieszajacej
remove_inode_hash(struct inode *) - usuwa z odp. listy mieszajacej

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:

insert_inode_free(struct inode *) - dolacza na poczatek listy
void remove_inode_free(struct inode *) - usuwa z listy
put_last_free(struct inode *) - podlacza na poczatek listy, przed
first_inode, ale nie przesuwa wskaznika first_inode. Tak jakby wstawia przed liste

W systemie istnieje takze globalna kolejka inode_wait, jest to kolejka
procesow czekajacych na wolny i-wezel w calym systemie.



Bibliografia



Pliki zrodlowe Linuxa:

/include/linux/fs.h
/include/linux/ext2_fs.h
/fs/inode.c
/fs/ext2/inode.c

Maurice J. Bach "Budowa systemu operacyjnego Unix"
- rozdzial 4
Linux Kernel Hackers Guide






Autor: Tomasz Lasica
  • zanotowane.pl
  • doc.pisz.pl
  • pdf.pisz.pl
  • qualintaka.pev.pl
  •