Changeset f2cb80a in mainline for kernel/generic/src/proc/scheduler.c
- Timestamp:
- 2024-02-23T17:57:23Z (11 months ago)
- Children:
- 192019f
- Parents:
- 86f862c (diff), 90ba06c (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the(diff)links above to see all the changes relative to each parent. - git-author:
- boba-buba <120932204+boba-buba@…> (2024-02-23 17:57:23)
- git-committer:
- GitHub <noreply@…> (2024-02-23 17:57:23)
- File:
-
- 1 edited
-
kernel/generic/src/proc/scheduler.c (modified) (13 diffs)
Legend:
- Unmodified
- Added
- Removed
-
kernel/generic/src/proc/scheduler.c
r86f862c rf2cb80a 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 68 atomic_size_t nrdy; /**< Number of ready threads in the system. */ 71 72 /** Take actions before new thread runs.73 *74 * Perform actions that need to be75 * taken before the newly selected76 * thread is passed control.77 *78 * THREAD->lock is locked on entry79 *80 */81 static void before_thread_runs(void)82 {83 before_thread_runs_arch();84 85 #ifdef CONFIG_FPU_LAZY86 /*87 * The only concurrent modification possible for fpu_owner here is88 * another thread changing it from itself to NULL in its destructor.89 */90 thread_t *owner = atomic_load_explicit(&CPU->fpu_owner,91 memory_order_relaxed);92 93 if (THREAD == owner)94 fpu_enable();95 else96 fpu_disable();97 #elif defined CONFIG_FPU98 fpu_enable();99 if (THREAD->fpu_context_exists)100 fpu_context_restore(&THREAD->fpu_context);101 else {102 fpu_init();103 THREAD->fpu_context_exists = true;104 }105 #endif106 107 #ifdef CONFIG_UDEBUG108 if (THREAD->btrace) {109 istate_t *istate = THREAD->udebug.uspace_state;110 if (istate != NULL) {111 printf("Thread %" PRIu64 " stack trace:\n", THREAD->tid);112 stack_trace_istate(istate);113 }114 115 THREAD->btrace = false;116 }117 #endif118 }119 120 /** Take actions after THREAD had run.121 *122 * Perform actions that need to be123 * taken after the running thread124 * had been preempted by the scheduler.125 *126 * THREAD->lock is locked on entry127 *128 */129 static void after_thread_ran(void)130 {131 after_thread_ran_arch();132 }133 69 134 70 #ifdef CONFIG_FPU_LAZY … … 207 143 list_remove(&thread->rq_link); 208 144 209 irq_spinlock_pass(&(CPU->rq[i].lock), &thread->lock); 210 211 thread->cpu = CPU; 212 thread->priority = i; /* Correct rq index */ 213 214 /* Time allocation in microseconds. */ 215 uint64_t time_to_run = (i + 1) * 10000; 216 217 /* This is safe because interrupts are disabled. */ 218 CPU->preempt_deadline = CPU->current_clock_tick + us2ticks(time_to_run); 219 220 /* 221 * Clear the stolen flag so that it can be migrated 222 * when load balancing needs emerge. 223 */ 224 thread->stolen = false; 225 irq_spinlock_unlock(&thread->lock, false); 145 irq_spinlock_unlock(&(CPU->rq[i].lock), false); 226 146 227 147 *rq_index = i; … … 257 177 * This improves energy saving and hyperthreading. 258 178 */ 259 CPU ->idle = true;179 CPU_LOCAL->idle = true; 260 180 261 181 /* … … 305 225 static void relink_rq(int start) 306 226 { 307 if (CPU->current_clock_tick < CPU->relink_deadline) 227 assert(interrupts_disabled()); 228 229 if (CPU_LOCAL->current_clock_tick < CPU_LOCAL->relink_deadline) 308 230 return; 309 231 310 CPU ->relink_deadline = CPU->current_clock_tick + NEEDS_RELINK_MAX;232 CPU_LOCAL->relink_deadline = CPU_LOCAL->current_clock_tick + NEEDS_RELINK_MAX; 311 233 312 234 /* Temporary cache for lists we are moving. */ … … 340 262 } 341 263 342 void scheduler(void) 343 { 344 ipl_t ipl = interrupts_disable(); 345 346 if (atomic_load(&haltstate)) 347 halt(); 348 349 if (THREAD) { 350 irq_spinlock_lock(&THREAD->lock, false); 351 } 352 353 scheduler_locked(ipl); 354 } 355 356 /** The scheduler 357 * 358 * The thread scheduling procedure. 359 * Passes control directly to 360 * scheduler_separated_stack(). 361 * 362 */ 363 void scheduler_locked(ipl_t ipl) 364 { 365 assert(CPU != NULL); 366 367 if (THREAD) { 368 /* Update thread kernel accounting */ 369 THREAD->kcycles += get_cycle() - THREAD->last_cycle; 370 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 { 371 270 #if (defined CONFIG_FPU) && (!defined CONFIG_FPU_LAZY) 372 271 fpu_context_save(&THREAD->fpu_context); 373 272 #endif 374 if (!context_save(&THREAD->saved_context)) { 375 /* 376 * This is the place where threads leave scheduler(); 377 */ 378 379 /* Save current CPU cycle */ 380 THREAD->last_cycle = get_cycle(); 381 382 irq_spinlock_unlock(&THREAD->lock, false); 383 interrupts_restore(THREAD->saved_ipl); 384 385 return; 386 } 387 388 /* 389 * Interrupt priority level of preempted thread is recorded 390 * here to facilitate scheduler() invocations from 391 * interrupts_disable()'d code (e.g. waitq_sleep_timeout()). 392 * 393 */ 394 THREAD->saved_ipl = ipl; 395 } 396 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 397 281 /* 398 * Through the 'CURRENT' structure, we keep track of THREAD, TASK, CPU, AS 399 * and preemption counter. At this point CURRENT could be coming either 400 * from THREAD's or CPU's stack. 401 * 282 * The only concurrent modification possible for fpu_owner here is 283 * another thread changing it from itself to NULL in its destructor. 402 284 */ 403 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 */ 404 316 405 317 /* 406 * We may not keep the old stack. 407 * Reason: If we kept the old stack and got blocked, for instance, in 408 * find_best_thread(), the old thread could get rescheduled by another 409 * CPU and overwrite the part of its own stack that was also used by 410 * the scheduler on this CPU. 411 * 412 * Moreover, we have to bypass the compiler-generated POP sequence 413 * which is fooled by SP being set to the very top of the stack. 414 * Therefore the scheduler() function continues in 415 * scheduler_separated_stack(). 416 * 318 * Clear the stolen flag so that it can be migrated 319 * when load balancing needs emerge. 417 320 */ 418 context_t ctx; 419 context_save(&ctx); 420 context_set(&ctx, FADDR(scheduler_separated_stack), 421 (uintptr_t) CPU->stack, STACK_SIZE); 422 context_restore(&ctx); 423 424 /* Not reached */ 425 } 426 427 /** Scheduler stack switch wrapper 428 * 429 * Second part of the scheduler() function 430 * using new stack. Handling the actual context 431 * switch to a new thread. 432 * 433 */ 434 void scheduler_separated_stack(void) 435 { 436 assert((!THREAD) || (irq_spinlock_locked(&THREAD->lock))); 437 assert(CPU != NULL); 438 assert(interrupts_disabled()); 439 440 if (THREAD) { 441 /* Must be run after the switch to scheduler stack */ 442 after_thread_ran(); 443 444 switch (THREAD->state) { 445 case Running: 446 irq_spinlock_unlock(&THREAD->lock, false); 447 thread_ready(THREAD); 448 break; 449 450 case Exiting: 451 irq_spinlock_unlock(&THREAD->lock, false); 452 waitq_close(&THREAD->join_wq); 453 454 /* 455 * Release the reference CPU has for the thread. 456 * If there are no other references (e.g. threads calling join), 457 * the thread structure is deallocated. 458 */ 459 thread_put(THREAD); 460 break; 461 462 case Sleeping: 463 /* 464 * Prefer the thread after it's woken up. 465 */ 466 THREAD->priority = -1; 467 irq_spinlock_unlock(&THREAD->lock, false); 468 break; 469 470 default: 471 /* 472 * Entering state is unexpected. 473 */ 474 panic("tid%" PRIu64 ": unexpected state %s.", 475 THREAD->tid, thread_states[THREAD->state]); 476 break; 477 } 478 479 THREAD = NULL; 480 } 481 482 int rq_index; 483 THREAD = find_best_thread(&rq_index); 484 485 relink_rq(rq_index); 486 487 switch_task(THREAD->task); 488 489 irq_spinlock_lock(&THREAD->lock, false); 490 THREAD->state = Running; 321 THREAD->stolen = false; 491 322 492 323 #ifdef SCHEDULER_VERBOSE 493 324 log(LF_OTHER, LVL_DEBUG, 494 325 "cpu%u: tid %" PRIu64 " (priority=%d, ticks=%" PRIu64 495 ", nrdy=%zu)", CPU->id, THREAD->tid, THREAD->priority,326 ", nrdy=%zu)", CPU->id, THREAD->tid, rq_index, 496 327 THREAD->ticks, atomic_load(&CPU->nrdy)); 497 328 #endif … … 505 336 * function must be executed before the switch to the new stack. 506 337 */ 507 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(); 508 498 509 499 /* 510 * Copy the knowledge of CPU, TASK, THREAD and preemption counter to511 * thread's stack.500 * On Sparc, this saves some extra userspace state that's not 501 * covered by context_save()/context_restore(). 512 502 */ 513 current_copy(CURRENT, (current_t *) THREAD->kstack); 514 515 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(); 516 611 517 612 /* Not reached */ … … 539 634 list_foreach_rev(old_rq->rq, rq_link, thread_t, thread) { 540 635 541 irq_spinlock_lock(&thread->lock, false);542 543 636 /* 544 637 * Do not steal CPU-wired threads, threads … … 547 640 * FPU context is still in the CPU. 548 641 */ 549 if (thread->stolen || thread->nomigrate || 550 thread == fpu_owner) { 551 irq_spinlock_unlock(&thread->lock, false); 642 if (thread->stolen || thread->nomigrate || thread == fpu_owner) { 552 643 continue; 553 644 } 554 645 555 646 thread->stolen = true; 556 thread->cpu = CPU; 557 558 irq_spinlock_unlock(&thread->lock, false); 647 atomic_set_unordered(&thread->cpu, CPU); 559 648 560 649 /* … … 659 748 * 660 749 */ 661 scheduler();750 thread_yield(); 662 751 } else { 663 752 /* … … 686 775 continue; 687 776 688 /* Technically a data race, but we don't really care in this case. */ 689 int needs_relink = cpus[cpu].relink_deadline - cpus[cpu].current_clock_tick; 690 691 printf("cpu%u: address=%p, nrdy=%zu, needs_relink=%d\n", 692 cpus[cpu].id, &cpus[cpu], atomic_load(&cpus[cpu].nrdy), 693 needs_relink); 777 printf("cpu%u: address=%p, nrdy=%zu\n", 778 cpus[cpu].id, &cpus[cpu], atomic_load(&cpus[cpu].nrdy)); 694 779 695 780 unsigned int i; … … 705 790 thread) { 706 791 printf("%" PRIu64 "(%s) ", thread->tid, 707 thread_states[ thread->state]);792 thread_states[atomic_get_unordered(&thread->state)]); 708 793 } 709 794 printf("\n");
Note:
See TracChangeset
for help on using the changeset viewer.
