1. Cechy ogólne

Andrew S. Tannenbaum na początku lat 80. XX wieku zaprojektował i stworzył od zera system plików na potrzeby swojego systemu operacyjnego i nazwał go MINIX file system. System ten jest tak zaprojektowany, żeby uniknąć skomplikowanych struktur danych i funkcjonalności, które utrudnią proces nauki systemów operacyjnych, a jednocześnie działają. Gdy Linux Torwalds zaczynał prace nad Linuxem (1991) pracował na komputerze z Minixem i zaadoptował ten system plików. Wkrótce jednak okazało się to bardzo problematyczne, więc powstał extended file system, który jednak szybko został wyparty przez swoja drugą wersję, znaną jako ext2. Od tego momentu MFS jest używany niezwykle rzadko. Następcami systemu plików ext2 są ext3 i ext4. O systemie plików ext2 warto zapamiętać:

• Podczas tworzenia systemu administrator może wybrać optymalny rozmiar bloku (w zakresie od 1 KiB do 4 KiB), zależnie od spodziewanego średniego rozmiaru pliku.
• Podczas tworzenia systemu administrator może ustalić liczbę i-węzłów dla partycji określonego rozmiaru, zależnie od spodziewanej liczby plików.
• Bloki dyskowe są dzielone na grupy obejmujące sąsiadujące ze sobą ścieżki, dzięki czemu odczyt pliku położonego w ramach pojedynczej grupy wiąże się z krótkim czasem przesuwu głowicy.
• System plików alokuje wstępnie bloki dyskowe dla zwykłych plików, zatem gdy plik rośnie, są już dla niego zarezerwowane bloki w fizycznie spójnych obszarach, co zmniejsza fragmentację pliku.
• System wspiera dowiązania symboliczne (ang. symbolic link). Jeśli takie dowiązanie reprezentuje krótką nazwę ścieżkową (mniej niż 60 znaków), to umieszcza się go w i-węźle, dzięki czemu tłumaczenie nazwy nie wymaga czytania bloku danych.

Dzięki dobrej i przemyślanej implementacji ext2 jest stabilny i elastyczny. Podjęte decyzje projektowe minimalizują ryzyko błędu przy awarii systemu, np. przy tworzeniu dowiązań twardych (ang. hard link) najpierw jest zwiększany licznik dowiązań w i-węźle dyskowym, a dopiero później nowa nazwa jest dodawana do właściwego katalogu. System zapewnia wsparcie dla automatycznej kontroli spójności podczas ładowania.

Źródła systemu plików ext2 w naszym obrazie Minixa znajdują się w katalogu /usr/src/minix/fs/ext2. Natomiast źródła MFS są w katalogu /usr/src/minix/fs/mfs.

2. Modyfikowanie, kompilowanie i instalowanie

Po dokonaniu zmian w systemie plików nie trzeba kompilować całego jądra. Wystarczy wejść do katalogu z systemem plików, wykonać polecenie make, następnie zainstalować zmiany poleceniem make install i zrestartować Minixa.

3. Ćwiczenia

Aby szybciej zrozumieć, jak działa system plików, proponujemy przeprowadzenie tych zajęć w formie ćwiczeń. Podobne zadania pojawiają się co roku na pisemnym egzaminie licencjackim.

A. Systemowa tablica otwartych plików

Związek między procesem a systemem plików opisany jest przez dwa pola w strukturze danych procesu (task_struct):

• struct fs_struct *fs zawiera informacje o systemie plików,
• struct files_struct *files zawiera informacje o otwartych przez proces plikach.

W strukturze files_struct znajduje się tablica indeksowana liczbami naturalnymi, które odpowiadają deskryptorom otwartych plików. Wartościami poszczególnych pozycji w tej tablicy są dowiązania do systemowej tablicy otwartych plików. Każde zakończone powodzeniem wywołanie funkcji open() powoduje utworzenie nowej pozycji w systemowej tablicy otwartych plików. Natomiast wywołania funkcji dup() i fork() powoduje, że do jednej pozycji mogą odnosić się różne deskryptory. Pozycja w systemowej tablicy otwartych plików jest opisana przez strukturę file. Pole f_count tej struktury odpowiada liczbie dowiązań do danej pozycji.

I-węzeł pliku

I-węzeł każdego otwartego pliku znajduje się w pamięci operacyjnej. Dla każdego pliku jest tylko jedna kopia i-węzła w pamięci niezależnie od tego, ile razy dany plik był otwierany. Pole i_count w i-węźle informuje, ile razy dla danego pliku wykonano funkcję open(). Uwaga: przedstawiony tutaj opis jest oczywiście niepełny. Zawiera tylko wyrywkowe informacje pomocne przy wykonywaniu poniższych zadań.

fd = open(plik[0], ...);
for (int i = 1; i ≤ 5; ++i)
{
    if (!fork()) break;
    fd = open(plik[i], ...);
}

