Od razu na początku pragnę zauważyć, że celem tego dokumentu nie jest opisanie sposobu zarządzania buforami przy obsłudze urządzeń blokowych. W celu uzyskania informacji należy się posłużyć materiałami dotyczącymi systemu plików.

W systemie Linux istnieje mechanizm buforowania. Spełnia on podstawową zasadę, którą musi spełniać system buforowania, mianowicie w danym momencie jest co najwyżej jeden bufor odpowiadający blokowi urządzenia blokowego. Funkcja może pobrać bufor i zapisać do niego dane, jak również może chcieć odczytać dane z bufora. Każdy bufor posiada trzy stany. Mówimy, że bufor jest ważny jeśli zawiera dane, które odpowiadają pewnemu blokowi w urządzeniu. Mówimy, że bufor jest zablokowany, jeśli trwa jakaś operacja na buforze i nie może być obecnie użyty. Mówimy, że bufor jest pobrudzony, jeśli jego dane trzeba zapisać na dysk, ponieważ został zmodyfikowany i dane różnią się od tych na dysku (nie oznacza to oczywiście, że nastąpi to od razu). System Linux udostępnia dwie ważne funkcje do operowania na buforach. Pierwsza - getblk(urządzenie, numer bloku, rozmiar) odpowiada za zwrócenie odpowiedniego bufora. Oczywiście jeśli dany blok na danym urządzeniu jest już buforowany, to jest on zwracany. Druga funkcja - brelse(bufor) zaznacza, że skończyliśmy korzystać z bufora. Po wywołaniu tej funkcji, w zależności od stanu, bufor może zostać zapisany do urządzenia lub ponownie użyty dla tego samego lub innego bloku.

Podobnie jak przy pozostałych funkcjach, funkcje odczytu i zapisu są opakowaniami dla odpowiednich funkcji systemowych. I tak dla read() jest wywoływane sys_read(), która po sprawdzeniu blokad wywołuje funkcję block_read(). Analogicznie działa funkcja write(), wywołująca funkcję sys_write(), a następnie block_write().

Idea działania algorytmu jest bardzo prosta. Odczyt danych jest podzielony na dwie fazy, które wykonują się na zmianę. W pierwszej fazie funkcja próbuje pobrać tak dużo nie ważnych buforów jak to tylko możliwe. Następnie w razie potrzeby funkcja zleca odczytanie zbioru buforów. W drugiej fazie dane z buforów są kopiowane do procesu wywołującego. Realizacja również nie jest skomplikowana.
Funkcja przyjmuje cztery parametry:
struct file * filp, const char * buf, size_t count, loff_t *ppos.
Krótki komentarz:

• filp - strukura file pobrana z tablicy deskryptorów
• buf - bufor, do którego należy odczytać dane
• count - ilość danych, którą należy odczytać-
• ppos. - pozycja od której należy rozpocząć czytanie

• size_t block - numer bloku, od którego należy rozpocząć kopiowanie danych z urządzenia
• loff_t offset - przesunięcie danych względem początku bloku
• ssize_t blocksize - rozmiar bloku urządzenia
• ssize_t blocksize_bits - logarytm dwójkowy z blocksize
• size_t blocks - ilość buforów z tablicy bhreq, które należy odczytać z urządzenia
• size_t left - ilość bajtów pozostała do odczytania
• int bhrequest - ilość buforów z tablicy bhreq, które należy odczytać z urządzenia
• struct buffer_head ** bhb - początek kolejki buflist
• struct buffer_head ** bhe - koniec kolejki buflist
• struct buffer_head * buflist[NBUF] - służy do przechowywania danych kolejki obsługiwanej przez zmienne bhb i bhe
• struct buffer_head * bhreq[NBUF] - bufory, które muszą być odczytane z urządzenia
• unsigned int chars - ilość bajtów do odczytania z kolejnego bloku
• loff_t size - rozmiar urządzenia
• kdev_t dev - numer urządzenia, do którego należy zapisac dane-
• ssize_t read - ilość danych, które zostały odczytane z urządzenia.

Na początku działania algorytmu, na podstawie struktury file (zmienna filp) ustawiana jest wartość zmiennej dev na numer urządzenia, z którego odczytuje dane. W tym czasie wykorzystywana jest praktycznie niepotrzebna zmienna inode.

