diff options
Diffstat (limited to 'hicn-light/src/hicn/base')
| -rw-r--r-- | hicn-light/src/hicn/base/CMakeLists.txt | 4 | ||||
| -rw-r--r-- | hicn-light/src/hicn/base/bitmap.h | 183 | ||||
| -rw-r--r-- | hicn-light/src/hicn/base/common.h | 4 | ||||
| -rw-r--r-- | hicn-light/src/hicn/base/loop.c | 340 | ||||
| -rw-r--r-- | hicn-light/src/hicn/base/loop.h | 98 | ||||
| -rw-r--r-- | hicn-light/src/hicn/base/pool.c | 133 | ||||
| -rw-r--r-- | hicn-light/src/hicn/base/pool.h | 212 | ||||
| -rw-r--r-- | hicn-light/src/hicn/base/test/CMakeLists.txt | 30 | ||||
| -rw-r--r-- | hicn-light/src/hicn/base/test/test-bitmap.cc | 141 | ||||
| -rw-r--r-- | hicn-light/src/hicn/base/test/test-hash.cc | 57 | ||||
| -rw-r--r-- | hicn-light/src/hicn/base/test/test-khash.cc | 139 | ||||
| -rw-r--r-- | hicn-light/src/hicn/base/test/test-loop.cc | 286 | ||||
| -rw-r--r-- | hicn-light/src/hicn/base/test/test-pool.cc | 210 | ||||
| -rw-r--r-- | hicn-light/src/hicn/base/test/test-vector.cc | 117 | ||||
| -rw-r--r-- | hicn-light/src/hicn/base/vector.c | 60 | ||||
| -rw-r--r-- | hicn-light/src/hicn/base/vector.h | 233 |
16 files changed, 1858 insertions, 389 deletions
diff --git a/hicn-light/src/hicn/base/CMakeLists.txt b/hicn-light/src/hicn/base/CMakeLists.txt index 5b2677ed1..6e5ed4a3e 100644 --- a/hicn-light/src/hicn/base/CMakeLists.txt +++ b/hicn-light/src/hicn/base/CMakeLists.txt @@ -36,3 +36,7 @@ set(TO_INSTALL_HEADER_FILES ${HEADER_FILES} PARENT_SCOPE ) + +if (BUILD_TESTS) + add_subdirectory(test) +endif()
\ No newline at end of file diff --git a/hicn-light/src/hicn/base/bitmap.h b/hicn-light/src/hicn/base/bitmap.h index df94b8039..46d473ff8 100644 --- a/hicn-light/src/hicn/base/bitmap.h +++ b/hicn-light/src/hicn/base/bitmap.h @@ -23,33 +23,186 @@ #ifndef UTIL_BITMAP_H #define UTIL_BITMAP_H +#include <assert.h> #include <string.h> +#include <sys/param.h> // MIN, MAX + +#include <hicn/util/log.h> + #include "common.h" +#include "vector.h" + +typedef uint_fast32_t bitmap_t; #define BITMAP_WIDTH(bitmap) (sizeof((bitmap)[0]) * 8) -#define bitmap_init(bitmap, size) \ - vector_init(bitmap, next_pow2(size / BITMAP_WIDTH(bitmap))) +/** + * @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))) -#define bitmap_ensure_pos(bitmap, pos) vector_ensure_pos(bitmap, pos / 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); +} -#define bitmap_get(bitmap, i) ((bitmap)[(i) / BITMAP_WIDTH(bitmap)] & (1 << ((i) % BITMAP_WIDTH(bitmap)))) +/** + * @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) -#define bitmap_is_set(bitmap, i) (bitmap_get((bitmap), (i)) == 1) +/** + * @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) -#define bitmap_set(bitmap, i) bitmap[(i) / BITMAP_WIDTH(bitmap)] |= 1 << ((i) % BITMAP_WIDTH(bitmap)) +/* + * @brief Returns whether the i-th bit is unset (equal to 0) in a bitmap. + * + * @param[in] bitmap The bitmap to access. + * @param[in] i The bit position. + * + * @return bool + */ +#define bitmap_set(bitmap, i) \ + _bitmap_set((bitmap_t**)&bitmap, i) + +/* + * @brief Returns whether the i-th bit is unset (equal to 0) in a bitmap (helper). + * + * @param[in] bitmap The bitmap to access. + * @param[in] i The bit position. + * + * @return bool + */ +static inline +int +_bitmap_set(bitmap_t ** bitmap, off_t i) +{ + if (bitmap_ensure_pos(bitmap, i) < 0) + return -1; + size_t offset = i / BITMAP_WIDTH(bitmap); + size_t pos = i % BITMAP_WIDTH(bitmap); + size_t shift = BITMAP_WIDTH(bitmap) - pos - 1; + (*bitmap)[offset] |= 1ul << 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_unset(bitmap, i) bitmap[(i) / BITMAP_WIDTH(bitmap)] &= ~ (1 << ((i) % BITMAP_WIDTH(bitmap))) +#define bitmap_set_to(bitmap, to) bitmap_set_range((bitmap), 0, (to)) -#define bitmap_set_to(bitmap, pos) \ -do { \ - size_t offset = (pos / BITMAP_WIDTH(bitmap) + 1); \ - memset(bitmap, 0xFF, pos * sizeof(bitmap[0])); \ - size_t set_bits = offset * BITMAP_WIDTH(bitmap); \ - for (unsigned i = pos; i < set_bits; i++) \ - bitmap_unset(bitmap, i); \ -} while(0); +#define bitmap_free(bitmap) vector_free(bitmap) #endif /* UTIL_BITMAP_H */ diff --git a/hicn-light/src/hicn/base/common.h b/hicn-light/src/hicn/base/common.h index 996050308..9ba426bb8 100644 --- a/hicn-light/src/hicn/base/common.h +++ b/hicn-light/src/hicn/base/common.h @@ -46,7 +46,7 @@ uint32_t __inline __builtin_clz(uint32_t value) { return 32; } -uint32_t __inline __builtin_clzll(uint64_t value) { +uint32_t __inline __builtin_clzl2(uint64_t value) { uint32_t leading_zero = 0; if (_BitScanReverse64(&leading_zero, value)) return 63 - leading_zero; @@ -57,6 +57,6 @@ uint32_t __inline __builtin_clzll(uint64_t value) { #define __builtin_clzl __builtin_clzll #endif -#define next_pow2(x) (x == 1 ? 1 : 1<<(64-__builtin_clzl(x-1))) +#define next_pow2(x) (x <= 1 ? 1 : 1ul <<(64-__builtin_clzl(x-1))) #endif /* UTIL_COMMON_H */ diff --git a/hicn-light/src/hicn/base/loop.c b/hicn-light/src/hicn/base/loop.c index fecab9c5f..d27e81f5b 100644 --- a/hicn-light/src/hicn/base/loop.c +++ b/hicn-light/src/hicn/base/loop.c @@ -20,51 +20,57 @@ #include <assert.h> #include <event2/event.h> +#include <event2/event_struct.h> #include <event2/thread.h> -#include <fcntl.h> // fcntl +#include <fcntl.h> // fcntl #ifdef WITH_THREAD #include <pthread.h> #endif /* WITH_THREAD */ -#include <stdlib.h> -#include <sys/timerfd.h> -#include <unistd.h> // fcntl - #include <hicn/util/log.h> -#include <hicn/util/map.h> +#include <stdlib.h> +#include <unistd.h> // fcntl #include "loop.h" -loop_t * MAIN_LOOP = NULL; +loop_t *MAIN_LOOP = NULL; /** * \brief Holds all callback parameters */ typedef struct { - void * owner; + void *owner; fd_callback_t callback; - void * data; + void *data; } cb_wrapper_args_t; -TYPEDEF_MAP_H(event_map, int, struct event *); -TYPEDEF_MAP(event_map, int, struct event *, int_cmp, int_snprintf, generic_snprintf); - -/* Map that associates timer fds with their associated cb_wrapper_args_t */ -TYPEDEF_MAP_H(timer_fd_map, int, cb_wrapper_args_t *); -TYPEDEF_MAP(timer_fd_map, int, cb_wrapper_args_t *, int_cmp, int_snprintf, generic_snprintf); +typedef enum { + EVTYPE_TIMER, + EVTYPE_FD, +} event_type_t; struct loop_s { - struct event_base * event_base; - event_map_t * event_map; - timer_fd_map_t * timer_fd_map; -#ifdef WITH_THREAD - pthread_t thread; -#endif /* WITH_THREAD */ + /* Libevent-based implementation */ + struct event_base *event_base; +}; + +struct event_s { + /* Reference to loop */ + loop_t *loop; + + /* Event type*/ + event_type_t event_type; + + /* Raw event */ + struct event raw_event; + + /* Callback on event */ + cb_wrapper_args_t callback; }; -loop_t * -loop_create() +loop_t *loop_create() { - loop_t * loop = malloc(sizeof(loop_t)); + loop_t *loop = malloc(sizeof(loop_t)); + if (!loop) { ERROR("[loop_create] Failed to allocate memory"); goto ERR_MALLOC; @@ -75,281 +81,135 @@ loop_create() #endif /* WITH_THREAD */ loop->event_base = event_base_new(); - if (!loop) - goto ERR_EVENT; - - loop->event_map = event_map_create(); - if (!loop->event_map) { - ERROR("[loop_create] Failed to create event_map"); - goto ERR_EVENT_MAP; - } - - loop->timer_fd_map = timer_fd_map_create(); - if (!loop->timer_fd_map) { - ERROR("[loop_create] Failed to create timer_fd_map"); - goto ERR_TIMER_FD_MAP; - } + if (!loop->event_base) goto ERR_EVENT; event_set_log_callback(NULL); return loop; - timer_fd_map_free(loop->timer_fd_map); -ERR_TIMER_FD_MAP: - event_map_free(loop->event_map); -ERR_EVENT_MAP: - event_base_free(loop->event_base); ERR_EVENT: - free(loop); ERR_MALLOC: return NULL; } -void -loop_free(loop_t * loop) -{ - /* - * Release all timer cb_wrapper_args_t - * - * We need to stop all timers, this should release associated fd events at - * the same time... for that reason, this code has to be called before - * releasing events - */ - - int * timer_fd_map_array; - int n = timer_fd_map_get_key_array(loop->timer_fd_map, &timer_fd_map_array); - if (n < 0) { - ERROR("[loop_free] Could not get event map array"); - } else { - for (unsigned i = 0; i < n; i++) { - int fd = timer_fd_map_array[i]; - if (loop_unregister_timer(loop, fd) < 0) { - ERROR("[loop_free] Could not unregister timer"); - } - } - free(timer_fd_map_array); - } - timer_fd_map_free(loop->timer_fd_map); - - /* Release all events */ - - int * event_map_array; - n = event_map_get_key_array(loop->event_map, &event_map_array); - if (n < 0) { - ERROR("[loop_free] Could not get event map array"); - } else { - for (unsigned i = 0; i < n; i++) { - int fd = event_map_array[i]; - if (loop_unregister_fd(loop, fd) < 0) { - ERROR("[loop_free] Could not unregister fd"); - } - } - free(event_map_array); - } - event_map_free(loop->event_map); - +void loop_free(loop_t *loop) { event_base_free(loop->event_base); - free(loop); } -int -loop_dispatch(loop_t * loop) +int _loop_dispatch(loop_t *loop, int flags) { -#ifdef WITH_THREAD - if (pthread_create(&loop->thread, NULL, (void * (*)(void *))event_base_dispatch, loop->event_base)) { - fprintf(stderr, "Error creating thread\n"); - return -1; - } -#else - event_base_dispatch(loop->event_base); -#endif /* WITH_THREAD */ + event_base_loop(loop->event_base, flags); return 0; } -int -loop_undispatch(loop_t * loop) +int loop_dispatch(loop_t *loop) { -#ifdef WITH_THREAD - DEBUG("Waiting for loop to terminate..."); - if(pthread_join(loop->thread, NULL)) { - fprintf(stderr, "Error joining thread\n"); - return -1; - } - DEBUG("Loop terminated !"); -#endif /* WITH_THREAD */ - return 0; + return _loop_dispatch(loop, EVLOOP_NO_EXIT_ON_EMPTY); } -void -loop_break(loop_t * loop) -{ - event_base_loopbreak(loop->event_base); -} +int loop_undispatch(loop_t *loop) { return 0; } + +void loop_break(loop_t *loop) { event_base_loopbreak(loop->event_base); } -void cb_wrapper(evutil_socket_t fd, short what, void * arg) { - cb_wrapper_args_t * cb_wrapper_args = arg; - cb_wrapper_args->callback(cb_wrapper_args->owner, fd, cb_wrapper_args->data); +void cb_wrapper(evutil_socket_t fd, short what, void *arg) +{ + cb_wrapper_args_t *cb_wrapper_args = arg; + cb_wrapper_args->callback(cb_wrapper_args->owner, fd, + cb_wrapper_args->data); } -int -loop_register_fd(loop_t * loop, int fd, void * callback_owner, - fd_callback_t callback, void * callback_data) +static inline void _event_create(event_t **event, loop_t *loop, + event_type_t type, void *callback_owner, + fd_callback_t callback, void *callback_data) { - /* This will be freed with the event */ - cb_wrapper_args_t * cb_wrapper_args = malloc(sizeof(cb_wrapper_args_t)); - *cb_wrapper_args = (cb_wrapper_args_t) { + *event = malloc(sizeof(event_t)); + (*event)->callback = (cb_wrapper_args_t){ .owner = callback_owner, .callback = callback, .data = callback_data, }; + (*event)->event_type = type; + (*event)->loop = loop; +} + +int loop_fd_event_create(event_t **event, loop_t *loop, int fd, + void *callback_owner, fd_callback_t callback, + void *callback_data) +{ + _event_create(event, loop, EVTYPE_FD, callback_owner, callback, + callback_data); evutil_make_socket_nonblocking(fd); - struct event * event = event_new(loop->event_base, fd, EV_READ | EV_PERSIST, cb_wrapper, cb_wrapper_args); - if (!event) { - ERROR("[loop_register_fd] event_new"); - goto ERR_EVENT_NEW; - } + event_assign(&(*event)->raw_event, loop->event_base, fd, + EV_READ | EV_PERSIST, cb_wrapper, &(*event)->callback); + + return 0; +} - if (event_add(event, NULL) < 0) { +int loop_fd_event_register(event_t *event) +{ + assert(event->event_type == EVTYPE_FD); + + if (event_add(&event->raw_event, NULL) < 0) { ERROR("[loop_register_fd] event_add"); goto ERR_EVENT_ADD; } - if (event_map_add(loop->event_map, fd, event) < 0) { - ERROR("[loop_register_fd] event_map_add"); - goto ERR_EVENT_MAP; - } - return 0; -ERR_EVENT_MAP: ERR_EVENT_ADD: - event_free(event); -ERR_EVENT_NEW: return -1; } -int -loop_unregister_fd(loop_t * loop, int fd) +int loop_event_unregister(event_t *event) { - struct event * event = NULL; - - if (event_map_remove(loop->event_map, fd, &event) < 0) { - ERROR("[loop_unregister_fd] Error removing event associated to fd"); - return -1; - } - - assert(event); - - cb_wrapper_args_t * cb_wrapper_args = event_get_callback_arg(event); - free(cb_wrapper_args); - - event_del(event); - event_free(event); - + event_del(&event->raw_event); return 0; } -int -loop_timer_callback(loop_t * loop, int fd, void * data) +int loop_timer_create(event_t **timer, loop_t *loop, void *callback_owner, + fd_callback_t callback, void *callback_data) { - char buf[1024]; /* size is not important */ - cb_wrapper_args_t * cb_wrapper_args = data; - while (read(fd, &buf, sizeof(buf)) > 0) - ; + _event_create(timer, loop, EVTYPE_TIMER, callback_owner, callback, + callback_data); - int rc = cb_wrapper_args->callback(cb_wrapper_args->owner, fd, - cb_wrapper_args->data); + evtimer_assign(&(*timer)->raw_event, loop->event_base, cb_wrapper, + &(*timer)->callback); - return rc; + return 0; } -int -_loop_register_timer(loop_t * loop, unsigned delay_ms, void * owner, - fd_callback_t callback, void * data) +static inline void _ms_to_timeval(unsigned delay_ms, struct timeval *tv) { - int fd = timerfd_create(CLOCK_MONOTONIC, 0); - if (fd == -1) { - perror("timerfd_create"); - return -1; - } - - if (fcntl(fd, F_SETFL, O_NONBLOCK) < 0) { - perror("fcntl"); - return -1; - } - - struct itimerspec ts = { - .it_interval = { - .tv_sec = delay_ms / 1000, - .tv_nsec = (delay_ms % 1000) * 1000000, - }, - .it_value = { - .tv_sec = delay_ms / 1000, - .tv_nsec = (delay_ms % 1000) * 1000000, - } - }; - - if (timerfd_settime(fd, 0, &ts, NULL) == -1) { - perror("timerfd_settime"); - return -1; - } + tv->tv_sec = delay_ms / 1000; + tv->tv_usec = (delay_ms % 1000) * 1000; +} - /* This should be freed together with the timer release */ - cb_wrapper_args_t * cb_wrapper_args = malloc(sizeof(cb_wrapper_args_t)); - *cb_wrapper_args = (cb_wrapper_args_t) { - .owner = owner, - .callback = callback, - .data = data, - }; +int loop_timer_register(event_t *timer, unsigned delay_ms) +{ + assert(timer->event_type == EVTYPE_TIMER); - if (timer_fd_map_add(loop->timer_fd_map, fd, cb_wrapper_args) < 0) { - ERROR("[loop_register_timer] Could not add cb_wrapper to timer map"); - return -1; - } + struct timeval tv; + _ms_to_timeval(delay_ms, &tv); - if (loop_register_fd(loop, fd, loop, - (fd_callback_t) loop_timer_callback, cb_wrapper_args) < 0) { - ERROR("[loop_register_timer] Error registering fd to event loop"); - return -1; + if (tv.tv_sec == 0 && tv.tv_usec == 0) { + event_active(&timer->raw_event, EV_TIMEOUT, 0); + } else { + event_add(&timer->raw_event, &tv); } - return fd; + return 0; } -int -loop_unregister_timer(loop_t * loop, int fd) +int loop_timer_is_enabled(event_t *timer) { - struct itimerspec ts = { - .it_interval = { - .tv_sec = 0, - .tv_nsec = 0, - }, - .it_value = { /* This value disables the timer */ - .tv_sec = 0, - .tv_nsec = 0, - } - }; - ts.it_value.tv_sec = 0; - - if (timerfd_settime(fd, 0, &ts, NULL) == -1) { - perror("timerfd_settime"); - return -1; - } - - cb_wrapper_args_t * cb_wrapper_args; - if (timer_fd_map_remove(loop->timer_fd_map, fd, &cb_wrapper_args) < 0) { - ERROR("[loop_unregister_timer] Could not remove cb_wrapper from timer map"); - return -1; - } - assert(cb_wrapper_args); - free(cb_wrapper_args); - - if (loop_unregister_fd(loop, fd) < 0) { - ERROR("[loop_unregister_timer] Error unregistering fd from event loop"); - return -1; - } + return evtimer_pending(&timer->raw_event, NULL) != 0; +} - return 0; +int loop_event_free(event_t *event) +{ + int ret = loop_event_unregister(event); + free(event); + return ret; } diff --git a/hicn-light/src/hicn/base/loop.h b/hicn-light/src/hicn/base/loop.h index b73d91738..544d73cd7 100644 --- a/hicn-light/src/hicn/base/loop.h +++ b/hicn-light/src/hicn/base/loop.h @@ -1,5 +1,5 @@ /* - * Copyright (c) 2017-2019 Cisco and/or its affiliates. + * Copyright (c) 2020 Cisco and/or its affiliates. * Licensed under the Apache License, Version 2.0 (the "License"); * you may not use this file except in compliance with the License. * You may obtain a copy of the License at: @@ -18,87 +18,125 @@ * \brief Face manager main loop */ -#ifndef FACEMGR_LOOP_H -#define FACEMGR_LOOP_H +#ifndef UTIL_LOOP_H +#define UTIL_LOOP_H /* fd & timer callbacks */ -typedef int (*fd_callback_t)(void * owner, int fd, void * data); +typedef int (*fd_callback_t)(void *owner, int fd, void *data); typedef struct { int fd; void *owner; fd_callback_t callback; - //int (*callback)(void * owner, int fd, void * data); void *data; } fd_callback_data_t; /* loop */ typedef struct loop_s loop_t; +typedef struct event_s event_t; -/* Global loop to be used in single threaded applications */ -extern loop_t * MAIN_LOOP; +extern loop_t *MAIN_LOOP; /** * \brief Creates a main loop * \return Pointer to the newly created loop, or NULL in case of error */ -loop_t * loop_create(); +loop_t *loop_create(); /** * \brief Releases a loop instance and frees all associated memory * \param [in] loop - Pointer to the loop instance to free */ -void loop_free(loop_t * loop); +void loop_free(loop_t *loop); /** - * \brief Runs the loop instance to process events + * \brief Runs the loop instance to process events (helper). * \param [in] loop - Pointer to the loop instance + * \param [in] flags - Loop mode: EVLOOP_ONCE, EVLOOP_NONBLOCK or EVLOOP_NO_EXIT_ON_EMPTY * \return 0 if successful, -1 otherwise */ -int loop_dispatch(loop_t * loop); +int _loop_dispatch(loop_t *loop, int flags); + +/** + * \brief Runs the loop instance to process events. + * \param [in] loop - Pointer to the loop instance + * \return 0 if successful, -1 otherwise + */ +int loop_dispatch(loop_t *loop); /** * \brief Terminates the dispatching of events * \param [in] loop - Pointer to the loop instance */ -int loop_undispatch(loop_t * loop); +int loop_undispatch(loop_t *loop); /** * \brief Breaks out of the loop * \param [in] loop - Pointer to the loop instance */ -void loop_break(loop_t * loop); +void loop_break(loop_t *loop); -/** - * \brief Registers a new file descriptor to the event loop - * \param [in] fd - File descriptor to register +/** Create new event associated with given fd. + * \param [out] event - Struct representing new fd event + * \param [in] loop - Loop running events + * \param [in] fd - fd to register * \param [in] callback_owner - Pointer to the owner of the callack (first * parameter of callback function) * \param [in] callback - Callback function * \param [in] callback_data - User data to pass alongside callback invocation * \return 0 in case of success, -1 otherwise */ -int -loop_register_fd(loop_t * loop, int fd, void * callback_owner, - fd_callback_t callback, void * callback_data); +int loop_fd_event_create(event_t **event, loop_t *loop, int fd, + void *callback_owner, fd_callback_t callback, + void *callback_data); /** - * \brief Unregisters a file descriptor from the event loop - * \param [in] fd - File descriptor to unregister + * Register event in corresponding event loop. + * \param [in] event - Struct representing fd event * \return 0 in case of success, -1 otherwise */ -int -loop_unregister_fd(loop_t * loop, int fd); +int loop_fd_event_register(event_t *event); -int _loop_register_timer(loop_t * loop, unsigned delay_ms, void * owner, - fd_callback_t callback, void * data); +/** + * Unregister event from corresponding event loop. + * \param [in] event - Struct representing fd event + * \return 0 in case of success, -1 otherwise + */ +int loop_event_unregister(event_t *event); -#define loop_register_timer(loop, delay_ms, owner, callback, data) \ - _loop_register_timer(loop, delay_ms, owner, (fd_callback_t) callback, data) +/** + * Free event object. + * \param [in] event - Struct representing the event + * \return 0 in case of success, -1 otherwise + */ +int loop_event_free(event_t *event); -int -loop_unregister_timer(loop_t * loop, int fd); +/** Create new timer event. + * \param [out] event - Struct representing new timer event + * \param [in] loop - Loop running events + * \param [in] callback_owner - Pointer to the owner of the callack (first + * parameter of callback function) + * \param [in] callback - Callback function + * \param [in] callback_data - User data to pass alongside callback invocation + * \return 0 in case of success, -1 otherwise + */ +int loop_timer_create(event_t **timer, loop_t *loop, void *callback_owner, + fd_callback_t callback, void *callback_data); + +/** + * Register event in corresponding event loop. + * \param [in] timer - Struct representing timer event + * \return 0 in case of success, -1 otherwise + */ +int loop_timer_register(event_t *timer, unsigned delay_ms); + +/** + * Check if timer is enabled. + * \param [in] timer - Struct representing timer event + * \return 1 if enabled, 0 otherwise + */ +int loop_timer_is_enabled(event_t *timer); -#endif /* FACEMGR_LOOP_H */ +#endif /* UTIL_LOOP_H */ diff --git a/hicn-light/src/hicn/base/pool.c b/hicn-light/src/hicn/base/pool.c index abca86422..662c1233c 100644 --- a/hicn-light/src/hicn/base/pool.c +++ b/hicn-light/src/hicn/base/pool.c @@ -15,48 +15,76 @@ /** * \file pool.c - * \brief Implementation of fixed-size pool allocator + * \brief Implementation of fixed-size pool allocator. + * + * NOTE: + * - Ideally, we should have a single realloc per resize, that would encompass + * both the free indices vector and bitmap, by nesting data structures. Because + * of the added complexity, and by lack of evidence of the need for this, we + * currently rely on a simpler implementation. */ +#include <assert.h> #include <stdlib.h> // calloc #include "common.h" #include "pool.h" +#include <stdio.h> // XXX -/** - * \brief Initialize the pool data structure - * \param [in,out] pool - Pointer to the pool structure storage - * \param [in] elt_size - Size of elements in vector - * \param [in] max_elts - Maximum size - * - * Note that an empty pool might be equal to NULL - */ void -_pool_init(void ** pool_ptr, size_t elt_size, size_t max_elts) +_pool_init(void ** pool_ptr, size_t elt_size, size_t init_size, size_t max_size) { - pool_hdr_t * ph = calloc(POOL_HDRLEN + elt_size * max_elts, 1); + 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) - abort(); + 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, max_elts); + vector_init(free_indices, init_size, max_size); + for(unsigned i = 0; i < init_size; i++) + free_indices[i] = (init_size - 1) - i; + vector_len(free_indices) = init_size; + ph->free_indices = free_indices; + /* Free bitmap */ uint_fast32_t * fb = ph->free_bitmap; - bitmap_init(fb, max_elts); - bitmap_set_to(fb, max_elts); - - for(unsigned i = 0; i < max_elts; i++) - free_indices[i] = (max_elts - 1) - i; - ph->free_indices = free_indices; + 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; } @@ -65,24 +93,69 @@ void _pool_resize(void ** pool_ptr, size_t elt_size) { pool_hdr_t * ph = pool_hdr(*pool_ptr); - size_t old_elts = ph->max_elts; - size_t new_elts = old_elts * 2; + size_t old_size = ph->alloc_size; + size_t new_size = old_size * 2; + + if (ph->max_size && new_size > ph->max_size) + goto ERR_MAX_SIZE; /* Double pool storage */ - ph = realloc(ph, POOL_HDRLEN + new_elts * elt_size); + ph = realloc(ph, POOL_HDRLEN + new_size * elt_size); if (!ph) - abort(); - ph->max_elts = new_elts; + goto ERR_REALLOC; + ph->elt_size = elt_size; + ph->alloc_size = new_size; /* - * After resize, the pool will have old_elts free indices, ranging from - * old_elts to (new_elts - 1) + * After resize, the pool will have new free indices, ranging from + * old_size to (new_size - 1) */ - off_t * free_indices = ph->free_indices; - vector_ensure_pos(free_indices, old_elts); - for (unsigned i = 0; i < old_elts; i++) - free_indices[i] = new_elts - 1 - i; + vector_ensure_pos(ph->free_indices, old_size); + for (unsigned i = 0; i < old_size; i++) + ph->free_indices[i] = new_size - 1 - i; + vector_len(ph->free_indices) = old_size; + + /* We also need to update the bitmap */ + bitmap_ensure_pos(&(ph->free_bitmap), new_size - 1); + bitmap_set_range(ph->free_bitmap, old_size, new_size - 1); /* Reassign pool pointer */ *pool_ptr = (uint8_t*)ph + POOL_HDRLEN; + + return; + +ERR_REALLOC: +ERR_MAX_SIZE: + *pool_ptr = NULL; + return; +} + +off_t +_pool_get(void ** pool_ptr, void ** elt, size_t elt_size) +{ + pool_hdr_t * ph = pool_hdr(*pool_ptr); + uint64_t l = vector_len(ph->free_indices); + if (l == 0) { + _pool_resize(pool_ptr, elt_size); + ph = pool_hdr(*pool_ptr); + l = vector_len(ph->free_indices); + } + off_t free_id = ph->free_indices[l - 1]; + vector_len(ph->free_indices)--; + bitmap_unset(ph->free_bitmap, free_id); + *elt = *pool_ptr + free_id * elt_size; + memset(*elt, 0, elt_size); + return free_id; +} + +void +_pool_put(void ** pool_ptr, void ** elt, size_t elt_size) +{ + pool_hdr_t * ph = pool_hdr(*pool_ptr); + uint64_t l = vector_len(ph->free_indices); + vector_ensure_pos(ph->free_indices, l); + off_t freed_id = (*elt - *pool_ptr) / elt_size; + ph->free_indices[l] = freed_id; + vector_len(ph->free_indices)++; + bitmap_set(ph->free_bitmap, freed_id); } diff --git a/hicn-light/src/hicn/base/pool.h b/hicn-light/src/hicn/base/pool.h index 360dedc5e..85117c452 100644 --- a/hicn-light/src/hicn/base/pool.h +++ b/hicn-light/src/hicn/base/pool.h @@ -15,7 +15,28 @@ /** * \file array.h - * \brief Fixed-size pool allocator + * \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 @@ -26,66 +47,163 @@ #include "bitmap.h" #include "vector.h" -/** Local variable naming macro. */ -#define _pool_var(v) _pool_##v - +/* Pool header */ typedef struct { size_t elt_size; - size_t max_elts; - uint_fast32_t * free_bitmap; + 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; -void _pool_init(void ** pool_ptr, size_t elt_size, size_t max_elts); +#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); -#define POOL_HDRLEN SIZEOF_ALIGNED(pool_hdr_t) +/** + * @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); -/* This header actually prepends the actual content of the pool */ -#define pool_hdr(pool) ((pool_hdr_t *)((uint8_t*)(pool) - POOL_HDRLEN)) +/** + * @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); -// XXX TODO need common naming for cur_len, len, max_len -#define pool_elts(pool) \ - (pool_hdr(pool)->max_elts - vector_len((pool_hdr(pool)->free_indices))) +/******************************************************************************/ +/* Public API */ -#define pool_init(pool, max_elts) \ - _pool_init((void**)&pool, sizeof(pool[0]), max_elts); +/** + * @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); -#define pool_free(pool) \ - _pool_free((void**)&pool); +/** + * @brief Free a pool data structure. + * + * @param[in] pool The pool data structure to free. + */ +#define pool_free(pool) _pool_free((void**)&pool); -#define pool_get(pool, elt) \ -do { \ - pool_hdr_t * _pool_var(ph) = pool_hdr(pool); \ - u64 _pool_var(l) = vector_len(_pool_var(ph)->free_indices); \ - if (_pool_var(l) == 0) \ - _pool_resize((void**)&(pool), sizeof((pool)[0])); \ - off_t _pool_var(free_id) = \ - _pool_var(ph)->free_indices[_pool_var(l) - 1]; \ - elt = (pool) + _pool_var(free_id); \ - memset(&elt, 0, sizeof(elt)); \ -} while(0) +/** + * @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)) -#define pool_put(pool, elt) \ -do { \ - pool_hdr_t * _pool_var(ph) = pool_hdr(pool); \ - u64 _pool_var(l) = vector_len(_pool_var(ph)->free_indices); \ - vector_ensure_pos(_pool_var(ph)->free_indices, _pool_var(l)); \ - _pool_var(ph)->free_indices[_pool_var(l)] = (elt) - (pool); \ - vector_len(_pool_var(ph)->free_indices)++; \ - bitmap_set(_pool_var(ph)->free_bitmap, _pool_var(l)); \ -} while(0) +/** + * @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) \ bitmap_is_unset((pool_hdr(pool))->free_bitmap, (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); \ uint_fast32_t * _pool_var(fb) = _pool_var(ph)->free_bitmap; \ - for((i) = 0; (i) < _pool_var(ph)->max_elts; (i)++) { \ + for((i) = 0; (i) < _pool_var(ph)->max_size; (i)++) { \ if (bitmap_is_unset(_pool_var(fb), (i))) \ continue; \ eltp = (pool) + (i); \ @@ -93,12 +211,28 @@ do { \ } \ } 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) - +#ifdef WITH_TESTS +#define pool_get_alloc_size(bitmap) pool_hdr(pool)->alloc_size +#define pool_get_free_indices(pool) pool_hdr(pool)->free_indices +#define pool_get_free_bitmap(pool) pool_hdr(pool)->free_bitmap +#endif /* WITH_TESTS */ #endif /* UTIL_POOL_H */ diff --git a/hicn-light/src/hicn/base/test/CMakeLists.txt b/hicn-light/src/hicn/base/test/CMakeLists.txt new file mode 100644 index 000000000..cdf6ed11b --- /dev/null +++ b/hicn-light/src/hicn/base/test/CMakeLists.txt @@ -0,0 +1,30 @@ +# Copyright (c) 2017-2019 Cisco and/or its affiliates. + +include(BuildMacros) + +list(APPEND TESTS + test-bitmap + test-hash + test-khash + test-loop + test-pool + test-vector +) + +foreach(test ${TESTS}) + build_executable(${test} + NO_INSTALL + SOURCES ${test}.cc + LINK_LIBRARIES ${LIBHICN_LIGHT_SHARED} ${LIBHICNCTRL_SHARED} ${GTEST_LIBRARIES} ${CMAKE_THREAD_LIBS_INIT} + INCLUDE_DIRS ${HICN_LIGHT_INCLUDE_DIRS} ${GTEST_INCLUDE_DIRS} + DEPENDS gtest ${LIBHICNCTRL_SHARED} ${LIBHICN_LIGHT_SHARED} + COMPONENT ${HICN_LIGHT} + DEFINITIONS "${COMPILER_DEFINITIONS}" + ) + + if(${CMAKE_VERSION} VERSION_GREATER "3.10.0") + gtest_discover_tests(${test}-bin TEST_PREFIX new:) + else() + add_test(NAME ${test}-bin COMMAND ${test}) + endif() +endforeach() diff --git a/hicn-light/src/hicn/base/test/test-bitmap.cc b/hicn-light/src/hicn/base/test/test-bitmap.cc new file mode 100644 index 000000000..d1b335ace --- /dev/null +++ b/hicn-light/src/hicn/base/test/test-bitmap.cc @@ -0,0 +1,141 @@ +/* + * Copyright (c) 2020 Cisco and/or its affiliates. + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at: + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include <gtest/gtest.h> + +#include <stdio.h> +#include <stdlib.h> +#include <string.h> +#include <sys/socket.h> +#include <sys/un.h> +#include <unistd.h> +#include <netinet/in.h> + +extern "C" { +#define WITH_TESTS +#include <hicn/base/bitmap.h> +} + +#define DEFAULT_SIZE 10 + +class BitmapTest : public ::testing::Test { +protected: + BitmapTest() { } + + virtual ~BitmapTest() { } + + bitmap_t * bitmap; +}; + +/* + * TEST: bitmap allocation + */ +TEST_F(BitmapTest, BitmapAllocation) +{ + int rc; + + /* + * We take a value < 32 on purpose to avoid confusion on the choice of a 32 + * or 64 bit integer for storage + */ + size_t size_not_pow2 = DEFAULT_SIZE; + bitmap_init(bitmap, size_not_pow2, 0); + + /* + * Bitmap should have been allocated with a size rounded to the next power + * of 2 + */ + EXPECT_EQ(bitmap_get_alloc_size(bitmap), 1UL); + + /* By default, no element should be set */ + EXPECT_FALSE(bitmap_is_set(bitmap, 0)); + EXPECT_TRUE(bitmap_is_unset(bitmap, 0)); + + EXPECT_EQ(bitmap_get_alloc_size(bitmap), 1UL); + + EXPECT_FALSE(bitmap_is_set(bitmap, size_not_pow2 - 1)); + EXPECT_TRUE(bitmap_is_unset(bitmap, size_not_pow2 - 1)); + + /* Bitmap should not have been reallocated */ + EXPECT_EQ(bitmap_get_alloc_size(bitmap), 1UL); + + /* After setting a bit after the end, bitmap should have been reallocated */ + bitmap_set(bitmap, sizeof(bitmap[0]) * 8 - 1); + EXPECT_EQ(bitmap_get_alloc_size(bitmap), 1UL); + + /* After setting a bit after the end, bitmap should have been reallocated */ + rc = bitmap_set(bitmap, sizeof(bitmap[0]) * 8); + EXPECT_GE(rc, 0); + EXPECT_EQ(bitmap_get_alloc_size(bitmap), 2UL); + + rc = bitmap_set(bitmap, sizeof(bitmap[0]) * 8 + 1); + EXPECT_GE(rc, 0); + EXPECT_EQ(bitmap_get_alloc_size(bitmap), 2UL); + + bitmap_free(bitmap); + + size_t size_pow2 = 16; + + /* Limiting test for allocation size */ + bitmap_init(bitmap, size_pow2, 0); + EXPECT_EQ(bitmap_get_alloc_size(bitmap), 1UL); + + bitmap_free(bitmap); +} + +TEST_F(BitmapTest, BitmapSet) +{ + bitmap_init(bitmap, DEFAULT_SIZE, 0); + + bitmap_set(bitmap, 20); + EXPECT_TRUE(bitmap_is_set(bitmap, 20)); + EXPECT_FALSE(bitmap_is_unset(bitmap, 20)); + EXPECT_FALSE(bitmap_is_set(bitmap, 19)); + EXPECT_TRUE(bitmap_is_unset(bitmap, 19)); + + bitmap_free(bitmap); +} + +TEST_F(BitmapTest, BitmapUnSet) { + bitmap_init(bitmap, DEFAULT_SIZE, 0); + + bitmap_set(bitmap, 20); + bitmap_set(bitmap, 19); + bitmap_unset(bitmap, 20); + EXPECT_FALSE(bitmap_is_set(bitmap, 20)); + EXPECT_TRUE(bitmap_is_unset(bitmap, 20)); + EXPECT_TRUE(bitmap_is_set(bitmap, 19)); + EXPECT_FALSE(bitmap_is_unset(bitmap, 19)); + + bitmap_free(bitmap); +} + +TEST_F(BitmapTest, BitmapSetTo) { + bitmap_init(bitmap, DEFAULT_SIZE, 0); + + bitmap_set_to(bitmap, 40); + EXPECT_TRUE(bitmap_is_set(bitmap, 20)); + EXPECT_TRUE(bitmap_is_set(bitmap, 21)); + EXPECT_TRUE(bitmap_is_unset(bitmap, 41)); + EXPECT_TRUE(bitmap_is_unset(bitmap, 42)); + + bitmap_free(bitmap); +} + +int main(int argc, char **argv) +{ + ::testing::InitGoogleTest(&argc, argv); + return RUN_ALL_TESTS(); +} diff --git a/hicn-light/src/hicn/base/test/test-hash.cc b/hicn-light/src/hicn/base/test/test-hash.cc new file mode 100644 index 000000000..78e318794 --- /dev/null +++ b/hicn-light/src/hicn/base/test/test-hash.cc @@ -0,0 +1,57 @@ +/* + * Copyright (c) 2020 Cisco and/or its affiliates. + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at: + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include <gtest/gtest.h> + +#include <stdio.h> +#include <stdlib.h> +#include <string.h> +#include <sys/socket.h> +#include <sys/un.h> +#include <unistd.h> +#include <netinet/in.h> + +extern "C" { +#include <hicn/base/hash.h> +} + +class HashTest : public ::testing::Test { + protected: + HashTest() { + } + + virtual ~HashTest() { + // You can do clean-up work that doesn't throw exceptions here. + } + + // If the constructor and destructor are not enough for setting up + // and cleaning up each test, you can define the following methods: + + virtual void SetUp() { + // Code here will be called immediately after the constructor (right + // before each test). + } + + virtual void TearDown() { + // Code here will be called immediately after each test (right + // before the destructor). + } +}; + +int main(int argc, char **argv) +{ + ::testing::InitGoogleTest(&argc, argv); + return RUN_ALL_TESTS(); +} diff --git a/hicn-light/src/hicn/base/test/test-khash.cc b/hicn-light/src/hicn/base/test/test-khash.cc new file mode 100644 index 000000000..798063ca5 --- /dev/null +++ b/hicn-light/src/hicn/base/test/test-khash.cc @@ -0,0 +1,139 @@ +/* + * Copyright (c) 2020 Cisco and/or its affiliates. + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at: + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include <gtest/gtest.h> + +#include <stdio.h> +#include <stdlib.h> +#include <string.h> +#include <sys/socket.h> +#include <sys/un.h> +#include <unistd.h> +#include <netinet/in.h> + +extern "C" { +#include <hicn/base/khash.h> + +} + +KHASH_MAP_INIT_INT(int, unsigned char) + +typedef struct { + unsigned key; + unsigned char val; +} int_unpack_t; + +typedef struct { + unsigned key; + unsigned char val; +} __attribute__ ((__packed__)) int_packed_t; + +#define hash_eq(a, b) ((a).key == (b).key) +#define hash_func(a) ((a).key) + +KHASH_INIT(iun, int_unpack_t, char, 0, hash_func, hash_eq) +KHASH_INIT(ipk, int_packed_t, char, 0, hash_func, hash_eq) + +class KHashTest : public ::testing::Test { + protected: + KHashTest() { + } + + virtual ~KHashTest() { + // You can do clean-up work that doesn't throw exceptions here. + } + + // If the constructor and destructor are not enough for setting up + // and cleaning up each test, you can define the following methods: + + virtual void SetUp() { + + khash = kh_init(int); + } + + virtual void TearDown() { + + kh_destroy(int, khash); + + } + khash_t(int) *khash; +}; + + +TEST_F(KHashTest, KhashIntSize) +{ + int ret; + int k; + int size = kh_size(khash); + + EXPECT_EQ(size, 0); + k = kh_put(int, khash, 10, &ret); + if (ret == 1) { + kh_val(khash, k) = 10; + } + size = kh_size(khash); + EXPECT_EQ(size, 1); + +} + +TEST_F(KHashTest, KhashIntPut) +{ + int ret; + int k; + k = kh_put(int, khash, 10, &ret); + if (ret == 1) { + kh_val(khash, k) = 10; + } + int size = kh_size(khash); + EXPECT_EQ(size, 1); + k = kh_put(int, khash, 20, &ret); + if (ret == 1) { + kh_val(khash, k) = 20; + } + size = kh_size(khash); + EXPECT_EQ(size, 2); +} + +TEST_F(KHashTest, KhashCheckValue) +{ + int ret; + int k; + k = kh_put(int, khash, 10, &ret); + if (ret == 1) { + kh_val(khash, k) = 100; + } + k = kh_put(int, khash, 20, &ret); + if (ret == 1) { + kh_val(khash, k) = 200; + } + + k = kh_put(int, khash, 10, &ret); + int val = -1; + if (!ret) + val = kh_val(khash, k); + EXPECT_EQ(val, 100); + + k = kh_put(int, khash, 20, &ret); + val = -1; + if (!ret) + val = kh_val(khash, k); + EXPECT_EQ(val, 200); +} + +int main(int argc, char **argv) +{ + ::testing::InitGoogleTest(&argc, argv); + return RUN_ALL_TESTS(); +} diff --git a/hicn-light/src/hicn/base/test/test-loop.cc b/hicn-light/src/hicn/base/test/test-loop.cc new file mode 100644 index 000000000..d50b2472a --- /dev/null +++ b/hicn-light/src/hicn/base/test/test-loop.cc @@ -0,0 +1,286 @@ +/* + * Copyright (c) 2020 Cisco and/or its affiliates. + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at: + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include <gtest/gtest.h> + +#include <stdio.h> +#include <stdlib.h> +#include <string.h> +#include <sys/socket.h> +#include <sys/un.h> +#include <unistd.h> +#include <netinet/in.h> + +extern "C" { +#include <hicn/base/loop.h> +} + +class LoopTest : public ::testing::Test { + static constexpr uint16_t BUFFER_SIZE = 1024; + protected: + LoopTest() + : server_port_(9191), + loop_(nullptr), + timer_tick_(2000), + connection_socket_(-1), + event_(nullptr), + timer_(nullptr) { + } + + virtual ~LoopTest() { + // You can do clean-up work that doesn't throw exceptions here. + } + + // If the constructor and destructor are not enough for setting up + // and cleaning up each test, you can define the following methods: + + virtual void SetUp() { + // Code here will be called immediately after the constructor (right + // before each test). + } + + virtual void TearDown() { + // Code here will be called immediately after each test (right + // before the destructor). + } + + static int onFirstTimerExpiration(void *owner, int fd, void* arg) { + std::cout << "This function should never be called" << std::endl; + EXPECT_TRUE(false); + return -1; + } + + static int onSecondTimerExpiration(void *owner, int fd, void* arg) { + std::cout << "First timer expired. Cancel second timer." << std::endl; + LoopTest *test = (LoopTest *)(arg); + loop_event_unregister(test->timer_); + return 0; + } + + static int onTimerExpiration(void *owner, int fd, void* arg) { + // Create client socket + struct sockaddr_in addr; + int client_socket; + LoopTest *test = (LoopTest *)(arg); + + client_socket = socket(AF_INET, SOCK_STREAM, 0); + if (client_socket == -1) { + perror("socket"); + return -1; + } + + addr.sin_addr.s_addr = htonl(INADDR_LOOPBACK); + addr.sin_family = AF_INET; + addr.sin_port = htons(test->server_port_); + + if (connect(client_socket, (struct sockaddr *)&addr, sizeof(struct sockaddr)) == -1) { + perror("connect"); + return -1; + } + + if (send(client_socket, "Hello, world!\n", 14, 0) == -1){ + perror("send"); + return -1; + } + + close(client_socket); + loop_event_unregister(test->timer_); + + return 0; + } + + static int onNewConnection(void *owner, int fd, void* arg) { + LoopTest *test = (LoopTest *)arg; + struct sockaddr_in addr; + addr.sin_addr.s_addr = INADDR_ANY; + addr.sin_family = AF_INET; + + socklen_t addr_len = sizeof(struct sockaddr_in); + int ret; + + int client_fd = accept(test->connection_socket_, (struct sockaddr*)(&addr), &addr_len); + if (client_fd == -1) { + if (errno != EAGAIN && errno != EWOULDBLOCK) { + fprintf(stderr, "accept failed"); + } + + perror("accept"); + return -1; + } + + // Read whatever data available and close connection. + ret = read(client_fd, test->buffer, BUFFER_SIZE); + if (ret < 0) { + perror("read"); + return -1; + } + + test->buffer[ret] = '\0'; + std::cout << "Received: " << (char*)test->buffer << std::endl; + + close(client_fd); + loop_event_unregister(test->event_); + + return 0; + } + + void createTcpSocketServer() { + struct sockaddr_in addr; + int ret; + + /* Create local socket. */ + + connection_socket_ = socket(AF_INET, SOCK_STREAM, 0); + if (connection_socket_ == -1) { + perror("socket"); + return; + } + + addr.sin_family = AF_INET; + addr.sin_port = htons(server_port_); + addr.sin_addr.s_addr = htonl(INADDR_ANY); + + ret = bind(connection_socket_, (const struct sockaddr *) &addr, + sizeof(struct sockaddr_in)); + if (ret == -1) { + perror("bind"); + return; + } + + ret = listen(connection_socket_, 20); + if (ret == -1) { + perror("listen"); + return; + } +} + + uint16_t server_port_; + loop_t *loop_; + unsigned timer_tick_; + int connection_socket_; + event_t *event_; + event_t *timer_; + char buffer[BUFFER_SIZE]; +}; + +TEST_F(LoopTest, LoopCreateAndFree) +{ + loop_ = loop_create(); + EXPECT_TRUE(loop_ != NULL); + loop_free (loop_); + EXPECT_TRUE(loop_ != NULL); +} + +TEST_F(LoopTest, EventCreateAndFree) +{ + int ret; + + // Fake fd + int fd = 1; + loop_ = loop_create(); + + ret = loop_fd_event_create(&event_, loop_, fd, nullptr, &LoopTest::onNewConnection, this); + EXPECT_TRUE(ret >= 0); + EXPECT_TRUE(event_); + + // Register the event + ret = loop_fd_event_register(event_); + EXPECT_TRUE(ret >= 0); + + // Unregister the event + ret = loop_event_free(event_); + EXPECT_TRUE(ret >= 0); + + // Free event loop + loop_free (loop_); +} + +TEST_F(LoopTest, TimerCreateAndCancel) +{ + int ret; + event_t *timer2; + loop_ = loop_create(); + + ret = loop_timer_create(&timer_, loop_, nullptr, &LoopTest::onFirstTimerExpiration, this); + EXPECT_TRUE(ret >= 0); + EXPECT_TRUE(timer_); + + ret = loop_timer_create(&timer2, loop_, nullptr, &LoopTest::onSecondTimerExpiration, this); + EXPECT_TRUE(ret >= 0); + EXPECT_TRUE(timer2); + + // Register the 1st timer + ret = loop_timer_register(timer_, timer_tick_); + EXPECT_TRUE(ret >= 0); + + // Register the 2nd timer + ret = loop_timer_register(timer2, timer_tick_ / 2); + EXPECT_TRUE(ret >= 0); + + _loop_dispatch(loop_, 0); + + loop_undispatch(loop_); + + // Unregister the events + ret = loop_event_free(timer_); + ret += loop_event_free(timer2); + EXPECT_TRUE(ret >= 0); + + // Free event loop + loop_free (loop_); +} + +TEST_F(LoopTest, LoopDispatch) +{ + int ret; + + // Create new unix socket + createTcpSocketServer(); + loop_ = loop_create(); + + ret = loop_fd_event_create(&event_, loop_, connection_socket_, nullptr, &LoopTest::onNewConnection, this); + EXPECT_TRUE(ret >= 0); + EXPECT_TRUE(event_); + + ret = loop_fd_event_register(event_); + EXPECT_TRUE(ret >= 0); + + // Create timer. + ret = loop_timer_create(&timer_, loop_, nullptr, &LoopTest::onTimerExpiration, this); + EXPECT_TRUE(ret >= 0); + EXPECT_TRUE(timer_); + + ret = loop_timer_register(timer_, timer_tick_); + EXPECT_TRUE(ret >= 0); + + // Start event dispatching + _loop_dispatch(loop_, 0); + + // Stop dispatching + loop_undispatch(loop_); + + // Free events + loop_event_free(timer_); + loop_event_free(event_); + + // Free event loop + loop_free (loop_); +} + +int main(int argc, char **argv) +{ + ::testing::InitGoogleTest(&argc, argv); + return RUN_ALL_TESTS(); +} diff --git a/hicn-light/src/hicn/base/test/test-pool.cc b/hicn-light/src/hicn/base/test/test-pool.cc new file mode 100644 index 000000000..fd0d5988b --- /dev/null +++ b/hicn-light/src/hicn/base/test/test-pool.cc @@ -0,0 +1,210 @@ +/* + * Copyright (c) 2020 Cisco and/or its affiliates. + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at: + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include <gtest/gtest.h> + +#include <stdio.h> +#include <stdlib.h> +#include <string.h> +#include <sys/socket.h> +#include <sys/un.h> +#include <unistd.h> +#include <netinet/in.h> + +extern "C" { +#define WITH_TESTS +#include <hicn/base/pool.h> +} + +/* + * TODO + * - test max_size + */ + +#define DEFAULT_SIZE 10 + +class PoolTest : public ::testing::Test { +protected: + PoolTest() { } + virtual ~PoolTest() { } + + int *pool; +}; + +TEST_F(PoolTest, PoolAllocation) +{ + int rc; + + pool_init(pool, DEFAULT_SIZE, 0); + + size_t pool_size = next_pow2(DEFAULT_SIZE); + + EXPECT_EQ(pool_get_alloc_size(pool), pool_size); + + /* Check that free indices and bitmaps are correctly initialize */ + off_t * fi = pool_get_free_indices(pool); + EXPECT_EQ(vector_len(fi), pool_size); + EXPECT_EQ(fi[0], (long) (pool_size - 1)); + EXPECT_EQ(fi[pool_size - 1], 0); + + /* The allocated size of the underlying vector should be the next power of two */ + EXPECT_EQ(vector_get_alloc_size(fi), pool_size); + + bitmap_t * fb = pool_get_free_bitmap(pool); + EXPECT_TRUE(bitmap_is_set(fb, 0)); + EXPECT_TRUE(bitmap_is_set(fb, pool_size - 2)); + EXPECT_TRUE(bitmap_is_set(fb, pool_size - 1)); + EXPECT_TRUE(bitmap_is_unset(fb, pool_size)); + + /* Getting elements from the pool should correctly update the free indices + * and bitmap */ + int * elt; + + rc = pool_get(pool, elt); + EXPECT_GE(rc, 0); + EXPECT_EQ(vector_len(fi), pool_size - 1); + EXPECT_TRUE(bitmap_is_unset(fb, 0)); + + rc = pool_get(pool, elt); + EXPECT_GE(rc, 0); + EXPECT_EQ(vector_len(fi), pool_size - 2); + EXPECT_TRUE(bitmap_is_unset(fb, 1)); + + for (unsigned i = 0; i < pool_size - 4; i++) { + rc = pool_get(pool, elt); + EXPECT_GE(rc, 0); + } + + rc = pool_get(pool, elt); + EXPECT_GE(rc, 0); + EXPECT_EQ(vector_len(fi), 1UL); + EXPECT_TRUE(bitmap_is_unset(fb, pool_size - 2)); + + rc = pool_get(pool, elt); + EXPECT_GE(rc, 0); + EXPECT_EQ(vector_len(fi), 0UL); + EXPECT_TRUE(bitmap_is_unset(fb, pool_size - 1)); + + /* + * Getting elements within the allocated range should not have triggered a + * resize + */ + EXPECT_EQ(pool_len(pool), pool_size); + + /* + * Getting elements once the allocated range has been exceeded should + * trigger a resize + */ + rc = pool_get(pool, elt); + EXPECT_GE(rc, 0); + + EXPECT_EQ(pool_get_alloc_size(pool), pool_size * 2); + + EXPECT_EQ(pool_len(pool), pool_size + 1); + + /* + * Doubling the size, we should have again pool_size elements free, minus 1 + */ + EXPECT_EQ(pool_get_free_indices_size(pool), pool_size - 1); + + /* + * NOTE: this is wrong as there has been a realloc and the old fi + * pointer is now invalid + */ + //EXPECT_EQ(vector_len(fi), pool_size - 1); + + /* And the bitmap should also be correctly modified */ + fb = pool_get_free_bitmap(pool); + EXPECT_TRUE(bitmap_is_unset(fb, pool_size)); + + /* Check that surrounding values are also correct */ + EXPECT_TRUE(bitmap_is_unset(fb, pool_size - 1)); + EXPECT_TRUE(bitmap_is_set(fb, pool_size + 1)); + + /* Setting elements after should through */ + + /* Check that free indices and bitmaps are correctly updated */ + + pool_free(pool); +} + +TEST_F(PoolTest, PoolPut) +{ + pool_init(pool, DEFAULT_SIZE, 0); + + int* elt; + pool_get(pool, elt); + *elt = 10; + pool_put(pool, elt); + + pool_free(pool); +} + +TEST_F(PoolTest, PoolGetForceBitmapRealloc) +{ + const int N = 64; + int *elts[N]; + int *elt = NULL; + pool_init(pool, N, 0); + + for (int i = 0; i < N; i++) + pool_get(pool, elts[i]); + pool_get(pool, elt); + + pool_free(pool); +} + +TEST_F(PoolTest, PoolGetAfterReleasing) +{ + int *elt1 = NULL, *elt2 = NULL, *tmp = NULL; + pool_init(pool, DEFAULT_SIZE, 0); + + // If two elements are requested... + off_t id1 = pool_get(pool, elt1); + pool_get(pool, tmp); + + // ...and the first one is released... + pool_put(pool, elt1); + + // ...requesting a new one should return + // the first one (that was freed) + off_t id2 = pool_get(pool, elt2); + EXPECT_EQ(id1, id2); + EXPECT_EQ(elt1, elt2); + + pool_free(pool); +} + +TEST_F(PoolTest, PoolGetMultipleElementsAfterReleasing) +{ + const int N = 2; + int *elts[N]; + pool_init(pool, N, 0); + + for (int i = 0; i < N; i++) + pool_get(pool, elts[i]); + for (int i = 0; i < N; i++) + pool_put(pool, elts[i]); + for (int i = 0; i < N; i++) + pool_get(pool, elts[i]); + + pool_free(pool); +} + +int main(int argc, char **argv) +{ + ::testing::InitGoogleTest(&argc, argv); + return RUN_ALL_TESTS(); +} diff --git a/hicn-light/src/hicn/base/test/test-vector.cc b/hicn-light/src/hicn/base/test/test-vector.cc new file mode 100644 index 000000000..aaec7a92c --- /dev/null +++ b/hicn-light/src/hicn/base/test/test-vector.cc @@ -0,0 +1,117 @@ +/* + * Copyright (c) 2020 Cisco and/or its affiliates. + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at: + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include <gtest/gtest.h> + +#include <stdio.h> +#include <stdlib.h> +#include <string.h> +#include <sys/socket.h> +#include <sys/un.h> +#include <unistd.h> +#include <netinet/in.h> + +extern "C" { +#define WITH_TESTS +#include <hicn/base/vector.h> +} + +/* + * TODO + * - test max_size + */ + +#define DEFAULT_SIZE 10 + +class VectorTest : public ::testing::Test { +protected: + VectorTest() { } + virtual ~VectorTest() { } + + int *vector = NULL; +}; + +/* TEST: Vector allocation and initialization */ +TEST_F(VectorTest, VectorAllocate) +{ + vector_init(vector, DEFAULT_SIZE, 0); + + /* Allocated size should be the next power of two */ + EXPECT_EQ(vector_get_alloc_size(vector), 16UL); + + /* Setting elements within the allocated size should not trigger a resize */ + vector_ensure_pos(vector, 15); + EXPECT_EQ(vector_get_alloc_size(vector), 16UL); + + /* Setting elements after should through */ + vector_ensure_pos(vector, 16); + EXPECT_EQ(vector_get_alloc_size(vector), 32UL); + + /* Check that free indices and bitmaps are correctly updated */ + + vector_free(vector); +} + +TEST_F(VectorTest, VectorSize) +{ + vector_init(vector, DEFAULT_SIZE, 0); + + vector_push(vector, 109); + int size = vector_len(vector); + EXPECT_EQ(size, 1); + vector_push(vector, 109); + size = vector_len(vector); + EXPECT_EQ(size, 2); + vector_push(vector, 109); + size = vector_len(vector); + EXPECT_EQ(size, 3); + + vector_free(vector); +} + +TEST_F(VectorTest, VectorCheckValue) +{ + vector_init(vector, DEFAULT_SIZE, 0); + + vector_push(vector, 109); + vector_push(vector, 200); + EXPECT_EQ(vector[0], 109); + EXPECT_EQ(vector[1], 200); + + vector_free(vector); +} + +TEST_F(VectorTest, VectorEnsurePos) +{ + vector_init(vector, DEFAULT_SIZE, 0); + + printf (" %p\n", vector); + vector_ensure_pos(vector, 1025); + for (int i = 0; i <1025; i++) { + //printf("i %d\n", i); + //printf (" %p\n", vector); + vector_push(vector, i); + } + int size = vector_len(vector); + EXPECT_EQ(size, 1025); + + vector_free(vector); +} + +int main(int argc, char **argv) +{ + ::testing::InitGoogleTest(&argc, argv); + return RUN_ALL_TESTS(); +} diff --git a/hicn-light/src/hicn/base/vector.c b/hicn-light/src/hicn/base/vector.c index 00ed7c305..43110414a 100644 --- a/hicn-light/src/hicn/base/vector.c +++ b/hicn-light/src/hicn/base/vector.c @@ -18,16 +18,30 @@ * \brief Implementation of resizeable static array */ +#include <assert.h> #include <stddef.h> // size_t #include <stdlib.h> // calloc +#include <stdio.h> #include "vector.h" +#define DEFAULT_VECTOR_SIZE 64 + void -_vector_init(void ** vector_ptr, size_t elt_size, size_t max_elts) +_vector_init(void ** vector_ptr, size_t elt_size, size_t init_size, size_t max_size) { - vector_hdr_t * vh = calloc(VECTOR_HDRLEN + elt_size * max_elts, 1); - *vector_ptr = (uint8_t*)vh - VECTOR_HDRLEN; + assert(vector_ptr); + assert(max_size == 0 || init_size < max_size); + + if (init_size == 0) + init_size = DEFAULT_VECTOR_SIZE; + + *vector_ptr = NULL; + _vector_resize(vector_ptr, elt_size, init_size); + + vector_hdr_t * vh = vector_hdr(*vector_ptr); + vh->cur_size = 0; + vh->max_size = max_size; } void @@ -37,18 +51,42 @@ _vector_free(void ** vector_ptr) *vector_ptr = NULL; } -void +int _vector_resize(void ** vector_ptr, size_t elt_size, off_t pos) { - vector_hdr_t * vh = vector_hdr(*vector_ptr); - size_t new_elts = (pos > 0) ? next_pow2(pos) : vh->max_elts * 2; + vector_hdr_t * vh; - /* Double the allocated vector size */ - vh = realloc(vh, VECTOR_HDRLEN + new_elts * elt_size); + 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) - abort(); - vh->max_elts = new_elts; + 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*) + VECTOR_HDRLEN; + *vector_ptr = (uint8_t*)vh + VECTOR_HDRLEN; + + return 0; } diff --git a/hicn-light/src/hicn/base/vector.h b/hicn-light/src/hicn/base/vector.h index 9b99ba813..fd8401e6d 100644 --- a/hicn-light/src/hicn/base/vector.h +++ b/hicn-light/src/hicn/base/vector.h @@ -16,55 +16,244 @@ /** * \file vector.h * \brief Resizeable static array + * + * A vector is a resizeable area of contiguous memory that contains elements of + * fixed size. It is mostly useful to serve as the basis for more advanced data + * structures such as memory pools. + * + * The internal API manipulates a pointer to the vector so that it can be + * seamlessly resized, and a more convenient user interface is provided through + * macros. + * + * A vector starts at index 0, and is typed according to the elements it + * contains. For that matter, the data structure header precedes the returned + * pointer which corresponds to the storage area. + * + * A vector is by default used as a stack where an end marker is maintained and + * new elements are pushed right after this end marker (an indication of + * the size of the vector) after ensuring the vector is sufficiently large. + * + * A user should not store any pointer to vector elements as this might change + * during reallocations, but should use indices instead. + * + * NOTE: a maximum size is currently not implemented. + * + * It is freely inspired (and simplified) from the VPP infra infrastructure + * library. */ #ifndef UTIL_VECTOR_H #define UTIL_VECTOR_H +#include <stdint.h> #include <stddef.h> #include <stdint.h> +#include <string.h> #include <sys/types.h> #include "common.h" -/** Local variable naming macro. */ -#define _vector_var(v) _vector_##v +/******************************************************************************/ +/* Vector header */ typedef struct { - size_t num_elts; - size_t max_elts; + 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; -void _vector_init(void ** vector_ptr, size_t elt_size, size_t max_elts); -void _vector_free(void ** vector_ptr); -void _vector_resize(void ** vector_ptr, size_t elt_size, off_t pos); - /* Make sure elements following the header are aligned */ #define VECTOR_HDRLEN SIZEOF_ALIGNED(vector_hdr_t) /* This header actually prepends the actual content of the vector */ #define vector_hdr(vector) ((vector_hdr_t *)((uint8_t*)vector - VECTOR_HDRLEN)) -#define vector_init(vector, max_elts) \ - _vector_init((void**)&vector, sizeof(vector[0]), max_elts) +/******************************************************************************/ +/* Helpers */ -#define vector_free(vector) \ - _vector_free(&vector) +/** 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] max_size Maximum vector size (O = unlimited). + */ +void _vector_init(void ** vector_ptr, size_t elt_size, size_t init_size, size_t max_size); -#define vector_len(vector) (vector_hdr(vector)->num_elts) +/** + * @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 */ + memcpy((uint8_t*)*vector_ptr + vh->cur_size * elt_size, elt, elt_size); + vh = vector_hdr(*vector_ptr); + 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] 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) -#define vector_ensure_pos(vector, pos) \ -do { \ - if ((pos) >= vector_len(vector)) \ - _vector_resize((void**)&(vector), sizeof((vector)[0]), pos); \ -} while(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); -#define vector_push(vector, elt) \ -do { \ - vector_ensure_pos(vector_len(vector)); \ - vector[vector_len(vector)++] = elt; \ +/** + * @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) \ +do { \ + typeof(elt) x = elt; \ + _vector_push((void**)&(vector), sizeof((vector)[0]), (void*)(&x)); \ } while(0) +/** + * @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 + #endif /* UTIL_VECTOR_H */ |