B. Struktura partycji w systemach plików ext2, ext3, ext4

W omawianych systemach plików pierwszy blok partycji jest zarezerwowany dla sektora startowego. Reszta partycji jest podzielona na grupy bloków tego samego rozmiaru o ustalonej strukturze. Liczba grup zależy od rozmiaru partycji i od wielkości bloku. Głównym ograniczeniem jest to, że mapa bitowa opisująca stan zajętości bloków wewnątrz grupy musi zmieścić się w jednym bloku.

Jak widać na rysunku, również mapa bitowa opisująca zajętość i-węzłów oraz superblok zajmują po jednym bloku. Pozostałe struktury są zmiennej długości.

Superblok zawiera informacje o całym systemie plików (m.in. rozmiar bloku, łączną liczbę bloków i i-węzłów, łączną liczbę wolnych bloków i i-węzłów). Deskryptor grupy przechowuje podstawowe informacje dotyczące grupy, takie jak liczbę wolnych bloków oraz i-węzłów w danej grupie, numery bloków map bitowych i numer pierwszego bloku tablicy i-węzłów.

Tablica i-węzłów to zbiór bloków, w ramach których przydzielane są i-węzły. Ich liczba jest ustalana podczas tworzenia systemu plików.

Różnice w strukturze partycji pomiędzy kolejnymi wersjami systemu plików od ext2 do ext4 są niewielkie. W oryginalnej wersji systemu ext2 kopia superbloku oraz deskryptory grup znajdowały się w każdej grupie (redundancja miała na celu zabezpieczenie danych przed awarią). W nowszych wersjach wprowadzono możliwość pominięcia kopii w niektórych grupach. Kopie superbloku i deskryptorów grup znajdują się wtedy w grupach o numerach 0, 1 oraz będących potęgą 3, 5 lub 7.

Zauważmy, że dla bardzo dużych partycji taki sposób organizacji staje się nieefektywny, ponieważ zbyt wiele miejsca jest przeznaczone na (redundantne) metadane. Chodzi tutaj przede wszystkim o deskryptory grup, których liczba rośnie wraz z rozmiarem partycji. Dlatego w późniejszych wersjach systemu (ext3 i ext4) wprowadzono tak zwane metagrupy. Metagrupa jest zbiorem grup, o tak dobranym rozmiarze, aby deskryptory grup w obrębie jednej metagrupy mieściły się w pojedynczym bloku dyskowym. Deskryptory grup danej metagrupy są przechowywane w jej pierwszej grupie i dodatkowo w drugiej i ostatniej.

C. Operacje na plikach

I-węzeł pliku w systemach ext2 i ext3 zawiera numery pierwszych 12 bloków z danymi oraz numery jednego bloku pośredniego, jednego bloku podwójnie pośredniego i jednego bloku potrójnie pośredniego (tablica i-block).

D. System plików ext4

Nasuwa się wniosek, że system plików ext3 dochodzi do granic swoich możliwości. Maksymalna wielkość partycji, czyli 16 TiB (ew. 32 TiB) jest już często przekraczana (np. w macierzach RAID), a ze względu na 32-bitowe numery bloków dyskowych więcej osiągnąć się nie da. Od 2006 roku trwały prace nad dwoma zasadniczymi zmianami, które pojawiły się w ext4, a także dostępnymi w ext3 w postaci łat.

Pierwsza i najważniejsza zmiana polega na zwiększeniu wielkości numeru bloku do 48 bitów, a druga – na zamianie mechanizmu pośredniego adresowania bloków na tzw. ekstenty (ang. extent), czyli ciągłe zbiory (zakresy) bloków danych.

struct ext4_extent {
    __le32  ee_block;       /* first logical block extent covers */
    __le16  ee_len;         /* number of blocks covered by extent */
    __le16  ee_start_hi;    /* high 16 bits of physical block */
    __le32  ee_start_lo;    /* low 32 bits of physical block */
};

Pojedynczy ekstent opisuje:

• 32-bitowy numer bloku logicznego pliku, będącego początkiem zakresu,
• 15-bitową długość zakresu (najstarszy bit służy do określenia, czy zestaw jest zapisany, czy nie),
• 48-bitowy numer bloku na dysku, będący początkiem zakresu na dysku.

W strukturze i-węzła tablica i-block, która w systemach ext2 i ext3 jest wykorzystywana do zapisywania numerów bloków, w ext4 służy do zapisania czterech ekstentów i jednego nagłówka ekstentu. W przypadku dużych plików system ext4 tworzy drzewo ekstentów. Dodatkowa struktura indeks ekstentu zawiera pozycję początkową ekstentu w pliku i numer bloku na dysku. Mechanizm ekstentów jest obecny także w innych popularnych systemach plików m.in. w XFS, JFS, Reiser4, a nawet w NTFS.