Kernel Modules in Haskell

September 13, 2009

If you love Haskell and Linux then today is your day – today we reconcile the two and allow you to write Linux Kernel modules in Haskell. By making GHC and the Linux build system meet in the middle we can have modules that are type safe and garbage collected. Using the copy of GHC modified for the House operating system as a base, it turns out to be relatively simple to make the modifications necessary to generate object files for the Kernel environment. Additionally, a new calling convention (regparm3) was added to make it easier to import (and export) functions from the Kernel.

EDIT: I’m getting tired of updating this page with extremely minor changes and having it jump to the top of planet.haskell.org, so for the latest take a look at the haskell wiki entry. It includes discussion of the starting environment – a pretty large omission from the original post.


Starting Environment

You need a Linux x86 (not AMD64) based distribution with GCC 4.4 or higher and recent versions of gnu make and patch along with many other common developer tools usually found in a binutils package (e.g. ar, ld). You also should have the necessary tools to build GHC 6.8.2 – this includes a copy of ghc-6.8.x, alex, and happy.


Building GHC to Make Object files for Linux Modules

Start by downloading the House 0.8.93 [1]. Use the build system to acquire ghc-6.8.2 and apply the House patches. The House patches allow GHC to compile Haskell binaries that will run on bare metal (x86) without an underlying operating system, so this makes a good starting point.

	> wget http://web.cecs.pdx.edu/~kennyg/house/House-0.8.93.tar.bz2
	> tar xjf House-0.8.93.tar.bz2
	> cd House-0.8.93
	> make boot
	> make stamp-patch

Now acquire the extra patch which changes the RTS to use the proper Kernel calls, instead of allocating its own memory, and to respect the current interrupt level. This patch also changes the build options to avoid common area blocks for uninitilized data (-fno-common) and use frame pointers (-fno-omit-frame-pointers).

	> wget https://projects.cecs.pdx.edu/~dubuisst/hghc.patch
	> patch -d ghc-6.8.2 -p1 < hghc.patch
        > make stamp-configure
	> make stamp-ghc							# makes ghc stage 1

Next, build a custom libgmp with the -fno-common flag set. This library is needed for the Integer support in Haskell.

	> wget ftp://ftp.gnu.org/gnu/gmp/gmp-4.3.1.tar.bz2
	> tar xjf gmp-4.3.1.tar.bz2
	> cd gmp-4.3.1
	> ./configure
	# edit 'Makefile' and add '-fno-common' to the end of the 'CFLAGS = ' line.
	> make
	> cp .libs/libgmp.a $HOUSE_DIR/support

Apply ‘support.patch’ to alter the build systems of the libtiny_{c,gcc,gmp}.a and build the libraries.

	> wget https://projects.cecs.pdx.edu/~dubuisst/support.patch
	> patch -p0 -d $HOUSE_DIR < support.patch
	> make -C $HOUSE_DIR/support

Build the cbits object files:

	> make -C $HOUSE_DIR/kernel cobjs

