Do spisu tresci tematu 5

5.3.4 Dostep do danych z pliku - algorytm bmap

Spis tresci

Wprowadzenie
Implementacja algorytmu bmap
Przyklad
Uwagi
Bibliografia

Wprowadzenie

Zadaniem algorytmu bmap jest przeksztalcanie logicznego adresu bajtu w pliku na adres fizyczny na dysku. W Linuxie wejsciem dla algorytmu bmap nie jest logiczny adres bajtu, ale logiczny adres bloku w ktorym ten bajt sie znajduje. Odwzorowanie adresu bajtu w pliku w numer bloku na dysku (w ktorym ten bajt sie znajduje) odbywa sie nastepujaco:

- znajac numer bajtu obliczamy logiczny numer bloku (wykonujac dzielenie calkowite numer_bajtu/rozmiar_bloku).

- znaleziony numer bloku przekazujemy funkcji bmap, ktora obliczy fizyczny numer bloku.

Omawiamy tutaj algorytm zaimplementowany w systemie plikow ext2.

Implementacja algorytmu `ext2_bmap()`

DEFINICJA: int ext2_bmap(struct inode * inode, int block)
    WYNIK: fizyczny numer bloku na dysku w przypadku sukcesu
           0, gdy blok nie znaleziony

Pierwszym argumentem funkcji jest wskaznik na i-wezel pliku. Drugim argumentem jest logiczny numer bloku.

Algorytm ext2_bmap() uzywa nastepujacych krotkich funkcji pomocniczych:

inode_bmap(inode,nr): Jest to makro, ktore przekazuje numer bloku zapisany na pozycji nr w tablicy blokow pliku w i-wezle wskazywanym przez inode. Parametr nr powinien zatem nalezec do przedzialu [0..EXT2_N_BLOCKS-1] (czyli [0..14]). Makro to uzywane jest przy pobieraniu adresu fizycznego jednego z blokow bezposrednich, bloku pojedynczego, podwojnego badz potrojnego posredniego.
int block_bmap(struct buffer_head * bh, int nr): Funkcja ta przekazuje liczbe zapisana w bloku z naglowka bufora bh, w komorce o numerze nr. Po odczytaniu zwalnia bufor (wykonujac brelse()).Uzywana jest przy odczytywaniu adresow w blokach pojedynczych, podwojnych i potrojnych posrednich.

Nalezy zwrocic uwage na dwie zmienne uzywane w funcji ext2_bmap():

addr_per_block: Jej wartosc jest stale ustawiona na liczbe adresow mieszczacych sie w bloku (czyli rozmiar_bloku/rozmiar_adresu).
addr_per_block_bits: Jej wartosc jest stale rowna logarytmowi przy podstawie 2 z wartosci zmiennej addr_per_block. Zmienna ta jest wykorzystywana przy wykonywaniu roznych operacji na bitach.

Przy przeksztalcaniu adresow zachodzi potrzeba obliczenia liczby blokow, ktore mieszcza sie w poszczegolnych strefach posredniosci. Ponizej mozna przeczytac, jak radzi sobie z tym problemem algorytm ext2_bmap():

