kernel: O(1) ReqQueue insertions

2 files changed, 13 insertions, 15 deletions

diff --git a/src/kernel/vfs/request.c b/src/kernel/vfs/request.c
index 58e2987..8a80f04 100644
--- a/src/kernel/vfs/request.c
+++ b/src/kernel/vfs/request.c
@@ -237,19 +237,17 @@ void
 reqqueue_init(ReqQueue *q)
 {
 	q->head = NULL;
+	q->slot = &q->head;
 }
 
 void
 reqqueue_join(ReqQueue *q, VfsReq *req)
 {
-	if (req->reqqueue_next)
-		panic_invalid_state();
-
-	VfsReq **it = &q->head;
-	while (*it != NULL) {
-		it = &(*it)->reqqueue_next;
-	}
-	*it = req;
+	assert(req->reqqueue_next == NULL);
+	assert(q->slot != NULL);
+	assert(*q->slot == NULL);
+	*q->slot = req;
+	q->slot = &req->reqqueue_next;
 }
 
 VfsReq *
@@ -259,6 +257,9 @@ reqqueue_pop(ReqQueue *q)
 	if (req) {
 		q->head = req->reqqueue_next;
 		req->reqqueue_next = NULL;
+		if (q->slot == &req->reqqueue_next) {
+			q->slot = &q->head;
+		}
 	}
 	return req;
 }
@@ -266,23 +267,19 @@ reqqueue_pop(ReqQueue *q)
 void
 reqqueue_ringreadall(ReqQueue *q, ring_t *r)
 {
-	VfsReq **queue = &q->head; /* whatever */
 	VfsReq *req;
 	char tmp[64];
 	size_t mlen = 0;
 	if (ring_used(r) == 0) return;
 
 	/* read as much as the biggest request wants */
-	for (req = *queue; req; req = req->reqqueue_next)
+	for (req = q->head; req; req = req->reqqueue_next) {
 		mlen = max(mlen, req->output.len);
+	}
 	mlen = min(mlen, sizeof tmp);
 	mlen = ring_get(r, tmp, mlen);
 
-	while (*queue) {
-		req = *queue;
-		*queue = req->reqqueue_next;
-		req->reqqueue_next = NULL;
-
+	while ((req = reqqueue_pop(q))) {
 		size_t ret = min(mlen, req->output.len);
 		assert(req->type == VFSOP_READ);
 		if (req->caller) {
diff --git a/src/kernel/vfs/request.h b/src/kernel/vfs/request.h
index 6786e72..45ec687 100644
--- a/src/kernel/vfs/request.h
+++ b/src/kernel/vfs/request.h
@@ -6,6 +6,7 @@
 
 struct ReqQueue {
 	VfsReq *head;
+	VfsReq **slot; /* points to the place where new entries should be placed */
 };
 
 struct VfsBackend {