hOp -- Sébastien Carlier and Jérémy Bobbio

What is hOp ?

hOp is a micro-kernel based on the RTS of GHC, the Glasgow Haskell Compiler. It is meant to enable people to experiment with writing device drivers in Haskell. Currently, hOp is still very hackish, and IA32-specific. Contributions are welcome!

The RTS of GHC is truly an amazing piece of software. By removing the system-specific bits, and just adding a few lines of C and assembly code, it turns into a standalone micro-kernel that can be extended in our favorite language, Haskell.

All functions from the base hierarchical library outside of the System module is available. This includes threads, communication primitives and the foreign interface, which means that experimenting with writing drivers in Haskell should be reasonably easy.

Building

In order to build hOp, you need every software package required to build GHC, autoconf, and also "genext2fs", which is available as a package in Debian GNU/Linux, but can also be compiled from source: http://uclibc.org/downloads/buildroot-sources/genext2fs_1.3.orig.tar.gz

Build steps are as follows:

1. Enter "make boot" to download and extract the source code of GHC.

2. Either enter "make floppy" to build a 2.88 MB floppy image named hOp.flp, or enter "make iso" to build a bootable CDROM image.

Starting hOp

hOp runs on real hardware, but 2.88MB floppy drives are rare, and burning the CDROM image wastes a blank CD.

