Skip to content
A scene from Ireland

Projects

log segments and RAID6 reshaping

Part of the design approach of LaFS - and any other log structured filesystem - is to divide the device space into relatively large segments. Each segment is many megabytes in size so the time to write a whole segment is much more than the time to seek to a new segment. Writes happen sequentially through a segment, so write throughput should be as high as the device can manage.

(obviously there needs to be a way to find or create segments with no live data so they can be written to. This is called cleaning and will not be discussed further here).

One of the innovations of LaFS is to allow segments to be aligned with the stripes in a RAID5 or RAID6 array so that each segment is a whole number of stripes and so that LaFS knows the details of the layout including chunk size and width (number of data devices).

This allows LaFS to always write in whole 'strips' - where a 'strip' is one block from each device chosen such that they all contribute to the one parity block. Blocks in a strip may not be contiguous (they only are if the chunksize matches the block size), so one would not normally write a single strip. However doing so is the most efficient way to write to RAID6 as no pre-reading is needed. So as LaFS knows the precise geometry and is free with how it chooses where to write, it can easily write just a strip if needed. It can also pad out the write with blocks of NULs to make sure a whole strip is written each time.

Normally one would hope that several strip would be written at once, hopefully a whole stripe or more, but it is very valuable to be able to write whole strips at a time.

This is lovely in theory but in practice there is a problem. People like to make their RAID6 arrays bigger, often by adding one or two devices to the array and "restriping" or "reshaping" the array. When you do this the geometry changes significantly and the alignment of strips and stripes and segments will be quite different. Suddenly the efficient IO practice of LaFS becomes very inefficient.

There are two ways to address this, one which I have had in mind since the beginning, one which only occurred to me recently.

A new release of wiggle

A long time ago, while in a job far far away....

Back in 2003 I wrote a program called "wiggle". Like many interesting projects it was written to scratch an itch.

While developing code for the Linux kernel I would often need to apply patches made for earlier versions against later versions. Sometimes there would be trivial conflicts and the "patch" program would just give up an create a reject file. After the 50th time that I applied a patch like this by hand it decided that enough was enough so I wrote "wiggle". It takes patches that don't quite apply properly and wiggles them in to place. If there is a change in part of the code that the patch doesn't actually change, wiggle doesn't let that get in the way. If there is a change in part of the code that the patch also changes, wiggle reports that inline as a conflict in a way that makes it easy to resolve by hand.

Since 2003 I have made a few improvements and fixed a few bugs. Just recently the Debian package of wiggle got a new maintainer who was very proactive in trying to get some patches upstream to me, and get some languishing bugs fixed.

Always keen to reward such friendly behaviour I applied the patches, fixed the bugs and finally made a new release of wiggle, the first in nearly 7 years.

Version 0.7 can be found in my git tree at git://neil.brown.name/wiggle or browsers at http://neil.brown.name/git?p=wiggle;a=summary or downloaded as a 'tar' archive from http://neil.brown.name/wiggle .

Feedback always welcome.

What I really want to know is how to get git to always use wiggle for merging conflicts. I can do it on a per-repository basis by setting the 'merge' attribute (I think) but I cannot make it automatically apply to all of my git trees...

  • in Projects
  • 7 min read

The LaFS directory structure

I've spent most of this week working on my filesystem - LaFS, having not touched it since December. As usual, working on it re-awakens my enthusiasm for it and as I seem to be in a blogging mood, I'm going to write about it. Currently. my favourite part of my filesystem is the directory structure. So I'm going to write about that.

The difficulty with designing directories for a Posix filesystem is that Posix provides two ways to find entries in a directory.

The most obvious way to find an entry is to look it up by name. So to be able to implement large directories at all efficiently, you need an index that can lead you quite quickly from a name to an entry.

However Posix also requires you to be able to look up an entry given a small fixed-length identified. This is needed to implement seekdir. The filesystem gets to choose the identifier and it returns it via the readdir or telldir function. However whatever identifier is returned must continue to work for that entry indefinitely until that entry is removed. There is no mechanism for the identifer to time out or be refreshed. It must be really stable. Even if Posix didn't require this, NFS does. To be able to export a filesystem via NFS, you really need to be able to find entries given small fixed-length keys.

As names in directories are not fixed length, and the maximum length is not small, this seems to imply that you need two separate indexes for a directory, and then need to keep them in-sync with each other, and a number of filesystems do just this.

My clever idea, which I only realised after failing to make a couple of other approaches work, and after arguing with Ted T'so about the ext3 directory structure, is that you can get by with only one index. Here is how.

Metad - a daemon for controlling daemons

As I progress in winding up my position at the Computing Support Group at cse.unsw I'm looking for programs that I wrote which might be more widely useful and trying to make them available to the open source community.

One such is 'metad' which you can find in my git repository at git://neil.brown.name/metad or http://neil.brown.name/git/?p=metad.

