Lokalne systemy plików bez kroniki

(s5fs, ffs, minix, ext, xia, ext2)

Jakub Matusz

System plików s5fs

Wstęp

System plików s5fs (system plików Systemu V) wprowadzono w pierwotnych wersjach systemu UNIX. Ze względu na jego pionierski charakter oraz prostą budowę, zaczniemy naszą analizę właśnie od niego. Przy okazji będzie to dobre wprowadzenie do problematyki związanej z systemami plików.

Budowa partycji

System plików umieszcza się na pojedynczym dysku logicznym lub partycji. Każdy system plików jest samowystarczalny, zawiera własny katalog główny, podkatalogi, pliki oraz związane z nimi dane i metadane. Drzewo plików widoczne dla użytkownika stanowi połączenie zamontowanych systemów plików.

Na rysunku widać strukturę partycji w s5fs.

Na początku partycji znajduje się obszar rozruchowy, może on zawierać kod niezbędny do rozruchu systemu. Co najmniej jedna partycja musi zawierać tą informację, ale każda partycja ma obszar rozruchowy, choć może on być pusty.
Za obszarem rozruchowym znajduje się superblok, który zawiera atrybuty i metadane dotyczące systemu plików.
Za superblokiem znajduje się lista i-węzłów, która jest liniową tablicą i-węzłów (rozmiar tablicy jest stały co ogranicza liczbę plików). Dla każdego pliku istnieje jeden i-węzeł, każdy i-węzeł ma unikatowy numer i-węzła, który jest równy indeksowi i-węzła na liście i-węzłów. I-węzeł zajmuje 64 bajty, więc w jednym bloku dyskowym może zmieścić się wiele i-węzłów. Superblok oraz listy i-węzłów zaczynają się w tym samym miejscu względem początku partycji we wszystkich partycjach w systemie, dzięki temu numer i-węzła można łatwo przekształcić na numer bloku itd.
Dalej znajduje się przestrzeń danych - bloki z danymi plików i katalogów oraz bloki pośrednie.

Partycję można traktować jako liniową tablicę bloków. Rozmiar bloku dyskowego wynosi 512 bajtów pomnożone przez pewną potęgę 2. W zależności od wydania stosowano następujące rozmiary bloków 512, 1024 lub 2048 bajtów. Blok jest najmniejszą jednostką przydziału miejsca na dysku dla pliku oraz jednostką ziarnistości operacji wejścia-wyjścia. Fizyczny numer bloku jest indeksem w tablicy bloków. Podprogram obsługi dysku tłumaczy numer bloku na numer cylindra, ścieżki i sektora, a sposób tego tłumaczenia zależy od fizycznej charakterystyki dysku oraz od położenia partycji na dysku.

Katalog

Przykładowy katalog w s5fs.

Katalog w systemie plików s5fs jest plikiem specjalnym zawierającym listę plików i podkatalogów. Składa się z rekordów o stałym rozmiarze równym 16 bajtów. Pierwsze 2 bajty zawierają numer i-węzła, a następne 14 nazwę pliku. Taka budowa katalogu ogranicza liczbę plików w partycji do 65535 plików ( 0 nie jest poprawnym numerem i-węzła) oraz długości nazw plików do 14 znaków. Ponieważ katalog jest plikiem, ma także i-węzeł, który zawiera pole identyfikujące plik jako katalog. Jeśli numer i-węzła odpowiadający pozycji jest równy 0 to oznacza, że plik już nie istnieje. Katalog główny partycji oraz jego pozycja zawsze mają numer równy i-węzła 2.

I-węzły

I-węzeł zawiera związane z plikiem informacje administracyjne oraz metadane, umieszcza się go na dysku w liście i-węzłów. Tabela zawiera opis pól i-węzła dyskowego.

Struktura i-węzła dyskowego.

