z!doctype html public "-//w3c//dtd html 4.0 transitional//en"> Algorytm block_read i block_write
Autor: Paweł Fic

Algorytm block_read i block_write

      Dobre obsłużenie urządzeń blokowych nie jest rzeczą łatwą. Każdy system operacyjny udostępnia użytkownikowi podstawowe funkcje do tego celu. Jednak mimo wszystkich wysiłków programista samemu pisząc program nie jest w stanie całkowicie zoptymalizować komunikacji między urządzeniem blokowym a komputerem w systemie wielozadaniowym.
      Pisząc program jedyne co można wziąć pod uwagę to żądania naszego programu do urządzenia. W systemie wielozadaniowym żądania wielu procesów przeplatają się, a próba samodzielnej optymalizacji pracy z urządzeniem może spowodować efekt przeciwny do oczekiwanego.
      Linux udostępnia użytkownikowi funkcje systemowe do pracy z urządzeniami. Funkcje te, chcąc skorzystać z urządzenia blokowego odwołują się wła?nie do funkcji block_read i block_write, przekazując im odpowiednie parametry. Wła?nie te funkcje odpowiedzialne są za optymalizację pracy całego systemu (wszystkich uruchomionych programów) z urządzeniami blokowymi.
 
Spis treści

Cel użycia algorytmów

Okre?lmy zatem podstawowe cele stawiane przed algorytmami:
  • optymalizacja czasu dostępu do urządzeń blokowych, zwłaszcza operacji czytania, gdyż występuje ona znacznie czę?ciej od operacji zapisu. Także bez otrzymiania żądanych danych program nie jest w stanie dalej pracować, podczas gdy operację zapisu system może wykonać z opóYnieniem, nie wstrzymując działania programu
  • ułatwienie użytkownikowi mniej lub bardziej uciążliwej pracy z urządzeniami blokowymi.
Spis treści

Na czym oparte są algorytmy

Wykorzystują one charakterystyczne dla urządzeń blokowych:
  • stosunkowo nieduża prędko?ć transferu danych pomiędzy urządzeniem a pamięcią komputera,
  • długi czas rozpoczęcia odczytu/zapisu
oraz systemu operacyjnego
  • sekwencyjne czytanie i pisanie z pliku (urządzenia),
  • równoczesne bądY wielokrotne korzystanie z tych samych plików.
Spis treści

Zastosowane rozwiązania

      Algorytmy starają się optymalnie wykorzystać podręczną pamięć urządzeń blokowych. Wczytywane dane przechowywane są w pamięci i je?li tylko nie zostaną z niej usunięte, funkcje nie wczytują ich ponownie. Ponieważ cała komunikacja z urządzeniami blokowymi odbywa się przez te funkcje, gwarantuje to, że nic nie zostanie dwukrotnie wczytane do pamięci.

      Sam proces czytania i pisania do urządzenia blokowego realizowany jest przez funkcję ll_rw_block. Funkcja ta dba o to, aby tranfer danych realizowany był przez urządzenie i kanały DMA, dzięki czemu operacja ta nie zajmuje czasu procesora.

      Stosowane jest także tzw. czytanie z wyprzedzeniem (read-ahead). Je?li system wykrył, że ma do czynienia z czytaniem sekwenyjnym to ustawia flagę read_ahead dla urządzenia (pliku), co powoduje, że przy następnej próbie czytania funkcje wczytają do pamięci dodatkowe dane. Czytanie z wyprzedzeniem staje się nieopłacalne je?li program korzysta z pliku z trybie swobodnego dostępu (RANDOM ACCES). Ponieważ mamy do czynienia bardziej ze zgadywaniem jak poszczególne programy korzystają z urządzenia, system stara się przyjąć odpowiednią strategię. Np. w momencie zmiany pozycji (odczytu/zapisu) w pliku flaga f_reada jest zerowana. Je?li jednak dwukrotnie, po kolei odczytamy fragment danych z pliku, to za drugą próbą przygotujemy się do trzeciego odczytu z pliku, który prawie na pewno nastąpi (czytanie z wyprzedzeniem polega na wczytywaniu nie mniejszej niż pewna opłacalna ilo?ci bloków z urządzenia).

Spis treści

Schemat działania algorytmu block_read

      Chcą obejrzec dokładny opis implementacji algorytmu, należy zajrzeć do rozdzialu implementacja algorytmu block write. Jednak wcze?niej warto zapoznać się z jego schematem. Projektując algorytm jego twórca miał cały czas na uwadze fakt, że operacja czytania z urządzeń blokowych jest kluczowa z punktu działania systemu.

