lib: Add basic FRCT mechanisms

This adds the basic FRCT mechanisms to the library. Upon flow alloc or
accept an FRCT instance is now created and used when reading or
writing to the flow. The timerwheel has been refactored to allow
recharging timers and removing them and is now part of the
library. The first SDU sent over the connection has the DRF set and
this initializes the connection. Sender and receiver inactivity timers
are added.

5 files changed, 0 insertions, 547 deletions

diff --git a/src/ipcpd/CMakeLists.txt b/src/ipcpd/CMakeLists.txt
index 0ead1fed..b2f350dd 100644
--- a/src/ipcpd/CMakeLists.txt
+++ b/src/ipcpd/CMakeLists.txt
@@ -2,13 +2,9 @@ set(IPCP_SOURCES
   # Add source files here
   ${CMAKE_CURRENT_SOURCE_DIR}/ipcp.c
   ${CMAKE_CURRENT_SOURCE_DIR}/shim-data.c
-  ${CMAKE_CURRENT_SOURCE_DIR}/timerwheel.c
   )
 
 add_subdirectory(local)
 add_subdirectory(normal)
 add_subdirectory(shim-udp)
 add_subdirectory(shim-eth-llc)
-if (NOT APPLE)
-  add_subdirectory(tests)
-endif ()
diff --git a/src/ipcpd/tests/CMakeLists.txt b/src/ipcpd/tests/CMakeLists.txt
deleted file mode 100644
index 9b5eeaa1..00000000
--- a/src/ipcpd/tests/CMakeLists.txt
+++ /dev/null
@@ -1,34 +0,0 @@
-get_filename_component(CURRENT_SOURCE_PARENT_DIR
-  ${CMAKE_CURRENT_SOURCE_DIR} DIRECTORY)
-get_filename_component(CURRENT_BINARY_PARENT_DIR
-  ${CMAKE_CURRENT_BINARY_DIR} DIRECTORY)
-
-include_directories(${CMAKE_CURRENT_SOURCE_DIR})
-include_directories(${CMAKE_CURRENT_BINARY_DIR})
-
-include_directories(${CURRENT_SOURCE_PARENT_DIR})
-include_directories(${CURRENT_BINARY_PARENT_DIR})
-
-include_directories(${CMAKE_SOURCE_DIR}/include)
-include_directories(${CMAKE_BINARY_DIR}/include)
-
-get_filename_component(PARENT_PATH ${CMAKE_CURRENT_SOURCE_DIR} DIRECTORY)
-get_filename_component(PARENT_DIR ${PARENT_PATH} NAME)
-
-create_test_sourcelist(${PARENT_DIR}_tests test_suite.c
-  # Add new tests here
-  timerwheel_test.c
-  )
-
-add_executable(${PARENT_DIR}_test EXCLUDE_FROM_ALL ${${PARENT_DIR}_tests})
-target_link_libraries(${PARENT_DIR}_test ouroboros)
-
-add_dependencies(check ${PARENT_DIR}_test)
-
-set(tests_to_run ${${PARENT_DIR}_tests})
-remove(tests_to_run test_suite.c)
-
-foreach (test ${tests_to_run})
-  get_filename_component(test_name ${test} NAME_WE)
-  add_test(${test_name} ${C_TEST_PATH}/${PARENT_DIR}_test ${test_name})
-endforeach (test)
diff --git a/src/ipcpd/tests/timerwheel_test.c b/src/ipcpd/tests/timerwheel_test.c
deleted file mode 100644
index 6ba1b890..00000000
--- a/src/ipcpd/tests/timerwheel_test.c
+++ /dev/null
@@ -1,104 +0,0 @@
-/*
- * Ouroboros - Copyright (C) 2016 - 2017
- *
- * Test of the timer wheel
- *
- *    Dimitri Staessens <dimitri.staessens@ugent.be>
- *    Sander Vrijders   <sander.vrijders@ugent.be>
- *
- * This program is free software; you can redistribute it and/or modify
- * it under the terms of the GNU General Public License version 2 as
- * published by the Free Software Foundation.
- *
- * This program is distributed in the hope that it will be useful,
- * but WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
- * GNU General Public License for more details.
- *
- * You should have received a copy of the GNU General Public License
- * along with this program; if not, write to the Free Software
- * Foundation, Inc., http://www.fsf.org/about/contact/.
- */
-
-#include "timerwheel.c"
-
-#include <pthread.h>
-#include <time.h>
-#include <stdlib.h>
-#include <stdio.h>
-
-#define MAX_ELEMENTS   100
-#define MAX_RESOLUTION 10  /* ms */
-#define MAX_ADDITIONS  1000
-
-int total;
-
-int add(void * o)
-{
-        total += *((int *) o);
-        return 0;
-}
-
-int timerwheel_test(int argc, char ** argv)
-{
-        struct timerwheel * tw;
-        long resolution;
-        long elements;
-        struct timespec wait;
-
-        int additions;
-
-        int check_total = 0;
-
-        int i;
-
-        (void) argc;
-        (void) argv;
-
-        total = 0;
-
-        srand(time(NULL));
-
-        resolution = rand() % (MAX_RESOLUTION - 1) + 1;
-        elements = rand() % (MAX_ELEMENTS - 10) + 10;
-
-        tw = timerwheel_create(resolution, resolution * elements);
-        if (tw == NULL) {
-                printf("Failed to create timerwheel.\n");
-                return -1;
-        }
-
-        wait.tv_sec = (resolution * elements) / 1000;
-        wait.tv_nsec = ((resolution * elements) % 1000) * MILLION;
-
-        additions = rand() % MAX_ADDITIONS + 1000;
-
-        for (i = 0; i < additions; ++i) {
-                int delay = rand() % (resolution * elements);
-                int var = rand() % 5;
-                check_total += var;
-                if (timerwheel_add(tw,
-                                   (void (*)(void *)) add,
-                                   (void *) &var,
-                                   sizeof(var),
-                                   delay)) {
-                        printf("Failed to add function.");
-                        return -1;
-                }
-        }
-
-        nanosleep(&wait, NULL);
-
-        /* On some systems and VMs, the scheduler may be too slow. */
-        if (total != check_total)
-                nanosleep(&wait, NULL);
-
-        timerwheel_destroy(tw);
-
-        if (total != check_total) {
-                printf("Totals do not match.\n");
-                return -1;
-        }
-
-        return 0;
-}
diff --git a/src/ipcpd/timerwheel.c b/src/ipcpd/timerwheel.c
deleted file mode 100644
index 6086181a..00000000
--- a/src/ipcpd/timerwheel.c
+++ /dev/null
@@ -1,366 +0,0 @@
-/*
- * Ouroboros - Copyright (C) 2016 - 2017
- *
- * Timerwheel
- *
- *    Dimitri Staessens <dimitri.staessens@ugent.be>
- *    Sander Vrijders   <sander.vrijders@ugent.be>
- *
- * This program is free software; you can redistribute it and/or modify
- * it under the terms of the GNU General Public License version 2 as
- * published by the Free Software Foundation.
- *
- * This program is distributed in the hope that it will be useful,
- * but WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
- * GNU General Public License for more details.
- *
- * You should have received a copy of the GNU General Public License
- * along with this program; if not, write to the Free Software
- * Foundation, Inc., http://www.fsf.org/about/contact/.
- */
-
-#include <ouroboros/config.h>
-#include <ouroboros/time_utils.h>
-#include <ouroboros/errno.h>
-#include <ouroboros/list.h>
-
-#include <pthread.h>
-#include <stdlib.h>
-#include <assert.h>
-#include <string.h>
-
-#define FRAC 10 /* accuracy of the timer */
-
-#define tw_used(tw) ((tw->head + tw->elements - tw->tail) & (tw->elements - 1));
-#define tw_free(tw) (tw_used(tw) + 1 < tw->elements)
-#define tw_empty(tw) (tw->head == tw->tail)
-
-enum tw_state {
-        TW_NULL = 0,
-        TW_RUNNING,
-        TW_DESTROY
-};
-
-struct tw_f {
-        struct list_head next;
-        void (* func)(void *);
-        void * arg;
-};
-
-struct tw_el {
-        struct list_head funcs;
-        struct timespec  expiry;
-};
-
-struct timerwheel {
-        struct tw_el *   wheel;
-
-        struct timespec  intv;
-
-        size_t           pos;
-
-        struct list_head wq;
-
-        pthread_cond_t   work;
-        pthread_mutex_t  lock;
-
-        int              resolution;
-        unsigned int     elements;
-
-        enum tw_state    state;
-        pthread_mutex_t  s_lock;
-
-        pthread_t        ticker;
-        pthread_t        worker;
-};
-
-static void tw_el_fini(struct tw_el * e)
-{
-        struct list_head * p;
-        struct list_head * h;
-
-        list_for_each_safe(p, h, &e->funcs) {
-                struct tw_f * f = list_entry(p, struct tw_f, next);
-                list_del(&f->next);
-                if (f->arg != NULL)
-                        free(f->arg);
-        }
-}
-
-static enum tw_state tw_get_state(struct timerwheel * tw)
-{
-        enum tw_state state;
-
-        assert(tw);
-
-        pthread_mutex_lock(&tw->s_lock);
-
-        state = tw->state;
-
-        pthread_mutex_unlock(&tw->s_lock);
-
-        return state;
-}
-
-static void tw_set_state(struct timerwheel * tw, enum tw_state state)
-{
-        assert(tw);
-        assert(state != TW_NULL);
-
-        pthread_mutex_lock(&tw->s_lock);
-
-        tw->state = state;
-
-        pthread_mutex_unlock(&tw->s_lock);
-}
-
-static void * worker(void * o)
-{
-        struct list_head * p;
-        struct list_head * h;
-
-        struct timerwheel * tw = (struct timerwheel *) o;
-        struct timespec dl;
-        struct timespec now;
-
-        clock_gettime(PTHREAD_COND_CLOCK, &now);
-
-        ts_add(&now, &tw->intv, &dl);
-
-        pthread_mutex_lock(&tw->lock);
-
-        while (tw_get_state(tw) == TW_RUNNING) {
-                if (pthread_cond_timedwait(&tw->work, &tw->lock, &dl)
-                    == ETIMEDOUT)
-                        ts_add(&dl, &tw->intv, &dl);
-
-                list_for_each_safe(p, h, &tw->wq) {
-                        struct tw_f * f = list_entry(p, struct tw_f, next);
-                        list_del(&f->next);
-                        pthread_mutex_unlock(&tw->lock);
-                        f->func(f->arg);
-                        if (f->arg != NULL)
-                                free(f->arg);
-                        free(f);
-
-                        pthread_mutex_lock(&tw->lock);
-                }
-        }
-
-        pthread_mutex_unlock(&tw->lock);
-
-        return (void *) o;
-}
-
-static void * movement(void * o)
-{
-        struct timerwheel * tw = (struct timerwheel *) o;
-        struct timespec now = {0, 0};
-        long ms = tw->resolution * tw->elements;
-        struct timespec total = {ms / 1000,
-                                 (ms % 1000) * MILLION};
-        struct list_head * p;
-        struct list_head * h;
-
-        while (tw_get_state(tw) == TW_RUNNING) {
-                clock_gettime(CLOCK_MONOTONIC, &now);
-
-                pthread_mutex_lock(&tw->lock);
-
-                if (ts_diff_us(&tw->wheel[tw->pos].expiry, &now) < 0) {
-                        pthread_mutex_unlock(&tw->lock);
-                        nanosleep(&tw->intv, NULL);
-                        continue;
-                }
-
-                list_for_each_safe(p, h, &tw->wheel[tw->pos].funcs) {
-                        struct tw_f * f = list_entry(p, struct tw_f, next);
-                        list_del(&f->next);
-                        list_add(&f->next, &tw->wq);
-                }
-
-                ts_add(&tw->wheel[tw->pos].expiry,
-                       &total,
-                       &tw->wheel[tw->pos].expiry);
-
-                tw->pos = (tw->pos + 1) & (tw->elements - 1);
-
-                pthread_cond_signal(&tw->work);
-
-                pthread_mutex_unlock(&tw->lock);
-        }
-
-        return (void *) 0;
-}
-
-struct timerwheel * timerwheel_create(unsigned int resolution,
-                                      unsigned int max_delay)
-{
-        struct timespec now = {0, 0};
-        struct timespec res_ts = {resolution / 1000,
-                                  (resolution % 1000) * MILLION};
-        unsigned long i;
-
-        struct timerwheel * tw;
-
-        pthread_condattr_t cattr;
-
-        assert(resolution != 0);
-
-        tw = malloc(sizeof(*tw));
-        if (tw == NULL)
-                return NULL;
-
-        if (pthread_mutex_init(&tw->lock, NULL))
-                return NULL;
-
-        tw->elements = 1;
-
-        while (tw->elements < max_delay / resolution)
-                tw->elements <<= 1;
-
-        tw->wheel = malloc(sizeof(*tw->wheel) * tw->elements);
-        if (tw->wheel == NULL) {
-                free(tw);
-                return NULL;
-        }
-
-        tw->resolution = resolution;
-
-        tw->intv.tv_sec = (tw->resolution / FRAC) / 1000;
-        tw->intv.tv_nsec = ((tw->resolution / FRAC) % 1000) * MILLION;
-
-        list_head_init(&tw->wq);
-
-        if (pthread_mutex_init(&tw->lock, NULL)) {
-                free(tw->wheel);
-                free(tw);
-                return NULL;
-        }
-
-        if (pthread_mutex_init(&tw->s_lock, NULL)) {
-                pthread_mutex_destroy(&tw->lock);
-                free(tw->wheel);
-                free(tw);
-                return NULL;
-        }
-
-        if (pthread_condattr_init(&cattr)) {
-                pthread_mutex_destroy(&tw->lock);
-                free(tw->wheel);
-                free(tw);
-                return NULL;
-        }
-#ifndef __APPLE__
-        pthread_condattr_setclock(&cattr, PTHREAD_COND_CLOCK);
-#endif
-        if (pthread_cond_init(&tw->work, &cattr)) {
-                pthread_mutex_destroy(&tw->s_lock);
-                pthread_mutex_destroy(&tw->lock);
-                free(tw->wheel);
-                free(tw);
-                return NULL;
-        }
-
-        tw->pos = 0;
-        tw->state = TW_RUNNING;
-
-        clock_gettime(CLOCK_MONOTONIC, &now);
-        now.tv_nsec -= (now.tv_nsec % MILLION);
-
-        for (i = 0; i < tw->elements; ++i) {
-                list_head_init(&tw->wheel[i].funcs);
-                tw->wheel[i].expiry = now;
-                ts_add(&now, &res_ts, &now);
-        }
-
-        if (pthread_create(&tw->worker, NULL, worker, (void *) tw)) {
-                pthread_cond_destroy(&tw->work);
-                pthread_mutex_destroy(&tw->s_lock);
-                pthread_mutex_destroy(&tw->lock);
-                free(tw->wheel);
-                free(tw);
-                return NULL;
-        }
-
-        if (pthread_create(&tw->ticker, NULL, movement, (void *) tw)) {
-                tw_set_state(tw, TW_DESTROY);
-                pthread_join(tw->worker, NULL);
-                pthread_cond_destroy(&tw->work);
-                pthread_mutex_destroy(&tw->s_lock);
-                pthread_mutex_destroy(&tw->lock);
-                free(tw->wheel);
-                free(tw);
-                return NULL;
-        }
-
-        return tw;
-}
-
-void timerwheel_destroy(struct timerwheel * tw)
-{
-        unsigned long i;
-
-        struct list_head * p;
-        struct list_head * h;
-
-        tw_set_state(tw, TW_DESTROY);
-
-        pthread_join(tw->ticker, NULL);
-        pthread_join(tw->worker, NULL);
-
-        for (i = 0; i < tw->elements; ++i)
-                tw_el_fini(&tw->wheel[i]);
-
-        pthread_mutex_lock(&tw->lock);
-
-        list_for_each_safe(p, h, &tw->wq) {
-                struct tw_f * f = list_entry(p, struct tw_f, next);
-                list_del(&f->next);
-                if (f->arg != NULL)
-                        free(f->arg);
-                free(f);
-        }
-
-        pthread_mutex_unlock(&tw->lock);
-
-        pthread_cond_destroy(&tw->work);
-        pthread_mutex_destroy(&tw->lock);
-        pthread_mutex_destroy(&tw->s_lock);
-
-        free(tw->wheel);
-        free(tw);
-}
-
-int timerwheel_add(struct timerwheel * tw,
-                   void (* func)(void *),
-                   void * arg,
-                   size_t arg_len,
-                   unsigned int delay)
-{
-        int pos;
-        struct tw_f * f = malloc(sizeof(*f));
-        if (f == NULL)
-                return -ENOMEM;
-
-        f->func = func;
-        f->arg = malloc(arg_len);
-        if (f->arg == NULL) {
-                free(f);
-                return -ENOMEM;
-        }
-
-        memcpy(f->arg, arg, arg_len);
-
-        assert(delay < tw->elements * tw->resolution);
-
-        pthread_mutex_lock(&tw->lock);
-
-        pos = (tw->pos + delay / tw->resolution) & (tw->elements - 1);
-        list_add(&f->next, &tw->wheel[pos].funcs);
-
-        pthread_mutex_unlock(&tw->lock);
-
-        return 0;
-}
diff --git a/src/ipcpd/timerwheel.h b/src/ipcpd/timerwheel.h
deleted file mode 100644
index 37a6d06a..00000000
--- a/src/ipcpd/timerwheel.h
+++ /dev/null
@@ -1,39 +0,0 @@
-/*
- * Ouroboros - Copyright (C) 2016 - 2017
- *
- * Ring buffer for incoming SDUs
- *
- *    Dimitri Staessens <dimitri.staessens@ugent.be>
- *    Sander Vrijders   <sander.vrijders@ugent.be>
- *
- * This program is free software; you can redistribute it and/or modify
- * it under the terms of the GNU General Public License version 2 as
- * published by the Free Software Foundation.
- *
- * This program is distributed in the hope that it will be useful,
- * but WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
- * GNU General Public License for more details.
- *
- * You should have received a copy of the GNU General Public License
- * along with this program; if not, write to the Free Software
- * Foundation, Inc., http://www.fsf.org/about/contact/.
- */
-
-#ifndef OUROBOROS_IPCPD_TIMERWHEEL_H
-#define OUROBOROS_IPCPD_TIMERWHEEL_H
-
-struct timerwheel;
-
-struct timerwheel * timerwheel_create(unsigned int resolution,
-                                      unsigned int max_delay);
-
-void                timerwheel_destroy(struct timerwheel * tw);
-
-int                 timerwheel_add(struct timerwheel * tw,
-                                   void (* func)(void *),
-                                   void *              arg,
-                                   size_t              arg_len,
-                                   unsigned int        delay); /* ms */
-
-#endif /* OUROBOROS_IPCPD_TIMERWHEEL_H */