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
> 满堂兮美人 忽独与余兮目成


Reply via email to