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, integer_t options);
  60
  61 static boolean_t
  62 sched_dualq_processor_queue_remove(processor_t processor, thread_t thread);
  63
  64 static ast_t
  65 sched_dualq_processor_csw_check(processor_t processor);
  66
  67 static boolean_t
  68 sched_dualq_processor_queue_has_priority(processor_t processor, int priority, boolean_t gte);
  69
  70 static int
  71 sched_dualq_runq_count(processor_t processor);
  72
  73 static boolean_t
  74 sched_dualq_processor_queue_empty(processor_t processor);
  75
  76 static uint64_t
  77 sched_dualq_runq_stats_count_sum(processor_t processor);
  78
  79 static int
  80 sched_dualq_processor_bound_count(processor_t processor);
  81
  82 static void
  83 sched_dualq_pset_init(processor_set_t pset);
  84
  85 static void
  86 sched_dualq_processor_init(processor_t processor);
  87
  88 static thread_t
  89 sched_dualq_choose_thread(processor_t processor, int priority, ast_t reason);
  90
  91 static void
  92 sched_dualq_processor_queue_shutdown(processor_t processor);
  93
  94 static sched_mode_t
  95 sched_dualq_initial_thread_sched_mode(task_t parent_task);
  96
  97 const struct sched_dispatch_table sched_dualq_dispatch = {
  98         .sched_name                                     = "dualq",
  99         .init                                           = sched_dualq_init,
 100         .timebase_init                                  = sched_timeshare_timebase_init,
 101         .processor_init                                 = sched_dualq_processor_init,
 102         .pset_init                                      = sched_dualq_pset_init,
 103         .maintenance_continuation                       = sched_timeshare_maintenance_continue,
 104         .choose_thread                                  = sched_dualq_choose_thread,
 105         .steal_thread_enabled                           = TRUE,
 106         .steal_thread                                   = sched_dualq_steal_thread,
 107         .compute_timeshare_priority                     = sched_compute_timeshare_priority,
 108         .choose_processor                               = choose_processor,
 109         .processor_enqueue                              = sched_dualq_processor_enqueue,
 110         .processor_queue_shutdown                       = sched_dualq_processor_queue_shutdown,
 111         .processor_queue_remove                         = sched_dualq_processor_queue_remove,
 112         .processor_queue_empty                          = sched_dualq_processor_queue_empty,
 113         .priority_is_urgent                             = priority_is_urgent,
 114         .processor_csw_check                            = sched_dualq_processor_csw_check,
 115         .processor_queue_has_priority                   = sched_dualq_processor_queue_has_priority,
 116         .initial_quantum_size                           = sched_timeshare_initial_quantum_size,
 117         .initial_thread_sched_mode                      = sched_dualq_initial_thread_sched_mode,
 118         .can_update_priority                            = can_update_priority,
 119         .update_priority                                = update_priority,
 120         .lightweight_update_priority                    = lightweight_update_priority,
 121         .quantum_expire                                 = sched_default_quantum_expire,
 122         .processor_runq_count                           = sched_dualq_runq_count,
 123         .processor_runq_stats_count_sum                 = sched_dualq_runq_stats_count_sum,
 124         .processor_bound_count                          = sched_dualq_processor_bound_count,
 125         .thread_update_scan                             = sched_dualq_thread_update_scan,
 126         .direct_dispatch_to_idle_processors             = FALSE,
 127         .multiple_psets_enabled                         = TRUE,
 128         .sched_groups_enabled                           = FALSE,
 129 };
 130
 131 __attribute__((always_inline))
 132 static inline run_queue_t dualq_main_runq(processor_t processor)
 133 {
 134         return &processor->processor_set->pset_runq;
 135 }
 136
 137 __attribute__((always_inline))
 138 static inline run_queue_t dualq_bound_runq(processor_t processor)
 139 {
 140         return &processor->runq;
 141 }
 142
 143 __attribute__((always_inline))
 144 static inline run_queue_t dualq_runq_for_thread(processor_t processor, thread_t thread)
 145 {
 146         if (thread->bound_processor == PROCESSOR_NULL) {
 147                 return dualq_main_runq(processor);
 148         } else {
 149                 assert(thread->bound_processor == processor);
 150                 return dualq_bound_runq(processor);
 151         }
 152 }
 153
 154 static sched_mode_t
 155 sched_dualq_initial_thread_sched_mode(task_t parent_task)
 156 {
 157         if (parent_task == kernel_task)
 158                 return TH_MODE_FIXED;
 159         else
 160                 return TH_MODE_TIMESHARE;
 161 }
 162
 163 static void
 164 sched_dualq_processor_init(processor_t processor)
 165 {
 166         run_queue_init(&processor->runq);
 167 }
 168
 169 static void
 170 sched_dualq_pset_init(processor_set_t pset)
 171 {
 172         run_queue_init(&pset->pset_runq);
 173 }
 174
 175 static void
 176 sched_dualq_init(void)
 177 {
 178         sched_timeshare_init();
 179 }
 180
 181 static thread_t
 182 sched_dualq_choose_thread(
 183                           processor_t      processor,
 184                           int              priority,
 185                  __unused ast_t            reason)
 186 {
 187         run_queue_t main_runq  = dualq_main_runq(processor);
 188         run_queue_t bound_runq = dualq_bound_runq(processor);
 189         run_queue_t chosen_runq;
 190
 191         if (bound_runq->highq < priority &&
 192              main_runq->highq < priority)
 193                 return THREAD_NULL;
 194
 195         if (bound_runq->count && main_runq->count) {
 196                 if (bound_runq->highq >= main_runq->highq) {
 197                         chosen_runq = bound_runq;
 198                 } else {
 199                         chosen_runq = main_runq;
 200                 }
 201         } else if (bound_runq->count) {
 202                 chosen_runq = bound_runq;
 203         } else if (main_runq->count) {
 204                 chosen_runq = main_runq;
 205         } else {
 206                 return (THREAD_NULL);
 207         }
 208
 209         return run_queue_dequeue(chosen_runq, SCHED_HEADQ);
 210 }
 211
 212 static boolean_t
 213 sched_dualq_processor_enqueue(
 214                               processor_t       processor,
 215                               thread_t          thread,
 216                               integer_t         options)
 217 {
 218         run_queue_t     rq = dualq_runq_for_thread(processor, thread);
 219         boolean_t       result;
 220
 221         result = run_queue_enqueue(rq, thread, options);
 222         thread->runq = processor;
 223
 224         return (result);
 225 }
 226
 227 static boolean_t
 228 sched_dualq_processor_queue_empty(processor_t processor)
 229 {
 230         return dualq_main_runq(processor)->count  == 0 &&
 231                dualq_bound_runq(processor)->count == 0;
 232 }
 233
 234 static ast_t
 235 sched_dualq_processor_csw_check(processor_t processor)
 236 {
 237         boolean_t       has_higher;
 238         int             pri;
 239
 240         run_queue_t main_runq  = dualq_main_runq(processor);
 241         run_queue_t bound_runq = dualq_bound_runq(processor);
 242
 243         assert(processor->active_thread != NULL);
 244
 245         pri = MAX(main_runq->highq, bound_runq->highq);
 246
 247         if (processor->first_timeslice) {
 248                 has_higher = (pri > processor->current_pri);
 249         } else {
 250                 has_higher = (pri >= processor->current_pri);
 251         }
 252
 253         if (has_higher) {
 254                 if (main_runq->urgency > 0)
 255                         return (AST_PREEMPT | AST_URGENT);
 256
 257                 if (bound_runq->urgency > 0)
 258                         return (AST_PREEMPT | AST_URGENT);
 259
 260                 return AST_PREEMPT;
 261         }
 262
 263         return AST_NONE;
 264 }
 265
 266 static boolean_t
 267 sched_dualq_processor_queue_has_priority(processor_t    processor,
 268                                          int            priority,
 269                                          boolean_t      gte)
 270 {
 271         int qpri = MAX(dualq_main_runq(processor)->highq, dualq_bound_runq(processor)->highq);
 272
 273         if (gte)
 274                 return qpri >= priority;
 275         else
 276                 return qpri > priority;
 277 }
 278
 279 static int
 280 sched_dualq_runq_count(processor_t processor)
 281 {
 282         return dualq_main_runq(processor)->count + dualq_bound_runq(processor)->count;
 283 }
 284
 285 static uint64_t
 286 sched_dualq_runq_stats_count_sum(processor_t processor)
 287 {
 288         uint64_t bound_sum = dualq_bound_runq(processor)->runq_stats.count_sum;
 289
 290         if (processor->cpu_id == processor->processor_set->cpu_set_low)
 291                 return bound_sum + dualq_main_runq(processor)->runq_stats.count_sum;
 292         else
 293                 return bound_sum;
 294 }
 295 static int
 296 sched_dualq_processor_bound_count(processor_t processor)
 297 {
 298         return dualq_bound_runq(processor)->count;
 299 }
 300
 301 static void
 302 sched_dualq_processor_queue_shutdown(processor_t processor)
 303 {
 304         processor_set_t pset = processor->processor_set;
 305         run_queue_t     rq   = dualq_main_runq(processor);
 306         thread_t        thread;
 307         queue_head_t    tqueue;
 308
 309         /* We only need to migrate threads if this is the last active processor in the pset */
 310         if (pset->online_processor_count > 0) {
 311                 pset_unlock(pset);
 312                 return;
 313         }
 314
 315         queue_init(&tqueue);
 316
 317         while (rq->count > 0) {
 318                 thread = run_queue_dequeue(rq, SCHED_HEADQ);
 319                 enqueue_tail(&tqueue, (queue_entry_t)thread);
 320         }
 321
 322         pset_unlock(pset);
 323
 324         while ((thread = (thread_t)(void*)dequeue_head(&tqueue)) != THREAD_NULL) {
 325                 thread_lock(thread);
 326
 327                 thread_setrun(thread, SCHED_TAILQ);
 328
 329                 thread_unlock(thread);
 330         }
 331 }
 332
 333 static boolean_t
 334 sched_dualq_processor_queue_remove(
 335                                    processor_t processor,
 336                                    thread_t    thread)
 337 {
 338         run_queue_t             rq;
 339         processor_set_t         pset = processor->processor_set;
 340
 341         pset_lock(pset);
 342
 343         rq = dualq_runq_for_thread(processor, thread);
 344
 345         if (processor == thread->runq) {
 346                 /*
 347                  * Thread is on a run queue and we have a lock on
 348                  * that run queue.
 349                  */
 350                 run_queue_remove(rq, thread);
 351         }
 352         else {
 353                 /*
 354                  * The thread left the run queue before we could
 355                  * lock the run queue.
 356                  */
 357                 assert(thread->runq == PROCESSOR_NULL);
 358                 processor = PROCESSOR_NULL;
 359         }
 360
 361         pset_unlock(pset);
 362
 363         return (processor != PROCESSOR_NULL);
 364 }
 365
 366 static thread_t
 367 sched_dualq_steal_thread(processor_set_t pset)
 368 {
 369         processor_set_t nset, cset = pset;
 370         thread_t        thread;
 371
 372         do {
 373                 if (cset->pset_runq.count > 0) {
 374                         thread = run_queue_dequeue(&cset->pset_runq, SCHED_HEADQ);
 375                         pset_unlock(cset);
 376                         return (thread);
 377                 }
 378
 379                 nset = next_pset(cset);
 380
 381                 if (nset != pset) {
 382                         pset_unlock(cset);
 383
 384                         cset = nset;
 385                         pset_lock(cset);
 386                 }
 387         } while (nset != pset);
 388
 389         pset_unlock(cset);
 390
 391         return (THREAD_NULL);
 392 }
 393
 394 static void
 395 sched_dualq_thread_update_scan(sched_update_scan_context_t scan_context)
 396 {
 397         boolean_t               restart_needed = FALSE;
 398         processor_t             processor = processor_list;
 399         processor_set_t         pset;
 400         thread_t                thread;
 401         spl_t                   s;
 402
 403         /*
 404          *  We update the threads associated with each processor (bound and idle threads)
 405          *  and then update the threads in each pset runqueue.
 406          */
 407
 408         do {
 409                 do {
 410                         pset = processor->processor_set;
 411
 412                         s = splsched();
 413                         pset_lock(pset);
 414
 415                         restart_needed = runq_scan(dualq_bound_runq(processor), scan_context);
 416
 417                         pset_unlock(pset);
 418                         splx(s);
 419
 420                         if (restart_needed)
 421                                 break;
 422
 423                         thread = processor->idle_thread;
 424                         if (thread != THREAD_NULL && thread->sched_stamp != sched_tick) {
 425                                 if (thread_update_add_thread(thread) == FALSE) {
 426                                         restart_needed = TRUE;
 427                                         break;
 428                                 }
 429                         }
 430                 } while ((processor = processor->processor_list) != NULL);
 431
 432                 /* Ok, we now have a collection of candidates -- fix them. */
 433                 thread_update_process_threads();
 434
 435         } while (restart_needed);
 436
 437         pset = &pset0;
 438
 439         do {
 440                 do {
 441                         s = splsched();
 442                         pset_lock(pset);
 443
 444                         restart_needed = runq_scan(&pset->pset_runq, scan_context);
 445
 446                         pset_unlock(pset);
 447                         splx(s);
 448
 449                         if (restart_needed)
 450                                 break;
 451                 } while ((pset = pset->pset_list) != NULL);
 452
 453                 /* Ok, we now have a collection of candidates -- fix them. */
 454                 thread_update_process_threads();
 455
 456         } while (restart_needed);
 457 }
 458
 459