In a recent blog posting Tom at Beware the Jabberwolk introduced a fascinating new idea - writing Linux kernel modules in Haskell. He’s maintaining an up to date version of his work in the Haskell Wiki entry Kernel Modules.

I had a few problems setting up the build environment as Tom described it, and the main purpose of this posting is to describe exactly what I did to make it work on a fresh Ubuntu 9.04 default installation. If you start from scratch and do exactly as I describe here, you should get a working build too.

Before I get into the details, why am I interested in this? There are potential benefits and drawbacks to writing kernel modules in Haskell, and the benefits come down to improving the chances of correctness and reducing the number of times we have to go round the testing cycle.

 

Benefits

There’s something about programming in Haskell which really needs to be experienced to be believed. Writing a Haskell program and then getting it to compile can be be a difficult and frustrating process, because the language forces the author to think things through more carefully. Expressions describe relationships, not procedural sequences of stuff to do. Every if must have its else. But when the program finally compiles and the time comes to run it - that’s when things get really weird. It works. This can leave a procedural programmer feeling profoundly disoriented. We are used to spotting the first bug or two, correcting them and rebuilding. After a few times around the cycle we have some confidence in the bits that are working, and know which bits still need work. When it just works, what do we do?

Haskell front-loads the development process. It is not a magic bullet. Errors in the programmer’s original intent will still be there, and (for example) I’ve made some ugly displays by incorrectly composing graphical widgets. But the errors are hugely reduced, as are the number of trips around the edit/build/test cycle. When that cycle includes a reboot, as bug fixing in kernel mode code often does, front-loading could significantly reduce total development time and programmer frustration.

There are three cases where writing device drivers in Haskell could be very attractive:

Mission Critical Drivers. I once wrote some mission critical drivers for a major telco. There would only be a few thousand running instances, but they would be handling things like calls to the emergency services. If they failed, people trying to call the fire brigade could find themselves cut off and having to restart the process, in a situation that was already dangerous and distressing. There wouldn’t be the huge installed base which sometimes is available to discover errors, and even if there were it would hardly be a good idea to use the first few dozen unnecessary deaths to iron out the bugs. These drivers had to be right, working correctly in themselves and doing nothing to compromise the platform, from the first day they were installed. Anything that can improve assurance of correctness in situations like this needs to be looked at.

Specialist Drivers. Process control and test rigs in manufacturing industry and sensors in labs often involve specialist hardware built for the specific purpose, often by small engineering firms, which need drivers. In these cases the driver authors will often know the exact properties of the computers the drivers will run on and their intended use - which negates some of the problems discussed below. Shorter development times could reduce cost and improve the business case.

Development Support. During the development of novel hardware or user mode software which must interact with kernel modules, the first release is rarely the last. Each release often involves changes to the kernel modules, which have to be made by a different development team. It all takes time. The ability to produce new kernel modules quickly during the hardware development process would be useful in itself, even if the final release has a traditional kernel module written in C.

 

Drawbacks

Haskell is a higher level language where we specify what we want rather than exactly how to do it, and let the compiler and runtime sort out a lot of the details for us. In this, it’s a bit like SQL! Unfortunately this leads to some obvious potential problems in kernel mode work, although some of them might not be as bad as they first seem.

Speed. There seems to be a general benchmark that J. Random Haskell Program runs about half as quickly as the same thing coded in C. One of the attractions of Haskell is that programs are naturally more amenable to find-grain parallelization than procedural programs, so when we are interested in using all the cores in modern CPUs, T x 2 / 8 cores is a good deal. Unfortunately going parallel is not such a good idea in the kernel, even if the House based stuff Tom described could do it. On the other hand, techniques for making Haskell go quicker seem to be pertinent to device drivers such as avoiding laziness (see below) and using unboxed values and machine types (we’ll be moving lots of buffers of data around). So there is an issue here which might be a real problem where screaming top performance is needed in the latest generation video driver, but might not be as bad as it seems and perhaps acceptable in less performance critical cases.

Garbage Collection. Haskell does its own memory management and collects garbage. We’ve all seen Java applications suffer a hiatus because the garbage collector has kicked in, and I doubt Linus Torvalds would be amused by a suggestion that we should garbage collect in the kernel. And yet… I counted how many calls to kfree() occur in the Linux source. There are over 18,000 of them, and that doesn’t include cases hidden in #defines. We already do lots of memory management in the kernel. Garbage collection has a bad name because of the hanging Java VMs, where it kicks in infrequently and then has lots of work to do. Conventional C memory management is amortized over operations more evenly. I suspect that frequent calls to the Haskell runtime’s System.Mem.performGC() routine would ease this problem.

Unexpected Strictness Problem. One of the properties that make Haskell powerful and concise is lazy evaluation. Haskell allows the use of things like infinite lists, which it only evaluates when it needs their values, and only as much as it needs. Unfortunately it’s rather easy to make a little change to a program which makes it need lots of values at the same time, so a memory efficient lazy program becomes a memory guzzling strict one, and the process size suddenly balloons. Not good at the best of times, a disaster in locked down kernel memory! I think the solution to this one is simply to avoid lazy evaluation - develop a coding style where we always write kernel modules in a strict style in the first place, which will likely improve efficiency anyway, since laziness has a performance overhead.

