Changes in kernel/generic/src/proc/scheduler.c [583c2a3:d23712e] in mainline
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
kernel/generic/src/proc/scheduler.c
r583c2a3 rd23712e 1 1 /* 2 2 * Copyright (c) 2010 Jakub Jermar 3 * Copyright (c) 2023 Jiří Zárevúcky 3 4 * All rights reserved. 4 5 * … … 50 51 #include <time/delay.h> 51 52 #include <arch/asm.h> 52 #include <arch/faddr.h>53 53 #include <arch/cycle.h> 54 54 #include <atomic.h> … … 66 66 #include <stacktrace.h> 67 67 68 static void scheduler_separated_stack(void); 69 70 atomic_t nrdy; /**< Number of ready threads in the system. */ 71 72 /** Carry out actions before new task runs. */ 73 static 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 */ 87 static 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 */ 128 static void after_thread_ran(void) 129 { 130 after_thread_ran_arch(); 131 } 68 atomic_size_t nrdy; /**< Number of ready threads in the system. */ 132 69 133 70 #ifdef CONFIG_FPU_LAZY … … 135 72 { 136 73 fpu_enable(); 137 irq_spinlock_lock(&CPU->lock, false); 74 75 /* We need this lock to ensure synchronization with thread destructor. */ 76 irq_spinlock_lock(&CPU->fpu_lock, false); 138 77 139 78 /* Save old context */ 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); 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 151 87 if (THREAD->fpu_context_exists) { 152 fpu_context_restore( THREAD->saved_fpu_context);88 fpu_context_restore(&THREAD->fpu_context); 153 89 } else { 154 90 fpu_init(); … … 156 92 } 157 93 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); 94 atomic_store_explicit(&CPU->fpu_owner, THREAD, memory_order_relaxed); 163 95 } 164 96 #endif /* CONFIG_FPU_LAZY */ … … 182 114 * 183 115 */ 184 static thread_t *find_best_thread(void) 185 { 116 static thread_t *try_find_thread(int *rq_index) 117 { 118 assert(interrupts_disabled()); 186 119 assert(CPU != NULL); 187 120 188 loop: 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++) { 121 if (atomic_load(&CPU->nrdy) == 0) 122 return NULL; 123 124 for (int i = 0; i < RQ_COUNT; i++) { 215 125 irq_spinlock_lock(&(CPU->rq[i].lock), false); 216 126 if (CPU->rq[i].n == 0) { … … 233 143 list_remove(&thread->rq_link); 234 144 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 145 irq_spinlock_unlock(&(CPU->rq[i].lock), false); 146 147 *rq_index = i; 248 148 return thread; 249 149 } 250 150 251 goto loop; 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(); 252 212 } 253 213 … … 265 225 static void relink_rq(int start) 266 226 { 227 assert(interrupts_disabled()); 228 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. */ 267 235 list_t list; 268 269 236 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 */ 304 void 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 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 { 321 270 #if (defined CONFIG_FPU) && (!defined CONFIG_FPU_LAZY) 322 fpu_context_save(THREAD->saved_fpu_context);271 fpu_context_save(&THREAD->fpu_context); 323 272 #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 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 347 281 /* 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 * 282 * The only concurrent modification possible for fpu_owner here is 283 * another thread changing it from itself to NULL in its destructor. 352 284 */ 353 current_copy(CURRENT, (current_t *) CPU->stack); 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 */ 354 316 355 317 /* 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 * 318 * Clear the stolen flag so that it can be migrated 319 * when load balancing needs emerge. 367 320 */ 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 */ 383 void 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); 391 assert(interrupts_disabled()); 392 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; 321 THREAD->stolen = false; 510 322 511 323 #ifdef SCHEDULER_VERBOSE 512 324 log(LF_OTHER, LVL_DEBUG, 513 325 "cpu%u: tid %" PRIu64 " (priority=%d, ticks=%" PRIu64 514 ", nrdy=%zu)", CPU->id, THREAD->tid, THREAD->priority,326 ", nrdy=%zu)", CPU->id, THREAD->tid, rq_index, 515 327 THREAD->ticks, atomic_load(&CPU->nrdy)); 516 328 #endif … … 524 336 * function must be executed before the switch to the new stack. 525 337 */ 526 before_thread_runs(); 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(); 527 498 528 499 /* 529 * Copy the knowledge of CPU, TASK, THREAD and preemption counter to530 * thread's stack.500 * On Sparc, this saves some extra userspace state that's not 501 * covered by context_save()/context_restore(). 531 502 */ 532 current_copy(CURRENT, (current_t *) THREAD->kstack); 533 534 context_restore(&THREAD->saved_context); 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(); 535 611 536 612 /* Not reached */ … … 538 614 539 615 #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 540 683 /** Load balancing thread 541 684 * … … 550 693 size_t average; 551 694 size_t rdy; 552 553 /*554 * Detach kcpulb as nobody will call thread_join_timeout() on it.555 */556 thread_detach(THREAD);557 695 558 696 loop: … … 582 720 */ 583 721 size_t acpu; 584 size_t acpu_bias = 0;585 722 int rq; 586 723 587 724 for (rq = RQ_COUNT - 1; rq >= 0; rq--) { 588 725 for (acpu = 0; acpu < config.cpu_active; acpu++) { 589 cpu_t *cpu = &cpus[ (acpu + acpu_bias) % config.cpu_active];726 cpu_t *cpu = &cpus[acpu]; 590 727 591 728 /* … … 601 738 continue; 602 739 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 740 if (steal_thread_from(cpu, rq) && --count == 0) 741 goto satisfied; 686 742 } 687 743 } … … 692 748 * 693 749 */ 694 scheduler();750 thread_yield(); 695 751 } else { 696 752 /* … … 719 775 continue; 720 776 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); 777 printf("cpu%u: address=%p, nrdy=%zu\n", 778 cpus[cpu].id, &cpus[cpu], atomic_load(&cpus[cpu].nrdy)); 726 779 727 780 unsigned int i; … … 737 790 thread) { 738 791 printf("%" PRIu64 "(%s) ", thread->tid, 739 thread_states[ thread->state]);792 thread_states[atomic_get_unordered(&thread->state)]); 740 793 } 741 794 printf("\n"); … … 743 796 irq_spinlock_unlock(&(cpus[cpu].rq[i].lock), false); 744 797 } 745 746 irq_spinlock_unlock(&cpus[cpu].lock, true);747 798 } 748 799 }
Note:
See TracChangeset
for help on using the changeset viewer.