[ccan] [PATCH] jacobson_karels: New module

[David Gibson]

A straightforward implementation of the Jacobson/Karels algorithm for
estimating round-trip time on a network link.

Signed-off-by: David Gibson <david at gibson.dropbear.id.au>
---
 ccan/jacobson_karels/LICENSE           |  1 +
 ccan/jacobson_karels/_info             | 25 ++++++++++++++++++++++++
 ccan/jacobson_karels/jacobson_karels.h | 35 ++++++++++++++++++++++++++++++++++
 ccan/jacobson_karels/test/run.c        | 23 ++++++++++++++++++++++
 4 files changed, 84 insertions(+)
 create mode 120000 ccan/jacobson_karels/LICENSE
 create mode 100644 ccan/jacobson_karels/_info
 create mode 100644 ccan/jacobson_karels/jacobson_karels.h
 create mode 100644 ccan/jacobson_karels/test/run.c

diff --git a/ccan/jacobson_karels/LICENSE b/ccan/jacobson_karels/LICENSE
new file mode 120000
index 0000000..dc314ec
--- /dev/null
+++ b/ccan/jacobson_karels/LICENSE
@@ -0,0 +1 @@
+../../licenses/LGPL-2.1
\ No newline at end of file
diff --git a/ccan/jacobson_karels/_info b/ccan/jacobson_karels/_info
new file mode 100644
index 0000000..9165470
--- /dev/null
+++ b/ccan/jacobson_karels/_info
@@ -0,0 +1,25 @@
+#include <string.h>
+#include "config.h"
+
+/**
+ * jacobson_karels - Jacobson/Karels Round Trip Time algorithm
+ *
+ * This implements the Jacobson/Karels algorithm for estimating round
+ * trip time and appropriate timeouts over a network link.
+ *
+ * Author: David Gibson <david at gibson.dropbear.id>
+ * License: LGPL (v2.1 or any later version)
+ */
+int main(int argc, char *argv[])
+{
+	/* Expect exactly one argument */
+	if (argc != 2)
+		return 1;
+
+	if (strcmp(argv[1], "depends") == 0) {
+		printf("ccan/minmax\n");
+		return 0;
+	}
+
+	return 1;
+}
diff --git a/ccan/jacobson_karels/jacobson_karels.h b/ccan/jacobson_karels/jacobson_karels.h
new file mode 100644
index 0000000..0e9bc2d
--- /dev/null
+++ b/ccan/jacobson_karels/jacobson_karels.h
@@ -0,0 +1,35 @@
+/* Licensed under LGPLv2.1+ - see LICENSE file for details */
+#ifndef CCAN_JACOBSON_KARELS_H
+#define CCAN_JACOBSON_KARELS_H
+
+#include "config.h"
+
+#include <ccan/minmax/minmax.h>
+
+#define JACOBSON_KARELS(_name, _type, _a1, _a2, _b1, _b2, _g, _k) \
+	struct _name##_state { \
+		_type rtt, variance; \
+	}; \
+	static void _name##_init(struct _name##_state *s, \
+				 _type rtt0, _type var0)  \
+	{ \
+		s->rtt = rtt0; \
+		s->variance = var0; \
+	} \
+	static void _name##_update(struct _name##_state *s, _type sample) \
+	{ \
+		_type diff = sample - s->rtt; \
+		s->rtt += (_a2) * diff / ((_a1) + (_a2)); \
+		diff = (diff < 0) ? -diff : diff; \
+		s->variance = ((_b1)*s->variance + (_b2) * diff) \
+			/ ((_b1) + (_b2));			 \
+	} \
+	static _type _name##_timeout(struct _name##_state *s, \
+				     _type tmin, _type tmax)  \
+	{ \
+		return clamp((_g) * s->rtt + (_k)*s->variance, tmin, tmax); \
+	}
+
+JACOBSON_KARELS(jacobson_karels, unsigned long, 7, 1, 3, 1, 1, 4)
+
+#endif /* CCAN_JACOBSON_KARELS_H */
diff --git a/ccan/jacobson_karels/test/run.c b/ccan/jacobson_karels/test/run.c
new file mode 100644
index 0000000..374345f
--- /dev/null
+++ b/ccan/jacobson_karels/test/run.c
@@ -0,0 +1,23 @@
+#include <ccan/jacobson_karels/jacobson_karels.h>
+#include <ccan/tap/tap.h>
+
+static void first_test(void)
+{
+	struct jacobson_karels_state s;
+
+	jacobson_karels_init(&s, 0, 0);
+	jacobson_karels_update(&s, 200);
+
+	ok1(jacobson_karels_timeout(&s, 2, 1000) == 225);
+}
+
+int main(void)
+{
+	/* This is how many tests you plan to run */
+	plan_tests(1);
+
+	first_test();
+
+	/* This exits depending on whether all tests passed */
+	return exit_status();
+}
-- 
1.9.3