summaryrefslogtreecommitdiffstats
path: root/src/bloombucket.h
diff options
context:
space:
mode:
authorMatt Dunwoodie <ncon@mail.noconroy.net>2019-08-22 20:02:14 +1000
committerMatt Dunwoodie <ncon@mail.noconroy.net>2019-08-22 21:52:16 +1000
commit0f81dae44d741a3ce2c6d1a59413c3703612b5f0 (patch)
tree14c3959e21414b0ac46b7761fc78bc2adb5eb6ef /src/bloombucket.h
parentActually make sure wg.4 gets included in build (diff)
downloadwireguard-openbsd-0f81dae44d741a3ce2c6d1a59413c3703612b5f0.tar.xz
wireguard-openbsd-0f81dae44d741a3ce2c6d1a59413c3703612b5f0.zip
Add bloombucket.h for ratelimiting.
In my perpetual quest for allocationless datastructures, this bloombucket attempts to rate limit an arbitrary number of peers during initiation. It works on a mix of a bloom filter and a token bucket, and has configurable parameters for size and number of hashes. The hashes are kept independent by using unique siphash keys. The idea is that a unique input, in this case the peer ip will be hashed into multiple buckets, and each of those buckets incremented. When evaluating if a packet should be rate limited, it sees if at least one of those buckets is not at the threshold. I don't have any good mathematical notes behind this, but will need to sit down and do some tests to get some sane defaults for the values.
Diffstat (limited to 'src/bloombucket.h')
-rw-r--r--src/bloombucket.h127
1 files changed, 127 insertions, 0 deletions
diff --git a/src/bloombucket.h b/src/bloombucket.h
new file mode 100644
index 00000000000..7bcaf863cce
--- /dev/null
+++ b/src/bloombucket.h
@@ -0,0 +1,127 @@
+/*
+ * Copyright (c) 2019 Matt Dunwoodie <ncon@noconroy.net>
+ *
+ * Permission to use, copy, modify, and distribute this software for any
+ * purpose with or without fee is hereby granted, provided that the above
+ * copyright notice and this permission notice appear in all copies.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+ * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+ * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+ * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+ * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+ * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ */
+
+#ifndef __BLOOMBUCKET_H__
+#define __BLOOMBUCKET_H__
+
+#include <sys/types.h>
+#include <sys/timeout.h>
+#include <crypto/siphash.h>
+
+struct bloom_bucket {
+ int type;
+ size_t size, nkeys;
+ uint8_t *bucket, interval, thresh;
+ SIPHASH_KEY *keys;
+ struct timeout tick;
+};
+
+void bb_init(struct bloom_bucket *, size_t, size_t, uint8_t, uint8_t, int, int);
+void bb_destroy(struct bloom_bucket *);
+void bb_tick(void *);
+int bb_recv(struct bloom_bucket *, uint8_t *, size_t);
+uint8_t bb_load(struct bloom_bucket *);
+
+void
+bb_init(struct bloom_bucket *bb, size_t size, size_t keys, uint8_t interval,
+ uint8_t thresh, int type, int flags)
+{
+ size_t i;
+
+ for (bb->size = 1; bb->size < size; bb->size <<= 1);
+
+ bb->type = type;
+ bb->nkeys = keys;
+ bb->thresh = thresh;
+ bb->interval = interval;
+ bb->keys = mallocarray(bb->nkeys, sizeof(*bb->keys), bb->type, flags);
+ bb->bucket = mallocarray(bb->size, 1, bb->type, flags | M_ZERO);
+
+ for (i = 0; i < bb->nkeys; i++)
+ arc4random_buf(&bb->keys[i], sizeof(*bb->keys));
+
+ timeout_set(&bb->tick, bb_tick, bb);
+}
+
+void
+bb_destroy(struct bloom_bucket *bb)
+{
+ free(bb->keys, bb->type, bb->nkeys);
+ free(bb->bucket, bb->type, bb->size);
+}
+
+void
+bb_tick(void *_bb)
+{
+ struct bloom_bucket *bb = _bb;
+ int act;
+ size_t i;
+
+ for (i = 0, act = 0; i < bb->size; i++) {
+ /* Check to protect underflow, as well as flag
+ * if action has been taken, therefore should
+ * schedule again. */
+ if (bb->bucket[i] > 0) {
+ bb->bucket[i]--;
+ act = 1;
+ }
+ }
+
+ if (act && !timeout_pending(&bb->tick))
+ timeout_add_sec(&bb->tick, bb->interval);
+}
+
+int
+bb_recv(struct bloom_bucket *bb, uint8_t *buf, size_t n)
+{
+ size_t i;
+ uint64_t hash;
+ uint8_t *elem, min = 0xff;
+
+ for (i = 0; i < bb->nkeys; i++) {
+ hash = SipHash24(&bb->keys[i], buf, n);
+ elem = &bb->bucket[hash & (bb->size - 1)];
+ if (*elem < min)
+ min = *elem;
+ if (*elem < bb->thresh)
+ (*elem)++;
+ }
+
+ if (!timeout_pending(&bb->tick))
+ timeout_add_sec(&bb->tick, bb->interval);
+
+ return min == bb->thresh;
+}
+
+uint8_t
+bb_load(struct bloom_bucket *bb)
+{
+ size_t i;
+ uint8_t log;
+ uint64_t sum;
+ for (i = 0, sum = 0; i < bb->size; i++)
+ sum += bb->bucket[i];
+
+ sum *= (0xffffffffffffffff / (bb->size * bb->thresh));
+
+ log = 0;
+ while (sum >>= 1)
+ log++;
+
+ return log;
+}
+
+#endif /* __BLOOMBUCKET_H__ */