% 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{Wirtualny system plików (VFS).}
\label{VFS}
% no więc najpierw przydał by się jakiś wstęp, info o tym, czym są pliki, jak
% wygląda ich obsługa od strony użytkownika
% potem o 
\subsection{Pliki od strony użytkownika.}
Interfejs plików jest jednym z najważniejszych interfejsów jakie programy
mają do dyspozycji. W systemach Unixowych pliki reprezentują całą gamę bytów:
\begin{itemize}
\item Pliki w standardowym rozumieniu, jako pewnej długości ciąg bajtów. Jest
to rodzaj pliku, z jakim użytkownik najczęściej ma kontakt, korzystając
z~sytemów plików takich jak FAT, NTFS, UFS, ext3 itd.
\item Urządzenia - zarówno fizycznie istniejące w komputerze, jak i wirtualne.
\item Potoki FIFO.
\item Pliki jako wirtualne byty służące do przekazywania różnych informacji 
z~jądra systemu.
\end{itemize}
Niezależnie od tego, co kryje się pod plikiem, od strony użytkownika posiada
on jednolity interfejs. Najważniejszymi funkcjami wchodzącymi w jego skład są:
\texttt{open}, \texttt{close}, \texttt{read}, \texttt{write}, \texttt{ioctl}
\texttt{fcntl}, \texttt{lseek} i \texttt{fstat}. Otwarty plik w programie jest
identyfikowany przy pomocy deskryptora pliku - zazwyczaj małej liczby nieujemnej.
Jądro systemu posiada związaną z każdym procesem tabelę, służącą do tłumaczenia
deskryptora pliku na strukturę \texttt{file\_t}. Wiele deskryptorów plików może
wskazywać na tą samą strukturę. Oto, jak wygląda \texttt{file\_t}:

\begin{center}
\begin{tabular}{|ll|l|}
\hline
vnode\_t   & *f\_vnode & Wskaźnik na v-węzeł związany z plikiem\\
off\_t     &  f\_offset & Aktualna pozycja kursora w pliku\\
int       &  f\_refcnt & Licznik referencji dla tej struktury\\
int       &  f\_flags & Flagi, początkowo ustawione przez open\\
\hline
\end{tabular}
\end{center}
 
Tak więc wszystkie deskryptory wskazujące na ten sam plik dzielą informacje
takie jak aktualna pozycja kursora oraz flagi pliku. Do pobrania struktury
\texttt{file\_t} na podstawie deskryptora służy funkcja \texttt{f\_get}.
Tablica deskryptorów plików została zrealizowana jako lista kawałków tablicy
o pojemności 32 wpisów.

\subsection{Pliki od strony jądra.}

Ważnym zadaniem jądra systemu operacyjnego jest stworzenie takich warunków,
w których pliki pochodzące z różnych systemów plików mogły być obsługiwane
przez pojedynczy, uniwersalny interfejs. Takie właśnie zadanie spełnia
VFS - wirtualny system plików. Zarówno pojęcie pliku jak i systemu plików
zostało ujęte w ramy ściśle zdefiniowanych struktur jądra, ukrywających
prawdziwą implementację powiązanych z nimi operacji. Pliki są reprezentowane
przez strukturę \texttt{vnode\_t}, natomiast systemy plików poprzez 
\texttt{vfs\_t}. Projekt VFS-a zawarty w Impali bazowany był na tym z SVR4.
\subsubsection{V-węzły}
Aby móc zrozumieć funkcjonowanie wirtualnego systemu plików, ważną jest
znajomość struktury, do której odnosi się większość operacji.
Oto jak wygląda v-węzeł:

\begin{center}
\begin{tabular}{|l l| l|}
\hline
int            &~v\_type        & typ v-węzła\\
int            &~v\_flags       & flagi v-węzła\\
int            &~v\_refcnt      & licznik referencji\\
vfs\_t         &*v\_vfs\_mounted\_here & system plików tutaj zamontowany\\
vfs\_t         &*v\_vfs         & system plików tego vnode\\
vnode\_ops\_t  &*v\_ops         & wskaźnik do \texttt{vnode\_ops} z tego fs\\
devd\_t        &*v\_dev         & urządzenie, jeśli to v-węzeł urządzenia\\
void           &*v\_private     & prywatne dane systemu plików, np. i-węzeł\\
mutex\_t       &~v\_mtx         & blokada do synchronizacji\\
\hline
\end{tabular}
\end{center}

