diff options
author | Brad Bishop <bradleyb@us.ibm.com> | 2014-06-30 22:10:16 -0500 |
---|---|---|
committer | Patrick Williams <iawillia@us.ibm.com> | 2014-07-02 22:49:29 -0500 |
commit | bf4630076762d9c20c16c80c1c791f352b046dd1 (patch) | |
tree | efc67bad010a28fd1abf5aeeefda2a969514fd97 /clib/src | |
download | ffs-bf4630076762d9c20c16c80c1c791f352b046dd1.tar.gz ffs-bf4630076762d9c20c16c80c1c791f352b046dd1.zip |
Port FFS tools over from Building Block repository.
Diffstat (limited to 'clib/src')
-rw-r--r-- | clib/src/array.c | 490 | ||||
-rw-r--r-- | clib/src/array_iter.c | 180 | ||||
-rw-r--r-- | clib/src/checksum.c | 43 | ||||
-rw-r--r-- | clib/src/crc32.c | 150 | ||||
-rw-r--r-- | clib/src/crc32_main.c | 76 | ||||
-rw-r--r-- | clib/src/db.c | 400 | ||||
-rw-r--r-- | clib/src/dispatch.c | 155 | ||||
-rw-r--r-- | clib/src/ecc.c | 456 | ||||
-rw-r--r-- | clib/src/err.c | 208 | ||||
-rw-r--r-- | clib/src/exception.c | 145 | ||||
-rw-r--r-- | clib/src/heap.c | 152 | ||||
-rw-r--r-- | clib/src/list.c | 49 | ||||
-rw-r--r-- | clib/src/list_iter.c | 139 | ||||
-rw-r--r-- | clib/src/memory_leak_detection.c | 1277 | ||||
-rw-r--r-- | clib/src/misc.c | 234 | ||||
-rw-r--r-- | clib/src/mq.c | 208 | ||||
-rw-r--r-- | clib/src/signal.c | 135 | ||||
-rw-r--r-- | clib/src/slab.c | 388 | ||||
-rw-r--r-- | clib/src/table.c | 679 | ||||
-rw-r--r-- | clib/src/table_iter.c | 138 | ||||
-rw-r--r-- | clib/src/timer.c | 133 | ||||
-rw-r--r-- | clib/src/trace_indent.c | 185 | ||||
-rw-r--r-- | clib/src/tree.c | 630 | ||||
-rw-r--r-- | clib/src/tree_iter.c | 137 | ||||
-rw-r--r-- | clib/src/value.c | 143 | ||||
-rw-r--r-- | clib/src/vector.c | 662 | ||||
-rw-r--r-- | clib/src/vector_iter.c | 177 | ||||
-rw-r--r-- | clib/src/watch.c | 135 |
28 files changed, 7904 insertions, 0 deletions
diff --git a/clib/src/array.c b/clib/src/array.c new file mode 100644 index 0000000..55e261c --- /dev/null +++ b/clib/src/array.c @@ -0,0 +1,490 @@ +/* + * Copyright (c) International Business Machines Corp., 2014 + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program 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 General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + */ + +/* + * File: array.c + * Author: Shaun Wetzstein <shaun@us.ibm.com> + * Descr: Sparse Array + * Note: + * Date: 08/29/10 + */ + +#include <unistd.h> +#include <stdarg.h> +#include <stdlib.h> +#include <malloc.h> +#include <stdint.h> +#include <stdio.h> +#include <string.h> +#include <errno.h> +#include <limits.h> + +#include "assert.h" +#include "misc.h" +#include "hash.h" +#include "array.h" +#include "slab.h" +#include "mqueue.h" +#include "tree.h" +#include "tree_iter.h" +#include "bb_trace.h" +#include "memory_leak_detection.h" + +/*! @cond */ +#define ARRAY_ELEM_SIZE_MIN 1 +#define ARRAY_ELEM_NUM_MIN 64 + +#define ARRAY_MAGIC 0x48444152 +#define ARRAY_NODE_MAGIC 0x4E444152 +/*! @endcond */ + +/* ======================================================================= */ + +/*! @cond */ +typedef struct array_node array_node_t; + +struct array_node { + uint32_t magic; + uint32_t address; + + tree_node_t node; +}; + +const char *__array_msg[] = { + "array: unexpected NULL pointer", + "array: unexpected cache and/or alloc size", + "array: out-of-memory", + "array: uninitialized array element", + "array: unexpected magic number", + "array: unexpected NULL message channel", +}; + +#define ARRAY_NULL (__array_msg[0]) +#define ARRAY_SIZE (__array_msg[1]) +#define ARRAY_OOM (__array_msg[2]) +#define ARRAY_UNINIT_ELEM (__array_msg[3]) +#define ARRAY_MAGIC_CHECK (__array_msg[4]) +#define ARRAY_MQ_NULL (__array_msg[5]) +/*! @endcond */ + +/* ======================================================================= */ + +#define __index_to_page(i,s) \ +({ \ + typeof(i) _p = ((i) / (s)); \ + (i) >= 0 ? _p :_p - 1; \ +}) + +#define __index_to_page_hashed(i,s) \ +({ \ + typeof(i) _h = int32_hash1(__index_to_page((i),(s))); \ + _h; \ +}) + +#define __page_to_low(p,s) \ +({ \ + typeof(p) _l = (p) * (s); \ + (p) >= 0 ? _l : _l - 1; \ +}) + +#define __page_to_high(p,s) \ +({ \ + typeof(p) _h = (p) * (s) + (s) - (typeof(p))1; \ + _h; \ +}) + +/* ======================================================================= */ + +static array_node_t *__array_grow(array_t * self, size_t idx) +{ + if (unlikely(self == NULL)) + throw_unexpected(ARRAY_NULL); + + array_node_t *node = NULL; + switch (POSIX_MEMALIGN + ((void **)&node, self->page_size, self->page_size)) { + case EINVAL: + throw_unexpected(ARRAY_SIZE); + case ENOMEM: + throw_unexpected(ARRAY_OOM); + } + assert(node != NULL); + + node->magic = ARRAY_NODE_MAGIC; + node->address = (uint32_t) node; + + const void *key = + (const void *)__index_to_page_hashed(idx, self->elem_num); + tree_node_init(&node->node, key); + + splay_insert(&self->tree, &node->node); + self->pages++; + + size_t page = __index_to_page(idx, self->elem_num); + + self->low = min(self->low, __page_to_low(page, self->elem_num)); + self->high = max(self->high, __page_to_high(page, self->elem_num)); + + return node; +} + +static int __array_compare(const int i1, const int i2) +{ + return i1 - i2; +} + +void array_init(array_t * self, size_t elem_size, size_t elem_num) +{ + if (unlikely(self == NULL)) + throw_unexpected(ARRAY_NULL); + + self->magic = ARRAY_MAGIC; + self->high = 0; + self->low = UINT32_MAX; + self->size = 0; + self->pages = 0; + + self->elem_size = max(elem_size, ARRAY_ELEM_SIZE_MIN); + self->elem_num = max(elem_num, ARRAY_ELEM_NUM_MIN); + + self->page_size = __round_pow2(elem_size * elem_num); + + self->map_size = align(elem_num / CHAR_BIT, sizeof(uint32_t)); + + self->elem_num = + (self->page_size - sizeof(array_node_t) - + self->map_size) / self->elem_size; + + tree_init(&self->tree, (compare_f) __array_compare); +} + +static void __array_delete(array_t * self) +{ + if (self != NULL) { + while (self->tree.root != NULL) { + array_node_t *node; + node = + container_of(tree_root(&self->tree), array_node_t, + node); + splay_remove(&self->tree, &node->node); + FREE(node); + } + tree_init(&self->tree, (compare_f) __array_compare); + } +} + +void array_delete(array_t * self) +{ + __array_delete(self); +} + +static void *__array_find_page(array_t * self, size_t idx) +{ + const void *hash = + (const void *)__index_to_page_hashed(idx, self->elem_num); + tree_node_t *node = tree_find(&self->tree, hash); + + if (node == NULL) + return (void *)__array_grow(self, idx); + else + return (void *)container_of(node, array_node_t, node); + + return NULL; +} + +static uint8_t *__array_find_map(array_t * self, size_t idx) +{ + if (unlikely(self == NULL)) + throw_unexpected(ARRAY_NULL); + + const void *hash = + (const void *)__index_to_page_hashed(idx, self->elem_num); + uint8_t *map = (uint8_t *) tree_find(&self->tree, hash); + if (map != NULL) + map += sizeof(tree_node_t); + + return map; +} + +const void *array_at(array_t * self, size_t idx) +{ + if (unlikely(self == NULL)) + throw_unexpected(ARRAY_NULL); + + uint32_t offset = idx % self->elem_num; + + uint8_t *map = __array_find_page(self, idx); + map += sizeof(array_node_t); + + uint8_t byte = offset / CHAR_BIT; + uint8_t mask = 0x80 >> (offset % CHAR_BIT); + + if ((map[byte] & mask) == 0) + throw_unexpected(ARRAY_UNINIT_ELEM); + + return map + self->map_size + (self->elem_size * offset); +} + +void array_get3(array_t * self, size_t elem_off, void *ptr) +{ + return array_get4(self, elem_off, ptr, 1); +} + +void array_get4(array_t * self, size_t elem_off, void *ptr, size_t elem_num) +{ + if (unlikely(self == NULL)) + throw_unexpected(ARRAY_NULL); + + while (0 < elem_num) { + memcpy(ptr, array_at(self, elem_off), self->elem_size); + + elem_off++; + elem_num--; + + ptr += self->elem_size; + } +} + +void __array_put(array_t * self, size_t elem_off, const void *ptr) +{ + if (unlikely(self == NULL)) + throw_unexpected(ARRAY_NULL); + + uint32_t offset = elem_off % self->elem_num; + + uint8_t *map = __array_find_page(self, elem_off); + map += sizeof(array_node_t); + + uint8_t byte = offset / CHAR_BIT; + uint8_t mask = 0x80 >> (offset % CHAR_BIT); + + if ((map[byte] & mask) == 0) + self->size++; + + map[byte] |= mask; + + memcpy(map + self->map_size + (self->elem_size * offset), + ptr, self->elem_size); +} + +void array_put3(array_t * self, size_t elem_off, const void *ptr) +{ + return array_put4(self, elem_off, ptr, 1); +} + +void array_put4(array_t * self, size_t elem_off, const void *ptr, + size_t elem_num) +{ + if (unlikely(self == NULL)) + throw_unexpected(ARRAY_NULL); + + while (0 < elem_num) { + __array_put(self, elem_off, ptr); + + elem_off++; + elem_num--; + + ptr += self->elem_size; + } +} + +bool array_status2(array_t * self, size_t idx) +{ + uint8_t *map = __array_find_map(self, idx); + + uint32_t offset = idx % self->elem_num; + uint8_t byte = offset / CHAR_BIT; + uint8_t mask = 0x80 >> (offset % CHAR_BIT); + + return ! !(map[byte] & mask); +} + +bool array_status3(array_t * self, size_t idx, bool status) +{ + uint8_t *map = __array_find_map(self, idx); + + if (map == NULL) { + map = (uint8_t *) __array_grow(self, idx); + map += sizeof(array_node_t); + } + + uint32_t offset = idx % self->elem_num; + uint8_t byte = offset / CHAR_BIT; + uint8_t mask = 0x80 >> (offset % CHAR_BIT); + + bool ret = ! !(map[byte] & mask); + + map[byte] &= ~mask; + if (status) + map[byte] |= mask; + + return ret; +} + +void array_resize(array_t * self, size_t size) +{ + if (unlikely(self == NULL)) + throw_unexpected(ARRAY_NULL); + while (0 < size) { + (void)__array_grow(self, self->high + 1); + size /= self->elem_num; + } +} + +size_t array_size(array_t * self) +{ + if (unlikely(self == NULL)) + throw_unexpected(ARRAY_NULL); + return self->size; +} + +size_t array_pages(array_t * self) +{ + if (unlikely(self == NULL)) + throw_unexpected(ARRAY_NULL); + return self->pages; +} + +size_t array_capacity(array_t * self) +{ + if (unlikely(self == NULL)) + throw_unexpected(ARRAY_NULL); + return self->high - self->low + 1; +} + +size_t array_low(array_t * self) +{ + if (unlikely(self == NULL)) + throw_unexpected(ARRAY_NULL); + return self->low; +} + +size_t array_high(array_t * self) +{ + if (unlikely(self == NULL)) + throw_unexpected(ARRAY_NULL); + return self->high; +} + +void array_send(array_t * self, mqueue_t * mq) +{ + if (unlikely(self == NULL)) + throw_unexpected(ARRAY_NULL); + if (unlikely(mq == NULL)) + throw_unexpected(ARRAY_MQ_NULL); + + mqueue_send(mq, (char *)self, sizeof(*self)); + + tree_iter_t it; + tree_iter_init(&it, &self->tree, TI_FLAG_FWD); + + array_node_t *node; + tree_for_each(&it, node, node) { + if (node->magic != ARRAY_NODE_MAGIC) + throw_unexpected(ARRAY_MAGIC_CHECK); + + mqueue_send(mq, (char *)node, self->page_size); + } +} + +void array_receive(array_t * self, mqueue_t * mq) +{ + if (unlikely(self == NULL)) + throw_unexpected(ARRAY_NULL); + if (unlikely(mq == NULL)) + throw_unexpected(ARRAY_MQ_NULL); + + __array_delete(self); + + mqueue_attr_t attr = mqueue_getattr(mq); + + array_node_t *node = NULL; + switch (POSIX_MEMALIGN + ((void **)&node, attr.mq_msgsize, attr.mq_msgsize)) { + case EINVAL: + throw_unexpected(ARRAY_SIZE); + case ENOMEM: + throw_unexpected(ARRAY_OOM); + } + assert(node != NULL); + + ssize_t len = mqueue_receive(mq, (void *)node, attr.mq_msgsize); + assert(0 < len); + + memcpy(self, (void *)node, sizeof(*self)); + tree_init(&self->tree, (compare_f) __array_compare); + + for (int i = 0; i < array_pages(self); i++) { + if (node == NULL) { + switch (POSIX_MEMALIGN + ((void **)&node, attr.mq_msgsize, + attr.mq_msgsize)) { + case EINVAL: + throw_unexpected(ARRAY_SIZE); + case ENOMEM: + throw_unexpected(ARRAY_OOM); + } + } + + len = mqueue_receive(mq, (void *)node, attr.mq_msgsize); + assert(0 < len); + + node->address = (uint32_t) node; + tree_node_init(&node->node, node->node.key); + splay_insert(&self->tree, &node->node); + + node = NULL; + } +} + +void array_dump(array_t * self, FILE * out) +{ + if (self != NULL) { + fprintf(out, + "array: [ page_size: %5u pages: %5u map_size: %5u capacity: %10u ]\n", + self->page_size, self->pages, self->map_size, + array_capacity(self)); + fprintf(out, + " [ elem_size: %5u elem_num: %5u size: %10u range: (%u....%u) ]\n", + self->elem_size, self->elem_num, array_size(self), + array_low(self), array_high(self)); + + dump_memory(out, (unsigned long)self, self, sizeof(*self)); + + tree_iter_t it; + for (tree_iter_init(&it, &self->tree, TI_FLAG_FWD); + tree_iter_elem(&it); tree_iter_inc(&it)) { + array_node_t *node; + node = + container_of(tree_iter_elem(&it), array_node_t, + node); + + fprintf(out, "magic[%x] address[%x]\n", + node->magic, node->address); + fprintf(out, + "n[%p] left[%p] right[%p] parent[%p] key[%p] \n", + &node->node, node->node.left, node->node.right, + node->node.parent, node->node.key); + + dump_memory(out, (unsigned long)node, node, + self->page_size); + } + } +} + +/* ======================================================================= */ diff --git a/clib/src/array_iter.c b/clib/src/array_iter.c new file mode 100644 index 0000000..921bf97 --- /dev/null +++ b/clib/src/array_iter.c @@ -0,0 +1,180 @@ +/* + * Copyright (c) International Business Machines Corp., 2014 + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program 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 General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + */ + +/* + * File: array_iter.c + * Author: Shaun Wetzstein <shaun@us.ibm.com> + * Descr: dynamic array + * Note: + * Date: 10/22/10 + */ + +#include <unistd.h> +#include <stdarg.h> +#include <stdlib.h> +#include <malloc.h> +#include <stdint.h> +#include <stdio.h> +#include <string.h> +#include <errno.h> +#include <limits.h> + +#include "assert.h" +#include "misc.h" +#include "hash.h" +#include "nargs.h" +#include "array_iter.h" + +/* ======================================================================= */ + +const char *__array_iter_msg[] = { + "array_iter: unexpected NULL pointer", + "array_iter: index out-of-range", +}; + +#define ARRAY_ITER_NULL (__array_iter_msg[0]) +#define ARRAY_ITER_RANGE (__array_iter_msg[1]) + +/* ======================================================================= */ + +static inline const void *__array_iter_bwd(array_iter_t * self) +{ + size_t low = array_low(self->array); + const void *ret = NULL; + + if (low < self->idx) + self->idx--; + + while (low < self->idx) { + if (array_status(self->array, self->idx)) + break; + self->idx--; + } + + if (low < self->idx) + ret = array_at(self->array, self->idx); + + return ret; +} + +static inline const void *__array_iter_fwd(array_iter_t * self) +{ + size_t high = array_high(self->array); + const void *ret = NULL; + + if (self->idx < high) + self->idx++; + + while (self->idx < high) { + if (array_status(self->array, self->idx)) + break; + self->idx++; + } + + if (self->idx < high) + ret = array_at(self->array, self->idx); + + return ret; +} + +void array_iter_init(array_iter_t * self, array_t * array, uint32_t flags) +{ + if (unlikely(self == NULL)) + throw_unexpected(ARRAY_ITER_NULL); + if (unlikely(array == NULL)) + throw_unexpected(ARRAY_ITER_NULL); + + self->flags = flags; + self->array = array; + + if (self->flags & AI_FLAG_BWD) { + self->idx = array_high(self->array); + __array_iter_bwd(self); + } else { + self->idx = array_low(self->array); + __array_iter_fwd(self); + } +} + +void array_iter_clear(array_iter_t * self) +{ + if (unlikely(self == NULL)) + throw_unexpected(ARRAY_ITER_NULL); + + if (self->flags & AI_FLAG_BWD) + self->idx = array_high(self->array); + else + self->idx = array_low(self->array); + + self->array = NULL; +} + +const void *array_iter_elem(array_iter_t * self) +{ + if (unlikely(self == NULL)) + throw_unexpected(ARRAY_ITER_NULL); + if (self->idx < array_low(self->array)) + throw_unexpected(ARRAY_ITER_RANGE); + if (array_high(self->array) <= self->idx) + throw_unexpected(ARRAY_ITER_RANGE); + + return array_status(self->array, self->idx) ? + array_at(self->array, self->idx) : NULL; +} + +const void *array_iter_inc1(array_iter_t * self) +{ + return array_iter_inc2(self, 1); +} + +const void *array_iter_inc2(array_iter_t * self, size_t inc) +{ + if (unlikely(self == NULL)) + throw_unexpected(ARRAY_ITER_NULL); + + const void *ret = NULL; + + if (self->flags & AI_FLAG_BWD) + ret = __array_iter_bwd(self); + else + ret = __array_iter_fwd(self); + + return ret; +} + +const void *array_iter_dec1(array_iter_t * self) +{ + return array_iter_dec2(self, 1); +} + +const void *array_iter_dec2(array_iter_t * self, size_t dec) +{ + if (unlikely(self == NULL)) + throw_unexpected(ARRAY_ITER_NULL); + + const void *ret = NULL; + + if (self->flags & AI_FLAG_BWD) + ret = __array_iter_fwd(self); + else + ret = __array_iter_bwd(self); + + return ret; +} + +/* ======================================================================= */ diff --git a/clib/src/checksum.c b/clib/src/checksum.c new file mode 100644 index 0000000..fea96b4 --- /dev/null +++ b/clib/src/checksum.c @@ -0,0 +1,43 @@ +/* + * Copyright (c) International Business Machines Corp., 2014 + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program 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 General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + */ + +#include <stdio.h> +#include <stdint.h> + +#include "assert.h" +#include "checksum.h" + +uint32_t memcpy_checksum(void *__restrict __dst, const void *__restrict __src, + size_t __n) +{ + uint8_t sum[4] = { 0, }; + + /* assert(((uintptr_t)__src & 3) == 0); */ + + size_t i; + + if (__dst == NULL) + for (i = 0; i < __n; i++) + sum[i & 3] ^= ((uint8_t *) __src)[i]; + else + for (i = 0; i < __n; i++) + sum[i & 3] ^= ((uint8_t *) __src)[i], + ((uint8_t *) __dst)[i] = ((uint8_t *) __src)[i]; + + return (sum[0] << 24) | (sum[1] << 16) | (sum[2] << 8) | sum[3]; +} diff --git a/clib/src/crc32.c b/clib/src/crc32.c new file mode 100644 index 0000000..d0cf657 --- /dev/null +++ b/clib/src/crc32.c @@ -0,0 +1,150 @@ +/* + * Copyright (c) International Business Machines Corp., 2014 + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program 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 General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + */ + +/* Crc - 32 BIT ANSI X3.66 CRC checksum files */ + +#include <stdio.h> +#include <stdint.h> + +#include "crc32.h" + +/**********************************************************************\ +|* Demonstration program to compute the 32-bit CRC used as the frame *| +|* check sequence in ADCCP (ANSI X3.66, also known as FIPS PUB 71 *| +|* and FED-STD-1003, the U.S. versions of CCITT's X.25 link-level *| +|* protocol). The 32-bit FCS was added via the Federal Register, *| +|* 1 June 1982, p.23798. I presume but don't know for certain that *| +|* this polynomial is or will be included in CCITT V.41, which *| +|* defines the 16-bit CRC (often called CRC-CCITT) polynomial. FIPS *| +|* PUB 78 says that the 32-bit FCS reduces otherwise undetected *| +|* errors by a factor of 10^-5 over 16-bit FCS. *| +\**********************************************************************/ + +/* Copyright (C) 1986 Gary S. Brown. You may use this program, or + code or tables extracted from it, as desired without restriction.*/ + +/* First, the polynomial itself and its table of feedback terms. The */ +/* polynomial is */ +/* X^32+X^26+X^23+X^22+X^16+X^12+X^11+X^10+X^8+X^7+X^5+X^4+X^2+X^1+X^0 */ +/* Note that we take it "backwards" and put the highest-order term in */ +/* the lowest-order bit. The X^32 term is "implied"; the LSB is the */ +/* X^31 term, etc. The X^0 term (usually shown as "+1") results in */ +/* the MSB being 1. */ + +/* Note that the usual hardware shift register implementation, which */ +/* is what we're using (we're merely optimizing it by doing eight-bit */ +/* chunks at a time) shifts bits into the lowest-order term. In our */ +/* implementation, that means shifting towards the right. Why do we */ +/* do it this way? Because the calculated CRC must be transmitted in */ +/* order from highest-order term to lowest-order term. UARTs transmit */ +/* characters in order from LSB to MSB. By storing the CRC this way, */ +/* we hand it to the UART in the order low-byte to high-byte; the UART */ +/* sends each low-bit to hight-bit; and the result is transmission bit */ +/* by bit from highest- to lowest-order term without requiring any bit */ +/* shuffling on our part. Reception works similarly. */ + +/* The feedback terms table consists of 256, 32-bit entries. Notes: */ +/* */ +/* 1. The table can be generated at runtime if desired; code to do so */ +/* is shown later. It might not be obvious, but the feedback */ +/* terms simply represent the results of eight shift/xor opera- */ +/* tions for all combinations of data and CRC register values. */ +/* */ +/* 2. The CRC accumulation logic is the same for all CRC polynomials, */ +/* be they sixteen or thirty-two bits wide. You simply choose the */ +/* appropriate table. Alternatively, because the table can be */ +/* generated at runtime, you can start by generating the table for */ +/* the polynomial in question and use exactly the same "updcrc", */ +/* if your application needn't simultaneously handle two CRC */ +/* polynomials. (Note, however, that XMODEM is strange.) */ +/* */ +/* 3. For 16-bit CRCs, the table entries need be only 16 bits wide; */ +/* of course, 32-bit entries work OK if the high 16 bits are zero. */ +/* */ +/* 4. The values must be right-shifted by eight bits by the "updcrc" */ +/* logic; the shift must be unsigned (bring in zeroes). On some */ +/* hardware you could probably optimize the shift in assembler by */ +/* using byte-swap instructions. */ + +static uint32_t __crc32_table[] = { /* CRC polynomial 0xedb88320 */ + 0x00000000, 0x77073096, 0xee0e612c, 0x990951ba, 0x076dc419, 0x706af48f, + 0xe963a535, 0x9e6495a3, 0x0edb8832, 0x79dcb8a4, 0xe0d5e91e, 0x97d2d988, + 0x09b64c2b, 0x7eb17cbd, 0xe7b82d07, 0x90bf1d91, 0x1db71064, 0x6ab020f2, + 0xf3b97148, 0x84be41de, 0x1adad47d, 0x6ddde4eb, 0xf4d4b551, 0x83d385c7, + 0x136c9856, 0x646ba8c0, 0xfd62f97a, 0x8a65c9ec, 0x14015c4f, 0x63066cd9, + 0xfa0f3d63, 0x8d080df5, 0x3b6e20c8, 0x4c69105e, 0xd56041e4, 0xa2677172, + 0x3c03e4d1, 0x4b04d447, 0xd20d85fd, 0xa50ab56b, 0x35b5a8fa, 0x42b2986c, + 0xdbbbc9d6, 0xacbcf940, 0x32d86ce3, 0x45df5c75, 0xdcd60dcf, 0xabd13d59, + 0x26d930ac, 0x51de003a, 0xc8d75180, 0xbfd06116, 0x21b4f4b5, 0x56b3c423, + 0xcfba9599, 0xb8bda50f, 0x2802b89e, 0x5f058808, 0xc60cd9b2, 0xb10be924, + 0x2f6f7c87, 0x58684c11, 0xc1611dab, 0xb6662d3d, 0x76dc4190, 0x01db7106, + 0x98d220bc, 0xefd5102a, 0x71b18589, 0x06b6b51f, 0x9fbfe4a5, 0xe8b8d433, + 0x7807c9a2, 0x0f00f934, 0x9609a88e, 0xe10e9818, 0x7f6a0dbb, 0x086d3d2d, + 0x91646c97, 0xe6635c01, 0x6b6b51f4, 0x1c6c6162, 0x856530d8, 0xf262004e, + 0x6c0695ed, 0x1b01a57b, 0x8208f4c1, 0xf50fc457, 0x65b0d9c6, 0x12b7e950, + 0x8bbeb8ea, 0xfcb9887c, 0x62dd1ddf, 0x15da2d49, 0x8cd37cf3, 0xfbd44c65, + 0x4db26158, 0x3ab551ce, 0xa3bc0074, 0xd4bb30e2, 0x4adfa541, 0x3dd895d7, + 0xa4d1c46d, 0xd3d6f4fb, 0x4369e96a, 0x346ed9fc, 0xad678846, 0xda60b8d0, + 0x44042d73, 0x33031de5, 0xaa0a4c5f, 0xdd0d7cc9, 0x5005713c, 0x270241aa, + 0xbe0b1010, 0xc90c2086, 0x5768b525, 0x206f85b3, 0xb966d409, 0xce61e49f, + 0x5edef90e, 0x29d9c998, 0xb0d09822, 0xc7d7a8b4, 0x59b33d17, 0x2eb40d81, + 0xb7bd5c3b, 0xc0ba6cad, 0xedb88320, 0x9abfb3b6, 0x03b6e20c, 0x74b1d29a, + 0xead54739, 0x9dd277af, 0x04db2615, 0x73dc1683, 0xe3630b12, 0x94643b84, + 0x0d6d6a3e, 0x7a6a5aa8, 0xe40ecf0b, 0x9309ff9d, 0x0a00ae27, 0x7d079eb1, + 0xf00f9344, 0x8708a3d2, 0x1e01f268, 0x6906c2fe, 0xf762575d, 0x806567cb, + 0x196c3671, 0x6e6b06e7, 0xfed41b76, 0x89d32be0, 0x10da7a5a, 0x67dd4acc, + 0xf9b9df6f, 0x8ebeeff9, 0x17b7be43, 0x60b08ed5, 0xd6d6a3e8, 0xa1d1937e, + 0x38d8c2c4, 0x4fdff252, 0xd1bb67f1, 0xa6bc5767, 0x3fb506dd, 0x48b2364b, + 0xd80d2bda, 0xaf0a1b4c, 0x36034af6, 0x41047a60, 0xdf60efc3, 0xa867df55, + 0x316e8eef, 0x4669be79, 0xcb61b38c, 0xbc66831a, 0x256fd2a0, 0x5268e236, + 0xcc0c7795, 0xbb0b4703, 0x220216b9, 0x5505262f, 0xc5ba3bbe, 0xb2bd0b28, + 0x2bb45a92, 0x5cb36a04, 0xc2d7ffa7, 0xb5d0cf31, 0x2cd99e8b, 0x5bdeae1d, + 0x9b64c2b0, 0xec63f226, 0x756aa39c, 0x026d930a, 0x9c0906a9, 0xeb0e363f, + 0x72076785, 0x05005713, 0x95bf4a82, 0xe2b87a14, 0x7bb12bae, 0x0cb61b38, + 0x92d28e9b, 0xe5d5be0d, 0x7cdcefb7, 0x0bdbdf21, 0x86d3d2d4, 0xf1d4e242, + 0x68ddb3f8, 0x1fda836e, 0x81be16cd, 0xf6b9265b, 0x6fb077e1, 0x18b74777, + 0x88085ae6, 0xff0f6a70, 0x66063bca, 0x11010b5c, 0x8f659eff, 0xf862ae69, + 0x616bffd3, 0x166ccf45, 0xa00ae278, 0xd70dd2ee, 0x4e048354, 0x3903b3c2, + 0xa7672661, 0xd06016f7, 0x4969474d, 0x3e6e77db, 0xaed16a4a, 0xd9d65adc, + 0x40df0b66, 0x37d83bf0, 0xa9bcae53, 0xdebb9ec5, 0x47b2cf7f, 0x30b5ffe9, + 0xbdbdf21c, 0xcabac28a, 0x53b39330, 0x24b4a3a6, 0xbad03605, 0xcdd70693, + 0x54de5729, 0x23d967bf, 0xb3667a2e, 0xc4614ab8, 0x5d681b02, 0x2a6f2b94, + 0xb40bbe37, 0xc30c8ea1, 0x5a05df1b, 0x2d02ef8d +}; + +inline uint32_t clib_crc32(unsigned char octet, uint32_t crc) +{ + return __crc32_table[(crc ^ (uint8_t) octet) & 0xff] ^ (crc >> 8); +} + +uint32_t memcpy32(void *__restrict __dst, const void *__restrict __src, + size_t __n) +{ + register uint32_t __crc = 0xFFFFFFFF; + + if (__dst == NULL) + for (; __n; --__n, ++__src) { + __crc = clib_crc32(*(uint8_t *) __src, __crc); + } else + for (; __n; --__n, ++__src, ++__dst) { + __crc = clib_crc32(*(uint8_t *) __src, __crc); + *(uint8_t *) __dst = *(uint8_t *) __src; + } + + return ~__crc; +} diff --git a/clib/src/crc32_main.c b/clib/src/crc32_main.c new file mode 100644 index 0000000..3bdf072 --- /dev/null +++ b/clib/src/crc32_main.c @@ -0,0 +1,76 @@ +/* + * Copyright (c) International Business Machines Corp., 2014 + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program 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 General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + */ + +#include <errno.h> +#include <fcntl.h> +#include <stdio.h> +#include <stdlib.h> +#include <string.h> +#include <sys/mman.h> +#include <sys/stat.h> +#include <sys/types.h> +#include <unistd.h> + +#include "crc32.h" + +void usage(void) +{ + printf("Usage: crc32 infile\n"); +} + +int main(int argc, const char *argv[]) +{ + if (argc != 2) { + usage(); + return 1; + } + + int fd = open(argv[1], O_RDONLY); + if (fd < 0) { + printf("open %s: %s\n", argv[1], strerror(errno)); + return 1; + } + + struct stat stat; + int rc = fstat(fd, &stat); + if (rc < 0) { + printf("stat %s: %s\n", argv[1], strerror(errno)); + return 1; + } + + off_t filesize = stat.st_size; + + void *in_buf = mmap(NULL, filesize, PROT_READ, MAP_PRIVATE, fd, 0); + if (in_buf == MAP_FAILED) { + /* FIXME could still try to use read().... */ + printf("mmap %d failed: %s\n", filesize, strerror(errno)); + return 1; + } + + rc = close(fd); + if (rc < 0) { + printf("close %s: %s\n", argv[1], strerror(errno)); + return 1; + } + + unsigned long crc32 = memcpy32(NULL, in_buf, filesize); + + printf("%#010lx", crc32), fflush(stdout); + + return 0; +} diff --git a/clib/src/db.c b/clib/src/db.c new file mode 100644 index 0000000..e61726c --- /dev/null +++ b/clib/src/db.c @@ -0,0 +1,400 @@ +/* + * Copyright (c) International Business Machines Corp., 2014 + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program 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 General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + */ + +/* + * File: db.c + * Author: Shaun Wetzstein <shaun@us.ibm.com> + * Descr: SQlite wrapper + * Note: + * Date: 02/25/11 + */ + +#include <stdio.h> +#include <unistd.h> +#include <stdarg.h> +#include <stdlib.h> +#include <malloc.h> +#include <sqlite3.h> +#include <stdint.h> +#include <string.h> +#include <errno.h> +#include <limits.h> + +#include "assert.h" +#include "err.h" + +#include "db.h" + +/* =======================================================================*/ + +int db_init(db_t * self, const char *path) +{ + assert(self != NULL); + + self->path = strdup(path); + if (self->path == NULL) { + ERRNO(errno); + return -1; + } + + self->db = NULL; + + return 0; +} + +int db_delete(db_t * self) +{ + if (self != NULL) { + db_close(self); + if (self->path != NULL) + free((char *)self->path); + memset(self, 0, sizeof(*self)); + } + + return 0; +} + +int db_execute(db_t * self, const char *fmt, ...) +{ + assert(self != NULL); + + va_list ap; + va_start(ap, fmt); + char *sql = NULL; + vasprintf(&sql, fmt, ap); + + assert(sql != NULL); + + int rc = sqlite3_exec(self->db, sql, NULL, NULL, NULL); + if (sql != NULL) + free(sql); + + if (rc != DB_OK) { + DBERR(self->db); + return -1; + } + + return 0; +} + +int db_open(db_t * self, int flags) +{ + assert(self != NULL); + + int rc = DB_OK; + + if (self->db != NULL) + db_close(self); + + rc = sqlite3_open_v2(self->path, &self->db, flags, NULL); + if (rc != DB_OK) { + DBERR(self->db); + return -1; + } + + return rc; +} + +int db_close(db_t * self) +{ + assert(self != NULL); + + int rc = DB_OK; + + if (self->db != NULL) { + /* finalize statements */ + rc = sqlite3_close(self->db); + } + + return rc; +} + +int db_register_function(db_t * self, const char *name, int argc, db_f func, + void *data) +{ + assert(self != NULL); + + int rc = DB_OK; + + rc = sqlite3_create_function(self->db, name, argc, SQLITE_ANY, data, + func, NULL, NULL); + if (rc != 0) { + DBERR(self->db); + return -1; + } + + return rc; +} + +int db_begin(db_t * self, transaction_type_t type) +{ + assert(self != NULL); + + const char *tran_type = NULL; + + switch (type) { + case tt_DEFERRED: + tran_type = "DEFERRED"; + break; + case tt_IMMEDIATE: + tran_type = "IMMEDIATE"; + break; + case tt_EXCLUSIVE: + tran_type = "EXCLUSIVE"; + break; + default: + UNEXPECTED("'%d' invalid transaction type", type); + return -1; + } + + return db_execute(self, "BEGIN %s TRANSACTION", tran_type); +} + +int db_commit(db_t * self) +{ + assert(self != NULL); + return db_execute(self, "COMMIT TRANSACTION"); +} + +int db_rollback(db_t * self) +{ + assert(self != NULL); + return db_execute(self, "ROLLBACK TRANSACTION"); +} + +/* =======================================================================*/ + +int statement_init(statement_t * self, db_t * db) +{ + assert(self != NULL); + assert(db != NULL); + + self->db = db; + self->stmt = NULL; + + return 0; +} + +int statement_delete(statement_t * self) +{ + assert(self != NULL); + + if (self->stmt != NULL) { + statement_finalize(self); + self->stmt = NULL; + } + + self->db = NULL; + free(self); + + return 0; +} + +int statement_prepare(statement_t * self, const char *sql) +{ + assert(self != NULL); + assert(sql != NULL); + + int rc = DB_OK; + + if (self->stmt != NULL) { + rc = sqlite3_finalize(self->stmt); + if (rc != DB_OK) { + SQLERR(self->db->db, self->stmt); + return -1; + } + } + + rc = sqlite3_prepare_v2(self->db->db, sql, -1, &self->stmt, NULL); + if (rc != DB_OK) { + SQLERR(self->db->db, self->stmt); + return -1; + } + + return rc; +} + +int statement_step(statement_t * self) +{ + assert(self != NULL); + + int rc = DB_OK; + + if (self->stmt != NULL) { + rc = sqlite3_step(self->stmt); + + switch (rc) { + case DB_DONE: + case DB_ROW: + break; + default: + SQLERR(self->db->db, self->stmt); + return -1; + } + } + + return rc; +} + +int statement_reset(statement_t * self) +{ + self = NULL; + return 0; +} + +int statement_finalize(statement_t * self) +{ + assert(self != NULL); + + int rc = DB_OK; + + if (self->stmt != NULL) { + rc = sqlite3_finalize(self->stmt); + if (rc != DB_OK) { + SQLERR(self->db->db, self->stmt); + return -1; + } + self->stmt = NULL; + } + + return rc; +} + +int statement_bind_int(statement_t * self, int pos, int val) +{ + assert(self != NULL); + + int rc = DB_OK; + + if (self->stmt != NULL) { + rc = sqlite3_bind_int(self->stmt, pos, val); + if (rc != DB_OK) { + SQLERR(self->db->db, self->stmt); + return -1; + } + } + + return rc; +} + +int statement_bind_int64(statement_t * self, int pos, int64_t val) +{ + assert(self != NULL); + + int rc = DB_OK; + + if (self->stmt != NULL) { + rc = sqlite3_bind_int64(self->stmt, pos, val); + if (rc != DB_OK) { + SQLERR(self->db->db, self->stmt); + return -1; + } + } + + return rc; +} + +int statement_bind_text(statement_t * self, int pos, const char *val) +{ + assert(self != NULL); + + int rc = DB_OK; + + if (self->stmt != NULL) { + rc = sqlite3_bind_text(self->stmt, pos, val, -1, + SQLITE_TRANSIENT); + if (rc != DB_OK) { + SQLERR(self->db->db, self->stmt); + return -1; + } + } + + return rc; +} + +int statement_bind_blob(statement_t * self, int pos, const void *val, int size) +{ + assert(self != NULL); + + int rc = DB_OK; + + if (self->stmt != NULL) { + rc = sqlite3_bind_blob(self->stmt, pos, val, size, + SQLITE_TRANSIENT); + if (rc != DB_OK) { + SQLERR(self->db->db, self->stmt); + return -1; + } + } + + return rc; +} + +int statement_column_int(statement_t * self, int pos) +{ + assert(self != NULL); + return sqlite3_column_int(self->stmt, pos); +} + +int64_t statement_column_int64(statement_t * self, int pos) +{ + assert(self != NULL); + return sqlite3_column_int64(self->stmt, pos); +} + +int statement_column_bytes(statement_t * self, int pos) +{ + assert(self != NULL); + return sqlite3_column_bytes(self->stmt, pos); +} + +const unsigned char *statement_column_text(statement_t * self, int pos) +{ + assert(self != NULL); + + const unsigned char *rc = NULL; + + if (self->stmt != NULL) { + rc = sqlite3_column_text(self->stmt, pos); + if (rc == NULL) { + SQLERR(self->db->db, self->stmt); + return NULL; + } + } + + return rc; +} + +const void *statement_column_blob(statement_t * self, int pos) +{ + assert(self != NULL); + + const void *rc = NULL; + + if (self->stmt != NULL) { + rc = sqlite3_column_blob(self->stmt, pos); + if (rc == NULL) { + SQLERR(self->db->db, self->stmt); + return NULL; + } + } + + return rc; +} + +/* =======================================================================*/ diff --git a/clib/src/dispatch.c b/clib/src/dispatch.c new file mode 100644 index 0000000..4630a70 --- /dev/null +++ b/clib/src/dispatch.c @@ -0,0 +1,155 @@ +/* + * Copyright (c) International Business Machines Corp., 2014 + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program 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 General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + */ + +/* + * File: dispatch.c + * Author: Shaun Wetzstein <shaun@us.ibm.com> + * Descr: + * Note: + * Date: 10/03/10 + */ + +#include <unistd.h> +#include <stdarg.h> +#include <stdlib.h> +#include <malloc.h> +#include <stdint.h> +#include <stdio.h> +#include <string.h> +#include <errno.h> +#include <limits.h> + +#include "misc.h" +#include "nargs.h" +#include "dispatch.h" + +#define DISPATCH_PAGE_SIZE 64 +#define DISPATCH_EVENT_SIZE 10 + +/* ======================================================================= */ + +const char *__dispatch_msg[] = { + "dispatch: unexpected NULL self pointer", + "dispatch: unexpected NULL callback structure", +}; + +#define DISPATCH_NULL (__dispatch_msg[0]) +#define DISPATCH_CALLBACK_NULL (__dispatch_msg[1]) + +/* ======================================================================= */ + +void dispatch_init(dispatch_t * self) +{ + if (unlikely(self == NULL)) + throw_unexpected(DISPATCH_NULL); + + if (self->fd != -1) + close(self->fd), self->fd = -1; + + self->fd = epoll_create1(EPOLL_CLOEXEC); + if (unlikely(self->fd == -1)) + throw_errno(errno); + + array_init(&self->events, sizeof(struct epoll_event), + DISPATCH_PAGE_SIZE); +} + +void dispatch_delete(dispatch_t * self) +{ + if (unlikely(self == NULL)) + throw_unexpected(DISPATCH_NULL); + close(self->fd), self->fd = -1; + array_delete(&self->events); +} + +int dispatch_fileno(dispatch_t * self) +{ + if (unlikely(self == NULL)) + throw_unexpected(DISPATCH_NULL); + return self->fd; +} + +int dispatch_add(dispatch_t * self, int fd, uint32_t events, + dispatch_callback_t * cb) +{ + if (unlikely(self == NULL)) + throw_unexpected(DISPATCH_NULL); + + array_status(&self->events, fd, true); + + struct epoll_event *ep; + ep = (struct epoll_event *)array_at(&self->events, fd); + ep->events = events; + ep->data.u64 = (uint64_t) fd << 32; + ep->data.ptr = (void *)cb; + + if (unlikely(epoll_ctl(self->fd, EPOLL_CTL_ADD, fd, ep))) + throw_errno(errno); + + return fd; +} + +void dispatch_remove(dispatch_t * self, int fd) +{ + if (unlikely(self == NULL)) + throw_unexpected(DISPATCH_NULL); + + if (unlikely(epoll_ctl(self->fd, EPOLL_CTL_DEL, fd, NULL))) + throw_errno(errno); + + array_status(&self->events, fd, false); +} + +void dispatch_wait1(dispatch_t * self) +{ + dispatch_wait2(self, -1); +} + +void dispatch_wait2(dispatch_t * self, int timeout) +{ + if (unlikely(self == NULL)) + throw_unexpected(DISPATCH_NULL); + + if (-1 < self->fd) { + struct epoll_event events[DISPATCH_EVENT_SIZE]; + + int rc = epoll_wait(self->fd, events, + DISPATCH_EVENT_SIZE, timeout); + + if (0 < rc) { + dump_memory(stdout, 0, events, sizeof(events)); + } + for (int n = 0; n < rc; n++) { + dispatch_callback_t *cb = + (dispatch_callback_t *) events[n].data.ptr; + if (cb != NULL) { + printf + ("cb[%p] fd[%d] data[%p] ep->data.u64[%lld]\n", + cb, cb->fd, cb->data, events[n].data.u64); + if (cb->func != NULL) { + // dispatch_event ev = {events[n].data.u64 >> 32, events[n].events}; + dispatch_event_t ev = + { cb->fd, events[n].events }; + cb->func(&ev, cb->data); + } + } + } + } +} + +/* ======================================================================= */ diff --git a/clib/src/ecc.c b/clib/src/ecc.c new file mode 100644 index 0000000..2103b00 --- /dev/null +++ b/clib/src/ecc.c @@ -0,0 +1,456 @@ +/* + * Copyright (c) International Business Machines Corp., 2014 + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program 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 General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + */ + +/* + * File: ecc.c + * Author: Shaun Wetzstein <shaun@us.ibm.com> + * Descr: SFC ECC functions + * Note: + * Date: 08/02/12 + * Descr: Added New ECC function with correctable bit functionality. + * Date: 12/04/13 + */ + +#include <unistd.h> +#include <stdarg.h> +#include <stdlib.h> +#include <stdbool.h> +#include <malloc.h> +#include <stdint.h> +#include <stdio.h> +#include <string.h> +#include <errno.h> +#include <limits.h> +#include <ctype.h> +#include <endian.h> +#include <assert.h> + +#include "ecc.h" +#include "builtin.h" +#include "attribute.h" + +#ifndef be64toh +#include <byteswap.h> +#if __BYTE_ORDER == __LITTLE_ENDIAN +#define be64toh(x) __bswap_64(x) +#define htobe64(x) __bswap_64(x) +#else +#define be64toh(x) (x) +#define htobe64(x) (x) +#endif +#endif + +/* + * This is an alternative way to calculate the ECC byte taken + * from the SFC spec. + */ +uint8_t sfc_ecc2(uint8_t __data[8]) __unused__; +uint8_t sfc_ecc2(uint8_t __data[8]) +{ + uint8_t ecc = 0; + + for (int byte = 0; byte < 8; byte++) { + for (int bit = 0; bit < 8; bit++) { + static unsigned char m[] = + { 0xff, 0x00, 0x00, 0xe8, 0x42, 0x3c, 0x0f, 0x99 }; + + unsigned char x = + __data[byte] & m[(byte + bit + 1) & 7]; + x = x ^ (x >> 4); + x = x ^ (x >> 2); + x = x ^ (x >> 1); + + ecc ^= (x & 1) << bit; + } + } + + return ~ecc; +} + +uint8_t sfc_ecc(uint8_t __data[8]) +{ +/* each bit of the ECC data corresponds to a row in this matrix */ + static uint8_t __matrix[8][8] = { +/* 11111111 00000000 00000000 11101000 01000010 00111100 00001111 10011001 */ + {0xff, 0x00, 0x00, 0xe8, 0x42, 0x3c, 0x0f, 0x99}, +/* 10011001 11111111 00000000 00000000 11101000 01000010 00111100 00001111 */ + {0x99, 0xff, 0x00, 0x00, 0xe8, 0x42, 0x3c, 0x0f}, +/* 00001111 10011001 11111111 00000000 00000000 11101000 01000010 00111100 */ + {0x0f, 0x99, 0xff, 0x00, 0x00, 0xe8, 0x42, 0x3c}, +/* 00111100 00001111 10011001 11111111 00000000 00000000 11101000 01000010 */ + {0x3c, 0x0f, 0x99, 0xff, 0x00, 0x00, 0xe8, 0x42}, +/* 01000010 00111100 00001111 10011001 11111111 00000000 00000000 11101000 */ + {0x42, 0x3c, 0x0f, 0x99, 0xff, 0x00, 0x00, 0xe8}, +/* 11101000 01000010 00111100 00001111 10011001 11111111 00000000 00000000 */ + {0xe8, 0x42, 0x3c, 0x0f, 0x99, 0xff, 0x00, 0x00}, +/* 00000000 11101000 01000010 00111100 00001111 10011001 11111111 00000000 */ + {0x00, 0xe8, 0x42, 0x3c, 0x0f, 0x99, 0xff, 0x00}, +/* 00000000 00000000 11101000 01000010 00111100 00001111 10011001 11111111 */ + {0x00, 0x00, 0xe8, 0x42, 0x3c, 0x0f, 0x99, 0xff}, + }; + + static uint8_t __mask[] = { +/* 10000000 01000000 00100000 00010000 00001000 00000100 00000010 00000001 */ + 0x80, 0x40, 0x20, 0x10, 0x08, 0x04, 0x02, 0x01 + }; + + uint8_t __and[8], __ecc = 0; + + for (uint32_t i = 0; i < sizeof(__matrix) / sizeof(*__matrix); i++) { + int __popcount = 0; + + for (uint32_t __byte = 0; __byte < 8; __byte++) { + /* compute the AND of the data and ECC matrix */ + __and[__byte] = __data[__byte] & __matrix[i][__byte]; + /* count the number of '1' bits in the result (parity) */ + __popcount += popcount(__and[__byte]); + } + + /* if the result is odd parity, turn on corresponding ECC bit */ + if ((__popcount) & 1) /* odd parity? */ + __ecc |= __mask[i]; + +#ifdef DEBUG + printf("\nmatrix["); + print_binary(NULL, __matrix[i], 8); + printf("]\n data["); + print_binary(NULL, __data, 8); + printf("]\n and["); + print_binary(NULL, __and, 8); + printf("]\n"); + printf("popcount: %d ecc %2.2x\n", __popcount, __ecc); +#endif + } + + /* the ECC data is inverted such that */ + /* 0xFFFFFFFFffffffff => 0xFF for erased NOR flash */ + return __ecc ^ 0xFF; +} + + +/* + * "aaaaaaaa [wwwwwwww_xxxxxxxx e yyyyyyyy_zzzzzzzz e] [........ ........]" + */ +static void __ecc_dump(FILE * __out, uint32_t __addr, + void *__restrict __buf, size_t __buf_sz, bool invert) +{ + if (__buf_sz <= 0 || __buf == NULL) + return; + if (__out == NULL) + __out = stdout; + + size_t hex_size = (16 + 2) * 2; // 16 bytes per doubleword plus ECC byte + size_t ascii_size = (8 + 1) * 2; // 8 bytes per doublewod plus ECC byte + + uint8_t hex[hex_size + 1], ascii[hex_size + 1]; + memset(hex, '.', hex_size), memset(ascii, '.', ascii_size); + + void print_line(void) { + const char *ansi_red = "\033[1;1m\033[1;31m"; + const char *ansi_norm = "\033[0m"; + + uint8_t c1 = sfc_ecc(ascii + 0), e1 = ascii[8]; + if (invert == true) + c1 = ~c1; + uint8_t c2 = sfc_ecc(ascii + 9), e2 = ascii[17]; + if (invert == true) + c2 = ~c2; + + for (size_t i = 0; i < ascii_size; i++) + ascii[i] = isprint(ascii[i]) ? ascii[i] : '.'; + + fprintf(__out, "%08x ", __addr); + + fprintf(__out, + "[%.8s_%.8s %.*s%.2s%.*s %.8s_%.8s %.*s%.2s%.*s] ", + hex + 0, hex + 8, (c1 != e1) ? strlen(ansi_red) : 0, + ansi_red, hex + 16, (c1 != e1) ? strlen(ansi_norm) : 0, + ansi_norm, hex + 18, hex + 26, + (c2 != e2) ? strlen(ansi_red) : 0, ansi_red, hex + 34, + (c2 != e2) ? strlen(ansi_norm) : 0, ansi_norm); + + fprintf(__out, "[%.8s %.8s]\n", ascii + 0, ascii + 9); + } + + size_t s = __addr % 16, i = 0; + __addr &= ~0xF; + + for (i = s; i < __buf_sz + s; i++) { + unsigned char c = ((unsigned char *)__buf)[i - s]; + + hex[((i << 1) + 0) % hex_size] = "0123456789abcdef"[c >> 4]; + hex[((i << 1) + 1) % hex_size] = "0123456789abcdef"[c & 0xf]; + + ascii[i % ascii_size] = c; + + if (i == 0) + continue; + + if ((i + 1) % ascii_size == 0) { + print_line(); + memset(hex, '.', hex_size), memset(ascii, '.', + ascii_size); + + __addr += ascii_size; + } + } + + if (i % ascii_size) + print_line(); + + return; +} + + + +/* ======================================== */ +static uint64_t ecc_matrix[] = { + //0000000000000000111010000100001000111100000011111001100111111111 + 0x0000e8423c0f99ff, + //0000000011101000010000100011110000001111100110011111111100000000 + 0x00e8423c0f99ff00, + //1110100001000010001111000000111110011001111111110000000000000000 + 0xe8423c0f99ff0000, + //0100001000111100000011111001100111111111000000000000000011101000 + 0x423c0f99ff0000e8, + //0011110000001111100110011111111100000000000000001110100001000010 + 0x3c0f99ff0000e842, + //0000111110011001111111110000000000000000111010000100001000111100 + 0x0f99ff0000e8423c, + //1001100111111111000000000000000011101000010000100011110000001111 + 0x99ff0000e8423c0f, + //1111111100000000000000001110100001000010001111000000111110011001 + 0xff0000e8423c0f99 +}; + +static uint8_t syndrome_matrix[] = { + GD, E7, E6, UE, E5, UE, UE, 47, E4, UE, UE, 37, UE, 35, 39, UE, + E3, UE, UE, 48, UE, 30, 29, UE, UE, 57, 27, UE, 31, UE, UE, UE, + E2, UE, UE, 17, UE, 18, 40, UE, UE, 58, 22, UE, 21, UE, UE, UE, + UE, 16, 49, UE, 19, UE, UE, UE, 23, UE, UE, UE, UE, 20, UE, UE, + E1, UE, UE, 51, UE, 46, 9, UE, UE, 34, 10, UE, 32, UE, UE, 36, + UE, 62, 50, UE, 14, UE, UE, UE, 13, UE, UE, UE, UE, UE, UE, UE, + UE, 61, 8, UE, 41, UE, UE, UE, 11, UE, UE, UE, UE, UE, UE, UE, + 15, UE, UE, UE, UE, UE, UE, UE, UE, UE, 12, UE, UE, UE, UE, UE, + E0, UE, UE, 55, UE, 45, 43, UE, UE, 56, 38, UE, 1, UE, UE, UE, + UE, 25, 26, UE, 2, UE, UE, UE, 24, UE, UE, UE, UE, UE, 28, UE, + UE, 59, 54, UE, 42, UE, UE, 44, 6, UE, UE, UE, UE, UE, UE, UE, + 5, UE, UE, UE, UE, UE, UE, UE, UE, UE, UE, UE, UE, UE, UE, UE, + UE, 63, 53, UE, 0, UE, UE, UE, 33, UE, UE, UE, UE, UE, UE, UE, + 3, UE, UE, 52, UE, UE, UE, UE, UE, UE, UE, UE, UE, UE, UE, UE, + 7, UE, UE, UE, UE, UE, UE, UE, UE, 60, UE, UE, UE, UE, UE, UE, + UE, UE, UE, UE, 4, UE, UE, UE, UE, UE, UE, UE, UE, UE, UE, UE, +}; + + +static uint8_t generate_ecc(uint64_t i_data) +{ + uint8_t result = 0; + + for (int i = 0; i < 8; i++) + { + result |= __builtin_parityll(ecc_matrix[i] & i_data) << i; + } + return result; +} +static uint8_t verify_ecc(uint64_t i_data, uint8_t i_ecc) +{ + return syndrome_matrix[generate_ecc(i_data) ^ i_ecc ]; +} +static uint8_t correct_ecc(uint64_t *io_data, uint8_t *io_ecc) +{ + uint8_t bad_bit = verify_ecc(*io_data, *io_ecc); + + if ((bad_bit != GD) && (bad_bit != UE)) // Good is done, UE is hopeless. + { + // Determine if the ECC or data part is bad, do bit flip. + if (bad_bit >= E7) + { + *io_ecc ^= (1 << (bad_bit - E7)); + } + else + { + *io_data ^=(1ull << (63 - bad_bit)); + } + } + return bad_bit; +} + +static void inject_ecc(const uint8_t* i_src, size_t i_srcSz, + uint8_t* o_dst, bool invert) +{ + assert(0 == (i_srcSz % sizeof(uint64_t))); + + for(size_t i = 0, o = 0; + i < i_srcSz; + i += sizeof(uint64_t), o += sizeof(uint64_t) + sizeof(uint8_t)) + { + // Read data word, copy to destination. + uint64_t data = *(const uint64_t*)(&i_src[i]); + + *(uint64_t*)(&o_dst[o]) = data; + data = be64toh(data); + + // Calculate ECC, copy to destination. + uint8_t ecc = generate_ecc(data); + o_dst[o + sizeof(uint64_t)] = invert ? ~ecc : ecc; + } +} +static ecc_status_t remove_ecc(uint8_t* io_src, size_t i_srcSz, + uint8_t* o_dst, size_t i_dstSz, + bool invert) +{ + assert(0 == (i_dstSz % sizeof(uint64_t))); + + ecc_status_t rc = CLEAN; + + for(size_t i = 0, o = 0; + i < i_srcSz; + i += sizeof(uint64_t) + sizeof(uint8_t), o += sizeof(uint64_t)) + { + // Read data and ECC parts. + uint64_t data = *(uint64_t*)(&io_src[i]); + data = be64toh(data); + + uint8_t ecc = io_src[i + sizeof(uint64_t)]; + if(invert) + { + ecc = ~ecc; + } + // Calculate failing bit and fix data. + uint8_t bad_bit = correct_ecc(&data, &ecc); + + // Return data to big endian. + data = htobe64(data); + + // Perform correction and status update. + if (bad_bit == UE) + { + rc = UNCORRECTABLE; + } + else if (bad_bit != GD) + { + if (rc != UNCORRECTABLE) + { + rc = CORRECTED; + } + *(uint64_t*)(&io_src[i]) = data; + io_src[i + sizeof(uint64_t)] = invert ? ~ecc : ecc; + } + + // Copy fixed data to destination buffer. + *(uint64_t*)(&o_dst[o]) = data; + } + return rc; +} +/* ========================================= */ + +static ssize_t __ecc_inject(void *__restrict __dst, size_t __dst_sz, + const void *__restrict __src, size_t __src_sz, + bool invert) +{ + int __size = sizeof(uint64_t); + + errno = 0; + if (__src_sz & (__size - 1)) { + errno = EINVAL; + return -1; + } + if (__dst_sz < (__src_sz + (__src_sz / __size))) { + errno = ENOBUFS; + return -1; + } + + ssize_t rc=0; + ssize_t c_sz = __src_sz; + for (; c_sz; c_sz -= __size) { + rc += __size + 1; + } + + inject_ecc(__src, __src_sz, __dst, invert); + return (rc); +} + +static ssize_t __ecc_remove(void *__restrict __dst, size_t __dst_sz, + const void *__restrict __src, size_t __src_sz, + bool invert) +{ + int __size = sizeof(uint64_t); + + errno = 0; + if ((__src_sz % (__size + 1)) != 0) { + errno = EINVAL; + return -1; + } + if (__dst_sz < (__src_sz - (__src_sz / __size))) { + errno = ENOBUFS; + return -1; + } + + + int target_size = ((__src_sz / (sizeof(uint64_t) + 1))*sizeof(uint64_t)); + if( remove_ecc((uint8_t*)__src, __src_sz, __dst, __dst_sz, invert) != CLEAN) + { + target_size = 0; + } + return target_size; +} + +void sfc_ecc_dump(FILE * __out, uint32_t __addr, + void *__restrict __buf, size_t __buf_sz) +{ + return __ecc_dump(__out, __addr, __buf, __buf_sz, false); +} + +/* ========================================= */ +ssize_t sfc_ecc_inject(void *__restrict __dst, size_t __dst_sz, + const void *__restrict __src, size_t __src_sz) +{ + return __ecc_inject(__dst, __dst_sz, __src, __src_sz, true); +} +ssize_t sfc_ecc_remove(void *__restrict __dst, size_t __dst_sz, + const void *__restrict __src, size_t __src_sz) +{ + return __ecc_remove(__dst, __dst_sz, __src, __src_sz, true); + +} +ssize_t p8_ecc_remove_size (void *__restrict __dst, size_t __dst_sz, + void *__restrict __src, size_t __src_sz __unused__) +{ + return __ecc_remove(__dst, __dst_sz, __src, __src_sz, false); +} + +/* ========================================= */ +ssize_t p8_ecc_inject(void *__restrict __dst, size_t __dst_sz, + const void *__restrict __src, size_t __src_sz) +{ + return __ecc_inject(__dst, __dst_sz, __src, __src_sz, false); +} + +ecc_status_t p8_ecc_remove (void *__restrict __dst, size_t __dst_sz, + void *__restrict __src, size_t __src_sz __unused__) +{ + return remove_ecc(__src, __src_sz, __dst, __dst_sz, false); +} + +void p8_ecc_dump(FILE * __out, uint32_t __addr, + void *__restrict __buf, size_t __buf_sz) +{ + return __ecc_dump(__out, __addr, __buf, __buf_sz, true); +} + diff --git a/clib/src/err.c b/clib/src/err.c new file mode 100644 index 0000000..e16f453 --- /dev/null +++ b/clib/src/err.c @@ -0,0 +1,208 @@ +/* + * Copyright (c) International Business Machines Corp., 2014 + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program 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 General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + */ + +/* + * File: err.c + * Author: Shaun Wetzstein <shaun@us.ibm.com> + * Descr: Error container + * Date: 04/04/12 + */ + +#include <errno.h> +#include <assert.h> +#include <pthread.h> +#include <stdlib.h> +#include <stdio.h> +#include <string.h> +#include <stdarg.h> +#include <execinfo.h> + +#include "attribute.h" +#include "min.h" + +#include "err.h" + +static pthread_key_t __err_key = 0; + +static const char *__err_type_name[] = { + [ERR_NONE] = "none", + [ERR_ERRNO] = "errno", + [ERR_UNEXPECTED] = "unexpected", + [ERR_VERSION] = "version", +}; + +/* =======================================================================*/ + +void err_delete(err_t * self) +{ + assert(self != NULL); + assert(self->magic == ERR_MAGIC); + + memset(self, 0, sizeof(*self)); + free(self); + + return; +} + +err_t *err_get(void) +{ + list_t *list = (list_t *) pthread_getspecific(__err_key); + + err_t *self = NULL; + + if (list != NULL) { + self = container_of(list_remove_tail(list), err_t, node); + + if (list_empty(list)) { + free(list), list = NULL; + assert(pthread_setspecific(__err_key, list) == 0); + } + } + + return self; +} + +void err_put(err_t * self) +{ + assert(self != NULL); + + list_t *list = pthread_getspecific(__err_key); + if (list == NULL) { + list = (list_t *) malloc(sizeof(*list)); + assert(list != NULL); + + list_init(list); + assert(pthread_setspecific(__err_key, list) == 0); + } + + list_add_head(list, &self->node); + + return; +} + +int err_type1(err_t * self) +{ + assert(self != NULL); + assert(self->magic == ERR_MAGIC); + + return self->type; +} + +void err_type2(err_t * self, int type) +{ + assert(self != NULL); + assert(self->magic == ERR_MAGIC); + + self->type = type; +} + +int err_code1(err_t * self) +{ + assert(self != NULL); + assert(self->magic == ERR_MAGIC); + + return self->code; +} + +void err_code2(err_t * self, int code) +{ + assert(self != NULL); + assert(self->magic == ERR_MAGIC); + + self->code = code; + + return; +} + +const char *err_file1(err_t * self) +{ + assert(self != NULL); + assert(self->magic == ERR_MAGIC); + + return self->file; +} + +void err_file2(err_t * self, const char *file) +{ + assert(self != NULL); + assert(self->magic == ERR_MAGIC); + + self->file = file; + + return; +} + +int err_line1(err_t * self) +{ + assert(self != NULL); + assert(self->magic == ERR_MAGIC); + + return self->line; +} + +void err_line2(err_t * self, int line) +{ + assert(self != NULL); + assert(self->magic == ERR_MAGIC); + + self->line = line; + + return; +} + +const void *err_data1(err_t * self) +{ + assert(self != NULL); + assert(self->magic == ERR_MAGIC); + + return self->data; +} + +void err_data2(err_t * self, int size, const void *data) +{ + assert(self != NULL); + assert(self->magic == ERR_MAGIC); + + self->size = min(size, ERR_DATA_SIZE); + memcpy(self->data, data, self->size); + + return; +} + +int err_size(err_t * self) +{ + assert(self != NULL); + assert(self->magic == ERR_MAGIC); + + return self->size; +} + +const char *err_type_name(err_t * self) +{ + assert(self != NULL); + assert(self->magic == ERR_MAGIC); + + return __err_type_name[self->type]; +} + +/* =======================================================================*/ + +__constructor static void __err__ctor__(void) +{ + assert(pthread_key_create(&__err_key, NULL) == 0); +} diff --git a/clib/src/exception.c b/clib/src/exception.c new file mode 100644 index 0000000..30b6dc6 --- /dev/null +++ b/clib/src/exception.c @@ -0,0 +1,145 @@ +/* + * Copyright (c) International Business Machines Corp., 2014 + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program 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 General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + */ + +/* + * File: exc.c + * Author: Shaun Wetzstein <shaun@us.ibm.com> + * Descr: {set,long}jmp implementation of exceptions for C code. + * Note: using these macros will create an exception context + * in each thread. + * Date: 7/06/09 + */ + +#include <errno.h> +#include <assert.h> +#include <pthread.h> +#include <stdio.h> +#include <stdarg.h> +#include <execinfo.h> + +#include "exception.h" +#include "misc.h" + +/* =======================================================================*/ + +const char *exception_name[] = { + "assertion", + "unexpected", + "errno", +}; + +typedef struct exception_context { + pthread_once_t once; + pthread_key_t key; +} exception_context; + +/* =======================================================================*/ + +static exception_context __exc_ctx = { PTHREAD_ONCE_INIT, 0 }; + +static inline void __exc_key_create(void) +{ + if (pthread_key_create(&__exc_ctx.key, NULL)) + __exc_throw(ASSERTION, NULL, 0, __FILE__, __LINE__); +} + +/* =======================================================================*/ + +void __exc_init(void) +{ + if (pthread_once(&__exc_ctx.once, __exc_key_create)) + __exc_throw(ASSERTION, NULL, 0, __FILE__, __LINE__); +} + +exception_frame_t *__exc_get_frame(void) +{ + return (exception_frame_t *) (pthread_getspecific(__exc_ctx.key)); +} + +void __exc_set_frame(exception_frame_t * f) +{ + if (pthread_setspecific(__exc_ctx.key, f)) + __exc_throw(ASSERTION, NULL, 0, __FILE__, __LINE__); +} + +void __exc_backtrace(const char *fmt, ...) +{ + if (fmt != NULL) { + va_list va; + va_start(va, fmt); + vfprintf(stderr, fmt, va); + va_end(va); + } + + fprintf(stderr, "========== backtrace ==========\n"); + void *bt[1024]; + int nr = backtrace(bt, sizeof bt); + backtrace_symbols_fd(bt, nr, fileno(stderr)); + fprintf(stderr, "========== backtrace ==========\n"); +} + +int __exc_throw(int ex, void *data, int size, const char *file, int line) +{ + extern char *program_invocation_short_name; + + exception_frame_t *frame = __exc_get_frame(); + + if (frame == NULL) { + __exc_backtrace + ("*** UNHANDLED EXCEPTION *** -- %s: %s(%d) ex=%d\n\n", + program_invocation_short_name, file, line, ex); + abort(); + } + + if (frame->magic != EXC_MAGIC) { + __exc_backtrace + ("*** CORRUPTED EXCEPTION FRAME *** -- %s: %s(%d) ex=%d\n\n", + program_invocation_short_name, file, line, ex); + abort(); + } + + frame->exc.file = file; + frame->exc.line = line; + + frame->exc.data = data; + frame->exc.size = size; + + longjmp(frame->jmp, ex); + + return -1; +} + +int __exc_rethrow(int ex, void *data, int size, const char *file, int line) +{ + exception_frame_t *frame = __exc_get_frame(); + + if (frame != NULL) + __exc_set_frame(frame->prev); + + return __exc_throw(ex, data, size, file, line); +} + +const char *__exc_name(int exc) +{ + return (exc < 0 || EXC_LAST <= exc) ? NULL : exception_name[exc]; +} + +__constructor void __exc_ctor(void) +{ + __exc_init(); +} diff --git a/clib/src/heap.c b/clib/src/heap.c new file mode 100644 index 0000000..2b339a2 --- /dev/null +++ b/clib/src/heap.c @@ -0,0 +1,152 @@ +/* + * Copyright (c) International Business Machines Corp., 2014 + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program 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 General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + */ + +#include <unistd.h> +#include <stdlib.h> +#include <malloc.h> +#include <stdint.h> +#include <stdio.h> +#include <string.h> +#include <errno.h> +#include <limits.h> + +#include "assert.h" +#include "misc.h" +#include "slab.h" +#include "heap.h" +#include "bb_trace.h" +#include "memory_leak_detection.h" + +/* ======================================================================= */ + +static const char *__heap_msg[] = { + "heap: unexpected NULL pointer" + "heap: unexpected cache and/or alloc size", + "heap: unexpected alloc size", +}; + +#define HEAP_NULL (__heap_msg[0]) +#define HEAP_SIZE (__heap_msg[1]) +#define HEAP_ALLOC (__heap_msg[2]) + +/* ======================================================================= */ + +void heap_dump(heap_t * self, FILE * out) +{ + if (self == NULL) + return; + + size_t i; + + fprintf(out, + "*******************************************************************\n"); + for (i = 0; i < self->slab_size; i++) + if (self->slab[i] != NULL) + slab_dump(self->slab[i], out); + fprintf(out, + "*******************************************************************\n"); +} + +heap_t *__heap_new(size_t alloc_size, size_t page_size, const char *file, + int line) +{ + alloc_size = max(__round_pow2(alloc_size), CACHE_ALLOC_MIN); + page_size = max(__round_pow2(page_size), CACHE_SIZE_MIN); + + if (alloc_size < CACHE_ALLOC_MIN || CACHE_ALLOC_MAX < alloc_size) + throw_unexpected(HEAP_SIZE); + if (page_size < CACHE_SIZE_MIN || CACHE_SIZE_MAX < page_size) + throw_unexpected(HEAP_SIZE); + + heap_t *self = (heap_t *) MALLOC(sizeof(*self) + + sizeof(*self->slab) * page_size / + alloc_size); + assert(self != NULL); + + self->page_size = page_size; + self->alloc_size = alloc_size; + self->slab_size = page_size / alloc_size; + + memset(self->slab, 0, self->slab_size * sizeof(*self->slab)); + + return self; +} + +void __heap_delete(heap_t * self, const char *file, int line) +{ + if (unlikely(self == NULL)) + return; + + size_t i; + for (i = 0; i < self->slab_size; i++) { + if (self->slab[i] != NULL) { + slab_delete(self->slab[i]); + self->slab[i] = NULL; + } + } + + memset(self, 0, sizeof *self); + FREE(self); +} + +void *__heap_alloc(heap_t * self, size_t size, const char *file, int line) +{ + if (unlikely(self == NULL)) + throw_unexpected(HEAP_NULL); + + size = max(align(size, self->alloc_size), self->alloc_size); + + size_t slab_pos = size / self->alloc_size - 1; + + if (unlikely(self->slab_size < slab_pos)) + throw_unexpected(HEAP_ALLOC); + + if (unlikely(self->slab[slab_pos] == NULL)) + self->slab[slab_pos] = slab_new(size, 0); + + return slab_alloc(self->slab[slab_pos]); +} + +void __heap_free(heap_t * self, void *ptr, const char *file, int line) +{ + if (unlikely(self == NULL)) + throw_unexpected(HEAP_NULL); + + void *data = (void *)((uint32_t) ptr & ~(self->page_size - 1)); + cache_t *c = (cache_t *) (data + self->page_size - sizeof(cache_t)); + cache_check(c); + slab_free(cache_slab(c), ptr); +} + +/* ======================================================================= */ + +static uint32_t page_size; + +void heap_ctor(void) __constructor; +void heap_ctor(void) +{ + page_size = (const uint32_t)sysconf(_SC_PAGESIZE); + assert(0 < page_size); +} + +void heap_dtor(void) __destructor; +void heap_dtor(void) +{ +} + +/* ======================================================================= */ diff --git a/clib/src/list.c b/clib/src/list.c new file mode 100644 index 0000000..3c72269 --- /dev/null +++ b/clib/src/list.c @@ -0,0 +1,49 @@ +/* + * Copyright (c) International Business Machines Corp., 2014 + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program 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 General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + */ + +#include <stdlib.h> +#include <stdint.h> +#include <stdio.h> +#include <errno.h> + +#include "assert.h" +#include "misc.h" +#include "list.h" + +/* ======================================================================= */ + +void list_dump(list_t * self, FILE * out) +{ + assert(self != NULL); + + fprintf(out, + "===================================================================\n"); + fprintf(out, "head: %8x node: %8x\n", (uint32_t) self, + (uint32_t) & self->node); + + list_node_t *node = &self->node; + do { + fprintf(out, " node: %8x - prev: %8x - next: %8x\n", + (uint32_t) node, (uint32_t) node->prev, + (uint32_t) node->next); + node = node->next; + } while (node != &self->node); + + fprintf(out, + "===================================================================\n"); +} diff --git a/clib/src/list_iter.c b/clib/src/list_iter.c new file mode 100644 index 0000000..fb1b81e --- /dev/null +++ b/clib/src/list_iter.c @@ -0,0 +1,139 @@ +/* + * Copyright (c) International Business Machines Corp., 2014 + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program 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 General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + */ + +/* + * File: list_iter.c + * Author: Shaun Wetzstein <shaun@us.ibm.com> + * Descr: List iterator + * Note: + * Date: 10/22/10 + */ + +#include <unistd.h> +#include <stdarg.h> +#include <stdlib.h> +#include <malloc.h> +#include <stdint.h> +#include <stdio.h> +#include <string.h> +#include <errno.h> +#include <limits.h> + +#include "libclib.h" +#include "list_iter.h" + +/* ======================================================================= */ + +static inline list_node_t *__list_iter_bwd(list_iter_t * self) +{ + assert(self != NULL); + + assert(self->list != NULL); + assert(self->node != NULL); + + if (self->node == &self->list->node) + self->node = NULL; + else + self->node = list_node_prev(self->node); + + return self->node; +} + +static inline list_node_t *__list_iter_fwd(list_iter_t * self) +{ + assert(self != NULL); + assert(self->list != NULL); + assert(self->node != NULL); + + if (self->node == &self->list->node) + self->node = NULL; + else + self->node = list_node_next(self->node); + + return self->node; +} + +void list_iter_init(list_iter_t * self, list_t * list, uint32_t flags) +{ + assert(self != NULL); + assert(list != NULL); + + self->flags = flags; + self->list = list; + + if (self->flags & LI_FLAG_BWD) + self->node = list_tail(self->list); + else + self->node = list_head(self->list); +} + +void list_iter_clear(list_iter_t * self) +{ + assert(self != NULL); + + if (self->flags & LI_FLAG_BWD) + self->node = list_tail(self->list); + else + self->node = list_head(self->list); +} + +list_node_t *list_iter_elem(list_iter_t * self) +{ + assert(self != NULL); + return self->node; +} + +list_node_t *list_iter_inc1(list_iter_t * self) +{ + return list_iter_inc2(self, 1); +} + +list_node_t *list_iter_inc2(list_iter_t * self, size_t count) +{ + assert(self != NULL); + + for (size_t i = 0; i < count && self->node != NULL; i++) { + if (self->flags & LI_FLAG_BWD) + __list_iter_bwd(self); + else + __list_iter_fwd(self); + } + + return self->node; +} + +list_node_t *list_iter_dec1(list_iter_t * self) +{ + return list_iter_dec2(self, 1); +} + +list_node_t *list_iter_dec2(list_iter_t * self, size_t count) +{ + assert(self != NULL); + + for (size_t i = 0; i < count && self->node != NULL; i++) { + if (self->flags & LI_FLAG_BWD) + __list_iter_fwd(self); + else + __list_iter_bwd(self); + } + + return self->node; +} + +/* ======================================================================= */ diff --git a/clib/src/memory_leak_detection.c b/clib/src/memory_leak_detection.c new file mode 100644 index 0000000..79dc6fb --- /dev/null +++ b/clib/src/memory_leak_detection.c @@ -0,0 +1,1277 @@ +/* + * Copyright (c) International Business Machines Corp., 2011 + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program 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 General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. + * + * Author: B. Rafanello + * + * Module: memory_leak_detection.c + * + * Implements a simple memory leak and buffer overwrite detection + * system. + * + * Version 0.0.0.1 + */ + +#define PROGRAM_VERSION "0.0.0.1" + +#include <stdio.h> +#include <stdlib.h> +#include <pthread.h> +#include <string.h> +#include <errno.h> +#include <execinfo.h> +#include "bb_trace.h" + +/*-------------------------------------------------- + * Private Constants + --------------------------------------------------*/ + +#define LEAK_SIGNATURE 8283471 +#define SENTINEL_VALUE 0xD9B79573 + +/*-------------------------------------------------- + * Private Type definitions + --------------------------------------------------*/ + +typedef unsigned int Sentinel_t; + +struct _Memory_Leak_Data { + unsigned int Signature; /* Indentify this structure in memory */ + void *Mem_Address; /* The address actually returned by malloc. */ + unsigned int User_Size; /* The size of the allocation as requested by the user. */ + unsigned int Alignment; /* The alignment requested by the user. */ + const char *Module_Name; /* The name of the module containing the function which allocated this memory. */ + const char *Function_Name; /* The name of the function which allocated this memory. */ + unsigned int Line_Number; /* The line number of the MALLOC call in the function which allocated this memory. */ + struct _Memory_Leak_Data *Next; /* The next allocated block of memory (if any). */ + struct _Memory_Leak_Data *Previous; /* The previous allocated block of memory (if any). */ + Sentinel_t Starting_Sentinel; /* The starting sentinel used to detect buffer overrun/memory overwrite errors. */ +}; + +typedef struct _Memory_Leak_Data Memory_Leak_Data_t; + +/*-------------------------------------------------- + Private global variables. +--------------------------------------------------*/ + +static pthread_mutex_t Memory_Leak_Lock = PTHREAD_MUTEX_INITIALIZER; /* Mutex to serialize access to the chain of allocations. */ +static Memory_Leak_Data_t *Memory_Chain = NULL; /* The start of our chain of allocations. */ +static unsigned int Memory_Chain_Entries = 0; /* The number of items in our chain. */ + +/*-------------------------------------------------- + Local functions +--------------------------------------------------*/ + +void print_backtrace(void) +{ +#define BT_SIZE 20 + void *bt[BT_SIZE]; + int nr = backtrace(&bt[0], BT_SIZE); + + fprintf(stderr, "========== backtrace ==========\n"); + backtrace_symbols_fd(bt, nr, fileno(stderr)); + fprintf(stderr, "========== backtrace ==========\n"); + + return; +} + +/*********************************************************************/ +/* */ +/* Function Name: Check_Leak_List */ +/* */ +/* Descriptive Name: */ +/* */ +/* Input: */ +/* */ +/* Output: If Success : */ +/* */ +/* If Failure : */ +/* */ +/* Error Handling: */ +/* */ +/* Side Effects: */ +/* */ +/* Notes: */ +/* */ +/*********************************************************************/ +static int Check_Leak_List(const void *p) +{ + Memory_Leak_Data_t *Current_Item; /* Used to walk the memory allocation chain. */ + Memory_Leak_Data_t *Previous_Item; /* Used to check the memory allocation chain. */ + Sentinel_t *Ending_Sentinel; /* To allow access to the sentinel at the end of the allocated memory. */ + unsigned int Data_Start; /* The address of the first byte of the data area of the current allocation. */ + unsigned int Data_End; /* The first byte after the data area of the current allocation. */ + unsigned int Address_To_Test; /* The address we are looking for. */ + unsigned int Address_Found = 2; /* Used to track whether the address was found in the allocation list. + If 2, then the address was not found. If 0, then the address was found and + it is the start of the data area of an allocation. If 1, then the address + was found and it lies within the data area of an allocation. */ + int rc = 0; /* Holds the return code. Assume success. */ + unsigned int Count = 0; + + FUNCTION_ENTRY() + + PRINT_FUNCTION_PARAMETER("Parameters:\n") + PRINT_FUNCTION_PARAMETER(" p = %p\n", p) + + USER3_PRINT_LINE("Memory_Chain = %p", Memory_Chain) + Current_Item = Memory_Chain; + Previous_Item = NULL; + + if (p != NULL) { + USER3_PRINT_LINE + ("Request: Check the memory allocation list for p = %p.\n", + p); + } else { + USER3_PRINT_LINE + ("Request: Check the integrity of the memory allocation list.\n"); + USER3_PRINT_LINE(" Items expected in list: %d\n", + Memory_Chain_Entries); + } + + while (Current_Item != NULL) { + /* Perform some simple checks on the items in the memory allocation list. */ + if (Current_Item->Signature == LEAK_SIGNATURE) { + + if (Current_Item->Starting_Sentinel == SENTINEL_VALUE) { + + /* Check the ending sentinel. */ + Ending_Sentinel = + (Sentinel_t *) ((unsigned int)Current_Item + + sizeof(Memory_Leak_Data_t) + + Current_Item->User_Size); + if (*Ending_Sentinel == SENTINEL_VALUE) { + + /* Check the previous pointer. */ + if (Current_Item->Previous == + Previous_Item) { + + if (p != NULL) { + /* We have an address to check. Does this address lie within this memory allocation? */ + Data_End = + (unsigned long) + Ending_Sentinel; + Data_Start = + (unsigned + long)((unsigned + int) + Current_Item + + + sizeof + (Memory_Leak_Data_t)); + Address_To_Test = + (unsigned long)p; + + if (Address_To_Test == + Data_Start) { + /* This address was returned to the user by MALLOC_func. */ + Address_Found = + 0; + break; + } else { + + if ((Address_To_Test > Data_Start) && (Address_To_Test < Data_End)) { + /* The address lies within the data area of the current allocation. */ + Address_Found + = 1; + break; + } + + } + + } + + } else { + /* We have a pointer problem! The previous pointer field does not point to the previous entry in the list! */ + rc = 3; + fprintf(stderr, + "Link Error! The previous pointer of the current item does not point to the previous item in the allocation list!\n"); + fprintf(stderr, + "Current_Item->Previous = %p, Actual Previous Item is %p.\n", + Current_Item->Previous, + Previous_Item); + fprintf(stderr, + "Item position in list: %d\n", + Count); + print_backtrace(); + } + + } else { + rc = 3; + fprintf(stderr, + "Possible overrun error -- ending sentinel corrupted!\n" + " Header Address: %p\n" + " User Address: %p\n" + " Size: %d\n" + " Allocated in module %s, function %s, at line %d\n", + Current_Item, + (void *)((unsigned int) + Current_Item + + sizeof + (Memory_Leak_Data_t)), + Current_Item->User_Size, + Current_Item->Module_Name, + Current_Item->Function_Name, + Current_Item->Line_Number); + print_backtrace(); + } + + } else { + rc = 3; + fprintf(stderr, + "Memory Overwrite Error! Starting Sentinel is incorrect!\n Following data may be incorrect!\n" + " Header Address: %p\n" + " Address: %p\n" " Size: %d\n" + " Allocated in module %s, function %s, at line %d\n", + Current_Item, + (void *)((unsigned int)Current_Item + + sizeof(Memory_Leak_Data_t)), + Current_Item->User_Size, + Current_Item->Module_Name, + Current_Item->Function_Name, + Current_Item->Line_Number); + print_backtrace(); + } + + Count += 1; + + } else { + rc = 3; + fprintf(stderr, + "Memory Overwrite Error! Memory management data signature is incorrect! Data Dump:\n" + " Header Address: %p\n" + " Signature: Actual[%u, 0x%x], Expected[%u, 0x%x]\n" + " User Address: %p\n" + " Size: [%u, 0x%x]\n" + " Starting Sentinel: Actual[%u, 0x%x], Expected[%u, 0x%x]\n" + " Next: %p\n" " Previous: %p\n" + " Module: %p\n" " Function: %p\n" + " Line [%u, ox%x]\n", Current_Item, + Current_Item->Signature, + Current_Item->Signature, LEAK_SIGNATURE, + LEAK_SIGNATURE, + (void *)((unsigned int)Current_Item + + sizeof(Memory_Leak_Data_t)), + Current_Item->User_Size, + Current_Item->User_Size, + Current_Item->Starting_Sentinel, + Current_Item->Starting_Sentinel, SENTINEL_VALUE, + SENTINEL_VALUE, Current_Item->Next, + Current_Item->Previous, + Current_Item->Module_Name, + Current_Item->Function_Name, + Current_Item->Line_Number, + Current_Item->Line_Number); + fprintf(stderr, + "Memory_Chain = %p\nMemory_Chain_Entries = %u\nCurrent_Item = %p, Count = %u\n\n", + Memory_Chain, Memory_Chain_Entries, + Current_Item, Count); + print_backtrace(); + + break; + } + + Previous_Item = Current_Item; + Current_Item = Current_Item->Next; + } + + if (p != NULL) { + + if (rc == 0) { + rc = Address_Found; + } + + } else { + + if ((Count != Memory_Chain_Entries) && (rc == 0)) { + fprintf(stderr, + "The number of entries found in the allocation list [%u] != list count [%u]!!\n\n", + Count, Memory_Chain_Entries); + print_backtrace(); + rc = 3; + } + + } + + FUNCTION_RETURN("%i", rc) +} + +/*********************************************************************/ +/* */ +/* Function Name: Add_Memory_Allocation_To_Chain */ +/* */ +/* Descriptive Name: Adds a memory tracking object to the list of */ +/* memory tracking objects which represents all */ +/* memory allocations being tracked by this */ +/* module. */ +/* */ +/* Input: Memory_Leak_Data_t * Memory_Leak_Data - The memory */ +/* tracking object to add. */ +/* */ +/* Output: If Success : None. */ +/* */ +/* If Failure : None. */ +/* */ +/* Error Handling: None. */ +/* */ +/* Side Effects: Other memory tracking objects may be modified. */ +/* The count of objects being tracked will be */ +/* incremented. */ +/* */ +/* Notes: */ +/* */ +/*********************************************************************/ +static void Add_Memory_Allocation_To_Chain(Memory_Leak_Data_t * + Memory_Leak_Data) +{ + + FUNCTION_ENTRY() + + PRINT_FUNCTION_PARAMETER("Parameters:\n") + PRINT_FUNCTION_PARAMETER(" Memory_Leak_Data = %p", + Memory_Leak_Data) + + if (Memory_Chain) { + /* Other allocations exist. Insert at the head of the chain. */ + Memory_Leak_Data->Next = Memory_Chain; + Memory_Chain->Previous = Memory_Leak_Data; + } else { + /* This is the first allocation. */ + Memory_Leak_Data->Next = NULL; + } + + /* Update the pointer to the start of the allocation list. */ + Memory_Chain = Memory_Leak_Data; + + /* Update the count of entries in the memory chain. */ + Memory_Chain_Entries += 1; + + FUNCTION_EXIT() +} + +/*********************************************************************/ +/* */ +/* Function Name: Remove_Memory_Allocation_From_Chain */ +/* */ +/* Descriptive Name: Removes a memory tracking object from */ +/* the linked list of memory tracking */ +/* objects representing current memory */ +/* allocations. */ +/* */ +/* Input: Memory_Leak_Data_t * Memory_Leak_Data - the memory */ +/* tracking object to remove. */ +/* */ +/* Output: If Success : None. */ +/* */ +/* If Failure : None. */ +/* */ +/* Error Handling: None. */ +/* */ +/* Side Effects: Other memory tracking objects may be modified. */ +/* The memory tracking object being removed will be */ +/* zeroed out and freed. */ +/* */ +/* Notes: */ +/* */ +/*********************************************************************/ +static void Remove_Memory_Allocation_From_Chain(Memory_Leak_Data_t * + Memory_Leak_Data) +{ + Memory_Leak_Data_t *Temp; /* Used when adjusting the memory allocation chain. */ + Sentinel_t *Ending_Sentinel; /* To allow access to the sentinel at the end of the allocated memory. */ + + FUNCTION_ENTRY() + + /* Are we the first item in the chain? */ + if (Memory_Leak_Data->Previous == NULL) { + + /* We are at the head of the chain, which means that Memory_Chain points to us! + * Point Memory_Chain to the Memory_Leak_Data_t that follows us (if any). + */ + Memory_Chain = Memory_Leak_Data->Next; + + /* Is there another item in the chain? If so, update it. */ + if (Memory_Chain != NULL) + Memory_Chain->Previous = NULL; + + } else { + + /* Are we the last item in the chain? */ + if (Memory_Leak_Data->Next == NULL) { + + /* We are at the end of the memory chain with at least 1 entry before us. */ + Temp = Memory_Leak_Data->Previous; + Temp->Next = NULL; + } else { + /* We are in the middle of the chain. */ + Temp = Memory_Leak_Data->Previous; + Temp->Next = Memory_Leak_Data->Next; + Temp = Memory_Leak_Data->Next; + Temp->Previous = Memory_Leak_Data->Previous; + } + + } + + /* Adjust the count of entries in the memory chain. */ + Memory_Chain_Entries -= 1; + + /* Calculate the address of the ending sentinel so that we can access it. */ + Ending_Sentinel = + (Sentinel_t *) ((unsigned int)Memory_Leak_Data + + sizeof(Memory_Leak_Data_t) + + Memory_Leak_Data->User_Size); + + /* Clean out the memory leak data. */ + Memory_Leak_Data->Function_Name = NULL; + Memory_Leak_Data->Line_Number = 0; + Memory_Leak_Data->Module_Name = NULL; + Memory_Leak_Data->Signature = 0; + Memory_Leak_Data->Starting_Sentinel = 0; + Memory_Leak_Data->User_Size = 0; + Memory_Leak_Data->Next = NULL; + Memory_Leak_Data->Previous = NULL; + *Ending_Sentinel = 0; + + free(Memory_Leak_Data->Mem_Address); + + FUNCTION_EXIT() +} + +/*-------------------------------------------------- + API Functions +--------------------------------------------------*/ + +/*********************************************************************/ +/* */ +/* Function Name: Print_Leak_List */ +/* */ +/* Descriptive Name: This function walks the list of allocated */ +/* memory blocks and prints information about */ +/* each one. If this is done at program exit, */ +/* the resulting list of memory blocks most */ +/* likely represents leaked memory. */ +/* */ +/* Input: None. */ +/* */ +/* Output: If Success : If there are any memory blocks being */ +/* tracked by this module, information about */ +/* block still being tracked will be sent to */ +/* stderr. */ +/* */ +/* If Failure : Error messages may be sent to stderr. */ +/* */ +/* Error Handling: If errors are detected, then error messages are */ +/* output on stderr. */ +/* */ +/* Side Effects: The internal structures of this module are checked*/ +/* for errors with any errors being reported on */ +/* stderr. */ +/* */ +/* Notes: */ +/* */ +/*********************************************************************/ +void Print_Leak_List(void) +{ + Memory_Leak_Data_t *Current_Item; /* Used to walk the memory allocation chain. */ + Sentinel_t *Ending_Sentinel; /* To allow access to the sentinel at the end of the allocated memory. */ + + API_FUNCTION_ENTRY() + + /* Get lock. */ + pthread_mutex_lock(&Memory_Leak_Lock); + + Current_Item = Memory_Chain; + + fprintf(stderr, + "\n\nMemory_Chain is %p, and Memory_Chain_Entries is %u.\n", + Memory_Chain, Memory_Chain_Entries); + fprintf(stderr, "\nCurrent Memory Allocation List\n\n"); + + while (Current_Item != NULL) { + /* Perform some simple checks on the data before we print it. */ + if (Current_Item->Signature == LEAK_SIGNATURE) { + + if (Current_Item->Starting_Sentinel == SENTINEL_VALUE) { + + /* Check the ending sentinel. */ + Ending_Sentinel = + (Sentinel_t *) ((unsigned int)Current_Item + + sizeof(Memory_Leak_Data_t) + + Current_Item->User_Size); + if (*Ending_Sentinel == SENTINEL_VALUE) { + fprintf(stderr, + "Memory Allocation Record\n"); + } else { + fprintf(stderr, + "\nPossible overrun error -- ending sentinel corrupted!\n"); + } + + fprintf(stderr, + " Allocation Block: %p\n" + " Header Address: %p\n" + " User Address: %p\n" + " Alignment: %u\n" + " Size: %d\n" + " Allocated in module %s, function %s, at line %d\n\n", + Current_Item->Mem_Address, + Current_Item, + (void *)((unsigned int)Current_Item + + sizeof(Memory_Leak_Data_t)), + Current_Item->Alignment, + Current_Item->User_Size, + Current_Item->Module_Name, + Current_Item->Function_Name, + Current_Item->Line_Number); + } else { + fprintf(stderr, + "\nMemory Overwrite Error! Starting Sentinel is incorrect!\n Following data may be incorrect!\n"); + fprintf(stderr, + " Allocation Block: %p\n" + " Header Address: %p\n" + " User Address: %p\n" + " Alignment: %u\n" " Size: %d\n" + " Allocated in module %s, function %s, at line %d\n\n", + Current_Item->Mem_Address, Current_Item, + (void *)((unsigned int)Current_Item + + sizeof(Memory_Leak_Data_t)), + Current_Item->Alignment, + Current_Item->User_Size, + Current_Item->Module_Name, + Current_Item->Function_Name, + Current_Item->Line_Number); + } + + } else { + fprintf(stderr, + "\n\nMemory Overwrite Error! Memory management data signature is incorrect! Data Dump:\n"); + fprintf(stderr, + " Allocation Block: %p\n" + " Header Address: %p\n" + " Signature: Actual[%u, 0x%x], Expected[%u, 0x%x]\n" + " Address: %p\n" " Alignment: %u\n" + " Size: [%u, 0x%x]\n" + " Starting Sentinel: Actual[%u, 0x%x], Expected[%u, 0x%x]\n" + " Next: %p\n" " Previous: %p\n" + " Module: %p\n" " Function: %p\n" + " Line [%u, ox%x]\n", + Current_Item->Mem_Address, Current_Item, + Current_Item->Signature, + Current_Item->Signature, LEAK_SIGNATURE, + LEAK_SIGNATURE, + (void *)((unsigned int)Current_Item + + sizeof(Memory_Leak_Data_t)), + Current_Item->Alignment, + Current_Item->User_Size, + Current_Item->User_Size, + Current_Item->Starting_Sentinel, + Current_Item->Starting_Sentinel, SENTINEL_VALUE, + SENTINEL_VALUE, Current_Item->Next, + Current_Item->Previous, + Current_Item->Module_Name, + Current_Item->Function_Name, + Current_Item->Line_Number, + Current_Item->Line_Number); + fprintf(stderr, + "Memory_Chain = %p\nMemory_Chain_Entries = %u\nCurrent_Item = %p\n\n", + Memory_Chain, Memory_Chain_Entries, + Current_Item); + break; + } + + Current_Item = Current_Item->Next; + } + + /* Release lock. */ + pthread_mutex_unlock(&Memory_Leak_Lock); + + API_FUNCTION_EXIT() + +} + +/*********************************************************************/ +/* */ +/* Function Name: MEMORY_func */ +/* */ +/* Descriptive Name: This function acts as a replacement for */ +/* malloc. It allocates memory (using malloc) */ +/* and enters that memory into a tracking */ +/* structure so that memory leaks, if any, may */ +/* be found. */ +/* */ +/* Input: size_t sz - The number of bytes to be allocated. */ +/* unsigned int Alignment - 0 for non-aligned (normal) */ +/* malloc, > 0 to return an */ +/* address aligned on a specific */ +/* memory boundary. If > 0, then */ +/* Alignment must be a power of 2 */ +/* and a multiple of sizeof(void *)*/ +/* void ** Memory_Location - The address of a variable which*/ +/* will hold the address of the */ +/* allocated by this function. */ +/* const char * mod_name - The name of the module from which*/ +/* this function was called. */ +/* const char * func - The name of the function from which */ +/* this function was called. */ +/* const int line - The line number of the code containing */ +/* the call to this function. */ +/* */ +/* Output: If Success : The function return value will be 0. */ +/* *Memory_Location will be set to the address*/ +/* of the first byte of the user portion of */ +/* any memory that was allocated. */ +/* */ +/* If Failure : The function return value will be EINVAL or*/ +/* ENOMEM. Errors may be reported on stderr. */ +/* *Memory_Location will be set to NULL. */ +/* */ +/* Error Handling: This function will abort if an error is */ +/* is detected. Errors could be lack of memory, or*/ +/* corruption of the internal structures used to */ +/* track allocated blocks of memory. */ +/* */ +/* Side Effects: Memory may be allocated, errors may be reported */ +/* on stderr. */ +/* */ +/* Notes: */ +/* */ +/*********************************************************************/ +int MEMORY_func(size_t sz, + unsigned int Alignment, + void **Memory_Location, + const char *mod_name, const char *func, const int line) +{ + Memory_Leak_Data_t *Memory_Leak_Data; /* For accessing our memory tracking data. */ + void *ptr = NULL; /* To hold the address that will be returned to the caller. */ + size_t New_Size; /* Used to adjust the size of the memory allocation. */ + Sentinel_t *Ending_Sentinel; /* To allow access to the sentinel at the end of the allocated memory. */ + unsigned int Proposed_User_Address; /* Used to calculate the address to return to the caller. */ + unsigned int Shift_Amount; /* Used when adjusting the address returned to caller to ensure proper alignment. */ + int Error = 0; + unsigned int i = 0; /* Used when calculating powers of two to check the alignment. */ + unsigned int Power_Of_Two = 1; /* Used when calculating powers of two to check the alignment. */ + +#define MAX_POWER_OF_TWO 31 + + API_FUNCTION_ENTRY() + + PRINT_API_PARAMETER("Parameters:\n") + PRINT_API_PARAMETER(" sz = %d", sz) + PRINT_API_PARAMETER(" Alignment = %d", Alignment) + PRINT_API_PARAMETER(" Memory_Location = %p", Memory_Location) + PRINT_API_PARAMETER(" mod_name = %s", mod_name) + PRINT_API_PARAMETER(" func = %s", func) + PRINT_API_PARAMETER(" line = %i", line) + + /* Check the size of the request. */ + if (sz == 0) { + Error = EINVAL; + fprintf(stderr, + "MALLOC: request is invalid - size[%u] in module %s, function %s at line %d\n", + sz, mod_name, func, line); + print_backtrace(); + } + + /* Check the alignment, if one was specified. */ + if (Alignment > 0) { + if (Alignment % sizeof(void *)) { + /* Improper alignment! */ + Error = EINVAL; + } else { + do { + Power_Of_Two *= 2; + i++; + } while ((Power_Of_Two != Alignment) + && (i < MAX_POWER_OF_TWO)); + + if (Power_Of_Two != Alignment) { + Error = EINVAL; + } + + } + + if (Error) { + fprintf(stderr, + "MEMORY_func: request for aligned memory uses invalid alignment! size[%u], alignment [%u] in module %s, function %s at line %d\n", + sz, Alignment, mod_name, func, line); + } + + } + + if (Memory_Location == NULL) { + Error = EINVAL; + fprintf(stderr, + "MEMORY_func: Location to place address of allocated memory is NULL! size[%u], alignment [%u] in module %s, function %s at line %d\n", + sz, Alignment, mod_name, func, line); + } else + *Memory_Location = NULL; + + if (Error != 0) { + API_FUNCTION_RETURN("%i", Error); + } + + USER3_PRINT_LINE + ("MEMORY_func: processing request - size[%u], alignment[%u] from module %s, function %s at line %d\n", + sz, Alignment, mod_name, func, line); + + /* Check */ + + /* Get lock. */ + pthread_mutex_lock(&Memory_Leak_Lock); + + /* Check the memory allocation list. If the list is bad, then abort because we are already screwed ... */ + if (!Check_Leak_List(NULL)) { + + /* Adjust the size of the request to account for the additional memory we need to track this request. */ + New_Size = + sz + sizeof(Memory_Leak_Data_t) + sizeof(Sentinel_t) + + Alignment; + + /* Get the memory. */ + ptr = malloc(New_Size); + + /* Was the memory available? */ + if (ptr != NULL) { + /* Determine where to put our memory leak data. */ + if (Alignment == 0) { + /* We can place the memory leak data right at the start of the memory block we got from malloc. */ + Memory_Leak_Data = (Memory_Leak_Data_t *) ptr; + } else { + Proposed_User_Address = + (unsigned int)ptr + + sizeof(Memory_Leak_Data_t); + Shift_Amount = + Alignment - + (Proposed_User_Address % Alignment); + Memory_Leak_Data = + (Memory_Leak_Data_t *) ((unsigned int)ptr + + Shift_Amount); + } + + /* Save the address returned by malloc() for use with free(). */ + Memory_Leak_Data->Mem_Address = ptr; + + /* Create the address to return to the caller. This address should be the first byte after + our memory leak data. */ + ptr = + (void *)((unsigned int)Memory_Leak_Data + + sizeof(Memory_Leak_Data_t)); + + /* Calculate the address of the trailing sentinel. */ + Ending_Sentinel = + (Sentinel_t *) ((unsigned int)ptr + sz); + + /* Initialize our memory leak data. */ + Memory_Leak_Data->Signature = LEAK_SIGNATURE; + Memory_Leak_Data->User_Size = sz; + Memory_Leak_Data->Alignment = Alignment; + Memory_Leak_Data->Module_Name = mod_name; + Memory_Leak_Data->Function_Name = func; + Memory_Leak_Data->Line_Number = line; + Memory_Leak_Data->Previous = NULL; + Memory_Leak_Data->Next = NULL; + Memory_Leak_Data->Starting_Sentinel = SENTINEL_VALUE; + *Ending_Sentinel = SENTINEL_VALUE; + + USER3_PRINT_LINE + ("MALLOC: Allocated header at %p ( = user address %p) size[%u] in module %s, function %s at line %d\n", + Memory_Leak_Data, ptr, sz, mod_name, func, line); + Add_Memory_Allocation_To_Chain(Memory_Leak_Data); + USER3_PRINT_LINE + ("MALLOC: Memory_Chain is %p, and Memory_Chain_Entries is %u.\n", + Memory_Chain, Memory_Chain_Entries); + + /* Set up return value. */ + *Memory_Location = ptr; + } else { + + fprintf(stderr, + "MALLOC: Memory allocation failed - no more memory available at this time!\n"); + print_backtrace(); + + USER3_PRINT_LINE + ("MALLOC: request was issued from module %s, function %s at line %d\n", + mod_name, func, line); + + } + + } else { + fprintf(stderr, + "MALLOC: Found the memory leak data to be corrupted! Aborting!\n"); + print_backtrace(); + } + + /* Release lock. */ + pthread_mutex_unlock(&Memory_Leak_Lock); + + API_FUNCTION_RETURN("%i", Error) + +} + +/*********************************************************************/ +/* */ +/* Function Name: MALLOC_func */ +/* */ +/* Descriptive Name: This function acts as a replacement for */ +/* malloc. It allocates memory (using malloc) */ +/* and enters that memory into a tracking */ +/* structure so that memory leaks, if any, may */ +/* be found. */ +/* */ +/* Input: size_t sz - The number of bytes to be allocated. */ +/* const char * mod_name - The name of the module from which*/ +/* this function was called. */ +/* const char * func - The name of the function from which */ +/* this function was called. */ +/* const int line - The line number of the code containing */ +/* the call to this function. */ +/* */ +/* Output: If Success : The function return value will be non-NULL.*/ +/* */ +/* If Failure : The function return value will be NULL. */ +/* Errors may be reported on stderr. */ +/* */ +/* Error Handling: This function will abort if an error is */ +/* is detected. Errors could be lack of memory, or*/ +/* corruption of the internal structures used to */ +/* track allocated blocks of memory. */ +/* */ +/* Side Effects: Memory may be allocated, errors may be reported */ +/* on stderr. */ +/* */ +/* Notes: */ +/* */ +/*********************************************************************/ +void *MALLOC_func(size_t sz, const char *mod_name, const char *func, + const int line) +{ + void *Return_Value; + int Error; + + Error = MEMORY_func(sz, 0, &Return_Value, mod_name, func, line); + + if (Error != 0) + return NULL; + else + return Return_Value; +} + +/*********************************************************************/ +/* */ +/* Function Name: FREE_func */ +/* */ +/* Descriptive Name: This function frees a block of memory being */ +/* tracked by this module and removes the block */ +/* from its tracking structures. */ +/* */ +/* Input: const void * p - The address of the block of memory to */ +/* be freed. */ +/* const char * mod_name - The name of the module requesting*/ +/* the block of memory be freed. */ +/* const char * func - The name of the function requesting */ +/* the block of memory be freed. */ +/* const int line - The line number of the line of code in */ +/* module calling this function. */ +/* */ +/* Output: If Success : None. */ +/* */ +/* If Failure : Errors may be reported to stderr. */ +/* */ +/* Error Handling: This function causes the internal structures */ +/* of this module to be checked as part of the */ +/* process of freeing the address p. This may */ +/* cause errors to be reported on stderr. If any */ +/* errors are found, then the address p may not be */ +/* freed. */ +/* */ +/* Side Effects: The block of memory associated with the address p */ +/* will be freed and available for reallocation. */ +/* Also, the memory tracking structures in this */ +/* module will undergo a series of checks. */ +/* */ +/* Notes: This function was not intended to be called directly but */ +/* rather through the macro FREE. */ +/* */ +/*********************************************************************/ +void FREE_func(const void *p, const char *mod_name, const char *func, + const int line) +{ + Memory_Leak_Data_t *Memory_Leak_Data; /* For accessing our memory tracking data. */ + + API_FUNCTION_ENTRY() + + PRINT_API_PARAMETER("Parameters:\n") + PRINT_API_PARAMETER(" p = %p", p) + PRINT_API_PARAMETER(" mod_name = %s", mod_name) + PRINT_API_PARAMETER(" func = %s", func) + PRINT_API_PARAMETER(" line = %i", line) + + /* Check the address passed to us. It must not be NULL, and must be > sizeof(Memory_Leak_Data_t) to + * prevent wrap around when we subtract sizeof(Memory_Leak_Data_t) to get the starting address of + * the memory leak data associated with p. + */ + if ((p == NULL) || ((unsigned int)p <= sizeof(Memory_Leak_Data_t))) { + fprintf(stderr, + "FREE: request has invalid user address [%p]. Request came from module %s, function %s, line %d\n", + p, mod_name, func, line); + print_backtrace(); + return; + } else { + USER3_PRINT_LINE + ("FREE: request to free [%p] received from module %s, function %s, line %d\n", + p, mod_name, func, line); + } + + /* Get lock. */ + pthread_mutex_lock(&Memory_Leak_Lock); + + /* Check the memory allocation list for errors. */ + if (!Check_Leak_List(NULL)) { + + /* Is the address given to us in the memory allocation list? */ + if (!Check_Leak_List(p)) { + /* Get access to the memory leak data. */ + Memory_Leak_Data = + (Memory_Leak_Data_t *) ((unsigned int)p - + sizeof(Memory_Leak_Data_t)); + + USER3_PRINT_LINE + ("FREE: Calling free on header address %p ( = user address %p) from module %s, function %s, line %d\n", + Memory_Leak_Data, p, mod_name, func, line); + Remove_Memory_Allocation_From_Chain(Memory_Leak_Data); + USER3_PRINT_LINE + ("FREE: Memory_Chain is %p, and Memory_Chain_Entries is %u.\n", + Memory_Chain, Memory_Chain_Entries); + + } else { + /* The address given to us was not in the memory allocation list! If we free this address, who knows what will happen! */ + fprintf(stderr, + "FREE: Invalid address! The address %p was not provided by MALLOC or has been passed to FREE more than once!\n", + p); + fprintf(stderr, + " Request came from module %s, function %s, line %d\n", + mod_name, func, line); + print_backtrace(); + } + + } else { + fprintf(stderr, + "FREE: Aborting due to errors in the memory leak data!\n"); + USER3_PRINT_LINE + ("FREE: request was submitted by module %s, function %s at line %d\n", + mod_name, func, line); + print_backtrace(); + + } + + pthread_mutex_unlock(&Memory_Leak_Lock); + + USER3_PRINT_LINE("FREE: request is complete.\n"); + + API_FUNCTION_EXIT() +} + +/*********************************************************************/ +/* */ +/* Function Name: Test_Address_Allocation */ +/* */ +/* Descriptive Name: This function tests the specified address to */ +/* to see if it lies within an allocated block */ +/* tracked by this module. */ +/* */ +/* Input: void * p - The address to be tested. */ +/* */ +/* Output: If Success : If the address p was found, then 0 will be */ +/* returned if the address is the start of */ +/* a block of allocated memory. If the */ +/* address p was found within an allocated */ +/* block of memory, then 1 is returned. */ +/* */ +/* If Failure : If the address p was NOT found, then 2 is */ +/* returned. If there was an error in the */ +/* memory tracking system then 3 will be */ +/* returned. */ +/* */ +/* Error Handling: This function relies on the error handling */ +/* built into the Check_Leak_List function and */ +/* has no error handling of its own. */ +/* */ +/* Side Effects: If the list of memory allocations contains errors */ +/* then those errors will be detected and reported */ +/* on stderr. */ +/* */ +/* Notes: If NULL is passed in as the address to test, then the */ +/* integrity of the internal tracking structures will be */ +/* checked, in which case a return value of 0 signifies */ +/* that the internal tracking structures have passed the */ +/* checks and a return value of 3 indicates that errors */ +/* were found. */ +/* */ +/*********************************************************************/ +unsigned int Test_Address_Allocation(void *p) +{ + unsigned int rc = 0; + + API_FUNCTION_ENTRY() + + PRINT_API_PARAMETER("Parameters:\n") + PRINT_API_PARAMETER(" p = %p", p) + + /* Get lock. */ + pthread_mutex_lock(&Memory_Leak_Lock); + + rc = Check_Leak_List(p); + + /* Release lock. */ + pthread_mutex_unlock(&Memory_Leak_Lock); + + API_FUNCTION_RETURN("%i", rc); +} + +/*********************************************************************/ +/* */ +/* Function Name: Duplicate_String */ +/* */ +/* Descriptive Name: This function duplicates a string. The memory*/ +/* allocated for the duplicate is allocated */ +/* using the MALLOC_func routine in this module */ +/* and is thus tracked by this module. */ +/* */ +/* Input: const char * Source - The string to be copied. */ +/* const char * mod_name - The name of the module containing*/ +/* the function which called this */ +/* function. */ +/* const char * func - The name of the function calling */ +/* this function. */ +/* const int line - The line number of the line of code in */ +/* module calling this function. */ +/* */ +/* Output: If Success : The function return value will be non-NULL */ +/* and will point to a duplicate of the */ +/* string given in Source. */ +/* */ +/* If Failure : The function return value will be NULL. */ +/* */ +/* Error Handling: Any errors detected by this function result in */ +/* a function return value of NULL. */ +/* */ +/* Side Effects: The memory tracking features of this module are */ +/* employed to allocate memory for the duplicate */ +/* string produced by this funciton. */ +/* */ +/* Notes: */ +/* */ +/*********************************************************************/ +char *Duplicate_String(const char *Source, + const char *mod_name, const char *func, const int line) +{ + char *Result; + + Result = (char *)MALLOC_func(strlen(Source) + 1, mod_name, func, line); + if (Result != NULL) + strcpy(Result, Source); + + return Result; +} + +/*********************************************************************/ +/* */ +/* Function Name: Realloc_func */ +/* */ +/* Descriptive Name: This function performs the same function as */ +/* the realloc function in the ANSI C library. */ +/* */ +/* Input: const void * p - The address of the block of memory to */ +/* be reallocated. */ +/* size_t size - The size of the memory block to return. */ +/* const char * mod_name - The name of the module requesting*/ +/* the block of memory be freed. */ +/* const char * func - The name of the function requesting */ +/* the block of memory be freed. */ +/* const int line - The line number of the line of code in */ +/* module calling this function. */ +/* */ +/* Output: If Success : The function return value will be a pointer*/ +/* to the new block of memory. */ +/* */ +/* If Failure : NULL will be returned and errno will be set*/ +/* to a non-null error code. */ +/* */ +/* Error Handling: This function causes the internal structures */ +/* of this module to be checked. This may */ +/* cause errors to be reported on stderr. If any */ +/* errors are found, then the address p may not be */ +/* freed. */ +/* */ +/* Side Effects: A new block of memory of size bytes will be */ +/* allocated, the contents of the current block will */ +/* be copied to the new block (at least as much as */ +/* will fit, and the current block will be freed. */ +/* This will cause internal structures in this module*/ +/* to be modified accordingly. */ +/* */ +/* Notes: This function was not intended to be called directly but */ +/* rather through the macro REALLOC. */ +/* */ +/* If p is NULL, then this will cause this function to */ +/* behave like malloc. */ +/* */ +/* If size is 0, then this will cause this function to */ +/* behave like free. */ +/* */ +/*********************************************************************/ +void *Realloc_func(void *p, size_t size, const char *mod_name, const char *func, + const int line) +{ + Memory_Leak_Data_t *Memory_Leak_Data; /* For accessing our memory tracking data. */ + int Error = 0; + unsigned int Copy_Size = 0; + void *Return_Value = NULL; + + API_FUNCTION_ENTRY() + + PRINT_API_PARAMETER("Parameters:\n") + PRINT_API_PARAMETER(" p = %p", p) + PRINT_API_PARAMETER(" size = %u", size) + PRINT_API_PARAMETER(" mod_name = %s", mod_name) + PRINT_API_PARAMETER(" func = %s", func) + PRINT_API_PARAMETER(" line = %i", line) + + /* Check the address passed to us. If it is NULL and size > 0, then we are merely doing a malloc. */ + if ((p == NULL) && (size > 0)) { + USER3_PRINT_LINE + ("REALLOC: p was NULL and size > 0, acting as MALLOC.\n") + Return_Value = MALLOC_func(size, mod_name, func, line); + if (Return_Value == NULL) { + errno = ENOMEM; + } + } else { + /* If size is 0 and p is not NULL, then we are doing a free. */ + if ((p != NULL) && (size == 0)) { + USER3_PRINT_LINE + ("REALLOC: p was non-NULL but size is 0, acting as FREE.\n") + FREE_func(p, mod_name, func, line); + } else { + /* Do we have real work to do? */ + if ((p != NULL) && (size != 0)) { + USER3_PRINT_LINE + ("REALLOC: p was non-NULL and size > 0, we have actual work to do!.\n") + + /* Get lock. */ + pthread_mutex_lock(&Memory_Leak_Lock); + + /* Check the memory allocation list for errors. */ + if (!Check_Leak_List(NULL)) { + + /* Is the address given to us in the memory allocation list? */ + if (!Check_Leak_List(p)) { + /* Get access to the memory leak data. */ + Memory_Leak_Data = + (Memory_Leak_Data_t + *) ((unsigned int)p - + sizeof + (Memory_Leak_Data_t)); + + /* Release the lock so that MEMORY_func can get it. */ + pthread_mutex_unlock + (&Memory_Leak_Lock); + + /* Call MEMORY_func to get the memory we need and add it to the list of memory blocks we are tracking. */ + Error = + MEMORY_func(size, + Memory_Leak_Data-> + Alignment, + &Return_Value, + mod_name, func, + line); + if (Error != 0) { + Return_Value = NULL; + errno = ENOMEM; + } else { + + /* We have the replacement memory. Now lets copy what we can from the original block to the new block. */ + if (size > + Memory_Leak_Data-> + User_Size) { + Copy_Size = + Memory_Leak_Data-> + User_Size; + } else { + Copy_Size = + size; + } + + /* Copy the data to be preserved from the original memory block to the new memory block. */ + memcpy(Return_Value, p, + Copy_Size); + + /* Zero out the original memory block ... this can catch errors as users should not assume that + * realloc will leave their original memory block intact. + */ + memset(p, 0x0, + Memory_Leak_Data-> + User_Size); + + /* Get the lock again. */ + pthread_mutex_lock + (&Memory_Leak_Lock); + + USER3_PRINT_LINE + ("REALLOC: Calling free on header address %p ( = user address %p) from module %s, function %s, line %d\n", + Memory_Leak_Data, + p, mod_name, func, + line); + Remove_Memory_Allocation_From_Chain + (Memory_Leak_Data); + USER3_PRINT_LINE + ("REALLOC: Memory_Chain is %p, and Memory_Chain_Entries is %u.\n", + Memory_Chain, + Memory_Chain_Entries); + + } + + } else { + /* The address given to us was not in the memory allocation list! If we free this address, who knows what will happen! */ + fprintf(stderr, + "REALLOC: Invalid address! The address %p was not provided by MALLOC or has been passed to FREE already!\n", + p); + fprintf(stderr, + " Request came from module %s, function %s, line %d\n", + mod_name, func, line); + print_backtrace(); + } + + } else { + fprintf(stderr, + "REALLOC: Aborting due to errors in the memory leak data!\n"); + USER3_PRINT_LINE + ("REALLOC: request was submitted by module %s, function %s at line %d\n", + mod_name, func, line); + print_backtrace(); + + } + + pthread_mutex_unlock(&Memory_Leak_Lock); + + } + + } + + } + + USER3_PRINT_LINE("REALLOC: request is complete.\n"); + + API_FUNCTION_RETURN("%p", Return_Value) +} diff --git a/clib/src/misc.c b/clib/src/misc.c new file mode 100644 index 0000000..c79bd13 --- /dev/null +++ b/clib/src/misc.c @@ -0,0 +1,234 @@ +/* + * Copyright (c) International Business Machines Corp., 2014 + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program 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 General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + */ + +/* + * File: misc.c + * Author: Shaun Wetzstein <shaun@us.ibm.com> + * Descr: + * Note: + * Date: 07/26/09 + */ + +#include <stdarg.h> +#include <stdlib.h> +#include <stdint.h> +#include <stdio.h> +#include <string.h> +#include <errno.h> +#include <ctype.h> + +#include "misc.h" + +inline void prefetch(void *addr, size_t len, ...) +{ + va_list v; + va_start(v, len); + int w = va_arg(v, int); + int l = va_arg(v, int); + va_end(v); + + while (0 < len) { + if (w) { + switch (l) { + case 0: + __builtin_prefetch(addr, 1, 0); + break; + case 1: + __builtin_prefetch(addr, 1, 1); + break; + case 2: + __builtin_prefetch(addr, 1, 2); + break; + } + } else { + switch (l) { + case 0: + __builtin_prefetch(addr, 0, 0); + break; + case 1: + __builtin_prefetch(addr, 0, 1); + break; + case 2: + __builtin_prefetch(addr, 0, 2); + break; + } + } + len -= sizeof addr; + } +} + +unsigned long align(unsigned long size, unsigned long offset) +{ + --offset; + return (size + offset) & ~offset; +} + +void print_binary(FILE * __out, void *__data, size_t __len) +{ + static const char *__ascii[] = { + "0000", "0001", "0010", "0011", "0100", "0101", "0110", "0111", + "1000", "1001", "1010", "1011", "1100", "1101", "1110", "1111", + }; + + if (__data == NULL) + return; + if (__out == NULL) + __out = stdout; + + size_t i; + for (i = 0; i < __len; i++) { + unsigned char c = *(unsigned char *)(__data + i); + + fprintf(__out, "%4.4s%4.4s", + __ascii[(c & 0xF0) >> 4], __ascii[c & 0x0F]); + } +} + +#if 0 +void dump_memory(FILE * file, unsigned long addr, const void *buf, size_t size) +{ + if (size <= 0 || buf == NULL) + return; + if (file == NULL) + file = stdout; + + unsigned long *ul = (unsigned long *)buf; + char hex[64] = { 0, }, ascii[32] = { + 0,}, c; + int hl = 0, al = 0; + + int cnt = size / sizeof(unsigned long); + + int i; + for (i = 0; i < cnt; i++) { + hl += snprintf(hex + hl, sizeof hex, "%08lx", ul[i]); + + c = (ul[i] & 0xFF000000) >> 24; + al += + snprintf(ascii + al, sizeof ascii, "%c", + (isprint(c) ? c : '.')); + + c = (ul[i] & 0x00FF0000) >> 16; + al += + snprintf(ascii + al, sizeof ascii, "%c", + (isprint(c) ? c : '.')); + + c = (ul[i] & 0x0000FF00) >> 8; + al += + snprintf(ascii + al, sizeof ascii, "%c", + (isprint(c) ? c : '.')); + + c = (ul[i] & 0x000000FF) >> 0; + al += + snprintf(ascii + al, sizeof ascii, "%c", + (isprint(c) ? c : '.')); + + if ((i + 1) % 4 == 0) { + fprintf(file, " %08lx [%s] [%s]\n", addr, hex, ascii); + + addr += 4 * sizeof(unsigned long); + hl = al = 0; + + memset(hex, 0, sizeof hex); + memset(ascii, 0, sizeof ascii); + } else { + hl += snprintf(hex + hl, sizeof hex, " "); + } + } + + int j; + for (j = 0; j < (i % 4); j++) { + hl += snprintf(hex + hl, sizeof hex, "%08lx ", 0ul); + al += snprintf(ascii + al, sizeof ascii, "%4.4s", "...."); + } + + if (i % 4 != 0) { + fprintf(file, " %08lx [%s] [%s]\n", addr, hex, ascii); + } + + return; +} +#endif + +/* + * "aaaaaaaa [wwwwwwww xxxxxxxx yyyyyyyy zzzzzzzz] [........ ........]" + */ +void dump_memory(FILE * __out, uint32_t __addr, const void *__restrict __buf, + size_t __buf_sz) +{ + if (__buf_sz <= 0 || __buf == NULL) + return; + if (__out == NULL) + __out = stdout; + + size_t hex_size = 16 * 2; // 16 bytes per doubleword + size_t ascii_size = 8 * 2; // 8 bytes per doubleword + + uint8_t hex[hex_size + 1], ascii[hex_size + 1]; + memset(hex, '.', hex_size), memset(ascii, '.', ascii_size); + + void print_line(void) { + fprintf(__out, "%08x ", __addr); + + fprintf(__out, "[%.8s %.8s %.8s %.8s] ", + hex + 0, hex + 8, hex + 16, hex + 24); + + fprintf(__out, "[%.8s %.8s]\n", ascii + 0, ascii + 8); + } + + size_t s = __addr % 16, i = 0; + __addr &= ~0xF; + + for (i = s; i < __buf_sz + s; i++) { + unsigned char c = ((unsigned char *)__buf)[i - s]; + + hex[((i << 1) + 0) % hex_size] = "0123456789abcdef"[c >> 4]; + hex[((i << 1) + 1) % hex_size] = "0123456789abcdef"[c & 0xf]; + + ascii[i % ascii_size] = isprint(c) ? c : '.'; + + if (i == 0) + continue; + + if ((i + 1) % ascii_size == 0) { + print_line(); + memset(hex, '.', hex_size), memset(ascii, '.', + ascii_size); + + __addr += ascii_size; + } + } + + if (i % ascii_size) + print_line(); + + return; +} + +int __round_pow2(int size) +{ + size--; + + size |= size >> 1; + size |= size >> 2; + size |= size >> 4; + size |= size >> 8; + size |= size >> 16; + + return ++size; +} diff --git a/clib/src/mq.c b/clib/src/mq.c new file mode 100644 index 0000000..6faf108 --- /dev/null +++ b/clib/src/mq.c @@ -0,0 +1,208 @@ +/* + * Copyright (c) International Business Machines Corp., 2014 + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program 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 General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + */ + +/* + * File: mqueue.c + * Author: Shaun Wetzstein <shaun@us.ibm.com> + * Descr: POSIX message queue wrapper + * Note: + * Date: 10/07/10 + */ + +#include <unistd.h> +#include <stdarg.h> +#include <stdlib.h> +#include <malloc.h> +#include <stdint.h> +#include <stdio.h> +#include <string.h> +#include <errno.h> +#include <limits.h> +#include <fcntl.h> + +#include <sys/types.h> +#include <sys/stat.h> + +#include "libclib.h" +#include "mq.h" + +#define MQUEUE_ROOT "/dev/mqueue" + +/* ======================================================================= */ + +int mqueue_init(mqueue_t * self, const char *service) +{ + assert(self != NULL); + + self->service = strdup(service); + self->in = self->out = (mqd_t) - 1; + + return 0; +} + +int mqueue_create(mqueue_t * self, pid_t tid) +{ + assert(self != NULL); + + char path[pathconf(MQUEUE_ROOT, _PC_PATH_MAX)]; + + sprintf(path, "%s/%d->%s", MQUEUE_ROOT, tid, self->service); + + self->out = open(path, O_WRONLY | O_CREAT, S_IWUSR); + if (self->out == (mqd_t) - 1) { + ERRNO(errno); + return -1; + } + + sprintf(path, "%s/%d<-%s", MQUEUE_ROOT, tid, self->service); + + self->in = open(path, O_RDONLY | O_CREAT, S_IRUSR); + if (self->in == (mqd_t) - 1) { + ERRNO(errno); + return -1; + } + + return 0; +} + +int mqueue_open(mqueue_t * self, char *path) +{ + assert(self != NULL); + + if (path != NULL) { + char *endp = NULL; + (void)strtol(path + 1, &endp, 10); + + if (strncmp(endp, "->", 2) == 0) { + self->in = mq_open((char *)path, O_RDONLY, + S_IRWXU, NULL); + if (self->in == (mqd_t) - 1) { + ERRNO(errno); + return -1; + } + } else if (strncmp(endp, "<-", 2) == 0) { + self->out = mq_open((char *)path, O_WRONLY, + S_IRWXU, NULL); + if (self->out == (mqd_t) - 1) { + ERRNO(errno); + return -1; + } + } else { + UNEXPECTED("'%s' invalid service", path); + return -1; + } + } + + return 0; +} + +int mqueue_close(mqueue_t * self, char *path) +{ + assert(self != NULL); + + if (path != NULL) { + char *endp = NULL; + (void)strtol(path + 1, &endp, 10); + + if (strncmp(endp, "->", 2) == 0) { + if (self->in != (mqd_t) - 1) + mq_close(self->in), self->in = (mqd_t) - 1; + } else if (strncmp(endp, "<-", 2) == 0) { + if (self->out != (mqd_t) - 1) + mq_close(self->out), self->out = (mqd_t) - 1; + } else { + UNEXPECTED("'%s' invalid service", path); + return -1; + } + } + + return 0; +} + +mqueue_attr_t mqueue_getattr(mqueue_t * self) +{ + assert(self != NULL); + + mqueue_attr_t attr; + mq_getattr(self->in, &attr); + + return attr; +} + +int mqueue_delete(mqueue_t * self) +{ + assert(self != NULL); + + char path[pathconf(MQUEUE_ROOT, _PC_PATH_MAX)]; + if (self->in != (mqd_t) - 1) { + sprintf(path, "%s/%d->%s", + MQUEUE_ROOT, gettid(), self->service); + unlink(path); + if (mq_close(self->in) == (mqd_t) - 1) { + ERRNO(errno); + return -1; + } + self->in = (mqd_t) - 1; + } + + if (self->out != (mqd_t) - 1) { + sprintf(path, "%s/%d<-%s", + MQUEUE_ROOT, gettid(), self->service); + unlink(path); + if (mq_close(self->in) == (mqd_t) - 1) { + ERRNO(errno); + return -1; + } + self->out = (mqd_t) - 1; + } + + if (self->service) { + free((void *)self->service); + self->service = NULL; + } + + return 0; +} + +int mqueue_send(mqueue_t * self, void *ptr, size_t len) +{ + assert(self != NULL); + + int rc = mq_send(self->out, (char *)ptr, len, 0); + if (rc == -1) { + ERRNO(errno); + return -1; + } + + return rc; +} + +int mqueue_receive(mqueue_t * self, void *ptr, size_t len) +{ + assert(self != NULL); + + int rc = mq_receive(self->in, (char *)ptr, len, 0); + if (rc == -1) { + ERRNO(errno); + return -1; + } + + return rc; +} + +/* ======================================================================= */ diff --git a/clib/src/signal.c b/clib/src/signal.c new file mode 100644 index 0000000..ed75c05 --- /dev/null +++ b/clib/src/signal.c @@ -0,0 +1,135 @@ +/* + * Copyright (c) International Business Machines Corp., 2014 + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program 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 General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + */ + +/* + * File: signal.c + * Author: Shaun Wetzstein <shaun@us.ibm.com> + * Descr: + * Note: + * Date: 10/03/10 + */ + +#include <unistd.h> +#include <stdarg.h> +#include <stdlib.h> +#include <malloc.h> +#include <stdint.h> +#include <signal.h> +#include <stdio.h> +#include <string.h> +#include <errno.h> +#include <limits.h> + +#include "misc.h" +#include "signal.h" + +/* ======================================================================= */ + +const char *__signal_msg[] = { + "signal: unexpected NULL self pointer", + "signal: unexpected NULL callback structure", +}; + +#define SIGNAL_NULL (__signal_msg[0]) + +/* ======================================================================= */ + +void signal_init(signal_t * self) +{ + if (unlikely(self == NULL)) + throw_unexpected(SIGNAL_NULL); + + if (self->fd != -1) + close(self->fd), self->fd = -1; + + sigemptyset(&self->mask); + self->flags = SFD_CLOEXEC; + + self->fd = signalfd(self->fd, &self->mask, self->flags); + if (unlikely(self->fd == -1)) + throw_errno(errno); +} + +void signal_delete(signal_t * self) +{ + if (unlikely(self == NULL)) + throw_unexpected(SIGNAL_NULL); + + close(self->fd), self->fd = -1; + + if (sigprocmask(SIG_UNBLOCK, &self->mask, NULL) == -1) + throw_errno(errno); + + sigemptyset(&self->mask); + self->flags = 0; +} + +int signal_fileno(signal_t * self) +{ + if (unlikely(self == NULL)) + throw_unexpected(SIGNAL_NULL); + return self->fd; +} + +int signal_setmask(signal_t * self, const sigset_t mask) +{ + if (unlikely(self == NULL)) + throw_unexpected(SIGNAL_NULL); + + self->mask = mask; + + if (sigprocmask(SIG_BLOCK, &self->mask, NULL) == -1) + throw_errno(errno); + + self->fd = signalfd(self->fd, &self->mask, self->flags); + if (unlikely(self->fd == -1)) + throw_errno(errno); + + return self->fd; +} + +#if 0 +void signal_wait1(signal_t * self) +{ + signal_wait2(self, -1); +} + +void signal_wait2(signal_t * self, int timeout) +{ + if (unlikely(self == NULL)) + throw_unexpected(SIGNAL_NULL); + + struct epoll_event events[signal_EVENT_SIZE]; + + int rc = epoll_wait(self->fd, events, + signal_EVENT_SIZE, timeout); + + for (int n = 0; n < rc; n++) { + signal_callback *cb = (signal_callback *) events[n].data.ptr; + if (cb != NULL) + if (cb->func != NULL) + cb->func((signal_event[1]) { { + events[n].data.u64 >> 32, + events[n].events} + } + , cb->data); + } +} +#endif + +/* ======================================================================= */ diff --git a/clib/src/slab.c b/clib/src/slab.c new file mode 100644 index 0000000..f9146af --- /dev/null +++ b/clib/src/slab.c @@ -0,0 +1,388 @@ +/* + * Copyright (c) International Business Machines Corp., 2014 + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program 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 General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + */ + +/* + * File: slab.c + * Author: Shaun Wetzstein <shaun@us.ibm.com> + * Descr: Slab based allocator + * Note: + * Date: 06/05/10 + */ + +#include <unistd.h> +#include <stdlib.h> +#include <malloc.h> +#include <stdint.h> +#include <stdio.h> +#include <string.h> +#include <errno.h> +#include <limits.h> + +#include "libclib.h" +#include "tree_iter.h" + +#include "slab.h" + +/* ======================================================================= */ + +/*! @cond */ +#define SLAB_NODE_MAGIC "SLND" + +#define SLAB_NODE_MAGIC_CHECK(m) ({ \ + bool rc = (((m)[0] != SLAB_NODE_MAGIC[0]) || \ + ((m)[1] != SLAB_NODE_MAGIC[1]) || \ + ((m)[2] != SLAB_NODE_MAGIC[2]) || \ + ((m)[3] != SLAB_NODE_MAGIC[3])); \ + rc; \ +}) + +typedef struct slab_node slab_node_t; + +struct slab_node { + uint8_t magic[4]; + + size_t free; + tree_node_t node; + + uint32_t bitmap[]; +}; + +#define SLAB_ALLOC_COUNT(s) ((s)->hdr.data_size / (s)->hdr.alloc_size) + +#define SLAB_PAGE_MAX UINT16_MAX +#define SLAB_PAGE_DIVISOR 32 +/*! @endcond */ + +/* ======================================================================= */ + +static slab_node_t *__slab_grow(slab_t * self) +{ + assert(self != NULL); + assert(!MAGIC_CHECK(self->hdr.id, SLAB_MAGIC)); + + slab_node_t *node = NULL; + if (posix_memalign((void **)&node, self->hdr.align_size, + self->hdr.page_size) < 0) { + ERRNO(errno); + return NULL; + } + + memset(node, 0, self->hdr.page_size); + + node->magic[0] = SLAB_NODE_MAGIC[0]; + node->magic[1] = SLAB_NODE_MAGIC[1]; + node->magic[2] = SLAB_NODE_MAGIC[2]; + node->magic[3] = SLAB_NODE_MAGIC[3]; + + node->free = SLAB_ALLOC_COUNT(self); + + tree_node_init(&node->node, (const void *)int32_hash1((int32_t) node)); + splay_insert(&self->tree, &node->node); + + self->hdr.page_count++; + + return node; +} + +/* ======================================================================= */ + +int slab_init3(slab_t * self, const char *name, size_t alloc_size) +{ + size_t page_size = max(sysconf(_SC_PAGESIZE), + __round_pow2(alloc_size * SLAB_PAGE_DIVISOR)); + return slab_init5(self, name, alloc_size, page_size, page_size); +} + +int slab_init4(slab_t * self, const char *name, size_t alloc_size, + size_t page_size) +{ + size_t align_size = (size_t) sysconf(_SC_PAGESIZE); + return slab_init5(self, name, alloc_size, page_size, align_size); +} + +int slab_init5(slab_t * self, const char *name, size_t alloc_size, + size_t page_size, size_t align_size) +{ + assert(self != NULL); + + if (unlikely(MAGIC_CHECK(self->hdr.id, SLAB_MAGIC) == false)) + slab_delete(self); + + alloc_size = align(alloc_size, sizeof(void *)); + if (alloc_size < SLAB_ALLOC_MIN || SLAB_ALLOC_MAX < alloc_size) { + UNEXPECTED("alloc_size out of range [%d..%d]", + SLAB_ALLOC_MIN, SLAB_ALLOC_MAX); + return -1; + } + + page_size = __round_pow2(page_size); + if (page_size / alloc_size < SLAB_PAGE_DIVISOR) { + UNEXPECTED("page_size out of range [%d..%d]", + alloc_size * SLAB_PAGE_DIVISOR, SLAB_PAGE_MAX); + return -1; + } + + size_t __page_size = (size_t) sysconf(_SC_PAGESIZE); + + align_size = __round_pow2(align_size); + if (align_size % __page_size) { + UNEXPECTED("align_size must be 0x%x aligned", __page_size); + return -1; + } + + memset(self, 0, sizeof *self); + + self->hdr.id[IDENT_MAGIC_0] = SLAB_MAGIC[IDENT_MAGIC_0]; + self->hdr.id[IDENT_MAGIC_1] = SLAB_MAGIC[IDENT_MAGIC_1]; + self->hdr.id[IDENT_MAGIC_2] = SLAB_MAGIC[IDENT_MAGIC_2]; + self->hdr.id[IDENT_MAGIC_3] = SLAB_MAGIC[IDENT_MAGIC_3]; + + self->hdr.id[IDENT_MAJOR] = CLIB_MAJOR; + self->hdr.id[IDENT_MINOR] = CLIB_MINOR; + self->hdr.id[IDENT_PATCH] = CLIB_PATCH; + + if (__BYTE_ORDER == __LITTLE_ENDIAN) + self->hdr.id[IDENT_FLAGS] |= SLAB_FLAG_LSB; + if (__BYTE_ORDER == __BIG_ENDIAN) + self->hdr.id[IDENT_FLAGS] |= SLAB_FLAG_MSB; + + if (name != NULL && *name != '\0') + strncpy(self->hdr.name, name, sizeof(self->hdr.name)); + + self->hdr.page_size = page_size; + self->hdr.align_size = align_size; + self->hdr.alloc_size = alloc_size; + + self->hdr.bitmap_size = + align(page_size / alloc_size, CHAR_BIT * sizeof(uint32_t)); + self->hdr.bitmap_size /= CHAR_BIT; + + self->hdr.data_size = + self->hdr.page_size - sizeof(slab_node_t) - self->hdr.bitmap_size; + + tree_init(&self->tree, default_compare); + + return 0; +} + +int slab_delete(slab_t * self) +{ + if (unlikely(self == NULL)) + return 0; + + if (unlikely(MAGIC_CHECK(self->hdr.id, SLAB_MAGIC))) { + UNEXPECTED("'%s' invalid or corrupt slab object", + self->hdr.name); + return -1; + } + + tree_iter_t it; + tree_iter_init(&it, &self->tree, TI_FLAG_FWD); + + slab_node_t *node; + tree_for_each(&it, node, node) { + if (SLAB_NODE_MAGIC_CHECK(node->magic)) { + UNEXPECTED("'%s' invalid or corrupt slab_node object " + "=> '%.4s'", self->hdr.name, node->magic); + return -1; + } + + if (splay_remove(&self->tree, &node->node) < 0) + return -1; + memset(node, 0, sizeof(*node)); + + free(node); + } + + memset(self, 0, sizeof(*self)); + + return 0; +} + +void *slab_alloc(slab_t * self) +{ + assert(self != NULL); + assert(!MAGIC_CHECK(self->hdr.id, SLAB_MAGIC)); + + tree_iter_t it; + tree_iter_init(&it, &self->tree, TI_FLAG_FWD); + + slab_node_t *node; + tree_for_each(&it, node, node) + if (0 < node->free) + break; + + if (unlikely(tree_iter_elem(&it) == NULL)) + node = __slab_grow(self); + + assert(node != NULL); + assert(0 < node->free); + + void *ptr = NULL; + + uint32_t map_pos; + for (map_pos = 0; map_pos < self->hdr.bitmap_size; map_pos++) + if (node->bitmap[map_pos] != UINT32_MAX) + break; + + if (unlikely(node->bitmap[map_pos] == UINT32_MAX)) { + UNEXPECTED("'%s' cache is corrupted", self->hdr.name); + return NULL; + } + if (unlikely(self->hdr.bitmap_size <= map_pos)) { + UNEXPECTED("'%s' cache is corrupted", self->hdr.name); + return NULL; + } + + uint32_t bit = clzl(~node->bitmap[map_pos]); + uint32_t mask = 0x80000000 >> bit; + + if (unlikely((node->bitmap[map_pos] & mask) == mask)) { + UNEXPECTED("'%s' cache is corrupted", self->hdr.name); + return NULL; + } + + node->bitmap[map_pos] |= mask; + node->free--; + + ptr = (void *)node->bitmap + self->hdr.bitmap_size + + (map_pos * INT32_BIT + bit) * self->hdr.alloc_size; + + return ptr; +} + +int slab_free(slab_t * self, void *ptr) +{ + assert(self != NULL); + assert(!MAGIC_CHECK(self->hdr.id, SLAB_MAGIC)); + + if (unlikely(ptr == NULL)) + return 0; + + slab_node_t *node = (slab_node_t *) ((uintptr_t) ptr & + ~(self->hdr.page_size - 1)); + assert(node != NULL); + + if (unlikely(SLAB_NODE_MAGIC_CHECK(node->magic))) { + int32_t hash = int32_hash1((int32_t) node); + if (splay_find(&self->tree, (const void *)hash) == NULL) { + UNEXPECTED("'%s' invalid slab_node pointer, %p", + self->hdr.name, ptr); + return -1; + } + } + + void *data = (void *)node->bitmap + self->hdr.bitmap_size; + assert(data != NULL); + + if (unlikely(ptr < data)) { + UNEXPECTED("'%s' pointer out-of-range, %p", + self->hdr.name, ptr); + return -1; + } + + size_t slot = (ptr - data) / self->hdr.alloc_size; + uint32_t mask = 0x80000000 >> slot; + size_t map_pos = slot / INT32_BIT; + + if (unlikely((node->bitmap[map_pos] & mask) != mask)) { + UNEXPECTED("'%s' double free detected, %p", + self->hdr.name, ptr); + return -1; + } + + node->bitmap[map_pos] &= ~mask; + node->free++; + + if (SLAB_ALLOC_COUNT(self) - node->free <= 0) { + splay_remove(&self->tree, &node->node); + self->hdr.page_count = max(0UL, self->hdr.page_count - 1); + memset(node, 0, sizeof(*node)); + free(node); + } + + return 0; +} + +size_t slab_alloc_size(slab_t * self) +{ + assert(self != NULL); + return self->hdr.alloc_size; +} + +size_t slab_page_size(slab_t * self) +{ + assert(self != NULL); + return self->hdr.page_size; +} + +size_t slab_data_size(slab_t * self) +{ + assert(self != NULL); + return self->hdr.data_size; +} + +size_t slab_bitmap_size(slab_t * self) +{ + assert(self != NULL); + return self->hdr.bitmap_size; +} + +size_t slab_align_size(slab_t * self) +{ + assert(self != NULL); + return self->hdr.align_size; +} + +void slab_dump(slab_t * self, FILE * out) +{ + if (out == NULL) + out = stdout; + + if (self != NULL) { + if (unlikely(MAGIC_CHECK(self->hdr.id, SLAB_MAGIC))) { + UNEXPECTED("'%s' invalid or corrupt slab object", + self->hdr.name); + return; + } + + fprintf(out, "%s: page_size: %d bitmap_size: %d data_size: " + "%d alloc_size: %d -- page_count: %d\n", + self->hdr.name, self->hdr.page_size, + self->hdr.bitmap_size, self->hdr.data_size, + self->hdr.alloc_size, self->hdr.page_count); + + tree_iter_t it; + tree_iter_init(&it, &self->tree, TI_FLAG_FWD); + + slab_node_t *node; + tree_for_each(&it, node, node) { + fprintf(out, "magic[%.4s] node: %p bitmap: %p data: " + "%p -- alloc: %d free: %d\n", + node->magic, &node->node, node->bitmap, + (void *)node->bitmap + self->hdr.bitmap_size, + self->hdr.data_size / self->hdr.alloc_size - + node->free, node->free); + + dump_memory(out, (unsigned long)node, node, + self->hdr.page_size); + } + } +} + +/* ======================================================================= */ diff --git a/clib/src/table.c b/clib/src/table.c new file mode 100644 index 0000000..108763e --- /dev/null +++ b/clib/src/table.c @@ -0,0 +1,679 @@ +/* + * Copyright (c) International Business Machines Corp., 2014 + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program 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 General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + */ + +/* + * File: table.c + * Author: Shaun Wetzstein <shaun@us.ibm.com> + * Descr: + * Note: + * Date: 08/21/10 + */ + +#include <unistd.h> +#include <stdarg.h> +#include <stdlib.h> +#include <malloc.h> +#include <stdint.h> +#include <stdio.h> +#include <string.h> +#include <errno.h> +#include <limits.h> + +#include "libclib.h" +#include "table.h" +#include "vector_iter.h" + +#define TABLE_PAGE_SIZE 4096 +#define TABLE_PAGE_DIVISOR 32 + +/* ======================================================================= */ +int table_init(table_t * self, const char *name, size_t col_nr) +{ + assert(self != NULL); + assert(name != NULL); + + if (col_nr == 0) { + UNEXPECTED("'%d' invalid column number", col_nr); + return -1; + } + + self->hdr.id[IDENT_MAGIC_0] = TABLE_MAGIC[IDENT_MAGIC_0]; + self->hdr.id[IDENT_MAGIC_1] = TABLE_MAGIC[IDENT_MAGIC_1]; + self->hdr.id[IDENT_MAGIC_2] = TABLE_MAGIC[IDENT_MAGIC_2]; + self->hdr.id[IDENT_MAGIC_3] = TABLE_MAGIC[IDENT_MAGIC_3]; + + self->hdr.id[IDENT_MAJOR] = CLIB_MAJOR; + self->hdr.id[IDENT_MINOR] = CLIB_MINOR; + self->hdr.id[IDENT_PATCH] = CLIB_PATCH; + + if (__BYTE_ORDER == __LITTLE_ENDIAN) + self->hdr.id[IDENT_FLAGS] |= TABLE_FLAG_LSB; + if (__BYTE_ORDER == __BIG_ENDIAN) + self->hdr.id[IDENT_FLAGS] |= TABLE_FLAG_MSB; + + /* FIX ME -- handle this more elegantly */ + //assert((col_nr * sizeof(value_t)) < TABLE_PAGE_SIZE); + + self->hdr.col_nr = col_nr; + + if (name == NULL || *name == '\0') + memset(self->hdr.name, 0, sizeof(self->hdr.name)); + else + strncpy(self->hdr.name, name, sizeof(self->hdr.name)); + + char name_vector[strlen(self->hdr.name) + 5]; + + size_t row_size = self->hdr.col_nr * sizeof(value_t); + + sprintf(name_vector, "%s.table", self->hdr.name); + vector_init(&self->table, name_vector, row_size, + __round_pow2(row_size * TABLE_PAGE_DIVISOR)); + + sprintf(name_vector, "%s.string", self->hdr.name); + vector_init(&self->string, name_vector, 1, TABLE_PAGE_SIZE); + + sprintf(name_vector, "%s.blob", self->hdr.name); + vector_init(&self->blob, name_vector, 1, TABLE_PAGE_SIZE); + + return 0; +} + +int table_delete(table_t * self) +{ + if (unlikely(self == NULL)) + return 0; + + if (MAGIC_CHECK(self->hdr.id, TABLE_MAGIC)) { + UNEXPECTED("'%2.2x%2.2x%2.2x%2.2x' invalid table magic " + "'%2.2x%2.2x%2.2x%2.2x", + self->hdr.id[IDENT_MAGIC_0], + self->hdr.id[IDENT_MAGIC_1], + self->hdr.id[IDENT_MAGIC_2], + self->hdr.id[IDENT_MAGIC_3], + TABLE_MAGIC[IDENT_MAGIC_0], + TABLE_MAGIC[IDENT_MAGIC_2], + TABLE_MAGIC[IDENT_MAGIC_3], + TABLE_MAGIC[IDENT_MAGIC_3]); + return -1; + } + + if (0 < vector_size(&self->table)) { + vector_iter_t it; + if (vector_iter_init(&it, &self->table, VI_FLAG_FWD) < 0) + return -1; + + value_t *v; + vector_for_each(&it, v) + for (size_t c = 0; c < self->hdr.col_nr; c++) + value_clear(v + c); + } + + if (vector_delete(&self->table) < 0) + return -1; + if (vector_delete(&self->string) < 0) + return -1; + if (vector_delete(&self->blob) < 0) + return -1; + + return 0; +} + +value_t *table_get(table_t * self, size_t row, size_t col) +{ + assert(self != NULL); + assert(!MAGIC_CHECK(self->hdr.id, TABLE_MAGIC)); + + row++; /* hide the column names */ + + return (value_t *) vector_at(&self->table, + row * self->hdr.col_nr + col); +} + +value_t *table_row2(table_t * self, size_t row_nr) +{ + assert(self != NULL); + assert(!MAGIC_CHECK(self->hdr.id, TABLE_MAGIC)); + + row_nr++; /* hide the column names */ + + return (value_t *) vector_at(&self->table, row_nr * self->hdr.col_nr); +} + +int table_row3(table_t * self, size_t row_nr, value_t * row) +{ + assert(self != NULL); + assert(row != NULL); + assert(!MAGIC_CHECK(self->hdr.id, TABLE_MAGIC)); + + row_nr++; /* hide the column names */ + + if (vector_size(&self->table) <= row_nr + 1) { + if (vector_size(&self->table, row_nr + 1) < 0) + return -1; + } else { + value_t *old; + old = (value_t *) vector_at(&self->table, row_nr); + assert(old != NULL); + + for (size_t col_nr = 0; col_nr < self->hdr.col_nr; col_nr++) + value_clear(old + col_nr); + } + + if (vector_put(&self->table, row_nr, row) < 0) + return -1; + + for (size_t col_nr = 0; col_nr < self->hdr.col_nr; col_nr++) + if (value_type(row + col_nr) == VT_STR || + value_type(row + col_nr) == VT_BLOB) + value_type(row + col_nr, VT_UNKNOWN); + + return 0; +} + +value_t *table_column(table_t * self, value_t * row, size_t col) +{ + assert(self != NULL); + assert(row != NULL); + assert(!MAGIC_CHECK(self->hdr.id, TABLE_MAGIC)); + assert(col < self->hdr.col_nr); + + return (void *)row + (vector_elem_size(&self->table) * col); +} + +int table_put(table_t * self, size_t row, size_t col, value_t * val) +{ + assert(self != NULL); + assert(val != NULL); + assert(!MAGIC_CHECK(self->hdr.id, TABLE_MAGIC)); + + row++; /* hide the column names */ + + size_t size = (row + 1) * self->hdr.col_nr; + + if (vector_size(&self->table) <= size) + if (vector_size(&self->table, size) < 0) + return -1; + + /* free existing pointer data */ + value_t *old = (value_t *) vector_at(&self->table, + row * self->hdr.col_nr + col); + assert(old != NULL); + value_clear(old); + + vector_put(&self->table, row * self->hdr.col_nr + col, (void *)val, 1); + + if ((value_type(val) == VT_STR) || (value_type(val) == VT_BLOB)) + value_type(val, VT_UNKNOWN); + + return 0; +} + +const char *table_name2(table_t * self, size_t col_nr) +{ + assert(self != NULL); + assert(!MAGIC_CHECK(self->hdr.id, TABLE_MAGIC)); + assert(col_nr < self->hdr.col_nr); + + const char *rc = NULL; + + value_t *row = (value_t *) vector_at(&self->table, 0); + if (row != NULL) { + value_t *col = row + col_nr; + switch (value_type(col)) { + case VT_STR_OFF: + rc = vector_at(&self->string, col->u64); + break; + case VT_STR_INLINE: + rc = (const char *)col->data; + break; + case VT_STR_CONST: + case VT_STR: + rc = value_string(col); + break; + default: + rc = NULL; + } + } + + return rc; +} + +int _table_name3(table_t * self, size_t col_nr, const char *name) +{ + return _table_name4(self, col_nr, name, strlen(name)); +} + +int _table_name4(table_t * self, size_t col_nr, const char *name, size_t len) +{ + assert(self != NULL); + assert(!MAGIC_CHECK(self->hdr.id, TABLE_MAGIC)); + assert(col_nr < self->hdr.col_nr); + + if (vector_size(&self->table) <= 0) + if (vector_size(&self->table, 1) < 0) + return -1; + + value_t *row = (value_t *) vector_at(&self->table, 0); + if (row != NULL) + value_string(row + col_nr, name, len); + + return 0; +} + +size_t table_rows(table_t * self) +{ + assert(self != NULL); + assert(!MAGIC_CHECK(self->hdr.id, TABLE_MAGIC)); + return vector_size(&self->table) - 1; +} + +size_t table_columns(table_t * self) +{ + assert(self != NULL); + assert(!MAGIC_CHECK(self->hdr.id, TABLE_MAGIC)); + return self->hdr.col_nr; +} + +int table_serialize(table_t * self) +{ + assert(self != NULL); + assert(!MAGIC_CHECK(self->hdr.id, TABLE_MAGIC)); + + vector_iter_t it; + vector_iter_init(&it, &self->table, VI_FLAG_FWD); + + value_t *row; + vector_for_each(&it, row) { + for (size_t c = 0; c < self->hdr.col_nr; c++) { + value_t *col = row + c; + + value_type_t type = value_type(col); + size_t len = value_size(col); + + vector_t *vec = NULL; + if (type == VT_STR) + vec = &self->string, type = VT_STR_OFF, len++; + else if (type == VT_BLOB) + vec = &self->blob, type = VT_BLOB_OFF; + else + continue; + + uint64_t off = vector_size(vec); + + if (vector_size(vec, off + len) < 0) + return -1; + if (vector_put(vec, off, col->ptr, len) < 0) + return -1; + + free(col->ptr), col->ptr = NULL; + + col->u64 = off; + value_type(col, type); + } + } + + return 0; +} + +ssize_t table_save(table_t * self, FILE * out) +{ + assert(self != NULL); + assert(out != NULL); + assert(!MAGIC_CHECK(self->hdr.id, TABLE_MAGIC)); + + /* ============= */ + + int header_swap(table_header_t * hdr) { + assert(hdr != NULL); + + if (hdr->id[IDENT_FLAGS] & TABLE_FLAG_MSB) { + hdr->col_nr = htobe32(hdr->col_nr); + } else if (hdr->id[IDENT_FLAGS] & TABLE_FLAG_LSB) { + hdr->col_nr = htole32(hdr->col_nr); + } else { + UNEXPECTED("'%s' invalid or corrupt table object => " + "'%x'", hdr->name, hdr->id[IDENT_FLAGS]); + return -1; + } + + return 0; + } + + /* ============= */ + + ssize_t len = 0; + + table_header_t hdr = self->hdr; + if (header_swap(&hdr) < 0) + return -1; + + clearerr(out); + len = fwrite(&self->hdr, 1, sizeof(self->hdr), out); + if (len != sizeof(self->hdr)) { + if (ferror(out)) { + ERRNO(errno); + return -1; + } + } + + ssize_t rc = vector_save(&self->table, out); + if (rc < 0) + return -1; + len += rc; + + rc = vector_save(&self->string, out); + if (rc < 0) + return -1; + len += rc; + + rc = vector_save(&self->blob, out); + if (rc < 0) + return -1; + len += rc; + + return len; +} + +int table_deserialize(table_t * self) +{ + assert(self != NULL); + assert(!MAGIC_CHECK(self->hdr.id, TABLE_MAGIC)); + + vector_iter_t it; + vector_iter_init(&it, &self->table, VI_FLAG_FWD); + + value_t *row; + vector_for_each(&it, row) { + for (size_t c = 0; c < self->hdr.col_nr; c++) { + value_t *col = row + c; + + value_type_t type = value_type(col); + size_t len = value_size(col); + + switch (type) { + uint64_t off; + case VT_STR_OFF: + len++; + value_type(col, VT_STR); + case VT_BLOB_OFF: + off = col->u64; + col->ptr = malloc(len); + + if (col->ptr == NULL) { + ERRNO(errno); + return -1; + } + + if (vector_get(&self->string, off, col->ptr, + len) < 0) + return -1; + + if (value_type(col) == VT_BLOB_OFF) + value_type(col, VT_BLOB); + break; + case VT_STR: + case VT_BLOB: + case VT_STR_CONST: + UNEXPECTED("'%s' invalid or corrupt type %d", + self->hdr.name, type); + return -1; + default: + ; + } + } + } + + if (vector_delete(&self->string) < 0) + return -1; + if (vector_delete(&self->blob) < 0) + return -1; + + return 0; +} + +ssize_t table_load(table_t * self, FILE * in) +{ + assert(self != NULL); + + /* ============= */ + + int header_swap(table_header_t * hdr) { + assert(hdr != NULL); + if (hdr->id[IDENT_FLAGS] & TABLE_FLAG_MSB) { + hdr->col_nr = be32toh(hdr->col_nr); + } else if (hdr->id[IDENT_FLAGS] & TABLE_FLAG_LSB) { + hdr->col_nr = le32toh(hdr->col_nr); + } else { + UNEXPECTED("'%s' invalid or corrupt table object => " + "'%x'", hdr->name, hdr->id[IDENT_FLAGS]); + return -1; + } + + return 0; + } + + int table_swap(table_t * tbl) { + vector_iter_t it; + if (vector_iter_init(&it, &tbl->table, VI_FLAG_FWD) < 0) + return -1; + + value_t *row; + vector_for_each(&it, row) { + for (size_t c = 0; c < self->hdr.col_nr; c++) { + value_t *col = row + c; + + value_type_t type = value_type(row); + +#define iBE(s) value_i##s(col, be##s##toh(value_i##s(col))) +#define uBE(s) value_u##s(col, be##s##toh(value_u##s(col))) +#define iLE(s) value_i##s(col, le##s##toh(value_i##s(col))) +#define uLE(s) value_u##s(col, le##s##toh(value_u##s(col))) + + if (tbl->hdr.id[IDENT_FLAGS] & TABLE_FLAG_MSB) { + switch (type) { + case VT_I16: + iBE(16); + break; + case VT_U16: + uBE(16); + break; + case VT_I32: + iBE(32); + break; + case VT_U32: + uBE(32); + break; + case VT_I64: + iBE(64); + break; + case VT_U64: + uBE(64); + break; + case VT_STR_OFF: + case VT_BLOB_OFF: + col->u64 = be64toh(col->u64); + break; + default: + ; + } + } else if (tbl->hdr.id[IDENT_FLAGS] & + TABLE_FLAG_LSB) { + switch (type) { + case VT_I16: + iLE(16); + break; + case VT_U16: + uLE(16); + break; + case VT_I32: + iLE(32); + break; + case VT_U32: + uLE(32); + break; + case VT_I64: + iLE(64); + break; + case VT_U64: + uLE(64); + break; + case VT_STR_OFF: + case VT_BLOB_OFF: + col->u64 = le64toh(col->u64); + break; + default: + ; + } + } else { + UNEXPECTED("'%s' invalid or corrupt " + "table object => '%x'", + tbl->hdr.name, + tbl->hdr.id[IDENT_FLAGS]); + return -1; + } + } + } + + return 0; + } + + /* ============= */ + + // zero'd table will cause a magic check + (void)table_delete(self); + + clearerr(in); + size_t len = fread(&self->hdr, 1, sizeof(self->hdr), in); + if (len != sizeof(self->hdr)) { + if (feof(in)) { + UNEXPECTED("'%s' end-of-file encountered", + self->hdr.name); + return -1; + } + if (ferror(in)) { + ERRNO(errno); + return -1; + } + } + + assert(!MAGIC_CHECK(self->hdr.id, TABLE_MAGIC)); + + if (header_swap(&self->hdr) < 0) + return -1; + + ssize_t rc = vector_load(&self->table, in); + if (rc < 0) + return -1; + len += rc; + + if (table_swap(self) < 0) + return -1; + + rc = vector_load(&self->string, in); + if (rc < 0) + return -1; + len += rc; + + rc = vector_load(&self->blob, in); + if (rc < 0) + return -1; + len += rc; + + return len; +} + +void table_print(table_t * self, FILE * out) +{ + if (self != NULL) { + if (unlikely(MAGIC_CHECK(self->hdr.id, TABLE_MAGIC))) { + UNEXPECTED("'%s' invalid or corrupt table object", + self->hdr.name); + return; + } + + vector_iter_t it; + vector_iter_init(&it, &self->table, VI_FLAG_FWD); + + value_t *row; + vector_for_each(&it, row) + for (size_t c = 0; c < self->hdr.col_nr; c++) + value_dump(row + c, out); + + vector_dump(&self->string, out); + } +} + +void table_dump(table_t * self, FILE * out) +{ + if (self != NULL) { + if (unlikely(MAGIC_CHECK(self->hdr.id, TABLE_MAGIC))) { + UNEXPECTED("'%s' invalid or corrupt table object", + self->hdr.name); + return; + } + + fprintf(out, + "table: [ size: %d cols: %d rows: %d name: '%s']\n", + sizeof(value_t), table_columns(self), table_rows(self), + self->hdr.name); + + dump_memory(out, (unsigned long)&self->hdr, &self->hdr, + sizeof(self->hdr)); + + vector_dump(&self->table, out); + vector_dump(&self->string, out); + vector_dump(&self->blob, out); + } +} + +#if 0 +void table_sort(table_t * self, compare_f cmp) +{ + /* The exchange function swaps two rows within the table + * exchange(table_t * self, size_t i, size_t j) + */ + + /* The partition method receives a list or sublist, and places the first element + * in its correct position within the list. It also ensures that all elements to + * the left of this are smaller, and all to the right are larger. + * + * partition(a[], p, r) + * i = p + * j = r + 1 + * pivot = a[p] + * do { + * do i = i + 1 while (a[i]<pivot) + * do j = j - 1 while (a[j]>pivot) + * if (i < j) exchange(a[i], a[j]) + * } while (i<j) + * exchange(a[p], a[j]) + * return j + */ + + /* + * quicksort(a[], p, r) + * if r > p then + * j = partition(a[], p, r) + * quicksort(a[], p, j-1) + * quicksort(a[], j+1, r) + * + */ +} +#endif + +/* ======================================================================= */ diff --git a/clib/src/table_iter.c b/clib/src/table_iter.c new file mode 100644 index 0000000..cb73573 --- /dev/null +++ b/clib/src/table_iter.c @@ -0,0 +1,138 @@ +/* + * Copyright (c) International Business Machines Corp., 2014 + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program 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 General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + */ + +/* + * File: table_iter.c + * Author: Shaun Wetzstein <shaun@us.ibm.com> + * Descr: + * Note: + * Date: 10/22/10 + */ + +#include <unistd.h> +#include <stdarg.h> +#include <stdlib.h> +#include <malloc.h> +#include <stdint.h> +#include <stdio.h> +#include <string.h> +#include <errno.h> +#include <limits.h> + +#include "assert.h" +#include "misc.h" + +#include "table_iter.h" + +/* ======================================================================= */ + +int table_iter_init(table_iter_t * self, table_t * table, uint32_t flags) +{ + assert(self != NULL); + assert(table != NULL); + + self->flags = flags; + self->table = table; + + if (self->flags & TI_FLAG_BWD) { + if (vector_iter_init(&self->it, &table->table, VI_FLAG_BWD) < 0) + return -1; + } else { + if (vector_iter_init(&self->it, &table->table, VI_FLAG_FWD) < 0) + return -1; + } + + return vector_iter_inc(&self->it) != NULL; +} + +int table_iter_clear(table_iter_t * self) +{ + assert(self != NULL); + + if (vector_iter_clear(&self->it) < 0) + return -1; + + self->table = NULL; + + return 0; +} + +const value_t *table_iter_elem(table_iter_t * self) +{ + assert(self != NULL); + return (value_t *) vector_iter_elem(&self->it); +} + +const value_t *table_iter_inc1(table_iter_t * self) +{ + return table_iter_inc2(self, 1); +} + +const value_t *table_iter_inc2(table_iter_t * self, size_t count) +{ + assert(self != NULL); + + const value_t *v = NULL; + + for (size_t i = 0; i < count; i++) { + if (self->flags & TI_FLAG_BWD) { + v = (value_t *) vector_iter_dec(&self->it); // columns + } else { + v = (value_t *) vector_iter_inc(&self->it); // columns + } + } + + return v; +} + +const value_t *table_iter_dec1(table_iter_t * self) +{ + return table_iter_dec2(self, 1); +} + +const value_t *table_iter_dec2(table_iter_t * self, size_t count) +{ + assert(self != NULL); + + const value_t *v = NULL; + + for (size_t i = 0; i < count; i++) { + if (self->flags & TI_FLAG_BWD) { + v = (value_t *) vector_iter_inc(&self->it); // columns + } else { + v = (value_t *) vector_iter_dec(&self->it); // columns + } + } + + return v; +} + +size_t table_iter_pos1(table_iter_t * self) +{ + assert(self != NULL); + return vector_iter_pos(&self->it) + 1; +} + +int table_iter_pos2(table_iter_t * self, size_t pos) +{ + assert(self != NULL); + assert(pos < table_rows(self->table)); + return vector_iter_pos(&self->it, pos + 1); +} + +/* ======================================================================= */ diff --git a/clib/src/timer.c b/clib/src/timer.c new file mode 100644 index 0000000..cb4d260 --- /dev/null +++ b/clib/src/timer.c @@ -0,0 +1,133 @@ +/* + * Copyright (c) International Business Machines Corp., 2014 + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program 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 General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + */ + +/* + * File: timer.c + * Author: Shaun Wetzstein <shaun@us.ibm.com> + * Descr: + * Note: + * Date: 10/03/10 + */ + +#include <unistd.h> +#include <stdarg.h> +#include <stdlib.h> +#include <malloc.h> +#include <stdint.h> +#include <stdio.h> +#include <string.h> +#include <errno.h> +#include <limits.h> + +#include "misc.h" +#include "timer.h" + +#define TIMER_PAGE_SIZE 64 +#define TIMER_EVENT_SIZE 64 + +/* ======================================================================= */ + +const char *__timer_msg[] = { + "timer: unexpected NULL self pointer", + "timer: unexpected NULL callback structure", +}; + +#define TIMER_NULL (__timer_msg[0]) +#define TIMER_CALLBACK_NULL (__timer_msg[1]) + +/* ======================================================================= */ + +void timer_init(timer * self, int clock) +{ + if (unlikely(self == NULL)) + throw_unexpected(TIMER_NULL); + + if (self->fd != -1) + close(self->fd), self->fd = -1; + + self->fd = timerfd_create(clock, TFD_CLOEXEC); + if (unlikely(self->fd == -1)) + throw_errno(errno); + + vector_init(&self->callbacks, "callbacks", + sizeof(timer_callback), TIMER_PAGE_SIZE); +} + +void timer_delete(timer * self) +{ + if (unlikely(self == NULL)) + throw_unexpected(TIMER_NULL); + close(self->fd), self->fd = -1; +} + +int timer_fileno(timer * self) +{ + if (unlikely(self == NULL)) + throw_unexpected(TIMER_NULL); + return self->fd; +} + +uint32_t timer_add(timer * self, timer_callback * cb) +{ + if (unlikely(self == NULL)) + throw_unexpected(TIMER_NULL); + + if (access(path, F_OK) != 0) + throw_errno(errno); + + uint32_t wd = inotify_add_timer(self->fd, path, events); + if (unlikely((int)wd == -1)) + throw_errno(errno); + + if (cb != NULL) + vcetor_put(&self->callbacks, wd, cb); + + return wd; +} + +void timer_remove(timer * self, uint32_t wd) +{ + if (unlikely(self == NULL)) + throw_unexpected(TIMER_NULL); + + int rc = inotify_rm_timer(self->fd, wd); + if (unlikely(rc == -1)) + throw_errno(errno); + + array_status(&self->callbacks, wd, false); +} + +void timer_wait(timer * self) +{ + if (unlikely(self == NULL)) + throw_unexpected(TIMER_NULL); + + /* FIX ME */ + + timer_event events[timer_EVENT_SIZE]; + + int n = read(self->fd, events, sizeof events); + printf("n[%d]\n", n); + + for (int i = 0; i < (n / sizeof *events); i++) + printf("%d: wd[%d] mask[%x] cookie[%x] name[%.*s]\n", + i, events[i].wd, events[i].mask, events[i].cookie, + events[i].len, events[i].name); +} + +/* ======================================================================= */ diff --git a/clib/src/trace_indent.c b/clib/src/trace_indent.c new file mode 100644 index 0000000..c1dd280 --- /dev/null +++ b/clib/src/trace_indent.c @@ -0,0 +1,185 @@ +/* + * Copyright (c) International Business Machines Corp., 2011 + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program 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 General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. + * + * Author: B. Rafanello + * + * Module: trace_indent.c + * + * Implements indentation for the trace output from bb_trace + * + * Version 0.0.0.1 + */ + +#include "trace_indent.h" +#include "stdio.h" + +/*-------------------------------------------------- + * Private Constants + --------------------------------------------------*/ + +#define DEFAULT_INDENT_SIZE 5 +#define MAX_INDENT_SIZE 129 +#define DEFAULT_INDENT " " + +/*-------------------------------------------------- + * Global variables. + --------------------------------------------------*/ + +/* The current trace level. */ +unsigned char BB_TRACE_LEVEL = 0; +unsigned char BB_PREVIOUS_TRACE_LEVEL = 0; + +/*-------------------------------------------------- + * Private global variables. + --------------------------------------------------*/ + +static unsigned int Current_Indent_Level = 0; +static unsigned int Current_Indent_Size = DEFAULT_INDENT_SIZE; +static char Indent[MAX_INDENT_SIZE] = DEFAULT_INDENT; + +/*-------------------------------------------------- + * Public Functions + --------------------------------------------------*/ + +/*********************************************************************/ +/* */ +/* Function Name: Set_Indent_Size */ +/* */ +/* Descriptive Name: Sets the number of spaces to use per indent. */ +/* If the current indent level is 5 and this */ +/* function is called to set the indent size to */ +/* 10, then 50 spaces will be printed by the */ +/* trace macros before each line of trace */ +/* output at this indent level. */ +/* */ +/* Input: unsigned int Spaces_Per_Indent - A value less than 128. */ +/* */ +/* Output: If Success : The specified value will be used for the */ +/* size of an indent. */ +/* */ +/* If Failure : This should only happen if the value */ +/* specified is >= 128, in which case it is */ +/* ignored and the previous value is retained.*/ +/* */ +/* Error Handling: Bad values for Spaces_Per_Indent are ignored. */ +/* */ +/* Side Effects: The number of spaces per indent may be changed. */ +/* */ +/* Notes: */ +/* */ +/*********************************************************************/ +void Set_Indent_Size(unsigned int Spaces_Per_Indent) +{ + unsigned int i; + + if (Spaces_Per_Indent <= MAX_INDENT_SIZE) { + Current_Indent_Size = Spaces_Per_Indent; + for (i = 0; i < Current_Indent_Size; i++) { + Indent[i] = ' '; + } + Indent[i] = 0x00; + } + + return; +} + +/*********************************************************************/ +/* */ +/* Function Name: Indent_Trace_Output */ +/* */ +/* Descriptive Name: This function increases the current indent */ +/* level by one. */ +/* */ +/* Input: None. */ +/* */ +/* Output: If Success : None */ +/* */ +/* If Failure : None */ +/* */ +/* Error Handling: None */ +/* */ +/* Side Effects: The current indent level for trace output will */ +/* be increased by 1. */ +/* */ +/* Notes: */ +/* */ +/*********************************************************************/ +void Indent_Trace_Output(void) +{ + Current_Indent_Level += 1; + return; +} + +/*********************************************************************/ +/* */ +/* Function Name: Outdent_Trace_Output */ +/* */ +/* Descriptive Name: This function reduces the current indent */ +/* level if it is greater than 0. */ +/* */ +/* Input: None */ +/* */ +/* Output: If Success : None */ +/* */ +/* If Failure : None */ +/* */ +/* Error Handling: If the current indent level is zero, then this */ +/* function does nothing. */ +/* */ +/* Side Effects: The current indent level for trace output may be */ +/* decreased by 1. */ +/* */ +/* Notes: */ +/* */ +/*********************************************************************/ +void Outdent_Trace_Output(void) +{ + if (Current_Indent_Level > 0) + Current_Indent_Level -= 1; + return; +} + +/*********************************************************************/ +/* */ +/* Function Name: Do_Indent */ +/* */ +/* Descriptive Name: This function prints to stderr the number of */ +/* spaces corresponding to the current indent */ +/* level. */ +/* */ +/* Input: None */ +/* */ +/* Output: If Success : None */ +/* */ +/* If Failure : None */ +/* */ +/* Error Handling: None */ +/* */ +/* Side Effects: Some number of space may be output to stderr. */ +/* */ +/* Notes: */ +/* */ +/*********************************************************************/ +void Do_Indent(void) +{ + unsigned int i; + + for (i = 0; i < Current_Indent_Level; i++) { + fprintf(stderr, "%s", Indent); + } + +} diff --git a/clib/src/tree.c b/clib/src/tree.c new file mode 100644 index 0000000..820f288 --- /dev/null +++ b/clib/src/tree.c @@ -0,0 +1,630 @@ +/* + * Copyright (c) International Business Machines Corp., 2014 + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program 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 General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + */ + +/* + * File: tree.c + * Author: Shaun Wetzstein <shaun@us.ibm.com> + * Descr: + * Note: + * Date: 08/21/10 + */ + +#include <unistd.h> +#include <stdarg.h> +#include <stdlib.h> +#include <malloc.h> +#include <stdint.h> +#include <stdio.h> +#include <string.h> +#include <errno.h> +#include <limits.h> + +#include "libclib.h" +#include "tree.h" +#include "slab.h" + +/* ======================================================================= */ + +tree_node_t *tree_node_prev(tree_node_t * self) +{ + assert(self != NULL); + + if (tree_node_left(self) != NULL) { + self = tree_node_left(self); + + while (tree_node_right(self) != NULL) + self = tree_node_right(self); + } else { + tree_node_t *parent = tree_node_parent(self); + + while (parent != NULL && self == tree_node_left(parent)) + self = parent, parent = tree_node_parent(parent); + + self = parent; + } + + return self; +} + +tree_node_t *tree_node_next(tree_node_t * self) +{ + assert(self != NULL); + + if (tree_node_right(self) != NULL) { + self = tree_node_right(self); + + while (self != NULL && tree_node_left(self) != NULL) + self = tree_node_left(self); + } else { + tree_node_t *parent = tree_node_parent(self); + + while (parent != NULL && self == tree_node_right(parent)) + self = parent, parent = tree_node_parent(parent); + + self = parent; + } + + return self; +} + +/* ======================================================================= */ + +int tree_init(tree_t * self, compare_f compare) +{ + assert(self != NULL); + assert(compare != NULL); + + self->root = NULL; + self->min = self->max = NULL; + self->compare = compare; + self->size = 0; + + return 0; +} + +static inline void __tree_new_min(tree_t * self, tree_node_t * node) +{ + assert(self != NULL); + assert(node != NULL); + + if (self->min == NULL) + self->min = node; + else if (self->compare(node->key, self->min->key) < 0) + self->min = node; +} + +static inline void __tree_new_max(tree_t * self, tree_node_t * node) +{ + assert(self != NULL); + assert(node != NULL); + + if (self->max == NULL) + self->max = node; + else if (self->compare(node->key, self->max->key) > 0) + self->max = node; +} + +static inline void +__tree_new_root(tree_t * self, tree_node_t * node, tree_node_t * left, + tree_node_t * right) +{ + assert(self != NULL); + assert(node != NULL); + + node->left = left; + node->right = right; + node->parent = NULL; + + if (unlikely(right != NULL)) + right->parent = node; + if (unlikely(left != NULL)) + left->parent = node; + + self->root = node; +} + +int tree_insert(tree_t * self, tree_node_t * node) +{ + assert(self != NULL); + assert(node != NULL); + + __tree_new_min(self, node); + __tree_new_max(self, node); + + if (unlikely(self->root == NULL)) { + __tree_new_root(self, node, NULL, NULL); + self->size++; + } else { + tree_node_t *root = self->root; + + while (root != NULL) { + int rc = self->compare(node->key, root->key); + + if (rc < 0) { + if (root->left == NULL) { + node->parent = root; + root->left = node; + self->size++; + return 0; + } else { + root = root->left; + } + } else if (0 < rc) { + if (root->right == NULL) { + node->parent = root; + root->right = node; + self->size++; + return 0; + } else { + root = root->right; + } + } else { + UNEXPECTED("duplicate key detected during " + "insert"); + return -1; + } + } + } + + return 0; +} + +static inline tree_node_t *__tree_find_min(tree_node_t * node) +{ + tree_node_t *min = node; + + if (node != NULL && node->right != NULL) { + min = node->right; + + while (min != NULL && min->left != NULL) + min = min->left; + } + + return min; +} + +static inline tree_node_t *__tree_find_max(tree_node_t * node) +{ + tree_node_t *max = node; + + if (node != NULL && node->left != NULL) { + max = node->left; + + while (max != NULL && max->right != NULL) + max = max->right; + } + + return max; +} + +int tree_remove(tree_t * self, tree_node_t * node) +{ + assert(self != NULL); + assert(node != NULL); + + if (unlikely(self->root == NULL) || unlikely(node == NULL)) + return 0; + + /* =========================== */ + + inline tree_node_t *__tree_find_min(tree_node_t * node) { + tree_node_t *min = node; + + if (node != NULL && node->right != NULL) { + min = node->right; + + while (min != NULL && min->left != NULL) + min = min->left; + } + + return min; + } + + inline tree_node_t *__tree_find_max(tree_node_t * node) { + tree_node_t *max = node; + + if (node != NULL && node->left != NULL) { + max = node->left; + + while (max != NULL && max->right != NULL) + max = max->right; + } + + return max; + } + + inline void remove_single_child(tree_node_t * node, bool left) { + tree_node_t *new_root = node->left; + + if (left == false) + new_root = node->right; + + if (node->parent != NULL) { + new_root->parent = node->parent; + + if (node->parent->left == node) // handle zig-zag + node->parent->left = new_root; + else if (node->parent->right == node) + node->parent->right = new_root; + } + + if (node == self->root) { + self->root = new_root; + self->root->parent = NULL; + } + } + + /* =========================== */ + + if (node == self->min) + self->min = tree_node_next(node); + if (node == self->max) + self->max = tree_node_prev(node); + + if (tree_node_leaf(node)) { + if (node->parent != NULL) { + if (node->parent->left == node) // left or right child? + node->parent->left = NULL; + else if (node->parent->right == node) + node->parent->right = NULL; + } + } else if (tree_node_internal(node)) { // two children! + tree_node_t *root = __tree_find_min(node); + assert(root != NULL); // must have a right child + + if (node->right == root) { // new 'root' is largest child + root->left = node->left; + if (node->left != NULL) + root->left->parent = root; + } else { // new 'root' is smallest grandchild + root->parent->left = root->right; + if (root->right != NULL) + root->right->parent = root->parent; + + root->right = node->right; + root->left = node->left; + + node->right->parent = root; + node->left->parent = root; + } + + root->parent = node->parent; + + if (self->root == node) { // find new parent + self->root = root; + } else { + if (node->parent->left == node) + node->parent->left = root; + else if (node->parent->right == node) + node->parent->right = root; + } + } else if (node->left != NULL) { // single left child + remove_single_child(node, true); + } else if (node->right != NULL) { // single right child + remove_single_child(node, false); + } + + node->right = node->left = node->parent = NULL; + + if (0 < self->size) + self->size--; + + if (self->size <= 0) + self->root = self->min = self->max = NULL; + + return 0; +} + +tree_node_t *tree_find(tree_t * self, const void *key) +{ + assert(self != NULL); + assert(key != NULL); + + tree_node_t *root = self->root; + + while (root != NULL) { + int rc = self->compare(key, root->key); + + if (rc < 0) + root = root->left; + else if (0 < rc) + root = root->right; + else + break; + } + + return root; +} + +int tree_walk(tree_t * self, tree_walk_f walk_func) +{ + assert(self != NULL); + assert(walk_func != NULL); + + int __tree_walk(tree_node_t * root) { + int rc = 0; + + if (likely(root != NULL)) { + __tree_walk(root->left); + rc = walk_func(root); + __tree_walk(root->right); + } + + return rc; + } + + return __tree_walk(self->root); +} + +void tree_dump(tree_t * self, FILE * out) +{ + assert(self != NULL); + + int __tree_node_dump(tree_node_t * node) { + if (node != NULL) + return fprintf(out, "node[%p] left[%p] right[%p] " + "parent[%p] -- key[%d]\n", + node, node->left, node->right, + node->parent, (intptr_t) node->key); + else + return 0; + } + + if (out == NULL) + out = stdout; + + fprintf(out, "root[%p] min[%p] max[%p] compare[%p] size[%d]\n", + self->root, self->min, self->max, self->compare, self->size); + + tree_walk(self, __tree_node_dump); +} + +void tree_node_dump(tree_node_t * node, FILE * out) +{ + if (node == NULL) + return; + + void __tree_node_dump(tree_node_t * root, int level) { + if (likely(root != NULL)) { + if (0 < level) { + for (int i = 0; i < level; i++) + fprintf(out, " "); + } + + fprintf(out, "node:[%p] left[%p] right[%p] parent[%p] " + "key[%d]\n", root, root->left, root->right, + root->parent, (intptr_t) node->key); + + level++; + __tree_node_dump(root->left, level); + __tree_node_dump(root->right, level); + level--; + } + } + + if (out == NULL) + out = stdout; + + __tree_node_dump(node, 0); +} + +/* ======================================================================= */ + +static tree_node_t *splay(tree_node_t * node, const void *key, + compare_f compare) +{ + if (node == NULL) + return node; + + tree_node_t N = { NULL, NULL, NULL, NULL } + , *l = &N, *r = &N, *y; + + for (;;) { + int rc = compare(key, node->key); + if (rc < 0) { + if (node->left == NULL) + break; + + /* rotate right */ + rc = compare(key, node->left->key); + if (rc < 0) { + y = node->left; + node->left = y->right; + if (y->right != NULL) + y->right->parent = node; + y->right = node; + node->parent = y; + y->parent = node->parent; + node = y; + + if (node->left == NULL) + break; + } + + /* link right */ + r->left = node; + node->parent = r; + + r = node; + node = node->left; + } else if (0 < rc) { + if (node->right == NULL) + break; + + /* rotate left */ + rc = compare(key, node->right->key); + if (0 < rc) { + y = node->right; + node->right = y->left; + if (y->left != NULL) + y->left->parent = node; + y->left = node; + node->parent = y; + y->parent = node->parent; + node = y; + + if (node->right == NULL) + break; + } + + /* link left */ + l->right = node; + node->parent = l; + + l = node; + node = node->right; + } else { + break; + } + } + + /* assemble */ + l->right = node->left; + if (node->left != NULL) + node->left->parent = l; + r->left = node->right; + if (node->right != NULL) + node->right->parent = r; + + node->left = N.right; + if (N.right != NULL) + N.right->parent = node; + + node->right = N.left; + if (N.left != NULL) + N.left->parent = node; + + node->parent = NULL; + + return node; +} + +int splay_insert(tree_t * self, tree_node_t * node) +{ + assert(self != NULL); + assert(node != NULL); + + __tree_new_min(self, node); + __tree_new_max(self, node); + + if (unlikely(self->root == NULL)) { + node->left = node->right = node->parent = NULL; + self->root = node; + self->size = 1; + return 0; + } + + self->root = splay(self->root, node->key, self->compare); + + int rc = self->compare(node->key, self->root->key); + + if (rc < 0) { + node->left = self->root->left; + if (node->left != NULL) + node->left->parent = node; + node->right = self->root; + self->root->left = NULL; + self->root->parent = node; + } else if (0 < rc) { + node->right = self->root->right; + if (node->right != NULL) + node->right->parent = node; + node->left = self->root; + self->root->right = NULL; + self->root->parent = node; + } else { + UNEXPECTED("duplicate key detected during insert"); + return -1; + } + + self->size++; + self->root = node; + + return 0; +} + +int splay_remove(tree_t * self, tree_node_t * node) +{ + assert(self != NULL); + assert(node != NULL); + + if (unlikely(self->root == NULL) || unlikely(node == NULL)) + return 0; + + if (node == self->min) + self->min = tree_node_next(node); + if (node == self->max) + self->max = tree_node_prev(node); + + self->root = splay(self->root, node->key, self->compare); + + if (node->key == self->root->key) { /* found it */ + tree_node_t *x; +#if SAVE + if (self->root->left == NULL) { + x = self->root->right; + } else { + x = splay(self->root->left, node->key, self->compare); + x->right = self->root->right; + } +#else + if (self->root->left != NULL && self->root->right != NULL) { + if (parity(int32_hash1((int32_t) self->root))) { + x = splay(self->root->left, node->key, + self->compare); + x->right = self->root->right; + } else { + x = splay(self->root->right, node->key, + self->compare); + x->left = self->root->left; + } + } else if (self->root->left == NULL) { + x = self->root->right; + } else { + x = splay(self->root->left, node->key, self->compare); + x->right = self->root->right; + } +#endif + + self->root->left = self->root->right = NULL; + self->root->parent = NULL; + self->root = x; + + if (0 < self->size) + self->size--; + if (0 < self->size) + self->root->parent = NULL; + } + + return 0; +} + +tree_node_t *splay_find(tree_t * self, const void *key) +{ + assert(self != NULL); + assert(key != NULL); + + self->root = splay(self->root, key, self->compare); + + if (self->root != NULL && self->compare(key, self->root->key)) + return NULL; + + return self->root; +} + +/* ======================================================================= */ diff --git a/clib/src/tree_iter.c b/clib/src/tree_iter.c new file mode 100644 index 0000000..3474b71 --- /dev/null +++ b/clib/src/tree_iter.c @@ -0,0 +1,137 @@ +/* + * Copyright (c) International Business Machines Corp., 2014 + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program 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 General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + */ + +/* + * File: tree_iter.c + * Author: Shaun Wetzstein <shaun@us.ibm.com> + * Descr: + * Note: + * Date: 10/22/10 + */ + +#include <unistd.h> +#include <stdarg.h> +#include <stdlib.h> +#include <malloc.h> +#include <stdint.h> +#include <stdio.h> +#include <string.h> +#include <errno.h> +#include <limits.h> + +#include "libclib.h" +#include "vector.h" +#include "tree_iter.h" + +/* ======================================================================= */ + +int tree_iter_init(tree_iter_t * self, tree_t * tree, uint32_t flags) +{ + assert(self != NULL); + assert(tree != NULL); + + self->node = NULL; + self->safe = NULL; + + self->tree = tree; + self->flags = flags; + + return tree_iter_clear(self); +} + +int tree_iter_clear(tree_iter_t * self) +{ + assert(self != NULL); + + if (self->flags & TI_FLAG_FWD) { + self->node = tree_min(self->tree); + if (self->node != NULL) + self->safe = tree_node_next(self->node); + } else if (self->flags & TI_FLAG_BWD) { + self->node = tree_max(self->tree); + if (self->node != NULL) + self->safe = tree_node_prev(self->node); + } else { + UNEXPECTED("invalid tree_iter flags"); + return -1; + } + + return 0; +} + +tree_node_t *tree_iter_elem(tree_iter_t * self) +{ + assert(self != NULL); + return self->node; +} + +tree_node_t *tree_iter_inc1(tree_iter_t * self) +{ + return tree_iter_inc2(self, 1); +} + +tree_node_t *tree_iter_inc2(tree_iter_t * self, size_t count) +{ + assert(self != NULL); + + for (size_t i = 0; i < count && self->node != NULL; i++) { + if (self->flags & TI_FLAG_FWD) { + self->node = self->safe; + if (self->node != NULL) + self->safe = tree_node_next(self->node); + } else if (self->flags & TI_FLAG_BWD) { + self->node = self->safe; + if (self->node != NULL) + self->safe = tree_node_prev(self->node); + } else { + UNEXPECTED("invalid tree_iter flags"); + return NULL; + } + } + + return self->node; +} + +tree_node_t *tree_iter_dec1(tree_iter_t * self) +{ + return tree_iter_dec2(self, 1); +} + +tree_node_t *tree_iter_dec2(tree_iter_t * self, size_t count) +{ + assert(self != NULL); + + for (size_t i = 0; i < count && self->node != NULL; i++) { + if (self->flags & TI_FLAG_FWD) { + self->node = self->safe; + if (self->node != NULL) + self->safe = tree_node_prev(self->node); + } else if (self->flags & TI_FLAG_BWD) { + self->node = self->safe; + if (self->node != NULL) + self->safe = tree_node_next(self->node); + } else { + UNEXPECTED("invalid tree_iter flags"); + return NULL; + } + } + + return self->node; +} + +/* ======================================================================= */ diff --git a/clib/src/value.c b/clib/src/value.c new file mode 100644 index 0000000..ad90d81 --- /dev/null +++ b/clib/src/value.c @@ -0,0 +1,143 @@ +/* + * Copyright (c) International Business Machines Corp., 2014 + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program 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 General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + */ + +/* + * File: value.c + * Author: Shaun Wetzstein <shaun@us.ibm.com> + * Descr: + * Note: + * Date: 08/23/10 + */ + +#include <unistd.h> +#include <stdarg.h> +#include <stdlib.h> +#include <malloc.h> +#include <stdint.h> +#include <stdio.h> +#include <string.h> +#include <errno.h> +#include <limits.h> + +#include "libclib.h" +#include "value.h" + +/* ======================================================================= */ + +void value_dump(const value_t * self, FILE * out) +{ + assert(self != NULL); + + static const char *type_name[] = { + "<unknown>", + "int8_t", "int16_t", "int32_t", "int64_t", + "uint8_t", "uint16_t", "uint32_t", "uint64_t", + "float", "double", + "string", "string-inline", "string-offset", "string-const", + "blob", "blob-inline", "blob-offset", "blob-file", + }; + + switch (self->type) { + case VT_I8: + fprintf(out, "value: [ data: %d size: %d type: %s ] %p\n", + self->i8, self->size, type_name[self->type], self); + break; + case VT_I16: + fprintf(out, "value: [ data: %d size: %d type: %s ] %p\n", + self->i16, self->size, type_name[self->type], self); + break; + case VT_I32: + fprintf(out, "value: [ data: %d size: %d type: %s ] %p\n", + self->i32, self->size, type_name[self->type], self); + break; + case VT_I64: + fprintf(out, "value: [ data: %lld size: %d type: %s ] %p\n", + self->i64, self->size, type_name[self->type], self); + break; + case VT_U8: + fprintf(out, "value: [ data: %ud size: %d type: %s ] %p\n", + self->u8, self->size, type_name[self->type], self); + break; + case VT_U16: + fprintf(out, "value: [ data: %d size: %d type: %s ] %p\n", + self->u16, self->size, type_name[self->type], self); + break; + case VT_U32: + fprintf(out, "value: [ data: %d size: %d type: %s ] %p\n", + self->u32, self->size, type_name[self->type], self); + break; + case VT_U64: + fprintf(out, "value: [ data: %lld size: %d type: %s ] %p\n", + self->u64, self->size, type_name[self->type], self); + break; + case VT_REAL32: + fprintf(out, "value: [ data: %f size: %d type: %s ] %p\n", + self->r32, self->size, type_name[self->type], self); + break; + case VT_REAL64: + fprintf(out, "value: [ data: %g size: %d type: %s ] %p\n", + self->r64, self->size, type_name[self->type], self); + break; + case VT_STR: + fprintf(out, "value: [ data: '%s' size: %d type: %s ] %p\n", + (char *)self->ptr, self->size, type_name[self->type], + self); + break; + case VT_STR_INLINE: + fprintf(out, "value: [ data: '%s' size: %d type: %s ] %p\n", + (char *)self->data, self->size, type_name[self->type], + self); + break; + case VT_STR_OFF: + fprintf(out, "value: [ data: %llu size: %d type: %s ] %p\n", + self->u64, self->size, type_name[self->type], self); + break; + case VT_STR_CONST: + fprintf(out, "value: [ data: '%s' size: %d type: %s ] %p\n", + (const char *)self->ptr, self->size, + type_name[self->type], self); + break; + case VT_BLOB: + fprintf(out, "value: [ size: %d type: %s ] %p\n", + self->size, type_name[self->type], self); + dump_memory(out, (unsigned long)self->ptr, self->ptr, + self->size); + break; + case VT_BLOB_INLINE: + fprintf(out, "value: [ size: %d type: %s ] %p\n", + self->size, type_name[self->type], self); + dump_memory(out, (unsigned long)self->data, self->data, + self->size); + break; + case VT_BLOB_OFF: + fprintf(out, "value: [ data: %llu size: %d type: %s ] %p\n", + self->u64, self->size, type_name[self->type], self); + break; + case VT_BLOB_FILE: + fprintf(out, "value: [ data: '%s' size: %d type: %s ] %p\n", + (char *)self->data, self->size, type_name[self->type], + self); + break; + default: + // throw_unexpected(VALUE_TYPE); + fprintf(out, "value: [ size: %d type: %s ] %p\n", + self->size, type_name[self->type], self); + } +} + +/* ======================================================================= */ diff --git a/clib/src/vector.c b/clib/src/vector.c new file mode 100644 index 0000000..54f9981 --- /dev/null +++ b/clib/src/vector.c @@ -0,0 +1,662 @@ +/* + * Copyright (c) International Business Machines Corp., 2014 + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program 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 General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + */ + +/* + * File: vector.c + * Author: Shaun Wetzstein <shaun@us.ibm.com> + * Descr: dynamic vector + * Note: + * Date: 08/29/10 + */ + +#include <unistd.h> +#include <stdarg.h> +#include <stdlib.h> +#include <malloc.h> +#include <stdint.h> +#include <stdio.h> +#include <string.h> +#include <errno.h> +#include <limits.h> + +#include "libclib.h" + +#include "vector.h" +#include "tree.h" +#include "tree_iter.h" +#include "mq.h" + +/* ======================================================================= */ + +/*! @cond */ +#define VECTOR_NODE_MAGIC "VCND" + +#define VECTOR_NODE_MAGIC_CHECK(m) ({ \ + bool rc = (((m)[0] != VECTOR_NODE_MAGIC[0]) || \ + ((m)[1] != VECTOR_NODE_MAGIC[1]) || \ + ((m)[2] != VECTOR_NODE_MAGIC[2]) || \ + ((m)[3] != VECTOR_NODE_MAGIC[3])); \ + rc; \ + }) + +typedef struct vector_node vector_node_t; + +struct vector_node { + uint8_t magic[4]; + + uint32_t address; + tree_node_t node; + + uint8_t data[]; +}; + +#define VECTOR_PAGE_MAX UINT16_MAX +#define VECTOR_PAGE_DIVISOR 32 + +#define __index_to_page(i,s) \ +({ \ + typeof(i) _p = ((i) / (s)); \ + _p; \ +}) + +#define __index_to_page_hashed(i,s) \ +({ \ + typeof(i) _h = int32_hash1(__index_to_page((i),(s))); \ + _h; \ +}) +/*! @endcond */ + +/* ======================================================================= */ + +static vector_node_t *__vector_find_page(vector_t * self, size_t idx) +{ + const void *hash; + hash = (const void *)__index_to_page_hashed(idx, self->hdr.elem_num); + + tree_node_t *node = tree_find(&self->tree, hash); + if (unlikely(node == NULL)) { + UNEXPECTED("'%d' index out of range", idx); + return NULL; + } + + return container_of(node, vector_node_t, node); +} + +static int __vector_shrink(vector_t * self) +{ + assert(self != NULL); + + vector_node_t *node = __vector_find_page(self, + vector_capacity(self) - 1); + assert(node != NULL); + + int rc = splay_remove(&self->tree, &node->node); + + free(node); + self->hdr.page_count--; + + return rc; +} + +static vector_node_t *__vector_grow(vector_t * self) +{ + assert(self != NULL); + assert(!MAGIC_CHECK(self->hdr.id, VECTOR_MAGIC)); + + vector_node_t *node = NULL; + int rc = posix_memalign((void **)&node, sizeof(void *), + self->hdr.page_size); + if (rc != 0) { + ERRNO(errno); + return NULL; + } + + memset(node, 0, self->hdr.page_size); + + node->magic[0] = VECTOR_NODE_MAGIC[0]; + node->magic[1] = VECTOR_NODE_MAGIC[1]; + node->magic[2] = VECTOR_NODE_MAGIC[2]; + node->magic[3] = VECTOR_NODE_MAGIC[3]; + + node->address = (uint32_t) node; + + size_t hash = __index_to_page_hashed(vector_capacity(self), + self->hdr.elem_num); + + tree_node_init(&node->node, (const void *)hash); + if (splay_insert(&self->tree, &node->node) < 0) { + free(node); + return NULL; + } + self->hdr.page_count++; + + return node; +} + +static int __vector_compare(const int i1, const int i2) +{ + return i1 - i2; +} + +/* ======================================================================= */ + +int vector_init3(vector_t * self, const char *name, size_t elem_size) +{ + size_t page_size = max(sysconf(_SC_PAGESIZE), + __round_pow2(elem_size * VECTOR_PAGE_DIVISOR)); + return vector_init4(self, name, elem_size, page_size); +} + +int vector_init4(vector_t * self, const char *name, size_t elem_size, + size_t page_size) +{ + assert(self != NULL); + + if (unlikely(MAGIC_CHECK(self->hdr.id, VECTOR_MAGIC)) == false) + vector_delete(self); + + if (elem_size < VECTOR_ELEM_MIN || VECTOR_ELEM_MAX < elem_size) { + UNEXPECTED("'%d' elem_size out of range [%d..%d]", + elem_size, VECTOR_ELEM_MIN, VECTOR_ELEM_MAX); + return -1; + } + + page_size = __round_pow2(page_size); + if (page_size / elem_size < VECTOR_PAGE_DIVISOR) { + UNEXPECTED("'%d' page_size out of range [%d..%d]", + page_size, elem_size * VECTOR_PAGE_DIVISOR, + VECTOR_PAGE_MAX); + return -1; + } + + memset(self, 0, sizeof *self); + + self->hdr.id[IDENT_MAGIC_0] = VECTOR_MAGIC[IDENT_MAGIC_0]; + self->hdr.id[IDENT_MAGIC_1] = VECTOR_MAGIC[IDENT_MAGIC_1]; + self->hdr.id[IDENT_MAGIC_2] = VECTOR_MAGIC[IDENT_MAGIC_2]; + self->hdr.id[IDENT_MAGIC_3] = VECTOR_MAGIC[IDENT_MAGIC_3]; + + self->hdr.id[IDENT_MAJOR] = CLIB_MAJOR; + self->hdr.id[IDENT_MINOR] = CLIB_MINOR; + self->hdr.id[IDENT_PATCH] = CLIB_PATCH; + + if (__BYTE_ORDER == __LITTLE_ENDIAN) + self->hdr.id[IDENT_FLAGS] |= VECTOR_FLAG_LSB; + if (__BYTE_ORDER == __BIG_ENDIAN) + self->hdr.id[IDENT_FLAGS] |= VECTOR_FLAG_MSB; + + self->hdr.page_size = page_size; + self->hdr.elem_size = elem_size; + self->hdr.elem_num = (self->hdr.page_size - sizeof(vector_node_t)) / + self->hdr.elem_size; + + if (name != NULL && *name != '\0') + strncpy(self->hdr.name, name, sizeof(self->hdr.name)); + + tree_init(&self->tree, (compare_f) __vector_compare); + + return 0; +} + +int vector_delete(vector_t * self) +{ + if (unlikely(self == NULL)) + return 0; + + assert(!MAGIC_CHECK(self->hdr.id, VECTOR_MAGIC)); + + tree_iter_t it; + tree_iter_init(&it, &self->tree, TI_FLAG_FWD); + + vector_node_t *node; + tree_for_each(&it, node, node) { + if (VECTOR_NODE_MAGIC_CHECK(node->magic)) { + UNEXPECTED("'%s' invalid or corrupt vector_node" + "object => '%.4s'", self->hdr.name, + node->magic); + return -1; + } + + if (splay_remove(&self->tree, &node->node) < 0) + return -1; + + memset(node, 0, sizeof(*node)); + free(node); + } + + self->hdr.page_count = self->hdr.size = 0; + + return 0; +} + +const void *vector_at(vector_t * self, size_t idx) +{ + assert(self != NULL); + assert(!MAGIC_CHECK(self->hdr.id, VECTOR_MAGIC)); + assert(idx < self->hdr.size); + + vector_node_t *node = __vector_find_page(self, idx); + return node->data + (self->hdr.elem_size * (idx % self->hdr.elem_num)); +} + +int vector_get3(vector_t * self, size_t idx, void *ptr) +{ + return vector_get4(self, idx, ptr, 1); +} + +int vector_get4(vector_t * self, size_t idx, void *ptr, size_t count) +{ + assert(self != NULL); + assert(!MAGIC_CHECK(self->hdr.id, VECTOR_MAGIC)); + + while (0 < count) { + memcpy(ptr, vector_at(self, idx), self->hdr.elem_size); + + idx++; + count--; + + ptr += self->hdr.elem_size; + } + + return 0; +} + +static inline int __vector_put(vector_t * self, size_t idx, const void *ptr) +{ + assert(self != NULL); + assert(!MAGIC_CHECK(self->hdr.id, VECTOR_MAGIC)); + + vector_node_t *node = __vector_find_page(self, idx); + assert(node != NULL); + + if (VECTOR_NODE_MAGIC_CHECK(node->magic)) { + UNEXPECTED("'%s' invalid or corrupt vector_node object => " + "'%.4s'", self->hdr.name, node->magic); + return -1; + } + + memcpy(node->data + (self->hdr.elem_size * (idx % self->hdr.elem_num)), + ptr, self->hdr.elem_size); + + return 0; +} + +int vector_put3(vector_t * self, size_t idx, const void *ptr) +{ + return vector_put4(self, idx, ptr, 1); +} + +int vector_put4(vector_t * self, size_t idx, const void *ptr, size_t count) +{ + assert(self != NULL); + assert(!MAGIC_CHECK(self->hdr.id, VECTOR_MAGIC)); + assert(idx < self->hdr.size); + + while (0 < count) { + if (__vector_put(self, idx, ptr) < 0) + return -1; + + idx++; + count--; + + ptr += self->hdr.elem_size; + } + + return 0; +} + +size_t vector_size1(vector_t * self) +{ + assert(self != NULL); + return self->hdr.size; +} + +int vector_size2(vector_t * self, size_t size) +{ + assert(self != NULL); + assert(!MAGIC_CHECK(self->hdr.id, VECTOR_MAGIC)); + + size_t pages = __index_to_page(size, self->hdr.elem_num) + 1; + + if (vector_pages(self) < pages) { + while (vector_pages(self) < pages) + (void)__vector_grow(self); + } else if (pages < vector_pages(self)) { + if (size <= 0) + vector_delete(self); + else + while (pages < vector_pages(self)) + if (__vector_shrink(self) < 0) + return -1; + } + + return self->hdr.size = size; +} + +size_t vector_pages(vector_t * self) +{ + assert(self != NULL); + assert(!MAGIC_CHECK(self->hdr.id, VECTOR_MAGIC)); + return self->hdr.page_count; +} + +size_t vector_capacity(vector_t * self) +{ + assert(self != NULL); + assert(!MAGIC_CHECK(self->hdr.id, VECTOR_MAGIC)); + return self->hdr.page_count * self->hdr.elem_num; +} + +size_t vector_elem_size(vector_t * self) +{ + assert(self != NULL); + assert(!MAGIC_CHECK(self->hdr.id, VECTOR_MAGIC)); + return self->hdr.elem_size; +} + +ssize_t vector_save(vector_t * self, FILE * out) +{ + assert(self != NULL); + assert(out != NULL); + assert(!MAGIC_CHECK(self->hdr.id, VECTOR_MAGIC)); + + int header_swap(vector_header_t * hdr) { + assert(hdr != NULL); + + if (hdr->id[IDENT_FLAGS] & VECTOR_FLAG_MSB) { + hdr->page_size = htobe32(hdr->page_size); + hdr->elem_size = htobe16(hdr->elem_size); + hdr->elem_num = htobe16(hdr->elem_num); + hdr->size = htobe32(hdr->size); + hdr->page_count = htobe32(hdr->page_count); + } else if (hdr->id[IDENT_FLAGS] & VECTOR_FLAG_LSB) { + hdr->page_size = htole32(hdr->page_size); + hdr->elem_size = htole16(hdr->elem_size); + hdr->elem_num = htole16(hdr->elem_num); + hdr->size = htole32(hdr->size); + hdr->page_count = htole32(hdr->page_count); + } else { + UNEXPECTED("'%s' invalid or corrupt flash object => " + "'%x'", hdr->name, hdr->id[IDENT_FLAGS]); + return -1; + } + + return 0; + } + + ssize_t save(vector_t * self, FILE * out) { + tree_iter_t it; + tree_iter_init(&it, &self->tree, TI_FLAG_FWD); + + ssize_t len = 0; + + vector_node_t *node; + tree_for_each(&it, node, node) { + if (VECTOR_NODE_MAGIC_CHECK(node->magic)) { + UNEXPECTED("'%s' invalid or corrupt vector_node" + "object => '%.4s'", self->hdr.name, + node->magic); + return -1; + } + + size_t rc; + + vector_node_t copy = *node; + + copy.address = 0; + copy.node.left = copy.node.right = NULL; + copy.node.parent = NULL; + + rc = fwrite((char *)©, 1, sizeof(copy), out); + if (rc != sizeof(copy)) { + if (ferror(out)) { + ERRNO(errno); + return -1; + } + } + len += rc; + + rc = fwrite((char *)node->data, 1, + self->hdr.page_size - sizeof(*node), out); + if (rc != self->hdr.page_size - sizeof(*node)) { + if (ferror(out)) { + ERRNO(errno); + return -1; + } + } + len += rc; + } + + return len; + } + + ssize_t total = 0; + + vector_header_t hdr = self->hdr; + if (header_swap(&hdr) < 0) + return -1; + + clearerr(out); + total = fwrite(&hdr, 1, sizeof(hdr), out); + if (total != sizeof(hdr)) { + if (ferror(out)) { + ERRNO(errno); + return -1; + } + } + + total += save(self, out); + + return total; +} + +ssize_t vector_load(vector_t * self, FILE * in) +{ + assert(self != NULL); + assert(in != NULL); + assert(!MAGIC_CHECK(self->hdr.id, VECTOR_MAGIC)); + + int header_swap(vector_header_t * hdr) { + assert(hdr != NULL); + + if (hdr->id[IDENT_FLAGS] & VECTOR_FLAG_MSB) { + hdr->page_size = be32toh(hdr->page_size); + hdr->elem_size = be16toh(hdr->elem_size); + hdr->elem_num = be16toh(hdr->elem_num); + hdr->size = be32toh(hdr->size); + hdr->page_count = be32toh(hdr->page_count); + } else if (hdr->id[IDENT_FLAGS] & VECTOR_FLAG_LSB) { + hdr->page_size = le32toh(hdr->page_size); + hdr->elem_size = le16toh(hdr->elem_size); + hdr->elem_num = le16toh(hdr->elem_num); + hdr->size = le32toh(hdr->size); + hdr->page_count = le32toh(hdr->page_count); + } else { + UNEXPECTED("'%s' invalid or corrupt flash object => " + "'%x'", hdr->name, hdr->id[IDENT_FLAGS]); + return -1; + } + + return 0; + } + + vector_delete(self); + + clearerr(in); + ssize_t len = fread(&self->hdr, 1, sizeof(self->hdr), in); + if (len != sizeof(self->hdr)) { + if (feof(in)) { + UNEXPECTED("'%s' end-of-file encountered", + self->hdr.name); + return -1; + } + if (ferror(in)) { + ERRNO(errno); + return -1; + } + } + + if (header_swap(&self->hdr) < 0) + return -1; + + assert(!MAGIC_CHECK(self->hdr.id, VECTOR_MAGIC)); + + tree_init(&self->tree, (compare_f) __vector_compare); + vector_node_t *node = NULL; + + for (size_t i = 0; i < vector_pages(self); i++) { + size_t rc = posix_memalign((void **)&node, sizeof(void *), + self->hdr.page_size); + if (rc != 0) { + ERRNO(errno); + return -1; + } + memset(node, 0, self->hdr.page_size); + + rc = fread((void *)node, 1, self->hdr.page_size, in); + if (rc != self->hdr.page_size) { + if (feof(in)) { + UNEXPECTED("'%s' end-of-file encountered", + self->hdr.name); + return -1; + } + if (ferror(in)) { + ERRNO(errno); + return -1; + } + } + + len += rc; + + if (VECTOR_NODE_MAGIC_CHECK(node->magic)) { + UNEXPECTED("'%s' invalid or corrupt vector_node " + "object => '%.4s'", self->hdr.name, + node->magic); + return -1; + } + + node->address = (uint32_t) node; + tree_node_init(&node->node, node->node.key); + splay_insert(&self->tree, &node->node); + + node = NULL; + } + + return len; +} + +int vector_send(vector_t * self, mqueue_t * mq) +{ + assert(self != NULL); + assert(mq != NULL); + assert(!MAGIC_CHECK(self->hdr.id, VECTOR_MAGIC)); + + mqueue_send(mq, (char *)self, sizeof(*self)); + + tree_iter_t it; + tree_iter_init(&it, &self->tree, TI_FLAG_FWD); + + vector_node_t *node; + tree_for_each(&it, node, node) { + assert(!VECTOR_NODE_MAGIC_CHECK(node->magic)); + mqueue_send(mq, (char *)node, self->hdr.page_size); + } + + return 0; +} + +int vector_receive(vector_t * self, mqueue_t * mq) +{ + assert(self != NULL); + assert(mq != NULL); + assert(!MAGIC_CHECK(self->hdr.id, VECTOR_MAGIC)); + + vector_delete(self); + + mqueue_attr_t attr = mqueue_getattr(mq); + + vector_node_t *node = NULL; + size_t rc = posix_memalign((void **)&node, attr.mq_msgsize, + attr.mq_msgsize); + if (rc != 0) { + ERRNO(errno); + return -1; + } + + ssize_t len = mqueue_receive(mq, (void *)node, attr.mq_msgsize); + assert(0 < len); + + assert(!MAGIC_CHECK(self->hdr.id, VECTOR_MAGIC)); + + memcpy(self, (void *)node, sizeof(*self)); + tree_init(&self->tree, (compare_f) __vector_compare); + + for (size_t i = 0; i < vector_pages(self); i++) { + rc = posix_memalign((void **)&node, attr.mq_msgsize, + attr.mq_msgsize); + if (rc != 0) { + ERRNO(errno); + return -1; + } + + len = mqueue_receive(mq, (void *)node, attr.mq_msgsize); + assert(0 < len); + + assert(!VECTOR_NODE_MAGIC_CHECK(node->magic)); + + node->address = (uint32_t) node; + tree_node_init(&node->node, node->node.key); + splay_insert(&self->tree, &node->node); + + node = NULL; + } + + return 0; +} + +void vector_dump(vector_t * self, FILE * out) +{ + if (out == NULL) + out = stdout; + + if (self != NULL) { + assert(!unlikely(MAGIC_CHECK(self->hdr.id, VECTOR_MAGIC))); + + fprintf(out, "%s: page_size: %d elem_size: %d elem_num: %d -- " + "size: %d capacity: %d -- page_count: %d\n", + self->hdr.name, self->hdr.page_size, + self->hdr.elem_size, self->hdr.elem_num, + vector_size(self), vector_capacity(self), + self->hdr.page_count); + + tree_iter_t it; + tree_iter_init(&it, &self->tree, TI_FLAG_FWD); + + vector_node_t *node; + tree_for_each(&it, node, node) { + fprintf(out, "magic[%.4s] node: %p data: %p -- " + "address: %x\n", node->magic, &node->node, + node->data, node->address); + + dump_memory(out, (unsigned long)node, node, + self->hdr.page_size); + } + } +} + +/* ======================================================================= */ diff --git a/clib/src/vector_iter.c b/clib/src/vector_iter.c new file mode 100644 index 0000000..4c95fd8 --- /dev/null +++ b/clib/src/vector_iter.c @@ -0,0 +1,177 @@ +/* + * Copyright (c) International Business Machines Corp., 2014 + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program 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 General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + */ + +/* + * File: vector_iter.c + * Author: Shaun Wetzstein <shaun@us.ibm.com> + * Descr: dynamic array + * Note: + * Date: 10/22/10 + */ + +#include <unistd.h> +#include <stdarg.h> +#include <stdlib.h> +#include <malloc.h> +#include <stdint.h> +#include <stdio.h> +#include <string.h> +#include <errno.h> +#include <limits.h> + +#include "libclib.h" +#include "vector_iter.h" + +/* ======================================================================= */ + +static inline const void *__vector_iter_bwd(vector_iter_t * self) +{ + size_t low = 0; + const void *ret = NULL; + + if (low < self->idx) + self->idx--; + + if (low < self->idx) + ret = vector_at(self->vector, self->idx); + + return ret; +} + +static inline const void *__vector_iter_fwd(vector_iter_t * self) +{ + size_t high = vector_size(self->vector); + const void *ret = NULL; + + if (self->idx < high) + self->idx++; + + if (self->idx < high) + ret = vector_at(self->vector, self->idx); + + return ret; +} + +int vector_iter_init(vector_iter_t * self, vector_t * vector, uint32_t flags) +{ + assert(self != NULL); + assert(vector != NULL); + + self->flags = flags; + self->vector = vector; + + if (self->flags & VI_FLAG_BWD) { + self->idx = vector_size(self->vector); + __vector_iter_bwd(self); + } else { + self->idx = 0; + } + + return 0; +} + +int vector_iter_clear(vector_iter_t * self) +{ + assert(self != NULL); + + if (self->flags & VI_FLAG_BWD) + self->idx = vector_size(self->vector); + else + self->idx = 0; + + self->vector = NULL; + return 0; +} + +const void *vector_iter_elem(vector_iter_t * self) +{ + assert(self != NULL); + + if (vector_capacity(self->vector) <= self->idx) { + UNEXPECTED("'%d' index out-of-range", self->idx); + return NULL; + } + + if (vector_size(self->vector) <= self->idx) + return NULL; + + return vector_at(self->vector, self->idx); +} + +const void *vector_iter_inc1(vector_iter_t * self) +{ + return vector_iter_inc2(self, 1); +} + +const void *vector_iter_inc2(vector_iter_t * self, size_t count) +{ + assert(self != NULL); + + const void *ret = NULL; + + for (size_t i = 0; i < count; i++) { + if (self->flags & VI_FLAG_BWD) + ret = __vector_iter_bwd(self); + else + ret = __vector_iter_fwd(self); + } + + return ret; +} + +const void *vector_iter_dec1(vector_iter_t * self) +{ + return vector_iter_dec2(self, 1); +} + +const void *vector_iter_dec2(vector_iter_t * self, size_t count) +{ + assert(self != NULL); + + const void *ret = NULL; + + for (size_t i = 0; i < count; i++) { + if (self->flags & VI_FLAG_BWD) + ret = __vector_iter_fwd(self); + else + ret = __vector_iter_bwd(self); + } + + return ret; +} + +size_t vector_iter_pos1(vector_iter_t * self) +{ + assert(self != NULL); + return self->idx; +} + +int vector_iter_pos2(vector_iter_t * self, size_t pos) +{ + assert(self != NULL); + + if (vector_size(self->vector) <= pos) { + UNEXPECTED("'%d' index out-of-range", pos); + return -1; + } + + self->idx = pos; + return 0; +} + +/* ======================================================================= */ diff --git a/clib/src/watch.c b/clib/src/watch.c new file mode 100644 index 0000000..6b78533 --- /dev/null +++ b/clib/src/watch.c @@ -0,0 +1,135 @@ +/* + * Copyright (c) International Business Machines Corp., 2014 + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program 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 General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + */ + +/* + * File: watch.c + * Author: Shaun Wetzstein <shaun@us.ibm.com> + * Descr: + * Note: + * Date: 10/03/10 + */ + +#include <unistd.h> +#include <stdarg.h> +#include <stdlib.h> +#include <malloc.h> +#include <stdint.h> +#include <stdio.h> +#include <string.h> +#include <errno.h> +#include <limits.h> + +#include "misc.h" +#include "nargs.h" +#include "watch.h" + +#define WATCH_PAGE_SIZE 64 +#define WATCH_EVENT_SIZE 64 + +/* ======================================================================= */ + +const char *__watch_msg[] = { + "watch: unexpected NULL self pointer", + "watch: unexpected NULL callback structure", +}; + +#define WATCH_NULL (__watch_msg[0]) +#define WATCH_CALLBACK_NULL (__watch_msg[1]) + +/* ======================================================================= */ + +void watch_init(watch_t * self) +{ + if (unlikely(self == NULL)) + throw_unexpected(WATCH_NULL); + + if (self->fd != -1) + close(self->fd), self->fd = -1; + + self->fd = inotify_init1(IN_CLOEXEC); + if (unlikely(self->fd == -1)) + throw_errno(errno); + + array_init(&self->callbacks, sizeof(watch_callback_t), WATCH_PAGE_SIZE); +} + +void watch_delete(watch_t * self) +{ + if (unlikely(self == NULL)) + throw_unexpected(WATCH_NULL); + close(self->fd), self->fd = -1; + array_delete(&self->callbacks); +} + +int watch_fileno(watch_t * self) +{ + if (unlikely(self == NULL)) + throw_unexpected(WATCH_NULL); + return self->fd; +} + +uint32_t watch_add(watch_t * self, const char *path, uint32_t events, + watch_callback_t * cb) +{ + if (unlikely(self == NULL)) + throw_unexpected(WATCH_NULL); + + if (access(path, F_OK) != 0) + throw_errno(errno); + + uint32_t wd = inotify_add_watch(self->fd, path, events); + if (unlikely((int)wd == -1)) + throw_errno(errno); + + if (cb != NULL) + array_put(&self->callbacks, wd, cb, 1); + + return wd; +} + +void watch_remove(watch_t * self, uint32_t wd) +{ + if (unlikely(self == NULL)) + throw_unexpected(WATCH_NULL); + + int rc = inotify_rm_watch(self->fd, wd); + if (unlikely(rc == -1)) + throw_errno(errno); + + array_status(&self->callbacks, wd, false); +} + +void watch_wait(watch_t * self) +{ + if (unlikely(self == NULL)) + throw_unexpected(WATCH_NULL); + + /* FIX ME */ + + watch_event_t events[WATCH_EVENT_SIZE]; + + ssize_t n = read(self->fd, events, sizeof events); + printf("n[%d]\n", n); + + for (ssize_t i = 0; i < (ssize_t) (n / sizeof *events); i++) + printf("%d: wd[%d] mask[%x] cookie[%x] name[%.*s]\n", + i, events[i].wd, events[i].mask, events[i].cookie, + events[i].len, events[i].name); +} + +/* ======================================================================= */ |