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?

Ideas for Aether

I've just installed aether-1.4 for this website and made a few enhancements that I might submit one day.

They include allowing a blog to select entries from another blog based on tags in the [entry] field. Thus my page has a News section which contains all items from my front page that mention 'raid' in the entry tag.

Also a blog can show just a list of pages (or the summaries there-of), so my page is now a blog of precisely three other pages. These are sorted by modify time.

Other changes I am contemplating include:

  • Once a password has been typed in, the "Edit" and "New" links at the bottom of the page become simple links that contain the password. This way I only need to type the password once. There would need to be an easy way to forget the password of course
    BULLET - Almost all my aether usage is using it as an error document, so the meaningless "me" doesn't appear. But when I edit a page it has to use a real URL, as you cannot post to an error document (I think). The "post" should pass in the preferred prefix so that when I come out of editing, I am back in the error-document space. (Does that make sense to anyone but me).

vpatch design notes

In my Linux kernel development work, I often apply patches to files that have changed since the patch was created. Sometimes these patches fail to apply for trivial reasons.

About a year ago I wrote a program called to help apply these patches, and it has been very useful. However the solution isn't perfect. The problem is that I cannot see what is going on.

When I apply a patch that fails, I would like to be able to see exactly why it failed, and what wiggle would do to fix it. But to do that I currently have to grovel around in various files. I would be nice if this was more automatic.

What I am envisaging is a new patch application tool. Let's call it vpatch.

Whitelisting email

I have been following SPF for a while and have been thinking through the whole junk-mail control issue.

I have come to the conclusion that the only viable long-term solution is agressive whitelisting.

I have been having thoughts about setting up a local service to support whitelisting.