Hello,
Donjuanplatinum, le mar. 17 nov. 2026 20:33:47 +0800, a ecrit:
> +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);
I don't think it is worth it: the for loop below goes through all bits
anyway, so masking out bits below low will not help it.
> +
> + 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
Please also update the low value, like the existing code in the caller
does. You can for instance make low an int* so the function can update
it.
> + 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;
Please avoid changing between tabs and spaces. Even if the existing code
might mix some, better stick to what is around the parts that you
change.
> + 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--;
Notably here it's really a spurious change :)
> + if (queue_empty(q))
> + runq_clrbit(pset->runq.bitmap, pri);
I would say put this before the runq.count--, so the runq.count-- is
next to the test for becoming 0.
> +
> + 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);
> + }
Same here, better put it before rq->count--.
> + 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);
I don't think it is worth calling runq_findbit here only to update
runq->low: next time we look for a thread, we will call it anyway. And
possibly in between some thread with lower prio will have been queued,
so having called runq_findbit will have been useless.
You can however set runq->low to 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);
And similarly.
> + }
> #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
> 满堂兮美人 忽独与余兮目成