Move stuff around, again

9 files changed, 245 insertions, 0 deletions

diff --git a/src/common/include/kogata/algo.h b/src/common/include/kogata/algo.h
new file mode 100644
index 0000000..80af052
--- /dev/null
+++ b/src/common/include/kogata/algo.h
@@ -0,0 +1,37 @@
+#pragma once
+
+#include <stdint.h>
+#include <stddef.h>
+#include <stdbool.h>
+
+#define MIN(a, b)   ((a)<(b)?(a):(b))
+#define MAX(a, b)   ((a)>(b)?(a):(b))
+#define ABS(a)		((a)<0?-(a):(a))
+
+// ============================================================= //
+// FUNCTION TYPES FOR KEY-VALUE DATA STRUCTURES (HASHTBL, BTREE) //
+
+typedef uint32_t hash_t;
+typedef hash_t (*hash_fun_t)(const void*);
+
+typedef int (*key_cmp_fun_t)(const void*, const void*);
+typedef bool (*key_eq_fun_t)(const void*, const void*);
+
+typedef void (*kv_iter_fun_t)(void* key, void* value);
+
+// void* is considered as an unsigned integer (and not a pointer)
+hash_t id_hash_fun(const void* v);
+bool id_key_eq_fun(const void* a, const void* b);
+int id_key_cmp_fun(const void* a, const void* b);
+
+// void* considered as char*
+hash_t str_hash_fun(const void* v);
+bool str_key_eq_fun(const void* a, const void* b);
+int str_key_cmp_fun(const void* a, const void* b);
+
+// Freeing functions (they are of type kv_iter_fun_t)
+void free_key(void* key, void* val);
+void free_val(void* key, void* val);
+void free_key_val(void* key, void* val);
+
+/* vim: set ts=4 sw=4 tw=0 noet :*/
diff --git a/src/common/include/kogata/btree.h b/src/common/include/kogata/btree.h
new file mode 100644
index 0000000..e796a2d
--- /dev/null
+++ b/src/common/include/kogata/btree.h
@@ -0,0 +1,33 @@
+#pragma once
+
+#include <kogata/algo.h>
+
+// A btree may contain several bindings for the same key (in that case they are not ordered)
+//	- btree_find returns any item with matching key, or null if none exists
+//	- btree_lower returns any item with matching key, or if none returns last item with smaller key
+//	- btree_upper returns any item with matching key, or if none returns first item with bigger key
+//	- btree_remove removes *all bindings* with matching key
+//	- btree_remove_v removes bindings with matching *key and value*
+//	- btree_iter_on calls iterator function on all bindings with matching key
+
+// Memory management is same as for hashtbl (a kv_iter_fun_t is called when an item is released)
+
+struct btree;
+typedef struct btree btree_t;
+
+btree_t* create_btree(key_cmp_fun_t cf, kv_iter_fun_t on_release);
+void delete_btree(btree_t *t);
+
+bool btree_add(btree_t *t, void* key, void* val);
+void btree_remove(btree_t *t, const void* key);
+void btree_remove_v(btree_t *t, const void* key, const void* value);
+
+void* btree_find(btree_t *i, const void* key);
+void* btree_lower(btree_t *i, const void* key, void** actual_key);
+void* btree_upper(btree_t *i, const void* key, void** actual_key);
+void btree_iter(btree_t *i, kv_iter_fun_t f);
+void btree_iter_on(btree_t *i, const void* key, kv_iter_fun_t f);
+
+size_t btree_count(btree_t *i);
+
+/* vim: set ts=4 sw=4 tw=0 noet :*/
diff --git a/src/common/include/kogata/debug.h b/src/common/include/kogata/debug.h
new file mode 100644
index 0000000..2db5a80
--- /dev/null
+++ b/src/common/include/kogata/debug.h
@@ -0,0 +1,18 @@
+#pragma once
+
+#include <stddef.h>
+#include <stdint.h>
+
+void sys_panic(const char* message, const char* file, int line)
+__attribute__((__noreturn__));
+
+void sys_panic_assert(const char* assertion, const char* file, int line)
+__attribute__((__noreturn__));
+
+#define PANIC(s) sys_panic(s, __FILE__, __LINE__);
+#define ASSERT(s) { if (!(s)) sys_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/kogata/hashtbl.h b/src/common/include/kogata/hashtbl.h
new file mode 100644
index 0000000..e8f327c
--- /dev/null
+++ b/src/common/include/kogata/hashtbl.h
@@ -0,0 +1,35 @@
+#pragma once
+
+#include <kogata/algo.h>
+
+// Simple hashtable structure (key -> void*)
+// Supports adding, seeking, removing, iterating
+// When adding a binding to the table, the previous binding for same key (if exists) is removed
+
+// The hashtbl is allocated with malloc/free
+// The keys/values are not copied by the hastbl, but when a key/value pair is removed from the
+// table some operations may be required (freeing memory), so a kv_iter_fun_t is passed when the
+// table is created which will be called whenever a k/v is released (on hashtbl_remove and delete_hashtbl)
+
+// A hashtbl may have only one binding for a given key (on add, previous binding is removed if necessary)
+
+struct hashtbl;
+typedef struct hashtbl hashtbl_t;
+
+hashtbl_t* create_hashtbl(key_eq_fun_t ef, hash_fun_t hf, kv_iter_fun_t on_release);
+void delete_hashtbl(hashtbl_t* ht);
+
+bool hashtbl_add(hashtbl_t* ht, void* key, void* v);	// true = ok, false on error (OOM for instance)
+void hashtbl_remove(hashtbl_t* ht, const void* key);
+
+void* hashtbl_find(hashtbl_t* ht, const void* key);		// null when not found
+void hashtbl_iter(hashtbl_t* ht, kv_iter_fun_t f);
+
+// hashtbl_change is particular :
+// - it does NOT call malloc and uses the existing hashtbl cell
+// - it does NOT call the on_release fun on the previous element
+bool hashtbl_change(hashtbl_t*  ht, void* key, void* v);
+
+size_t hashtbl_count(hashtbl_t* ht);
+
+/* vim: set ts=4 sw=4 tw=0 noet :*/
diff --git a/src/common/include/kogata/malloc.h b/src/common/include/kogata/malloc.h
new file mode 100644
index 0000000..e55c25e
--- /dev/null
+++ b/src/common/include/kogata/malloc.h
@@ -0,0 +1,13 @@
+#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);
+void* calloc(size_t nmemb, size_t sz);
+void* realloc(void* ptr, size_t sz);
+
+/* vim: set ts=4 sw=4 tw=0 noet :*/
diff --git a/src/common/include/kogata/mutex.h b/src/common/include/kogata/mutex.h
new file mode 100644
index 0000000..88c077e
--- /dev/null
+++ b/src/common/include/kogata/mutex.h
@@ -0,0 +1,22 @@
+#pragma once
+
+#include <stdint.h>
+#include <stdbool.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
+bool mutex_try_lock(mutex_t* mutex);	//lock mutex only if free, returns true when locked, false when 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/kogata/printf.h b/src/common/include/kogata/printf.h
new file mode 100644
index 0000000..b4e1c1b
--- /dev/null
+++ b/src/common/include/kogata/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/kogata/region_alloc.h b/src/common/include/kogata/region_alloc.h
new file mode 100644
index 0000000..d314bd5
--- /dev/null
+++ b/src/common/include/kogata/region_alloc.h
@@ -0,0 +1,32 @@
+#pragma once
+
+// Virtual memory region allocator
+
+// This is entirely thread-safe
+
+#include <stdint.h>
+#include <stddef.h>
+#include <stdbool.h>
+
+struct region_info;
+
+typedef bool (*map_page_fun_t)(void* addr);	// map a single page (used by region allocator)
+
+typedef struct region_info {
+	void* addr;
+	size_t size;
+	char* type;
+} region_info_t;
+
+// rsvd_end : when used for kernel memory region management, a reserved region
+// exists between begin (=K_HIGHHALF_ADDR) and the end of kernel static data
+// for user processes, use rsvd_end = begin (no reserved region)
+void region_allocator_init(void* begin, void* rsvd_end, void* end, map_page_fun_t map);
+
+void* region_alloc(size_t size, char* type);	// returns 0 on error
+region_info_t *find_region(void* addr);
+void region_free(void* addr);
+
+void dbg_print_region_info();
+
+/* vim: set ts=4 sw=4 tw=0 noet :*/
diff --git a/src/common/include/kogata/slab_alloc.h b/src/common/include/kogata/slab_alloc.h
new file mode 100644
index 0000000..1191057
--- /dev/null
+++ b/src/common/include/kogata/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 <kogata/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 :*/