From 16f04029db50b765d952cf4cf053d34262a40db1 Mon Sep 17 00:00:00 2001
From: Martin Mares <mj@ucw.cz>
Date: Fri, 20 Feb 2009 17:41:47 +0100
Subject: [PATCH] Logging: Implemented rate limiting based on the Token Bucket
 Filter.

So far, it is a simple FP implementation. Maybe I will switch to integers later.
---
 ucw/Makefile |  2 +-
 ucw/tbf.c    | 56 ++++++++++++++++++++++++++++++++++++++++++++++++++++
 ucw/tbf.h    | 23 +++++++++++++++++++++
 3 files changed, 80 insertions(+), 1 deletion(-)
 create mode 100644 ucw/tbf.c
 create mode 100644 ucw/tbf.h

diff --git a/ucw/Makefile b/ucw/Makefile
index ccfc20ce..a696e7a7 100644
--- a/ucw/Makefile
+++ b/ucw/Makefile
@@ -12,7 +12,7 @@ LIBUCW_MODS= \
 	alloc alloc_str realloc bigalloc mempool mempool-str mempool-fmt eltpool \
 	mmap partmap hashfunc \
 	slists simple-lists bitsig \
-	log log-stream log-file log-syslog log-conf proctitle \
+	log log-stream log-file log-syslog log-conf proctitle tbf \
 	conf-alloc conf-dump conf-input conf-intr conf-journal conf-parse conf-section \
 	ipaccess \
 	profile \
diff --git a/ucw/tbf.c b/ucw/tbf.c
new file mode 100644
index 00000000..7e4d474e
--- /dev/null
+++ b/ucw/tbf.c
@@ -0,0 +1,56 @@
+/*
+ *	UCW Library -- Rate Limiting based on the Token Bucket Filter
+ *
+ *	(c) 2009 Martin Mares <mj@ucw.cz>
+ *
+ *	This software may be freely distributed and used according to the terms
+ *	of the GNU Lesser General Public License.
+ */
+
+#include "ucw/lib.h"
+#include "ucw/tbf.h"
+
+void
+tbf_init(struct token_bucket_filter *f)
+{
+  if (!f->burst)
+    f->burst = MAX(2*f->rate, 1);
+  f->last_hit = 0;
+  f->bucket = f->burst;
+}
+
+int
+tbf_limit(struct token_bucket_filter *f, timestamp_t now)
+{
+  timestamp_t delta_t = now - f->last_hit;
+  f->last_hit = now;
+
+  double b = f->bucket + f->rate * delta_t / 1000;
+  b = MIN(b, f->burst);
+  if (b >= 1)
+    {
+      f->bucket = b - 1;
+      return 1;
+    }
+  else
+    {
+      f->bucket = b;
+      return 0;
+    }
+}
+
+#ifdef TEST
+
+int main(void)
+{
+  struct token_bucket_filter t = { .rate = 1, .burst = 2 };
+  tbf_init(&t);
+  for (timestamp_t now = 0; now < 3000; now += 77)
+    {
+      int res = tbf_limit(&t, now);
+      msg(L_DEBUG, "t=%u result=%d bucket=%f", (uns) now, res, t.bucket);
+    }
+  return 0;
+}
+
+#endif
diff --git a/ucw/tbf.h b/ucw/tbf.h
new file mode 100644
index 00000000..14154791
--- /dev/null
+++ b/ucw/tbf.h
@@ -0,0 +1,23 @@
+/*
+ *	UCW Library -- Rate Limiting based on the Token Bucket Filter
+ *
+ *	(c) 2009 Martin Mares <mj@ucw.cz>
+ *
+ *	This software may be freely distributed and used according to the terms
+ *	of the GNU Lesser General Public License.
+ */
+
+#ifndef _UCW_TBF_H_
+#define _UCW_TBF_H_
+
+struct token_bucket_filter {
+  double rate;				// Number of tokens per second
+  uns burst;				// Capacity of the bucket
+  timestamp_t last_hit;			// Internal state...
+  double bucket;
+};
+
+void tbf_init(struct token_bucket_filter *f);
+int tbf_limit(struct token_bucket_filter *f, timestamp_t now);
+
+#endif
-- 
2.39.2