add task queues

10 files changed, 303 insertions, 54 deletions

diff --git a/include/kpl.h b/include/kpl.h
index 0e17ac6..4f1a74b 100644
--- a/include/kpl.h
+++ b/include/kpl.h
@@ -1,11 +1,14 @@
 
 #pragma once
 
+#define KPL_VERSION "0.0.0"
+
 // All headers in one file for including
 
-#include "kpl/macro.h"
+#include "kpl/queue.h"
 #include "kpl/io.h"
 #include "kpl/process.h"
+#include "kpl/code.h"
 
 typedef enum : uint32_t {
     KPL_CONFIG_FLAG_EVAL    = 1 << 0,
@@ -15,9 +18,10 @@ typedef enum : uint32_t {
 typedef struct {
     uint32_t flags;
     int32_t argc, main_module_arg_index;
-    const char **argv, *module_extension;
+    const char **argv, *module_extension, *version;
     kpl_config_io io;
     kpl_config_thread thread;
+    kpl_config_code code;
 } kpl_config;
 
 void kpl_config_init(kpl_config *config);
@@ -30,4 +34,5 @@ typedef struct _kpl_env {
     kpl_config config;
     kpl_io io;
     kpl_process process;
+    kpl_code code;
 } kpl_env;
diff --git a/include/kpl/code.h b/include/kpl/code.h
new file mode 100644
index 0000000..fb44f86
--- /dev/null
+++ b/include/kpl/code.h
@@ -0,0 +1,25 @@
+
+#pragma once
+
+// Queues and trees for code life cycle
+
+#include "kpl/queue.h"
+
+typedef enum : int8_t {
+    KPL_CONFIG_CODE_QUEUE_POW2_MIN       = 4,
+    KPL_CONFIG_CODE_QUEUE_POW2_DEFAULT   = 6,
+    KPL_CONFIG_CODE_QUEUE_POW2_MAX       = 8,
+} kpl_config_code_queue_pow;
+
+typedef struct {
+    int8_t queue_pow2;
+} kpl_config_code;
+
+// TODO namespace tree
+
+// TODO module tree
+
+typedef struct {
+    kpl_config_code *config_code;
+    kpl_ring_queue code_queue;
+} kpl_code;
diff --git a/include/kpl/io.h b/include/kpl/io.h
index 9a85d1f..514f2d4 100644
--- a/include/kpl/io.h
+++ b/include/kpl/io.h
@@ -5,16 +5,17 @@
 
 #include "kpl/macro.h"
 
-typedef enum : int32_t {
-    KPL_IO_QUEUE_POW_MIN        = 4,
-    KPL_IO_QUEUE_POW_DEFAULT    = 10,
-    KPL_IO_QUEUE_POW_MAX        = 16
+typedef enum : int8_t {
+    KPL_CONFIG_IO_QUEUE_POW2_MIN        = 4,
+    KPL_CONFIG_IO_QUEUE_POW2_DEFAULT    = 10,
+    KPL_CONFIG_IO_QUEUE_POW2_MAX        = 16
 } kpl_io_queue_pow_options;
 
 typedef struct {
-    int32_t queue_pow;
+    int8_t queue_pow2;
 } kpl_config_io;
 
 typedef struct {
-
+    kpl_config_io *config_io;
+    // TODO
 } kpl_io;
diff --git a/include/kpl/process.h b/include/kpl/process.h
index d46fd2f..b47e122 100644
--- a/include/kpl/process.h
+++ b/include/kpl/process.h
@@ -3,14 +3,25 @@
 
 // Kpl threads, allocators, atomic queues and garbage collection
 
-#include "kpl/macro.h"
+#include "kpl/queue.h"
+
+typedef enum : int8_t {
+    KPL_CONFIG_THREAD_COUNT_AFFINITY    = -1,
+    KPL_CONFIG_THREAD_COUNT_MAX         = 127
+} kpl_config_thread_count;
+
+typedef enum : uint8_t {
+    KPL_CONFIG_THREAD_RING_POOL_COUNT                   = 28,
+    KPL_CONFIG_THREAD_RING_POOL_MIN_OBJECT_SIZE_POW2    = 5,
+    KPL_CONFIG_THREAD_RING_POOL_MAX_OBJECT_SIZE_POW2    = 27,
+    KPL_CONFIG_THREAD_RING_POOL_MIN_RING_SIZE_POW2      = 6,
+    KPL_CONFIG_THREAD_RING_POOL_MAX_RING_SIZE_POW2      = 20
+} kpl_config_thread_ring_pool;
 
 typedef struct {
-    int32_t count;
+    int8_t count, ring_pool_entries_pow2[KPL_CONFIG_THREAD_RING_POOL_COUNT];
 } kpl_config_thread;
 
-typedef struct _kpl_task kpl_task;
-
 typedef struct _kpl_env kpl_env;
 
 typedef void kpl_task_fn(kpl_task *task, kpl_env *env);
@@ -24,21 +35,16 @@ typedef struct _kpl_task {
 } kpl_task;
 
 typedef struct {
-    kpl_task *_Atomic head, *_Atomic tail;
-    struct {
-       kpl_task *_Atomic next;
-    } dummy;
-} kpl_task_queue;
-
-typedef struct {
     kpl_task_queue task_queue;
     _Atomic ssize_t priority;
     // TODO
-    sem_t spin_counter;
-    pthread_t thread;
+    sem_t sem;
+    pthread_t pthread;
 } kpl_thread;
 
 typedef struct {
+    kpl_config_thread *config_thread;
     _Atomic ssize_t total_priority;
     kpl_thread *threads;
+    kpl_ring_queue memory_pool[KPL_CONFIG_THREAD_RING_POOL_COUNT];
 } kpl_process;
diff --git a/include/kpl/queue.h b/include/kpl/queue.h
new file mode 100644
index 0000000..3d77e13
--- /dev/null
+++ b/include/kpl/queue.h
@@ -0,0 +1,40 @@
+
+#pragma once
+
+// KPL atomic queues
+
+#include "kpl/macro.h"
+
+typedef struct _kpl_task kpl_task;
+
+typedef struct {
+    kpl_task *_Atomic head, *tail;
+    struct {
+       kpl_task *_Atomic next;
+    } dummy;
+} kpl_task_queue;
+
+void kpl_task_queue_init(kpl_task_queue *task_queue);
+
+void kpl_task_queue_add(kpl_task_queue *task_queue, kpl_task *task);
+
+kpl_task *kpl_task_queue_next(kpl_task_queue *task_queue);
+
+typedef struct {
+    _Atomic ssize_t index;
+    void *data;
+} kpl_ring_queue_item;
+
+typedef struct {
+    size_t items_mask;
+    _Atomic ssize_t head_index, tail_index;
+    kpl_ring_queue_item *items;
+} kpl_ring_queue;
+
+void kpl_ring_queue_init(kpl_ring_queue *ring_queue, int8_t size_pow);
+
+void kpl_ring_queue_free(kpl_ring_queue *ring_queue);
+
+bool kpl_ring_queue_add(kpl_ring_queue *ring_queue, void *data);
+
+void *kpl_ring_queue_next(kpl_ring_queue *ring_queue);
diff --git a/include/kpl/system.h b/include/kpl/system.h
index 201c1b6..3f897ab 100644
--- a/include/kpl/system.h
+++ b/include/kpl/system.h
@@ -8,5 +8,6 @@
 #include <stdint.h>
 #include <stdbool.h>
 #include <string.h>
+#include <ctype.h>
 #include <pthread.h>
 #include <semaphore.h>
diff --git a/source/config.c b/source/config.c
index 461197d..31de7d4 100644
--- a/source/config.c
+++ b/source/config.c
@@ -1,15 +1,25 @@
 
 #include "kpl.h"
 
-static kpl_config default_config = {
-    .argc = -1, .main_module_arg_index = -1,
+static const kpl_config default_config = {
+    .argc = -1, .main_module_arg_index = -1, .version = KPL_VERSION,
     .argv = NULL, .module_extension = ".kpl",
     .flags = 0,
     .io = {
-        .queue_pow = KPL_IO_QUEUE_POW_DEFAULT
+        .queue_pow2 = KPL_CONFIG_IO_QUEUE_POW2_DEFAULT
     },
     .thread = {
-        .count = -1
+        .count = KPL_CONFIG_THREAD_COUNT_AFFINITY,
+        .ring_pool_entries_pow2 = {
+            [0] = 0, [1] = 0, [2] = 0, [3] = 0, [4] = 0, [5] = 13,
+            [6] = 13, [7] = 13, [8] = 13, [9] = 13, [10] = 13, [11] = 13,
+            [12] = 13, [13] = 13, [14] = 13, [15] = 13, [16] = 13, [17] = 13,
+            [18] = 13, [19] = 13, [20] = 13, [21] = 13, [22] = 13, [23] = 13,
+            [24] = 13, [25] = 13, [26] = 13, [27] = 13
+        }
+    },
+    .code = {
+        .queue_pow2 = KPL_CONFIG_CODE_QUEUE_POW2_DEFAULT
     }
 };
 
@@ -30,6 +40,46 @@ static int32_t kpl_arg_match_module_extension(const char *match_str, const int32
     return KPL_EXIT_CODE_SUCCESS;
 }
 
+static int32_t kpl_arg_match_io_queue_pow2(const char *match_str, const int32_t match_str_index, kpl_config *config) {
+    int32_t queue_pow2 = atoi(match_str + match_str_index);
+    if (queue_pow2 < KPL_CONFIG_IO_QUEUE_POW2_MIN || queue_pow2 > KPL_CONFIG_IO_QUEUE_POW2_MAX)
+        return KPL_EXIT_CODE_ERROR;
+    config->io.queue_pow2 = queue_pow2;
+    return KPL_EXIT_CODE_SUCCESS;
+}
+
+static int32_t kpl_arg_match_thread_count(const char *match_str, const int32_t match_str_index, kpl_config *config) {
+    int32_t thread_count = atoi(match_str + match_str_index);
+    if (thread_count <= 0 || thread_count > KPL_CONFIG_THREAD_COUNT_MAX)
+        return KPL_EXIT_CODE_ERROR;
+    config->thread.count = thread_count;
+    return KPL_EXIT_CODE_SUCCESS;
+}
+
+static int32_t kpl_arg_match_memory_pool_pow2(const char *match_str, const int32_t match_str_index, kpl_config *config) {
+    char *endptr;
+    int32_t object_size_pow2 = strtol(match_str + match_str_index, &endptr, 10);
+    if (object_size_pow2 < KPL_CONFIG_THREAD_RING_POOL_MIN_OBJECT_SIZE_POW2 ||
+        object_size_pow2 > KPL_CONFIG_THREAD_RING_POOL_MAX_OBJECT_SIZE_POW2)
+        return KPL_EXIT_CODE_ERROR;
+    while (*endptr && !isdigit(*endptr))
+        endptr++;
+    int32_t entry_size_pow2 = strtol(endptr, NULL, 10);
+    if (entry_size_pow2 < KPL_CONFIG_THREAD_RING_POOL_MIN_RING_SIZE_POW2 ||
+        entry_size_pow2 > KPL_CONFIG_THREAD_RING_POOL_MAX_RING_SIZE_POW2)
+        return KPL_EXIT_CODE_ERROR;
+    config->thread.ring_pool_entries_pow2[object_size_pow2] = entry_size_pow2;
+    return KPL_EXIT_CODE_SUCCESS;
+}
+
+static int32_t kpl_arg_match_code_queue_pow2(const char *match_str, const int32_t match_str_index, kpl_config *config) {
+    int32_t queue_pow2 = atoi(match_str + match_str_index);
+    if (queue_pow2 < KPL_CONFIG_CODE_QUEUE_POW2_MIN || queue_pow2 > KPL_CONFIG_CODE_QUEUE_POW2_MAX)
+        return KPL_EXIT_CODE_ERROR;
+    config->code.queue_pow2 = queue_pow2;
+    return KPL_EXIT_CODE_SUCCESS;
+}
+
 static int32_t kpl_arg_match_eval(const char *match_str, const int32_t match_str_index, kpl_config *config) {
     (void) match_str;
     (void) match_str_index;
@@ -44,20 +94,14 @@ static int32_t kpl_arg_match_repl(const char *match_str, const int32_t match_str
     return KPL_EXIT_CODE_SUCCESS;
 }
 
-static int32_t kpl_arg_match_io_queue_pow(const char *match_str, const int32_t match_str_index, kpl_config *config) {
-    int32_t queue_pow = atoi(match_str + match_str_index);
-    if (queue_pow < KPL_IO_QUEUE_POW_MIN || queue_pow > KPL_IO_QUEUE_POW_MAX)
-        return KPL_EXIT_CODE_ERROR;
-    config->io.queue_pow = queue_pow;
-    return KPL_EXIT_CODE_SUCCESS;
-}
-
-static int32_t kpl_arg_match_thread_count(const char *match_str, const int32_t match_str_index, kpl_config *config) {
-    int32_t thread_count = atoi(match_str + match_str_index);
-    if (!thread_count)
-        return KPL_EXIT_CODE_ERROR;
-    config->thread.count = thread_count;
-    return KPL_EXIT_CODE_SUCCESS;
+static int32_t kpl_arg_match_version(const char *match_str, const int32_t match_str_index, kpl_config *config) {
+    (void) match_str_index;
+    printf("\nKevin's Programming Language ("  KPL_COLOR(LIGHT_BLUE) "KPL" KPL_COLOR(RESET)
+        "), Version: " KPL_COLOR(LIGHT_GREEN) "%s\n" KPL_COLOR(RESET),
+        config->version);
+    if (match_str)
+        putchar('\n');
+    return KPL_EXIT_CODE_HELP;
 }
 
 static int32_t kpl_arg_match_help(const char *match_str, const int32_t match_str_index, kpl_config *config);
@@ -65,36 +109,56 @@ static int32_t kpl_arg_match_help(const char *match_str, const int32_t match_str
 static kpl_arg_match arg_match_array[] = {
     {
         .match_str = "--module-extension=",
-        .help_message="[WORD], Change the module extension for imports (default .kpl)",
+        .help_message="[WORD]; Change the module extension for imports (default .kpl)",
         .arg_match_fn = kpl_arg_match_module_extension
     },
     {
-        .match_str = "--eval",
-        .help_message = " [STRING...], Evaluate next argument(s) as modules",
-        .arg_match_fn = kpl_arg_match_eval
-    },
-    {
-        .match_str = "--io-queue-pow=",
-        .help_message = "[NUMBER], Power of two for calculating the size of the io_uring queue",
-        .arg_match_fn = kpl_arg_match_io_queue_pow
+        .match_str = "--io-queue-pow2=",
+        .help_message = "[NUMBER]; Power of 2 for calculating the size of the io_uring queue",
+        .arg_match_fn = kpl_arg_match_io_queue_pow2
     },
     {
         .match_str = "--thread-count=",
-        .help_message = "[NUMBER], Number of running threads, minimum is 1",
+        .help_message = "[NUMBER]; Number of running threads, minimum is 1",
         .arg_match_fn = kpl_arg_match_thread_count
     },
     {
+        .match_str = "--memory-pool-pow2=",
+        .help_message = "[NUMBER1],[NUMBER2]; Set the memory pool [NUMBER1] to have 2 ** [NUMBER2] entires",
+        .arg_match_fn = kpl_arg_match_memory_pool_pow2
+    },
+    {
+        .match_str = "--code-queue-pow2=",
+        .help_message = "[NUMBER]; Power of 2 for calculating the size of the code queue",
+        .arg_match_fn = kpl_arg_match_code_queue_pow2
+    },
+    {
+        .match_str = "--eval",
+        .help_message = " [STRING...]; Evaluate next argument(s) as modules",
+        .arg_match_fn = kpl_arg_match_eval
+    },
+    {
         .match_str = "--repl",
-        .help_message = ", Start (R)ead, (E)valuate, (P)rint, (L)oop",
+        .help_message = "; Start (R)ead, (E)valuate, (P)rint, (L)oop",
         .arg_match_fn = kpl_arg_match_repl
     },
-    { .match_str = "--help", .help_message = ", Show help", .arg_match_fn = kpl_arg_match_help },
+    {
+        .match_str = "--version",
+        .help_message = "; Show version",
+        .arg_match_fn = kpl_arg_match_version
+    },
+    {
+        .match_str = "--help",
+        .help_message = "; Show help",
+        .arg_match_fn = kpl_arg_match_help
+    },
     { .match_str = NULL, .help_message = NULL, .arg_match_fn = NULL }
 };
 
 static int32_t kpl_arg_match_help(const char *match_str, const int32_t match_str_index, kpl_config *config) {
     (void) match_str;
     (void) match_str_index;
+    kpl_arg_match_version(NULL, 0, config);
     printf("\nUsage " KPL_COLOR(BOLD) "%s" KPL_COLOR(RESET) KPL_COLOR(WHITE) " [OPTIONS] [MODULE]" KPL_COLOR(RESET)
         KPL_COLOR(BOLD) "%s\n\n" KPL_COLOR(RESET), config->argv[0], config->module_extension);
     printf("Where " KPL_COLOR(WHITE) "[OPTIONS]" KPL_COLOR(RESET) " are:\n");
diff --git a/source/queue.c b/source/queue.c
new file mode 100644
index 0000000..519aa1f
--- /dev/null
+++ b/source/queue.c
@@ -0,0 +1,42 @@
+
+#include "kpl.h"
+
+void kpl_task_queue_init(kpl_task_queue *task_queue) {
+    __atomic_store_n(&task_queue->dummy.next, NULL, __ATOMIC_RELAXED);
+    __atomic_store_n(&task_queue->head, &task_queue->dummy, __ATOMIC_RELAXED);
+    task_queue->tail = (kpl_task*) &task_queue->dummy;
+}
+
+void kpl_task_queue_add(kpl_task_queue *task_queue, kpl_task *task) {
+    __atomic_store_n(&task->next, NULL, __ATOMIC_RELAXED);
+    kpl_task *head = __atomic_exchange_n(&task_queue->head, task, __ATOMIC_SEQ_CST);
+    __atomic_store_n(&head->next, task, __ATOMIC_RELEASE);
+}
+
+kpl_task *kpl_task_queue_next(kpl_task_queue *task_queue) {
+    kpl_task *task = NULL;
+    for (;;) {
+        kpl_task *tail = task_queue->tail, *next = __atomic_load_n(&tail->next, __ATOMIC_ACQUIRE);
+        if (tail == (kpl_task*) &task_queue->dummy) {
+            if (!next)
+                break;
+            tail = task_queue->tail = next;
+            next = __atomic_load_n(&tail->next, __ATOMIC_ACQUIRE);
+        }
+        if (!next) {
+            kpl_task *head = __atomic_load_n(&task_queue->head, __ATOMIC_ACQUIRE);
+            if (tail != head)
+                continue;
+            kpl_task_queue_add(task_queue, (kpl_task*) &task_queue->dummy);
+            next = __atomic_load_n(&tail->next, __ATOMIC_ACQUIRE);
+        }
+        if (next) {
+            task_queue->tail = next;
+            task = tail;
+            break;
+        }
+    }
+    if (task)
+        __atomic_store_n(&task->next, NULL, __ATOMIC_RELAXED);
+    return task;
+}
diff --git a/test/config.c b/test/config.c
index a8fd1ad..a871243 100644
--- a/test/config.c
+++ b/test/config.c
@@ -20,14 +20,14 @@ KPL_TEST(config_change_module_extension) {
     KPL_ASSERT(strcmp(config.module_extension, ".l") == 0, "Invalid new module extension");
 }
 
-KPL_TEST(config_io_queue_pow) {
+KPL_TEST(config_io_queue_pow2) {
     kpl_config config;
     const int32_t argc = 3;
-    const char *argv[] = { "./kpl", "--io-queue-pow=14", "./file.kpl" };
+    const char *argv[] = { "./kpl", "--io-queue-pow2=14", "./file.kpl" };
     kpl_config_init(&config);
     int32_t code = kpl_config_parse_args(&config, argc, argv);
     KPL_ASSERT(code == KPL_EXIT_CODE_SUCCESS, "Invalid exit code");
-    KPL_ASSERT(config.io.queue_pow == 14, "Invalid io queue power of two");
+    KPL_ASSERT(config.io.queue_pow2 == 14, "Invalid io queue power of two");
 }
 
 KPL_TEST(config_thread_count) {
@@ -39,3 +39,13 @@ KPL_TEST(config_thread_count) {
     KPL_ASSERT(code == KPL_EXIT_CODE_SUCCESS, "Invalid exit code");
     KPL_ASSERT(config.thread.count == 1, "Invalid thread count");
 }
+
+KPL_TEST(config_memory_pool_pow2) {
+    kpl_config config;
+    const int32_t argc = 3;
+    const char *argv[] = { "./kpl", "--memory-pool-pow2=6,7", "./file.kpl" };
+    kpl_config_init(&config);
+    int32_t code = kpl_config_parse_args(&config, argc, argv);
+    KPL_ASSERT(code == KPL_EXIT_CODE_SUCCESS, "Invalid exit code");
+    KPL_ASSERT(config.thread.ring_pool_entries_pow2[6] == 7, "Invalid entries pow2");
+}
diff --git a/test/queue.c b/test/queue.c
new file mode 100644
index 0000000..9886225
--- /dev/null
+++ b/test/queue.c
@@ -0,0 +1,55 @@
+
+#include "kpl_test.h"
+
+typedef struct {
+    _Atomic int32_t increments;
+    bool pop_error;
+    kpl_task_queue task_queue;
+    pthread_t pthread;
+} kpl_task_queue_thread_test;
+
+#define TASK_QUEUE_THREAD_COUNT 3
+
+#define TASK_QUEUE_PER_THREAD_INCREMENTS 10
+
+static const int32_t kpl_task_queue_total_increments = TASK_QUEUE_THREAD_COUNT * TASK_QUEUE_PER_THREAD_INCREMENTS;
+
+static kpl_task_queue_thread_test task_queue_threads[TASK_QUEUE_THREAD_COUNT] = {};
+
+static void *queue_task_queue_thread_fn(void *arg) {
+    const int32_t thread_id = (int32_t) (intptr_t) arg;
+    for (int32_t round = 0; round < TASK_QUEUE_PER_THREAD_INCREMENTS; round++) {
+        for (int32_t id = 0; id < TASK_QUEUE_THREAD_COUNT; id++) {
+            kpl_task *task = calloc(1, sizeof(kpl_task));
+            kpl_task_queue_add(&task_queue_threads[id].task_queue, task);
+        }
+        kpl_task *task = kpl_task_queue_next(&task_queue_threads[thread_id].task_queue);
+        if (task) {
+            task_queue_threads[thread_id].increments++;
+            free(task);
+        } else {
+            task_queue_threads[thread_id].pop_error = true;
+            break;
+        }
+    }
+    return NULL;
+}
+
+KPL_TEST(queue_task_queue_threads) {
+    for (int32_t id = 0; id < TASK_QUEUE_THREAD_COUNT; id++)
+        kpl_task_queue_init(&task_queue_threads[id].task_queue);
+    for (int32_t id = 0; id < TASK_QUEUE_THREAD_COUNT; id++)
+        pthread_create(&task_queue_threads[id].pthread, NULL, queue_task_queue_thread_fn, (void*) (intptr_t) id);
+    for (int32_t id = 0; id < TASK_QUEUE_THREAD_COUNT; id++)
+        pthread_join(task_queue_threads[id].pthread, NULL);
+    for (int32_t id = 0; id < TASK_QUEUE_THREAD_COUNT; id++) {
+        kpl_task *task = NULL;
+        while ((task = kpl_task_queue_next(&task_queue_threads[id].task_queue))) {
+            task_queue_threads[id].increments++;
+            free(task);
+        }
+        KPL_ASSERT(!task_queue_threads[id].pop_error, "Task queue pop failed");
+        KPL_ASSERT(task_queue_threads[id].increments == kpl_task_queue_total_increments,
+                "Invalid number of increments");
+    }
+}