Linux 2.4.7 - systemy plików

Jerzy Szczepkowski

Krótki opis systemu EXT2
Obsługa map bitowych zajętości bloków
Algorytm zwalniania bloku dyskowego ext2_free_blocks
Algorytm przydziału bloku dyskowego ext2_new_block

System plików EXT2

EXT2

Podstawowy system plików w Linux
Wprowadzony w 1994 roku, jako następca Ext FS (Extended File System)
wybrane możliwości:
- Przy formatowaniu partycji można wybrać rozmiar bloku: 1024, 2048, 4096.
- Przy formatowaniu można określić liczbę i-węzłów.
- Prealokacja bloków.
- Pliki niezmienne (immutable) - tylko do odczytu.

Następcy (EXT3)

Fragmentacja bloków
Listy kontroli dostępu
Przechowywanie na dysku plików zaszyfrowanych i skompresowanych
undelete

Partycja EXT2

blok startowy

BIOS szuka na nim systemu operacyjnego
Niezależny od EXT2

grupa bloków

super blok

są w nim przechowywane informacje o partycji
w każdej grupie bloków trzymana jest jego kopia
jądro standardowo korzysta z kopii grupy 0
wybrane pola:
- s_blocks_count - całkowita liczba bloków danych
- s_free_blocks_count - liczba wolnych bloków danych
- s_inodes_count - liczba i-węzłów na partycji
- s_free_inodes_count - liczba wolnych i-węzłów
- s_inodes_pre_group - liczba i-węzłów w grupie
- s_mnt_count - liczba operacji montowania od ostatniego sprawdzenia
- s_max_mnt_count - co ile montowań wykonujemy sprawdzenia
- s_state - status (0 - zamontowany, 1 - poprawnie odmontowany, 2 - błędy)
- i wiele, wiele innych...

deskryptory grup

tablica z deskryptorami wszystkich grup
w każdej grupie bloków trzymana jest jej kopia
jądro standardowo korzysta z kopii grupy 0
w deskryptorze trzymane są informacje o grupie, między innymi:
- s_free_blocks_count - liczba wolnych bloków w grupie
- s_free_inodes_count - liczba wolnych i-węzłów w grupie
- i inne...
rozmiar pojedynczego deskryptora wynosi 24B

mapy bitowe zajętości bloków i i-węzłów

określają które z bloków (i-węzłów) w grupie są wolne:
- bit 0 - wolne
- bit 1 - zajęte
są rozmiaru dokładnie jednego bloku dyskowego

tablica i-węzłów

każdy i-węzeł grupy ma swój wpis
rozmiar wpisu 128B

bloki danych

używane w zależności od rodzaju pliku który z nich korzysta
zwykły plik - jeśli niepusty przechowuje w nich dane
katalog - przechowuje nazwy plików które zawiera oraz numery odpowiadających im i-węzłów
dowiązanie symboliczne - przechowuje ścieżkę dowiązania (jeśli ma ponad 60B - nie mieści się w i-węźle)
pozostałe pliki (potoki, urządzenia, gniazda...) - nie korzystają z bloków (wszystko w i-węźle)

Mapy bitowe zajętości bloków

Są buforowane w pamięci obiektu superblok, w tablicy s_block_bitmap wielkości 8 (standardowo)
- Jeśli wszystkie się w niej mieszczą każdej odpowiada własny slot
- wpp. algorytm LRU
funkcje:
- ext2_count_free - Liczy ile jest wolnych bloków w podanej mapie bitowej.
- load_block_bitmap - Ładuje mapę bitową zadanej grupy bloków do pamięci podręcznej.
- read_block_bitmap - Odczytuje mapę bitową z dysku do zadanego slotu w superbloku.

Funkcja read_block_bitmap()

                static int read_block_bitmap (struct super_block * sb, 
                                              unsigned int block_group,
                                              unsigned long bitmap_nr);

*sb - wskaźnik do superbloku, dla którego ładujemy bitmapę.
block_group - numer grupy bloków którego bitmapę ładujemy.
bitmap_nr - indeks w tablicy bitmap superbloku.

jeśli ładowanie się powiodło >= 0
wpp. kod błędu

Algorytm po prostu czyta z dysku.

Funkcja ext2_count_free

                unsigned long ext2_count_free (struct buffer_head * map, 
                                               unsigned int numchars);

*map - początek buforu z mapą bitową
numchar - długość mapy bitowej (w bajtach)

liczba wolnych bloków w grupie.

Funkcja sumuje liczbę bitów 0 w bitmapie.

Funkcja load_block_bitmap

                static inline int load_block_bitmap (struct super_block * sb,
                                                     unsigned int block_group);