dev = inode->i_rdev;

Nastepnie ustalana jest wielkość bloku dla urządzenia. W tym celu odczytywane są odpowiednie pola z tablicy blksize_size, o ile są one określone. W tym bowiem przypadku przyjmuje się, że wielkość bloku jest równa BLOCK_SIZE, który jest zdefiniowany w pliku include/linux/fs.h i może mieć wartość np. 2^10.

blocksize = BLOCK_SIZE;
if (blksize_size[MAJOR(dev)] && blksize_size[MAJOR(dev)][MINOR(dev)])
  blocksize = blksize_size[MAJOR(dev)][MINOR(dev)];

Następnie obliczany jest logarytm dwójkowy z wielkości bloku. Sensowność tego rozwiązania jest dyskutowana przy omawianiu funkcji block_write() (Patrz podrozdział 9.1). Następnie zmienna offset jest ustawiana na pozycję początkową odczytu z urządzenia, natomiast size jest ustawiane na rozmiar urządzenia. W tym celu wykorzystywana jest tablica blk_size zawierająca wielkości urządzeń blokowych oraz ustawiona zmianna dev.

offset = *ppos;
if (blk_size[MAJOR(dev)])
  size = (loff_t) blk_size[MAJOR(dev)][MINOR(dev)] << BLOCK_SIZE_BITS;
else
  size = (loff_t) INT_MAX << BLOCK_SIZE_BITS;

Mając już rozmiar urządzenia funkcja może sprawdzić, czy podane parametry dotyczące początkowej pozycji odczytu i rozmiaru danych do odczytania są poprawne. W tym celu najpierw jest sprawdzane czy czytanie nie zaczyna się poza urządzeniem. Dalej sprawdzane jest sztuczne ograniczenie na ilość danych, które ogranicza wielkość jednorazowo odczytywanych danych do wartości INT_MAX. Również w oczywisty sposób nie jest możliwe odczytanie większej ilości danych, niż pozostała od pozycji początkowej do końca. Biorąc pod uwagę wszystkie te warunki ustawiana jest zmienna left oznaczająca ilość danych, które powinny być odczytane. Warto zwrócić uwagę, że może być to wartość różna niż podany przez wywołującego parametr count. Oczywiście jak ilość danych do odczytania wynosi w tym miejscu 0, to można od razu opuścić funkcję.

if (offset > size)
  left = 0;
else if (size - offset > INT_MAX)
  left = INT_MAX;
else
  left = size - offset;
if (left > count)
  left = count;
if (left <= 0)
  return 0;

Biorąc pod uwagę fakt, że urządzenie blokowe zawsze operuje na całych blokach, to aby rozpocząć operacje odczytu potrzebne są jeszcze dane o początkowej pozycji i o ilości danych do przeczytania wyrażone w blokach. Tak więc kolejnym krokiem jest wyliczenie bloku oraz przesunięcia wewnątrz niego pozycji, od której rozpocznie się odczyt, a także w bardzo sprytny sposób wyznaczenia ilości bloków o odczytu. Początkowy numer bloku i przesunięcie względem niego jest przechowywane w zmiennych block i offset natomiast ilość bloków do odczytania w blocks. Ponadto do zmiannej size obliczana jest wielkość urządzenia wyrażona w blokach.

block = offset >> blocksize_bits;
offset &= blocksize-1;
size >>= blocksize_bits;
rblocks = blocks = (left + offset + blocksize - 1) >> blocksize_bits;

W tym momencie zauważmy, że liczba bloków do odczytania może być mała, co więcej można się spodziewać, że kolejne żądanie odczytu będzie dotyczyło kolejnych bloków urządzenia, z którego czytamy. Zatem funkcja jeśli tylko ma taką możliwość, to znaczy jeśli urządzenie dostarcza usługę, próbuje czytać bloki z wyprzedzeniem. Stwierdzenie czy urządzenie zaleca czytanie z wyprzedzeniem polega na sprawdzeniu czy pole w tablicy read_ahead jest ustawione.

if (filp->f_reada) {
  if (blocks < read_ahead[MAJOR(dev)] / (blocksize >> 9))
    blocks = read_ahead[MAJOR(dev)] / (blocksize >> 9);
  if (rblocks > blocks)
    blocks = rblocks;
}

