From f2c51bc81d2aa618b29ddbeaae5ac1c5308821f0 Mon Sep 17 00:00:00 2001 From: Alex Auvolat Date: Mon, 9 Feb 2015 17:39:41 +0100 Subject: Reorganize all. --- src/common/Makefile | 11 ++ src/common/README | 18 +++ src/common/buffer.c | 167 ++++++++++++++++++++++++ src/common/common.lib | Bin 0 -> 41450 bytes src/common/hashtbl.c | 166 +++++++++++++++++++++++ src/common/include/buffer.h | 41 ++++++ src/common/include/debug.h | 14 ++ src/common/include/hashtbl.h | 34 +++++ src/common/include/malloc.h | 11 ++ src/common/include/mutex.h | 21 +++ src/common/include/printf.h | 10 ++ src/common/include/slab_alloc.h | 45 +++++++ src/common/include/string.h | 17 +++ src/common/mutex.c | 27 ++++ src/common/printf.c | 120 +++++++++++++++++ src/common/slab_alloc.c | 283 ++++++++++++++++++++++++++++++++++++++++ src/common/string.c | 90 +++++++++++++ 17 files changed, 1075 insertions(+) create mode 100644 src/common/Makefile create mode 100644 src/common/README create mode 100644 src/common/buffer.c create mode 100644 src/common/common.lib create mode 100644 src/common/hashtbl.c create mode 100644 src/common/include/buffer.h create mode 100644 src/common/include/debug.h create mode 100644 src/common/include/hashtbl.h create mode 100644 src/common/include/malloc.h create mode 100644 src/common/include/mutex.h create mode 100644 src/common/include/printf.h create mode 100644 src/common/include/slab_alloc.h create mode 100644 src/common/include/string.h create mode 100644 src/common/mutex.c create mode 100644 src/common/printf.c create mode 100644 src/common/slab_alloc.c create mode 100644 src/common/string.c (limited to 'src/common') 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 + +#include +#include + +#include + +// 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 Binary files /dev/null and b/src/common/common.lib differ 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 +#include +#include + +#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 +#include +#include + +// 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 +#include + +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 +#include +#include + +// 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 +#include + +// 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 + +#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 +#include +#include + +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 +#include +#include + + +#if defined(__linux__) +//redefine necessary stuff +#include // standard linux assert.h +#define ASSERT assert +#include +#define dbg_printf printf +#else +#include +#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 +#include + +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 + +/* 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 +#include + +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 + +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 + + +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 :*/ -- cgit v1.2.3