XFS FUSE Implementation (Week 1)
Hi, I'm Khaled Emara from Egypt. I have been given the opportunity to join FreeBSD this summer in as a participant in Google Summer of Code. This summer I'll be working on an XFS implementation in user space using the FUSE kernel module. I plan on using Rust and the fuse crate. This port is will be read-only.
File Systems are interfaces between the kernel and block devices such as your Hard Disk or SSD. In Unix, File Systems can be though of as rooted Trees. You start with the root node which in turn can contain any of the following:
- Symbolic Links
- Devices (Character, Block, or FIFO)
Directories can recursively contain any of the above. Each node in the File System is identifies by an ID called its Inode. Directories contain tuples of (name, Inode).
Block devices are usually read in chunks called blocks that are usually between 512 and 65536 with the most common nowadays 4096 Bytes. File Inodes are then mapped to these blocks one way or the other. So, the job of the File System is to map the binary in theses blocks to a rooted File Tree.
Filesystem in Userspace (FUSE) is a mechanism for Unix-like operating systems that lets non-privileged users create their own file systems without editing kernel code. This is achieved by running file system code in user space, while the FUSE kernel module provides only a "bridge" to the actual kernel interfaces. Usually there is a client that handles communication with the FUSE module. The most popular one is libfuse, but it only supports the C programming language. Thus, I'll be using the fuse crate with Rust.
So, now we want to read binary blocks and interpret them. There are two things to be aware of:
Endianness is the order of bytes in words and half-words. Say we are using an x86-64 CPU that has a word size of 8 bytes. Now there are two arrangements for the bytes:
Byte 7, Byte 6, Byte 5, Byte 4, Byte 3, Byte 2, Byte 1, Byte 0
Byte 0, Byte 1, Byte 2, Byte 3, Byte 4, Byte 5, Byte 6, Byte 7
The one where we put the least significant Byte first is called Little Endian while the other is called Big Endian. Most of the structures in XFS are Big Endian, so we have to make sure to convert it first when reading.
Although modern architectures support byte addressing, but only one word can be read at a time. Let's say the word size is 4 bytes. And the memory is arranged as follows:
0 1 2 3 4 - 0 1 2 3
where the first word is from 0-3 and the second start at 4. Say the data is stored starting from 1 to 4. That means in order to read our data we have to first read the first byte, then the second and the do some bit magic with them in order to concatenate the fourth byte with the first three. Which is inefficient, so modern compilers tend to "unpack" data structures by inserting padding to improve performance. But data on disk doesn't suffer the same fate. So instead of wasting space we pack the data as closely together as possible.
XFS is a high performance filesystem which was designed to maximize parallel throughput and to scale up to extremely large 64-bit storage systems. Originally developed by SGI in October 1993 for IRIX, XFS can handle large files, large filesystems, many inodes, large directories, large file attributes, and large allocations. Filesystems are optimized for parallel access by splitting the storage device into semi-autonomous allocation groups. XFS employs branching trees (B+ trees) to facilitate fast searches of large lists; it also uses delayed extent-based allocation to improve data contiguity and IO performance.
This concludes our introduction this week.