It is usually more convenient to use an IA32 emulator such as Bochs (http://bochs.sourceforge.net/), which can read 2.88MB floppy disks and CDROM images.

Here is a minimal configuration file (.bochsrc) for Bochs:

--- 8< --- cut here --- 8< --------------------------------------------- config_interface: x display_library: term romimage: file=/usr/share/bochs/BIOS-bochs-latest, address=0xf0000 megs: 32 vgaromimage: /usr/share/vgabios/vgabios.bin floppya: 2_88=hOp.flp, status=inserted ata0: enabled=0, ioaddr1=0x1f0, ioaddr2=0x3f0, irq=14 ata1: enabled=0, ioaddr1=0x170, ioaddr2=0x370, irq=15 ata2: enabled=0, ioaddr1=0x1e8, ioaddr2=0x3e0, irq=11 ata3: enabled=0, ioaddr1=0x168, ioaddr2=0x360, irq=9 boot: floppy ips: 1000000 floppy_bootsig_check: disabled=0 log: /tmp/bochsout.txt panic: action=ask error: action=report info: action=report debug: action=ignore debugger_log: - vga_update_interval: 300000 keyboard_serial_delay: 250 keyboard_paste_delay: 100000 floppy_command_delay: 500 mouse: enabled=0 private_colormap: enabled=0 --- 8< --- cut here --- 8< ---------------------------------------------

Enabling Debugging

Debugging can be enabled by doing the following changes:

• build.mk

  To compile the RTS with debugging enabled, you need to change the compilation options in build.mk:

  GhcRtsHcOpts = -optc-DSTANDALONE -optc-DDEBUG -optc-UPROFILING
  GhcRtsCcOpts = -O -DSTANDALONE -DDEBUG -UPROFILING
  

• kernel/Makefile

  RTS debug messages are printed using a simple compatibility layer to functions like fprintf. These messages can currently be either displayed directly on screen (which trash what was displayed by Haskell code) or using the "console output" feature of Bochs.

  To enable video printing, add in kernel/Makefile:

  OBJS += cbits/video.o

  To enable Bochs output, add in kernel/Makefile:

  CFLAGS += -DBOCHS_VIDEO

• kernel/cbits/c_start.c

  When booting, hOp launches the usual main() function of the RTS. The same debug flags as on the command line are thus available; they can be set by modifying argc and argv at the start of c_start() in kernel/cbits/c_start.c.

Implentation details

Making a standalone RTS

The Run-Time System (RTS) of GHC handles memory management, thread scheduling and inter-thread communication, so it can be thought of as a micro-kernel. Making a standalone RTS - removing all dependencies on an operating system - is in fact fairly straightforward.

The RTS is written in portable C code, and therefore requires a C execution environment to run. Our goal to remove dependencies on an operating system precludes the use of a full featured C library, so only a handful of functions are included to provide a very minimal C environment. It is composed of the following components:

• a tiny libc with these functions:

  • abs, isdigit, memcpy, memmove, memset, strcmp, strnlen
  • iswalnum, iswalpha, iswcntrl, iswdigit, iswlower, iswpunct, iswupper, iswblank These functions are generacted from the character database named UnicodeData.txt available at www.unicode.org
  • malloc/free/realloc from Doug Lea's implementation

• a minimal libgcc with __divdi3, __moddi3, __udivdi3, __umoddi3 extracted from libgcc on the build system

• several functions from libgmp, extracted from libgmp.a of the build system; ad-hoc replacements are provided for assert.o and memory.o to remove some dependencies.

• math functions from Sun Microsystems' public domain math library

We also provide simple wrappers for fprintf, stderr, stdout, fflush, fprintf, fwrite, fputc, fputs, fopen in order to build RTS with debugging option enabled.

We say that C code (including the RTS, boot code, and parts of the interrupt handling code) is executed in the "C land", which has its own explicitly managed heap (malloc/free), and uses conventions defined by the C compiler for function calls, etc.

We say that Haskell code is executed in the "Haskell land", with its heap being managed by the RTS, and using the execution model of the RTS (STG).

Although our goal is to minimize the amount of code running in C land, favoring Haskell code, data can be exchanged between this two worlds using primitive operations of the Haskell compiler or the Foreign Function Interface (FFI).

Memory model

hOp only supports IA32 (i.e., Intel's x86 family of processors), but is meant to eventually run of multiple architectures. The remaining subsections of this section give IA32 specific details.

hOp currently operates in protected mode with a flat address space (paging is disabled), and is limited to use only 32MB of memory (it will crash miserably if you have less memory; adding code to detect the amount of available memory is future work).

------------ 0x00000000 0 Interrupt vectors ------------ 0x00000400 1kB C stack ------------ 0x000A0000 640kB Video RAM and BIOS ------------ 0x00100000 1MB hOp kernel ------------ 0x00400000 4MB C heap ------------ 0x00800000 8MB Haskell heap ------------ 0x02000000 32MB

The low level interface to the C heap is a trivial implementation of the standard Unix system call sbrk(2). The high level interface uses Doug Lea's malloc.

The Haskell heap is divided in 1MB blocks, which are handed out as needed to the RTS to be managed by the garbage collector. The C land functions MBlock_init() and getMBlocks() manage a static variable pointing to the next 1MB block start address.

Interrupt handling

• Each interrupt handler runs in its own Haskell thread.
• These threads, wrapped in StablePtrs, are registered in a global array "irqHandlerThreads" which resides in C land.
• A new blocked state "BlockedWaitingInterrupts" was added.
• In order to register a thread as an handler for a given IRQ, a new PrimOp, registerForIRQ#, was added. It creates a new StablePtr for the current thread, update the global array, enable the IRQ and put the thread in blocked state, waiting for interrupts.
• Another new PrimOp, waitNextInterrupt#, is used after handling an interrupt to sends a specific End Of Interrupt to the controller and block the thread again until the next IRQ.
• When an interrupt occurs, the C handler examines the irqHandlerThreads array; if a thread was registered, it is unblocked and a context switch is requested (and will occur when control is next passed to the Haskell scheduler).

This interrupt handling model was the easiest to implement but it has some major drawbacks:

• The current garbage collector is neither concurrent nor incremental, which could lead to severe loss of interrupt during a long garbage collection.
• It relies on the ability of the i8259A programmable interrupt controller (PIC) to accept Specific End Of Interrupt signals. This feature may not be available on other PICs.
• The current Haskell scheduler does not support multiple priority levels; many threads running concurrently could delay handling an interrupt for a long time.

We plan to improve this aspect in future versions.

Boot process

GRUB already takes care of setting up x86 protected mode, which makes the boot process easier.

------- C land start.S | Load static, flat-memory GDT (segment descriptors) | Initialize the memory to 0xCC (IA32 breakpoint instruction) | Initialize the C stack | Jump to c_start c_start.c | Initialize PIC (IRQs 0-15 mapped to interrupts 0x20-0x2F) | Initialize IDT (interrupt vectors) | Initialize Haskell block allocator (MBlock_init) | Pass control to the RTS ------- Haskell land Main.hs | Start a console driver which handles a basic x86 text console | Start a keyboard controller | Start an idle thread | Bind the keyboard and console driver to a simple Readline clone | which allows shell-like interaction with the system