Reorganize all.

17 files changed, 1075 insertions, 0 deletions

diff --git a/src/common/Makefile b/src/common/Makefile
new file mode 100644
index 0000000..d27c6d5
--- /dev/null
+++ b/src/common/Makefile
@@ -0,0 +1,11 @@
+OBJ = string.o printf.o slab_alloc.o mutex.o hashtbl.o buffer.o
+
+LIB = 
+
+CFLAGS = -I ./include
+
+LDFLAGS = 
+
+OUT = common.lib
+
+include ../rules.make
diff --git a/src/common/README b/src/common/README
new file mode 100644
index 0000000..deae76f
--- /dev/null
+++ b/src/common/README
@@ -0,0 +1,18 @@
+This directory contains the library functions common to userland
+and kernel code.
+
+It relies on a few functions being exported :
+
+- panic(char* msg, char* file, int line)
+- panic_assert(char* assert, char* file, int line)
+- dbg_print(const char* str)
+- void* malloc(size_t size)
+- free(void* ptr)
+
+These function are supposed to be defined in the code that calls
+the common functions. The headers for these functions are to be
+found in `assert.h` and `malloc.h`.
+
+Panic and panic_assert end the execution of the current program
+(or of the kernel when in kernel-mode).
+
diff --git a/src/common/buffer.c b/src/common/buffer.c
new file mode 100644
index 0000000..21f1ec4
--- /dev/null
+++ b/src/common/buffer.c
@@ -0,0 +1,167 @@
+#include <malloc.h>
+
+#include <buffer.h>
+#include <string.h>
+
+#include <debug.h>
+
+// three types of buffers
+#define T_BYTES		1
+#define T_SLICE		2
+#define T_CONCAT	3
+
+struct buffer {
+	uint16_t rc, type;		// takes less space like this
+	size_t len;
+	union {
+		struct {
+			const char* data;
+			bool owned;
+		} bytes;
+		struct {
+			struct buffer *buf;
+			size_t begin;
+		} slice;
+		struct {
+			struct buffer *a, *b;
+		} concat;
+	};
+};
+
+void buffer_ref(buffer_t *b) {
+	b->rc++;
+}
+
+void buffer_unref(buffer_t *b) {
+	b->rc--;
+	if (b->rc == 0) {
+		switch (b->type) {
+			case T_BYTES:
+				if (b->bytes.owned) free((void*)b->bytes.data);
+				break;
+			case T_SLICE:
+				buffer_unref(b->slice.buf);
+				break;
+			case T_CONCAT:
+				buffer_unref(b->concat.a);
+				buffer_unref(b->concat.b);
+				break;
+			default:
+				ASSERT(false);
+		}
+		free(b);
+	}
+}
+
+size_t buffer_size(buffer_t *b) {
+	return b->len;
+}
+
+size_t read_buffer(buffer_t *b, char* dest, size_t begin, size_t n) {
+	if (begin >= b->len) return 0;
+	if (begin + n >= b->len) n = b->len - begin;
+
+	switch (b->type) {
+		case T_BYTES:
+			memcpy(dest, b->bytes.data + begin, n);
+			break;
+		case T_SLICE:
+			read_buffer(b->slice.buf, dest, begin + b->slice.begin, n);
+			break;
+		case T_CONCAT: {
+			size_t la = b->concat.a->len;
+			if (begin < la) {
+				size_t r = read_buffer(b->concat.a, dest, begin, n);
+				if (r < n) {
+					ASSERT(read_buffer(b->concat.b, dest, 0, n - r) == n - r);
+				}
+			} else {
+				ASSERT(read_buffer(b->concat.b, dest, begin - la, n) == n);
+			}
+			break;
+		}
+		default:
+			ASSERT(false);
+	}
+
+	return n;
+}
+
+// ========================= //
+// BUFFER CREATION FUNCTIONS //
+// ========================= //
+
+buffer_t *buffer_from_bytes_nocopy(const char* data, size_t n, bool own_bytes) {
+	buffer_t *b = (buffer_t*)malloc(sizeof(buffer_t));
+	if (b == 0) return 0;
+
+	b->rc = 1;
+	b->type = T_BYTES;
+	b->len = n;
+	b->bytes.data = data;
+	b->bytes.owned = own_bytes;
+
+	return b;
+}
+buffer_t *buffer_from_bytes(const char* data, size_t n) {
+	char* data2 = (char*)malloc(n);
+	if (data2 == 0) return 0;
+
+	memcpy(data2, data, n);
+
+	buffer_t *b = buffer_from_bytes_nocopy(data2, n, true);
+	if (b == 0) {
+		free(data2);
+		return 0;
+	}
+
+	return b;
+}
+
+
+buffer_t* buffer_slice(buffer_t* src, size_t begin, size_t n) {
+	if (begin + n > src->len) return 0;	// invalid request
+
+	buffer_t *b = (buffer_t*)malloc(sizeof(buffer_t));
+	if (b == 0) return 0;
+
+	b->rc = 1;
+	b->type = T_SLICE;
+	b->len = n;
+	b->slice.buf = src;
+	b->slice.begin = begin;
+
+	return b;
+}
+
+buffer_t* buffer_concat(buffer_t* a, buffer_t* b) {
+	buffer_t *r = (buffer_t*)malloc(sizeof(buffer_t));
+	if (r == 0) return r;
+
+	r->rc = 1;
+	r->type = T_CONCAT;
+	r->len = a->len + b->len;
+	r->concat.a = a;
+	r->concat.b = b;
+
+	return r;
+}
+
+buffer_t* buffer_slice_k(buffer_t *b, size_t begin, size_t n) {
+	buffer_t *r = buffer_slice(b, begin, n);
+	if (r != 0) {
+		buffer_ref(b);
+	}
+	return r;
+}
+
+buffer_t* buffer_concat_k(buffer_t *a, buffer_t *b) {
+	buffer_t *r = buffer_concat(a, b);
+	if (r != 0) {
+		buffer_ref(a);
+		buffer_ref(b);
+	}
+	return r;
+}
+
+/* vim: set ts=4 sw=4 tw=0 noet :*/
diff --git a/src/common/common.lib b/src/common/common.lib
new file mode 100644
index 0000000..16259e6
--- /dev/null
+++ b/src/common/common.lib
diff --git a/src/common/hashtbl.c b/src/common/hashtbl.c
new file mode 100644
index 0000000..47072b4
--- /dev/null
+++ b/src/common/hashtbl.c
@@ -0,0 +1,166 @@
+#include <hashtbl.h>
+#include <malloc.h>
+#include <string.h>
+
+#define DEFAULT_INIT_SIZE 16
+#define SLOT_OF_HASH(k, nslots) (((size_t)(k)*21179)%(size_t)(nslots))
+
+typedef struct hashtbl_item {
+	void* key;
+	void* val;
+	struct hashtbl_item *next;
+} hashtbl_item_t;
+
+// When nitems > size * 3/4, size is multiplied by two
+// When nitems < size * 1/4, size is divided by two
+struct hashtbl {
+	key_eq_fun_t ef;
+	hash_fun_t hf;
+	size_t size, nitems;
+	hashtbl_item_t **items;
+};
+
+hashtbl_t *create_hashtbl(key_eq_fun_t ef, hash_fun_t hf, size_t initial_size) {
+	hashtbl_t *ht = (hashtbl_t*)malloc(sizeof(hashtbl_t));
+	if (ht == 0) return 0;
+
+	ht->ef = ef;
+	ht->hf = hf;
+
+	ht->size = (initial_size == 0 ? DEFAULT_INIT_SIZE : initial_size);
+	ht->nitems = 0;
+
+	ht->items = (hashtbl_item_t**)malloc(ht->size * sizeof(hashtbl_item_t*));
+	if (ht->items == 0) {
+		free(ht);
+		return 0;
+	}
+
+	for (size_t i = 0; i < ht->size; i++) ht->items[i] = 0;
+
+	return ht;
+}
+
+void delete_hashtbl(hashtbl_t *ht) {
+	// Free items
+	for (size_t i = 0; i < ht->size; i++) {
+		while (ht->items[i] != 0) {
+			hashtbl_item_t *n = ht->items[i]->next;
+			free(ht->items[i]);
+			ht->items[i] = n;
+		}
+	}
+
+	// Free table
+	free(ht->items);
+	free(ht);
+}
+
+static void hashtbl_check_size(hashtbl_t *ht) {
+	size_t nsize = 0;
+	if (4 * ht->nitems < ht->size) nsize = ht->size / 2;
+	if (4 * ht->nitems > 3 * ht->size) nsize = ht->size * 2;
+
+	if (nsize != 0) {
+		hashtbl_item_t **nitems = (hashtbl_item_t**)malloc(nsize * sizeof(hashtbl_item_t*));
+		if (nitems == 0) return;	// if we can't realloc, too bad, we just lose space
+
+		for (size_t i = 0; i < nsize; i++) nitems[i] = 0;
+
+		// rehash
+		for (size_t i = 0; i < ht->size; i++) {
+			while (ht->items[i] != 0) {
+				hashtbl_item_t *x = ht->items[i];
+				ht->items[i] = x->next;
+
+				size_t slot = SLOT_OF_HASH(ht->hf(x->key), nsize);
+				x->next = nitems[slot];
+				nitems[slot] = x;
+			}
+		}
+		free(ht->items);
+		ht->size = nsize;
+		ht->items = nitems;
+	}
+}
+
+int hashtbl_add(hashtbl_t *ht, void* key, void* v) {
+	size_t slot = SLOT_OF_HASH(ht->hf(key), ht->size);
+
+	hashtbl_item_t *i = (hashtbl_item_t*)malloc(sizeof(hashtbl_item_t));
+	if (i == 0) return 1;	// OOM
+
+	// make sure item is not already present
+	hashtbl_remove(ht, key);
+
+	i->key = key;
+	i->val = v;
+	i->next = ht->items[slot];
+	ht->items[slot] = i;
+	ht->nitems++;
+
+	hashtbl_check_size(ht);
+
+	return 0;
+}
+
+void* hashtbl_find(hashtbl_t* ht, void* key) {
+	size_t slot = SLOT_OF_HASH(ht->hf(key), ht->size);
+
+	for (hashtbl_item_t *i = ht->items[slot]; i != 0; i = i->next) {
+		if (ht->ef(i->key, key)) return i->val;
+	}
+
+	return 0;
+}
+
+void hashtbl_remove(hashtbl_t* ht, void* key) {
+	size_t slot = SLOT_OF_HASH(ht->hf(key), ht->size);
+
+	if (ht->items[slot] == 0) return;
+
+	if (ht->ef(ht->items[slot]->key, key)) {
+		hashtbl_item_t *x = ht->items[slot];
+		ht->items[slot] = x->next;
+		free(x);
+		ht->nitems--;
+	} else {
+		for (hashtbl_item_t *i = ht->items[slot]; i->next != 0; i = i->next) {
+			if (ht->ef(i->next->key, key)) {
+				hashtbl_item_t *x = i->next;
+				i->next = x->next;
+				free(x);
+				ht->nitems--;
+				break;
+			}
+		}
+	}
+	
+	hashtbl_check_size(ht);
+}
+
+size_t hashtbl_count(hashtbl_t* ht) {
+	return ht->nitems;
+}
+
+hash_t id_hash_fun(const void* v) {
+	return (hash_t)v;
+}
+
+hash_t str_hash_fun(const void* v) {
+	hash_t h = 712;
+	for (char* s = (char*)v; *s != 0; s++) {
+		h = h * 101 + *s;
+	}
+	return h;
+}
+
+bool id_key_eq_fun(const void* a, const void* b) {
+	return a == b;
+}
+
+bool str_key_eq_fun(const void* a, const void* b) {
+	return strcmp((const char*)a, (const char*)b) == 0;
+}
+
+/* vim: set ts=4 sw=4 tw=0 noet :*/
diff --git a/src/common/include/buffer.h b/src/common/include/buffer.h
new file mode 100644
index 0000000..0d6cfbf
--- /dev/null
+++ b/src/common/include/buffer.h
@@ -0,0 +1,41 @@
+#pragma once
+
+#include <stdint.h>
+#include <stddef.h>
+#include <stdbool.h>
+
+// The buffer_t type is a simple reference-counted buffer type
+// enabling the creation, sharing, slicing and concatenation of buffers
+// without having to copy everything each time
+
+// Buffers are always allocated on the core kernel heap (kmalloc/kfree)
+
+// Once a buffer is allocated, its contents is immutable
+
+// Encoding and decoding functions for buffer contents are provided in
+// a separate file (encode.h)
+
+struct buffer;
+typedef struct buffer buffer_t;
+
+void buffer_ref(buffer_t*);				// increase reference counter
+void buffer_unref(buffer_t*);			// decrease reference counter
+
+size_t buffer_len(buffer_t* buf);
+size_t read_buffer(buffer_t* buf, char* to, size_t begin, size_t n);	// returns num of bytes read
+
+buffer_t* buffer_from_bytes(const char* data, size_t n);	// bytes are COPIED
+buffer_t* buffer_from_bytes_nocopy(const char* data, size_t n, bool own_bytes);	// bytes are NOT COPIED
+
+// these functions GIVE the buffer in order to create the new buffer, ie they do not increase RC
+// the buffer is NOT GIVED if the new buffer could not be created (ie retval == 0)
+buffer_t* buffer_slice(buffer_t* b, size_t begin, size_t n);
+buffer_t* buffer_concat(buffer_t* a, buffer_t* b);
+
+// these functions KEEP a reference on the buffer (ie RC is incremented)
+// the RC is NOT INCREMENTED if the new buffer cannot be created
+buffer_t* buffer_slice_k(buffer_t* b, size_t begin, size_t n);
+buffer_t* buffer_concat_k(buffer_t* a, buffer_t* b);
+
+
+/* vim: set ts=4 sw=4 tw=0 noet :*/
diff --git a/src/common/include/debug.h b/src/common/include/debug.h
new file mode 100644
index 0000000..a4b8b6f
--- /dev/null
+++ b/src/common/include/debug.h
@@ -0,0 +1,14 @@
+#pragma once
+
+#include <stddef.h>
+#include <stdint.h>
+
+void panic(const char* message, const char* file, int line);
+void panic_assert(const char* assertion, const char* file, int line);
+#define PANIC(s) panic(s, __FILE__, __LINE__);
+#define ASSERT(s) { if (!(s)) panic_assert(#s, __FILE__, __LINE__); }
+
+void dbg_print(const char* str);
+void dbg_printf(const char* format, ...);
+
+/* vim: set ts=4 sw=4 tw=0 noet :*/
diff --git a/src/common/include/hashtbl.h b/src/common/include/hashtbl.h
new file mode 100644
index 0000000..16dfefb
--- /dev/null
+++ b/src/common/include/hashtbl.h
@@ -0,0 +1,34 @@
+#pragma once
+
+#include <stdint.h>
+#include <stddef.h>
+#include <stdbool.h>
+
+// Simple hashtable structure (key -> void*)
+// Supports adding, seeking, removing
+// When adding a binding to the table, the previous binding for same key (if exists) is removed
+
+// TODO : possibility to allocate the hashtbl structure on any heap
+// (currently uses kmalloc/kfree)
+
+struct hashtbl;
+typedef struct hashtbl hashtbl_t;
+
+typedef size_t hash_t;
+typedef hash_t (*hash_fun_t)(const void*);
+typedef bool (*key_eq_fun_t)(const void*, const void*);
+
+hashtbl_t* create_hashtbl(key_eq_fun_t ef, hash_fun_t hf, size_t initial_size);	// 0 -> default size
+void delete_hashtbl(hashtbl_t* ht);
+
+int hashtbl_add(hashtbl_t* ht, void* key, void* v);	// non-null on error (OOM for instance)
+void* hashtbl_find(hashtbl_t* ht, void* key);		// null when not found
+void hashtbl_remove(hashtbl_t* ht, void* key);
+size_t hashtbl_count(hashtbl_t* ht);
+
+hash_t id_hash_fun(const void* v);
+hash_t str_hash_fun(const void* v);
+bool id_key_eq_fun(const void* a, const void* b);
+bool str_key_eq_fun(const void* a, const void* b);
+
+/* vim: set ts=4 sw=4 tw=0 noet :*/
diff --git a/src/common/include/malloc.h b/src/common/include/malloc.h
new file mode 100644
index 0000000..0ba5572
--- /dev/null
+++ b/src/common/include/malloc.h
@@ -0,0 +1,11 @@
+#pragma once
+
+#include <stdint.h>
+#include <stddef.h>
+
+// Header is in common/, but implementation is not.
+
+void* malloc(size_t sz);
+void free(void* ptr);
+
+/* vim: set ts=4 sw=4 tw=0 noet :*/
diff --git a/src/common/include/mutex.h b/src/common/include/mutex.h
new file mode 100644
index 0000000..6814adf
--- /dev/null
+++ b/src/common/include/mutex.h
@@ -0,0 +1,21 @@
+#pragma once
+
+#include <stdint.h>
+
+#define MUTEX_LOCKED 1
+#define MUTEX_UNLOCKED 0
+
+
+typedef uint32_t mutex_t;
+
+void mutex_lock(mutex_t* mutex);	//wait for mutex to be free
+int mutex_try_lock(mutex_t* mutex);	//lock mutex only if free, returns !0 if locked, 0 if was busy
+void mutex_unlock(mutex_t* mutex);
+
+// the mutex code assumes a yield() function is defined somewhere
+void yield();
+
+#define STATIC_MUTEX(name) static mutex_t name __attribute__((section("locks"))) = MUTEX_UNLOCKED;
+	
+
+/* vim: set ts=4 sw=4 tw=0 noet :*/
diff --git a/src/common/include/printf.h b/src/common/include/printf.h
new file mode 100644
index 0000000..b4e1c1b
--- /dev/null
+++ b/src/common/include/printf.h
@@ -0,0 +1,10 @@
+#pragma once
+
+#include <stddef.h>
+#include <stdint.h>
+#include <stdarg.h>
+
+int snprintf(char* s, size_t n, const char* format, ...);
+int vsnprintf(char* s, size_t n, const char* format, va_list arg);
+
+/* vim: set ts=4 sw=4 tw=0 noet :*/
diff --git a/src/common/include/slab_alloc.h b/src/common/include/slab_alloc.h
new file mode 100644
index 0000000..c8d5d6c
--- /dev/null
+++ b/src/common/include/slab_alloc.h
@@ -0,0 +1,45 @@
+#pragma once
+
+// Self-contained piece of library : a slab allocator...
+// Depends on page_alloc_fun_t and page_free_fun_t : a couple of functions
+// that can allocate/free multiples of one page at a time
+
+#include <stdint.h>
+#include <stddef.h>
+#include <stdbool.h>
+
+
+#if defined(__linux__)
+//redefine necessary stuff
+#include <assert.h> 		// standard linux assert.h
+#define ASSERT assert
+#include <stdio.h> 
+#define dbg_printf printf
+#else
+#include <debug.h>
+#endif
+
+#define PAGE_SIZE 0x1000
+
+// expected format for the array of slab_type_t given to slab_create :
+// an array of slab_type descriptors, with last descriptor full of zeroes
+// and with obj_size increasing (strictly) in the array
+typedef struct slab_type {
+	const char *descr;
+	size_t obj_size;
+	size_t pages_per_cache;
+} slab_type_t;
+
+struct mem_allocator;
+typedef struct mem_allocator mem_allocator_t;
+
+typedef void* (*page_alloc_fun_t)(size_t bytes);
+typedef void (*page_free_fun_t)(void* ptr);
+
+mem_allocator_t* create_slab_allocator(const slab_type_t *types, page_alloc_fun_t af, page_free_fun_t ff);
+void destroy_slab_allocator(mem_allocator_t*);
+
+void* slab_alloc(mem_allocator_t* a, size_t sz);
+void slab_free(mem_allocator_t* a, void* ptr);
+
+/* vim: set ts=4 sw=4 tw=0 noet :*/
diff --git a/src/common/include/string.h b/src/common/include/string.h
new file mode 100644
index 0000000..682b25a
--- /dev/null
+++ b/src/common/include/string.h
@@ -0,0 +1,17 @@
+#pragma once
+
+#include <stddef.h>
+#include <stdint.h>
+
+void *memcpy(void *dest, const void *src, size_t count);
+void *memset(void *dest, int val, size_t count);
+int memcmp(const void *s1, const void *s2, size_t n);
+void *memmove(void *dest, const void *src, size_t count);
+
+size_t strlen(const char *str);
+char *strchr(const char *str, char c);
+char *strcpy(char *dest, const char *src);
+char *strcat(char *dest, const char *src);
+int strcmp(const char *s1, const char *s2);
+
+/* vim: set ts=4 sw=4 tw=0 noet :*/
diff --git a/src/common/mutex.c b/src/common/mutex.c
new file mode 100644
index 0000000..cda8049
--- /dev/null
+++ b/src/common/mutex.c
@@ -0,0 +1,27 @@
+#include <mutex.h>
+
+/*	Internal use only. This function is atomic, meaning it cannot be interrupted by a system task switch. */
+static uint32_t atomic_exchange(uint32_t* ptr, uint32_t newval) {
+	uint32_t r;
+	asm volatile("xchg (%%ecx), %%eax" : "=a"(r) : "c"(ptr), "a"(newval));
+	return r;
+}
+
+void mutex_lock(uint32_t* mutex) {
+	while (atomic_exchange(mutex, MUTEX_LOCKED) == MUTEX_LOCKED) {
+		yield();
+	}
+}
+
+int mutex_try_lock(uint32_t* mutex) {
+	if (atomic_exchange(mutex, MUTEX_LOCKED) == MUTEX_LOCKED) {
+		return 0;
+	}
+	return 1;
+}
+
+void mutex_unlock(uint32_t* mutex) {
+	*mutex = MUTEX_UNLOCKED;
+}
+
+/* vim: set ts=4 sw=4 tw=0 noet :*/
diff --git a/src/common/printf.c b/src/common/printf.c
new file mode 100644
index 0000000..68e08d8
--- /dev/null
+++ b/src/common/printf.c
@@ -0,0 +1,120 @@
+#include <printf.h>
+#include <stdarg.h>
+
+int snprintf(char * buff, size_t len, const char *format, ...) {
+	va_list ap;
+
+	va_start(ap, format);
+	len = vsnprintf(buff, len, format, ap);
+	va_end(ap);
+
+	return len;
+}
+
+int vsnprintf(char *buff, size_t len, const char* format, va_list ap){
+	size_t i, result;
+
+	if (!buff || !format)
+		return -1;
+
+#define PUTCHAR(thechar) \
+	do { \
+		if (result < len-1) \
+		*buff++ = (thechar);  \
+		result++; \
+	} while (0)
+
+	result = 0;
+	for(i = 0; format[i] != '\0' ; i++) {
+		if (format[i] == '%') {
+			i++;
+			switch(format[i]) {
+				case '%':
+					PUTCHAR('%');
+					break;
+
+				case 'i':;
+				case 'd': {
+					 int integer = va_arg(ap,int);
+					 int cpt2 = 0;
+					 char buff_int[16];
+
+					 if (integer<0)
+						 PUTCHAR('-');
+
+					 do {
+						 int m10 = integer%10;
+						 m10 = (m10 < 0)? -m10:m10;
+						 buff_int[cpt2++] = (char)('0'+ m10);
+						 integer = integer/10;
+					 } while(integer != 0);
+
+					 for(cpt2 = cpt2 - 1; cpt2 >= 0; cpt2--)
+						 PUTCHAR(buff_int[cpt2]);
+
+					 break;
+				}
+				case 'c': {
+					 int value = va_arg(ap,int);
+					 PUTCHAR((char)value);
+					 break;
+				}
+				case 's': {
+					 char *string = va_arg(ap,char *);
+					 if (!string)
+						 string = "(null)";
+					 for(; *string != '\0' ; string++)
+						 PUTCHAR(*string);
+					 break;
+				}
+				case 'x': {
+					 unsigned int hexa = va_arg(ap,int);
+					 unsigned int nb;
+					 int j, had_nonzero = 0;
+					 for(j = 0; j < 8; j++) {
+						 nb = (unsigned int)(hexa << (j*4));
+						 nb = (nb >> 28) & 0xf;
+						 // Skip the leading zeros
+						 if (nb == 0) {
+							 if (had_nonzero)
+								 PUTCHAR('0');
+						 } else {
+							 had_nonzero = 1;
+							 if (nb < 10)
+								 PUTCHAR('0'+nb);
+							 else
+								 PUTCHAR('a'+(nb-10));
+						 }
+					 }
+					 if (!had_nonzero)
+						 PUTCHAR('0');
+					 break;
+				}
+				case 'p': {
+					 unsigned int hexa = va_arg(ap,int);
+					 unsigned int nb;
+					 int j;
+					 for (j = 0; j < 8; j++) {
+						 nb = (unsigned int)(hexa << (j*4));
+						 nb = (nb >> 28) & 0xf;
+						 if (nb < 10)
+							 PUTCHAR('0'+nb);
+						 else
+							 PUTCHAR('a'+(nb-10));
+					 }
+					 break;
+				}
+				default:
+					 PUTCHAR('%');
+					 PUTCHAR(format[i]);
+			}
+		} else {
+			PUTCHAR(format[i]);
+		}
+	}
+
+	*buff = '\0';
+	return result;
+}
+
+/* vim: set ts=4 sw=4 tw=0 noet :*/
diff --git a/src/common/slab_alloc.c b/src/common/slab_alloc.c
new file mode 100644
index 0000000..714c49f
--- /dev/null
+++ b/src/common/slab_alloc.c
@@ -0,0 +1,283 @@
+#include <slab_alloc.h>
+
+typedef struct object {
+	struct object *next;
+} object_t;
+
+typedef struct cache {
+	void* region_addr;
+	
+	uint32_t n_free_objs;
+	object_t* first_free_obj;
+
+	struct cache *next_cache;	// next cache in this slab
+} cache_t;
+
+typedef struct region {
+	void* region_addr;
+	size_t region_size;
+	struct region *next_region;
+	bool contains_descriptors;
+} region_t;
+
+typedef union descriptor {
+	cache_t c;
+	region_t r;
+	union descriptor *next_free;
+} descriptor_t;
+
+typedef struct slab {
+	cache_t *first_cache;		// linked list of caches
+} slab_t;
+
+struct mem_allocator {
+	const slab_type_t *types;
+	slab_t *slabs;
+
+	descriptor_t *first_free_descriptor;
+	region_t *all_regions;
+
+	page_alloc_fun_t alloc_fun;
+	page_free_fun_t free_fun;
+};
+
+// ============================================== //
+// Helper functions for the manipulation of lists //
+// ============================================== //
+
+static void add_free_descriptor(mem_allocator_t *a, descriptor_t *c) {
+	c->next_free = a->first_free_descriptor;
+	a->first_free_descriptor = c;
+}
+
+static descriptor_t *take_descriptor(mem_allocator_t *a) {
+	if (a->first_free_descriptor == 0) {
+		void* p = a->alloc_fun(PAGE_SIZE);
+		if (p == 0) return 0;
+
+		const void* end = p + PAGE_SIZE;
+		for (descriptor_t *i = (descriptor_t*)p; i + 1 <= (descriptor_t*)end; i++) {
+			add_free_descriptor(a, i);
+		}
+
+		// register the descriptor region
+		descriptor_t *dd = a->first_free_descriptor;
+		ASSERT(dd != 0);
+		a->first_free_descriptor = dd->next_free;
+
+		region_t *drd = &dd->r;
+		drd->region_addr = p;
+		drd->region_size = PAGE_SIZE;
+		drd->contains_descriptors = true;
+		drd->next_region = a->all_regions;
+		a->all_regions = drd;
+	}
+
+	descriptor_t *x = a->first_free_descriptor;
+	ASSERT(x != 0);
+	a->first_free_descriptor = x->next_free;
+	return x;
+}
+
+// ============================== //
+// The actual allocator functions //
+// ============================== //
+
+mem_allocator_t* create_slab_allocator(const slab_type_t *types, page_alloc_fun_t af, page_free_fun_t ff) {
+	union {
+		void* addr;
+		mem_allocator_t *a;
+		slab_t *s;
+		descriptor_t *d;
+	} ptr;
+
+	ptr.addr = af(PAGE_SIZE);
+	if (ptr.addr == 0) return 0;	// could not allocate
+	const void* end_addr = ptr.addr + PAGE_SIZE;
+
+	mem_allocator_t *a = ptr.a;
+	ptr.a++;
+
+	a->all_regions = 0;
+	a->alloc_fun = af;
+	a->free_fun = ff;
+
+	a->types = types;
+	a->slabs = ptr.s;
+	for (const slab_type_t *t = types; t->obj_size != 0; t++) {
+		ASSERT(t->obj_size >= sizeof(object_t));
+		ptr.s->first_cache = 0;
+		ptr.s++;
+	}
+
+	a->first_free_descriptor = 0;
+	while (ptr.d + 1 <= (descriptor_t*)end_addr) {
+		add_free_descriptor(a, ptr.d);
+		ptr.d++;
+	}
+
+	return a;
+}
+
+static void stack_and_destroy_regions(page_free_fun_t ff, region_t *r) {
+	if (r == 0) return;
+	void* addr = r->region_addr;
+	ASSERT(r != r->next_region);
+	stack_and_destroy_regions(ff, r->next_region);
+	ff(addr);
+}
+void destroy_slab_allocator(mem_allocator_t *a) {
+	for (int i = 0; a->types[i].obj_size != 0; i++) {
+		for (cache_t *c = a->slabs[i].first_cache; c != 0; c = c->next_cache) {
+			a->free_fun(c->region_addr);
+		}
+	}
+	region_t *dr = 0;
+	region_t *i = a->all_regions;
+	while (i != 0) {
+		region_t *r = i;
+		i = r->next_region;
+		if (r->contains_descriptors) {
+			r->next_region = dr;
+			dr = r;
+		} else {
+			a->free_fun(r->region_addr);
+		}
+	}
+	stack_and_destroy_regions(a->free_fun, dr);
+	a->free_fun(a);
+}
+
+void* slab_alloc(mem_allocator_t* a, size_t sz) {
+	for (int i = 0; a->types[i].obj_size != 0; i++) {
+		const size_t obj_size = a->types[i].obj_size;
+		if (sz <= obj_size) {
+			// find a cache with free space
+			cache_t *fc = a->slabs[i].first_cache;
+			while (fc != 0 && fc->n_free_objs == 0) {
+				ASSERT(fc->first_free_obj == 0); // make sure n_free == 0 iff no object in the free stack
+				fc = fc->next_cache;
+			}
+			// if none found, try to allocate a new one
+			if (fc == 0) {
+				descriptor_t *fcd = take_descriptor(a);
+				if (fcd == 0) return 0;
+
+				fc = &fcd->c;
+				ASSERT((descriptor_t*)fc == fcd);
+
+				const size_t cache_size = a->types[i].pages_per_cache * PAGE_SIZE;
+				fc->region_addr = a->alloc_fun(cache_size);
+				if (fc->region_addr == 0) {
+					add_free_descriptor(a, fcd);
+					return 0;
+				}
+
+				fc->n_free_objs = 0;
+				fc->first_free_obj = 0;
+				for (void* p = fc->region_addr; p + obj_size <= fc->region_addr + cache_size; p += obj_size) {
+					object_t *x = (object_t*)p;
+					x->next = fc->first_free_obj;
+					fc->first_free_obj = x;
+					fc->n_free_objs++;
+				}
+				ASSERT(fc->n_free_objs == cache_size / obj_size);
+
+				fc->next_cache = a->slabs[i].first_cache;
+				a->slabs[i].first_cache = fc;
+			}
+			// allocate on fc
+			ASSERT(fc != 0 && fc->n_free_objs > 0);
+
+			object_t *x = fc->first_free_obj;
+			fc->first_free_obj = x->next;
+			fc->n_free_objs--;
+
+			ASSERT((fc->n_free_objs == 0) == (fc->first_free_obj == 0));
+
+			// TODO : if fc is full, put it at the end
+			return x;
+		}
+	}
+
+	// otherwise directly allocate using a->alloc_fun
+	descriptor_t *rd = take_descriptor(a);
+	if (rd == 0) return 0;
+	region_t *r = &rd->r;
+	ASSERT((descriptor_t*)r == rd);
+
+	r->region_addr = a->alloc_fun(sz);
+	if (r->region_addr == 0) {
+		add_free_descriptor(a, rd);
+		return 0;
+	} else {
+		r->region_size = sz;
+		r->contains_descriptors = false;
+
+		r->next_region = a->all_regions;
+		a->all_regions = r;
+
+		return (void*)r->region_addr;
+	}
+}
+
+void slab_free(mem_allocator_t* a, void* addr) {
+
+	for (int i = 0; a->types[i].obj_size != 0; i++) {
+		size_t region_size = PAGE_SIZE * a->types[i].pages_per_cache;
+		for (cache_t *r = a->slabs[i].first_cache; r != 0; r = r->next_cache) {
+			if (addr >= r->region_addr && addr < r->region_addr + region_size) {
+				ASSERT((addr - r->region_addr) % a->types[i].obj_size == 0);
+
+				object_t *o = (object_t*)addr;
+				o->next = r->first_free_obj;
+				r->first_free_obj = o;
+				r->n_free_objs++;
+
+				if (r->n_free_objs == region_size / a->types[i].obj_size) {
+					// region is completely unused, free it.
+					if (a->slabs[i].first_cache == r) {
+						a->slabs[i].first_cache = r->next_cache;
+					} else {
+						for (cache_t *it = a->slabs[i].first_cache; it->next_cache != 0; it = it->next_cache) {
+							if (it->next_cache == r) {
+								it->next_cache = r->next_cache;
+								break;
+							}
+						}
+					}
+					a->free_fun(r->region_addr);
+					add_free_descriptor(a, (descriptor_t*)r);
+				}
+				return;
+			}
+		}
+	}
+
+	// otherwise the block was directly allocated : look for it in regions.
+	ASSERT(a->all_regions != 0);
+
+	if (a->all_regions->region_addr == addr) {
+		a->free_fun(addr);	// found it, free it
+
+		region_t *r = a->all_regions;
+		a->all_regions = r->next_region;
+		add_free_descriptor(a, (descriptor_t*)r);
+	} else {
+		for (region_t *i = a->all_regions; i->next_region != 0; i = i->next_region) {
+			if (i->next_region->region_addr == addr) {
+				a->free_fun(addr);	// found it, free it
+
+				region_t *r = i->next_region;
+				ASSERT(!r->contains_descriptors);
+				i->next_region = r->next_region;
+				add_free_descriptor(a, (descriptor_t*)r);
+				return;
+			}
+		}
+		ASSERT(false);
+	}
+}
+
+/* vim: set ts=4 sw=4 tw=0 noet :*/
+
diff --git a/src/common/string.c b/src/common/string.c
new file mode 100644
index 0000000..9dce27b
--- /dev/null
+++ b/src/common/string.c
@@ -0,0 +1,90 @@
+#include <string.h>
+
+
+size_t strlen(const char* str) {
+	size_t ret = 0;
+	while (str[ret] != 0)
+		ret++;
+	return ret;
+}
+
+char *strchr(const char *str, char c) {
+	while (*str) {
+		if (*str == c) return (char*)str;
+		str++;
+	}
+	return NULL;
+}
+
+char *strcpy(char *dest, const char *src) {
+	memcpy(dest, src, strlen(src) + 1);
+	return (char*)src;
+}
+
+char *strcat(char *dest, const char *src) {
+	char *dest2 = dest;
+	dest2 += strlen(dest) - 1;
+	while (*src) {
+		*dest2 = *src;
+		src++;
+		dest2++;
+	}
+	*dest2 = 0;
+	return dest;
+}
+
+int strcmp(const char *s1, const char *s2) {
+	while ((*s1) && (*s1 == *s2)) {
+		s1++;
+		s2++;
+	}
+	return (*(unsigned char*)s1 - *(unsigned char*)s2);
+}
+
+void *memcpy(void *vd, const void *vs, size_t count) {
+	uint8_t *dest = (uint8_t*)vd, *src = (uint8_t*)vs;
+	size_t f = count % 4, n = count / 4, i;
+	const uint32_t* s = (uint32_t*)src;
+	uint32_t* d = (uint32_t*)dest;
+	for (i = 0; i < n; i++) {
+		d[i] = s[i];
+	}
+	if (f != 0) {
+		for (i = count - f; i < count; i++) {
+			dest[i] = src[i];
+		}
+	}
+	return vd;
+}
+
+void *memmove(void *vd, const void *vs, size_t count) {
+	uint8_t *dest = (uint8_t*)vd, *src = (uint8_t*)vs;
+
+	if (vd < vs) {
+		for (size_t i = 0; i < count; i++)
+			dest[i] = src[i];
+	} else {
+		for (size_t i = 0; i < count; i++)
+			dest[count - i] = src[count - i];
+	}
+	return vd;
+}
+
+int memcmp(const void *va, const void *vb, size_t count) {
+	uint8_t *a = (uint8_t*)va;
+	uint8_t *b = (uint8_t*)vb;
+	for (size_t i = 0; i < count; i++) {
+		if (a[i] != b[i]) return (int)a[i] - (int)b[i];
+	}
+	return 0;
+}
+
+void *memset(void *dest, int val, size_t count) {
+	uint8_t *dest_c = (uint8_t*)dest;
+	for (size_t i = 0; i < count; i++) {
+		dest_c[i] = val;
+	}
+	return dest;
+}
+
+/* vim: set ts=4 sw=4 tw=0 noet :*/