Merge lib into kern

There are no precise enough criteria to justify the separation of these
two directories.

19 files changed, 2318 insertions, 16 deletions

diff --git a/kern/assert.h b/kern/assert.h
new file mode 100644
index 00000000..d0fd08a5
--- /dev/null
+++ b/kern/assert.h
@@ -0,0 +1,40 @@
+/*
+ * Copyright (c) 2010 Richard Braun.
+ *
+ * This program is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program.  If not, see <http://www.gnu.org/licenses/>.
+ */
+
+#ifndef _KERN_ASSERT_H
+#define _KERN_ASSERT_H
+
+#ifdef NDEBUG
+#define assert(expression) ((void)(expression))
+#else /* NDEBUG */
+
+#include <kern/macros.h>
+#include <kern/panic.h>
+
+/*
+ * Panic if the given expression is false.
+ */
+#define assert(expression)                                          \
+MACRO_BEGIN                                                         \
+    if (unlikely(!(expression)))                                    \
+        panic("assertion (%s) failed in %s:%d, function %s()",      \
+              __QUOTE(expression), __FILE__, __LINE__, __func__);   \
+MACRO_END
+
+#endif /* NDEBUG */
+
+#endif /* _KERN_ASSERT_H */
diff --git a/kern/init.h b/kern/init.h
index e9762724..6e437c0a 100644
--- a/kern/init.h
+++ b/kern/init.h
@@ -18,7 +18,7 @@
 #ifndef _KERN_INIT_H
 #define _KERN_INIT_H
 
-#include <lib/macros.h>
+#include <kern/macros.h>
 
 /*
  * These sections should contain code and data which can be discarded once
diff --git a/kern/kmem.c b/kern/kmem.c
index 663cafe2..70aeebb6 100644
--- a/kern/kmem.c
+++ b/kern/kmem.c
@@ -48,20 +48,20 @@
  * handled likewise.
  */
 
+#include <kern/assert.h>
 #include <kern/init.h>
+#include <kern/limits.h>
+#include <kern/list.h>
 #include <kern/kmem.h>
+#include <kern/macros.h>
 #include <kern/panic.h>
 #include <kern/param.h>
 #include <kern/printk.h>
-#include <lib/assert.h>
-#include <lib/limits.h>
-#include <lib/list.h>
-#include <lib/macros.h>
-#include <lib/rbtree.h>
-#include <lib/sprintf.h>
-#include <lib/stddef.h>
-#include <lib/stdint.h>
-#include <lib/string.h>
+#include <kern/rbtree.h>
+#include <kern/sprintf.h>
+#include <kern/stddef.h>
+#include <kern/stdint.h>
+#include <kern/string.h>
 #include <machine/cpu.h>
 #include <vm/vm_kmem.h>
 
diff --git a/kern/kmem.h b/kern/kmem.h
index dee4a857..350c8977 100644
--- a/kern/kmem.h
+++ b/kern/kmem.h
@@ -21,10 +21,10 @@
 #ifndef _KERN_KMEM_H
 #define _KERN_KMEM_H
 
+#include <kern/list.h>
 #include <kern/param.h>