Impala posiada następujące typy v-węzłów:
\begin{center}
\begin{tabular}{lcl}
VNODE\_TYPE\_REG & - &zwykły plik \\
VNODE\_TYPE\_DIR & - &plik reprezentujący katalog \\
VNODE\_TYPE\_DEV & - &plik reprezentujący urządzenie \\
VNODE\_TYPE\_LNK & - &plik będący dowiązaniem symbolicznym \\
VNODE\_TYPE\_FIF & - &plik reprezentujący potok \\
\end{tabular}
\end{center}

Operacje możliwe do wykonania na v-węźle ukryte są w strukturze
\texttt{vnode\_ops\_t} dostarczanej dla każdego v-węzła przez związany z nim
system plików. Struktura ta zawiera wskaźniki do funkcji wykonujących wszystkie
przewidziane przez nas operacje, jakie są możliwe do wykonania na pliku.
Szczegółowo została ona przedstawiona w tabeli \ref{vnodeops}.

Dla wygody korzystania z v-węzłów dla każdej z operacji wprowadzono
odpowiednie makro \texttt{VOP\_XXX(v, ...)} wykonujące operację \texttt{XXX}
na v-węźle \texttt{v}.
Dla dalszego ułatwienia pracy z v-węzłami, wprowadzono następujące ogólne
procedury:
\begin{itemize}
\item \texttt{vnode\_opendev} - otwiera vnode urządzenia o podanej nazwie
\item \texttt{vnode\_rdwr}, \texttt{vnode\_urdwr} - wykonują operacje odczytu
i zapisu do danego v-węzła
\item \texttt{vnode\_stat} - pobiera różne informacje o pliku
\item \texttt{vnode\_isatty} - sprawdza czy v-węzeł związany jest z terminalem
\item \texttt{vnode\_access\_ok} - weryfikuje uprawnienia danego procesu do
dostępu do pliku z zamiarem wykonania podanych operacji
\item \texttt{vnode\_alloc} - przydziela nową, pustą strukturę v-węzła
\item \texttt{vrele} - zwalnia daną referencję do v-węzła
\item \texttt{vref} - tworzy nową referencję do v-węzła
\end{itemize}
W kwestii zliczania referencji, przyjęta przez nas strategia zakłada, że
każda funkcja zwracająca w wyniku v-węzeł, musi zwrócić go ze zwiększoną już
liczbą referencji (tj. wykonanym \texttt{vref}). Dzięki temu, eliminujemy
jedną z możliwych sytuacji wyścigu. Procedura wywołująca staje się w ten sposób
właścicielem zwróconego wskaźnika do v-węzła. Jeżeli nie będzie już więcej z
niego korzystała, musi wykonać na nim \texttt{vrele}.

Kolejnym ustaleniem, jest to, że funkcja, która dostała v-węzeł jako argument,
może bez przeszkód z niego korzystać, o ile nie zachowuje tego wskaźnika na później.
Każde klonowanie wskaźnika wymaga wywołania funkcji \texttt{vref}.
Wyraźnie oznaczone funkcje mogą jednak przejmować prawo własności do referencji
od strony wywołującej. Jest to wykorzystywane dla wygody, w sytuacjach, gdy po
wykonaniu procedury dalszy dostęp do obiektu nie jest zazwyczaj potrzebny.

Podobna strategia została zastosowana w odniesieniu do struktury \texttt{file\_t}.
Odpowiednie funkcje mają nazwy \texttt{frele} i \texttt{fref}.

W przypadku zwalniania ostatniej referencji do v-węzła, wykonywana jest na nim
operacja \texttt{VOP\_INACTIVE}, mająca na celu poinformowanie i-węzła (zależnej
od sytemu plików części v-węzła) o tej sytuacji. Umożliwi to wykonanie końcowych
czynności, takich jak zwolnienie i-węzła.
\begin{table}
\begin{tabular}{|l l|p{9cm}|}
\hline
vnode\_open\_t      &*vop\_open&Otwieranie pliku \\
vnode\_create\_t    &*vop\_create&Tworzenie nowego pliku \\
vnode\_close\_t     &*vop\_close&Zamykanie pliku \\
vnode\_read\_t      &*vop\_read&Odczytywanie z pliku \\
vnode\_write\_t     &*vop\_write&Zapisywanie do pliku \\
vnode\_ioctl\_t     &*vop\_ioctl&Wykonywanie dodatkowych operacji \\
vnode\_seek\_t      &*vop\_seek&Sprawdzanie, czy dana pozycja jest prawidłowa\\
vnode\_truncate\_t  &*vop\_truncate&Zmiana rozmiaru pliku\\
vnode\_getattr\_t   &*vop\_getattr&Pobieranie różnych atrybutów pliku\\
vnode\_setattr\_t   &*vop\_setattr&Ustawianie atrybutów pliku\\
vnode\_lookup\_t    &*vop\_lookup&Poszukiwanie v-węzła o podanej nazwie, począwszy
    od danego v-węzła katalogu\\