The Geek Honeypot. Haskell is fascinating, in its potential and intellectual challenges. Even the idea of writing kernel modules in it doesn’t seem so crazy. Remember that the language is a honeypot for the geekish mind, and retain a healthy degree of skepticism!

 

What About F#?

All this talk of writing Linux kernel modules in Haskell raises an obvious question: Windows drivers are harder than Linux ones, and F# - a functional language - is one of the heads of the .NET hydra. Might there be benefits in writing Windows drivers in F#? I fear the answer is no. The whole point about Haskell is that it is a pure functional language. This is what gives it the added rigour, and also produces the intellectual challenge of using it. From what I’ve seen (and I’m not an expert), F# is not a pure functional language. It allows us to work procedurally and use functional features when it’s convenient to do so, like Python or Perl 6. This gives power with a much easier learning curve, but takes away exactly the property that makes Haskell so attractive for kernel mode code. Probably a better approach would be to try the idea out in Linux, and if it proves to be good, recreate the same environment in the Windows world.

 

How to Perform Tom’s Build on a Fresh Ubuntu 9.04 Installation

Download and do a default installation of Ubuntu 9.04. The Update Manager will offer quite a lot of updates now that 9.04 is getting a bit old, some of them security ones, but when I was testing these notes I closed it without installing any to ensure a known state.

I’m using VirtualBox for these experiments. Virtual machines are wonderful for getting installation and configuration stuff right, because it’s so easy to copy the hard disk and backtrack to unambiguously known points. I needed to install the kernel headers and build essentials really early so I could get the VirtualBox tools working, so this is the first command to give:

$ sudo apt-get install build-essential linux-headers-generic

Next there’s a bunch of packages to load. Do this using the Synaptic Package Manager - from the menu bar:

System/Administration/Synaptic Package Manager

Then use the Quick search and select from the packages offered - always accept any dependencies :


Quick search Select
autoreconf autoconf2.13
ghc ghc6
alex alex
happy happy

Then apply the changes. Once they have been applied, quit the Package Manager so that the next command will work.

You will need gcc 4.4.1. To get this, give the command (it’s all one line):

$ echo "deb http://us.archive.ubuntu.com/ubuntu karmic main restricted" | sudo tee -a /etc/apt/sources.list && sudo aptitude update && sudo aptitude install gcc

It’s necessary to make a global change to the system headers to prevent calls from the standard IO library to stack protection routines which are not available to kernel mode code:

$ sudo vi /usr/include/features.h

In the section with many #undef lines, add the line:

#undef _FORTIFY_SOURCE

Next download the tarballs and other files you will need. In Tom’s instructions this is done at the appropriate points in the build, but I found it easier to grab everything once and script the build process as much as possible. I’ve also slightly changed Tom’s patch files to remove common allocations and profiling calls which were preventing the built module loading on my Ubuntu 9.04 installation:

$ mkdir Tarballs$ cd Tarballs
$ wget http://web.cecs.pdx.edu/~kennyg/house/House-0.8.93.tar.bz2
$ wget http://www.haskell.org/ghc/dist/6.8.2/ghc-6.8.2-src.tar.bz2
$ wget http://www.haskell.org/ghc/dist/6.8.2/ghc-6.8.2-src-extralibs.tar.bz2
$ wget ftp://ftp.gnu.org/gnu/gmp/gmp-4.3.1.tar.bz2
$ wget https://projects.cecs.pdx.edu/~dubuisst/hello.c
$ wget https://projects.cecs.pdx.edu/~dubuisst/hsHello.hs
$ wget http://the-programmers-stone.com/wp-content/uploads/2009/10/hghc.patch
$ wget http://the-programmers-stone.com/wp-content/uploads/2009/10/support.patch
$ wget http://the-programmers-stone.com/wp-content/uploads/2009/10/hlkm-build
$ cd ..

Now you should have a directory Tarballs below the one you’re in (probably your $HOME), and be ready to perform the build. There are a few variations from Tom’s instructions - for example there are changes to more than one Makefile in the gmp subtree - but they are scripted, including all but one of the manual edits. You will need to edit the script and change $HOUSE_DIR and $WDIR to point to your $HOME and not my /home/alan unless you also happen to have a most excellent name :-)

$ vi Tarballs/hlkm-build
$ chmod +x Tarballs/hlkm-build
$ Tarballs/hlkm-build

The whole build takes about half an hour on a 2GHz machine. There is one point when the script drops you into vi, and just as Tom says, you need to add the line:

startupHaskell(0, NULL, NULL);

Before the call to rts_lock() in the hello() function, and after the call to rts_unlock() in the goodbye() function add the line:

hs_exit_nowait();

Write the file back and allow the script to complete. You should then be able to use one xterm to:

$ tail -f /var/log/messages

and in another xterm:

$ cd House-0.8.93/Wdir
$ sudo insmod module.ko

and see the messages from the kernel module appear in the log messages! Next step - make it do something more interesting!