1\section{Overview}
2
3The layout of the FAT16 and FAT32 filesystems can be seen in Figures
4\ref{fig:fat16_layout} and \ref{fig:fat32_layout} respectively. The \ac{fat}
5itself is simply a linked list, where the value of a cell indicates the index
6of the next cell, and special values indicate unused, bad and list-terminating
7cells.  The data area is split into clusters with sizes a multiple of the
8sector size. The cluster corresponding to a \ac{fat} entry is simply the
9cluster with the same index, i.e. for an index $i$ the \ac{fat} entry is
10$fat\_start + i \cdot entry\_size$ and the cluster entry is $clusters\_start +
11i \cdot cluster\_size$.
12
13\begin{figure}[htb]
14\centering
15\includegraphics[width=.7\textwidth]{fat16_layout.pdf}
16\caption{FAT16 Layout}
17\label{fig:fat16_layout}
18\end{figure}
19
20\begin{figure}[htb]
21\centering
22\includegraphics[width=.7\textwidth]{fat32_layout.pdf}
23\caption{FAT32 Layout}
24\label{fig:fat32_layout}
25\end{figure}
26
27FAT16 (and FAT12) have the particularity that the root directory is not like
28other directories, but is instead inside its own area preceding the start of
29the ``clusters'' area. This also implies that the maximum number of entries in
30the root directory is fixed when formatting. FAT32 removes this limitation, and
31adds an additional \ac{fsis} containing dynamic information about the state of
32the filesystem, e.g. the amount of allocated/free space.
33
34\section{Implementation and Limitations}
35
36We have implemented read-only support for FAT16 and FAT32. However, because the
37example \lstinline+ata_rw28+ interface only has the 28-bit {\tt READ DMA} and
38{\tt WRITE DMA} commands, we can only access the first 128GB of a disk (with
39512-byte sectors).
40
41\subsection{Unicode}
42
43While FAT 8.3 filenames are 8-bit strings, FAT long filenames use UTF-16.
44Barrelfish does not have any concept of Unicode, so our FAT implementation
45replaces non-\acs{ascii} characters with a question mark in directory listings,
46and does not support opening files with non-\acs{ascii} filenames.
47
48\subsection{BSD conv Functions}
49
50To generate 8.3 filenames in the first place, we have adapted various
51conversion functions from OpenBSD's msdosfs. However, our current
52implementation still compares filenames case-sensitively.
53
54\section{Caching Layer}
55
56\begin{figure}[htb]
57\centering
58\includegraphics[width=.7\textwidth]{cache_design.pdf}
59\caption{Cache Design}
60\label{fig:cache_design}
61\end{figure}
62
63The FAT code uses a cache layer as a global block and cluster store,
64simplifying the code and improving performance. The cache is implemented as a
65fixed-size hashmap from keys to indices into a backing array. The backing array
66uses doubly linked lists to handle collisions, the free list, and a list of
67unused cache entries that can be freed if space is required. Clients must
68acquire a reference to a cache entry, either using \lstinline+fs_cache_acquire+
69if the entry is already present, or \lstinline+fs_cache_put+ when creating a
70new entry. When the entry is no longer used, the client must call
71\lstinline+fs_cache_release+. If the reference count for an entry sinks to
72zero, it is appended to the aforementioned list of unused entries, which can be
73seen as an \acs{lru} queue. Thus when \lstinline+fs_cache_put+ is called and
74the cache is at its maximum capacity, it can pop the front entry from the
75unused list, free its data, and use the entry for the new cache item.
76
77The caching API consists of the following methods:
78\begin{itemize}
79	\item \lstinline+fs_cache_init+ and \lstinline+fs_cache_free+, for cache
80		setup and teardown. The initialization method takes the maximum capacity
81		of the backing array and the hashmap size. Both values must be powers of
82		two.
83	\item \lstinline+fs_cache_acquire+, for getting a reference to an existing
84		entry.
85	\item \lstinline+fs_cache_put+, for adding an item to the cache. This also
86		increments the reference count as if \lstinline+fs_cache_acquire+ had
87		been called.
88	\item \lstinline+fs_cache_release+, for releasing a reference to an entry.
89\end{itemize}
90
91\section{VFS Interaction}
92
93The mount URI for FAT has the format
94\verb@fat<version>://<port>[+<startblock>]@, e.g. \verb@fat32://0+63@, where
95{\tt version} is is either 16 or 32, {\tt port} is the \acs{ahci} port of the
96device, and the optional {\tt startblock} specifies the offset the first sector
97of the filesystem (the boot sector).
98
99Unlike Barrelfish's ramfs, our FAT implementation does not share state between
100multiple mounts using \acs{idc}, so with the current \acs{vfs} implementation
101mounting a FAT filesystem gives the mounting domain exclusive access to the
102filesystem and the whole disk. An alternative that would avoid code duplication
103would be for the \acs{vfs} to allow part of its directory structure to be
104exported as a service, creating a Barrelfish-internal system conceptually
105similar to NFS.
106