-#include <lib/list.h>
-#include <lib/rbtree.h>
-#include <lib/stddef.h>
+#include <kern/rbtree.h>
+#include <kern/stddef.h>
 
 /*
  * Per-processor cache of pre-constructed objects.
diff --git a/kern/limits.h b/kern/limits.h
new file mode 100644
index 00000000..48f4b945
--- /dev/null
+++ b/kern/limits.h
@@ -0,0 +1,23 @@
+/*
+ * Copyright (c) 2010 Richard Braun.
+ *
+ * This program is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program.  If not, see <http://www.gnu.org/licenses/>.
+ */
+
+#ifndef _KERN_LIMITS_H
+#define _KERN_LIMITS_H
+
+#define CHAR_BIT 8
+
+#endif /* _KERN_LIMITS_H */
diff --git a/kern/list.h b/kern/list.h
new file mode 100644
index 00000000..647e94c9
--- /dev/null
+++ b/kern/list.h
@@ -0,0 +1,364 @@
+/*
+ * Copyright (c) 2009, 2010 Richard Braun.
+ *
+ * This program is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program.  If not, see <http://www.gnu.org/licenses/>.
+ *
+ *
+ * Simple doubly-linked list.
+ */
+
+#ifndef _KERN_LIST_H
+#define _KERN_LIST_H
+
+#include <kern/macros.h>
+#include <kern/stddef.h>
+
+/*
+ * Structure used as both head and node.
+ *
+ * This implementation relies on using the same type for both heads and nodes.
+ *
+ * It is recommended to encode the use of struct list variables in their names,
+ * e.g. struct list free_list or struct list free_objects is a good hint for a
+ * list of free objects. A declaration like struct list free_node clearly
+ * indicates it is used as part of a node in the free list.
+ */
+struct list {
+    struct list *prev;
+    struct list *next;
+};
+
+/*
+ * Static list initializer.
+ */
+#define LIST_INITIALIZER(list) { &(list), &(list) }
+
+/*
+ * Initialize a list.
+ */
+static inline void
+list_init(struct list *list)
+{
+    list->prev = list;
+    list->next = list;
+}
+
+/*
+ * Initialize a list node.
+ *
+ * An entry is in no list when its node members point to NULL.
+ */
+static inline void
+list_node_init(struct list *node)
+{
+    node->prev = NULL;
+    node->next = NULL;
+}
+
+/*
+ * Return true if node is in no list.
+ */
+static inline int
+list_node_unlinked(const struct list *node)
+{
+    return node->prev == NULL;
+}
+
+/*
+ * Macro that evaluates to the address of the structure containing the
+ * given node based on the given type and member.
+ */
+#define list_entry(node, type, member) structof(node, type, member)
+
+/*
+ * Return the first node of a list.
+ */
+static inline struct list *
+list_first(const struct list *list)
+{
+    return list->next;
+}
+
+/*
+ * Return the last node of a list.
+ */
+static inline struct list *
+list_last(const struct list *list)
+{
+    return list->prev;
+}
+
+/*
+ * Return the node next to the given node.
+ */
+static inline struct list *
+list_next(const struct list *node)
+{
+    return node->next;
+}
+
+/*
+ * Return the node previous to the given node.
+ */
+static inline struct list *
+list_prev(const struct list *node)
+{
+    return node->prev;
+}
+
+/*
+ * Get the first entry of a list.
+ */
+#define list_first_entry(list, type, member) \
+    list_entry(list_first(list), type, member)
+
+/*
+ * Get the last entry of a list.
+ */
+#define list_last_entry(list, type, member) \
+    list_entry(list_last(list), type, member)
+
+/*
+ * Return true if node is after the last or before the first node of the list.
+ */
+static inline int
+list_end(const struct list *list, const struct list *node)
+{
+    return list == node;
+}
+
+/*
+ * Return true if list is empty.
+ */
+static inline int
+list_empty(const struct list *list)
+{
+    return list == list->next;
+}
+
+/*
+ * Return true if list contains exactly one node.
+ */
+static inline int
+list_singular(const struct list *list)
+{
+    return (list != list->next) && (list->next == list->prev);
+}
+
+/*
+ * Split list2 by moving its nodes up to (but not including) the given
+ * node into list1 (which can be in a stale state).
+ *
+ * If list2 is empty, or node is list2 or list2->next, nothing is done.
+ */
+static inline void
+list_split(struct list *list1, struct list *list2, struct list *node)
+{
+    if (list_empty(list2) || (list2->next == node) || list_end(list2, node))
+        return;
+
+    list1->next = list2->next;
+    list1->next->prev = list1;
+
+    list1->prev = node->prev;
+    node->prev->next = list1;
+
+    list2->next = node;
+    node->prev = list2;
+}
+
+/*
+ * Append the nodes of list2 at the end of list1.
+ *
+ * After completion, list2 is stale.
+ */
+static inline void
+list_concat(struct list *list1, const struct list *list2)
+{
+    struct list *last1, *first2, *last2;
+
+    if (list_empty(list2))
+        return;
+
+    last1 = list1->prev;
+    first2 = list2->next;
+    last2 = list2->prev;
+
+    last1->next = first2;
+    first2->prev = last1;
+
+    last2->next = list1;
+    list1->prev = last2;
+}
+
+/*
+ * Set the new head of a list.
+ *
+ * This function is an optimized version of :
+ * list_init(&new_list);
+ * list_concat(&new_list, &old_list);
+ *
+ * After completion, old_head is stale.
+ */
+static inline void
+list_set_head(struct list *new_head, const struct list *old_head)
+{
+    if (list_empty(old_head)) {
+        list_init(new_head);
+        return;
+    }
+
+    *new_head = *old_head;
+    new_head->next->prev = new_head;
+    new_head->prev->next = new_head;
+}
+
+/*
+ * Add a node between two nodes.
+ */
+static inline void
+list_add(struct list *prev, struct list *next, struct list *node)
+{
+    next->prev = node;
+    node->next = next;
+
+    prev->next = node;
+    node->prev = prev;
+}
+
+/*
+ * Insert a node at the head of a list.
+ */
+static inline void
+list_insert(struct list *list, struct list *node)
+{
+    list_add(list, list->next, node);
+}
+
+/*
+ * Insert a node at the tail of a list.
+ */
+static inline void
+list_insert_tail(struct list *list, struct list *node)
+{
+    list_add(list->prev, list, node);
+}
+
+/*
+ * Insert a node before another node.
+ */
+static inline void
+list_insert_before(struct list *next, struct list *node)
+{
+    list_add(next->prev, next, node);
+}
+
+/*
+ * Insert a node after another node.
+ */
+static inline void
+list_insert_after(struct list *prev, struct list *node)
+{
+    list_add(prev, prev->next, node);
+}
+
+/*
+ * Remove a node from a list.
+ *
+ * After completion, the node is stale.
+ */
+static inline void
+list_remove(struct list *node)
+{
+    node->prev->next = node->next;
+    node->next->prev = node->prev;
+}
+
+/*
+ * Forge a loop to process all nodes of a list.
+ *
+ * The node must not be altered during the loop.
+ */
+#define list_for_each(list, node)   \
+for (node = list_first(list);       \
+     !list_end(list, node);         \
+     node = list_next(node))
+
+/*
+ * Forge a loop to process all nodes of a list.
+ */
+#define list_for_each_safe(list, node, tmp)             \
+for (node = list_first(list), tmp = list_next(node);    \
+     !list_end(list, node);                             \
+     node = tmp, tmp = list_next(node))
+
+/*
+ * Version of list_for_each() that processes nodes backward.
+ */
+#define list_for_each_reverse(list, node)   \
+for (node = list_last(list);                \
+     !list_end(list, node);                 \
+     node = list_prev(node))
+
+/*
+ * Version of list_for_each_safe() that processes nodes backward.
+ */
+#define list_for_each_reverse_safe(list, node, tmp) \
+for (node = list_last(list), tmp = list_prev(node); \
+     !list_end(list, node);                         \
+     node = tmp, tmp = list_prev(node))
+
+/*
+ * Forge a loop to process all entries of a list.
+ *
+ * The entry node must not be altered during the loop.
+ */
+#define list_for_each_entry(list, entry, member)                    \
+for (entry = list_entry(list_first(list), typeof(*entry), member);  \
+     !list_end(list, &entry->member);                               \
+     entry = list_entry(list_next(&entry->member), typeof(*entry),  \
+                        member))
+
+/*
+ * Forge a loop to process all entries of a list.
+ */
+#define list_for_each_entry_safe(list, entry, tmp, member)          \
+for (entry = list_entry(list_first(list), typeof(*entry), member),  \
+       tmp = list_entry(list_next(&entry->member), typeof(*entry),  \
+                        member);                                    \
+     !list_end(list, &entry->member);                               \
+     entry = tmp, tmp = list_entry(list_next(&entry->member),       \
+                                   typeof(*entry), member))
+
+/*
+ * Version of list_for_each_entry() that processes entries backward.
+ */
+#define list_for_each_entry_reverse(list, entry, member)            \
+for (entry = list_entry(list_last(list), typeof(*entry), member);   \
+     !list_end(list, &entry->member);                               \
+     entry = list_entry(list_prev(&entry->member), typeof(*entry),  \
+                        member))
+
+/*
+ * Version of list_for_each_entry_safe() that processes entries backward.
+ */
+#define list_for_each_entry_reverse_safe(list, entry, tmp, member)  \
+for (entry = list_entry(list_last(list), typeof(*entry), member),   \
+       tmp = list_entry(list_prev(&entry->member), typeof(*entry),  \
+                        member);                                    \
+     !list_end(list, &entry->member);                               \
+     entry = tmp, tmp = list_entry(list_prev(&entry->member),       \
+                                   typeof(*entry), member))
+
+#endif /* _KERN_LIST_H */
diff --git a/kern/macros.h b/kern/macros.h
new file mode 100644
index 00000000..012dd15b
--- /dev/null
+++ b/kern/macros.h
@@ -0,0 +1,73 @@
+/*
+ * Copyright (c) 2009, 2010 Richard Braun.
+ *
+ * This program is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program.  If not, see <http://www.gnu.org/licenses/>.
+ *
+ *
+ * Helper macros.
+ */
+
+#ifndef _KERN_MACROS_H
+#define _KERN_MACROS_H
+
+#ifndef __ASSEMBLER__
+#include <kern/stddef.h>
+#endif /* __ASSEMBLER__ */
+
+#define MACRO_BEGIN         ({
+#define MACRO_END           })
+
+#define __QUOTE(x)          #x
+#define QUOTE(x)            __QUOTE(x)
+
+#ifdef __ASSEMBLER__
+#define DECL_CONST(x, s)    x
+#else /* __ASSEMBLER__ */
+#define __DECL_CONST(x, s)  x##s
+#define DECL_CONST(x, s)    __DECL_CONST(x, s)
+#endif /* __ASSEMBLER__ */
+
+#define STRLEN(x)           (sizeof(x) - 1)
+#define ARRAY_SIZE(x)       (sizeof(x) / sizeof((x)[0]))
+
+#define MIN(a, b)           ((a) < (b) ? (a) : (b))
+#define MAX(a, b)           ((a) > (b) ? (a) : (b))
+
+#define P2ALIGNED(x, a)     (((x) & ((a) - 1)) == 0)
+#define ISP2(x)             P2ALIGNED(x, x)
+#define P2ALIGN(x, a)       ((x) & -(a))
+#define P2ROUND(x, a)       (-(-(x) & -(a)))
+#define P2END(x, a)         (-(~(x) & -(a)))
+
+#define structof(ptr, type, member) \
+    ((type *)((char *)ptr - offsetof(type, member)))
+
+#define alignof(x)          __alignof__(x)
+
+#define likely(expr)        __builtin_expect(!!(expr), 1)
+#define unlikely(expr)      __builtin_expect(!!(expr), 0)
+
+#define barrier()           asm volatile("" : : : "memory")
+
+#define __noreturn          __attribute__((noreturn))
+#define __aligned(x)        __attribute__((aligned(x)))
+#define __always_inline     inline __attribute__((always_inline))
+#define __section(x)        __attribute__((section(x)))
+#define __packed            __attribute__((packed))
+#define __alias(x)          __attribute__((alias(x)))
+
+#define __format_printf(fmt, args) \
+    __attribute__((format(printf, fmt, args)))
+
+#endif /* _KERN_MACROS_H */
diff --git a/kern/panic.h b/kern/panic.h
index a3bfbbe2..9d1d31e0 100644
--- a/kern/panic.h
+++ b/kern/panic.h
@@ -18,7 +18,7 @@
 #ifndef _KERN_PANIC_H
 #define _KERN_PANIC_H
 
