15 files changed, 983 insertions, 0 deletions

diff --git a/klib/buddymap.c b/klib/buddymap.c
new file mode 100644
index 0000000..62cecf1
--- /dev/null
+++ b/klib/buddymap.c
@@ -0,0 +1,170 @@
+#include "buddymap.h"
+#include "jove.h"
+#include "print.h"
+
+#define BLOCK_AT_LAYER(blocks, l, i) blocks[l][i / BUDDY_BLOCK_BITS]
+#define BLOCK_BITMASK(i) (1ULL << (i % BUDDY_BLOCK_BITS))
+#define LOG2(v) (31 - __builtin_clz(v))
+
+bool
+buddy_bit_test(struct BuddyMap *map, size_t l, size_t i)
+{
+    return (BLOCK_AT_LAYER(map->blocks, l, i) & BLOCK_BITMASK(i)) > 0;
+}
+
+void
+buddy_bit_mark(struct BuddyMap *map, size_t l, size_t i)
+{
+    size_t wi = i << l;
+    size_t bits = 1ULL << l;
+    for(size_t wl = 0; wl < map->orders; wl++) {
+        if(bits == 0) {
+            if(buddy_bit_test(map, wl - 1, (wi << 1) + 1)) bits = 1;
+        }
+        for(size_t bit = 0; bit < bits; bit++) {
+            size_t rbit = bit + wi;
+            if(l == 0 && !buddy_bit_test(map, 0, rbit)) map->free--;
+            BLOCK_AT_LAYER(map->blocks, wl, rbit) |= BLOCK_BITMASK(rbit);
+        }
+        bits >>= 1;
+        wi >>= 1;
+    }
+}
+
+void
+buddy_bit_free(struct BuddyMap *map, size_t l, size_t i)
+{
+    size_t wi = i << l;
+    size_t bits = 1ULL << l;
+    for(size_t wl = 0; wl < map->orders; wl++) {
+        if(bits == 0) bits = 1;
+        for(size_t bit = 0; bit < bits; bit++) {
+            size_t rbit = bit + wi;
+            if(l == 0 && buddy_bit_test(map, 0, rbit)) map->free++;
+            BLOCK_AT_LAYER(map->blocks, wl, rbit) &= ~BLOCK_BITMASK(rbit);
+        }
+        bits >>= 1;
+        wi >>= 1;
+    }
+}
+
+static void
+s_buddy_op_range(
+        struct BuddyMap *map,
+        size_t l,
+        size_t start,
+        size_t end,
+        void (*op)(struct BuddyMap*, size_t, size_t))
+{
+    size_t layerw = 1ULL << l;
+    size_t start_off = start % layerw;
+    size_t end_off = end % layerw;
+
+    size_t start_real = start + (start_off > 0 ? (layerw - start_off) : 0);
+    size_t end_real = end - end_off;
+
+    if(start_real != start) s_buddy_op_range(map, l - 1, start, start_real, op);
+    if(end_real != end) s_buddy_op_range(map, l - 1, end_real, end, op);
+
+    size_t start_bit = start_real >> l;
+    size_t end_bit = end_real >> l;
+    if(start_bit == end_bit || end_bit < start_bit) return;
+    for(size_t bit = start_bit; bit < end_bit; bit++)
+        op(map, l, bit);
+}
+
+static size_t
+s_buddy_layer_bestfit(struct BuddyMap *map, size_t length)
+{
+    if(length == 1) return 0;
+    size_t length_log2 = LOG2(length);
+    if(length_log2 > map->orders) length_log2 = map->orders - 1;
+    return length_log2;
+}
+
+void
+buddy_mark_range(struct BuddyMap *map, size_t start, size_t end)
+{
+    size_t l = s_buddy_layer_bestfit(map, end - start);
+    s_buddy_op_range(map, l, start, end, buddy_bit_mark);
+}
+void 
+buddy_free_range(struct BuddyMap *map, size_t start, size_t end)
+{ 
+    size_t l = s_buddy_layer_bestfit(map, end - start);
+    s_buddy_op_range(map, l, start, end, buddy_bit_free);
+}
+
+static intmax_t
+s_buddy_top_firstfree(struct BuddyMap *map)
+{
+    size_t layer = map->orders - 1;
+    size_t layer_bits = map->bits >> layer;
+    size_t layer_blocks = layer_bits / BUDDY_BLOCK_BITS;
+    for(size_t i = 0; i < layer_blocks; i++) {
+        if(map->blocks[layer][i] == (uintptr_t)-1) continue;
+        for(size_t j = 0; j < BUDDY_BLOCK_BITS; j++) {
+            size_t bit = (i * BUDDY_BLOCK_BITS) + j;
+            if(buddy_bit_test(map, layer, bit)) continue;
+            return bit;
+        }
+    }
+    return -1;
+}
+
+static intmax_t
+s_buddy_top_alloc_contig(struct BuddyMap *map, size_t length)
+{
+    size_t layer = map->orders - 1;
+    size_t layer_bits = map->bits >> layer;
+
+    size_t contig_base = 0;
+    size_t contig_bits = 0;
+    for(size_t i = 0; i < layer_bits; i++) {
+        if(buddy_bit_test(map, layer, i)) {
+            contig_base = i + 1;
+            contig_bits = 0;
+            continue;
+        }
+        if(++contig_bits == length) {
+            return contig_base;
+        }
+    }
+    return -1;
+}
+
+intmax_t
+buddy_alloc(struct BuddyMap *map, size_t length)
+{
+    size_t layer = s_buddy_layer_bestfit(map, length);
+    size_t layerw = 1ULL << layer;
+    size_t allocw = length / layerw;
+
+    if(allocw == 0) allocw = 1;
+    if(allocw > 1)
+        return s_buddy_top_alloc_contig(map, length);
+
+    intmax_t alloci = s_buddy_top_firstfree(map);
+    if(alloci < 0) {
+        klogf("Top layer is full!\n");
+        return -1;
+    }
+
+    for(int wlayer = map->orders - 2; wlayer > layer; wlayer--) {
+        alloci <<= 1;
+        if(buddy_bit_test(map, wlayer, alloci)) {
+            alloci++;
+        }
+    }
+    alloci <<= 1;
+    if(buddy_bit_test(map, layer, alloci)) alloci++;
+
+    s_buddy_op_range(map, layer, alloci, alloci + length, buddy_bit_mark);
+    return alloci;
+}
+
+void
+buddy_free(struct BuddyMap *map, size_t i, size_t length)
+{
+    buddy_free_range(map, i, i + length);
+}
diff --git a/klib/buddymap.h b/klib/buddymap.h
new file mode 100644
index 0000000..1af8dfb
--- /dev/null
+++ b/klib/buddymap.h
@@ -0,0 +1,35 @@
+#ifndef JOVE_LIB_BUDDYMAP_H
+#define JOVE_LIB_BUDDYMAP_H 1
+
+#include <stddef.h>
+#include <stdint.h>
+#include <stdbool.h>
+
+#define BUDDY_BLOCK_BYTES sizeof(intmax_t)
+#define BUDDY_BLOCK_BITS (BUDDY_BLOCK_BYTES * 8)
+
+#define BUDDY_BITS_FOR(range) (range * 2)
+#define BUDDY_BLOCKS_FOR(range) (BUDDY_BITS_FOR(range) / BUDDY_BLOCK_BITS)
+
+struct BuddyMap
+{
+    size_t orders;
+    size_t bits;
+    size_t free;
+    uintmax_t **blocks;
+};
+
+#define BUDDY_BIT_PARTIAL 0
+#define BUDDY_BIT_FULL 1
+
+bool buddy_bit_test(struct BuddyMap *map, size_t l, size_t i);
+void buddy_bit_mark(struct BuddyMap *map, size_t l, size_t i);
+void buddy_bit_free(struct BuddyMap *map, size_t l, size_t i);
+
+void buddy_mark_range(struct BuddyMap *map, size_t start, size_t end);
+void buddy_free_range(struct BuddyMap *map, size_t start, size_t end);
+
+intmax_t buddy_alloc(struct BuddyMap *map, size_t length);
+void buddy_free(struct BuddyMap *map, size_t i, size_t length);
+
+#endif
diff --git a/klib/format.h b/klib/format.h
new file mode 100644
index 0000000..5a2b75c
--- /dev/null
+++ b/klib/format.h
@@ -0,0 +1,13 @@
+#ifndef JOVE_LIB_FORMAT_H
+#define JOVE_LIB_FORMAT_H 1
+
+#include <stddef.h>
+#include <stdbool.h>
+
+size_t ltostr(char *s, size_t limit, unsigned long l, bool sgn, int radix);
+
+char *sfmt(char *s, size_t limit, const char *fmt, ...);
+#include <stdarg.h>
+char *svfmt(char *s, size_t limit, const char *fmt, va_list ap);
+
+#endif
diff --git a/klib/hash.h b/klib/hash.h
new file mode 100644
index 0000000..03b0f3a
--- /dev/null
+++ b/klib/hash.h
@@ -0,0 +1,18 @@
+#ifndef JOVE_LIB_HASH_H
+#define JOVE_LIB_HASH_H 1
+
+#include <stdint.h>
+
+static intmax_t
+string_hash(const char *str)
+{
+    /* Hash function courtesy of the following website:
+     * http://www.cse.yorku.ca/~oz/hash.html*/
+    intmax_t r = 5381;
+    while (*str) {
+        r = (r * 33) ^ *(str++);
+    }
+    return r;
+}
+
+#endif
diff --git a/klib/kpanic.c b/klib/kpanic.c
new file mode 100644
index 0000000..2918711
--- /dev/null
+++ b/klib/kpanic.c
@@ -0,0 +1,16 @@
+#include "jove.h"
+#include "print.h"
+
+#include <stdarg.h>
+#include <stddef.h>
+
+__attribute__((noreturn))
+void _kpanic(const char *file, int line, const char *fmt, ...)
+{
+    va_list ap;
+    va_start(ap, fmt);
+    klogf("!!! PANIC !!!\n%s:%i\n", file, line);
+    _plogvf(NULL, NULL, 0, PRINT_LOG, fmt, ap);
+    va_end(ap);
+    for(;;) __asm__ volatile("hlt");
+}
diff --git a/klib/linkedlist.c b/klib/linkedlist.c
new file mode 100644
index 0000000..6cc6403
--- /dev/null
+++ b/klib/linkedlist.c
@@ -0,0 +1,34 @@
+#include "linkedlist.h"
+
+void
+sll_new(struct SLinkedList *list, size_t obj_size)
+{
+    list->obj_size = obj_size;
+    list->count = 0;
+    list->head = list->tail = NULL;
+};
+
+void
+sll_push(struct SLinkedList *list, void *data)
+{
+    struct SLLNode *node = (struct SLLNode*)data;
+    if(list->tail != NULL) {
+        list->tail->next = node;
+    }
+    if(list->head == NULL)
+        list->head = node;
+    list->tail = node;
+    list->count++;
+}
+
+void*
+sll_get(struct SLinkedList *list, size_t index)
+{
+    struct SLLNode *node = list->head;
+    if(node == NULL) return NULL;
+    if(index > list->count) return list->tail;
+    for(size_t i = 0; i < index; i++) {
+        node = node->next;
+    }
+    return node;
+}
diff --git a/klib/linkedlist.h b/klib/linkedlist.h
new file mode 100644
index 0000000..26c148e
--- /dev/null
+++ b/klib/linkedlist.h
@@ -0,0 +1,26 @@
+#ifndef JOVE_LIB_LINKEDLIST_H
+#define JOVE_LIB_LINKEDLIST_H 1
+
+#include <stdint.h>
+#include <stddef.h>
+
+struct SLLNode {
+    struct SLLNode *next;
+    char data[];
+};
+
+/*Singly Linked List*/
+struct SLinkedList
+{
+    struct SLLNode *head;
+    struct SLLNode *tail;
+    
+    size_t obj_size;
+    size_t count;
+};
+
+void sll_new(struct SLinkedList *list, size_t obj_size);
+void sll_push(struct SLinkedList *list, void *node);
+void *sll_get(struct SLinkedList *list, size_t index);
+
+#endif
diff --git a/klib/ltostr.c b/klib/ltostr.c
new file mode 100644
index 0000000..e28be31
--- /dev/null
+++ b/klib/ltostr.c
@@ -0,0 +1,26 @@
+#include "format.h"
+
+size_t
+ltostr(char *s, size_t limit, unsigned long l, bool sgn, int radix)
+{
+    size_t si = 0;
+    size_t digits = 0;
+    if((long)l < 0 && sgn) {
+        l = -((long)l);
+        s[0] = '-';
+    }
+    for(unsigned long lv = l; lv != 0; lv /= radix)
+        digits++;
+    digits = digits > limit ? limit : digits;
+
+    if(digits-- == 0)
+        s[si++] = '0'; 
+    for(unsigned long lv = l; lv != 0; lv /= radix)
+    {
+        if(si >= limit) return si;
+        int digit = lv % radix;
+        s[(digits - si)] = (digit >= 10 ? (digit + 'a' - 10) : digit + '0');
+        si++;
+    }
+    return si;
+}
diff --git a/klib/mem.c b/klib/mem.c
new file mode 100644
index 0000000..cf9e2aa
--- /dev/null
+++ b/klib/mem.c
@@ -0,0 +1,52 @@
+#include "string.h"
+#include "memory.h"
+
+void*
+memset(void *dest, int c, size_t n)
+{
+    char *destc = (char*)dest;
+    for(size_t i = 0; i < n; i++)
+        destc[i] = c;
+    return dest;
+}
+
+void*
+memcpy(void *dest, const void *src, size_t n)
+{
+    char *destc = (char*)dest;
+    const char *srcc = (const char*)src;
+    for(size_t i = 0; i < n; i++)
+        destc[i] = srcc[i];
+    return dest;
+}
+
+void*
+memmove(void *dest, const void *src, size_t n)
+{
+    char *destc = (char*)dest;
+    const char *srcc = (const char*)src;
+    if(destc + n < srcc) return memcpy(dest, src, n);
+    char buffer[n];
+    memcpy(buffer, src, n);
+    return memcpy(destc, buffer, n);
+}
+
+int
+memcmp(const void *a, const void *b, size_t n)
+{
+    const char *ac = (const char*)a;
+    const char *bc = (const char*)b;
+    for(size_t i = 0; i < n; i++) {
+        if(ac[i] != bc[i]) return ac[i] - bc[i];
+    }
+    return 0;
+}
+
+char*
+strdup(const char *s)
+{
+    size_t slen = strlen(s);
+    char *ret = kmalloc(slen);
+    memcpy(ret, s, slen);
+    return ret;
+}
diff --git a/klib/rbtree.c b/klib/rbtree.c
new file mode 100644
index 0000000..2920384
--- /dev/null
+++ b/klib/rbtree.c
@@ -0,0 +1,361 @@
+#include "rbtree.h"
+#include "assert.h"
+#include "string.h"
+
+#define BLACK 0
+#define RED 1
+
+#define LEFT 0
+#define left children[LEFT]
+
+#define RIGHT 1
+#define right children[RIGHT]
+
+#define CHILD_DIR(c) (c->parent->children[LEFT] == c ? LEFT : RIGHT)
+
+/**Given a root and a direction, rotate the subtree such that the order of the
+ * elements are unchanged.
+ * The opposite direction child of the given root is treated as the pivot point
+ * The dir-most child of the pivot becomes the opposite dir child of the root.
+ * The pivot becomes the root and vice-versa.
+ * @param tree to do rotation on.
+ * @param root of rotation.
+ * @param dir to rotate by.
+ * @return new root node.*/
+rbnode_t*
+s_node_rotate(rbtree_t *tree, rbnode_t *root, bool dir)
+{
+    assert(root != NULL);
+    rbnode_t *gparent = root->parent;
+    rbnode_t *sibling = root->children[1-dir];
+    rbnode_t *child = NULL;
+
+    assert(sibling != NULL);
+    child = sibling->children[dir];
+
+    /* Opposite child of root is dir-most child of sibling.*/
+    root->children[1-dir] = child;
+    if(child != NULL) child->parent = root;
+
+    /* Child of sibling is the root.*/
+    sibling->children[  dir] = root;
+    root->parent = sibling;
+
+    /* Parent of sibling is the grandparent. */
+    sibling->parent = gparent;
+    if(gparent != NULL)
+        gparent->children[CHILD_DIR(root)] = sibling;
+    else
+        tree->root = sibling;
+
+    return sibling;
+}
+
+/**Search the rbtree for a node that matches the key.
+ * If no such node is found, returns NULL.
+ * @param tree to search through.
+ * @param key to search for.
+ * @return found node.*/
+rbnode_t*
+s_find(rbtree_t *tree, intmax_t key)
+{
+    rbnode_t *node = tree->root;
+    while(node != NULL && node->key != key) {
+        node = node->children[node->key > key];
+    }
+    return node;
+}
+
+rbnode_t*
+s_closest(rbtree_t *tree, intmax_t key)
+{
+    rbnode_t *node = tree->root;
+    while(node != NULL && node->key != key) {
+        rbnode_t *child = node->children[node->key > key];
+        if(child == NULL) return node;
+        node = child;
+    }
+    return node;
+}
+
+/**Find the left-most node for this subtree.
+ * @param node root of the subtree to search through.
+ * @return left-most node.*/
+rbnode_t*
+s_node_min(rbnode_t *node)
+{
+    while(node->left != NULL) node = node->left;
+    return node;
+}
+
+/**Find the successor for the specified node.
+ * The successor is defined as the left-most node of the right sub-tree.
+ * (the smallest node larger than the root)
+ * @param node to search for.
+ * @return the successor.*/
+rbnode_t*
+s_node_successor(rbnode_t *node)
+{
+    if(node->right != NULL)
+        return s_node_min(node->right);
+    /* If the node has no left child (meaning that the node is larger than it's
+     * parents), we cycle up through the RHS of the parent tree (such that each
+     * parent is smaller than the child) until we reach a point by which the 
+     * child node is smaller than the parent.*/
+    rbnode_t *parent = node->parent;
+    while(parent != NULL && node == parent->right) {
+        node = parent;
+        parent = node->parent;
+    }
+    return parent;
+}
+
+/**Copy the data from one node onto another, keeping parent and child relations.
+ * @prarm tree for metadata purposes.
+ * @param dest destination node.
+ * @param src source node.*/
+void
+s_node_copy_value(rbtree_t *tree, rbnode_t *dest, rbnode_t *src)
+{
+    dest->key = src->key;
+    memcpy(dest->data, src->data, tree->objw);
+}
+
+/**Perform tree adjustments after insertion to rebalance the rbtree.
+ * @param tree to rebalance.
+ * @param node that was inserted.
+ * @param parent of the node.
+ * @param dir that the node was inserted in.*/
+void
+s_node_insert_fix(
+        rbtree_t *tree,
+        rbnode_t *node,
+        rbnode_t *parent,
+        bool dir)
+{
+    rbnode_t *gparent;
+    rbnode_t *uncle;
+    while((parent = node->parent) != NULL) {
+        if(parent->color == BLACK) return; /* Tree is valid. no fixes needed.*/
+        /*Parent is known to be red.*/
+        if((gparent = parent->parent) == NULL) {
+            /*Parent is red and the root. We can just fix it and return.*/
+            parent->color = BLACK;
+            return;
+        }
+        /* Parent is red and has a parent.
+         * We now need to fix the parent.*/
+        dir = CHILD_DIR(parent);
+        uncle = gparent->children[1-dir];
+        if(uncle == NULL || uncle->color == BLACK) {
+            /* Parent is red, but uncle (opposite child of gparent) is black.
+             * We need to rotate the gparent node such that the parent takes
+             * its place. However, if the current node is an inner child of 
+             * gparent, we need to rotate N into P.*/
+            if(node == parent->children[1-dir]) {
+                /* Node is an inner child. We need to rotate N and P first.*/
+                s_node_rotate(tree, parent, dir);
+                node = parent;
+                parent = gparent->children[dir];
+            }
+            /* N is not an inner child, we can rotate the tree properly.*/
+            s_node_rotate(tree, gparent, 1-dir);
+            parent->color = BLACK;
+            gparent->color = RED;
+            return;
+        }
+    }
+}
+
+/**Insert a node into the rbtree on the parent and direction given.
+ * @param tree to insert into.
+ * @param node to insert.
+ * @param parent node to insert onto.
+ * @param dir direction to insert node.*/
+void
+s_node_insert(rbtree_t *tree, rbnode_t *node, rbnode_t *parent, bool dir)
+{
+    node->color = RED;
+    node->left = NULL;
+    node->right = NULL;
+    node->parent = parent;
+    if(parent == NULL) {
+        tree->root = node;
+        return;
+    }
+    parent->children[dir] = node;
+    s_node_insert_fix(tree, node, parent, dir);
+}
+
+void
+s_node_remove_fixup(rbtree_t *tree, rbnode_t *node)
+{
+    bool dir;
+    rbnode_t *parent = node->parent;
+    rbnode_t *sibling;
+    rbnode_t *cnephew;
+    rbnode_t *dnephew;
+
+    dir = CHILD_DIR(node);
+    parent->children[dir] = NULL;
+    while((parent = node->parent) != NULL)
+    {
+        dir = CHILD_DIR(node);
+        sibling = parent->children[1-dir];
+        cnephew = parent->children[  dir];
+        dnephew = parent->children[1-dir];
+        if(sibling->color == RED)
+            goto case3;
+        if(dnephew != NULL && dnephew->color == RED)
+            goto case6;
+        if(cnephew != NULL && cnephew->color == RED)
+            goto case5;
+        if(parent->color == RED)
+            goto case4;
+
+        /* The parent, both nephews, and sibling are black. We need to paint
+         * the sibling black and move up a level.*/
+        sibling->color = RED;
+        node = parent;
+    }
+    return;
+
+case3:
+    /* The sibling is red, which means both nephews and the parent are black.
+     * We rotate the subtree so that the parent moves to become the siblings
+     * left child. The tree is then repainted.*/
+    s_node_rotate(tree, parent, dir);
+    parent->color = RED;
+    sibling->color = BLACK;
+    /* Now we are working on the sibling subtree.*/
+    sibling = cnephew;
+    dnephew = sibling->children[1-dir];
+    if(dnephew != NULL && dnephew->color == BLACK)
+        goto case6;
+    cnephew = sibling->children[dir];
+    if(cnephew != NULL && cnephew->color == RED)
+        goto case5;
+
+case4:
+    sibling->color = RED;
+    parent->color = BLACK;
+    return;
+
+case5:
+    s_node_rotate(tree, sibling, 1-dir);
+    sibling->color = RED;
+    cnephew->color = BLACK;
+    dnephew = sibling;
+    sibling = cnephew;
+
+case6:
+    s_node_rotate(tree, parent, dir);
+    sibling->color = parent->color;
+    parent->color = BLACK;
+    dnephew->color = BLACK;
+}
+
+void
+s_node_remove(rbtree_t *tree, rbnode_t *node)
+{
+    rbnode_t *parent = node->parent;
+    if(node->left != NULL && node->right != NULL) {
+        /* Node is a full tree. We can replace the node with it's successor to
+         * keep the balance.
+         * Needs to recurse if the successor has a right-most child, which is
+         * dealt with in the next case.*/
+        rbnode_t *successor = s_node_successor(node);
+        s_node_copy_value(tree, node, successor);
+        s_node_remove(tree, successor);
+        return;
+    } else if(node->left == NULL && node->right == NULL) {
+        if(parent == NULL) {
+            tree->root = NULL;
+            kfree(node);
+            return;
+        }
+        if(node->color == RED) {
+            parent->children[CHILD_DIR(node)] = NULL;
+            kfree(node);
+            return;
+        }
+        s_node_remove_fixup(tree, node);
+    } else {
+        /* Node has a single child. Because the child must be red as per spec,
+         * and this node must be black, we can simply replace the node
+         * with it's child and color it black.*/
+        rbnode_t *child = node->left == NULL ? node->right : node->left;
+        memcpy(node, child, sizeof(rbnode_t) + tree->objw);
+        node->parent = parent;
+        node->color = BLACK;
+        kfree(child);
+        return;
+    }
+}
+
+void
+__rbtree_new(rbtree_t *tree, size_t objw)
+{
+    *tree = (rbtree_t) {
+        .root = NULL,
+        .objw = objw,
+    };
+}
+
+void*
+rbtree_find(rbtree_t *tree, intmax_t key)
+{
+    rbnode_t *found = s_find(tree, key);
+    if(found == NULL) return NULL;
+    return found->data;
+}
+
+rbnode_t*
+s_node_new(rbtree_t *tree, intmax_t key, void *data)
+{
+    rbnode_t *node = kmalloc(sizeof(rbnode_t) + tree->objw);
+    if(data != NULL) memcpy(node->data, data, tree->objw);
+    node->key = key;
+    return node;
+}
+
+void*
+rbtree_insert(rbtree_t *tree, intmax_t key, void *data)
+{
+    assert(tree != NULL);
+
+    rbnode_t *node = s_closest(tree, key);
+    if(node != NULL && node->key == key) {
+        memcpy(node->data, data, tree->objw);
+    } else if(node != NULL) {
+        rbnode_t *child = s_node_new(tree, key, data);
+        s_node_insert(tree, child, node, node->key > key);
+        return child->data;
+    } else {
+        node = s_node_new(tree, key, data);
+        node->parent = NULL;
+        node->children[0] = node->children[1] = NULL;
+        node->color = BLACK;
+        tree->root = node;
+    }
+    return node->data;
+}
+
+void *rbtree_reserve(rbtree_t *tree, intmax_t key)
+{
+    assert(tree != NULL);
+
+    rbnode_t *node = s_closest(tree, key);
+    if(node != NULL && node->key == key) {
+        return node->data;
+    } else if(node != NULL) {
+        rbnode_t *child = s_node_new(tree, key, NULL);
+        s_node_insert(tree, child, node, node->key > key);
+        return child->data;
+    } else {
+        node = s_node_new(tree, key, NULL);
+        tree->root = node;
+    }
+    return node->data;
+}
+
diff --git a/klib/rbtree.h b/klib/rbtree.h
new file mode 100644
index 0000000..4376713
--- /dev/null
+++ b/klib/rbtree.h
@@ -0,0 +1,48 @@
+#ifndef JOVE_LIB_RBTREE_H
+#define JOVE_LIB_RBTREE_H 1
+
+#include <stdint.h>
+#include <stddef.h>
+#include <stdbool.h>
+#include "memory.h"
+
+typedef struct rbnode
+{
+    struct rbnode *parent;
+    struct rbnode *children[2];
+    intmax_t key;
+    bool color;
+    char data[];
+} rbnode_t;
+
+typedef struct rbtree
+{
+    rbnode_t *root;
+    size_t objw;
+} rbtree_t;
+
+/**Instantiate a new tree based on the given type.
+ * @param tree to instantiate into.
+ * @param type to instantiate for.*/
+#define rbtree_new(tree, type) __rbtree_new(tree, sizeof(type))
+void __rbtree_new(rbtree_t *tree, size_t objw);
+
+/**Find the data corresponding to the key in the tree.
+ * usage: rbtree_find(type)(tree, key);
+ * @param tree to search through.
+ * @param key to search for.
+ * @return */
+void *rbtree_find(rbtree_t *tree, intmax_t key);
+
+/**Insert a value into the given tree using the given key.
+ * If the key is already present within the tree, the existing data is
+ * overwritten.
+ * @param tree to insert into.
+ * @param key to insert.
+ * @param value to insert.
+ * @return pointer to inserted data.
+ * */
+void *rbtree_insert(rbtree_t *tree, intmax_t key, void *value);
+void *rbtree_reserve(rbtree_t *tree, intmax_t key);
+
+#endif
diff --git a/klib/sfmt.c b/klib/sfmt.c
new file mode 100644
index 0000000..519fbf4
--- /dev/null
+++ b/klib/sfmt.c
@@ -0,0 +1,115 @@
+#include "string.h"
+#include "format.h"
+
+char*
+sfmt(char *s, size_t limit, const char *fmt, ...)
+{
+    va_list ap;
+    va_start(ap, fmt);
+
+    s = svfmt(s, limit, fmt, ap);
+
+    va_end(ap);
+    return s;
+}
+
+char*
+svfmt(char *s, size_t limit, const char *fmt, va_list ap)
+{
+
+    size_t fmtlen = strlen(fmt);
+    size_t si = 0;
+    for(size_t fmti = 0; fmti < fmtlen; fmti++)
+    {
+        if(si >= limit) break;
+        if(fmt[fmti] != '%') {
+            s[si++] = fmt[fmti];
+            continue;
+        }
+        // TODO: Format flags
+        fmti++;
+
+        bool alt = false;
+        bool zpad = false;
+        for(;;fmti++){
+            if(fmt[fmti] == '#') { alt = true; continue; }
+            if(fmt[fmti] == '0') { zpad = true; continue; }
+            break;
+        }
+        int fwidth = 0;
+        if(fmt[fmti] >= '1' && fmt[fmti] <= '9')
+        {
+            for(;fmt[fmti] >= '0' && fmt[fmti] <= '9';fmti++) {
+                fwidth *= 10;
+                fwidth += fmt[fmti] - '0';
+            }
+        }
+        int precision = 0;
+        if(fmt[fmti] == '.')
+        {
+            fmti++;
+            for(;fmt[fmti] >= '0' && fmt[fmti] <= '9';fmti++) {
+                precision *= 10;
+                precision += fmt[fmti] - '0';
+            }
+        }
+
+        bool sgn = true;
+        bool upper = false;
+        int radix = 10;
+        switch(fmt[fmti])
+        {
+            case '%':
+                s[si++] = '%';
+                break;
+            case 'p':
+                radix = 16;
+                alt = true;
+            case 'b':
+                if(radix == 10) radix = 2;
+            case 'X':
+                upper = true;
+            case 'x':
+                if(radix == 10)
+                    radix = 16;
+            case 'o':
+                if(radix == 10)
+                    radix = 8;
+            case 'u':
+                sgn = false;
+            case 'i': {
+                if((radix == 8 || radix == 16) && alt) {
+                    s[si++] = '0';
+                    if(radix == 16) {
+                        s[si++] = 'x';
+                    }
+                    if(radix == 2) {
+                        s[si++] = 'b';
+                    }
+                }
+                size_t osi = si;
+                size_t nlen = ltostr(&s[si], limit - si, va_arg(ap, long), sgn, radix);
+                if(upper) sntoupper(&s[si], nlen);
+                si += nlen;
+
+                int lpad = fwidth - (int)nlen;
+                if(lpad > 0)
+                {
+                    if(lpad + osi >= limit) lpad = (limit - osi - 1);
+                    memmove(&s[osi + lpad], &s[osi], nlen);
+                    memset(&s[osi], zpad ? '0' : ' ', lpad);
+                    si += lpad;
+                }
+                      } break;
+            case 's': {
+                const char *str = va_arg(ap, char*);
+                size_t slen = strlen(str);
+                size_t wlen = slen > limit - si ? limit - si : slen;
+                for(size_t i = 0; i < wlen; i++)
+                    s[si++] = str[i];
+                      } break;
+        }
+    }
+    s[si] = 0;
+    return s;
+}
diff --git a/klib/spinlock.h b/klib/spinlock.h
new file mode 100644
index 0000000..75af28a
--- /dev/null
+++ b/klib/spinlock.h
@@ -0,0 +1,27 @@
+#ifndef JOVE_LIB_SPINLOCK_H
+#define JOVE_LIB_SPINLOCK_H 1
+
+#include <stdatomic.h>
+
+typedef struct Spinlock
+{
+    atomic_flag flg;
+    
+    const char *locker_file;
+    const char *locker_func;
+    int locker_line;
+} spinlock_t;
+
+#define spinlock_acquire(lock) \
+    while(atomic_flag_test_and_set_explicit(&lock.flg, memory_order_acquire)) \
+        __builtin_ia32_pause(); \
+    lock.locker_file = __FILE__; \
+    lock.locker_func = __FUNCTION__; \
+    lock.locker_line = __LINE__
+
+#define spinlock_release(lock) \
+    atomic_flag_clear_explicit(&lock.flg, memory_order_release); \
+    lock.locker_file = lock.locker_func = NULL; \
+    lock.locker_line = -1
+
+#endif
diff --git a/klib/string.c b/klib/string.c
new file mode 100644
index 0000000..4bb1bad
--- /dev/null
+++ b/klib/string.c
@@ -0,0 +1,16 @@
+#include "string.h"
+
+size_t strlen(const char *s) {
+    size_t l = 0;
+    for(; *s != 0; s++, l++);
+    return l;
+}
+
+int strcmp(const char *a, const char *b)
+{
+    size_t i = 0;
+    for(; a[i] != 0 && b[i] != 0; i++) {
+        if(a[i] != b[i]) return a[i] - b[i];
+    }
+    return a[i] - b[i];
+}
diff --git a/klib/toupper.c b/klib/toupper.c
new file mode 100644
index 0000000..807eb38
--- /dev/null
+++ b/klib/toupper.c
@@ -0,0 +1,26 @@
+#include "string.h"
+
+int
+toupper(int c)
+{
+    if(c >= 'a' && c <= 'z')
+        c -= ('a' - 'A');
+    return c;
+}
+
+char*
+stoupper(char *s)
+{
+    char *o = s;
+    for(; *s != 0; s++)
+        *s = toupper(*s);
+    return o;
+}
+
+char*
+sntoupper(char *s, size_t limit)
+{
+    for(size_t i = 0; i < limit; i++)
+        s[i] = toupper(s[i]);
+    return s;
+}