ipcpd: Restructure policy code

The policies were all in a single folder pol/, and have been moved to
a folder per component/mechanism to keep things a bit more orderly.

Signed-off-by: Dimitri Staessens <dimitri@ouroboros.rocks>
Signed-off-by: Sander Vrijders <sander@ouroboros.rocks>

1 files changed, 296 insertions, 0 deletions

diff --git a/src/ipcpd/unicast/ca/mb-ecn.c b/src/ipcpd/unicast/ca/mb-ecn.c
new file mode 100644
index 00000000..38305a39
--- /dev/null
+++ b/src/ipcpd/unicast/ca/mb-ecn.c
@@ -0,0 +1,296 @@
+/*
+ * Ouroboros - Copyright (C) 2016 - 2021
+ *
+ * Multi-bit ECN Congestion Avoidance
+ *
+ *    Dimitri Staessens <dimitri@ouroboros.rocks>
+ *    Sander Vrijders   <sander@ouroboros.rocks>
+ *
+ * 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/.
+ */
+
+#if defined(__linux__) || defined(__CYGWIN__)
+#define _DEFAULT_SOURCE
+#else
+#define _POSIX_C_SOURCE 200809L
+#endif
+
+#include "config.h"
+
+#include <ouroboros/ipcp-dev.h>
+#include <ouroboros/time_utils.h>
+
+#include "mb-ecn.h"
+
+#include <inttypes.h>
+#include <stdlib.h>
+#include <string.h>
+#include <stdio.h>
+
+/* congestion avoidance constants */
+#define CA_SHFT      5                    /* Average over 32 pkts   */
+#define CA_WND       (1 << CA_SHFT)       /* 32 pkts receiver wnd   */
+#define CA_UPD       (1 << (CA_SHFT - 2)) /* Update snd every 8 pkt */
+#define CA_SLOT      24                   /* Initial slot = 16 ms   */
+#define CA_INC       1UL << 16            /* ~4MiB/s^2 additive inc */
+#define CA_IWL       1UL << 16            /* Initial limit ~4MiB/s  */
+#define CA_MINPS     8                    /* Mimimum pkts / slot    */
+#define CA_MAXPS     64                   /* Maximum pkts / slot    */
+#define ECN_Q_SHFT   4
+#define ts_to_ns(ts) ((size_t) ts.tv_sec * BILLION + ts.tv_nsec)
+
+struct mb_ecn_ctx {
+        uint16_t        rx_ece; /* Level of congestion (upstream)   */
+        size_t          rx_ctr; /* Receiver side packet counter     */
+
+        uint16_t        tx_ece; /* Level of congestion (downstream) */
+        size_t          tx_ctr; /* Sender side packet counter       */
+        size_t          tx_wbc; /* Window byte count                */
+        size_t          tx_wpc; /* Window packet count              */
+        size_t          tx_wbl; /* Window byte limit                */
+        bool            tx_cav; /* Congestion avoidance             */
+        size_t          tx_mul; /* Slot size multiplier             */
+        size_t          tx_inc; /* Additive increase                */
+        size_t          tx_slot;
+};
+
+struct ca_ops mb_ecn_ca_ops = {
+        .ctx_create     = mb_ecn_ctx_create,
+        .ctx_destroy    = mb_ecn_ctx_destroy,
+        .ctx_update_snd = mb_ecn_ctx_update_snd,
+        .ctx_update_rcv = mb_ecn_ctx_update_rcv,
+        .ctx_update_ece = mb_ecn_ctx_update_ece,
+        .wnd_wait       = mb_ecn_wnd_wait,
+        .calc_ecn       = mb_ecn_calc_ecn,
+        .print_stats    = mb_ecn_print_stats
+};
+
+void * mb_ecn_ctx_create(void)
+{
+        struct timespec     now;
+        struct mb_ecn_ctx * ctx;
+
+        ctx = malloc(sizeof(*ctx));
+        if (ctx == NULL)
+                return NULL;
+
+        clock_gettime(PTHREAD_COND_CLOCK, &now);
+
+        memset(ctx, 0, sizeof(*ctx));
+
+        ctx->tx_mul  = CA_SLOT;
+        ctx->tx_wbl  = CA_IWL;
+        ctx->tx_inc  = CA_INC;
+        ctx->tx_slot = ts_to_ns(now) >> ctx->tx_mul;
+
+        return (void *) ctx;
+}
+
+void mb_ecn_ctx_destroy(void * ctx)
+{
+        free(ctx);
+}
+
+#define _slot_after(new, old) ((int64_t) (old - new) < 0)
+
+ca_wnd_t mb_ecn_ctx_update_snd(void * _ctx,
+                               size_t len)
+{
+        struct timespec     now;
+        size_t              slot;
+        ca_wnd_t            wnd;
+        struct mb_ecn_ctx * ctx = _ctx;
+
+        clock_gettime(PTHREAD_COND_CLOCK, &now);
+
+        slot = ts_to_ns(now) >> ctx->tx_mul;
+
+        ctx->tx_ctr++;
+        ctx->tx_wpc++;
+        ctx->tx_wbc += len;
+
+        if (ctx->tx_ctr > CA_WND)
+                ctx->tx_ece = 0;
+
+        if (_slot_after(slot, ctx->tx_slot)) {
+                bool carry = false; /* may carry over if window increases */
+
+                ctx->tx_slot = slot;
+
+                if (!ctx->tx_cav) { /* Slow start */
+                        if (ctx->tx_wbc > ctx->tx_wbl)
+                                ctx->tx_wbl <<= 1;
+                } else {
+                        if (ctx->tx_ece) /* Mult. Decrease */
+                                ctx->tx_wbl -= (ctx->tx_wbl * ctx->tx_ece)
+                                        >> (CA_SHFT + 8);
+                        else /* Add. Increase */
+                                ctx->tx_wbl = ctx->tx_wbc + ctx->tx_inc;
+                }
+
+                /* Window scaling */
+                if (ctx->tx_wpc < CA_MINPS) {
+                        size_t fact = 0; /* factor to scale the window up */
+                        size_t pkts = ctx->tx_wpc;
+                        while (pkts < CA_MINPS) {
+                                pkts <<= 1;
+                                fact++;
+                        }
+                        ctx->tx_mul += fact;
+                        ctx->tx_slot >>= fact;
+                        if ((ctx->tx_slot & ((1 << fact)  - 1)) == 0) {
+                                carry = true;
+                                ctx->tx_slot += 1;
+                        }
+                        ctx->tx_wbl <<= fact;
+                        ctx->tx_inc <<= fact;
+                } else if (ctx->tx_wpc > CA_MAXPS) {
+                        size_t fact = 0; /* factor to scale the window down */
+                        size_t pkts = ctx->tx_wpc;
+                        while (pkts > CA_MAXPS) {
+                                pkts >>= 1;
+                                fact++;
+                        }
+                        ctx->tx_mul -= fact;
+                        ctx->tx_slot <<= fact;
+                        ctx->tx_wbl >>= fact;
+                        ctx->tx_inc >>= fact;
+                } else {
+                        ctx->tx_slot = slot;
+                }
+
+                if (!carry) {
+                        ctx->tx_wbc = 0;
+                        ctx->tx_wpc = 0;
+                }
+        }
+
+        if (ctx->tx_wbc > ctx->tx_wbl)
+                wnd.wait = ((ctx->tx_slot + 1) << ctx->tx_mul) - ts_to_ns(now);
+        else
+                wnd.wait = 0;
+
+        return wnd;
+}
+
+void mb_ecn_wnd_wait(ca_wnd_t wnd)
+{
+        if (wnd.wait > 0) {
+                struct timespec s = {0, 0};
+                if (wnd.wait > BILLION) /* Don't care throttling < 1s */
+                        s.tv_sec = 1;
+                else
+                        s.tv_nsec = wnd.wait;
+
+                nanosleep(&s, NULL);
+        }
+}
+
+bool mb_ecn_ctx_update_rcv(void *     _ctx,
+                           size_t     len,
+                           uint8_t    ecn,
+                           uint16_t * ece)
+{
+        struct mb_ecn_ctx* ctx = _ctx;
+        bool               update;
+
+        (void) len;
+
+        if ((ctx->rx_ece | ecn) == 0)
+                return false;
+
+        if (ecn == 0) { /* End of congestion */
+                ctx->rx_ece >>= 2;
+                update = ctx->rx_ece == 0;
+        } else {
+                if (ctx->rx_ece == 0) { /* Start of congestion */
+                        ctx->rx_ece = ecn;
+                        ctx->rx_ctr = 0;
+                        update = true;
+                } else { /* Congestion update */
+                        ctx->rx_ece -= ctx->rx_ece >> CA_SHFT;
+                        ctx->rx_ece += ecn;
+                        update = (ctx->rx_ctr++ & (CA_UPD - 1)) == true;
+                }
+        }
+
+        *ece = ctx->rx_ece;
+
+        return update;
+}
+
+
+void mb_ecn_ctx_update_ece(void *   _ctx,
+                           uint16_t ece)
+{
+        struct mb_ecn_ctx* ctx = _ctx;
+
+        ctx->tx_ece = ece;
+        ctx->tx_ctr = 0;
+        ctx->tx_cav = true;
+}
+
+int  mb_ecn_calc_ecn(int       fd,
+                     uint8_t * ecn,
+                     qoscube_t qc,
+                     size_t    len)
+{
+        size_t q;
+
+        (void) len;
+        (void) qc;
+
+        q = ipcp_flow_queued(fd);
+
+        *ecn |= (uint8_t) (q >> ECN_Q_SHFT);
+
+        return 0;
+}
+
+ssize_t  mb_ecn_print_stats(void * _ctx,
+                            char * buf,
+                            size_t len)
+{
+        struct mb_ecn_ctx* ctx = _ctx;
+        char *             regime;
+
+        if (len < 1024)
+                return 0;
+
+        if (!ctx->tx_cav)
+                regime = "Slow start";
+        else if (ctx->tx_ece)
+                regime = "Multiplicative dec";
+        else
+                regime = "Additive inc";
+
+        sprintf(buf,
+                "Congestion avoidance algorithm:  %20s\n"
+                "Upstream congestion level:       %20u\n"
+                "Upstream packet counter:         %20zu\n"
+                "Downstream congestion level:     %20u\n"
+                "Downstream packet counter:       %20zu\n"
+                "Congestion window size (ns):     %20" PRIu64 "\n"
+                "Packets in this window:          %20zu\n"
+                "Bytes in this window:            %20zu\n"
+                "Max bytes in this window:        %20zu\n"
+                "Current congestion regime:       %20s\n",
+                "Multi-bit ECN",
+                ctx->tx_ece, ctx->tx_ctr,
+                ctx->rx_ece, ctx->rx_ctr, (uint64_t) (1ULL << ctx->tx_mul),
+                ctx->tx_wpc, ctx->tx_wbc, ctx->tx_wbl,
+                regime);
+
+        return strlen(buf);
+}