summaryrefslogtreecommitdiffstats
path: root/src/mpq.h
diff options
context:
space:
mode:
authorMatt Dunwoodie <ncon@mail.noconroy.net>2019-09-19 13:43:56 +0200
committerMatt Dunwoodie <ncon@mail.noconroy.net>2019-09-19 13:43:56 +0200
commit32c7ece818e25483b2d7b19d893eab1c837e3945 (patch)
treeffdead93cdcc961e931ffbc39f6af11ea4100db6 /src/mpq.h
parentFix incorrect behaviour in wg_handshake_initiation_ready (diff)
downloadwireguard-openbsd-32c7ece818e25483b2d7b19d893eab1c837e3945.tar.xz
wireguard-openbsd-32c7ece818e25483b2d7b19d893eab1c837e3945.zip
Add simplified mpq.h
The idea here isn't to be complicated with mpq.h, instead, mpq is just a queue that follows the parallel/serial queue mentality. That is, we want to operate on a queue in parallel, but the final step should still be performed in enqueueing order. This is most helpful to prevent reordering of incoming and outgoing packets in the network stack. This probably won't be used for a while, but it is handy to have around.
Diffstat (limited to 'src/mpq.h')
-rw-r--r--src/mpq.h177
1 files changed, 177 insertions, 0 deletions
diff --git a/src/mpq.h b/src/mpq.h
new file mode 100644
index 00000000000..9af2ca8e086
--- /dev/null
+++ b/src/mpq.h
@@ -0,0 +1,177 @@
+/*
+ * 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 _MPQ_H_
+#define _MPQ_H_
+
+#include <sys/types.h>
+#include <sys/malloc.h>
+#include <sys/mutex.h>
+#include <sys/systm.h>
+
+struct mpq {
+ struct mutex mpq_mtx;
+ size_t mpq_len, mpq_maxlen, mpq_phead, mpq_shead, mpq_tail;
+ void **mpq_items;
+};
+
+struct mpq_commit {
+ void **itemp;
+};
+
+void mpq_init(struct mpq *, int, size_t);
+void mpq_destroy(struct mpq *);
+int mpq_enqueue(struct mpq *, void *);
+void *mpq_parallel(struct mpq *, struct mpq_commit *);
+void mpq_parallel_commit(struct mpq *, struct mpq_commit *, void *);
+void *mpq_serial(struct mpq *);
+
+#define MPQ_ITEM(mpq, item) ((mpq)->mpq_items[(mpq)->item])
+#define MPQ_INC(mpq, item) ((mpq)->item = ((mpq)->item + 1) % (mpq)->mpq_maxlen)
+#define MPQ_LOAD(mpq, item) ((mpq)->item <= (mpq)->mpq_tail ? \
+ (mpq)->mpq_tail - (mpq)->item : (mpq)->mpq_maxlen - (mpq)->item + (mpq)->mpq_tail)
+
+void
+mpq_init(struct mpq *mpq, int ipl, size_t len)
+{
+ bzero(mpq, sizeof(*mpq));
+ mtx_init(&mpq->mpq_mtx, ipl);
+ mpq->mpq_items = mallocarray(len, sizeof(void *), M_DEVBUF, M_WAITOK);
+ mpq->mpq_maxlen = len;
+}
+
+void *
+mpq_parallel(struct mpq *mpq, struct mpq_commit *commit)
+{
+ void *item = NULL;
+ mtx_enter(&mpq->mpq_mtx);
+ item = MPQ_ITEM(mpq, mpq_phead);
+ if (item != NULL) {
+ commit->itemp = &MPQ_ITEM(mpq, mpq_phead);
+ MPQ_ITEM(mpq, mpq_phead) = NULL;
+ MPQ_INC(mpq, mpq_phead);
+ } else {
+ commit->itemp = NULL;
+ }
+ mtx_leave(&mpq->mpq_mtx);
+ return item;
+}
+
+void
+mpq_parallel_commit(struct mpq *mpq, struct mpq_commit *commit, void *item)
+{
+ mtx_enter(&mpq->mpq_mtx);
+ *commit->itemp = item;
+ mtx_leave(&mpq->mpq_mtx);
+}
+
+void *
+mpq_serial(struct mpq *mpq)
+{
+ void *item = NULL;
+ mtx_enter(&mpq->mpq_mtx);
+ item = MPQ_ITEM(mpq, mpq_shead);
+ if (item != NULL && mpq->mpq_phead != mpq->mpq_shead) {
+ MPQ_ITEM(mpq, mpq_shead) = NULL;
+ MPQ_INC(mpq, mpq_shead);
+ }
+ mtx_leave(&mpq->mpq_mtx);
+ return item;
+}
+
+int
+mpq_enqueue(struct mpq *mpq, void *item)
+{
+ int dropped = 0;
+ assert(item != NULL);
+ mtx_enter(&mpq->mpq_mtx);
+ if (MPQ_LOAD(mpq, mpq_shead) < mpq->mpq_maxlen - 1) {
+ MPQ_ITEM(mpq, mpq_tail) = item;
+ MPQ_INC(mpq, mpq_tail);
+ } else {
+ dropped = 1;
+ }
+ mtx_leave(&mpq->mpq_mtx);
+
+ return dropped;
+}
+
+/* TESTS (need to comment out sys/systm.h in mpq.h includes)
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <assert.h>
+#include <string.h>
+#define mallocarray(a, b, _x, _y) malloc((a) * (b))
+#define bzero(a, b) memset(a, 0, b);
+#include "mpq.h"
+
+void __mtx_init(struct mutex *a, int b) {}
+void mtx_enter(struct mutex *a) {}
+void mtx_leave(struct mutex *a) {}
+
+int
+main(int argc, char *argv[])
+{
+ int ret;
+ size_t i;
+ struct mpq_commit commit, falsecommit;
+ struct mpq test_mpq;
+ mpq_init(&test_mpq, 0, 4);
+
+ // basic test
+ assert(mpq_parallel(&test_mpq, &commit) == NULL);
+ assert(commit.itemp == NULL);
+ assert(mpq_serial(&test_mpq) == NULL);
+
+ for (i = 1; i < 8; i++) {
+ ret = mpq_enqueue(&test_mpq, (void *)i);
+ assert(ret == (i < 4 ? 0 : 1));
+ }
+
+ assert(mpq_parallel(&test_mpq, &commit) == (void *)1);
+ assert(mpq_serial(&test_mpq) == NULL);
+ mpq_parallel_commit(&test_mpq, &commit, (void *) 1);
+ assert(mpq_serial(&test_mpq) == (void *)1);
+
+ assert(mpq_parallel(&test_mpq, &commit) == (void *)2);
+ mpq_parallel_commit(&test_mpq, &commit, (void *) 2);
+ assert(mpq_parallel(&test_mpq, &commit) == (void *)3);
+ mpq_parallel_commit(&test_mpq, &commit, (void *) 3);
+
+ assert(mpq_parallel(&test_mpq, &commit) == NULL);
+
+ assert(mpq_serial(&test_mpq) == (void *)2);
+ assert(mpq_serial(&test_mpq) == (void *)3);
+ assert(mpq_serial(&test_mpq) == NULL);
+
+ // test replacement
+
+ mpq_enqueue(&test_mpq, (void *)1);
+
+ assert(mpq_parallel(&test_mpq, &commit) == (void *)1);
+ assert(mpq_parallel(&test_mpq, &falsecommit) == NULL);
+ mpq_parallel_commit(&test_mpq, &commit, (void *) 2);
+ assert(mpq_parallel(&test_mpq, &commit) == NULL);
+ assert(mpq_serial(&test_mpq) == (void *)2);
+ assert(mpq_serial(&test_mpq) == NULL);
+
+ printf("Passed!!\n");
+}
+
+*/
+
+#endif /* _MPQ_H_ */