diff options
Diffstat (limited to 'hicn-light/src/hicn/base')
| -rw-r--r-- | hicn-light/src/hicn/base/CMakeLists.txt | 39 | ||||
| -rw-r--r-- | hicn-light/src/hicn/base/bitmap.h | 188 | ||||
| -rw-r--r-- | hicn-light/src/hicn/base/common.h | 62 | ||||
| -rw-r--r-- | hicn-light/src/hicn/base/hash.h | 349 | ||||
| -rw-r--r-- | hicn-light/src/hicn/base/khash.h | 748 | ||||
| -rw-r--r-- | hicn-light/src/hicn/base/loop.c | 201 | ||||
| -rw-r--r-- | hicn-light/src/hicn/base/loop.h | 138 | ||||
| -rw-r--r-- | hicn-light/src/hicn/base/pool.c | 158 | ||||
| -rw-r--r-- | hicn-light/src/hicn/base/pool.h | 254 | ||||
| -rw-r--r-- | hicn-light/src/hicn/base/ring.c | 45 | ||||
| -rw-r--r-- | hicn-light/src/hicn/base/ring.h | 201 | ||||
| -rw-r--r-- | hicn-light/src/hicn/base/vector.c | 85 | ||||
| -rw-r--r-- | hicn-light/src/hicn/base/vector.h | 327 |
13 files changed, 2795 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..1180ed05b --- /dev/null +++ b/hicn-light/src/hicn/base/CMakeLists.txt @@ -0,0 +1,39 @@ +# Copyright (c) 2021-2022 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. + +list(APPEND HEADER_FILES + ${CMAKE_CURRENT_SOURCE_DIR}/bitmap.h + ${CMAKE_CURRENT_SOURCE_DIR}/common.h + ${CMAKE_CURRENT_SOURCE_DIR}/hash.h + ${CMAKE_CURRENT_SOURCE_DIR}/khash.h + ${CMAKE_CURRENT_SOURCE_DIR}/loop.h + ${CMAKE_CURRENT_SOURCE_DIR}/pool.h + ${CMAKE_CURRENT_SOURCE_DIR}/ring.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}/ring.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..ed3fac2fd --- /dev/null +++ b/hicn-light/src/hicn/base/bitmap.h @@ -0,0 +1,188 @@ +/* + * Copyright (c) 2021 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 <assert.h> +#include <string.h> +#include <sys/param.h> // MIN, MAX + +#include <hicn/util/log.h> + +#include "common.h" +#include "vector.h" + +typedef uint_fast32_t bitmap_t; + +#define BITMAP_WIDTH(bitmap) (sizeof((bitmap)[0]) * 8) + +/** + * @brief Allocate and initialize a bitmap + * + * @param[in,out] bitmap Bitmap to allocate and initialize + * @param[in] max_size Bitmap max_size + */ +#define bitmap_init(bitmap, init_size, max_size) \ + vector_init( \ + bitmap, next_pow2((init_size) / BITMAP_WIDTH(bitmap)), \ + max_size == 0 ? 0 : next_pow2((max_size) / BITMAP_WIDTH(bitmap))) + +/* + * @brief Ensures a bitmap is sufficiently large to hold an element at the + * given position. + * + * @param[in] bitmap The bitmap for which to validate the position. + * @param[in] pos The position to validate. + * + * NOTE: + * - This function should always be called before writing to a bitmap element + * to eventually make room for it (the bitmap will eventually be resized). + */ +static inline int bitmap_ensure_pos(bitmap_t** bitmap, off_t pos) { + size_t offset = pos / BITMAP_WIDTH(*bitmap); + return vector_ensure_pos(*bitmap, offset); +} + +/** + * @brief Returns the allocated size of a bitmap. + * + * @see listener_table_get_by_id + */ +#define bitmap_get_alloc_size(bitmap) vector_get_alloc_size(bitmap) + +/** + * @brief Retrieve the state of the i-th bit in the bitmap. + * + * @param[in] bitmap The bitmap to access. + * @param[in] i The bit position. + */ +static inline int bitmap_get(const bitmap_t* bitmap, off_t i) { + size_t offset = i / BITMAP_WIDTH(bitmap); + assert(offset < bitmap_get_alloc_size(bitmap)); + size_t pos = i % BITMAP_WIDTH(bitmap); + size_t shift = BITMAP_WIDTH(bitmap) - pos - 1; + return (bitmap[offset] >> shift) & 1; +} + +/* + * @brief Returns whether the i-th bit is set (equal to 1) in a bitmap. + * + * @param[in] bitmap The bitmap to access. + * @param[in] i The bit position. + * + * @return bool + */ +#define bitmap_is_set(bitmap, i) (bitmap_get((bitmap), (i)) == 1) +#define bitmap_is_unset(bitmap, i) (bitmap_get((bitmap), (i)) == 0) + +/* + * @brief Returns whether the i-th bit is unset (equal to 0) in a bitmap. + * + * @param[in] bitmap The bitmap to access. + * @param[in] i The bit position. + * + * @return bool + */ +#define bitmap_set(bitmap, i) _bitmap_set((bitmap_t**)&bitmap, i) + +/* + * @brief Returns whether the i-th bit is unset (equal to 0) in a bitmap + * (helper). + * + * @param[in] bitmap The bitmap to access. + * @param[in] i The bit position. + * + * @return bool + */ +static inline int _bitmap_set(bitmap_t** bitmap, off_t i) { + if (bitmap_ensure_pos(bitmap, i) < 0) return -1; + size_t offset = i / BITMAP_WIDTH(bitmap); + size_t pos = i % BITMAP_WIDTH(bitmap); + size_t shift = BITMAP_WIDTH(bitmap) - pos - 1; + (*bitmap)[offset] |= (bitmap_t)1 << shift; + return 0; +} + +static inline int bitmap_unset(bitmap_t* bitmap, off_t i) { + if (bitmap_ensure_pos(&bitmap, i) < 0) return -1; + size_t offset = i / BITMAP_WIDTH(bitmap); + size_t pos = i % BITMAP_WIDTH(bitmap); + size_t shift = BITMAP_WIDTH(bitmap) - pos - 1; + bitmap[offset] &= ~(1ul << shift); + return 0; +} + +static inline int bitmap_set_range(bitmap_t* bitmap, off_t from, off_t to) { + assert(from <= to); + ssize_t offset_from = from / BITMAP_WIDTH(bitmap); + ssize_t offset_to = to / BITMAP_WIDTH(bitmap); + size_t pos_from = from % BITMAP_WIDTH(bitmap); + size_t pos_to = to % BITMAP_WIDTH(bitmap); + + /* + * First block initialization is needed if <from> is not aligned with the + * bitmap element size or if to is within the same one. + */ + if ((pos_from != 0) || + ((offset_to == offset_from) && (pos_to != BITMAP_WIDTH(bitmap) - 1))) { + size_t from_end = MIN(to, (offset_from + 1) * BITMAP_WIDTH(bitmap)); + for (size_t k = from; k < from_end; k++) { + if (bitmap_set(bitmap, k) < 0) goto END; + } + } + + /* + * Second block is needed if <to> is not aligned with the bitmap element + * size + */ + if ((pos_to != BITMAP_WIDTH(bitmap) - 1) && (offset_to != offset_from)) { + size_t to_start = MAX(from, offset_to * BITMAP_WIDTH(bitmap)); + for (size_t k = to_start; k < (size_t)to; k++) { + if (bitmap_set(bitmap, k) < 0) goto END; + } + } + + if (pos_from != 0) offset_from += 1; + if (pos_to != BITMAP_WIDTH(bitmap) - 1) offset_to -= 1; + + /* + * We need to cover both elements at position offset_from and offset_to + * provided that offset_from is not bigger + */ + if (offset_to >= offset_from) { + memset(&bitmap[offset_from], 0xFF, + (offset_to - offset_from + 1) * sizeof(bitmap[0])); + } + + return 0; + +END: + ERROR("Error setting bitmap range\n"); + return -1; +} + +#define bitmap_set_to(bitmap, to) bitmap_set_range((bitmap), 0, (to)) + +#define bitmap_free(bitmap) vector_free(bitmap) + +#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..9f7e3beec --- /dev/null +++ b/hicn-light/src/hicn/base/common.h @@ -0,0 +1,62 @@ +/* + * Copyright (c) 2021 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_clzl2(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 : 1ul << (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..3c54feb29 --- /dev/null +++ b/hicn-light/src/hicn/base/hash.h @@ -0,0 +1,349 @@ +/* + * Copyright (c) 2021 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..4c62b0260 --- /dev/null +++ b/hicn-light/src/hicn/base/khash.h @@ -0,0 +1,748 @@ +/* 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) + +/****************************************************************************** + * Custom + *high-level interface + ******************************************************************************/ + +#define _kh_var(x) _kh_var_##x + +/** + * @brief Return the value corresponding to a key in the hashtable. + * @return The value associated with the key or null if not found + */ +#define kh_get_val(kname, hashtable, key, default_val) \ + ({ \ + khiter_t _kh_var(k) = kh_get(kname, hashtable, key); \ + (_kh_var(k) != kh_end(hashtable) ? kh_val(hashtable, _kh_var(k)) \ + : default_val); \ + }) + +/** + * @brief Add key/value pair in the hashtable. + * @return 0 if an existing value (corresponding to the provided key) + * has been replaced; 1 if a new key/value pair has been added + * (the key was not already present in the hash table); + * 2 if a new key/value pair has been added in correspondence + * of a key previously deleted key + */ +#define kh_put_val(kname, hashtable, key, val) \ + ({ \ + int _kh_var(ret); \ + khiter_t _kh_var(k) = kh_put(kname, hashtable, key, &_kh_var(ret)); \ + kh_value(hashtable, _kh_var(k)) = val; \ + _kh_var(ret); \ + }) + +/** + * @brief Remove a key/value pair from the hashtable. + * @return void + */ +#define kh_remove_val(kname, hashtable, key) \ + ({ \ + khiter_t _kh_var(k) = kh_get(kname, hashtable, key); \ + if (_kh_var(k) != kh_end(hashtable)) { \ + free((void *)kh_key(hashtable, _kh_var(k))); \ + kh_del(kname, hashtable, _kh_var(k)); \ + } \ + }) + +/** + * @brief Free the hashtable. + * @return void + */ +#define kh_free(kname, hashtable) \ + ({ \ + const void *_kh_var(key); \ + unsigned _kh_var(val); \ + (void)_kh_var(val); \ + \ + kh_foreach(hashtable, _kh_var(key), _kh_var(val), \ + { free((void *)_kh_var(key)); }) kh_destroy(kname, hashtable); \ + }) + +#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..68970ed3a --- /dev/null +++ b/hicn-light/src/hicn/base/loop.c @@ -0,0 +1,201 @@ +/* + * Copyright (c) 2021 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/event_struct.h> +#include <event2/thread.h> +#include <fcntl.h> // fcntl +#ifdef WITH_THREAD +#include <pthread.h> +#endif /* WITH_THREAD */ +#include <hicn/util/log.h> +#include <stdlib.h> +#include <unistd.h> // fcntl + +#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 enum { + EVTYPE_TIMER, + EVTYPE_FD, +} event_type_t; + +struct loop_s { + /* Libevent-based implementation */ + struct event_base *event_base; +}; + +struct event_s { + /* Reference to loop */ + loop_t *loop; + + /* Event type*/ + event_type_t event_type; + + /* Raw event */ + struct event raw_event; + + /* Callback on event */ + cb_wrapper_args_t callback; +}; + +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->event_base) goto ERR_EVENT; + + event_set_log_callback(NULL); + + return loop; + +ERR_EVENT: +ERR_MALLOC: + return NULL; +} + +void loop_free(loop_t *loop) { + event_base_free(loop->event_base); + free(loop); +} + +int _loop_dispatch(loop_t *loop, int flags) { + event_base_loop(loop->event_base, flags); + return 0; +} + +int loop_dispatch(loop_t *loop) { + return _loop_dispatch(loop, EVLOOP_NO_EXIT_ON_EMPTY); +} + +int loop_break(loop_t *loop) { return event_base_loopbreak(loop->event_base); } + +int loop_undispatch(loop_t *loop) { return 0; } + +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); +} + +static inline void _event_create(event_t **event, loop_t *loop, + event_type_t type, void *callback_owner, + fd_callback_t callback, void *callback_data) { + *event = malloc(sizeof(event_t)); + (*event)->callback = (cb_wrapper_args_t){ + .owner = callback_owner, + .callback = callback, + .data = callback_data, + }; + (*event)->event_type = type; + (*event)->loop = loop; +} + +int loop_fd_event_create(event_t **event, loop_t *loop, int fd, + void *callback_owner, fd_callback_t callback, + void *callback_data) { + _event_create(event, loop, EVTYPE_FD, callback_owner, callback, + callback_data); + + evutil_make_socket_nonblocking(fd); + event_assign(&(*event)->raw_event, loop->event_base, fd, EV_READ | EV_PERSIST, + cb_wrapper, &(*event)->callback); + + return 0; +} + +int loop_fd_event_register(event_t *event) { + assert(event->event_type == EVTYPE_FD); + + if (event_add(&event->raw_event, NULL) < 0) { + ERROR("[loop_fd_event_register] event_add"); + goto ERR_EVENT_ADD; + } + + return 0; + +ERR_EVENT_ADD: + return -1; +} + +int loop_event_unregister(event_t *event) { + event_del(&event->raw_event); + return 0; +} + +int loop_timer_create(event_t **timer, loop_t *loop, void *callback_owner, + fd_callback_t callback, void *callback_data) { + _event_create(timer, loop, EVTYPE_TIMER, callback_owner, callback, + callback_data); + + evtimer_assign(&(*timer)->raw_event, loop->event_base, cb_wrapper, + &(*timer)->callback); + + return 0; +} + +static inline void _ms_to_timeval(unsigned delay_ms, struct timeval *tv) { + tv->tv_sec = delay_ms / 1000; + tv->tv_usec = (delay_ms % 1000) * 1000; +} + +int loop_timer_register(event_t *timer, unsigned delay_ms) { + assert(timer->event_type == EVTYPE_TIMER); + + struct timeval tv; + _ms_to_timeval(delay_ms, &tv); + + if (tv.tv_sec == 0 && tv.tv_usec == 0) { + event_active(&timer->raw_event, EV_TIMEOUT, 0); + } else { + event_add(&timer->raw_event, &tv); + } + + return 0; +} + +int loop_timer_is_enabled(event_t *timer) { + return evtimer_pending(&timer->raw_event, NULL) != 0; +} + +int loop_event_free(event_t *event) { + int ret = loop_event_unregister(event); + free(event); + return ret; +} diff --git a/hicn-light/src/hicn/base/loop.h b/hicn-light/src/hicn/base/loop.h new file mode 100644 index 000000000..f81af333b --- /dev/null +++ b/hicn-light/src/hicn/base/loop.h @@ -0,0 +1,138 @@ +/* + * Copyright (c) 2021 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 UTIL_LOOP_H +#define UTIL_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; + void *data; +} fd_callback_data_t; + +/* loop */ + +typedef struct loop_s loop_t; +typedef struct event_s event_t; + +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 (helper). + * \param [in] loop - Pointer to the loop instance + * \param [in] flags - Loop mode: EVLOOP_ONCE, EVLOOP_NONBLOCK or + * EVLOOP_NO_EXIT_ON_EMPTY \return 0 if successful, -1 otherwise + */ +int _loop_dispatch(loop_t *loop, int flags); + +/** + * \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_break(loop_t *loop); + +int loop_undispatch(loop_t *loop); + +/** Create new event associated with given fd. + * \param [out] event - Struct representing new fd event + * \param [in] loop - Loop running events + * \param [in] fd - fd 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_fd_event_create(event_t **event, loop_t *loop, int fd, + void *callback_owner, fd_callback_t callback, + void *callback_data); + +/** + * Register event in corresponding event loop. + * \param [in] event - Struct representing fd event + * \return 0 in case of success, -1 otherwise + */ +int loop_fd_event_register(event_t *event); + +/** + * Unregister event from corresponding event loop. + * \param [in] event - Struct representing fd event + * \return 0 in case of success, -1 otherwise + */ +int loop_event_unregister(event_t *event); + +/** + * Free event object. + * \param [in] event - Struct representing the event + * \return 0 in case of success, -1 otherwise + */ +int loop_event_free(event_t *event); + +/** Create new timer event. + * \param [out] event - Struct representing new timer event + * \param [in] loop - Loop running events + * \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_timer_create(event_t **timer, loop_t *loop, void *callback_owner, + fd_callback_t callback, void *callback_data); + +/** + * Register event in corresponding event loop. + * \param [in] timer - Struct representing timer event + * \return 0 in case of success, -1 otherwise + */ +int loop_timer_register(event_t *timer, unsigned delay_ms); + +/** + * Check if timer is enabled. + * \param [in] timer - Struct representing timer event + * \return 1 if enabled, 0 otherwise + */ +int loop_timer_is_enabled(event_t *timer); + +#endif /* UTIL_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..ba2a14c5f --- /dev/null +++ b/hicn-light/src/hicn/base/pool.c @@ -0,0 +1,158 @@ +/* + * Copyright (c) 2021 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. + * + * NOTE: + * - Ideally, we should have a single realloc per resize, that would encompass + * both the free indices vector and bitmap, by nesting data structures. Because + * of the added complexity, and by lack of evidence of the need for this, we + * currently rely on a simpler implementation. + */ + +#include <assert.h> +#include <stdlib.h> // calloc + +#include "common.h" +#include "pool.h" + +#include <stdio.h> // XXX + +void _pool_init(void** pool_ptr, size_t elt_size, size_t init_size, + size_t max_size) { + assert(pool_ptr); + assert(elt_size); + + init_size = next_pow2(init_size); + + if (max_size && init_size > max_size) goto ERR_MAX_SIZE; + + /* The initial pool size is rounded to the next power of two */ + size_t alloc_size = next_pow2(init_size); + + pool_hdr_t* ph = calloc(POOL_HDRLEN + alloc_size * elt_size, 1); + if (!ph) goto ERR_MALLOC; + + ph->elt_size = elt_size; + ph->alloc_size = alloc_size; + ph->max_size = max_size; + + /* Free indices */ + off_t* free_indices; + vector_init(free_indices, init_size, max_size); + for (unsigned i = 0; i < init_size; i++) + free_indices[i] = (init_size - 1) - i; + vector_len(free_indices) = init_size; + ph->free_indices = free_indices; + + /* Free bitmap */ + uint_fast32_t* fb = ph->free_bitmap; + bitmap_init(fb, init_size, max_size); + bitmap_set_to(fb, init_size); + ph->free_bitmap = fb; + + *pool_ptr = (uint8_t*)ph + POOL_HDRLEN; + + return; + +ERR_MALLOC: +ERR_MAX_SIZE: + *pool_ptr = NULL; + return; +} + +void _pool_free(void** pool_ptr) { + pool_hdr_t* ph = pool_hdr(*pool_ptr); + vector_free(ph->free_indices); + bitmap_free(ph->free_bitmap); + + free(pool_hdr(*pool_ptr)); + *pool_ptr = NULL; +} + +bool _pool_validate_id(void** pool_ptr, off_t id) { + pool_hdr_t* ph = pool_hdr(*pool_ptr); + size_t pool_size = pool_get_alloc_size(*pool_ptr); + if (id >= pool_size || !bitmap_is_unset(ph->free_bitmap, id)) return false; + + return true; +} + +void _pool_resize(void** pool_ptr, size_t elt_size) { + pool_hdr_t* ph = pool_hdr(*pool_ptr); + size_t old_size = ph->alloc_size; + size_t new_size = old_size * 2; + + TRACE("pool_resize to %lu", new_size); + + if (ph->max_size && new_size > ph->max_size) goto ERR_MAX_SIZE; + + /* Double pool storage */ + ph = realloc(ph, POOL_HDRLEN + new_size * elt_size); + if (!ph) goto ERR_REALLOC; + ph->elt_size = elt_size; + ph->alloc_size = new_size; + + /* + * After resize, the pool will have new free indices, ranging from + * old_size to (new_size - 1) + */ + vector_ensure_pos(ph->free_indices, old_size); + for (unsigned i = 0; i < old_size; i++) + ph->free_indices[i] = new_size - 1 - i; + vector_len(ph->free_indices) = old_size; + + /* We also need to update the bitmap */ + bitmap_ensure_pos(&(ph->free_bitmap), new_size - 1); + bitmap_set_range(ph->free_bitmap, old_size, new_size - 1); + + /* Reassign pool pointer */ + *pool_ptr = (uint8_t*)ph + POOL_HDRLEN; + + return; + +ERR_REALLOC: +ERR_MAX_SIZE: + *pool_ptr = NULL; + return; +} + +off_t _pool_get(void** pool_ptr, void** elt, size_t elt_size) { + pool_hdr_t* ph = pool_hdr(*pool_ptr); + uint64_t l = vector_len(ph->free_indices); + if (l == 0) { + _pool_resize(pool_ptr, elt_size); + ph = pool_hdr(*pool_ptr); + l = vector_len(ph->free_indices); + } + off_t free_id = ph->free_indices[l - 1]; + vector_len(ph->free_indices)--; + bitmap_unset(ph->free_bitmap, free_id); + *elt = *pool_ptr + free_id * elt_size; + memset(*elt, 0, elt_size); + return free_id; +} + +void _pool_put(void** pool_ptr, void** elt, size_t elt_size) { + pool_hdr_t* ph = pool_hdr(*pool_ptr); + uint64_t l = vector_len(ph->free_indices); + vector_ensure_pos(ph->free_indices, l); + off_t freed_id = (*elt - *pool_ptr) / elt_size; + ph->free_indices[l] = freed_id; + vector_len(ph->free_indices)++; + bitmap_set(ph->free_bitmap, freed_id); +} diff --git a/hicn-light/src/hicn/base/pool.h b/hicn-light/src/hicn/base/pool.h new file mode 100644 index 000000000..b6573195c --- /dev/null +++ b/hicn-light/src/hicn/base/pool.h @@ -0,0 +1,254 @@ +/* + * Copyright (c) 2021 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.h + * \brief Fixed-size pool allocator. + * + * This memory pool allocates a single block of memory that is used to + * efficiently allocate/deallocate fixed-size blocks for high churn data + * structures. + * + * Internally this data structure leverages a vector for managing elements (and + * it thus resizeable if needed), as well as a list of free indices (in the + * form of another vector) and a bitmap marking free indices also (for fast + * iteration). + * + * The internal API manipulates a pointer to the vector that that is can be + * seamlessly resized, and a more convenient user interface is provided through + * macros. + * + * The vector of free indices is managed as a stack where elements indices are + * retrieved from and put back to the end of the vector. In the bitmap, + * available elements are set to 1, and unset to 0 when in use. + * + * The pool is not currently resized down when releasing elements. + * + * It is freely inspired (and simplified) from the VPP infra infrastructure + * library. + */ + +#ifndef UTIL_POOL_H +#define UTIL_POOL_H + +#include <stdint.h> +#include <stdbool.h> + +#include "bitmap.h" +#include "vector.h" + +/* Pool header */ + +typedef struct { + size_t elt_size; + size_t alloc_size; + size_t max_size; + bitmap_t *free_bitmap; /* bitmap of free indices */ + off_t *free_indices; /* vector of free indices */ +} pool_hdr_t; + +#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)) + +/******************************************************************************/ +/* Helpers */ + +/** Local variable naming macro. */ +#define _pool_var(v) _pool_##v + +/** + * @brief Allocate and initialize a pool data structure (helper). + * + * @param[in,out] pool_ptr Pointer to the pool data structure. + * @param[in] elt_size Size of elements in vector. + * @param[in] max_size Maximum size. + * + * NOTE: that an empty pool might be equal to NULL. + */ +void _pool_init(void **pool_ptr, size_t elt_size, size_t init_size, + size_t max_size); + +/** + * @brief Free a pool data structure (helper). + * + * @param[in] pool_ptr Pointer to the pool data structure. + */ +void _pool_free(void **pool_ptr); + +/** + * @brief Resize a pool data structure (helper). + * + * @param pool_ptr Pointer to the pool data structure. + * + * This function should only be called internally, as the resize is implicitly + * done (if allowed by the maximum size) when the user tries to get a new slot. + */ +void _pool_resize(void **pool_ptr, size_t elt_size); + +/** + * @brief Get a free element from the pool data structure (helper). + * + * @param[in] pool Pointer to the pool data structure to use. + * @param[in,out] elt Pointer to an empty element that will be used to return + * the allocated one from the pool. + * + * NOTES: + * - The memory chunk is cleared upon attribution + */ +off_t _pool_get(void **pool, void **elt, size_t elt_size); + +/** + * @brief Put an element back into the pool data structure (helper). + * + * @param[in] pool_ptr Pointer to the pool data structure to use. + * @param[in] elt Pointer to the pool element to put back. + */ +void _pool_put(void **pool, void **elt, size_t elt_size); + +/** + * @brief Validate a pool element by index (helper). + * + * @param[in] pool The pool data structure to use. + * @param[in] id The index of the element to validate. + * + * @return bool A flag indicating whether the index is valid or not. + */ +bool _pool_validate_id(void **pool_ptr, off_t id); +/******************************************************************************/ +/* Public API */ + +/** + * @brief Allocate and initialize a pool data structure. + * + * @param[in,out] pool Pointer to the pool data structure. + * @param[in] elt_size Size of elements in pool. + * @param[in] max_size Maximum size. + * + * NOTE: that an empty pool might be equal to NULL. + */ +#define pool_init(pool, init_size, max_size) \ + _pool_init((void **)&pool, sizeof(pool[0]), init_size, max_size); + +/** + * @brief Free a pool data structure. + * + * @param[in] pool The pool data structure to free. + */ +#define pool_free(pool) _pool_free((void **)&pool); + +/** + * @brief Get a free element from the pool data structure. + * + * @param[in] pool The pool data structure to use. + * @param[in,out] elt An empty element that will be used to return the + * allocated one from the pool. + * + * NOTES: + * - The memory chunk is cleared upon attribution + */ +#define pool_get(pool, elt) \ + _pool_get((void **)&pool, (void **)&elt, sizeof(*elt)) + +/** + * @brief Put an element back into the pool data structure. + * + * @param[in] pool The pool data structure to use. + * @param[in] elt The pool element to put back. + */ +#define pool_put(pool, elt) \ + _pool_put((void **)&pool, (void **)&elt, sizeof(*elt)) + +/** + * @brief Validate a pool element by index. + * + * @param[in] pool The pool data structure to use. + * @param[in] id The index of the element to validate. + * + * @return bool A flag indicating whether the index is valid or not. + */ +#define pool_validate_id(pool, id) _pool_validate_id((void **)&pool, (id)) + +#define pool_get_free_indices_size(pool) \ + vector_len(pool_hdr(pool)->free_indices) + +/** + * @brief Returns the current length of the pool. + * + * @param[in] pool The pool data structure for which to return the length. + * + * @return size_t The current length of the pool. + * + * NOTE: + * - The pool length corresponds to the number of allocated elements, not the + * size of the pool. + */ +#define pool_len(pool) \ + (pool_hdr(pool)->alloc_size - pool_get_free_indices_size(pool)) + +/** + * @brief Enumerate elements from a pool. + * + * @param[in] pool The pool data structure to enumerate. + * @param[in, out] i An integer that will be used for enumeration. + * @param[in, out] eltp A pointer to the element type that will be used for + * enumeration. + * @param[in] BODY Block to execute during enumeration. + * + * Enumeration will iteratively execute BODY with (i, eltp) corresponding + * respectively to the index and element found in the pool. + * + * NOTE: i stars at 0. + */ +#define pool_enumerate(pool, i, eltp, BODY) \ + do { \ + pool_hdr_t *_pool_var(ph) = pool_hdr(pool); \ + bitmap_t *_pool_var(fb) = _pool_var(ph)->free_bitmap; \ + for ((i) = 0; (i) < _pool_var(ph)->alloc_size; (i)++) { \ + if (bitmap_is_set(_pool_var(fb), (i))) continue; \ + eltp = (pool) + (i); \ + do { \ + BODY; \ + } while (0); \ + } \ + } while (0) + +/** + * @brief Iterate over elements in a pool. + * + * @param[in] pool The pool data structure to iterate over. + * @param[in,out] eltp A pointer to the element type that will be used for + * iteration. + * @param[in] BODY Block to execute during iteration. + * + * Iteration will execute BODY with eltp corresponding successively to all + * elements found in the pool. It is implemented using the more generic + * enumeration function. + */ +#define pool_foreach(pool, eltp, BODY) \ + do { \ + unsigned _pool_var(i); \ + pool_enumerate((pool), _pool_var(i), (eltp), BODY); \ + } while (0) + +#define pool_get_alloc_size(pool) pool_hdr(pool)->alloc_size + +#ifdef WITH_TESTS +#define pool_get_free_indices(pool) pool_hdr(pool)->free_indices +#define pool_get_free_bitmap(pool) pool_hdr(pool)->free_bitmap +#endif /* WITH_TESTS */ + +#endif /* UTIL_POOL_H */ diff --git a/hicn-light/src/hicn/base/ring.c b/hicn-light/src/hicn/base/ring.c new file mode 100644 index 000000000..29727886a --- /dev/null +++ b/hicn-light/src/hicn/base/ring.c @@ -0,0 +1,45 @@ + +/* + * Copyright (c) 2021 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 ring.c + * \brief Implementation of ring buffer. + */ + +#include <stdlib.h> + +#include "ring.h" + +void _ring_init(void** ring_ptr, size_t elt_size, size_t max_size) { + assert(ring_ptr); + assert(elt_size > 0); + // we use a static array, not a vector (for now) + assert(max_size != 0); + + ring_hdr_t* rh = malloc(RING_HDRLEN + max_size * elt_size); + + rh->roff = 0; + rh->woff = 0; + rh->size = 0; + rh->max_size = max_size; + + *ring_ptr = (uint8_t*)rh + RING_HDRLEN; +} + +void _ring_free(void** ring_ptr) { + free(ring_hdr(*ring_ptr)); + *ring_ptr = NULL; +} diff --git a/hicn-light/src/hicn/base/ring.h b/hicn-light/src/hicn/base/ring.h new file mode 100644 index 000000000..492a8fdac --- /dev/null +++ b/hicn-light/src/hicn/base/ring.h @@ -0,0 +1,201 @@ +/* + * Copyright (c) 2021 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 ring.h + * \brief Fixed-size pool allocator. + */ + +#ifndef UTIL_RING_H +#define UTIL_RING_H + +#include <assert.h> +#include <stdint.h> +#include <string.h> +#include <sys/param.h> // MIN +#include <sys/types.h> + +#include <stdio.h> // XXX debug + +#include "common.h" + +/******************************************************************************/ +/* Ring header */ + +typedef struct { + size_t roff; + size_t woff; + size_t size; + size_t max_size; +} ring_hdr_t; + +/* Make sure elements following the header are aligned */ +#define RING_HDRLEN SIZEOF_ALIGNED(ring_hdr_t) + +/* This header actually prepends the actual content of the vector */ +#define ring_hdr(ring) ((ring_hdr_t *)((uint8_t *)ring - RING_HDRLEN)) + +/******************************************************************************/ +/* Helpers */ + +/** Local variable naming macro. */ +#define _ring_var(v) _ring_##v + +/** + * @brief Allocate and initialize a ring data structure (helper function). + * + * @param[in,out] ring_ptr Ring buffer to allocate and initialize. + * @param[in] elt_size Size of a ring element. + * @param[in] max_size Maximum vector size (O = unlimited). + */ +void _ring_init(void **ring_ptr, size_t elt_size, size_t max_size); + +/** + * @brief Free a ring data structure. + * + * @param ring_ptr[in] Pointer to the ring data structure to free. + */ +void _ring_free(void **ring_ptr); + +static inline int _ring_add(void **ring_ptr, size_t elt_size, void *eltp) { + assert(*ring_ptr); + ring_hdr_t *rh = ring_hdr(*ring_ptr); + + /* We always write ! */ + memcpy((uint8_t *)*ring_ptr + rh->woff * elt_size, eltp, elt_size); + rh->woff++; + if (rh->woff == rh->max_size) rh->woff = 0; + if (rh->size < rh->max_size) { + rh->size++; + } else { + /* One packet was dropped */ + rh->roff++; + if (rh->roff == rh->max_size) rh->roff = 0; + } + return 0; +} + +static inline unsigned _ring_get_fullness(void **ring_ptr) { + assert(*ring_ptr); + ring_hdr_t *rh = ring_hdr(*ring_ptr); + return rh->size * 100 / rh->max_size; +} + +static inline unsigned _ring_is_full(void **ring_ptr) { + assert(*ring_ptr); + ring_hdr_t *rh = ring_hdr(*ring_ptr); + return rh->size == rh->max_size; +} + +static inline size_t _ring_get_size(void **ring_ptr) { + assert(*ring_ptr); + ring_hdr_t *rh = ring_hdr(*ring_ptr); + return rh->size; +} + +static inline int _ring_advance(void **ring_ptr, unsigned n) { + assert(*ring_ptr); + ring_hdr_t *rh = ring_hdr(*ring_ptr); + assert(n <= rh->size); + + rh->roff += n; + rh->size -= n; + while (rh->roff >= rh->max_size) rh->roff -= rh->max_size; + return 0; +} + +static inline int _ring_get(void **ring_ptr, size_t elt_size, unsigned i, + void *eltp) { + assert(*ring_ptr); + ring_hdr_t *rh = ring_hdr(*ring_ptr); + assert(i <= rh->size); + size_t pos = rh->roff + i; + if (pos >= rh->max_size) pos -= rh->max_size; + memcpy(eltp, (uint8_t *)*ring_ptr + pos * elt_size, elt_size); + return 0; +} + +/******************************************************************************/ +/* Public API */ + +/** + * @brief Allocate and initialize a ring data structure. + * + * @param[in,out] ring Ring to allocate and initialize. + * @param[in] max_size Maximum ring size (nonzero). + * + * NOTE: + * - Allocated memory is set to 0 (used by bitmap) + */ + +#define ring_init(RING, MAX_SIZE) \ + _ring_init((void **)&(RING), sizeof((RING)[0]), (MAX_SIZE)) + +#define ring_free(RING) _ring_free((void **)&(RING)) + +#define ring_get_fullness(RING) _ring_get_fullness((void **)&(RING)) + +#define ring_is_full(RING) _ring_is_full((void **)&(RING)) + +#define ring_get_size(RING) _ring_get_size((void **)&(RING)) + +#define ring_add(RING, ELT) _ring_add((void **)&(RING), sizeof(RING[0]), ELT) + +#define ring_add_value(RING, VALUE) \ + do { \ + typeof(VALUE) _ring_var(v) = VALUE; \ + _ring_add((void **)&(RING), sizeof(RING[0]), &_ring_var(v)); \ + } while (0) + +#define ring_advance(RING, N) _ring_advance((void **)&(RING), (N)) + +#define ring_get(RING, I, ELTP) \ + _ring_get((void **)&RING, sizeof(RING[0]), (I), (ELTP)) + +/** + * @brief Helper function used by ring_foreach(). + */ +#define ring_enumerate_n(RING, I, ELTP, COUNT, BODY) \ + ({ \ + for ((I) = 0; (I) < MIN(ring_get_size(RING), (COUNT)); (I)++) { \ + ring_get((RING), (I), (ELTP)); \ + { BODY; } \ + } \ + }) + +#define ring_enumerate(ring, i, eltp, BODY) \ + ring_enumerate_n((ring), (i), (eltp), 1, (BODY)) + +/** + * @brief Iterate over elements in a ring. + * + * @param[in] pool The ring data structure to iterate over + * @param[in, out] eltp A pointer to the element that will be used for + * iteration + * @param[in] BODY Block to execute during iteration + * + * @note Iteration will execute BODY with eltp corresponding successively to all + * elements found in the ring. It is implemented using the more generic + * enumeration function. + */ +#define ring_foreach_n(ring, eltp, count, BODY) \ + ({ \ + unsigned _ring_var(i); \ + ring_enumerate_n((ring), _ring_var(i), (eltp), (count), BODY); \ + }) + +#define ring_foreach(ring, eltp, BODY) ring_foreach_n((ring), (eltp), 1, (BODY)) + +#endif /* UTIL_RING_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..36d808932 --- /dev/null +++ b/hicn-light/src/hicn/base/vector.c @@ -0,0 +1,85 @@ +/* + * Copyright (c) 2021 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 <assert.h> +#include <stddef.h> // size_t +#include <stdlib.h> // calloc +#include <stdio.h> + +#include "vector.h" + +#define DEFAULT_VECTOR_SIZE 64 + +void _vector_init(void** vector_ptr, size_t elt_size, size_t init_size, + size_t max_size) { + assert(vector_ptr); + assert(max_size == 0 || init_size < max_size); + + if (init_size == 0) init_size = DEFAULT_VECTOR_SIZE; + + *vector_ptr = NULL; + _vector_resize(vector_ptr, elt_size, init_size); + + vector_hdr_t* vh = vector_hdr(*vector_ptr); + vh->cur_size = 0; + vh->max_size = max_size; +} + +void _vector_free(void** vector_ptr) { + free(vector_hdr(*vector_ptr)); + *vector_ptr = NULL; +} + +int _vector_resize(void** vector_ptr, size_t elt_size, off_t pos) { + vector_hdr_t* vh; + + size_t old_size; + + if (*vector_ptr) { + vh = vector_hdr(*vector_ptr); + old_size = vh->alloc_size; + } else { + vh = NULL; + old_size = 0; + } + + /* Round the allocated size to the next power of 2 of the requested position + */ + size_t new_size = next_pow2(pos); + + /* Don't grow the vector back */ + if (new_size < old_size) return 0; + + /* Don't exceed maximum size (for init, check is done beforehand) */ + if (vh && vh->max_size && new_size > vh->max_size) return -1; + + vh = realloc(vh, VECTOR_HDRLEN + new_size * elt_size); + if (!vh) return -1; + vh->alloc_size = new_size; + + /* Zero out the newly allocated memory (except headers) */ + memset((uint8_t*)vh + VECTOR_HDRLEN + old_size * elt_size, 0, + (new_size - old_size) * elt_size); + + /* Reassign vector pointer */ + *vector_ptr = (uint8_t*)vh + VECTOR_HDRLEN; + + return 0; +} diff --git a/hicn-light/src/hicn/base/vector.h b/hicn-light/src/hicn/base/vector.h new file mode 100644 index 000000000..0b7a74aeb --- /dev/null +++ b/hicn-light/src/hicn/base/vector.h @@ -0,0 +1,327 @@ +/* + * Copyright (c) 2021 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 + * + * A vector is a resizeable area of contiguous memory that contains elements of + * fixed size. It is mostly useful to serve as the basis for more advanced data + * structures such as memory pools. + * + * The internal API manipulates a pointer to the vector so that it can be + * seamlessly resized, and a more convenient user interface is provided through + * macros. + * + * A vector starts at index 0, and is typed according to the elements it + * contains. For that matter, the data structure header precedes the returned + * pointer which corresponds to the storage area. + * + * A vector is by default used as a stack where an end marker is maintained and + * new elements are pushed right after this end marker (an indication of + * the size of the vector) after ensuring the vector is sufficiently large. + * + * A user should not store any pointer to vector elements as this might change + * during reallocations, but should use indices instead. + * + * NOTE: a maximum size is currently not implemented. + * + * It is freely inspired (and simplified) from the VPP infra infrastructure + * library. + */ + +#ifndef UTIL_VECTOR_H +#define UTIL_VECTOR_H + +#include <stdint.h> +#include <stddef.h> +#include <stdint.h> +#include <string.h> +#include <sys/types.h> + +#include "common.h" + +/******************************************************************************/ +/* Vector header */ + +typedef struct { + size_t cur_size; /** Vector current size (corresponding to the highest used + element). */ + size_t alloc_size; /** The currently allocated size. */ + size_t max_size; /** The maximum allowed size (0 = no limit) */ +} vector_hdr_t; + +/* 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)) + +/******************************************************************************/ +/* Helpers */ + +/** Local variable naming macro. */ +#define _vector_var(v) _vector_##v + +/** + * @brief Allocate and initialize a vector data structure (helper function). + * + * @param[in,out] vector_ptr Vector to allocate and initialize. + * @param[in] elt_size Size of a vector element. + * @param[in] init_size Initial vector size. + * @param[in] max_size Maximum vector size (O = unlimited). + */ +void _vector_init(void **vector_ptr, size_t elt_size, size_t init_size, + size_t max_size); + +/** + * @brief Free a vector data structure. + * + * @param vector_ptr[in] Pointer to the vector data structure to free. + */ +void _vector_free(void **vector_ptr); + +/** + * @brief Resize a vector data structure. + * + * @param[in] vector_ptr A pointer to the vector data structure to resize. + * @param[in] elt_size The size of a vector element. + * @param[in] pos The position at which the vector should be able to hold an + * element. + * + * @return int Flag indicating whether the vector has been correctly resized. + * + * NOTE: + * - The resize operation does not specify the final size of the vector but + * instead ensure that it is large enough to hold an element at the specified + * position. This allows the caller not to care about doing successive calls to + * this API while the vector is growing in size. + */ +int _vector_resize(void **vector_ptr, size_t elt_size, off_t pos); + +/** + * @brief Ensures a vector is sufficiently large to hold an element at the + * given position. + * + * @param[in] vector_ptr A pointer to the vector data structure to resize. + * @param[in] elt_size The size of a vector element. + * @param[in] pos The position to validate. + * + * @return int Flag indicating whether the vector is available. + * + * NOTE: + * - This function should always be called before writing to a vector element + * to eventually make room for it (the vector will eventually be resized). + * - This function can fail if the vector is full and for any reason it cannot + * be resized. + */ +static inline int _vector_ensure_pos(void **vector_ptr, size_t elt_size, + off_t pos) { + vector_hdr_t *vh = vector_hdr(*vector_ptr); + if (pos >= (off_t)vh->alloc_size) + return _vector_resize(vector_ptr, elt_size, pos + 1); + return 0; +} + +/** + * @brief Push an element at the end of a vector. + * + * @param[in] vector_ptr A pointer to the vector data structure to resize. + * @param[in] elt_size The size of a vector element. + * @param[in] elt The element to insert. + * + * NOTE: + * - This function ensures there is sufficient room for inserting the element, + * and evenutually resizes the vector to make room for it (if allowed by + * maximum size). + */ +static inline int _vector_push(void **vector_ptr, size_t elt_size, void *elt) { + vector_hdr_t *vh = vector_hdr(*vector_ptr); + if (_vector_ensure_pos(vector_ptr, elt_size, vh->cur_size) < 0) return -1; + + /* Always get header after a potential resize */ + vh = vector_hdr(*vector_ptr); + memcpy((uint8_t *)*vector_ptr + vh->cur_size * elt_size, elt, elt_size); + vh = vector_hdr(*vector_ptr); + vh->cur_size++; + return 0; +} + +/** + * @brief Remove all the occurrencies of an element from the vector. + * The order of the elements is NOT maintained. + * + * @param[in, out] vector The vector data structure to resize + * @param[in] elt_size The size of a vector element + * @param[in] elt The element to remove + * @return int Number of elemets (equal to 'elt') removed from the vector + */ +static inline int _vector_remove_unordered(void *vector, size_t elt_size, + void *elt) { + size_t num_removed = 0; + vector_hdr_t *vh = vector_hdr(vector); + for (size_t i = 0; i < vector_hdr(vector)->cur_size; i++) { + if (memcmp((uint8_t *)vector + i * elt_size, elt, elt_size) == 0) { + vh->cur_size--; + memcpy((uint8_t *)vector + i * elt_size, + (uint8_t *)vector + vh->cur_size * elt_size, elt_size); + num_removed++; + } + } + return num_removed; +} + +/******************************************************************************/ +/* Public API */ + +/** + * @brief Allocate and initialize a vector data structure. + * + * @param[in,out] vector Vector to allocate and initialize. + * @param[in] init_size Initial vector size. + * @param[in] max_size Maximum vector size (nonzero). + * + * NOTE: + * - Allocated memory is set to 0 (used by bitmap) + */ + +#define vector_init(vector, init_size, max_size) \ + _vector_init((void **)&vector, sizeof(vector[0]), init_size, max_size) + +/** + * @brief Free a vector data structure. + * + * @param[in] vector The vector data structure to free. + */ +#define vector_free(vector) _vector_free((void **)&vector) + +/** + * @brief Resize a vector data structure. + * + * @param[in] vector The vector data structure to resize. + * @param[in] pos The position at which the vector should be able to hold an + * element. + * + * @return int Flag indicating whether the vector has been correctly resized. + * + * NOTE: + * - The resize operation does not specify the final size of the vector but + * instead ensure that it is large enough to hold an element at the specified + * position. This allows the caller not to care about doing successive calls to + * this API while the vector is growing in size. + * - If the new size is smaller than the current size, the content of the + * vector will be truncated. + * - Newly allocated memory is set to 0 (used by bitmap) + */ +#define vector_resize(vector) \ + _vector_resize((void **)&(vector), sizeof((vector)[0]), 0) + +/** + * @brief Ensures a vector is sufficiently large to hold an element at the + * given position. + * + * @param[in] vector The vector for which to validate the position. + * @param[in] pos The position to validate. + * + * NOTE: + * - This function should always be called before writing to a vector element + * to eventually make room for it (the vector will eventually be resized). + */ +#define vector_ensure_pos(vector, pos) \ + _vector_ensure_pos((void **)&(vector), sizeof((vector)[0]), pos); + +/** + * @brief Push an element at the end of a vector. + * + * @param[in] vector The vector in which to insert the element. + * @param[in] elt The element to insert. + * + * NOTE: + * - This function ensures there is sufficient room for inserting the element, + * and evenutually resizes the vector to make room for it (if allowed by + * maximum size). + */ +#define vector_push(vector, elt) \ + ({ \ + typeof(elt) x = elt; \ + _vector_push((void **)&(vector), sizeof((vector)[0]), (void *)(&x)); \ + }) + +/** + * @brief Remove all the occurrencies of an element from the vector. + * The order of the elements is NOT maintained. + * + * @param[in, out] vector The vector data structure to resize + * @param[in] elt The element to remove + * @return int Number of elemets (equal to 'elt') removed from the vector + */ +#define vector_remove_unordered(vector, elt) \ + ({ \ + typeof(elt) x = elt; \ + _vector_remove_unordered((void *)(vector), sizeof((vector)[0]), \ + (void *)(&x)); \ + }) + +/** + * @brief Returns the length of a vector. + * + * @param[in] vector The vector from which to get the size. + * + * @see vector_ensure_pos + * + * NOTE: + * - The size of the vector corresponds to the highest accessed index (for + * example as specified in the resize operation) and not the currently + * allocated size which will typically be bigger to amortize allocations. + * - A user should always call vector_ensure_pos to ensure the vector is + * sufficiently large to hold an element at the specified position. + */ +#define vector_len(vector) vector_hdr(vector)->cur_size + +/** + * @brief Returns the allocated size of a vector. + */ +#define vector_get_alloc_size(vector) vector_hdr(vector)->alloc_size + +/** + * @brief Iterate over elements in a vector. + * + * @param[in] pool The vector data structure to iterate over + * @param[in, out] eltp A pointer to the element that will be used for + * iteration + * @param[in] BODY Block to execute during iteration + * + * @note Iteration will execute BODY with eltp corresponding successively to all + * elements found in the vector. It is implemented using the more generic + * enumeration function. + */ +#define vector_foreach(vector, eltp, BODY) \ + ({ \ + unsigned _vector_var(i); \ + vector_enumerate((vector), _vector_var(i), (eltp), BODY); \ + }) + +/** + * @brief Helper function used by vector_foreach(). + */ +#define vector_enumerate(vector, i, eltp, BODY) \ + ({ \ + for ((i) = 0; (i) < vector_len(vector); (i)++) { \ + eltp = (vector) + (i); \ + { BODY; } \ + } \ + }) + +#endif /* UTIL_VECTOR_H */ |