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.
> +static inline int runq_findbit(const unsigned long *bitmap)
You could add a "low" parameter here.
> +{
> + int i;
> + unsigned long word;
> +
> + for (i = 0; i < NRQS_BITMAP_SIZE; i++) {
> + word = bitmap[i];
> + 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 * (sizeof(unsigned long) * 8) + 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 c1b809be..5cb0ac50 100644
> --- a/kern/sched_prim.c
> +++ b/kern/sched_prim.c
> @@ -1198,6 +1198,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 +1222,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 +1456,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 +1465,12 @@ 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 DEBUG
> checkrq(rq, "rem_runq: after removing thread");
> #endif /* DEBUG */
> @@ -1515,19 +1522,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--;
> + i = runq_findbit(runq->bitmap);
And you can pass runq->low to runq_findbit.
> + 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);
And here pass i+1.
> + else
> runq->low = i;
? If the runq is empty, better set low to NRQS, so the next time a
thread is queued, low will be set to its priority.
> - simple_unlock(&runq->lock);
> - return th;
> - }
> + } else {
> + runq->low = i;
> }
> - panic("choose_thread");
> - /*NOTREACHED*/
> + simple_unlock(&runq->lock);
> + return th;
> }
> simple_unlock(&runq->lock);
>
> @@ -1561,35 +1578,34 @@ thread_t choose_pset_thread(
And same in this function.
> 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);
> + 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 MACH_FIXPRI
> - if ((runq->count > 0) &&
> - (pset->policies & POLICY_FIXEDPRI)) {
> - while (queue_empty(q)) {
> - q++;
> - i++;
> - }
> - }
> + if ((runq->count > 0) &&
> + (pset->policies & POLICY_FIXEDPRI)) {
> + runq->low = runq_findbit(runq->bitmap);
> + } else
> #endif /* MACH_FIXPRI */
> - runq->low = i;
> + {
> + 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);
>
> --
> 2.55.0
>