Pliki w systemie UNIX nie zajmują ciągłego obszaru na dysku, w miarę wzrostu rozmiaru pliku jądro przydziela mu nowe bloki w wygodnym miejscu na dysku, pozwala to łatwo zmniejszać i zwiększać rozmiar pliku nie fragmentując dysku, co byłoby konieczne podczas alokacji ciągłej. Jedynie ostatni blok pliku może zawierać przestrzeń niewykorzystaną. W każdym pliku marnuje się średnio przestrzeń o rozmiarze połowy bloku. System plików musi więc utrzymywać informacje o położeniu bloków każdego pliku. Informacje te przechowuje się w postaci adresów bloków fizycznych. Logiczny numer bloku jest indeksem w tej tablicy. Wielkość tablicy zależy od rozmiaru pliku. Dla dużych plików wymagało by to trzymania tablicy w kilku blokach dyskowych. Większość plików posiada jednak mały rozmiar, więc duże tablice powodowałyby duże straty miejsca. Ponadto przechowywanie tej tablicy w oddzielnych blokach powodowało by konieczność dodatkowych operacji odczytu przy każdym dostępie do pliku, a w konsekwencji malała by wydajność. Dlatego trzyma się małą listę w samym i-węźle, a dodatkowe bloki stosuje się w przypadku dużych plików. Jest to efektywne rozwiązanie do obsługi małych plików i wystarczająco elastyczne do obsługi bardzo dużych plików.

Tablica bloków pliku.

Tą strategię realizuje tablica di_addr - (39 bajtów - 13 elementów, każdy element - 3 bajtowy fizyczny numer bloku). Jeśli rozmiar bloku wynosi 1024 bajty, to taki schemat pozwala na zaadresowanie 10 bloków bezpośrednio, 256 za pośrednictwem bloku pośredniego 65536 (256x256) za pomocą podwójnie pośredniego, 16777216 (256X256X256) za pomocą bloku pośredniego 3 stopnia.

Dziury

Pliki unix'owe mogą zawierać tzw. dziury. Użytkownik może utworzyć plik, przesunąć go(lseek), ustawić wskaźnik pozycji w pliku na dużą wartość i tam zapisać dane. Przestrzeń bez danych między tą pozycją a początkiem pliku jest dziurą. Jeśli proces spróbuje odczytać tą przestrzeń stwierdzi, że znajdują się tam bajty NULL o wartości 0. Żeby nie marnować miejsca na dziury jądro wpisuje zera w odpowiednie miejsca tablicy di_addr lub bloku pośredniego. Przy próbie odczytu, jądro przekazuje w wyniku blok wypełniony zerami. Przestrzeń dyskowa jest przydzielana jedynie przy zapisie danych do bloku. Ma pewne to ważne konsekwencje. Proces może nagle stwierdzić brak miejsca na dysku podczas zapisywania danych do dziury, a po skopiowaniu pliku z dziurą nowy plik ma zamiast dziury strony wypełnione zerami, ponieważ kopiowanie polega na odczycie zawartości pliku i zapisie jej do nowego pliku. Gdy jądro kopiuje dziurę, tworzy strony wypełnione zerami, nie interpretując ich zawartości. Może to powodować problemy przy korzystaniu z programów do sporządzania kopii zapasowych i archiwizowania takich jak tar lub cpio, które operują na poziomie plików, a nie na poziomie surowego dysku. Administrator systemu może sporządzić kopię systemu plików, a następnie stwierdzić, że ten sam dysk jest za mały do odtworzenia archiwum.

Superblok

Superblok zawiera metadane dotyczące systemu plików, dla każdego systemu plików istnieje jeden superblok umieszczony na początku systemu plików na dysku. Jądro odczytuje superblok podczas montowania systemu plików i trzyma go w pamięci operacyjnej aż do chwili zdemontowania systemu plików.

Superblok przechowuje następujące informacje:

 rozmiar systemu plików w blokach

 rozmiar listy i-węzłów w blokach

 liczbę wolnych bloków oraz wolnych i-węzłów

 listę wolnych bloków i listę wolnych i-węzłów

Alokacja i-węzłów

Stosuje się algorytm przeszukiwania sekwencyjnego, zoptymalizowany przez częściową listę wolnych i-węzłów zawartą w superbloku.

 Alokujemy od początku listy (tu z prawej do lewej).

 Jeśli numer zwalnianego i-węzła jest mniejszy niż tego z końca listy, to dodajemy go na końcu listy, w przeciwnym wypadku nie robimy nic.

 Pustą listę uzupełniamy o wolne i-węzły zaczynając przeszukiwanie od następnego po ostatnio zaalokowanym. (pozwala na to poprzednia reguła)

Przykładowa sytuacja początkowa.

Alokujemy nr 43.

Alokujemy nr 44.