liczba blokow bezposrednich = EXT2_NDIR_BLOCKS
liczba blokow dostepnych poprzez blok pojedynczy posredni = addr_per_block
liczba blokow dostepnych poprzez blok podwojny posredni =
```
1 << (addr_per_block_bits*2)
```
(czyli wartosc zmiennej addr_per_block do kwadratu.
liczba blokow dostepnych poprzez blok potrojny posredni =
```
(1 << (addr_per_block_bits * 2)) << addr_per_block_bits
```
(czyli wartosc zmiennej addr_per_block do potegi trzeciej)

Maksymalna liczba blokow dajaca sie zaadresowac w i-wezle jest suma wymienionych wyzej czterech liczb.

Implementacja funkcji ext2_bmap:

{
   /* Sprawdz czy parametr wywolania block jest poprawny */
   
   if (block < 0) return 0; /* Blok nie znaleziony */
   if (block >= maksymalna liczba blokow mozliwa do zaadresowania w i-wezle)
      return 0;

   /* Numer block jest poprawny; dalsze dzialanie zalezy od poziomu
      posredniosci, w ktorym znajduje sie blok block */

DIR: 
   /* Poziom bezposredni */
   
   /* Blok jest w poziomie bezposrednim, gdy jego numer jest mniejszy
      od liczby blokow bezposrednich */

   if (block < EXT2_NDIR_BLOCKS)
      return inode_bmap(inode,block);

   /* Blok jest w strefach posrednich; pomijamy bloki bezposrednie */
   block -= EXT2_NDIR_BLOCKS;

IND:
   /* Pierwszy poziom posredniosci */

   /* Blok jest w pierwszym poziomie posredniosci, gdy zmienna block
      w tej chwili jest mniejsza od liczby blokow dostepnych poprzez
      pojedynczy blok posredni */

   if (block < addr_per_block)
   {
      /* Pobierz numer bloku pojedynczego posredniego */

      i = inode_bmap(inode, EXT2_IND_BLOCK);
      
      if (i == 0)
         return 0;

      /* Wczytaj blok o numerze i ( zapiszemy to krotko bread(i) )
         a nastepnie przekaz go jako pierwszy argument do funkcji
         pomocniczej block_bmap */

      return block_bmap( bread(i), block );
   }

   /* Blok jest w poziomie posredniosci wyzszym od pierwszego;
      pomijamy bloki w pierwszym poziomie posredniosci */

   block -= addr_per_block;

DIND:
   /* Drugi poziom posredniosci */

   if (block < liczba blokow dostepnych poprzez blok podwojny posredni)
   {

      /* Blok jest w drugim poziomie posredniosci */

      /* Pobierz numer bloku podwojnego posredniego */
  
      i = inode_bmap(inode, EXT2_DIND_BLOCK);

      if (i == 0)
         return 0;

      /* Pobierz numer bloku pojedynczego posredniego,
         w ktorym znajduje sie szukany blok; ten blok pojedynczy
         posredni ma numer block/addr_per_block (czesc calkowita
         ilorazu */

      i = block_bmap(bread(i), block >> addr_per_block_bits);

      if (i == 0)
         return 0;

      /* W bloku o numerze i, na pozycji (block mod addr_per_block)
         znajduje sie szukany adres bloku */

      return block_bmap(bread(i), block & (addr_per_block - 1));
   }

   /* Pomijamy bloki w strefie drugiej posredniosci */

   block -= liczba blokow dostepnych poprzez podwojny blok posredni;

TIND:
   /* Trzeci poziom posredniosci */

   /* Pobierz numer bloku potrojnego posredniego */

   i = inode_bmap(inode, EXT2_TIND_BLOCK);

   if (i == 0)
      return 0;

   /* Pobierz numer bloku podwojnego posredniego, w ktorym znajduje sie
      szukany blok; ten blok podwojny posredni ma numer rowny calosci
      z dzielenia liczby block przez kwadrat liczby addr_per_block */

   i = block_bmap( bread(i), block >> (addr_per_block_bits * 2) );

   if (i == 0)
      return 0;

   /* Z bloku i pobierz numer bloku pojedynczego posredniego, w ktorym
      znajduje sie szukany blok; ten numer mozna otrzymac biorac czesc
      calkowita z ilorazu block przez addr_per_block, a nastepnie z tego
      wyniku reszte modulo addr_per_block */

   i = block_bmap( bread(i), 
		(block >> addr_per_block_bits) & (addr_per_block - 1) );

   if (i == 0)
      return 0;

   /* Teraz w bloku i na pozycji block mod addr_per_block znajduje sie
      szukany adres bloku */

   return block_bmap(bread(i), block & (addr_per_block - 1))
}

Przyklad

Zalozmy, ze w bloku mieszcza sie 4 adresy: addr_per_block = 4, zatem addr_per_block_bits = 2. Przypuscmy, ze uklad blokow pewnego pliku jest taki, jak na rysunku ponizej.

Powiedzmy, ze chcemy odczytac blok o numerze (logicznym) 22.

block = 22

Poniewaz 22 >= 12 (EXT2_NDIR_BLOCK) to blok nie lezy wsrod blokow bezposrednich.

block = 22 - 12 = 10

Sprawdzamy, ze 10 >= addr_per_block, czyli musimy rozpatrywac blok podwojny posredni.

block = 10 - addr_per_block = 10 - 4 = 6

Sprawdzamy, ze 6 < 16 (addr_per_block do kwadratu), czyli szukany blok jest w strefie podwojnej posredniosci.

Pobieramy adres bloku podwojnego posredniego w i-wezle: 185. Wczytujemy blok 185. Mamy 6 > > 2 = 1, czyli szukany blok lezy w drugim bloku pojedynczym posrednim (z zapisanych w bloku o numerze 185). Pobieramy numer tego bloku; jest to 114.

Wczytujemy blok 114. Numer interesujacego nas bloku jest na pozycji 6 & (addr_per_block - 1) = 6 & 3 = 2. Zatem numer fizyczny bloku o numerze logicznym 22 to 600.

Uwagi

Konwersja bajtu o wysokim numerze, korzystajaca z blokow posrednich jest dosyc kosztowna, wymaga od jadra kilku dostepow do blokow dyskowych (to moze prowadzic do oczekiwania w stanie uspienia podczas wykonania ext2_bmap). Algorytm jest optymalny dla systemu z niewielkimi plikami (n.p. nie korzystajacymi z blokow podwojnego i potrojnego posredniego -- dla tych blokow konwersja adresu jest najkosztowniejsza).
W opisie algorytmu bmap w ksiazce Bacha znajdujemy optymalicacje polegajaca na czytaniu blokow z wyprzedzeniem. Nie jest ona realizowana w Linuxie.

Bibliografia

Pliki zrodlowe Linuxa:
- fs/ext2/inode.c (m.in. implementacja algorytmu bmap)

Autor: Andrzej Dorf