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