libcr_ipc: select.h

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_ */