Josef “Jeff” Sipek

Simple File System

On three or four occasions over the past 4 years, I had a use for simple file system spec. Either to teach people about file systems, or to have a simple file system to implement to learn the idiosyncracies of an operating system’s VFS layer. This is what I came up with back in 2011 when helping a friend learn about file systems.

Simple File System

The structure is really simple. All multi-byte integers are stored as big endian.

A disk is a linear sequence of blocks. Each block is 512 bytes long. You can read/write a block at a time. The first block on the disk is number 0, the second is 1, etc.

The following is the file system structure. First of all, the file system uses 1024 byte blocks, and therefore you need to issue two disk I/Os to process a file system block worth of data.

The first fs block (disk blocks 0 & 1) is reserved, you should not change it in any way.

The second block contains the superblock:

struct superblock {
        uint32_t magic;        /* == 0x42420374 */
        uint32_t root_inode;   /* the disk block containing the root inode */
        uint32_t nblocks;      /* number of block on the disk */
        uint32_t _pad[253];    /* unused (should be '\0' filled) */
};

Starting at the third block is the block allocation map. The most significant bit of the first byte of this block represents fs block 0. The next bit represents block 1, etc.

Each file is represented by an inode. The inode contains a number of data block pointers. The first pointer (blocks[0]) contains the first 1024 bytes of the file, blocks[1] the second, etc. The timestamps are in microseconds since 00:00:00 Jan 1, 1900 UTC.

sturct inode {
        uint32_t size;         /* file length in bytes */
        uint32_t _pad0;        /* unused (should be 0) */
        uint64_t ctime;        /* creation time stamp */
        uint64_t mtime;        /* last modification time stamp */
        uint16_t nblocks;      /* number of data blocks in this file */
        uint16_t _pad1;        /* unused (should be 0) */
        uint32_t _pad2;        /* unused (should be 0) */
        uint32_t blocks[248];  /* file block ptrs */
};

The root directory is represented by an inode, the data pointed to by this inode’s blocks[] have a special format. They should be treated as arrays of directory entries. The filename is space padded (so, “foo.txt” would be stored as “foo.txt                     ”).

struct direntry {
        char fname[28];        /* the filename */
        uint32_t inode;        /* the inode block ptr */
};

So, graphically, the file system looks something like:

sb -> rootinode
        |-> direntries
        |     |-> <"foo.txt", inodeptr>
        |     |                 \-> inode
        |     |                       |-> data
        |     |                       |-> data
        |     |                       \-> data
        |     |-> <"bar.txt", inodeptr>
        |     |                 \-> inode
        |     |                       |-> data
        |     |                       |-> data
        |     |                       \-> data
        |     |             .
        |     |             .
        |     |             .
        |     \-> <"xyz.txt", inodeptr>
        |                       \-> inode
        |                             |-> data
        |                             |-> data
        |                             \-> data
        |                   .
        |                   .
        |                   .
        \-> direntries
              |-> <"aaa.txt", inodeptr>
              |                 \-> inode
              |                       |-> data
              |                       |-> data
              |                       \-> data
              |-> <"bbb.txt", inodeptr>
              |                 \-> inode
              |                       |-> data
              |                       |-> data
              |                       \-> data
              |             .
              |             .
              |             .
              \-> <"ccc.txt", inodeptr>
                                \-> inode
                                      |-> data
                                      |-> data
                                      \-> data

Delegating mount/umount Privileges

Recently, I was doing some file system changes. Obviously, I wanted to run them as an unprivileged user. Unfortunately, the test involved mounting and unmounting a filesystem (tmpfs to be specific). At first I was going to set up a sudo rule to allow mount and umount to run without asking for a password. Then I remembered that I should be able to give the unprivileged user the additional privileges. It turns out that there is only one privilege (sys_mount) necessary to delegate…and it is easy to do!

$ usermod -K defaultpriv=basic,sys_mount jeffpc

Then it’s a matter of logging out and back in. We can check using ppriv:

$ ppriv $$
925:    bash
flags = <none>
        E: basic,sys_mount
        I: basic,sys_mount
        P: basic,sys_mount
        L: all

At this point, mounting and unmounting works without sudo or similar user switching:

$ mkdir tmp
$ mount -F tmpfs none /tmp/tmp
$ df -h /tmp/tmp
Filesystem      Size  Used Avail Use% Mounted on
swap            2.6G     0  2.6G   0% /tmp/tmp

XFS & ext3

So, here’s a mini-rant…There are just as many XFS complaints as ext3 complaints on the linux-kernel mailing list. Yep. It is that simple. I can’t stand the fact that some people make a big deal out of complaints about XFS, but are oddly silent (or ignorant?) of the fact that there are just as many “problems” with Ext2/3. I’m not even considering Ext4, as it is in development.

XFS, ext3 and 16TB

So, I was in #linuxfs on OFTC, and a whole discussion happened about XFS and ext3. Eric Sandeen was working on fixing up few bugs in ext3 to make it work on 16TB of storage. I couldn’t help but mention XFS. The discussion then evolved into XFS is a large pile of code that is really nasty in places (I do agree with that) but it still performs very well. Eric pasted a link to this image (I copied it for archival purposes.) which shows the code size of XFS over time. It is actually kind of scary.

XFS code size

OLS 2006 - Day 4

Friday was kind of interesting. The talks were little weaker, but there were some interesting ones. For example, Matt Mackall’s Towards a Better SCM: Revlog and Mercurial talk was a nice way to learn how Mercurial stores the history. I got tired so I went back to the hotel, and fell asleep for few hours. I woke up just in time to head over to the conference center for the 20:00 Stackable file systems BOF. That was interesting. A lot of useful people showed up, including Christoph Hellwig, Ted Tso, Val Henson, Steve French (Samba/CIFS guy), Jan Blunck,Eric Van Hensbergen (plan9 fs implementation in Linux) and many more. Topics included limited stackspace (4K on i386), cache consistency, locking, and nameidata structure brain damage.

As we planed before, after the BOF we invited everyone over to the hotel for some snacks and drinks. That’s where things got really interesting. I spent a lot of time with Jan Blunck and Eric Van Hensbergen talking about the proper way to do unions. Three people, three different ways to union files :)

After that we had some fun with the stack space issue and Reiserfs (and Hans’s approach to open source).

stack space
There should be a competition "who can create the largest storage stack without overflowing the stack." For example, unionfs on top of gzipfs on top of versionfs on top of device mapper on top of md on top of scsi over ethernet on top of ppp tunneled thought ssh …. you get the idea
Reiserfs
Apparently, Christoph once fixed something trivial in reiserfs code, he sent the patch to Hans, and in return he got a gigantic legal document (I know exactly what he is talking about as I have submitted a patch once as well). Well, he didn’t like it, so he gave Hans a bunch of options one of which included certain sum of money for copyright to the code. Interestingly enough, Hans accepted. Too bad I didn’t know about this story before, I might have made some money of off my one line fix to the reiserfs section in the Kconfig file. :)

I have to say, I really want to look at how plan9 works thanks to the conversation I had with Eric Van Hensbergen. It seems to have a lot of really good ideas. Hrm, now that I think about it, I might install it one of my old boxes. Yeah, I know I am odd.

Powered by blahgd