diff options
Diffstat (limited to 'hicn-light/src/hicn/base')
-rw-r--r-- | hicn-light/src/hicn/base/CMakeLists.txt | 38 | ||||
-rw-r--r-- | hicn-light/src/hicn/base/bitmap.h | 55 | ||||
-rw-r--r-- | hicn-light/src/hicn/base/common.h | 62 | ||||
-rw-r--r-- | hicn-light/src/hicn/base/hash.h | 250 | ||||
-rw-r--r-- | hicn-light/src/hicn/base/khash.h | 627 | ||||
-rw-r--r-- | hicn-light/src/hicn/base/loop.c | 355 | ||||
-rw-r--r-- | hicn-light/src/hicn/base/loop.h | 104 | ||||
-rw-r--r-- | hicn-light/src/hicn/base/pool.c | 88 | ||||
-rw-r--r-- | hicn-light/src/hicn/base/pool.h | 104 | ||||
-rw-r--r-- | hicn-light/src/hicn/base/vector.c | 54 | ||||
-rw-r--r-- | hicn-light/src/hicn/base/vector.h | 70 |
11 files changed, 1807 insertions, 0 deletions
diff --git a/hicn-light/src/hicn/base/CMakeLists.txt b/hicn-light/src/hicn/base/CMakeLists.txt new file mode 100644 index 000000000..5b2677ed1 --- /dev/null +++ b/hicn-light/src/hicn/base/CMakeLists.txt @@ -0,0 +1,38 @@ +# Copyright (c) 2017-2019 Cisco and/or its affiliates. +# Licensed under the Apache License, Version 2.0 (the "License"); +# you may not use this file except in compliance with the License. +# You may obtain a copy of the License at: +# +# http://www.apache.org/licenses/LICENSE-2.0 +# +# Unless required by applicable law or agreed to in writing, software +# distributed under the License is distributed on an "AS IS" BASIS, +# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +# See the License for the specific language governing permissions and +# limitations under the License. + +cmake_minimum_required(VERSION 3.5 FATAL_ERROR) + +list(APPEND HEADER_FILES + ${CMAKE_CURRENT_SOURCE_DIR}/bitmap.h + ${CMAKE_CURRENT_SOURCE_DIR}/common.h + ${CMAKE_CURRENT_SOURCE_DIR}/khash.h + ${CMAKE_CURRENT_SOURCE_DIR}/loop.h + ${CMAKE_CURRENT_SOURCE_DIR}/pool.h + ${CMAKE_CURRENT_SOURCE_DIR}/vector.h +) + +list(APPEND SOURCE_FILES + ${CMAKE_CURRENT_SOURCE_DIR}/loop.c + ${CMAKE_CURRENT_SOURCE_DIR}/pool.c + ${CMAKE_CURRENT_SOURCE_DIR}/vector.c +) + +set(SOURCE_FILES ${SOURCE_FILES} PARENT_SCOPE) +set(HEADER_FILES ${HEADER_FILES} PARENT_SCOPE) + +set(TO_INSTALL_HEADER_FILES + ${TO_INSTALL_HEADER_FILES} + ${HEADER_FILES} + PARENT_SCOPE +) diff --git a/hicn-light/src/hicn/base/bitmap.h b/hicn-light/src/hicn/base/bitmap.h new file mode 100644 index 000000000..df94b8039 --- /dev/null +++ b/hicn-light/src/hicn/base/bitmap.h @@ -0,0 +1,55 @@ +/* + * Copyright (c) 2020 Cisco and/or its affiliates. + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at: + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +/** + * \file bitmap.h + * \brief Bitmap + * + * A bitmap is implemented as a wrapper over a vector made of bit elements + */ + +#ifndef UTIL_BITMAP_H +#define UTIL_BITMAP_H + +#include <string.h> +#include "common.h" + +#define BITMAP_WIDTH(bitmap) (sizeof((bitmap)[0]) * 8) + +#define bitmap_init(bitmap, size) \ + vector_init(bitmap, next_pow2(size / BITMAP_WIDTH(bitmap))) + +#define bitmap_ensure_pos(bitmap, pos) vector_ensure_pos(bitmap, pos / BITMAP_WIDTH(bitmap)) + +#define bitmap_get(bitmap, i) ((bitmap)[(i) / BITMAP_WIDTH(bitmap)] & (1 << ((i) % BITMAP_WIDTH(bitmap)))) + +#define bitmap_is_set(bitmap, i) (bitmap_get((bitmap), (i)) == 1) + +#define bitmap_is_unset(bitmap, i) (bitmap_get((bitmap), (i)) == 0) + +#define bitmap_set(bitmap, i) bitmap[(i) / BITMAP_WIDTH(bitmap)] |= 1 << ((i) % BITMAP_WIDTH(bitmap)) + +#define bitmap_unset(bitmap, i) bitmap[(i) / BITMAP_WIDTH(bitmap)] &= ~ (1 << ((i) % BITMAP_WIDTH(bitmap))) + +#define bitmap_set_to(bitmap, pos) \ +do { \ + size_t offset = (pos / BITMAP_WIDTH(bitmap) + 1); \ + memset(bitmap, 0xFF, pos * sizeof(bitmap[0])); \ + size_t set_bits = offset * BITMAP_WIDTH(bitmap); \ + for (unsigned i = pos; i < set_bits; i++) \ + bitmap_unset(bitmap, i); \ +} while(0); + +#endif /* UTIL_BITMAP_H */ diff --git a/hicn-light/src/hicn/base/common.h b/hicn-light/src/hicn/base/common.h new file mode 100644 index 000000000..996050308 --- /dev/null +++ b/hicn-light/src/hicn/base/common.h @@ -0,0 +1,62 @@ +/* + * Copyright (c) 2020 Cisco and/or its affiliates. + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at: + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +/** + * \file array.h + * \brief Fixed-size pool allocator + */ + +#ifndef UTIL_COMMON_H +#define UTIL_COMMON_H + +#define round_pow2(x, pow2) ((x + pow2 - 1) & ~(pow2 - 1)) + +#define _SIZEOF_ALIGNED(x, size) round_pow2(sizeof(x), size) +#define SIZEOF_ALIGNED(x) _SIZEOF_ALIGNED(x, sizeof(void*)) + +/* Definitions for builtins unavailable on MSVC */ +#if defined(_MSC_VER) && !defined(__clang__) +#include <intrin.h> + +uint32_t __inline __builtin_ctz(uint32_t value) { + uint32_t trailing_zero = 0; + if (_BitScanForward(&trailing_zero, value)) + return trailing_zero; + else + return 32; +} + +uint32_t __inline __builtin_clz(uint32_t value) { + uint32_t leading_zero = 0; + if (_BitScanReverse(&leading_zero, value)) + return 31 - leading_zero; + else + return 32; +} + +uint32_t __inline __builtin_clzll(uint64_t value) { + uint32_t leading_zero = 0; + if (_BitScanReverse64(&leading_zero, value)) + return 63 - leading_zero; + else + return 64; +} + +#define __builtin_clzl __builtin_clzll +#endif + +#define next_pow2(x) (x == 1 ? 1 : 1<<(64-__builtin_clzl(x-1))) + +#endif /* UTIL_COMMON_H */ diff --git a/hicn-light/src/hicn/base/hash.h b/hicn-light/src/hicn/base/hash.h new file mode 100644 index 000000000..0b6a659bd --- /dev/null +++ b/hicn-light/src/hicn/base/hash.h @@ -0,0 +1,250 @@ +/* + * Copyright (c) 2017-2019 Cisco and/or its affiliates. + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at: + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +/* + * \file hash.h + * \brief Simple non-cryptographic hash implementation. + * + * Two helpers are provided : + * hash(buf, len) : hash a buffer <buf> of length <len> + * hash_struct(buf) : hash a buffer corresponding to an allocated struct + * + * This file consists in excerpts from Jenkins hash (public domain). + * http://www.burtleburtle.net/bob/c/lookup3.c + */ +#ifndef UTIL_HASH_H +#define UTIL_HASH_H + +#if (defined(__BYTE_ORDER) && defined(__LITTLE_ENDIAN) && \ + __BYTE_ORDER == __LITTLE_ENDIAN) || \ + (defined(i386) || defined(__i386__) || defined(__i486__) || \ + defined(__i586__) || defined(__i686__) || defined(vax) || defined(MIPSEL)) +# define HASH_LITTLE_ENDIAN 1 +# define HASH_BIG_ENDIAN 0 +#elif (defined(__BYTE_ORDER) && defined(__BIG_ENDIAN) && \ + __BYTE_ORDER == __BIG_ENDIAN) || \ + (defined(sparc) || defined(POWERPC) || defined(mc68000) || defined(sel)) +# define HASH_LITTLE_ENDIAN 0 +# define HASH_BIG_ENDIAN 1 +#else +# define HASH_LITTLE_ENDIAN 0 +# define HASH_BIG_ENDIAN 0 +#endif + +#define hashsize(n) ((uint32_t)1<<(n)) +#define hashmask(n) (hashsize(n)-1) +#define rot(x,k) (((x)<<(k)) | ((x)>>(32-(k)))) + +#define mix(a,b,c) \ +{ \ + a -= c; a ^= rot(c, 4); c += b; \ + b -= a; b ^= rot(a, 6); a += c; \ + c -= b; c ^= rot(b, 8); b += a; \ + a -= c; a ^= rot(c,16); c += b; \ + b -= a; b ^= rot(a,19); a += c; \ + c -= b; c ^= rot(b, 4); b += a; \ +} + +#define final(a,b,c) \ +{ \ + c ^= b; c -= rot(b,14); \ + a ^= c; a -= rot(c,11); \ + b ^= a; b -= rot(a,25); \ + c ^= b; c -= rot(b,16); \ + a ^= c; a -= rot(c,4); \ + b ^= a; b -= rot(a,14); \ + c ^= b; c -= rot(b,24); \ +} + +static inline +uint32_t hashlittle( const void *key, size_t length, uint32_t initval) +{ + uint32_t a,b,c; /* internal state */ + union { const void *ptr; size_t i; } u; /* needed for Mac Powerbook G4 */ + + /* Set up the internal state */ + a = b = c = 0xdeadbeef + ((uint32_t)length) + initval; + + u.ptr = key; + if (HASH_LITTLE_ENDIAN && ((u.i & 0x3) == 0)) { + const uint32_t *k = (const uint32_t *)key; /* read 32-bit chunks */ + + /*------ all but last block: aligned reads and affect 32 bits of (a,b,c) */ + while (length > 12) + { + a += k[0]; + b += k[1]; + c += k[2]; + mix(a,b,c); + length -= 12; + k += 3; + } + + /*----------------------------- handle the last (probably partial) block */ + /* + * "k[2]&0xffffff" actually reads beyond the end of the string, but + * then masks off the part it's not allowed to read. Because the + * string is aligned, the masked-off tail is in the same word as the + * rest of the string. Every machine with memory protection I've seen + * does it on word boundaries, so is OK with this. But VALGRIND will + * still catch it and complain. The masking trick does make the hash + * noticably faster for short strings (like English words). + */ +#ifndef VALGRIND + + switch(length) + { + case 12: c+=k[2]; b+=k[1]; a+=k[0]; break; + case 11: c+=k[2]&0xffffff; b+=k[1]; a+=k[0]; break; + case 10: c+=k[2]&0xffff; b+=k[1]; a+=k[0]; break; + case 9 : c+=k[2]&0xff; b+=k[1]; a+=k[0]; break; + case 8 : b+=k[1]; a+=k[0]; break; + case 7 : b+=k[1]&0xffffff; a+=k[0]; break; + case 6 : b+=k[1]&0xffff; a+=k[0]; break; + case 5 : b+=k[1]&0xff; a+=k[0]; break; + case 4 : a+=k[0]; break; + case 3 : a+=k[0]&0xffffff; break; + case 2 : a+=k[0]&0xffff; break; + case 1 : a+=k[0]&0xff; break; + case 0 : return c; /* zero length strings require no mixing */ + } + +#else /* make valgrind happy */ + + k8 = (const uint8_t *)k; + switch(length) + { + case 12: c+=k[2]; b+=k[1]; a+=k[0]; break; + case 11: c+=((uint32_t)k8[10])<<16; /* fall through */ + case 10: c+=((uint32_t)k8[9])<<8; /* fall through */ + case 9 : c+=k8[8]; /* fall through */ + case 8 : b+=k[1]; a+=k[0]; break; + case 7 : b+=((uint32_t)k8[6])<<16; /* fall through */ + case 6 : b+=((uint32_t)k8[5])<<8; /* fall through */ + case 5 : b+=k8[4]; /* fall through */ + case 4 : a+=k[0]; break; + case 3 : a+=((uint32_t)k8[2])<<16; /* fall through */ + case 2 : a+=((uint32_t)k8[1])<<8; /* fall through */ + case 1 : a+=k8[0]; break; + case 0 : return c; + } + +#endif /* !valgrind */ + + } else if (HASH_LITTLE_ENDIAN && ((u.i & 0x1) == 0)) { + const uint16_t *k = (const uint16_t *)key; /* read 16-bit chunks */ + const uint8_t *k8; + + /*--------------- all but last block: aligned reads and different mixing */ + while (length > 12) + { + a += k[0] + (((uint32_t)k[1])<<16); + b += k[2] + (((uint32_t)k[3])<<16); + c += k[4] + (((uint32_t)k[5])<<16); + mix(a,b,c); + length -= 12; + k += 6; + } + + /*----------------------------- handle the last (probably partial) block */ + k8 = (const uint8_t *)k; + switch(length) + { + case 12: c+=k[4]+(((uint32_t)k[5])<<16); + b+=k[2]+(((uint32_t)k[3])<<16); + a+=k[0]+(((uint32_t)k[1])<<16); + break; + case 11: c+=((uint32_t)k8[10])<<16; /* fall through */ + case 10: c+=k[4]; + b+=k[2]+(((uint32_t)k[3])<<16); + a+=k[0]+(((uint32_t)k[1])<<16); + break; + case 9 : c+=k8[8]; /* fall through */ + case 8 : b+=k[2]+(((uint32_t)k[3])<<16); + a+=k[0]+(((uint32_t)k[1])<<16); + break; + case 7 : b+=((uint32_t)k8[6])<<16; /* fall through */ + case 6 : b+=k[2]; + a+=k[0]+(((uint32_t)k[1])<<16); + break; + case 5 : b+=k8[4]; /* fall through */ + case 4 : a+=k[0]+(((uint32_t)k[1])<<16); + break; + case 3 : a+=((uint32_t)k8[2])<<16; /* fall through */ + case 2 : a+=k[0]; + break; + case 1 : a+=k8[0]; + break; + case 0 : return c; /* zero length requires no mixing */ + } + + } else { /* need to read the key one byte at a time */ + const uint8_t *k = (const uint8_t *)key; + + /*--------------- all but the last block: affect some 32 bits of (a,b,c) */ + while (length > 12) + { + a += k[0]; + a += ((uint32_t)k[1])<<8; + a += ((uint32_t)k[2])<<16; + a += ((uint32_t)k[3])<<24; + b += k[4]; + b += ((uint32_t)k[5])<<8; + b += ((uint32_t)k[6])<<16; + b += ((uint32_t)k[7])<<24; + c += k[8]; + c += ((uint32_t)k[9])<<8; + c += ((uint32_t)k[10])<<16; + c += ((uint32_t)k[11])<<24; + mix(a,b,c); + length -= 12; + k += 12; + } + + /*-------------------------------- last block: affect all 32 bits of (c) */ + switch(length) /* all the case statements fall through */ + { + case 12: c+=((uint32_t)k[11])<<24; + case 11: c+=((uint32_t)k[10])<<16; + case 10: c+=((uint32_t)k[9])<<8; + case 9 : c+=k[8]; + case 8 : b+=((uint32_t)k[7])<<24; + case 7 : b+=((uint32_t)k[6])<<16; + case 6 : b+=((uint32_t)k[5])<<8; + case 5 : b+=k[4]; + case 4 : a+=((uint32_t)k[3])<<24; + case 3 : a+=((uint32_t)k[2])<<16; + case 2 : a+=((uint32_t)k[1])<<8; + case 1 : a+=k[0]; + break; + case 0 : return c; + } + } + + final(a,b,c); + return c; +} + +/* Helpers */ + +#define HASH_INITVAL 1 +//#define hash(buf, len) (hash_t)hashlittle(buf, len, HASH_INITVAL) +#define hash(buf, len) hashlittle(buf, len, HASH_INITVAL) +#define hash_struct(buf) hash(buf, sizeof(buf)) + +#define str_hash(str) (hash(str, strlen(str))) +#define str_hash_eq(a, b) (str_hash(b) - str_hash(a)) + +#endif /* UTIL_JENKINS_HASH_H */ diff --git a/hicn-light/src/hicn/base/khash.h b/hicn-light/src/hicn/base/khash.h new file mode 100644 index 000000000..f75f3474c --- /dev/null +++ b/hicn-light/src/hicn/base/khash.h @@ -0,0 +1,627 @@ +/* The MIT License + + Copyright (c) 2008, 2009, 2011 by Attractive Chaos <attractor@live.co.uk> + + Permission is hereby granted, free of charge, to any person obtaining + a copy of this software and associated documentation files (the + "Software"), to deal in the Software without restriction, including + without limitation the rights to use, copy, modify, merge, publish, + distribute, sublicense, and/or sell copies of the Software, and to + permit persons to whom the Software is furnished to do so, subject to + the following conditions: + + The above copyright notice and this permission notice shall be + included in all copies or substantial portions of the Software. + + THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, + EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF + MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND + NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS + BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN + ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN + CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE + SOFTWARE. +*/ + +/* + An example: + +#include "khash.h" +KHASH_MAP_INIT_INT(32, char) +int main() { + int ret, is_missing; + khiter_t k; + khash_t(32) *h = kh_init(32); + k = kh_put(32, h, 5, &ret); + kh_value(h, k) = 10; + k = kh_get(32, h, 10); + is_missing = (k == kh_end(h)); + k = kh_get(32, h, 5); + kh_del(32, h, k); + for (k = kh_begin(h); k != kh_end(h); ++k) + if (kh_exist(h, k)) kh_value(h, k) = 1; + kh_destroy(32, h); + return 0; +} +*/ + +/* + 2013-05-02 (0.2.8): + + * Use quadratic probing. When the capacity is power of 2, stepping function + i*(i+1)/2 guarantees to traverse each bucket. It is better than double + hashing on cache performance and is more robust than linear probing. + + In theory, double hashing should be more robust than quadratic probing. + However, my implementation is probably not for large hash tables, because + the second hash function is closely tied to the first hash function, + which reduce the effectiveness of double hashing. + + Reference: http://research.cs.vt.edu/AVresearch/hashing/quadratic.php + + 2011-12-29 (0.2.7): + + * Minor code clean up; no actual effect. + + 2011-09-16 (0.2.6): + + * The capacity is a power of 2. This seems to dramatically improve the + speed for simple keys. Thank Zilong Tan for the suggestion. Reference: + + - http://code.google.com/p/ulib/ + - http://nothings.org/computer/judy/ + + * Allow to optionally use linear probing which usually has better + performance for random input. Double hashing is still the default as it + is more robust to certain non-random input. + + * Added Wang's integer hash function (not used by default). This hash + function is more robust to certain non-random input. + + 2011-02-14 (0.2.5): + + * Allow to declare global functions. + + 2009-09-26 (0.2.4): + + * Improve portability + + 2008-09-19 (0.2.3): + + * Corrected the example + * Improved interfaces + + 2008-09-11 (0.2.2): + + * Improved speed a little in kh_put() + + 2008-09-10 (0.2.1): + + * Added kh_clear() + * Fixed a compiling error + + 2008-09-02 (0.2.0): + + * Changed to token concatenation which increases flexibility. + + 2008-08-31 (0.1.2): + + * Fixed a bug in kh_get(), which has not been tested previously. + + 2008-08-31 (0.1.1): + + * Added destructor +*/ + + +#ifndef __AC_KHASH_H +#define __AC_KHASH_H + +/*! + @header + + Generic hash table library. + */ + +#define AC_VERSION_KHASH_H "0.2.8" + +#include <stdlib.h> +#include <string.h> +#include <limits.h> + +/* compiler specific configuration */ + +#if UINT_MAX == 0xffffffffu +typedef unsigned int khint32_t; +#elif ULONG_MAX == 0xffffffffu +typedef unsigned long khint32_t; +#endif + +#if ULONG_MAX == ULLONG_MAX +typedef unsigned long khint64_t; +#else +typedef unsigned long long khint64_t; +#endif + +#ifndef kh_inline +#ifdef _MSC_VER +#define kh_inline __inline +#else +#define kh_inline inline +#endif +#endif /* kh_inline */ + +#ifndef klib_unused +#if (defined __clang__ && __clang_major__ >= 3) || (defined __GNUC__ && __GNUC__ >= 3) +#define klib_unused __attribute__ ((__unused__)) +#else +#define klib_unused +#endif +#endif /* klib_unused */ + +typedef khint32_t khint_t; +typedef khint_t khiter_t; + +#define __ac_isempty(flag, i) ((flag[i>>4]>>((i&0xfU)<<1))&2) +#define __ac_isdel(flag, i) ((flag[i>>4]>>((i&0xfU)<<1))&1) +#define __ac_iseither(flag, i) ((flag[i>>4]>>((i&0xfU)<<1))&3) +#define __ac_set_isdel_false(flag, i) (flag[i>>4]&=~(1ul<<((i&0xfU)<<1))) +#define __ac_set_isempty_false(flag, i) (flag[i>>4]&=~(2ul<<((i&0xfU)<<1))) +#define __ac_set_isboth_false(flag, i) (flag[i>>4]&=~(3ul<<((i&0xfU)<<1))) +#define __ac_set_isdel_true(flag, i) (flag[i>>4]|=1ul<<((i&0xfU)<<1)) + +#define __ac_fsize(m) ((m) < 16? 1 : (m)>>4) + +#ifndef kroundup32 +#define kroundup32(x) (--(x), (x)|=(x)>>1, (x)|=(x)>>2, (x)|=(x)>>4, (x)|=(x)>>8, (x)|=(x)>>16, ++(x)) +#endif + +#ifndef kcalloc +#define kcalloc(N,Z) calloc(N,Z) +#endif +#ifndef kmalloc +#define kmalloc(Z) malloc(Z) +#endif +#ifndef krealloc +#define krealloc(P,Z) realloc(P,Z) +#endif +#ifndef kfree +#define kfree(P) free(P) +#endif + +static const double __ac_HASH_UPPER = 0.77; + +#define __KHASH_TYPE(name, khkey_t, khval_t) \ + typedef struct kh_##name##_s { \ + khint_t n_buckets, size, n_occupied, upper_bound; \ + khint32_t *flags; \ + khkey_t *keys; \ + khval_t *vals; \ + } kh_##name##_t; + +#define __KHASH_PROTOTYPES(name, khkey_t, khval_t) \ + extern kh_##name##_t *kh_init_##name(void); \ + extern void kh_destroy_##name(kh_##name##_t *h); \ + extern void kh_clear_##name(kh_##name##_t *h); \ + extern khint_t kh_get_##name(const kh_##name##_t *h, khkey_t key); \ + extern int kh_resize_##name(kh_##name##_t *h, khint_t new_n_buckets); \ + extern khint_t kh_put_##name(kh_##name##_t *h, khkey_t key, int *ret); \ + extern void kh_del_##name(kh_##name##_t *h, khint_t x); + +#define __KHASH_IMPL(name, SCOPE, khkey_t, khval_t, kh_is_map, __hash_func, __hash_equal) \ + SCOPE kh_##name##_t *kh_init_##name(void) { \ + return (kh_##name##_t*)kcalloc(1, sizeof(kh_##name##_t)); \ + } \ + SCOPE void kh_destroy_##name(kh_##name##_t *h) \ + { \ + if (h) { \ + kfree((void *)h->keys); kfree(h->flags); \ + kfree((void *)h->vals); \ + kfree(h); \ + } \ + } \ + SCOPE void kh_clear_##name(kh_##name##_t *h) \ + { \ + if (h && h->flags) { \ + memset(h->flags, 0xaa, __ac_fsize(h->n_buckets) * sizeof(khint32_t)); \ + h->size = h->n_occupied = 0; \ + } \ + } \ + SCOPE khint_t kh_get_##name(const kh_##name##_t *h, khkey_t key) \ + { \ + if (h->n_buckets) { \ + khint_t k, i, last, mask, step = 0; \ + mask = h->n_buckets - 1; \ + k = __hash_func(key); i = k & mask; \ + last = i; \ + while (!__ac_isempty(h->flags, i) && (__ac_isdel(h->flags, i) || !__hash_equal(h->keys[i], key))) { \ + i = (i + (++step)) & mask; \ + if (i == last) return h->n_buckets; \ + } \ + return __ac_iseither(h->flags, i)? h->n_buckets : i; \ + } else return 0; \ + } \ + SCOPE int kh_resize_##name(kh_##name##_t *h, khint_t new_n_buckets) \ + { /* This function uses 0.25*n_buckets bytes of working space instead of [sizeof(key_t+val_t)+.25]*n_buckets. */ \ + khint32_t *new_flags = 0; \ + khint_t j = 1; \ + { \ + kroundup32(new_n_buckets); \ + if (new_n_buckets < 4) new_n_buckets = 4; \ + if (h->size >= (khint_t)(new_n_buckets * __ac_HASH_UPPER + 0.5)) j = 0; /* requested size is too small */ \ + else { /* hash table size to be changed (shrink or expand); rehash */ \ + new_flags = (khint32_t*)kmalloc(__ac_fsize(new_n_buckets) * sizeof(khint32_t)); \ + if (!new_flags) return -1; \ + memset(new_flags, 0xaa, __ac_fsize(new_n_buckets) * sizeof(khint32_t)); \ + if (h->n_buckets < new_n_buckets) { /* expand */ \ + khkey_t *new_keys = (khkey_t*)krealloc((void *)h->keys, new_n_buckets * sizeof(khkey_t)); \ + if (!new_keys) { kfree(new_flags); return -1; } \ + h->keys = new_keys; \ + if (kh_is_map) { \ + khval_t *new_vals = (khval_t*)krealloc((void *)h->vals, new_n_buckets * sizeof(khval_t)); \ + if (!new_vals) { kfree(new_flags); return -1; } \ + h->vals = new_vals; \ + } \ + } /* otherwise shrink */ \ + } \ + } \ + if (j) { /* rehashing is needed */ \ + for (j = 0; j != h->n_buckets; ++j) { \ + if (__ac_iseither(h->flags, j) == 0) { \ + khkey_t key = h->keys[j]; \ + khval_t val; \ + khint_t new_mask; \ + new_mask = new_n_buckets - 1; \ + if (kh_is_map) val = h->vals[j]; \ + __ac_set_isdel_true(h->flags, j); \ + while (1) { /* kick-out process; sort of like in Cuckoo hashing */ \ + khint_t k, i, step = 0; \ + k = __hash_func(key); \ + i = k & new_mask; \ + while (!__ac_isempty(new_flags, i)) i = (i + (++step)) & new_mask; \ + __ac_set_isempty_false(new_flags, i); \ + if (i < h->n_buckets && __ac_iseither(h->flags, i) == 0) { /* kick out the existing element */ \ + { khkey_t tmp = h->keys[i]; h->keys[i] = key; key = tmp; } \ + if (kh_is_map) { khval_t tmp = h->vals[i]; h->vals[i] = val; val = tmp; } \ + __ac_set_isdel_true(h->flags, i); /* mark it as deleted in the old hash table */ \ + } else { /* write the element and jump out of the loop */ \ + h->keys[i] = key; \ + if (kh_is_map) h->vals[i] = val; \ + break; \ + } \ + } \ + } \ + } \ + if (h->n_buckets > new_n_buckets) { /* shrink the hash table */ \ + h->keys = (khkey_t*)krealloc((void *)h->keys, new_n_buckets * sizeof(khkey_t)); \ + if (kh_is_map) h->vals = (khval_t*)krealloc((void *)h->vals, new_n_buckets * sizeof(khval_t)); \ + } \ + kfree(h->flags); /* free the working space */ \ + h->flags = new_flags; \ + h->n_buckets = new_n_buckets; \ + h->n_occupied = h->size; \ + h->upper_bound = (khint_t)(h->n_buckets * __ac_HASH_UPPER + 0.5); \ + } \ + return 0; \ + } \ + SCOPE khint_t kh_put_##name(kh_##name##_t *h, khkey_t key, int *ret) \ + { \ + khint_t x; \ + if (h->n_occupied >= h->upper_bound) { /* update the hash table */ \ + if (h->n_buckets > (h->size<<1)) { \ + if (kh_resize_##name(h, h->n_buckets - 1) < 0) { /* clear "deleted" elements */ \ + *ret = -1; return h->n_buckets; \ + } \ + } else if (kh_resize_##name(h, h->n_buckets + 1) < 0) { /* expand the hash table */ \ + *ret = -1; return h->n_buckets; \ + } \ + } /* TODO: to implement automatically shrinking; resize() already support shrinking */ \ + { \ + khint_t k, i, site, last, mask = h->n_buckets - 1, step = 0; \ + x = site = h->n_buckets; k = __hash_func(key); i = k & mask; \ + if (__ac_isempty(h->flags, i)) x = i; /* for speed up */ \ + else { \ + last = i; \ + while (!__ac_isempty(h->flags, i) && (__ac_isdel(h->flags, i) || !__hash_equal(h->keys[i], key))) { \ + if (__ac_isdel(h->flags, i)) site = i; \ + i = (i + (++step)) & mask; \ + if (i == last) { x = site; break; } \ + } \ + if (x == h->n_buckets) { \ + if (__ac_isempty(h->flags, i) && site != h->n_buckets) x = site; \ + else x = i; \ + } \ + } \ + } \ + if (__ac_isempty(h->flags, x)) { /* not present at all */ \ + h->keys[x] = key; \ + __ac_set_isboth_false(h->flags, x); \ + ++h->size; ++h->n_occupied; \ + *ret = 1; \ + } else if (__ac_isdel(h->flags, x)) { /* deleted */ \ + h->keys[x] = key; \ + __ac_set_isboth_false(h->flags, x); \ + ++h->size; \ + *ret = 2; \ + } else *ret = 0; /* Don't touch h->keys[x] if present and not deleted */ \ + return x; \ + } \ + SCOPE void kh_del_##name(kh_##name##_t *h, khint_t x) \ + { \ + if (x != h->n_buckets && !__ac_iseither(h->flags, x)) { \ + __ac_set_isdel_true(h->flags, x); \ + --h->size; \ + } \ + } + +#define KHASH_DECLARE(name, khkey_t, khval_t) \ + __KHASH_TYPE(name, khkey_t, khval_t) \ + __KHASH_PROTOTYPES(name, khkey_t, khval_t) + +#define KHASH_INIT2(name, SCOPE, khkey_t, khval_t, kh_is_map, __hash_func, __hash_equal) \ + __KHASH_TYPE(name, khkey_t, khval_t) \ + __KHASH_IMPL(name, SCOPE, khkey_t, khval_t, kh_is_map, __hash_func, __hash_equal) + +#define KHASH_INIT(name, khkey_t, khval_t, kh_is_map, __hash_func, __hash_equal) \ + KHASH_INIT2(name, static kh_inline klib_unused, khkey_t, khval_t, kh_is_map, __hash_func, __hash_equal) + +/* --- BEGIN OF HASH FUNCTIONS --- */ + +/*! @function + @abstract Integer hash function + @param key The integer [khint32_t] + @return The hash value [khint_t] + */ +#define kh_int_hash_func(key) (khint32_t)(key) +/*! @function + @abstract Integer comparison function + */ +#define kh_int_hash_equal(a, b) ((a) == (b)) +/*! @function + @abstract 64-bit integer hash function + @param key The integer [khint64_t] + @return The hash value [khint_t] + */ +#define kh_int64_hash_func(key) (khint32_t)((key)>>33^(key)^(key)<<11) +/*! @function + @abstract 64-bit integer comparison function + */ +#define kh_int64_hash_equal(a, b) ((a) == (b)) +/*! @function + @abstract const char* hash function + @param s Pointer to a null terminated string + @return The hash value + */ +static kh_inline khint_t __ac_X31_hash_string(const char *s) +{ + khint_t h = (khint_t)*s; + if (h) for (++s ; *s; ++s) h = (h << 5) - h + (khint_t)*s; + return h; +} +/*! @function + @abstract Another interface to const char* hash function + @param key Pointer to a null terminated string [const char*] + @return The hash value [khint_t] + */ +#define kh_str_hash_func(key) __ac_X31_hash_string(key) +/*! @function + @abstract Const char* comparison function + */ +#define kh_str_hash_equal(a, b) (strcmp(a, b) == 0) + +static kh_inline khint_t __ac_Wang_hash(khint_t key) +{ + key += ~(key << 15); + key ^= (key >> 10); + key += (key << 3); + key ^= (key >> 6); + key += ~(key << 11); + key ^= (key >> 16); + return key; +} +#define kh_int_hash_func2(key) __ac_Wang_hash((khint_t)key) + +/* --- END OF HASH FUNCTIONS --- */ + +/* Other convenient macros... */ + +/*! + @abstract Type of the hash table. + @param name Name of the hash table [symbol] + */ +#define khash_t(name) kh_##name##_t + +/*! @function + @abstract Initiate a hash table. + @param name Name of the hash table [symbol] + @return Pointer to the hash table [khash_t(name)*] + */ +#define kh_init(name) kh_init_##name() + +/*! @function + @abstract Destroy a hash table. + @param name Name of the hash table [symbol] + @param h Pointer to the hash table [khash_t(name)*] + */ +#define kh_destroy(name, h) kh_destroy_##name(h) + +/*! @function + @abstract Reset a hash table without deallocating memory. + @param name Name of the hash table [symbol] + @param h Pointer to the hash table [khash_t(name)*] + */ +#define kh_clear(name, h) kh_clear_##name(h) + +/*! @function + @abstract Resize a hash table. + @param name Name of the hash table [symbol] + @param h Pointer to the hash table [khash_t(name)*] + @param s New size [khint_t] + */ +#define kh_resize(name, h, s) kh_resize_##name(h, s) + +/*! @function + @abstract Insert a key to the hash table. + @param name Name of the hash table [symbol] + @param h Pointer to the hash table [khash_t(name)*] + @param k Key [type of keys] + @param r Extra return code: -1 if the operation failed; + 0 if the key is present in the hash table; + 1 if the bucket is empty (never used); 2 if the element in + the bucket has been deleted [int*] + @return Iterator to the inserted element [khint_t] + */ +#define kh_put(name, h, k, r) kh_put_##name(h, k, r) + +/*! @function + @abstract Retrieve a key from the hash table. + @param name Name of the hash table [symbol] + @param h Pointer to the hash table [khash_t(name)*] + @param k Key [type of keys] + @return Iterator to the found element, or kh_end(h) if the element is absent [khint_t] + */ +#define kh_get(name, h, k) kh_get_##name(h, k) + +/*! @function + @abstract Remove a key from the hash table. + @param name Name of the hash table [symbol] + @param h Pointer to the hash table [khash_t(name)*] + @param k Iterator to the element to be deleted [khint_t] + */ +#define kh_del(name, h, k) kh_del_##name(h, k) + +/*! @function + @abstract Test whether a bucket contains data. + @param h Pointer to the hash table [khash_t(name)*] + @param x Iterator to the bucket [khint_t] + @return 1 if containing data; 0 otherwise [int] + */ +#define kh_exist(h, x) (!__ac_iseither((h)->flags, (x))) + +/*! @function + @abstract Get key given an iterator + @param h Pointer to the hash table [khash_t(name)*] + @param x Iterator to the bucket [khint_t] + @return Key [type of keys] + */ +#define kh_key(h, x) ((h)->keys[x]) + +/*! @function + @abstract Get value given an iterator + @param h Pointer to the hash table [khash_t(name)*] + @param x Iterator to the bucket [khint_t] + @return Value [type of values] + @discussion For hash sets, calling this results in segfault. + */ +#define kh_val(h, x) ((h)->vals[x]) + +/*! @function + @abstract Alias of kh_val() + */ +#define kh_value(h, x) ((h)->vals[x]) + +/*! @function + @abstract Get the start iterator + @param h Pointer to the hash table [khash_t(name)*] + @return The start iterator [khint_t] + */ +#define kh_begin(h) (khint_t)(0) + +/*! @function + @abstract Get the end iterator + @param h Pointer to the hash table [khash_t(name)*] + @return The end iterator [khint_t] + */ +#define kh_end(h) ((h)->n_buckets) + +/*! @function + @abstract Get the number of elements in the hash table + @param h Pointer to the hash table [khash_t(name)*] + @return Number of elements in the hash table [khint_t] + */ +#define kh_size(h) ((h)->size) + +/*! @function + @abstract Get the number of buckets in the hash table + @param h Pointer to the hash table [khash_t(name)*] + @return Number of buckets in the hash table [khint_t] + */ +#define kh_n_buckets(h) ((h)->n_buckets) + +/*! @function + @abstract Iterate over the entries in the hash table + @param h Pointer to the hash table [khash_t(name)*] + @param kvar Variable to which key will be assigned + @param vvar Variable to which value will be assigned + @param code Block of code to execute + */ +#define kh_foreach(h, kvar, vvar, code) { khint_t __i; \ + for (__i = kh_begin(h); __i != kh_end(h); ++__i) { \ + if (!kh_exist(h,__i)) continue; \ + (kvar) = kh_key(h,__i); \ + (vvar) = kh_val(h,__i); \ + code; \ + } } + +/*! @function + @abstract Iterate over the values in the hash table + @param h Pointer to the hash table [khash_t(name)*] + @param vvar Variable to which value will be assigned + @param code Block of code to execute + */ +#define kh_foreach_value(h, vvar, code) { khint_t __i; \ + for (__i = kh_begin(h); __i != kh_end(h); ++__i) { \ + if (!kh_exist(h,__i)) continue; \ + (vvar) = kh_val(h,__i); \ + code; \ + } } + +/* More convenient interfaces */ + +/*! @function + @abstract Instantiate a hash set containing integer keys + @param name Name of the hash table [symbol] + */ +#define KHASH_SET_INIT_INT(name) \ + KHASH_INIT(name, khint32_t, char, 0, kh_int_hash_func, kh_int_hash_equal) + +/*! @function + @abstract Instantiate a hash map containing integer keys + @param name Name of the hash table [symbol] + @param khval_t Type of values [type] + */ +#define KHASH_MAP_INIT_INT(name, khval_t) \ + KHASH_INIT(name, khint32_t, khval_t, 1, kh_int_hash_func, kh_int_hash_equal) + +/*! @function + @abstract Instantiate a hash set containing 64-bit integer keys + @param name Name of the hash table [symbol] + */ +#define KHASH_SET_INIT_INT64(name) \ + KHASH_INIT(name, khint64_t, char, 0, kh_int64_hash_func, kh_int64_hash_equal) + +/*! @function + @abstract Instantiate a hash map containing 64-bit integer keys + @param name Name of the hash table [symbol] + @param khval_t Type of values [type] + */ +#define KHASH_MAP_INIT_INT64(name, khval_t) \ + KHASH_INIT(name, khint64_t, khval_t, 1, kh_int64_hash_func, kh_int64_hash_equal) + +typedef const char *kh_cstr_t; +/*! @function + @abstract Instantiate a hash map containing const char* keys + @param name Name of the hash table [symbol] + */ +#define KHASH_SET_INIT_STR(name) \ + KHASH_INIT(name, kh_cstr_t, char, 0, kh_str_hash_func, kh_str_hash_equal) + +/*! @function + @abstract Instantiate a hash map containing const char* keys + @param name Name of the hash table [symbol] + @param khval_t Type of values [type] + */ +#define KHASH_MAP_INIT_STR(name, khval_t) \ + KHASH_INIT(name, kh_cstr_t, khval_t, 1, kh_str_hash_func, kh_str_hash_equal) + +#endif /* __AC_KHASH_H */ diff --git a/hicn-light/src/hicn/base/loop.c b/hicn-light/src/hicn/base/loop.c new file mode 100644 index 000000000..fecab9c5f --- /dev/null +++ b/hicn-light/src/hicn/base/loop.c @@ -0,0 +1,355 @@ +/* + * Copyright (c) 2017-2020 Cisco and/or its affiliates. + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at: + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +/** + * @file loop.c + * @brief Implementation of event loop based on libevent + */ + +#include <assert.h> +#include <event2/event.h> +#include <event2/thread.h> +#include <fcntl.h> // fcntl +#ifdef WITH_THREAD +#include <pthread.h> +#endif /* WITH_THREAD */ +#include <stdlib.h> +#include <sys/timerfd.h> +#include <unistd.h> // fcntl + +#include <hicn/util/log.h> +#include <hicn/util/map.h> + +#include "loop.h" + +loop_t * MAIN_LOOP = NULL; + +/** + * \brief Holds all callback parameters + */ +typedef struct { + void * owner; + fd_callback_t callback; + void * data; +} cb_wrapper_args_t; + +TYPEDEF_MAP_H(event_map, int, struct event *); +TYPEDEF_MAP(event_map, int, struct event *, int_cmp, int_snprintf, generic_snprintf); + +/* Map that associates timer fds with their associated cb_wrapper_args_t */ +TYPEDEF_MAP_H(timer_fd_map, int, cb_wrapper_args_t *); +TYPEDEF_MAP(timer_fd_map, int, cb_wrapper_args_t *, int_cmp, int_snprintf, generic_snprintf); + +struct loop_s { + struct event_base * event_base; + event_map_t * event_map; + timer_fd_map_t * timer_fd_map; +#ifdef WITH_THREAD + pthread_t thread; +#endif /* WITH_THREAD */ +}; + +loop_t * +loop_create() +{ + loop_t * loop = malloc(sizeof(loop_t)); + if (!loop) { + ERROR("[loop_create] Failed to allocate memory"); + goto ERR_MALLOC; + } + +#ifdef WITH_THREAD + evthread_use_pthreads(); +#endif /* WITH_THREAD */ + + loop->event_base = event_base_new(); + if (!loop) + goto ERR_EVENT; + + loop->event_map = event_map_create(); + if (!loop->event_map) { + ERROR("[loop_create] Failed to create event_map"); + goto ERR_EVENT_MAP; + } + + loop->timer_fd_map = timer_fd_map_create(); + if (!loop->timer_fd_map) { + ERROR("[loop_create] Failed to create timer_fd_map"); + goto ERR_TIMER_FD_MAP; + } + + event_set_log_callback(NULL); + + return loop; + + timer_fd_map_free(loop->timer_fd_map); +ERR_TIMER_FD_MAP: + event_map_free(loop->event_map); +ERR_EVENT_MAP: + event_base_free(loop->event_base); +ERR_EVENT: + free(loop); +ERR_MALLOC: + return NULL; +} + +void +loop_free(loop_t * loop) +{ + /* + * Release all timer cb_wrapper_args_t + * + * We need to stop all timers, this should release associated fd events at + * the same time... for that reason, this code has to be called before + * releasing events + */ + + int * timer_fd_map_array; + int n = timer_fd_map_get_key_array(loop->timer_fd_map, &timer_fd_map_array); + if (n < 0) { + ERROR("[loop_free] Could not get event map array"); + } else { + for (unsigned i = 0; i < n; i++) { + int fd = timer_fd_map_array[i]; + if (loop_unregister_timer(loop, fd) < 0) { + ERROR("[loop_free] Could not unregister timer"); + } + } + free(timer_fd_map_array); + } + timer_fd_map_free(loop->timer_fd_map); + + /* Release all events */ + + int * event_map_array; + n = event_map_get_key_array(loop->event_map, &event_map_array); + if (n < 0) { + ERROR("[loop_free] Could not get event map array"); + } else { + for (unsigned i = 0; i < n; i++) { + int fd = event_map_array[i]; + if (loop_unregister_fd(loop, fd) < 0) { + ERROR("[loop_free] Could not unregister fd"); + } + } + free(event_map_array); + } + event_map_free(loop->event_map); + + event_base_free(loop->event_base); + + free(loop); +} + +int +loop_dispatch(loop_t * loop) +{ +#ifdef WITH_THREAD + if (pthread_create(&loop->thread, NULL, (void * (*)(void *))event_base_dispatch, loop->event_base)) { + fprintf(stderr, "Error creating thread\n"); + return -1; + } +#else + event_base_dispatch(loop->event_base); +#endif /* WITH_THREAD */ + return 0; +} + +int +loop_undispatch(loop_t * loop) +{ +#ifdef WITH_THREAD + DEBUG("Waiting for loop to terminate..."); + if(pthread_join(loop->thread, NULL)) { + fprintf(stderr, "Error joining thread\n"); + return -1; + } + DEBUG("Loop terminated !"); +#endif /* WITH_THREAD */ + return 0; +} + +void +loop_break(loop_t * loop) +{ + event_base_loopbreak(loop->event_base); +} + +void cb_wrapper(evutil_socket_t fd, short what, void * arg) { + cb_wrapper_args_t * cb_wrapper_args = arg; + cb_wrapper_args->callback(cb_wrapper_args->owner, fd, cb_wrapper_args->data); +} + +int +loop_register_fd(loop_t * loop, int fd, void * callback_owner, + fd_callback_t callback, void * callback_data) +{ + /* This will be freed with the event */ + cb_wrapper_args_t * cb_wrapper_args = malloc(sizeof(cb_wrapper_args_t)); + *cb_wrapper_args = (cb_wrapper_args_t) { + .owner = callback_owner, + .callback = callback, + .data = callback_data, + }; + + evutil_make_socket_nonblocking(fd); + struct event * event = event_new(loop->event_base, fd, EV_READ | EV_PERSIST, cb_wrapper, cb_wrapper_args); + if (!event) { + ERROR("[loop_register_fd] event_new"); + goto ERR_EVENT_NEW; + } + + if (event_add(event, NULL) < 0) { + ERROR("[loop_register_fd] event_add"); + goto ERR_EVENT_ADD; + } + + if (event_map_add(loop->event_map, fd, event) < 0) { + ERROR("[loop_register_fd] event_map_add"); + goto ERR_EVENT_MAP; + } + + return 0; + +ERR_EVENT_MAP: +ERR_EVENT_ADD: + event_free(event); +ERR_EVENT_NEW: + return -1; +} + +int +loop_unregister_fd(loop_t * loop, int fd) +{ + struct event * event = NULL; + + if (event_map_remove(loop->event_map, fd, &event) < 0) { + ERROR("[loop_unregister_fd] Error removing event associated to fd"); + return -1; + } + + assert(event); + + cb_wrapper_args_t * cb_wrapper_args = event_get_callback_arg(event); + free(cb_wrapper_args); + + event_del(event); + event_free(event); + + return 0; +} + +int +loop_timer_callback(loop_t * loop, int fd, void * data) +{ + char buf[1024]; /* size is not important */ + cb_wrapper_args_t * cb_wrapper_args = data; + while (read(fd, &buf, sizeof(buf)) > 0) + ; + + int rc = cb_wrapper_args->callback(cb_wrapper_args->owner, fd, + cb_wrapper_args->data); + + return rc; +} + +int +_loop_register_timer(loop_t * loop, unsigned delay_ms, void * owner, + fd_callback_t callback, void * data) +{ + int fd = timerfd_create(CLOCK_MONOTONIC, 0); + if (fd == -1) { + perror("timerfd_create"); + return -1; + } + + if (fcntl(fd, F_SETFL, O_NONBLOCK) < 0) { + perror("fcntl"); + return -1; + } + + struct itimerspec ts = { + .it_interval = { + .tv_sec = delay_ms / 1000, + .tv_nsec = (delay_ms % 1000) * 1000000, + }, + .it_value = { + .tv_sec = delay_ms / 1000, + .tv_nsec = (delay_ms % 1000) * 1000000, + } + }; + + if (timerfd_settime(fd, 0, &ts, NULL) == -1) { + perror("timerfd_settime"); + return -1; + } + + /* This should be freed together with the timer release */ + cb_wrapper_args_t * cb_wrapper_args = malloc(sizeof(cb_wrapper_args_t)); + *cb_wrapper_args = (cb_wrapper_args_t) { + .owner = owner, + .callback = callback, + .data = data, + }; + + if (timer_fd_map_add(loop->timer_fd_map, fd, cb_wrapper_args) < 0) { + ERROR("[loop_register_timer] Could not add cb_wrapper to timer map"); + return -1; + } + + if (loop_register_fd(loop, fd, loop, + (fd_callback_t) loop_timer_callback, cb_wrapper_args) < 0) { + ERROR("[loop_register_timer] Error registering fd to event loop"); + return -1; + } + + return fd; +} + +int +loop_unregister_timer(loop_t * loop, int fd) +{ + struct itimerspec ts = { + .it_interval = { + .tv_sec = 0, + .tv_nsec = 0, + }, + .it_value = { /* This value disables the timer */ + .tv_sec = 0, + .tv_nsec = 0, + } + }; + ts.it_value.tv_sec = 0; + + if (timerfd_settime(fd, 0, &ts, NULL) == -1) { + perror("timerfd_settime"); + return -1; + } + + cb_wrapper_args_t * cb_wrapper_args; + if (timer_fd_map_remove(loop->timer_fd_map, fd, &cb_wrapper_args) < 0) { + ERROR("[loop_unregister_timer] Could not remove cb_wrapper from timer map"); + return -1; + } + assert(cb_wrapper_args); + free(cb_wrapper_args); + + if (loop_unregister_fd(loop, fd) < 0) { + ERROR("[loop_unregister_timer] Error unregistering fd from event loop"); + return -1; + } + + return 0; +} diff --git a/hicn-light/src/hicn/base/loop.h b/hicn-light/src/hicn/base/loop.h new file mode 100644 index 000000000..b73d91738 --- /dev/null +++ b/hicn-light/src/hicn/base/loop.h @@ -0,0 +1,104 @@ +/* + * Copyright (c) 2017-2019 Cisco and/or its affiliates. + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at: + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +/** + * \file loop.h + * \brief Face manager main loop + */ + +#ifndef FACEMGR_LOOP_H +#define FACEMGR_LOOP_H + +/* fd & timer callbacks */ + +typedef int (*fd_callback_t)(void * owner, int fd, void * data); + +typedef struct { + int fd; + void *owner; + fd_callback_t callback; + //int (*callback)(void * owner, int fd, void * data); + void *data; +} fd_callback_data_t; + +/* loop */ + +typedef struct loop_s loop_t; + +/* Global loop to be used in single threaded applications */ +extern loop_t * MAIN_LOOP; + +/** + * \brief Creates a main loop + * \return Pointer to the newly created loop, or NULL in case of error + */ +loop_t * loop_create(); + +/** + * \brief Releases a loop instance and frees all associated memory + * \param [in] loop - Pointer to the loop instance to free + */ +void loop_free(loop_t * loop); + +/** + * \brief Runs the loop instance to process events + * \param [in] loop - Pointer to the loop instance + * \return 0 if successful, -1 otherwise + */ +int loop_dispatch(loop_t * loop); + +/** + * \brief Terminates the dispatching of events + * \param [in] loop - Pointer to the loop instance + */ +int loop_undispatch(loop_t * loop); + +/** + * \brief Breaks out of the loop + * \param [in] loop - Pointer to the loop instance + */ +void loop_break(loop_t * loop); + +/** + * \brief Registers a new file descriptor to the event loop + * \param [in] fd - File descriptor to register + * \param [in] callback_owner - Pointer to the owner of the callack (first + * parameter of callback function) + * \param [in] callback - Callback function + * \param [in] callback_data - User data to pass alongside callback invocation + * \return 0 in case of success, -1 otherwise + */ +int +loop_register_fd(loop_t * loop, int fd, void * callback_owner, + fd_callback_t callback, void * callback_data); + +/** + * \brief Unregisters a file descriptor from the event loop + * \param [in] fd - File descriptor to unregister + * \return 0 in case of success, -1 otherwise + */ +int +loop_unregister_fd(loop_t * loop, int fd); + +int _loop_register_timer(loop_t * loop, unsigned delay_ms, void * owner, + fd_callback_t callback, void * data); + +#define loop_register_timer(loop, delay_ms, owner, callback, data) \ + _loop_register_timer(loop, delay_ms, owner, (fd_callback_t) callback, data) + +int +loop_unregister_timer(loop_t * loop, int fd); + +#endif /* FACEMGR_LOOP_H */ diff --git a/hicn-light/src/hicn/base/pool.c b/hicn-light/src/hicn/base/pool.c new file mode 100644 index 000000000..abca86422 --- /dev/null +++ b/hicn-light/src/hicn/base/pool.c @@ -0,0 +1,88 @@ +/* + * Copyright (c) 2020 Cisco and/or its affiliates. + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at: + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +/** + * \file pool.c + * \brief Implementation of fixed-size pool allocator + */ + +#include <stdlib.h> // calloc + +#include "common.h" +#include "pool.h" + + +/** + * \brief Initialize the pool data structure + * \param [in,out] pool - Pointer to the pool structure storage + * \param [in] elt_size - Size of elements in vector + * \param [in] max_elts - Maximum size + * + * Note that an empty pool might be equal to NULL + */ +void +_pool_init(void ** pool_ptr, size_t elt_size, size_t max_elts) +{ + pool_hdr_t * ph = calloc(POOL_HDRLEN + elt_size * max_elts, 1); + if (!ph) + abort(); + + /* Free indices */ + off_t * free_indices; + vector_init(free_indices, max_elts); + + uint_fast32_t * fb = ph->free_bitmap; + bitmap_init(fb, max_elts); + bitmap_set_to(fb, max_elts); + + for(unsigned i = 0; i < max_elts; i++) + free_indices[i] = (max_elts - 1) - i; + ph->free_indices = free_indices; + + *pool_ptr = (uint8_t*)ph + POOL_HDRLEN; +} + +void +_pool_free(void ** pool_ptr) +{ + free(pool_hdr(*pool_ptr)); + *pool_ptr = NULL; +} + +void +_pool_resize(void ** pool_ptr, size_t elt_size) +{ + pool_hdr_t * ph = pool_hdr(*pool_ptr); + size_t old_elts = ph->max_elts; + size_t new_elts = old_elts * 2; + + /* Double pool storage */ + ph = realloc(ph, POOL_HDRLEN + new_elts * elt_size); + if (!ph) + abort(); + ph->max_elts = new_elts; + + /* + * After resize, the pool will have old_elts free indices, ranging from + * old_elts to (new_elts - 1) + */ + off_t * free_indices = ph->free_indices; + vector_ensure_pos(free_indices, old_elts); + for (unsigned i = 0; i < old_elts; i++) + free_indices[i] = new_elts - 1 - i; + + /* Reassign pool pointer */ + *pool_ptr = (uint8_t*)ph + POOL_HDRLEN; +} diff --git a/hicn-light/src/hicn/base/pool.h b/hicn-light/src/hicn/base/pool.h new file mode 100644 index 000000000..360dedc5e --- /dev/null +++ b/hicn-light/src/hicn/base/pool.h @@ -0,0 +1,104 @@ +/* + * Copyright (c) 2020 Cisco and/or its affiliates. + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at: + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +/** + * \file array.h + * \brief Fixed-size pool allocator + */ + +#ifndef UTIL_POOL_H +#define UTIL_POOL_H + +#include <stdint.h> + +#include "bitmap.h" +#include "vector.h" + +/** Local variable naming macro. */ +#define _pool_var(v) _pool_##v + + +typedef struct { + size_t elt_size; + size_t max_elts; + uint_fast32_t * free_bitmap; + off_t * free_indices; /* vector of free indices */ +} pool_hdr_t; + +void _pool_init(void ** pool_ptr, size_t elt_size, size_t max_elts); +void _pool_free(void ** pool_ptr); +void _pool_resize(void ** pool_ptr, size_t elt_size); + +#define POOL_HDRLEN SIZEOF_ALIGNED(pool_hdr_t) + +/* This header actually prepends the actual content of the pool */ +#define pool_hdr(pool) ((pool_hdr_t *)((uint8_t*)(pool) - POOL_HDRLEN)) + +// XXX TODO need common naming for cur_len, len, max_len +#define pool_elts(pool) \ + (pool_hdr(pool)->max_elts - vector_len((pool_hdr(pool)->free_indices))) + +#define pool_init(pool, max_elts) \ + _pool_init((void**)&pool, sizeof(pool[0]), max_elts); + +#define pool_free(pool) \ + _pool_free((void**)&pool); + +#define pool_get(pool, elt) \ +do { \ + pool_hdr_t * _pool_var(ph) = pool_hdr(pool); \ + u64 _pool_var(l) = vector_len(_pool_var(ph)->free_indices); \ + if (_pool_var(l) == 0) \ + _pool_resize((void**)&(pool), sizeof((pool)[0])); \ + off_t _pool_var(free_id) = \ + _pool_var(ph)->free_indices[_pool_var(l) - 1]; \ + elt = (pool) + _pool_var(free_id); \ + memset(&elt, 0, sizeof(elt)); \ +} while(0) + +#define pool_put(pool, elt) \ +do { \ + pool_hdr_t * _pool_var(ph) = pool_hdr(pool); \ + u64 _pool_var(l) = vector_len(_pool_var(ph)->free_indices); \ + vector_ensure_pos(_pool_var(ph)->free_indices, _pool_var(l)); \ + _pool_var(ph)->free_indices[_pool_var(l)] = (elt) - (pool); \ + vector_len(_pool_var(ph)->free_indices)++; \ + bitmap_set(_pool_var(ph)->free_bitmap, _pool_var(l)); \ +} while(0) + +#define pool_validate_id(pool, id) \ + bitmap_is_unset((pool_hdr(pool))->free_bitmap, (id)) + +#define pool_enumerate(pool, i, eltp, BODY) \ +do { \ + pool_hdr_t * _pool_var(ph) = pool_hdr(pool); \ + uint_fast32_t * _pool_var(fb) = _pool_var(ph)->free_bitmap; \ + for((i) = 0; (i) < _pool_var(ph)->max_elts; (i)++) { \ + if (bitmap_is_unset(_pool_var(fb), (i))) \ + continue; \ + eltp = (pool) + (i); \ + do { BODY; } while (0); \ + } \ +} while(0) + +#define pool_foreach(pool, eltp, BODY) \ +do { \ + unsigned _pool_var(i); \ + pool_enumerate((pool), _pool_var(i), (eltp), BODY); \ +} while(0) + + + +#endif /* UTIL_POOL_H */ diff --git a/hicn-light/src/hicn/base/vector.c b/hicn-light/src/hicn/base/vector.c new file mode 100644 index 000000000..00ed7c305 --- /dev/null +++ b/hicn-light/src/hicn/base/vector.c @@ -0,0 +1,54 @@ +/* + * Copyright (c) 2020 Cisco and/or its affiliates. + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at: + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +/** + * \file vector.c + * \brief Implementation of resizeable static array + */ + +#include <stddef.h> // size_t +#include <stdlib.h> // calloc + +#include "vector.h" + +void +_vector_init(void ** vector_ptr, size_t elt_size, size_t max_elts) +{ + vector_hdr_t * vh = calloc(VECTOR_HDRLEN + elt_size * max_elts, 1); + *vector_ptr = (uint8_t*)vh - VECTOR_HDRLEN; +} + +void +_vector_free(void ** vector_ptr) +{ + free(vector_hdr(*vector_ptr)); + *vector_ptr = NULL; +} + +void +_vector_resize(void ** vector_ptr, size_t elt_size, off_t pos) +{ + vector_hdr_t * vh = vector_hdr(*vector_ptr); + size_t new_elts = (pos > 0) ? next_pow2(pos) : vh->max_elts * 2; + + /* Double the allocated vector size */ + vh = realloc(vh, VECTOR_HDRLEN + new_elts * elt_size); + if (!vh) + abort(); + vh->max_elts = new_elts; + + /* Reassign vector pointer */ + *vector_ptr = (uint8_t*) + VECTOR_HDRLEN; +} diff --git a/hicn-light/src/hicn/base/vector.h b/hicn-light/src/hicn/base/vector.h new file mode 100644 index 000000000..9b99ba813 --- /dev/null +++ b/hicn-light/src/hicn/base/vector.h @@ -0,0 +1,70 @@ +/* + * Copyright (c) 2020 Cisco and/or its affiliates. + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at: + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +/** + * \file vector.h + * \brief Resizeable static array + */ + +#ifndef UTIL_VECTOR_H +#define UTIL_VECTOR_H + +#include <stddef.h> +#include <stdint.h> +#include <sys/types.h> + +#include "common.h" + +/** Local variable naming macro. */ +#define _vector_var(v) _vector_##v + +typedef struct { + size_t num_elts; + size_t max_elts; +} vector_hdr_t; + +void _vector_init(void ** vector_ptr, size_t elt_size, size_t max_elts); +void _vector_free(void ** vector_ptr); +void _vector_resize(void ** vector_ptr, size_t elt_size, off_t pos); + +/* Make sure elements following the header are aligned */ +#define VECTOR_HDRLEN SIZEOF_ALIGNED(vector_hdr_t) + +/* This header actually prepends the actual content of the vector */ +#define vector_hdr(vector) ((vector_hdr_t *)((uint8_t*)vector - VECTOR_HDRLEN)) + +#define vector_init(vector, max_elts) \ + _vector_init((void**)&vector, sizeof(vector[0]), max_elts) + +#define vector_free(vector) \ + _vector_free(&vector) + +#define vector_len(vector) (vector_hdr(vector)->num_elts) + +#define vector_resize(vector) _vector_resize((void**)&(vector), sizeof((vector)[0]), 0) + +#define vector_ensure_pos(vector, pos) \ +do { \ + if ((pos) >= vector_len(vector)) \ + _vector_resize((void**)&(vector), sizeof((vector)[0]), pos); \ +} while(0) + +#define vector_push(vector, elt) \ +do { \ + vector_ensure_pos(vector_len(vector)); \ + vector[vector_len(vector)++] = elt; \ +} while(0) + +#endif /* UTIL_VECTOR_H */ |