Urządzenia techniki komputerowej. 1
______________________________________________________________________
URZ
DZENIA TECHNIKI
KOMPUTEROWEJ
Systemy plików ext
2 Urządzenia techniki komputerowej.
______________________________________________________________________
I. Struktura systemu plików EXT2
Wstęp
System plików Ext2 na dysku składa się z wielu grup bloków dyskowych, przy
czym pojedynczy blok uwa\
amy za podstawową fizyczną jednostkę objętościową danych.
Wielkość bloku dyskowego jest stała w ramach całego systemu plików. Stałe ograniczające
rozmiar bloku dyskowego znajdują się w pliku nagłówkowym:
include/linux/ext2_fs.h
#define EXT2_MIN_BLOCK_SIZE 1024 /* bajtów */
#define EXT2_MAX_BLOCK_SIZE 4096 /* bajtów */
Fizycznie bloki na dysku poło\
one są w grupach. Struktura ta wygląda następująco.
Rys.1 Fizyczna struktura systemu plików na dysku.
Boot Bloki Bloki Bloki
Sektor Grupy 1 Grupy 2 . . . . . . . . . . Grupy N
W systemie EXT2 mo\
na jednak wyró\
nić logiczne grupy bloków, które nie zupełnie
pokrywają się z fizycznymi grupami.
Na logiczną grupę składają się:
Grupa bloków na poziomie logicznym
" deskryptor grupy (32 bajty)
" blok z mapą zajętości bloków danych (1 blok dyskowy)
" blok z mapą zajętości i-węzłów ( 1 blok dyskowy)
" bloki z tablicą i-węzłów
" bloki danych
Natomiast ka\
da grupa fizyczna zawiera informacje o jednej grupie logicznej, a ponadto
pewne informacje o całym systemie plików.
Rys.2 Fizyczna grupa bloków na dysku.
Blok z Blok z
Bloki
Bitmapą Bitmapą
Deskryptorów Tablica I- Bloki
Blok Zajętości Zajętości i-
Systemu węzłów Danych
Identyfikacyjny bloków węzłów
plików
danej Grupy danej Grupy
______________________________________________________________________
Urządzenia techniki komputerowej. 3
______________________________________________________________________
Grupa fizyczna zawiera blok z mapą zajętości bloków danych, blok z mapą zajętości
tablicy i-węzłów, bloki z tablicą i-węzłów, bloki danych - określonej grupy logicznej oraz
redundantną kopię bloku identyfikacyjnego (ang. super block, którego strukturę ext2-
super_block opisano w paragrafie dotyczącym struktur danych) i bloki z deskryptorami
wszystkich grup logicznych systemu plików. Przy czym kolejność występowania tych
bloków jest taka jak na rys. 2.
Podczas inicjalizowania systemu, do pamięci wczytywane są bloki z deskryptorami grup
logicznych z pierwszej grupy fizycznych bloków dyskowych, gdy nie występują sytuacje
wyjątkowe system nie korzysta z bloków z deskryptorami i z bloku identyfikacyjnego z
pozostałych grup fizycznych. Deskryptor grupy opisuje struktura ext2_grup_desc, która
zajmuje 32 bajty, co oznacza, \
e gdy blok dyskowy ma pojemność 1024 bajty to jeden blok
zawiera 32 deskryptory grup logicznych.
Podzielenie systemu plików na grupy bloków ma na celu zwiększenie
bezpieczeństwa oraz optymalizację zapisu danych na dysku. Zwiększenie bezpieczeństwa
jest uzyskane poprzez utrzymywanie redundantnych informacji o systemie plików (blok
informacyjny oraz deskryptory grup) w ka\
dej fizycznej grupie bloków. Optymalizacja
zapisu danych jest uzyskiwana poprzez algorytmy przydziału nowych i-węzłów i bloków
dyskowych. Podczas przydziału i-węzeła plikowi, który jest katalogiem wyszukiwana jest
grupa z największą liczbą wolnych i-węzłów. Je\
eli nie jest to katalog to zaczyna się szukać
wolnego i-węzła od grupy w której znajduję się i-węzeł katalogu tego pliku. Dzięki czemu
zwiększa się prawdopodobieństwo, \
e i-węzły plików z danego katalogu le\
ą w tej samej
grupie a przez to, co się zaraz oka\
e równie\
i prawdopodobieństwo poło\
enia bloków
danych plików z danego katalogu w jednej grupie bloków.
Wyszukiwanie wolnego bloku dyskowego zaczyna się od grupy w której znajduję się i-
węzeł pliku, przez co z du\
ym prawdopodobieństwem bloki danych jednego pliku poło\
one
są w obrębie jednej grupy bloków dyskowych. Algorytmy przydziału i-węzłów i bloków
danych powodują więc ich równomierne rozło\
enie w grupach oraz w miarę mo\
liwości
spójne poło\
enie bloków danych plików.
Przydział i-węzła nowemu plikowi
Przydziałem i-węzła tworzonemu plikowi (w file systemie ext2) zajmuje się funkcja
ext2_new_inode, znajdująca się w pliku fs/ext2/ialloc.c.
Deklaracja funkcji:
struct inode * ext2_new_inode (const struct inode * dir, int mode, int * err)
dir - wskaz
nik do i-węzła katalogu w którym ma być umieszczony plik
mode - flaga opisująca typ pliku (katalogu czy inny)
err - wskaz
nik do zmiennej przekazującej rodzaj błędu funkcji
4 Urządzenia techniki komputerowej.
______________________________________________________________________
Algorytm przydziału i-węzla zale\
y od tego czy przydzielamy i-węzeł katalogowi
czy plikowi innego typu. Jeśli plik jest katalogiem to przydzielany jest mu i-węzeł z grupy
bloków, w której znajduje się najwięcej wolnych i-węzłów. Wymaga to przeszukania
wszystkich deskryptorów grup,w których znajdują się liczniki wolnych i-węzłów. Nie jest
to kosztowne, bowiem tworzenie nowego pliku nie jest czynnością powtarzaną z du\
ą
częstotliwością w systemie, a ponadto wszystkie deskryptory grup wczytywane są do
pamięci w momencie ładowania systemu i pozostają tam stale do końca działania
systemu.(jest ich od kilkudziesięciu do kilkuset).
Je\
eli plik nie jest katalogiem, to szukanie wolnego i-węzła zaczynamy od grupy, w której
znajduje się katalog tworzonego pliku. Powoduje to, \
e z większym prawdopodopieństwem
pliki le\
ące w tym samym katalogu będą znajdować się w tej samej grupie bloków. Je\
eli w
grupie katalogu nie istnieją wolne i-węzły, to przeszukiwanie grup odbywa się przy pomocy
algorytmu nazwanego quadratic hash (patrz skomentowany kod fukncji ext2_new_inode()).
Gdy nie da to rezultatu następuje liniowe przeszukiwanie wszystkich grup po kolei w celu
znalezienia grupy z wolnymi i-węzłami.
Po wybraniu grupy bloków, pozostaje wyszukać wolny i-węzeł w grupie i
przydzielić go utworzonemu plikowi. Informacja, który i-węzeł w grupie bloków jest
wolny, a który zajęty przechowywana jest w mapach bitowych. W odró\
nieniu od
deskryptorów grup mapy bitowe zajętości i-węzłów nie są wszystkie przechowywane w
pamięci.W pliku include/linux/ext2_fs_sb.h zadeklarowana jest stała
EXT2_MAX_GROUP_LOADED, która określa maksymalną ilość załadowanych bitmap w
pamięci i jej wartość wynosi 8. Zatem widać \
e tylko niewielka część bitmap mo\
e się
znalez
ć jednocześnie w pamięci. Gdy liczba grup przewy\
sza tę stała (przypadek
najczęstszy), wówczas stosowany jest algorytm LRU do wymiany bitmap w
pamięci(funkcja load_inode_bitmap()). Po znalezieniu i-węzła bufory zawierające
deskryptor grupy i mapę bitową są zaznaczne jako "dirty" w celu ich póz
niejszego zapisu
na dysk, a wskaz
nik do wybranego i-węzła jest zwracany jako wartość funkcji.
II. Opis ogólny katalogów w systemie EXT2
Katalogi są plikami, które nadają systemowi plików strukturę hierarchiczną. Strukturę tę
mo\
na wyobrazić sobie jako drzewo, którego zbiorem wierzchołków jest zbiór plików
systemu. Wierzchołki, które nie są liśćmi, to właśnie katalogi. Hierarchia taka pozwala na
przechowywanie danych w sposób bardziej "logiczny", wspiera systemy dla wielu
u\
ytkowników, itp.
Korzeń drzewa - główny katalog systemu plików - ma nazwę / (ukośnik). U\
ytkownik
odwołuje się do plików systemu podając tzw. ście\
kę dostępu. Składa się ona z ciągu
znaków zakończonego zerem. Występujące w tym ciągu ukośniki (/) dzielą ście\
kę na
części, z których ka\
da, z wyjątkiem ostatniej, musi być nazwą katalogu. Ście\
ka
rozpoczynająca się znakiem ukośnika określa drogę w drzewie hierarchii począwszy od
korzenia, tzn. ka\
da następna część musi być nazwą pliku, który jest pozycją (patrz dalej)
katalogu o nazwie, która jest poprzednią częścią.
______________________________________________________________________
Urządzenia techniki komputerowej. 5
______________________________________________________________________
Ście\
ka nie rozpoczynająca się znakiem ukośnika prowadzi nie od korzenia systemu, a
od katalogu bie\
ącego - z ka\
dym procesem związany jest pewien wybrany katalog, który
nazywa się katalogiem bie\
ącym (tego procesu).
Ka\
dy katalog zawiera pliki kropka i kropka-kropka (. i ..), które odpowiadają
odpowiednio katalogowi bie\
ącemu i macierzystemu. W katalogu będącym korzeniem
drzewa systemu plikow odpowiednie pozycje mają numer i-węzła systemu plikow (patrz
ni\
ej).
Informacja w ka\
dym katalogu (który - przypominam - jest plikem ) zapisana jest w
postaci ciągu pozycji o następującej budowie:
struct ext2_dir_entry {
_u32 inode /* numer i-węzła */
_u16 rec_len /* długość pozycji katalogowej */
_u16 name_len /* długość nazwy */
char name[EXT2_NAME_LEN] /* nazwa */
}
Rozmiar pozycji katalogowej nie jest ustalony z góry. Ka\
da ma rozmiar określony
przez długość nazwy zaokrąglonej do długości 4n bajtów, która to wielkość jest wpisana w
polu rec_len. Informacja o faktycznej długości nazwy pliku znajduje sie w polu name_len.
Długość nazwy pliku jest ograniczona do 255 znaków (stała EXT2_NAME_LEN). W
zale\
ności od ustawienia flagi NO_TRUNCATE, nazwy dłu\
sze są obcinane lub traktowane
jako błędne.
W katalogu mogą znajdować się pozycje, które mają numer i-węzła równy 0. Taka
sytuacja powstaje w momencie usuwania pliku z katalogu. Dodawanie pozycji odbywa się
przy pomocy liniowego przeszukiwania katalogu, a\
do pierwszej struktury, w której numer
i-węzła jest równy 0 oraz jej rozmiar jest wystarczający. Je\
eli takiej pozycji nie uda się
znalez
ć, to nowa pozycja zostaje dopisana na końcu katalogu.
Z ka\
dym katalogiem, jak ze zwykłym plikiem, związane są prawa dostępu (zapisane w
i-węz
le), których znaczenie jest następujące:
" prawo czytania - pozwala odczytywac katalog, czyli wyświetlać jego zawartość
" prawo zapisu - pozwala tworzyć i usuwać pozycje katalogowe (funkcje systemowe
creat, mknod, link, unlink)
" wykonywania - pozwala przeszukiwac katalog
Procesy mają mo\
liwość odczytu katalogu jako pliku, jednak zapisywać katalog mo\
e
tylko jądro, co gwarantuje integralność systemu plików.
6 Urządzenia techniki komputerowej.
______________________________________________________________________
Pierwszy dostęp procesu (u\
ytkownika) do pliku odbywa się poprzez opisaną wy\
ej
ście\
kę dostępu (lub inaczej: nazwę ście\
kową) - np. funkcje systemowe open, chdir, link.
Poniewa\
jądro posługuje się wewnętrznie numerami i-węzłów, nie nazwami ście\
kowymi,
to nale\
y ka\
dą nazwę ście\
kową przekształcić w numer odpowiedniego i-węzła. Robi to
algorytm namei. Z algorytmu tego korzystają następujące funkcje systemowe: open, stat,
creat, link, chdir, unlink, chroot, mknod, chow, chmod, mount, umount.
III. Struktura systemu plików EXT3
Ext3 (ang. third extended filesystem) to nowoczesny system plików oparty na systemie
ext2. Jest to domyślny system plików w większości dystrybucji systemu GNU/Linux
opartych na jądrze 2.4 oraz nowszych.
System plików ext3 jest rozszerzeniem ext2 i ró\
ni się od niego dodanym
mechanizmem księgowania  dokładnego zapisu zmian na dysku, który w razie awarii
systemu umo\
liwia szybsze przywrócenie spójności systemu plików ni\
w przypadku ext2.
Poza mechanizmem księgowania system plików ext3 ró\
ni się od ext2 brakiem mo\
liwości
odzyskania skasowanych plików.
W odró\
nieniu od większości innych systemów z księgowaniem system ext3 daje do
wyboru trzy tryby księgowania:
w trybie najbezpieczniejszym księgowane są zarówno metadane jak i zwykłe dane;
w trybie domyślnym księgowane są tylko metadane;
istnieje jeszcze jeden tryb, w którym księgowane są równie\
tylko metadane, ale jest mniej
bezpieczny, bo pozwala na modyfikacje danych objętych metadanymi nie zapisanymi
jeszcze na dysk.
System plików ext2 mo\
e być w prosty sposób przekształcony do systemu ext3 i
odwrotnie. Konwersja systemu plików z ext2 do ext3 polega na dodaniu pliku dziennika. Z
tego względu nie jest konieczne tworzenie kopii zapasowej konwertowanych partycji i
konwersję w obie strony mo\
na przeprowadzić bezpośrednio po prawidłowym
odmontowaniu systemu plików.
System plików ext3 jest w pełni kompatybilny wstecz. Mogą z niego korzystać
programy napisane dla ext2 (np. program rozruchowy GRUB).
Ze względu na sposób działania, w systemie ext3 nie jest mo\
liwe odzyskanie skasowanych
plików (w przeciwieństwie do ext2).
______________________________________________________________________