Samuel Thibault <[email protected]> writes:

> Hello,
>
> Thanks for this optimization, just some comments to make it a strict
> improvement.
>
> Donjuanplatinum, le mer. 30 sept. 2026 10:07:05 +0800, a ecrit:
>> The scheduler currently use lineary search.
>
> But it also uses a "low" value to avoid searching the whole array.
>
Hi Samuel,

Thanks for your review. I have attached the updated patch.

>From f87604ccc3659a457592905b282d9c064dd1d028 Mon Sep 17 00:00:00 2001
From: Donjuanplatinum <[email protected]>
Date: Tue, 17 Nov 2026 20:30:20 +0800
Subject: [PATCH] sched: use a bitmap to speed up run queue lookup

* kern/processor.c (pset_init, processor_init): Add bitmap init.
* kern/sched.h (NRQS_BITMAP_SIZE, run_queue, runq_setbit, runq_clrbit)
(runq_findbit): New functions and constant.
* kern/sched_prim.c (thread_select, rem_runq, choose_thread)
(choose_pset_thread, do_runq_scan): Use bitmap-based run queue lookup.
---
 kern/processor.c  |  10 +++-
 kern/sched.h      |  50 ++++++++++++++++
 kern/sched_prim.c | 146 +++++++++++++++++++++++++++++-----------------
 3 files changed, 152 insertions(+), 54 deletions(-)

