From e09104e6e294bed185227d5a2065d7a1877562b9 Mon Sep 17 00:00:00 2001 From: midipix Date: Sun, 12 Apr 2015 12:23:25 -0400 Subject: dalist: initial commit. --- Makefile.in | 14 ++ config.lzy | 28 ++++ configure | 115 +++++++++++++++++ dalist.lzy | 127 ++++++++++++++++++ include/dalist/dalist.h | 256 +++++++++++++++++++++++++++++++++++++ include/dalist/dalist_api.h | 32 +++++ include/dalist/dalist_env.h | 25 ++++ src/dalist.c | 297 +++++++++++++++++++++++++++++++++++++++++++ src/dalist_debug.c | 213 +++++++++++++++++++++++++++++++ src/dalist_impl.h | 43 +++++++ src/dalist_lib_entry_point.c | 12 ++ src/dalist_memfn.c | 267 ++++++++++++++++++++++++++++++++++++++ 12 files changed, 1429 insertions(+) create mode 100644 Makefile.in create mode 100644 config.lzy create mode 100755 configure create mode 100644 dalist.lzy create mode 100644 include/dalist/dalist.h create mode 100644 include/dalist/dalist_api.h create mode 100644 include/dalist/dalist_env.h create mode 100644 src/dalist.c create mode 100644 src/dalist_debug.c create mode 100644 src/dalist_impl.h create mode 100644 src/dalist_lib_entry_point.c create mode 100644 src/dalist_memfn.c diff --git a/Makefile.in b/Makefile.in new file mode 100644 index 0000000..b370cb0 --- /dev/null +++ b/Makefile.in @@ -0,0 +1,14 @@ +all: + ./lazy -x build + +install: + ./lazy -x build -e install + +clean: + rm -rf src + rm -rf lib + rm -f lazy + rm -f lazy.config.tag + rm -f lz_stack + rm -f *.objs + rm -rf *.lst diff --git a/config.lzy b/config.lzy new file mode 100644 index 0000000..4983d6b --- /dev/null +++ b/config.lzy @@ -0,0 +1,28 @@ +# package +lz_package=dalist + + +# toolchain +lz_default_target=x86_64-nt64-midipix +lz_default_arch=x86_64 +lz_default_compiler=gcc + + +# lazy +lz_cflags_cmdline= +lz_cxxflags_cmdline= +lz_ldflags_cmdline= + +lz_cflags_debug= +lz_cflags_release= + +lz_cflags_include_first= +lz_cflags_include_last= +lz_cflags_include_cmdline= +lz_cxxflags_include_cmdline= + +lz_exec_prefix= +lz_bindir= +lz_libdir= +lz_includedir= +lz_syslibdir= diff --git a/configure b/configure new file mode 100755 index 0000000..eb7a40c --- /dev/null +++ b/configure @@ -0,0 +1,115 @@ +#!/bin/sh + +# a simple configure-make wrapper for use in conjunction with the 'lazy' build script. +# 'lazy' is deviant, occasionally useful, and permissively licensed; get_lazy() below, +# then look for configure.template in the root directory. + +init_vars() +{ + lz_config_dir=`readlink -f $(dirname $0)` + lz_pwd=`pwd` + + if [ x"$lz_config" = x ]; then + . $lz_config_dir/config.lzy || exit 2 + else + . "$lz_config" || exit 2 + fi +} + + +error_msg() +{ + echo $@ >&2 +} + + +require_out_of_tree() +{ + if [ x"$lz_config_dir" = x"$lz_pwd" ]; then + error_msg "$lz_package: out-of-tree builds are required." + error_msg "please invoke configure again from a clean build directory." + exit 2 + fi + + return 0 +} + + +get_lazy() +{ + which lazy && lazy=`which lazy` && return 0 + + if ! [ -d slazy ]; then + git clone git://midipix.org/lazy slazy || exit 2 + fi + + lazy=$lz_pwd/slazy/lazy +} + + +lazy_approach() +{ + if [ x"$lz_prefix" = x ]; then + error_msg "prefix is required." + exit 2 + fi + + if [ x"$lz_arch" = x ]; then lz_arch=$lz_default_arch; fi + if [ x"$lz_target" = x ]; then lz_target=$lz_default_target; fi + if [ x"$lz_compiler" = x ]; then lz_compiler=$lz_default_compiler; fi + if [ x"$lz_compiler" = x ]; then lz_compiler=gcc; fi + + $lazy -x config $lz_debug \ + -t $lz_target \ + -a $lz_arch \ + -c $lz_compiler \ + -n $lz_package \ + -p $lz_config_dir \ + -f $lz_prefix \ + || exit 2 + +} + + +lazy_copy() +{ + cp "$lz_config_dir/Makefile.in" "$lz_pwd/Makefile" +} + + +for arg ; do + case "$arg" in + --help) usage + ;; + + --prefix=*) + lz_prefix=${arg#*=} + ;; + --host=*) + lz_target=${arg#*=} + ;; + --target=*) + lz_target=${arg#*=} + ;; + --compiler=*) + lz_compiler=${arg#*=} + ;; + --config=*) + lz_config=${arg#*=} + ;; + --debug) + lz_debug='-d' + ;; + *) + error_msg ${arg#}: "unsupported config argument." + exit 2 + ;; + esac +done + + +init_vars +require_out_of_tree +get_lazy +lazy_approach +lazy_copy diff --git a/dalist.lzy b/dalist.lzy new file mode 100644 index 0000000..1b82f7b --- /dev/null +++ b/dalist.lzy @@ -0,0 +1,127 @@ +lz_project_rules() +{ + lz_rules="all install xstatic install_xstatic" +} + +lz_project_definitions() +{ + dalist_lib_name=libdalist + dalist_so_name="$lz_build_dir/lib/$dalist_lib_name$lz_dylib_ext" + dalist_a_name="$lz_build_dir/lib/$dalist_lib_name$lz_stlib_ext" + dalist_so_def_name="$lz_build_dir/lib/$dalist_lib_name$lz_libdef_ext" + dalist_implib_name="$lz_build_dir/lib/$dalist_lib_name$lz_implib_ext" + + lz_cflags_common="-DMIDIPIX_FREESTANDING + -D__NT$lz_arch_bits \ + -UWIN32 -U_WIN32 -U__WIN32__ -UWIN64 -U_WIN64 -U__WIN64__ \ + -Werror=all -fno-builtin -ffreestanding" + + + # lz_cflags_extra="-Os -fno-stack-protector -fomit-frame-pointer -fno-unwind-tables -fno-asynchronous-unwind-tables" + + dalist_so_ldflags="-shared --image-base=0x320000 \ + --entry "$lz_default_underscore"dalist_lib_entry_point@12 \ + --exclude-all-symbols \ + --output-def $dalist_so_def_name \ + --out-implib $dalist_implib_name \ + --subsystem=windows" + + lz_cflags_include_common="-I$lz_project_dir/include" + + if [ "$MIDIPIX_ROOT"x != x ]; then + lz_cflags_include_common="$lz_cflags_include_common -I$MIDIPIX_ROOT/include" + fi + + dalist_so_obj_list=dalist.so.objs + dalist_so_src_list=dalist.so.src.lst + + dalist_a_obj_list=dalist.a.objs + dalist_a_src_list=dalist.a.src.lst +} + +dalist_shared() +{ + lz_src_dirs="src" + lz_cflags_step="-DDALIST_BUILD" + + if ! [ "$lz_pecoff_winnt"x = yesx ]; then + lz_cflags_step="$lz_cflags_step -fpic" + fi + + lz_compile "$dalist_so_obj_list" "$dalist_so_src_list" "$lz_dyobj_ext" + lz_link "$dalist_so_obj_list" "$dalist_so_src_list" "$dalist_so_name" \ + "$dalist_so_ldflags" \ + '' +} + + +dalist_static() +{ + lz_src_dirs="src" + + lz_compile "$dalist_a_obj_list" "$dalist_a_src_list" "$lz_stobj_ext" + lz_archive "$dalist_a_obj_list" "$dalist_a_src_list" "$dalist_a_name" +} + + +dalist_xstatic() +{ + lz_src_dirs="src" + lz_cflags_step="-DDALIST_BUILD" + + lz_compile "$dalist_a_obj_list" "$dalist_a_src_list" "$lz_stobj_ext" + lz_archive "$dalist_a_obj_list" "$dalist_a_src_list" "$dalist_a_name" +} + + +dalist_install_headers() +{ + lz_pushd $lz_project_dir + + cp -r -t $lz_prefix/include include/$lz_project_name + + lz_popd +} + + +dalist_install_shared() +{ + lz_pushd $lz_build_dir/lib + + cp -t $lz_prefix/lib $dalist_lib_name$lz_dylib_ext + cp -t $lz_prefix/lib $dalist_lib_name$lz_implib_ext + + lz_popd +} + + +dalist_install_static() +{ + lz_pushd $lz_build_dir/lib + + cp -t $lz_prefix/lib $dalist_lib_name$lz_stlib_ext + + lz_popd +} + +dalist_install_xstatic() +{ + lz_step dalist_xstatic + lz_step dalist_install_static +} + + +dalist_all() +{ + lz_step dalist_shared + lz_step dalist_static +} + + +dalist_install() +{ + lz_step dalist_all + lz_step dalist_install_shared + lz_step dalist_install_static + lz_step dalist_install_headers +} diff --git a/include/dalist/dalist.h b/include/dalist/dalist.h new file mode 100644 index 0000000..a478306 --- /dev/null +++ b/include/dalist/dalist.h @@ -0,0 +1,256 @@ +#ifndef DALIST_H +#define DALIST_H + +#include "dalist_api.h" + +#ifdef __cplusplus +extern "C" { +#endif + +/* dalist node types */ +enum dalist_node_types { + DALIST_NODE, + DALIST_NODE_EX, +}; + + +/* dalist caller-provided memory allocation methods */ +enum dalist_memfn { + DALIST_MEMFN_CUSTOM, + DALIST_MEMFN_MMAP, + DALIST_MEMFN_MALLOC, + DALIST_MEMFN_NT_ALLOCATE_VIRTUAL_MEMORY, +}; + + +/* dalist debug environments */ +enum dalist_dbgenv { + DALIST_DEBUG_ENV_POSIX, + DALIST_DEBUG_ENV_NT, +}; + + +/* dalist return values */ +#define DALIST_OK (0x0) +#define DALIST_EINTERNAL (0xD0000000) /* internal error */ +#define DALIST_EMEMFN (0xD0000001) /* memory allocation error */ +#define DALIST_EMEMBLOCK (0xD0000002) /* invalid memory block */ +#define DALIST_ELIST (0xD0000003) /* invalid list */ +#define DALIST_ENODE (0xD0000004) /* invalid node */ +#define DALIST_EPARAMMIX (0xD0000005) /* invalid parameter mix */ +#define DALIST_EKEYEXISTS (0xD0000006) /* key already exists */ +#define DALIST_ELISTNOTEMPTY (0xD0000007) /* null insertion point with non-empty list */ + +/* dalist debug return values */ +#define DALIST_EDEBUGSTRUCT (0xD0001000) /* invalid debug structure */ +#define DALIST_EDEBUGENV (0xD0001001) /* invalid debug environment */ +#define DALIST_EDEBUGSPRINTF (0xD0001002) /* invalid debug pointer to sprintf */ +#define DALIST_EDEBUGWRITE (0xD0001003) /* invalid debug pointer to write (posix) */ +#define DALIST_EDEBUGWRITEFILE (0xD0001004) /* invalid debug pointer to zw_write_file (nt) */ + + +/* dalist node flag bits */ +#define DALIST_NODE_TYPE_NONE (0x00u) +#define DALIST_NODE_TYPE_EXISTING (0x01u) +#define DALIST_NODE_TYPE_NEW (0x02u) +#define DALIST_NODE_TYPE_DELETED (0x04u) +#define DALIST_NODE_MEM_BLOCK_BASE (0x80u) + + +struct dalist_node { + struct dalist_node * prev; + struct dalist_node * next; + uintptr_t any; +}; + + +struct dalist { + struct dalist_node * head; + struct dalist_node * tail; +}; + + +struct dalist_node_ex { + struct dalist_node_ex * prev; + struct dalist_node_ex * next; + uintptr_t key; + uintptr_t flags; + uintptr_t dblock; +}; + + +struct dalist_debug; + +struct dalist_ex { + void * head; /************************************/ + void * tail; /* head, tail, free: */ + void * free; /* dalist_node when dblock_size is */ + uintptr_t * bookmarks; /* zero, dalist_node_ex otherwise. */ + size_t dblock_size; /* */ + size_t lblock_size; /* lblock_size: */ + void * memfn_ptr; /* used when memfn_method is mmap */ + enum dalist_memfn memfn_method; /* or nt_allocate_virtual_memory */ + int memfn_status; /* as the system call's alloc_size */ + int mmap_prot; /* argument. */ + int mmap_flags; /* */ + int mmap_fildes; /* */ + intptr_t mmap_offset; /************************************/ + struct dalist_debug * debug; + + struct dalist_info { + uintptr_t list_nodes; + uintptr_t free_nodes; + uintptr_t bookmark_from; + uintptr_t bookmark_to; + uintptr_t bookmark_key_min; + uintptr_t bookmark_key_max; + uintptr_t nodes_below_first_bookmark; + uintptr_t nodes_above_last_bookmark; + } info; +}; + + +/* signatures for caller-provided debug output functions */ +typedef int __cdecl dalist_sprintf(char * buffer, const char * format, ...); +typedef ssize_t __cdecl dalist_write(int fildes, const void *buf, size_t nbyte); +typedef int32_t __stdcall dalist_write_file( + void * hfile, + void * hevent, + void * apc_routine, + void * apc_context, + void * io_status_block, + void * buffer, + uint32_t bytes_sent, + int64_t * byte_offset, + uint32_t * key); + + +/* debug */ +struct dalist_debug { + enum dalist_dbgenv dbgenv; + dalist_sprintf * sprintf; /* required (all) */ + dalist_write * write; /* required (posix only) */ + dalist_write_file * zw_write_file; /* required (nt only) */ +}; + + +/* signatures for caller-provided memory allocation functions */ +typedef void * __cdecl dalist_memfn_mmap( + void * addr, + size_t alloc_size, + int prot, + int flags, + int fildes, + intptr_t offset); + + +typedef void * __cdecl dalist_memfn_malloc( + size_t alloc_size); + + +typedef int32_t __stdcall dalist_memfn_nt_allocvm( + void * hprocess, + void ** base_address, + uint32_t zero_bits, + size_t * alloc_size, + uint32_t alloc_type, + uint32_t protect); + + +/** + * dalist_memfn_custom: + * must return either DALIST_OK or DALIST_EMEMFN; + * may update the list's memfn_status member +**/ +typedef int __cdecl dalist_memfn_custom( + struct dalist_ex * dlist, + void ** addr, + size_t * alloc_size); + +dalist_api +int dalist_init(struct dalist * dlist); + +dalist_api +int dalist_init_ex( + struct dalist_ex * dlist, + size_t dblock_size, + size_t lblock_size, + void * memfn_ptr, + enum dalist_memfn memfn_method); + +dalist_api +int dalist_insert_before( + struct dalist * dlist, + struct dalist_node * lnode, + struct dalist_node * nnode); + +dalist_api +int dalist_insert_after( + struct dalist * dlist, + struct dalist_node * lnode, + struct dalist_node * nnode); + +dalist_api +int dalist_get_free_node( + struct dalist_ex * dlist, + void ** fnode); + +dalist_api +int dalist_deposit_free_node( + struct dalist_ex * dlist, + void * fnode); + +dalist_api +int dalist_deposit_memory_block( + struct dalist_ex * dlist, + void * addr, + size_t alloc_size); + +dalist_api +int dalist_unlink_node( + struct dalist * dlist, + struct dalist_node * node); + +dalist_api +int dalist_unlink_node_ex( + struct dalist_ex * dlist, + struct dalist_node_ex * node); + +dalist_api +int dalist_discard_node( + struct dalist_ex * dlist, + struct dalist_node_ex * node); + +dalist_api +int dalist_get_node_by_key( + struct dalist_ex * dlist, + struct dalist_node_ex **node, + uintptr_t key, + uintptr_t get_flags, + uintptr_t * node_flags); + +dalist_api +int dalist_insert_node_by_key( + struct dalist_ex * dlist, + struct dalist_node_ex * node); + +/* debug routines */ +dalist_api +int dalist_debug_setup( + struct dalist_ex * dlist, + struct dalist_debug * dlist_debug, + enum dalist_dbgenv dbgenv, + dalist_sprintf * pfn_sprintf, + dalist_write * pfn_write, + dalist_write_file * pfn_write_file); + +dalist_api +int dalist_debug_print( + struct dalist_ex * dlist, + intptr_t fildes_or_hfile); + + +#ifdef __cplusplus +} +#endif +#endif diff --git a/include/dalist/dalist_api.h b/include/dalist/dalist_api.h new file mode 100644 index 0000000..b120527 --- /dev/null +++ b/include/dalist/dalist_api.h @@ -0,0 +1,32 @@ +#ifndef DALIST_API_H +#define DALIST_API_H + +/* host type (posix-libc/free-standing) */ +#include "dalist_env.h" + +/* dalist_export */ +#if defined(__attr_export__) +#define dalist_export __attr_export__ +#else +#define dalist_export +#endif + +/* dalist_import */ +#if defined(__attr_import__) +#define dalist_import __attr_import__ +#else +#define dalist_import +#endif + +/* dalist_api */ +#if defined (DALIST_BUILD) +#define dalist_api dalist_export +#elif defined (DALIST_SHARED) +#define dalist_api dalist_import +#elif defined (DALIST_STATIC) +#define dalist_api +#else +#define dalist_api +#endif + +#endif diff --git a/include/dalist/dalist_env.h b/include/dalist/dalist_env.h new file mode 100644 index 0000000..2f2b57a --- /dev/null +++ b/include/dalist/dalist_env.h @@ -0,0 +1,25 @@ +#ifndef DALIST_ENV_H +#define DALIST_ENV_H + +#if defined (MIDIPIX_FREESTANDING) + +#include + +#else + +#include +#include +#include +#include + +#ifndef __cdecl +#define __cdecl +#endif + +#ifndef __stdcall +#define __stdcall +#endif + +#endif + +#endif diff --git a/src/dalist.c b/src/dalist.c new file mode 100644 index 0000000..dffac64 --- /dev/null +++ b/src/dalist.c @@ -0,0 +1,297 @@ +/*****************************************************************************/ +/* dalist: a zero-dependency book-keeping library */ +/* Copyright (C) 2013,2014,2015 Z. Gilboa */ +/* Released under GPLv2 and GPLv3; see COPYING.DALIST. */ +/*****************************************************************************/ + +#include +#include "dalist_impl.h" + + +dalist_api +int dalist_init(struct dalist * dlist) +{ + dlist->head = dlist->tail = 0; + return DALIST_OK; +} + + +dalist_api +int dalist_init_ex( + struct dalist_ex * dlist, + size_t dblock_size, + size_t lblock_size, + void * memfn_ptr, + enum dalist_memfn memfn_method) + +{ + if (!dlist) + return DALIST_ELIST; + + dlist->head = dlist->tail = 0; + + dlist->dblock_size = dblock_size; + dlist->lblock_size = lblock_size; + + dlist->memfn_ptr = memfn_ptr; + dlist->memfn_method = memfn_method; + + dlist->free = 0; + dlist->bookmarks = 0; + dlist->memfn_status = 0; + + dlist->info.list_nodes = 0; + dlist->info.free_nodes = 0; + + dlist->info.bookmark_from = 0; + dlist->info.bookmark_to = 0; + + dlist->info.bookmark_key_min = 0; + dlist->info.bookmark_key_max = 0; + + dlist->info.nodes_below_first_bookmark = 0; + dlist->info.nodes_above_last_bookmark = 0; + + return DALIST_OK; +} + + +dalist_api +int dalist_insert_before( + struct dalist * dlist, + struct dalist_node * lnode, + struct dalist_node * nnode) +{ + if (!dlist) + return DALIST_ELIST; + + if (lnode) { + /* insert before an existing node */ + nnode->prev = lnode->prev; + nnode->next = lnode; + lnode->prev = nnode; + + if (nnode->prev) + nnode->prev->next = nnode; + else + dlist->head = nnode; + } else { + if (dlist->head) + return DALIST_ENODE; + else { + /* nnode is the new head/tail */ + nnode->next = 0; + nnode->prev = 0; + dlist->head = nnode; + dlist->tail = nnode; + } + } + + return DALIST_OK; +} + + +dalist_api +int dalist_insert_after( + struct dalist * dlist, + struct dalist_node * lnode, + struct dalist_node * nnode) +{ + if (!dlist) + return DALIST_ELIST; + + if (lnode) { + /* insert after an existing node */ + nnode->prev = lnode; + nnode->next = lnode->next; + lnode->next = nnode; + + if (nnode->next) + nnode->next->prev = nnode; + else + dlist->tail = nnode; + } else { + if (dlist->head) + return DALIST_ENODE; + else { + /* nnode is the new head/tail */ + nnode->next = 0; + nnode->prev = 0; + dlist->head = nnode; + dlist->tail = nnode; + } + } + + return DALIST_OK; +} + + +dalist_api +int dalist_unlink_node( + struct dalist * dlist, + struct dalist_node * node) +{ + struct dalist_node * prev; + struct dalist_node * next; + + if (!dlist) + return DALIST_ELIST; + else if (!node) + return DALIST_ENODE; + + prev = node->prev; + next = node->next; + + if (prev) + prev->next = next; + else + dlist->head = next; + + if (next) + next->prev = prev; + else + dlist->tail = prev; + + return DALIST_OK; +} + + +dalist_api +int dalist_unlink_node_ex( + struct dalist_ex * dlist, + struct dalist_node_ex * node) +{ + int ret; + + ret = dalist_unlink_node( + (struct dalist *)dlist, + (struct dalist_node *)node); + + if (ret == DALIST_OK) + dlist->info.list_nodes--; + + return ret; +} + + +dalist_api +int dalist_discard_node( + struct dalist_ex * dlist, + struct dalist_node_ex * node) +{ + int ret; + + ret = dalist_unlink_node_ex(dlist,node); + + if (ret == DALIST_OK) + ret = dalist_deposit_free_node(dlist,node); + + return ret; +} + + +dalist_api +int dalist_get_node_by_key( + struct dalist_ex * dlist, + struct dalist_node_ex **node, + uintptr_t key, + uintptr_t get_flags, + uintptr_t * node_flags) +{ + struct dalist_node_ex * cnode; + struct dalist_node_ex * nnode; + uintptr_t flags; + int ret; + + if (!dlist) return DALIST_ELIST; + + /* init */ + if (!node_flags) + node_flags = &flags; + + *node = 0; + *node_flags = DALIST_NODE_TYPE_NONE; + + /* traverse */ + cnode = (struct dalist_node_ex *)dlist->head; + + while (cnode && (cnode->key < key)) + cnode = cnode->next; + + /* return matching node */ + if (cnode && (cnode->key == key)) { + *node_flags = DALIST_NODE_TYPE_EXISTING; + *node = cnode; + return DALIST_OK; + } + + /* key not found, possibly a new node */ + if (get_flags & DALIST_NODE_TYPE_NEW) { + ret = dalist_get_free_node(dlist, (void **)&nnode); + if (ret) return ret; + + nnode->key = key; + + if (cnode) + ret = dalist_insert_before( + (struct dalist *)dlist, + (struct dalist_node *)cnode, + (struct dalist_node *)nnode); + else + ret = dalist_insert_after( + (struct dalist *)dlist, + (struct dalist_node *)dlist->tail, + (struct dalist_node *)nnode); + + if (ret == DALIST_OK) { + *node = nnode; + dlist->info.list_nodes++; + *node_flags = DALIST_NODE_TYPE_NEW; + } else + dalist_deposit_free_node(dlist,nnode); + } else + ret = DALIST_OK; + + return ret; +} + + +dalist_api +int dalist_insert_node_by_key( + struct dalist_ex * dlist, + struct dalist_node_ex * node) +{ + struct dalist_node_ex * cnode; + int ret; + + /* verify dlist */ + if (!dlist) + return DALIST_ELIST; + + /* traverse */ + cnode = (struct dalist_node_ex *)dlist->head; + + while (cnode && (cnode->key < node->key)) + cnode = cnode->next; + + /* verify that node-> is unique */ + if (cnode && (cnode->key == node->key)) + return DALIST_EKEYEXISTS; + + /* key is unique, add a new node */ + if (cnode) + ret = dalist_insert_before( + (struct dalist *)dlist, + (struct dalist_node *)cnode, + (struct dalist_node *)node); + else + ret = dalist_insert_after( + (struct dalist *)dlist, + (struct dalist_node *)dlist->tail, + (struct dalist_node *)node); + + if (ret == DALIST_OK) + dlist->info.list_nodes++; + + return ret; +} diff --git a/src/dalist_debug.c b/src/dalist_debug.c new file mode 100644 index 0000000..4461286 --- /dev/null +++ b/src/dalist_debug.c @@ -0,0 +1,213 @@ +/*****************************************************************************/ +/* dalist: a zero-dependency book-keeping library */ +/* Copyright (C) 2013,2014,2015 Z. Gilboa */ +/* Released under GPLv2 and GPLv3; see COPYING.DALIST. */ +/*****************************************************************************/ + +#include +#include "dalist_impl.h" + +dalist_api +int dalist_debug_setup( + struct dalist_ex * dlist, + struct dalist_debug * dlist_debug, + enum dalist_dbgenv dbgenv, + dalist_sprintf * pfn_sprintf, + dalist_write * pfn_write, + dalist_write_file * pfn_write_file) +{ + if (dlist) + /* in case we fail */ + dlist->debug = 0; + else + return DALIST_ELIST; + + if (!dlist_debug) + return DALIST_EDEBUGSTRUCT; + else if (!pfn_sprintf) + return DALIST_EDEBUGSPRINTF; + + switch (dbgenv) { + case DALIST_DEBUG_ENV_POSIX: + if (!pfn_write) + return DALIST_EDEBUGWRITE; + break; + + case DALIST_DEBUG_ENV_NT: + if (!pfn_write_file) + return DALIST_EDEBUGWRITEFILE; + break; + + default: + return DALIST_EDEBUGENV; + } + + dlist_debug->dbgenv = dbgenv; + dlist_debug->sprintf = pfn_sprintf; + dlist_debug->write = pfn_write; + dlist_debug->zw_write_file = pfn_write_file; + + dlist->debug = dlist_debug; + + return DALIST_OK; +} + + +static const char dalist_fmt_header_32[] = + "dlist:\t\t0x%08x\n" + "dlist->head:\t0x%08x\n" + "dlist->tail:\t0x%08x\n\n"; + +static const char dalist_fmt_header_64[] = + "dlist:\t\t0x%016x\n" + "dlist->head:\t0x%016x\n" + "dlist->tail:\t0x%016x\n\n"; + +static const char dalist_fmt_node_32[] = + "node: 0x%08x\t" + "prev: 0x%08x\t" + "next: 0x%08x\t" + "any: 0x%08x\t\n"; + +static const char dalist_fmt_node_64[] = + "node: 0x%016x\t" + "prev: 0x%016x\t" + "next: 0x%016x\t" + "any: 0x%016x\t\n"; + + +static int dalist_dbg_write_posix( + struct dalist_ex * dlist, + intptr_t fildes_or_hfile, + const void * buf, + size_t nbyte) +{ + int fildes; + dalist_write * pfn_write; + ssize_t bytes_written; + + fildes = (int)fildes_or_hfile; + pfn_write = (dalist_write *)dlist->debug->write; + + bytes_written = pfn_write(fildes,buf,nbyte); + + if (bytes_written == nbyte) + return DALIST_OK; + else + return DALIST_EDEBUGENV; +} + + +static int dalist_dbg_write_nt( + struct dalist_ex * dlist, + intptr_t fildes_or_hfile, + const void * buf, + size_t nbyte) +{ + void * hfile; + dalist_iosb iosb; + dalist_write_file * pfn_write_file; + + hfile = (void *)fildes_or_hfile; + pfn_write_file = (dalist_write_file *)dlist->debug->zw_write_file; + + return pfn_write_file( + hfile, + (void *)0, + (void *)0, + (void *)0, + &iosb, + (void *)buf, + (uint32_t)nbyte, + (int64_t *)0, + (uint32_t *)0); + + if (iosb.info == nbyte) + return DALIST_OK; + else + return DALIST_EDEBUGENV; +} + + +dalist_api +int dalist_debug_print( + struct dalist_ex * dlist, + intptr_t fildes_or_hfile) +{ + const char * fmt_header; + const char * fmt_node; + char dbg_buf[128]; + intptr_t nbyte; + + int status; + struct dalist_node * node; + dalist_sprintf * dbg_sprintf; + dalist_dbg_write * dbg_write; + + if (!dlist) + return DALIST_ELIST; + else if (!dlist->debug) + return DALIST_EDEBUGENV; + + /* initial setup */ + dbg_sprintf = (dalist_sprintf *)dlist->debug->sprintf; + + if (sizeof(size_t) == 4) { + fmt_header = (char *)dalist_fmt_header_32; + fmt_node = (char *)dalist_fmt_node_32; + } else if (sizeof(size_t) == 8) { + fmt_header = (char *)dalist_fmt_header_64; + fmt_node = (char *)dalist_fmt_node_64; + } else + return DALIST_EDEBUGENV; + + if (dlist->debug->dbgenv == DALIST_DEBUG_ENV_POSIX) + dbg_write = dalist_dbg_write_posix; + else if (dlist->debug->dbgenv == DALIST_DEBUG_ENV_NT) + dbg_write = dalist_dbg_write_nt; + else + dbg_write = 0; + + if ((!dbg_sprintf) || (!dbg_write)) + return DALIST_EDEBUGENV; + + /* print list header */ + nbyte = dbg_sprintf((char *)dbg_buf,fmt_header,dlist,dlist->head,dlist->tail); + + if (nbyte < 0) + return DALIST_EDEBUGENV; + + status = dbg_write(dlist,fildes_or_hfile,dbg_buf,nbyte); + + if (status != NT_STATUS_SUCCESS) + return DALIST_EDEBUGENV; + + /* print node information */ + status = DALIST_OK; + node = (struct dalist_node *)dlist->head; + + while (node && (status == DALIST_OK)) { + /* create output line */ + nbyte = dbg_sprintf( + (char *)dbg_buf, + fmt_node, + node, + node->prev, + node->next, + node->any); + + if (nbyte < 0) + return DALIST_EDEBUGENV; + + /* write output line */ + status = dbg_write( + dlist, + fildes_or_hfile, + dbg_buf, + nbyte); + + node = node->next; + } + + return DALIST_OK; +} diff --git a/src/dalist_impl.h b/src/dalist_impl.h new file mode 100644 index 0000000..97cef11 --- /dev/null +++ b/src/dalist_impl.h @@ -0,0 +1,43 @@ +#include + +/* internal synonyms and prototypes */ +typedef dalist_memfn_custom memfn_custom; +typedef dalist_memfn_mmap memfn_mmap; +typedef dalist_memfn_malloc memfn_malloc; +typedef dalist_memfn_nt_allocvm memfn_allocvm; + + +/* memfn_allocvm */ +#define NT_STATUS_SUCCESS 0 +#define NT_CURRENT_PROCESS_HANDLE (void *)(uintptr_t)-1 +#define NT_PAGE_READWRITE (0x0004u) +#define NT_MEM_COMMIT (0x1000u) +#define NT_MEM_RESERVE (0x2000u) +#define NT_MEM_DECOMMIT (0x4000u) +#define NT_MEM_RELEASE (0x8000u) + +/* host environment */ +#if defined (MIDIPIX_FREESTANDING) +#define dalist_errno(x) x +#define PROT_READ 1 +#define PROT_WRITE 2 +#define MAP_ANON 0x20 +#define MAP_SHARED 0x01 +#else +#define dalist_errno(x) errno +#endif + +typedef struct _dalist_io_status_block { + union { + int32_t status; + void * pointer; + }; + intptr_t info; +} dalist_io_status_block, dalist_iosb; + + +typedef int dalist_dbg_write( + struct dalist_ex * dlist, + intptr_t fildes_or_hfile, + const void * buf, + size_t nbyte); diff --git a/src/dalist_lib_entry_point.c b/src/dalist_lib_entry_point.c new file mode 100644 index 0000000..d4124ed --- /dev/null +++ b/src/dalist_lib_entry_point.c @@ -0,0 +1,12 @@ +#ifdef MIDIPIX_FREESTANDING + +#include + +int __stdcall dalist_lib_entry_point( + void * hinstance, + uint32_t reason, + void * reserved) +{ + return 1; +} +#endif diff --git a/src/dalist_memfn.c b/src/dalist_memfn.c new file mode 100644 index 0000000..e1fa9f0 --- /dev/null +++ b/src/dalist_memfn.c @@ -0,0 +1,267 @@ +/*****************************************************************************/ +/* dalist: a zero-dependency book-keeping library */ +/* Copyright (C) 2013,2014,2015 Z. Gilboa */ +/* Released under GPLv2 and GPLv3; see COPYING.DALIST. */ +/*****************************************************************************/ + +#include +#include "dalist_impl.h" + +/* private prototypes */ +static void * dalist_alloc(struct dalist_ex * dlist); + +static int dalist_memfn_internal( + struct dalist_ex * dlist, + void ** addr, + size_t * alloc_size); + + +dalist_api +int dalist_get_free_node( + struct dalist_ex * dlist, + void ** fnode) +{ + int ret; + struct dalist_node * nfree; + + /* in case we fail */ + *fnode = (void *)0; + + if (dlist->free) + /* allocation is not needed */ + nfree = (struct dalist_node *)dlist->free; + else + nfree = (struct dalist_node *)dalist_alloc(dlist); + + if (nfree) { + *fnode = nfree; + dlist->free = nfree->next; + + if (nfree->next) /* new head of dlist->free */ + nfree->next->prev = 0; + + /* bookkeeping */ + dlist->info.free_nodes--; + + /* and for good measure */ + nfree->prev = nfree->next = 0; + ret = DALIST_OK; + } else + ret = DALIST_EMEMFN; + + return ret; +} + + +dalist_api +int dalist_deposit_free_node( + struct dalist_ex * dlist, + void * fnode) +{ + int ret; + struct dalist_node * nfree; + + if (fnode) { + nfree = (struct dalist_node *)fnode; + nfree->next = (struct dalist_node *)dlist->free; + + /* fnode is now the head free node */ + nfree->prev = 0; + dlist->free = fnode; + + /* bookkeeping */ + dlist->info.free_nodes++; + ret = DALIST_OK; + } else { + ret = DALIST_ENODE; + } + + return ret; +} + + +dalist_api +int dalist_deposit_memory_block( + struct dalist_ex * dlist, + void * addr, + size_t alloc_size) +{ + struct dalist_node * fnode; + struct dalist_node * fnode_next; + char * naddr; + char * naddr_next; + char * naddr_upper; + size_t node_size; + + /* node_size: before alignment */ + if (dlist->dblock_size == 0) + node_size = sizeof(struct dalist_node); + else + node_size = (size_t)&((struct dalist_node_ex *)0)->dblock + + dlist->dblock_size; + + /* node_size: after alignment */ + node_size += sizeof(uintptr_t)-1; + node_size |= sizeof(uintptr_t)-1; + node_size ^= sizeof(uintptr_t)-1; + + /* validate block size */ + if (alloc_size < node_size) + return DALIST_EMEMBLOCK; + + /* marks */ + naddr = (char *)addr; + naddr_next = naddr + node_size; + naddr_upper = naddr + alloc_size; + + /* chain of free nodes */ + while ((naddr_next + node_size) < naddr_upper) { + fnode = (struct dalist_node *)naddr; + fnode_next = (struct dalist_node *)naddr_next; + + fnode->next = fnode_next; + fnode_next->prev = fnode; + + naddr += node_size; + naddr_next += node_size; + } + + /* free nodes block: head and tail */ + fnode = (struct dalist_node *)addr; + fnode_next = (struct dalist_node *)naddr; + + if (dlist->free) { + /* link with pre-allocated free nodes */ + fnode_next->next = (struct dalist_node *)dlist->free; + ((struct dalist_node *)dlist->free)->prev = fnode_next; + } else { + /* no pre-allocated free nodes */ + fnode_next->next = 0; + } + + /* fnode is now the head free node */ + fnode->prev = 0; + dlist->free = fnode; + + /* bookkeeping */ + dlist->info.free_nodes += (alloc_size / node_size); + + return DALIST_OK; +} + + +static void * __cdecl dalist_alloc(struct dalist_ex * dlist) +{ + int ret; + void * addr; + size_t alloc_size; + memfn_custom * pmemfn; + struct dalist_node * fnode; + + /* pmemfn */ + if (dlist->memfn_method == DALIST_MEMFN_CUSTOM) + pmemfn = (dalist_memfn_custom *)dlist->memfn_ptr; + else + pmemfn = dalist_memfn_internal; + + /* allocate: try */ + fnode = 0; + ret = pmemfn(dlist,&addr,&alloc_size); + + /* allocate: verify */ + if (ret == DALIST_OK) { + if (dlist->memfn_method == DALIST_MEMFN_MALLOC) + fnode = (struct dalist_node *)addr; + else if (dalist_deposit_memory_block( + dlist, + addr, + alloc_size) == DALIST_OK) + fnode = (struct dalist_node *)dlist->free; + } + + return fnode; +} + + +static int __cdecl dalist_memfn_internal( + struct dalist_ex * dlist, + void ** address, + size_t * alloc_size) +{ + int ret; + void * addr; + size_t size; + + memfn_mmap * pfn_mmap; + memfn_malloc * pfn_malloc; + memfn_allocvm * pfn_allocvm; + + switch (dlist->memfn_method) { + case DALIST_MEMFN_MALLOC: + if (dlist->dblock_size == 0) + size = sizeof(struct dalist_node); + else + size = (size_t)((struct dalist_node_ex *)0)->dblock + + dlist->dblock_size; + + pfn_malloc = (memfn_malloc * )dlist->memfn_ptr; + addr = pfn_malloc(size); + + if (addr) { + *address = addr; + *alloc_size = size; + ret = dlist->memfn_status = DALIST_OK; + } else { + ret = DALIST_EMEMFN; + dlist->memfn_status = dalist_errno(ret); + } + break; + + case DALIST_MEMFN_MMAP: + pfn_mmap = (memfn_mmap * )dlist->memfn_ptr; + + addr = pfn_mmap( + (void *)0, + dlist->lblock_size, + PROT_READ | PROT_WRITE, + MAP_ANON | MAP_SHARED, + 0,0); + + if (addr) { + *address = addr; + *alloc_size = dlist->lblock_size; + ret = dlist->memfn_status = DALIST_OK; + } else { + ret = DALIST_EMEMFN; + dlist->memfn_status = dalist_errno(ret); + } + break; + + case DALIST_MEMFN_NT_ALLOCATE_VIRTUAL_MEMORY: + addr = (void *)0; + size = dlist->lblock_size; + pfn_allocvm = (memfn_allocvm * )dlist->memfn_ptr; + + dlist->memfn_status = pfn_allocvm( + NT_CURRENT_PROCESS_HANDLE, + &addr, + 0, + &size, + NT_MEM_COMMIT, + NT_PAGE_READWRITE); + + if (dlist->memfn_status == NT_STATUS_SUCCESS) { + *address = addr; + *alloc_size = size; + ret = DALIST_OK; + } else { + ret = DALIST_EMEMFN; + } + break; + default: + ret = DALIST_EINTERNAL; + break; + } + + return ret; +} -- cgit v1.2.3