*sb - wskaźnik do deskryptora super bloku w obrębie którego działamy.
block_group - numer grupy bloków której bitmapę chcemy wczytać.

slot w pamięci podręcznej superbloku, gdzie jest bitmapa >= 0
wpp. kod błędu

jeżeli żądana bitmapa jest załadowana w slocie 0, zwracamy 0
jeżeli mamy mniej grup bloków niż rozmiar pamięci podręcznej (EXT2_MAX_GROUP_LOADED, standardowo 8), i żądana mapa jest już załadowana to zwracamy jej slot.
wpp. wywołujemy funkcje __load_block_bitmap

Funkcja __load_block_bitmap

                static int __load_block_bitmap (struct super_block * sb,
                                                unsigned int block_group)

*sb - wskaźnik do deskryptora superbloku w obrębie którego działamy.
block_group - numer grupy bloków której bitmapę chcemy wczytać.

slot w pamięci podręcznej superbloku, gdzie jest bitmapa >= 0
wpp. kod błędu

jeżeli mamy mniej grup bloków niż rozmiar pamięci podręcznej, czytamy mapę bitową do slotu o numerze jej grupy i zwracamy ten numer.
wpp. obsługujemy algorytm LRU:
- jeżeli mapa jest załadowana przeszeregowujemy mapy młodsze od niej o jeden slot w górę, a ją przesuwamy pod slot.
- jeżeli nie jest: zwalniamy ostatnią pozycje bufora jeśli był pełen, dokonujemy przeszeregowania i czytamy mapę z dysku pod slot 0.

Zwalnianie bloków

Funkcja ext2_free_blocks

                void ext2_free_blocks (const struct inode * inode, 
                                       unsigned long block,
                                       unsigned long count)

*inode - wskaźnik do i-węzła którego bloki zwalniamy.
block - numer pierwszego bloku który mamy zwolnić
count - liczba (kolejnych) bloków do zwolnienia

wskazane bloki są zwalniane...
mogą się one znajdować w różnych (lecz kolejnych) grupach

Alokacja bloków

Funkcja ext2_alloc_block

                static int ext2_alloc_block (struct inode * inode, 
                                             unsigned long goal, 
                                             int *err)

*inode - wskaźnik do i-węzła dla którego chcemy alokować nowy blok
goal - numer bloku od którego mamy rozpocząć poszukiwania
*err - wsk. na potrzeby wyniku

*err - wsk. do ew. błędu

jeżeli i-węzeł posiada jakieś prealokowane bloki i pierwszy z nich ma taki sam numer jak goal, lub numer o jeden większy to zwracamy numer pierwszego z prealokowanych bloków
wpp. zwalniamy wszystkie ew. prealokowane bloki i wywołujemy funkcje ext2_new_block z takim samy goal i inode oraz z odpowiednimi wsk. dla prealokacji

wywołujemy funkcje ext2_new_block z takim samy goal i inode oraz z pustymi wskaźnikami dla prealkokacji

Funkcja ext2_new_block

                int ext2_new_block (const struct inode * inode, 
                                    unsigned long goal,
                                    u32 * prealloc_count, 
                                    u32 * prealloc_block, 
                                    int * err)

*inode - wskaźnik do i-węzła dla którego chcemy alokować nowy blok
goal - numer bloku od którego mamy rozpocząć poszukiwania
*prealloc_count - wsk. do liczby bloków które będziemy próbować prealokować
*prealloc_block - wsk. na potrzeby wyniku
*err - wsk. na potrzeby wyniku

*prealloc_count - wsk. do liczba bloków które udało nam sie prealokować
*prealloc_block - wsk. do numeru pierwszego prealokowanego bloku
*err - wsk. do ew. błędu

Wchodzimy do sekcji krytycznej (lock_super)
Szukamy wolnego bloku:
- Próbujemy zaalokować blok o numerze goal
- Próbujemy zaalokować któryś z następujących po nim 63 bloków
- Przeszukujemy aktualną grupę - najpierw szukamy wolnego bajtu w mapie bitowej, potem wolnego bitu.
- Przeszukujemy cyklicznie pozostałe grupy, aż znajdziemy taką w której są wolne bloki. Szukamy w jej mapie bitowej najpierw wolnego bajtu, potem bitu.
Jeśli znaleźliśmy bajt - cofamy się do siedmiu bloków (jeśli są wolne)
Alokujemy wolny blok
Jeśli działamy z prealokacją i mamy ustawione prealloc_count - staramy się prealokować do prealloc_count-1 bloków za nim.
Wychodzimy z sekcji krytycznej (unlock_super)

Gorące podziekowania dla kol. Maćka Makowskiego za udostępnienie szablonu prezentacji.