[PATCH v3 libinput] util: introduce ratelimit helpers

[Peter Hutterer]

From: David Herrmann <dh.herrmann at gmail.com>

This adds "struct ratelimit" and "ratelimit_test()". It's a very simple
rate-limit helper modeled after Linux' lib/ratelimit.c by Dave Young.

This comes in handy to limit log-messages in possible busy loops etc..

Signed-off-by: David Herrmann <dh.herrmann at gmail.com>
Reviewed-by: Peter Hutterer <peter.hutterer at who-t.net>
Signed-off-by: Peter Hutterer <peter.hutterer at who-t.net>
---
The test succeeded but not in valgrind which slows everything down enough
that we didn't trigger the rate limit (valgrind is part of make check). I
though of adding extra flags to detect when we're running valgrind but it's
simpler to just extend the timeouts a bit.
So instead of 10 msg per 10ms it's 10 per 100ms, the wait is 20ms and then
another 90ms to go definitely above the 100ms.
And only loop three times, otherwise we trigger the generic test timeout
detection.

Changes to v3:
- ck_assert(a == b) -> ck_assert_int_eq(a, b)
- timeouts tweaked to avoid test failures when running through valgrind

 src/libinput-util.c | 48 ++++++++++++++++++++++++++++++++++++++++++++++++
 src/libinput-util.h | 16 ++++++++++++++++
 test/misc.c         | 42 ++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 106 insertions(+)

diff --git a/src/libinput-util.c b/src/libinput-util.c
index eeb9786..34d5549 100644
--- a/src/libinput-util.c
+++ b/src/libinput-util.c
@@ -65,3 +65,51 @@ list_empty(const struct list *list)
 {
 	return list->next == list;
 }
+
+void
+ratelimit_init(struct ratelimit *r, uint64_t ival_ms, unsigned int burst)
+{
+	r->interval = ival_ms;
+	r->begin = 0;
+	r->burst = burst;
+	r->num = 0;
+}
+
+/*
+ * Perform rate-limit test. Returns RATELIMIT_PASS if the rate-limited action
+ * is still allowed, RATELIMIT_THRESHOLD if the limit has been reached with
+ * this call, and RATELIMIT_EXCEEDED if you're beyond the threshold.
+ * It's safe to treat the return-value as boolean, if you're not interested in
+ * the exact state. It evaluates to "true" if the threshold hasn't been
+ * exceeded, yet.
+ *
+ * The ratelimit object must be initialized via ratelimit_init().
+ *
+ * Modelled after Linux' lib/ratelimit.c by Dave Young
+ * <hidave.darkstar at gmail.com>, which is licensed GPLv2.
+ */
+enum ratelimit_state
+ratelimit_test(struct ratelimit *r)
+{
+	struct timespec ts;
+	uint64_t mtime;
+
+	if (r->interval <= 0 || r->burst <= 0)
+		return RATELIMIT_PASS;
+
+	clock_gettime(CLOCK_MONOTONIC, &ts);
+	mtime = ts.tv_sec * 1000 + ts.tv_nsec / 1000 / 1000;
+
+	if (r->begin <= 0 || r->begin + r->interval < mtime) {
+		/* reset counter */
+		r->begin = mtime;
+		r->num = 1;
+		return RATELIMIT_PASS;
+	} else if (r->num < r->burst) {
+		/* continue burst */
+		return (++r->num == r->burst) ? RATELIMIT_THRESHOLD
+					      : RATELIMIT_PASS;
+	}
+
+	return RATELIMIT_EXCEEDED;
+}
diff --git a/src/libinput-util.h b/src/libinput-util.h
index 51759e8..909c9db 100644
--- a/src/libinput-util.h
+++ b/src/libinput-util.h
@@ -280,4 +280,20 @@ matrix_to_farray6(const struct matrix *m, float out[6])
 	out[5] = m->val[1][2];
 }
 
+enum ratelimit_state {
+	RATELIMIT_EXCEEDED,
+	RATELIMIT_THRESHOLD,
+	RATELIMIT_PASS,
+};
+
+struct ratelimit {
+	uint64_t interval;
+	uint64_t begin;
+	unsigned int burst;
+	unsigned int num;
+};
+
+void ratelimit_init(struct ratelimit *r, uint64_t ival_ms, unsigned int burst);
+enum ratelimit_state ratelimit_test(struct ratelimit *r);
+
 #endif /* LIBINPUT_UTIL_H */
diff --git a/test/misc.c b/test/misc.c
index 1512180..38320f3 100644
--- a/test/misc.c
+++ b/test/misc.c
@@ -508,6 +508,46 @@ START_TEST(matrix_helpers)
 }
 END_TEST
 
+START_TEST(ratelimit_helpers)
+{
+	struct ratelimit rl;
+	unsigned int i, j;
+
+	/* 10 attempts every 100ms */
+	ratelimit_init(&rl, 100, 10);
+
+	for (j = 0; j < 3; ++j) {
+		/* a burst of 9 attempts must succeed */
+		for (i = 0; i < 9; ++i) {
+			ck_assert_int_eq(ratelimit_test(&rl),
+					 RATELIMIT_PASS);
+		}
+
+		/* the 10th attempt reaches the threshold */
+		ck_assert_int_eq(ratelimit_test(&rl), RATELIMIT_THRESHOLD);
+
+		/* ..then further attempts must fail.. */
+		ck_assert_int_eq(ratelimit_test(&rl), RATELIMIT_EXCEEDED);
+
+		/* ..regardless of how often we try. */
+		for (i = 0; i < 100; ++i) {
+			ck_assert_int_eq(ratelimit_test(&rl),
+					 RATELIMIT_EXCEEDED);
+		}
+
+		/* ..even after waiting 20ms */
+		msleep(20);
+		for (i = 0; i < 100; ++i) {
+			ck_assert_int_eq(ratelimit_test(&rl),
+					 RATELIMIT_EXCEEDED);
+		}
+
+		/* but after 100ms the counter is reset */
+		msleep(90); /* +10ms to account for time drifts */
+	}
+}
+END_TEST
+
 int main (int argc, char **argv) {
 	litest_add_no_device("events:conversion", event_conversion_device_notify);
 	litest_add_no_device("events:conversion", event_conversion_pointer);
@@ -519,5 +559,7 @@ int main (int argc, char **argv) {
 	litest_add_no_device("config:status string", config_status_string);
 
 	litest_add_no_device("misc:matrix", matrix_helpers);
+	litest_add_no_device("misc:ratelimit", ratelimit_helpers);
+
 	return litest_run(argc, argv);
 }
-- 
2.1.0