Zwracamy nr 43.

Zwracamy nr 44.

Alokujemy nr 45 .. 43.

Uzupełniamy listę.

Ze względu na rzadkość alokacji i-węzłów, kosztowna operacja uzupełniania listy jest do zniesienia.

Alokacja bloków

Nie ma możliwości sprawdzenia czy blok jest wolny, więc trzeba pamiętać całą listę wolnych bloków.

 Początek listy jest w superbloku.

 Ostatni element listy w danym bloku zawiera dalszą część listy.

 Alokujemy z początku listy.

 Zwracamy również na początek.

Przykładowa lista wolnych bloków. Alokujemy od nr 128 do nr 30.

Przy alokacji nr 30 musimy poprawić strukturę.

Zwracamy 49, ale superblok jest pełny.

Analiza

S5fs charakteryzuje się prostą budową powoduje to jednak problemy dotyczące niezawodności, wydajności i funkcjonalności.

Problemy z niezawodnością:

 1 superblok

Problemy z wydajnością:

 i-węzły na początku systemu plików, dane dalej

 i-węzły przydzielane losowo bez prób grupowania (np. pliki tego samego katalogu)

 przydział bloków na początku optymalny, potem losowy (spowolnienie operacji sekwencyjnych na pliku)

 trudno ustalić dobrą wielkość bloku, trzeba znaleźć inny sposób przydziału miejsca na pliki

Problemy z funkcjonalnością:

 14 znakowe nazwy plików

 maksymalnie 65535 i-węzłów

System plików ffs

Wstęp

FFS wprowadzony po raz pierwszy do 4.2 BSD ma lepszą wydajność, większą odporność na błędy i bogatszą funkcjonalność niż s5fs. Większość algorytmów wykorzystanych w funkcjach systemowych oraz struktur jądra pozostała w nim niezmieniona. Główne różnice dotyczą warstwy dyskowej, struktur umieszczanych na dysku oraz sposobu przydziału wolnych bloków.

Budowa dysku

Aby zrozumieć czynniki, które wpływają na wydajność operacji dyskowych, trzeba znać sposób składowania danych na dysku.

Schemat budowy dysku.

Rozmiar sektora wyznacza ziarnistość dyskowych operacji wejścia-wyjścia. UNIX traktuje dysk jako liniową tablicę bloków. Liczba sektorów w bloku jest małą potęgą 2. Dla wygody, możemy założyć, że jest dokładnie jeden sektor w bloku.
Po obliczeniu położenia żądanego bloku, podprogram obsługi dysku musi przesunąć głowicę do odpowiedniego cylindra. Ten czas przemieszczania głowicy jest główną składową czasu trwania dyskowej operacji wejścia-wyjścia.
Gdy głowica jest już na właściwej pozycji, trzeba poczekać aż w wyniku ruchu obrotowego dysku pod głowicą znajdzie się właściwy sektor. To opóźnienie nazywa się opóźnieniem obrotowym. Gdy właściwy sektor znajduje się już pod głowicą można rozpocząć przesyłanie.
Optymalizacja polega więc na zredukowania tych opóźnień, za pomocą sensownego rozmieszczenia bloków na dysku.

Organizacja danych na dysku

W ffs partycja dzieli się na jedną lub kilka grup cylindrów, z których każda jest małym zbiorem kolejnych cylindrów. Umożliwia to przechowywanie związanych ze sobą danych w tej samej grupie cylindrów, co ogranicza ruch głowic.
Superblok zawiera informacje o całym systemie plików, liczbę, rozmiar i położenie grup cylindrów, rozmiar bloku, łączną liczbę bloków oraz i-węzłów itd. Dane w superbloku nie zmieniają się chyba, że buduje się system plików od nowa.
Każda grupa cylindrów ma strukturę danych zawierającą informacje o tej grupie, listę wolnych i-węzłów oraz listę wolnych bloków.
Superblok znajduje się na początku partycji, za obszarem rozruchowym, ale ponieważ jego dane są niezbędne do poprawnego funkcjonowania systemu plików, należy je chronić przed błędami dyskowymi. Każda grupa cylindrów zawiera zatem kopię superbloku. System ffs utrzymuje te kopie pod różnymi przesunięciami w każdej grupie cylindrów w ten sposób, że żaden pojedynczy cylinder, ścieżka ani płyta nie zawiera wszystkich kopii superbloku. Przestrzeń między początkiem grupy cylindrów a początkiem superbloku jest wykorzystywana do przechowywania bloków z danymi. Wyjątkiem jest tylko pierwsza grupa cylindrów.

Bloki i fragmenty

Zwiększenie rozmiaru bloku poprawia wydajność, gdyż można wtedy przesyłać większą ilość danych w pojedynczych operacjach we-wy, powoduje to jednak większe straty miejsca. W ffs wykorzystano zalety obu rozwiązań i podzielono bloki na fragmenty.
Bloki jednej partycji muszą mieć ten sam rozmiar. Rozmiar bloku jest potęgą 2 i jest nie mniejszy niż 4096 bajtów, większość implementacji nakłada na rozmiar bloku górne ograniczenie równe 8192 bajty - to znacznie więcej niż 512 lub 1024 bajty w s5fs. Oprócz zwiększonej przepustowości umożliwia to adresowanie plików do 2 do 32 bajtów długości (4GB) za pomocą jedynie 2 poziomów pośrednich. W ffs nie ma bloku pośredniego 3 poziomu, chociaż niektóre warianty używają go do wspierania plików dłuższych niż 4GB.

Problem strat miejsca w małych (typowych dla Unix'a) plikach rozwiązano dzieląc każdego blok na kilka fragmentów. Rozmiar fragmentu ustala się podczas tworzenia systemu plików, a liczba fragmentów w bloku może być równa 1, 2, 4 , 8 z dolnym ograniczeniem równym 512 bajtów (jak typowy rozmiar ówczesnego sektora dysku). Ponieważ każdy fragment podlega przydzielaniu i adresowaniu, zamiast listy wolnych bloków - mapa bitowa z informacjami o stanie każdego fragmentu.

Plik w ffs składa się z całkowicie wypełnionych bloków dyskowych z wyjątkiem ostatniego bloku. Blok plikowy musi mieścić się całkowicie w jednym bloku dyskowym, nawet jeśli sąsiadujące bloki dyskowe zawierają wystarczająco dużo następujących bezpośrednio po sobie wolnych fragmentów do przechowania bloku plikowego, to jednak nie można ich łączyć. Co więcej jeśli ostatni blok pliku zawiera więcej niż jeden fragment, to fragmenty te muszą zajmować ciągły obszar w tym samym bloku. Przedstawiony schemat zmniejsza straty przestrzeni dyskowej, ale od czasu do czasu wymaga kopiowania danych plikowych. Rozważmy plik, którego ostatni blok zawiera pojedynczy fragment. Pozostałe fragmenty w tym bloku można przydzielić innym plikom. Jeśli ten plik zwiększy się o jeszcze jeden fragment , to trzeba znaleźć inny blok, w którym byłyby wolne dwa kolejne fragmenty. Pierwszy fragment należy skopiować z pierwotnej pozycji, a drugi wypełnić nowymi danymi.

Jeśli rozmiar pliku zwiększa się małymi porcjami, to jego fragmenty trzeba wielokrotnie kopiować, co powoduje spadek wydajności. W ffs kontroluje się to pozwalając, aby fragmenty znajdowały się jedynie w blokach bezpośrednich. Warto więc zapisywać całymi blokami.

Strategie alokacji

 Próbuj przydzielać i-węzły wszystkich plików z jednego katalogu w tej samej grupie cylindrów.
Wiele poleceń (ls -l) sięga do wszystkich i-węzłów plików z tego samego katalogu w bardzo krótkich odstępach czasu. Użytkownicy pracują też często w sposób wykazujący lokalność odwołań, korzystając z plików tego samego katalogu.

 Twórz każdy nowy katalog w grupie cylindrów innej niż grupa, w której umieszczono katalog macierzysty, tak aby równomiernie rozmieszczać dane na dysku. Podprogram przydziału miejsca na dysku wybiera nową grupę cylindrów z grup, w których wartość licznika wolnych i-węzłów przekracza wartość średnią, spośród nich wybiera następnie tą, w której jest najmniej katalogów.

 Próbuj umieszczać bloki z danymi pliku w tej samej grupie cylindrów, co jego i-węzeł, ponieważ często jest wymagany dostęp do i-węzła i do danych.

 Unikaj wypełnienia grupy cylindrów jednym dużym plikiem. Zmieniaj grupę cylindrów, kiedy rozmiar pliku osiągnie 48kB, a potem ponownie po każdym MB. Jeśli rozmiar bloku wynosi 4096 bajtów, to pozycje bezpośrednich bloków w i-węźle zajmują pierwsze 48kB. W ffs liczbę bezpośrednich bloków dyskowych zwiększono z 10 do 12, stąd wybór tej akurat wielkości. Wyboru nowej grupy cylindrów dokonuje się na podstawie wartości licznika jej wolnych bloków.

 Przydzielaj kolejne bloki pliku w miarę możliwości w pozycjach optymalnych względem obrotu dysku. Podczas sekwencyjnego odczytu pliku występuje pewne opóźnienie pomiędzy zakończeniem odczytu bloku a obsłużeniem przez jądro informacji o zakończeniu operacji we-wy i zapoczątkowaniem kolejnego odczytu. Ponieważ dysk obraca się cały ten czas, pod głowicą zdąży przesunąć się kilka sektorów. Optymalizacja obrotowa polega na określeniu liczby sektorów, które należy pominąć przy przydzielaniu miejsca na dysku, tak aby po zapoczątkowaniu kolejnego odczytu odpowiedni sektor znalazł się od razu pod głowicą. Liczba ta jest nazywana współczynnikiem opóźnienia obrotowego lub przeplotem dysku.

Implementacja dąży do kompromisu pomiędzy rozmieszczaniem danych w dogodnych miejscach oraz potrzebą ich równomiernego rozproszenia po całym dysku. Zbyt duża lokalność rozmieszczania powodowałaby upychanie danych w jednej grupie cylindrów, w tym przypadku można było by otrzymać jedną dużą grupę cylindrów, tak jak w systemie s5fs. Powyższe reguły przeciwdziałają takiemu scenariuszowi.

Ta implementacja jest bardzo wygodna, gdy na dysku jest dużo wolnego miejsca. Jej wydajność gwałtownie spada przy ok. 90 % zapełnienia dysku. Gdy wolnych bloków jest bardzo mało, to ich znalezienie w optymalnych miejscach staje się trudne. Z tego powodu system plików utrzymuje parametr określający rozmiar zarezerwowanego miejsca, zazwyczaj ustawiany na 10% pojemności dysku. Tylko nadzorca może otrzymywać miejsce z tej rezerwy.

Rozszerzenia funkcjonalne

Organizacja danych na dysku jest inna niż w s5fs, dlatego zmiana systemu plików z s5fs na ffs wymaga zrzutu zawartości wszystkich dysków, a następnie ich odtworzenia w nowym systemie plików. Ponieważ te systemy są i tak niezgodne, twórcy ffs wprowadzili także inne zmiany funkcjonalne niezgodne z systemem s5fs.

 W ffs zmieniono strukturę katalogu, tak aby umożliwić tworzenie nazw plików dłuższych niż 14 znaków. Pozycje w katalogu mają zmienną długość. Część stała wpisu składa się z numeru i-węzła, długości części zmiennej i długości nazwy pliku. Maksymalny rozmiar nazwy pliku wynosi obecnie 255 znaków, podczas usuwania pliku ffs łączy zwalniane miejsce z poprzednią pozycją. Katalog jest przydzielany porcjami wielkości 512 bajtów, żadna jego pozycja nie może rozciągać się na wiele porcji.

 Wprowadzono dowiązania symboliczne.

 Do wersji 4.2 BSD wprowadzono funkcję systemową rename, która niepodzielnie zmienia nazwy plików i katalogów. Poprzednio wymagało to wywołania link, a potem unlink.

 Wprowadzono też mechanizm ograniczania zasobów systemowych dostępnych dla konkretnego użytkownika (zarówno i-węzły jaki bloki dyskowe).

Niektóre z tych ulepszeń wprowadzono potem do s5fs.

Analiza porównawcza z s5fs

 Kilkakrotnie większa przepustowość operacji we-wy i stopień wykorzystania procesora.

 Straty dyskowe się równoważą bo fragment jak blok, łatwiej pamiętać duże bloki, ale trzeba pamiętać fragmenty. s5fs z blokami 1kb ~ ffs z blokami 4kB, fragmenty 512 B i rezerwa 5%.

 Zmieniła się geometria dysków (scsi) (zewnętrzne ścieżki mają więcej sektorów), więc optymalizacja rotacyjna może nawet przeszkadzać, ale grupowanie nadal jest zaletą.

 Wprowadzono dużo ulepszeń (np. podręczna pamięć buforowa)

Od Minixa do Ext2

Można powiedzieć, że Linux wyrósł na gruncie systemu Minix stworzonego przez Tanenbauma. Łatwiejszym wyjściem było współdzielenie dysków przez dwa systemy niż implementowanie nowego sytemu plików, stąd Torvalds zdecydował się na zaimplementowanie wsparcia dla systemu plików Minix'a.

Minix

Struktura partycji w minix fs.

Podstawowe właściwości systemu plików minix:

 Wiele rozwiązań zbudowanych na podstawie s5fs

 7 bloków bezpośrednich, brak bloku pośredniego 3 poziomu (razem 9)

 16 bitowe adresowanie bloków danych (ogranicza wielkość partycji do ok. 64MB)

 bloki 1kB

 nazwy do 14 znaków

 Zastosowanie bitmap, które można przechowywać w pamięci operacyjnej

 Zastosowanie stref (1, 2, 4, 8 bloków, domyślnie 1) i alokacja strefami (dla większych stref większych niż 1 można osiągnąć większy rozmiar partycji)

Ext, Xia, Ext2

Jak widać system plików Minix'a posiadał wiele niedogodności, więc zaczęto myśleć nad wprowadzeniem nowych systemów plików, w czym bardzo pomocne było wprowadzenie powłoki VFS.

Wkrótce po jej zintegrowaniu został dodany system plików Extended File System, który usuwał dwa duże ograniczenia Minix'a: jego maksymalny rozmiar wynosił 2GB, a pliki mogły mieć długość do 255 znaków. To była duża zmiana w stosunku do Minix'a, ale pewne kwestie pozostały nierozwiązane. Nie było wsparcia dla znaczników czasowych, system plików wykorzystywał listy bloków i i-węzłów, co powodowało słabą wydajność, w czasie używania listy stawały się nieposortowane, a system plików ulegał fragmentacji.

Odpowiedzią na te bolączki było wydanie dwóch nowych systemów plików: Xia i Ext2 (Second Extended File System). Xia w znacznej mierze bazowała na Minix'ie i dodała jedynie kilka nowych funkcjonalności. Uogólniając były to: wsparcie dla długich nazw plików, dla większych partycji i dla 3 znaczników czasowych. Ext2 natomiast bazował na kodzie systemu Ext, wprowadzając wiele reorganizacji i ulepszeń. Został stworzony pod kątem rozwoju i stwarzał do tego szerokie możliwości.

W momencie wprowadzenia dwóch nowych systemów plików oferowały one podobną jakość. Ze względu na swój minimalizm Xia okazała się jednak bardziej stabilna. Jednak po pewnym czasie losy się odwróciły i wraz z użytkowaniem systemu Ext2 jego błędy zostały poprawione, a stosowane w nim rozwiązania znacznie poszerzone i ulepszone. To doprowadziło do sytuacji, w której Ext2 stał się standardowym systemem plików Linux'a.

Poniższa tabela prezentuje porównanie kilku podstawowych cech wspomnianych systemów plików:

Kilka słów o ext2

Na budowę ext2 duży wpływ wywarł system ffs, stąd bardzo liczne podobieństwa. Warto wspomnieć, że podział na grupy cylindrów analogiczny do tego z systemu plików z BSD nie jest już sztywno związany z fizyczną strukturą dysku, gdyż jak wspomniałem nowoczesne dyski wykazują tendencję do zoptymalizowanego dostępu sekwencyjnego i nie ujawniają swojej fizycznej geometrii systemom operacyjnym.

Ze względu na wspomniane podobieństwo oraz fakt, że system ten został dokładnie omówiony na wykładzie i ćwiczeniach nie będę go tu szczegółowiej prezentował.

Bibliografia

U. Vahalia: "Jądro systemu UNIX"
M. Bach: "Budowa systemu operacyjnego UNIX"
A. Tanenbaum: "Operating Systems: Design And Implementation"
S. Pate: "UNIX Filesystems: Evolution, Design, and Implementation"

---