From f8217d240d598f39f70047f7a623dd46312542c6 Mon Sep 17 00:00:00 2001 From: 3gg <3gg@shellblade.net> Date: Sat, 4 Dec 2021 16:01:12 -0800 Subject: Initial commit. --- CMakeLists.txt | 9 ++ README.md | 4 +- cstring/CMakeLists.txt | 11 +++ cstring/include/cstring.h | 64 +++++++++++++++ list/CMakeLists.txt | 23 ++++++ list/include/list.h | 21 +++++ list/src/list.c | 14 ++++ list/test/list_test.c | 34 ++++++++ list/test/test.h | 185 ++++++++++++++++++++++++++++++++++++++++++ listpool/CMakeLists.txt | 26 ++++++ listpool/README.md | 14 ++++ listpool/include/listpool.h | 79 ++++++++++++++++++ listpool/src/listpool.c | 78 ++++++++++++++++++ listpool/test/listpool_test.c | 166 +++++++++++++++++++++++++++++++++++++ listpool/test/test.h | 185 ++++++++++++++++++++++++++++++++++++++++++ log/CMakeLists.txt | 9 ++ log/README.md | 1 + log/include/log/log.h | 19 +++++ log/src/log.c | 1 + mempool/CMakeLists.txt | 23 ++++++ mempool/README.md | 20 +++++ mempool/include/mempool.h | 91 +++++++++++++++++++++ mempool/src/mempool.c | 85 +++++++++++++++++++ mempool/test/mempool_test.c | 157 +++++++++++++++++++++++++++++++++++ mempool/test/test.h | 185 ++++++++++++++++++++++++++++++++++++++++++ 25 files changed, 1502 insertions(+), 2 deletions(-) create mode 100644 CMakeLists.txt create mode 100644 cstring/CMakeLists.txt create mode 100644 cstring/include/cstring.h create mode 100644 list/CMakeLists.txt create mode 100644 list/include/list.h create mode 100644 list/src/list.c create mode 100644 list/test/list_test.c create mode 100644 list/test/test.h create mode 100644 listpool/CMakeLists.txt create mode 100644 listpool/README.md create mode 100644 listpool/include/listpool.h create mode 100644 listpool/src/listpool.c create mode 100644 listpool/test/listpool_test.c create mode 100644 listpool/test/test.h create mode 100644 log/CMakeLists.txt create mode 100644 log/README.md create mode 100644 log/include/log/log.h create mode 100644 log/src/log.c create mode 100644 mempool/CMakeLists.txt create mode 100644 mempool/README.md create mode 100644 mempool/include/mempool.h create mode 100644 mempool/src/mempool.c create mode 100644 mempool/test/mempool_test.c create mode 100644 mempool/test/test.h diff --git a/CMakeLists.txt b/CMakeLists.txt new file mode 100644 index 0000000..36df847 --- /dev/null +++ b/CMakeLists.txt @@ -0,0 +1,9 @@ +cmake_minimum_required(VERSION 3.16) + +project(clib) + +add_subdirectory(cstring) +add_subdirectory(list) +add_subdirectory(listpool) +add_subdirectory(log) +add_subdirectory(mempool) diff --git a/README.md b/README.md index 941fc04..4cab9fe 100644 --- a/README.md +++ b/README.md @@ -1,3 +1,3 @@ -# clib +# C Library -A collection of small C libraries. \ No newline at end of file +A collection of small C libraries. diff --git a/cstring/CMakeLists.txt b/cstring/CMakeLists.txt new file mode 100644 index 0000000..67fb366 --- /dev/null +++ b/cstring/CMakeLists.txt @@ -0,0 +1,11 @@ +cmake_minimum_required(VERSION 3.16) + +project(cstring) + +add_library(cstring INTERFACE) + +target_include_directories(cstring INTERFACE + include) + +target_link_libraries(cstring INTERFACE + -lbsd) diff --git a/cstring/include/cstring.h b/cstring/include/cstring.h new file mode 100644 index 0000000..644f1e1 --- /dev/null +++ b/cstring/include/cstring.h @@ -0,0 +1,64 @@ +/// Fixed-size strings with value semantics. +#pragma once + +#include +#include + +/// A fixed-size string. +/// The string is null-terminated so that it can be used with the usual C APIs. +#define DEF_STRING(STRING, SIZE) \ + typedef struct STRING { \ + int length; \ + char str[SIZE]; \ + } STRING; \ + \ + static const size_t STRING##_size = SIZE; \ + \ + static inline const char* STRING##_cstring(const STRING* str) { \ + return str->str; \ + } \ + \ + static inline STRING STRING##_make(const char* cstr) { \ + if (!cstr) { \ + return (STRING){0}; \ + } else { \ + STRING str = (STRING){0}; \ + str.length = strlcpy(str.str, cstr, SIZE); \ + return str; \ + } \ + } \ + \ + static inline STRING STRING##_dirname(STRING path) { \ + STRING str = path; \ + for (int i = str.length - 1; i >= 0; --i) { \ + if (str.str[i] == '/' || str.str[i] == '\\') { \ + str.str[i] = 0; \ + str.length = i; \ + return str; \ + } else { \ + str.str[i] = 0; \ + } \ + } \ + str = (STRING){0}; \ + str.str[0] = '.'; \ + str.length = 1; \ + return str; \ + } \ + \ + static inline STRING STRING##_concat(STRING a, STRING b) { \ + assert(a.length + b.length + 1 < SIZE); \ + STRING str = {0}; \ + strlcpy(str.str, a.str, SIZE); \ + strlcpy(str.str + a.length, b.str, SIZE); \ + str.length = a.length + b.length; \ + return str; \ + } \ + \ + static inline STRING STRING##_concat_path(STRING a, STRING b) { \ + return STRING##_concat(STRING##_concat(a, STRING##_make("/")), b); \ + } + +DEF_STRING(sstring, 32) // Small. +DEF_STRING(mstring, 256) // Medium. +DEF_STRING(lstring, 1024) // Large. +DEF_STRING(xlstring, 4096) // Extra large. diff --git a/list/CMakeLists.txt b/list/CMakeLists.txt new file mode 100644 index 0000000..5d11d28 --- /dev/null +++ b/list/CMakeLists.txt @@ -0,0 +1,23 @@ +cmake_minimum_required(VERSION 3.16) + +project(list) + +# Library + +add_library(list + src/list.c) + +target_include_directories(list PUBLIC + include) + +target_compile_options(list PRIVATE -Wall -Wextra) + +# Test + +add_executable(list_test + test/list_test.c) + +target_link_libraries(list_test + list) + +target_compile_options(list_test PRIVATE -DUNIT_TEST -Wall -Wextra) diff --git a/list/include/list.h b/list/include/list.h new file mode 100644 index 0000000..b00b48b --- /dev/null +++ b/list/include/list.h @@ -0,0 +1,21 @@ +/// A doubly linked list. +/// +/// This list does not hold user data. Instead, the list can be used as an +/// intrusive list or as part as a more complex data structure. +#pragma once + +#include + +typedef struct list list; + +typedef struct list { + list* prev; + list* next; +} list; + +/// Create a new list from an array of `size` items. +void list_make(list* list, size_t size); + +/// Iterates over all the items in the list. +#define list_foreach(LIST, iter) \ + for (struct list* iter = LIST; iter; iter = iter->next) diff --git a/list/src/list.c b/list/src/list.c new file mode 100644 index 0000000..f5b6507 --- /dev/null +++ b/list/src/list.c @@ -0,0 +1,14 @@ +#include "list.h" + +#include + +void list_make(list* list, size_t size) { + if (size == 0) { + return; + } + assert(list); + for (size_t i = 0; i < size; ++i) { + list[i].prev = (i == 0 ? 0 : &list[i - 1]); + list[i].next = (i == size - 1 ? 0 : &list[i + 1]); + } +} diff --git a/list/test/list_test.c b/list/test/list_test.c new file mode 100644 index 0000000..a11c713 --- /dev/null +++ b/list/test/list_test.c @@ -0,0 +1,34 @@ +#include "list.h" + +#include "test.h" + +#define TEST_LIST_SIZE 10 + +// Create an empty list. +TEST_CASE(list_create_empty) { list_make(0, 0); } + +// Create a list of a given size. +TEST_CASE(list_create) { + struct list list[TEST_LIST_SIZE]; + list_make(list, TEST_LIST_SIZE); +} + +// Iterate over a list. +TEST_CASE(list_traverse) { + int numbers[TEST_LIST_SIZE] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; + + struct list list[TEST_LIST_SIZE]; + list_make(list, TEST_LIST_SIZE); + + int count = 0; + int sum = 0; + list_foreach(list, item) { + count++; + sum += numbers[item - list]; + } + + TEST_EQUAL(count, TEST_LIST_SIZE); + TEST_EQUAL(sum, TEST_LIST_SIZE * (TEST_LIST_SIZE + 1) / 2); +} + +int main() { return 0; } diff --git a/list/test/test.h b/list/test/test.h new file mode 100644 index 0000000..fd8dc22 --- /dev/null +++ b/list/test/test.h @@ -0,0 +1,185 @@ +// SPDX-License-Identifier: MIT +#pragma once + +#ifdef UNIT_TEST + +#include +#include +#include +#include + +#if defined(__DragonFly__) || defined(__FreeBSD__) || defined(__FreeBSD_kernel__) || \ + defined(__NetBSD__) || defined(__OpenBSD__) +#define USE_SYSCTL_FOR_ARGS 1 +// clang-format off +#include +#include +// clang-format on +#include // getpid +#endif + +struct test_file_metadata; + +struct test_failure { + bool present; + const char *message; + const char *file; + int line; +}; + +struct test_case_metadata { + void (*fn)(struct test_case_metadata *, struct test_file_metadata *); + struct test_failure failure; + const char *name; + struct test_case_metadata *next; +}; + +struct test_file_metadata { + bool registered; + const char *name; + struct test_file_metadata *next; + struct test_case_metadata *tests; +}; + +struct test_file_metadata __attribute__((weak)) * test_file_head; + +#define SET_FAILURE(_message) \ + metadata->failure = (struct test_failure) { \ + .message = _message, .file = __FILE__, .line = __LINE__, .present = true, \ + } + +#define TEST_EQUAL(a, b) \ + do { \ + if ((a) != (b)) { \ + SET_FAILURE(#a " != " #b); \ + return; \ + } \ + } while (0) + +#define TEST_TRUE(a) \ + do { \ + if (!(a)) { \ + SET_FAILURE(#a " is not true"); \ + return; \ + } \ + } while (0) + +#define TEST_STREQUAL(a, b) \ + do { \ + if (strcmp(a, b) != 0) { \ + SET_FAILURE(#a " != " #b); \ + return; \ + } \ + } while (0) + +#define TEST_CASE(_name) \ + static void __test_h_##_name(struct test_case_metadata *, \ + struct test_file_metadata *); \ + static struct test_file_metadata __test_h_file; \ + static struct test_case_metadata __test_h_meta_##_name = { \ + .name = #_name, \ + .fn = __test_h_##_name, \ + }; \ + static void __attribute__((constructor(101))) __test_h_##_name##_register(void) { \ + __test_h_meta_##_name.next = __test_h_file.tests; \ + __test_h_file.tests = &__test_h_meta_##_name; \ + if (!__test_h_file.registered) { \ + __test_h_file.name = __FILE__; \ + __test_h_file.next = test_file_head; \ + test_file_head = &__test_h_file; \ + __test_h_file.registered = true; \ + } \ + } \ + static void __test_h_##_name( \ + struct test_case_metadata *metadata __attribute__((unused)), \ + struct test_file_metadata *file_metadata __attribute__((unused))) + +extern void __attribute__((weak)) (*test_h_unittest_setup)(void); +/// Run defined tests, return true if all tests succeeds +/// @param[out] tests_run if not NULL, set to whether tests were run +static inline void __attribute__((constructor(102))) run_tests(void) { + bool should_run = false; +#ifdef USE_SYSCTL_FOR_ARGS + int mib[] = { + CTL_KERN, +#if defined(__NetBSD__) || defined(__OpenBSD__) + KERN_PROC_ARGS, + getpid(), + KERN_PROC_ARGV, +#else + KERN_PROC, + KERN_PROC_ARGS, + getpid(), +#endif + }; + char *arg = NULL; + size_t arglen; + sysctl(mib, sizeof(mib) / sizeof(mib[0]), NULL, &arglen, NULL, 0); + arg = malloc(arglen); + sysctl(mib, sizeof(mib) / sizeof(mib[0]), arg, &arglen, NULL, 0); +#else + FILE *cmdlinef = fopen("/proc/self/cmdline", "r"); + char *arg = NULL; + int arglen; + fscanf(cmdlinef, "%ms%n", &arg, &arglen); + fclose(cmdlinef); +#endif + for (char *pos = arg; pos < arg + arglen; pos += strlen(pos) + 1) { + if (strcmp(pos, "--unittest") == 0) { + should_run = true; + break; + } + } + free(arg); + + if (!should_run) { + return; + } + + if (&test_h_unittest_setup) { + test_h_unittest_setup(); + } + + struct test_file_metadata *i = test_file_head; + int failed = 0, success = 0; + while (i) { + fprintf(stderr, "Running tests from %s:\n", i->name); + struct test_case_metadata *j = i->tests; + while (j) { + fprintf(stderr, "\t%s ... ", j->name); + j->failure.present = false; + j->fn(j, i); + if (j->failure.present) { + fprintf(stderr, "failed (%s at %s:%d)\n", j->failure.message, + j->failure.file, j->failure.line); + failed++; + } else { + fprintf(stderr, "passed\n"); + success++; + } + j = j->next; + } + fprintf(stderr, "\n"); + i = i->next; + } + int total = failed + success; + fprintf(stderr, "Test results: passed %d/%d, failed %d/%d\n", success, total, + failed, total); + exit(failed == 0 ? EXIT_SUCCESS : EXIT_FAILURE); +} + +#else + +#include + +#define TEST_CASE(name) static void __attribute__((unused)) __test_h_##name(void) + +#define TEST_EQUAL(a, b) \ + (void)(a); \ + (void)(b) +#define TEST_TRUE(a) (void)(a) +#define TEST_STREQUAL(a, b) \ + (void)(a); \ + (void)(b) + +#endif diff --git a/listpool/CMakeLists.txt b/listpool/CMakeLists.txt new file mode 100644 index 0000000..6522d1f --- /dev/null +++ b/listpool/CMakeLists.txt @@ -0,0 +1,26 @@ +cmake_minimum_required(VERSION 3.16) + +project(listpool) + +# Library + +add_library(listpool + src/listpool.c) + +target_include_directories(listpool PUBLIC + include) + +target_link_libraries(listpool + list) + +target_compile_options(listpool PRIVATE -Wall -Wextra) + +# Test + +add_executable(listpool_test + test/listpool_test.c) + +target_link_libraries(listpool_test +listpool) + +target_compile_options(listpool_test PRIVATE -DUNIT_TEST -DNDEBUG -Wall -Wextra) diff --git a/listpool/README.md b/listpool/README.md new file mode 100644 index 0000000..ed38980 --- /dev/null +++ b/listpool/README.md @@ -0,0 +1,14 @@ +# Listpool + +A block allocator built from a single, contiguous array of memory that maintains +free and used blocks in doubly linked lists. + +A `listpool` is similar to a `mempool`, but the additional structure allows it +to: + +- Allocate and free blocks in constant time. +- Traverse used blocks in linear time in the number of used blocks, as opposed + to the total number of blocks like in a `mempool`. + +A `listpool` otherwise provides the same guarantees and characteristics as a +`mempool`. diff --git a/listpool/include/listpool.h b/listpool/include/listpool.h new file mode 100644 index 0000000..a5e4955 --- /dev/null +++ b/listpool/include/listpool.h @@ -0,0 +1,79 @@ +#pragma once + +#include "list.h" + +#include +#include +#include + +/// Define a typed listpool of a given size. +#define DEF_LISTPOOL(POOL, TYPE, NUM_BLOCKS) \ + typedef struct POOL { \ + listpool pool; \ + list nodes[NUM_BLOCKS]; \ + TYPE blocks[NUM_BLOCKS]; \ + } POOL; + +/// Creates a new listpool. +#define listpool_make(POOL) \ + { \ + assert(POOL); \ + const size_t block_size = sizeof((POOL)->blocks[0]); \ + const size_t num_blocks = sizeof((POOL)->blocks) / block_size; \ + listpool_make_(&(POOL)->pool, (POOL)->nodes, (POOL)->blocks, num_blocks, \ + block_size); \ + } + +/// Allocate a new block. +/// Return 0 if there is no memory left. +#define listpool_alloc(POOL) listpool_alloc_(&(POOL)->pool) + +/// Free the block. +/// The block pointer is conveniently set to 0. +#define listpool_free(POOL, ITEM) listpool_free_(&(POOL)->pool, (void**)ITEM) + +/// Remove a value from the list. +/// Defined here instead of DEF_LISTPOOL_IMPL() because not all types may have +/// an operator==. +#define listpool_remove(POOL, VAL) \ + { \ + listpool_foreach(POOL, iter, { \ + if (*iter == VAL) { \ + listpool_free(POOL, &iter); \ + break; \ + } \ + }); \ + } + +/// Iterate over the used items of the pool. +#define listpool_foreach(POOL, ITER, BODY) \ + for (list* it_ = (POOL)->pool.used; it_; it_ = it_->next) { \ + typeof((POOL)->blocks[0])* ITER = \ + &(POOL)->blocks[it_ - (POOL)->pool.nodes]; \ + (void)ITER; \ + BODY; \ + } + +typedef struct listpool { + size_t block_size_bytes; + size_t num_blocks; + list* free; // Head of the free list. + list* used; // Head of the used list. + list* nodes; // Array of nodes. + uint8_t* blocks; // Array of blocks; +} listpool; + +/// Create a new list pool from a user-provided array of memory. +/// `nodes` must have at least `num_blocks` nodes. +/// `blocks` must be at least `num_blocks` * `block_size_bytes` bytes. +/// All blocks are zeroed out for convenience. +void listpool_make_(listpool* pool, list* nodes, void* blocks, + size_t num_blocks, size_t block_size_bytes); + +/// Allocate a new block. +/// Return 0 if there is no memory left. +void* listpool_alloc_(listpool* pool); + +/// Free the block. +/// The block pointer is conveniently set to 0. +void listpool_free_(listpool* pool, void** block_ptr); diff --git a/listpool/src/listpool.c b/listpool/src/listpool.c new file mode 100644 index 0000000..9c86a3b --- /dev/null +++ b/listpool/src/listpool.c @@ -0,0 +1,78 @@ +#include "listpool.h" + +#include + +void listpool_make_(listpool* pool, list* nodes, void* blocks, + size_t num_blocks, size_t block_size_bytes) { + assert(pool); + pool->block_size_bytes = block_size_bytes; + pool->num_blocks = num_blocks; + pool->free = &nodes[0]; + pool->used = 0; + pool->nodes = nodes; + pool->blocks = blocks; + list_make(nodes, num_blocks); + memset(blocks, 0, num_blocks * block_size_bytes); +} + +void* listpool_alloc_(listpool* pool) { + assert(pool); + if (!pool->free) { + return 0; + } + + const size_t index = pool->free - pool->nodes; + assert(index < pool->num_blocks); + + list* free = pool->free; + pool->free = pool->free->next; + + // pool->used is always the head of the used list, so prepend the new item to + // the list. + list* new_used = free; + new_used->prev = 0; + new_used->next = pool->used; + if (pool->used) { + pool->used->prev = new_used; + } + pool->used = new_used; + + return pool->blocks + index * pool->block_size_bytes; +} + +void listpool_free_(listpool* pool, void** block_ptr) { + assert(pool); + assert(block_ptr); + + memset(*block_ptr, 0, pool->block_size_bytes); + + const size_t index = + ((uint8_t*)*block_ptr - pool->blocks) / pool->block_size_bytes; + assert(index < pool->num_blocks); + + list* item = &pool->nodes[index]; + + // We must remove the item from the used list first. + if (item->prev) { + item->prev->next = item->next; + } + if (item->next) { + item->next->prev = item->prev; + } + if (item == pool->used) { + pool->used = item->next; + } + + // pool->free is always the head of the free list, so prepend the new item to + // the list. The item is now free to wire after removing it from the used + // list. + if (!pool->free) { + pool->free = item; + } else { + item->next = pool->free; + pool->free->prev = item; + pool->free = item; + } + + *block_ptr = 0; +} diff --git a/listpool/test/listpool_test.c b/listpool/test/listpool_test.c new file mode 100644 index 0000000..cb54d00 --- /dev/null +++ b/listpool/test/listpool_test.c @@ -0,0 +1,166 @@ +#include "listpool.h" + +#include "test.h" + +#define NUM_BLOCKS 10 + +DEF_LISTPOOL(test_pool, int, NUM_BLOCKS); + +static int count(test_pool* pool) { + int count = 0; + listpool_foreach(pool, n, { count++; }); + return count; +} + +static int sum(test_pool* pool) { + int sum = 0; + listpool_foreach(pool, n, { sum += *n; }); + return sum; +} + +// Create a pool. +TEST_CASE(listpool_create) { + test_pool pool; + listpool_make(&pool); +} + +// Allocate all N blocks. +TEST_CASE(listpool_fully_allocate) { + test_pool pool; + listpool_make(&pool); + + for (int i = 0; i < NUM_BLOCKS; ++i) { + const int* block = listpool_alloc(&pool); + TEST_TRUE(block != 0); + } +} + +// Allocate all N blocks, then free them. +TEST_CASE(listpool_fill_then_free) { + test_pool pool; + listpool_make(&pool); + + int* blocks[NUM_BLOCKS] = {0}; + for (int i = 0; i < NUM_BLOCKS; i++) { + blocks[i] = listpool_alloc(&pool); + TEST_TRUE(blocks[i] != 0); + } + + for (int i = 0; i < NUM_BLOCKS; i++) { + listpool_free(&pool, &blocks[i]); + TEST_EQUAL(blocks[i], 0); // Pointer should be set to 0 on free. + } + + TEST_EQUAL(count(&pool), 0); +} + +// Attempt to allocate blocks past the maximum pool size. +// The pool should handle the failed allocations gracefully. +TEST_CASE(listpool_allocate_beyond_max_size) { + test_pool pool; + listpool_make(&pool); + + // Fully allocate the pool. + for (int i = 0; i < NUM_BLOCKS; ++i) { + TEST_TRUE(listpool_alloc(&pool) != 0); + } + + // Past the end. + for (int i = 0; i < NUM_BLOCKS; ++i) { + TEST_EQUAL(listpool_alloc(&pool), 0); + } +} + +// Free blocks should always remain zeroed out. +// This tests the invariant right after creating the pool. +TEST_CASE(listpool_zero_free_blocks_after_creation) { + test_pool pool; + listpool_make(&pool); + + const int zero = 0; + for (int i = 0; i < NUM_BLOCKS; ++i) { + const int* block = (const int*)(pool.blocks) + i; + TEST_EQUAL(memcmp(block, &zero, sizeof(int)), 0); + } +} + +// Free blocks should always remain zeroed out. +// This tests the invariant after freeing a block. +TEST_CASE(listpool_zero_free_block_after_free) { + test_pool pool; + listpool_make(&pool); + + int* val = listpool_alloc(&pool); + TEST_TRUE(val != 0); + *val = 177; + + int* old_val = val; + listpool_free(&pool, &val); // val pointer is set to 0. + TEST_EQUAL(*old_val, 0); // Block is zeroed out after free. +} + +// Traverse an empty pool. +TEST_CASE(listpool_traverse_empty) { + test_pool pool; + listpool_make(&pool); + + TEST_EQUAL(count(&pool), 0); +} + +// Traverse a partially full pool. +TEST_CASE(listpool_traverse_partially_full) { + const int N = NUM_BLOCKS / 2; + + test_pool pool; + listpool_make(&pool); + + for (int i = 0; i < N; ++i) { + int* val = listpool_alloc(&pool); + TEST_TRUE(val != 0); + *val = i + 1; + } + + TEST_EQUAL(sum(&pool), (N) * (N + 1) / 2); +} + +// Traverse a full pool. +TEST_CASE(listpool_traverse_full) { + test_pool pool; + listpool_make(&pool); + + for (int i = 0; i < NUM_BLOCKS; ++i) { + int* val = listpool_alloc(&pool); + TEST_TRUE(val != 0); + *val = i + 1; + } + + TEST_EQUAL(sum(&pool), (NUM_BLOCKS) * (NUM_BLOCKS + 1) / 2); +} + +// Remove a value from the list. +TEST_CASE(listpool_remove_value) { + test_pool pool; + listpool_make(&pool); + + int* x = listpool_alloc(&pool); + int* y = listpool_alloc(&pool); + TEST_TRUE(x != 0); + TEST_TRUE(y != 0); + + *x = 155; + *y = 177; + + listpool_remove(&pool, 155); // x + + TEST_EQUAL(count(&pool), 1); + TEST_EQUAL(sum(&pool), *y); +} + +// Stress test. +// +// 1. Allocate the pool, either fully or partially. If fully, attempt to +// allocate some items past the end. +// +// 2. Free all allocated items in some random order. + +int main() { return 0; } diff --git a/listpool/test/test.h b/listpool/test/test.h new file mode 100644 index 0000000..fd8dc22 --- /dev/null +++ b/listpool/test/test.h @@ -0,0 +1,185 @@ +// SPDX-License-Identifier: MIT +#pragma once + +#ifdef UNIT_TEST + +#include +#include +#include +#include + +#if defined(__DragonFly__) || defined(__FreeBSD__) || defined(__FreeBSD_kernel__) || \ + defined(__NetBSD__) || defined(__OpenBSD__) +#define USE_SYSCTL_FOR_ARGS 1 +// clang-format off +#include +#include +// clang-format on +#include // getpid +#endif + +struct test_file_metadata; + +struct test_failure { + bool present; + const char *message; + const char *file; + int line; +}; + +struct test_case_metadata { + void (*fn)(struct test_case_metadata *, struct test_file_metadata *); + struct test_failure failure; + const char *name; + struct test_case_metadata *next; +}; + +struct test_file_metadata { + bool registered; + const char *name; + struct test_file_metadata *next; + struct test_case_metadata *tests; +}; + +struct test_file_metadata __attribute__((weak)) * test_file_head; + +#define SET_FAILURE(_message) \ + metadata->failure = (struct test_failure) { \ + .message = _message, .file = __FILE__, .line = __LINE__, .present = true, \ + } + +#define TEST_EQUAL(a, b) \ + do { \ + if ((a) != (b)) { \ + SET_FAILURE(#a " != " #b); \ + return; \ + } \ + } while (0) + +#define TEST_TRUE(a) \ + do { \ + if (!(a)) { \ + SET_FAILURE(#a " is not true"); \ + return; \ + } \ + } while (0) + +#define TEST_STREQUAL(a, b) \ + do { \ + if (strcmp(a, b) != 0) { \ + SET_FAILURE(#a " != " #b); \ + return; \ + } \ + } while (0) + +#define TEST_CASE(_name) \ + static void __test_h_##_name(struct test_case_metadata *, \ + struct test_file_metadata *); \ + static struct test_file_metadata __test_h_file; \ + static struct test_case_metadata __test_h_meta_##_name = { \ + .name = #_name, \ + .fn = __test_h_##_name, \ + }; \ + static void __attribute__((constructor(101))) __test_h_##_name##_register(void) { \ + __test_h_meta_##_name.next = __test_h_file.tests; \ + __test_h_file.tests = &__test_h_meta_##_name; \ + if (!__test_h_file.registered) { \ + __test_h_file.name = __FILE__; \ + __test_h_file.next = test_file_head; \ + test_file_head = &__test_h_file; \ + __test_h_file.registered = true; \ + } \ + } \ + static void __test_h_##_name( \ + struct test_case_metadata *metadata __attribute__((unused)), \ + struct test_file_metadata *file_metadata __attribute__((unused))) + +extern void __attribute__((weak)) (*test_h_unittest_setup)(void); +/// Run defined tests, return true if all tests succeeds +/// @param[out] tests_run if not NULL, set to whether tests were run +static inline void __attribute__((constructor(102))) run_tests(void) { + bool should_run = false; +#ifdef USE_SYSCTL_FOR_ARGS + int mib[] = { + CTL_KERN, +#if defined(__NetBSD__) || defined(__OpenBSD__) + KERN_PROC_ARGS, + getpid(), + KERN_PROC_ARGV, +#else + KERN_PROC, + KERN_PROC_ARGS, + getpid(), +#endif + }; + char *arg = NULL; + size_t arglen; + sysctl(mib, sizeof(mib) / sizeof(mib[0]), NULL, &arglen, NULL, 0); + arg = malloc(arglen); + sysctl(mib, sizeof(mib) / sizeof(mib[0]), arg, &arglen, NULL, 0); +#else + FILE *cmdlinef = fopen("/proc/self/cmdline", "r"); + char *arg = NULL; + int arglen; + fscanf(cmdlinef, "%ms%n", &arg, &arglen); + fclose(cmdlinef); +#endif + for (char *pos = arg; pos < arg + arglen; pos += strlen(pos) + 1) { + if (strcmp(pos, "--unittest") == 0) { + should_run = true; + break; + } + } + free(arg); + + if (!should_run) { + return; + } + + if (&test_h_unittest_setup) { + test_h_unittest_setup(); + } + + struct test_file_metadata *i = test_file_head; + int failed = 0, success = 0; + while (i) { + fprintf(stderr, "Running tests from %s:\n", i->name); + struct test_case_metadata *j = i->tests; + while (j) { + fprintf(stderr, "\t%s ... ", j->name); + j->failure.present = false; + j->fn(j, i); + if (j->failure.present) { + fprintf(stderr, "failed (%s at %s:%d)\n", j->failure.message, + j->failure.file, j->failure.line); + failed++; + } else { + fprintf(stderr, "passed\n"); + success++; + } + j = j->next; + } + fprintf(stderr, "\n"); + i = i->next; + } + int total = failed + success; + fprintf(stderr, "Test results: passed %d/%d, failed %d/%d\n", success, total, + failed, total); + exit(failed == 0 ? EXIT_SUCCESS : EXIT_FAILURE); +} + +#else + +#include + +#define TEST_CASE(name) static void __attribute__((unused)) __test_h_##name(void) + +#define TEST_EQUAL(a, b) \ + (void)(a); \ + (void)(b) +#define TEST_TRUE(a) (void)(a) +#define TEST_STREQUAL(a, b) \ + (void)(a); \ + (void)(b) + +#endif diff --git a/log/CMakeLists.txt b/log/CMakeLists.txt new file mode 100644 index 0000000..490c78c --- /dev/null +++ b/log/CMakeLists.txt @@ -0,0 +1,9 @@ +cmake_minimum_required(VERSION 3.16) + +add_library(log + src/log.c) + +target_include_directories(log PUBLIC + include) + +target_compile_options(log PRIVATE -Wall -Wextra) diff --git a/log/README.md b/log/README.md new file mode 100644 index 0000000..1c70225 --- /dev/null +++ b/log/README.md @@ -0,0 +1 @@ +# Logging Library diff --git a/log/include/log/log.h b/log/include/log/log.h new file mode 100644 index 0000000..41a83cc --- /dev/null +++ b/log/include/log/log.h @@ -0,0 +1,19 @@ +#pragma once + +// Current implementation assumes a posix environment. + +#include + +typedef enum { LogDebug, LogInfo, LogWarning, LogError } LogLevel; + +#define LOG(tag, ...) \ + { \ + printf("[%s] %s:%d: ", #tag, __FILE__, __LINE__); \ + printf(__VA_ARGS__); \ + printf("\n"); \ + } + +#define LOGD(...) LOG(DEBUG, __VA_ARGS__) +#define LOGI(...) LOG(INFO, __VA_ARGS__) +#define LOGW(...) LOG(WARN, __VA_ARGS__) +#define LOGE(...) LOG(ERROR, __VA_ARGS__) diff --git a/log/src/log.c b/log/src/log.c new file mode 100644 index 0000000..0e0248e --- /dev/null +++ b/log/src/log.c @@ -0,0 +1 @@ +#include diff --git a/mempool/CMakeLists.txt b/mempool/CMakeLists.txt new file mode 100644 index 0000000..1ff4ff1 --- /dev/null +++ b/mempool/CMakeLists.txt @@ -0,0 +1,23 @@ +cmake_minimum_required(VERSION 3.16) + +project(mempool) + +# Library + +add_library(mempool + src/mempool.c) + +target_include_directories(mempool PUBLIC + include) + +target_compile_options(mempool PRIVATE -Wall -Wextra) + +# Test + +add_executable(mempool_test + test/mempool_test.c) + +target_link_libraries(mempool_test + mempool) + +target_compile_options(mempool_test PRIVATE -DUNIT_TEST -DNDEBUG -Wall -Wextra) diff --git a/mempool/README.md b/mempool/README.md new file mode 100644 index 0000000..ed2935e --- /dev/null +++ b/mempool/README.md @@ -0,0 +1,20 @@ +# Mempool + +A memory pool implementation. + +Each block in the pool is tagged with a boolean value that indicates whether the +block is free or in use. The allocator otherwise maintains little additional +information. Therefore, some operations have linear-time complexity. +Specifically: + +- Allocating a block scans the pool for the next free block in linear time. +- Freeing a block runs in constant time. +- Iterating over the pool's used blocks is linear over the number of blocks in + the pool, as opposed to just the number of used blocks. + +The allocator's internal data is also stored separately from the main array of +blocks so that the block data remains tightly packed. + +For convenience of programming and debugging, free blocks in the mempool always +remain zeroed out. If your data structures are valid when zeroed out, then you +do not need to explicitly initialize them. diff --git a/mempool/include/mempool.h b/mempool/include/mempool.h new file mode 100644 index 0000000..41d56e5 --- /dev/null +++ b/mempool/include/mempool.h @@ -0,0 +1,91 @@ +#pragma once + +#include +#include +#include +#include + +/// Define a typed mempool of the given number of blocks. +#define DEF_MEMPOOL(POOL, TYPE, NUM_BLOCKS) \ + typedef struct POOL { \ + mempool pool; \ + BlockInfo block_info[NUM_BLOCKS]; \ + TYPE blocks[NUM_BLOCKS]; \ + } POOL; + +/// Create a new pool. +#define mempool_make(POOL) \ + { \ + assert(POOL); \ + const size_t block_size = sizeof((POOL)->blocks[0]); \ + const size_t num_blocks = sizeof((POOL)->blocks) / block_size; \ + mempool_make_(&(POOL)->pool, (POOL)->block_info, (POOL)->blocks, \ + num_blocks, block_size); \ + } + +/// Allocate a new block. +/// Return 0 if there is no memory left. +#define mempool_alloc(POOL) mempool_alloc_(&(POOL)->pool) + +/// Free the block. +/// The block pointer is conveniently set to 0. +#define mempool_free(POOL, BLOCK_PTR) \ + assert(*BLOCK_PTR); \ + mempool_free_(&(POOL)->pool, (void**)BLOCK_PTR) + +/// Return the ith block. +/// The block must have been allocated. +#define mempool_get_block(POOL, INDEX) \ + ((typeof((POOL)->blocks[0])*)mempool_get_block_(&(POOL)->pool, INDEX)) + +/// Get the index to the given block. +#define mempool_get_block_index(POOL, BLOCK_PTR) \ + mempool_get_block_index_(&(POOL)->pool, BLOCK_PTR) + +/// Iterate over the used blocks of the pool. +#define mempool_foreach(POOL, ITER, BODY) \ + for (size_t i = 0; \ + i < (sizeof((POOL)->blocks) / sizeof(typeof((POOL)->blocks[0]))); \ + ++i) { \ + if (!(POOL)->block_info[i].used) { \ + continue; \ + } \ + typeof((POOL)->blocks[0])* ITER = &(POOL)->blocks[i]; \ + (void)ITER; \ + BODY; \ + } + +typedef struct BlockInfo { + bool used; +} BlockInfo; + +typedef struct mempool { + size_t block_size_bytes; + size_t num_blocks; + size_t next_free_block; + bool full; + BlockInfo* block_info; + uint8_t* blocks; +} mempool; + +/// Create a pool allocator from user-provided memory. +/// `BlockInfo` must hold at least `num_blocks` entries. +/// `blocks` must be at least `num_blocks` * `block_size_bytes` bytes. +/// All blocks are zeroed out for convenience. +void mempool_make_(mempool*, BlockInfo*, void* blocks, size_t num_blocks, + size_t block_size_bytes); + +/// Allocate a new block. +/// Return 0 if there is no memory left. +void* mempool_alloc_(mempool*); + +/// Free the block. +/// The block pointer is conveniently set to 0. +void mempool_free_(mempool*, void** block_ptr); + +/// Return the ith block. +/// The block must have been allocated. +void* mempool_get_block_(const mempool*, size_t block_index); + +/// Get the index to the given block. +size_t mempool_get_block_index_(const mempool*, const void* block); diff --git a/mempool/src/mempool.c b/mempool/src/mempool.c new file mode 100644 index 0000000..b7e8705 --- /dev/null +++ b/mempool/src/mempool.c @@ -0,0 +1,85 @@ +#include "mempool.h" + +#include + +static inline size_t min(size_t a, size_t b) { return a < b ? a : b; } + +void mempool_make_(mempool* pool, BlockInfo* block_info, void* blocks, + size_t num_blocks, size_t block_size_bytes) { + assert(pool); + assert(block_info); + assert(blocks); + assert(num_blocks >= 1); + pool->block_size_bytes = block_size_bytes; + pool->num_blocks = num_blocks; + pool->next_free_block = 0; + pool->full = false; + pool->block_info = block_info; + pool->blocks = blocks; + memset(blocks, 0, num_blocks * block_size_bytes); +} + +void* mempool_alloc_(mempool* pool) { + assert(pool); + + if (pool->full) { + return 0; + } + + // Allocate the block. + void* block = &pool->blocks[pool->next_free_block * pool->block_size_bytes]; + pool->block_info[pool->next_free_block].used = true; + + // Search for the next free block. If it does not exist, flag the pool full. + pool->full = true; + for (size_t i = 1; i < pool->num_blocks && i != 0; i++) { + pool->next_free_block = (pool->next_free_block + 1) % pool->num_blocks; + if (!pool->block_info[pool->next_free_block].used) { + pool->full = false; + break; + } + } + + return block; +} + +void mempool_free_(mempool* pool, void** block_ptr) { + assert(pool); + assert(block_ptr); + + memset(*block_ptr, 0, pool->block_size_bytes); + + const size_t block_index = + ((uint8_t*)*block_ptr - pool->blocks) / pool->block_size_bytes; + assert(block_index < pool->num_blocks); + + // Disallow double-frees. + assert(pool->block_info[block_index].used); + + pool->block_info[block_index].used = false; + if (pool->full) { + pool->next_free_block = block_index; + pool->full = false; + } else { + // Prefer to allocate blocks towards the start of the pool. This way, blocks + // should cluster around this area and the pool should offer better memory + // locality for used blocks. + pool->next_free_block = min(pool->next_free_block, block_index); + } + + *block_ptr = 0; +} + +void* mempool_get_block_(const mempool* pool, size_t block_index) { + assert(pool); + assert(block_index < pool->num_blocks); + assert(pool->block_info[block_index].used); + return pool->blocks + block_index * pool->block_size_bytes; +} + +size_t mempool_get_block_index_(const mempool* pool, const void* block) { + assert(pool); + const size_t block_byte_index = (const uint8_t*)block - pool->blocks; + assert(block_byte_index % pool->block_size_bytes == 0); + return block_byte_index / pool->block_size_bytes; +} diff --git a/mempool/test/mempool_test.c b/mempool/test/mempool_test.c new file mode 100644 index 0000000..d257922 --- /dev/null +++ b/mempool/test/mempool_test.c @@ -0,0 +1,157 @@ +#include "mempool.h" + +#include "test.h" + +#define NUM_BLOCKS 10 + +DEF_MEMPOOL(test_pool, int, NUM_BLOCKS); + +static int count(test_pool* pool) { + int count = 0; + mempool_foreach(pool, n, { count++; }); + return count; +} + +static int sum(test_pool* pool) { + int sum = 0; + mempool_foreach(pool, n, { sum += *n; }); + return sum; +} + +// Create a pool. +TEST_CASE(mempool_create) { + test_pool pool; + mempool_make(&pool); +} + +// Allocate all N blocks. +TEST_CASE(mempool_allocate_until_full) { + test_pool pool; + mempool_make(&pool); + + for (int i = 0; i < NUM_BLOCKS; ++i) { + const int* block = mempool_alloc(&pool); + TEST_TRUE(block != 0); + } +} + +// Allocate all N blocks, then free them. +TEST_CASE(mempool_fill_then_free) { + test_pool pool; + mempool_make(&pool); + + int* blocks[NUM_BLOCKS] = {0}; + for (int i = 0; i < NUM_BLOCKS; ++i) { + blocks[i] = mempool_alloc(&pool); + TEST_TRUE(blocks[i] != 0); + } + + for (int i = 0; i < NUM_BLOCKS; ++i) { + mempool_free(&pool, &blocks[i]); + TEST_EQUAL(blocks[i], 0); // Pointer should be set to 0 on free. + } + + TEST_EQUAL(count(&pool), 0); +} + +// Attempt to allocate blocks past the maximum pool size. +// The pool should handle the failed allocations gracefully. +TEST_CASE(mempool_allocate_beyond_max_size) { + test_pool pool; + mempool_make(&pool); + + // Fully allocate the pool. + for (int i = 0; i < NUM_BLOCKS; ++i) { + TEST_TRUE(mempool_alloc(&pool) != 0); + } + + // Past the end. + for (int i = 0; i < NUM_BLOCKS; ++i) { + TEST_EQUAL(mempool_alloc(&pool), 0); + } +} + +// Free blocks should always remain zeroed out. +// This tests the invariant right after creating the pool. +TEST_CASE(mempool_zero_free_blocks_after_creation) { + test_pool pool; + mempool_make(&pool); + + const int zero = 0; + for (int i = 0; i < NUM_BLOCKS; ++i) { + const int* block = (const int*)(pool.blocks) + i; + TEST_EQUAL(memcmp(block, &zero, sizeof(int)), 0); + } +} + +// Free blocks should always remain zeroed out. +// This tests the invariant after freeing a block. +TEST_CASE(mempool_zero_free_block_after_free) { + test_pool pool; + mempool_make(&pool); + + int* val = mempool_alloc(&pool); + TEST_TRUE(val != 0); + *val = 177; + + int* old_val = val; + mempool_free(&pool, &val); // val pointer is set to 0. + TEST_EQUAL(*old_val, 0); // Block is zeroed out after free. +} + +// Traverse an empty pool. +TEST_CASE(mempool_traverse_empty) { + test_pool pool; + mempool_make(&pool); + + TEST_EQUAL(count(&pool), 0); +} + +// Traverse a partially full pool. +TEST_CASE(mempool_traverse_partially_full) { + const int N = NUM_BLOCKS / 2; + + test_pool pool; + mempool_make(&pool); + + for (int i = 0; i < N; ++i) { + int* val = mempool_alloc(&pool); + TEST_TRUE(val != 0); + *val = i + 1; + } + + TEST_EQUAL(sum(&pool), N * (N + 1) / 2); +} + +// Traverse a full pool. +TEST_CASE(mempool_traverse_full) { + test_pool pool; + mempool_make(&pool); + + for (int i = 0; i < NUM_BLOCKS; ++i) { + int* val = mempool_alloc(&pool); + TEST_TRUE(val != 0); + *val = i + 1; + } + + TEST_EQUAL(sum(&pool), NUM_BLOCKS * (NUM_BLOCKS + 1) / 2); +} + +// Get the ith (allocated) block. +TEST_CASE(mempool_get_block) { + test_pool pool; + mempool_make(&pool); + + for (int i = 0; i < NUM_BLOCKS; ++i) { + int* block = mempool_alloc(&pool); + TEST_TRUE(block != 0); + *block = i; + TEST_EQUAL(mempool_get_block_index(&pool, block), (size_t)i); + } + + for (int i = 0; i < NUM_BLOCKS; ++i) { + TEST_EQUAL(*mempool_get_block(&pool, i), i); + } +} + +int main() { return 0; } diff --git a/mempool/test/test.h b/mempool/test/test.h new file mode 100644 index 0000000..fd8dc22 --- /dev/null +++ b/mempool/test/test.h @@ -0,0 +1,185 @@ +// SPDX-License-Identifier: MIT +#pragma once + +#ifdef UNIT_TEST + +#include +#include +#include +#include + +#if defined(__DragonFly__) || defined(__FreeBSD__) || defined(__FreeBSD_kernel__) || \ + defined(__NetBSD__) || defined(__OpenBSD__) +#define USE_SYSCTL_FOR_ARGS 1 +// clang-format off +#include +#include +// clang-format on +#include // getpid +#endif + +struct test_file_metadata; + +struct test_failure { + bool present; + const char *message; + const char *file; + int line; +}; + +struct test_case_metadata { + void (*fn)(struct test_case_metadata *, struct test_file_metadata *); + struct test_failure failure; + const char *name; + struct test_case_metadata *next; +}; + +struct test_file_metadata { + bool registered; + const char *name; + struct test_file_metadata *next; + struct test_case_metadata *tests; +}; + +struct test_file_metadata __attribute__((weak)) * test_file_head; + +#define SET_FAILURE(_message) \ + metadata->failure = (struct test_failure) { \ + .message = _message, .file = __FILE__, .line = __LINE__, .present = true, \ + } + +#define TEST_EQUAL(a, b) \ + do { \ + if ((a) != (b)) { \ + SET_FAILURE(#a " != " #b); \ + return; \ + } \ + } while (0) + +#define TEST_TRUE(a) \ + do { \ + if (!(a)) { \ + SET_FAILURE(#a " is not true"); \ + return; \ + } \ + } while (0) + +#define TEST_STREQUAL(a, b) \ + do { \ + if (strcmp(a, b) != 0) { \ + SET_FAILURE(#a " != " #b); \ + return; \ + } \ + } while (0) + +#define TEST_CASE(_name) \ + static void __test_h_##_name(struct test_case_metadata *, \ + struct test_file_metadata *); \ + static struct test_file_metadata __test_h_file; \ + static struct test_case_metadata __test_h_meta_##_name = { \ + .name = #_name, \ + .fn = __test_h_##_name, \ + }; \ + static void __attribute__((constructor(101))) __test_h_##_name##_register(void) { \ + __test_h_meta_##_name.next = __test_h_file.tests; \ + __test_h_file.tests = &__test_h_meta_##_name; \ + if (!__test_h_file.registered) { \ + __test_h_file.name = __FILE__; \ + __test_h_file.next = test_file_head; \ + test_file_head = &__test_h_file; \ + __test_h_file.registered = true; \ + } \ + } \ + static void __test_h_##_name( \ + struct test_case_metadata *metadata __attribute__((unused)), \ + struct test_file_metadata *file_metadata __attribute__((unused))) + +extern void __attribute__((weak)) (*test_h_unittest_setup)(void); +/// Run defined tests, return true if all tests succeeds +/// @param[out] tests_run if not NULL, set to whether tests were run +static inline void __attribute__((constructor(102))) run_tests(void) { + bool should_run = false; +#ifdef USE_SYSCTL_FOR_ARGS + int mib[] = { + CTL_KERN, +#if defined(__NetBSD__) || defined(__OpenBSD__) + KERN_PROC_ARGS, + getpid(), + KERN_PROC_ARGV, +#else + KERN_PROC, + KERN_PROC_ARGS, + getpid(), +#endif + }; + char *arg = NULL; + size_t arglen; + sysctl(mib, sizeof(mib) / sizeof(mib[0]), NULL, &arglen, NULL, 0); + arg = malloc(arglen); + sysctl(mib, sizeof(mib) / sizeof(mib[0]), arg, &arglen, NULL, 0); +#else + FILE *cmdlinef = fopen("/proc/self/cmdline", "r"); + char *arg = NULL; + int arglen; + fscanf(cmdlinef, "%ms%n", &arg, &arglen); + fclose(cmdlinef); +#endif + for (char *pos = arg; pos < arg + arglen; pos += strlen(pos) + 1) { + if (strcmp(pos, "--unittest") == 0) { + should_run = true; + break; + } + } + free(arg); + + if (!should_run) { + return; + } + + if (&test_h_unittest_setup) { + test_h_unittest_setup(); + } + + struct test_file_metadata *i = test_file_head; + int failed = 0, success = 0; + while (i) { + fprintf(stderr, "Running tests from %s:\n", i->name); + struct test_case_metadata *j = i->tests; + while (j) { + fprintf(stderr, "\t%s ... ", j->name); + j->failure.present = false; + j->fn(j, i); + if (j->failure.present) { + fprintf(stderr, "failed (%s at %s:%d)\n", j->failure.message, + j->failure.file, j->failure.line); + failed++; + } else { + fprintf(stderr, "passed\n"); + success++; + } + j = j->next; + } + fprintf(stderr, "\n"); + i = i->next; + } + int total = failed + success; + fprintf(stderr, "Test results: passed %d/%d, failed %d/%d\n", success, total, + failed, total); + exit(failed == 0 ? EXIT_SUCCESS : EXIT_FAILURE); +} + +#else + +#include + +#define TEST_CASE(name) static void __attribute__((unused)) __test_h_##name(void) + +#define TEST_EQUAL(a, b) \ + (void)(a); \ + (void)(b) +#define TEST_TRUE(a) (void)(a) +#define TEST_STREQUAL(a, b) \ + (void)(a); \ + (void)(b) + +#endif -- cgit v1.2.3