Ignore:
File:
1 edited

Legend:

Unmodified
Added
Removed

  • kernel/generic/src/proc/scheduler.c

    rd23712e r583c2a3  
    11/*
    22 * Copyright (c) 2010 Jakub Jermar
    3  * Copyright (c) 2023 Jiří Zárevúcky
    43 * All rights reserved.
    54 *
    … …  
    5150#include <time/delay.h>
    5251#include <arch/asm.h>
     52#include <arch/faddr.h>
    5353#include <arch/cycle.h>
    5454#include <atomic.h>
    … …  
    6666#include <stacktrace.h>
    6767
    68 atomic_size_t nrdy;  /**< Number of ready threads in the system. */
     68static void scheduler_separated_stack(void);
     69
     70atomic_t nrdy;  /**< Number of ready threads in the system. */
     71
     72/** Carry out actions before new task runs. */
     73static void before_task_runs(void)
     74{
     75        before_task_runs_arch();
     76}
     77
     78/** Take actions before new thread runs.
     79 *
     80 * Perform actions that need to be
     81 * taken before the newly selected
     82 * thread is passed control.
     83 *
     84 * THREAD->lock is locked on entry
     85 *
     86 */
     87static void before_thread_runs(void)
     88{
     89        before_thread_runs_arch();
     90
     91#ifdef CONFIG_FPU_LAZY
     92        if (THREAD == CPU->fpu_owner)
     93                fpu_enable();
     94        else
     95                fpu_disable();
     96#elif defined CONFIG_FPU
     97        fpu_enable();
     98        if (THREAD->fpu_context_exists)
     99                fpu_context_restore(THREAD->saved_fpu_context);
     100        else {
     101                fpu_init();
     102                THREAD->fpu_context_exists = true;
     103        }
     104#endif
     105
     106#ifdef CONFIG_UDEBUG
     107        if (THREAD->btrace) {
     108                istate_t *istate = THREAD->udebug.uspace_state;
     109                if (istate != NULL) {
     110                        printf("Thread %" PRIu64 " stack trace:\n", THREAD->tid);
     111                        stack_trace_istate(istate);
     112                }
     113
     114                THREAD->btrace = false;
     115        }
     116#endif
     117}
     118
     119/** Take actions after THREAD had run.
     120 *
     121 * Perform actions that need to be
     122 * taken after the running thread
     123 * had been preempted by the scheduler.
     124 *
     125 * THREAD->lock is locked on entry
     126 *
     127 */
     128static void after_thread_ran(void)
     129{
     130        after_thread_ran_arch();
     131}
    69132
    70133#ifdef CONFIG_FPU_LAZY
    … …  
    72135{
    73136        fpu_enable();
    74 
    75         /* We need this lock to ensure synchronization with thread destructor. */
    76         irq_spinlock_lock(&CPU->fpu_lock, false);
     137        irq_spinlock_lock(&CPU->lock, false);
    77138
    78139        /* Save old context */
    79         thread_t *owner = atomic_load_explicit(&CPU->fpu_owner, memory_order_relaxed);
    80         if (owner != NULL) {
    81                 fpu_context_save(&owner->fpu_context);
    82                 atomic_store_explicit(&CPU->fpu_owner, NULL, memory_order_relaxed);
    83         }
    84 
    85         irq_spinlock_unlock(&CPU->fpu_lock, false);
    86 
     140        if (CPU->fpu_owner != NULL) {
     141                irq_spinlock_lock(&CPU->fpu_owner->lock, false);
     142                fpu_context_save(CPU->fpu_owner->saved_fpu_context);
     143
     144                /* Don't prevent migration */
     145                CPU->fpu_owner->fpu_context_engaged = false;
     146                irq_spinlock_unlock(&CPU->fpu_owner->lock, false);
     147                CPU->fpu_owner = NULL;
     148        }
     149
     150        irq_spinlock_lock(&THREAD->lock, false);
    87151        if (THREAD->fpu_context_exists) {
    88                 fpu_context_restore(&THREAD->fpu_context);
     152                fpu_context_restore(THREAD->saved_fpu_context);
    89153        } else {
    90154                fpu_init();
    … …  
    92156        }
    93157
    94         atomic_store_explicit(&CPU->fpu_owner, THREAD, memory_order_relaxed);
     158        CPU->fpu_owner = THREAD;
     159        THREAD->fpu_context_engaged = true;
     160        irq_spinlock_unlock(&THREAD->lock, false);
     161
     162        irq_spinlock_unlock(&CPU->lock, false);
    95163}
    96164#endif /* CONFIG_FPU_LAZY */
    … …  
    114182 *
    115183 */
    116 static thread_t *try_find_thread(int *rq_index)
    117 {
    118         assert(interrupts_disabled());
     184static thread_t *find_best_thread(void)
     185{
    119186        assert(CPU != NULL);
    120187
    121         if (atomic_load(&CPU->nrdy) == 0)
    122                 return NULL;
    123 
    124         for (int i = 0; i < RQ_COUNT; i++) {
     188loop:
     189
     190        if (atomic_load(&CPU->nrdy) == 0) {
     191                /*
     192                 * For there was nothing to run, the CPU goes to sleep
     193                 * until a hardware interrupt or an IPI comes.
     194                 * This improves energy saving and hyperthreading.
     195                 */
     196                irq_spinlock_lock(&CPU->lock, false);
     197                CPU->idle = true;
     198                irq_spinlock_unlock(&CPU->lock, false);
     199                interrupts_enable();
     200
     201                /*
     202                 * An interrupt might occur right now and wake up a thread.
     203                 * In such case, the CPU will continue to go to sleep
     204                 * even though there is a runnable thread.
     205                 */
     206                cpu_sleep();
     207                interrupts_disable();
     208                goto loop;
     209        }
     210
     211        assert(!CPU->idle);
     212
     213        unsigned int i;
     214        for (i = 0; i < RQ_COUNT; i++) {
    125215                irq_spinlock_lock(&(CPU->rq[i].lock), false);
    126216                if (CPU->rq[i].n == 0) {
    … …  
    143233                list_remove(&thread->rq_link);
    144234
    145                 irq_spinlock_unlock(&(CPU->rq[i].lock), false);
    146 
    147                 *rq_index = i;
     235                irq_spinlock_pass(&(CPU->rq[i].lock), &thread->lock);
     236
     237                thread->cpu = CPU;
     238                thread->ticks = us2ticks((i + 1) * 10000);
     239                thread->priority = i;  /* Correct rq index */
     240
     241                /*
     242                 * Clear the stolen flag so that it can be migrated
     243                 * when load balancing needs emerge.
     244                 */
     245                thread->stolen = false;
     246                irq_spinlock_unlock(&thread->lock, false);
     247
    148248                return thread;
    149249        }
    150250
    151         return NULL;
    152 }
    153 
    154 /** Get thread to be scheduled
    155  *
    156  * Get the optimal thread to be scheduled
    157  * according to thread accounting and scheduler
    158  * policy.
    159  *
    160  * @return Thread to be scheduled.
    161  *
    162  */
    163 static thread_t *find_best_thread(int *rq_index)
    164 {
    165         assert(interrupts_disabled());
    166         assert(CPU != NULL);
    167 
    168         while (true) {
    169                 thread_t *thread = try_find_thread(rq_index);
    170 
    171                 if (thread != NULL)
    172                         return thread;
    173 
    174                 /*
    175                  * For there was nothing to run, the CPU goes to sleep
    176                  * until a hardware interrupt or an IPI comes.
    177                  * This improves energy saving and hyperthreading.
    178                  */
    179                 CPU_LOCAL->idle = true;
    180 
    181                 /*
    182                  * Go to sleep with interrupts enabled.
    183                  * Ideally, this should be atomic, but this is not guaranteed on
    184                  * all platforms yet, so it is possible we will go sleep when
    185                  * a thread has just become available.
    186                  */
    187                 cpu_interruptible_sleep();
    188         }
    189 }
    190 
    191 static void switch_task(task_t *task)
    192 {
    193         /* If the task stays the same, a lot of work is avoided. */
    194         if (TASK == task)
    195                 return;
    196 
    197         as_t *old_as = AS;
    198         as_t *new_as = task->as;
    199 
    200         /* It is possible for two tasks to share one address space. */
    201         if (old_as != new_as)
    202                 as_switch(old_as, new_as);
    203 
    204         if (TASK)
    205                 task_release(TASK);
    206 
    207         TASK = task;
    208 
    209         task_hold(TASK);
    210 
    211         before_task_runs_arch();
     251        goto loop;
    212252}
    213253
    … …  
    225265static void relink_rq(int start)
    226266{
     267        list_t list;
     268
     269        list_initialize(&list);
     270        irq_spinlock_lock(&CPU->lock, false);
     271
     272        if (CPU->needs_relink > NEEDS_RELINK_MAX) {
     273                int i;
     274                for (i = start; i < RQ_COUNT - 1; i++) {
     275                        /* Remember and empty rq[i + 1] */
     276
     277                        irq_spinlock_lock(&CPU->rq[i + 1].lock, false);
     278                        list_concat(&list, &CPU->rq[i + 1].rq);
     279                        size_t n = CPU->rq[i + 1].n;
     280                        CPU->rq[i + 1].n = 0;
     281                        irq_spinlock_unlock(&CPU->rq[i + 1].lock, false);
     282
     283                        /* Append rq[i + 1] to rq[i] */
     284
     285                        irq_spinlock_lock(&CPU->rq[i].lock, false);
     286                        list_concat(&CPU->rq[i].rq, &list);
     287                        CPU->rq[i].n += n;
     288                        irq_spinlock_unlock(&CPU->rq[i].lock, false);
     289                }
     290
     291                CPU->needs_relink = 0;
     292        }
     293
     294        irq_spinlock_unlock(&CPU->lock, false);
     295}
     296
     297/** The scheduler
     298 *
     299 * The thread scheduling procedure.
     300 * Passes control directly to
     301 * scheduler_separated_stack().
     302 *
     303 */
     304void scheduler(void)
     305{
     306        volatile ipl_t ipl;
     307
     308        assert(CPU != NULL);
     309
     310        ipl = interrupts_disable();
     311
     312        if (atomic_load(&haltstate))
     313                halt();
     314
     315        if (THREAD) {
     316                irq_spinlock_lock(&THREAD->lock, false);
     317
     318                /* Update thread kernel accounting */
     319                THREAD->kcycles += get_cycle() - THREAD->last_cycle;
     320
     321#if (defined CONFIG_FPU) && (!defined CONFIG_FPU_LAZY)
     322                fpu_context_save(THREAD->saved_fpu_context);
     323#endif
     324                if (!context_save(&THREAD->saved_context)) {
     325                        /*
     326                         * This is the place where threads leave scheduler();
     327                         */
     328
     329                        /* Save current CPU cycle */
     330                        THREAD->last_cycle = get_cycle();
     331
     332                        irq_spinlock_unlock(&THREAD->lock, false);
     333                        interrupts_restore(THREAD->saved_context.ipl);
     334
     335                        return;
     336                }
     337
     338                /*
     339                 * Interrupt priority level of preempted thread is recorded
     340                 * here to facilitate scheduler() invocations from
     341                 * interrupts_disable()'d code (e.g. waitq_sleep_timeout()).
     342                 *
     343                 */
     344                THREAD->saved_context.ipl = ipl;
     345        }
     346
     347        /*
     348         * Through the 'CURRENT' structure, we keep track of THREAD, TASK, CPU, AS
     349         * and preemption counter. At this point CURRENT could be coming either
     350         * from THREAD's or CPU's stack.
     351         *
     352         */
     353        current_copy(CURRENT, (current_t *) CPU->stack);
     354
     355        /*
     356         * We may not keep the old stack.
     357         * Reason: If we kept the old stack and got blocked, for instance, in
     358         * find_best_thread(), the old thread could get rescheduled by another
     359         * CPU and overwrite the part of its own stack that was also used by
     360         * the scheduler on this CPU.
     361         *
     362         * Moreover, we have to bypass the compiler-generated POP sequence
     363         * which is fooled by SP being set to the very top of the stack.
     364         * Therefore the scheduler() function continues in
     365         * scheduler_separated_stack().
     366         *
     367         */
     368        context_save(&CPU->saved_context);
     369        context_set(&CPU->saved_context, FADDR(scheduler_separated_stack),
     370            (uintptr_t) CPU->stack, STACK_SIZE);
     371        context_restore(&CPU->saved_context);
     372
     373        /* Not reached */
     374}
     375
     376/** Scheduler stack switch wrapper
     377 *
     378 * Second part of the scheduler() function
     379 * using new stack. Handling the actual context
     380 * switch to a new thread.
     381 *
     382 */
     383void scheduler_separated_stack(void)
     384{
     385        DEADLOCK_PROBE_INIT(p_joinwq);
     386        task_t *old_task = TASK;
     387        as_t *old_as = AS;
     388
     389        assert((!THREAD) || (irq_spinlock_locked(&THREAD->lock)));
     390        assert(CPU != NULL);
    227391        assert(interrupts_disabled());
    228392
    229         if (CPU_LOCAL->current_clock_tick < CPU_LOCAL->relink_deadline)
    230                 return;
    231 
    232         CPU_LOCAL->relink_deadline = CPU_LOCAL->current_clock_tick + NEEDS_RELINK_MAX;
    233 
    234         /* Temporary cache for lists we are moving. */
    235         list_t list;
    236         list_initialize(&list);
    237 
    238         size_t n = 0;
    239 
    240         /* Move every list (except the one with highest priority) one level up. */
    241         for (int i = RQ_COUNT - 1; i > start; i--) {
    242                 irq_spinlock_lock(&CPU->rq[i].lock, false);
    243 
    244                 /* Swap lists. */
    245                 list_swap(&CPU->rq[i].rq, &list);
    246 
    247                 /* Swap number of items. */
    248                 size_t tmpn = CPU->rq[i].n;
    249                 CPU->rq[i].n = n;
    250                 n = tmpn;
    251 
    252                 irq_spinlock_unlock(&CPU->rq[i].lock, false);
    253         }
    254 
    255         /* Append the contents of rq[start + 1]  to rq[start]. */
    256         if (n != 0) {
    257                 irq_spinlock_lock(&CPU->rq[start].lock, false);
    258                 list_concat(&CPU->rq[start].rq, &list);
    259                 CPU->rq[start].n += n;
    260                 irq_spinlock_unlock(&CPU->rq[start].lock, false);
    261         }
    262 }
    263 
    264 /**
    265  * Do whatever needs to be done with current FPU state before we switch to
    266  * another thread.
    267  */
    268 static void fpu_cleanup(void)
    269 {
    270 #if (defined CONFIG_FPU) && (!defined CONFIG_FPU_LAZY)
    271         fpu_context_save(&THREAD->fpu_context);
    272 #endif
    273 }
    274 
    275 /**
    276  * Set correct FPU state for this thread after switch from another thread.
    277  */
    278 static void fpu_restore(void)
    279 {
    280 #ifdef CONFIG_FPU_LAZY
    281         /*
    282          * The only concurrent modification possible for fpu_owner here is
    283          * another thread changing it from itself to NULL in its destructor.
    284          */
    285         thread_t *owner = atomic_load_explicit(&CPU->fpu_owner,
    286             memory_order_relaxed);
    287 
    288         if (THREAD == owner)
    289                 fpu_enable();
    290         else
    291                 fpu_disable();
    292 
    293 #elif defined CONFIG_FPU
    294         fpu_enable();
    295         if (THREAD->fpu_context_exists)
    296                 fpu_context_restore(&THREAD->fpu_context);
    297         else {
    298                 fpu_init();
    299                 THREAD->fpu_context_exists = true;
    300         }
    301 #endif
    302 }
    303 
    304 /** Things to do before we switch to THREAD context.
    305  */
    306 static void prepare_to_run_thread(int rq_index)
    307 {
    308         relink_rq(rq_index);
    309 
    310         switch_task(THREAD->task);
    311 
    312         assert(atomic_get_unordered(&THREAD->cpu) == CPU);
    313 
    314         atomic_set_unordered(&THREAD->state, Running);
    315         atomic_set_unordered(&THREAD->priority, rq_index);  /* Correct rq index */
    316 
    317         /*
    318          * Clear the stolen flag so that it can be migrated
    319          * when load balancing needs emerge.
    320          */
    321         THREAD->stolen = false;
     393        /*
     394         * Hold the current task and the address space to prevent their
     395         * possible destruction should thread_destroy() be called on this or any
     396         * other processor while the scheduler is still using them.
     397         */
     398        if (old_task)
     399                task_hold(old_task);
     400
     401        if (old_as)
     402                as_hold(old_as);
     403
     404        if (THREAD) {
     405                /* Must be run after the switch to scheduler stack */
     406                after_thread_ran();
     407
     408                switch (THREAD->state) {
     409                case Running:
     410                        irq_spinlock_unlock(&THREAD->lock, false);
     411                        thread_ready(THREAD);
     412                        break;
     413
     414                case Exiting:
     415                repeat:
     416                        if (THREAD->detached) {
     417                                thread_destroy(THREAD, false);
     418                        } else {
     419                                /*
     420                                 * The thread structure is kept allocated until
     421                                 * somebody calls thread_detach() on it.
     422                                 */
     423                                if (!irq_spinlock_trylock(&THREAD->join_wq.lock)) {
     424                                        /*
     425                                         * Avoid deadlock.
     426                                         */
     427                                        irq_spinlock_unlock(&THREAD->lock, false);
     428                                        delay(HZ);
     429                                        irq_spinlock_lock(&THREAD->lock, false);
     430                                        DEADLOCK_PROBE(p_joinwq,
     431                                            DEADLOCK_THRESHOLD);
     432                                        goto repeat;
     433                                }
     434                                _waitq_wakeup_unsafe(&THREAD->join_wq,
     435                                    WAKEUP_FIRST);
     436                                irq_spinlock_unlock(&THREAD->join_wq.lock, false);
     437
     438                                THREAD->state = Lingering;
     439                                irq_spinlock_unlock(&THREAD->lock, false);
     440                        }
     441                        break;
     442
     443                case Sleeping:
     444                        /*
     445                         * Prefer the thread after it's woken up.
     446                         */
     447                        THREAD->priority = -1;
     448
     449                        /*
     450                         * We need to release wq->lock which we locked in
     451                         * waitq_sleep(). Address of wq->lock is kept in
     452                         * THREAD->sleep_queue.
     453                         */
     454                        irq_spinlock_unlock(&THREAD->sleep_queue->lock, false);
     455
     456                        irq_spinlock_unlock(&THREAD->lock, false);
     457                        break;
     458
     459                default:
     460                        /*
     461                         * Entering state is unexpected.
     462                         */
     463                        panic("tid%" PRIu64 ": unexpected state %s.",
     464                            THREAD->tid, thread_states[THREAD->state]);
     465                        break;
     466                }
     467
     468                THREAD = NULL;
     469        }
     470
     471        THREAD = find_best_thread();
     472
     473        irq_spinlock_lock(&THREAD->lock, false);
     474        int priority = THREAD->priority;
     475        irq_spinlock_unlock(&THREAD->lock, false);
     476
     477        relink_rq(priority);
     478
     479        /*
     480         * If both the old and the new task are the same,
     481         * lots of work is avoided.
     482         */
     483        if (TASK != THREAD->task) {
     484                as_t *new_as = THREAD->task->as;
     485
     486                /*
     487                 * Note that it is possible for two tasks
     488                 * to share one address space.
     489                 */
     490                if (old_as != new_as) {
     491                        /*
     492                         * Both tasks and address spaces are different.
     493                         * Replace the old one with the new one.
     494                         */
     495                        as_switch(old_as, new_as);
     496                }
     497
     498                TASK = THREAD->task;
     499                before_task_runs();
     500        }
     501
     502        if (old_task)
     503                task_release(old_task);
     504
     505        if (old_as)
     506                as_release(old_as);
     507
     508        irq_spinlock_lock(&THREAD->lock, false);
     509        THREAD->state = Running;
    322510
    323511#ifdef SCHEDULER_VERBOSE
    324512        log(LF_OTHER, LVL_DEBUG,
    325513            "cpu%u: tid %" PRIu64 " (priority=%d, ticks=%" PRIu64
    326             ", nrdy=%zu)", CPU->id, THREAD->tid, rq_index,
     514            ", nrdy=%zu)", CPU->id, THREAD->tid, THREAD->priority,
    327515            THREAD->ticks, atomic_load(&CPU->nrdy));
    328516#endif
    … …  
    336524         * function must be executed before the switch to the new stack.
    337525         */
    338         before_thread_runs_arch();
    339 
    340 #ifdef CONFIG_UDEBUG
    341         if (atomic_get_unordered(&THREAD->btrace)) {
    342                 istate_t *istate = THREAD->udebug.uspace_state;
    343                 if (istate != NULL) {
    344                         printf("Thread %" PRIu64 " stack trace:\n", THREAD->tid);
    345                         stack_trace_istate(istate);
    346                 } else {
    347                         printf("Thread %" PRIu64 " interrupt state not available\n", THREAD->tid);
    348                 }
    349 
    350                 atomic_set_unordered(&THREAD->btrace, false);
    351         }
    352 #endif
    353 
    354         fpu_restore();
    355 
    356         /* Time allocation in microseconds. */
    357         uint64_t time_to_run = (rq_index + 1) * 10000;
    358 
    359         /* Set the time of next preemption. */
    360         CPU_LOCAL->preempt_deadline =
    361             CPU_LOCAL->current_clock_tick + us2ticks(time_to_run);
    362 
    363         /* Save current CPU cycle */
    364         THREAD->last_cycle = get_cycle();
    365 }
    366 
    367 static void add_to_rq(thread_t *thread, cpu_t *cpu, int i)
    368 {
    369         /* Add to the appropriate runqueue. */
    370         runq_t *rq = &cpu->rq[i];
    371 
    372         irq_spinlock_lock(&rq->lock, false);
    373         list_append(&thread->rq_link, &rq->rq);
    374         rq->n++;
    375         irq_spinlock_unlock(&rq->lock, false);
    376 
    377         atomic_inc(&nrdy);
    378         atomic_inc(&cpu->nrdy);
    379 }
    380 
    381 /** Requeue a thread that was just preempted on this CPU.
    382  */
    383 static void thread_requeue_preempted(thread_t *thread)
    384 {
    385         assert(interrupts_disabled());
    386         assert(atomic_get_unordered(&thread->state) == Running);
    387         assert(atomic_get_unordered(&thread->cpu) == CPU);
    388 
    389         int prio = atomic_get_unordered(&thread->priority);
    390 
    391         if (prio < RQ_COUNT - 1) {
    392                 prio++;
    393                 atomic_set_unordered(&thread->priority, prio);
    394         }
    395 
    396         atomic_set_unordered(&thread->state, Ready);
    397 
    398         add_to_rq(thread, CPU, prio);
    399 }
    400 
    401 void thread_requeue_sleeping(thread_t *thread)
    402 {
    403         ipl_t ipl = interrupts_disable();
    404 
    405         assert(atomic_get_unordered(&thread->state) == Sleeping || atomic_get_unordered(&thread->state) == Entering);
    406 
    407         atomic_set_unordered(&thread->priority, 0);
    408         atomic_set_unordered(&thread->state, Ready);
    409 
    410         /* Prefer the CPU on which the thread ran last */
    411         cpu_t *cpu = atomic_get_unordered(&thread->cpu);
    412 
    413         if (!cpu) {
    414                 cpu = CPU;
    415                 atomic_set_unordered(&thread->cpu, CPU);
    416         }
    417 
    418         add_to_rq(thread, cpu, 0);
    419 
    420         interrupts_restore(ipl);
    421 }
    422 
    423 static void cleanup_after_thread(thread_t *thread)
    424 {
    425         assert(CURRENT->mutex_locks == 0);
    426         assert(interrupts_disabled());
    427 
    428         int expected;
    429 
    430         switch (atomic_get_unordered(&thread->state)) {
    431         case Running:
    432                 thread_requeue_preempted(thread);
    433                 break;
    434 
    435         case Exiting:
    436                 waitq_close(&thread->join_wq);
    437 
    438                 /*
    439                  * Release the reference CPU has for the thread.
    440                  * If there are no other references (e.g. threads calling join),
    441                  * the thread structure is deallocated.
    442                  */
    443                 thread_put(thread);
    444                 break;
    445 
    446         case Sleeping:
    447                 expected = SLEEP_INITIAL;
    448 
    449                 /* Only set SLEEP_ASLEEP in sleep pad if it's still in initial state */
    450                 if (!atomic_compare_exchange_strong_explicit(&thread->sleep_state,
    451                     &expected, SLEEP_ASLEEP,
    452                     memory_order_acq_rel, memory_order_acquire)) {
    453 
    454                         assert(expected == SLEEP_WOKE);
    455                         /* The thread has already been woken up, requeue immediately. */
    456                         thread_requeue_sleeping(thread);
    457                 }
    458                 break;
    459 
    460         default:
    461                 /*
    462                  * Entering state is unexpected.
    463                  */
    464                 panic("tid%" PRIu64 ": unexpected state %s.",
    465                     thread->tid, thread_states[atomic_get_unordered(&thread->state)]);
    466                 break;
    467         }
    468 }
    469 
    470 /** Switch to scheduler context to let other threads run. */
    471 void scheduler_enter(state_t new_state)
    472 {
    473         ipl_t ipl = interrupts_disable();
    474 
    475         assert(CPU != NULL);
    476         assert(THREAD != NULL);
    477 
    478         if (atomic_load(&haltstate))
    479                 halt();
    480 
    481         /* Check if we have a thread to switch to. */
    482 
    483         int rq_index;
    484         thread_t *new_thread = try_find_thread(&rq_index);
    485 
    486         if (new_thread == NULL && new_state == Running) {
    487                 /* No other thread to run, but we still have work to do here. */
    488                 interrupts_restore(ipl);
    489                 return;
    490         }
    491 
    492         atomic_set_unordered(&THREAD->state, new_state);
    493 
    494         /* Update thread kernel accounting */
    495         atomic_time_increment(&THREAD->kcycles, get_cycle() - THREAD->last_cycle);
    496 
    497         fpu_cleanup();
    498 
    499         /*
    500          * On Sparc, this saves some extra userspace state that's not
    501          * covered by context_save()/context_restore().
    502          */
    503         after_thread_ran_arch();
    504 
    505         if (new_thread) {
    506                 thread_t *old_thread = THREAD;
    507                 CPU_LOCAL->prev_thread = old_thread;
    508                 THREAD = new_thread;
    509                 /* No waiting necessary, we can switch to the new thread directly. */
    510                 prepare_to_run_thread(rq_index);
    511 
    512                 current_copy(CURRENT, (current_t *) new_thread->kstack);
    513                 context_swap(&old_thread->saved_context, &new_thread->saved_context);
    514         } else {
    515                 /*
    516                  * A new thread isn't immediately available, switch to a separate
    517                  * stack to sleep or do other idle stuff.
    518                  */
    519                 current_copy(CURRENT, (current_t *) CPU_LOCAL->stack);
    520                 context_swap(&THREAD->saved_context, &CPU_LOCAL->scheduler_context);
    521         }
    522 
    523         assert(CURRENT->mutex_locks == 0);
    524         assert(interrupts_disabled());
    525 
    526         /* Check if we need to clean up after another thread. */
    527         if (CPU_LOCAL->prev_thread) {
    528                 cleanup_after_thread(CPU_LOCAL->prev_thread);
    529                 CPU_LOCAL->prev_thread = NULL;
    530         }
    531 
    532         interrupts_restore(ipl);
    533 }
    534 
    535 /** Enter main scheduler loop. Never returns.
    536  *
    537  * This function switches to a runnable thread as soon as one is available,
    538  * after which it is only switched back to if a thread is stopping and there is
    539  * no other thread to run in its place. We need a separate context for that
    540  * because we're going to block the CPU, which means we need another context
    541  * to clean up after the previous thread.
    542  */
    543 void scheduler_run(void)
    544 {
    545         assert(interrupts_disabled());
    546 
    547         assert(CPU != NULL);
    548         assert(TASK == NULL);
    549         assert(THREAD == NULL);
    550         assert(interrupts_disabled());
    551 
    552         while (!atomic_load(&haltstate)) {
    553                 assert(CURRENT->mutex_locks == 0);
    554 
    555                 int rq_index;
    556                 THREAD = find_best_thread(&rq_index);
    557                 prepare_to_run_thread(rq_index);
    558 
    559                 /*
    560                  * Copy the knowledge of CPU, TASK, THREAD and preemption counter to
    561                  * thread's stack.
    562                  */
    563                 current_copy(CURRENT, (current_t *) THREAD->kstack);
    564 
    565                 /* Switch to thread context. */
    566                 context_swap(&CPU_LOCAL->scheduler_context, &THREAD->saved_context);
    567 
    568                 /* Back from another thread. */
    569                 assert(CPU != NULL);
    570                 assert(THREAD != NULL);
    571                 assert(CURRENT->mutex_locks == 0);
    572                 assert(interrupts_disabled());
    573 
    574                 cleanup_after_thread(THREAD);
    575 
    576                 /*
    577                  * Necessary because we're allowing interrupts in find_best_thread(),
    578                  * so we need to avoid other code referencing the thread we left.
    579                  */
    580                 THREAD = NULL;
    581         }
    582 
    583         halt();
    584 }
    585 
    586 /** Thread wrapper.
    587  *
    588  * This wrapper is provided to ensure that a starting thread properly handles
    589  * everything it needs to do when first scheduled, and when it exits.
    590  */
    591 void thread_main_func(void)
    592 {
    593         assert(interrupts_disabled());
    594 
    595         void (*f)(void *) = THREAD->thread_code;
    596         void *arg = THREAD->thread_arg;
    597 
    598         /* This is where each thread wakes up after its creation */
    599 
    600         /* Check if we need to clean up after another thread. */
    601         if (CPU_LOCAL->prev_thread) {
    602                 cleanup_after_thread(CPU_LOCAL->prev_thread);
    603                 CPU_LOCAL->prev_thread = NULL;
    604         }
    605 
    606         interrupts_enable();
    607 
    608         f(arg);
    609 
    610         thread_exit();
     526        before_thread_runs();
     527
     528        /*
     529         * Copy the knowledge of CPU, TASK, THREAD and preemption counter to
     530         * thread's stack.
     531         */
     532        current_copy(CURRENT, (current_t *) THREAD->kstack);
     533
     534        context_restore(&THREAD->saved_context);
    611535
    612536        /* Not reached */
    … …  
    614538
    615539#ifdef CONFIG_SMP
    616 
    617 static thread_t *steal_thread_from(cpu_t *old_cpu, int i)
    618 {
    619         runq_t *old_rq = &old_cpu->rq[i];
    620         runq_t *new_rq = &CPU->rq[i];
    621 
    622         ipl_t ipl = interrupts_disable();
    623 
    624         irq_spinlock_lock(&old_rq->lock, false);
    625 
    626         /*
    627          * If fpu_owner is any thread in the list, its store is seen here thanks to
    628          * the runqueue lock.
    629          */
    630         thread_t *fpu_owner = atomic_load_explicit(&old_cpu->fpu_owner,
    631             memory_order_relaxed);
    632 
    633         /* Search rq from the back */
    634         list_foreach_rev(old_rq->rq, rq_link, thread_t, thread) {
    635 
    636                 /*
    637                  * Do not steal CPU-wired threads, threads
    638                  * already stolen, threads for which migration
    639                  * was temporarily disabled or threads whose
    640                  * FPU context is still in the CPU.
    641                  */
    642                 if (thread->stolen || thread->nomigrate || thread == fpu_owner) {
    643                         continue;
    644                 }
    645 
    646                 thread->stolen = true;
    647                 atomic_set_unordered(&thread->cpu, CPU);
    648 
    649                 /*
    650                  * Ready thread on local CPU
    651                  */
    652 
    653 #ifdef KCPULB_VERBOSE
    654                 log(LF_OTHER, LVL_DEBUG,
    655                     "kcpulb%u: TID %" PRIu64 " -> cpu%u, "
    656                     "nrdy=%ld, avg=%ld", CPU->id, thread->tid,
    657                     CPU->id, atomic_load(&CPU->nrdy),
    658                     atomic_load(&nrdy) / config.cpu_active);
    659 #endif
    660 
    661                 /* Remove thread from ready queue. */
    662                 old_rq->n--;
    663                 list_remove(&thread->rq_link);
    664                 irq_spinlock_unlock(&old_rq->lock, false);
    665 
    666                 /* Append thread to local queue. */
    667                 irq_spinlock_lock(&new_rq->lock, false);
    668                 list_append(&thread->rq_link, &new_rq->rq);
    669                 new_rq->n++;
    670                 irq_spinlock_unlock(&new_rq->lock, false);
    671 
    672                 atomic_dec(&old_cpu->nrdy);
    673                 atomic_inc(&CPU->nrdy);
    674                 interrupts_restore(ipl);
    675                 return thread;
    676         }
    677 
    678         irq_spinlock_unlock(&old_rq->lock, false);
    679         interrupts_restore(ipl);
    680         return NULL;
    681 }
    682 
    683540/** Load balancing thread
    684541 *
    … …  
    693550        size_t average;
    694551        size_t rdy;
     552
     553        /*
     554         * Detach kcpulb as nobody will call thread_join_timeout() on it.
     555         */
     556        thread_detach(THREAD);
    695557
    696558loop:
    … …  
    720582         */
    721583        size_t acpu;
     584        size_t acpu_bias = 0;
    722585        int rq;
    723586
    724587        for (rq = RQ_COUNT - 1; rq >= 0; rq--) {
    725588                for (acpu = 0; acpu < config.cpu_active; acpu++) {
    726                         cpu_t *cpu = &cpus[acpu];
     589                        cpu_t *cpu = &cpus[(acpu + acpu_bias) % config.cpu_active];
    727590
    728591                        /*
    … …  
    738601                                continue;
    739602
    740                         if (steal_thread_from(cpu, rq) && --count == 0)
    741                                 goto satisfied;
     603                        irq_spinlock_lock(&(cpu->rq[rq].lock), true);
     604                        if (cpu->rq[rq].n == 0) {
     605                                irq_spinlock_unlock(&(cpu->rq[rq].lock), true);
     606                                continue;
     607                        }
     608
     609                        thread_t *thread = NULL;
     610
     611                        /* Search rq from the back */
     612                        link_t *link = list_last(&cpu->rq[rq].rq);
     613
     614                        while (link != NULL) {
     615                                thread = (thread_t *) list_get_instance(link,
     616                                    thread_t, rq_link);
     617
     618                                /*
     619                                 * Do not steal CPU-wired threads, threads
     620                                 * already stolen, threads for which migration
     621                                 * was temporarily disabled or threads whose
     622                                 * FPU context is still in the CPU.
     623                                 */
     624                                irq_spinlock_lock(&thread->lock, false);
     625
     626                                if ((!thread->wired) && (!thread->stolen) &&
     627                                    (!thread->nomigrate) &&
     628                                    (!thread->fpu_context_engaged)) {
     629                                        /*
     630                                         * Remove thread from ready queue.
     631                                         */
     632                                        irq_spinlock_unlock(&thread->lock,
     633                                            false);
     634
     635                                        atomic_dec(&cpu->nrdy);
     636                                        atomic_dec(&nrdy);
     637
     638                                        cpu->rq[rq].n--;
     639                                        list_remove(&thread->rq_link);
     640
     641                                        break;
     642                                }
     643
     644                                irq_spinlock_unlock(&thread->lock, false);
     645
     646                                link = list_prev(link, &cpu->rq[rq].rq);
     647                                thread = NULL;
     648                        }
     649
     650                        if (thread) {
     651                                /*
     652                                 * Ready thread on local CPU
     653                                 */
     654
     655                                irq_spinlock_pass(&(cpu->rq[rq].lock),
     656                                    &thread->lock);
     657
     658#ifdef KCPULB_VERBOSE
     659                                log(LF_OTHER, LVL_DEBUG,
     660                                    "kcpulb%u: TID %" PRIu64 " -> cpu%u, "
     661                                    "nrdy=%ld, avg=%ld", CPU->id, thread->tid,
     662                                    CPU->id, atomic_load(&CPU->nrdy),
     663                                    atomic_load(&nrdy) / config.cpu_active);
     664#endif
     665
     666                                thread->stolen = true;
     667                                thread->state = Entering;
     668
     669                                irq_spinlock_unlock(&thread->lock, true);
     670                                thread_ready(thread);
     671
     672                                if (--count == 0)
     673                                        goto satisfied;
     674
     675                                /*
     676                                 * We are not satisfied yet, focus on another
     677                                 * CPU next time.
     678                                 *
     679                                 */
     680                                acpu_bias++;
     681
     682                                continue;
     683                        } else
     684                                irq_spinlock_unlock(&(cpu->rq[rq].lock), true);
     685
    742686                }
    743687        }
    … …  
    748692                 *
    749693                 */
    750                 thread_yield();
     694                scheduler();
    751695        } else {
    752696                /*
    … …  
    775719                        continue;
    776720
    777                 printf("cpu%u: address=%p, nrdy=%zu\n",
    778                     cpus[cpu].id, &cpus[cpu], atomic_load(&cpus[cpu].nrdy));
     721                irq_spinlock_lock(&cpus[cpu].lock, true);
     722
     723                printf("cpu%u: address=%p, nrdy=%zu, needs_relink=%zu\n",
     724                    cpus[cpu].id, &cpus[cpu], atomic_load(&cpus[cpu].nrdy),
     725                    cpus[cpu].needs_relink);
    779726
    780727                unsigned int i;
    … …  
    790737                            thread) {
    791738                                printf("%" PRIu64 "(%s) ", thread->tid,
    792                                     thread_states[atomic_get_unordered(&thread->state)]);
     739                                    thread_states[thread->state]);
    793740                        }
    794741                        printf("\n");
    … …  
    796743                        irq_spinlock_unlock(&(cpus[cpu].rq[i].lock), false);
    797744                }
     745
     746                irq_spinlock_unlock(&cpus[cpu].lock, true);
    798747        }
    799748}
Note: See TracChangeset for help on using the changeset viewer.