diff options
Diffstat (limited to 'lib')
| -rw-r--r-- | lib/includes/CMakeLists.txt | 6 | ||||
| -rw-r--r-- | lib/includes/hicn/base.h | 140 | ||||
| -rw-r--r-- | lib/includes/hicn/common.h | 80 | ||||
| -rw-r--r-- | lib/includes/hicn/compat.h | 2 | ||||
| -rw-r--r-- | lib/includes/hicn/header.h | 2 | ||||
| -rw-r--r-- | lib/includes/hicn/ops.h | 71 | ||||
| -rw-r--r-- | lib/includes/hicn/util/array.h | 4 | ||||
| -rw-r--r-- | lib/includes/hicn/util/bitmap.h | 212 | ||||
| -rw-r--r-- | lib/includes/hicn/util/hash.h | 367 | ||||
| -rw-r--r-- | lib/includes/hicn/util/khash.h | 826 | ||||
| -rw-r--r-- | lib/includes/hicn/util/pool.h | 264 | ||||
| -rw-r--r-- | lib/includes/hicn/util/ring.h | 227 | ||||
| -rw-r--r-- | lib/includes/hicn/util/vector.h | 470 | ||||
| -rw-r--r-- | lib/src/CMakeLists.txt | 3 | ||||
| -rw-r--r-- | lib/src/common.c | 73 | ||||
| -rw-r--r-- | lib/src/ops.c | 4 | ||||
| -rw-r--r-- | lib/src/protocol/ah.c | 4 | ||||
| -rw-r--r-- | lib/src/protocol/icmp.c | 4 | ||||
| -rw-r--r-- | lib/src/protocol/ipv4.c | 25 | ||||
| -rw-r--r-- | lib/src/protocol/ipv6.c | 25 | ||||
| -rw-r--r-- | lib/src/protocol/new.c | 5 | ||||
| -rw-r--r-- | lib/src/protocol/tcp.c | 29 | ||||
| -rw-r--r-- | lib/src/protocol/udp.c | 29 | ||||
| -rw-r--r-- | lib/src/util/log.c | 13 | ||||
| -rw-r--r-- | lib/src/util/pool.c | 174 | ||||
| -rw-r--r-- | lib/src/util/ring.c | 49 | ||||
| -rw-r--r-- | lib/src/util/vector.c | 101 |
27 files changed, 3143 insertions, 66 deletions
diff --git a/lib/includes/CMakeLists.txt b/lib/includes/CMakeLists.txt index 821feb2bb..392c2c94e 100644 --- a/lib/includes/CMakeLists.txt +++ b/lib/includes/CMakeLists.txt @@ -48,12 +48,18 @@ set(LIBHICN_HEADER_FILES_PROTOCOL ${CMAKE_CURRENT_SOURCE_DIR}/hicn/protocol/udp.h ${CMAKE_CURRENT_SOURCE_DIR}/hicn/protocol/new.h ${CMAKE_CURRENT_SOURCE_DIR}/hicn/util/array.h + ${CMAKE_CURRENT_SOURCE_DIR}/hicn/util/bitmap.h + ${CMAKE_CURRENT_SOURCE_DIR}/hicn/util/hash.h ${CMAKE_CURRENT_SOURCE_DIR}/hicn/util/ip_address.h + ${CMAKE_CURRENT_SOURCE_DIR}/hicn/util/khash.h ${CMAKE_CURRENT_SOURCE_DIR}/hicn/util/log.h ${CMAKE_CURRENT_SOURCE_DIR}/hicn/util/map.h + ${CMAKE_CURRENT_SOURCE_DIR}/hicn/util/pool.h + ${CMAKE_CURRENT_SOURCE_DIR}/hicn/util/ring.h ${CMAKE_CURRENT_SOURCE_DIR}/hicn/util/set.h ${CMAKE_CURRENT_SOURCE_DIR}/hicn/util/sstrncpy.h ${CMAKE_CURRENT_SOURCE_DIR}/hicn/util/token.h ${CMAKE_CURRENT_SOURCE_DIR}/hicn/util/types.h + ${CMAKE_CURRENT_SOURCE_DIR}/hicn/util/vector.h PARENT_SCOPE ) diff --git a/lib/includes/hicn/base.h b/lib/includes/hicn/base.h index 844814d57..b825619b7 100644 --- a/lib/includes/hicn/base.h +++ b/lib/includes/hicn/base.h @@ -21,6 +21,8 @@ #ifndef HICN_BASE_H #define HICN_BASE_H +#include <stdio.h> +#include <stdbool.h> #include "common.h" #ifdef _WIN32 #include <Winsock2.h> @@ -148,6 +150,16 @@ hicn_type_is_none (hicn_type_t type) } /** + * @brief hICN Packet type + */ +typedef enum +{ + HICN_PACKET_TYPE_INTEREST, + HICN_PACKET_TYPE_DATA, + HICN_PACKET_N_TYPE, +} hicn_packet_type_t; + +/** * @brief hICN Payload type * * This type distinguishes several types of data packet, which can either carry @@ -160,6 +172,61 @@ typedef enum HPT_UNSPEC = 999 } hicn_payload_type_t; +/*************************************************************** + * Interest Manifest + ***************************************************************/ + +#define MAX_SUFFIXES_IN_MANIFEST 255 +#define WORD_WIDTH (sizeof (uint32_t) * 8) +#define BITMAP_SIZE ((MAX_SUFFIXES_IN_MANIFEST + 1) / WORD_WIDTH) + +typedef struct +{ + /* This can be 16 bits, but we use 32 bits for alignment */ + uint32_t n_suffixes; + + uint32_t request_bitmap[BITMAP_SIZE]; + + /* Followed by the list of prefixes to ask */ + /* ... */ +} interest_manifest_header_t; + +// Bitmap operations + +static inline void +set_bit (uint32_t *bitmap, int i) +{ + size_t offset = i / WORD_WIDTH; + size_t pos = i % WORD_WIDTH; + bitmap[offset] |= ((uint32_t) 1 << pos); +} + +static inline void +unset_bit (uint32_t *bitmap, int i) +{ + size_t offset = i / WORD_WIDTH; + size_t pos = i % WORD_WIDTH; + bitmap[offset] &= ~((uint32_t) 1 << pos); +} + +static inline bool +is_bit_set (const uint32_t *bitmap, int i) +{ + size_t offset = i / WORD_WIDTH; + size_t pos = i % WORD_WIDTH; + return bitmap[offset] & ((uint32_t) 1 << pos); +} + +static inline void +bitmap_print (u32 *bitmap, size_t n_words) +{ + for (size_t word = 0; word < n_words; word++) + { + for (int bit = 31; bit >= 0; bit--) + (is_bit_set (&bitmap[word], bit)) ? printf ("1") : printf ("0"); + } +} + /** * @brief Path label computations * @@ -194,6 +261,79 @@ update_pathlabel (hicn_pathlabel_t current_label, hicn_faceid_t face_id, pl_face_id; } +/*************************************************************** + * Statistics + ***************************************************************/ + +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; + + // Data processing + uint32_t countDroppedNoReversePath; + uint32_t countDataExpired; + + // TODO(eloparco): Currently not used + // uint32_t countDroppedNoHopLimit; + // uint32_t countDroppedZeroHopLimitFromRemote; + // uint32_t countDroppedZeroHopLimitToRemote; +} forwarder_stats_t; + +typedef struct +{ + uint32_t n_pit_entries; + uint32_t n_cs_entries; + uint32_t n_lru_evictions; +} pkt_cache_stats_t; + +typedef struct +{ + forwarder_stats_t forwarder; + pkt_cache_stats_t pkt_cache; +} hicn_light_stats_t; + +typedef struct +{ + struct + { + uint32_t rx_pkts; + uint32_t rx_bytes; + uint32_t tx_pkts; + uint32_t tx_bytes; + } interests; + struct + { + uint32_t rx_pkts; + uint32_t rx_bytes; + uint32_t tx_pkts; + uint32_t tx_bytes; + } data; +} connection_stats_t; + #endif /* HICN_BASE_H */ /* diff --git a/lib/includes/hicn/common.h b/lib/includes/hicn/common.h index b0898ce1f..1998099db 100644 --- a/lib/includes/hicn/common.h +++ b/lib/includes/hicn/common.h @@ -224,8 +224,6 @@ ip_csum_sub_even (ip_csum_t c, ip_csum_t x) u32 cumulative_hash32 (const void *data, size_t len, u32 lastValue); u32 hash32 (const void *data, size_t len); -u64 cumulative_hash64 (const void *data, size_t len, u64 lastValue); -u64 hash64 (const void *data, size_t len); void hicn_packet_dump (const uint8_t *buffer, size_t len); /** @@ -270,23 +268,75 @@ csum (const void *addr, size_t size, u16 init) #define HICN_IP_VERSION(packet) \ ((hicn_header_t *) packet)->protocol.ipv4.version -/* - * ntohll / htonll allows byte swapping for 64 bits integers - */ -#ifndef htonll -#define htonll(x) \ - ((1 == htonl (1)) ? \ - (x) : \ - ((uint64_t) htonl ((x) &0xFFFFFFFF) << 32) | htonl ((x) >> 32)) +#ifndef ntohll +static inline uint64_t +ntohll (uint64_t input) +{ + uint64_t return_val = input; +#if (__BYTE_ORDER__) == (__ORDER_LITTLE_ENDIAN__) + uint8_t *tmp = (uint8_t *) &return_val; + + tmp[0] = (uint8_t) (input >> 56); + tmp[1] = (uint8_t) (input >> 48); + tmp[2] = (uint8_t) (input >> 40); + tmp[3] = (uint8_t) (input >> 32); + tmp[4] = (uint8_t) (input >> 24); + tmp[5] = (uint8_t) (input >> 16); + tmp[6] = (uint8_t) (input >> 8); + tmp[7] = (uint8_t) (input >> 0); #endif -#ifndef ntohll -#define ntohll(x) \ - ((1 == ntohl (1)) ? \ - (x) : \ - ((uint64_t) ntohl ((x) &0xFFFFFFFF) << 32) | ntohl ((x) >> 32)) + return return_val; +} + +static inline uint64_t +htonll (uint64_t input) +{ + return (ntohll (input)); +} +#endif + +#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 /* HICN_COMMON_H */ /* diff --git a/lib/includes/hicn/compat.h b/lib/includes/hicn/compat.h index 8de3f9d7e..98c035b57 100644 --- a/lib/includes/hicn/compat.h +++ b/lib/includes/hicn/compat.h @@ -93,6 +93,8 @@ hicn_get_ah_format (hicn_format_t format) // HICN_V6_MIN_HDR_LEN : HICN_V4_MIN_HDR_LEN) #define HICN_MIN_HDR_LEN HICN_V6_MIN_HDR_LEN +hicn_type_t hicn_header_to_type (const hicn_header_t *h); + /** * @brief Parse packet headers and return hICN format * @param [in] format - hICN Format diff --git a/lib/includes/hicn/header.h b/lib/includes/hicn/header.h index 8af9170f8..208e35d68 100644 --- a/lib/includes/hicn/header.h +++ b/lib/includes/hicn/header.h @@ -135,6 +135,8 @@ typedef union #define HICN_V4_TCP_AH_HDRLEN (HICN_V4_TCP_HDRLEN + AH_HDRLEN) #define HICN_V4_ICMP_AH_HDRLEN (HICN_V4_ICMP_HDRLEN + AH_HDRLEN) +#define HICN_DEFAULT_PORT 9695 + #endif /* HICN_HEADER_H */ /* diff --git a/lib/includes/hicn/ops.h b/lib/includes/hicn/ops.h index e9eebc76c..4efef6523 100644 --- a/lib/includes/hicn/ops.h +++ b/lib/includes/hicn/ops.h @@ -257,6 +257,45 @@ typedef struct hicn_ops_s const hicn_lifetime_t lifetime); /** + * @brief Get the source port of the hicn packet. + * @param [in] type - hICN packet type + * @param [in] h - Buffer holding the Interest or Data packet + * @param [out] source_port - Retrieved source port + * @return hICN error code + */ + int (*get_source_port) (hicn_type_t type, const hicn_protocol_t *h, + u16 *source_port); + + /** + * @brief Get the destination port of the hicn packet. + * @param [in] type - hICN packet type + * @param [in] h - Buffer holding the Interest or Data packet + * @param [out] source_port - Retrieved destination port + * @return hICN error code + */ + int (*get_dest_port) (hicn_type_t type, const hicn_protocol_t *h, + u16 *dest_port); + + /** + * @brief Set the source port of the hicn packet. + * @param [in] type - hICN packet type + * @param [in] h - Buffer holding the Interest or Data packet + * @param [out] source_port - Source port to set + * @return hICN error code + */ + int (*set_source_port) (hicn_type_t type, hicn_protocol_t *h, + u16 source_port); + + /** + * @brief Set the destination port of the hicn packet. + * @param [in] type - hICN packet type + * @param [in] h - Buffer holding the Interest or Data packet + * @param [out] source_port - Destination port to set + * @return hICN error code + */ + int (*set_dest_port) (hicn_type_t type, hicn_protocol_t *h, u16 dest_port); + + /** * @brief Update all checksums in packet headers * @param [in] type - hICN packet type * @param [in,out] h - Buffer holding the packet @@ -540,6 +579,10 @@ typedef struct hicn_ops_s ATTR_INIT (reset_data_for_hash, protocol##_reset_data_for_hash), \ ATTR_INIT (get_lifetime, protocol##_get_lifetime), \ ATTR_INIT (set_lifetime, protocol##_set_lifetime), \ + ATTR_INIT (get_source_port, protocol##_get_source_port), \ + ATTR_INIT (get_dest_port, protocol##_get_dest_port), \ + ATTR_INIT (set_source_port, protocol##_set_source_port), \ + ATTR_INIT (set_dest_port, protocol##_set_dest_port), \ ATTR_INIT (update_checksums, protocol##_update_checksums), \ ATTR_INIT (verify_checksums, protocol##_verify_checksums), \ ATTR_INIT (rewrite_interest, protocol##_rewrite_interest), \ @@ -775,6 +818,34 @@ PAYLOAD (hicn_type_t type, const hicn_protocol_t *h) return HICN_LIB_ERROR_##error; \ } +#define DECLARE_get_source_port(protocol, error) \ + int protocol##_get_source_port (hicn_type_t type, const hicn_protocol_t *h, \ + u16 *source_port) \ + { \ + return HICN_LIB_ERROR_##error; \ + } + +#define DECLARE_get_dest_port(protocol, error) \ + int protocol##_get_dest_port (hicn_type_t type, const hicn_protocol_t *h, \ + u16 *dest_port) \ + { \ + return HICN_LIB_ERROR_##error; \ + } + +#define DECLARE_set_source_port(protocol, error) \ + int protocol##_set_source_port (hicn_type_t type, hicn_protocol_t *h, \ + u16 source_port) \ + { \ + return HICN_LIB_ERROR_##error; \ + } + +#define DECLARE_set_dest_port(protocol, error) \ + int protocol##_set_dest_port (hicn_type_t type, hicn_protocol_t *h, \ + u16 dest_port) \ + { \ + return HICN_LIB_ERROR_##error; \ + } + #define DECLARE_update_checksums(protocol, error) \ int protocol##_update_checksums (hicn_type_t type, hicn_protocol_t *h, \ u16 partial_csum, size_t payload_length) \ diff --git a/lib/includes/hicn/util/array.h b/lib/includes/hicn/util/array.h index 46d60976e..f56c13140 100644 --- a/lib/includes/hicn/util/array.h +++ b/lib/includes/hicn/util/array.h @@ -28,8 +28,6 @@ #define BUFSIZE 1024 -typedef int (*cmp_t) (const void *x, const void *y); - #define TYPEDEF_ARRAY_H(NAME, T) \ \ typedef struct \ @@ -151,7 +149,7 @@ typedef int (*cmp_t) (const void *x, const void *y); for (unsigned i = 0; i < array->size; i++) \ { \ if (CMP (search, array->elements[i]) == 0) \ - return facelet_array_remove_index (array, i, element); \ + return NAME##_remove_index (array, i, element); \ } \ /* Not found */ \ if (element) \ diff --git a/lib/includes/hicn/util/bitmap.h b/lib/includes/hicn/util/bitmap.h new file mode 100644 index 000000000..11eb7870b --- /dev/null +++ b/lib/includes/hicn/util/bitmap.h @@ -0,0 +1,212 @@ +/* + * 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 <hicn/common.h> +#include <hicn/util/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/lib/includes/hicn/util/hash.h b/lib/includes/hicn/util/hash.h new file mode 100644 index 000000000..ded8fc370 --- /dev/null +++ b/lib/includes/hicn/util/hash.h @@ -0,0 +1,367 @@ +/* + * 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 + +#include <stdint.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/lib/includes/hicn/util/khash.h b/lib/includes/hicn/util/khash.h new file mode 100644 index 000000000..17401091f --- /dev/null +++ b/lib/includes/hicn/util/khash.h @@ -0,0 +1,826 @@ +/* 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 return codes + ******************************************************************************/ + +// RESET: same as added, but the key was already added in the past +#define foreach_kh_rc \ + _ (REPLACED) \ + _ (ADDED) \ + _ (RESET) \ + _ (NOT_FOUND) \ + _ (FOUND) \ + _ (FAIL) + +typedef enum +{ +#define _(x) KH_##x, + foreach_kh_rc +#undef _ +} kh_rc; + +/****************************************************************************** + * 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/lib/includes/hicn/util/pool.h b/lib/includes/hicn/util/pool.h new file mode 100644 index 000000000..7488e08fd --- /dev/null +++ b/lib/includes/hicn/util/pool.h @@ -0,0 +1,264 @@ +/* + * 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 <hicn/util/vector.h> +#include "../common.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/lib/includes/hicn/util/ring.h b/lib/includes/hicn/util/ring.h new file mode 100644 index 000000000..9510672b3 --- /dev/null +++ b/lib/includes/hicn/util/ring.h @@ -0,0 +1,227 @@ +/* + * 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 (unsigned int) (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/lib/includes/hicn/util/vector.h b/lib/includes/hicn/util/vector.h new file mode 100644 index 000000000..46f195c6d --- /dev/null +++ b/lib/includes/hicn/util/vector.h @@ -0,0 +1,470 @@ +/* + * 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 <stdbool.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). + * @return int 0 if successful, -1 otherwise + */ +int _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--; + // Copy last element to current position (hence order is not + // maintained) + memcpy ((uint8_t *) vector + i * elt_size, + (uint8_t *) vector + vh->cur_size * elt_size, elt_size); + num_removed++; + } + } + return (int) num_removed; +} + +/** + * @brief Get the element at the specified position and store in 'elt'. + * + * @param[in] vector Pointer to the vector data structure to use + * @param[in] pos Position of the element to retrieve + * @param[in] elt_size The size of a vector element + * @param[in] elt The element where the result is stored + * @return int 0 if successful, -1 otherwise + */ +static inline int +_vector_get (void *vector, off_t pos, size_t elt_size, void *elt) +{ + vector_hdr_t *vh = vector_hdr (vector); + if (pos >= vh->alloc_size) + return -1; + + memcpy (elt, (uint8_t *) vector + pos * elt_size, elt_size); + return 0; +} + +/** + * @brief Check if specified element is present in vector. + * + * @param[in] vector Pointer to the vector data structure to use + * @param[in] elt_size The size of a vector element + * @param[in] elt The element to search for + * @return true If specified element is contained in the vector + * @return false + */ +static inline bool +_vector_contains (void *vector, size_t elt_size, void *elt) +{ + for (int i = 0; i < vector_hdr (vector)->cur_size; i++) + { + if (memcmp ((uint8_t *) vector + i * elt_size, elt, elt_size) == 0) + return true; + } + + return false; +} + +/** + * @brief Remove the element at the specified position from the vector. + * Relative element order is preserved by shifting left the elements after the + * target. + * + * @param[in, out] vector Pointer to the vector data structure to use + * @param[in] elt_size The size of a vector element + * @param[in] pos Position of the element to remove + * @return int 0 if successful, -1 otherwise + */ +static inline int +_vector_remove_at (void **vector_ptr, size_t elt_size, off_t pos) +{ + vector_hdr_t *vh = vector_hdr (*vector_ptr); + if (pos >= vh->cur_size) + return -1; + + // Shift backward by one position all the elements after the one specified + memmove ((uint8_t *) (*vector_ptr) + pos * elt_size, + (uint8_t *) (*vector_ptr) + (pos + 1) * elt_size, + (vh->cur_size - 1 - pos) * elt_size); + vh->cur_size--; + + return 0; +} + +/******************************************************************************/ +/* 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) _vector_var (x) = elt; \ + _vector_push ((void **) &(vector), sizeof ((vector)[0]), \ + (void *) (&_vector_var (x))); \ + }) + +#define vector_at(vector, pos) \ + ({ \ + assert (pos < vector_hdr (vector)->cur_size); \ + (vector)[(pos)]; \ + }) + +#define vector_set(vector, pos, elt) \ + ({ \ + assert (pos < vector_hdr (vector)->cur_size); \ + (vector)[(pos)] = elt; \ + }) + +/** + * @brief Clear the vector content, i.e. new pushes will insert starting from + * position 0. + * + * @param[in, out] vector The vector to reset + */ +#define vector_reset(vector) (vector_len (vector) = 0) + +/** + * @brief Get the element at the specified position and store in 'elt'. + * + * @param[in] vector The vector data structure to use + * @param[in] pos Position of the element to retrieve + * @param[in] elt The element where the result is stored + * @return int 0 if successful, -1 otherwise + */ +#define vector_get(vector, pos, elt) \ + _vector_get ((void *) (vector), (pos), sizeof ((vector)[0]), \ + (void *) (&elt)); + +/** + * @brief Check if specified element is present in vector. + * + * @param[in] vector The vector data structure to use + * @param[in] elt The element to search for + * @return true If specified element is contained in the vector + * @return false + */ +#define vector_contains(vector, elt) \ + ({ \ + typeof (elt) _vector_var (x) = elt; \ + _vector_contains ((void *) (vector), sizeof ((vector)[0]), \ + (void *) (&_vector_var (x))); \ + }) + +/** + * @brief Remove the element at the specified position from the vector. + * Relative element order is preserved by shifting left the elements after the + * target. + * + * @param[in, out] vector The vector data structure to use + * @param[in] pos Position of the element to remove + * @return int 0 if successful, -1 otherwise + */ +#define vector_remove_at(vector, pos) \ + _vector_remove_at ((void **) &(vector), sizeof ((vector)[0]), (pos)) + +/** + * @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/lib/src/CMakeLists.txt b/lib/src/CMakeLists.txt index ef74127cc..8e81aa442 100644 --- a/lib/src/CMakeLists.txt +++ b/lib/src/CMakeLists.txt @@ -33,6 +33,9 @@ list(APPEND LIBHICN_SOURCE_FILES protocol/new.c util/ip_address.c util/log.c + util/pool.c + util/ring.c + util/vector.c ) if (WIN32) diff --git a/lib/src/common.c b/lib/src/common.c index c4cb8bc3e..362034942 100644 --- a/lib/src/common.c +++ b/lib/src/common.c @@ -54,61 +54,44 @@ get_addr_family (const char *ip_address) /* hashes */ -u32 -cumulative_hash32 (const void *data, size_t len, u32 lastValue) +// FNV-1a 32-bit http://www.isthe.com/chongo/tech/comp/fnv/ +typedef u_int32_t Fnv32_t; +#define FNV_32_PRIME ((Fnv32_t) 0x01000193) +#define FNV1_32_INIT ((Fnv32_t) 0x811c9dc5) +#define FNV1_32A_INIT FNV1_32_INIT + +Fnv32_t +cumulative_hash32 (const void *buf, size_t len, Fnv32_t hval) { - // Standard FNV 32-bit prime: see - // http://www.isthe.com/chongo/tech/comp/fnv/#FNV-param - const u32 fnv1a_prime = 0x01000193; - u32 hash = lastValue; - size_t i; - - const char *chardata = data; + unsigned char *bp = (unsigned char *) buf; /* start of buffer */ + unsigned char *be = bp + len; /* beyond end of buffer */ - for (i = 0; i < len; i++) + /* + * FNV-1a hash each octet in the buffer + */ + while (bp < be) { - hash = hash ^ chardata[i]; - hash = hash * fnv1a_prime; - } - return hash; -} + /* xor the bottom with the current octet */ + hval ^= (Fnv32_t) *bp++; -u32 -hash32 (const void *data, size_t len) -{ - // Standard FNV 32-bit offset: see - // http://www.isthe.com/chongo/tech/comp/fnv/#FNV-param - const u32 fnv1a_offset = 0x811C9DC5; - return cumulative_hash32 (data, len, fnv1a_offset); -} - -u64 -cumulative_hash64 (const void *data, size_t len, u64 lastValue) -{ - // Standard FNV 64-bit prime: see - // http://www.isthe.com/chongo/tech/comp/fnv/#FNV-param - const u64 fnv1a_prime = 0x00000100000001B3ULL; - u64 hash = lastValue; - const char *chardata = data; - size_t i; - - for (i = 0; i < len; i++) - { - hash = hash ^ chardata[i]; - hash = hash * fnv1a_prime; + /* multiply by the 32 bit FNV magic prime mod 2^32 */ +#if defined(NO_FNV_GCC_OPTIMIZATION) + hval *= FNV_32_PRIME; +#else + hval += + (hval << 1) + (hval << 4) + (hval << 7) + (hval << 8) + (hval << 24); +#endif } - return hash; + /* return our new hash value */ + return hval; } -u64 -hash64 (const void *data, size_t len) +u32 +hash32 (const void *data, size_t len) { - // Standard FNV 64-bit offset: see - // http://www.isthe.com/chongo/tech/comp/fnv/#FNV-param - const u64 fnv1a_offset = 0xCBF29CE484222325ULL; - return cumulative_hash64 (data, len, fnv1a_offset); + return cumulative_hash32 (data, len, FNV1_32A_INIT); } void diff --git a/lib/src/ops.c b/lib/src/ops.c index 80ffcf3c5..20362d69d 100644 --- a/lib/src/ops.c +++ b/lib/src/ops.c @@ -57,6 +57,10 @@ DECLARE_update_data_pathlabel (none, NONE); DECLARE_reset_data_for_hash (none, NONE); DECLARE_get_lifetime (none, NONE); DECLARE_set_lifetime (none, NONE); +DECLARE_get_source_port (none, NONE); +DECLARE_get_dest_port (none, NONE); +DECLARE_set_source_port (none, NONE); +DECLARE_set_dest_port (none, NONE); DECLARE_update_checksums (none, NONE); DECLARE_verify_checksums (none, NONE); DECLARE_rewrite_interest (none, NONE); diff --git a/lib/src/protocol/ah.c b/lib/src/protocol/ah.c index b3d24161d..c9ed40179 100644 --- a/lib/src/protocol/ah.c +++ b/lib/src/protocol/ah.c @@ -45,6 +45,10 @@ DECLARE_set_data_pathlabel (ah, UNEXPECTED); DECLARE_update_data_pathlabel (ah, UNEXPECTED); DECLARE_get_lifetime (ah, UNEXPECTED); DECLARE_set_lifetime (ah, UNEXPECTED); +DECLARE_get_source_port (ah, UNEXPECTED); +DECLARE_get_dest_port (ah, UNEXPECTED); +DECLARE_set_source_port (ah, UNEXPECTED); +DECLARE_set_dest_port (ah, UNEXPECTED); DECLARE_get_payload_length (ah, UNEXPECTED); DECLARE_set_payload_length (ah, UNEXPECTED); DECLARE_get_payload_type (ah, UNEXPECTED); diff --git a/lib/src/protocol/icmp.c b/lib/src/protocol/icmp.c index 0452e4fbb..1fc6c7d2f 100644 --- a/lib/src/protocol/icmp.c +++ b/lib/src/protocol/icmp.c @@ -38,6 +38,10 @@ DECLARE_set_data_pathlabel (icmp, UNEXPECTED); DECLARE_update_data_pathlabel (icmp, UNEXPECTED); DECLARE_get_lifetime (icmp, UNEXPECTED); DECLARE_set_lifetime (icmp, UNEXPECTED); +DECLARE_get_source_port (icmp, UNEXPECTED); +DECLARE_get_dest_port (icmp, UNEXPECTED); +DECLARE_set_source_port (icmp, UNEXPECTED); +DECLARE_set_dest_port (icmp, UNEXPECTED); DECLARE_get_length (icmp, UNEXPECTED); DECLARE_get_payload_length (icmp, UNEXPECTED); DECLARE_set_payload_length (icmp, UNEXPECTED); diff --git a/lib/src/protocol/ipv4.c b/lib/src/protocol/ipv4.c index 5d445f018..840fbe34b 100644 --- a/lib/src/protocol/ipv4.c +++ b/lib/src/protocol/ipv4.c @@ -228,6 +228,31 @@ ipv4_set_lifetime (hicn_type_t type, hicn_protocol_t *h, } int +ipv4_get_source_port (hicn_type_t type, const hicn_protocol_t *h, + u16 *source_port) +{ + return CHILD_OPS (get_source_port, type, h, source_port); +} + +int +ipv4_get_dest_port (hicn_type_t type, const hicn_protocol_t *h, u16 *dest_port) +{ + return CHILD_OPS (get_dest_port, type, h, dest_port); +} + +int +ipv4_set_source_port (hicn_type_t type, hicn_protocol_t *h, u16 source_port) +{ + return CHILD_OPS (set_source_port, type, h, source_port); +} + +int +ipv4_set_dest_port (hicn_type_t type, hicn_protocol_t *h, u16 dest_port) +{ + return CHILD_OPS (set_dest_port, type, h, dest_port); +} + +int ipv4_update_checksums (hicn_type_t type, hicn_protocol_t *h, u16 partial_csum, size_t payload_length) { diff --git a/lib/src/protocol/ipv6.c b/lib/src/protocol/ipv6.c index b3a107a13..b3c543249 100644 --- a/lib/src/protocol/ipv6.c +++ b/lib/src/protocol/ipv6.c @@ -212,6 +212,31 @@ ipv6_set_lifetime (hicn_type_t type, hicn_protocol_t *h, } int +ipv6_get_source_port (hicn_type_t type, const hicn_protocol_t *h, + u16 *source_port) +{ + return CHILD_OPS (get_source_port, type, h, source_port); +} + +int +ipv6_get_dest_port (hicn_type_t type, const hicn_protocol_t *h, u16 *dest_port) +{ + return CHILD_OPS (get_dest_port, type, h, dest_port); +} + +int +ipv6_set_source_port (hicn_type_t type, hicn_protocol_t *h, u16 source_port) +{ + return CHILD_OPS (set_source_port, type, h, source_port); +} + +int +ipv6_set_dest_port (hicn_type_t type, hicn_protocol_t *h, u16 dest_port) +{ + return CHILD_OPS (set_dest_port, type, h, dest_port); +} + +int ipv6_update_checksums (hicn_type_t type, hicn_protocol_t *h, u16 partial_csum, size_t payload_length) { diff --git a/lib/src/protocol/new.c b/lib/src/protocol/new.c index 8c79963ad..07c1d0d76 100644 --- a/lib/src/protocol/new.c +++ b/lib/src/protocol/new.c @@ -22,6 +22,11 @@ #pragma GCC diagnostic push #pragma GCC diagnostic ignored "-Wunused-function" +DECLARE_get_source_port (new, UNEXPECTED); +DECLARE_get_dest_port (new, UNEXPECTED); +DECLARE_set_source_port (new, UNEXPECTED); +DECLARE_set_dest_port (new, UNEXPECTED); + static int is_interest (u8 flags) { diff --git a/lib/src/protocol/tcp.c b/lib/src/protocol/tcp.c index 8097cfd12..82fc461ea 100644 --- a/lib/src/protocol/tcp.c +++ b/lib/src/protocol/tcp.c @@ -251,6 +251,35 @@ tcp_set_lifetime (hicn_type_t type, hicn_protocol_t *h, } int +tcp_get_source_port (hicn_type_t type, const hicn_protocol_t *h, + u16 *source_port) +{ + *source_port = ntohs (h->tcp.sport); + return HICN_LIB_ERROR_NONE; +} + +int +tcp_get_dest_port (hicn_type_t type, const hicn_protocol_t *h, u16 *dest_port) +{ + *dest_port = ntohs (h->tcp.dport); + return HICN_LIB_ERROR_NONE; +} + +int +tcp_set_source_port (hicn_type_t type, hicn_protocol_t *h, u16 source_port) +{ + h->tcp.sport = htons (source_port); + return HICN_LIB_ERROR_NONE; +} + +int +tcp_set_dest_port (hicn_type_t type, hicn_protocol_t *h, u16 dest_port) +{ + h->tcp.dport = htons (dest_port); + return HICN_LIB_ERROR_NONE; +} + +int tcp_update_checksums (hicn_type_t type, hicn_protocol_t *h, u16 partial_csum, size_t payload_length) { diff --git a/lib/src/protocol/udp.c b/lib/src/protocol/udp.c index ee46b8e9d..7a14b09c2 100644 --- a/lib/src/protocol/udp.c +++ b/lib/src/protocol/udp.c @@ -143,6 +143,35 @@ udp_set_lifetime (hicn_type_t type, hicn_protocol_t *h, } int +udp_get_source_port (hicn_type_t type, const hicn_protocol_t *h, + u16 *source_port) +{ + *source_port = ntohs (h->udp.src_port); + return HICN_LIB_ERROR_NONE; +} + +int +udp_get_dest_port (hicn_type_t type, const hicn_protocol_t *h, u16 *dest_port) +{ + *dest_port = ntohs (h->udp.dst_port); + return HICN_LIB_ERROR_NONE; +} + +int +udp_set_source_port (hicn_type_t type, hicn_protocol_t *h, u16 source_port) +{ + h->udp.src_port = htons (source_port); + return HICN_LIB_ERROR_NONE; +} + +int +udp_set_dest_port (hicn_type_t type, hicn_protocol_t *h, u16 dest_port) +{ + h->udp.dst_port = htons (dest_port); + return HICN_LIB_ERROR_NONE; +} + +int udp_update_checksums (hicn_type_t type, hicn_protocol_t *h, u16 partial_csum, size_t payload_length) { diff --git a/lib/src/util/log.c b/lib/src/util/log.c index 975762603..91a87e848 100644 --- a/lib/src/util/log.c +++ b/lib/src/util/log.c @@ -30,6 +30,10 @@ log_conf_t log_conf = DEFAULT_LOG_CONF; #define FMT_DATETIME_LEN 20 #define snprintf_nowarn(...) (snprintf (__VA_ARGS__) < 0 ? abort () : (void) 0) +#define COLOR_RED "\033[31m" +#define COLOR_YELLOW "\033[33m" +#define COLOR_RESET "\033[0m" + static char ts[FMT_DATETIME_LEN]; static char * @@ -104,7 +108,7 @@ _log_va (int level, const char *fmt, va_list ap) } else { - __android_log_vprint (ANDROID_LOG_INFO, "HICN FACEMGR", fmt, ap); + __android_log_vprint (prio, "HICN FACEMGR", fmt, ap); } #else @@ -112,6 +116,7 @@ _log_va (int level, const char *fmt, va_list ap) if (level > log_conf.log_level) return; + char *color = COLOR_RESET; switch (level) { case LOG_FATAL: @@ -119,9 +124,11 @@ _log_va (int level, const char *fmt, va_list ap) break; case LOG_ERROR: prefix = "ERROR: "; + color = COLOR_RED; break; case LOG_WARN: prefix = "WARNING: "; + color = COLOR_YELLOW; break; case LOG_INFO: prefix = ""; @@ -137,9 +144,9 @@ _log_va (int level, const char *fmt, va_list ap) break; } FILE *f = log_conf.log_file ? log_conf.log_file : stdout; - fprintf (f, "%s %s", timestamp (), prefix); + fprintf (f, "%s%s %s", color, timestamp (), prefix); vfprintf (f, fmt, ap); - fprintf (f, "\n"); + fprintf (f, "%s\n", COLOR_RESET); #ifdef DEBUG fflush (f); #endif diff --git a/lib/src/util/pool.c b/lib/src/util/pool.c new file mode 100644 index 000000000..c6be92ce8 --- /dev/null +++ b/lib/src/util/pool.c @@ -0,0 +1,174 @@ +/* + * 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 <hicn/util/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; + + WARN ("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; + 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/lib/src/util/ring.c b/lib/src/util/ring.c new file mode 100644 index 000000000..2c722a842 --- /dev/null +++ b/lib/src/util/ring.c @@ -0,0 +1,49 @@ + +/* + * 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 <hicn/util/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/lib/src/util/vector.c b/lib/src/util/vector.c new file mode 100644 index 000000000..1f5cd0269 --- /dev/null +++ b/lib/src/util/vector.c @@ -0,0 +1,101 @@ +/* + * 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 <hicn/util/vector.h> + +#define DEFAULT_VECTOR_SIZE 64 + +int +_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; + int rc = _vector_resize (vector_ptr, elt_size, init_size); + if (rc < 0) + return -1; + + vector_hdr_t *vh = vector_hdr (*vector_ptr); + vh->cur_size = 0; + vh->max_size = max_size; + + return 0; +} + +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; +} |