[PATCH 1/2] Introduce basic rate limiter

[Vladimir Davydov]

We will use it to limit the rate of log messages.

Needed for #2218
---
 src/ratelimit.h            | 104 +++++++++++++++++++++++++++++++++++++++++++++
 test/unit/CMakeLists.txt   |   2 +
 test/unit/ratelimit.c      |  78 ++++++++++++++++++++++++++++++++++
 test/unit/ratelimit.result |  13 ++++++
 4 files changed, 197 insertions(+)
 create mode 100644 src/ratelimit.h
 create mode 100644 test/unit/ratelimit.c
 create mode 100644 test/unit/ratelimit.result

diff --git a/src/ratelimit.h b/src/ratelimit.h
new file mode 100644
index 00000000..2bf0bac7
--- /dev/null
+++ b/src/ratelimit.h
@@ -0,0 +1,104 @@
+#ifndef TARANTOOL_RATELIMIT_H_INCLUDED
+#define TARANTOOL_RATELIMIT_H_INCLUDED
+/*
+ * Copyright 2010-2018, Tarantool AUTHORS, please see AUTHORS file.
+ *
+ * Redistribution and use in source and binary forms, with or
+ * without modification, are permitted provided that the following
+ * conditions are met:
+ *
+ * 1. Redistributions of source code must retain the above
+ *    copyright notice, this list of conditions and the
+ *    following disclaimer.
+ *
+ * 2. Redistributions in binary form must reproduce the above
+ *    copyright notice, this list of conditions and the following
+ *    disclaimer in the documentation and/or other materials
+ *    provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY <COPYRIGHT HOLDER> ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
+ * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+ * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL
+ * <COPYRIGHT HOLDER> OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
+ * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
+ * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
+ * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF
+ * THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ */
+#include <stdbool.h>
+
+#if defined(__cplusplus)
+extern "C" {
+#endif
+
+/**
+ * Rate limit state.
+ */
+struct ratelimit {
+	/** Time interval used for rate limiting, in seconds. */
+	double interval;
+	/** Max number of events per interval. */
+	int burst;
+	/** Number of events emitted in the current interval. */
+	int emitted;
+	/** Number of events suppressed in the current interval. */
+	int suppressed;
+	/** Start time of the current interval. */
+	double start;
+};
+
+/**
+ * Rate limit state initializer.
+ */
+#define RATELIMIT_INITIALIZER(interval_init, burst_init) \
+	{ (interval_init), (burst_init), 0, 0, 0 }
+
+/**
+ * Initialize a rate limit state.
+ */
+static inline void
+ratelimit_create(struct ratelimit *rl, double interval, int burst)
+{
+	rl->interval = interval;
+	rl->burst = burst;
+	rl->emitted = 0;
+	rl->suppressed = 0;
+	rl->start = 0;
+}
+
+/**
+ * Check if an event may be emitted. Returns true on success.
+ * @now is the current time.
+ *
+ * If the current interval is over, the total number of events
+ * suppressed in it is added to @suppressed.
+ */
+static inline bool
+ratelimit_check(struct ratelimit *rl, double now, int *suppressed)
+{
+	if (now > rl->start + rl->interval) {
+		/* Current interval is over, reset counters. */
+		*suppressed += rl->suppressed;
+		rl->emitted = 0;
+		rl->suppressed = 0;
+		rl->start = now;
+	}
+	if (rl->emitted < rl->burst) {
+		rl->emitted++;
+		return true;
+	} else {
+		rl->suppressed++;
+		return false;
+	}
+}
+
+#if defined(__cplusplus)
+} /* extern "C" */
+#endif
+
+#endif /* TARANTOOL_RATELIMIT_H_INCLUDED */
diff --git a/test/unit/CMakeLists.txt b/test/unit/CMakeLists.txt
index 7cba5cbb..0025d361 100644
--- a/test/unit/CMakeLists.txt
+++ b/test/unit/CMakeLists.txt
@@ -136,6 +136,8 @@ add_executable(rmean.test rmean.cc)
 target_link_libraries(rmean.test stat unit)
 add_executable(histogram.test histogram.c)
 target_link_libraries(histogram.test stat unit)
+add_executable(ratelimit.test ratelimit.c)
+target_link_libraries(ratelimit.test unit)
 
 add_executable(say.test say.c)
 target_link_libraries(say.test core unit)
diff --git a/test/unit/ratelimit.c b/test/unit/ratelimit.c
new file mode 100644
index 00000000..3dfbe485
--- /dev/null
+++ b/test/unit/ratelimit.c
@@ -0,0 +1,78 @@
+#include <stdlib.h>
+#include <time.h>
+
+#include "unit.h"
+#include "ratelimit.h"
+
+#define check(expected_emitted, expected_suppressed) do {		\
+	is(emitted, expected_emitted, "emitted %d expected %d",		\
+	   emitted, expected_emitted);					\
+	is(suppressed, expected_suppressed, "suppressed %d expected %d",\
+	   suppressed, expected_suppressed);				\
+} while (0)
+
+int
+main()
+{
+	header();
+	plan(10);
+
+	srand(time(NULL));
+	double now = rand();
+
+	int burst = 10;
+	double interval = 5;
+	int count, emitted, suppressed;
+	struct ratelimit rl = RATELIMIT_INITIALIZER(interval, burst);
+	now += interval;
+
+	count = burst;
+	emitted = suppressed = 0;
+	for (int i = 0; i < count; i++) {
+		if (ratelimit_check(&rl, now, &suppressed))
+			emitted++;
+		now += interval / count / 2;
+	}
+	check(count, 0);
+
+	emitted = suppressed = 0;
+	for (int i = 0; i < count; i++) {
+		if (ratelimit_check(&rl, now, &suppressed))
+			emitted++;
+		now += interval / count / 2;
+	}
+	check(0, 0);
+
+	now += 1;
+	emitted = suppressed = 0;
+	if (ratelimit_check(&rl, now, &suppressed))
+		emitted++;
+	check(1, count);
+
+	now += interval * 2;
+	emitted = suppressed = 0;
+	if (ratelimit_check(&rl, now, &suppressed))
+		emitted++;
+	check(1, 0);
+
+	interval = 5;
+	burst = 100;
+	ratelimit_create(&rl, interval, burst);
+
+	int interval_count = 10;
+	count = burst * interval_count * 4;
+	emitted = suppressed = 0;
+	for (int i = 0; i < count; i++) {
+		if (ratelimit_check(&rl, now, &suppressed))
+			emitted++;
+		now += interval_count * interval / count;
+	}
+	now += interval;
+	ratelimit_check(&rl, now, &suppressed);
+	check(interval_count * burst, count - interval_count * burst);
+
+	check_plan();
+	footer();
+
+	return 0;
+}
diff --git a/test/unit/ratelimit.result b/test/unit/ratelimit.result
new file mode 100644
index 00000000..8a755c64
--- /dev/null
+++ b/test/unit/ratelimit.result
@@ -0,0 +1,13 @@
+	*** main ***
+1..10
+ok 1 - emitted 10 expected 10
+ok 2 - suppressed 0 expected 0
+ok 3 - emitted 0 expected 0
+ok 4 - suppressed 0 expected 0
+ok 5 - emitted 1 expected 1
+ok 6 - suppressed 10 expected 10
+ok 7 - emitted 1 expected 1
+ok 8 - suppressed 0 expected 0
+ok 9 - emitted 1000 expected 1000
+ok 10 - suppressed 3000 expected 3000
+	*** main: done ***
-- 
2.11.0