% Impala Operating System
%
% Copyright (C) 2009 University of Wroclaw. Department of Computer Science
%    http://www.ii.uni.wroc.pl/
% Copyright (C) 2009 Mateusz Kocielski, Artur Koninski, Pawel Wieczorek
%    http://bitbucket.org/wieczyk/impala/
% All rights reserved.
%
% Redistribution and use in source and binary forms, with or without
% modification, are permitted provided that the following conditions
% are met:
% 1. Redistributions of source code must retain the above copyright
%  notice, this list of conditions and the following disclaimer.
% 2. Redistributions in binary form must reproduce the above copyright
%  notice, this list of conditions and the following disclaimer in the
%  documentation and/or other materials provided with the distribution.
%
% THIS SOFTWARE IS PROVIDED BY AUTHOR AND CONTRIBUTORS ``AS IS'' AND
% ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
% IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
% ARE DISCLAIMED.  IN NO EVENT SHALL AUTHOR OR CONTRIBUTORS BE LIABLE
% FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
% DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
% OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
% HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
% LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
% OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
% SUCH DAMAGE.
%
% $Id$

\section{Strumieniowe wejście-wyjście.}

\section{Buforowane wejście-wyjście.} \label{BIO}

Operacje wejścia-wyjścia są na urządzeniach blokowych opisywane przez
nagłówki buforów (\texttt{iobuf\_t}). Każdy nagłówek buforu zawiera
w~sobie następujące pola:
\begin{itemize}
\item \texttt{addr} - adres bufora
\item \texttt{size} - długość bufora w~bajtach
\item \texttt{bcount} - długość bufora w~blokach
\item \texttt{blkno} - logiczny numer bloku
\item \texttt{flags} - znaczniki
\item \texttt{errno} - numer błędu
\item \texttt{oper} - kierunek transferu \texttt{BIO\_READ}
    lub~\texttt{BIO\_WRITE}
\item \texttt{resid} - ilość pozostałych bajtów do~przesłania (na~potrzeby
sterowników)
\item \texttt{dev} - deskryptor urządzenia
\item \texttt{sleepq} - śpiąca kolejka
\end{itemize}

Zdefiniowane znaczniki \texttt{iobuf\_t.flags}:
\begin{itemize}
\item \texttt{BIO\_DONE} - operacja wejścia-wyjścia zakończona
\item \texttt{BIO\_ERROR} - wystąpił błąd podczas ostatniej operacji wejścia-wyjścia
\item \texttt{BIO\_VALID} - dane w buforze są prawidłowe
\item \texttt{BIO\_CACHE} - nagłówek jest w tablicy haszującej
\item \texttt{BIO\_BUSY} - nagłówek jest zajęty przez klienta
\end{itemize}

System udostępnia mechanizm buforowanego wejścia-wyjścia, który jest warstwą
pomiędzy swoimi klientami (modułami obsługi systemów plików) a~sterownikami
urządzeń. Mechanizm posługuje się stałą ilością nagłówków buforów, które
oprócz opisywania operacji dla sterowników służą do~zapamiętywania ich wyników.
Zapamiętane dane mogą ograniczyć potrzebę korzystania z~urządzenia.


Należy zwrócić uwagę, że buforowane są operacje wejścia-wyjścia, nie sam
nośnik urządzenia. Ta subtelna różnica objawia się tym, że jeden bufor
może pamiętać ciąg stu sektorów zaczynając od dwudziestego, a drugi bufor
może pamiętać ciąg dziesięciu sektorów zaczynając od pięćdziesiątego tego
samego urządzenia.
Mechanizm nie zapewnia, że buforowanie ,,wspólnych'' sektorów  zawiera
te~same dane. Odpowiedzialność tworzenia sensownych operacji wejścia-wyjścia
spada na~klientów tego mechanizmu.

\subsection{Tablica haszująca.}

W celu przyspieszenia szukania buforów w~pamięci system posługuje się
tablica haszującą, która korzysta z funkcji haszującej zależnej od~adresu
deskryptora urządzenia oraz pierwszego bloku operacji.