vnode\_mkdir\_t     &*vop\_mkdir&Tworzenie nowego katalogu\\
vnode\_getdents\_t  &*vop\_getdents&Pobieranie zawartości katalogu\\
vnode\_readlink\_t  &*vop\_readlink&Odczytywanie nazwy pliku, na który wskazuje
    dowiązanie symboliczne\\
vnode\_symlink\_t   &*vop\_symlink&Tworzenie dowiązania symbolicznego\\
vnode\_access\_t    &*vop\_access&Sprawdzanie praw dostępu do pliku\\
vnode\_sync\_t      &*vop\_sync&Synchronizowanie stanu pliku w pamięci ze stanem
    na trwałym nośniku\\
vnode\_inactive\_t  &*vop\_inactive&Informowanie pliku, że ostatnia referencja
do tego v-węzła jest właśnie usuwana\\
vnode\_lock\_t      &*vop\_lock&Blokowanie pliku\\
vnode\_unlock\_t    &*vop\_unlock&Odblokowywanie pliku\\
vnode\_rmdir\_t     &*vop\_rmdir&Usuwanie katalogu\\
vnode\_link\_t      &*vop\_link&Podwiązywanie istniejącego pliku pod nową nazwą\\
vnode\_unlink\_t    &*vop\_unlink&Usuwanie wpisu z katalogu\\
\hline
\end{tabular}
\caption{Struktura v-węzła - \texttt{vnode\_t}}
\label{vnodeops}
\end{table}
\subsection{System plików.}
Struktura reprezentująca zamontowane systemy plików jest analogiczna do
struktury v-węzła, jednakże związane z nią operacje są mniej liczne:
\begin{center}
\begin{tabular}{|l l| l|}
\hline
vfs\_ops\_t    &*vfs\_ops &   definicje operacji związanych z tym systemem plików\\
vnode\_t      &*vfs\_mpoint &  v-węzeł który przykryliśmy montując ten s. plików\\
devd\_t       &*vfs\_mdev &    urządzenie, używane przez ten s. plików\\
void         &*vfs\_private & prywatne dane systemu plików\\
vfs\_conf\_t   &*vfs\_conf &  struktura definiująca typ zamontowanego systemy plików\\
list\_node\_t  &~L\_mountlist & węzeł z listy zamontowanych fs\\
\hline
\end{tabular}
\end{center}
Operacje, możliwe do wykonania na systemie plików to montowanie systemu plików,
odmontowywanie go, synchronizowanie jego stanu z pamięcią trwałą, oraz pobranie
v-węzła katalogu głównego systemu plików. Podobnie jak przy v-węzłach, dla
wygody korzystania z tych operacji utworzone zostały makra, o nazwach
\texttt{VFS\_XXX}.
W chwili obecnej żaden z systemów plików nie posiada zaimplementowanej obsługi
odmontowywania systemu plików.
Do montowania systemu plików istnieje dodatkowa funkcja \texttt{vfs\_mount}
korzystająca z makra \texttt{VFS\_MOUNT} i wykonująca wszelkie niezbędne czynności
potrzebne do zamontowania systemu plików na podstawie v-węzła punktu montowania,
informacji o nazwie systemu plików oraz strukturze urządzenia które należy zamontować.

Zaimplementowane w Impali systemy plików to:
\begin{itemize}
\item MFS - pamięciowy system plików, zamontowany jako korzeń drzewa katalogów.
\item FAT12 - system plików potrzebny do odczytania danych z dyskietki. Dyskietka
jest domyślnie montowana w systemie plików pod katalogiem \texttt{/mnt/fd0/}.
\item devfs - system pełniący rolę pojemnika na pliki urządzeń, a także pośrednika
między interfejsem plików a interfejsem urządzeń. Domyślnie zamontowany 
w~\texttt{/dev/}.
\item fifofs - system plików na użytek plików potoków. Nie obsługuje on funkcji
montowania.
\end{itemize}

Wszystkie te systemy plików kompilowane są do pojedynczej biblioteki 
\texttt{libfs.a} udostępniającej tablicę funkcji inicjalizacji poszczególnych
systemów plików \texttt{fstab}. Funkcje zawarte w tej tabeli są automatycznie
wykonywane podczas inicjalizacji wirtualnego systemu plików.

Jedną z ważniejszych funkcji, udostępnionych przez
podsystem VFS, jest \texttt{vfs\_lookup}. Służy ona do zlokalizowania
v-węzła pliku na podstawie ścieżki dostępu. Implementuje ona standardowy
schemat rozwiązywania ścieżek.