-#include <lib/macros.h>
+#include <kern/macros.h>
 
 /*
  * Print the given message and halt the system immediately.
diff --git a/kern/printk.c b/kern/printk.c
index 38d835c0..386ac979 100644
--- a/kern/printk.c
+++ b/kern/printk.c
@@ -17,7 +17,7 @@
 
 #include <kern/printk.h>
 #include <kern/spinlock.h>
-#include <lib/sprintf.h>
+#include <kern/sprintf.h>
 
 /*
  * Size of the static buffer.
diff --git a/kern/printk.h b/kern/printk.h
index 37f25453..5e2a871b 100644
--- a/kern/printk.h
+++ b/kern/printk.h
@@ -29,7 +29,7 @@
 
 #include <stdarg.h>
 
-#include <lib/macros.h>
+#include <kern/macros.h>
 
 int printk(const char *format, ...) __format_printf(1, 2);
 int vprintk(const char *format, va_list ap) __format_printf(1, 0);
diff --git a/kern/rbtree.c b/kern/rbtree.c
new file mode 100644
index 00000000..569d3fac
--- /dev/null
+++ b/kern/rbtree.c
@@ -0,0 +1,489 @@
+/*
+ * Copyright (c) 2010, 2012 Richard Braun.
+ *
+ * This program is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program.  If not, see <http://www.gnu.org/licenses/>.
+ */
+
+#include <kern/assert.h>
+#include <kern/macros.h>
+#include <kern/rbtree.h>
+#include <kern/rbtree_i.h>
+#include <kern/stddef.h>
+
+/*
+ * Return the index of a node in the children array of its parent.
+ *
+ * The parent parameter must not be null, and must be the parent of the
+ * given node.
+ */
+static inline int
+rbtree_node_index(const struct rbtree_node *node,
+                  const struct rbtree_node *parent)
+{
+    assert(parent != NULL);
+    assert((node == NULL) || (rbtree_node_parent(node) == parent));
+
+    if (parent->children[RBTREE_LEFT] == node)
+        return RBTREE_LEFT;
+
+    assert(parent->children[RBTREE_RIGHT] == node);
+
+    return RBTREE_RIGHT;
+}
+
+/*
+ * Return the color of a node.
+ */
+static inline int
+rbtree_node_color(const struct rbtree_node *node)
+{
+    return node->parent & RBTREE_COLOR_MASK;
+}
+
+/*
+ * Return true if the node is red.
+ */
+static inline int
+rbtree_node_is_red(const struct rbtree_node *node)
+{
+    return rbtree_node_color(node) == RBTREE_COLOR_RED;
+}
+
+/*
+ * Return true if the node is black.
+ */
+static inline int
+rbtree_node_is_black(const struct rbtree_node *node)
+{
+    return rbtree_node_color(node) == RBTREE_COLOR_BLACK;
+}
+
+/*
+ * Set the parent of a node, retaining its current color.
+ */
+static inline void
+rbtree_node_set_parent(struct rbtree_node *node, struct rbtree_node *parent)
+{
+    assert(rbtree_node_check_alignment(node));
+    assert(rbtree_node_check_alignment(parent));
+
+    node->parent = (unsigned long)parent | (node->parent & RBTREE_COLOR_MASK);
+}
+
+/*
+ * Set the color of a node, retaining its current parent.
+ */
+static inline void
+rbtree_node_set_color(struct rbtree_node *node, int color)
+{
+    assert((color & ~RBTREE_COLOR_MASK) == 0);
+    node->parent = (node->parent & RBTREE_PARENT_MASK) | color;
+}
+
+/*
+ * Set the color of a node to red, retaining its current parent.
+ */
+static inline void
+rbtree_node_set_red(struct rbtree_node *node)
+{
+    rbtree_node_set_color(node, RBTREE_COLOR_RED);
+}
+
+/*
+ * Set the color of a node to black, retaining its current parent.
+ */
+static inline void
+rbtree_node_set_black(struct rbtree_node *node)
+{
+    rbtree_node_set_color(node, RBTREE_COLOR_BLACK);
+}
+
+/*
+ * Return the left-most deepest child node of the given node.
+ */
+static struct rbtree_node *
+rbtree_node_find_deepest(struct rbtree_node *node)
+{
+    struct rbtree_node *parent;
+
+    assert(node != NULL);
+
+    for (;;) {
+        parent = node;
+        node = node->children[RBTREE_LEFT];
+
+        if (node == NULL) {
+            node = parent->children[RBTREE_RIGHT];
+
+            if (node == NULL)
+                return parent;
+        }
+    }
+}
+
+/*
+ * Perform a tree rotation, rooted at the given node.
+ *
+ * The direction parameter defines the rotation direction and is either
+ * RBTREE_LEFT or RBTREE_RIGHT.
+ */
+static void
+rbtree_rotate(struct rbtree *tree, struct rbtree_node *node, int direction)
+{
+    struct rbtree_node *parent, *rnode;
+    int left, right;
+
+    left = direction;
+    right = 1 - left;
+    parent = rbtree_node_parent(node);
+    rnode = node->children[right];
+
+    node->children[right] = rnode->children[left];
+
+    if (rnode->children[left] != NULL)
+        rbtree_node_set_parent(rnode->children[left], node);
+
+    rnode->children[left] = node;
+    rbtree_node_set_parent(rnode, parent);
+
+    if (unlikely(parent == NULL))
+        tree->root = rnode;
+    else
+        parent->children[rbtree_node_index(node, parent)] = rnode;
+
+    rbtree_node_set_parent(node, rnode);
+}
+
+void
+rbtree_insert_rebalance(struct rbtree *tree, struct rbtree_node *parent,
+                        int index, struct rbtree_node *node)
+{
+    struct rbtree_node *grand_parent, *uncle, *tmp;
+    int left, right;
+
+    assert(rbtree_node_check_alignment(parent));
+    assert(rbtree_node_check_alignment(node));
+
+    node->parent = (unsigned long)parent | RBTREE_COLOR_RED;
+    node->children[RBTREE_LEFT] = NULL;
+    node->children[RBTREE_RIGHT] = NULL;
+
+    if (unlikely(parent == NULL))
+        tree->root = node;
+    else
+        parent->children[index] = node;
+
+    for (;;) {
+        if (parent == NULL) {
+            rbtree_node_set_black(node);
+            break;
+        }
+
+        if (rbtree_node_is_black(parent))
+            break;
+
+        grand_parent = rbtree_node_parent(parent);
+        assert(grand_parent != NULL);
+
+        left = rbtree_node_index(parent, grand_parent);
+        right = 1 - left;
+
+        uncle = grand_parent->children[right];
+
+        /*
+         * Uncle is red. Flip colors and repeat at grand parent.
+         */
+        if ((uncle != NULL) && rbtree_node_is_red(uncle)) {
+            rbtree_node_set_black(uncle);
+            rbtree_node_set_black(parent);
+            rbtree_node_set_red(grand_parent);
+            node = grand_parent;
+            parent = rbtree_node_parent(node);
+            continue;
+        }
+
+        /*
+         * Node is the right child of its parent. Rotate left at parent.
+         */
+        if (parent->children[right] == node) {
+            rbtree_rotate(tree, parent, left);
+            tmp = node;
+            node = parent;
+            parent = tmp;
+        }
+
+        /*
+         * Node is the left child of its parent. Handle colors, rotate right
+         * at grand parent, and leave.
+         */
+        rbtree_node_set_black(parent);
+        rbtree_node_set_red(grand_parent);
+        rbtree_rotate(tree, grand_parent, right);
+        break;
+    }
+
+    assert(rbtree_node_is_black(tree->root));
+}
+
+void
+rbtree_remove(struct rbtree *tree, struct rbtree_node *node)
+{
+    struct rbtree_node *child, *parent, *brother;
+    int color, left, right;
+
+    if (node->children[RBTREE_LEFT] == NULL)
+        child = node->children[RBTREE_RIGHT];
+    else if (node->children[RBTREE_RIGHT] == NULL)
+        child = node->children[RBTREE_LEFT];
+    else {
+        struct rbtree_node *successor;
+
+        /*
+         * Two-children case: replace the node with its successor.
+         */
+
+        successor = node->children[RBTREE_RIGHT];
+
+        while (successor->children[RBTREE_LEFT] != NULL)
+            successor = successor->children[RBTREE_LEFT];
+
+        color = rbtree_node_color(successor);
+        child = successor->children[RBTREE_RIGHT];
+        parent = rbtree_node_parent(node);
+
+        if (unlikely(parent == NULL))
+            tree->root = successor;
+        else
+            parent->children[rbtree_node_index(node, parent)] = successor;
+
+        parent = rbtree_node_parent(successor);
+
+        /*
+         * Set parent directly to keep the original color.
+         */
+        successor->parent = node->parent;
+        successor->children[RBTREE_LEFT] = node->children[RBTREE_LEFT];
+        rbtree_node_set_parent(successor->children[RBTREE_LEFT], successor);
+
+        if (node == parent)
+            parent = successor;
+        else {
+            successor->children[RBTREE_RIGHT] = node->children[RBTREE_RIGHT];
+            rbtree_node_set_parent(successor->children[RBTREE_RIGHT],
+                                   successor);
+            parent->children[RBTREE_LEFT] = child;
+
+            if (child != NULL)
+                rbtree_node_set_parent(child, parent);
+        }
+
+        goto update_color;
+    }
+
+    /*
+     * Node has at most one child.
+     */
+
+    color = rbtree_node_color(node);
+    parent = rbtree_node_parent(node);
+
+    if (child != NULL)
+        rbtree_node_set_parent(child, parent);
+
+    if (unlikely(parent == NULL))
+        tree->root = child;
+    else
+        parent->children[rbtree_node_index(node, parent)] = child;
+
+    /*
+     * The node has been removed, update the colors. The child pointer can
+     * be null, in which case it is considered a black leaf.
+     */
+update_color:
+    if (color == RBTREE_COLOR_RED)
+        return;
+
+    for (;;) {
+        if ((child != NULL) && rbtree_node_is_red(child)) {
+            rbtree_node_set_black(child);
+            break;
+        }
+
+        if (parent == NULL)
+            break;
+
+        left = rbtree_node_index(child, parent);
+        right = 1 - left;
+
+        brother = parent->children[right];
+
+        /*
+         * Brother is red. Recolor and rotate left at parent so that brother
+         * becomes black.
+         */
+        if (rbtree_node_is_red(brother)) {
+            rbtree_node_set_black(brother);
+            rbtree_node_set_red(parent);
+            rbtree_rotate(tree, parent, left);
+            brother = parent->children[right];
+        }
+
+        /*
+         * Brother has no red child. Recolor and repeat at parent.
+         */
+        if (((brother->children[RBTREE_LEFT] == NULL)
+             || rbtree_node_is_black(brother->children[RBTREE_LEFT]))
+            && ((brother->children[RBTREE_RIGHT] == NULL)
+                || rbtree_node_is_black(brother->children[RBTREE_RIGHT]))) {
+            rbtree_node_set_red(brother);
+            child = parent;
+            parent = rbtree_node_parent(child);
+            continue;
+        }
+
+        /*
+         * Brother's right child is black. Recolor and rotate right at brother.
+         */
+        if ((brother->children[right] == NULL)
+            || rbtree_node_is_black(brother->children[right])) {
+            rbtree_node_set_black(brother->children[left]);
+            rbtree_node_set_red(brother);
+            rbtree_rotate(tree, brother, right);
+            brother = parent->children[right];
+        }
+
+        /*
+         * Brother's left child is black. Exchange parent and brother colors
+         * (we already know brother is black), set brother's right child black,
+         * rotate left at parent and leave.
+         */
+        rbtree_node_set_color(brother, rbtree_node_color(parent));
+        rbtree_node_set_black(parent);
+        rbtree_node_set_black(brother->children[right]);
+        rbtree_rotate(tree, parent, left);
+        break;
+    }
+
+    assert((tree->root == NULL) || rbtree_node_is_black(tree->root));
+}
+
+struct rbtree_node *
+rbtree_nearest(struct rbtree_node *parent, int index, int direction)
+{
+    assert(rbtree_check_index(direction));
+
+    if (parent == NULL)
+        return NULL;
+
+    assert(rbtree_check_index(index));
+
+    if (index != direction)
+        return parent;
+
+    return rbtree_walk(parent, direction);
+}
+
+struct rbtree_node *
+rbtree_firstlast(const struct rbtree *tree, int direction)
+{
+    struct rbtree_node *prev, *cur;
+
+    assert(rbtree_check_index(direction));
+
+    prev = NULL;
+
+    for (cur = tree->root; cur != NULL; cur = cur->children[direction])
+        prev = cur;
+
+    return prev;
+}
+
+struct rbtree_node *
+rbtree_walk(struct rbtree_node *node, int direction)
+{
+    int left, right;
+
+    assert(rbtree_check_index(direction));
+
+    left = direction;
+    right = 1 - left;
+
+    if (node == NULL)
+        return NULL;
+
+    if (node->children[left] != NULL) {
+        node = node->children[left];
+
+        while (node->children[right] != NULL)
+            node = node->children[right];
+    } else {
+        struct rbtree_node *parent;
+        int index;
+
+        for (;;) {
+            parent = rbtree_node_parent(node);
+
+            if (parent == NULL)
+                return NULL;
+
+            index = rbtree_node_index(node, parent);
+            node = parent;
+
+            if (index == right)
+                break;
+        }
+    }
+
+    return node;
+}
+
+struct rbtree_node *
+rbtree_postwalk_deepest(const struct rbtree *tree)
+{
+    struct rbtree_node *node;
+
+    node = tree->root;
+
+    if (node == NULL)
+        return NULL;
+
+    return rbtree_node_find_deepest(node);
+}
+
+struct rbtree_node *
+rbtree_postwalk_unlink(struct rbtree_node *node)
+{
+    struct rbtree_node *parent;
+    int index;
+
+    if (node == NULL)
+        return NULL;
+
+    assert(node->children[RBTREE_LEFT] == NULL);
+    assert(node->children[RBTREE_RIGHT] == NULL);
+
+    parent = rbtree_node_parent(node);
+
+    if (parent == NULL)
+        return NULL;
+
+    index = rbtree_node_index(node, parent);
+    parent->children[index] = NULL;
+    node = parent->children[RBTREE_RIGHT];
+
+    if (node == NULL)
+        return parent;
+
+    return rbtree_node_find_deepest(node);
+}
diff --git a/kern/rbtree.h b/kern/rbtree.h
new file mode 100644
index 00000000..45521c13
--- /dev/null
+++ b/kern/rbtree.h
@@ -0,0 +1,299 @@
+/*
+ * Copyright (c) 2010, 2011, 2012 Richard Braun.
+ *
+ * This program is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program.  If not, see <http://www.gnu.org/licenses/>.
+ *
+ *
+ * Red-black tree.
+ */
+
+#ifndef _KERN_RBTREE_H
+#define _KERN_RBTREE_H
+
+#include <kern/assert.h>
+#include <kern/macros.h>
+#include <kern/stddef.h>
+
+/*
+ * Indexes of the left and right nodes in the children array of a node.
+ */
+#define RBTREE_LEFT     0
+#define RBTREE_RIGHT    1
+
+/*
+ * Red-black node.
+ */
+struct rbtree_node;
+
+/*
+ * Red-black tree.
+ */
+struct rbtree;
+
+/*
+ * Static tree initializer.
+ */
+#define RBTREE_INITIALIZER { NULL }
+
+#include <kern/rbtree_i.h>
+
+/*
+ * Initialize a tree.
+ */
+static inline void
+rbtree_init(struct rbtree *tree)
+{
+    tree->root = NULL;
+}
+
+/*
+ * Initialize a node.
+ *
+ * A node is in no tree when its parent points to itself.
+ */
+static inline void
+rbtree_node_init(struct rbtree_node *node)
+{
+    assert(rbtree_node_check_alignment(node));
+
+    node->parent = (unsigned long)node | RBTREE_COLOR_RED;
+    node->children[RBTREE_LEFT] = NULL;
+    node->children[RBTREE_RIGHT] = NULL;
+}
+
+/*
+ * Return true if node is in no tree.
+ */
+static inline int
+rbtree_node_unlinked(const struct rbtree_node *node)
+{
+    return rbtree_node_parent(node) == node;
+}
+
+/*
+ * Macro that evaluates to the address of the structure containing the
+ * given node based on the given type and member.
+ */
+#define rbtree_entry(node, type, member) structof(node, type, member)
+
+/*
+ * Return true if tree is empty.
+ */
+static inline int
+rbtree_empty(const struct rbtree *tree)
+{
+    return tree->root == NULL;
+}
+
+/*
+ * Look up a node in a tree.
+ *
+ * Note that implementing the lookup algorithm as a macro gives two benefits:
+ * First, it avoids the overhead of a callback function. Next, the type of the
+ * cmp_fn parameter isn't rigid. The only guarantee offered by this
+ * implementation is that the key parameter is the first parameter given to
+ * cmp_fn. This way, users can pass only the value they need for comparison
+ * instead of e.g. allocating a full structure on the stack.
+ *
+ * See rbtree_insert().
+ */
+#define rbtree_lookup(tree, key, cmp_fn)        \
+MACRO_BEGIN                                     \
+    struct rbtree_node *cur;                    \
+    int diff;                                   \
+                                                \
+    cur = (tree)->root;                         \
+                                                \
+    while (cur != NULL) {                       \
+        diff = cmp_fn(key, cur);                \
+                                                \
+        if (diff == 0)                          \
+            break;                              \
+                                                \
+        cur = cur->children[rbtree_d2i(diff)];  \
+    }                                           \
+                                                \
+    cur;                                        \
+MACRO_END
+
+/*
+ * Look up a node or one of its nearest nodes in a tree.
+ *
+ * This macro essentially acts as rbtree_lookup() but if no entry matched
+ * the key, an additional step is performed to obtain the next or previous
+ * node, depending on the direction (left or right).
+ *
+ * The constraints that apply to the key parameter are the same as for
+ * rbtree_lookup().
+ */
+#define rbtree_lookup_nearest(tree, key, cmp_fn, dir)   \
+MACRO_BEGIN                                             \
+    struct rbtree_node *cur, *prev;                     \
+    int diff, index;                                    \
+                                                        \
+    prev = NULL;                                        \
+    index = -1;                                         \
+    cur = (tree)->root;                                 \
+                                                        \
+    while (cur != NULL) {                               \
+        diff = cmp_fn(key, cur);                        \
+                                                        \
+        if (diff == 0)                                  \
+            break;                                      \
+                                                        \
+        prev = cur;                                     \
+        index = rbtree_d2i(diff);                       \
+        cur = cur->children[index];                     \
+    }                                                   \
+                                                        \
+    if (cur == NULL)                                    \
+        cur = rbtree_nearest(prev, index, dir);         \
+                                                        \
+    cur;                                                \
+MACRO_END
+
+/*
+ * Insert a node in a tree.
+ *
+ * This macro performs a standard lookup to obtain the insertion point of
+ * the given node in the tree (it is assumed that the inserted node never
+ * compares equal to any other entry in the tree) and links the node. It
+ * then checks red-black rules violations, and rebalances the tree if
+ * necessary.
+ *
+ * Unlike rbtree_lookup(), the cmp_fn parameter must compare two complete
+ * entries, so it is suggested to use two different comparison inline
+ * functions, such as myobj_cmp_lookup() and myobj_cmp_insert(). There is no
+ * guarantee about the order of the nodes given to the comparison function.
+ *
+ * See rbtree_lookup().
+ */
+#define rbtree_insert(tree, node, cmp_fn)               \
+MACRO_BEGIN                                             \
+    struct rbtree_node *cur, *prev;                     \
+    int diff, index;                                    \
+                                                        \
+    prev = NULL;                                        \
+    index = -1;                                         \
+    cur = (tree)->root;                                 \
+                                                        \
+    while (cur != NULL) {                               \
+        diff = cmp_fn(node, cur);                       \
+        assert(diff != 0);                              \
+        prev = cur;                                     \
+        index = rbtree_d2i(diff);                       \
+        cur = cur->children[index];                     \
+    }                                                   \
+                                                        \
+    rbtree_insert_rebalance(tree, prev, index, node);   \
+MACRO_END
+
+/*
+ * Look up a node/slot pair in a tree.
+ *
+ * This macro essentially acts as rbtree_lookup() but in addition to a node,
+ * it also returns a slot, which identifies an insertion point in the tree.
+ * If the returned node is null, the slot can be used by rbtree_insert_slot()
+ * to insert without the overhead of an additional lookup. The slot is a
+ * simple unsigned long integer.
+ *
+ * The constraints that apply to the key parameter are the same as for
+ * rbtree_lookup().
+ */
+#define rbtree_lookup_slot(tree, key, cmp_fn, slot) \
+MACRO_BEGIN                                         \
+    struct rbtree_node *cur, *prev;                 \
+    int diff, index;                                \
+                                                    \
+    prev = NULL;                                    \
+    index = 0;                                      \
+    cur = (tree)->root;                             \
+                                                    \
+    while (cur != NULL) {                           \
+        diff = cmp_fn(key, cur);                    \
+                                                    \
+        if (diff == 0)                              \
+            break;                                  \
+                                                    \
+        prev = cur;                                 \
+        index = rbtree_d2i(diff);                   \
+        cur = cur->children[index];                 \
+    }                                               \
+                                                    \
+    (slot) = rbtree_slot(prev, index);              \
+    cur;                                            \
+MACRO_END
+
+/*
+ * Insert a node at an insertion point in a tree.
+ *
+ * This macro essentially acts as rbtree_insert() except that it doesn't
+ * obtain the insertion point with a standard lookup. The insertion point
+ * is obtained by calling rbtree_lookup_slot(). In addition, the new node
+ * must not compare equal to an existing node in the tree (i.e. the slot
+ * must denote a null node).
+ */
+#define rbtree_insert_slot(tree, slot, node)            \
+MACRO_BEGIN                                             \
+    struct rbtree_node *parent;                         \
+    int index;                                          \
+                                                        \
+    parent = rbtree_slot_parent(slot);                  \
+    index = rbtree_slot_index(slot);                    \
+    rbtree_insert_rebalance(tree, parent, index, node); \
+MACRO_END
+
+/*
+ * Remove a node from a tree.
+ *
+ * After completion, the node is stale.
+ */
+void rbtree_remove(struct rbtree *tree, struct rbtree_node *node);
+
+/*
+ * Return the first node of a tree.
+ */
+#define rbtree_first(tree) rbtree_firstlast(tree, RBTREE_LEFT)
+
+/*
+ * Return the last node of a tree.
+ */
+#define rbtree_last(tree) rbtree_firstlast(tree, RBTREE_RIGHT)
+
+/*
+ * Return the node previous to the given node.
+ */
+#define rbtree_prev(node) rbtree_walk(node, RBTREE_LEFT)
+
+/*
+ * Return the node next to the given node.
+ */
+#define rbtree_next(node) rbtree_walk(node, RBTREE_RIGHT)
+
+/*
+ * Forge a loop to process all nodes of a tree, removing them when visited.
+ *
+ * This macro can only be used to destroy a tree, so that the resources used
+ * by the entries can be released by the user. It basically removes all nodes
+ * without doing any color checking.
+ *
+ * After completion, all nodes and the tree root member are stale.
+ */
+#define rbtree_for_each_remove(tree, node, tmp)         \
+for (node = rbtree_postwalk_deepest(tree),              \
+     tmp = rbtree_postwalk_unlink(node);                \
+     node != NULL;                                      \
+     node = tmp, tmp = rbtree_postwalk_unlink(node))    \
+
+#endif /* _KERN_RBTREE_H */
diff --git a/kern/rbtree_i.h b/kern/rbtree_i.h
new file mode 100644
index 00000000..7f9650e7
--- /dev/null
+++ b/kern/rbtree_i.h
@@ -0,0 +1,187 @@
+/*
+ * Copyright (c) 2010, 2011, 2012 Richard Braun.
+ *
+ * This program is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program.  If not, see <http://www.gnu.org/licenses/>.
+ */
+
+#ifndef _KERN_RBTREE_I_H
+#define _KERN_RBTREE_I_H
+
+#include <kern/assert.h>
+#include <kern/macros.h>
+#include <kern/stddef.h>
+
+/*
+ * Red-black node structure.
+ *
+ * To reduce the number of branches and the instruction cache footprint,
+ * the left and right child pointers are stored in an array, and the symmetry
+ * of most tree operations is exploited by using left/right variables when
+ * referring to children.
+ *
+ * In addition, this implementation assumes that all nodes are 4-byte aligned,
+ * so that the least significant bit of the parent member can be used to store
+ * the color of the node. This is true for all modern 32 and 64 bits
+ * architectures, as long as the nodes aren't embedded in structures with
+ * special alignment constraints such as member packing.
+ */
+struct rbtree_node {
+    unsigned long parent;
+    struct rbtree_node *children[2];
+};
+
+/*
+ * Red-black tree structure.
+ */
+struct rbtree {
+    struct rbtree_node *root;
+};
+
+/*
+ * Masks applied on the parent member of a node to obtain either the
+ * color or the parent address.
+ */
+#define RBTREE_COLOR_MASK   0x1UL
+#define RBTREE_PARENT_MASK  (~0x3UL)
+
+/*
+ * Node colors.
+ */
+#define RBTREE_COLOR_RED    0
+#define RBTREE_COLOR_BLACK  1
+
+/*
+ * Masks applied on slots to obtain either the child index or the parent
+ * address.
+ */
+#define RBTREE_SLOT_INDEX_MASK  0x1UL
+#define RBTREE_SLOT_PARENT_MASK (~RBTREE_SLOT_INDEX_MASK)
+
+/*
+ * Return true if the given index is a valid child index.
+ */
+static inline int
+rbtree_check_index(int index)
+{
+    return index == (index & 1);
+}
+
+/*
+ * Convert the result of a comparison into an index in the children array
+ * (0 or 1).
+ *
+ * This function is mostly used when looking up a node.
+ */
+static inline int
+rbtree_d2i(int diff)
+{
+    return !(diff <= 0);
+}
+
+/*
+ * Return true if the given pointer is suitably aligned.
+ */
+static inline int
+rbtree_node_check_alignment(const struct rbtree_node *node)
+{
+    return ((unsigned long)node & (~RBTREE_PARENT_MASK)) == 0;
+}
+
+/*
+ * Return the parent of a node.
+ */
+static inline struct rbtree_node *
+rbtree_node_parent(const struct rbtree_node *node)
+{
+    return (struct rbtree_node *)(node->parent & RBTREE_PARENT_MASK);
+}
+
+/*
+ * Translate an insertion point into a slot.
+ */
+static inline unsigned long
+rbtree_slot(struct rbtree_node *parent, int index)
+{
+    assert(rbtree_node_check_alignment(parent));
+    assert(rbtree_check_index(index));
+    return (unsigned long)parent | index;
+}
+
+/*
+ * Extract the parent address from a slot.
+ */
+static inline struct rbtree_node *
+rbtree_slot_parent(unsigned long slot)
+{
+    return (struct rbtree_node *)(slot & RBTREE_SLOT_PARENT_MASK);
+}
+
+/*
+ * Extract the index from a slot.
+ */
+static inline int
+rbtree_slot_index(unsigned long slot)
+{
+    return slot & RBTREE_SLOT_INDEX_MASK;
+}
+
+/*
+ * Insert a node in a tree, rebalancing it if necessary.
+ *
+ * The index parameter is the index in the children array of the parent where
+ * the new node is to be inserted. It is ignored if the parent is null.
+ *
+ * This function is intended to be used by the rbtree_insert() macro only.
+ */
+void rbtree_insert_rebalance(struct rbtree *tree, struct rbtree_node *parent,
+                             int index, struct rbtree_node *node);
+
+/*
+ * Return the previous or next node relative to a location in a tree.
+ *
+ * The parent and index parameters define the location, which can be empty.
+ * The direction parameter is either RBTREE_LEFT (to obtain the previous
+ * node) or RBTREE_RIGHT (to obtain the next one).
+ */
+struct rbtree_node * rbtree_nearest(struct rbtree_node *parent, int index,
+                                    int direction);
+
+/*
+ * Return the first or last node of a tree.
+ *
+ * The direction parameter is either RBTREE_LEFT (to obtain the first node)
+ * or RBTREE_RIGHT (to obtain the last one).
+ */
+struct rbtree_node * rbtree_firstlast(const struct rbtree *tree, int direction);
+
+/*
+ * Return the node next to, or previous to the given node.
+ *
+ * The direction parameter is either RBTREE_LEFT (to obtain the previous node)
+ * or RBTREE_RIGHT (to obtain the next one).
+ */
+struct rbtree_node * rbtree_walk(struct rbtree_node *node, int direction);
+
+/*
+ * Return the left-most deepest node of a tree, which is the starting point of
+ * the postorder traversal performed by rbtree_for_each_remove().
+ */
+struct rbtree_node * rbtree_postwalk_deepest(const struct rbtree *tree);
+
+/*
+ * Unlink a node from its tree and return the next (right) node in postorder.
+ */
+struct rbtree_node * rbtree_postwalk_unlink(struct rbtree_node *node);
+
+#endif /* _KERN_RBTREE_I_H */
diff --git a/kern/sprintf.c b/kern/sprintf.c
new file mode 100644
index 00000000..13f2671e
--- /dev/null
+++ b/kern/sprintf.c
@@ -0,0 +1,550 @@
+/*
+ * Copyright (c) 2010 Richard Braun.
+ *
+ * This program is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program.  If not, see <http://www.gnu.org/licenses/>.
+ */
+
+#include <stdarg.h>
+
+#include <kern/limits.h>
+#include <kern/sprintf.h>
+#include <kern/stddef.h>
+#include <kern/stdint.h>
+
+/*
+ * Formatting flags.
+ *
+ * FORMAT_LOWER must be 0x20 as it is OR'd with digits, eg.
+ * '0': 0x30 | 0x20 => 0x30 ('0')
+ * 'A': 0x41 | 0x20 => 0x61 ('a')
+ */
+#define SPRINTF_FORMAT_ALT_FORM     0x01
+#define SPRINTF_FORMAT_ZERO_PAD     0x02
+#define SPRINTF_FORMAT_LEFT_JUSTIFY 0x04
+#define SPRINTF_FORMAT_BLANK        0x08
+#define SPRINTF_FORMAT_SIGN         0x10
+#define SPRINTF_FORMAT_LOWER        0x20
+#define SPRINTF_FORMAT_CONV_SIGNED  0x40
+
+enum {
+    SPRINTF_MODIFIER_NONE,
+    SPRINTF_MODIFIER_CHAR,
+    SPRINTF_MODIFIER_SHORT,
+    SPRINTF_MODIFIER_LONG,
+    SPRINTF_MODIFIER_LONGLONG,
+    SPRINTF_MODIFIER_PTR,       /* Used only for %p */
+    SPRINTF_MODIFIER_SIZE,
+    SPRINTF_MODIFIER_PTRDIFF
+};
+
+enum {
+    SPRINTF_SPECIFIER_INVALID,
+    SPRINTF_SPECIFIER_INT,
+    SPRINTF_SPECIFIER_CHAR,
+    SPRINTF_SPECIFIER_STR,
+    SPRINTF_SPECIFIER_NRCHARS,
+    SPRINTF_SPECIFIER_PERCENT
+};
+
+/*
+ * Size for the temporary number buffer. The minimum base is 8 so 3 bits
+ * are consumed per digit. Add one to round up. The conversion algorithm
+ * doesn't use the null byte.
+ */
+#define SPRINTF_MAX_NUM_SIZE (((sizeof(uint64_t) * CHAR_BIT) / 3) + 1)
+
+/*
+ * Special size for vsnprintf(), used by sprintf()/vsprintf() when the
+ * buffer size is unknown.
+ */
+#define SPRINTF_NOLIMIT ((size_t)-1)
+
+static const char sprintf_digits[] = "0123456789ABCDEF";
+
+static inline char *
+sprintf_putchar(char *str, char *end, char c)
+{
+    if (str < end)
+        *str = c;
+
+    str++;
+
+    return str;
+}
+
+static inline int
+sprintf_isdigit(char c)
+{
+    return (c >= '0') && (c <= '9');
+}
+
+int
+sprintf(char *str, const char *format, ...)
+{
+    va_list ap;
+    int length;
+
+    va_start(ap, format);
+    length = vsprintf(str, format, ap);
+    va_end(ap);
+
+    return length;
+}
+
+int
+vsprintf(char *str, const char *format, va_list ap)
+{
+    return vsnprintf(str, SPRINTF_NOLIMIT, format, ap);
+}
+
+int
+snprintf(char *str, size_t size, const char *format, ...)
+{
+    va_list ap;
+    int length;
+
+    va_start(ap, format);
+    length = vsnprintf(str, size, format, ap);
+    va_end(ap);
+
+    return length;
+}
+
+int
+vsnprintf(char *str, size_t size, const char *format, va_list ap)
+{
+    unsigned long long n;
+    int i, len, found, flags, width, precision, modifier, specifier, shift;
+    unsigned char r, base, mask;
+    char c, *s, *start, *end, sign, tmp[SPRINTF_MAX_NUM_SIZE];
+
+    start = str;
+
+    if (size == 0)
+        end = NULL;
+    else if (size == SPRINTF_NOLIMIT)
+        end = (char *)-1;
+    else
+        end = start + size - 1;
+
+    while ((c = *format) != '\0') {
+        if (c != '%') {
+            str = sprintf_putchar(str, end, c);
+            format++;
+            continue;
+        }
+
+        /* Flags */
+
+        found = 1;
+        flags = 0;
+
+        do {
+            format++;
+            c = *format;
+
+            switch (c) {
+            case '#':
+                flags |= SPRINTF_FORMAT_ALT_FORM;
+                break;
+            case '0':
+                flags |= SPRINTF_FORMAT_ZERO_PAD;
+                break;
+            case '-':
+                flags |= SPRINTF_FORMAT_LEFT_JUSTIFY;
+                break;
+            case ' ':
+                flags |= SPRINTF_FORMAT_BLANK;
+                break;
+            case '+':
+                flags |= SPRINTF_FORMAT_SIGN;
+                break;
+            default:
+                found = 0;
+                break;
+            }
+        } while (found);
+
+        /* Width */
+
+        if (sprintf_isdigit(c)) {
+            width = 0;
+
+            while (sprintf_isdigit(c)) {
+                width = width * 10 + (c - '0');
+                format++;
+                c = *format;
+            }
+        } else if (c == '*') {
+            width = va_arg(ap, int);
+
+            if (width < 0) {
+                flags |= SPRINTF_FORMAT_LEFT_JUSTIFY;
+                width = -width;
+            }
+
+            format++;
+            c = *format;
+        } else {
+            width = 0;
+        }
+
+        /* Precision */
+
+        if (c == '.') {
+            format++;
+            c = *format;
+
+            if (sprintf_isdigit(c)) {
+                precision = 0;
+
+                while (sprintf_isdigit(c)) {
+                    precision = precision * 10 + (c - '0');
+                    format++;
+                    c = *format;
+                }
+            } else if (c == '*') {
+                precision = va_arg(ap, int);
+
+                if (precision < 0)
+                    precision = 0;
+
+                format++;
+                c = *format;
+            } else {
+                precision = 0;
+            }
+        } else {
+            /* precision is >= 0 only if explicit */
+            precision = -1;
+        }
+
+        /* Length modifier */
+
+        switch (c) {
+        case 'h':
+        case 'l':
+            format++;
+
+            if (c == *format) {
+                modifier = (c == 'h')
+                           ? SPRINTF_MODIFIER_CHAR
+                           : SPRINTF_MODIFIER_LONGLONG;
+                goto skip_modifier;
+            } else {
+                modifier = (c == 'h')
+                           ? SPRINTF_MODIFIER_SHORT
+                           : SPRINTF_MODIFIER_LONG;
+                c = *format;
+            }
+
+            break;
+        case 'z':
+            modifier = SPRINTF_MODIFIER_SIZE;
+            goto skip_modifier;
+        case 't':
+            modifier = SPRINTF_MODIFIER_PTRDIFF;
+skip_modifier:
+            format++;
+            c = *format;
+            break;
+        default:
+            modifier = SPRINTF_MODIFIER_NONE;
+            break;
+        }
+
+        /* Specifier */
+
+        switch (c) {
+        case 'd':
+        case 'i':
+            flags |= SPRINTF_FORMAT_CONV_SIGNED;
+        case 'u':
+            base = 10;
+            goto integer;
+        case 'o':
+            base = 8;
+            goto integer;
+        case 'p':
+            flags |= SPRINTF_FORMAT_ALT_FORM;
+            modifier = SPRINTF_MODIFIER_PTR;
+        case 'x':
+            flags |= SPRINTF_FORMAT_LOWER;
+        case 'X':
+            base = 16;
+integer:
+            specifier = SPRINTF_SPECIFIER_INT;
+            break;
+        case 'c':
+            specifier = SPRINTF_SPECIFIER_CHAR;
+            break;
+        case 's':
+            specifier = SPRINTF_SPECIFIER_STR;
+            break;
+        case 'n':
+            specifier = SPRINTF_SPECIFIER_NRCHARS;
+            break;
+        case '%':
+            specifier = SPRINTF_SPECIFIER_PERCENT;
+            break;
+        default:
+            specifier = SPRINTF_SPECIFIER_INVALID;
+            break;
+        }
+
+        /* Output */
+
+        switch (specifier) {
+        case SPRINTF_SPECIFIER_INT:
+            switch (modifier) {
+            case SPRINTF_MODIFIER_CHAR:
+                if (flags & SPRINTF_FORMAT_CONV_SIGNED)
+                    n = (signed char)va_arg(ap, int);
+                else
+                    n = (unsigned char)va_arg(ap, int);
+                break;
+            case SPRINTF_MODIFIER_SHORT:
+                if (flags & SPRINTF_FORMAT_CONV_SIGNED)
+                    n = (short)va_arg(ap, int);
+                else
+                    n = (unsigned short)va_arg(ap, int);
+                break;
+            case SPRINTF_MODIFIER_LONG:
+                if (flags & SPRINTF_FORMAT_CONV_SIGNED)
+                    n = va_arg(ap, long);
+                else
+                    n = va_arg(ap, unsigned long);
+                break;
+            case SPRINTF_MODIFIER_LONGLONG:
+                if (flags & SPRINTF_FORMAT_CONV_SIGNED)
+                    n = va_arg(ap, long long);
+                else
+                    n = va_arg(ap, unsigned long long);
+                break;
+            case SPRINTF_MODIFIER_PTR:
+                n = (unsigned long)va_arg(ap, void *);
+                break;
+            case SPRINTF_MODIFIER_SIZE:
+                if (flags & SPRINTF_FORMAT_CONV_SIGNED)
+                    n = va_arg(ap, ssize_t);
+                else
+                    n = va_arg(ap, size_t);
+                break;
+            case SPRINTF_MODIFIER_PTRDIFF:
+                n = va_arg(ap, ptrdiff_t);
+                break;
+            default:
+                if (flags & SPRINTF_FORMAT_CONV_SIGNED)
+                    n = va_arg(ap, int);
+                else
+                    n = va_arg(ap, unsigned int);
+                break;
+            }
+
+            if ((flags & SPRINTF_FORMAT_LEFT_JUSTIFY) || (precision >= 0))
+                flags &= ~SPRINTF_FORMAT_ZERO_PAD;
+
+            sign = 0;
+
+            if (flags & SPRINTF_FORMAT_ALT_FORM) {
+                /* '0' for octal */
+                width--;
+
+                /* '0x' or '0X' for hexadecimal */
+                if (base == 16)
+                    width--;
+            } else if (flags & SPRINTF_FORMAT_CONV_SIGNED) {
+                if ((long long)n < 0) {
+                    sign = '-';
+                    width--;
+                    n = -(long long)n;
+                } else if (flags & SPRINTF_FORMAT_SIGN) {
+                    /* SPRINTF_FORMAT_SIGN must precede SPRINTF_FORMAT_BLANK. */
+                    sign = '+';
+                    width--;
+                } else if (flags & SPRINTF_FORMAT_BLANK) {
+                    sign = ' ';
+                    width--;
+                }
+            }
+
+            /* Conversion, in reverse order */
+
+            i = 0;
+
+            if (n == 0) {
+                if (precision != 0)
+                    tmp[i++] = '0';
+            } else if (base == 10) {
+                /*
+                 * Try to avoid 64 bits operations if the processor doesn't
+                 * support them. Note that even when using modulus and
+                 * division operators close to each other, the compiler will
+                 * forge two calls to __udivdi3() and __umoddi3() instead of
+                 * one to __udivmoddi3(), whereas processor instructions are
+                 * generally correctly used once, giving both the remainder
+                 * and the quotient, through plain or reciprocal division.
+                 */
+#ifndef __LP64__
+                if (modifier == SPRINTF_MODIFIER_LONGLONG) {
+#endif /* __LP64__ */
+                    do {
+                        r = n % 10;
+                        n /= 10;
+                        tmp[i++] = sprintf_digits[r];
+                    } while (n != 0);
+#ifndef __LP64__
+                } else {
+                    unsigned long m;
+
+                    m = (unsigned long)n;
+
+                    do {
+                        r = m % 10;
+                        m /= 10;
+                        tmp[i++] = sprintf_digits[r];
+                    } while (m != 0);
+                }
+#endif /* __LP64__ */
+            } else {
+                mask = base - 1;
+                shift = (base == 8) ? 3 : 4;
+
+                do {
+                    r = (unsigned char)n & mask;
+                    n >>= shift;
+                    tmp[i++] = sprintf_digits[r]
+                               | (flags & SPRINTF_FORMAT_LOWER);
+                } while (n != 0);
+            }
+
+            if (i > precision)
+                precision = i;
+
+            width -= precision;
+
+            if (!(flags & (SPRINTF_FORMAT_LEFT_JUSTIFY
+                           | SPRINTF_FORMAT_ZERO_PAD)))
+                while (width-- > 0)
+                    str = sprintf_putchar(str, end, ' ');
+
+            if (flags & SPRINTF_FORMAT_ALT_FORM) {
+                str = sprintf_putchar(str, end, '0');
+
+                if (base == 16)
+                    str = sprintf_putchar(str, end,
+                                          'X' | (flags & SPRINTF_FORMAT_LOWER));
+            } else if (sign) {
+                str = sprintf_putchar(str, end, sign);
+            }
+
+            if (!(flags & SPRINTF_FORMAT_LEFT_JUSTIFY)) {
+                c = (flags & SPRINTF_FORMAT_ZERO_PAD) ? '0' : ' ';
+
+                while (width-- > 0)
+                    str = sprintf_putchar(str, end, c);
+            }
+
+            while (i < precision--)
+                str = sprintf_putchar(str, end, '0');
+
+            while (i-- > 0)
+                str = sprintf_putchar(str, end, tmp[i]);
+
+            while (width-- > 0)
+                str = sprintf_putchar(str, end, ' ');
+
+            break;
+        case SPRINTF_SPECIFIER_CHAR:
+            c = (unsigned char)va_arg(ap, int);
+
+            if (!(flags & SPRINTF_FORMAT_LEFT_JUSTIFY))
+                while (--width > 0)
+                    str = sprintf_putchar(str, end, ' ');
+
+            str = sprintf_putchar(str, end, c);
+
+            while (--width > 0)
+                str = sprintf_putchar(str, end, ' ');
+
+            break;
+        case SPRINTF_SPECIFIER_STR:
+            s = va_arg(ap, char *);
+
+            if (s == NULL)
+                s = "(null)";
+
+            len = 0;
+
+            for (len = 0; s[len] != '\0'; len++)
+                if (len == precision)
+                    break;
+
+            if (!(flags & SPRINTF_FORMAT_LEFT_JUSTIFY))
+                while (len < width--)
+                    str = sprintf_putchar(str, end, ' ');
+
+            for (i = 0; i < len; i++) {
+                str = sprintf_putchar(str, end, *s);
+                s++;
+            }
+
+            while (len < width--)
+                str = sprintf_putchar(str, end, ' ');
+
+            break;
+        case SPRINTF_SPECIFIER_NRCHARS:
+            if (modifier == SPRINTF_MODIFIER_CHAR) {
+                signed char *ptr = va_arg(ap, signed char *);
+                *ptr = str - start;
+            } else if (modifier == SPRINTF_MODIFIER_SHORT) {
+                short *ptr = va_arg(ap, short *);
+                *ptr = str - start;
+            } else if (modifier == SPRINTF_MODIFIER_LONG) {
+                long *ptr = va_arg(ap, long *);
+                *ptr = str - start;
+            } else if (modifier == SPRINTF_MODIFIER_LONGLONG) {
+                long long *ptr = va_arg(ap, long long *);
+                *ptr = str - start;
+            } else if (modifier == SPRINTF_MODIFIER_SIZE) {
+                ssize_t *ptr = va_arg(ap, ssize_t *);
+                *ptr = str - start;
+            } else if (modifier == SPRINTF_MODIFIER_PTRDIFF) {
+                ptrdiff_t *ptr = va_arg(ap, ptrdiff_t *);
+                *ptr = str - start;
+            } else {
+                int *ptr = va_arg(ap, int *);
+                *ptr = str - start;
+            }
+
+            break;
+        case SPRINTF_SPECIFIER_PERCENT:
+        case SPRINTF_SPECIFIER_INVALID:
+            str = sprintf_putchar(str, end, '%');
+            break;
+        default:
+            break;
+        }
+
+        if (specifier != SPRINTF_SPECIFIER_INVALID)
+            format++;
+    }
+
+    if (str < end)
+        *str = '\0';
+    else if (end != NULL)
+        *end = '\0';
+
+    return str - start;
+}
diff --git a/kern/sprintf.h b/kern/sprintf.h
new file mode 100644
index 00000000..0c097953
--- /dev/null
+++ b/kern/sprintf.h
@@ -0,0 +1,43 @@
+/*
+ * Copyright (c) 2010 Richard Braun.
+ *
+ * This program is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program.  If not, see <http://www.gnu.org/licenses/>.
+ *
+ *
+ * Formatted string functions.
+ *
+ * The functions provided by this module implement a subset of the C99
+ * sprintf() like functions, mostly centered around character, string, and
+ * integer conversions.
+ *
+ * The supported specifiers are: d i o u x X c s p n %
+ * The supported length modifiers are: hh h l ll z t
+ */
+
+#ifndef _KERN_SPRINTF_H
+#define _KERN_SPRINTF_H
+
+#include <stdarg.h>
+
+#include <kern/macros.h>
+
+int sprintf(char *str, const char *format, ...) __format_printf(2, 3);
+int vsprintf(char *str, const char *format, va_list ap) __format_printf(2, 0);
+
+int snprintf(char *str, size_t size, const char *format, ...)
+    __format_printf(3, 4);
+int vsnprintf(char *str, size_t size, const char *format, va_list ap)
+    __format_printf(3, 0);
+
+#endif /* _KERN_SPRINTF_H */
diff --git a/kern/stddef.h b/kern/stddef.h
new file mode 100644
index 00000000..b07c9924
--- /dev/null
+++ b/kern/stddef.h
@@ -0,0 +1,35 @@
+/*
+ * Copyright (c) 2010, 2011 Richard Braun.
+ *
+ * This program is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program.  If not, see <http://www.gnu.org/licenses/>.
+ */
+
+#ifndef _KERN_STDDEF_H
+#define _KERN_STDDEF_H
+
+#define NULL ((void *)0)
+
+#define offsetof(type, member) __builtin_offsetof(type, member)
+
+#ifdef __LP64__
+typedef unsigned long size_t;
+typedef long ssize_t;
+typedef long ptrdiff_t;
+#else /* __LP64__ */
+typedef unsigned int size_t;
+typedef int ssize_t;
+typedef int ptrdiff_t;
+#endif /* __LP64__ */
+
+#endif /* _KERN_STDDEF_H */
diff --git a/kern/stdint.h b/kern/stdint.h
new file mode 100644
index 00000000..d6794c4e
--- /dev/null
+++ b/kern/stdint.h
@@ -0,0 +1,30 @@
+/*
+ * Copyright (c) 2010, 2011 Richard Braun.
+ *
+ * This program is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program.  If not, see <http://www.gnu.org/licenses/>.
+ */
+
+#ifndef _KERN_STDINT_H
+#define _KERN_STDINT_H
+
+typedef signed char int8_t;
+typedef unsigned char uint8_t;
+typedef signed short int16_t;
+typedef unsigned short uint16_t;
+typedef signed int int32_t;
+typedef unsigned int uint32_t;
+typedef signed long long int64_t;
+typedef unsigned long long uint64_t;
+
+#endif /* _KERN_STDINT_H */
diff --git a/kern/string.c b/kern/string.c
new file mode 100644
index 00000000..82bcd2f1
--- /dev/null
+++ b/kern/string.c
@@ -0,0 +1,138 @@
+/*
+ * Copyright (c) 2012 Richard Braun.
+ *
+ * This program is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program.  If not, see <http://www.gnu.org/licenses/>.
+ *
+ *
+ * Trivial, portable implementations.
+ */
+
+#include <kern/stddef.h>
+#include <kern/string.h>
+
+void *
+memcpy(void *dest, const void *src, size_t n)
+{
+    const char *src_ptr;
+    char *dest_ptr;
+    size_t i;
+
+    dest_ptr = dest;
+    src_ptr = src;
+
+    for (i = 0; i < n; i++)
+        *dest_ptr++ = *src_ptr++;
+
+    return dest;
+}
+
+void *
+memmove(void *dest, const void *src, size_t n)
+{
+    const char *src_ptr;
+    char *dest_ptr;
+    size_t i;
+
+    if (src == dest)
+        return dest;
+    else if (src < dest) {
+        dest_ptr = (char *)dest + n - 1;
+        src_ptr = (const char *)src + n - 1;
+
+        for (i = 0; i < n; i++)
+            *dest_ptr-- = *src_ptr--;
+    } else if (src > dest) {
+        dest_ptr = dest;
+        src_ptr = src;
+
+        for  (i = 0; i < n; i++)
+            *dest_ptr++ = *src_ptr++;
+    }
+
+    return dest;
+}
+
+void *
+memset(void *s, int c, size_t n)
+{
+    char *buffer;
+    size_t i;
+
+    buffer = s;
+
+    for (i = 0; i < n; i++)
+        buffer[i] = c;
+
+    return s;
+}
+
+int
+memcmp(const void *s1, const void *s2, size_t n)
+{
+    const char *a1, *a2;
+    size_t i;
+
+    a1 = s1;
+    a2 = s2;
+
+    for (i = 0; i < n; i++)
+        if (a1[i] != a2[i])
+            return a2[i] - a1[i];
+
+    return 0;
+}
+
+size_t
+strlen(const char *s)
+{
+    size_t i;
+
+    i = 0;
+
+    while (*s++ != '\0')
+        i++;
+
+    return i;
+}
+
+char *
+strcpy(char *dest, const char *src)
+{
+    char *tmp;
+
+    tmp = dest;
+
+    while ((*dest = *src) != '\0') {
+        dest++;
+        src++;
+    }
+
+    return tmp;
+}
+
+int
+strcmp(const char *s1, const char *s2)
+{
+    char c1, c2;
+
+    while ((c1 = *s1) == (c2 = *s2)) {
+        if (c1 == '\0')
+            return 0;
+
+        s1++;
+        s2++;
+    }
+
+    return (c1 < c2) ? -1 : 1;
+}
diff --git a/kern/string.h b/kern/string.h
new file mode 100644
index 00000000..8dd4d9d0
--- /dev/null
+++ b/kern/string.h
@@ -0,0 +1,31 @@
+/*
+ * Copyright (c) 2012 Richard Braun.
+ *
+ * This program is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program.  If not, see <http://www.gnu.org/licenses/>.
+ */
+
+#ifndef _KERN_STRING_H
+#define _KERN_STRING_H
+
+#include <kern/stddef.h>
+
+void * memcpy(void *dest, const void *src, size_t n);
+void * memmove(void *dest, const void *src, size_t n);
+void * memset(void *s, int c, size_t n);
+int memcmp(const void *s1, const void *s2, size_t n);
+size_t strlen(const char *s);
+char * strcpy(char *dest, const char *src);
+int strcmp(const char *s1, const char *s2);
+
+#endif /* _KERN_STRING_H */