\begin{eqnarray*}
 hash(\mbox{\texttt{dev}}, \mbox{{\texttt{blkno}}})
& = &
 h(\mbox{\texttt{adres-deskryptora(dev)}} \times \mbox{({\texttt{blkno}+1)}})\\
 h(k)
& = &
 ((ak + b) \mbox{ mod }p) \mbox{ mod }m
\end{eqnarray*}


Nagłówki są nawlekane na~dwie listy, listę wolnych nagłówków jeżeli z~danego
buforu nikt nie korzysta oraz na listę tablicy haszującej. Przykładowa
tablica jest przedstawiona na rysunku \ref{bio:bufhash}.

\begin{figure}
 \centering
 \includegraphics{work/bio_bufhash}
 \caption{Przykładowa tablica haszująca. Bloczki z~pierwszej kolumny
 oznaczają nagłówki list, a z pozostałych kolumn nagłówki buforów.
 Listy $h[i]$ oznaczają listy tablicy haszującej, a \texttt{free} oznacza
 listę wolnych nagłówków.
}
 \label{bio:bufhash}
\end{figure}

Bufor znajduje się na~wolnej liście tylko wtedy, gdy nie jest używany
przez żadnego klienta. Może on też jednocześnie znajdować się w~tablicy
haszującej, co oznacza że buforuje poprzednio wykonaną operację.

Tablica haszująca oraz lista wolnych buforów znajduje się
w~strukturze \texttt{bufhash}. 

\subsection{Cykl życia nagłówka buforu.}

Stała ilość buforów wymaga ustalenia rygorystycznych zasad posługiwania się
nimi. Każdy nagłówek może być dany jednemu klientowi.

Klient może otrzymać bufor za~pomocą dwóch procedur \texttt{bio\_getblk}
oraz \texttt{bio\_read}. Obydwie pobierają te same argumenty: urządzenie
na którym ma być wykonany transfer, numer logiczny bloku oraz długość, która
musi być wielokrotnością sektora danego urządzenia.

Procedura \texttt{bio\_getblk} przeszukuje najpierw tablicę haszującą
w~celu znalezienia danej operacji. Jeżeli nagłówek jest używany
przez innego klienta, to~klient o~niego proszący jest usypiany
na~śpiącej kolejce \texttt{iobuf\_t.sleepq}. Po obudzeniu procedura jest
restartowana, ponieważ dany nagłówek buforu mógł zmienić buforowaną operację.

Jeżeli odpowiedni bufor nie zostanie znaleziony w~tablicy haszującej
to~nagłówek jest przydzielany z~listy wolnych buforów, jeżeli wzięty nagłówek
znajduje się również w tablicy haszującej (to~znaczy buforuje inną operację
niż my szukamy) to należy go z niej usunąć.

Zdobyty nagłówek buforu jest organizowany przez procedurę \texttt{buf\_alloc},
która sprawdza czy nie należy przydzielić buforu lub zmienić rozmiaru
obecnie przydzielonego. Następnie jest naznaczany flagą \texttt{BIO\_BUSY}
i~zwracany klientowi.

Procedura \texttt{bio\_read} jest nakładką na~wyżej omówioną, jeżeli bufor
nie jest naznaczony flagą \texttt{BIO\_VALID} to~nagłówek jest przekazywany
jako zlecenie do~sterownika urządzenia. W~takim wypadku klient jest blokowany
na~czas wykonania zlecenia.

Operacja zapisu może zostać wykonana za pomocą operacji \texttt{bio\_write},
po wykonaniu działania klient musi zwrócić bufor mechanizmowi używając
procedury \texttt{bio\_release}.

Dla~sterowników urządzeń są dostarczone procedury \texttt{bio\_done}
i \texttt{bio\_error} informujące klientów o~zakończeniu operacji zleconej
przed dany nagłówek. Obydwie procedury budzą klienta oczekującego na~bufor
za~pomocą \texttt{bio\_wait}.

