1 files changed, 95 insertions, 0 deletions
diff --git a/libcr_ipc/sema.c b/libcr_ipc/sema.c
new file mode 100644
index 0000000..a8b5ec4
--- /dev/null
+++ b/libcr_ipc/sema.c
@@ -0,0 +1,95 @@
+/* coroutine_sema.h - Simple semaphores for coroutine.{h,c}
+ *
+ * Copyright (C) 2024  Luke T. Shumaker <lukeshu@lukeshu.com>
+ * SPDX-Licence-Identifier: AGPL-3.0-or-later
+ */
+
+#include <assert.h>
+
+#include "coroutine_sema.h"
+
+struct cid_list {
+	cid_t                    val;
+	struct cid_list         *next;
+};
+
+/* head->next->next->tail */
+
+struct _cr_sema {
+	int              cnt;
+
+	struct cid_list  *head, **tail;
+	/* locked indicates that a call from within a coroutine is is
+	 * messing with ->{head,tail}, so a signal handler can't read
+	 * it.  */
+	bool             locked;
+};
+
+/** Drain the sema->{head,tail} list.  Returns true if cr_getcid() was drained.  */
+static inline bool drain(volatile cr_sema_t *sema) {
+	assert(!sema->locked);
+	cid_t self = cr_getcid();
+
+	enum drain_result {
+		DRAINING,
+		DRAINED_SELF, /* stopped because drained `self` */
+		DRAINED_ALL,  /* stopped because sema->head == NULL */
+		DRAINED_SOME, /* stopped because sema->cnt == 0 */
+	} state = DRAINING;
+	do { 
+		sema->locked = true;
+		while (state == DRAINING) {
+			if (!sema->head) {
+				state = DRAINED_ALL;
+			} else if (!sema->cnt) {
+				state = DRAINED_SOME;
+			} else {
+				sema->cnt--;
+				cid_t cid = sema->head->val;
+				if (cid == self)
+					state = DRAINED_SELF;
+				else
+					cr_unpause(sema->head->val);
+				sema->head = sema->head->next;
+				if (!sema->head)
+					sema->tail = &sema->head;
+			}
+		}
+		sema->locked = false;
+		/* If there are still coroutines in sema->head, check
+		 * that sema->cnt wasn't incremented between `if
+		 * (!sema->cnt)` and `sema->locked = false`.  */
+	} while (state == DRAINED_SOME && cnt);
+	/* If state == DRAINED_SELF, then we better have been the last
+	 * item in the list!  */
+	assert(state != DRAINED_SELF || !sema->head);
+	return state == DRAINED_SELF;
+}
+
+void cr_sema_signal(volatile cr_sema_t *sema) {
+	sema->cnt++;
+	if (!sema->locked)
+		drain();
+}
+
+void cr_sema_wait(volatile cr_sema_t *sema) {
+	struct cid_list self = {
+		.val = cr_getcid(),
+		.next = NULL,
+	};
+
+	sema->locked = true;
+	if (!sema->tail)
+		sema->head = &self;
+	else
+		*(sema->tail) = &self;
+	sema->tail = &(self.next);
+	sema->locked = false;
+
+	if (drain())
+		/* DRAINED_SELF: (1) No need to pause+yield, (2) we
+		 * better have been the last item in the list!  */
+		assert(!self.next);
+	else
+		cr_pause_and_yield();
+}