From fb7949549435e735acef3674b10f429fa4c4789e Mon Sep 17 00:00:00 2001
From: dzwdz
Date: Sun, 14 Jul 2024 23:20:35 +0200
Subject: kernel: new queue abstraction

The postqueue functions remain as-is, as that's a more "specialized" interface.
They're mostly wrappers around queue.h, though.
---
 man/queue.9              | 43 +++++++++++++++++++++++++++++++++++++++++++
 src/kernel/queue.h       | 37 +++++++++++++++++++++++++++++++++++++
 src/kernel/vfs/request.c | 20 ++++----------------
 3 files changed, 84 insertions(+), 16 deletions(-)
 create mode 100644 man/queue.9
 create mode 100644 src/kernel/queue.h

diff --git a/man/queue.9 b/man/queue.9
new file mode 100644
index 0000000..d53adf8
--- /dev/null
+++ b/man/queue.9
@@ -0,0 +1,43 @@
+.Dd July 14, 2024
+.Dt QUEUE 9
+.Os Camellia
+.Sh NAME
+.Nm QUEUE_INIT ,
+.Nm QUEUE_APPEND ,
+.Nm QUEUE_POP
+.Nd macros for intrusive linked lists
+.Sh SYNOPSIS
+.In kernel/queue.h
+.Bd -literal
+struct YourNode {
+	...
+	struct YourNode *NAME_next;
+};
+struct YourHead {
+	struct YourNode *head, **slot;
+};
+.Ed
+.Fn QUEUE_INIT "YourHead *q"
+.Fn QUEUE_APPEND "YourHead *q" "NAME" "YourNode *el"
+.Ft YourNode *
+.Fn QUEUE_POP "YourHead *q" "NAME"
+.Sh DESCRIPTION
+These macros, inspired by BSD's
+.In sys/queue.h ,
+operate on intrusive linked lists.
+Currently, only
+.Em queues
+\(em singly-linked lists with O(1) insertions at the end \(em
+are supported.
+.Pp
+The linked list internals are intentionally exposed, as they're also meant
+to be used by e.g. memory management code for integrity checks.
+It's fine to modify them directly.
+.Sh RATIONALE
+The macros are a bit ugly, but they prevent code duplication,
+and using the same implementation everywhere probably makes bugs less likely.
+.Pp
+I've considered just using
+.In sys/queue.h ,
+which has the benefit of being more familiar to other programmers,
+but I dislike how it hides the list internals from the programmer.
diff --git a/src/kernel/queue.h b/src/kernel/queue.h
new file mode 100644
index 0000000..896824f
--- /dev/null
+++ b/src/kernel/queue.h
@@ -0,0 +1,37 @@
+/* documented in queue(9) */
+#include <kernel/panic.h>
+
+/* struct QueueNode {
+ *   ...
+ *   struct QueueNode *name_next;
+ *   ...
+ * }
+ * struct QueueHead {
+ *   struct QueueNode *head, **slot;
+ * }
+ */
+
+#define QUEUE_INIT(q) do { \
+	(q)->head = NULL; \
+	(q)->slot = &(q)->head; \
+} while(0)
+
+#define QUEUE_APPEND(q, name, el) do { \
+	assert((el)->name##_next == NULL); \
+	assert((q)->slot != NULL); \
+	assert(*(q)->slot == NULL); \
+	*(q)->slot = (el); \
+	(q)->slot = &(el)->name##_next; \
+} while(0)
+
+#define QUEUE_POP(q, name) ({ \
+	typeof((q)->head) __q_el = (q)->head; \
+	if (__q_el) { \
+		(q)->head = __q_el->name##_next; \
+		__q_el->name##_next = NULL; \
+		if ((q)->slot == &__q_el->name##_next) { \
+			(q)->slot = &(q)->head; \
+		} \
+	} \
+	__q_el; \
+})
diff --git a/src/kernel/vfs/request.c b/src/kernel/vfs/request.c
index 8a80f04..8e6f14a 100644
--- a/src/kernel/vfs/request.c
+++ b/src/kernel/vfs/request.c
@@ -3,6 +3,7 @@
 #include <kernel/malloc.h>
 #include <kernel/panic.h>
 #include <kernel/proc.h>
+#include <kernel/queue.h>
 #include <kernel/vfs/request.h>
 #include <shared/mem.h>
 
@@ -236,32 +237,19 @@ vfsback_provdown(VfsBackend *b)
 void
 reqqueue_init(ReqQueue *q)
 {
-	q->head = NULL;
-	q->slot = &q->head;
+	QUEUE_INIT(q);
 }
 
 void
 reqqueue_join(ReqQueue *q, VfsReq *req)
 {
-	assert(req->reqqueue_next == NULL);
-	assert(q->slot != NULL);
-	assert(*q->slot == NULL);
-	*q->slot = req;
-	q->slot = &req->reqqueue_next;
+	QUEUE_APPEND(q, reqqueue, req);
 }
 
 VfsReq *
 reqqueue_pop(ReqQueue *q)
 {
-	VfsReq *req = q->head;
-	if (req) {
-		q->head = req->reqqueue_next;
-		req->reqqueue_next = NULL;
-		if (q->slot == &req->reqqueue_next) {
-			q->slot = &q->head;
-		}
-	}
-	return req;
+	return QUEUE_POP(q, reqqueue);
 }
 
 void
-- 
cgit v1.2.3