diff options
Diffstat (limited to 'libdimension/base')
| -rw-r--r-- | libdimension/base/array.c | 33 | ||||
| -rw-r--r-- | libdimension/base/dictionary.c | 228 | ||||
| -rw-r--r-- | libdimension/base/error.c | 144 | ||||
| -rw-r--r-- | libdimension/base/inline.c | 43 | ||||
| -rw-r--r-- | libdimension/base/malloc.c | 94 | ||||
| -rw-r--r-- | libdimension/base/pool.c | 177 | ||||
| -rw-r--r-- | libdimension/base/profile.c | 168 |
7 files changed, 887 insertions, 0 deletions
diff --git a/libdimension/base/array.c b/libdimension/base/array.c new file mode 100644 index 0000000..d8faed7 --- /dev/null +++ b/libdimension/base/array.c @@ -0,0 +1,33 @@ +/************************************************************************* + * Copyright (C) 2014 Tavian Barnes <tavianator@tavianator.com> * + * * + * This file is part of The Dimension Library. * + * * + * The Dimension Library is free software; you can redistribute it and/ * + * or modify it under the terms of the GNU Lesser General Public License * + * as published by the Free Software Foundation; either version 3 of the * + * License, or (at your option) any later version. * + * * + * The Dimension Library is distributed in the hope that it will be * + * useful, but WITHOUT ANY WARRANTY; without even the implied warranty * + * of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU * + * Lesser General Public License for more details. * + * * + * You should have received a copy of the GNU Lesser General Public * + * License along with this program. If not, see * + * <http://www.gnu.org/licenses/>. * + *************************************************************************/ + +/** + * @file + * Non-inline array functions. + */ + +#include "dimension/base.h" + +void +dmnsn_array_cleanup(void *ptr) +{ + dmnsn_array *array = ptr; + dmnsn_free(array->ptr); +} diff --git a/libdimension/base/dictionary.c b/libdimension/base/dictionary.c new file mode 100644 index 0000000..6e99abd --- /dev/null +++ b/libdimension/base/dictionary.c @@ -0,0 +1,228 @@ +/************************************************************************* + * Copyright (C) 2010-2014 Tavian Barnes <tavianator@tavianator.com> * + * * + * This file is part of The Dimension Library. * + * * + * The Dimension Library is free software; you can redistribute it and/ * + * or modify it under the terms of the GNU Lesser General Public License * + * as published by the Free Software Foundation; either version 3 of the * + * License, or (at your option) any later version. * + * * + * The Dimension Library is distributed in the hope that it will be * + * useful, but WITHOUT ANY WARRANTY; without even the implied warranty * + * of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU * + * Lesser General Public License for more details. * + * * + * You should have received a copy of the GNU Lesser General Public * + * License along with this program. If not, see * + * <http://www.gnu.org/licenses/>. * + *************************************************************************/ + +/** + * @file + * Associative arrays, implemented with PATRICIA tries. + */ + +#include "dimension/base.h" + +struct dmnsn_dictionary { + size_t obj_size; ///< The size of the objects in the trie. + char *prefix; ///< The local string prefix of the current node. + void *value; ///< The node's stored object, if it's a leaf. + dmnsn_array *children; ///< The node's children. +}; + +dmnsn_dictionary * +dmnsn_new_dictionary(size_t obj_size) +{ + dmnsn_dictionary *dict = DMNSN_MALLOC(dmnsn_dictionary); + dict->obj_size = obj_size; + dict->prefix = dmnsn_strdup(""); + dict->value = NULL; + dict->children = DMNSN_NEW_ARRAY(dmnsn_dictionary *); + return dict; +} + +void +dmnsn_delete_dictionary(dmnsn_dictionary *dict) +{ + if (dict) { + dmnsn_free(dict->prefix); + dmnsn_free(dict->value); + DMNSN_ARRAY_FOREACH (dmnsn_dictionary **, subtrie, dict->children) { + dmnsn_delete_dictionary(*subtrie); + } + dmnsn_delete_array(dict->children); + + dmnsn_free(dict); + } +} + +bool +dmnsn_dictionary_get(const dmnsn_dictionary *dict, const char *key, void *obj) +{ + const void *value = dmnsn_dictionary_at(dict, key); + if (value) { + memcpy(obj, value, dict->obj_size); + return true; + } else { + return false; + } +} + +void * +dmnsn_dictionary_at(const dmnsn_dictionary *dict, const char *key) +{ + // PATRICIA trie search: O(k), where k is the length of the longest string in + // the trie. + + size_t len = strlen(dict->prefix); + if (strncmp(key, dict->prefix, len) != 0) + return NULL; + key += len; + + while (true) { + if (*key == '\0' && dict->value) { + return dict->value; + } else { + dmnsn_dictionary **first = dmnsn_array_first(dict->children), **subtrie; + ptrdiff_t size = dmnsn_array_size(dict->children); + for (subtrie = first; subtrie - first < size; ++subtrie) { + len = strlen((*subtrie)->prefix); + if (strncmp(key, (*subtrie)->prefix, len) == 0) { + dict = *subtrie; + key += len; + break; + } + } + + if (subtrie - first == size) + break; + } + } + + return NULL; +} + +void +dmnsn_dictionary_insert(dmnsn_dictionary *dict, const char *key, + const void *obj) +{ + // PATRICIA trie insertion: O(k), where k is the length of the longest string + // in the trie. + + while (true) { + if (dict->prefix[0] == '\0' && !dict->value + && dmnsn_array_size(dict->children) == 0) + { + // Replace an empty tree with a single-element tree + dict->prefix = dmnsn_realloc(dict->prefix, strlen(key) + 1); + strcpy(dict->prefix, key); + + dict->value = dmnsn_malloc(dict->obj_size); + memcpy(dict->value, obj, dict->obj_size); + break; + } + + char *prefix = dict->prefix; + while (*prefix == *key && *prefix && *key) { + ++prefix; + ++key; + } + + if (*key == '\0' && *prefix == '\0') { + // Complete match + if (!dict->value) { + dict->value = dmnsn_malloc(dict->obj_size); + } + memcpy(dict->value, obj, dict->obj_size); + break; + } else if (*prefix == '\0') { + // Partial match; key starts with prefix + dmnsn_dictionary **first = dmnsn_array_first(dict->children), **subtrie; + ptrdiff_t size = dmnsn_array_size(dict->children); + for (subtrie = first; subtrie - first < size; ++subtrie) { + if ((*subtrie)->prefix[0] == key[0]) { + dict = *subtrie; + break; + } + } + + if (subtrie - first == size) { + // No submatch found, add a new child + dmnsn_dictionary *child = dmnsn_new_dictionary(dict->obj_size); + dmnsn_array_push(dict->children, &child); + dict = child; + } + } else { + // Split the tree + dmnsn_dictionary *copy = dmnsn_new_dictionary(dict->obj_size); + copy->prefix = dmnsn_realloc(copy->prefix, strlen(prefix) + 1); + strcpy(copy->prefix, prefix); + *prefix = '\0'; + + copy->value = dict->value; + dict->value = NULL; + + dmnsn_array *temp = copy->children; + copy->children = dict->children; + dict->children = temp; + + dmnsn_dictionary *subtrie = dmnsn_new_dictionary(dict->obj_size); + dmnsn_array_push(dict->children, ©); + dmnsn_array_push(dict->children, &subtrie); + dict = subtrie; + } + } +} + +bool +dmnsn_dictionary_remove(dmnsn_dictionary *dict, const char *key) +{ + // PATRICIA trie removal: O(k), where k is the length of the longest string + // in the trie. + + // This implementation doesn't actually collapse the tree back upwards if a + // node is left with only one child, to reduce complexity. + + size_t len = strlen(dict->prefix); + if (strncmp(key, dict->prefix, len) != 0) + return false; + key += len; + + while (true) { + if (*key == '\0' && dict->value) { + dmnsn_free(dict->value); + dict->value = NULL; + return true; + } else { + dmnsn_dictionary **first = dmnsn_array_first(dict->children), **subtrie; + ptrdiff_t size = dmnsn_array_size(dict->children); + for (subtrie = first; subtrie - first < size; ++subtrie) { + len = strlen((*subtrie)->prefix); + if (strncmp(key, (*subtrie)->prefix, len) == 0) { + dict = *subtrie; + key += len; + break; + } + } + + if (subtrie - first == size) + break; + } + } + + return false; +} + +void +dmnsn_dictionary_apply(dmnsn_dictionary *dict, dmnsn_callback_fn *callback) +{ + if (dict->value) { + callback(dict->value); + } + + DMNSN_ARRAY_FOREACH (dmnsn_dictionary **, subtrie, dict->children) { + dmnsn_dictionary_apply(*subtrie, callback); + } +} diff --git a/libdimension/base/error.c b/libdimension/base/error.c new file mode 100644 index 0000000..6b8d18e --- /dev/null +++ b/libdimension/base/error.c @@ -0,0 +1,144 @@ +/************************************************************************* + * Copyright (C) 2009-2014 Tavian Barnes <tavianator@tavianator.com> * + * * + * This file is part of The Dimension Library. * + * * + * The Dimension Library is free software; you can redistribute it and/ * + * or modify it under the terms of the GNU Lesser General Public License * + * as published by the Free Software Foundation; either version 3 of the * + * License, or (at your option) any later version. * + * * + * The Dimension Library is distributed in the hope that it will be * + * useful, but WITHOUT ANY WARRANTY; without even the implied warranty * + * of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU * + * Lesser General Public License for more details. * + * * + * You should have received a copy of the GNU Lesser General Public * + * License along with this program. If not, see * + * <http://www.gnu.org/licenses/>. * + *************************************************************************/ + +/** + * @file + * Error handling. + */ + +#include "internal.h" +#include "internal/platform.h" +#include <errno.h> +#include <pthread.h> +#include <stdatomic.h> +#include <stdbool.h> +#include <stdio.h> +#include <stdlib.h> +#include <string.h> + +/// Report internal errors in this file. +#define DMNSN_LOCAL_ERROR(str) \ + do { \ + fprintf(stderr, "Dimension ERROR: %s, %s:%u: %s\n", \ + DMNSN_FUNC, __FILE__, __LINE__, (str)); \ + abort(); \ + } while (0) + +/// The default fatal error handler. +static void dmnsn_default_fatal_error_fn(void); + +/// The current fatal error handler. +static atomic(dmnsn_fatal_error_fn *) dmnsn_fatal = ATOMIC_VAR_INIT(dmnsn_default_fatal_error_fn); + +/// The current resilience. +static atomic_bool dmnsn_always_die = ATOMIC_VAR_INIT(false); + +void +dmnsn_report_impl(bool die, const char *func, const char *file, unsigned int line, const char *str) +{ + // Save the value of errno + int err = errno; + + bool always_die = atomic_load(&dmnsn_always_die); + + // Print the diagnostic string + fprintf(stderr, "Dimension %s: %s, %s:%u: %s\n", + die ? "ERROR" : "WARNING", func, file, line, str); + + // Print the value of errno + if (err != 0) { + fprintf(stderr, "Last error: %d", err); +#if DMNSN_STRERROR_R + char errbuf[256]; + if (strerror_r(err, errbuf, 256) == 0) { + fprintf(stderr, " (%s)", errbuf); + } +#elif DMNSN_SYS_ERRLIST + if (err >= 0 && err < sys_nerr) { + fprintf(stderr, " (%s)", sys_errlist[err]); + } +#endif + fprintf(stderr, "\n"); + } + + // Print a stack trace to standard error + dmnsn_backtrace(stderr); + + // Call the fatal error handler if needed + if (die || always_die) { + static __thread bool thread_exiting = false; + + if (thread_exiting) { + if (die) { + // Prevent infinite recursion if the fatal error function itself calls + // dmnsn_error() (not dmnsn_warning()) + DMNSN_LOCAL_ERROR("Error raised while in error handler, aborting."); + } + } else { + thread_exiting = true; + + dmnsn_fatal_error_fn *fatal = dmnsn_get_fatal_error_fn(); + fatal(); + DMNSN_LOCAL_ERROR("Fatal error handler didn't exit."); + } + } +} + +void +dmnsn_report_warning(const char *func, const char *file, unsigned int line, const char *str) +{ + dmnsn_report_impl(false, func, file, line, str); +} + +DMNSN_NORETURN +dmnsn_report_error(const char *func, const char *file, unsigned int line, const char *str) +{ + dmnsn_report_impl(true, func, file, line, str); + DMNSN_UNREACHABLE(); +} + +void +dmnsn_die_on_warnings(bool always_die) +{ + atomic_store(&dmnsn_always_die, always_die); +} + +dmnsn_fatal_error_fn * +dmnsn_get_fatal_error_fn(void) +{ + dmnsn_fatal_error_fn *fatal = atomic_load(&dmnsn_fatal); + return fatal; +} + +void +dmnsn_set_fatal_error_fn(dmnsn_fatal_error_fn *fatal) +{ + atomic_store(&dmnsn_fatal, fatal); +} + +static void +dmnsn_default_fatal_error_fn(void) +{ + if (dmnsn_is_main_thread()) { + exit(EXIT_FAILURE); + } else { + pthread_exit(NULL); + } +} diff --git a/libdimension/base/inline.c b/libdimension/base/inline.c new file mode 100644 index 0000000..b0622fe --- /dev/null +++ b/libdimension/base/inline.c @@ -0,0 +1,43 @@ +/************************************************************************* + * Copyright (C) 2009-2014 Tavian Barnes <tavianator@tavianator.com> * + * * + * This file is part of The Dimension Library. * + * * + * The Dimension Library is free software; you can redistribute it and/ * + * or modify it under the terms of the GNU Lesser General Public License * + * as published by the Free Software Foundation; either version 3 of the * + * License, or (at your option) any later version. * + * * + * The Dimension Library is distributed in the hope that it will be * + * useful, but WITHOUT ANY WARRANTY; without even the implied warranty * + * of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU * + * Lesser General Public License for more details. * + * * + * You should have received a copy of the GNU Lesser General Public * + * License along with this program. If not, see * + * <http://www.gnu.org/licenses/>. * + *************************************************************************/ + +/** + * @file + * Emit definitions of inline functions, if necessary. + */ + +// Set DMNSN_INLINE to produce definitions of inline functions, emitted here, +// if needed +#ifdef __cplusplus + // C++ inline semantics + #define DMNSN_INLINE inline +#elif __STDC_VERSION__ >= 199901L + // C99 inline semantics + #define DMNSN_INLINE +#elif defined(__GNUC__) + // GCC inline semantics + #define DMNSN_INLINE __inline__ +#else + // Unknown C - mark functions static and hope the compiler is smart enough to + // inline them + #define DMNSN_INLINE static +#endif + +#include "dimension.h" diff --git a/libdimension/base/malloc.c b/libdimension/base/malloc.c new file mode 100644 index 0000000..6aaf68c --- /dev/null +++ b/libdimension/base/malloc.c @@ -0,0 +1,94 @@ +/************************************************************************* + * Copyright (C) 2010-2014 Tavian Barnes <tavianator@tavianator.com> * + * * + * This file is part of The Dimension Library. * + * * + * The Dimension Library is free software; you can redistribute it and/ * + * or modify it under the terms of the GNU Lesser General Public License * + * as published by the Free Software Foundation; either version 3 of the * + * License, or (at your option) any later version. * + * * + * The Dimension Library is distributed in the hope that it will be * + * useful, but WITHOUT ANY WARRANTY; without even the implied warranty * + * of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU * + * Lesser General Public License for more details. * + * * + * You should have received a copy of the GNU Lesser General Public * + * License along with this program. If not, see * + * <http://www.gnu.org/licenses/>. * + *************************************************************************/ + +/** + * @file + * Dynamic memory. + */ + +#include "internal.h" +#include <stdlib.h> +#include <string.h> +#include <stdatomic.h> + +#if DMNSN_DEBUG +static atomic_size_t dmnsn_allocs = ATOMIC_VAR_INIT(0); +#endif + +void * +dmnsn_malloc(size_t size) +{ + void *ptr = malloc(size); + if (!ptr) { + dmnsn_error("Memory allocation failed."); + } + +#if DMNSN_DEBUG + atomic_fetch_add(&dmnsn_allocs, 1); +#endif + + return ptr; +} + +void * +dmnsn_realloc(void *ptr, size_t size) +{ +#if DMNSN_DEBUG + if (!ptr) { + atomic_fetch_add(&dmnsn_allocs, 1); + } +#endif + + ptr = realloc(ptr, size); + if (!ptr) { + dmnsn_error("Memory allocation failed."); + } + return ptr; +} + +char * +dmnsn_strdup(const char *s) +{ + char *copy = dmnsn_malloc(strlen(s) + 1); + strcpy(copy, s); + return copy; +} + +void +dmnsn_free(void *ptr) +{ +#if DMNSN_DEBUG + if (ptr) { + atomic_fetch_sub(&dmnsn_allocs, 1); + } +#endif + + free(ptr); +} + +#if DMNSN_DEBUG +DMNSN_LATE_DESTRUCTOR static void +dmnsn_leak_check(void) +{ + if (atomic_load_explicit(&dmnsn_allocs, memory_order_relaxed) > 0) { + dmnsn_warning("Leaking memory."); + } +} +#endif diff --git a/libdimension/base/pool.c b/libdimension/base/pool.c new file mode 100644 index 0000000..4bfdd7d --- /dev/null +++ b/libdimension/base/pool.c @@ -0,0 +1,177 @@ +/************************************************************************* + * Copyright (C) 2014 Tavian Barnes <tavianator@tavianator.com> * + * * + * This file is part of The Dimension Library. * + * * + * The Dimension Library is free software; you can redistribute it and/ * + * or modify it under the terms of the GNU Lesser General Public License * + * as published by the Free Software Foundation; either version 3 of the * + * License, or (at your option) any later version. * + * * + * The Dimension Library is distributed in the hope that it will be * + * useful, but WITHOUT ANY WARRANTY; without even the implied warranty * + * of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU * + * Lesser General Public License for more details. * + * * + * You should have received a copy of the GNU Lesser General Public * + * License along with this program. If not, see * + * <http://www.gnu.org/licenses/>. * + *************************************************************************/ + +/** + * @file + * Memory pool implementation. + */ + +#include "internal.h" +#include "internal/concurrency.h" +#include <stdatomic.h> + +/// Number of pointers per block, we want a block to fit in a single page. +#define DMNSN_POOL_BLOCK_SIZE (4096/sizeof(void *) - 4) +/// Number of pointers per tidy block +#define DMNSN_TIDY_BLOCK_SIZE ((4096 - 4*sizeof(void *))/(sizeof(void *) + sizeof(dmnsn_callback_fn *))) + +/// A single block in a thread-specific pool. +typedef struct dmnsn_pool_block { + /// Current index into allocs[]. + size_t i; + /// All allocations in the current block. + void *allocs[DMNSN_POOL_BLOCK_SIZE]; + /// Tail pointer to the previous block in the global chain. + struct dmnsn_pool_block *prev; +} dmnsn_pool_block; + +/// A single tidy block in a thread-specific pool. +typedef struct dmnsn_tidy_block { + /// Current index into allocs[]. + size_t i; + /// All allocations in the current block. + void *allocs[DMNSN_TIDY_BLOCK_SIZE]; + /// All cleanup callbacks in the current block. + dmnsn_callback_fn *cleanup_fns[DMNSN_TIDY_BLOCK_SIZE]; + /// Tail pointer to the previous tidy block in the global chain. + struct dmnsn_tidy_block *prev; +} dmnsn_tidy_block; + +/// dmnsn_pool implementation. +struct dmnsn_pool { + /// Thread-local regular block. + pthread_key_t thread_block; + /// Thread-local tidy block. + pthread_key_t thread_tidy_block; + + /// Global chain of regular blocks. + atomic(dmnsn_pool_block *) chain; + /// Global chain of tidy blocks. + atomic(dmnsn_tidy_block *) tidy_chain; +}; + +dmnsn_pool * +dmnsn_new_pool(void) +{ + dmnsn_pool *pool = DMNSN_MALLOC(dmnsn_pool); + + dmnsn_key_create(&pool->thread_block, NULL); + dmnsn_key_create(&pool->thread_tidy_block, NULL); + + atomic_store_explicit(&pool->chain, NULL, memory_order_relaxed); + atomic_store_explicit(&pool->tidy_chain, NULL, memory_order_relaxed); + + return pool; +} + +void * +dmnsn_palloc(dmnsn_pool *pool, size_t size) +{ + dmnsn_pool_block *old_block = pthread_getspecific(pool->thread_block); + + dmnsn_pool_block *new_block = old_block; + if (dmnsn_unlikely(!old_block || old_block->i == DMNSN_POOL_BLOCK_SIZE)) { + new_block = DMNSN_MALLOC(dmnsn_pool_block); + new_block->i = 0; + } + + void *result = dmnsn_malloc(size); + new_block->allocs[new_block->i++] = result; + + if (dmnsn_unlikely(new_block != old_block)) { + dmnsn_setspecific(pool->thread_block, new_block); + + // Atomically update pool->chain + dmnsn_pool_block *old_chain = atomic_exchange(&pool->chain, new_block); + new_block->prev = old_chain; + } + + return result; +} + +void * +dmnsn_palloc_tidy(dmnsn_pool *pool, size_t size, dmnsn_callback_fn *cleanup_fn) +{ + dmnsn_assert(cleanup_fn != NULL, "NULL cleanup_fn"); + + dmnsn_tidy_block *old_block = pthread_getspecific(pool->thread_tidy_block); + + dmnsn_tidy_block *new_block = old_block; + if (dmnsn_unlikely(!old_block || old_block->i == DMNSN_TIDY_BLOCK_SIZE)) { + new_block = DMNSN_MALLOC(dmnsn_tidy_block); + new_block->i = 0; + } + + void *result = dmnsn_malloc(size); + + size_t i = new_block->i; + new_block->allocs[i] = result; + new_block->cleanup_fns[i] = cleanup_fn; + ++new_block->i; + + if (dmnsn_unlikely(new_block != old_block)) { + dmnsn_setspecific(pool->thread_tidy_block, new_block); + + // Atomically update pool->tidy_chain + dmnsn_tidy_block *old_chain = atomic_exchange(&pool->tidy_chain, new_block); + new_block->prev = old_chain; + } + + return result; +} + +void +dmnsn_delete_pool(dmnsn_pool *pool) +{ + if (!pool) { + return; + } + + dmnsn_pool_block *block = atomic_load_explicit(&pool->chain, memory_order_relaxed); + while (block) { + // Free all the allocations + for (size_t i = block->i; i-- > 0;) { + dmnsn_free(block->allocs[i]); + } + + // Free the block itself and go to the previous one + dmnsn_pool_block *saved = block; + block = block->prev; + dmnsn_free(saved); + } + + dmnsn_tidy_block *tidy_block = atomic_load_explicit(&pool->tidy_chain, memory_order_relaxed); + while (tidy_block) { + // Free all the allocations + for (size_t i = tidy_block->i; i-- > 0;) { + void *ptr = tidy_block->allocs[i]; + tidy_block->cleanup_fns[i](ptr); + dmnsn_free(ptr); + } + + // Free the block itself and go to the previous one + dmnsn_tidy_block *saved = tidy_block; + tidy_block = tidy_block->prev; + dmnsn_free(saved); + } + + dmnsn_key_delete(pool->thread_tidy_block); + dmnsn_free(pool); +} diff --git a/libdimension/base/profile.c b/libdimension/base/profile.c new file mode 100644 index 0000000..87f27c1 --- /dev/null +++ b/libdimension/base/profile.c @@ -0,0 +1,168 @@ +/************************************************************************* + * Copyright (C) 2010-2011 Tavian Barnes <tavianator@tavianator.com> * + * * + * This file is part of The Dimension Library. * + * * + * The Dimension Library is free software; you can redistribute it and/ * + * or modify it under the terms of the GNU Lesser General Public License * + * as published by the Free Software Foundation; either version 3 of the * + * License, or (at your option) any later version. * + * * + * The Dimension Library is distributed in the hope that it will be * + * useful, but WITHOUT ANY WARRANTY; without even the implied warranty * + * of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU * + * Lesser General Public License for more details. * + * * + * You should have received a copy of the GNU Lesser General Public * + * License along with this program. If not, see * + * <http://www.gnu.org/licenses/>. * + *************************************************************************/ + +/** + * @file + * Branch profile accounting. + */ + +#include "internal.h" +#include "internal/concurrency.h" +#include <inttypes.h> +#include <pthread.h> +#include <stdio.h> + +/// Information on one predicted branch. +typedef struct { + char *location; + uint64_t predicted, branches; +} dmnsn_branch; + +/// Count of mispredicted branches. +static dmnsn_dictionary *dmnsn_profile = NULL; +/// Mutex which protects \c dmnsn_profile. +static pthread_mutex_t dmnsn_profile_mutex = PTHREAD_MUTEX_INITIALIZER; + +/// Thread-local count of mispredicted branches. +static pthread_key_t dmnsn_thread_profile; +/// Initialize the thread-specific pointer exactly once. +static pthread_once_t dmnsn_thread_profile_once = PTHREAD_ONCE_INIT; + +/// Add thread-specific profile data to the global counts. +static void +dmnsn_profile_globalize(void *ptr) +{ + dmnsn_branch *branch = ptr; + dmnsn_branch *global = dmnsn_dictionary_at(dmnsn_profile, branch->location); + if (global) { + global->predicted += branch->predicted; + global->branches += branch->branches; + dmnsn_free(branch->location); + } else { + dmnsn_dictionary_insert(dmnsn_profile, branch->location, branch); + } +} + +/// Destructor function for thread-specific profile data. +static void +dmnsn_delete_thread_profile(void *ptr) +{ + dmnsn_dictionary *thread_profile = ptr; + + dmnsn_lock_mutex(&dmnsn_profile_mutex); + dmnsn_dictionary_apply(thread_profile, dmnsn_profile_globalize); + dmnsn_unlock_mutex(&dmnsn_profile_mutex); + + dmnsn_delete_dictionary(thread_profile); +} + +/// Initialize the thread-specific pointer. +static void +dmnsn_initialize_thread_profile(void) +{ + dmnsn_key_create(&dmnsn_thread_profile, dmnsn_delete_thread_profile); + + dmnsn_lock_mutex(&dmnsn_profile_mutex); + dmnsn_profile = dmnsn_new_dictionary(sizeof(dmnsn_branch)); + dmnsn_unlock_mutex(&dmnsn_profile_mutex); +} + +/// Get the thread-specific profile data. +static dmnsn_dictionary * +dmnsn_get_thread_profile(void) +{ + dmnsn_once(&dmnsn_thread_profile_once, dmnsn_initialize_thread_profile); + return pthread_getspecific(dmnsn_thread_profile); +} + +/// Set the thread-specific profile data. +static void +dmnsn_set_thread_profile(dmnsn_dictionary *thread_profile) +{ + dmnsn_setspecific(dmnsn_thread_profile, thread_profile); +} + +bool +dmnsn_expect(bool result, bool expected, const char *func, const char *file, + unsigned int line) +{ + int size = snprintf(NULL, 0, "%s:%s:%u", file, func, line) + 1; + if (size < 1) { + dmnsn_error("sprintf() failed."); + } + + char key[size]; + if (snprintf(key, size, "%s:%s:%u", file, func, line) < 0) { + dmnsn_error("sprintf() failed."); + } + + dmnsn_dictionary *thread_profile = dmnsn_get_thread_profile(); + if (!thread_profile) { + thread_profile = dmnsn_new_dictionary(sizeof(dmnsn_branch)); + dmnsn_set_thread_profile(thread_profile); + } + + dmnsn_branch *branch = dmnsn_dictionary_at(thread_profile, key); + if (branch) { + ++branch->branches; + if (result == expected) { + ++branch->predicted; + } + } else { + dmnsn_branch new_branch = { + .location = dmnsn_strdup(key), + .predicted = (result == expected) ? 1 : 0, + .branches = 1 + }; + dmnsn_dictionary_insert(thread_profile, key, &new_branch); + } + + return result; +} + +static void +dmnsn_print_bad_prediction(void *ptr) +{ + dmnsn_branch *branch = ptr; + double rate = ((double)branch->predicted)/branch->branches; + if (rate < 0.75 || branch->branches < 100000) { + fprintf(stderr, + "Bad branch prediction: %s: %" PRIu64 "/%" PRIu64 " (%g%%)\n", + branch->location, branch->predicted, branch->branches, 100.0*rate); + } + + dmnsn_free(branch->location); +} + +DMNSN_DESTRUCTOR static void +dmnsn_print_bad_predictions(void) +{ + dmnsn_dictionary *thread_profile = dmnsn_get_thread_profile(); + if (thread_profile) { + dmnsn_delete_thread_profile(thread_profile); + dmnsn_set_thread_profile(NULL); + } + + dmnsn_lock_mutex(&dmnsn_profile_mutex); + dmnsn_dictionary_apply(dmnsn_profile, dmnsn_print_bad_prediction); + dmnsn_delete_dictionary(dmnsn_profile); + dmnsn_profile = NULL; + dmnsn_unlock_mutex(&dmnsn_profile_mutex); +} |