diff options
| author |   Luca Muscariello <lumuscar@cisco.com> | 2022-06-09 21:34:09 +0200 |
|---|---|---|
| committer |   Luca Muscariello <muscariello@ieee.org> | 2022-06-30 10:47:50 +0200 |
| commit | 6b94663b2455e212009a544ae23bb6a8c55407f8 (patch) | |
| tree | 0af780ce5eeb1009fd24b8af8af08e8368eda3bd /hicn-light/src | |
| parent | a1ac96f497719b897793ac14b287cb8d840651c1 (diff) | |
refactor(lib, hicn-light, vpp, hiperf): HICN-723
- move infra data structure into the shared lib
- new packet cache using double hashing and lookup on prefix suffix
- testing updates
- authenticated requests using interest manifests
Co-authored-by: Mauro Sardara <msardara@cisco.com>
Co-authored-by: Jordan Augé <jordan.auge+fdio@cisco.com>
Co-authored-by: Michele Papalini <micpapal@cisco.com>
Co-authored-by: Olivier Roques <oroques+fdio@cisco.com>
Co-authored-by: Enrico Loparco <eloparco@cisco.com>
Change-Id: Iaddebfe6aa5279ea8553433b0f519578f6b9ccd9
Signed-off-by: Luca Muscariello <muscariello@ieee.org>
Diffstat (limited to 'hicn-light/src')
63 files changed, 1816 insertions, 3052 deletions
diff --git a/hicn-light/src/hicn/base/CMakeLists.txt b/hicn-light/src/hicn/base/CMakeLists.txt index 1180ed05b..2541ed830 100644 --- a/hicn-light/src/hicn/base/CMakeLists.txt +++ b/hicn-light/src/hicn/base/CMakeLists.txt @@ -12,21 +12,11 @@ # 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) diff --git a/hicn-light/src/hicn/base/bitmap.h b/hicn-light/src/hicn/base/bitmap.h deleted file mode 100644 index 060fd5be0..000000000 --- a/hicn-light/src/hicn/base/bitmap.h +++ /dev/null @@ -1,191 +0,0 @@ -/* - * 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_ptr, off_t i) { - if (bitmap_ensure_pos(bitmap_ptr, i) < 0) return -1; - - bitmap_t* bitmap = *bitmap_ptr; - 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 deleted file mode 100644 index 9f7e3beec..000000000 --- a/hicn-light/src/hicn/base/common.h +++ /dev/null @@ -1,62 +0,0 @@ -/* - * 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 deleted file mode 100644 index 3c54feb29..000000000 --- a/hicn-light/src/hicn/base/hash.h +++ /dev/null @@ -1,349 +0,0 @@ -/* - * 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 deleted file mode 100644 index 4c62b0260..000000000 --- a/hicn-light/src/hicn/base/khash.h +++ /dev/null @@ -1,748 +0,0 @@ -/* 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/pool.c b/hicn-light/src/hicn/base/pool.c deleted file mode 100644 index e5fb7d6ac..000000000 --- a/hicn-light/src/hicn/base/pool.c +++ /dev/null @@ -1,158 +0,0 @@ -/* - * 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 */ - bitmap_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 deleted file mode 100644 index b6573195c..000000000 --- a/hicn-light/src/hicn/base/pool.h +++ /dev/null @@ -1,254 +0,0 @@ -/* - * 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 deleted file mode 100644 index 29727886a..000000000 --- a/hicn-light/src/hicn/base/ring.c +++ /dev/null @@ -1,45 +0,0 @@ - -/* - * 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 deleted file mode 100644 index 492a8fdac..000000000 --- a/hicn-light/src/hicn/base/ring.h +++ /dev/null @@ -1,201 +0,0 @@ -/* - * 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 deleted file mode 100644 index 36d808932..000000000 --- a/hicn-light/src/hicn/base/vector.c +++ /dev/null @@ -1,85 +0,0 @@ -/* - * 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 deleted file mode 100644 index 0b7a74aeb..000000000 --- a/hicn-light/src/hicn/base/vector.h +++ /dev/null @@ -1,327 +0,0 @@ -/* - * 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 */ diff --git a/hicn-light/src/hicn/cli/hicnc.c b/hicn-light/src/hicn/cli/hicnc.c index d14093b6b..3074016c5 100644 --- a/hicn-light/src/hicn/cli/hicnc.c +++ b/hicn-light/src/hicn/cli/hicnc.c @@ -25,6 +25,7 @@ #include "../config/parse.h" #include <hicn/util/log.h> #include <hicn/util/sstrncpy.h> +#include <hicn/ctrl/hicn-light-ng.h> #define PORT 9695 @@ -359,6 +360,70 @@ int main(int argc, char *const *argv) { rc = hc_subscription_delete(s, &command.object.subscription); break; + case OBJECT_STATS: + switch (command.action) { + case ACTION_GET: + rc = hc_stats_get(s, &data); + if (rc < 0) break; + + hc_stats_snprintf(buf, MAX_LEN, (hicn_light_stats_t *)data->buffer); + INFO("\n%s", buf); + break; + + case ACTION_LIST: + rc = hc_stats_list(s, &data); + if (rc < 0) break; + + cmd_stats_list_item_t *conn_stats = + (cmd_stats_list_item_t *)data->buffer; + cmd_stats_list_item_t *end = + (cmd_stats_list_item_t *)(data->buffer + + data->size * data->out_element_size); + while (conn_stats < end) { + INFO("Connection #%d:", conn_stats->id); + INFO("\tinterests received: %d pkts (%d bytes)", + conn_stats->stats.interests.rx_pkts, + conn_stats->stats.interests.rx_bytes); + INFO("\tinterests transmitted: %d pkts (%d bytes)", + conn_stats->stats.interests.tx_pkts, + conn_stats->stats.interests.tx_bytes); + INFO("\tdata received: %d pkts (%d bytes)", + conn_stats->stats.data.rx_pkts, + conn_stats->stats.data.rx_bytes); + INFO("\tdata transmitted: %d pkts (%d bytes)", + conn_stats->stats.data.tx_pkts, + conn_stats->stats.data.tx_bytes); + + conn_stats++; + } + break; + + default: + break; + } + break; + +#ifdef TEST_FACE_CREATION + case OBJECT_FACE: + switch (command.action) { + case ACTION_CREATE: { + hc_face_t face = {0}; + face.face.type = FACE_TYPE_UDP; + face.face.family = AF_INET; + face.face.local_addr = IPV4_LOOPBACK; + face.face.remote_addr = IPV4_LOOPBACK; + face.face.local_port = 9696; + face.face.remote_port = 9696; + + rc = hc_face_create(s, &face); + break; + } + default: + break; + } + break; +#endif + default: break; } diff --git a/hicn-light/src/hicn/cli/hicnd.c b/hicn-light/src/hicn/cli/hicnd.c index e73517e4c..fa1b1c024 100644 --- a/hicn-light/src/hicn/cli/hicnd.c +++ b/hicn-light/src/hicn/cli/hicnd.c @@ -26,9 +26,9 @@ #include <sys/stat.h> #include <hicn/util/log.h> +#include <hicn/base/loop.h> #include "logo.h" -#include "../base/loop.h" #include "../core/forwarder.h" #include "../config/configuration.h" // XXX needed ? #include "../config/configuration_file.h" diff --git a/hicn-light/src/hicn/config/CMakeLists.txt b/hicn-light/src/hicn/config/CMakeLists.txt index 00ee24077..90d0a2229 100644 --- a/hicn-light/src/hicn/config/CMakeLists.txt +++ b/hicn-light/src/hicn/config/CMakeLists.txt @@ -29,6 +29,7 @@ list(APPEND SOURCE_FILES ${CMAKE_CURRENT_SOURCE_DIR}/command_policy.c ${CMAKE_CURRENT_SOURCE_DIR}/command_punting.c ${CMAKE_CURRENT_SOURCE_DIR}/command_route.c + ${CMAKE_CURRENT_SOURCE_DIR}/command_stats.c ${CMAKE_CURRENT_SOURCE_DIR}/command_strategy.c ${CMAKE_CURRENT_SOURCE_DIR}/command_subscription.c ${CMAKE_CURRENT_SOURCE_DIR}/command.c diff --git a/hicn-light/src/hicn/config/command_stats.c b/hicn-light/src/hicn/config/command_stats.c new file mode 100644 index 000000000..70f74fd8c --- /dev/null +++ b/hicn-light/src/hicn/config/command_stats.c @@ -0,0 +1,18 @@ +#include <math.h> +#include "command.h" + +/* Commands */ + +static const command_parser_t command_stats_get = { + .action = ACTION_GET, + .object = OBJECT_STATS, + .nparams = 0, +}; +COMMAND_REGISTER(command_stats_get); + +static const command_parser_t command_stats_list = { + .action = ACTION_LIST, + .object = OBJECT_STATS, + .nparams = 0, +}; +COMMAND_REGISTER(command_stats_list);
\ No newline at end of file diff --git a/hicn-light/src/hicn/config/commands.c b/hicn-light/src/hicn/config/commands.c index e99e0b8f5..be00575d7 100644 --- a/hicn-light/src/hicn/config/commands.c +++ b/hicn-light/src/hicn/config/commands.c @@ -90,7 +90,8 @@ static inline unsigned _symbolic_to_conn_id(forwarder_t *forwarder, } } else { // case for symbolic as input: check if symbolic name can be resolved - conn_id = connection_table_get_id_by_name(table, symbolic_or_connid); + conn_id = (unsigned int)connection_table_get_id_by_name(table, + symbolic_or_connid); if (connection_id_is_valid(conn_id)) { DEBUG("Resolved symbolic name '%s' to conn_id %u", symbolic_or_connid, conn_id); @@ -151,6 +152,7 @@ uint8_t *configuration_on_listener_add(forwarder_t *forwarder, uint8_t *packet, } address_t address; + memset(&address, 0, sizeof(address_t)); if (address_from_ip_port(&address, control->family, &control->address, control->port) < 0) { WARN( @@ -206,7 +208,8 @@ unsigned symbolic_to_listener_id(forwarder_t *forwarder, } } else { // case for symbolic as input: check if symbolic name can be resolved - listener_id = listener_table_get_id_by_name(table, symbolic_or_listener_id); + listener_id = (unsigned int)listener_table_get_id_by_name( + table, symbolic_or_listener_id); if (listener_id_is_valid(listener_id)) { DEBUG("Resolved symbolic name '%s' to conn_id %u", symbolic_or_listener_id, listener_id); @@ -262,7 +265,8 @@ uint8_t *configuration_on_listener_remove(forwarder_t *forwarder, address_pair_get_local(pair))) continue; - unsigned conn_id = connection_table_get_connection_id(table, connection); + unsigned conn_id = + (unsigned int)connection_table_get_connection_id(table, connection); /* Remove connection from the FIB */ forwarder_remove_connection_id_from_routes(forwarder, conn_id); @@ -335,8 +339,9 @@ uint8_t *configuration_on_listener_list(forwarder_t *forwarder, uint8_t *packet, uint8_t command_id = msg_received->header.command_id; uint32_t seq_num = msg_received->header.seq_num; - msg_listener_list_reply_t *msg; - msg_malloc_list(msg, command_id, n, seq_num) if (!msg) goto NACK; + msg_listener_list_reply_t *msg = NULL; + msg_malloc_list(msg, command_id, n, seq_num); + if (!msg) goto NACK; cmd_listener_list_item_t *payload = &msg->payload; listener_t *listener; @@ -376,14 +381,23 @@ uint8_t *configuration_on_connection_add(forwarder_t *forwarder, goto NACK; } - const char *symbolic_name = control->symbolic; - if (!face_type_is_defined(control->type)) goto NACK; connection_table_t *table = forwarder_get_connection_table(forwarder); - if (connection_table_get_by_name(table, symbolic_name)) { - ERROR("Connection symbolic name already exists"); - goto NACK; + char *symbolic_name = control->symbolic; + + // Generate connection name if not specified + if (symbolic_name[0] == '\0') { + int rc = connection_table_get_random_name(table, symbolic_name); + if (rc < 0) { + ERROR("Unable to generate new connection name"); + goto NACK; + } + } else { + if (connection_table_get_by_name(table, symbolic_name)) { + ERROR("Connection symbolic name already exists"); + goto NACK; + } } address_pair_t pair; @@ -561,6 +575,14 @@ static inline void fill_connections_command(forwarder_t *forwarder, } } +static inline void fill_connection_stats_command(connection_t *connection, + cmd_stats_list_item_t *cmd) { + assert(connection && cmd); + + cmd->id = connection->id; + cmd->stats = connection->stats; +} + uint8_t *configuration_on_connection_list(forwarder_t *forwarder, uint8_t *packet, unsigned ingress_id, size_t *reply_size) { @@ -576,8 +598,9 @@ uint8_t *configuration_on_connection_list(forwarder_t *forwarder, uint8_t command_id = msg_received->header.command_id; uint32_t seq_num = msg_received->header.seq_num; - msg_connection_list_reply_t *msg; - msg_malloc_list(msg, command_id, n, seq_num) if (!msg) goto NACK; + msg_connection_list_reply_t *msg = NULL; + msg_malloc_list(msg, command_id, n, seq_num); + if (!msg) goto NACK; cmd_connection_list_item_t *payload = &msg->payload; connection_t *connection; @@ -807,7 +830,7 @@ uint8_t *configuration_on_route_list(forwarder_t *forwarder, uint8_t *packet, n += nexthops_get_len(nexthops); }); - msg_route_list_reply_t *msg; + msg_route_list_reply_t *msg = NULL; msg_malloc_list(msg, command_id, n, seq_num); if (!msg) goto NACK; @@ -938,8 +961,9 @@ uint8_t *configuration_on_cache_list(forwarder_t *forwarder, uint8_t *packet, .payload = { .store_in_cs = forwarder_cs_get_store(forwarder), .serve_from_cs = forwarder_cs_get_serve(forwarder), - .cs_size = forwarder_cs_get_size(forwarder), - .num_stale_entries = forwarder_cs_get_num_stale_entries(forwarder)}}; + .cs_size = (unsigned int)forwarder_cs_get_size(forwarder), + .num_stale_entries = + (unsigned int)forwarder_cs_get_num_stale_entries(forwarder)}}; *reply_size = sizeof(*msg); return (uint8_t *)msg; @@ -1068,6 +1092,65 @@ NACK: return (uint8_t *)msg; } +/* Statistics */ + +uint8_t *configuration_on_stats_get(forwarder_t *forwarder, uint8_t *packet, + unsigned ingress_id, size_t *reply_size) { + assert(forwarder && packet); + INFO("CMD: stats get (ingress=%d)", ingress_id); + + msg_stats_get_t *msg_received = (msg_stats_get_t *)packet; + uint32_t seq_num = msg_received->header.seq_num; + + msg_stats_get_reply_t *msg = malloc(sizeof(*msg)); + *msg = (msg_stats_get_reply_t){ + .header = {.message_type = RESPONSE_LIGHT, + .length = 1, + .seq_num = seq_num}, + .payload = {.forwarder = forwarder_get_stats(forwarder), + .pkt_cache = + pkt_cache_get_stats(forwarder_get_pkt_cache(forwarder))} + + }; + + *reply_size = sizeof(*msg); + return (uint8_t *)msg; +} + +uint8_t *configuration_on_stats_list(forwarder_t *forwarder, uint8_t *packet, + unsigned ingress_id, size_t *reply_size) { + assert(forwarder && packet); + INFO("CMD: stats list (ingress=%d)", ingress_id); + + connection_table_t *table = forwarder_get_connection_table(forwarder); + // -1 since current connection (i.e. the one used to send + // the command) is not considered + size_t n = connection_table_len(table) - 1; + msg_stats_list_t *msg_received = (msg_stats_list_t *)packet; + uint8_t command_id = msg_received->header.command_id; + uint32_t seq_num = msg_received->header.seq_num; + + msg_stats_list_reply_t *msg = NULL; + msg_malloc_list(msg, command_id, n, seq_num); + if (!msg) goto NACK; + + cmd_stats_list_item_t *payload = &msg->payload; + connection_t *connection; + connection_table_foreach(table, connection, { + if (connection->id == ingress_id) continue; + fill_connection_stats_command(connection, payload); + payload++; + }); + + *reply_size = sizeof(msg->header) + n * sizeof(msg->payload); + return (uint8_t *)msg; + +NACK: + *reply_size = sizeof(msg_header_t); + make_nack(msg); + return (uint8_t *)msg; +} + /* WLDR */ uint8_t *configuration_on_wldr_set(forwarder_t *forwarder, uint8_t *packet, @@ -1365,7 +1448,7 @@ uint8_t *configuration_on_policy_list(forwarder_t *forwarder, uint8_t *packet, uint8_t command_id = msg_received->header.command_id; uint32_t seq_num = msg_received->header.seq_num; - msg_policy_list_reply_t *msg; + msg_policy_list_reply_t *msg = NULL; msg_malloc_list(msg, command_id, n, seq_num); if (!msg) goto NACK; diff --git a/hicn-light/src/hicn/config/commands.h b/hicn-light/src/hicn/config/commands.h index cedf4de01..3852a76ac 100644 --- a/hicn-light/src/hicn/config/commands.h +++ b/hicn-light/src/hicn/config/commands.h @@ -149,4 +149,7 @@ uint8_t *configuration_on_policy_remove(forwarder_t *forwarder, uint8_t *packet, uint8_t *configuration_on_policy_list(forwarder_t *forwarder, uint8_t *packet, unsigned ingress_id, size_t *reply_size); +uint8_t *configuration_on_stats_list(forwarder_t *forwarder, uint8_t *packet, + unsigned ingress_id, size_t *reply_size); + #endif // HICNLIGHT_COMMANDS_H diff --git a/hicn-light/src/hicn/config/configuration.h b/hicn-light/src/hicn/config/configuration.h index 9861b6c9f..93b4cf7c3 100644 --- a/hicn-light/src/hicn/config/configuration.h +++ b/hicn-light/src/hicn/config/configuration.h @@ -26,7 +26,7 @@ #ifndef HICNLIGHT_CONFIGURATION_H #define HICNLIGHT_CONFIGURATION_H -#include "../base/khash.h" +#include <hicn/util/khash.h> #include "../core/msgbuf.h" #include "../core/strategy.h" #include <hicn/ctrl/api.h> diff --git a/hicn-light/src/hicn/core/CMakeLists.txt b/hicn-light/src/hicn/core/CMakeLists.txt index 57ffb780f..9516a6a72 100644 --- a/hicn-light/src/hicn/core/CMakeLists.txt +++ b/hicn-light/src/hicn/core/CMakeLists.txt @@ -21,6 +21,7 @@ list(APPEND HEADER_FILES ${CMAKE_CURRENT_SOURCE_DIR}/fib_entry.h ${CMAKE_CURRENT_SOURCE_DIR}/fib.h ${CMAKE_CURRENT_SOURCE_DIR}/forwarder.h + ${CMAKE_CURRENT_SOURCE_DIR}/interest_manifest.h ${CMAKE_CURRENT_SOURCE_DIR}/listener.h ${CMAKE_CURRENT_SOURCE_DIR}/listener_table.h ${CMAKE_CURRENT_SOURCE_DIR}/listener_vft.h @@ -52,6 +53,7 @@ list(APPEND SOURCE_FILES ${CMAKE_CURRENT_SOURCE_DIR}/fib.c ${CMAKE_CURRENT_SOURCE_DIR}/fib_entry.c ${CMAKE_CURRENT_SOURCE_DIR}/forwarder.c + ${CMAKE_CURRENT_SOURCE_DIR}/interest_manifest.c ${CMAKE_CURRENT_SOURCE_DIR}/listener.c ${CMAKE_CURRENT_SOURCE_DIR}/listener_table.c ${CMAKE_CURRENT_SOURCE_DIR}/listener_vft.c diff --git a/hicn-light/src/hicn/core/address_pair.h b/hicn-light/src/hicn/core/address_pair.h index 72b92d6b5..2fd207d34 100644 --- a/hicn-light/src/hicn/core/address_pair.h +++ b/hicn-light/src/hicn/core/address_pair.h @@ -43,6 +43,12 @@ int address_pair_from_ip_port(address_pair_t* pair, int family, ip_address_t* local_addr, uint16_t local_port, ip_address_t* remote_addr, uint16_t remote_port); +static inline int address_pair_equals(const address_pair_t* pair1, + const address_pair_t* pair2) { + return address_equals(&pair1->local, &pair2->local) && + address_equals(&pair1->remote, &pair2->remote); +} + #define address_pair_get_local(pair) (&(pair)->local) #define address_pair_get_remote(pair) (&(pair)->remote) diff --git a/hicn-light/src/hicn/core/connection.c b/hicn-light/src/hicn/core/connection.c index c8cc1d0b9..2108d30af 100644 --- a/hicn-light/src/hicn/core/connection.c +++ b/hicn-light/src/hicn/core/connection.c @@ -28,8 +28,6 @@ #include "connection.h" #include "connection_vft.h" -#define _conn_var(x) _connection_##x - // This is called by configuration connection_t *connection_create(face_type_t type, const char *name, const address_pair_t *pair, @@ -212,18 +210,16 @@ int connection_send_packet(const connection_t *connection, connection, packet, size); } -bool _connection_send(const connection_t *connection, msgbuf_t *msgbuf, - bool queue) { +bool _connection_send(connection_t *connection, msgbuf_t *msgbuf, bool queue) { return connection_vft[get_protocol(connection->type)]->send(connection, msgbuf, queue); } -bool connection_flush(const connection_t *connection) { +bool connection_flush(connection_t *connection) { return connection_vft[get_protocol(connection->type)]->flush(connection); } -bool connection_send(const connection_t *connection, off_t msgbuf_id, - bool queue) { +bool connection_send(connection_t *connection, off_t msgbuf_id, bool queue) { assert(connection); assert(msgbuf_id_is_valid(msgbuf_id)); @@ -254,7 +250,7 @@ bool connection_send(const connection_t *connection, off_t msgbuf_id, * handled inside the MessageProcessor. This is specific to WLDR * retransmittions. This is done only for data packets */ -bool connection_resend(const connection_t *connection, msgbuf_t *msgbuf, +bool connection_resend(connection_t *connection, msgbuf_t *msgbuf, bool notification) { assert(connection); assert(msgbuf); diff --git a/hicn-light/src/hicn/core/connection.h b/hicn-light/src/hicn/core/connection.h index 05dc1d6e2..ac75428dd 100644 --- a/hicn-light/src/hicn/core/connection.h +++ b/hicn-light/src/hicn/core/connection.h @@ -84,6 +84,7 @@ typedef struct { */ struct wldr_s* wldr; + connection_stats_t stats; } connection_t; #if 1 @@ -209,10 +210,9 @@ int connection_finalize(connection_t* connection); int connection_send_packet(const connection_t* connection, const uint8_t* packet, size_t size); -bool connection_flush(const connection_t* connection); +bool connection_flush(connection_t* connection); -bool connection_send(const connection_t* connection, off_t msgbuf_id, - bool queue); +bool connection_send(connection_t* connection, off_t msgbuf_id, bool queue); size_t connection_process_buffer(connection_t* connection, const uint8_t* buffer, size_t size); diff --git a/hicn-light/src/hicn/core/connection_table.c b/hicn-light/src/hicn/core/connection_table.c index 09236ae8e..c723073a1 100644 --- a/hicn-light/src/hicn/core/connection_table.c +++ b/hicn-light/src/hicn/core/connection_table.c @@ -74,6 +74,54 @@ void connection_table_free(connection_table_t *table) { free(table); } +connection_t *connection_table_allocate(const connection_table_t *table, + const address_pair_t *pair, + const char *name) { + connection_t *conn = NULL; + pool_get(table->connections, conn); + if (!conn) return NULL; + + off_t id = conn - table->connections; + int rc; + + // Add in name hash table + khiter_t k = kh_put_ct_name(table->id_by_name, strdup(name), &rc); + assert(rc == KH_ADDED || rc == KH_RESET); + kh_value(table->id_by_name, k) = (unsigned int)id; + + // Add in pair hash table + address_pair_t *pair_copy = (address_pair_t *)malloc(sizeof(address_pair_t)); + memcpy(pair_copy, pair, sizeof(address_pair_t)); + + k = kh_put_ct_pair(table->id_by_pair, pair_copy, &rc); + assert(rc == KH_ADDED || rc == KH_RESET); + kh_value(table->id_by_pair, k) = (unsigned int)id; + + assert(kh_size(table->id_by_name) == kh_size(table->id_by_pair)); + return conn; +} + +void connection_table_deallocate(const connection_table_t *table, + const connection_t *conn) { + const char *name = connection_get_name(conn); + const address_pair_t *pair = connection_get_pair(conn); + + // Remove from name hash table + khiter_t k = kh_get_ct_name(table->id_by_name, name); + assert(k != kh_end(table->id_by_name)); + free((char *)kh_key(table->id_by_name, k)); + kh_del_ct_name(table->id_by_name, k); + + // Remove from pair hash table + k = kh_get_ct_pair(table->id_by_pair, pair); + assert(k != kh_end(table->id_by_pair)); + free((address_pair_t *)kh_key(table->id_by_pair, k)); + kh_del_ct_pair(table->id_by_pair, k); + + assert(kh_size(table->id_by_name) == kh_size(table->id_by_pair)); + pool_put(table->connections, conn); +} + connection_t *connection_table_get_by_pair(const connection_table_t *table, const address_pair_t *pair) { khiter_t k = kh_get_ct_pair(table->id_by_pair, pair); @@ -90,7 +138,7 @@ off_t connection_table_get_id_by_name(const connection_table_t *table, connection_t *connection_table_get_by_name(const connection_table_t *table, const char *name) { - unsigned conn_id = connection_table_get_id_by_name(table, name); + unsigned conn_id = (unsigned int)connection_table_get_id_by_name(table, name); if (!connection_id_is_valid(conn_id)) return NULL; return connection_table_at(table, conn_id); } @@ -141,22 +189,24 @@ connection_t *_connection_table_get_by_id(connection_table_t *table, off_t id) { return connection_table_get_by_id(table, id); } -#define RANDBYTE() (u8)(rand() & 0xFF) - -char *connection_table_get_random_name(const connection_table_t *table) { - char *connection_name = malloc(SYMBOLIC_NAME_LEN * sizeof(char)); - u8 rand_num; +static inline u16 RAND16() { return rand() & 0xFFFF; } - /* Generate a random connection name */ - while (1) { - rand_num = RANDBYTE(); - int rc = snprintf(connection_name, SYMBOLIC_NAME_LEN, "conn%u", rand_num); - _ASSERT(rc < SYMBOLIC_NAME_LEN); +int connection_table_get_random_name(const connection_table_t *table, + char *name) { + int i, n_attempts = 2 * USHRT_MAX; + for (i = 0; i < n_attempts; i++) { + int rc = snprintf(name, SYMBOLIC_NAME_LEN, "conn%u", RAND16()); + if (rc >= SYMBOLIC_NAME_LEN) continue; - // Return if connection name does not already exist - khiter_t k = kh_get_ct_name(table->id_by_name, connection_name); + // Check if generated connection name is a duplicate + khiter_t k = kh_get_ct_name(table->id_by_name, name); if (k == kh_end(table->id_by_name)) break; } - return connection_name; + if (i == n_attempts) { + ERROR("Unable to generate new unique connection name"); + return -1; + } + + return 0; }
\ No newline at end of file diff --git a/hicn-light/src/hicn/core/connection_table.h b/hicn-light/src/hicn/core/connection_table.h index 4c03aa642..7d4bad761 100644 --- a/hicn-light/src/hicn/core/connection_table.h +++ b/hicn-light/src/hicn/core/connection_table.h @@ -30,22 +30,18 @@ #ifndef HICNLIGHT_CONNECTION_TABLE_H #define HICNLIGHT_CONNECTION_TABLE_H +#include <hicn/util/khash.h> +#include <hicn/util/hash.h> #include "address_pair.h" #include "connection.h" -#include "../base/hash.h" -#include "../base/khash.h" -#include "../base/pool.h" - -#define _ct_var(x) _ct_var_##x +#include <hicn/util/pool.h> /* Hash functions for indices. */ #define address_pair_hash(pair) (hash_struct(pair)) -#define address_pair_hash_eq(a, b) \ - (address_pair_hash(b) == address_pair_hash(a)) /* Hash table types for indices. */ KHASH_INIT(ct_pair, const address_pair_t *, unsigned, 1, address_pair_hash, - address_pair_hash_eq); + address_pair_equals); KHASH_MAP_INIT_STR(ct_name, unsigned); typedef struct { @@ -72,34 +68,9 @@ typedef struct { * - You should always check that the returned connection is not NULL, which * would signal that the pool is exhausted and could not be extended. */ -static inline connection_t *connection_table_allocate( - const connection_table_t *table, const address_pair_t *pair, - const char *name) { - connection_t *conn; - pool_get(table->connections, conn); - - if (conn) { - off_t id = conn - table->connections; - int res; - khiter_t k; - - // Add in name hash table - k = kh_put_ct_name(table->id_by_name, strdup(name), &res); - kh_value(table->id_by_name, k) = id; - - // Add in pair hash table - address_pair_t *pair_copy = - (address_pair_t *)malloc(sizeof(address_pair_t)); - memcpy(pair_copy, pair, sizeof(address_pair_t)); - - k = kh_put_ct_pair(table->id_by_pair, pair_copy, &res); - assert(res != -1); - kh_value(table->id_by_pair, k) = id; - } - - return conn; -} - +connection_t *connection_table_allocate(const connection_table_t *table, + const address_pair_t *pair, + const char *name); /** * @brief Deallocate a connection and return it to the connection table pool. * @@ -110,26 +81,8 @@ static inline connection_t *connection_table_allocate( * - Upon returning a connection to the pool, all indices pointing to that * connection are also cleared. */ -static inline void connection_table_deallocate(const connection_table_t *table, - const connection_t *conn) { - const char *name = connection_get_name(conn); - const address_pair_t *pair = connection_get_pair(conn); - khiter_t k; - - // Remove from name hash table - k = kh_get_ct_name(table->id_by_name, name); - assert(k != kh_end(table->id_by_name)); - free((char *)kh_key(table->id_by_name, k)); - kh_del_ct_name(table->id_by_name, k); - - // Remove from pair hash table - k = kh_get_ct_pair(table->id_by_pair, pair); - assert(k != kh_end(table->id_by_pair)); - free((address_pair_t *)kh_key(table->id_by_pair, k)); - kh_del_ct_pair(table->id_by_pair, k); - - pool_put(table->connections, conn); -} +void connection_table_deallocate(const connection_table_t *table, + const connection_t *conn); /** * @brief Returns the length of the connection table, the number of active @@ -292,6 +245,7 @@ void connection_table_print_by_pair(const connection_table_t *table); void connection_table_print_by_name(const connection_table_t *table); -char *connection_table_get_random_name(const connection_table_t *table); +int connection_table_get_random_name(const connection_table_t *table, + char *name); #endif /* HICNLIGHT_CONNECTION_TABLE_H */ diff --git a/hicn-light/src/hicn/core/connection_vft.h b/hicn-light/src/hicn/core/connection_vft.h index e6290cdd4..1a6ecbb78 100644 --- a/hicn-light/src/hicn/core/connection_vft.h +++ b/hicn-light/src/hicn/core/connection_vft.h @@ -28,8 +28,8 @@ typedef struct { void (*finalize)(connection_t* connection); int (*get_socket)(const listener_t* listener, const address_t* local, const address_t* remote, const char* interface_name); - bool (*flush)(const connection_t* connection); - bool (*send)(const connection_t* connection, msgbuf_t* msgbuf, bool queue); + bool (*flush)(connection_t* connection); + bool (*send)(connection_t* connection, msgbuf_t* msgbuf, bool queue); int (*send_packet)(const connection_t* connection, const uint8_t* packet, size_t size); // void (*read_callback)(connection_t * connection, int fd, void * data); diff --git a/hicn-light/src/hicn/core/content_store.c b/hicn-light/src/hicn/core/content_store.c index edbdc5ac1..360e6d333 100644 --- a/hicn-light/src/hicn/core/content_store.c +++ b/hicn-light/src/hicn/core/content_store.c @@ -84,3 +84,5 @@ void cs_log(cs_t *cs) { cs->stats.lru.countUpdates, cs->stats.lru.countLruDeletions, cs->stats.lru.countLruEvictions); } + +cs_lru_stats_t cs_get_lru_stats(cs_t *cs) { return cs->stats.lru; } diff --git a/hicn-light/src/hicn/core/content_store.h b/hicn-light/src/hicn/core/content_store.h index d47d603be..ceaf05e6b 100644 --- a/hicn-light/src/hicn/core/content_store.h +++ b/hicn-light/src/hicn/core/content_store.h @@ -1,7 +1,7 @@ #ifndef HICNLIGHT_CS_H #define HICNLIGHT_CS_H -#include "../base/pool.h" +#include <hicn/util/pool.h> #include "../content_store/lru.h" #include "msgbuf_pool.h" @@ -103,4 +103,6 @@ void cs_miss(cs_t *cs); */ void cs_log(cs_t *cs); +cs_lru_stats_t cs_get_lru_stats(cs_t *cs); + #endif /* HICNLIGHT_CS_H */ diff --git a/hicn-light/src/hicn/core/fib_entry.c b/hicn-light/src/hicn/core/fib_entry.c index 616f12961..80d337884 100644 --- a/hicn-light/src/hicn/core/fib_entry.c +++ b/hicn-light/src/hicn/core/fib_entry.c @@ -378,7 +378,7 @@ nexthops_t *fib_entry_get_available_nexthops(fib_entry_t *entry, connection_table_foreach(table, connection, { if (connection_is_local(connection)) continue; new_nexthops->elts[nexthops_get_len(new_nexthops)] = - connection_table_get_connection_id(table, connection); + (unsigned int)connection_table_get_connection_id(table, connection); nexthops_inc(new_nexthops); }); diff --git a/hicn-light/src/hicn/core/forwarder.c b/hicn-light/src/hicn/core/forwarder.c index 37502f3ac..74be6431a 100644 --- a/hicn-light/src/hicn/core/forwarder.c +++ b/hicn-light/src/hicn/core/forwarder.c @@ -69,45 +69,9 @@ #endif /* WITH_POLICY_STATS */ #include <hicn/core/wldr.h> +#include <hicn/core/interest_manifest.h> #include <hicn/util/log.h> -typedef struct { - // Packets processed - uint32_t countReceived; // Interest and data only - uint32_t countInterestsReceived; - uint32_t countObjectsReceived; - - // Packets Dropped - uint32_t countDropped; - uint32_t countInterestsDropped; - uint32_t countObjectsDropped; - uint32_t countOtherDropped; - - // Forwarding - uint32_t countInterestForwarded; - uint32_t countObjectsForwarded; - - // Errors while forwarding - uint32_t countDroppedConnectionNotFound; - uint32_t countSendFailures; - uint32_t countDroppedNoRoute; - - // Interest processing - uint32_t countInterestsAggregated; - uint32_t countInterestsRetransmitted; - uint32_t countInterestsSatisfiedFromStore; - uint32_t countInterestsExpired; - uint32_t countDataExpired; - - // Data processing - uint32_t countDroppedNoReversePath; - - // TODO(eloparco): Currently not used - // uint32_t countDroppedNoHopLimit; - // uint32_t countDroppedZeroHopLimitFromRemote; - // uint32_t countDroppedZeroHopLimitToRemote; -} forwarder_stats_t; - struct forwarder_s { // uint16_t server_port; @@ -138,13 +102,12 @@ struct forwarder_s { * The message forwarder has to decide whether to queue incoming packets for * batching, or trigger the transmission on the connection */ - unsigned pending_conn[MAX_MSG]; - size_t num_pending_conn; - - // msgbuf_t msgbuf; /* Storage for msgbuf, which are currently processed 1 by - // 1 */ + unsigned *pending_conn; subscription_table_t *subscriptions; + + // Used to store the msgbufs that need to be released + off_t *acquired_msgbuf_ids; }; /** @@ -223,8 +186,12 @@ forwarder_t *forwarder_create(configuration_t *configuration) { #endif /* WITH_POLICY_STATS */ memset(&forwarder->stats, 0, sizeof(forwarder_stats_t)); + vector_init(forwarder->pending_conn, MAX_MSG, 0); + vector_init(forwarder->acquired_msgbuf_ids, MAX_MSG, 0); - forwarder->num_pending_conn = 0; + char *n_suffixes_per_split_str = getenv("N_SUFFIXES_PER_SPIT"); + if (n_suffixes_per_split_str) + N_SUFFIXES_PER_SPIT = atoi(n_suffixes_per_split_str); return forwarder; @@ -267,6 +234,8 @@ void forwarder_free(forwarder_t *forwarder) { listener_table_free(forwarder->listener_table); subscription_table_free(forwarder->subscriptions); configuration_free(forwarder->config); + vector_free(forwarder->pending_conn); + vector_free(forwarder->acquired_msgbuf_ids); free(forwarder); } @@ -295,6 +264,11 @@ listener_table_t *forwarder_get_listener_table(forwarder_t *forwarder) { return forwarder->listener_table; } +pkt_cache_t *forwarder_get_pkt_cache(const forwarder_t *forwarder) { + assert(forwarder); + return forwarder->pkt_cache; +} + void forwarder_cs_set_store(forwarder_t *forwarder, bool val) { assert(forwarder); forwarder->store_in_cs = val; @@ -393,7 +367,7 @@ static ssize_t forwarder_forward_via_connection(forwarder_t *forwarder, const msgbuf_pool_t *msgbuf_pool = forwarder_get_msgbuf_pool(forwarder); msgbuf_t *msgbuf = msgbuf_pool_at(msgbuf_pool, msgbuf_id); - const connection_t *conn = connection_table_get_by_id(table, conn_id); + connection_t *conn = connection_table_get_by_id(table, conn_id); if (!conn) { forwarder->stats.countDroppedConnectionNotFound++; @@ -429,12 +403,8 @@ static ssize_t forwarder_forward_via_connection(forwarder_t *forwarder, #endif /* ... and mark the connection as pending if this is not yet the case */ - unsigned i; - for (i = 0; i < forwarder->num_pending_conn; i++) { - if (forwarder->pending_conn[i] == conn_id) break; - } - if (i == forwarder->num_pending_conn) // Not found - forwarder->pending_conn[forwarder->num_pending_conn++] = conn_id; + if (!vector_contains(forwarder->pending_conn, conn_id)) + vector_push(forwarder->pending_conn, conn_id); if (!success) { forwarder->stats.countSendFailures++; @@ -457,7 +427,8 @@ static ssize_t forwarder_forward_via_connection(forwarder_t *forwarder, break; } - TRACE("forward msgbuf %p to interface %u", msgbuf, conn_id); + TRACE("forward msgbuf %p (size=%u) to interface %u", msgbuf, + msgbuf_get_len(msgbuf), conn_id); return msgbuf_get_len(msgbuf); } @@ -496,8 +467,7 @@ static unsigned forwarder_forward_to_nexthops(forwarder_t *forwarder, static bool forwarder_forward_via_fib(forwarder_t *forwarder, off_t msgbuf_id, pkt_cache_verdict_t verdict, pkt_cache_entry_t *entry) { - assert(forwarder); - assert(msgbuf_id_is_valid(msgbuf_id)); + assert(forwarder && entry && msgbuf_id_is_valid(msgbuf_id)); const msgbuf_pool_t *msgbuf_pool = forwarder_get_msgbuf_pool(forwarder); msgbuf_t *msgbuf = msgbuf_pool_at(msgbuf_pool, msgbuf_id); @@ -515,15 +485,8 @@ static bool forwarder_forward_via_fib(forwarder_t *forwarder, off_t msgbuf_id, return false; } - // if this is the first time that we sent this interest the pit entry would be - // NULL. in that case we add the interest to the pit - if (entry == NULL) { - entry = pkt_cache_add_to_pit(forwarder->pkt_cache, msgbuf); - } pit_entry_t *pit_entry = &entry->u.pit_entry; - if (!pit_entry) { - return false; - } + if (!pit_entry) return false; pit_entry_set_fib_entry(pit_entry, fib_entry); @@ -547,21 +510,19 @@ static bool forwarder_forward_via_fib(forwarder_t *forwarder, off_t msgbuf_id, #endif /* ! BYPASS_FIB */ -ssize_t _forwarder_forward_upon_interest(forwarder_t *forwarder, - msgbuf_pool_t *msgbuf_pool, - off_t data_msgbuf_id, - off_t interest_msgbuf_id, - pkt_cache_entry_t *entry, - pkt_cache_verdict_t verdict) { +int _forwarder_forward_upon_interest( + forwarder_t *forwarder, msgbuf_pool_t *msgbuf_pool, off_t data_msgbuf_id, + off_t interest_msgbuf_id, pkt_cache_entry_t *entry, + pkt_cache_verdict_t verdict, bool is_aggregated) { msgbuf_t *msgbuf = msgbuf_pool_at(msgbuf_pool, interest_msgbuf_id); + // - Aggregation can be perfomed, do not forward if (verdict == PKT_CACHE_VERDICT_AGGREGATE_INTEREST) { - // the packet shuold not be forwarder forwarder_drop(forwarder, interest_msgbuf_id); return msgbuf_get_len(msgbuf); } - // - Forward reply if a data packet matching the interest was found + // - Data packet matching the interest was found, forward reply if (verdict == PKT_CACHE_VERDICT_FORWARD_DATA) { assert(forwarder->serve_from_cs == true); @@ -569,19 +530,26 @@ ssize_t _forwarder_forward_upon_interest(forwarder_t *forwarder, msgbuf_t *data_msgbuf = msgbuf_pool_at(msgbuf_pool, data_msgbuf_id); msgbuf_reset_pathlabel(data_msgbuf); - forwarder_forward_via_connection(forwarder, data_msgbuf_id, msgbuf_get_connection_id(interest_msgbuf)); + return msgbuf_get_len(msgbuf); + } + + // - For aggregated interest, the interest forwarding is done in + // `_forwarder_forward_aggregated_interest()` + if (is_aggregated) return msgbuf_get_len(msgbuf); - // - Try to forward the interest - } else if (!forwarder_forward_via_fib(forwarder, interest_msgbuf_id, verdict, - entry)) { + // - Try to forward the interest + int rc = + forwarder_forward_via_fib(forwarder, interest_msgbuf_id, verdict, entry); + if (!rc) { + // - Not able to forward, drop the packet forwarder->stats.countDroppedNoRoute++; INFO("Message %lu did not match FIB, no route (count %u)", interest_msgbuf_id, forwarder->stats.countDroppedNoRoute); - // - Drop the packet (no forwarding) forwarder_drop(forwarder, interest_msgbuf_id); + return -1; } return msgbuf_get_len(msgbuf); @@ -590,19 +558,12 @@ ssize_t _forwarder_forward_upon_interest(forwarder_t *forwarder, static void _forwarder_update_interest_stats(forwarder_t *forwarder, pkt_cache_verdict_t verdict, msgbuf_t *msgbuf, - pkt_cache_entry_t *entry) { - long expiration = -1; - if (entry == NULL) - expiration = ticks_now() + msgbuf_get_interest_lifetime(msgbuf); - else if (entry->has_expire_ts) - expiration = entry->expire_ts; - + bool has_expire_ts, + uint64_t expire_ts) { + long expiration = has_expire_ts ? expire_ts : -1; switch (verdict) { case PKT_CACHE_VERDICT_FORWARD_INTEREST: - DEBUG( - "Message will be added to PIT (expiration=%ld), " - "if nexthops are available", - expiration); + DEBUG("Message added to PIT (expiration=%ld)", expiration); break; case PKT_CACHE_VERDICT_AGGREGATE_INTEREST: @@ -632,7 +593,7 @@ static void _forwarder_update_interest_stats(forwarder_t *forwarder, break; case PKT_CACHE_VERDICT_ERROR: - ERROR("Inivalid packet cache content"); + ERROR("Invalid packet cache content"); break; default: @@ -640,6 +601,234 @@ static void _forwarder_update_interest_stats(forwarder_t *forwarder, } } +static interest_manifest_header_t *_forwarder_get_interest_manifest( + msgbuf_t *msgbuf) { + uint8_t *packet = msgbuf_get_packet(msgbuf); + hicn_header_t *header = (hicn_header_t *)packet; + hicn_type_t type = hicn_header_to_type(header); + + hicn_payload_type_t payload_type; + int rc = hicn_ops_vft[type.l1]->get_payload_type(type, &header->protocol, + &payload_type); + _ASSERT(rc == HICN_LIB_ERROR_NONE); + if (payload_type != HPT_MANIFEST) return NULL; + + size_t header_length, payload_length; + rc = hicn_ops_vft[type.l1]->get_header_length(type, &header->protocol, + &header_length); + assert(rc == HICN_LIB_ERROR_NONE); + + rc = hicn_ops_vft[type.l1]->get_payload_length(type, &header->protocol, + &payload_length); + assert(rc == HICN_LIB_ERROR_NONE); + + u8 *payload = (u8 *)header + header_length; + interest_manifest_header_t *int_manifest_header = + (interest_manifest_header_t *)payload; + if (!interest_manifest_is_valid(int_manifest_header, payload_length)) + return NULL; + + return int_manifest_header; +} + +// Manifest is split using splitting strategy, then every +// sub-manifest is sent using the forwarding strategy defined for the prefix +int _forwarder_forward_aggregated_interest( + forwarder_t *forwarder, interest_manifest_header_t *int_manifest_header, + int n_suffixes_to_fwd, msgbuf_t *msgbuf, off_t msgbuf_id, + pkt_cache_entry_t **entries) { + assert(msgbuf_id_is_valid(msgbuf_id) && + msgbuf_get_type(msgbuf) == MSGBUF_TYPE_INTEREST); + + fib_entry_t *fib_entry = fib_match_message(forwarder->fib, msgbuf); + if (!fib_entry) return -1; + + int n_suffixes_per_split = N_SUFFIXES_PER_SPIT; + switch (disaggregation_strategy) { + case INT_MANIFEST_SPLIT_NONE: + n_suffixes_per_split = int_manifest_header->n_suffixes + 1; + + case INT_MANIFEST_SPLIT_MAX_N_SUFFIXES: { + // Generate sub-manifests: same as original manifest, + // but different suffix in the header and different bitmap + + int total_len = 0; + // Suffixes in manifest plus the one in the header + int total_suffixes = int_manifest_header->n_suffixes + 1; + + // Save copy of original bitmap to use as a reference + // to generate bitmaps for sub-manifests + u32 original_bitmap[BITMAP_SIZE] = {0}; + memcpy(&original_bitmap, int_manifest_header->request_bitmap, + BITMAP_SIZE * sizeof(u32)); + + int suffix_index = 0; // Position of suffix in initial manifest + while (suffix_index < total_suffixes) { + // If more than one sub-manifest, + // clone original interest manifest and update suffix + if (suffix_index > 0) { + msgbuf_t *clone; + off_t clone_id = + msgbuf_pool_clone(forwarder->msgbuf_pool, &clone, msgbuf_id); + msgbuf_pool_acquire(clone); + forwarder_acquired_msgbuf_ids_push(forwarder, clone_id); + + msgbuf_id = clone_id; + msgbuf = clone; + } + + u32 curr_bitmap[BITMAP_SIZE] = {0}; + int first_suffix_index_in_submanifest = suffix_index; + suffix_index = interest_manifest_update_bitmap( + original_bitmap, curr_bitmap, suffix_index, total_suffixes, + n_suffixes_per_split); + int first_suffix_index_in_next_submanifest = suffix_index; + + // Update manifest bitmap in current msgbuf + interest_manifest_header_t *manifest = + _forwarder_get_interest_manifest(msgbuf); + assert(manifest != NULL); + memcpy(manifest->request_bitmap, curr_bitmap, + BITMAP_SIZE * sizeof(u32)); + WITH_TRACE({ + bitmap_print(manifest->request_bitmap, BITMAP_SIZE); + printf("\n"); + }); + + // Update PIT entries for suffixes in current sub-manifest + nexthops_t *nexthops = + fib_entry_get_nexthops_from_strategy(fib_entry, msgbuf, false); + if (nexthops_get_curlen(nexthops) == 0) return -1; + + for (int i = first_suffix_index_in_submanifest; + i < first_suffix_index_in_next_submanifest; i++) { + if (!is_bit_set(manifest->request_bitmap, i)) continue; + + pit_entry_t *pit_entry = &(entries[i]->u.pit_entry); + if (!pit_entry) return -1; + + pit_entry_set_fib_entry(pit_entry, fib_entry); + unsigned nexthop; + nexthops_foreach(nexthops, nexthop, + { pit_entry_egress_add(pit_entry, nexthop); }); + } + + if (forwarder_forward_to_nexthops(forwarder, msgbuf_id, nexthops) <= + 0) { + ERROR("Message %p returned an empty next hop set", msgbuf); + continue; + } + + total_len += msgbuf_get_len(msgbuf); + } + + return total_len; + } + + default: + return -1; + } +} + +static ssize_t forwarder_process_single_interest(forwarder_t *forwarder, + msgbuf_pool_t *msgbuf_pool, + msgbuf_t *msgbuf, + off_t msgbuf_id) { + pkt_cache_verdict_t verdict = PKT_CACHE_VERDICT_ERROR; + off_t data_msgbuf_id = INVALID_MSGBUF_ID; + pkt_cache_entry_t *entry = NULL; + + // Update packet cache + pkt_cache_on_interest(forwarder->pkt_cache, msgbuf_pool, msgbuf_id, &verdict, + &data_msgbuf_id, &entry, msgbuf_get_name(msgbuf), + forwarder->serve_from_cs); + _forwarder_update_interest_stats(forwarder, verdict, msgbuf, + entry->has_expire_ts, entry->expire_ts); + + int rc = _forwarder_forward_upon_interest( + forwarder, msgbuf_pool, data_msgbuf_id, msgbuf_id, entry, verdict, false); + + // No route when trying to forward interest, remove from PIT + if (rc == -1) + pkt_cache_pit_remove_entry(forwarder->pkt_cache, entry, + msgbuf_get_name(msgbuf)); + + return msgbuf_get_len(msgbuf); +} + +static ssize_t forwarder_process_aggregated_interest( + forwarder_t *forwarder, interest_manifest_header_t *int_manifest_header, + msgbuf_pool_t *msgbuf_pool, msgbuf_t *msgbuf, off_t msgbuf_id) { + pkt_cache_verdict_t verdict = PKT_CACHE_VERDICT_ERROR; + off_t data_msgbuf_id = INVALID_MSGBUF_ID; + pkt_cache_entry_t *entry = NULL; + // Save PIT entries to avoid re-doing pkt cache lookup in + // `_forwarder_forward_aggregated_interest()` + pkt_cache_entry_t *entries[BITMAP_SIZE * WORD_WIDTH]; + + int pos = 0; // Position of current suffix in manifest + int n_suffixes_to_fwd = 0; + u32 *suffix = (u32 *)(int_manifest_header + 1); + u32 seq = name_GetSegment(msgbuf_get_name(msgbuf)); + + Name name_copy = EMPTY_NAME; + name_Copy(msgbuf_get_name(msgbuf), &name_copy); + + // The fist loop iteration handles the suffix in the header, + // the following ones handle the suffiexes in the manifest + while (true) { + if (!is_bit_set(int_manifest_header->request_bitmap, pos)) goto NEXT_SUFFIX; + + // Update packet cache + pkt_cache_on_interest(forwarder->pkt_cache, msgbuf_pool, msgbuf_id, + &verdict, &data_msgbuf_id, &entry, &name_copy, + forwarder->serve_from_cs); + entries[pos] = entry; + _forwarder_update_interest_stats(forwarder, verdict, msgbuf, + entry->has_expire_ts, entry->expire_ts); + + // Here only data forwarding is performed, interest forwarding is done + // in '_forwarder_forward_aggregated_interest()' + int rc = + _forwarder_forward_upon_interest(forwarder, msgbuf_pool, data_msgbuf_id, + msgbuf_id, entry, verdict, true); + + // No route when trying to forward interest, remove from PIT + if (rc == -1) + pkt_cache_pit_remove_entry(forwarder->pkt_cache, entry, &name_copy); + + // Unset in bitmap if no interest forwarding needed, + // otherwise increase count of suffixes to forward + if (rc == -1 || verdict == PKT_CACHE_VERDICT_AGGREGATE_INTEREST || + verdict == PKT_CACHE_VERDICT_FORWARD_DATA) { + unset_bit(int_manifest_header->request_bitmap, pos); + } else { + n_suffixes_to_fwd++; + } + + NEXT_SUFFIX: + if (pos++ >= int_manifest_header->n_suffixes) break; + + // Use next segment in manifest + seq = *suffix; + suffix++; + name_SetSegment(&name_copy, seq); + + WITH_DEBUG({ + char *nameString = name_ToString(&name_copy); + DEBUG("Next in manifest: %s", nameString); + free(nameString); + }); + } + + // Return if nothing in the manifest to forward + if (n_suffixes_to_fwd == 0) return msgbuf_get_len(msgbuf); + + return _forwarder_forward_aggregated_interest(forwarder, int_manifest_header, + n_suffixes_to_fwd, msgbuf, + msgbuf_id, entries); +} + /** * @function forwarder_process_interest * @abstract Receive an interest from the network @@ -657,29 +846,39 @@ static ssize_t forwarder_process_interest(forwarder_t *forwarder, msgbuf_pool_t *msgbuf_pool = forwarder_get_msgbuf_pool(forwarder); msgbuf_t *msgbuf = msgbuf_pool_at(msgbuf_pool, msgbuf_id); + const connection_table_t *table = forwarder_get_connection_table(forwarder); + connection_t *conn = + connection_table_get_by_id(table, msgbuf_get_connection_id(msgbuf)); assert(msgbuf_get_type(msgbuf) == MSGBUF_TYPE_INTEREST); - forwarder->stats.countReceived++; + u32 n_suffixes = 0; + interest_manifest_header_t *int_manifest_header = + _forwarder_get_interest_manifest(msgbuf); + if (int_manifest_header) n_suffixes = int_manifest_header->n_suffixes; + + // Update stats forwarder->stats.countInterestsReceived++; + conn->stats.interests.rx_pkts++; + conn->stats.interests.rx_bytes += msgbuf_get_len(msgbuf); WITH_DEBUG({ char *nameString = name_ToString(msgbuf_get_name(msgbuf)); - DEBUG("INTEREST (%s) msgbuf_id=%lu ingress=%u length=%u", nameString, - msgbuf_id, msgbuf_get_connection_id(msgbuf), msgbuf_get_len(msgbuf)); + DEBUG("INTEREST (%s) suffixes=%u msgbuf_id=%lu ingress=%u length=%u", + nameString, n_suffixes, msgbuf_id, msgbuf_get_connection_id(msgbuf), + msgbuf_get_len(msgbuf)); free(nameString); - }) - - pkt_cache_verdict_t verdict = PKT_CACHE_VERDICT_ERROR; - off_t data_msgbuf_id = INVALID_MSGBUF_ID; - pkt_cache_entry_t *entry = NULL; - pkt_cache_on_interest(forwarder->pkt_cache, msgbuf_pool, msgbuf_id, &verdict, - &data_msgbuf_id, &entry, forwarder->serve_from_cs); + }); - _forwarder_update_interest_stats(forwarder, verdict, msgbuf, entry); + // Cache suffixes for current prefix to (possibly) avoid double lookups + pkt_cache_save_suffixes_for_prefix( + forwarder->pkt_cache, name_GetContentName(msgbuf_get_name(msgbuf))); - return _forwarder_forward_upon_interest( - forwarder, msgbuf_pool, data_msgbuf_id, msgbuf_id, entry, verdict); + if (!int_manifest_header) + return forwarder_process_single_interest(forwarder, msgbuf_pool, msgbuf, + msgbuf_id); + return forwarder_process_aggregated_interest(forwarder, int_manifest_header, + msgbuf_pool, msgbuf, msgbuf_id); } static void _forwarder_log_on_data(forwarder_t *forwarder, @@ -700,7 +899,7 @@ static void _forwarder_log_on_data(forwarder_t *forwarder, DEBUG("Message not stored in CS"); break; case PKT_CACHE_VERDICT_ERROR: - ERROR("Inivalid packet cache content"); + ERROR("Invalid packet cache content"); break; default: break; @@ -726,24 +925,31 @@ static ssize_t forwarder_process_data(forwarder_t *forwarder, off_t msgbuf_id) { DEBUG("DATA (%s) msgbuf_id=%lu ingress=%u length=%u", nameString, msgbuf_id, msgbuf_get_connection_id(msgbuf), msgbuf_get_len(msgbuf)); free(nameString); - )} - - forwarder->stats.countReceived++; - forwarder->stats.countObjectsReceived++; + }); const connection_table_t *table = forwarder_get_connection_table(forwarder); - const connection_t *conn = + connection_t *conn = connection_table_get_by_id(table, msgbuf_get_connection_id(msgbuf)); + // Update stats + forwarder->stats.countObjectsReceived++; + conn->stats.data.rx_pkts++; + conn->stats.data.rx_bytes += msgbuf_get_len(msgbuf); + + // Cache suffixes for current prefix to (possibly) avoid double lookups + pkt_cache_save_suffixes_for_prefix( + forwarder->pkt_cache, name_GetContentName(msgbuf_get_name(msgbuf))); + pkt_cache_verdict_t verdict = PKT_CACHE_VERDICT_ERROR; bool wrong_egress; - nexthops_t *ingressSetUnion = - pkt_cache_on_data(forwarder->pkt_cache, msgbuf_pool, msgbuf_id, - forwarder->store_in_cs, connection_is_local(conn), &wrong_egress, &verdict); + nexthops_t *ingressSetUnion = pkt_cache_on_data( + forwarder->pkt_cache, msgbuf_pool, msgbuf_id, forwarder->store_in_cs, + connection_is_local(conn), &wrong_egress, &verdict); _forwarder_log_on_data(forwarder, verdict); - if (wrong_egress) { // Interest sent via a connection but received from another + if (wrong_egress) { // Interest sent via a connection but received from + // another WARN("Data coming from unexpected connection, discarded"); } else if (!ingressSetUnion) { // No match in the PIT forwarder->stats.countDroppedNoReversePath++; @@ -776,15 +982,15 @@ void forwarder_flush_connections(forwarder_t *forwarder) { // DEBUG("[forwarder_flush_connections]"); const connection_table_t *table = forwarder_get_connection_table(forwarder); - for (unsigned i = 0; i < forwarder->num_pending_conn; i++) { + for (unsigned i = 0; i < vector_len(forwarder->pending_conn); i++) { unsigned conn_id = forwarder->pending_conn[i]; - const connection_t *conn = connection_table_at(table, conn_id); + connection_t *conn = connection_table_at(table, conn_id); if (!connection_flush(conn)) { WARN("Could not flush connection queue"); // XXX keep track of non flushed connections... } } - forwarder->num_pending_conn = 0; + vector_reset(forwarder->pending_conn); // DEBUG("[forwarder_flush_connections] done"); } @@ -957,6 +1163,23 @@ cs_t *forwarder_get_cs(const forwarder_t *forwarder) { return pkt_cache_get_cs(forwarder->pkt_cache); } +// IMPORTANT: Use this function ONLY for read-only operations since a realloc +// would otherwise modify the returned copy but not the original msgbuf ids +// vector in the forwarder. This constraint cannot be enforced by returning a +// (const off_t *) because the vector_t macros still cast to (void **). +off_t *forwarder_get_acquired_msgbuf_ids(const forwarder_t *forwarder) { + return forwarder->acquired_msgbuf_ids; +} + +void forwarder_acquired_msgbuf_ids_reset(const forwarder_t *forwarder) { + vector_reset(forwarder->acquired_msgbuf_ids); +} + +void forwarder_acquired_msgbuf_ids_push(const forwarder_t *forwarder, + off_t msgbuf_id) { + vector_push(forwarder->acquired_msgbuf_ids, msgbuf_id); +} + // ======================================================= fib_t *forwarder_get_fib(forwarder_t *forwarder) { return forwarder->fib; } @@ -1052,14 +1275,15 @@ ssize_t forwarder_receive(forwarder_t *forwarder, listener_t *listener, const connection_table_t *table = forwarder_get_connection_table(listener->forwarder); connection_t *connection = connection_table_get_by_pair(table, pair); - unsigned conn_id = connection - ? connection_table_get_connection_id(table, connection) - : CONNECTION_ID_UNDEFINED; + unsigned conn_id = connection ? (unsigned)connection_table_get_connection_id( + table, connection) + : CONNECTION_ID_UNDEFINED; assert((conn_id != CONNECTION_ID_UNDEFINED) || listener); msgbuf_type_t type = get_type_from_packet(msgbuf_get_packet(msgbuf)); + forwarder->stats.countReceived++; msgbuf->type = type; msgbuf->connection_id = conn_id; msgbuf->recv_ts = now; @@ -1067,12 +1291,14 @@ ssize_t forwarder_receive(forwarder_t *forwarder, listener_t *listener, switch (type) { case MSGBUF_TYPE_INTEREST: if (!connection_id_is_valid(msgbuf->connection_id)) { - char *conn_name = connection_table_get_random_name(table); + char conn_name[SYMBOLIC_NAME_LEN]; + int rc = connection_table_get_random_name(table, conn_name); + if (rc < 0) return 0; + unsigned connection_id = listener_create_connection(listener, conn_name, pair); msgbuf->connection_id = connection_id; connection = connection_table_get_by_id(table, connection_id); - free(conn_name); } msgbuf->path_label = 0; // not used for interest packets name_create_from_interest(packet, msgbuf_get_name(msgbuf)); @@ -1102,10 +1328,12 @@ ssize_t forwarder_receive(forwarder_t *forwarder, listener_t *listener, case MSGBUF_TYPE_MAPME: // XXX what about acks ? if (!connection_id_is_valid(msgbuf->connection_id)) { - char *conn_name = connection_table_get_random_name(table); + char conn_name[SYMBOLIC_NAME_LEN]; + int rc = connection_table_get_random_name(table, conn_name); + if (rc < 0) return 0; + msgbuf->connection_id = listener_create_connection(listener, conn_name, pair); - free(conn_name); } mapme_process(forwarder->mapme, msgbuf); return size; @@ -1113,12 +1341,14 @@ ssize_t forwarder_receive(forwarder_t *forwarder, listener_t *listener, case MSGBUF_TYPE_COMMAND: // Create the connection to send the ack back if (!connection_id_is_valid(msgbuf->connection_id)) { - char *conn_name = connection_table_get_random_name(table); + char conn_name[SYMBOLIC_NAME_LEN]; + int rc = connection_table_get_random_name(table, conn_name); + if (rc < 0) return 0; + unsigned connection_id = listener_create_connection(listener, conn_name, pair); msgbuf->connection_id = connection_id; connection = connection_table_get_by_id(table, connection_id); - free(conn_name); } msg_header_t *msg = (msg_header_t *)packet; @@ -1163,3 +1393,7 @@ void forwarder_log(forwarder_t *forwarder) { forwarder->stats.countInterestsExpired, forwarder->stats.countDataExpired, forwarder->stats.countDroppedNoReversePath); } + +forwarder_stats_t forwarder_get_stats(forwarder_t *forwarder) { + return forwarder->stats; +}
\ No newline at end of file diff --git a/hicn-light/src/hicn/core/forwarder.h b/hicn-light/src/hicn/core/forwarder.h index 76c12368a..2f940cf15 100644 --- a/hicn-light/src/hicn/core/forwarder.h +++ b/hicn-light/src/hicn/core/forwarder.h @@ -98,6 +98,8 @@ listener_table_t *forwarder_get_listener_table(forwarder_t *forwarder); connection_table_t *forwarder_get_connection_table( const forwarder_t *forwarder); +pkt_cache_t *forwarder_get_pkt_cache(const forwarder_t *forwarder); + void forwarder_cs_set_store(forwarder_t *forwarder, bool val); bool forwarder_cs_get_store(forwarder_t *forwarder); @@ -159,6 +161,18 @@ void forwarder_set_strategy(forwarder_t *forwarder, Name *name_prefix, cs_t *forwarder_get_cs(const forwarder_t *forwarder); +off_t *forwarder_get_acquired_msgbuf_ids(const forwarder_t *forwarder); + +/** + * @note Acquire msgbuf ids vector ONLY for read-only operations. + */ +off_t *forwarder_get_acquired_msgbuf_ids(const forwarder_t *forwarder); + +void forwarder_acquired_msgbuf_ids_reset(const forwarder_t *forwarder); + +void forwarder_acquired_msgbuf_ids_push(const forwarder_t *forwarder, + off_t msgbuf_id); + /** * @brief Returns the forwarder's FIB. * @param[in] forwarder - Pointer to the forwarder. @@ -226,4 +240,6 @@ ssize_t forwarder_receive(forwarder_t *forwarder, listener_t *listener, */ void forwarder_log(forwarder_t *forwarder); +forwarder_stats_t forwarder_get_stats(forwarder_t *forwarder); + #endif // HICNLIGHT_FORWARDER_H diff --git a/hicn-light/src/hicn/core/interest_manifest.c b/hicn-light/src/hicn/core/interest_manifest.c new file mode 100644 index 000000000..1be8a3fb5 --- /dev/null +++ b/hicn-light/src/hicn/core/interest_manifest.c @@ -0,0 +1,64 @@ +/* + * Copyright (c) 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. + */ + +#include "interest_manifest.h" + +int_manifest_split_strategy_t disaggregation_strategy = + INT_MANIFEST_SPLIT_MAX_N_SUFFIXES; +unsigned N_SUFFIXES_PER_SPIT = 256; + +bool interest_manifest_is_valid(interest_manifest_header_t *int_manifest_header, + size_t payload_length) { + if (int_manifest_header->n_suffixes == 0 || + int_manifest_header->n_suffixes > MAX_SUFFIXES_IN_MANIFEST) { + ERROR("Manifest with invalid number of suffixes (%d)", + int_manifest_header->n_suffixes); + return false; + } + + uint32_t empty_bitmap[BITMAP_SIZE] = {0}; + if (memcmp(empty_bitmap, int_manifest_header->request_bitmap, + sizeof(empty_bitmap)) == 0) { + ERROR("Manifest with empty bitmap"); + return false; + } + + if (payload_length - sizeof(interest_manifest_header_t) != + int_manifest_header->n_suffixes * sizeof(u32)) { + ERROR("Size of suffixes in intereset manifest (%d) is not equal to %d", + payload_length - sizeof(interest_manifest_header_t), + int_manifest_header->n_suffixes * sizeof(u32)); + return false; + } + + return true; +} + +int interest_manifest_update_bitmap(const u32 *initial_bitmap, + u32 *bitmap_to_update, int start, int n, + int max_suffixes) { + int i = start, n_ones = 0; + while (i < n) { + if (is_bit_set(initial_bitmap, i)) { + set_bit(bitmap_to_update, i); + n_ones++; + } + i++; + + if (n_ones == max_suffixes) break; + } + + return i; +} diff --git a/hicn-light/src/hicn/core/interest_manifest.h b/hicn-light/src/hicn/core/interest_manifest.h new file mode 100644 index 000000000..fcb2b9897 --- /dev/null +++ b/hicn-light/src/hicn/core/interest_manifest.h @@ -0,0 +1,40 @@ +/* + * Copyright (c) 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. + */ + +#ifndef HICNLIGHT_INTEREST_MANIFEST_H +#define HICNLIGHT_INTEREST_MANIFEST_H + +#include <string.h> +#include <stdbool.h> + +#include <hicn/util/log.h> +#include <hicn/base.h> + +typedef enum { + INT_MANIFEST_SPLIT_NONE, + INT_MANIFEST_SPLIT_MAX_N_SUFFIXES +} int_manifest_split_strategy_t; + +extern int_manifest_split_strategy_t disaggregation_strategy; +extern unsigned N_SUFFIXES_PER_SPIT; + +bool interest_manifest_is_valid(interest_manifest_header_t *int_manifest_header, + size_t payload_length); + +int interest_manifest_update_bitmap(const u32 *initial_bitmap, + u32 *bitmap_to_update, int start, int n, + int max_suffixes); + +#endif /* HICNLIGHT_INTEREST_MANIFEST_H */ diff --git a/hicn-light/src/hicn/core/listener.c b/hicn-light/src/hicn/core/listener.c index ecdfc38f4..188f0c317 100644 --- a/hicn-light/src/hicn/core/listener.c +++ b/hicn-light/src/hicn/core/listener.c @@ -24,7 +24,6 @@ #include "forwarder.h" #include "listener_vft.h" -#include "../base/loop.h" #include "../io/base.h" listener_key_t listener_key_factory(address_t address, face_type_t type) { @@ -44,7 +43,8 @@ listener_t *listener_create(face_type_t type, const address_t *address, listener_key_t key = listener_key_factory(*address, type); listener_t *listener = listener_table_allocate(table, &key, name); - unsigned listener_id = listener_table_get_listener_id(table, listener); + unsigned listener_id = + (unsigned int)listener_table_get_listener_id(table, listener); int ret = listener_initialize(listener, type, name, listener_id, address, interface_name, forwarder); @@ -194,7 +194,7 @@ unsigned listener_create_connection(listener_t *listener, connection_t *connection = connection_table_allocate(table, pair, connection_name); unsigned connection_id = - connection_table_get_connection_id(table, connection); + (unsigned int)connection_table_get_connection_id(table, connection); /* * We create a connected connection with its own fd, instead of returning @@ -337,11 +337,10 @@ ssize_t listener_read_batch(listener_t *listener, int fd) { size_t total_processed_bytes = 0; ssize_t num_msg_received = 0; - off_t *acquired_msgbuf_ids; - vector_init(acquired_msgbuf_ids, MAX_MSG, 0); forwarder_t *forwarder = listener->forwarder; msgbuf_pool_t *msgbuf_pool = forwarder_get_msgbuf_pool(forwarder); + forwarder_acquired_msgbuf_ids_reset(forwarder); /* Receive messages in the loop as long as we manage to fill the buffers */ do { @@ -381,7 +380,7 @@ ssize_t listener_read_batch(listener_t *listener, int fd) { } msgbuf_pool_acquire(msgbufs[i]); - vector_push(acquired_msgbuf_ids, msgbuf_ids[i]); + forwarder_acquired_msgbuf_ids_push(forwarder, msgbuf_ids[i]); } if (num_msg_received < 0) break; @@ -403,11 +402,12 @@ ssize_t listener_read_batch(listener_t *listener, int fd) { */ forwarder_flush_connections(forwarder); + const off_t *acquired_msgbuf_ids = + forwarder_get_acquired_msgbuf_ids(forwarder); for (int i = 0; i < vector_len(acquired_msgbuf_ids); i++) { msgbuf_t *msgbuf = msgbuf_pool_at(msgbuf_pool, acquired_msgbuf_ids[i]); msgbuf_pool_release(msgbuf_pool, &msgbuf); } - vector_free(acquired_msgbuf_ids); return total_processed_bytes; } diff --git a/hicn-light/src/hicn/core/listener.h b/hicn-light/src/hicn/core/listener.h index 346c874c0..5d0384329 100644 --- a/hicn-light/src/hicn/core/listener.h +++ b/hicn-light/src/hicn/core/listener.h @@ -25,7 +25,7 @@ #include "address_pair.h" #include "msgbuf.h" -#include "../base/loop.h" +#include <hicn/base/loop.h> #define LISTENER_ID_UNDEFINED ~0 @@ -36,6 +36,12 @@ typedef struct { face_type_t type; } listener_key_t; +static inline int listener_key_equals(const listener_key_t *key1, + const listener_key_t *key2) { + return address_equals(&key1->address, &key2->address) && + (key1->type == key2->type); +} + /** * @brief Create a listener key starting from an address and a face type. * diff --git a/hicn-light/src/hicn/core/listener_table.c b/hicn-light/src/hicn/core/listener_table.c index 32b8e9d45..220b738bb 100644 --- a/hicn-light/src/hicn/core/listener_table.c +++ b/hicn-light/src/hicn/core/listener_table.c @@ -72,6 +72,54 @@ void listener_table_free(listener_table_t *table) { free(table); } +listener_t *listener_table_allocate(const listener_table_t *table, + const listener_key_t *key, + const char *name) { + listener_t *listener = NULL; + pool_get(table->listeners, listener); + if (!listener) return NULL; + + off_t id = listener - table->listeners; + int rc; + + // Add in name hash table + khiter_t k = kh_put_lt_name(table->id_by_name, strdup(name), &rc); + assert(rc == KH_ADDED || rc == KH_RESET); + kh_value(table->id_by_name, k) = (unsigned int)id; + + // Add in key hash table + listener_key_t *key_copy = (listener_key_t *)malloc(sizeof(listener_key_t)); + memcpy(key_copy, key, sizeof(listener_key_t)); + + k = kh_put_lt_key(table->id_by_key, key_copy, &rc); + assert(rc == KH_ADDED || rc == KH_RESET); + kh_value(table->id_by_key, k) = (unsigned int)id; + + assert(kh_size(table->id_by_name) == kh_size(table->id_by_key)); + return listener; +} + +void listener_table_deallocate(const listener_table_t *table, + listener_t *listener) { + const char *name = listener_get_name(listener); + listener_key_t *key = listener_get_key(listener); + + // Remove from name hash table + khiter_t k = kh_get_lt_name(table->id_by_name, name); + assert(k != kh_end(table->id_by_name)); + free((char *)kh_key(table->id_by_name, k)); + kh_del_lt_name(table->id_by_name, k); + + // Remove from key hash table + k = kh_get_lt_key(table->id_by_key, key); + assert(k != kh_end(table->id_by_key)); + free((listener_key_t *)kh_key(table->id_by_key, k)); + kh_del_lt_key(table->id_by_key, k); + + assert(kh_size(table->id_by_name) == kh_size(table->id_by_key)); + pool_put(table->listeners, listener); +} + listener_t *listener_table_get_by_address(listener_table_t *table, face_type_t type, const address_t *address) { @@ -104,7 +152,8 @@ off_t listener_table_get_id_by_name(const listener_table_t *table, listener_t *listener_table_get_by_name(listener_table_t *table, const char *name) { - unsigned listener_id = listener_table_get_id_by_name(table, name); + unsigned listener_id = + (unsigned int)listener_table_get_id_by_name(table, name); if (!listener_id_is_valid(listener_id)) return NULL; return listener_table_at(table, listener_id); } diff --git a/hicn-light/src/hicn/core/listener_table.h b/hicn-light/src/hicn/core/listener_table.h index 5fed638e8..7e2e99d7f 100644 --- a/hicn-light/src/hicn/core/listener_table.h +++ b/hicn-light/src/hicn/core/listener_table.h @@ -30,22 +30,19 @@ #ifndef HICNLIGHT_LISTENER_TABLE_H #define HICNLIGHT_LISTENER_TABLE_H +#include <hicn/util/khash.h> +#include <hicn/util/hash.h> #include "address.h" #include "listener.h" -#include "../base/common.h" -#include "../base/hash.h" -#include "../base/khash.h" -#include "../base/pool.h" - -#define _lt_var(x) _lt_var_##x +#include <hicn/util/pool.h> /* Hash functions for indices */ #define key_hash(key) (hash_struct(key)) -#define key_hash_eq(a, b) (key_hash(b) == key_hash(a)) /* Hash table types for indices */ KHASH_MAP_INIT_STR(lt_name, unsigned); -KHASH_INIT(lt_key, const listener_key_t *, unsigned, 1, key_hash, key_hash_eq); +KHASH_INIT(lt_key, const listener_key_t *, unsigned, 1, key_hash, + listener_key_equals); typedef struct { size_t max_size; @@ -70,34 +67,9 @@ typedef struct { * - You should always check that the returned listener is not NULL, which * would signal that the pool is exhausted and could not be extended. */ - -static inline listener_t *listener_table_allocate(const listener_table_t *table, - const listener_key_t *key, - const char *name) { - listener_t *listener; - pool_get(table->listeners, listener); - - if (listener) { - off_t id = listener - table->listeners; - int res; - khiter_t k; - - // Add in name hash table - k = kh_put_lt_name(table->id_by_name, strdup(name), &res); - assert(res > 0); - kh_value(table->id_by_name, k) = id; - - // Add in key hash table - listener_key_t *key_copy = (listener_key_t *)malloc(sizeof(listener_key_t)); - memcpy(key_copy, key, sizeof(listener_key_t)); - - k = kh_put_lt_key(table->id_by_key, key_copy, &res); - assert(res > 0); - kh_value(table->id_by_key, k) = id; - } - - return listener; -} +listener_t *listener_table_allocate(const listener_table_t *table, + const listener_key_t *key, + const char *name); /** * @brief Deallocate a listener and return it to the listener table pool. @@ -109,27 +81,8 @@ static inline listener_t *listener_table_allocate(const listener_table_t *table, * - Upon returning a listener to the pool, all indices pointing to that * listener are also cleared. */ - -static inline void listener_table_deallocate(const listener_table_t *table, - listener_t *listener) { - const char *name = listener_get_name(listener); - listener_key_t *key = listener_get_key(listener); - khiter_t k; - - // Remove from name hash table - k = kh_get_lt_name(table->id_by_name, name); - assert(k != kh_end(table->id_by_name)); - free((char *)kh_key(table->id_by_name, k)); - kh_del_lt_name(table->id_by_name, k); - - // Remove from key hash table - k = kh_get_lt_key(table->id_by_key, key); - assert(k != kh_end(table->id_by_key)); - free((listener_key_t *)kh_key(table->id_by_key, k)); - kh_del_lt_key(table->id_by_key, k); - - pool_put(table->listeners, listener); -} +void listener_table_deallocate(const listener_table_t *table, + listener_t *listener); /** * @brief Returns the length of the listener table, the number of active diff --git a/hicn-light/src/hicn/core/msgbuf_pool.c b/hicn-light/src/hicn/core/msgbuf_pool.c index fb5d0a07c..a2092aaf6 100644 --- a/hicn-light/src/hicn/core/msgbuf_pool.c +++ b/hicn-light/src/hicn/core/msgbuf_pool.c @@ -18,9 +18,8 @@ * @brief Implementation of hICN packet pool. */ -#include "../base/pool.h" +#include <hicn/util/pool.h> #include "msgbuf_pool.h" -#include "../core/name.h" // name_Release msgbuf_pool_t *_msgbuf_pool_create(size_t init_size, size_t max_size) { msgbuf_pool_t *msgbuf_pool = malloc(sizeof(msgbuf_pool_t)); @@ -38,7 +37,9 @@ void msgbuf_pool_free(msgbuf_pool_t *msgbuf_pool) { } off_t msgbuf_pool_get(msgbuf_pool_t *msgbuf_pool, msgbuf_t **msgbuf) { - return pool_get(msgbuf_pool->buffers, *msgbuf); + off_t id = pool_get(msgbuf_pool->buffers, *msgbuf); + (*msgbuf)->refs = 0; + return id; } void msgbuf_pool_put(msgbuf_pool_t *msgbuf_pool, msgbuf_t *msgbuf) { diff --git a/hicn-light/src/hicn/core/name.c b/hicn-light/src/hicn/core/name.c index 8886cc929..d30cebefc 100644 --- a/hicn-light/src/hicn/core/name.c +++ b/hicn-light/src/hicn/core/name.c @@ -20,11 +20,10 @@ #include <stdio.h> #include <string.h> -#include <hicn/common.h> // cumulative_hash32 #include <hicn/core/messageHandler.h> #include <hicn/core/name.h> #include <hicn/util/log.h> -#include <hicn/base/hash.h> +#include <hicn/util/hash.h> #define IPv6_TYPE 6 #define IPv4_TYPE 4 diff --git a/hicn-light/src/hicn/core/nameBitvector.c b/hicn-light/src/hicn/core/nameBitvector.c index 1314671db..aa431879c 100644 --- a/hicn-light/src/hicn/core/nameBitvector.c +++ b/hicn-light/src/hicn/core/nameBitvector.c @@ -20,7 +20,7 @@ #include <hicn/core/messageHandler.h> #include <hicn/core/nameBitvector.h> -#include <hicn/base/hash.h> +#include <hicn/util/hash.h> #include <hicn/ctrl/hicn-light-ng.h> #define DEFAULT_PORT 1234 diff --git a/hicn-light/src/hicn/core/nameBitvector.h b/hicn-light/src/hicn/core/nameBitvector.h index e3cc108ac..549b26679 100644 --- a/hicn-light/src/hicn/core/nameBitvector.h +++ b/hicn-light/src/hicn/core/nameBitvector.h @@ -23,11 +23,13 @@ #include "address.h" #define NAME_LEN 2 -typedef struct { +typedef struct __attribute__((__packed__)) { uint64_t bits[NAME_LEN]; - uint8_t len; - uint8_t IPversion; + uint32_t len; + uint32_t IPversion; } NameBitvector; +static_assert(sizeof(NameBitvector) == 24, + "Name prefix should be stored on 24 bytes"); #define EMPTY_NAME_BITVECTOR \ (NameBitvector) { .bits[0] = 0, .bits[1] = 0, .len = 0, .IPversion = 0, } diff --git a/hicn-light/src/hicn/core/packet_cache.c b/hicn-light/src/hicn/core/packet_cache.c index 203ad4a63..8bd188c8b 100644 --- a/hicn-light/src/hicn/core/packet_cache.c +++ b/hicn-light/src/hicn/core/packet_cache.c @@ -20,6 +20,111 @@ #include "packet_cache.h" +/****************************************************************************** + * Low-level operations on the hash table + ******************************************************************************/ + +void _prefix_map_free(kh_pkt_cache_prefix_t *prefix_to_suffixes) { + const NameBitvector *key; + kh_pkt_cache_suffix_t *value; + kh_foreach(prefix_to_suffixes, key, value, { + free((NameBitvector *)key); + kh_destroy_pkt_cache_suffix(value); + }); + kh_destroy_pkt_cache_prefix(prefix_to_suffixes); +} + +kh_pkt_cache_suffix_t *_get_suffixes(kh_pkt_cache_prefix_t *prefix_to_suffixes, + const NameBitvector *prefix) { + khiter_t k = kh_get_pkt_cache_prefix(prefix_to_suffixes, prefix); + + // Return suffixes found + if (k != kh_end(prefix_to_suffixes)) { + kh_pkt_cache_suffix_t *suffixes = kh_val(prefix_to_suffixes, k); + return suffixes; + } + + kh_pkt_cache_suffix_t *suffixes = kh_init_pkt_cache_suffix(); + NameBitvector *nb_copy = (NameBitvector *)malloc(sizeof(NameBitvector)); + *nb_copy = *prefix; + + int rc; + k = kh_put_pkt_cache_prefix(prefix_to_suffixes, nb_copy, &rc); + assert(rc == KH_ADDED || rc == KH_RESET); + kh_value(prefix_to_suffixes, k) = suffixes; + return suffixes; +} + +void _remove_suffix(kh_pkt_cache_prefix_t *prefixes, + const NameBitvector *prefix, uint32_t suffix) { + kh_pkt_cache_suffix_t *suffixes = _get_suffixes(prefixes, prefix); + assert(suffixes != NULL); + + khiter_t k = kh_get_pkt_cache_suffix(suffixes, suffix); + assert(k != kh_end(suffixes)); + kh_del_pkt_cache_suffix(suffixes, k); + + // TODO(eloparco): Remove prefix if no associated suffixes? +} + +void __add_suffix(kh_pkt_cache_suffix_t *suffixes, uint32_t suffix, + unsigned val) { + int rc; + khiter_t k = kh_put_pkt_cache_suffix(suffixes, suffix, &rc); + assert(rc == KH_ADDED || rc == KH_RESET); + kh_value(suffixes, k) = val; +} + +void _add_suffix(kh_pkt_cache_prefix_t *prefixes, const NameBitvector *prefix, + uint32_t suffix, unsigned val) { + kh_pkt_cache_suffix_t *suffixes = _get_suffixes(prefixes, prefix); + assert(suffixes != NULL); + + __add_suffix(suffixes, suffix, val); +} + +unsigned __get_suffix(kh_pkt_cache_suffix_t *suffixes, uint32_t suffix, + int *rc) { + *rc = KH_FOUND; + khiter_t k = kh_get_pkt_cache_suffix(suffixes, suffix); + + // Not Found + if (k == kh_end(suffixes)) { + *rc = KH_NOT_FOUND; + return -1; + } + + unsigned index = kh_val(suffixes, k); + return index; +} + +void pkt_cache_save_suffixes_for_prefix(pkt_cache_t *pkt_cache, + const NameBitvector *prefix) { + // Cached prefix matches the current one + if (nameBitvector_Compare(&pkt_cache->cached_prefix, prefix) == 0) return; + + // Update cached prefix information + pkt_cache->cached_prefix = *prefix; + pkt_cache->cached_suffixes = + _get_suffixes(pkt_cache->prefix_to_suffixes, prefix); +} + +void pkt_cache_reset_suffixes_for_prefix(pkt_cache_t *pkt_cache) { + pkt_cache->cached_suffixes = NULL; +} + +unsigned _get_suffix(kh_pkt_cache_prefix_t *prefixes, + const NameBitvector *prefix, uint32_t suffix, int *rc) { + kh_pkt_cache_suffix_t *suffixes = _get_suffixes(prefixes, prefix); + assert(suffixes != NULL); + + return __get_suffix(suffixes, suffix, rc); +} + +/****************************************************************************** + * Public API + ******************************************************************************/ + pkt_cache_t *pkt_cache_create(size_t cs_size) { pkt_cache_t *pkt_cache = (pkt_cache_t *)malloc(sizeof(pkt_cache_t)); @@ -28,23 +133,20 @@ pkt_cache_t *pkt_cache_create(size_t cs_size) { pkt_cache->cs = cs_create(cs_size); if (!pkt_cache->cs) return NULL; - pkt_cache->index_by_name = kh_init(pkt_cache_name); + pkt_cache->prefix_to_suffixes = kh_init_pkt_cache_prefix(); pool_init(pkt_cache->entries, DEFAULT_PKT_CACHE_SIZE, 0); + pkt_cache->cached_prefix = EMPTY_NAME_BITVECTOR; + pkt_cache->cached_suffixes = NULL; + return pkt_cache; } void pkt_cache_free(pkt_cache_t *pkt_cache) { assert(pkt_cache); - // Free hashmap - const Name *k_name; - unsigned v; - (void)v; - kh_foreach(pkt_cache->index_by_name, k_name, v, { free((Name *)k_name); }); - kh_destroy(pkt_cache_name, pkt_cache->index_by_name); - - // Free pool + // Free prefix hash table and pool + _prefix_map_free(pkt_cache->prefix_to_suffixes); pool_free(pkt_cache->entries); // Free PIT and CS @@ -54,6 +156,30 @@ void pkt_cache_free(pkt_cache_t *pkt_cache) { free(pkt_cache); } +kh_pkt_cache_suffix_t *pkt_cache_get_suffixes(const pkt_cache_t *pkt_cache, + const NameBitvector *prefix) { + return _get_suffixes(pkt_cache->prefix_to_suffixes, prefix); +} + +pkt_cache_entry_t *pkt_cache_allocate(pkt_cache_t *pkt_cache, + const Name *name) { + pkt_cache_entry_t *entry = NULL; + pool_get(pkt_cache->entries, entry); + if (!entry) return NULL; + + off_t id = entry - pkt_cache->entries; + + if (pkt_cache->cached_suffixes) { + __add_suffix(pkt_cache->cached_suffixes, name_GetSegment(name), + (unsigned int)id); + } else { + _add_suffix(pkt_cache->prefix_to_suffixes, name_GetContentName(name), + name_GetSegment(name), (unsigned int)id); + } + + return entry; +} + pit_t *pkt_cache_get_pit(pkt_cache_t *pkt_cache) { return pkt_cache->pit; } cs_t *pkt_cache_get_cs(pkt_cache_t *pkt_cache) { return pkt_cache->cs; } @@ -63,14 +189,22 @@ pkt_cache_entry_t *pkt_cache_lookup(pkt_cache_t *pkt_cache, const Name *name, pkt_cache_lookup_t *lookup_result, off_t *entry_id, bool is_serve_from_cs_enabled) { - Name name_key = name_key_factory(name); - khiter_t k = kh_get_pkt_cache_name(pkt_cache->index_by_name, &name_key); - if (k == kh_end(pkt_cache->index_by_name)) { + int rc; + + unsigned index = -1; + if (pkt_cache->cached_suffixes) { + index = + __get_suffix(pkt_cache->cached_suffixes, name_GetSegment(name), &rc); + } else { + index = _get_suffix(pkt_cache->prefix_to_suffixes, + name_GetContentName(name), name_GetSegment(name), &rc); + } + + if (rc == KH_NOT_FOUND) { *lookup_result = PKT_CACHE_LU_NONE; return NULL; } - off_t index = kh_val(pkt_cache->index_by_name, k); pkt_cache_entry_t *entry = pkt_cache_at(pkt_cache, index); assert(entry); bool expired = false; @@ -103,11 +237,9 @@ void pkt_cache_cs_remove_entry(pkt_cache_t *pkt_cache, pkt_cache_entry_t *entry, off_t msgbuf_id = entry->u.cs_entry.msgbuf_id; msgbuf_t *msgbuf = msgbuf_pool_at(msgbuf_pool, msgbuf_id); - Name name_key = name_key_factory(msgbuf_get_name(msgbuf)); - khiter_t k = kh_get_pkt_cache_name(pkt_cache->index_by_name, &name_key); - assert(k != kh_end(pkt_cache->index_by_name)); - free((Name *)kh_key(pkt_cache->index_by_name, k)); - kh_del(pkt_cache_name, pkt_cache->index_by_name, k); + const Name *name = msgbuf_get_name(msgbuf); + _remove_suffix(pkt_cache->prefix_to_suffixes, name_GetContentName(name), + name_GetSegment(name)); // Do not update the LRU cache for evicted entries if (!is_evicted) cs_vft[pkt_cache->cs->type]->remove_entry(pkt_cache, entry); @@ -130,12 +262,8 @@ void pkt_cache_pit_remove_entry(pkt_cache_t *pkt_cache, assert(entry); assert(entry->entry_type == PKT_CACHE_PIT_TYPE); - Name name_key = name_key_factory(name); - khiter_t k = kh_get_pkt_cache_name(pkt_cache->index_by_name, &name_key); - assert(k != kh_end(pkt_cache->index_by_name)); - free((Name *)kh_key(pkt_cache->index_by_name, k)); - kh_del(pkt_cache_name, pkt_cache->index_by_name, k); - + _remove_suffix(pkt_cache->prefix_to_suffixes, name_GetContentName(name), + name_GetSegment(name)); pool_put(pkt_cache->entries, entry); WITH_DEBUG({ @@ -158,7 +286,7 @@ void _pkt_cache_add_to_cs(pkt_cache_t *pkt_cache, pkt_cache_entry_t *entry, pkt_cache->cs->num_entries++; - int tail_id = pkt_cache->cs->lru.tail; + int tail_id = (int)(pkt_cache->cs->lru.tail); int result = cs_vft[pkt_cache->cs->type]->add_entry(pkt_cache, entry_id); if (result == LRU_EVICTION) { // Remove tail (already removed from LRU cache) @@ -237,11 +365,11 @@ void pkt_cache_update_cs(pkt_cache_t *pkt_cache, msgbuf_pool_t *msgbuf_pool, } pkt_cache_entry_t *pkt_cache_add_to_pit(pkt_cache_t *pkt_cache, - const msgbuf_t *msgbuf) { + const msgbuf_t *msgbuf, + const Name *name) { assert(pkt_cache); - pkt_cache_entry_t *entry = - pkt_cache_allocate(pkt_cache, msgbuf_get_name(msgbuf)); + pkt_cache_entry_t *entry = pkt_cache_allocate(pkt_cache, name); _pkt_cache_add_to_pit(pkt_cache, entry, msgbuf); return entry; } @@ -276,7 +404,7 @@ void pkt_cache_update_pit(pkt_cache_t *pkt_cache, pkt_cache_entry_t *entry, bool pkt_cache_try_aggregate_in_pit(pkt_cache_t *pkt_cache, pkt_cache_entry_t *entry, - const msgbuf_t *msgbuf) { + const msgbuf_t *msgbuf, const Name *name) { assert(pkt_cache); assert(entry); assert(entry->entry_type == PKT_CACHE_PIT_TYPE); @@ -294,7 +422,7 @@ bool pkt_cache_try_aggregate_in_pit(pkt_cache_t *pkt_cache, if (is_aggregated) pit_entry_ingress_add(pit_entry, connection_id); WITH_DEBUG({ - char *name_str = name_ToString(msgbuf_get_name(msgbuf)); + char *name_str = name_ToString(name); if (is_aggregated) { DEBUG("Interest %s already existing (expiry %lu): aggregate", name_str, entry->expire_ts); @@ -407,7 +535,7 @@ nexthops_t *pkt_cache_on_data(pkt_cache_t *pkt_cache, return NULL; default: - ERROR("Inivalid packet cache content"); + ERROR("Invalid packet cache content"); return NULL; } } @@ -415,7 +543,7 @@ nexthops_t *pkt_cache_on_data(pkt_cache_t *pkt_cache, void pkt_cache_on_interest(pkt_cache_t *pkt_cache, msgbuf_pool_t *msgbuf_pool, off_t msgbuf_id, pkt_cache_verdict_t *verdict, off_t *data_msgbuf_id, pkt_cache_entry_t **entry_ptr, - bool is_serve_from_cs_enabled) { + const Name *name, bool is_serve_from_cs_enabled) { assert(pkt_cache); assert(msgbuf_id_is_valid(msgbuf_id)); @@ -425,8 +553,8 @@ void pkt_cache_on_interest(pkt_cache_t *pkt_cache, msgbuf_pool_t *msgbuf_pool, off_t entry_id; pkt_cache_lookup_t lookup_result; pkt_cache_entry_t *entry = - pkt_cache_lookup(pkt_cache, msgbuf_get_name(msgbuf), msgbuf_pool, - &lookup_result, &entry_id, is_serve_from_cs_enabled); + pkt_cache_lookup(pkt_cache, name, msgbuf_pool, &lookup_result, &entry_id, + is_serve_from_cs_enabled); *entry_ptr = entry; cs_entry_t *cs_entry = NULL; @@ -434,6 +562,9 @@ void pkt_cache_on_interest(pkt_cache_t *pkt_cache, msgbuf_pool_t *msgbuf_pool, bool is_aggregated; switch (lookup_result) { case PKT_CACHE_LU_NONE: + entry = pkt_cache_add_to_pit(pkt_cache, msgbuf, name); + *entry_ptr = entry; + *verdict = PKT_CACHE_VERDICT_FORWARD_INTEREST; break; @@ -448,7 +579,8 @@ void pkt_cache_on_interest(pkt_cache_t *pkt_cache, msgbuf_pool_t *msgbuf_pool, break; case PKT_CACHE_LU_INTEREST_NOT_EXPIRED: - is_aggregated = pkt_cache_try_aggregate_in_pit(pkt_cache, entry, msgbuf); + is_aggregated = + pkt_cache_try_aggregate_in_pit(pkt_cache, entry, msgbuf, name); *verdict = is_aggregated ? PKT_CACHE_VERDICT_AGGREGATE_INTEREST : PKT_CACHE_VERDICT_RETRANSMIT_INTEREST; @@ -477,36 +609,30 @@ void pkt_cache_on_interest(pkt_cache_t *pkt_cache, msgbuf_pool_t *msgbuf_pool, void pkt_cache_cs_clear(pkt_cache_t *pkt_cache) { assert(pkt_cache); - const Name *k_name; - unsigned v_pool_pos; - kh_foreach(pkt_cache->index_by_name, k_name, v_pool_pos, - { - khiter_t k = - kh_get_pkt_cache_name(pkt_cache->index_by_name, k_name); - assert(k != kh_end(pkt_cache->index_by_name)); - - pkt_cache_entry_t *entry = pkt_cache_at(pkt_cache, v_pool_pos); - if (entry->entry_type == PKT_CACHE_CS_TYPE) { - // Remove from hashmap - free((Name *)kh_key(pkt_cache->index_by_name, k)); - kh_del(pkt_cache_name, pkt_cache->index_by_name, k); - - // Remove from pool - pool_put(pkt_cache->entries, entry); - } - }) - - // Re-create CS - cs_clear(pkt_cache->cs); -} + kh_pkt_cache_suffix_t *v_suffixes; + u32 k_suffix; + u32 v_pkt_cache_entry_id; + kh_foreach_value(pkt_cache->prefix_to_suffixes, v_suffixes, { + kh_foreach(v_suffixes, k_suffix, v_pkt_cache_entry_id, { + pkt_cache_entry_t *entry = pkt_cache_at(pkt_cache, v_pkt_cache_entry_id); + if (entry->entry_type == PKT_CACHE_CS_TYPE) { + // Remove from hash table + khiter_t k = kh_get_pkt_cache_suffix(v_suffixes, k_suffix); + assert(k != kh_end(v_suffixes)); + kh_del_pkt_cache_suffix(v_suffixes, k); + + // Remove from pool + pool_put(pkt_cache->entries, entry); + } + }); + }); -size_t pkt_cache_get_size(pkt_cache_t *pkt_cache) { - uint64_t hashmap_size = kh_size(pkt_cache->index_by_name); - return hashmap_size; -} + // Reset cached prefix + pkt_cache->cached_prefix = EMPTY_NAME_BITVECTOR; + pkt_cache->cached_suffixes = NULL; -size_t pkt_cache_get_cs_size(pkt_cache_t *pkt_cache) { - return pkt_cache->cs->num_entries; + // Re-create CS + cs_clear(pkt_cache->cs); } size_t pkt_cache_get_num_cs_stale_entries(pkt_cache_t *pkt_cache) { @@ -531,17 +657,35 @@ int pkt_cache_set_cs_size(pkt_cache_t *pkt_cache, size_t size) { return 0; } +size_t pkt_cache_get_size(pkt_cache_t *pkt_cache) { + return pool_len(pkt_cache->entries); +} + +size_t pkt_cache_get_cs_size(pkt_cache_t *pkt_cache) { + return pkt_cache->cs->num_entries; +} + size_t pkt_cache_get_pit_size(pkt_cache_t *pkt_cache) { - uint64_t hashmap_size = kh_size(pkt_cache->index_by_name); - uint64_t pit_size = hashmap_size - pkt_cache->cs->num_entries; + uint64_t pkt_cache_size = pkt_cache_get_size(pkt_cache); + uint64_t pit_size = pkt_cache_size - pkt_cache_get_cs_size(pkt_cache); return pit_size; } void pkt_cache_log(pkt_cache_t *pkt_cache) { - uint64_t hashmap_size = kh_size(pkt_cache->index_by_name); - uint64_t pit_size = hashmap_size - pkt_cache->cs->num_entries; DEBUG("Packet cache: total size = %lu, PIT size = %lu, CS size = %u", - hashmap_size, pit_size, pkt_cache->cs->num_entries); + pkt_cache_get_size(pkt_cache), pkt_cache_get_pit_size(pkt_cache), + pkt_cache_get_cs_size(pkt_cache)); cs_log(pkt_cache->cs); } + +pkt_cache_stats_t pkt_cache_get_stats(pkt_cache_t *pkt_cache) { + cs_lru_stats_t lru_stats = cs_get_lru_stats(pkt_cache_get_cs(pkt_cache)); + pkt_cache_stats_t stats = { + .n_pit_entries = (uint32_t)pkt_cache_get_pit_size(pkt_cache), + .n_cs_entries = (uint32_t)pkt_cache_get_cs_size(pkt_cache), + .n_lru_evictions = (uint32_t)lru_stats.countLruEvictions, + }; + + return stats; +} diff --git a/hicn-light/src/hicn/core/packet_cache.h b/hicn-light/src/hicn/core/packet_cache.h index ccfc83b97..47926fcdc 100644 --- a/hicn-light/src/hicn/core/packet_cache.h +++ b/hicn-light/src/hicn/core/packet_cache.h @@ -19,7 +19,7 @@ * * The packet cache is a data structure that merges together the PIT and the CS, * to which it holds a reference. - * It contains PIT and CS entries, indexed in a hashtable by hICN packet names. + * It contains PIT and CS entries, indexed in a two-level hash table. * * Each entry has shared fields, e.g. entry type (PIT or CS) and timestamps, * which are used by both PIT and CS entries. In addition, a C union holds @@ -27,41 +27,64 @@ * * Having a single entry that can hold PIT or CS entries allows to reduce * the number of lookups. + * + * A prefix hash table <prefix, suffix_hashtable> stores the suffixes associated + * to each prefix, where each value in the map points to a separate hash + * table <suffix, packet_cache_reference> that can be used to retrieved the + * packet cache entry. + * When an interest/data packet is received, the prefix and the associated + * suffixes are saved; if the next packet cache operation involves the same + * prefix, no additional lookups in the prefix hash hashtable are needed. */ #ifndef HICNLIGHT_PACKET_CACHE_H #define HICNLIGHT_PACKET_CACHE_H +#include <hicn/util/khash.h> #include "content_store.h" #include "pit.h" #include "msgbuf_pool.h" -#include "../base/khash.h" #include "../content_store/lru.h" #define DEFAULT_PKT_CACHE_SIZE 2048 typedef enum { PKT_CACHE_PIT_TYPE, PKT_CACHE_CS_TYPE } pkt_cache_entry_type_t; -/** - * @brief Return a Name that can be used as key for hash table lookups. - * The returned Name is a copy of the input one but it is "memsetted" - * to ensure successful hash calculation. - */ -static inline Name name_key_factory(const Name *name) { - NameBitvector *content_name = name_GetContentName(name); +#define foreach_kh_verdict \ + _(FORWARD_INTEREST) \ + _(AGGREGATE_INTEREST) \ + _(RETRANSMIT_INTEREST) \ + _(FORWARD_DATA) \ + _(INTEREST_EXPIRED_FORWARD_INTEREST) \ + _(DATA_EXPIRED_FORWARD_INTEREST) \ + _(STORE_DATA) \ + _(CLEAR_DATA) \ + _(UPDATE_DATA) \ + _(IGNORE_DATA) \ + _(ERROR) - Name name_key; - memset(&name_key, 0, sizeof(Name)); +typedef enum { +#define _(x) PKT_CACHE_VERDICT_##x, + foreach_kh_verdict +#undef _ +} pkt_cache_verdict_t; - name_key.content_name = *content_name; - name_key.segment = name_GetSegment(name); - name_key.name_hash = name_HashCode(name); +#define foreach_kh_lookup \ + _(INTEREST_NOT_EXPIRED) \ + _(INTEREST_EXPIRED) \ + _(DATA_NOT_EXPIRED) \ + _(DATA_EXPIRED) \ + _(NONE) - return name_key; -} +typedef enum { +#define _(x) PKT_CACHE_LU_##x, + foreach_kh_lookup +#undef _ +} pkt_cache_lookup_t; -KHASH_INIT(pkt_cache_name, const Name *, unsigned, 1, name_HashCode, - name_Equals); +KHASH_MAP_INIT_INT(pkt_cache_suffix, unsigned); +KHASH_INIT(pkt_cache_prefix, const NameBitvector *, kh_pkt_cache_suffix_t *, 1, + nameBitvector_GetHash32, nameBitvector_Equals); typedef struct { pkt_cache_entry_type_t entry_type; @@ -82,7 +105,12 @@ typedef struct { pit_t *pit; cs_t *cs; pkt_cache_entry_t *entries; - kh_pkt_cache_name_t *index_by_name; + kh_pkt_cache_prefix_t *prefix_to_suffixes; + + // Cached prefix info to avoid double lookups, + // used for both single interest speculation and interest manifest + NameBitvector cached_prefix; + kh_pkt_cache_suffix_t *cached_suffixes; } pkt_cache_t; /** @@ -92,7 +120,6 @@ typedef struct { */ pkt_cache_t *pkt_cache_create(size_t cs_size); -#define _pc_var(x) _pkt_cache_##x /** * @brief Add an entry with the specified name to the packet cache. * @@ -101,29 +128,7 @@ pkt_cache_t *pkt_cache_create(size_t cs_size); * allocated one from the msgbuf pool. * * @param[in] name Name to use */ -static inline pkt_cache_entry_t *pkt_cache_allocate( - const pkt_cache_t *pkt_cache, const Name *name) { - pkt_cache_entry_t *entry = NULL; - pool_get(pkt_cache->entries, entry); - assert(entry); - - off_t id = entry - pkt_cache->entries; - int res; - - // Generate the key (starting from the name) to use in the name hash table - NameBitvector *nb = name_GetContentName(name); - Name *name_copy = (Name *)calloc(1, sizeof(Name)); - name_copy->content_name = *nb; - name_copy->segment = name_GetSegment(name); - name_copy->name_hash = name_HashCode(name); - - // Add in name hash table - khiter_t k = kh_put_pkt_cache_name(pkt_cache->index_by_name, name_copy, &res); - assert(res != -1); - kh_value(pkt_cache->index_by_name, k) = id; - - return entry; -} +pkt_cache_entry_t *pkt_cache_allocate(pkt_cache_t *pkt_cache, const Name *name); /** * @brief Free a packet cache data structure. @@ -189,28 +194,6 @@ size_t pkt_cache_get_cs_size(pkt_cache_t *pkt_cache); */ size_t pkt_cache_get_pit_size(pkt_cache_t *pkt_cache); -typedef enum { - PKT_CACHE_LU_INTEREST_NOT_EXPIRED, - PKT_CACHE_LU_INTEREST_EXPIRED, - PKT_CACHE_LU_DATA_NOT_EXPIRED, - PKT_CACHE_LU_DATA_EXPIRED, - PKT_CACHE_LU_NONE -} pkt_cache_lookup_t; - -typedef enum { - PKT_CACHE_VERDICT_FORWARD_INTEREST, - PKT_CACHE_VERDICT_AGGREGATE_INTEREST, - PKT_CACHE_VERDICT_RETRANSMIT_INTEREST, - PKT_CACHE_VERDICT_FORWARD_DATA, - PKT_CACHE_VERDICT_INTEREST_EXPIRED_FORWARD_INTEREST, - PKT_CACHE_VERDICT_DATA_EXPIRED_FORWARD_INTEREST, - PKT_CACHE_VERDICT_STORE_DATA, - PKT_CACHE_VERDICT_CLEAR_DATA, - PKT_CACHE_VERDICT_UPDATE_DATA, - PKT_CACHE_VERDICT_IGNORE_DATA, - PKT_CACHE_VERDICT_ERROR -} pkt_cache_verdict_t; - #define pkt_cache_entry_get_create_ts(E) ((E)->create_ts) #define pkt_cache_entry_get_expire_ts(E) ((E)->expire_ts) #define pkt_cache_entry_set_expire_ts(E, EXPIRY_TIME) \ @@ -241,7 +224,7 @@ pkt_cache_entry_t *pkt_cache_lookup(pkt_cache_t *pkt_cache, const Name *name, bool is_serve_from_cs_enabled); /** - * @brief Clear the content of the CS. + * @brief Clear the content of the CS (PIT entries are left unmodified). * * @param pkt_cache Pointer to the packet cache data structure to use */ @@ -254,6 +237,8 @@ void pkt_cache_cs_clear(pkt_cache_t *pkt_cache); */ void pkt_cache_log(pkt_cache_t *pkt_cache); +pkt_cache_stats_t pkt_cache_get_stats(pkt_cache_t *pkt_cache); + // TODO(eloparco): To implement void pkt_cache_print(const pkt_cache_t *pkt_cache); @@ -320,10 +305,13 @@ void pkt_cache_cs_to_pit(pkt_cache_t *pkt_cache, pkt_cache_entry_t *entry, * @param[in] pkt_cache Pointer to the packet cache data structure to use * @param[in] msgbuf Pointer to the msgbuf associated with the PIT entry to * insert + * @param[in] name Interest name to use; in case of aggregated interests, it is + * different from the name stored in the msgbuf * @return pkt_cache_entry_t* Pointer to the packet cache (PIT) entry created */ pkt_cache_entry_t *pkt_cache_add_to_pit(pkt_cache_t *pkt_cache, - const msgbuf_t *msgbuf); + const msgbuf_t *msgbuf, + const Name *name); /** * @brief Add CS entry to the packet cache. @@ -374,6 +362,8 @@ void pkt_cache_update_cs(pkt_cache_t *pkt_cache, msgbuf_pool_t *msgbuf_pool, * @param[in, out] entry Pointer to the PIT entry to update * @param[in] msgbuf Pointer to the msgbuf associated with the PIT entry to * update + * @param[in] name Interest name to use; in case of aggregated interests, it is + * different from the name stored in the msgbuf * @return true If aggregation (interest sent from a connection not stored in * the PIT entry) * @return false If retransmission (interest sent from a connection already @@ -381,7 +371,23 @@ void pkt_cache_update_cs(pkt_cache_t *pkt_cache, msgbuf_pool_t *msgbuf_pool, */ bool pkt_cache_try_aggregate_in_pit(pkt_cache_t *pkt_cache, pkt_cache_entry_t *entry, - const msgbuf_t *msgbuf); + const msgbuf_t *msgbuf, const Name *name); + +/** + * @brief Cache prefix info (prefix + associated suffixes) to speed up lookups. + * + * @param[in] pkt_cache Pointer to the packet cache data structure to use + * @param[in] prefix Name prefix to cache + */ +void pkt_cache_save_suffixes_for_prefix(pkt_cache_t *pkt_cache, + const NameBitvector *prefix); + +/** + * @brief Reset cached prefix info to force double lookups. + * + * @param[in] pkt_cache Pointer to the packet cache data structure to use + */ +void pkt_cache_reset_suffixes_for_prefix(pkt_cache_t *pkt_cache); /************ Handle data/interest packets received *******/ @@ -413,7 +419,24 @@ nexthops_t *pkt_cache_on_data(pkt_cache_t *pkt_cache, void pkt_cache_on_interest(pkt_cache_t *pkt_cache, msgbuf_pool_t *msgbuf_pool, off_t msgbuf_id, pkt_cache_verdict_t *verdict, off_t *data_msgbuf_id, pkt_cache_entry_t **entry_ptr, - bool is_serve_from_cs_enabled); + const Name *name, bool is_serve_from_cs_enabled); + +/********* Low-level operations on the hash table *********/ +#ifdef WITH_TESTS +unsigned __get_suffix(kh_pkt_cache_suffix_t *suffixes, uint32_t suffix, + int *rc); +unsigned _get_suffix(kh_pkt_cache_prefix_t *prefixes, + const NameBitvector *prefix, uint32_t suffix, int *rc); +void __add_suffix(kh_pkt_cache_suffix_t *suffixes, uint32_t suffix, + unsigned val); +void _add_suffix(kh_pkt_cache_prefix_t *prefixes, const NameBitvector *prefix, + uint32_t suffix, unsigned val); +void _remove_suffix(kh_pkt_cache_prefix_t *prefixes, + const NameBitvector *prefix, uint32_t suffix); +void _prefix_map_free(kh_pkt_cache_prefix_t *prefix_to_suffixes); +kh_pkt_cache_suffix_t *_get_suffixes(kh_pkt_cache_prefix_t *prefix_to_suffixes, + const NameBitvector *prefix); +#endif /************** Content Store *****************************/ diff --git a/hicn-light/src/hicn/core/policy_stats.h b/hicn-light/src/hicn/core/policy_stats.h index fa12b51cb..aee68e515 100644 --- a/hicn-light/src/hicn/core/policy_stats.h +++ b/hicn-light/src/hicn/core/policy_stats.h @@ -5,7 +5,6 @@ #ifdef WITH_POLICY_STATS #include <hicn/policy.h> -#include "../base/loop.h" typedef struct policy_stats_mgr_s { void* forwarder; diff --git a/hicn-light/src/hicn/core/subscription.c b/hicn-light/src/hicn/core/subscription.c index 0c4949f26..ad4006531 100644 --- a/hicn-light/src/hicn/core/subscription.c +++ b/hicn-light/src/hicn/core/subscription.c @@ -3,7 +3,7 @@ */ #include "subscription.h" -#include <hicn/base/vector.h> +#include <hicn/util/vector.h> #include <hicn/util/log.h> /*----------------------------------------------------------------------------* diff --git a/hicn-light/src/hicn/io/base.c b/hicn-light/src/hicn/io/base.c index 71d10021e..cd7362956 100644 --- a/hicn-light/src/hicn/io/base.c +++ b/hicn-light/src/hicn/io/base.c @@ -42,7 +42,7 @@ ssize_t io_read_single_fd(int fd, msgbuf_t *msgbuf, address_t *address) { return -1; } - msgbuf->length = n; + msgbuf->length = (unsigned int)n; *address = ADDRESS_ANY(AF_UNSPEC, 0); // XXX placeholder, see hicn.c } @@ -55,7 +55,7 @@ ssize_t io_read_single_socket(int fd, msgbuf_t *msgbuf, address_t *address) { uint8_t *packet = msgbuf_get_packet(msgbuf); ssize_t n = recvfrom(fd, packet, MTU, 0, (struct sockaddr *)sa, &sa_len); - msgbuf->length = n; + msgbuf->length = (unsigned int)n; return n; } @@ -114,21 +114,6 @@ ssize_t io_read_batch_socket(int fd, msgbuf_t **msgbuf, address_t **address, struct mmsghdr *msg = &msghdr[i]; msgbuf[i]->length = msg->msg_len; - /* - * As is, the address we put in the array has uninitialized - * memory in it: - * *address[i] = *(address_t*)msg->msg_hdr.msg_name; - * - * This can be confirmed by testing with the following - * memset which removes the valgrind errors: - * memset(address[i], 0, sizeof(address_t)); - * - * The solution is to copy only the part which we know is - * initialized (we have compatible types, since the destination, an - * address_t, is effectively a struct sockaddr_storage). We might - * eventually provide a helper for this to avoid similar mistakes. - */ - //*address[i] = *(address_t*)msg->msg_hdr.msg_name; memcpy(address[i], msg->msg_hdr.msg_name, msg->msg_hdr.msg_namelen); } break; diff --git a/hicn-light/src/hicn/io/hicn.c b/hicn-light/src/hicn/io/hicn.c index 8b4ad2e00..d019a49c1 100644 --- a/hicn-light/src/hicn/io/hicn.c +++ b/hicn-light/src/hicn/io/hicn.c @@ -401,12 +401,10 @@ static void connection_hicn_finalize(connection_t *connection) { return; } -static bool connection_hicn_flush(const connection_t *connection) { - return false; -} +static bool connection_hicn_flush(connection_t *connection) { return false; } -static bool connection_hicn_send(const connection_t *connection, - msgbuf_t *msgbuf, bool queue) { +static bool connection_hicn_send(connection_t *connection, msgbuf_t *msgbuf, + bool queue) { assert(connection); /* msgbuf can be NULL */ diff --git a/hicn-light/src/hicn/io/tcp.c b/hicn-light/src/hicn/io/tcp.c index 69ad32d16..50591c3fc 100644 --- a/hicn-light/src/hicn/io/tcp.c +++ b/hicn-light/src/hicn/io/tcp.c @@ -287,9 +287,7 @@ connection_tcp_sendv(connnection_t * connection, struct iovec * iov, } #endif -static bool connection_tcp_flush(const connection_t *connection) { - return true; -} +static bool connection_tcp_flush(connection_t *connection) { return true; } /** * @function streamConnection_Send @@ -303,8 +301,8 @@ static bool connection_tcp_flush(const connection_t *connection) { */ // XXX address not used anywhere // XXX too much repeated code with sendv here -static bool connection_tcp_send(const connection_t *connection, - msgbuf_t *msgbuf, bool queue) { +static bool connection_tcp_send(connection_t *connection, msgbuf_t *msgbuf, + bool queue) { assert(connection); assert(msgbuf); diff --git a/hicn-light/src/hicn/io/udp.c b/hicn-light/src/hicn/io/udp.c index 3301e2178..149d53aea 100644 --- a/hicn-light/src/hicn/io/udp.c +++ b/hicn-light/src/hicn/io/udp.c @@ -49,10 +49,9 @@ #include <hicn/util/log.h> #include <hicn/util/sstrncpy.h> +#include <hicn/util/ring.h> #include "base.h" -#include "../base/loop.h" -#include "../base/ring.h" #include "../core/address_pair.h" #include "../core/connection.h" #include "../core/connection_vft.h" @@ -344,7 +343,7 @@ static void connection_udp_finalize(connection_t *connection) { ring_free(data->ring); } -static bool connection_udp_flush(const connection_t *connection) { +static bool connection_udp_flush(connection_t *connection) { #ifdef __linux__ int retry = 0; off_t msgbuf_id = 0; @@ -375,9 +374,16 @@ SEND: msgbuf_t *msgbuf = msgbuf_pool_at(msgbuf_pool, msgbuf_id); // update path label - if (msgbuf_get_type(msgbuf) == MSGBUF_TYPE_DATA) + if (msgbuf_get_type(msgbuf) == MSGBUF_TYPE_DATA) { msgbuf_update_pathlabel(msgbuf, connection_get_id(connection)); + connection->stats.data.tx_pkts++; + connection->stats.data.tx_bytes += msgbuf_get_len(msgbuf); + } else { + connection->stats.interests.tx_pkts++; + connection->stats.interests.tx_bytes += msgbuf_get_len(msgbuf); + } + data->iovecs[i].iov_base = msgbuf_get_packet(msgbuf); data->iovecs[i].iov_len = msgbuf_get_len(msgbuf); cpt++; @@ -430,8 +436,8 @@ SENDMMSG: * @param dummy is ignored. A udp connection has only one peer. * @return <#return#> */ -static bool connection_udp_send(const connection_t *connection, - msgbuf_t *msgbuf, bool queue) { +static bool connection_udp_send(connection_t *connection, msgbuf_t *msgbuf, + bool queue) { assert(connection); assert(msgbuf); @@ -454,9 +460,16 @@ static bool connection_udp_send(const connection_t *connection, #endif /* __linux__ */ /* Send one */ // update the path label befor send the packet - if (msgbuf_get_type(msgbuf) == MSGBUF_TYPE_DATA) + if (msgbuf_get_type(msgbuf) == MSGBUF_TYPE_DATA) { msgbuf_update_pathlabel(msgbuf, connection_get_id(connection)); + connection->stats.data.tx_pkts++; + connection->stats.data.tx_bytes += msgbuf_get_len(msgbuf); + } else { + connection->stats.interests.tx_pkts++; + connection->stats.interests.tx_bytes += msgbuf_get_len(msgbuf); + } + ssize_t writeLength = write(connection->fd, msgbuf_get_packet(msgbuf), msgbuf_get_len(msgbuf)); diff --git a/hicn-light/src/hicn/strategies/probe_generator.c b/hicn-light/src/hicn/strategies/probe_generator.c index 439de0a12..bc141e518 100644 --- a/hicn-light/src/hicn/strategies/probe_generator.c +++ b/hicn-light/src/hicn/strategies/probe_generator.c @@ -78,7 +78,7 @@ int generate_probe(probe_generator_t *pg, const msgbuf_t *msgbuf, const forwarder_t *forwarder, nexthop_t nexthop) { msgbuf_pool_t *msgbuf_pool = forwarder_get_msgbuf_pool(forwarder); connection_table_t *table = forwarder_get_connection_table(forwarder); - const connection_t *conn = connection_table_get_by_id(table, nexthop); + connection_t *conn = connection_table_get_by_id(table, nexthop); if (!conn) return -1; msgbuf_t *probe; diff --git a/hicn-light/src/hicn/strategies/probe_generator.h b/hicn-light/src/hicn/strategies/probe_generator.h index 26d6a3a22..7a9f3a58a 100644 --- a/hicn-light/src/hicn/strategies/probe_generator.h +++ b/hicn-light/src/hicn/strategies/probe_generator.h @@ -16,7 +16,7 @@ #ifndef HICNLIGHT_PROBE_GENERATOR #define HICNLIGHT_PROBE_GENERATOR -#include "../base/khash.h" +#include <hicn/util/khash.h> #include <hicn/core/ticks.h> #include <hicn/core/msgbuf.h> diff --git a/hicn-light/src/hicn/test/CMakeLists.txt b/hicn-light/src/hicn/test/CMakeLists.txt index 0ded4253d..65e216c1e 100644 --- a/hicn-light/src/hicn/test/CMakeLists.txt +++ b/hicn-light/src/hicn/test/CMakeLists.txt @@ -13,6 +13,7 @@ list(APPEND TESTS_SRC test-ctrl.cc test-ring.cc test-vector.cc + test-interest_manifest.cc test-msgbuf_pool.cc test-nexthops.cc test-connection_table.cc diff --git a/hicn-light/src/hicn/test/test-bitmap.cc b/hicn-light/src/hicn/test/test-bitmap.cc index f9cd4024f..1fd21a1bb 100644 --- a/hicn-light/src/hicn/test/test-bitmap.cc +++ b/hicn-light/src/hicn/test/test-bitmap.cc @@ -25,7 +25,7 @@ extern "C" { #define WITH_TESTS -#include <hicn/base/bitmap.h> +#include <hicn/util/bitmap.h> } #define DEFAULT_SIZE 10 diff --git a/hicn-light/src/hicn/test/test-connection_table.cc b/hicn-light/src/hicn/test/test-connection_table.cc index 6bbf478e2..d17de7c2c 100644 --- a/hicn-light/src/hicn/test/test-connection_table.cc +++ b/hicn-light/src/hicn/test/test-connection_table.cc @@ -35,7 +35,7 @@ extern "C" { class ConnectionTableTest : public ::testing::Test { protected: ConnectionTableTest() { - log_conf.log_level = LOG_INFO; + log_conf.log_level = LOG_WARN; conn_table_ = connection_table_create(); pair_ = @@ -164,6 +164,10 @@ TEST_F(ConnectionTableTest, RemoveConnection) { } TEST_F(ConnectionTableTest, PrintTable) { + // Set verbose log level + int old_log_level = log_conf.log_level; + log_conf.log_level = LOG_INFO; + connection_ = connection_table_allocate(conn_table_, &pair_, CONNECTION_NAME); connection_->type = FACE_TYPE_TCP; @@ -184,6 +188,8 @@ TEST_F(ConnectionTableTest, PrintTable) { EXPECT_THAT(std_out, testing::HasSubstr("127.0.0.1:2")); EXPECT_THAT(std_out, testing::HasSubstr("127.0.0.1:3")); EXPECT_THAT(std_out, testing::HasSubstr("127.0.0.1:4")); + + log_conf.log_level = old_log_level; // Restore old log level } TEST_F(ConnectionTableTest, AddMultipleConnections) { @@ -248,3 +254,43 @@ TEST_F(ConnectionTableTest, Iterate) { EXPECT_THAT(std_out, testing::HasSubstr("127.0.0.1:3")); EXPECT_THAT(std_out, testing::HasSubstr("127.0.0.1:4")); } + +TEST_F(ConnectionTableTest, GenerateConnName) { + char conn_name[SYMBOLIC_NAME_LEN]; + int rc = connection_table_get_random_name(conn_table_, conn_name); + EXPECT_EQ(rc, 0); + + connection_ = connection_table_allocate(conn_table_, &pair_, conn_name); + connection_->type = FACE_TYPE_TCP; + connection_->pair = pair_; + + char conn_name2[SYMBOLIC_NAME_LEN]; + rc = connection_table_get_random_name(conn_table_, conn_name2); + EXPECT_EQ(rc, 0); + EXPECT_NE(strncmp(conn_name, conn_name2, SYMBOLIC_NAME_LEN), 0); +} + +TEST_F(ConnectionTableTest, GenerateConnNameExhaustion) { + char conn_name[SYMBOLIC_NAME_LEN]; + bool unable_to_allocate = false; + + // Force name exhaustion + int i, n_connections = 1 + USHRT_MAX; + for (int i = 0; i <= n_connections; i++) { + int rc = connection_table_get_random_name(conn_table_, conn_name); + if (rc < 0) { + unable_to_allocate = true; + break; + } + + address_pair_t pair = + address_pair_factory(_ADDRESS4_LOCALHOST(1), _ADDRESS4_LOCALHOST(i)); + connection_t *conn = + connection_table_allocate(conn_table_, &pair, conn_name); + memset(conn, 0, sizeof(connection_t)); + conn->type = FACE_TYPE_TCP; + conn->pair = pair; + } + + EXPECT_TRUE(unable_to_allocate); +}
\ No newline at end of file diff --git a/hicn-light/src/hicn/test/test-hash.cc b/hicn-light/src/hicn/test/test-hash.cc index 2b72e194a..3b03a08a6 100644 --- a/hicn-light/src/hicn/test/test-hash.cc +++ b/hicn-light/src/hicn/test/test-hash.cc @@ -22,14 +22,18 @@ #include <sys/socket.h> #include <sys/un.h> #include <unistd.h> -// #include <hicn/transport/utils/hash.h> +#include <unordered_set> +#include <hicn/test/test-utils.h> extern "C" { -#include <hicn/base/hash.h> +#include <hicn/util/hash.h> #include <hicn/core/address_pair.h> #include <hicn/core/listener.h> } +static constexpr uint32_t init_val = 2166136261UL; +static constexpr int N_HASHES = 50000; + TEST(HashTest, MultipleHashesForSameAddrPair) { address_pair_t pair = address_pair_factory(_ADDRESS4_LOCALHOST(1), _ADDRESS4_LOCALHOST(2)); @@ -108,16 +112,106 @@ TEST(HashTest, SameListenerKeys) { } TEST(HashTest, Collisions) { - uint32_t init_val = 2166136261UL; - (void)init_val; - - std::map<u32, uint32_t> hashes; + std::unordered_set<uint32_t> hashes; + int n_collisions = 0; for (int i = 0; i < 50000; i++) { uint32_t seg = i; - // u32 h = utils::hash::fnv32_buf (&seg, sizeof (seg)); - // u32 h = cumulative_hash32 (&seg, sizeof (seg), init_val); + // u32 h = utils::hash::fnv32_buf(&seg, sizeof(seg)); + // u32 h = cumulative_hash32(&seg, sizeof(uint32_t), init_val); u32 h = hash(&seg, sizeof(seg)); - EXPECT_FALSE(hashes.find(h) != hashes.end()) << seg << " - " << hashes[h]; - hashes[h] = seg; + + if (hashes.find(h) != hashes.end()) n_collisions++; + hashes.insert(h); } + EXPECT_EQ(n_collisions, 0); +} + +/*** Compare FNV with Jenkins ***/ + +typedef struct { + uint32_t data[6]; +} small_struct_t; // Same size as 'NameBitvector' + +typedef struct { + uint64_t data[32]; +} big_struct_t; // Same size as 'address_pair_t' + +TEST(HashTest, PerformanceComparisonSmallStruct) { + small_struct_t small_struct; + + // FNV + auto time_fnv = get_execution_time([&]() { + for (int i = 0; i < N_HASHES; i++) { + small_struct.data[0] = i; + cumulative_hash32(&small_struct, sizeof(small_struct_t), init_val); + } + }); + + // Jenkins + auto time_jenkins = get_execution_time([&]() { + for (int i = 0; i < N_HASHES; i++) { + small_struct.data[0] = i; + hash(&small_struct, sizeof(small_struct_t)); + } + }); + + std::cout << "Small struct (size = " << sizeof(small_struct_t) << " bytes)\n"; + std::cout << "FNV: " << time_fnv << "ms\n"; + std::cout << "Jenkins: " << time_jenkins << "ms\n"; +} + +TEST(HashTest, PerformanceComparisonBigStruct) { + big_struct_t big_struct; + + // FNV + auto time_fnv = get_execution_time([&]() { + for (int i = 0; i < N_HASHES; i++) { + big_struct.data[0] = i; + cumulative_hash32(&big_struct, sizeof(big_struct_t), init_val); + } + }); + + // Jenkins + auto time_jenkins = get_execution_time([&]() { + for (int i = 0; i < N_HASHES; i++) { + big_struct.data[0] = i; + hash(&big_struct, sizeof(big_struct_t)); + } + }); + + std::cout << "Big struct (size = " << sizeof(big_struct_t) << " bytes)\n"; + std::cout << "FNV: " << time_fnv << "ms\n"; + std::cout << "Jenkins: " << time_jenkins << "ms\n"; +} + +TEST(HashTest, CollisionsComparison) { + small_struct_t small_struct = {0}; + std::unordered_set<uint32_t> hashes; + int n_collisions_fnv = 0, n_collisions_jenkins = 0, n_collisions_murmur = 0, + n_collisions_xxhash = 0; + + // FNV + for (int i = 0; i < 10 * N_HASHES; i++) { + small_struct.data[0] = i; + uint32_t h = + cumulative_hash32(&small_struct, sizeof(small_struct_t), init_val); + + if (hashes.find(h) != hashes.end()) n_collisions_fnv++; + hashes.insert(h); + } + + hashes.clear(); + + // Jenkins + for (int i = 0; i < 10 * N_HASHES; i++) { + small_struct.data[0] = i; + uint32_t h = hash(&small_struct, sizeof(small_struct_t)); + + if (hashes.find(h) != hashes.end()) n_collisions_jenkins++; + hashes.insert(h); + } + + std::cout << "Small struct (size = " << sizeof(small_struct_t) << " bytes)\n"; + std::cout << "FNV: " << n_collisions_fnv << " collision/s\n"; + std::cout << "Jenkins: " << n_collisions_jenkins << " collision/s\n"; }
\ No newline at end of file diff --git a/hicn-light/src/hicn/test/test-interest_manifest.cc b/hicn-light/src/hicn/test/test-interest_manifest.cc new file mode 100644 index 000000000..6408a3f2a --- /dev/null +++ b/hicn-light/src/hicn/test/test-interest_manifest.cc @@ -0,0 +1,79 @@ +/* + * 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. + */ + +#include <gtest/gtest.h> + +extern "C" { +#include <hicn/core/interest_manifest.h> +} + +static constexpr size_t WORD_SIZE = 32; + +class InterestManifestTest : public ::testing::Test { + protected: + InterestManifestTest() {} + virtual ~InterestManifestTest() {} +}; + +TEST_F(InterestManifestTest, OneWordBitmapUpdate) { + u32 initial_bitmap[1]; + u32 curr_bitmap[1] = {0}; + initial_bitmap[0] = 0x00000b07; // 000000000000000000000101100000111 + + // Consume first 4 'one' bits (i.e. suffixes), reaching position 9 + int pos = 0, max_suffixes = 4; + pos = interest_manifest_update_bitmap(initial_bitmap, curr_bitmap, pos, + WORD_SIZE, max_suffixes); + EXPECT_EQ(pos, 9); + EXPECT_EQ(curr_bitmap[0], 0x00000107); + + // Consume the remaining 2 'one' bits, reaching end of bitmap + u32 curr_bitmap2[1] = {0}; + pos = interest_manifest_update_bitmap(initial_bitmap, curr_bitmap2, pos, + WORD_SIZE, max_suffixes); + EXPECT_EQ(pos, WORD_SIZE); + EXPECT_EQ(curr_bitmap2[0], 0x00000a00); + + // Consume all suffixes at once + u32 curr_bitmap3[1] = {0}; + max_suffixes = 16; + pos = interest_manifest_update_bitmap(initial_bitmap, curr_bitmap3, 0, + WORD_SIZE, max_suffixes); + EXPECT_EQ(pos, WORD_SIZE); + EXPECT_EQ(curr_bitmap3[0], initial_bitmap[0]); +} + +TEST_F(InterestManifestTest, TwoWordBitmapUpdate) { + u32 initial_bitmap[2]; + initial_bitmap[0] = 0x00000b07; + initial_bitmap[1] = 0x00000b07; + // -> 100000000000000000000101100000111000000000000000000000101100000111 + + int expected_pos[] = {34, 64}; + u32 expected_bitmap[][2] = {{0x00000b07, 0x00000003}, {0x0, 0x00000b04}}; + + // Loop to consume all suffixes + int pos = 0, max_suffixes = 8, i = 0, len = WORD_SIZE * 2; + while (pos != len) { + u32 curr_bitmap[2] = {0}; + pos = interest_manifest_update_bitmap(initial_bitmap, curr_bitmap, pos, len, + max_suffixes); + + EXPECT_EQ(pos, expected_pos[i]); + EXPECT_EQ(curr_bitmap[0], expected_bitmap[i][0]); + EXPECT_EQ(curr_bitmap[1], expected_bitmap[i][1]); + i++; + } +}
\ No newline at end of file diff --git a/hicn-light/src/hicn/test/test-khash.cc b/hicn-light/src/hicn/test/test-khash.cc index 4fcb48c31..f437f8858 100644 --- a/hicn-light/src/hicn/test/test-khash.cc +++ b/hicn-light/src/hicn/test/test-khash.cc @@ -24,7 +24,7 @@ #include <netinet/in.h> extern "C" { -#include <hicn/base/khash.h> +#include <hicn/util/khash.h> } KHASH_MAP_INIT_INT(int, unsigned char) diff --git a/hicn-light/src/hicn/test/test-msgbuf_pool.cc b/hicn-light/src/hicn/test/test-msgbuf_pool.cc index 5537aa216..e9c8e6424 100644 --- a/hicn-light/src/hicn/test/test-msgbuf_pool.cc +++ b/hicn-light/src/hicn/test/test-msgbuf_pool.cc @@ -26,7 +26,7 @@ extern "C" { #define WITH_TESTS #include <hicn/core/msgbuf_pool.h> -#include <hicn/base/pool.h> +#include <hicn/util/pool.h> } class MsgbufPoolTest : public ::testing::Test { diff --git a/hicn-light/src/hicn/test/test-packet_cache.cc b/hicn-light/src/hicn/test/test-packet_cache.cc index bb24daeb8..0b4b214f0 100644 --- a/hicn-light/src/hicn/test/test-packet_cache.cc +++ b/hicn-light/src/hicn/test/test-packet_cache.cc @@ -15,23 +15,26 @@ #include <gtest/gtest.h> -#include <thread> #include <optional> +#include <random> +#include <hicn/test/test-utils.h> extern "C" { #define WITH_TESTS #include <hicn/core/packet_cache.h> } -const unsigned CS_SIZE = 100; -const unsigned CONN_ID = 0; -const unsigned CONN_ID_2 = 1; -const unsigned MSGBUF_ID = 0; -const unsigned MSGBUF_ID_2 = 1; -const unsigned MSGBUF_ID_3 = 2; -const unsigned FIVE_SECONDS = 5000; -const unsigned IPV4_LEN = 32; -const unsigned IPV6_LEN = 128; +static constexpr unsigned CS_SIZE = 100; +static constexpr unsigned CONN_ID = 0; +static constexpr unsigned CONN_ID_2 = 1; +static constexpr unsigned MSGBUF_ID = 0; +static constexpr unsigned MSGBUF_ID_2 = 1; +static constexpr unsigned MSGBUF_ID_3 = 2; +static constexpr unsigned FIVE_SECONDS = 5000; +static constexpr unsigned IPV4_LEN = 32; +static constexpr unsigned IPV6_LEN = 128; + +static constexpr int N_OPS = 50000; class PacketCacheTest : public ::testing::Test { protected: @@ -40,33 +43,78 @@ class PacketCacheTest : public ::testing::Test { name = (Name *)malloc(sizeof(Name)); name_CreateFromAddress(name, AF_INET, IPV4_ANY, IPV4_LEN); msgbuf_pool = msgbuf_pool_create(); + msgbuf = msgbuf_create(msgbuf_pool, CONN_ID, name); } + virtual ~PacketCacheTest() { - pkt_cache_free(pkt_cache); + free(name); msgbuf_pool_free(msgbuf_pool); + pkt_cache_free(pkt_cache); + } + + msgbuf_t *msgbuf_create(msgbuf_pool_t *msgbuf_pool, unsigned conn_id, + Name *name, + std::optional<Ticks> lifetime = FIVE_SECONDS) { + msgbuf_t *msgbuf; + msgbuf_pool_get(msgbuf_pool, &msgbuf); + + msgbuf->connection_id = conn_id; + name_Copy(name, msgbuf_get_name(msgbuf)); + hicn_packet_init_header(HF_INET6_TCP, + (hicn_header_t *)msgbuf_get_packet(msgbuf)); + msgbuf_set_interest_lifetime(msgbuf, *lifetime); + + return msgbuf; + } + + Name get_name_from_prefix(const char *prefix_str) { + ip_address_t prefix; + inet_pton(AF_INET6, prefix_str, (struct in6_addr *)&prefix); + + Name name; + name_CreateFromAddress(&name, AF_INET6, prefix, IPV6_LEN); + + return name; } pkt_cache_t *pkt_cache; pkt_cache_entry_t *entry = nullptr; msgbuf_pool_t *msgbuf_pool; Name *name; -}; - -msgbuf_t *msgbuf_factory(msgbuf_pool_t *msgbuf_pool, unsigned conn_id, - Name *name, - std::optional<Ticks> lifetime = FIVE_SECONDS) { msgbuf_t *msgbuf; - msgbuf_pool_get(msgbuf_pool, &msgbuf); - - msgbuf->connection_id = conn_id; - name_Copy(name, msgbuf_get_name(msgbuf)); - hicn_packet_init_header(HF_INET6_TCP, - (hicn_header_t *)msgbuf_get_packet(msgbuf)); - // Same as 'msgbuf_set_data_expiry_time', - // it would write in the same field - msgbuf_set_interest_lifetime(msgbuf, *lifetime); +}; - return msgbuf; +TEST_F(PacketCacheTest, LowLevelOperations) { + int rc; + kh_pkt_cache_prefix_t *prefix_to_suffixes = kh_init_pkt_cache_prefix(); + NameBitvector *prefix = name_GetContentName(name); + _add_suffix(prefix_to_suffixes, prefix, 1, 11); + _add_suffix(prefix_to_suffixes, prefix, 2, 22); + + unsigned id = _get_suffix(prefix_to_suffixes, prefix, 1, &rc); + EXPECT_EQ(rc, KH_FOUND); + EXPECT_EQ(id, 11); + + id = _get_suffix(prefix_to_suffixes, prefix, 2, &rc); + EXPECT_EQ(rc, KH_FOUND); + EXPECT_EQ(id, 22); + + id = _get_suffix(prefix_to_suffixes, prefix, 5, &rc); + EXPECT_EQ(rc, KH_NOT_FOUND); + EXPECT_EQ(id, -1); + + _add_suffix(prefix_to_suffixes, prefix, 5, 55); + id = _get_suffix(prefix_to_suffixes, prefix, 5, &rc); + EXPECT_EQ(rc, KH_FOUND); + EXPECT_EQ(id, 55); + + _remove_suffix(prefix_to_suffixes, prefix, 2); + _add_suffix(prefix_to_suffixes, prefix, 2, 222); + id = _get_suffix(prefix_to_suffixes, prefix, 2, &rc); + EXPECT_EQ(rc, KH_FOUND); + EXPECT_EQ(id, 222); + + _prefix_map_free(prefix_to_suffixes); } TEST_F(PacketCacheTest, CreatePacketCache) { @@ -89,10 +137,12 @@ TEST_F(PacketCacheTest, AddPacketCacheEntry) { EXPECT_NE(entry, nullptr); ASSERT_EQ(pkt_cache_get_size(pkt_cache), 1u); - // // Get entry by name - Name name_key = name_key_factory(name); - khiter_t k = kh_get_pkt_cache_name(pkt_cache->index_by_name, &name_key); - EXPECT_NE(k, kh_end(pkt_cache->index_by_name)); + // Get entry by name + pkt_cache_lookup_t lookup_result; + off_t entry_id; + pkt_cache_entry_t *entry = pkt_cache_lookup(pkt_cache, name, msgbuf_pool, + &lookup_result, &entry_id, true); + EXPECT_NE(lookup_result, PKT_CACHE_LU_NONE); } TEST_F(PacketCacheTest, GetCS) { @@ -141,14 +191,11 @@ TEST_F(PacketCacheTest, AddEntryAndLookup) { } TEST_F(PacketCacheTest, AddToPIT) { - // Prepare msgbuf - msgbuf_t *msgbuf = msgbuf_factory(msgbuf_pool, CONN_ID, name); - // Check if entry properly created - pkt_cache_entry_t *entry = pkt_cache_add_to_pit(pkt_cache, msgbuf); + pkt_cache_entry_t *entry = pkt_cache_add_to_pit(pkt_cache, msgbuf, name); ASSERT_NE(entry, nullptr); EXPECT_EQ(entry->entry_type, PKT_CACHE_PIT_TYPE); - EXPECT_EQ(pit_entry_ingress_contains(&entry->u.pit_entry, CONN_ID), true); + EXPECT_TRUE(pit_entry_ingress_contains(&entry->u.pit_entry, CONN_ID)); ASSERT_EQ(pkt_cache_get_pit_size(pkt_cache), 1u); ASSERT_EQ(pkt_cache_get_cs_size(pkt_cache), 0u); @@ -162,9 +209,6 @@ TEST_F(PacketCacheTest, AddToPIT) { } TEST_F(PacketCacheTest, AddToCS) { - // Prepare msgbuf - msgbuf_t *msgbuf = msgbuf_factory(msgbuf_pool, CONN_ID, name); - // Check if entry properly created pkt_cache_entry_t *entry = pkt_cache_add_to_cs(pkt_cache, msgbuf_pool, msgbuf, MSGBUF_ID); @@ -191,9 +235,8 @@ TEST_F(PacketCacheTest, AddToCS) { } TEST_F(PacketCacheTest, PitToCS) { - // Prepare msgbuf and PIT entry - msgbuf_t *msgbuf = msgbuf_factory(msgbuf_pool, CONN_ID, name); - pkt_cache_entry_t *entry = pkt_cache_add_to_pit(pkt_cache, msgbuf); + // Prepare PIT entry + pkt_cache_entry_t *entry = pkt_cache_add_to_pit(pkt_cache, msgbuf, name); off_t entry_id = pkt_cache_get_entry_id(pkt_cache, entry); ASSERT_EQ(pkt_cache_get_pit_size(pkt_cache), 1u); ASSERT_EQ(pkt_cache_get_cs_size(pkt_cache), 0u); @@ -224,8 +267,7 @@ TEST_F(PacketCacheTest, PitToCS) { } TEST_F(PacketCacheTest, CsToPIT) { - // Prepare msgbuf and CS entry - msgbuf_t *msgbuf = msgbuf_factory(msgbuf_pool, CONN_ID, name); + // Prepare CS entry pkt_cache_entry_t *entry = pkt_cache_add_to_cs(pkt_cache, msgbuf_pool, msgbuf, MSGBUF_ID); off_t entry_id = pkt_cache_get_entry_id(pkt_cache, entry); @@ -237,7 +279,7 @@ TEST_F(PacketCacheTest, CsToPIT) { entry_id); ASSERT_NE(entry, nullptr); EXPECT_EQ(entry->entry_type, PKT_CACHE_PIT_TYPE); - EXPECT_EQ(pit_entry_ingress_contains(&entry->u.pit_entry, CONN_ID), true); + EXPECT_TRUE(pit_entry_ingress_contains(&entry->u.pit_entry, CONN_ID)); ASSERT_EQ(pkt_cache_get_pit_size(pkt_cache), 1u); ASSERT_EQ(pkt_cache_get_cs_size(pkt_cache), 0u); @@ -250,14 +292,13 @@ TEST_F(PacketCacheTest, CsToPIT) { } TEST_F(PacketCacheTest, UpdateInPIT) { - // Prepare msgbuf and PIT entry - msgbuf_t *msgbuf = msgbuf_factory(msgbuf_pool, CONN_ID, name); - pkt_cache_entry_t *entry = pkt_cache_add_to_pit(pkt_cache, msgbuf); + // Prepare PIT entry + pkt_cache_entry_t *entry = pkt_cache_add_to_pit(pkt_cache, msgbuf, name); off_t entry_id = pkt_cache_get_entry_id(pkt_cache, entry); Name new_name; name_CreateFromAddress(&new_name, AF_INET, IPV4_LOOPBACK, IPV4_LEN); - msgbuf_t *new_msgbuf = msgbuf_factory(msgbuf_pool, CONN_ID_2, &new_name); + msgbuf_t *new_msgbuf = msgbuf_create(msgbuf_pool, CONN_ID_2, &new_name); // Check if entry properly updated pkt_cache_update_pit(pkt_cache, entry, new_msgbuf); @@ -276,15 +317,14 @@ TEST_F(PacketCacheTest, UpdateInPIT) { } TEST_F(PacketCacheTest, UpdateInCS) { - // Prepare msgbuf and CS entry - msgbuf_t *msgbuf = msgbuf_factory(msgbuf_pool, CONN_ID, name); + // Prepare CS entry pkt_cache_entry_t *entry = pkt_cache_add_to_cs(pkt_cache, msgbuf_pool, msgbuf, MSGBUF_ID); off_t entry_id = pkt_cache_get_entry_id(pkt_cache, entry); Name new_name; name_CreateFromAddress(&new_name, AF_INET, IPV4_LOOPBACK, IPV4_LEN); - msgbuf_t *new_msgbuf = msgbuf_factory(msgbuf_pool, CONN_ID_2, &new_name); + msgbuf_t *new_msgbuf = msgbuf_create(msgbuf_pool, CONN_ID_2, &new_name); // Check if entry properly updated pkt_cache_update_cs(pkt_cache, msgbuf_pool, entry, new_msgbuf, MSGBUF_ID_2); @@ -304,9 +344,8 @@ TEST_F(PacketCacheTest, UpdateInCS) { } TEST_F(PacketCacheTest, RemoveFromPIT) { - // Prepare msgbuf and PIT entry - msgbuf_t *msgbuf = msgbuf_factory(msgbuf_pool, CONN_ID, name); - pkt_cache_entry_t *entry = pkt_cache_add_to_pit(pkt_cache, msgbuf); + // Prepare PIT entry + pkt_cache_entry_t *entry = pkt_cache_add_to_pit(pkt_cache, msgbuf, name); ASSERT_EQ(pkt_cache_get_pit_size(pkt_cache), 1u); ASSERT_EQ(pkt_cache_get_cs_size(pkt_cache), 0u); @@ -324,8 +363,7 @@ TEST_F(PacketCacheTest, RemoveFromPIT) { } TEST_F(PacketCacheTest, RemoveFromCS) { - // Prepare msgbuf and CS entry - msgbuf_t *msgbuf = msgbuf_factory(msgbuf_pool, CONN_ID, name); + // Prepare CS entry pkt_cache_entry_t *entry = pkt_cache_add_to_cs(pkt_cache, msgbuf_pool, msgbuf, MSGBUF_ID); ASSERT_EQ(pkt_cache_get_pit_size(pkt_cache), 0u); @@ -351,11 +389,10 @@ TEST_F(PacketCacheTest, RemoveFromCS) { } TEST_F(PacketCacheTest, AddTwoEntriesToCS) { - // Prepare msgbufs - msgbuf_t *msgbuf = msgbuf_factory(msgbuf_pool, CONN_ID, name); + // Prepare another msgbuf Name new_name; name_CreateFromAddress(&new_name, AF_INET, IPV4_LOOPBACK, IPV4_LEN); - msgbuf_t *new_msgbuf = msgbuf_factory(msgbuf_pool, CONN_ID_2, &new_name); + msgbuf_t *new_msgbuf = msgbuf_create(msgbuf_pool, CONN_ID_2, &new_name); pkt_cache_entry_t *entry_1 = pkt_cache_add_to_cs(pkt_cache, msgbuf_pool, msgbuf, MSGBUF_ID); @@ -374,18 +411,17 @@ TEST_F(PacketCacheTest, AddTwoEntriesToCS) { } TEST_F(PacketCacheTest, AggregateInPIT) { - // Prepare msgbufs - msgbuf_t *msgbuf = msgbuf_factory(msgbuf_pool, CONN_ID, name); + // Prepare another msgbuf Name new_name; name_CreateFromAddress(&new_name, AF_INET, IPV4_LOOPBACK, IPV4_LEN); - msgbuf_t *new_msgbuf = msgbuf_factory(msgbuf_pool, CONN_ID_2, &new_name); + msgbuf_t *new_msgbuf = msgbuf_create(msgbuf_pool, CONN_ID_2, &new_name); // Check if entry properly created (use sleep to get an updated ts) - pkt_cache_entry_t *entry = pkt_cache_add_to_pit(pkt_cache, msgbuf); + pkt_cache_entry_t *entry = pkt_cache_add_to_pit(pkt_cache, msgbuf, name); Ticks old_lifetime = entry->expire_ts; std::this_thread::sleep_for(std::chrono::milliseconds(100)); bool is_aggregated = - pkt_cache_try_aggregate_in_pit(pkt_cache, entry, new_msgbuf); + pkt_cache_try_aggregate_in_pit(pkt_cache, entry, new_msgbuf, name); Ticks new_lifetime = entry->expire_ts; ASSERT_NE(entry, nullptr); @@ -403,18 +439,17 @@ TEST_F(PacketCacheTest, AggregateInPIT) { } TEST_F(PacketCacheTest, RetransmissionInPIT) { - // Prepare msgbufs (using same connection ID) - msgbuf_t *msgbuf = msgbuf_factory(msgbuf_pool, CONN_ID, name); + // Prepare another msgbuf (using same connection ID) Name new_name; name_CreateFromAddress(&new_name, AF_INET, IPV4_LOOPBACK, IPV4_LEN); - msgbuf_t *new_msgbuf = msgbuf_factory(msgbuf_pool, CONN_ID, &new_name); + msgbuf_t *new_msgbuf = msgbuf_create(msgbuf_pool, CONN_ID, &new_name); // Check if entry properly created (use sleep to get an updated ts) - pkt_cache_entry_t *entry = pkt_cache_add_to_pit(pkt_cache, msgbuf); + pkt_cache_entry_t *entry = pkt_cache_add_to_pit(pkt_cache, msgbuf, name); Ticks old_lifetime = entry->expire_ts; std::this_thread::sleep_for(std::chrono::milliseconds(100)); bool is_aggregated = - pkt_cache_try_aggregate_in_pit(pkt_cache, entry, new_msgbuf); + pkt_cache_try_aggregate_in_pit(pkt_cache, entry, new_msgbuf, name); Ticks new_lifetime = entry->expire_ts; ASSERT_NE(entry, nullptr); @@ -433,10 +468,10 @@ TEST_F(PacketCacheTest, RetransmissionInPIT) { TEST_F(PacketCacheTest, LookupExpiredInterest) { // Prepare msgbuf with 0 as interest lifetime - msgbuf_t *msgbuf = msgbuf_factory(msgbuf_pool, CONN_ID, name, 0); + msgbuf_t *msgbuf = msgbuf_create(msgbuf_pool, CONN_ID, name, 0); // Add to PIT - pkt_cache_entry_t *entry = pkt_cache_add_to_pit(pkt_cache, msgbuf); + pkt_cache_entry_t *entry = pkt_cache_add_to_pit(pkt_cache, msgbuf, name); ASSERT_NE(entry, nullptr); // Wait to make the interest expire @@ -451,7 +486,7 @@ TEST_F(PacketCacheTest, LookupExpiredInterest) { TEST_F(PacketCacheTest, LookupExpiredData) { // Prepare msgbuf with 0 as data expiry time - msgbuf_t *msgbuf = msgbuf_factory(msgbuf_pool, CONN_ID, name, 0); + msgbuf_t *msgbuf = msgbuf_create(msgbuf_pool, CONN_ID, name, 0); // Add to CS pkt_cache_entry_t *entry = @@ -470,20 +505,20 @@ TEST_F(PacketCacheTest, LookupExpiredData) { TEST_F(PacketCacheTest, GetStaleEntries) { // Add to CS a msgbuf with immediate expiration (i.e. stale) - msgbuf_t *msgbuf = msgbuf_factory(msgbuf_pool, CONN_ID, name, 0); + msgbuf_t *msgbuf = msgbuf_create(msgbuf_pool, CONN_ID, name, 0); pkt_cache_add_to_cs(pkt_cache, msgbuf_pool, msgbuf, MSGBUF_ID); // Add to CS another msgbuf with immediate expiration (i.e. stale) Name name_2; name_CreateFromAddress(&name_2, AF_INET, IPV4_LOOPBACK, IPV4_LEN); - msgbuf_t *msgbuf_2 = msgbuf_factory(msgbuf_pool, CONN_ID, &name_2, 0); + msgbuf_t *msgbuf_2 = msgbuf_create(msgbuf_pool, CONN_ID, &name_2, 0); pkt_cache_add_to_cs(pkt_cache, msgbuf_pool, msgbuf_2, MSGBUF_ID_2); // Add to CS a msgbuf with 5-seconds expiration (i.e. not stale) Name name_3; name_CreateFromAddress(&name_3, AF_INET6, IPV6_LOOPBACK, IPV6_LEN); msgbuf_t *msgbuf_3 = - msgbuf_factory(msgbuf_pool, CONN_ID, &name_3, FIVE_SECONDS); + msgbuf_create(msgbuf_pool, CONN_ID, &name_3, FIVE_SECONDS); pkt_cache_add_to_cs(pkt_cache, msgbuf_pool, msgbuf_3, MSGBUF_ID_3); size_t num_stale_entries = pkt_cache_get_num_cs_stale_entries(pkt_cache); @@ -502,7 +537,7 @@ TEST_F(PacketCacheTest, GetMultipleStaleEntries) { inet_pton(AF_INET6, name, (struct in6_addr *)&addr); Name name; name_CreateFromAddress(&name, AF_INET6, addr, IPV6_LEN); - msgbuf_t *msgbuf = msgbuf_factory(msgbuf_pool, i, &name, 0); + msgbuf_t *msgbuf = msgbuf_create(msgbuf_pool, i, &name, 0); pkt_cache_add_to_cs(pkt_cache, msgbuf_pool, msgbuf, i); } @@ -514,7 +549,7 @@ TEST_F(PacketCacheTest, GetMultipleStaleEntries) { inet_pton(AF_INET6, name, (struct in6_addr *)&addr); Name name; name_CreateFromAddress(&name, AF_INET6, addr, IPV6_LEN); - msgbuf_t *msgbuf = msgbuf_factory(msgbuf_pool, i, &name, FIVE_SECONDS); + msgbuf_t *msgbuf = msgbuf_create(msgbuf_pool, i, &name, FIVE_SECONDS); pkt_cache_add_to_cs(pkt_cache, msgbuf_pool, msgbuf, i); } @@ -522,3 +557,126 @@ TEST_F(PacketCacheTest, GetMultipleStaleEntries) { size_t num_stale_entries = pkt_cache_get_num_cs_stale_entries(pkt_cache); EXPECT_EQ(num_stale_entries, (size_t)NUM_STALES); } + +TEST_F(PacketCacheTest, PerformanceDoubleLookup) { + Name tmp = get_name_from_prefix("b001::0"); + + auto elapsed_time_double = get_execution_time([&]() { + kh_pkt_cache_prefix_t *prefix_to_suffixes = kh_init_pkt_cache_prefix(); + + // Add to hash table + for (int seq = 0; seq < N_OPS; seq++) { + name_SetSegment(&tmp, seq); + _add_suffix(prefix_to_suffixes, name_GetContentName(&tmp), + name_GetSegment(&tmp), name_GetSegment(&tmp)); + } + + // Read from hash table + int rc; + for (int seq = 0; seq < N_OPS; seq++) { + name_SetSegment(&tmp, seq); + _get_suffix(prefix_to_suffixes, name_GetContentName(&tmp), seq, &rc); + } + + _prefix_map_free(prefix_to_suffixes); + }); + std::cout << "Double lookup: " << elapsed_time_double << " ms\n"; +} + +TEST_F(PacketCacheTest, PerformanceCachedLookup) { + Name tmp = get_name_from_prefix("b001::0"); + + auto elapsed_time_single = get_execution_time([&]() { + kh_pkt_cache_prefix_t *prefix_to_suffixes = kh_init_pkt_cache_prefix(); + kh_pkt_cache_suffix_t *suffixes = + _get_suffixes(prefix_to_suffixes, name_GetContentName(&tmp)); + + // Add to hash table + for (int seq = 0; seq < N_OPS; seq++) { + name_SetSegment(&tmp, seq); + __add_suffix(suffixes, name_GetSegment(&tmp), name_GetSegment(&tmp)); + } + + // Read from hash table + int rc; + for (int seq = 0; seq < N_OPS; seq++) { + name_SetSegment(&tmp, seq); + __get_suffix(suffixes, name_GetSegment(&tmp), &rc); + } + + _prefix_map_free(prefix_to_suffixes); + }); + std::cout << "Cached lookup: " << elapsed_time_single << " ms\n"; +} + +TEST_F(PacketCacheTest, PerformanceCachedLookupRandom) { + Name tmp = get_name_from_prefix("b001::0"); + + // Prepare random sequence numbers + std::random_device rd; + std::mt19937 gen(rd()); + uint32_t seqs[N_OPS]; + for (int seq = 0; seq < N_OPS; seq++) seqs[seq] = seq; + std::shuffle(std::begin(seqs), std::end(seqs), gen); + + auto elapsed_time_single_rand = get_execution_time([&]() { + kh_pkt_cache_prefix_t *prefix_to_suffixes = kh_init_pkt_cache_prefix(); + kh_pkt_cache_suffix_t *suffixes = + _get_suffixes(prefix_to_suffixes, name_GetContentName(&tmp)); + + // Add to hash table + for (int seq = 0; seq < N_OPS; seq++) { + name_SetSegment(&tmp, seqs[seq]); + __add_suffix(suffixes, name_GetSegment(&tmp), name_GetSegment(&tmp)); + } + + // Read from hash table + int rc; + for (int seq = 0; seq < N_OPS; seq++) { + name_SetSegment(&tmp, seqs[seq]); + __get_suffix(suffixes, name_GetSegment(&tmp), &rc); + } + + _prefix_map_free(prefix_to_suffixes); + }); + std::cout << "Cached lookup (rand): " << elapsed_time_single_rand << " ms\n"; +} + +TEST_F(PacketCacheTest, Clear) { + Name tmp_name1, tmp_name2; + cs_t *cs = pkt_cache_get_cs(pkt_cache); + + // Create name and add to msgbuf pool + name_Copy(name, &tmp_name1); + name_SetSegment(&tmp_name1, 1); + msgbuf_t *tmp_msgbuf1 = msgbuf_create(msgbuf_pool, CONN_ID_2, &tmp_name1); + + // Create (another) name and add to msgbuf pool + name_Copy(name, &tmp_name2); + name_SetSegment(&tmp_name2, 2); + msgbuf_t *tmp_msgbuf2 = msgbuf_create(msgbuf_pool, CONN_ID_2, &tmp_name2); + + // Add to packet cache (2 entries in the CS, 1 in the PIT) + pkt_cache_add_to_cs(pkt_cache, msgbuf_pool, msgbuf, MSGBUF_ID); + pkt_cache_add_to_pit(pkt_cache, tmp_msgbuf1, &tmp_name1); + pkt_cache_add_to_cs(pkt_cache, msgbuf_pool, tmp_msgbuf2, MSGBUF_ID_2); + + // Check stats (before clearing the packet cache) + ASSERT_EQ(pkt_cache_get_size(pkt_cache), 3u); + ASSERT_EQ(pkt_cache_get_pit_size(pkt_cache), 1u); + ASSERT_EQ(pkt_cache_get_cs_size(pkt_cache), 2u); + ASSERT_EQ(cs->num_entries, 2u); + ASSERT_EQ(cs->stats.lru.countAdds, 2u); + + // Clear packet cache (i.e. remove content packets from packet cache): + // PIT entry should still be there while CS entries are cleared + pkt_cache_cs_clear(pkt_cache); + cs = pkt_cache_get_cs(pkt_cache); + + // Check stats (after clearing the packet cache) + ASSERT_EQ(pkt_cache_get_size(pkt_cache), 1u); + ASSERT_EQ(pkt_cache_get_pit_size(pkt_cache), 1u); + ASSERT_EQ(pkt_cache_get_cs_size(pkt_cache), 0u); + ASSERT_EQ(cs->num_entries, 0u); + ASSERT_EQ(cs->stats.lru.countAdds, 0u); +}
\ No newline at end of file diff --git a/hicn-light/src/hicn/test/test-pool.cc b/hicn-light/src/hicn/test/test-pool.cc index c631415ca..8cd891d6a 100644 --- a/hicn-light/src/hicn/test/test-pool.cc +++ b/hicn-light/src/hicn/test/test-pool.cc @@ -25,7 +25,7 @@ extern "C" { #define WITH_TESTS -#include <hicn/base/pool.h> +#include <hicn/util/pool.h> } /* diff --git a/hicn-light/src/hicn/test/test-ring.cc b/hicn-light/src/hicn/test/test-ring.cc index 51f1f5327..ab96d76c0 100644 --- a/hicn-light/src/hicn/test/test-ring.cc +++ b/hicn-light/src/hicn/test/test-ring.cc @@ -25,7 +25,7 @@ extern "C" { #define WITH_TESTS -#include <hicn/base/ring.h> +#include <hicn/util/ring.h> } #define DEFAULT_SIZE 10UL diff --git a/hicn-light/src/hicn/test/test-subscription.cc b/hicn-light/src/hicn/test/test-subscription.cc index 18ef60c0d..f89254e67 100644 --- a/hicn-light/src/hicn/test/test-subscription.cc +++ b/hicn-light/src/hicn/test/test-subscription.cc @@ -6,7 +6,7 @@ extern "C" { #include <hicn/core/subscription.h> -#include <hicn/base/vector.h> +#include <hicn/util/vector.h> } static inline unsigned CONN_ID = 1; diff --git a/hicn-light/src/hicn/test/test-utils.h b/hicn-light/src/hicn/test/test-utils.h new file mode 100644 index 000000000..577629584 --- /dev/null +++ b/hicn-light/src/hicn/test/test-utils.h @@ -0,0 +1,26 @@ +#pragma once + +#include <vector> +#include <thread> +#include <numeric> + +static constexpr int N_RUNS = 100; + +// Utility function for time execution calculation +template <typename F, typename... Args> +double get_execution_time(F func, Args &&...args) { + std::vector<float> execution_times; + + for (int i = 0; i < N_RUNS; i++) { + auto start = std::chrono::high_resolution_clock::now(); + func(std::forward<Args>(args)...); + auto end = std::chrono::high_resolution_clock::now(); + + std::chrono::duration<double, std::milli> ms = end - start; + execution_times.emplace_back(ms.count()); + } + + // Calculate average + return std::reduce(execution_times.begin(), execution_times.end()) / + execution_times.size(); +}
\ No newline at end of file diff --git a/hicn-light/src/hicn/test/test-vector.cc b/hicn-light/src/hicn/test/test-vector.cc index fb30a8228..dda71fd0c 100644 --- a/hicn-light/src/hicn/test/test-vector.cc +++ b/hicn-light/src/hicn/test/test-vector.cc @@ -15,26 +15,12 @@ #include <gtest/gtest.h> -#include <stdio.h> -#include <stdlib.h> -#include <string.h> -#include <sys/socket.h> -#include <sys/un.h> -#include <unistd.h> -#include <netinet/in.h> - extern "C" { -#define WITH_TESTS -#include <hicn/base/vector.h> +#include <hicn/util/vector.h> } -/* - * TODO - * - test max_size - */ - -#define DEFAULT_SIZE 10 -const size_t N_ELEMENTS = 5; +static constexpr size_t DEFAULT_SIZE = 10; +static constexpr size_t N_ELEMENTS = 5; class VectorTest : public ::testing::Test { protected: @@ -44,58 +30,62 @@ class VectorTest : public ::testing::Test { int *vector = NULL; }; -/* TEST: Vector allocation and initialization */ -TEST_F(VectorTest, VectorAllocate) { - /* Allocated size should be the next power of two */ +TEST_F(VectorTest, VectorAllocateAndResize) { + // Allocated size should be the next power of two EXPECT_EQ(vector_get_alloc_size(vector), 16UL); - /* Setting elements within the allocated size should not trigger a resize */ + // Setting elements within the allocated size should not trigger a resize vector_ensure_pos(vector, 15); EXPECT_EQ(vector_get_alloc_size(vector), 16UL); - /* Setting elements after should through */ + // Setting elements after should through vector_ensure_pos(vector, 16); EXPECT_EQ(vector_get_alloc_size(vector), 32UL); - - /* Check that free indices and bitmaps are correctly updated */ } TEST_F(VectorTest, VectorSize) { - vector_push(vector, 109); - int size = vector_len(vector); - EXPECT_EQ(size, 1); - vector_push(vector, 109); - size = vector_len(vector); - EXPECT_EQ(size, 2); - vector_push(vector, 109); - size = vector_len(vector); - EXPECT_EQ(size, 3); + EXPECT_EQ(vector_len(vector), 0); + + // Check size after pushing one element + vector_push(vector, 1); + EXPECT_EQ(vector_len(vector), 1); + + // Check size after pushing additional elements + vector_push(vector, 2); + vector_push(vector, 3); + EXPECT_EQ(vector_len(vector), 3); + + // Try adding multiple elements + const int n_elements_to_add = 5; + size_t expected_new_len = vector_len(vector) + n_elements_to_add; + for (int i = 0; i < n_elements_to_add; i++) vector_push(vector, i); + EXPECT_EQ(vector_len(vector), expected_new_len); } TEST_F(VectorTest, VectorCheckValue) { + // Add elements vector_push(vector, 109); vector_push(vector, 200); - EXPECT_EQ(vector[0], 109); - EXPECT_EQ(vector[1], 200); -} - -TEST_F(VectorTest, VectorEnsurePos) { - printf(" %p\n", vector); - vector_ensure_pos(vector, 1025); - for (int i = 0; i < 1025; i++) { - // printf("i %d\n", i); - // printf (" %p\n", vector); - vector_push(vector, i); - } - int size = vector_len(vector); - EXPECT_EQ(size, 1025); + EXPECT_EQ(vector_at(vector, 0), 109); + EXPECT_EQ(vector_at(vector, 1), 200); + + // Update element + vector_set(vector, 1, 400); + EXPECT_EQ(vector_at(vector, 1), 400); + + // Add at last available position + size_t prev_size = vector_len(vector); + vector_set(vector, vector_len(vector) - 1, 123); + EXPECT_EQ(vector_at(vector, vector_len(vector) - 1), 123); + EXPECT_EQ(prev_size, vector_len(vector)) << "Size should not have changed"; } TEST_F(VectorTest, RemoveElement) { // Populate vector for (size_t i = 0; i < N_ELEMENTS; i++) vector_push(vector, i); EXPECT_EQ(vector_len(vector), N_ELEMENTS); - for (size_t i = 0; i < vector_len(vector); i++) EXPECT_EQ(vector[i], (int)i); + for (size_t i = 0; i < vector_len(vector); i++) + EXPECT_EQ(vector_at(vector, i), (int)i); // Remove element int value_to_remove = 3; @@ -104,15 +94,30 @@ TEST_F(VectorTest, RemoveElement) { EXPECT_EQ(vector_len(vector), N_ELEMENTS - 1); EXPECT_EQ(num_removed, 1); for (size_t i = 0; i < vector_len(vector); i++) - EXPECT_NE(vector[i], value_to_remove); + EXPECT_NE(vector_at(vector, i), value_to_remove); +} + +TEST_F(VectorTest, RemoveNonExistingElement) { + // Push some initial values + vector_push(vector, 1); + vector_push(vector, 2); + vector_push(vector, 3); + EXPECT_EQ(vector_len(vector), 3); + + // Remove non-existing element + int num_removed = vector_remove_unordered(vector, 5); + EXPECT_EQ(num_removed, 0); + size_t prev_size = vector_len(vector); + EXPECT_EQ(prev_size, vector_len(vector)) << "Size should not have changed"; } TEST_F(VectorTest, RemoveDuplicatedElement) { // Populate vector for (size_t i = 0; i < N_ELEMENTS; i++) vector_push(vector, i); EXPECT_EQ(vector_len(vector), N_ELEMENTS); - for (size_t i = 0; i < vector_len(vector); i++) EXPECT_EQ(vector[i], (int)i); - vector[0] = 3; // Duplicate element + for (size_t i = 0; i < vector_len(vector); i++) + EXPECT_EQ(vector_at(vector, i), (int)i); + vector_set(vector, 0, 3); // Duplicate element // Remove (duplicated) elements int value_to_remove = 3; @@ -121,7 +126,7 @@ TEST_F(VectorTest, RemoveDuplicatedElement) { EXPECT_EQ(vector_len(vector), N_ELEMENTS - 2); EXPECT_EQ(num_removed, 2); for (size_t i = 0; i < vector_len(vector); i++) - EXPECT_NE(vector[i], value_to_remove); + EXPECT_NE(vector_at(vector, i), value_to_remove); } TEST_F(VectorTest, Iterate) { @@ -139,10 +144,89 @@ TEST_F(VectorTest, MultipleResize) { for (size_t i = 0; i < N_ELEMENTS; i++) vector_push(small_vector, i); - for (size_t i = 0; i < N_ELEMENTS; i++) EXPECT_EQ(small_vector[i], (int)i); + for (size_t i = 0; i < N_ELEMENTS; i++) + EXPECT_EQ(vector_at(small_vector, i), (int)i); EXPECT_EQ(vector_len(small_vector), 5UL); EXPECT_EQ(vector_get_alloc_size(small_vector), 8UL); vector_free(small_vector); +} + +TEST_F(VectorTest, MaxSize) { + const int max_size = 4; + + // Fill the vector until max size is reached + int *small_vector; + vector_init(small_vector, 2, max_size); + for (int i = 0; i < max_size; i++) vector_push(small_vector, i); + + // Try expanding or appending elements should fail + int rc = vector_ensure_pos(small_vector, max_size); + EXPECT_EQ(rc, -1); + rc = vector_push(small_vector, 123); + EXPECT_EQ(rc, -1); + + vector_free(small_vector); +} + +TEST_F(VectorTest, Contains) { + // No elements + EXPECT_EQ(vector_contains(vector, 1), false); + + // Push one element + vector_push(vector, 1); + EXPECT_EQ(vector_contains(vector, 1), true); + + // Update element + vector_set(vector, 0, 2); + EXPECT_EQ(vector_contains(vector, 1), false); + EXPECT_EQ(vector_contains(vector, 2), true); +} + +TEST_F(VectorTest, Remove) { + // Remove element at invalid position + int rc = vector_remove_at(vector, 2); + EXPECT_EQ(rc, -1); // Failure + + // Push two elements and remove the second one + vector_push(vector, 1); + vector_push(vector, 2); + rc = vector_remove_at(vector, 1); + EXPECT_EQ(rc, 0); // Success + EXPECT_EQ(vector_len(vector), 1); + + // Push another element: it should replace the previous one + vector_push(vector, 3); + EXPECT_EQ(vector_len(vector), 2); + EXPECT_EQ(vector_at(vector, 1), 3); +} + +TEST_F(VectorTest, RemoveInTheMiddle) { + for (size_t i = 0; i < N_ELEMENTS; i++) vector_push(vector, i); + + // Remove element in central position + int rc = vector_remove_at(vector, 2); + EXPECT_EQ(rc, 0); // Success + EXPECT_EQ(vector_contains(vector, 2), false); + EXPECT_EQ(vector_len(vector), N_ELEMENTS - 1); + + // Check if elements have been shifted (preserving the order) + int expected[] = {0, 1, 3, 4}; + for (int i = 0; i < vector_len(vector); i++) + EXPECT_EQ(vector_at(vector, i), expected[i]); +} + +TEST_F(VectorTest, Reset) { + vector_push(vector, 1); + vector_push(vector, 2); + EXPECT_EQ(vector_len(vector), 2); + + vector_reset(vector); + EXPECT_EQ(vector_len(vector), 0); + + vector_push(vector, 5); + EXPECT_EQ(vector_len(vector), 1); + EXPECT_EQ(vector_contains(vector, 5), true); + EXPECT_EQ(vector_at(vector, 0), 5); }
\ No newline at end of file |