Blog literacki, portal erotyczny - seks i humor nie z tej ziemi
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