1.  Pobranie rozmiaru bloku dla urządzenia z którego żądamy odczytu.
2.  Ustalenie ile bajtów użytkownik może odczytać z urządzenia.
3.  Konfrontacja ilo?ci bajtów które użytkownik chce i może odczytać z urządzenia, wybranie mniejszej warto?ci.
4.  Obliczenie w których blokach znajdują się żądane dane.
5.  Je?li ustawiona jest flaga f_reada dla urządzenia, to je?li ilo?ć bloków do wczytania jest mniejsza niż okre?lona minimalna dla urządzenia, to ją zwiększamy.
6.  Sprawdzamy, czy pobierając wyznaczone bloki nie wykroczymy poza rozmiar urządzenia, je?li tak, to zmniejszamy ilo?ć bloków do pobrania.
7.  Inicjujemy listy bloków bhreq i buflist (bloków do wczytania i bloków z których będziemy kopiować dane do pamięci użytkownika.
8.  Dla kolejnych bloków:
 
8.1.  Sprawdzamy, czy blok jest w pamięci podręcznej.
8.2.  Je?li bloku nie ma w pamięci, to dodajemy go do listy bloków, które należy zglosić do wczytania (lista bhreq).
8.3.  Dodajemy blok do listy bloków, które mają być skopiowane do pamięci użytkownika (lista buflist).
9.  żądamy wczytania bloków z listy do wczytania (lista bhreq). Lista nie będzie nam już potrzebna.
10.  Kopiujemy kolejno bloki z listy bloków do pamięci użytkownika. Blok pierwszy kopiujemy tylko od miejsca, w którym zaczyna się fragment danych żądany przez użytkownika, a ostatni tylko do miejsca, w którym ten fragment się kończy. Blok z którego zakończyli?my kopiowanie zostaje zwalniany i usuwany z listy buflist
11.  Zwalniamy wszytkie bloki, z które mamy na li?cie buflist, poniewaY nie będziemy z nich korzystać.
12.  Zwracamy ilo?ć wczytanych bajtów (lub błąd je?li odczyt z urządzenia się nie udał).

      Ze względu na to, że listy bhreq, buflist mają ograniczony rozmiar, kroki 7, 8, 9, 10 powtarzane są w pętli, tak długo, aż wczytana zostanie cało?ć danych. Także je?li w kroku 10, wystąpią jakie? nieprawidłowo?ci związane z odczytem, algorytm zostanie przerwany. Przerwanie algorytmu polega na przej?ciu do kroku 11.

Spis treści

Schemat działania algorytmu block_write

      Algorytm ten oparty jest na podobnych zasadach co algorytm block_read, jednak ponieważ z operacją zapisu mamy (statystycznie) do czynienia dużo rzadziej niż z operacją odczytu Wbrew pozorom algorytm, może wykonać się całkowicie, nie wykonując ani jednego zapisu do urządzenia.
 
1. Sprawdzenie, czy użytkownik może zapisywać do urządzenia.
2. Pobranie rozmiaru bloku dla urządzenia
3. Obliczenie, od którego miejsca będziemy zapisywać
4. Obliczenie, ile miejsca jest na urządzeniu do którego będziemy zapisywać 
5. Tak długo, aż nie zapiszemy wszystkich danych:
 
5.1. Je?li aktualny blok jest poza urządzeniem zgłaszamy błąd braku miejsca do zapisu (ENOSPC) 
5.2. Sprawdzamy ile bajtów należy zapisać do aktualnego bloku (warto?ć ta tylko dla pierwszego i ostatniego bloku może być różna od blocksize)
5.3. Pobieramy bufor bloku do którego chcemy zapisywać. Je?li operacja się nie powiodła kończymy.
5.4. Je?li nie jest wypełnony aktualnymi danymi, a ilo?ć danych do zapisu w tym buforze jest różna od blocksize, to musimy uzupełnić jego zawarto?ć. 
 
5.4.1. Sprawdzamy, czy dla urządzenia ustawiona jest flaga f_reada. Je?li nie to wczytujemy z urządzenia tylko zawarto?ć aktualnego bloku. Je?li tak, to taże kilku następnych bloków starając się wczytać ich dokładnie tyle ile ustawionych jest dla używanego urządzenia w tablicy read_ahaead.
5.5. Zwiększamy liczniki zapisanych bloków i bajtów.
5.6 Modyfikujemy zawarto?ć buforu aktualnie zapisywanego bloku.
5.7 Oznaczamy bufor jako brudny (wymagający zapisania na dysku).
5.8 Je?li ustawiona jest flaga O_SYNC synchronicznego zapisu dodaje bufor bloku do listy buforów do zapisanie, je?li nie to zwalnia bufor bloku.
5.9 Je?li wypełni się lista buforów do zapisania wywoływana jest funkcja ll_rw_block, która ma za zadanie wydać zlecenie zapisu bloków na dysk.
6. Je?li lista buforów do zapisania nie jest pusta wykonujemy polecenie ll_rw_block. Może to mieć miejsce wtw. gdy dla urządzenia ustawiona jest flaga O_SYNC. 
7. Zwracamy ilo?ć zapisanych bajtów bądY kod błędu który wystąpił.
      Jak wynika z tre?ci algorytmu nie zajmuje się on zapisem na dysk. Je?li ustawiona jest flaga O_SYNC zleca to funkcji ll_rw_block, która zgłasza żądanie zapisu do algorytmu szeregującego żądania.
      Je?li jednak flaga O_SYNC nie jest ustawiona, zapis wykonywany jest dopiero, gdy zabraknie miejsca w pamięci podręcznej urządzenia blokowego, bądY zdecyduje o tym algorytm optymalizujący pracę z urządzeniem.
Spis treści

Implementacja algorytmu block_read

      Poniżej zaprezentowany jest kompletny kod funkcji block_read, użyty w jądrze 2.4.7 Linuxa. Implementacja przepleciona jest z dokładnym opisem. Tak naprawde zalecane jest odwoływać się do niej w momencie, gdy zainteresuje nas co? w kodzie Yródłowym, ponieważ z powodu dużej ilo?ci opisów sam kod jest bardzo nieczytelny.

Pobierane parametry:

  • flip wskazuje na struturę file z informacjami o urządzeniu do czytania;
  • buf wskazuje na obszar pamięciu użytkownika, w którym należy umie?cić wczytane dane;
  • count jest ilo?cią bajtów do odczytania;
  • loff_t wskaznik na zmienną zawierającą przesunięcie w pliku urządzenia, przeważnie wskazuje na flip->f_pos.
ssize_t block_read(struct file * filp, char * buf, size_t count, loff_t *ppos)
{
Zmienna inode jest potrzebna tylko po to, aby pobrać numer główny i podrzędny urządzenia. 
        struct inode * inode = filp->f_dentry->d_inode;
Zmienne potrzebne do obliczania ilo?ci bloków, aktualnej pozycji (aktualnie kopiowanego bajtu) w kopiowanym bloku. 
        size_t block;
        loff_t offset;
        ssize_t blocksize;
        ssize_t blocksize_bits, i;
        size_t blocks, rblocks, left;
Zmienne do operacji na listach, a także miejsce w pamięciu na n-elementowe listy. 
        int bhrequest, uptodate;
        struct buffer_head ** bhb, ** bhe; 
        struct buffer_head * buflist[NBUF];     
        struct buffer_head * bhreq[NBUF];
Pozostałe zmienne: 
        unsigned int chars;
        loff_t size;
        kdev_t dev;
        ssize_t read;
Pobranie informacji o urządzeniu z któego będziemy czytać. Tak naprawde jest to probranie numerów głównego i podrzędnego urządzenia. Ze zmiennej dev informacje te uzyskane mogą być makrodefinicjami MAJOR i MINOR. 
        dev = inode->i_rdev;
Probranie rozmiaru bloku dla urządzenia. Jak wiemy z urządzenia dane mogą być czytane tylko w blokach, których rozmiary są okre?lone dla każdego urządzenia. Najpierw ustawiany jest domy?lny rozmiar bloku BLOCK_SIZE (1024 bajty). Je?li dla urządzenia głównego zdefiniowana jest tablica rozmiarów bloków urządzeń podrzędnych i w tej tablicy wpisany jest rozmiar bloku dla interesującego nas urządzenia, to zmieniamy blocksize na rozmiar pobrany z tablicy.
Warto zwrócić uwagę, że kod pisany jest optymalnie, ponieważ konstrukcja:
if ... then ... else blocksize = BLOCK_SIZE;
teoretycznie oszczędziła by jedno przypisanie, ale tak naprawdę byłaby kosztowniejsza do zapisania w języku niskopoziomowym (przez kompilator) - wymagałaby dodatkowego skoku. ?wiadczy to o tym, że nawet w takich szczegółach implementacyjnych autor (sam Linus Torvalds) zwracał uwagę na optymalizacje kodu. Co prawda optymalizacja praktycznie nie ma wpływu na szybko?ć działania systemu, ale ?wiadczy o stylu programowania. 
        blocksize = BLOCK_SIZE;
        if (blksize_size[MAJOR(dev)] && blksize_size[MAJOR(dev)][MINOR(dev)])
                blocksize = blksize_size[MAJOR(dev)][MINOR(dev)];
Obliczenie warto?ci logarytmu o podstawie 2 z rozmiaru bloku, czyli ilo?ci bitów, które zajmuje blok. Ponieważ rozmiary bloków są potęgami dwójki informacja taka wykorzystana zostanie do dzielenia ilo?ci bajtów przez rozmiar bloku (obliczania ilo?ci bloków, które należy wczytać).
  
        i = blocksize;
        blocksize_bits = 0;
        while (i != 1) {
                blocksize_bits++;
                i >>= 1;
        }
   blocksize = 1024, 
warto?ci w tabelce przy opuszczaniu pętli, 
blocksize_bits 1 2 3 4 5 6 7 8 9 10
i 512 256 128 64 32 16 8 4 2 1
Pobranie pozycji od której będziemy czytać dane w urządzeniu. Następnie z tablicy blk_size, pobieramy ilo?ć bajtów, które mogą być pobrane z urządzenia. Ilo?ć ta jest w tej tablicy zapisana w jednostkach po 2^BLOCK_SIZE_BITS bajtów. 
        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;
Ustalamy ile bajtów zostało nam do przeczytania z urządzenia: zmienna left. Je?li wskaYnik miejsca do odczytu wykracza poza rozmiar urządzenia, to nie odczytamy żadnych bajtów. Możemy wczytać tylko MAX_INT bajtów (typ zmiennej left może nie zmie?cić większej liczby), więc je?li różnica size - offset przekracza tą warto?ć, to jest do niej skracana. Je?li nie to ilo?c bajtów bajtów, które można wczytać z urządzenia ustawiana jest na size - offset. 
        if (offset > size)
                left = 0;
        /* size - offset might not fit into left, so check explicitly. */
        else if (size - offset > INT_MAX)
                left = INT_MAX;
        else
                left = size - offset;
Je?li możemy wczytać więcej bajtów niż nas interesuje, to zmniejszamy zmienną left do zmiennej count. Powoduje to, że kbd jest ilo?cią bajtów, jaka nas interesuje i jaką damy radę wczytać z urządzenia. Je?li jest ona <= 0 to zwracamy warto?ć 0, czyli ilo?ć bajtów, które wczytali?my z urządzenia. Większej ilo?ci nie wczytamy, ponieważ albo nie damy rady, albo użytkownik wła?nie o tyle prosił. 
        if (left > count)
                left = count;
        if (left <= 0)
                return 0;
Wczytaną ilo?ć bajtów ustawiamy na 0.
Obliczamy pierwszy blok z którego rozpoczniemy czytanie z urządzenia (po prostu usuwamy ostatnich blocksize_bits bitów ze zmiennej offset).
 
321 322 323 324 326 327 328 329
     
Kolorem niebieskim zaznaczony jest fragment danych, którym zainteresowany jest programista. Jak widzimy, aby go odczytać musimy zarządzać bloków od 324 do 238. Ponieważ rozmiar bloku jest potęgą dwójki to, tak wygląda rozkład bitów zmiennej offset:
 
0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 1 0 0 1 0 1 0 0 1 1 0 1 0

W zmiennej offset zostawiamy tylko ostatnich blocksize_bits. Operacja bitowa & (AND) porównuje bity zapisie bitowym dwóch liczbach. Liczba offset porównywana jest z liczbą blocksize = 2^blocksizebits pomniejszoną o jeden. Wiemy, że suma dla i od 0 do n-1 czynników 2^i = 2^n - 1, co powoduje, że 2^n-1 ma w zapisie binarnym n kolejnycn jedynek.

Do zmiennych rblocks, blocks wpisujemy ilo?ć bloków do przeczytania. Przesunięcie w prawo, jest to dzielenie bez reszty, zatem samo (left + offset) / blocksize spowodowało by możliwo?c pominięcia ostatniego bloku, (left + offset + blocksize) / blocksize spowodowało by możlio?ć czytania o jeden blok za dużo. 

        read = 0;
        block = offset >> blocksize_bits;
        offset &= blocksize-1;
        size >>= blocksize_bits;
        rblocks = blocks = (left + offset + blocksize - 1) >> blocksize_bits;
Ustawiamy początek i koniec listy na buflist, teraz mamy do wykorzystania n kolejnych miejsc listy do wypełnienia. 
        bhb = bhe = buflist;
Je?li dla urządzenia ustawiona jest flaga czytania z wyprzedzeniem, to sprawdzamy, czy nie chcemy wczytać mniej niż minimalnej opłacalnej ilo?ci bloków z urządzenia. Warunek rblocks > blocks nigdy nie zostanie spłniony, chyba, że kompilator Yle zinterpretuje poprzednie porównanie. 
        if (filp->f_reada) {
                if (blocks < read_ahead[MAJOR(dev)] / (blocksize >> 9))
                        blocks = read_ahead[MAJOR(dev)] / (blocksize >> 9);
                if (rblocks > blocks)
                        blocks = rblocks;
                
        }
Je?li wyszli?my poza urządzenie, to zmniejszamy ilo?ć bloków do odczytania do tylu ile nam zostało. Je?li nie zostało już nic do czytania, to zwracamy 0, jako jedyny możliwy wynik działania funkcji. 
        if (block + blocks > size) {
                blocks = size - block;
                if (blocks == 0)
                        return 0;
        }
Tutaj rozpoczyna się wczytywanie danych z urządzenia. 
        /* We do this in a two stage process.  We first try to request
           as many blocks as we can, then we wait for the first one to
           complete, and then we try to wrap up as many as are actually
           done.  This routine is rather generic, in that it can be used
           in a filesystem by substituting the appropriate function in
           for getblk.

           This routine is optimized to make maximum use of the various
           buffers and caches. */
Pętlę powtarzamy tak długo, jak długo będą jeszcze jakie? dane do wczytania z urządzenia. 
        do {
W poniższej pętli ustawiamy kolejno na li?cie buflist bufory bloków które będziemy chcieli odczytać. Adres bloku w pamięci zawsze zwróci nam funkcja getblk, je?li jednak nie będzie danego bloku w pamieci, to ustawimy go do kolejki bhreq. 
                bhrequest = 0;          // liczba buforów bloku do do wczytania
                uptodate = 1;           // żeby wykryć, możemy od razu kopiować bufor do pamięci
                while (blocks) {
                        --blocks;
                        *bhb = getblk(dev, block++, blocksize);
*bhb zawsze musi być różne od NULL, a !buff_uptodate(*kbd) zwraca warto?ć true je?li bufor nie zawiera poprawnych danych. 
                        if (*bhb && !buffer_uptodate(*bhb)) {
                                uptodate = 0;
                                bhreq[bhrequest++] = *bhb;
                        }

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

                        /* If the block we have on hand is uptodate, go ahead
                           and complete processing. */
Je?li update == 1, to znaczy że ten blok możemy już zacząć kopiować do pamieci użytkownika. Być może w tym czasie z urządzenia wczytane zostaną kolejne bloki. Jest to wła?nie jeden z istotnych elementów optymalizacji czytania. 
                        if (uptodate)
                                break;
Je?li bhb == bhe, to znaczy, że na li?cie (cyklicznej) buflist zrobili?my koło i wszystkie jej pozycje zajęte są nie skopiowanymi do pamięci użytkownika buforami bloków. Przerwyamy wyznaczanie bloków w celu ich skopiowania do pamięci użytkownika. 
                        if (bhb == bhe)
                                break;
                }
Tutaj zgłaszamy pro?bę o wypełnienie nie uzupełnionych buforów blokami z urządzenia. Zauważmy, że lista bhrequest nie jest cykliczna. Jest zerowana za każdym razem, gdy rozpoczynamy pętlę wyznaczającą bufory do kopiowania, a jej rozmiar jest taki sam jak buflist, co gwarantuje, że nie wykroczymym poza jej zakres (bufor znajdujący się w bhreq musi znajdować się w buflist). 
                /* Now request them all */
                if (bhrequest) {
                        ll_rw_block(READ, bhrequest, bhreq);
                }
Powtarzamy tą pętle tak długo, aż wczytamy wszystko, wczytamy zawarto?ć wszystkich wyznaczonych buforów, bądY trafimy na nie wczytany do końca bufor na li?cie buforów do kopiowania. W takiej sytuacji, możemy skorzystać z chwili w której czekamy na dane od urządzenia i złożyć zamówienie na nowe bloki w miejsce tych, które zdążyli?my zwolnić. Wła?nie dlatego w tej procedurze przesuwamy się po li?cie wskaznikiem bhe, czyli wskaYnikiem końca listy. 
                do { /* Finish off all I/O that has actually completed */
                        if (*bhe) {
Je?li bhe reprezentuje sobą blok pamięci, to czekaj, aż zakończy się transfer danych pomiędzy urządzeniem a buforem (nie czekamy w ogóle, je?li bufor już jest w pamięci, dlatego wła?nie staramy się takie bufory kopiować od razu, pozwalając aby te, wymagające czekania wczytały sie w międzyczasie). 
                                wait_on_buffer(*bhe);
                                if (!buffer_uptodate(*bhe)) {   /* read error? */
Je?li czekanie się skończyło, a bufor nie jest aktualny, oznacza to, że nastąpił błąd odczytu z urządzenia. Zwalniamy bufor i kończymy pętlę. Przed wyj?ciem z pętli zerujemy liczbę bajtów, która nam została do wczytania, co spowoduje, że przerwiemy czytanie. 
                                        brelse(*bhe);
                                        if (++bhe == &buflist[NBUF])
                                          bhe = buflist;
                                        left = 0;
                                        break;
                                }
                        }
Czy pozostałe bajty mieszczą się we fragmencie od pozycji offset w aktualnym buforze do końca aktuanego bufora (czy wszystko mie?ci się w aktualnym buforze). Je?li tak to chars czyli ilo?ć znaków do skopiowania z bufora ustawiamy na tyle ile bajtów nam zostało, je?li nie, to kopiujemy wszystko od aktuanej pozycji do końca bufora. 
                        if (left < blocksize - offset)
                                chars = left;
                        else
                                chars = blocksize - offset;
Zwiększamy pozycję w pliku,
zmniejszamy ilo?ć bajtów, które zostały nam do wczytania,
zwiększamy ilo?ć przeczytanych bajtów. 
                        *ppos += chars;
                        left -= chars;
                        read += chars;
Je?li bufor bloku istnieje w pamięci, to kopiujemy jego zawarto?ć do pamięci użytkownika, je?li nie istnieje to wypełniamy ją zerami. 
                        if (*bhe) {
                                copy_to_user(buf,offset+(*bhe)->b_data,chars);
                                brelse(*bhe);
                                buf += chars;
                        } else {
                                while (chars-- > 0)
                                        put_user(0,buf++);
                        }
Ustawiamy się na początku następnego bufora. Je?li wyszli?my poza tablicę buflist z pomocą której zaimplementowana jest lista cykliczna, to wracamy na jej początek. 
                        offset = 0;
                        if (++bhe == &buflist[NBUF])
                                bhe = buflist;
                } while (left > 0 && bhe != bhb && (!*bhe || !buffer_locked(*bhe)));
Je?li wczytali?my wszystkie bloki to przerwyamy pętlę. 
                if (bhe == bhb && !blocks)
                        break;
        } while (left > 0);
Zwalnianie wszystkich bloków znajdujących się na liście buforów do oczytu. Przeważnie zwalniamy bufory bloków, których zażądaliśmy w ramach czytania z wyprzedzeniem. Jeśli podczas odczytu nastąpi błąd, to pętla zwolni bloki, których sobie zażyczyli?my do odczytu. 
/* Release the read-ahead blocks */
        while (bhe != bhb) {
                brelse(*bhe);
                if (++bhe == &buflist[NBUF])
                        bhe = buflist;
        };
Je?li nic nie przeczytali?my, to zwracamy błąd wej?cia/wyj?cia, ponieważ wszystkie warianty, w których 0 odczytanych bajtów jest wynikiem nie spowodowanym blędem zostały przedtem rozważone. 
        if (!read)
                return -EIO;
Ustawiamy flagę czytania z wyprzedzeniem dla urządzenia, ponieważ jak co? się zdarzy dwa razy, to najprawdopodobniej zdarzy się też trzeci raz. 
        filp->f_reada = 1;
        return read;
}
Spis treści

Implementacja algorytmu block_write.

      Poniżej znajduje się implementacja algorytmu block_write przepleciona z dokładnym opisem. Tak naprawde zalecane jest odwoływać się do niej w momencie, gdy zainteresuje nas co? w kodzie Yródłowym, poniważ z powodu dużej ilo?ci opisów sam kod jest bardzo nieczytelny.

Pobierane parametry:

  • flip wskazuje na struturę file z informacjami o urządzeniu do zapisu;
  • buf wskazuje na obszar pamięciu użytkownika, z którego pobrać dane do zapisu;
  • count jest ilo?cią bajtów do zapisania;
  • loff_t wskaznik na zmienną zawierającą przesunięcie w pliku urządzenia, przeważnie wskazuje na flip->f_pos.
ssize_t block_write(struct file * filp, const char * buf,
                    size_t count, loff_t *ppos)
{
Zmienna inode jest potrzebna tylko po to, aby pobrać numer główny i podrzędny urządzenia. 
        struct inode * inode = filp->f_dentry->d_inode;
Zmienne kolejno oznaczające bądY używane do: rozmiar bloku dla urządzenia do zapisu, ilo?ć bitów w zapisie tego rozmiaru, zmienna pomocnicza, zmienna do pamiętania czy wystąpił błąd zapisu, zmienna pamiętająca numer aktualnie zapisywanego bloku w urządzaniu, ilo?ć bloków do zapisania, ilo?ć znaków do zapisania, znaków zapisanych i warto?ć wyniku funkcji. 
        ssize_t blocksize, blocksize_bits, i, buffercount, write_error;
        ssize_t block, blocks;
        loff_t offset;
        ssize_t chars;
        ssize_t written, retval;
Lista buforów do wczytania w przypadku czytania z wyprzedzeniem, rozmiar urządzenia (ilo?ć bloków urządzenia) i informacje o urządzeniu. 
        struct buffer_head * bhlist[NBUF];
        size_t size;
        kdev_t dev = inode->i_rdev;
Lista buforów bloków do zapisania w przypadku, gdy ustawiona jest flaga O_SYNC, i zmienna pomocnicza p, która ma być rejestrem (o?mio bitowym), ponieważ pełni któtko swoją funkcję i nie musi być pamiętana. 
        struct buffer_head * bh, *bufferlist[NBUF];
        register char * p;
Sprawdzenie, czy urządzenie nie jest tylko do oczytu, czyli czy można po nim pisać. Je?li nie zwracamy błąd EPERM. 
        if (is_read_only(dev))
                return -EPERM;
Inicjujemy zmienne na 0, i obliczamy rozmiar bloku urządzenia. Domy?lny, albo okre?lony w tablicy blksize_size. 
        retval = written = write_error = buffercount = 0;
        blocksize = BLOCK_SIZE;
        if (blksize_size[MAJOR(dev)] && blksize_size[MAJOR(dev)][MINOR(dev)])
                blocksize = blksize_size[MAJOR(dev)][MINOR(dev)];
Obliczamy ilo?ć bitów w zapisie rozmiaru bloku. Rozmiar bloku jest potęgą dwójki, ułatwi nam to dzielenie i pobieranie reszty z dzielenia przez rozmiar bloku (dokładniejszy opis w implementacji algorytmu block_read). 
        i = blocksize;
        blocksize_bits = 0;
        while(i != 1) {
                blocksize_bits++;
                i >>= 1;
        }
Wyznaczamy pierwszy blok, do którego będziemy zapisywać i dokładną pozycję w tym bloku od której rozpoczniemy zapis (dokładniejszy opis przy wyznaczaniu początku odczytu w block_read). 
        block = *ppos >> blocksize_bits;
        offset = *ppos & (blocksize-1);
Pobieramy rozmiar urządzenia do którego będziemy zapisywać. Mimo iż jeste?my w tym momencie stwierdzić czy starczy nam miejsca do zapisania cało?ci danych na urządzeniu nie robimy tego, tylko czekamy, aż numer zapisywanego bloku wykroczy poza zakres. 
        if (blk_size[MAJOR(dev)])
                size = ((loff_t) blk_size[MAJOR(dev)][MINOR(dev)] << BLOCK_SIZE_BITS) >> blocksize_bits;
        else
                size = INT_MAX;
Dopóki jest jeszcze co? do zapisania... 
        while (count>0) {
Je?li aktualnie ropatrywany blok jest poza urządzeniem (przekroczyli?my rozmiar urządzenia), to zgło? błąd braku miejsca na urządzeniu (ENOSPC). 
                if (block >= size) {
                        retval = -ENOSPC;
                        goto cleanup;
                }
Najpierw do chars wstawiamy ile bajtów możemy zapisać w bieżącym bloku, a następnie sprawdzamy, czy nie jest to więcej niż chemy zapisać. W ten sposób ustalamy, ile bajtów zapiszemy w bieżącym bloku. 
                chars = blocksize - offset;
                if (chars > count)
                        chars=count;
Poniższy fragment kodu jest skróconym zapisem tego, co ma wykonać fragment po else. Fragment po else wzbogacony został o czytanie z wyprzedzeniem. Mimo iż w praktyce jest on pomijany przez kompilator warto go zrozumieć.

Głównym celem tego fragmentu jest wyznaczenie obszaru bufora bloku w pamięci komputera, tak, aby dalsza czę?ć procedury mogła wypełnić go danymi z pamięci użytkownika. Je?li jest to pierwszy lub ostatni z zapisywanych buforów, to nie zostanie on wypełniony w cało?ci nowymi danymi, musi przedtem zostać więc wczytany z urządzenia, żeby nie utracić wcze?niej zapisanych danych. 

#if 0
                /* get the buffer head */
                {
Je?li chars != blocksize, to znaczy, że nie zapiszemy całego bufora, więc jako funkcję pobierającą adres do bufora przypisujemy bread, co spowoduje, że je?li aktualnej zawarto?ci bloku nie ma w buforze, to zostanie ona wczytana. Je?li zapisujemy cały blok, to nie interesuje nas jego zawarto?ć. Wystarczy, że pobierzemy adres bufora w pamięci, mogą w nim być dane nieaktualne. Używamy wtedy funkcji getblk. 
                        struct buffer_head * (*fn)(kdev_t, int, int) = getblk;
                        if (chars != blocksize)
                                fn = bread;
Pobieramy adres bufora. Je?li się nie uda, to ustawiamy, że operacja pisania zakończyła się błędem wej?cia/wyj?cia i kończymy 
                        bh = fn(dev, block, blocksize);
                        if (!bh) {
                                retval = -EIO;
                                goto cleanup;
                        }
Je?li trwa transfer danych pomiędzy urządzeniem a buforem, to musimy poczekać aż zostanie zakończony (najprawdopodobniej bufor wypełnia się aktualnymi danymi). 
                        if (!buffer_uptodate(bh))
                                wait_on_buffer(bh);
                }
#else
Poniższy fragment kodu realizuje to samo co fragment przed else. Je?li jednak musimy odczytać jaki? blok z urządzenia (pierwszy lub ostatni) to czytamy od razu kilka bloków je?li ustawiona jest flaga czytania z wyprzedeniem dla urządzenia.

Najpierw i tak musimy pobraćadres bufora bloku. W przypadku błędu kończymy funkcje, zgłaszając błąd wej?cia/wyj?cia. 

                bh = getblk(dev, block, blocksize);
                if (!bh) {
                        retval = -EIO;
                        goto cleanup;
                }
Je?li bufor nie jest wypełniony aktualnymi danymi... 
                if (!buffer_uptodate(bh))
                {
... to chcąc zapisać cały bufor musimy tylko poczekać, aż zakończy się ewentualny transfer danych z urządzenia do bufora... 
                  if (chars == blocksize)
                    wait_on_buffer(bh);
                  else
                  {
Je?li jednak chcemy wypełnić tylko fragment buforu to musimy wczytać zawarto?ć bloku z urządzenia, uwzględniając przy tym flagę odczytu z wyprzedzeniem. Tworzymy zatem listę buforów które będziemy chcieli wczytać. Jako pierwszy na tej li?cie jest nasz bufor (bloku który chcemy zapisać). 
                    bhlist[0] = bh;
                    if (!filp->f_reada || !read_ahead[MAJOR(dev)]) {
Je?li flaga nie jest ustawiona to czytamy tylko jeden (nasz) blok. 
                      /* We do this to force the read of a single buffer */
                      blocks = 1;
                    } else {
Je?li jednak flaga jest ustawiona, to wyznaczamy ile bloków przypada na czytanie z wyprzedzeniem dla urządzenia. Przypominam, że warto?c ta jest zapisana w tablicy read_ahead indeksowanej głównym numerem urządzenia, a rozmiar danych do wczytania z wyprzedzeniem jest wyrażony w jednostkach po 512 bajtów. Rozmiar ten zamieniamy na rozmiar wyrażony w blokach urządzenia. 
                      /* Read-ahead before write */
                      blocks = read_ahead[MAJOR(dev)] / (blocksize >> 9) / 2;
Sprawdzamy, czy przy czytaniu nie wypadniemy poza rozmiar urządzenia. 
                      if (block + blocks > size) blocks = size - block;
I czy ilo?ć żadanych bloków mie?ci się w kolejce NBUF. 
                      if (blocks > NBUF) blocks=NBUF;
W przypadku błędnego wypełnienia tablicy read_ahead może zdarzyć się, że ilo?ć bloków do odczytu będzie równa 0. Musimy obsłużyć ten przypadek. 
                      if (!blocks) blocks = 1;
Dla każdego buforu bloku który mamy na li?cie do wczytania, pobieramy jego adres z pamięci. Je?li się to nie powiedzie dla którego? bloku to zwalniamy wszystkie pozostałe bloki i kończymy zgłaszając błąd wej?cia/wyj?cia. 
                      for(i=1; i < blocks; i++)
                      {
                        bhlist[i] = getblk (dev, block+i, blocksize);
                        if (!bhlist[i])
                        {
                          while(i >= 0) brelse(bhlist[i--]);
                          retval = -EIO;
                          goto cleanup;
                        }
                      }
                    }
Je?li się powiedzie, to żądamy wczytania wszystkich bloków. 
                    ll_rw_block(READ, blocks, bhlist);
Potem zwalniamy wszystkie bloki, oprócz pierwszego (pod indeksem 0), bo tylko on nam jest potrzebny. 
                    for(i=1; i < blocks; i++) brelse(bhlist[i]);
Czekamy, aż zakończy się transfer danych pomiędzy buforem a urządzeniem. Je?li po zakończeniu transferu bufor nie będzie wypełniony aktualnymi danymi to zgłaszamy błąd wej?cia/wyj?cia. Kończymy algorytm. 
                    wait_on_buffer(bh);
                    if (!buffer_uptodate(bh)) {
                          brelse(bh);
                          retval = -EIO;
                          goto cleanup;
                    }
                  };
                };
#endif
Zwiększamy licznik zapisanych bloków, wskaYnik w pliku, wskaYnik w aktualnym bloku ustawiamy na 0 (znajdujemy się teraz na początku następnego bloku, albo skończymy czytanie). Kopiujemy dane z pamięci urzytkownika do bufora bloku. 
                block++;
                p = offset + bh->b_data;
                offset = 0;
                *ppos += chars;
                written += chars;
                count -= chars;
                copy_from_user(p,buf,chars);
                p += chars;
                buf += chars;
Zaznaczamy, że bufor jest wypełniony aktualnym i danymi i że wymaga zapisu na dysk (jest brudny - dirty). 
                mark_buffer_uptodate(bh, 1);
                mark_buffer_dirty(bh);
Je?li urządzenie pracuje w trybie zapisu synchronicznego, to dodajemy bufor do listy buforów do zapisania na dysku. 
                if (filp->f_flags & O_SYNC)
                        bufferlist[buffercount++] = bh;
                else
Je?li nie, to zwalniamy bufor. Zostanie on zapisany na dysku w momencie w którym zdecyduje o tym specjalny proces odpowiedzialny za zarządzaniem urządzeniem. 
                        brelse(bh);
Je?li wypełni się kolejka buforów do zapisania (możliwe tylko w trybie zapisu synchronicznego) to wydajemy polecenie zapisu wszystkich buforów z listy i czy?cimy liste. 
                if (buffercount == NBUF){
                        ll_rw_block(WRITE, buffercount, bufferlist);
                        for(i=0; i < buffercount; i++){
                                wait_on_buffer(bufferlist[i]);
                                if (!buffer_uptodate(bufferlist[i]))
                                        write_error=1;
                                brelse(bufferlist[i]);
                        }
                        buffercount=0;
                }
Wywołujemy funkcję odpowiedzialną o zarządzanie zapisywaniem na dysk. 
                balance_dirty(dev);
Je?li gdzie? wcze?niej zgłosili?my błąd zapisu, to przerywamy zapis. 
                if (write_error)
                        break;
        }
Zwalniamy wszystkie bufory w kolejce buforów do zapisanie (tylko tryb asynchroniczny). 
        cleanup:
        if ( buffercount ){
                ll_rw_block(WRITE, buffercount, bufferlist);
                for(i=0; i < buffercount; i++){
                        wait_on_buffer(bufferlist[i]);
                        if (!buffer_uptodate(bufferlist[i]))
                                write_error=1;
                        brelse(bufferlist[i]);
                }
        }
Ustawiamy flagę odczytu z wyprzedzeinem, ponieważ je?li próba zapisu (odczytu z urządzenia) się powtórzy, bedzie podejrzenie pracy sekwencyjnej urządzenia. Zwracamy błąd wej?cia/wyj?cia je?li gdzie? wcze?niej wystąpił błąd zapisu. Na wyniku podajemy ilo?ć zapisanych bajtów. 
        if(!retval)
                filp->f_reada = 1;
        if(write_error)
                return -EIO;
        return written ? written : retval;
}
Spis treści

Podsumowanie.

      Algorytmy wykorzystują mechanizm optymalizujący czytanie i pisanie do urządzeń. Obliczają które bloki z urządzenia należy pobrać, które wystarczy tylko zapisać. Starają się (zwłaszcza block_read) maksymalnie wykorzytać fakt, że transfer danych pomiędzy urządzeniem a pamięcią nie zajmuje procesora. Korzystają tylko z cech charakterystycznych dla urządzeń blokowych, dlatego podmieniając kod procedur do wypełniania buforów bloków danymi z urządzenia możemy nimi obsługiwać dowolne urządzenie blokowe. Nawet operacje kopiowania danych w pamięci pozostawiają odpowiednim funkcjom systemu co powoduje, że wykorzystują maksymalnie jego możliwo?ci.