divergefs file system for Plan 9

Introduction

I worked on a diverge file system for Plan 9 operating system which resolves many slightly-irritating situations such as needing shell scripts containing many bind commands when compiling kernel or system programs as an unprivilged user.

Plan 9

Plan 9 uses file metaphor throughout the whole system, and programs communicate through a special file protocol called 9p. As a result, the implementations are cleaner, and users can enjoy uniform operations. Since kernel only needs to know 9p, the job of understanding different file formats, and exposing other resources as files can be easily implemented in the user space. Plan 9 also allows each process to have a separate namespace which means a single file can be different things in different processes. Therefore, many ugly hacks that are seen inside the kernel of normal Unix clones such as /dev/tty, can again be easily implemented in the user space.

See:

• Plan 9 From Bell Labs
• Why Plan 9

The problem

Even though Plan 9 is versatile with namespace manipulation through bind and mount, kernel compiling as a normal user can be difficult. In order to compile the kernel, the user has to create several shadow directories for the ones that they don't have write access for and bind all the shadows in front of the old ones.

The matter gets worse when the user wants to modify or apply patch to the underlying read-only files. The current "bind" mechanism isn't smart enough to perform the modification automatically inside the shadow directories when editing files in the read-only directories, so the users are forced to manually copy all the files they need to change into their shadow directories.

The following two scenarios illustrate the problems described above:

Union directory

Combining directory trees under Plan 9 using bind does not perform true union of the directory trees. Consider the following two directory trees:

a/
  aa/
    aaa.txt
b/
  aa/
    bbb.txt

After the command
% bind -b b a # binds b on top of a
aaa.txt will be not be visible.

Read-only

When target directory is not writable either due to insufficient permission or read-only media, a user has to copy everything to a writable directory before doing any modification. To illustrate the limitations of the existing kernel support for directory binding, consider this directory tree:

readonly/
  hello.c

temp/

Though the command
% bind -bc temp readonly
binds temp on top of readonly, and permits creation of files in temp, hello.c cannot be modified or removed.

Divergefs

I wrote a user-level file system that solves the problems above by allowing files to "diverge" from the original mount point onto user specified directories.

The job of understanding 9p is already done in lib9p which also handles dispatching incoming packets to program specified callbacks and delivering outgoing packets for all the file operations. Therefore, the program needs only to interpose itself on top of the original mount point and properly route the requests to different directories.

Holes

File deletion and renaming are more subtle than they first appear. Consider this directory tree:

  top/
    test.txt
  base/
    test.txt

Assuming that top is layered on top of base, to the user there is only one file called text.txt which is served from the top later. If the user executes
% rm test.txt
the file is removed from the top layer, causing the base layer's test.txt to show through, which is not the desired behavior from the user's point of view.

In divergefs, the special "hole" mechanism is used to provide the proper behavior of the layering file system. When user performs
% rm test.txt
a hole will be associated with that path name, which prevents any files matching the same path inside different layers to show through. When the user creates a file, the path name is first matched against the hole database, and if a matching hole is found, the hole is removed as a result of the creation. In order to provide consistent behavior across multiple sessions mounting the same directory, a file is used to save all the holes, which can be re-read during a later divergefs' initialization.

Rules

Instead of having all the changes saved into a single overlay directory, rules give users the flexibility to "diverge" files to different layers of the directory as long as the file satisfies the rule for that layer.

Rules include file extension matching, regular expression file name matching, file attribute matching (readable, writable, directory and etc).

References

• The intro(5) and 9p(2) manual pages
• The following source files: ramfs.c, lnfs.c, mkdir.c, rm.c, cp.c, test.c, and chmod.c.
• The Use of Name Spaces in Plan 9
• How to Use the Plan 9 C Compiler
• Plan 9 Mkfiles
• Plan 9 C Compilers
• Lexical File Names in Plan 9, or, Getting Dot-Dot Right
• Troff User's Manual

Design Decisions

Regression test suite

The test suite helped a lot during development in identifying bugs and preventing introducing bugs. A generic testing framework written in C is included with the source code under the tests subdirectory.

Generic data structures

To unburden future programmers from reinventing wheels, generic implementations of array, set, and dictionary were developed in the course of this project.

Lex/yacc configuration parsing

Since the configuration file syntax is only experimental, scanner and parser are generated from lex and yacc files to provide more flexibility for future modification either by myself or others.

Conclusion

Once divergefs was stable enough, it was used during its own compilation process. The result was significant speed up during development on foreign Plan 9 machine with all the source code located on local Linux machine. Right now, divergefs is stable enough for regular Plan 9 kernel and userland programs building as a normal user. The source code is currently hosted on the "sources" repository at /n/sources/contrib/de0u/divergefs.tar.gz.

For more info on divergefs and download location, please check out the divergefs entry in the Plan 9 wiki.

[Last modified Tuesday August 23, 2005]