Teraz trzeba znowu sprawdzić czy nowa wartość ilości bloków do przeczytania nie odwołuje się do bloków poza urządzeniem.

if (block + blocks > size) {
  blocks = size - block;
  if (blocks == 0)
    return 0;
}

W tym momencie funkcja posiada wszystkie informacje, aby rozpocząć czytanie. W dalszym części funkcja spróbuje odczytać tyle bloków na ile jest ustawiona zmienna blocks. Pierwszym blokiem będzie blok o numerze ze zmiennej block. W pierwszym bloku przesunięcie czytanych danych wynosi offset. Do skopiowania jest w sumie left bajtów.

Jak już wspominałem algorytm odczytu składa się z dwóch występujących na zmianę faz. W tych fazach wykorzystywane są tablice bhreq i buflist. Z pierwszą związany jest licznik bhrequest, który zawiera ilość zajętych pól w tablicy. Z drugą zawiazane są wskaźniki bhb i bhe, które wykorzystują tą tablicę w celu obsługi kolejki. Początkowo oczywiście obie tablice są puste. Od tej chwili mówiąc kolejka będziemy mieli na myśli zmienne bhb i bhe, gdzie bhb jest początkiem kolejki zaś bhe jej końcem. Zawsze wstawiamy na początek kolejki zaś usuwamy z końca.

Faza pierwsza.
Celem tej fazy jest pobranie do kolejki jak największej ilości buforów dla kolejnych bloków. Bufory są pobierane oczywiście za pomocą funkcji getblk(). Przy każdym buforze sprawdzane jest czy bufor jest ważny. Jeśli nie, to w oczywisty sposób trzeba do niego sprowadzić dane z urządzenia. Dlatego właśnie wszystkie bufory, do których trzeba sprowadzić dane są zapamiętywane w tablicy bhreq. W tym momencie korzystamy z tego, że wielkość tablicy bhreq jest niemniejsza niż tablicy buflist (w tym przypadku równa). Zauważmy, że wszelkie błędy przy pobieraniu buforów są w tym momencie ignorowane.

*bhb = getblk(dev, block++, blocksize);
if (*bhb && !buffer_uptodate(*bhb)) {
  uptodate = 0;
  bhreq[bhrequest++] = *bhb;
}

Koniec fazy następuje jeśli wypełni się kolejka lub jeśli odczytany bufor jest pierwszym pobranym buforem w tej fazie i jest ważny lub też jeśli po prostu zostały przeczytane wszystkie bloki.

while (blocks) {
  blocks;
  (...)
  if (uptodate)
    break;
  if (bhb == bhe)
    break;
}

Po zakończeniu pierwszej fazy wysyłane jest do urządzenia żądanie odczytu dla wszystkich bloków, które zostały przetworzone w poprzedniej fazie.

if (bhrequest) {
  ll_rw_block(READ, bhrequest, bhreq);
}

Faza druga.
Celem drugiej fazy jest odczytanie danych z buforów pobranych w fazie pierwszej i skopiowanie ich do pamięci wywołującego. W tej fazie przetwarzane i usuwane są kolejne elementy kolejki. Dla każdego elementu na początku sprawdzane jest czy w ogóle jest on buforem, ponieważ w fazie pierwszej ignorowane są blędy pobrania bufora. Jeśli jest to bufor, to najpierw trzeba poczekać na zakończenie operacji na nim. Jeśli po zakończeniu operacji bufor jest ważny, to wszystko jest w porządku w przeciwnym przypadku prawdopodobnie wystąpił jakiś bląd przy odczycie danych. Następnie aktualny bufor jest zaznaczany jako nieużywany, zaś ilość danych do odczytu jest ustawiana na 0. Zatem w tym momencie kończone są fazy odczytu.

if (*bhe) {
  wait_on_buffer(*bhe);
  if (!buffer_uptodate(*bhe)) { /* read error? */
    brelse(*bhe);
    if (++bhe == &buflist[NBUF])
      bhe = buflist;
    left = 0;
    break;
  }
}