metad is a daemon for managing other daemons. It is a bit like inetd in that it starts programs and waits for them to complete. However it isn't just starting programs based on network activity - that is possible, but was a later addition.

The main purpose is to run all other little daemons one seems to need and to allow those daemons to be stopped and started remotely. It may not be very interesting on a single-user machine, but it is wonderful when administering a network

suidrun - for providing setuid to customers when you want to mount with nosuid

We have several thousand customers, mostly students. Many of them have no idea what a setuid bit is, and don't really need to know. This has lead to several hundred setuid or setgid files that really should be set-id. This may not actually be a real security threat (a setuid image file cannot do much) but there is the potential for a security problem.

Also, allowing setuid files means that someone with temporary elevated privileges can (a workstation left logged-on) can easily elevant them to permanent privileges. This can be alleviated by reguilar scanning, but for this you need a lisdt of allowed setuid programs, and if you have decided to have such a list, there are better ways than scanning.

So I have written a little program that can give setuid functionality to customers whose homedirectory is on a filesystem that is mounted with nosetuid. The program requires all setuid programs to be recorded in a control file - /etc/suidrun.rc. Providing such files pass some simple tests, they can be run as though the setuid bit were really working.

The program in available under the GPL from http://www.cse.unsw.edu.au/~neilb/source/suidrun/.

See the man-page for more details.

User-space touchpad driver for ALPS in Latitude D800

Over the past few months (too many!) I've playing with a user-space driver for the touchpad on my Dell Lattitude D800 note-book - an ALPS touchpad.

The 2.6 Linux kernel does contain a driver for the ALPS touchpad, but I am unconvinced that the kernel is the right place for such a driver, and it doesn't let me do interesting things and experiment easily.

Anyway, I now have a user-space ALPS driver that does what I want. I supports corner-taps which give me access to all 3 X11 button, and side-stroking to get a scroll wheel. It also allows me to continue dragging something after my finger hits the edge of the pad.

The sourcecode is at http://www.cse.unsw.edu.au/~neilb/D800/ALPSmouse.c. It should compile quite easily. You just run it (as root) and tell X11:

        Option          "Device"                "/dev/input/mice"
        Option          "Protocol"              "ImPS/2"

Blog thoughts

No entries for several months... Why? Maybe I just lost the urge.. or maybe there is something more.

I am a person who is keen on structure. Not everything I do it totally structured, but where structure exists I like to find and make use of it. The thing about a blog is it is largely unstructured. It it just a time-ordered series of thoughts. I think that is great, but I would like there to be extra structure as well.

Sometimes different blog entries at different times are connected by a theme. That connection should be made apparent somehow. But this blog doesn't let me.

So I tried creating sub-blogs (look over on the right hand side) but there didn't really get anywhere.

So where next?

A final word on AVL trees

One thing bothered me about the AVl code I developed in the preceeding two articles. That is that there were two versions of each of avl_rotate_2 and avl_rotate_3, one for each of insert and delete. I don't like code duplication and the two versions were very similar despite not being identical. This just wouldn't do.

The differences between the rotation routines were two fold. Firstly the rotation went in opposite directions, and secondly the final setting of ->longer was quite different.

The first is easily fixed by passing 1-dir in place of dir for one of the call. The other took a little bit more work, but was achievable by moving some of the setting of ->longer out of the rotate function and into the call site.

The result is a smaller set of code with no significant code duplication. I made a few other minor changes and rearrangements and the result is available, free of charge or any other restrictions, as avl3.c

Non-recursive algorithm for AVL tree deletion

I suggested in my other article on AVL insertion that deletion would probably be fairly symmetric to insertion. It isn't, though there are similarities.

Deletion is somewhat more complicated than insertion, but not greatly so. Like insertion, it can be done neatly without recursion and using constant storage (no stack necessary). The cost of constant storage is that some comparisons need to be done twice (though on average, it is less than one per deletion).

These extra comparisons can be avoided by using one bit of storage for each level of the tree, which is less than twice the base-2 logarithm of the number of elements in the tree. If the tree is stored in memory, then the storage equivalent of two pointers will provide enough bits. This is small enough to be considered constant.

I have found other descriptions of non-recursive AVL deletion elsewhere on the web, specifically at http://benpfaff.org/avl/algorithm.ps and http://www.stanford.edu/~blp/avl/libavl.html/Deleting-from-an-AVL-Tree.html.

I don't find either of these treatments particularly easy to read, but that might be my problem, not theirs. If you don't like what I have written, please try one of those.

Enough introduction - on to the code.

Non-recursive algorithm for AVL tree insertion

I recently wanted to write code for insertion into an AVL tree. Because this code will eventually (hopefully) live inside the Linux kernel, I wanted it to be non-recursive (as recursive code doesn't sit will in the context of the kernel).

I found that taking a non-recursive approach leads to code that is (arguably) cleaner and more transparent than the traditional recursive approach. In fact, I liked what I came up with so much that I thought I would share it.