summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--libcr_ipc/include/libcr_ipc/_TODO_select.h65
-rw-r--r--libcr_ipc/include/libcr_ipc/chan.h34
-rw-r--r--libcr_ipc/include/libcr_ipc/select.h224
3 files changed, 240 insertions, 83 deletions
diff --git a/libcr_ipc/include/libcr_ipc/_TODO_select.h b/libcr_ipc/include/libcr_ipc/_TODO_select.h
deleted file mode 100644
index 5510fc4..0000000
--- a/libcr_ipc/include/libcr_ipc/_TODO_select.h
+++ /dev/null
@@ -1,65 +0,0 @@
-/*
- * Copyright (C) 2024 Luke T. Shumaker <lukeshu@lukeshu.com>
- * SPDX-Licence-Identifier: AGPL-3.0-or-later
- */
-
-struct _cr_select_arg {
- enum _cr_select_op {
- _CR_SELECT_NONE,
- _CR_SELECT_RECV,
- _CR_SELECT_SEND,
- _CR_SELECT_DEFAULT,
- } op;
- struct _cr_chan *ch;
- struct _cr_chan_waiter self;
-};
-#define CR_SELECT_RECV(ch) ((struct _cr_select_arg){.op=_CR_SELECT_RECV, sizeof((ch)->vals[0]), ch,
-#define CR_SELECT_SEND(ch) _CR_SELECT_SEND, sizeof((ch)->vals[0]), ch,
-#define CR_SELECT_DEFAULT _CR_SELECT_DEFAULT,
-#define CR_SELECT(OPS) switch(_cr_chan_select(OPS _CR_SELECT_NONE))
-
-size_t _cr_chan_select(enum _cr_select_op a, ...) {
- restart:
- size_t blocking, nonblocking;
- bool have_default = false;
-
- va_list args;
- va_start(args, a);
- bool first = true;
- for (size_t i = 0; true; i++) {
- enum _cr_select_op op;
- if (first) {
- op = a;
- first = false;
- } else
- op = va_arg(args, enum _cr_select_op);
- if (op == _CR_SELECT_NONE)
- break;
- else if (op == _CR_SELECT_DEFAULT) {
- have_default = true;
- continue;
- }
- size_t sz;
- struct _cr_chan *ch;
- sz = va_arg(args, size_t);
- ch = va_arg(args, struct _cr_chan *);
- if (op == _CR_SELECT_RECV) {
- if (ch->waiters.front && ch->waiter_typ == _CH_CHAN_SENDER)
- nonblocking++;
- else
- blocking++;
- } else {
- if (ch->waiters.front && ch->waiter_typ == _CH_CHAN_RECVER)
- nonblocking++;
- else
- blocking++;
- }
- }
- va_end(args);
-
- random()
-
- if (nonblocking == 0 && !have_default) {
- goto restart;
- }
-}
diff --git a/libcr_ipc/include/libcr_ipc/chan.h b/libcr_ipc/include/libcr_ipc/chan.h
index 26e8a8d..0b45752 100644
--- a/libcr_ipc/include/libcr_ipc/chan.h
+++ b/libcr_ipc/include/libcr_ipc/chan.h
@@ -105,9 +105,12 @@ enum _cr_chan_waiter_typ {
};
struct _cr_chan_waiter {
- struct _cr_chan_waiter *rear;
+ struct _cr_chan_waiter *front, *rear;
cid_t cid;
void *val_ptr;
+ void (*dequeue)(void *, size_t);
+ void *dequeue_arg1;
+ size_t dequeue_arg2;
};
struct _cr_chan {
@@ -117,6 +120,11 @@ struct _cr_chan {
} waiters;
};
+static void _cr_chan_dequeue(void *_ch, size_t) {
+ struct _cr_chan *ch = _ch;
+ _cr_ipc_dll_pop_from_front(&ch->waiters);
+}
+
static inline void _cr_chan_xfer(enum _cr_chan_waiter_typ self_typ, struct _cr_chan *ch, void *val_ptr, size_t val_size) {
assert(ch);
assert(val_ptr);
@@ -127,31 +135,21 @@ static inline void _cr_chan_xfer(enum _cr_chan_waiter_typ self_typ, struct _cr_c
memcpy(ch->waiters.front->val_ptr, val_ptr, val_size);
else
memcpy(val_ptr, ch->waiters.front->val_ptr, val_size);
- /* Advance cpy_front and *maybe* unpause_front. */
cr_unpause(ch->waiters.front->cid);
- _cr_ipc_sll_pop_from_front(&ch->waiters);
+ ch->waiters.front->dequeue(ch->waiters.front->dequeue_arg1,
+ ch->waiters.front->dequeue_arg2);
cr_yield();
} else { /* blocking slow-path */
struct _cr_chan_waiter self = {
- .cid = cr_getcid(),
- .val_ptr = val_ptr,
+ .cid = cr_getcid(),
+ .val_ptr = val_ptr,
+ .dequeue = _cr_chan_dequeue,
+ .dequeue_arg1 = ch,
};
- _cr_ipc_sll_push_to_rear(&ch->waiters, &self);
+ _cr_ipc_dll_push_to_rear(&ch->waiters, &self);
ch->waiter_typ = self_typ;
cr_pause_and_yield();
}
}
-/* TODO: Implement CR_SELECT() (see `_TODO_select.h`).
- *
- * Changes required to what's here in chan.h:
- *
- * - Change the singly-linked-list to a doubly-linked-list (add
- * `*front` to _waiter, then replace `sll` with `ddl`).
- *
- * - Have the non-blocking fast-path not just call _pop_from_front()
- * on that channel's list, but _remove() on all selected channels'
- * lists.
- */
-
#endif /* _COROUTINE_CHAN_H_ */
diff --git a/libcr_ipc/include/libcr_ipc/select.h b/libcr_ipc/include/libcr_ipc/select.h
new file mode 100644
index 0000000..2af85a2
--- /dev/null
+++ b/libcr_ipc/include/libcr_ipc/select.h
@@ -0,0 +1,224 @@
+/* libcr_ipc/select.h - Select between channels
+ *
+ * Copyright (C) 2024 Luke T. Shumaker <lukeshu@lukeshu.com>
+ * SPDX-Licence-Identifier: AGPL-3.0-or-later
+ */
+
+#include <alloca.h> /* for alloca() */
+#include <assert.h> /* for assert() */
+#include <stdarg.h> /* for va_* */
+#include <stddef.h> /* for size_t */
+#include <stdlib.h> /* for random() */
+
+#include <libcr_ipc/chan.h>
+
+#ifndef _COROUTINE_SELECT_H_
+#define _COROUTINE_SELECT_H_
+
+/* arguments ******************************************************************/
+
+/**
+ * Do not populate cr_select_arg yourself; use the
+ * CR_SELECT_{RECV,SEND,DEFAULT} macros.
+ */
+struct cr_select_arg {
+ enum {
+ _CR_SELECT_OP_NONE,
+ _CR_SELECT_OP_RECV,
+ _CR_SELECT_OP_SEND,
+ _CR_SELECT_OP_DEFAULT,
+ } op;
+ struct _cr_chan *ch;
+ void *val_ptr;
+ size_t val_siz;
+};
+
+#define CR_SELECT_RECV(CH, VALP) ({ \
+ assert(CH); \
+ assert(VALP); \
+ /* The _valp indirection is to get the \
+ * compiler to check that the types are \
+ * compatible. */ \
+ typeof((CH)->vals[0]) *_valp = VALP; \
+ ((struct cr_select_arg){ \
+ .op = _CR_SELECT_OP_RECV, \
+ .ch = &((CH)->core), \
+ .val_ptr = _valp, \
+ .val_siz = sizeof((CH)->vals[0]), \
+ }); \
+ })
+#define CR_SELECT_SEND(CH, VAL) ({ \
+ assert(CH); \
+ typeof((CH)->vals[0]) val_lvalue = VAL; \
+ ((struct cr_select_arg){ \
+ .op = _CR_SELECT_OP_SEND, \
+ .ch = &((CH)->core), \
+ .val_ptr = &val_lvalue;, \
+ .val_siz = sizeof((CH)->vals[0]), \
+ }); \
+ })
+#define CR_SELECT_DEFAULT \
+ ((struct cr_select_arg){ \
+ .op = _CR_SELECT_OP_DEFAULT, \
+ })
+#define _CR_SELECT_END \
+ ((struct cr_select_arg){ \
+ .op = _CR_SELECT_OP_NONE, \
+ })
+
+/* cr_select_v(arg_cnt, arg_vec) **********************************************/
+
+static inline size_t _cr_select_pickone(size_t cnt) {
+ long fair_cnt = (0x80000000L / cnt) * cnt;
+ long rnd;
+ do {
+ rnd = random();
+ } while (rnd >= fair_cnt);
+ return rnd % cnt;
+}
+
+enum _cr_select_class {
+ _CR_SELECT_CLASS_DEFAULT,
+ _CR_SELECT_CLASS_BLOCKING,
+ _CR_SELECT_CLASS_NONBLOCK,
+};
+
+static inline enum _cr_select_class _cr_select_getclass(struct cr_select_arg arg) {
+ switch (arg.op) {
+ case _CR_SELECT_OP_RECV:
+ if (arg.ch->waiters.front && arg.ch->waiter_typ == _CR_CHAN_SENDER)
+ return _CR_SELECT_CLASS_NONBLOCK;
+ else
+ return _CR_SELECT_CLASS_BLOCKING;
+ case _CR_SELECT_OP_SEND:
+ if (arg.ch->waiters.front && arg.ch->waiter_typ == _CR_CHAN_RECVER)
+ return _CR_SELECT_CLASS_NONBLOCK;
+ else
+ return _CR_SELECT_CLASS_BLOCKING;
+ case _CR_SELECT_OP_DEFAULT:
+ return _CR_SELECT_CLASS_DEFAULT;
+ default:
+ __builtin_unreachable();
+ }
+}
+
+struct _cr_select_waiters {
+ size_t cnt;
+ struct cr_select_arg *args;
+ struct _cr_chan_waiter *nodes;
+};
+
+static void _cr_select_dequeue(void *_waiters, size_t idx) {
+ struct _cr_select_waiters *waiters = waiters;
+ for (size_t i = 0; i < waiters->cnt; i++)
+ _cr_ipc_dll_remove(&(waiters->args[i].ch->waiters),
+ &(waiters->nodes[i]));
+ waiters->cnt = idx;
+}
+
+static size_t cr_select_v(size_t arg_cnt, struct cr_select_arg arg_vec[]) {
+ size_t cnt_blocking = 0;
+ size_t cnt_nonblock = 0;
+ size_t cnt_default = 0;
+
+ assert(arg_cnt);
+ assert(arg_vec);
+
+ for (size_t i = 0; i < arg_cnt; i++) {
+ switch (_cr_select_getclass(arg_vec[i])) {
+ case _CR_SELECT_CLASS_BLOCKING:
+ cnt_blocking++;
+ break;
+ case _CR_SELECT_CLASS_NONBLOCK:
+ cnt_nonblock++;
+ break;
+ case _CR_SELECT_CLASS_DEFAULT:
+ cnt_default++;
+ break;
+ }
+ }
+
+ if (cnt_nonblock) {
+ size_t choice = _cr_select_pickone(cnt_nonblock);
+ for (size_t i = 0, seen = 0; i < arg_cnt; i++) {
+ if (_cr_select_getclass(arg_vec[i]) == _CR_SELECT_CLASS_NONBLOCK) {
+ if (seen == choice) {
+ _cr_chan_xfer(arg_vec[i].op == _CR_SELECT_OP_RECV
+ ? _CR_CHAN_RECVER
+ : _CR_CHAN_SENDER,
+ arg_vec[i].ch,
+ arg_vec[i].val_ptr,
+ arg_vec[i].val_siz);
+ return i;
+ }
+ seen++;
+ }
+ }
+ __builtin_unreachable();
+ }
+
+ if (cnt_default) {
+ for (size_t i = 0; i < arg_cnt; i++)
+ if (_cr_select_getclass(arg_vec[i]) == _CR_SELECT_CLASS_DEFAULT)
+ return i;
+ __builtin_unreachable();
+ }
+
+ struct _cr_select_waiters waiters = {
+ .cnt = arg_cnt,
+ .args = arg_vec,
+ .nodes = alloca(sizeof(struct _cr_chan_waiter) * arg_cnt),
+ };
+ for (size_t i = 0; i < arg_cnt; i++) {
+ waiters.nodes[i] = (struct _cr_chan_waiter){
+ .cid = cr_getcid(),
+ .val_ptr = arg_vec[i].val_ptr,
+ .dequeue = _cr_select_dequeue,
+ .dequeue_arg1 = &waiters,
+ .dequeue_arg2 = i,
+ };
+ _cr_ipc_dll_push_to_rear(&arg_vec[i].ch->waiters, &waiters.nodes[i]);
+ }
+ cr_pause_and_yield();
+ return waiters.cnt;
+}
+
+/* cr_select_l(arg1, arg2, arg3, ...) ******************************************/
+
+#define cr_select_l(...) _cr_selectl(__VA_ARGS__ __VA_OPT__(,) _CR_SELECT_END)
+static inline size_t _cr_select_l(struct cr_select_arg first_arg, ...) {
+ va_list list;
+
+ /* Pass 1: Count how many args we have. */
+ size_t arg_cnt = 0;
+ va_start(list, first_arg);
+ for (;;) {
+ struct cr_select_arg arg;
+ if (arg_cnt == 0)
+ arg = first_arg;
+ else
+ arg = va_arg(list, struct cr_select_arg);
+ if (arg.op == _CR_SELECT_OP_NONE)
+ break;
+ arg_cnt++;
+ }
+ va_end(list);
+
+ /* Pass 2: Copy the args to a simple vector on the stack. */
+ struct cr_select_arg *arg_vec = alloca(sizeof(struct cr_select_arg) * arg_cnt);
+ va_start(list, first_arg);
+ for (size_t i = 0; i < arg_cnt; i++) {
+ struct cr_select_arg arg;
+ if (i == 0)
+ arg = first_arg;
+ else
+ arg = va_arg(list, struct cr_select_arg);
+ arg_vec[i] = arg;
+ }
+ va_end(list);
+
+ /* Now pass that to cr_select_v() for the real work. */
+ return cr_select_v(arg_cnt, arg_vec);
+}
+
+#endif /* _COROUTINE_SELECT_H_ */
generated by cgit v1.2.3-2-g168b (git 2.25.1) at 2024-11-21 18:24:52 +0000