osfmk/kern/sched_dualq.c

   1 /*
   2  * Copyright (c) 2013 Apple Inc. All rights reserved.
   3  *
   4  * @APPLE_OSREFERENCE_LICENSE_HEADER_START@
   5  *
   6  * This file contains Original Code and/or Modifications of Original Code
   7  * as defined in and that are subject to the Apple Public Source License
   8  * Version 2.0 (the 'License'). You may not use this file except in
   9  * compliance with the License. The rights granted to you under the License
  10  * may not be used to create, or enable the creation or redistribution of,
  11  * unlawful or unlicensed copies of an Apple operating system, or to
  12  * circumvent, violate, or enable the circumvention or violation of, any
  13  * terms of an Apple operating system software license agreement.
  14  *
  15  * Please obtain a copy of the License at
  16  * http://www.opensource.apple.com/apsl/ and read it before using this file.
  17  *
  18  * The Original Code and all software distributed under the License are
  19  * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
  20  * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
  21  * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
  22  * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
  23  * Please see the License for the specific language governing rights and
  24  * limitations under the License.
  25  *
  26  * @APPLE_OSREFERENCE_LICENSE_HEADER_END@
  27  */
  28
  29 #include <mach/mach_types.h>
  30 #include <mach/machine.h>
  31
  32 #include <machine/machine_routines.h>
  33 #include <machine/sched_param.h>
  34 #include <machine/machine_cpu.h>
  35
  36 #include <kern/kern_types.h>
  37 #include <kern/debug.h>
  38 #include <kern/machine.h>
  39 #include <kern/misc_protos.h>
  40 #include <kern/processor.h>
  41 #include <kern/queue.h>
  42 #include <kern/sched.h>
  43 #include <kern/sched_prim.h>
  44 #include <kern/task.h>
  45 #include <kern/thread.h>
  46
  47 #include <sys/kdebug.h>
  48
  49 static void
  50 sched_dualq_init(void);
  51
  52 static thread_t
  53 sched_dualq_steal_thread(processor_set_t pset);
  54
  55 static void
  56 sched_dualq_thread_update_scan(sched_update_scan_context_t scan_context);
  57
  58 static boolean_t
  59 sched_dualq_processor_enqueue(processor_t processor, thread_t thread,
  60     sched_options_t options);
  61
  62 static boolean_t
  63 sched_dualq_processor_queue_remove(processor_t processor, thread_t thread);
  64
  65 static ast_t
  66 sched_dualq_processor_csw_check(processor_t processor);
  67
  68 static boolean_t
  69 sched_dualq_processor_queue_has_priority(processor_t processor, int priority, boolean_t gte);
  70
  71 static int
  72 sched_dualq_runq_count(processor_t processor);
  73
  74 static boolean_t
  75 sched_dualq_processor_queue_empty(processor_t processor);
  76
  77 static uint64_t
  78 sched_dualq_runq_stats_count_sum(processor_t processor);
  79
  80 static int
  81 sched_dualq_processor_bound_count(processor_t processor);
  82
  83 static void
  84 sched_dualq_pset_init(processor_set_t pset);
  85
  86 static void
  87 sched_dualq_processor_init(processor_t processor);
  88
  89 static thread_t
  90 sched_dualq_choose_thread(processor_t processor, int priority, ast_t reason);
  91
  92 static void
  93 sched_dualq_processor_queue_shutdown(processor_t processor);
  94
  95 static sched_mode_t
  96 sched_dualq_initial_thread_sched_mode(task_t parent_task);
  97
  98 static bool
  99 sched_dualq_thread_avoid_processor(processor_t processor, thread_t thread);
 100
 101 const struct sched_dispatch_table sched_dualq_dispatch = {
 102         .sched_name                                     = "dualq",
 103         .init                                           = sched_dualq_init,
 104         .timebase_init                                  = sched_timeshare_timebase_init,
 105         .processor_init                                 = sched_dualq_processor_init,
 106         .pset_init                                      = sched_dualq_pset_init,
 107         .maintenance_continuation                       = sched_timeshare_maintenance_continue,
 108         .choose_thread                                  = sched_dualq_choose_thread,
 109         .steal_thread_enabled                           = sched_steal_thread_enabled,
 110         .steal_thread                                   = sched_dualq_steal_thread,
 111         .compute_timeshare_priority                     = sched_compute_timeshare_priority,
 112         .choose_processor                               = choose_processor,
 113         .processor_enqueue                              = sched_dualq_processor_enqueue,
 114         .processor_queue_shutdown                       = sched_dualq_processor_queue_shutdown,
 115         .processor_queue_remove                         = sched_dualq_processor_queue_remove,
 116         .processor_queue_empty                          = sched_dualq_processor_queue_empty,
 117         .priority_is_urgent                             = priority_is_urgent,
 118         .processor_csw_check                            = sched_dualq_processor_csw_check,
 119         .processor_queue_has_priority                   = sched_dualq_processor_queue_has_priority,
 120         .initial_quantum_size                           = sched_timeshare_initial_quantum_size,
 121         .initial_thread_sched_mode                      = sched_dualq_initial_thread_sched_mode,
 122         .can_update_priority                            = can_update_priority,
 123         .update_priority                                = update_priority,
 124         .lightweight_update_priority                    = lightweight_update_priority,
 125         .quantum_expire                                 = sched_default_quantum_expire,
 126         .processor_runq_count                           = sched_dualq_runq_count,
 127         .processor_runq_stats_count_sum                 = sched_dualq_runq_stats_count_sum,
 128         .processor_bound_count                          = sched_dualq_processor_bound_count,
 129         .thread_update_scan                             = sched_dualq_thread_update_scan,
 130         .multiple_psets_enabled                         = TRUE,
 131         .sched_groups_enabled                           = FALSE,
 132         .avoid_processor_enabled                        = TRUE,
 133         .thread_avoid_processor                         = sched_dualq_thread_avoid_processor,
 134         .processor_balance                              = sched_SMT_balance,
 135
 136         .rt_runq                                        = sched_rtglobal_runq,
 137         .rt_init                                        = sched_rtglobal_init,
 138         .rt_queue_shutdown                              = sched_rtglobal_queue_shutdown,
 139         .rt_runq_scan                                   = sched_rtglobal_runq_scan,
 140         .rt_runq_count_sum                              = sched_rtglobal_runq_count_sum,
 141
 142         .qos_max_parallelism                            = sched_qos_max_parallelism,
 143         .check_spill                                    = sched_check_spill,
 144         .ipi_policy                                     = sched_ipi_policy,
 145         .thread_should_yield                            = sched_thread_should_yield,
 146         .run_count_incr                                 = sched_run_incr,
 147         .run_count_decr                                 = sched_run_decr,
 148         .update_thread_bucket                           = sched_update_thread_bucket,
 149         .pset_made_schedulable                          = sched_pset_made_schedulable,
 150 };
 151
 152 __attribute__((always_inline))
 153 static inline run_queue_t
 154 dualq_main_runq(processor_t processor)
 155 {
 156         return &processor->processor_set->pset_runq;
 157 }
 158
 159 __attribute__((always_inline))
 160 static inline run_queue_t
 161 dualq_bound_runq(processor_t processor)
 162 {
 163         return &processor->runq;
 164 }
 165
 166 __attribute__((always_inline))
 167 static inline run_queue_t
 168 dualq_runq_for_thread(processor_t processor, thread_t thread)
 169 {
 170         if (thread->bound_processor == PROCESSOR_NULL) {
 171                 return dualq_main_runq(processor);
 172         } else {
 173                 assert(thread->bound_processor == processor);
 174                 return dualq_bound_runq(processor);
 175         }
 176 }
 177
 178 static sched_mode_t
 179 sched_dualq_initial_thread_sched_mode(task_t parent_task)
 180 {
 181         if (parent_task == kernel_task) {
 182                 return TH_MODE_FIXED;
 183         } else {
 184                 return TH_MODE_TIMESHARE;
 185         }
 186 }
 187
 188 static void
 189 sched_dualq_processor_init(processor_t processor)
 190 {
 191         run_queue_init(&processor->runq);
 192 }
 193
 194 static void
 195 sched_dualq_pset_init(processor_set_t pset)
 196 {
 197         run_queue_init(&pset->pset_runq);
 198 }
 199
 200 extern int sched_allow_NO_SMT_threads;
 201 static void
 202 sched_dualq_init(void)
 203 {
 204         sched_timeshare_init();
 205
 206         if (PE_parse_boot_argn("disable_NO_SMT_threads", NULL, 0)) {
 207                 sched_allow_NO_SMT_threads = 0;
 208         }
 209 }
 210
 211 static thread_t
 212 sched_dualq_choose_thread(
 213         processor_t      processor,
 214         int              priority,
 215         __unused ast_t            reason)
 216 {
 217         run_queue_t main_runq  = dualq_main_runq(processor);
 218         run_queue_t bound_runq = dualq_bound_runq(processor);
 219         run_queue_t chosen_runq;
 220
 221         if (bound_runq->highq < priority &&
 222             main_runq->highq < priority) {
 223                 return THREAD_NULL;
 224         }
 225
 226         if (bound_runq->count && main_runq->count) {
 227                 if (bound_runq->highq >= main_runq->highq) {
 228                         chosen_runq = bound_runq;
 229                 } else {
 230                         chosen_runq = main_runq;
 231                 }
 232         } else if (bound_runq->count) {
 233                 chosen_runq = bound_runq;
 234         } else if (main_runq->count) {
 235                 chosen_runq = main_runq;
 236         } else {
 237                 return THREAD_NULL;
 238         }
 239
 240         if (chosen_runq == bound_runq) {
 241                 return run_queue_dequeue(chosen_runq, SCHED_HEADQ);
 242         }
 243
 244         if (processor->is_SMT) {
 245                 thread_t potential_thread = run_queue_peek(chosen_runq);
 246                 if (potential_thread == THREAD_NULL) {
 247                         return THREAD_NULL;
 248                 }
 249                 if (processor->processor_primary != processor) {
 250                         /*
 251                          * Secondary processor may not run a NO_SMT thread,
 252                          * nor any thread if the primary is running a NO_SMT thread.
 253                          */
 254                         if (thread_no_smt(potential_thread)) {
 255                                 processor->must_idle = true;
 256                                 return THREAD_NULL;
 257                         }
 258                         processor_t primary = processor->processor_primary;
 259                         if (primary->state == PROCESSOR_RUNNING) {
 260                                 if (processor_active_thread_no_smt(primary)) {
 261                                         processor->must_idle = true;
 262                                         return THREAD_NULL;
 263                                 }
 264                         }
 265                 } else if (processor->processor_secondary != PROCESSOR_NULL) {
 266                         processor_t secondary = processor->processor_secondary;
 267                         /*
 268                          * Primary processor may not run a NO_SMT thread if
 269                          * its secondary is running a bound thread.
 270                          */
 271                         if (secondary->state == PROCESSOR_RUNNING) {
 272                                 if (thread_no_smt(potential_thread) && secondary->current_is_bound) {
 273                                         processor->must_idle = true;
 274                                         return THREAD_NULL;
 275                                 }
 276                         }
 277                 }
 278         }
 279
 280         return run_queue_dequeue(chosen_runq, SCHED_HEADQ);
 281 }
 282
 283 static boolean_t
 284 sched_dualq_processor_enqueue(
 285         processor_t       processor,
 286         thread_t          thread,
 287         sched_options_t   options)
 288 {
 289         run_queue_t     rq = dualq_runq_for_thread(processor, thread);
 290         boolean_t       result;
 291
 292         result = run_queue_enqueue(rq, thread, options);
 293         thread->runq = processor;
 294
 295         return result;
 296 }
 297
 298 static boolean_t
 299 sched_dualq_processor_queue_empty(processor_t processor)
 300 {
 301         return dualq_main_runq(processor)->count == 0 &&
 302                dualq_bound_runq(processor)->count == 0;
 303 }
 304
 305 static ast_t
 306 sched_dualq_processor_csw_check(processor_t processor)
 307 {
 308         boolean_t       has_higher;
 309         int             pri;
 310
 311         if (sched_dualq_thread_avoid_processor(processor, current_thread())) {
 312                 return AST_PREEMPT | AST_URGENT;
 313         }
 314
 315         run_queue_t main_runq  = dualq_main_runq(processor);
 316         run_queue_t bound_runq = dualq_bound_runq(processor);
 317
 318         assert(processor->active_thread != NULL);
 319
 320         pri = MAX(main_runq->highq, bound_runq->highq);
 321
 322         if (processor->first_timeslice) {
 323                 has_higher = (pri > processor->current_pri);
 324         } else {
 325                 has_higher = (pri >= processor->current_pri);
 326         }
 327
 328         if (has_higher) {
 329                 if (main_runq->urgency > 0) {
 330                         return AST_PREEMPT | AST_URGENT;
 331                 }
 332
 333                 if (bound_runq->urgency > 0) {
 334                         return AST_PREEMPT | AST_URGENT;
 335                 }
 336
 337                 return AST_PREEMPT;
 338         }
 339
 340         return AST_NONE;
 341 }
 342
 343 static boolean_t
 344 sched_dualq_processor_queue_has_priority(processor_t    processor,
 345     int            priority,
 346     boolean_t      gte)
 347 {
 348         run_queue_t main_runq  = dualq_main_runq(processor);
 349         run_queue_t bound_runq = dualq_bound_runq(processor);
 350
 351         int qpri = MAX(main_runq->highq, bound_runq->highq);
 352
 353         if (gte) {
 354                 return qpri >= priority;
 355         } else {
 356                 return qpri > priority;
 357         }
 358 }
 359
 360 static int
 361 sched_dualq_runq_count(processor_t processor)
 362 {
 363         return dualq_main_runq(processor)->count + dualq_bound_runq(processor)->count;
 364 }
 365
 366 static uint64_t
 367 sched_dualq_runq_stats_count_sum(processor_t processor)
 368 {
 369         uint64_t bound_sum = dualq_bound_runq(processor)->runq_stats.count_sum;
 370
 371         if (processor->cpu_id == processor->processor_set->cpu_set_low) {
 372                 return bound_sum + dualq_main_runq(processor)->runq_stats.count_sum;
 373         } else {
 374                 return bound_sum;
 375         }
 376 }
 377 static int
 378 sched_dualq_processor_bound_count(processor_t processor)
 379 {
 380         return dualq_bound_runq(processor)->count;
 381 }
 382
 383 static void
 384 sched_dualq_processor_queue_shutdown(processor_t processor)
 385 {
 386         processor_set_t pset = processor->processor_set;
 387         run_queue_t     rq   = dualq_main_runq(processor);
 388         thread_t        thread;
 389         queue_head_t    tqueue;
 390
 391         /* We only need to migrate threads if this is the last active processor in the pset */
 392         if (pset->online_processor_count > 0) {
 393                 pset_unlock(pset);
 394                 return;
 395         }
 396
 397         queue_init(&tqueue);
 398
 399         while (rq->count > 0) {
 400                 thread = run_queue_dequeue(rq, SCHED_HEADQ);
 401                 enqueue_tail(&tqueue, &thread->runq_links);
 402         }
 403
 404         pset_unlock(pset);
 405
 406         qe_foreach_element_safe(thread, &tqueue, runq_links) {
 407                 remqueue(&thread->runq_links);
 408
 409                 thread_lock(thread);
 410
 411                 thread_setrun(thread, SCHED_TAILQ);
 412
 413                 thread_unlock(thread);
 414         }
 415 }
 416
 417 static boolean_t
 418 sched_dualq_processor_queue_remove(
 419         processor_t processor,
 420         thread_t    thread)
 421 {
 422         run_queue_t             rq;
 423         processor_set_t         pset = processor->processor_set;
 424
 425         pset_lock(pset);
 426
 427         rq = dualq_runq_for_thread(processor, thread);
 428
 429         if (processor == thread->runq) {
 430                 /*
 431                  * Thread is on a run queue and we have a lock on
 432                  * that run queue.
 433                  */
 434                 run_queue_remove(rq, thread);
 435         } else {
 436                 /*
 437                  * The thread left the run queue before we could
 438                  * lock the run queue.
 439                  */
 440                 assert(thread->runq == PROCESSOR_NULL);
 441                 processor = PROCESSOR_NULL;
 442         }
 443
 444         pset_unlock(pset);
 445
 446         return processor != PROCESSOR_NULL;
 447 }
 448
 449 static thread_t
 450 sched_dualq_steal_thread(processor_set_t pset)
 451 {
 452         processor_set_t cset = pset;
 453         processor_set_t nset = next_pset(cset);
 454         thread_t        thread;
 455
 456         while (nset != pset) {
 457                 pset_unlock(cset);
 458                 cset = nset;
 459                 pset_lock(cset);
 460
 461                 if (cset->pset_runq.count > 0) {
 462                         /* Need task_restrict logic here */
 463                         thread = run_queue_dequeue(&cset->pset_runq, SCHED_HEADQ);
 464                         pset_unlock(cset);
 465                         return thread;
 466                 }
 467
 468                 nset = next_pset(cset);
 469         }
 470
 471         pset_unlock(cset);
 472
 473         return THREAD_NULL;
 474 }
 475
 476 static void
 477 sched_dualq_thread_update_scan(sched_update_scan_context_t scan_context)
 478 {
 479         boolean_t               restart_needed = FALSE;
 480         processor_t             processor = processor_list;
 481         processor_set_t         pset;
 482         thread_t                thread;
 483         spl_t                   s;
 484
 485         /*
 486          *  We update the threads associated with each processor (bound and idle threads)
 487          *  and then update the threads in each pset runqueue.
 488          */
 489
 490         do {
 491                 do {
 492                         pset = processor->processor_set;
 493
 494                         s = splsched();
 495                         pset_lock(pset);
 496
 497                         restart_needed = runq_scan(dualq_bound_runq(processor), scan_context);
 498
 499                         pset_unlock(pset);
 500                         splx(s);
 501
 502                         if (restart_needed) {
 503                                 break;
 504                         }
 505
 506                         thread = processor->idle_thread;
 507                         if (thread != THREAD_NULL && thread->sched_stamp != sched_tick) {
 508                                 if (thread_update_add_thread(thread) == FALSE) {
 509                                         restart_needed = TRUE;
 510                                         break;
 511                                 }
 512                         }
 513                 } while ((processor = processor->processor_list) != NULL);
 514
 515                 /* Ok, we now have a collection of candidates -- fix them. */
 516                 thread_update_process_threads();
 517         } while (restart_needed);
 518
 519         pset = &pset0;
 520
 521         do {
 522                 do {
 523                         s = splsched();
 524                         pset_lock(pset);
 525
 526                         restart_needed = runq_scan(&pset->pset_runq, scan_context);
 527
 528                         pset_unlock(pset);
 529                         splx(s);
 530
 531                         if (restart_needed) {
 532                                 break;
 533                         }
 534                 } while ((pset = pset->pset_list) != NULL);
 535
 536                 /* Ok, we now have a collection of candidates -- fix them. */
 537                 thread_update_process_threads();
 538         } while (restart_needed);
 539 }
 540
 541 extern int sched_allow_rt_smt;
 542
 543 /* Return true if this thread should not continue running on this processor */
 544 static bool
 545 sched_dualq_thread_avoid_processor(processor_t processor, thread_t thread)
 546 {
 547         if (thread->bound_processor == processor) {
 548                 /* Thread is bound here */
 549                 return false;
 550         }
 551
 552         if (processor->processor_primary != processor) {
 553                 /*
 554                  * This is a secondary SMT processor.  If the primary is running
 555                  * a realtime thread, only allow realtime threads on the secondary.
 556                  */
 557                 processor_t primary = processor->processor_primary;
 558                 if ((primary->current_pri >= BASEPRI_RTQUEUES) && ((thread->sched_pri < BASEPRI_RTQUEUES) || !sched_allow_rt_smt)) {
 559                         return true;
 560                 }
 561
 562                 /* NO_SMT threads are not allowed on secondary processors */
 563                 if (thread_no_smt(thread)) {
 564                         return true;
 565                 }
 566
 567                 if (primary->state == PROCESSOR_RUNNING) {
 568                         if (processor_active_thread_no_smt(primary)) {
 569                                 /* No threads allowed on secondary if primary has NO_SMT */
 570                                 return true;
 571                         }
 572                 }
 573         }
 574
 575         if (processor->processor_secondary != PROCESSOR_NULL) {
 576                 /*
 577                  * This is a primary SMT processor.  If the secondary is running
 578                  * a bound thread, the primary may not run a NO_SMT thread.
 579                  */
 580                 processor_t secondary = processor->processor_secondary;
 581
 582                 if (secondary->state == PROCESSOR_RUNNING) {
 583                         if (secondary->current_is_bound && thread_no_smt(thread)) {
 584                                 return true;
 585                         }
 586                 }
 587         }
 588
 589         return false;
 590 }