In preparation for the final linking, which is done manually, pick a working directory ($WDIR) that will serve to hold the needed libraries. Make some last minute modifications to the archives and copy libHSrts.a, libcbits.a, libtiny_gmp.a, libtiny_c.a, and libtiny_gcc.a

	> mkdir $WDIR
	> ar d support/libtiny_c.a dlmalloc.o		# dlmalloc assumes it manages all memory
	> ar q $WDIR/libcbits.a kernel/cbits/*.o
	> cp ghc-6.8.2/rts/libHSrts.a support/libtiny_{c,gcc,gmp}.a $WDIR


Build a Kernel Module

First, write the C shim that will be read by the Linux build system. While it might be possible to avoid C entirely its easier to use the build system, and its plethora of macros, than fight it. The basic components of the shim are a license declaration, function prototypes for the imported (Haskell) functions, initialization, and exit functions. All these can be seen in the example hello.c [2].

Notice that many of the standard C functions in the GHC RTS were not changed by our patches. To allow the RTS to perform key actions, such as malloc and free, the hello.c file includes shim functions such as ‘malloc’ which simply calls ‘kmalloc’. Any derivative module you make should include these functions either in the main C file or a supporting one.

Second, write a Haskell module and export the initialization and exit function so the C module may call them. Feel free to import kernel functions, just be sure to use the ‘regparm3′ key word in place of ‘ccall’ or ‘stdcall’. For example:

	foreign import regparm3 unsafe foo :: CString -> IO CInt
	foreign export regparm3 hello :: IO CInt

Continuing the example started by hello.c, ‘hsHello.hs’ is online [3].

Now start building the object files. Starting with building hsHello.o, you must execute:

        > $HOUSE_DIR/ghc-6.8.2/compiler/stage1/ghc-inplace -B$HOUSE_DIR/ghc-6.8.2  hsHello.hs -c

* note that this step will generate or overwrite any hsHello_stub.c file.

When GHC generates C code for exported functions there is an implicit assumption that the program will be compiled by GHC. As a result the nursery and most the RTS systems are not initialized so the proper function calls must be added to hsHello_stub.c.

Add the funcion call “startupHaskell(0, NULL, NULL);” before rts_lock() in the initializing Haskell function. Similarly, add a call to “hs_exit_nowait()” after rts_unlock().

The stub may now be compiled, producing hsHello_stub.o. This is done below via hghc, which is an alias for our version of ghc with many flags [4].

	> hghc hsHello_stub.c -c

The remaining object files, hello.o and module_name.mod.o, can be created by the Linux build system. The necessary make file should contain the following:

	obj-m := module.o		# Obviously you should name the module as you see fit
	module-objs := hello.o

And the make command (assuming the kernel source is in /usr/src/kernels/):

	> make -C /usr/src/kernels/2.6.29.6-217.2.16.fc11.i586 M=`pwd` modules

This should make “hello.o” and “module.mod.o”. Everything can now be linked together with a single ld command.

	> ld -r -m elf_i386 -o module.ko hsHello_stub.o hsHello.o module.mod.o hello.o *.a libcbits.a

A successful build should not have any common block variables and the only undefined symbols should be provided by the kernel, meaning you should recognize said functions. As a result, the first command below should not result in output while the second should be minimal.

	> nm module.ko | egrep “^ +C ”
	> nm module.ko | egrep “^ +U ”
 	        U __kmalloc
 	        U kfree
 	        U krealloc
 	        U mcount
 	        U printk


Known Issue

The House-GHC 6.8.2 run-time system (RTS) does not clean up the allocated memory on shutdown, so adding and removing kernel modules results in large memory leaks which can eventually crash the system. This should be relatively easy to fix, but little investigation was done.

A good estimate of the memory leak is the number of megabytes in the heap (probably 1MB, unless your module needs lots of memory) plus 14 bytes of randomly leaked memory from two unidentified (6 and 8 byte) allocations.

[1] http://web.cecs.pdx.edu/~kennyg/house/
[2] https://projects.cecs.pdx.edu/~dubuisst/hello.c
[3] https://projects.cecs.pdx.edu/~dubuisst/hsHello.hs
[4] $HOUSE_DIR/ghc-6.8.2/compiler/stage1/ghc-inplace -B$HOUSE_DIR/ghc-6.8.2 -optc-fno-common -optc-Wa,symbolic -optc-static-libgcc -optc-nostdlib -optc-I/usr/src/kernels/2.6.29.6-213.fc11.i586/arch/x86/include/ -optc-MD -optc-mno-sse -optc-mno-mmx -optc-mno-sse2 -optc-mno-3dnow -optc-Wframe-larger-than=1024 -optc-fno-stack-protector -optc-fno-optimize-sibling-calls -optc-g -optc-fno-dwarf2-cfi-asm -optc-Wno-pointer-sign -optc-fwrapv -optc-fno-strict-aliasing -I/usr/src/kernels/2.6.29.6-213.fc11.i586/include/ -optc-mpreferred-stack-boundary=2 -optc-march=i586 -optc-Wa,-mtune=generic32 -optc-ffreestanding -optc-mtune=generic -optc-fno-asynchronous-unwind-tables -optc-pg -optc-fno-omit-frame-pointer -fvia-c

About these ads

34 Responses to “Kernel Modules in Haskell”

  1. running Says:

    this is.. blasphemy!
    this is madness!


  2. [...] Kernel Modules in Haskell « Beware the Jabberwolk a few seconds ago from web [...]

  3. this is Says:

    this is beautiful!


  4. hands down awesome. thanks.


  5. [...] Kernel Modules in Haskell « Beware the Jabberwolk a few seconds ago from Gwibber [...]

  6. Tracy Reed Says:

    Filesystem please!

  7. Felipe Lessa Says:

    Although I won’t try it myself, it is a nice guide, thanks!


  8. So why ghc-6.8.2? It this not possible with 6.10.4 or 6.12 which seems just around the corner.

    • tommd Says:

      The House patches are for GHC 6.8.2 and I used that as a base. Constantly updating a set of patches for each new GHC release takes a non-trivial amount of time. It would be nice if this modification, the regparm3, some sort of Linux Kernel friendly modification, and HALVM were all accepted in GHC HEAD, but that is not the case.


  9. [...] that they would get into kernel development, but only if they could do it in Haskell. Here is a web site with instructions on how to do just that. “By making GHC and the Linux build system meet in [...]


  10. [...] Kernel Modules in Haskell « Beware the Jabberwolk a few seconds ago from Gwibber [...]


  11. [...] Kernel Modules in Haskell « Beware the Jabberwolk a few seconds ago from Gwibber [...]


  12. [...] Kernel Modules in Haskell « Beware the Jabberwolk a few seconds ago from Afficheur [...]


  13. [...] that they would get into kernel development, but only if they could do it in Haskell. Here is a web site with instructions on how to do just that. “By making GHC and the Linux build system meet in [...]


  14. [...] Kernel Modules in Haskell « Beware the Jabberwolk a few seconds ago from Gwibber [...]

  15. Chris Chittleborough Says:

    I’ve just submitted this as a slashdot story. Because something so beautiful needs to be shared with as many people as possible. Wow.

  16. Andy Says:

    The old saying “you can’t polish a turd” comes to mind :-)

  17. Alan Carter Says:

    This is fascinating in two ways. Improved assurance of correctness is good in itself, but more immediately applicable is the possibility of reducing the development time of specialist hardware drivers by converting the build/test/boot cycle to a fight with the Haskell type system at compile time. In such cases, with few running instances in controlled conditions, the angst over e.g. GC in the kernel will be much less relevant.

    So I’ve been trying to build a module. I have a couple of small bits of advice to add to the recipe you have given, and a couple of outstanding problems.

    To set up on Ubuntu 9.04 (probably the most common config at the moment):

    1) Using Synaptic package manager:
    Search for “kernel”, select “linux-headers-2.6.28-15-generic”
    Search for “autoreconf”, select “autoconf2.13″
    Search for “ghc”, select “ghc6″
    Search for “alex”, select “alex”
    Search for “happy”, select “happy”
    Always accept any dependencies suggested, and apply the changes
    Close the package manager when you are done so that aptitude can work in the next step.

    2) Obtain gcc 4.4.1. How to do this easily is given at:

    http://ubuntuforums.org/showthread.php?t=1251357

    The incantation is (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

    The command in your recipe that requires the kernel sources is then:

    make -C /usr/src/linux-headers-2.6.28-15-generic M=`pwd` modules

    The recipe you have given will then complete to building module.ko, but the module has some problems which prevent it from loading.

    The command:

    > nm module.ko | egrep “^ +U ”

    shows many unresolved dependencies:

    > nm module.ko | egrep “^ +U ”
    U __fprintf_chk
    U __kmalloc
    U __sprintf_chk
    U __stack_chk_fail
    U __stginit_base_ForeignziCziString_
    U __stginit_base_ForeignziCziTypes_
    U __stginit_base_Prelude_
    U __vfprintf_chk
    U base_ForeignziCziString_newCString_closure
    U base_ForeignziCziTypes_zdf234_closure
    U base_GHCziBase_Czh_con_info
    U base_GHCziBase_Czh_static_info
    U base_GHCziBase_False_closure
    U base_GHCziBase_Izh_con_info
    U base_GHCziBase_Izh_static_info
    U base_GHCziBase_True_closure
    U base_GHCziBase_unpackCStringzh_closure
    U base_GHCziFloat_Dzh_con_info
    U base_GHCziFloat_Fzh_con_info
    U base_GHCziIOBase_BlockedIndefinitely_closure
    U base_GHCziIOBase_BlockedOnDeadMVar_closure
    U base_GHCziIOBase_NestedAtomically_closure
    U base_GHCziIOBase_NonTermination_closure
    U base_GHCziIOBase_stackOverflow_closure
    U base_GHCziIOBase_zdf16_closure
    U base_GHCziInt_I16zh_con_info
    U base_GHCziInt_I32zh_con_info
    U base_GHCziInt_I64zh_con_info
    U base_GHCziInt_I8zh_con_info
    U base_GHCziNum_Szh_con_info
    U base_GHCziPack_unpackCString_closure
    U base_GHCziPtr_FunPtr_con_info
    U base_GHCziPtr_Ptr_con_info
    U base_GHCziStable_StablePtr_con_info
    U base_GHCziTopHandler_runIO_closure
    U base_GHCziWeak_runFinalizzerBatch_closure
    U base_GHCziWord_W16zh_con_info
    U base_GHCziWord_W32zh_con_info
    U base_GHCziWord_W64zh_con_info
    U base_GHCziWord_W8zh_con_info
    U base_GHCziWord_Wzh_con_info
    U kfree
    U krealloc
    U mcount
    U printk

    Most of these may be resolved by copying another library from the ghc build and rerunning the link:

    > cp $HOUSE_DIR/ghc-6.8.2/libraries/base/dist/build/libHSbase-3.0.1.0.a $WDIR
    > ld -r -m elf_i386 -o module.ko hsHello_stub.o hsHello.o module.mod.o hello.o *.a libcbits.a
    > nm module.ko | egrep “^ +U ”
    U __fprintf_chk
    U __kmalloc
    U __sprintf_chk
    U __stack_chk_fail
    U __vfprintf_chk
    U kfree
    U krealloc
    U mcount
    U printk

    However, the *chk* symbols remain a problem – they are found in libc (which isn’t much help for kernel code) and are not listed in /proc/kallsyms. They are referenced by stuff in the Haskell system the recipe has built. For example, __fprintf_chk is referenced by libHSrts.a and libtiny_gmp.a. For me, this has been a show stopper and any suggestions would be gratefully received!

    The other problem concerns the -fno-common flag. When I attempt to load the module (knowing there will be unresolved symbols) the kernel complains:

    Oct 7 19:52:12 alan-carter-ubuntu kernel: [12554.276022] module: please compile with -fno-common
    Oct 7 19:52:12 alan-carter-ubuntu kernel: [12554.276294] module: Unknown symbol mcount
    Oct 7 19:52:12 alan-carter-ubuntu kernel: [12554.276388] module: Unknown symbol __vfprintf_chk
    Oct 7 19:52:12 alan-carter-ubuntu kernel: [12554.276412] module: please compile with -fno-common
    Oct 7 19:52:12 alan-carter-ubuntu kernel: [12554.276416] module: please compile with -fno-common
    Oct 7 19:52:12 alan-carter-ubuntu kernel: [12554.276432] module: please compile with -fno-common
    Oct 7 19:52:12 alan-carter-ubuntu kernel: [12554.276445] module: please compile with -fno-common
    Oct 7 19:52:12 alan-carter-ubuntu kernel: [12554.276539] module: Unknown symbol __stack_chk_fail
    Oct 7 19:52:12 alan-carter-ubuntu kernel: [12554.276542] module: please compile with -fno-common
    Oct 7 19:52:12 alan-carter-ubuntu kernel: [12554.276570] module: please compile with -fno-common
    Oct 7 19:52:12 alan-carter-ubuntu kernel: [12554.276866] module: Unknown symbol __sprintf_chk
    Oct 7 19:52:12 alan-carter-ubuntu kernel: [12554.276960] module: Unknown symbol __fprintf_chk

    Lots of complaints about -fno-common. I’ve tried to solve this by intervening at various points in the recipe, finding all CFLAGS (and in an alternate approach -fomit-frame-pointer) and adding -fno-common, but I still see many lines in the builds with no -fno-commit in them, and the complaints won’t go away. I am defeated by the build system(s) and cannot see where the commands are originally coming from. Again, any suggestions gratefully received!

    The possibilities for sanitary specialist driver writing are so cool, I’d really like to be able to do this!

    • tommd Says:

      Oohh – details, thank you!

      Your problems, as I see them:

      1) Undefined modules
      Most of these are from libHSBase, which I have just now added to the Wiki version of these instructions. Odd, I thought I already fixed that.

      2) More undefined modules (_chk)
      I don’t have any _chk symbols (defined or otherwise) in any of my libraries, so I’m not sure what you’re linking in – which library has these symbols?

      3) Common area allocations
      run: nm *.a | egrep “^ +C |a:”

      Where are the common area allocations coming from? libgmp would be my first guess, but lets find out for sure.

      • Alan Carter Says:

        The undefined *chk* symbols appear in the built .a files in $WDIR as follows:

        __fprintf_chk
        libHSrts.a
        libtiny_gmp.a

        __sprintf_chk
        libHSrts.a

        __stack_chk_fail
        libcbits.a
        libtiny_gmp.a

        __vfprintf_chk
        libHSrts.a

        These symbols are defined in the regular libc.a, which of course we aren’t linking.

        The common area allocations are in all 7 .a files:

        > nm *.a | egrep “^ +C |a:”
        libcbits.a:
        libHSbase-3.0.1.0.a:
        libHSrts.a:
        libtiny_c.a:
        libtiny_gcc.a:
        libtiny_gmp.a:
        libtiny_m.a:

        It’s probably a clue that I don’t see a -fno-commit in any of the make outputs, no matter what I do to add it to every line that has a CFLAGS = or -fomit-frame-pointer (which I thought would be a good marker) in the whole $HOUSE_DIR at various stages – redoing from start each time of course. Makes me think it might be some divergent behaviour of the make program itself.

        > make –version
        GNU Make 3.81

      • Alan Carter Says:

        A further clue: The *chk* symbols come from stdio, controlled by a preprocessor symbol _FORTIFY_SOURCE > 1. I’ve tried changing the stamp-configure target in $HOUSE_DIR/Makefile to call configure with CFLAGS=”-fno-common -D_FORTIFY_SOURCE=0″ which could have solved both problems at once, but it doesn’t have any effect on the gcc commands run by the stamp-ghc target. I’m missing something about how the CFLAGS get assembled and propagated through the $HOUSE_DIR Makefiles.

      • Alan Carter Says:

        I’ve got the module building OK now – several changes were needed, mainly removing -g and -pg from the patch files, adding an undef to the system includes, extra Makefile changes. All the details, the hacked patch files and a script which contains small changes to the build sequence are at:

        http://the-programmers-stone.com/2009/10/11/linux-kernel-modules-in-haskell-ubuntu-904-details/

    • TomMD Says:

      Nice work on that blog post Alan! Sorry I haven’t had time to carry on this conversation properly, but I see you’ve done a bang-up job. Very cool.

  18. anh nguyen Says:

    Hi, I have a same problem with “Unknown symbol mcount” when I do: #insmod x_tables.ko. Please show me how to solve it. Many thanks!

    • tommd Says:

      I don’t think you understood this blog post. You should post your problem on a site such as superuser.com or a forum specific to your Linux distribution. When you do so, include more details of your problem, kernel version, where the module came from, etc.


  19. […] Des Prix: comparatif vente viagra viagra pharmacie prix. Levitra France Prix – ??? – ?????? Kernel Modules in Haskell | Beware the Jabberwolk Levitra Prix – News et informations – GrayChoku Vente Viagra En France Acheter Cialis Au […]

  20. Anonymous Says:

    […] Pour Son Entrée En Vigueur: levitra femme achat acheter levitra sans ordonnance canada. Kernel Modules in Haskell | Beware the Jabberwolk Parliamo dei nostri Amici Animali • Leggi argomento – Zyrtec *****acie Francaise The […]

  21. John Says:

    Awesome!! really helpful


  22. I am flabbergasted. You are the best person in this cruel world.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: