Do spisu treści

6.3.4 Przydział bloków dyskowych



Spis treści

W systemie Linux operacja alokacji bloków dyskowych realizowana jest przez funkcję systemową ext2_new_block, której definicja znajduje się w pliku "balloc.c". Nagłówek tej funkcji przedstawia się nastepująco: 

int ext2_new_block (const struct inode *inode, unsigned long goal,
       u32 *prealloc_count, u32 *prealloc_block, int err);
Parametr inode wskazuje na i-węzeł, dla którego przydzielamy blok, zaś parametr goal podaje numer bloku, który chcielibyśmy zaalokować. Jeżeli nie będzie możliwa alokacja bloku o tym numerze, funkcja ext2_new_block spróbuje przydzielić jakikolwiek inny wolny blok.

Oto szczegółowy scenariusz działania:

Najpierw procedura pobiera z podanego parametru inode wskaźnik do struktury opisującej super-blok bieżącej grupy (tzn. grupy, do której należy podany i-węzeł) i blokuje ten super-blok. To blokowanie zapewnia, że żadne dwa procesy nie będą jednocześnie próbować alokować bloków w tym filesystemie. Jest to konieczne, ponieważ przydzielanie bloków wymaga modyfikacji struktur dyskowych i ich odwzorowania w pamięci (w buforach). W szczególności często modyfikowany jest sam super-blok.
W każdym filesystemie pewna liczba wolnych bloków zarezerwowana jest dla administratora systemu. Gdyby nie było tego ograniczenia, łatwo byłoby zablokować system i jedynym ratunkiem byłoby zakończenie wszystkich zadań. Dlatego jeżeli liczba wolnych bloków filesystemu zapisana super-bloku jest mniejsza niż to minimum zarezerwowane dla administratora systemu, użytkownik wywołujący procedurę nie jest administratorem systemu ani nie ma odpowiednich uprawnień, to wykonanie procedury kończy się z kodem błędu. W przeciwnym przypadku przechodzimy do pierwszej fazy działania, w której próbuje się znaleźć wolny blok w filesystemie.
Bloku zawsze próbujemy szukać najpier w bieżącej grupie, dopiero potem szukamy w pozostałych. Poza tym, ponieważ sytuacja, w której struktury opisujące stan filesystemu dość rzadko tracą integralność, testowanie, czy jakaś grupa ma wolne bloki rozpoczyna się zawsze od sprawdzenia licznika wolnych bloków tej grupy. Można założyć, że jego wartość prawie zawsze będzie zgodna z tym, co zawiera bitmapa.
Pobierany jest zatem deskryptor bieżącej grupy. Jeżeli licznik wolnych bloków jest większy niz zero, to załadowana zostaje bitmapa zajętości bloków tej grupy i sprawdzane jest, czy zadany blok jest wolny. Jeśli jest, zostaje przydzielony, a jeśli nie, próbuje się przydzielić jeden z następujących po nim kilkunastu bloków, testując odpowiednie bity w bitmapie zajętości. Liczba sprawdzanych tutaj bloków jest w zasadzie pseudolosowa, ale ograniczona przez ilość bloków w grupie. Szukanie nowego bloku do przydzielenia w pierwszej kolejności w najbliższym sąsiedztwie podanego bloku ma zasadniczy sens dla prędkości działania systemu plików. Właśnie temu, że podobne przypadki szczególne uwzględniane są w algorytmie przydziału bloków, system plików ext2 zawdzięcza wyjątkowo niski współczynnik fragmentacji plików. Bloki danego pliku są prawie zawsze położone blisko siebie i wczytywanie pliku jest szybkie.
Jeżeli nie udało się znaleźć wolnego bloku w najbliższym sąsiedztwie, to najpierw przeszukujemy pozostałą, nie sprawdzoną dotąd część bieżącej grupy. Mimo wszystko lepiej, aby blok był w tej samej grupie, nawet, jeżeli do wolnego bloku w innej grupie byłoby bliżej. Dzięki temu zwiększa się prawdopodobieństwo, że wszystkie bloki pliku będą w tej samej grupie lub przynajmniej w maksymalnie kilku, najlepiej sąsiadujących, dzięki temu dane plików o i-węzłach z różnych grup są dodatkowo separowane od siebie, co zwiększa stopień uporządkowania na dysku, a właśnie taki cel przyświeca grupom w filesystemie.
W przypadku porażki poszukiwanie kontynuowane jest w pozostałych grupach. Najpierw, poczynając od grupy następnej po bieżącej, poszukuje się grupy, która ma jakieś wolne bloki testując licznik wolnych bloków w deskryptorze. Tutaj wykorzystuje się niski współczynnik awaryjności systemu ext2. Prawdopodobieństwo tego, że gdzieś będą wolne bloki, a licznik będzie zero lub na odwrót jest na tyle niskie, że można je zlekceważyć. Gdyby chcieć testować po kolei wszystkie bitmapy, tracilibyśmy średnio o wiele więcej.
Po znalezieniu takiej grupy ładowana jest jej bitmapa zajętości. Następnie w pierwszej kolejności próbuje się znaleźć w tej grupie ciąg co najmniej ośmiu następujących po sobie wolnych bloków (cały wolny bajt w bitmapie). Czyni się tak po to, aby zwiększyć szanse, że kolejne kilka bloków, które proces będzie chciał alokować, będzie leżało tuż obok właśnie alokowanego. To jeden ze sposobów unikania fragmentacji plików. Opłaca się to czynić, mimo, że czasem konieczne jest powtórne przeszukanie bitmapy, jeśli się nie uda. Procesy rzadko tworzą pliki o bardzo małych rozmiarach, dlatego taki sposób postępowania nie powinien prowadzić do stopniowego zrównywania rozmiarów wolnych, niezaalokowanych ciągów bloków, choć widać, że warto byłoby wprowadzić dodatkowy parametr sterujący, który mówiłby procedurze, czy alokowany plik jest bardzo mały (wtedy nawet lepiej jest załatać nim małą dziurę) czy raczej duży (wtedy dobrze jest szukać większych wolnych ciągów bloków).
Jeżeli długi ciąg wolnych bloków nie zostanie znaleziony, próbuje się znaleźć jakikolwiek wolny blok w tej grupie. Jeżeli nie zostanie znaleziony, zgłoszony zostaje błąd systemowy integralności informacji w deskryptorze (licznik wolnych bloków). Jeśli zaś wolny blok zostanie znaleziony, to przechodzimy do drugiej fazy działania.
Natomiast w przypadku, kiedy poszukiwanie całego wolnego bajtu w bitmapie zakończyło się sukcesem, bitmapa przeszukiwana jest od początku bajtu wstecz w celu zlokalizowania początku tego wolnego obszaru. Skoro już znaleziono większy wolny obszar, warto upychać dane od początku tego obszaru, żeby go zbyt prędko nie sfragmentować. Przeszukiwanie, co łatwo zauwazyć, wystarczy ograniczyć do siedmiu bloków w tył. Znalezione miejsce jest miejscem przydziału nowego bloku.

