Algorytm alokacji bloków dyskowych - ext2_new_block
Michał Fiejka
1. Wstęp
Algorytm ext2_new_block służy do alokacji bloków dyskowych na potrzeby systemu. Funkcja ta zdefiniowana jest w pliku fs/ext2/balloc.c. Obok niej zdefiniowane są tam również funkcje do obsługi bitmap zajętości bloków na dysku.
2. Działanie
Nagłówek:
void ext2_free_blocks (struct inode * inode, unsigned long block, unsigned long count)
Dane wejściowe:
- inode - wskaźnik do struktury i-node, dla której próbujemy przydzielić blok;
- goal - numer bloku, który byłby najlepszy jako przydzielony.
Dane wyjściowe:
Funkcja zwraca numer przydzielonego bloku, lub zero jeśli wystąpił błąd (wtedy parametr err zawiera numer błędu).
Ponadto zostają uzupełnione otrzymane parametry:
- prealloc_count - ilością prealokowanych bloków;
- prealloc_block - numerem pierwszego prealokowanego bloku;
- err - numerem ewentualnego błędu.
Algorytm działa w czterech fazach:
- Odnalezienie wolnego bloku (z uwzględnieniem bloku przekazywanego jako parametr, jako mającego najwyższy priorytet);
- Sprawdzenie czy dany blok może być przydzielony (przeciwwskazania: przekroczenie quoty lub blok leży w obszarze systemowym);
- Ewentualna prealokacja;
- Uaktualnienie struktur na dysku;
1.
W pierwszej kolejności funkcja pobiera z parametru i-node wskaźnik do super-bloku bieżącej grupy i blokuje go. Ma to zapobiec sytuacji w której dwa procesy usiłują zaalokować ten sam blok.
Potem funkcja sprawdza, czy w ogóle możliwe jest przydzielenie jakiegokolwiek bloku. W tym celu sprawdzamy, czy na dysku są jeszcze wolne bloki. Jeżeli są to sprawdzamy czy przydzielenie jednego z nich nie zmniejszy ilości wolnych bloków poniżej minimum. Owo minimum to ilość bloków zarezerwowanych dla super-użytkownika. Tylko jemu możemy przydzielić bloki z tego obszaru. Jeżeli coś się nie powiedzie funkcja ustawia odpowiedni kod błędu i zwraca zero.
Sprawdzamy poprawność parametru goal. Jeżeli wykracza poza zakres to ustawiamy go na zero. Ładujemy mapę bitową zajętości bloków danej grupy.
Następnie sprawdzamy czy blok, którego numer był przekazany nam jako parametr, jest wolny. Jeżeli tak to przechodzimy do następnej fazy. Jeżeli nie to próbujemy przydzielić blok, który znajduje się w "niedalekim" sąsiedztwie tego bloku. Przeszukujemy mapę bitową w przód aż do pseudolosowo wybranej wartości nie przekraczającej ilości bloków w grupie. Jeżeli uda nam się znaleźć jakiś wolny blok to przechodzimy do fazy drugiej. W przeciwnym przypadku próbujemy znaleźć w bitmapie ciąg ośmiu zerowych bitów, szukając zerowego bajtu. Gdy to nam się powiedzie, to oznacza, że znaleźliśmy spójny ciąg pustych bloków. Cofamy się teraz do początku tego bloku (najwyżej o siedem pozycji) i przechodzimy do kolejnej fazy. Ten fragment algorytmu ilustruje następujący schemat:
Jeżeli przeszukując mapę bitową nie znajdziemy żadnego zerowego bajtu, poszukujemy na niej pierwszego zerowego bitu. Jeżeli odniesiemy sukces to zwracamy numer tego bloku, w przeciwnym przypadku oznacza to że w naszej grupie nie ma wolnych bloków. Kontynuujemy wtedy poszukiwania cyklicznie w kolejnych grupach. To znaczy sprawdzamy czy licznik wolnych bloków następnej grupy jest większy od zera i ładujemy jej bitmapę, przechodzimy ją w poszukiwaniu zerowych bajtów, jeżeli to nie odniesie skutku - przeszukujemy bitmapę w poszukiwaniu zerowego bitu.
Po pierwszej fazie powinniśmy być w posiadaniu numeru wolnego bloku.
2.
Teraz dopiero następuje próba zwiększenia quoty oraz sprawdzenie, czy przydzielając ten blok nie przekroczymy quoty użytkownika. Jeżeli tak to wychodzimy z błędem, jeżeli nie to sprawdzamy czy wybrany blok nie leży w obszarze systemowym. Jeżeli tak się stało to wywołujemy ext2_panic w przeciwnym przypadku sprawdzamy czy ten blok nie jest dziwnym trafem zajęty, jeżeli tak to odwracamy zmiany w quota i cały proces wykonujemy od początku w nieskończonej pętli. Gdy blok nie jest zajęty to sami go zajmujemy ustawiając odpowiedni bit zajętości.
3.
Przechodzimy teraz do trzeciej fazy. Prealokacja odbywa się jedynie jeżeli w systemie jest zdefiniowana taka opcja. Prealokacja pozwala na zmniejszenie fragmentacji dysku poprzez zwrócenie poza blokiem o który proszono, także kilka innych (wolnych) bloków w bezpośrednim sąsiedztwie przydzielanego bloku. Dzięki takiemu rozwiązaniu duże pliki - zajmujące kilka bloków mogą dostawać bloki które fizycznie leżą na dysku w bezpośrednim sąsiedztwie.
Prealokacja polega na przeszukaniu pewnej stałej liczby bloków (zazwyczaj osiem) bezpośrednio za wybranym blokiem. Przeszukanie kończy się gdy trafimy na zajęty blok, lub przekroczymy ową stałą. Dostajemy w ten sposób zwarty ciąg wolnych bloków w bezpośrednim sąsiedztwie naszego bloku. Aktualizujemy teraz odpowiednie liczniki wolnych bloków. Wyniki naszych poszukiwań zapisujemy w parametrach które otrzymaliśmy. Na prealloc_count ilość wolnych bloków, na prealloc_block numer pierwszego bloku za blokiem wybranym w fazie pierwszej. Prealokowanych bloków nie zaznaczamy jako zajęte.
4.
W ostatniej fazie dokonujemy uaktualnienia struktur na dysku. Najpierw zaznaczamy, że blok zawierający mapę bitową jest używany, potem ewentualnie czekamy, aż będzie gotowy do zapisu. Następnie dodatkowo sprawdzamy czy blok nie jest poza zasięgiem. Jeżeli tak to kończymy z błędem, a jeśli nie to wczytujemy wybrany blok oznaczamy jako brudny i do zapisania na dysk. Podobnie bloki z deskryptorami grupy i super-bloku, ponieważ ich zawartość zmieniła się. Ostatecznie zwalniamy super-blok i kończymy wykonanie procedury, zwracając numer zaalokowanego bloku.
Schemat działania algorytmu ext2_new_block