xnu-3789.70.16.tar.gz
[apple/xnu.git] / osfmk / kern / sched_grrr.c
CommitLineData
6d2010ae 1/*
39037602 2 * Copyright (c) 2009-2016 Apple Inc. All rights reserved.
6d2010ae
A
3 *
4 * @APPLE_OSREFERENCE_LICENSE_HEADER_START@
39037602 5 *
6d2010ae
A
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.
39037602 14 *
6d2010ae
A
15 * Please obtain a copy of the License at
16 * http://www.opensource.apple.com/apsl/ and read it before using this file.
39037602 17 *
6d2010ae
A
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.
39037602 25 *
6d2010ae
A
26 * @APPLE_OSREFERENCE_LICENSE_HEADER_END@
27 */
28
29#include <mach/mach_types.h>
30#include <mach/machine.h>
31#include <mach/policy.h>
32#include <mach/sync_policy.h>
33#include <mach/thread_act.h>
34
35#include <machine/machine_routines.h>
36#include <machine/sched_param.h>
37#include <machine/machine_cpu.h>
38
39#include <kern/kern_types.h>
40#include <kern/clock.h>
41#include <kern/counters.h>
42#include <kern/cpu_number.h>
43#include <kern/cpu_data.h>
44#include <kern/debug.h>
6d2010ae
A
45#include <kern/macro_help.h>
46#include <kern/machine.h>
47#include <kern/misc_protos.h>
48#include <kern/processor.h>
49#include <kern/queue.h>
50#include <kern/sched.h>
51#include <kern/sched_prim.h>
52#include <kern/syscall_subr.h>
53#include <kern/task.h>
54#include <kern/thread.h>
6d2010ae
A
55
56#include <vm/pmap.h>
57#include <vm/vm_kern.h>
58#include <vm/vm_map.h>
59
60#include <mach/sdt.h>
61
62#include <sys/kdebug.h>
63
64#if defined(CONFIG_SCHED_GRRR_CORE)
65
66static void
67grrr_priority_mapping_init(void);
68
69static boolean_t
70grrr_enqueue(
71 grrr_run_queue_t rq,
72 thread_t thread);
39037602 73
6d2010ae
A
74static thread_t
75grrr_select(
76 grrr_run_queue_t rq);
77
78static void
79grrr_remove(
80 grrr_run_queue_t rq,
81 thread_t thread);
82
83
84static void
85grrr_sorted_list_insert_group(grrr_run_queue_t rq,
86 grrr_group_t group);
87
88static void
89grrr_rescale_work(grrr_run_queue_t rq);
90
91static void
92grrr_runqueue_init(grrr_run_queue_t runq);
93
94/* Map Mach priorities to ones suitable for proportional sharing */
95static grrr_proportional_priority_t grrr_priority_mapping[NRQS];
96
97/* Map each proportional priority to its group */
98static grrr_group_index_t grrr_group_mapping[NUM_GRRR_PROPORTIONAL_PRIORITIES];
99
100uint32_t grrr_rescale_tick;
101
102#endif /* defined(CONFIG_SCHED_GRRR_CORE) */
103
104#if defined(CONFIG_SCHED_GRRR)
105
106static void
107sched_grrr_init(void);
108
109static void
110sched_grrr_timebase_init(void);
111
112static void
113sched_grrr_processor_init(processor_t processor);
114
115static void
116sched_grrr_pset_init(processor_set_t pset);
117
118static void
119sched_grrr_maintenance_continuation(void);
120
121static thread_t
122sched_grrr_choose_thread(processor_t processor,
fe8ab488
A
123 int priority,
124 ast_t reason);
6d2010ae
A
125
126static thread_t
127sched_grrr_steal_thread(processor_set_t pset);
128
3e170ce0
A
129static int
130sched_grrr_compute_priority(thread_t thread);
6d2010ae
A
131
132static processor_t
133sched_grrr_choose_processor( processor_set_t pset,
134 processor_t processor,
135 thread_t thread);
136
137static boolean_t
138sched_grrr_processor_enqueue(
139 processor_t processor,
140 thread_t thread,
141 integer_t options);
142
143static void
144sched_grrr_processor_queue_shutdown(
145 processor_t processor);
146
147static boolean_t
148sched_grrr_processor_queue_remove(
149 processor_t processor,
150 thread_t thread);
151
152static boolean_t
153sched_grrr_processor_queue_empty(processor_t processor);
154
155static boolean_t
156sched_grrr_processor_queue_has_priority(processor_t processor,
157 int priority,
158 boolean_t gte);
159
160static boolean_t
161sched_grrr_priority_is_urgent(int priority);
162
163static ast_t
164sched_grrr_processor_csw_check(processor_t processor);
165
166static uint32_t
167sched_grrr_initial_quantum_size(thread_t thread);
168
169static sched_mode_t
170sched_grrr_initial_thread_sched_mode(task_t parent_task);
171
6d2010ae
A
172static boolean_t
173sched_grrr_can_update_priority(thread_t thread);
174
175static void
176sched_grrr_update_priority(thread_t thread);
177
178static void
179sched_grrr_lightweight_update_priority(thread_t thread);
180
6d2010ae
A
181static int
182sched_grrr_processor_runq_count(processor_t processor);
183
184static uint64_t
185sched_grrr_processor_runq_stats_count_sum(processor_t processor);
186
fe8ab488
A
187static int
188sched_grrr_processor_bound_count(processor_t processor);
189
190static void
3e170ce0 191sched_grrr_thread_update_scan(sched_update_scan_context_t scan_context);
fe8ab488 192
6d2010ae 193const struct sched_dispatch_table sched_grrr_dispatch = {
3e170ce0 194 .sched_name = "grrr",
fe8ab488
A
195 .init = sched_grrr_init,
196 .timebase_init = sched_grrr_timebase_init,
197 .processor_init = sched_grrr_processor_init,
198 .pset_init = sched_grrr_pset_init,
199 .maintenance_continuation = sched_grrr_maintenance_continuation,
200 .choose_thread = sched_grrr_choose_thread,
3e170ce0 201 .steal_thread_enabled = FALSE,
fe8ab488 202 .steal_thread = sched_grrr_steal_thread,
3e170ce0 203 .compute_timeshare_priority = sched_grrr_compute_priority,
fe8ab488
A
204 .choose_processor = sched_grrr_choose_processor,
205 .processor_enqueue = sched_grrr_processor_enqueue,
206 .processor_queue_shutdown = sched_grrr_processor_queue_shutdown,
207 .processor_queue_remove = sched_grrr_processor_queue_remove,
208 .processor_queue_empty = sched_grrr_processor_queue_empty,
209 .priority_is_urgent = sched_grrr_priority_is_urgent,
210 .processor_csw_check = sched_grrr_processor_csw_check,
211 .processor_queue_has_priority = sched_grrr_processor_queue_has_priority,
212 .initial_quantum_size = sched_grrr_initial_quantum_size,
213 .initial_thread_sched_mode = sched_grrr_initial_thread_sched_mode,
214 .can_update_priority = sched_grrr_can_update_priority,
215 .update_priority = sched_grrr_update_priority,
216 .lightweight_update_priority = sched_grrr_lightweight_update_priority,
3e170ce0 217 .quantum_expire = sched_default_quantum_expire,
fe8ab488
A
218 .processor_runq_count = sched_grrr_processor_runq_count,
219 .processor_runq_stats_count_sum = sched_grrr_processor_runq_stats_count_sum,
fe8ab488
A
220 .processor_bound_count = sched_grrr_processor_bound_count,
221 .thread_update_scan = sched_grrr_thread_update_scan,
222 .direct_dispatch_to_idle_processors = TRUE,
3e170ce0
A
223 .multiple_psets_enabled = TRUE,
224 .sched_groups_enabled = FALSE,
6d2010ae
A
225};
226
6d2010ae
A
227extern int max_unsafe_quanta;
228
229static uint32_t grrr_quantum_us;
230static uint32_t grrr_quantum;
231
232static uint64_t sched_grrr_tick_deadline;
233
234static void
235sched_grrr_init(void)
236{
237 if (default_preemption_rate < 1)
238 default_preemption_rate = 100;
239 grrr_quantum_us = (1000 * 1000) / default_preemption_rate;
39037602 240
6d2010ae
A
241 printf("standard grrr timeslicing quantum is %d us\n", grrr_quantum_us);
242
243 grrr_priority_mapping_init();
244}
245
246static void
247sched_grrr_timebase_init(void)
248{
249 uint64_t abstime;
250
251 /* standard timeslicing quantum */
252 clock_interval_to_absolutetime_interval(
253 grrr_quantum_us, NSEC_PER_USEC, &abstime);
254 assert((abstime >> 32) == 0 && (uint32_t)abstime != 0);
255 grrr_quantum = (uint32_t)abstime;
39037602 256
6d2010ae
A
257 thread_depress_time = 1 * grrr_quantum;
258 default_timeshare_computation = grrr_quantum / 2;
259 default_timeshare_constraint = grrr_quantum;
39037602 260
6d2010ae
A
261 max_unsafe_computation = max_unsafe_quanta * grrr_quantum;
262 sched_safe_duration = 2 * max_unsafe_quanta * grrr_quantum;
263
264}
265
266static void
267sched_grrr_processor_init(processor_t processor)
268{
269 grrr_runqueue_init(&processor->grrr_runq);
270}
271
272static void
273sched_grrr_pset_init(processor_set_t pset __unused)
274{
275}
276
277static void
278sched_grrr_maintenance_continuation(void)
279{
280 uint64_t abstime = mach_absolute_time();
39037602 281
6d2010ae 282 grrr_rescale_tick++;
39037602 283
6d2010ae
A
284 /*
285 * Compute various averages.
286 */
39236c6e 287 compute_averages(1);
39037602 288
6d2010ae
A
289 if (sched_grrr_tick_deadline == 0)
290 sched_grrr_tick_deadline = abstime;
39037602 291
6d2010ae
A
292 clock_deadline_for_periodic_event(10*sched_one_second_interval, abstime,
293 &sched_grrr_tick_deadline);
39037602 294
6d2010ae
A
295 assert_wait_deadline((event_t)sched_grrr_maintenance_continuation, THREAD_UNINT, sched_grrr_tick_deadline);
296 thread_block((thread_continue_t)sched_grrr_maintenance_continuation);
297 /*NOTREACHED*/
298}
299
6d2010ae
A
300static thread_t
301sched_grrr_choose_thread(processor_t processor,
fe8ab488
A
302 int priority __unused,
303 ast_t reason __unused)
6d2010ae
A
304{
305 grrr_run_queue_t rq = &processor->grrr_runq;
39037602
A
306
307 return grrr_select(rq);
6d2010ae
A
308}
309
310static thread_t
311sched_grrr_steal_thread(processor_set_t pset)
312{
313 pset_unlock(pset);
39037602
A
314
315 return THREAD_NULL;
6d2010ae
A
316}
317
3e170ce0
A
318static int
319sched_grrr_compute_priority(thread_t thread)
6d2010ae 320{
3e170ce0 321 return thread->base_pri;
6d2010ae
A
322}
323
324static processor_t
325sched_grrr_choose_processor( processor_set_t pset,
326 processor_t processor,
327 thread_t thread)
328{
329 return choose_processor(pset, processor, thread);
330}
331
332static boolean_t
333sched_grrr_processor_enqueue(
334 processor_t processor,
335 thread_t thread,
336 integer_t options __unused)
337{
338 grrr_run_queue_t rq = &processor->grrr_runq;
339 boolean_t result;
39037602 340
6d2010ae 341 result = grrr_enqueue(rq, thread);
39037602 342
6d2010ae 343 thread->runq = processor;
39037602 344
6d2010ae
A
345 return result;
346}
347
348static void
349sched_grrr_processor_queue_shutdown(
350 processor_t processor)
351{
352 processor_set_t pset = processor->processor_set;
353 thread_t thread;
354 queue_head_t tqueue, bqueue;
39037602 355
6d2010ae
A
356 queue_init(&tqueue);
357 queue_init(&bqueue);
39037602 358
fe8ab488 359 while ((thread = sched_grrr_choose_thread(processor, IDLEPRI, AST_NONE)) != THREAD_NULL) {
6d2010ae
A
360 if (thread->bound_processor == PROCESSOR_NULL) {
361 enqueue_tail(&tqueue, (queue_entry_t)thread);
362 } else {
39037602 363 enqueue_tail(&bqueue, (queue_entry_t)thread);
6d2010ae
A
364 }
365 }
39037602 366
39236c6e 367 while ((thread = (thread_t)(void *)dequeue_head(&bqueue)) != THREAD_NULL) {
6d2010ae 368 sched_grrr_processor_enqueue(processor, thread, SCHED_TAILQ);
39037602
A
369 }
370
6d2010ae 371 pset_unlock(pset);
39037602 372
39236c6e 373 while ((thread = (thread_t)(void *)dequeue_head(&tqueue)) != THREAD_NULL) {
6d2010ae 374 thread_lock(thread);
39037602 375
6d2010ae 376 thread_setrun(thread, SCHED_TAILQ);
39037602 377
6d2010ae
A
378 thread_unlock(thread);
379 }
380}
381
382static boolean_t
383sched_grrr_processor_queue_remove(
384 processor_t processor,
385 thread_t thread)
386{
39037602
A
387 processor_set_t pset = processor->processor_set;
388
389 pset_lock(pset);
390
6d2010ae
A
391 if (processor == thread->runq) {
392 /*
393 * Thread is on a run queue and we have a lock on
394 * that run queue.
395 */
396 grrr_run_queue_t rq = &processor->grrr_runq;
397
398 grrr_remove(rq, thread);
399 } else {
400 /*
401 * The thread left the run queue before we could
39037602 402 * lock the run queue.
6d2010ae
A
403 */
404 assert(thread->runq == PROCESSOR_NULL);
39037602 405 processor = PROCESSOR_NULL;
6d2010ae 406 }
39037602
A
407
408 pset_unlock(pset);
409
410 return (processor != PROCESSOR_NULL);
6d2010ae 411}
39037602 412
6d2010ae
A
413static boolean_t
414sched_grrr_processor_queue_empty(processor_t processor __unused)
415{
416 boolean_t result;
39037602 417
6d2010ae 418 result = (processor->grrr_runq.count == 0);
39037602 419
6d2010ae
A
420 return result;
421}
422
423static boolean_t
424sched_grrr_processor_queue_has_priority(processor_t processor,
425 int priority,
426 boolean_t gte __unused)
427{
428 grrr_run_queue_t rq = &processor->grrr_runq;
429 unsigned int i;
430
431 i = grrr_group_mapping[grrr_priority_mapping[priority]];
432 for ( ; i < NUM_GRRR_GROUPS; i++) {
433 if (rq->groups[i].count > 0)
39037602 434 return TRUE;
6d2010ae 435 }
39037602
A
436
437 return FALSE;
6d2010ae
A
438}
439
440/* Implement sched_preempt_pri in code */
441static boolean_t
442sched_grrr_priority_is_urgent(int priority)
443{
444 if (priority <= BASEPRI_FOREGROUND)
445 return FALSE;
39037602 446
6d2010ae
A
447 if (priority < MINPRI_KERNEL)
448 return TRUE;
449
450 if (priority >= BASEPRI_PREEMPT)
451 return TRUE;
39037602 452
6d2010ae
A
453 return FALSE;
454}
455
456static ast_t
457sched_grrr_processor_csw_check(processor_t processor)
458{
459 int count;
39037602 460
6d2010ae 461 count = sched_grrr_processor_runq_count(processor);
39037602
A
462
463 if (count > 0)
6d2010ae 464 return AST_PREEMPT;
39037602 465
6d2010ae
A
466 return AST_NONE;
467}
468
469static uint32_t
470sched_grrr_initial_quantum_size(thread_t thread __unused)
471{
472 return grrr_quantum;
473}
474
475static sched_mode_t
476sched_grrr_initial_thread_sched_mode(task_t parent_task)
477{
478 if (parent_task == kernel_task)
479 return TH_MODE_FIXED;
480 else
39037602 481 return TH_MODE_TIMESHARE;
6d2010ae
A
482}
483
6d2010ae
A
484static boolean_t
485sched_grrr_can_update_priority(thread_t thread __unused)
486{
487 return FALSE;
488}
489
490static void
491sched_grrr_update_priority(thread_t thread __unused)
492{
39037602 493 return;
6d2010ae
A
494}
495
496static void
497sched_grrr_lightweight_update_priority(thread_t thread __unused)
498{
499 return;
500}
501
6d2010ae
A
502static int
503sched_grrr_processor_runq_count(processor_t processor)
504{
505 return processor->grrr_runq.count;
506}
507
508static uint64_t
509sched_grrr_processor_runq_stats_count_sum(processor_t processor)
510{
511 return processor->grrr_runq.runq_stats.count_sum;
512}
513
fe8ab488
A
514static int
515sched_grrr_processor_bound_count(__unused processor_t processor)
516{
517 return 0;
518}
519
520static void
3e170ce0 521sched_grrr_thread_update_scan(__unused sched_update_scan_context_t scan_context)
fe8ab488 522{
39037602 523 return;
fe8ab488
A
524}
525
6d2010ae
A
526#endif /* defined(CONFIG_SCHED_GRRR) */
527
528#if defined(CONFIG_SCHED_GRRR_CORE)
529
530static void
531grrr_priority_mapping_init(void)
532{
533 unsigned int i;
39037602 534
6d2010ae
A
535 /* Map 0->0 up to 10->20 */
536 for (i=0; i <= 10; i++) {
537 grrr_priority_mapping[i] = 2*i;
538 }
39037602 539
6d2010ae
A
540 /* Map user priorities 11->33 up to 51 -> 153 */
541 for (i=11; i <= 51; i++) {
542 grrr_priority_mapping[i] = 3*i;
543 }
39037602 544
6d2010ae
A
545 /* Map high priorities 52->180 up to 127->255 */
546 for (i=52; i <= 127; i++) {
547 grrr_priority_mapping[i] = 128 + i;
548 }
39037602 549
6d2010ae 550 for (i = 0; i < NUM_GRRR_PROPORTIONAL_PRIORITIES; i++) {
39037602
A
551
552#if 0
6d2010ae
A
553 unsigned j, k;
554 /* Calculate log(i); */
555 for (j=0, k=1; k <= i; j++, k *= 2);
556#endif
39037602 557
6d2010ae
A
558 /* Groups of 4 */
559 grrr_group_mapping[i] = i >> 2;
560 }
6d2010ae
A
561}
562
563static thread_t
564grrr_intragroup_schedule(grrr_group_t group)
565{
566 thread_t thread;
567
568 if (group->count == 0) {
569 return THREAD_NULL;
570 }
39037602 571
6d2010ae
A
572 thread = group->current_client;
573 if (thread == THREAD_NULL) {
39236c6e 574 thread = (thread_t)(void *)queue_first(&group->clients);
6d2010ae 575 }
39037602 576
6d2010ae 577 if (1 /* deficit */) {
39236c6e 578 group->current_client = (thread_t)(void *)queue_next((queue_entry_t)thread);
6d2010ae 579 if (queue_end(&group->clients, (queue_entry_t)group->current_client)) {
39236c6e 580 group->current_client = (thread_t)(void *)queue_first(&group->clients);
6d2010ae 581 }
39037602 582
6d2010ae
A
583 thread = group->current_client;
584 }
39037602 585
6d2010ae
A
586 return thread;
587}
588
589static thread_t
590grrr_intergroup_schedule(grrr_run_queue_t rq)
591{
592 thread_t thread;
593 grrr_group_t group;
39037602 594
6d2010ae
A
595 if (rq->count == 0) {
596 return THREAD_NULL;
597 }
39037602 598
6d2010ae 599 group = rq->current_group;
39037602 600
6d2010ae
A
601 if (group == GRRR_GROUP_NULL) {
602 group = (grrr_group_t)queue_first(&rq->sorted_group_list);
603 }
39037602 604
6d2010ae 605 thread = grrr_intragroup_schedule(group);
39037602 606
6d2010ae
A
607 if ((group->work >= (UINT32_MAX-256)) || (rq->last_rescale_tick != grrr_rescale_tick)) {
608 grrr_rescale_work(rq);
609 }
610 group->work++;
39037602 611
6d2010ae
A
612 if (queue_end(&rq->sorted_group_list, queue_next((queue_entry_t)group))) {
613 /* last group, go back to beginning */
614 group = (grrr_group_t)queue_first(&rq->sorted_group_list);
615 } else {
616 grrr_group_t nextgroup = (grrr_group_t)queue_next((queue_entry_t)group);
617 uint64_t orderleft, orderright;
39037602 618
6d2010ae
A
619 /*
620 * The well-ordering condition for intergroup selection is:
621 *
622 * (group->work+1) / (nextgroup->work+1) > (group->weight) / (nextgroup->weight)
623 *
624 * Multiply both sides by their denominators to avoid division
625 *
626 */
627 orderleft = (group->work + 1) * ((uint64_t)nextgroup->weight);
628 orderright = (nextgroup->work + 1) * ((uint64_t)group->weight);
629 if (orderleft > orderright) {
630 group = nextgroup;
631 } else {
632 group = (grrr_group_t)queue_first(&rq->sorted_group_list);
633 }
634 }
39037602 635
6d2010ae 636 rq->current_group = group;
39037602 637
6d2010ae
A
638 return thread;
639}
640
641static void
642grrr_runqueue_init(grrr_run_queue_t runq)
643{
644 grrr_group_index_t index;
39037602 645
6d2010ae 646 runq->count = 0;
39037602 647
6d2010ae
A
648 for (index = 0; index < NUM_GRRR_GROUPS; index++) {
649 unsigned int prisearch;
650
651 for (prisearch = 0;
652 prisearch < NUM_GRRR_PROPORTIONAL_PRIORITIES;
653 prisearch++) {
654 if (grrr_group_mapping[prisearch] == index) {
655 runq->groups[index].minpriority = (grrr_proportional_priority_t)prisearch;
656 break;
657 }
658 }
39037602 659
6d2010ae
A
660 runq->groups[index].index = index;
661
662 queue_init(&runq->groups[index].clients);
663 runq->groups[index].count = 0;
664 runq->groups[index].weight = 0;
665 runq->groups[index].work = 0;
666 runq->groups[index].current_client = THREAD_NULL;
667 }
39037602 668
6d2010ae
A
669 queue_init(&runq->sorted_group_list);
670 runq->weight = 0;
671 runq->current_group = GRRR_GROUP_NULL;
672}
673
674static void
675grrr_rescale_work(grrr_run_queue_t rq)
676{
677 grrr_group_index_t index;
678
679 /* avoid overflow by scaling by 1/8th */
680 for (index = 0; index < NUM_GRRR_GROUPS; index++) {
681 rq->groups[index].work >>= 3;
682 }
683
684 rq->last_rescale_tick = grrr_rescale_tick;
685}
686
687static boolean_t
688grrr_enqueue(
689 grrr_run_queue_t rq,
690 thread_t thread)
39037602 691{
6d2010ae
A
692 grrr_proportional_priority_t gpriority;
693 grrr_group_index_t gindex;
694 grrr_group_t group;
695
696 gpriority = grrr_priority_mapping[thread->sched_pri];
697 gindex = grrr_group_mapping[gpriority];
698 group = &rq->groups[gindex];
699
700#if 0
701 thread->grrr_deficit = 0;
702#endif
39037602 703
6d2010ae
A
704 if (group->count == 0) {
705 /* Empty group, this is the first client */
706 enqueue_tail(&group->clients, (queue_entry_t)thread);
707 group->count = 1;
708 group->weight = gpriority;
709 group->current_client = thread;
710 } else {
711 /* Insert before the current client */
712 if (group->current_client == THREAD_NULL ||
713 queue_first(&group->clients) == (queue_entry_t)group->current_client) {
714 enqueue_head(&group->clients, (queue_entry_t)thread);
715 } else {
716 insque((queue_entry_t)thread, queue_prev((queue_entry_t)group->current_client));
717 }
718 SCHED_STATS_RUNQ_CHANGE(&rq->runq_stats, rq->count);
719 group->count++;
720 group->weight += gpriority;
721
722 /* Since there was already a client, this is on the per-processor sorted list already */
723 remqueue((queue_entry_t)group);
724 }
39037602 725
6d2010ae
A
726 grrr_sorted_list_insert_group(rq, group);
727
728 rq->count++;
729 rq->weight += gpriority;
39037602
A
730
731 return FALSE;
6d2010ae
A
732}
733
734static thread_t
735grrr_select(grrr_run_queue_t rq)
736{
737 thread_t thread;
738
739 thread = grrr_intergroup_schedule(rq);
740 if (thread != THREAD_NULL) {
741 grrr_proportional_priority_t gpriority;
742 grrr_group_index_t gindex;
743 grrr_group_t group;
39037602 744
6d2010ae
A
745 gpriority = grrr_priority_mapping[thread->sched_pri];
746 gindex = grrr_group_mapping[gpriority];
747 group = &rq->groups[gindex];
39037602 748
6d2010ae
A
749 remqueue((queue_entry_t)thread);
750 SCHED_STATS_RUNQ_CHANGE(&rq->runq_stats, rq->count);
751 group->count--;
752 group->weight -= gpriority;
753 if (group->current_client == thread) {
754 group->current_client = THREAD_NULL;
755 }
39037602 756
6d2010ae
A
757 remqueue((queue_entry_t)group);
758 if (group->count == 0) {
759 if (rq->current_group == group) {
760 rq->current_group = GRRR_GROUP_NULL;
761 }
762 } else {
763 /* Need to re-insert in sorted location */
764 grrr_sorted_list_insert_group(rq, group);
765 }
39037602 766
6d2010ae
A
767 rq->count--;
768 rq->weight -= gpriority;
39037602 769
6d2010ae 770 thread->runq = PROCESSOR_NULL;
39037602
A
771 }
772
773 return thread;
6d2010ae
A
774}
775
776static void
777grrr_remove(
778 grrr_run_queue_t rq,
779 thread_t thread)
39037602 780{
6d2010ae
A
781 grrr_proportional_priority_t gpriority;
782 grrr_group_index_t gindex;
783 grrr_group_t group;
39037602 784
6d2010ae
A
785 gpriority = grrr_priority_mapping[thread->sched_pri];
786 gindex = grrr_group_mapping[gpriority];
787 group = &rq->groups[gindex];
39037602 788
6d2010ae
A
789 remqueue((queue_entry_t)thread);
790 SCHED_STATS_RUNQ_CHANGE(&rq->runq_stats, rq->count);
791 group->count--;
792 group->weight -= gpriority;
793 if (group->current_client == thread) {
794 group->current_client = THREAD_NULL;
795 }
39037602 796
6d2010ae
A
797 remqueue((queue_entry_t)group);
798 if (group->count == 0) {
799 if (rq->current_group == group) {
800 rq->current_group = GRRR_GROUP_NULL;
801 }
802 } else {
803 /* Need to re-insert in sorted location */
804 grrr_sorted_list_insert_group(rq, group);
805 }
39037602 806
6d2010ae
A
807 rq->count--;
808 rq->weight -= gpriority;
39037602 809
6d2010ae
A
810 thread->runq = PROCESSOR_NULL;
811}
812
813static void
814grrr_sorted_list_insert_group(grrr_run_queue_t rq,
815 grrr_group_t group)
816{
817 /* Simple insertion sort */
818 if (queue_empty(&rq->sorted_group_list)) {
819 enqueue_tail(&rq->sorted_group_list, (queue_entry_t)group);
820 } else {
821 grrr_group_t search_group;
39037602 822
6d2010ae
A
823 /* Start searching from the head (heaviest weight) for the first
824 * element less than us, so we can insert before it
825 */
826 search_group = (grrr_group_t)queue_first(&rq->sorted_group_list);
827 while (!queue_end(&rq->sorted_group_list, (queue_entry_t)search_group) ) {
39037602 828
6d2010ae
A
829 if (search_group->weight < group->weight) {
830 /* we should be before this */
831 search_group = (grrr_group_t)queue_prev((queue_entry_t)search_group);
832 break;
833 } if (search_group->weight == group->weight) {
834 /* Use group index as a tie breaker */
835 if (search_group->index < group->index) {
836 search_group = (grrr_group_t)queue_prev((queue_entry_t)search_group);
837 break;
838 }
839 }
39037602 840
6d2010ae
A
841 /* otherwise, our weight is too small, keep going */
842 search_group = (grrr_group_t)queue_next((queue_entry_t)search_group);
843 }
39037602 844
6d2010ae
A
845 if (queue_end(&rq->sorted_group_list, (queue_entry_t)search_group)) {
846 enqueue_tail(&rq->sorted_group_list, (queue_entry_t)group);
847 } else {
848 insque((queue_entry_t)group, (queue_entry_t)search_group);
849 }
850 }
851}
852
853#endif /* defined(CONFIG_SCHED_GRRR_CORE) */