Jeśli wszystko poszło dobrze, funkcja przystępuje do kopiowania danych do pamięcie procesu wywołującego, to znaczy do buforu wskazywanego przez parametr buf. Aby jednak to zrobić konieczne jest wyliczenie ile danych należy skopiować. Następnie aktualizowana jest pozycja danych do odczytu oraz zaktualizowane są liczniki danych pozostałych do skopiowania (left) i ilości skopiowanych danych (read). Zauważmy, że wielkość chars, ilości danych do skopiowania, jest prawie zawsze równa wielkości bloku. Jedyne przypadki, gdy tak nie jest występują gdy blok jest pierwszym lub ostatnim odczytywanym blokiem. Można wiec się zastanawić czy rzeczywiście takie rozwiązanie jest optymalne, ponieważ w przypadku odczytywania dużej ilości bloków w każdej pętli wykonywane są niepotrzebne porównania i obliczenia.

if (left < blocksize - offset)
  chars = left;
else
  chars = blocksize - offset;
*ppos += chars;
left -= chars;
read += chars;


Teraz można przystąpić do kopiowania danych. W przypadku gdy bufor dla bloku jest określony, to kopiowane są dane z bufora do pamięci wywołującego, a nastepnie bufor jest zaznaczany jako nieużywany. W przypadku gdy nie jest określony bufor zamiast danych z urządzenia wpisywane są wartości 0.

if (*bhe) {
  copy_to_user(buf,offset+(*bhe)->b_data,chars);
  brelse(*bhe);
  buf += chars;
} else {
  while (chars-- > 0)
  put_user(0,buf++);
}

W tym momencie przesunięcie danych względem początku bloku jest równe zero.

offset = 0;

Jedyna rzecz jaka pozostała, to usunąć właśnie przetworzony blok z kolejki.

if (++bhe == &buflist[NBUF])
  bhe = buflist;

Powstaje pytanie kiedy zakończyć fazę ? Więc oczywiście należy to zrobić jeśli nie ma już nic do odczytania. Jest jasne, że koniec jest w przypadku przetworzeniu wszystkich buforów przygotowanych w fazie pierwszej. Również kończona jest faza jeśli kolejny bufor do przetworzenia jest zablokowany. Warto się zastanowić co się dalej będzie działo z tym buforem ? Otóż nie zostanie on usunięty z kolejki. Przy następnej fazie pierwszej funkcja nie wykona na nim żadnej operacji, ale być może zostaną pobrane i odczytane kolejne bufory. Zatem zamiast bezczynnego czekania na odblokowanie bufora. zostaną wykonane kolejne odczyty danych. Czekanie nastąpi dopiero w kolejnej fazie drugiej. Po opuszczeniu fazy drugiej spwawdzane jest czy należy kontynuować odczytywanie. Więc ewidentnie nie ma po co kontynuować odczytywania jeśli wszystko zostało odczytane, ale także w przypadku gdy odczytano wszystkie bloki i kolejka jest pusta.

do {
  (...)
  if (bhe == bhb && !blocks)
    break;
} while (left > 0);

Moim zdaniem ten fragment kodu jest wyjątkowo nieelegancko napisany. W tym stylu nie należy pisać w języku imperatywnym, szczególnie gdy istnieje takie oto eleganckie rozwiązanie.

do {
  (...)
} while ((bhe != bhb || blocks) && left > 0);

Po zakończeniu odczytywania danych funkcja musi po sobie posprzątać, to znaczy zaznaczyć jako nieużywane wszystkie bufory z kolejki. Trzeba sobie zdać sprawę, że takie pozostałości nie muszą być wynikiem błędu, ponieważ możemy wykorzystywać czytanie z wyprzedzeniem. A więc jasne jest, że nie wszystkie dane, które zostaną przeczytane z urządzenia są istotne, więc część buforów będzie w takim przypadku niewykorzystana.

while (bhe != bhb) {
  brelse(*bhe);
  if (++bhe == &buflist[NBUF])
    bhe = buflist;
};

To już jest właściwie koniec funkcji. Warto jeszcze powiedzieć, że jeśli w funkcji udało się przeczytać choć jeden bajt danych poprawnie, to niezależnie co by się działo, to takie wykonanie nie jest błędne i wywołujący nie dowie się co się stało.

if (!read)
  return -EIO;
return read;

Używane tablice danych - patrz opis funkcji block_write() (rozdział 9.1).

Używane struktury - patrz opis funkcji block_write() (rozdział 9.1).

Typy danych - patrz opis funkcji block_write() (rozdział 9.1).