Druga faza działania rozpoczyna się od sprawdzenia, czy alokacja nowego bloku nie narusza nałożonej na filesystem quoty. Jeżeli narusza, to wyjście z kodem błędu, jeśli natomiast nie narusza, to w dalszej kolejności sprawdza się, czy alokowany blok nie leży w obszarze systemowym. Jeżeli nie leży, to podjęta zostaje próba ustawienia bitu zajętości dla tego bloku w bitmapie zajętości. Ta próba w pewnych sytuacjach może się nie powieść i wówczas cały algorytm, począwszy od początku pierwszej fazy, wykonywany jest od nowa, do skutku, w pętli nieskończonej. Nie jest jasne, co może być powodem niepowodzenia takiej próby. Z uwagi na to, że algorytm przydziału bloków zaczyna się od zablokowania super-bloku danego filesystemu, a kończy jego odblokowaniem, nie jest możliwe, aby dwa procesy wykonywały tę funkcję jednocześnie na rzecz tego samego filesystemu.

Po ustawieniu bitu zajętości rozpoczyna się trzecia faza, w której dokonuje się opcjonalnej alokacji z wyprzedzeniem. Chęć dokonania prealokacji deklaruje się za pośrednictwem parametru prealloc_block. Próbuje się alokować dodatkowe bloki spośród następujących bezpośrednio po pierwszym zaalokowanym, ale maksymalnie osiem i tylko do końca bieżącej grupy (tzn. nie więcej niż tyle, ile jest bloków w danej grupie za bieżącym). Nie jest wcale oczywiste, że taki sztywny sposób prealokacji ma sens. Funkcja nie przyjmuje żadnego parametru sterującego, który wskazywałby liczbę bloków do prealokacji. Jeżeli często tworzone są pliki o rozmiarach rzędu kilkunastu bloków (czyli kilku kilobajtów, a przecież większość plików w systemie jest takiego rozmiaru), a bloki są im przydzielane sekwencyjnie, to średnio cztery bloki prealokowane są niepotrzebnie, czyli około 20% długości pliku. Widać tutaj, że opisywany algorytm można by usprawnić.
Prealokacja zaczyna się od próby wywołania alloc_block i, jeżeli to się uda, próbuje się ustawić bit zajętości. W przypadku, kiedy alokacja się uda, a ustawienie bitu zajętości nie, dealokuje się blok. Po zakończeniu w parametrze prealloc_count zwracana jest liczba prealokowanych w ten sposób bloków. Jest to zwarty obszar, bo prealokacja kończy się po pierwszym niepowodzeniu.

Po fazie prealokacji następuje ostatnia, czwarta faza działania, w której uaktualnia się struktury na dysku. W pierwszej kolejności bitmapa bieżącej grupy przesłana zostaje na dysk. Jej bufor oznaczony zostaje jako brudny i, jeśli jest to możliwe, wystartowana zostaje transmisja asynchroniczna, a jeśli nie, to synchroniczna i czeka się na jej zakończenie. Następnie dodatkowo sprawdza się, czy przydzielone bloki nie są poza zakresem i ewentualnie zgłaszany jest błąd systemowy. Nie jest jasne, dlaczego ten warunek nie jest sprawdzany wcześniej. Najprawdopodobniej sytuacja ta jest do tego stopnia nieprawdopodobna, że minimalnie krótki czas zaoszczędzony na jej sprawdzaniu procentuje średnio bardziej niż czas , który traci się, gdy ona wystąpi.
Bufora przydzielonego dla załadowania bitmapy używa się na załadowanie zadanego bloku funkcją getblk, zeruje się bufor i oznacza jako brudny, do zapisania, po czym zwalnia się go (faza inicjalizacji zerami nowego bloku). Podsystem obsługi buforów zapisze go na dysk. Bufory bloku z deskryptorami grupy i super-bloku także oznacza się jako brudne, do zapisania na dysk, ponieważ ich zawartość zmieniła się. Ostatecznie zwalnia się semafor super-bloku i kończy wykonanie procedury, zwracając numer zaalokowanego bloku.

Powyższy opis można skonfrontować z oryginalnym kodem procedury ext2_new_block() opatrzonym komentarzami.

Bibliografia

  1. Pliki źródłowe Linuxa:
  2. Projekt Linux
  3. Linux Kernel Hackers Guide
  4. Maurice J. Bach "Budowa systemu operacyjnego UNIX"

Autor: Krzysztof Ostrowski