aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
-rw-r--r--.gitignore1
-rw-r--r--src/Makefile.am6
-rw-r--r--src/gprs_codel.c179
-rw-r--r--src/gprs_codel.h108
-rw-r--r--tests/Makefile.am11
-rw-r--r--tests/codel/codel_test.c147
-rw-r--r--tests/codel/codel_test.ok29
-rw-r--r--tests/testsuite.at6
8 files changed, 483 insertions, 4 deletions
diff --git a/.gitignore b/.gitignore
index b093692..6cc9aa5 100644
--- a/.gitignore
+++ b/.gitignore
@@ -38,6 +38,7 @@ tests/tbf/TbfTest
tests/types/TypesTest
tests/ms/MsTest
tests/llist/LListTest
+tests/codel/codel_test
tests/emu/pcu_emu
tests/testsuite
tests/testsuite.log
diff --git a/src/Makefile.am b/src/Makefile.am
index a63281f..3587416 100644
--- a/src/Makefile.am
+++ b/src/Makefile.am
@@ -54,7 +54,8 @@ libgprs_la_SOURCES = \
sba.cpp \
decoding.cpp \
llc.cpp \
- rlc.cpp
+ rlc.cpp \
+ gprs_codel.c
if ENABLE_SYSMOBTS
libgprs_la_SOURCES += \
@@ -99,7 +100,8 @@ noinst_HEADERS = \
decoding.h \
llc.h \
pcu_utils.h \
- cxx_linuxlist.h
+ cxx_linuxlist.h \
+ gprs_codel.h
osmo_pcu_SOURCES = pcu_main.cpp
diff --git a/src/gprs_codel.c b/src/gprs_codel.c
new file mode 100644
index 0000000..02440b4
--- /dev/null
+++ b/src/gprs_codel.c
@@ -0,0 +1,179 @@
+/* gprs_codel.cpp
+ *
+ * Copyright (C) 2015 by Sysmocom s.f.m.c. GmbH
+ * Author: Jacob Erlbeck <jerlbeck@sysmocom.de>
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * 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., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
+ */
+
+#include "gprs_codel.h"
+#include "gprs_debug.h"
+
+#include <osmocom/core/utils.h>
+
+#include <stdint.h>
+#include <stdlib.h>
+#include <math.h>
+
+static void control_law(struct gprs_codel *state, struct timeval *delta)
+{
+ /* 256 / sqrt(x), limited to 255 */
+ static uint8_t inv_sqrt_tab[] = {255,
+ 255, 181, 147, 128, 114, 104, 96, 90, 85, 80, 77, 73, 71, 68,
+ 66, 64, 62, 60, 58, 57, 55, 54, 53, 52, 51, 50, 49, 48, 47, 46,
+ 45, 45, 44, 43, 43, 42, 42, 41, 40, 40, 39, 39, 39, 38, 38, 37,
+ 37, 36, 36, 36, 35, 35, 35, 34, 34, 34, 33, 33, 33, 33, 32, 32,
+ 32, 32, 31, 31, 31, 31, 30, 30, 30, 30, 29, 29, 29, 29, 29, 28,
+ 28, 28, 28, 28, 28, 27, 27, 27, 27, 27, 27, 26, 26, 26, 26, 26,
+ 26, 26, 25, 25, 25, 25, 25, 25, 25, 25, 24, 24, 24, 24, 24, 24,
+ 24, 24, 24, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 22, 22, 22,
+ 22, 22, 22, 22, 22, 22, 22, 22, 22, 21, 21, 21, 21, 21, 21, 21,
+ 21, 21, 21, 21, 21, 21, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20,
+ 20, 20, 20, 20, 20, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19,
+ 19, 19, 19, 19, 19, 19, 19, 18, 18, 18, 18, 18, 18, 18, 18, 18,
+ 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 17, 17, 17, 17,
+ 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17,
+ 17, 17, 17, 17
+ };
+ uint_fast32_t delta_usecs;
+ uint_fast32_t inv_sqrt;
+ div_t q;
+
+ if (state->count >= ARRAY_SIZE(inv_sqrt_tab))
+ inv_sqrt = 16;
+ else
+ inv_sqrt = inv_sqrt_tab[state->count];
+
+ /* delta = state->interval / sqrt(count) */
+ delta_usecs = state->interval.tv_sec * 1000000 + state->interval.tv_usec;
+ delta_usecs = delta_usecs * inv_sqrt / 256;
+
+ q = div(delta_usecs, 1000000);
+ delta->tv_sec = q.quot;
+ delta->tv_usec = q.rem;
+}
+
+void gprs_codel_init(struct gprs_codel *state)
+{
+ static const struct gprs_codel init_state = {0};
+
+ *state = init_state;
+ gprs_codel_set_interval(state, -1);
+ gprs_codel_set_maxpacket(state, -1);
+}
+
+void gprs_codel_set_interval(struct gprs_codel *state, int interval_ms)
+{
+ div_t q;
+
+ if (interval_ms <= 0)
+ interval_ms = GPRS_CODEL_DEFAULT_INTERVAL_MS;
+
+ q = div(interval_ms, 1000);
+ state->interval.tv_sec = q.quot;
+ state->interval.tv_usec = q.rem * 1000;
+
+ /* target ~ 5% of interval */
+ q = div(interval_ms * 13 / 256, 1000);
+ state->target.tv_sec = q.quot;
+ state->target.tv_usec = q.rem * 1000;
+}
+
+void gprs_codel_set_maxpacket(struct gprs_codel *state, int maxpacket)
+{
+
+ if (maxpacket < 0)
+ maxpacket = GPRS_CODEL_DEFAULT_MAXPACKET;
+
+ state->maxpacket = maxpacket;
+}
+
+/*
+ * This is an broken up variant of the algorithm being described in
+ * http://queue.acm.org/appendices/codel.html
+ */
+int gprs_codel_control(struct gprs_codel *state, const struct timeval *recv,
+ const struct timeval *now, int bytes)
+{
+ struct timeval sojourn_time;
+ struct timeval delta;
+
+ if (recv == NULL)
+ goto stop_dropping;
+
+ timersub(now, recv, &sojourn_time);
+
+ if (timercmp(&sojourn_time, &state->target, <))
+ goto stop_dropping;
+
+ if (bytes >= 0 && (unsigned)bytes <= state->maxpacket)
+ goto stop_dropping;
+
+ if (!timerisset(&state->first_above_time)) {
+ timeradd(now, &state->interval, &state->first_above_time);
+ goto not_ok_to_drop;
+ }
+
+ if (timercmp(now, &state->first_above_time, <))
+ goto not_ok_to_drop;
+
+ /* Ok to drop */
+
+ if (!state->dropping) {
+ int recently = 0;
+ int in_drop_cycle = 0;
+ if (timerisset(&state->drop_next)) {
+ timersub(now, &state->drop_next, &delta);
+ in_drop_cycle = timercmp(&delta, &state->interval, <);
+ recently = in_drop_cycle;
+ }
+ if (!recently) {
+ timersub(now, &state->first_above_time, &delta);
+ recently = !timercmp(&delta, &state->interval, <);
+ };
+ if (!recently)
+ return 0;
+
+ state->dropping = 1;
+
+ if (in_drop_cycle && state->count > 2)
+ state->count -= 2;
+ else
+ state->count = 1;
+
+ state->drop_next = *now;
+ } else {
+ if (timercmp(now, &state->drop_next, <))
+ return 0;
+
+ state->count += 1;
+ }
+
+ control_law(state, &delta);
+ timeradd(&state->drop_next, &delta, &state->drop_next);
+
+#if 1
+ LOGP(DRLCMAC, LOGL_INFO,
+ "CoDel decided to drop packet, window = %d.%03dms, count = %d\n",
+ (int)delta.tv_sec, (int)(delta.tv_usec / 1000), state->count);
+#endif
+ return 1;
+
+stop_dropping:
+ timerclear(&state->first_above_time);
+not_ok_to_drop:
+ state->dropping = 0;
+ return 0;
+}
diff --git a/src/gprs_codel.h b/src/gprs_codel.h
new file mode 100644
index 0000000..fb74423
--- /dev/null
+++ b/src/gprs_codel.h
@@ -0,0 +1,108 @@
+/* gprs_codel.h
+ *
+ * This is an implementation of the CoDel algorithm based on the reference
+ * pseudocode (see http://queue.acm.org/appendices/codel.html).
+ * Instead of abstracting the queue itself, the following implementation
+ * provides a time stamp based automaton. The main work is done by a single
+ * decision function which updates the state and tells whether to pass or to
+ * drop a packet after it has been taken from the queue.
+ *
+ * Copyright (C) 2015 by Sysmocom s.f.m.c. GmbH
+ * Author: Jacob Erlbeck <jerlbeck@sysmocom.de>
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * 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., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
+ */
+
+#pragma once
+
+#include <sys/time.h>
+
+/* Spec default values */
+#define GPRS_CODEL_DEFAULT_INTERVAL_MS 100
+#define GPRS_CODEL_DEFAULT_MAXPACKET 512
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+struct gprs_codel {
+ int dropping;
+ unsigned count;
+ struct timeval first_above_time;
+ struct timeval drop_next;
+ struct timeval target;
+ struct timeval interval;
+ unsigned maxpacket;
+};
+
+/*!
+ * \brief Decide about packet drop and update CoDel state
+ *
+ * This function takes timing information and decides whether the packet in
+ * question should be dropped in order to keep related queue in a 'good' state.
+ * The function is meant to be called when the packet is dequeued.
+ *
+ * The CoDel state is updated by this function.
+ *
+ * \param state A pointer to the CoDel state of this queue
+ * \param recv The time when the packet has entered the queue,
+ * use NULL if dequeueing was not possible because the queue is
+ * empty
+ * \param now The current (dequeueing) time
+ * \param bytes The number of bytes currently stored in the queue (-1 if
+ * unknown)
+ *
+ * \return != 0 if the packet should be dropped, 0 otherwise
+ */
+int gprs_codel_control(struct gprs_codel *state, const struct timeval *recv,
+ const struct timeval *now, int bytes);
+
+/*!
+ * \brief Initialise CoDel state
+ *
+ * This function initialises the CoDel state object. It sets the interval time
+ * to the default value (GPRS_CODEL_DEFAULT_INTERVAL_MS).
+ *
+ * \param state A pointer to the CoDel state of this queue
+ */
+void gprs_codel_init(struct gprs_codel *state);
+
+/*!
+ * \brief Set interval time
+ *
+ * This function changes the interval time.
+ * The target time is derived from the interval time as proposed in the spec
+ * (5% of interval time).
+ *
+ * \param state A pointer to the CoDel state of this queue
+ * \param interval_ms The initial interval in ms to be used (<= 0 selects the
+ * default value)
+ */
+void gprs_codel_set_interval(struct gprs_codel *state, int interval_ms);
+
+/*!
+ * \brief Set max packet size
+ *
+ * This function changes the maxpacket value. If no more than this number of
+ * bytes are still stored in the queue, no dropping will be done.
+ *
+ * \param state A pointer to the CoDel state of this queue
+ * \param maxpacket The value in bytes
+ */
+void gprs_codel_set_maxpacket(struct gprs_codel *state, int maxpacket);
+
+#ifdef __cplusplus
+}
+#endif
diff --git a/tests/Makefile.am b/tests/Makefile.am
index 5d7aab0..413599b 100644
--- a/tests/Makefile.am
+++ b/tests/Makefile.am
@@ -1,7 +1,7 @@
AM_CPPFLAGS = $(STD_DEFINES_AND_INCLUDES) $(LIBOSMOCORE_CFLAGS) $(LIBOSMOGB_CFLAGS) $(LIBOSMOGSM_CFLAGS) -I$(top_srcdir)/src/
AM_LDFLAGS = -lrt
-check_PROGRAMS = rlcmac/RLCMACTest alloc/AllocTest tbf/TbfTest types/TypesTest ms/MsTest llist/LListTest llc/LlcTest
+check_PROGRAMS = rlcmac/RLCMACTest alloc/AllocTest tbf/TbfTest types/TypesTest ms/MsTest llist/LListTest llc/LlcTest codel/codel_test
noinst_PROGRAMS = emu/pcu_emu
rlcmac_RLCMACTest_SOURCES = rlcmac/RLCMACTest.cpp
@@ -71,6 +71,12 @@ llist_LListTest_LDADD = \
$(LIBOSMOCORE_LIBS) \
$(COMMON_LA)
+codel_codel_test_SOURCES = codel/codel_test.c
+codel_codel_test_LDADD = \
+ $(top_builddir)/src/libgprs.la \
+ $(LIBOSMOCORE_LIBS) \
+ $(COMMON_LA)
+
# The `:;' works around a Bash 3.2 bug when the output is not writeable.
$(srcdir)/package.m4: $(top_srcdir)/configure.ac
:;{ \
@@ -97,7 +103,8 @@ EXTRA_DIST = \
types/TypesTest.ok types/TypesTest.err \
ms/MsTest.ok ms/MsTest.err \
llc/LlcTest.ok llc/LlcTest.err \
- llist/LListTest.ok llist/LListTest.err
+ llist/LListTest.ok llist/LListTest.err \
+ codel/codel_test.ok
DISTCLEANFILES = atconfig
diff --git a/tests/codel/codel_test.c b/tests/codel/codel_test.c
new file mode 100644
index 0000000..91bad13
--- /dev/null
+++ b/tests/codel/codel_test.c
@@ -0,0 +1,147 @@
+/* Test routines for the CoDel implementation
+ *
+ * (C) 2015 by sysmocom s.f.m.c. GmbH
+ * Author: Jacob Erlbeck <jerlbeck@sysmocom.de>
+ */
+
+#undef _GNU_SOURCE
+#define _GNU_SOURCE
+
+#if 0
+#include <osmocom/core/talloc.h>
+#include <osmocom/core/prim.h>
+#endif
+#include <osmocom/core/application.h>
+#include <osmocom/core/utils.h>
+#include <osmocom/core/logging.h>
+
+#include "gprs_codel.h"
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <sys/time.h>
+
+static int do_codel_control(struct gprs_codel *state, const struct timeval *recv,
+ struct timeval *now, const struct timeval *delta_now, int count)
+{
+ int drop;
+
+ drop = gprs_codel_control(state, recv, now, -1);
+ if (drop) {
+ printf("Dropping packet %d, "
+ "recv = %d.%03d, now = %d.%03d, "
+ "codel.count = %d\n",
+ count,
+ (int)recv->tv_sec, (int)recv->tv_usec/1000,
+ (int)now->tv_sec, (int)now->tv_usec/1000,
+ state->count);
+ } else {
+ timeradd(now, delta_now, now);
+ }
+
+ return drop == 0 ? 0 : 1;
+}
+
+static void test_codel(void)
+{
+ struct gprs_codel codel;
+ struct timeval now;
+ struct timeval recv;
+ const struct timeval delta_now = {0, 10000};
+ const struct timeval init_delta_recv = {0, 5000};
+ struct timeval delta_recv;
+ unsigned count;
+ unsigned sum = 0;
+ unsigned dropped = 0;
+ int drop;
+
+ printf("----- %s START\n", __func__);
+ gprs_codel_init(&codel);
+ gprs_codel_set_interval(&codel, 100);
+
+ timerclear(&now);
+ timerclear(&recv);
+ delta_recv = init_delta_recv;
+
+ for (count = 0; count < 20; count++, sum++) {
+ drop = do_codel_control(&codel, &recv, &now, &delta_now, sum);
+ timeradd(&recv, &delta_recv, &recv);
+ dropped += drop;
+ }
+
+ printf("Dropped %d packets\n", dropped);
+ OSMO_ASSERT(dropped == 0);
+ OSMO_ASSERT(!codel.dropping);
+
+ for (count = 0; count < 20; count++, sum++) {
+ drop = do_codel_control(&codel, &recv, &now, &delta_now, sum);
+ timeradd(&recv, &delta_recv, &recv);
+ dropped += drop;
+ }
+
+ OSMO_ASSERT(dropped == 2);
+ OSMO_ASSERT(codel.dropping);
+
+ /* slow down recv rate */
+ delta_recv.tv_usec = delta_now.tv_usec;
+
+ for (count = 0; count < 75; count++, sum++) {
+ drop = do_codel_control(&codel, &recv, &now, &delta_now, sum);
+ timeradd(&recv, &delta_recv, &recv);
+ dropped += drop;
+ }
+
+ OSMO_ASSERT(dropped == 20);
+ OSMO_ASSERT(codel.dropping);
+
+ for (count = 0; count < 50; count++, sum++) {
+ drop = do_codel_control(&codel, &recv, &now, &delta_now, sum);
+ timeradd(&recv, &delta_recv, &recv);
+ dropped += drop;
+ }
+
+ OSMO_ASSERT(dropped == 20);
+ OSMO_ASSERT(!codel.dropping);
+ OSMO_ASSERT(codel.count >= 20);
+
+ /* go back to old data rate */
+ delta_recv = init_delta_recv;
+
+ for (count = 0; count < 20; count++, sum++) {
+ drop = do_codel_control(&codel, &recv, &now, &delta_now, sum);
+ timeradd(&recv, &delta_recv, &recv);
+ dropped += drop;
+ }
+
+ OSMO_ASSERT(dropped == 20);
+ OSMO_ASSERT(!codel.dropping);
+
+ for (count = 0; count < 20; count++, sum++) {
+ drop = do_codel_control(&codel, &recv, &now, &delta_now, sum);
+ timeradd(&recv, &delta_recv, &recv);
+ dropped += drop;
+ }
+
+ OSMO_ASSERT(dropped == 22);
+ OSMO_ASSERT(codel.count >= 2);
+
+ printf("Dropped %d packets\n", dropped);
+
+ printf("----- %s END\n", __func__);
+}
+
+static struct log_info info = {};
+
+int main(int argc, char **argv)
+{
+ osmo_init_logging(&info);
+ log_set_use_color(osmo_stderr_target, 0);
+ log_set_print_filename(osmo_stderr_target, 0);
+ log_set_log_level(osmo_stderr_target, LOGL_INFO);
+
+ printf("===== CoDel test START\n");
+ test_codel();
+ printf("===== CoDel test END\n\n");
+
+ exit(EXIT_SUCCESS);
+}
diff --git a/tests/codel/codel_test.ok b/tests/codel/codel_test.ok
new file mode 100644
index 0000000..ec0696e
--- /dev/null
+++ b/tests/codel/codel_test.ok
@@ -0,0 +1,29 @@
+===== CoDel test START
+----- test_codel START
+Dropped 0 packets
+Dropping packet 21, recv = 0.105, now = 0.210, codel.count = 1
+Dropping packet 32, recv = 0.160, now = 0.310, codel.count = 2
+Dropping packet 41, recv = 0.210, now = 0.390, codel.count = 3
+Dropping packet 47, recv = 0.270, now = 0.440, codel.count = 4
+Dropping packet 53, recv = 0.330, now = 0.490, codel.count = 5
+Dropping packet 59, recv = 0.390, now = 0.540, codel.count = 6
+Dropping packet 64, recv = 0.440, now = 0.580, codel.count = 7
+Dropping packet 69, recv = 0.490, now = 0.620, codel.count = 8
+Dropping packet 73, recv = 0.530, now = 0.650, codel.count = 9
+Dropping packet 77, recv = 0.570, now = 0.680, codel.count = 10
+Dropping packet 81, recv = 0.610, now = 0.710, codel.count = 11
+Dropping packet 86, recv = 0.660, now = 0.750, codel.count = 12
+Dropping packet 89, recv = 0.690, now = 0.770, codel.count = 13
+Dropping packet 93, recv = 0.730, now = 0.800, codel.count = 14
+Dropping packet 97, recv = 0.770, now = 0.830, codel.count = 15
+Dropping packet 100, recv = 0.800, now = 0.850, codel.count = 16
+Dropping packet 104, recv = 0.840, now = 0.880, codel.count = 17
+Dropping packet 107, recv = 0.870, now = 0.900, codel.count = 18
+Dropping packet 111, recv = 0.910, now = 0.930, codel.count = 19
+Dropping packet 114, recv = 0.940, now = 0.950, codel.count = 20
+Dropping packet 186, recv = 1.555, now = 1.660, codel.count = 1
+Dropping packet 197, recv = 1.610, now = 1.760, codel.count = 2
+Dropped 22 packets
+----- test_codel END
+===== CoDel test END
+
diff --git a/tests/testsuite.at b/tests/testsuite.at
index d7a85e5..71179d1 100644
--- a/tests/testsuite.at
+++ b/tests/testsuite.at
@@ -50,3 +50,9 @@ cat $abs_srcdir/llist/LListTest.ok > expout
cat $abs_srcdir/llist/LListTest.err > experr
AT_CHECK([$OSMO_QEMU $abs_top_builddir/tests/llist/LListTest], [0], [expout], [experr])
AT_CLEANUP
+
+AT_SETUP([codel])
+AT_KEYWORDS([codel])
+cat $abs_srcdir/codel/codel_test.ok > expout
+AT_CHECK([$OSMO_QEMU $abs_top_builddir/tests/codel/codel_test], [0], [expout], [ignore])
+AT_CLEANUP