diff --git a/kern/processor.c b/kern/processor.c
index 485eb51b..8bc60c0e 100644
--- a/kern/processor.c
+++ b/kern/processor.c
@@ -138,8 +138,11 @@ void pset_init(
 	int	i;
 
 	simple_lock_init(&pset->runq.lock);
-	pset->runq.low = 0;
+	pset->runq.low = NRQS;
 	pset->runq.count = 0;
+	for (i = 0; i < NRQS_BITMAP_SIZE; i++) {
+	    pset->runq.bitmap[i] = 0;
+	}
 	for (i = 0; i < NRQS; i++) {
 	    queue_init(&(pset->runq.runq[i]));
 	}
@@ -190,8 +193,11 @@ void processor_init(
 	int	i;
 
 	simple_lock_init(&pr->runq.lock);
-	pr->runq.low = 0;
+	pr->runq.low = NRQS;
 	pr->runq.count = 0;
+	for (i = 0; i < NRQS_BITMAP_SIZE; i++) {
+	    pr->runq.bitmap[i] = 0;
+	}
 	for (i = 0; i < NRQS; i++) {
 	    queue_init(&(pr->runq.runq[i]));
 	}
diff --git a/kern/sched.h b/kern/sched.h
index 1f33f018..b6193681 100644
--- a/kern/sched.h
+++ b/kern/sched.h
@@ -62,11 +62,17 @@
 #endif	/* STAT_TIME */
 #define NRQS	65			/* 65 run queues per cpu */
 
+/*
+ *      Bitmap size for priority tracking.
+ */
+#define NRQS_BITMAP_SIZE	((NRQS + (sizeof(unsigned long) * 8) - 1) / (sizeof(unsigned long) * 8))
+
 struct run_queue {
 	queue_head_t		runq[NRQS];	/* one for each priority */
 	decl_simple_lock_data(,	lock);		/* one lock for all queues,
 						   shall be taken at splsched
 						   only */
+	unsigned long		bitmap[NRQS_BITMAP_SIZE]; /* priority bitmap */
 	int			low;		/* low queue value */
 	int			count;		/* count of threads runable */
 };
@@ -158,6 +164,50 @@ struct shift {
 
 typedef	struct shift	*shift_t, shift_data_t;
 
+/*
+ *	Bitmap operations for run queue priority tracking.
+ */
+
+static inline void runq_setbit(unsigned long *bitmap, int pri)
+{
+  bitmap[pri / (sizeof(unsigned long) * 8)] |=
+    (1UL << (pri % (sizeof(unsigned long) * 8)));
+}
+
+static inline void runq_clrbit(unsigned long *bitmap, int pri)
+{
+  bitmap[pri / (sizeof(unsigned long) * 8)] &=
+    ~(1UL << (pri % (sizeof(unsigned long) * 8)));
+}
+
+static inline int runq_findbit(const unsigned long *bitmap, int low)
+{
+  int i;
+  unsigned long word;
+  const int bits_per_long = sizeof(unsigned long) * 8;
+
+  for (i = low / bits_per_long; i < NRQS_BITMAP_SIZE; i++) {
+    word = bitmap[i];
+
+    if (i == low / bits_per_long)
+      word &= ~0UL << (low % bits_per_long);
+
+    if (word != 0) {
+      int bit;
+#if defined(__GNUC__)
+      bit = __builtin_ctzl(word);
+#else
+      for (bit = 0; bit < (sizeof(unsigned long) * 8); bit++) {
+	if (word & (1UL << bit))
+	  break;
+      }
+#endif
+      return i * bits_per_long + bit;
+    }
+  }
+  return NRQS;
+}
+
 /*
  *	sched_tick increments once a second.  Used to age priorities.
  */
diff --git a/kern/sched_prim.c b/kern/sched_prim.c
index 8cf2ab27..f89b0c53 100644
--- a/kern/sched_prim.c
+++ b/kern/sched_prim.c
@@ -564,12 +564,13 @@ static thread_t thread_select(
 		}
 		else {
 			queue_t	q;
-
-			/*
-			 *	If there is a thread at hint, grab it,
-			 *	else call choose_pset_thread.
-			 */
-			q = pset->runq.runq + pset->runq.low;
+		        int pri;
+                        /*
+                         *	If there is a thread at hint, grab it,
+                         *	else call choose_pset_thread.
+                         */
+                        pri = pset->runq.low;
+			q = pset->runq.runq + pri;
 
 			if (queue_empty(q)) {
 				pset->runq.low++;
@@ -578,20 +579,27 @@ static thread_t thread_select(
 			else {
 				thread = (thread_t) dequeue_head(q);
 				thread->runq = RUN_QUEUE_NULL;
-				pset->runq.count--;
+                                pset->runq.count--;
+				if (queue_empty(q))
+				  runq_clrbit(pset->runq.bitmap, pri);
+
+				if (pset->runq.count == 0)
+				  {
+				    pset->runq.low = NRQS;
+				  }
 #if	MACH_FIXPRI
 				/*
 				 *	Cannot lazy evaluate pset->runq.low for
 				 *	fixed priority policy
 				 */
-				if ((pset->runq.count > 0) &&
-				    (pset->policies & POLICY_FIXEDPRI)) {
-					    while (queue_empty(q)) {
-						pset->runq.low++;
-						q++;
-					    }
+				else if (queue_empty(q) &&
+		     (pset->policies & POLICY_FIXEDPRI)) {
+				  pset->runq.low = runq_findbit(pset->runq.bitmap, pri + 1);
 				}
-#endif	/* MACH_FIXPRI */
+#endif /* MACH_FIXPRI */
+				else {
+			  pset->runq.low = pri;
+			}
 #if	DEBUG
 				checkrq(&pset->runq, "thread_select: after");
 #endif	/* DEBUG */
@@ -1198,6 +1206,7 @@ void update_priority(
 	    runq_lock(rq);	/* lock the run queue */	\
 	    checkrq((rq), "thread_setrun: before adding thread");	\
 	    enqueue_tail(&(rq)->runq[whichq], &((th)->links));		\
+	    runq_setbit((rq)->bitmap, whichq);				\
 									\
 	    if (whichq < (rq)->low || (rq)->count == 0) 		\
 		 (rq)->low = whichq;	/* minimize */			\
@@ -1221,6 +1230,7 @@ void update_priority(
 									\
 	    runq_lock(rq);	/* lock the run queue */	\
 	    enqueue_tail(&(rq)->runq[whichq], &((th)->links));		\
+	    runq_setbit((rq)->bitmap, whichq);				\
 									\
 	    if (whichq < (rq)->low || (rq)->count == 0) 		\
 		 (rq)->low = whichq;	/* minimize */			\
@@ -1454,6 +1464,7 @@ struct run_queue *rem_runq(
 		checkrq(rq, "rem_runq: at entry");
 #endif	/* DEBUG */
 		if (rq == th->runq) {
+			int pri;
 			/*
 			 *	Thread is in a runq and we have a lock on
 			 *	that runq.
@@ -1462,8 +1473,16 @@ struct run_queue *rem_runq(
 			checkrq(rq, "rem_runq: before removing thread");
 			thread_check(th, rq);
 #endif	/* DEBUG */
+			pri = th->sched_pri;
 			remqueue(&rq->runq[0], (queue_entry_t) th);
 			rq->count--;
+			if (queue_empty(&rq->runq[pri])) {
+				runq_clrbit(rq->bitmap, pri);
+                        }
+			if (runq->count == 0)
+			  {
+			    runq->low = NRQS;
+			  }
 #if	DEBUG
 			checkrq(rq, "rem_runq: after removing thread");
 #endif	/* DEBUG */
@@ -1515,19 +1534,29 @@ thread_t choose_thread(
 
 	simple_lock(&runq->lock);
 	if (runq->count > 0) {
-	    q = runq->runq + runq->low;
-	    for (i = runq->low; i < NRQS ; i++, q++) {
-		if (!queue_empty(q)) {
-		    th = (thread_t) dequeue_head(q);
-		    th->runq = RUN_QUEUE_NULL;
-		    runq->count--;
-		    runq->low = i;
-		    simple_unlock(&runq->lock);
-		    return th;
-		}
+	  i = runq_findbit(runq->bitmap, runq->low);
+	    if (i >= NRQS) {
+		panic("choose_thread: bitmap/count mismatch");
+	    }
+	    q = runq->runq + i;
+	    if (queue_empty(q)) {
+		panic("choose_thread: bitmap points to empty queue");
+	    }
+	    th = (thread_t) dequeue_head(q);
+	    th->runq = RUN_QUEUE_NULL;
+	    runq->count--;
+
+	    if (queue_empty(q)) {
+		runq_clrbit(runq->bitmap, i);
+		if (runq->count > 0)
+		    runq->low = runq_findbit(runq->bitmap, i + 1);
+		else
+		    runq->low = NRQS;
+	    } else {
+		runq->low = i;
 	    }
-	    panic("choose_thread");
-	    /*NOTREACHED*/
+	    simple_unlock(&runq->lock);
+	    return th;
 	}
 	simple_unlock(&runq->lock);
 
@@ -1561,35 +1590,42 @@ thread_t choose_pset_thread(
 	runq = &pset->runq;
 
 	if (runq->count > 0) {
-	    q = runq->runq + runq->low;
-	    for (i = runq->low; i < NRQS ; i++, q++) {
-		if (!queue_empty(q)) {
-		    th = (thread_t) dequeue_head(q);
-		    th->runq = RUN_QUEUE_NULL;
-		    runq->count--;
-		    /*
-		     *	For POLICY_FIXEDPRI, runq->low must be
-		     *	accurate!
-		     */
+	    i = runq_findbit(runq->bitmap, runq->low);
+	    if (i >= NRQS) {
+		panic("choose_pset_thread: bitmap/count mismatch");
+	    }
+	    q = runq->runq + i;
+	    if (queue_empty(q)) {
+		panic("choose_pset_thread: bitmap points to empty queue");
+	    }
+	    th = (thread_t) dequeue_head(q);
+	    th->runq = RUN_QUEUE_NULL;
+	    runq->count--;
+	    if (queue_empty(q))
+		runq_clrbit(runq->bitmap, i);
+
+	    if (runq->count == 0)
+	    {
+		runq->low = NRQS;
+            }
+            /*
+	     *	For POLICY_FIXEDPRI, runq->low must be
+	     *	accurate!
+	     */
 #if	MACH_FIXPRI
-		    if ((runq->count > 0) &&
-			(pset->policies & POLICY_FIXEDPRI)) {
-			    while (queue_empty(q)) {
-				q++;
-				i++;
-			    }
-		    }
+	    else if (queue_empty(q) &&
+		     (pset->policies & POLICY_FIXEDPRI)) {
+		runq->low = runq_findbit(runq->bitmap, i + 1);
+	    }
 #endif	/* MACH_FIXPRI */
-		    runq->low = i;
+	    else {
+		runq->low = i;
+	    }
 #if	DEBUG
-		    checkrq(runq, "choose_pset_thread");
+	  checkrq(runq, "choose_pset_thread");
 #endif	/* DEBUG */
-		    simple_unlock(&runq->lock);
-		    return th;
-		}
-	    }
-	    panic("choose_pset_thread");
-	    /*NOTREACHED*/
+	    simple_unlock(&runq->lock);
+	    return th;
 	}
 	simple_unlock(&runq->lock);
 
@@ -1936,10 +1972,16 @@ do_runq_scan(
 			     *	see it.  So we remove the thread
 			     *	from the runq to make it safe.
 			     */
-			    remqueue(q, (queue_entry_t) thread);
+                            remqueue(q, (queue_entry_t)thread);
 			    runq->count--;
 			    thread->runq = RUN_QUEUE_NULL;
+		            if (queue_empty(q))
+                              runq_clrbit(runq->bitmap, q - runq->runq);
 
+                            if (runq->count == 0)
+			      {
+				runq->low = NRQS;
+			      }
 			    stuck_threads[stuck_count++] = thread;
 if (do_thread_scan_debug)
     printf("do_runq_scan: adding thread %p\n", thread);
-- 
2.56.0

-- 
Donjuanplatinum, Yifei Yao <[email protected]>
GPG: 1C9E EEE5 4C8E D5A8 3039  1C87 A9F6 8632 D259 40E6
满堂兮美人 忽独与余兮目成

Reply via email to