diff options
| -rw-r--r-- | Makefile | 8 | ||||
| -rw-r--r-- | README | 12 | ||||
| -rw-r--r-- | include/README | 8 | ||||
| -rw-r--r-- | include/kpl.h | 42 | ||||
| -rw-r--r-- | include/kpl/base.h | 35 | ||||
| -rw-r--r-- | include/kpl/env.h | 93 | ||||
| -rw-r--r-- | include/kpl/memory.h | 63 | ||||
| -rw-r--r-- | include/kpl/object.h | 33 | ||||
| -rw-r--r-- | include/kpl/runtime.h | 52 | ||||
| -rw-r--r-- | source/README | 2 | ||||
| -rw-r--r-- | source/env.c | 6 | ||||
| -rw-r--r-- | source/memory.c | 112 | ||||
| -rw-r--r-- | source/object.c | 34 | ||||
| -rw-r--r-- | test/memory.c | 19 | ||||
| -rw-r--r-- | test/test.c | 4 |
15 files changed, 425 insertions, 98 deletions
@@ -1,5 +1,5 @@ -.PHONY: kpl_test_memory kpl_test_thread clean rsync_list +.PHONY: kpl_valgrind kpl_test_valgrind kpl_test_memory kpl_test_thread clean rsync_list MAKEFLAGS := -j$(shell nproc) @@ -23,9 +23,15 @@ kpl: FLAGS += -DKPL_MAIN kpl: $(SOURCE_OBJECTS) $(CCOBJ) +kpl_valgrind: FLAGS += -DKPL_VALGRIND +kpl_valgrind: kpl + kpl_test: $(SOURCE_OBJECTS) $(TEST_OBJECTS) $(CCOBJ) +kpl_test_valgrind: FLAGS += -DKPL_VALGRIND +kpl_test_valgrind: kpl_test + kpl_test_memory: FFLAGS += -fsanitize=address,leak,undefined kpl_test_memory: kpl_test @@ -37,3 +37,15 @@ Cross Architecture Testing: See TESTING --- + +Valgrind + +make kpl_valgrind # Build KPL with valgrind support for KPL's custom allocator +make kpl_test_valgrind # Build tests with valgrind support for KPL's custom allocator + +--- + +Sanitizers + +make kpl_test_memory # Build tests with memory,leak and undefined sanitizers +make kpl_test_thread # Build tests with thread sanitizer diff --git a/include/README b/include/README index 6800f87..4147aed 100644 --- a/include/README +++ b/include/README @@ -10,3 +10,11 @@ kpl.h # For the main kpl application kpl_test.h # For Testing --- + +Compiler Flags + +KPL_COLOR_OFF # Turn off internal pretty printing, does not effect source file pretty printing + +KPL_VALGRIND # Add valgrind memory checking to the custom allocators + +--- diff --git a/include/kpl.h b/include/kpl.h index 913edb7..1d53bef 100644 --- a/include/kpl.h +++ b/include/kpl.h @@ -4,6 +4,44 @@ #pragma once -#include "kpl/runtime.h" - #define KPL_VERSION "0.0.0" + +// System includes +#include <stdlib.h> +#include <stdio.h> +#include <stdint.h> +#include <stdbool.h> +#include <stddef.h> +#include <string.h> +#include <ctype.h> +#include <limits.h> +#include <pthread.h> +#include <semaphore.h> +#include <fcntl.h> +#include <unistd.h> +#include <sys/stat.h> +#include <sys/ioctl.h> +#include <sys/mman.h> +#include <sys/uio.h> +#include <sys/param.h> +#include <linux/fs.h> +#include <linux/io_uring.h> +#ifdef KPL_VALGRIND +#include <valgrind/valgrind.h> +#include <valgrind/memcheck.h> +#endif + +// KPL forward declarations +typedef struct _kpl_task kpl_task; + +typedef struct _kpl_thread kpl_thread; + +typedef struct _kpl_env kpl_env; + +// KPL includes +#include "kpl/color.h" +#include "kpl/class.h" +#include "kpl/object.h" +#include "kpl/tree.h" +#include "kpl/memory.h" +#include "kpl/env.h" diff --git a/include/kpl/base.h b/include/kpl/base.h deleted file mode 100644 index 9420a44..0000000 --- a/include/kpl/base.h +++ /dev/null @@ -1,35 +0,0 @@ -/* - * The header for headers included in kpl.h - */ - -#pragma once - -// System includes -#include <stdlib.h> -#include <stdio.h> -#include <stdint.h> -#include <stdbool.h> -#include <string.h> -#include <ctype.h> -#include <limits.h> -#include <pthread.h> -#include <semaphore.h> -#include <fcntl.h> -#include <unistd.h> -#include <sys/stat.h> -#include <sys/ioctl.h> -#include <sys/mman.h> -#include <sys/uio.h> -#include <sys/param.h> -#include <linux/fs.h> -#include <linux/io_uring.h> -// KPL includes -#include "color.h" -#include "class.h" -#include "object.h" -#include "tree.h" - -typedef enum : int32_t { - KPL_EXIT_CODE_SUCCESS = 0, - KPL_EXIT_CODE_ERROR = 1 -} kpl_exit_code; diff --git a/include/kpl/env.h b/include/kpl/env.h new file mode 100644 index 0000000..19d9536 --- /dev/null +++ b/include/kpl/env.h @@ -0,0 +1,93 @@ +/* + * KPL environment objects + */ + +#pragma once + +typedef enum : int32_t { + KPL_THREAD_DETERIMINE_COUNT = -1, + KPL_THREAD_MAIN_ID = 0 +} kpl_thread_enum; + +typedef struct _kpl_thread { + int32_t thread_id; // self id + kpl_memory_allocator memory_allocator; + // TODO io_uring + // TODO jit allocator + _Atomic ssize_t priority; // running + the total number of tasks in threads queue, lower is higher priority + kpl_object_queue task_queue; + pthread_t pthread; // not used for main thread + sem_t sem; // wait when no task queue and io queue is empty +} kpl_thread; + +/* + * All allocations must extend the KPL_OBJECT_HEADER + * All objects are allocated through this + */ +inline void *kpl_thread_object_allocate(kpl_thread *thread, int32_t size) { + return kpl_memory_allocator_allocate(&thread->memory_allocator, size, thread->thread_id); +} + +/* + * Life cycle: + * kpl_env env = {}; + * kpl_env_config &env, argc, argv + * kpl_env_init &env + * add to the namespace tree + * add a file load task, string evaluate task or REPL task to main thread task queue + * kpl_env_run &env + * kpl_env_free &env + */ +typedef struct _kpl_env { + int32_t thread_count; // -1 updates this value to max possible, 0 invalid, >= 1 for specific number + _Atomic ssize_t total_priority; // the sum of the threads priority fields, application stops on zero + kpl_thread *threads; // 0 is main thread, >= 1 are spawned pthreads + kpl_tree *namespace_tree, *module_tree; // *namespace_tree lookups are thread safe, *module_tree needs mutex + pthread_mutex_t module_tree_mutex; +} kpl_env; // kpl state, no globals + +/* + * All objects are retuned by this + */ +inline void kpl_env_object_return(kpl_env *env, void *object) { + kpl_memory_allocator_return(&env->threads[((kpl_object*) object)->thread_id].memory_allocator, object); +} + +/* + * Must match the type of c main return + * if code != KPL_EXIT_CODE_SUCCESS then return code + */ +typedef enum : int32_t { + KPL_EXIT_CODE_SUCCESS = 0, + KPL_EXIT_CODE_ERROR = 1, + KPL_EXIT_CODE_HELP = 2 +} kpl_exit_code; + +/* + * Set up initial values before initialization + * For defaults and/or directly setting without arguments, pass 0 to argc then fields can be updated directly + */ +kpl_exit_code kpl_env_config(kpl_env *env, int32_t argc, char *argv[]); + +/* + * Initialize + * env kpl_env_config must be called before this + */ +kpl_exit_code kpl_env_init(kpl_env *env); + +/* + * Can be run multiple times as long as new tasks are added after each run + */ +kpl_exit_code kpl_env_run(kpl_env *env); + +/* + * Stops KPL, can be called on any task in KPL + * Does not return just signals to all threads to stop, the return status will be from kpl_env_run + * Start can be called again + */ +void kpl_env_stop(kpl_env *env); + +/* + * Clean up + */ +void kpl_env_free(kpl_env *env); diff --git a/include/kpl/memory.h b/include/kpl/memory.h new file mode 100644 index 0000000..5eb6d85 --- /dev/null +++ b/include/kpl/memory.h @@ -0,0 +1,63 @@ +/* + * KPL memory allocator + */ + +typedef enum : int32_t { + KPL_MEMORY_ALLOCATOR_MIN_SIZE_POW2 = 5, + KPL_MEMORY_ALLOCATOR_MIN_ROUND_SIZE_POW2 = KPL_MEMORY_ALLOCATOR_MIN_SIZE_POW2 - 1, + KPL_MEMORY_ALLOCATOR_MAX_SIZE_POW2 = 22, + KPL_MEMORY_ALLOCATOR_SLAB_COUNT = KPL_MEMORY_ALLOCATOR_MAX_SIZE_POW2 + 1 +} kpl_memory_allocator_enum; + + +/* + * Each slab is a linked list allocated with calloc and free + * *buffer is allocated with mmap + */ +typedef struct _kpl_memory_allocator_slab { + uint32_t buffer_size, buffer_used; + struct _kpl_memory_allocator_slab *slab_next; + uint8_t *buffer; +} kpl_memory_allocator_slab; + +/* + * Each group only allocates for a single power of two + */ +typedef struct { + int32_t slab_size_pow2; + kpl_memory_allocator_slab *slab_head, *slab_tail; + kpl_object_queue object_pool; +} kpl_memory_allocator_slab_group; + +/* + * The allocator allocates object rounded to the next power of two + * We first check if the pool has objects, then bump allocate off the slab *buffer + * Each slab is only responsible for one power of two, all objects in buffer and pool are of the same size + * The memory is allocated from buffer and returned to the pool + * The slabs and buffers are freed and returned to the system at once on allocator free + * The object pools are from each mapped buffer, they do not need to be freed + */ +typedef struct { + kpl_memory_allocator_slab_group slabs[KPL_MEMORY_ALLOCATOR_SLAB_COUNT]; +} kpl_memory_allocator; + +/* + * Called by owner thread + */ +void kpl_memory_allocator_init(kpl_memory_allocator *memory_allocator); + +/* + * Called by owner thread + */ +void kpl_memory_allocator_free(kpl_memory_allocator *memory_allocator); + +/* + * Only call this though kpl_thread_object_allocate + * All allocations must extend the KPL_OBJECT_HEADER + */ +void *kpl_memory_allocator_allocate(kpl_memory_allocator *memory_allocator, int32_t size, int32_t thread_id); + +/* + * Only call this though kpl_env_object_return + */ +void kpl_memory_allocator_return(kpl_memory_allocator *memory_allocator, void *object); diff --git a/include/kpl/object.h b/include/kpl/object.h index 0f54a5e..751088d 100644 --- a/include/kpl/object.h +++ b/include/kpl/object.h @@ -8,22 +8,45 @@ // size in bytes, index on the kpl_threads array #define KPL_OBJECT_HEADER(STRUCT_NAME) \ struct STRUCT_NAME *_Atomic queue_next; \ - int32_t obj_size, thread_id + int32_t object_size, thread_id typedef struct _kpl_object { KPL_OBJECT_HEADER(_kpl_object); -} kpl_object; // all kpl objects allocated by the kpl allocator extend this header +} kpl_object; // all kpl objects allocated by the kpl memory allocator extend this header +/* + * Atomic linked list queue any thread can add, only owner thread can remove + */ typedef struct { kpl_object *_Atomic head, *tail; // head is modified with atomic exchange struct { kpl_object *_Atomic queue_next; } dummy; // head and tail are never null will always point to this -} kpl_object_queue; // atomic linked list queue any thread can add, only owner thread can remove +} kpl_object_queue; -typedef struct _kpl_task kpl_task; +/* + * Only owner thread can call this + */ +inline void kpl_object_queue_init(kpl_object_queue *object_queue) { + __atomic_store_n(&object_queue->dummy.queue_next, NULL, __ATOMIC_RELAXED); + __atomic_store_n(&object_queue->head, &object_queue->dummy, __ATOMIC_RELAXED); + object_queue->tail = (kpl_object*) &object_queue->dummy; +} -typedef struct _kpl_env kpl_env; +/* + * Always succeeds, any thread can call this + */ +inline void kpl_object_queue_enqueue(kpl_object_queue *object_queue, void *object) { + kpl_object *obj = object; + __atomic_store_n(&obj->queue_next, NULL, __ATOMIC_RELAXED); + kpl_object *head = __atomic_exchange_n(&object_queue->head, obj, __ATOMIC_SEQ_CST); + __atomic_store_n(&head->queue_next, obj, __ATOMIC_RELEASE); +} + +/* + * Null for not found, only owner thread can call this + */ +void *kpl_object_queue_dequeue(kpl_object_queue *object_queue); typedef void kpl_task_fn(kpl_task *task, kpl_env *env); diff --git a/include/kpl/runtime.h b/include/kpl/runtime.h deleted file mode 100644 index 2adf402..0000000 --- a/include/kpl/runtime.h +++ /dev/null @@ -1,52 +0,0 @@ -/* - * KPL allocators, io and threading - */ - -#pragma once - -#include "base.h" - -typedef enum : uint8_t { - KPL_MEMORY_ALLOCATOR_MIN_POW2 = 7, - KPL_MEMORY_ALLOCATOR_MAX_POW2 = 30 -} kpl_memory_allocator_enum; - -/* - * All allocations are rounded to the next power of two at lest to a min or error if over max - * Each power of two has a bucket in the memory pool for reuse - */ -typedef struct { -// TODO MEMORY ALLOCATOR -} kpl_memory_allocator; - -typedef enum : uint8_t { - KPL_MEMORY_POOL_COUNT = 31 -} kpl_memory_pool_enum; - -// TODO IO URING - -// TODO JIT ALLOCATOR - -typedef struct { - kpl_memory_allocator allocator; - kpl_object_queue memory_pools[KPL_MEMORY_POOL_COUNT]; // each index represents 2 ** INDEX size in bytes - // TODO io_uring - // TODO jit allocator - _Atomic ssize_t priority; // running + the total number of tasks in threads queue, lower is higher priority - kpl_object_queue task_queue; - pthread_t pthread; // not used for main thread - sem_t sem; // wait when no task queue and io queue is empty -} kpl_thread; - -typedef enum : int32_t { - KPL_THREAD_DETERIMINE_COUNT = -1, - KPL_THREAD_MAIN_ID = 0 -} kpl_thread_enum; - -typedef struct _kpl_env { - int32_t thread_count; // -1 updates this value to max possible, 0 invalid, >= 1 for specific number - _Atomic ssize_t total_priority; // the sum of the threads priority fields, application stops on zero - kpl_thread *thread_array; // 0 is main thread, >= 1 are spawned pthreads - kpl_tree *namespace_tree, *module_tree; // *namespace_tree lookups are thread safe, *module_tree needs mutex - pthread_mutex_t module_tree_mutex; -} kpl_env; // kpl state, no globals diff --git a/source/README b/source/README index 016daa8..e277eab 100644 --- a/source/README +++ b/source/README @@ -4,6 +4,6 @@ Source Files Compiler Flags -KPL_COLOR_OFF # Turn off internal pretty printing, does not effect source file pretty printing +KPL_MAIN # Add the c main function for creating the standalone KPL executable --- diff --git a/source/env.c b/source/env.c new file mode 100644 index 0000000..587918e --- /dev/null +++ b/source/env.c @@ -0,0 +1,6 @@ + +#include "kpl.h" + +inline void *kpl_thread_object_allocate(kpl_thread *thread, int32_t size); + +inline void kpl_env_object_return(kpl_env *env, void *object); diff --git a/source/memory.c b/source/memory.c new file mode 100644 index 0000000..d7618a7 --- /dev/null +++ b/source/memory.c @@ -0,0 +1,112 @@ + +#include "kpl.h" + +void kpl_memory_allocator_init(kpl_memory_allocator *memory_allocator) { + for (int32_t slab_pow2 = KPL_MEMORY_ALLOCATOR_MIN_SIZE_POW2; + slab_pow2 <= KPL_MEMORY_ALLOCATOR_MAX_SIZE_POW2; slab_pow2++) { + kpl_memory_allocator_slab_group *slab_group = &memory_allocator->slabs[slab_pow2]; + slab_group->slab_size_pow2 = slab_pow2; + slab_group->slab_head = slab_group->slab_tail = NULL; + kpl_object_queue_init(&slab_group->object_pool); + } +} + +static void kpl_memory_allocator_slab_free(kpl_memory_allocator_slab_group *slab_group) { + kpl_memory_allocator_slab *slab_head = slab_group->slab_head; + while (slab_head) { + kpl_memory_allocator_slab *slab_tmp = slab_head; + slab_head = slab_head->slab_next; + munmap(slab_tmp->buffer, slab_tmp->buffer_size); + free(slab_tmp); + } +} + +void kpl_memory_allocator_free(kpl_memory_allocator *memory_allocator) { + for (int32_t slab_pow2 = KPL_MEMORY_ALLOCATOR_MIN_SIZE_POW2; + slab_pow2 < KPL_MEMORY_ALLOCATOR_SLAB_COUNT; slab_pow2++) { + kpl_memory_allocator_slab_group *slab_group = &memory_allocator->slabs[slab_pow2]; +#ifdef KPL_VALGRIND + kpl_object *object = NULL; + while ((object = kpl_object_queue_dequeue(&slab_group->object_pool))) + VALGRIND_FREELIKE_BLOCK(object, 0); +#endif + kpl_memory_allocator_slab_free(slab_group); + } +} + +static int32_t kpl_memory_allocator_get_size_pow2(int32_t size) { + return size > 1 ? 32 - __builtin_clz(size - 1) : 0; +} + +static const int32_t pages_per_pow2[] = { + [5] = 5, + [6] = 10, + [7] = 15, + [8] = 20, + [9] = 25, + [10] = 30, + [11] = 35, + [12] = 40, + [13] = 2, + [14] = 4, + [15] = 8, + [16] = 16, + [17] = 32, + [18] = 64, + [19] = 128, + [20] = 256, + [21] = 512, + [22] = 1024, +}; + +static kpl_memory_allocator_slab *kpl_memory_allocator_slab_init(int32_t size_pow2) { + kpl_memory_allocator_slab *slab = calloc(1, sizeof(kpl_memory_allocator_slab)); + slab->buffer_size = getpagesize() * pages_per_pow2[size_pow2]; + slab->buffer = mmap(NULL, slab->buffer_size, PROT_READ | PROT_WRITE, MAP_ANONYMOUS | MAP_SHARED, -1, 0); + return slab; +} + +static void *kpl_memory_allocator_slab_bump(kpl_memory_allocator_slab *slab, int32_t size) { + void *object = slab->buffer + slab->buffer_used; + slab->buffer_used += size; + return object; +} + +static kpl_object *kpl_memory_allocator_slab_allocate(kpl_memory_allocator_slab_group *slab_group, + int32_t thread_id) { + kpl_memory_allocator_slab *slab = slab_group->slab_tail; + int32_t size = 1 << slab_group->slab_size_pow2; + if (!slab || slab->buffer_used + size > slab->buffer_size) { + slab = kpl_memory_allocator_slab_init(slab_group->slab_size_pow2); + if (!slab_group->slab_head) + slab_group->slab_head = slab_group->slab_tail = slab; + else + slab_group->slab_tail = slab_group->slab_tail->slab_next = slab; + } + kpl_object *object = kpl_memory_allocator_slab_bump(slab, size); +#ifdef KPL_VALGRIND + VALGRIND_MALLOCLIKE_BLOCK(object, size, 0, 0); +#endif + __atomic_store_n(&object->queue_next, NULL, __ATOMIC_RELAXED); + object->object_size = size; + object->thread_id = thread_id; + return object; +} + +void *kpl_memory_allocator_allocate(kpl_memory_allocator *memory_allocator, int32_t size, int32_t thread_id) { + if (size < (1 << KPL_MEMORY_ALLOCATOR_MIN_ROUND_SIZE_POW2)) + return NULL; + int32_t size_pow2 = kpl_memory_allocator_get_size_pow2(size); + if (size_pow2 < KPL_MEMORY_ALLOCATOR_MIN_SIZE_POW2) + size_pow2 = KPL_MEMORY_ALLOCATOR_MIN_SIZE_POW2; + kpl_memory_allocator_slab_group *slab_group = &memory_allocator->slabs[size_pow2]; + kpl_object *object = kpl_object_queue_dequeue(&slab_group->object_pool); + if (!object) + object = kpl_memory_allocator_slab_allocate(slab_group, thread_id); + return object; +} + +void kpl_memory_allocator_return(kpl_memory_allocator *memory_allocator, void *object) { + int32_t size_pow2 = kpl_memory_allocator_get_size_pow2(((kpl_object*) object)->object_size); + kpl_object_queue_enqueue(&memory_allocator->slabs[size_pow2].object_pool, object); +} diff --git a/source/object.c b/source/object.c new file mode 100644 index 0000000..d569df0 --- /dev/null +++ b/source/object.c @@ -0,0 +1,34 @@ + +#include "kpl.h" + +extern inline void kpl_object_queue_init(kpl_object_queue *object_queue); + +extern inline void kpl_object_queue_enqueue(kpl_object_queue *object_queue, void *object); + +void *kpl_object_queue_dequeue(kpl_object_queue *object_queue) { + kpl_object *object = NULL; + for (;;) { + kpl_object *tail = object_queue->tail, *queue_next = __atomic_load_n(&tail->queue_next, __ATOMIC_ACQUIRE); + if (tail == (kpl_object*) &object_queue->dummy) { + if (!queue_next) + break; + tail = object_queue->tail = queue_next; + queue_next = __atomic_load_n(&tail->queue_next, __ATOMIC_ACQUIRE); + } + if (!queue_next) { + kpl_object *head = __atomic_load_n(&object_queue->head, __ATOMIC_ACQUIRE); + if (head != tail) + continue; + kpl_object_queue_enqueue(object_queue, (kpl_object*) &object_queue->dummy); + queue_next = __atomic_load_n(&tail->queue_next, __ATOMIC_ACQUIRE); + } + if (queue_next) { + object_queue->tail = queue_next; + object = tail; + break; + } + } + if (object) + __atomic_store_n(&object->queue_next, NULL, __ATOMIC_RELAXED); + return object; +} diff --git a/test/memory.c b/test/memory.c new file mode 100644 index 0000000..05db8a2 --- /dev/null +++ b/test/memory.c @@ -0,0 +1,19 @@ + +#include "kpl_test.h" + +KPL_TEST(allocate) { + kpl_memory_allocator allocator = {}; + kpl_memory_allocator_init(&allocator); + for (int32_t times = 0; times < 700; times++) { + kpl_object *objects[10] = {}; + for (int32_t object = 0; object < 10; object++) { + objects[object] = kpl_memory_allocator_allocate(&allocator, 32, KPL_THREAD_MAIN_ID); + KPL_ASSERT(objects[object]->object_size == 32, "Invalid size for 32 byte object"); + } + for (int32_t object = 0; object < 10; object++) + kpl_memory_allocator_return(&allocator, objects[object]); + } + kpl_memory_allocator_slab_group *slab_group32 = &allocator.slabs[5]; + KPL_ASSERT(slab_group32->slab_head == slab_group32->slab_tail, "Only one slab should have been allocated"); + kpl_memory_allocator_free(&allocator); +} diff --git a/test/test.c b/test/test.c index 02a8730..0dcf302 100644 --- a/test/test.c +++ b/test/test.c @@ -29,7 +29,7 @@ static void kpl_test_report(const kpl_test *_test) { _test->error_line_number, _test->error_message); } -static int32_t kpl_test_report_error(void) { +static kpl_exit_code kpl_test_report_error(void) { if (!error_head) { printf(KPL_COLOR2(BOLD, GREEN) "PASSED\n" KPL_COLOR(RESET)); return KPL_EXIT_CODE_SUCCESS; @@ -55,7 +55,7 @@ static void kpl_test_run_one(kpl_test *_test) { error_tail = error_tail->list_next = _test; } -static int32_t kpl_test_run_all(void) { +static kpl_exit_code kpl_test_run_all(void) { while (test_head) { kpl_test *_test = test_head; test_head = test_head->list_next; |