1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18#include "sched.h"
19#include "pelt.h"
20
21struct dl_bandwidth def_dl_bandwidth;
22
23static inline struct task_struct *dl_task_of(struct sched_dl_entity *dl_se)
24{
25 return container_of(dl_se, struct task_struct, dl);
26}
27
28static inline struct rq *rq_of_dl_rq(struct dl_rq *dl_rq)
29{
30 return container_of(dl_rq, struct rq, dl);
31}
32
33static inline struct dl_rq *dl_rq_of_se(struct sched_dl_entity *dl_se)
34{
35 struct task_struct *p = dl_task_of(dl_se);
36 struct rq *rq = task_rq(p);
37
38 return &rq->dl;
39}
40
41static inline int on_dl_rq(struct sched_dl_entity *dl_se)
42{
43 return !RB_EMPTY_NODE(&dl_se->rb_node);
44}
45
46#ifdef CONFIG_SMP
47static inline struct dl_bw *dl_bw_of(int i)
48{
49 RCU_LOCKDEP_WARN(!rcu_read_lock_sched_held(),
50 "sched RCU must be held");
51 return &cpu_rq(i)->rd->dl_bw;
52}
53
54static inline int dl_bw_cpus(int i)
55{
56 struct root_domain *rd = cpu_rq(i)->rd;
57 int cpus = 0;
58
59 RCU_LOCKDEP_WARN(!rcu_read_lock_sched_held(),
60 "sched RCU must be held");
61 for_each_cpu_and(i, rd->span, cpu_active_mask)
62 cpus++;
63
64 return cpus;
65}
66#else
67static inline struct dl_bw *dl_bw_of(int i)
68{
69 return &cpu_rq(i)->dl.dl_bw;
70}
71
72static inline int dl_bw_cpus(int i)
73{
74 return 1;
75}
76#endif
77
78static inline
79void __add_running_bw(u64 dl_bw, struct dl_rq *dl_rq)
80{
81 u64 old = dl_rq->running_bw;
82
83 lockdep_assert_held(&(rq_of_dl_rq(dl_rq))->lock);
84 dl_rq->running_bw += dl_bw;
85 SCHED_WARN_ON(dl_rq->running_bw < old);
86 SCHED_WARN_ON(dl_rq->running_bw > dl_rq->this_bw);
87
88 cpufreq_update_util(rq_of_dl_rq(dl_rq), 0);
89}
90
91static inline
92void __sub_running_bw(u64 dl_bw, struct dl_rq *dl_rq)
93{
94 u64 old = dl_rq->running_bw;
95
96 lockdep_assert_held(&(rq_of_dl_rq(dl_rq))->lock);
97 dl_rq->running_bw -= dl_bw;
98 SCHED_WARN_ON(dl_rq->running_bw > old);
99 if (dl_rq->running_bw > old)
100 dl_rq->running_bw = 0;
101
102 cpufreq_update_util(rq_of_dl_rq(dl_rq), 0);
103}
104
105static inline
106void __add_rq_bw(u64 dl_bw, struct dl_rq *dl_rq)
107{
108 u64 old = dl_rq->this_bw;
109
110 lockdep_assert_held(&(rq_of_dl_rq(dl_rq))->lock);
111 dl_rq->this_bw += dl_bw;
112 SCHED_WARN_ON(dl_rq->this_bw < old);
113}
114
115static inline
116void __sub_rq_bw(u64 dl_bw, struct dl_rq *dl_rq)
117{
118 u64 old = dl_rq->this_bw;
119
120 lockdep_assert_held(&(rq_of_dl_rq(dl_rq))->lock);
121 dl_rq->this_bw -= dl_bw;
122 SCHED_WARN_ON(dl_rq->this_bw > old);
123 if (dl_rq->this_bw > old)
124 dl_rq->this_bw = 0;
125 SCHED_WARN_ON(dl_rq->running_bw > dl_rq->this_bw);
126}
127
128static inline
129void add_rq_bw(struct sched_dl_entity *dl_se, struct dl_rq *dl_rq)
130{
131 if (!dl_entity_is_special(dl_se))
132 __add_rq_bw(dl_se->dl_bw, dl_rq);
133}
134
135static inline
136void sub_rq_bw(struct sched_dl_entity *dl_se, struct dl_rq *dl_rq)
137{
138 if (!dl_entity_is_special(dl_se))
139 __sub_rq_bw(dl_se->dl_bw, dl_rq);
140}
141
142static inline
143void add_running_bw(struct sched_dl_entity *dl_se, struct dl_rq *dl_rq)
144{
145 if (!dl_entity_is_special(dl_se))
146 __add_running_bw(dl_se->dl_bw, dl_rq);
147}
148
149static inline
150void sub_running_bw(struct sched_dl_entity *dl_se, struct dl_rq *dl_rq)
151{
152 if (!dl_entity_is_special(dl_se))
153 __sub_running_bw(dl_se->dl_bw, dl_rq);
154}
155
156void dl_change_utilization(struct task_struct *p, u64 new_bw)
157{
158 struct rq *rq;
159
160 BUG_ON(p->dl.flags & SCHED_FLAG_SUGOV);
161
162 if (task_on_rq_queued(p))
163 return;
164
165 rq = task_rq(p);
166 if (p->dl.dl_non_contending) {
167 sub_running_bw(&p->dl, &rq->dl);
168 p->dl.dl_non_contending = 0;
169
170
171
172
173
174
175
176 if (hrtimer_try_to_cancel(&p->dl.inactive_timer) == 1)
177 put_task_struct(p);
178 }
179 __sub_rq_bw(p->dl.dl_bw, &rq->dl);
180 __add_rq_bw(new_bw, &rq->dl);
181}
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237static void task_non_contending(struct task_struct *p)
238{
239 struct sched_dl_entity *dl_se = &p->dl;
240 struct hrtimer *timer = &dl_se->inactive_timer;
241 struct dl_rq *dl_rq = dl_rq_of_se(dl_se);
242 struct rq *rq = rq_of_dl_rq(dl_rq);
243 s64 zerolag_time;
244
245
246
247
248
249 if (dl_se->dl_runtime == 0)
250 return;
251
252 if (dl_entity_is_special(dl_se))
253 return;
254
255 WARN_ON(dl_se->dl_non_contending);
256
257 zerolag_time = dl_se->deadline -
258 div64_long((dl_se->runtime * dl_se->dl_period),
259 dl_se->dl_runtime);
260
261
262
263
264
265 zerolag_time -= rq_clock(rq);
266
267
268
269
270
271 if ((zerolag_time < 0) || hrtimer_active(&dl_se->inactive_timer)) {
272 if (dl_task(p))
273 sub_running_bw(dl_se, dl_rq);
274 if (!dl_task(p) || p->state == TASK_DEAD) {
275 struct dl_bw *dl_b = dl_bw_of(task_cpu(p));
276
277 if (p->state == TASK_DEAD)
278 sub_rq_bw(&p->dl, &rq->dl);
279 raw_spin_lock(&dl_b->lock);
280 __dl_sub(dl_b, p->dl.dl_bw, dl_bw_cpus(task_cpu(p)));
281 __dl_clear_params(p);
282 raw_spin_unlock(&dl_b->lock);
283 }
284
285 return;
286 }
287
288 dl_se->dl_non_contending = 1;
289 get_task_struct(p);
290 hrtimer_start(timer, ns_to_ktime(zerolag_time), HRTIMER_MODE_REL);
291}
292
293static void task_contending(struct sched_dl_entity *dl_se, int flags)
294{
295 struct dl_rq *dl_rq = dl_rq_of_se(dl_se);
296
297
298
299
300
301 if (dl_se->dl_runtime == 0)
302 return;
303
304 if (flags & ENQUEUE_MIGRATED)
305 add_rq_bw(dl_se, dl_rq);
306
307 if (dl_se->dl_non_contending) {
308 dl_se->dl_non_contending = 0;
309
310
311
312
313
314
315
316 if (hrtimer_try_to_cancel(&dl_se->inactive_timer) == 1)
317 put_task_struct(dl_task_of(dl_se));
318 } else {
319
320
321
322
323
324
325
326 add_running_bw(dl_se, dl_rq);
327 }
328}
329
330static inline int is_leftmost(struct task_struct *p, struct dl_rq *dl_rq)
331{
332 struct sched_dl_entity *dl_se = &p->dl;
333
334 return dl_rq->root.rb_leftmost == &dl_se->rb_node;
335}
336
337void init_dl_bandwidth(struct dl_bandwidth *dl_b, u64 period, u64 runtime)
338{
339 raw_spin_lock_init(&dl_b->dl_runtime_lock);
340 dl_b->dl_period = period;
341 dl_b->dl_runtime = runtime;
342}
343
344void init_dl_bw(struct dl_bw *dl_b)
345{
346 raw_spin_lock_init(&dl_b->lock);
347 raw_spin_lock(&def_dl_bandwidth.dl_runtime_lock);
348 if (global_rt_runtime() == RUNTIME_INF)
349 dl_b->bw = -1;
350 else
351 dl_b->bw = to_ratio(global_rt_period(), global_rt_runtime());
352 raw_spin_unlock(&def_dl_bandwidth.dl_runtime_lock);
353 dl_b->total_bw = 0;
354}
355
356void init_dl_rq(struct dl_rq *dl_rq)
357{
358 dl_rq->root = RB_ROOT_CACHED;
359
360#ifdef CONFIG_SMP
361
362 dl_rq->earliest_dl.curr = dl_rq->earliest_dl.next = 0;
363
364 dl_rq->dl_nr_migratory = 0;
365 dl_rq->overloaded = 0;
366 dl_rq->pushable_dl_tasks_root = RB_ROOT_CACHED;
367#else
368 init_dl_bw(&dl_rq->dl_bw);
369#endif
370
371 dl_rq->running_bw = 0;
372 dl_rq->this_bw = 0;
373 init_dl_rq_bw_ratio(dl_rq);
374}
375
376#ifdef CONFIG_SMP
377
378static inline int dl_overloaded(struct rq *rq)
379{
380 return atomic_read(&rq->rd->dlo_count);
381}
382
383static inline void dl_set_overload(struct rq *rq)
384{
385 if (!rq->online)
386 return;
387
388 cpumask_set_cpu(rq->cpu, rq->rd->dlo_mask);
389
390
391
392
393
394
395 smp_wmb();
396 atomic_inc(&rq->rd->dlo_count);
397}
398
399static inline void dl_clear_overload(struct rq *rq)
400{
401 if (!rq->online)
402 return;
403
404 atomic_dec(&rq->rd->dlo_count);
405 cpumask_clear_cpu(rq->cpu, rq->rd->dlo_mask);
406}
407
408static void update_dl_migration(struct dl_rq *dl_rq)
409{
410 if (dl_rq->dl_nr_migratory && dl_rq->dl_nr_running > 1) {
411 if (!dl_rq->overloaded) {
412 dl_set_overload(rq_of_dl_rq(dl_rq));
413 dl_rq->overloaded = 1;
414 }
415 } else if (dl_rq->overloaded) {
416 dl_clear_overload(rq_of_dl_rq(dl_rq));
417 dl_rq->overloaded = 0;
418 }
419}
420
421static void inc_dl_migration(struct sched_dl_entity *dl_se, struct dl_rq *dl_rq)
422{
423 struct task_struct *p = dl_task_of(dl_se);
424
425 if (p->nr_cpus_allowed > 1)
426 dl_rq->dl_nr_migratory++;
427
428 update_dl_migration(dl_rq);
429}
430
431static void dec_dl_migration(struct sched_dl_entity *dl_se, struct dl_rq *dl_rq)
432{
433 struct task_struct *p = dl_task_of(dl_se);
434
435 if (p->nr_cpus_allowed > 1)
436 dl_rq->dl_nr_migratory--;
437
438 update_dl_migration(dl_rq);
439}
440
441
442
443
444
445static void enqueue_pushable_dl_task(struct rq *rq, struct task_struct *p)
446{
447 struct dl_rq *dl_rq = &rq->dl;
448 struct rb_node **link = &dl_rq->pushable_dl_tasks_root.rb_root.rb_node;
449 struct rb_node *parent = NULL;
450 struct task_struct *entry;
451 bool leftmost = true;
452
453 BUG_ON(!RB_EMPTY_NODE(&p->pushable_dl_tasks));
454
455 while (*link) {
456 parent = *link;
457 entry = rb_entry(parent, struct task_struct,
458 pushable_dl_tasks);
459 if (dl_entity_preempt(&p->dl, &entry->dl))
460 link = &parent->rb_left;
461 else {
462 link = &parent->rb_right;
463 leftmost = false;
464 }
465 }
466
467 if (leftmost)
468 dl_rq->earliest_dl.next = p->dl.deadline;
469
470 rb_link_node(&p->pushable_dl_tasks, parent, link);
471 rb_insert_color_cached(&p->pushable_dl_tasks,
472 &dl_rq->pushable_dl_tasks_root, leftmost);
473}
474
475static void dequeue_pushable_dl_task(struct rq *rq, struct task_struct *p)
476{
477 struct dl_rq *dl_rq = &rq->dl;
478
479 if (RB_EMPTY_NODE(&p->pushable_dl_tasks))
480 return;
481
482 if (dl_rq->pushable_dl_tasks_root.rb_leftmost == &p->pushable_dl_tasks) {
483 struct rb_node *next_node;
484
485 next_node = rb_next(&p->pushable_dl_tasks);
486 if (next_node) {
487 dl_rq->earliest_dl.next = rb_entry(next_node,
488 struct task_struct, pushable_dl_tasks)->dl.deadline;
489 }
490 }
491
492 rb_erase_cached(&p->pushable_dl_tasks, &dl_rq->pushable_dl_tasks_root);
493 RB_CLEAR_NODE(&p->pushable_dl_tasks);
494}
495
496static inline int has_pushable_dl_tasks(struct rq *rq)
497{
498 return !RB_EMPTY_ROOT(&rq->dl.pushable_dl_tasks_root.rb_root);
499}
500
501static int push_dl_task(struct rq *rq);
502
503static inline bool need_pull_dl_task(struct rq *rq, struct task_struct *prev)
504{
505 return dl_task(prev);
506}
507
508static DEFINE_PER_CPU(struct callback_head, dl_push_head);
509static DEFINE_PER_CPU(struct callback_head, dl_pull_head);
510
511static void push_dl_tasks(struct rq *);
512static void pull_dl_task(struct rq *);
513
514static inline void deadline_queue_push_tasks(struct rq *rq)
515{
516 if (!has_pushable_dl_tasks(rq))
517 return;
518
519 queue_balance_callback(rq, &per_cpu(dl_push_head, rq->cpu), push_dl_tasks);
520}
521
522static inline void deadline_queue_pull_task(struct rq *rq)
523{
524 queue_balance_callback(rq, &per_cpu(dl_pull_head, rq->cpu), pull_dl_task);
525}
526
527static struct rq *find_lock_later_rq(struct task_struct *task, struct rq *rq);
528
529static struct rq *dl_task_offline_migration(struct rq *rq, struct task_struct *p)
530{
531 struct rq *later_rq = NULL;
532
533 later_rq = find_lock_later_rq(p, rq);
534 if (!later_rq) {
535 int cpu;
536
537
538
539
540
541 cpu = cpumask_any_and(cpu_active_mask, p->cpus_ptr);
542 if (cpu >= nr_cpu_ids) {
543
544
545
546
547 BUG_ON(dl_bandwidth_enabled());
548
549
550
551
552
553
554 cpu = cpumask_any(cpu_active_mask);
555 }
556 later_rq = cpu_rq(cpu);
557 double_lock_balance(rq, later_rq);
558 }
559
560 set_task_cpu(p, later_rq->cpu);
561 double_unlock_balance(later_rq, rq);
562
563 return later_rq;
564}
565
566#else
567
568static inline
569void enqueue_pushable_dl_task(struct rq *rq, struct task_struct *p)
570{
571}
572
573static inline
574void dequeue_pushable_dl_task(struct rq *rq, struct task_struct *p)
575{
576}
577
578static inline
579void inc_dl_migration(struct sched_dl_entity *dl_se, struct dl_rq *dl_rq)
580{
581}
582
583static inline
584void dec_dl_migration(struct sched_dl_entity *dl_se, struct dl_rq *dl_rq)
585{
586}
587
588static inline bool need_pull_dl_task(struct rq *rq, struct task_struct *prev)
589{
590 return false;
591}
592
593static inline void pull_dl_task(struct rq *rq)
594{
595}
596
597static inline void deadline_queue_push_tasks(struct rq *rq)
598{
599}
600
601static inline void deadline_queue_pull_task(struct rq *rq)
602{
603}
604#endif
605
606static void enqueue_task_dl(struct rq *rq, struct task_struct *p, int flags);
607static void __dequeue_task_dl(struct rq *rq, struct task_struct *p, int flags);
608static void check_preempt_curr_dl(struct rq *rq, struct task_struct *p, int flags);
609
610
611
612
613
614
615
616
617
618
619
620
621
622static inline void setup_new_dl_entity(struct sched_dl_entity *dl_se)
623{
624 struct dl_rq *dl_rq = dl_rq_of_se(dl_se);
625 struct rq *rq = rq_of_dl_rq(dl_rq);
626
627 WARN_ON(dl_se->dl_boosted);
628 WARN_ON(dl_time_before(rq_clock(rq), dl_se->deadline));
629
630
631
632
633
634
635 if (dl_se->dl_throttled)
636 return;
637
638
639
640
641
642
643 dl_se->deadline = rq_clock(rq) + dl_se->dl_deadline;
644 dl_se->runtime = dl_se->dl_runtime;
645}
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665static void replenish_dl_entity(struct sched_dl_entity *dl_se,
666 struct sched_dl_entity *pi_se)
667{
668 struct dl_rq *dl_rq = dl_rq_of_se(dl_se);
669 struct rq *rq = rq_of_dl_rq(dl_rq);
670
671 BUG_ON(pi_se->dl_runtime <= 0);
672
673
674
675
676
677 if (dl_se->dl_deadline == 0) {
678 dl_se->deadline = rq_clock(rq) + pi_se->dl_deadline;
679 dl_se->runtime = pi_se->dl_runtime;
680 }
681
682 if (dl_se->dl_yielded && dl_se->runtime > 0)
683 dl_se->runtime = 0;
684
685
686
687
688
689
690
691 while (dl_se->runtime <= 0) {
692 dl_se->deadline += pi_se->dl_period;
693 dl_se->runtime += pi_se->dl_runtime;
694 }
695
696
697
698
699
700
701
702
703
704
705 if (dl_time_before(dl_se->deadline, rq_clock(rq))) {
706 printk_deferred_once("sched: DL replenish lagged too much\n");
707 dl_se->deadline = rq_clock(rq) + pi_se->dl_deadline;
708 dl_se->runtime = pi_se->dl_runtime;
709 }
710
711 if (dl_se->dl_yielded)
712 dl_se->dl_yielded = 0;
713 if (dl_se->dl_throttled)
714 dl_se->dl_throttled = 0;
715}
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741static bool dl_entity_overflow(struct sched_dl_entity *dl_se,
742 struct sched_dl_entity *pi_se, u64 t)
743{
744 u64 left, right;
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764 left = (pi_se->dl_deadline >> DL_SCALE) * (dl_se->runtime >> DL_SCALE);
765 right = ((dl_se->deadline - t) >> DL_SCALE) *
766 (pi_se->dl_runtime >> DL_SCALE);
767
768 return dl_time_before(right, left);
769}
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789static void
790update_dl_revised_wakeup(struct sched_dl_entity *dl_se, struct rq *rq)
791{
792 u64 laxity = dl_se->deadline - rq_clock(rq);
793
794
795
796
797
798
799
800 WARN_ON(dl_time_before(dl_se->deadline, rq_clock(rq)));
801
802 dl_se->runtime = (dl_se->dl_density * laxity) >> BW_SHIFT;
803}
804
805
806
807
808
809
810
811
812
813
814
815
816static inline bool dl_is_implicit(struct sched_dl_entity *dl_se)
817{
818 return dl_se->dl_deadline == dl_se->dl_period;
819}
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851static void update_dl_entity(struct sched_dl_entity *dl_se,
852 struct sched_dl_entity *pi_se)
853{
854 struct dl_rq *dl_rq = dl_rq_of_se(dl_se);
855 struct rq *rq = rq_of_dl_rq(dl_rq);
856
857 if (dl_time_before(dl_se->deadline, rq_clock(rq)) ||
858 dl_entity_overflow(dl_se, pi_se, rq_clock(rq))) {
859
860 if (unlikely(!dl_is_implicit(dl_se) &&
861 !dl_time_before(dl_se->deadline, rq_clock(rq)) &&
862 !dl_se->dl_boosted)){
863 update_dl_revised_wakeup(dl_se, rq);
864 return;
865 }
866
867 dl_se->deadline = rq_clock(rq) + pi_se->dl_deadline;
868 dl_se->runtime = pi_se->dl_runtime;
869 }
870}
871
872static inline u64 dl_next_period(struct sched_dl_entity *dl_se)
873{
874 return dl_se->deadline - dl_se->dl_deadline + dl_se->dl_period;
875}
876
877
878
879
880
881
882
883
884
885
886
887static int start_dl_timer(struct task_struct *p)
888{
889 struct sched_dl_entity *dl_se = &p->dl;
890 struct hrtimer *timer = &dl_se->dl_timer;
891 struct rq *rq = task_rq(p);
892 ktime_t now, act;
893 s64 delta;
894
895 lockdep_assert_held(&rq->lock);
896
897
898
899
900
901
902 act = ns_to_ktime(dl_next_period(dl_se));
903 now = hrtimer_cb_get_time(timer);
904 delta = ktime_to_ns(now) - rq_clock(rq);
905 act = ktime_add_ns(act, delta);
906
907
908
909
910
911
912 if (ktime_us_delta(act, now) < 0)
913 return 0;
914
915
916
917
918
919
920
921
922
923
924 if (!hrtimer_is_queued(timer)) {
925 get_task_struct(p);
926 hrtimer_start(timer, act, HRTIMER_MODE_ABS);
927 }
928
929 return 1;
930}
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945static enum hrtimer_restart dl_task_timer(struct hrtimer *timer)
946{
947 struct sched_dl_entity *dl_se = container_of(timer,
948 struct sched_dl_entity,
949 dl_timer);
950 struct task_struct *p = dl_task_of(dl_se);
951 struct rq_flags rf;
952 struct rq *rq;
953
954 rq = task_rq_lock(p, &rf);
955
956
957
958
959
960 if (!dl_task(p))
961 goto unlock;
962
963
964
965
966
967 if (dl_se->dl_boosted)
968 goto unlock;
969
970
971
972
973
974 if (!dl_se->dl_throttled)
975 goto unlock;
976
977 sched_clock_tick();
978 update_rq_clock(rq);
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994 if (!task_on_rq_queued(p)) {
995 replenish_dl_entity(dl_se, dl_se);
996 goto unlock;
997 }
998
999#ifdef CONFIG_SMP
1000 if (unlikely(!rq->online)) {
1001
1002
1003
1004
1005 lockdep_unpin_lock(&rq->lock, rf.cookie);
1006 rq = dl_task_offline_migration(rq, p);
1007 rf.cookie = lockdep_pin_lock(&rq->lock);
1008 update_rq_clock(rq);
1009
1010
1011
1012
1013
1014
1015 }
1016#endif
1017
1018 enqueue_task_dl(rq, p, ENQUEUE_REPLENISH);
1019 if (dl_task(rq->curr))
1020 check_preempt_curr_dl(rq, p, 0);
1021 else
1022 resched_curr(rq);
1023
1024#ifdef CONFIG_SMP
1025
1026
1027
1028
1029 if (has_pushable_dl_tasks(rq)) {
1030
1031
1032
1033
1034 rq_unpin_lock(rq, &rf);
1035 push_dl_task(rq);
1036 rq_repin_lock(rq, &rf);
1037 }
1038#endif
1039
1040unlock:
1041 task_rq_unlock(rq, p, &rf);
1042
1043
1044
1045
1046
1047 put_task_struct(p);
1048
1049 return HRTIMER_NORESTART;
1050}
1051
1052void init_dl_task_timer(struct sched_dl_entity *dl_se)
1053{
1054 struct hrtimer *timer = &dl_se->dl_timer;
1055
1056 hrtimer_init(timer, CLOCK_MONOTONIC, HRTIMER_MODE_REL);
1057 timer->function = dl_task_timer;
1058}
1059
1060
1061
1062
1063
1064
1065
1066
1067
1068
1069
1070
1071
1072
1073
1074
1075
1076
1077
1078static inline void dl_check_constrained_dl(struct sched_dl_entity *dl_se)
1079{
1080 struct task_struct *p = dl_task_of(dl_se);
1081 struct rq *rq = rq_of_dl_rq(dl_rq_of_se(dl_se));
1082
1083 if (dl_time_before(dl_se->deadline, rq_clock(rq)) &&
1084 dl_time_before(rq_clock(rq), dl_next_period(dl_se))) {
1085 if (unlikely(dl_se->dl_boosted || !start_dl_timer(p)))
1086 return;
1087 dl_se->dl_throttled = 1;
1088 if (dl_se->runtime > 0)
1089 dl_se->runtime = 0;
1090 }
1091}
1092
1093static
1094int dl_runtime_exceeded(struct sched_dl_entity *dl_se)
1095{
1096 return (dl_se->runtime <= 0);
1097}
1098
1099extern bool sched_rt_bandwidth_account(struct rt_rq *rt_rq);
1100
1101
1102
1103
1104
1105
1106
1107
1108
1109
1110
1111
1112
1113
1114
1115
1116
1117
1118
1119
1120static u64 grub_reclaim(u64 delta, struct rq *rq, struct sched_dl_entity *dl_se)
1121{
1122 u64 u_inact = rq->dl.this_bw - rq->dl.running_bw;
1123 u64 u_act;
1124 u64 u_act_min = (dl_se->dl_bw * rq->dl.bw_ratio) >> RATIO_SHIFT;
1125
1126
1127
1128
1129
1130
1131
1132
1133
1134 if (u_inact + rq->dl.extra_bw > BW_UNIT - u_act_min)
1135 u_act = u_act_min;
1136 else
1137 u_act = BW_UNIT - u_inact - rq->dl.extra_bw;
1138
1139 return (delta * u_act) >> BW_SHIFT;
1140}
1141
1142
1143
1144
1145
1146static void update_curr_dl(struct rq *rq)
1147{
1148 struct task_struct *curr = rq->curr;
1149 struct sched_dl_entity *dl_se = &curr->dl;
1150 u64 delta_exec, scaled_delta_exec;
1151 int cpu = cpu_of(rq);
1152 u64 now;
1153
1154 if (!dl_task(curr) || !on_dl_rq(dl_se))
1155 return;
1156
1157
1158
1159
1160
1161
1162
1163
1164
1165 now = rq_clock_task(rq);
1166 delta_exec = now - curr->se.exec_start;
1167 if (unlikely((s64)delta_exec <= 0)) {
1168 if (unlikely(dl_se->dl_yielded))
1169 goto throttle;
1170 return;
1171 }
1172
1173 schedstat_set(curr->se.statistics.exec_max,
1174 max(curr->se.statistics.exec_max, delta_exec));
1175
1176 curr->se.sum_exec_runtime += delta_exec;
1177 account_group_exec_runtime(curr, delta_exec);
1178
1179 curr->se.exec_start = now;
1180 cgroup_account_cputime(curr, delta_exec);
1181
1182 if (dl_entity_is_special(dl_se))
1183 return;
1184
1185
1186
1187
1188
1189
1190
1191
1192 if (unlikely(dl_se->flags & SCHED_FLAG_RECLAIM)) {
1193 scaled_delta_exec = grub_reclaim(delta_exec,
1194 rq,
1195 &curr->dl);
1196 } else {
1197 unsigned long scale_freq = arch_scale_freq_capacity(cpu);
1198 unsigned long scale_cpu = arch_scale_cpu_capacity(cpu);
1199
1200 scaled_delta_exec = cap_scale(delta_exec, scale_freq);
1201 scaled_delta_exec = cap_scale(scaled_delta_exec, scale_cpu);
1202 }
1203
1204 dl_se->runtime -= scaled_delta_exec;
1205
1206throttle:
1207 if (dl_runtime_exceeded(dl_se) || dl_se->dl_yielded) {
1208 dl_se->dl_throttled = 1;
1209
1210
1211 if (dl_runtime_exceeded(dl_se) &&
1212 (dl_se->flags & SCHED_FLAG_DL_OVERRUN))
1213 dl_se->dl_overrun = 1;
1214
1215 __dequeue_task_dl(rq, curr, 0);
1216 if (unlikely(dl_se->dl_boosted || !start_dl_timer(curr)))
1217 enqueue_task_dl(rq, curr, ENQUEUE_REPLENISH);
1218
1219 if (!is_leftmost(curr, &rq->dl))
1220 resched_curr(rq);
1221 }
1222
1223
1224
1225
1226
1227
1228
1229
1230
1231
1232
1233
1234 if (rt_bandwidth_enabled()) {
1235 struct rt_rq *rt_rq = &rq->rt;
1236
1237 raw_spin_lock(&rt_rq->rt_runtime_lock);
1238
1239
1240
1241
1242
1243 if (sched_rt_bandwidth_account(rt_rq))
1244 rt_rq->rt_time += delta_exec;
1245 raw_spin_unlock(&rt_rq->rt_runtime_lock);
1246 }
1247}
1248
1249static enum hrtimer_restart inactive_task_timer(struct hrtimer *timer)
1250{
1251 struct sched_dl_entity *dl_se = container_of(timer,
1252 struct sched_dl_entity,
1253 inactive_timer);
1254 struct task_struct *p = dl_task_of(dl_se);
1255 struct rq_flags rf;
1256 struct rq *rq;
1257
1258 rq = task_rq_lock(p, &rf);
1259
1260 sched_clock_tick();
1261 update_rq_clock(rq);
1262
1263 if (!dl_task(p) || p->state == TASK_DEAD) {
1264 struct dl_bw *dl_b = dl_bw_of(task_cpu(p));
1265
1266 if (p->state == TASK_DEAD && dl_se->dl_non_contending) {
1267 sub_running_bw(&p->dl, dl_rq_of_se(&p->dl));
1268 sub_rq_bw(&p->dl, dl_rq_of_se(&p->dl));
1269 dl_se->dl_non_contending = 0;
1270 }
1271
1272 raw_spin_lock(&dl_b->lock);
1273 __dl_sub(dl_b, p->dl.dl_bw, dl_bw_cpus(task_cpu(p)));
1274 raw_spin_unlock(&dl_b->lock);
1275 __dl_clear_params(p);
1276
1277 goto unlock;
1278 }
1279 if (dl_se->dl_non_contending == 0)
1280 goto unlock;
1281
1282 sub_running_bw(dl_se, &rq->dl);
1283 dl_se->dl_non_contending = 0;
1284unlock:
1285 task_rq_unlock(rq, p, &rf);
1286 put_task_struct(p);
1287
1288 return HRTIMER_NORESTART;
1289}
1290
1291void init_dl_inactive_task_timer(struct sched_dl_entity *dl_se)
1292{
1293 struct hrtimer *timer = &dl_se->inactive_timer;
1294
1295 hrtimer_init(timer, CLOCK_MONOTONIC, HRTIMER_MODE_REL);
1296 timer->function = inactive_task_timer;
1297}
1298
1299#ifdef CONFIG_SMP
1300
1301static void inc_dl_deadline(struct dl_rq *dl_rq, u64 deadline)
1302{
1303 struct rq *rq = rq_of_dl_rq(dl_rq);
1304
1305 if (dl_rq->earliest_dl.curr == 0 ||
1306 dl_time_before(deadline, dl_rq->earliest_dl.curr)) {
1307 dl_rq->earliest_dl.curr = deadline;
1308 cpudl_set(&rq->rd->cpudl, rq->cpu, deadline);
1309 }
1310}
1311
1312static void dec_dl_deadline(struct dl_rq *dl_rq, u64 deadline)
1313{
1314 struct rq *rq = rq_of_dl_rq(dl_rq);
1315
1316
1317
1318
1319
1320 if (!dl_rq->dl_nr_running) {
1321 dl_rq->earliest_dl.curr = 0;
1322 dl_rq->earliest_dl.next = 0;
1323 cpudl_clear(&rq->rd->cpudl, rq->cpu);
1324 } else {
1325 struct rb_node *leftmost = dl_rq->root.rb_leftmost;
1326 struct sched_dl_entity *entry;
1327
1328 entry = rb_entry(leftmost, struct sched_dl_entity, rb_node);
1329 dl_rq->earliest_dl.curr = entry->deadline;
1330 cpudl_set(&rq->rd->cpudl, rq->cpu, entry->deadline);
1331 }
1332}
1333
1334#else
1335
1336static inline void inc_dl_deadline(struct dl_rq *dl_rq, u64 deadline) {}
1337static inline void dec_dl_deadline(struct dl_rq *dl_rq, u64 deadline) {}
1338
1339#endif
1340
1341static inline
1342void inc_dl_tasks(struct sched_dl_entity *dl_se, struct dl_rq *dl_rq)
1343{
1344 int prio = dl_task_of(dl_se)->prio;
1345 u64 deadline = dl_se->deadline;
1346
1347 WARN_ON(!dl_prio(prio));
1348 dl_rq->dl_nr_running++;
1349 add_nr_running(rq_of_dl_rq(dl_rq), 1);
1350
1351 inc_dl_deadline(dl_rq, deadline);
1352 inc_dl_migration(dl_se, dl_rq);
1353}
1354
1355static inline
1356void dec_dl_tasks(struct sched_dl_entity *dl_se, struct dl_rq *dl_rq)
1357{
1358 int prio = dl_task_of(dl_se)->prio;
1359
1360 WARN_ON(!dl_prio(prio));
1361 WARN_ON(!dl_rq->dl_nr_running);
1362 dl_rq->dl_nr_running--;
1363 sub_nr_running(rq_of_dl_rq(dl_rq), 1);
1364
1365 dec_dl_deadline(dl_rq, dl_se->deadline);
1366 dec_dl_migration(dl_se, dl_rq);
1367}
1368
1369static void __enqueue_dl_entity(struct sched_dl_entity *dl_se)
1370{
1371 struct dl_rq *dl_rq = dl_rq_of_se(dl_se);
1372 struct rb_node **link = &dl_rq->root.rb_root.rb_node;
1373 struct rb_node *parent = NULL;
1374 struct sched_dl_entity *entry;
1375 int leftmost = 1;
1376
1377 BUG_ON(!RB_EMPTY_NODE(&dl_se->rb_node));
1378
1379 while (*link) {
1380 parent = *link;
1381 entry = rb_entry(parent, struct sched_dl_entity, rb_node);
1382 if (dl_time_before(dl_se->deadline, entry->deadline))
1383 link = &parent->rb_left;
1384 else {
1385 link = &parent->rb_right;
1386 leftmost = 0;
1387 }
1388 }
1389
1390 rb_link_node(&dl_se->rb_node, parent, link);
1391 rb_insert_color_cached(&dl_se->rb_node, &dl_rq->root, leftmost);
1392
1393 inc_dl_tasks(dl_se, dl_rq);
1394}
1395
1396static void __dequeue_dl_entity(struct sched_dl_entity *dl_se)
1397{
1398 struct dl_rq *dl_rq = dl_rq_of_se(dl_se);
1399
1400 if (RB_EMPTY_NODE(&dl_se->rb_node))
1401 return;
1402
1403 rb_erase_cached(&dl_se->rb_node, &dl_rq->root);
1404 RB_CLEAR_NODE(&dl_se->rb_node);
1405
1406 dec_dl_tasks(dl_se, dl_rq);
1407}
1408
1409static void
1410enqueue_dl_entity(struct sched_dl_entity *dl_se,
1411 struct sched_dl_entity *pi_se, int flags)
1412{
1413 BUG_ON(on_dl_rq(dl_se));
1414
1415
1416
1417
1418
1419
1420 if (flags & ENQUEUE_WAKEUP) {
1421 task_contending(dl_se, flags);
1422 update_dl_entity(dl_se, pi_se);
1423 } else if (flags & ENQUEUE_REPLENISH) {
1424 replenish_dl_entity(dl_se, pi_se);
1425 } else if ((flags & ENQUEUE_RESTORE) &&
1426 dl_time_before(dl_se->deadline,
1427 rq_clock(rq_of_dl_rq(dl_rq_of_se(dl_se))))) {
1428 setup_new_dl_entity(dl_se);
1429 }
1430
1431 __enqueue_dl_entity(dl_se);
1432}
1433
1434static void dequeue_dl_entity(struct sched_dl_entity *dl_se)
1435{
1436 __dequeue_dl_entity(dl_se);
1437}
1438
1439static void enqueue_task_dl(struct rq *rq, struct task_struct *p, int flags)
1440{
1441 struct task_struct *pi_task = rt_mutex_get_top_task(p);
1442 struct sched_dl_entity *pi_se = &p->dl;
1443
1444
1445
1446
1447
1448
1449
1450
1451
1452 if (pi_task && dl_prio(pi_task->normal_prio) && p->dl.dl_boosted) {
1453 pi_se = &pi_task->dl;
1454 } else if (!dl_prio(p->normal_prio)) {
1455
1456
1457
1458
1459
1460
1461
1462 BUG_ON(!p->dl.dl_boosted || flags != ENQUEUE_REPLENISH);
1463 return;
1464 }
1465
1466
1467
1468
1469
1470
1471
1472 if (!p->dl.dl_throttled && !dl_is_implicit(&p->dl))
1473 dl_check_constrained_dl(&p->dl);
1474
1475 if (p->on_rq == TASK_ON_RQ_MIGRATING || flags & ENQUEUE_RESTORE) {
1476 add_rq_bw(&p->dl, &rq->dl);
1477 add_running_bw(&p->dl, &rq->dl);
1478 }
1479
1480
1481
1482
1483
1484
1485
1486
1487
1488
1489
1490
1491
1492 if (p->dl.dl_throttled && !(flags & ENQUEUE_REPLENISH)) {
1493 if (flags & ENQUEUE_WAKEUP)
1494 task_contending(&p->dl, flags);
1495
1496 return;
1497 }
1498
1499 enqueue_dl_entity(&p->dl, pi_se, flags);
1500
1501 if (!task_current(rq, p) && p->nr_cpus_allowed > 1)
1502 enqueue_pushable_dl_task(rq, p);
1503}
1504
1505static void __dequeue_task_dl(struct rq *rq, struct task_struct *p, int flags)
1506{
1507 dequeue_dl_entity(&p->dl);
1508 dequeue_pushable_dl_task(rq, p);
1509}
1510
1511static void dequeue_task_dl(struct rq *rq, struct task_struct *p, int flags)
1512{
1513 update_curr_dl(rq);
1514 __dequeue_task_dl(rq, p, flags);
1515
1516 if (p->on_rq == TASK_ON_RQ_MIGRATING || flags & DEQUEUE_SAVE) {
1517 sub_running_bw(&p->dl, &rq->dl);
1518 sub_rq_bw(&p->dl, &rq->dl);
1519 }
1520
1521
1522
1523
1524
1525
1526
1527
1528
1529
1530 if (flags & DEQUEUE_SLEEP)
1531 task_non_contending(p);
1532}
1533
1534
1535
1536
1537
1538
1539
1540
1541
1542
1543
1544static void yield_task_dl(struct rq *rq)
1545{
1546
1547
1548
1549
1550
1551
1552 rq->curr->dl.dl_yielded = 1;
1553
1554 update_rq_clock(rq);
1555 update_curr_dl(rq);
1556
1557
1558
1559
1560
1561 rq_clock_skip_update(rq);
1562}
1563
1564#ifdef CONFIG_SMP
1565
1566static int find_later_rq(struct task_struct *task);
1567
1568static int
1569select_task_rq_dl(struct task_struct *p, int cpu, int sd_flag, int flags)
1570{
1571 struct task_struct *curr;
1572 struct rq *rq;
1573
1574 if (sd_flag != SD_BALANCE_WAKE)
1575 goto out;
1576
1577 rq = cpu_rq(cpu);
1578
1579 rcu_read_lock();
1580 curr = READ_ONCE(rq->curr);
1581
1582
1583
1584
1585
1586
1587
1588
1589
1590
1591 if (unlikely(dl_task(curr)) &&
1592 (curr->nr_cpus_allowed < 2 ||
1593 !dl_entity_preempt(&p->dl, &curr->dl)) &&
1594 (p->nr_cpus_allowed > 1)) {
1595 int target = find_later_rq(p);
1596
1597 if (target != -1 &&
1598 (dl_time_before(p->dl.deadline,
1599 cpu_rq(target)->dl.earliest_dl.curr) ||
1600 (cpu_rq(target)->dl.dl_nr_running == 0)))
1601 cpu = target;
1602 }
1603 rcu_read_unlock();
1604
1605out:
1606 return cpu;
1607}
1608
1609static void migrate_task_rq_dl(struct task_struct *p, int new_cpu __maybe_unused)
1610{
1611 struct rq *rq;
1612
1613 if (p->state != TASK_WAKING)
1614 return;
1615
1616 rq = task_rq(p);
1617
1618
1619
1620
1621
1622 raw_spin_lock(&rq->lock);
1623 if (p->dl.dl_non_contending) {
1624 sub_running_bw(&p->dl, &rq->dl);
1625 p->dl.dl_non_contending = 0;
1626
1627
1628
1629
1630
1631
1632
1633 if (hrtimer_try_to_cancel(&p->dl.inactive_timer) == 1)
1634 put_task_struct(p);
1635 }
1636 sub_rq_bw(&p->dl, &rq->dl);
1637 raw_spin_unlock(&rq->lock);
1638}
1639
1640static void check_preempt_equal_dl(struct rq *rq, struct task_struct *p)
1641{
1642
1643
1644
1645
1646 if (rq->curr->nr_cpus_allowed == 1 ||
1647 !cpudl_find(&rq->rd->cpudl, rq->curr, NULL))
1648 return;
1649
1650
1651
1652
1653
1654 if (p->nr_cpus_allowed != 1 &&
1655 cpudl_find(&rq->rd->cpudl, p, NULL))
1656 return;
1657
1658 resched_curr(rq);
1659}
1660
1661#endif
1662
1663
1664
1665
1666
1667static void check_preempt_curr_dl(struct rq *rq, struct task_struct *p,
1668 int flags)
1669{
1670 if (dl_entity_preempt(&p->dl, &rq->curr->dl)) {
1671 resched_curr(rq);
1672 return;
1673 }
1674
1675#ifdef CONFIG_SMP
1676
1677
1678
1679
1680 if ((p->dl.deadline == rq->curr->dl.deadline) &&
1681 !test_tsk_need_resched(rq->curr))
1682 check_preempt_equal_dl(rq, p);
1683#endif
1684}
1685
1686#ifdef CONFIG_SCHED_HRTICK
1687static void start_hrtick_dl(struct rq *rq, struct task_struct *p)
1688{
1689 hrtick_start(rq, p->dl.runtime);
1690}
1691#else
1692static void start_hrtick_dl(struct rq *rq, struct task_struct *p)
1693{
1694}
1695#endif
1696
1697static inline void set_next_task(struct rq *rq, struct task_struct *p)
1698{
1699 p->se.exec_start = rq_clock_task(rq);
1700
1701
1702 dequeue_pushable_dl_task(rq, p);
1703}
1704
1705static struct sched_dl_entity *pick_next_dl_entity(struct rq *rq,
1706 struct dl_rq *dl_rq)
1707{
1708 struct rb_node *left = rb_first_cached(&dl_rq->root);
1709
1710 if (!left)
1711 return NULL;
1712
1713 return rb_entry(left, struct sched_dl_entity, rb_node);
1714}
1715
1716static struct task_struct *
1717pick_next_task_dl(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)
1718{
1719 struct sched_dl_entity *dl_se;
1720 struct task_struct *p;
1721 struct dl_rq *dl_rq;
1722
1723 dl_rq = &rq->dl;
1724
1725 if (need_pull_dl_task(rq, prev)) {
1726
1727
1728
1729
1730
1731
1732 rq_unpin_lock(rq, rf);
1733 pull_dl_task(rq);
1734 rq_repin_lock(rq, rf);
1735
1736
1737
1738
1739
1740 if (rq->stop && task_on_rq_queued(rq->stop))
1741 return RETRY_TASK;
1742 }
1743
1744
1745
1746
1747
1748 if (prev->sched_class == &dl_sched_class)
1749 update_curr_dl(rq);
1750
1751 if (unlikely(!dl_rq->dl_nr_running))
1752 return NULL;
1753
1754 put_prev_task(rq, prev);
1755
1756 dl_se = pick_next_dl_entity(rq, dl_rq);
1757 BUG_ON(!dl_se);
1758
1759 p = dl_task_of(dl_se);
1760
1761 set_next_task(rq, p);
1762
1763 if (hrtick_enabled(rq))
1764 start_hrtick_dl(rq, p);
1765
1766 deadline_queue_push_tasks(rq);
1767
1768 if (rq->curr->sched_class != &dl_sched_class)
1769 update_dl_rq_load_avg(rq_clock_pelt(rq), rq, 0);
1770
1771 return p;
1772}
1773
1774static void put_prev_task_dl(struct rq *rq, struct task_struct *p)
1775{
1776 update_curr_dl(rq);
1777
1778 update_dl_rq_load_avg(rq_clock_pelt(rq), rq, 1);
1779 if (on_dl_rq(&p->dl) && p->nr_cpus_allowed > 1)
1780 enqueue_pushable_dl_task(rq, p);
1781}
1782
1783
1784
1785
1786
1787
1788
1789
1790
1791static void task_tick_dl(struct rq *rq, struct task_struct *p, int queued)
1792{
1793 update_curr_dl(rq);
1794
1795 update_dl_rq_load_avg(rq_clock_pelt(rq), rq, 1);
1796
1797
1798
1799
1800
1801 if (hrtick_enabled(rq) && queued && p->dl.runtime > 0 &&
1802 is_leftmost(p, &rq->dl))
1803 start_hrtick_dl(rq, p);
1804}
1805
1806static void task_fork_dl(struct task_struct *p)
1807{
1808
1809
1810
1811
1812}
1813
1814static void set_curr_task_dl(struct rq *rq)
1815{
1816 set_next_task(rq, rq->curr);
1817}
1818
1819#ifdef CONFIG_SMP
1820
1821
1822#define DL_MAX_TRIES 3
1823
1824static int pick_dl_task(struct rq *rq, struct task_struct *p, int cpu)
1825{
1826 if (!task_running(rq, p) &&
1827 cpumask_test_cpu(cpu, p->cpus_ptr))
1828 return 1;
1829 return 0;
1830}
1831
1832
1833
1834
1835
1836static struct task_struct *pick_earliest_pushable_dl_task(struct rq *rq, int cpu)
1837{
1838 struct rb_node *next_node = rq->dl.pushable_dl_tasks_root.rb_leftmost;
1839 struct task_struct *p = NULL;
1840
1841 if (!has_pushable_dl_tasks(rq))
1842 return NULL;
1843
1844next_node:
1845 if (next_node) {
1846 p = rb_entry(next_node, struct task_struct, pushable_dl_tasks);
1847
1848 if (pick_dl_task(rq, p, cpu))
1849 return p;
1850
1851 next_node = rb_next(next_node);
1852 goto next_node;
1853 }
1854
1855 return NULL;
1856}
1857
1858static DEFINE_PER_CPU(cpumask_var_t, local_cpu_mask_dl);
1859
1860static int find_later_rq(struct task_struct *task)
1861{
1862 struct sched_domain *sd;
1863 struct cpumask *later_mask = this_cpu_cpumask_var_ptr(local_cpu_mask_dl);
1864 int this_cpu = smp_processor_id();
1865 int cpu = task_cpu(task);
1866
1867
1868 if (unlikely(!later_mask))
1869 return -1;
1870
1871 if (task->nr_cpus_allowed == 1)
1872 return -1;
1873
1874
1875
1876
1877
1878 if (!cpudl_find(&task_rq(task)->rd->cpudl, task, later_mask))
1879 return -1;
1880
1881
1882
1883
1884
1885
1886
1887
1888
1889
1890
1891
1892
1893 if (cpumask_test_cpu(cpu, later_mask))
1894 return cpu;
1895
1896
1897
1898
1899 if (!cpumask_test_cpu(this_cpu, later_mask))
1900 this_cpu = -1;
1901
1902 rcu_read_lock();
1903 for_each_domain(cpu, sd) {
1904 if (sd->flags & SD_WAKE_AFFINE) {
1905 int best_cpu;
1906
1907
1908
1909
1910
1911 if (this_cpu != -1 &&
1912 cpumask_test_cpu(this_cpu, sched_domain_span(sd))) {
1913 rcu_read_unlock();
1914 return this_cpu;
1915 }
1916
1917 best_cpu = cpumask_first_and(later_mask,
1918 sched_domain_span(sd));
1919
1920
1921
1922
1923
1924
1925 if (best_cpu < nr_cpu_ids) {
1926 rcu_read_unlock();
1927 return best_cpu;
1928 }
1929 }
1930 }
1931 rcu_read_unlock();
1932
1933
1934
1935
1936
1937 if (this_cpu != -1)
1938 return this_cpu;
1939
1940 cpu = cpumask_any(later_mask);
1941 if (cpu < nr_cpu_ids)
1942 return cpu;
1943
1944 return -1;
1945}
1946
1947
1948static struct rq *find_lock_later_rq(struct task_struct *task, struct rq *rq)
1949{
1950 struct rq *later_rq = NULL;
1951 int tries;
1952 int cpu;
1953
1954 for (tries = 0; tries < DL_MAX_TRIES; tries++) {
1955 cpu = find_later_rq(task);
1956
1957 if ((cpu == -1) || (cpu == rq->cpu))
1958 break;
1959
1960 later_rq = cpu_rq(cpu);
1961
1962 if (later_rq->dl.dl_nr_running &&
1963 !dl_time_before(task->dl.deadline,
1964 later_rq->dl.earliest_dl.curr)) {
1965
1966
1967
1968
1969
1970 later_rq = NULL;
1971 break;
1972 }
1973
1974
1975 if (double_lock_balance(rq, later_rq)) {
1976 if (unlikely(task_rq(task) != rq ||
1977 !cpumask_test_cpu(later_rq->cpu, task->cpus_ptr) ||
1978 task_running(rq, task) ||
1979 !dl_task(task) ||
1980 !task_on_rq_queued(task))) {
1981 double_unlock_balance(rq, later_rq);
1982 later_rq = NULL;
1983 break;
1984 }
1985 }
1986
1987
1988
1989
1990
1991
1992 if (!later_rq->dl.dl_nr_running ||
1993 dl_time_before(task->dl.deadline,
1994 later_rq->dl.earliest_dl.curr))
1995 break;
1996
1997
1998 double_unlock_balance(rq, later_rq);
1999 later_rq = NULL;
2000 }
2001
2002 return later_rq;
2003}
2004
2005static struct task_struct *pick_next_pushable_dl_task(struct rq *rq)
2006{
2007 struct task_struct *p;
2008
2009 if (!has_pushable_dl_tasks(rq))
2010 return NULL;
2011
2012 p = rb_entry(rq->dl.pushable_dl_tasks_root.rb_leftmost,
2013 struct task_struct, pushable_dl_tasks);
2014
2015 BUG_ON(rq->cpu != task_cpu(p));
2016 BUG_ON(task_current(rq, p));
2017 BUG_ON(p->nr_cpus_allowed <= 1);
2018
2019 BUG_ON(!task_on_rq_queued(p));
2020 BUG_ON(!dl_task(p));
2021
2022 return p;
2023}
2024
2025
2026
2027
2028
2029
2030static int push_dl_task(struct rq *rq)
2031{
2032 struct task_struct *next_task;
2033 struct rq *later_rq;
2034 int ret = 0;
2035
2036 if (!rq->dl.overloaded)
2037 return 0;
2038
2039 next_task = pick_next_pushable_dl_task(rq);
2040 if (!next_task)
2041 return 0;
2042
2043retry:
2044 if (WARN_ON(next_task == rq->curr))
2045 return 0;
2046
2047
2048
2049
2050
2051
2052 if (dl_task(rq->curr) &&
2053 dl_time_before(next_task->dl.deadline, rq->curr->dl.deadline) &&
2054 rq->curr->nr_cpus_allowed > 1) {
2055 resched_curr(rq);
2056 return 0;
2057 }
2058
2059
2060 get_task_struct(next_task);
2061
2062
2063 later_rq = find_lock_later_rq(next_task, rq);
2064 if (!later_rq) {
2065 struct task_struct *task;
2066
2067
2068
2069
2070
2071
2072 task = pick_next_pushable_dl_task(rq);
2073 if (task == next_task) {
2074
2075
2076
2077
2078 goto out;
2079 }
2080
2081 if (!task)
2082
2083 goto out;
2084
2085 put_task_struct(next_task);
2086 next_task = task;
2087 goto retry;
2088 }
2089
2090 deactivate_task(rq, next_task, 0);
2091 set_task_cpu(next_task, later_rq->cpu);
2092
2093
2094
2095
2096
2097 update_rq_clock(later_rq);
2098 activate_task(later_rq, next_task, ENQUEUE_NOCLOCK);
2099 ret = 1;
2100
2101 resched_curr(later_rq);
2102
2103 double_unlock_balance(rq, later_rq);
2104
2105out:
2106 put_task_struct(next_task);
2107
2108 return ret;
2109}
2110
2111static void push_dl_tasks(struct rq *rq)
2112{
2113
2114 while (push_dl_task(rq))
2115 ;
2116}
2117
2118static void pull_dl_task(struct rq *this_rq)
2119{
2120 int this_cpu = this_rq->cpu, cpu;
2121 struct task_struct *p;
2122 bool resched = false;
2123 struct rq *src_rq;
2124 u64 dmin = LONG_MAX;
2125
2126 if (likely(!dl_overloaded(this_rq)))
2127 return;
2128
2129
2130
2131
2132
2133 smp_rmb();
2134
2135 for_each_cpu(cpu, this_rq->rd->dlo_mask) {
2136 if (this_cpu == cpu)
2137 continue;
2138
2139 src_rq = cpu_rq(cpu);
2140
2141
2142
2143
2144
2145 if (this_rq->dl.dl_nr_running &&
2146 dl_time_before(this_rq->dl.earliest_dl.curr,
2147 src_rq->dl.earliest_dl.next))
2148 continue;
2149
2150
2151 double_lock_balance(this_rq, src_rq);
2152
2153
2154
2155
2156
2157 if (src_rq->dl.dl_nr_running <= 1)
2158 goto skip;
2159
2160 p = pick_earliest_pushable_dl_task(src_rq, this_cpu);
2161
2162
2163
2164
2165
2166
2167 if (p && dl_time_before(p->dl.deadline, dmin) &&
2168 (!this_rq->dl.dl_nr_running ||
2169 dl_time_before(p->dl.deadline,
2170 this_rq->dl.earliest_dl.curr))) {
2171 WARN_ON(p == src_rq->curr);
2172 WARN_ON(!task_on_rq_queued(p));
2173
2174
2175
2176
2177
2178 if (dl_time_before(p->dl.deadline,
2179 src_rq->curr->dl.deadline))
2180 goto skip;
2181
2182 resched = true;
2183
2184 deactivate_task(src_rq, p, 0);
2185 set_task_cpu(p, this_cpu);
2186 activate_task(this_rq, p, 0);
2187 dmin = p->dl.deadline;
2188
2189
2190 }
2191skip:
2192 double_unlock_balance(this_rq, src_rq);
2193 }
2194
2195 if (resched)
2196 resched_curr(this_rq);
2197}
2198
2199
2200
2201
2202
2203static void task_woken_dl(struct rq *rq, struct task_struct *p)
2204{
2205 if (!task_running(rq, p) &&
2206 !test_tsk_need_resched(rq->curr) &&
2207 p->nr_cpus_allowed > 1 &&
2208 dl_task(rq->curr) &&
2209 (rq->curr->nr_cpus_allowed < 2 ||
2210 !dl_entity_preempt(&p->dl, &rq->curr->dl))) {
2211 push_dl_tasks(rq);
2212 }
2213}
2214
2215static void set_cpus_allowed_dl(struct task_struct *p,
2216 const struct cpumask *new_mask)
2217{
2218 struct root_domain *src_rd;
2219 struct rq *rq;
2220
2221 BUG_ON(!dl_task(p));
2222
2223 rq = task_rq(p);
2224 src_rd = rq->rd;
2225
2226
2227
2228
2229
2230
2231 if (!cpumask_intersects(src_rd->span, new_mask)) {
2232 struct dl_bw *src_dl_b;
2233
2234 src_dl_b = dl_bw_of(cpu_of(rq));
2235
2236
2237
2238
2239
2240 raw_spin_lock(&src_dl_b->lock);
2241 __dl_sub(src_dl_b, p->dl.dl_bw, dl_bw_cpus(task_cpu(p)));
2242 raw_spin_unlock(&src_dl_b->lock);
2243 }
2244
2245 set_cpus_allowed_common(p, new_mask);
2246}
2247
2248
2249static void rq_online_dl(struct rq *rq)
2250{
2251 if (rq->dl.overloaded)
2252 dl_set_overload(rq);
2253
2254 cpudl_set_freecpu(&rq->rd->cpudl, rq->cpu);
2255 if (rq->dl.dl_nr_running > 0)
2256 cpudl_set(&rq->rd->cpudl, rq->cpu, rq->dl.earliest_dl.curr);
2257}
2258
2259
2260static void rq_offline_dl(struct rq *rq)
2261{
2262 if (rq->dl.overloaded)
2263 dl_clear_overload(rq);
2264
2265 cpudl_clear(&rq->rd->cpudl, rq->cpu);
2266 cpudl_clear_freecpu(&rq->rd->cpudl, rq->cpu);
2267}
2268
2269void __init init_sched_dl_class(void)
2270{
2271 unsigned int i;
2272
2273 for_each_possible_cpu(i)
2274 zalloc_cpumask_var_node(&per_cpu(local_cpu_mask_dl, i),
2275 GFP_KERNEL, cpu_to_node(i));
2276}
2277
2278#endif
2279
2280static void switched_from_dl(struct rq *rq, struct task_struct *p)
2281{
2282
2283
2284
2285
2286
2287
2288
2289
2290 if (task_on_rq_queued(p) && p->dl.dl_runtime)
2291 task_non_contending(p);
2292
2293 if (!task_on_rq_queued(p)) {
2294
2295
2296
2297
2298
2299
2300 if (p->dl.dl_non_contending)
2301 sub_running_bw(&p->dl, &rq->dl);
2302 sub_rq_bw(&p->dl, &rq->dl);
2303 }
2304
2305
2306
2307
2308
2309
2310 if (p->dl.dl_non_contending)
2311 p->dl.dl_non_contending = 0;
2312
2313
2314
2315
2316
2317
2318 if (!task_on_rq_queued(p) || rq->dl.dl_nr_running)
2319 return;
2320
2321 deadline_queue_pull_task(rq);
2322}
2323
2324
2325
2326
2327
2328static void switched_to_dl(struct rq *rq, struct task_struct *p)
2329{
2330 if (hrtimer_try_to_cancel(&p->dl.inactive_timer) == 1)
2331 put_task_struct(p);
2332
2333
2334 if (!task_on_rq_queued(p)) {
2335 add_rq_bw(&p->dl, &rq->dl);
2336
2337 return;
2338 }
2339
2340 if (rq->curr != p) {
2341#ifdef CONFIG_SMP
2342 if (p->nr_cpus_allowed > 1 && rq->dl.overloaded)
2343 deadline_queue_push_tasks(rq);
2344#endif
2345 if (dl_task(rq->curr))
2346 check_preempt_curr_dl(rq, p, 0);
2347 else
2348 resched_curr(rq);
2349 }
2350}
2351
2352
2353
2354
2355
2356static void prio_changed_dl(struct rq *rq, struct task_struct *p,
2357 int oldprio)
2358{
2359 if (task_on_rq_queued(p) || rq->curr == p) {
2360#ifdef CONFIG_SMP
2361
2362
2363
2364
2365
2366
2367 if (!rq->dl.overloaded)
2368 deadline_queue_pull_task(rq);
2369
2370
2371
2372
2373
2374
2375 if (dl_time_before(rq->dl.earliest_dl.curr, p->dl.deadline))
2376 resched_curr(rq);
2377#else
2378
2379
2380
2381
2382
2383 resched_curr(rq);
2384#endif
2385 }
2386}
2387
2388const struct sched_class dl_sched_class = {
2389 .next = &rt_sched_class,
2390 .enqueue_task = enqueue_task_dl,
2391 .dequeue_task = dequeue_task_dl,
2392 .yield_task = yield_task_dl,
2393
2394 .check_preempt_curr = check_preempt_curr_dl,
2395
2396 .pick_next_task = pick_next_task_dl,
2397 .put_prev_task = put_prev_task_dl,
2398
2399#ifdef CONFIG_SMP
2400 .select_task_rq = select_task_rq_dl,
2401 .migrate_task_rq = migrate_task_rq_dl,
2402 .set_cpus_allowed = set_cpus_allowed_dl,
2403 .rq_online = rq_online_dl,
2404 .rq_offline = rq_offline_dl,
2405 .task_woken = task_woken_dl,
2406#endif
2407
2408 .set_curr_task = set_curr_task_dl,
2409 .task_tick = task_tick_dl,
2410 .task_fork = task_fork_dl,
2411
2412 .prio_changed = prio_changed_dl,
2413 .switched_from = switched_from_dl,
2414 .switched_to = switched_to_dl,
2415
2416 .update_curr = update_curr_dl,
2417};
2418
2419int sched_dl_global_validate(void)
2420{
2421 u64 runtime = global_rt_runtime();
2422 u64 period = global_rt_period();
2423 u64 new_bw = to_ratio(period, runtime);
2424 struct dl_bw *dl_b;
2425 int cpu, ret = 0;
2426 unsigned long flags;
2427
2428
2429
2430
2431
2432
2433
2434
2435
2436
2437 for_each_possible_cpu(cpu) {
2438 rcu_read_lock_sched();
2439 dl_b = dl_bw_of(cpu);
2440
2441 raw_spin_lock_irqsave(&dl_b->lock, flags);
2442 if (new_bw < dl_b->total_bw)
2443 ret = -EBUSY;
2444 raw_spin_unlock_irqrestore(&dl_b->lock, flags);
2445
2446 rcu_read_unlock_sched();
2447
2448 if (ret)
2449 break;
2450 }
2451
2452 return ret;
2453}
2454
2455void init_dl_rq_bw_ratio(struct dl_rq *dl_rq)
2456{
2457 if (global_rt_runtime() == RUNTIME_INF) {
2458 dl_rq->bw_ratio = 1 << RATIO_SHIFT;
2459 dl_rq->extra_bw = 1 << BW_SHIFT;
2460 } else {
2461 dl_rq->bw_ratio = to_ratio(global_rt_runtime(),
2462 global_rt_period()) >> (BW_SHIFT - RATIO_SHIFT);
2463 dl_rq->extra_bw = to_ratio(global_rt_period(),
2464 global_rt_runtime());
2465 }
2466}
2467
2468void sched_dl_do_global(void)
2469{
2470 u64 new_bw = -1;
2471 struct dl_bw *dl_b;
2472 int cpu;
2473 unsigned long flags;
2474
2475 def_dl_bandwidth.dl_period = global_rt_period();
2476 def_dl_bandwidth.dl_runtime = global_rt_runtime();
2477
2478 if (global_rt_runtime() != RUNTIME_INF)
2479 new_bw = to_ratio(global_rt_period(), global_rt_runtime());
2480
2481
2482
2483
2484 for_each_possible_cpu(cpu) {
2485 rcu_read_lock_sched();
2486 dl_b = dl_bw_of(cpu);
2487
2488 raw_spin_lock_irqsave(&dl_b->lock, flags);
2489 dl_b->bw = new_bw;
2490 raw_spin_unlock_irqrestore(&dl_b->lock, flags);
2491
2492 rcu_read_unlock_sched();
2493 init_dl_rq_bw_ratio(&cpu_rq(cpu)->dl);
2494 }
2495}
2496
2497
2498
2499
2500
2501
2502
2503
2504
2505int sched_dl_overflow(struct task_struct *p, int policy,
2506 const struct sched_attr *attr)
2507{
2508 struct dl_bw *dl_b = dl_bw_of(task_cpu(p));
2509 u64 period = attr->sched_period ?: attr->sched_deadline;
2510 u64 runtime = attr->sched_runtime;
2511 u64 new_bw = dl_policy(policy) ? to_ratio(period, runtime) : 0;
2512 int cpus, err = -1;
2513
2514 if (attr->sched_flags & SCHED_FLAG_SUGOV)
2515 return 0;
2516
2517
2518 if (new_bw == p->dl.dl_bw && task_has_dl_policy(p))
2519 return 0;
2520
2521
2522
2523
2524
2525
2526 raw_spin_lock(&dl_b->lock);
2527 cpus = dl_bw_cpus(task_cpu(p));
2528 if (dl_policy(policy) && !task_has_dl_policy(p) &&
2529 !__dl_overflow(dl_b, cpus, 0, new_bw)) {
2530 if (hrtimer_active(&p->dl.inactive_timer))
2531 __dl_sub(dl_b, p->dl.dl_bw, cpus);
2532 __dl_add(dl_b, new_bw, cpus);
2533 err = 0;
2534 } else if (dl_policy(policy) && task_has_dl_policy(p) &&
2535 !__dl_overflow(dl_b, cpus, p->dl.dl_bw, new_bw)) {
2536
2537
2538
2539
2540
2541
2542
2543 __dl_sub(dl_b, p->dl.dl_bw, cpus);
2544 __dl_add(dl_b, new_bw, cpus);
2545 dl_change_utilization(p, new_bw);
2546 err = 0;
2547 } else if (!dl_policy(policy) && task_has_dl_policy(p)) {
2548
2549
2550
2551
2552
2553 err = 0;
2554 }
2555 raw_spin_unlock(&dl_b->lock);
2556
2557 return err;
2558}
2559
2560
2561
2562
2563
2564
2565
2566
2567
2568void __setparam_dl(struct task_struct *p, const struct sched_attr *attr)
2569{
2570 struct sched_dl_entity *dl_se = &p->dl;
2571
2572 dl_se->dl_runtime = attr->sched_runtime;
2573 dl_se->dl_deadline = attr->sched_deadline;
2574 dl_se->dl_period = attr->sched_period ?: dl_se->dl_deadline;
2575 dl_se->flags = attr->sched_flags;
2576 dl_se->dl_bw = to_ratio(dl_se->dl_period, dl_se->dl_runtime);
2577 dl_se->dl_density = to_ratio(dl_se->dl_deadline, dl_se->dl_runtime);
2578}
2579
2580void __getparam_dl(struct task_struct *p, struct sched_attr *attr)
2581{
2582 struct sched_dl_entity *dl_se = &p->dl;
2583
2584 attr->sched_priority = p->rt_priority;
2585 attr->sched_runtime = dl_se->dl_runtime;
2586 attr->sched_deadline = dl_se->dl_deadline;
2587 attr->sched_period = dl_se->dl_period;
2588 attr->sched_flags = dl_se->flags;
2589}
2590
2591
2592
2593
2594
2595
2596
2597
2598
2599
2600
2601bool __checkparam_dl(const struct sched_attr *attr)
2602{
2603
2604 if (attr->sched_flags & SCHED_FLAG_SUGOV)
2605 return true;
2606
2607
2608 if (attr->sched_deadline == 0)
2609 return false;
2610
2611
2612
2613
2614
2615 if (attr->sched_runtime < (1ULL << DL_SCALE))
2616 return false;
2617
2618
2619
2620
2621
2622 if (attr->sched_deadline & (1ULL << 63) ||
2623 attr->sched_period & (1ULL << 63))
2624 return false;
2625
2626
2627 if ((attr->sched_period != 0 &&
2628 attr->sched_period < attr->sched_deadline) ||
2629 attr->sched_deadline < attr->sched_runtime)
2630 return false;
2631
2632 return true;
2633}
2634
2635
2636
2637
2638void __dl_clear_params(struct task_struct *p)
2639{
2640 struct sched_dl_entity *dl_se = &p->dl;
2641
2642 dl_se->dl_runtime = 0;
2643 dl_se->dl_deadline = 0;
2644 dl_se->dl_period = 0;
2645 dl_se->flags = 0;
2646 dl_se->dl_bw = 0;
2647 dl_se->dl_density = 0;
2648
2649 dl_se->dl_throttled = 0;
2650 dl_se->dl_yielded = 0;
2651 dl_se->dl_non_contending = 0;
2652 dl_se->dl_overrun = 0;
2653}
2654
2655bool dl_param_changed(struct task_struct *p, const struct sched_attr *attr)
2656{
2657 struct sched_dl_entity *dl_se = &p->dl;
2658
2659 if (dl_se->dl_runtime != attr->sched_runtime ||
2660 dl_se->dl_deadline != attr->sched_deadline ||
2661 dl_se->dl_period != attr->sched_period ||
2662 dl_se->flags != attr->sched_flags)
2663 return true;
2664
2665 return false;
2666}
2667
2668#ifdef CONFIG_SMP
2669int dl_task_can_attach(struct task_struct *p, const struct cpumask *cs_cpus_allowed)
2670{
2671 unsigned int dest_cpu;
2672 struct dl_bw *dl_b;
2673 bool overflow;
2674 int cpus, ret;
2675 unsigned long flags;
2676
2677 dest_cpu = cpumask_any_and(cpu_active_mask, cs_cpus_allowed);
2678
2679 rcu_read_lock_sched();
2680 dl_b = dl_bw_of(dest_cpu);
2681 raw_spin_lock_irqsave(&dl_b->lock, flags);
2682 cpus = dl_bw_cpus(dest_cpu);
2683 overflow = __dl_overflow(dl_b, cpus, 0, p->dl.dl_bw);
2684 if (overflow) {
2685 ret = -EBUSY;
2686 } else {
2687
2688
2689
2690
2691
2692
2693 __dl_add(dl_b, p->dl.dl_bw, cpus);
2694 ret = 0;
2695 }
2696 raw_spin_unlock_irqrestore(&dl_b->lock, flags);
2697 rcu_read_unlock_sched();
2698
2699 return ret;
2700}
2701
2702int dl_cpuset_cpumask_can_shrink(const struct cpumask *cur,
2703 const struct cpumask *trial)
2704{
2705 int ret = 1, trial_cpus;
2706 struct dl_bw *cur_dl_b;
2707 unsigned long flags;
2708
2709 rcu_read_lock_sched();
2710 cur_dl_b = dl_bw_of(cpumask_any(cur));
2711 trial_cpus = cpumask_weight(trial);
2712
2713 raw_spin_lock_irqsave(&cur_dl_b->lock, flags);
2714 if (cur_dl_b->bw != -1 &&
2715 cur_dl_b->bw * trial_cpus < cur_dl_b->total_bw)
2716 ret = 0;
2717 raw_spin_unlock_irqrestore(&cur_dl_b->lock, flags);
2718 rcu_read_unlock_sched();
2719
2720 return ret;
2721}
2722
2723bool dl_cpu_busy(unsigned int cpu)
2724{
2725 unsigned long flags;
2726 struct dl_bw *dl_b;
2727 bool overflow;
2728 int cpus;
2729
2730 rcu_read_lock_sched();
2731 dl_b = dl_bw_of(cpu);
2732 raw_spin_lock_irqsave(&dl_b->lock, flags);
2733 cpus = dl_bw_cpus(cpu);
2734 overflow = __dl_overflow(dl_b, cpus, 0, 0);
2735 raw_spin_unlock_irqrestore(&dl_b->lock, flags);
2736 rcu_read_unlock_sched();
2737
2738 return overflow;
2739}
2740#endif
2741
2742#ifdef CONFIG_SCHED_DEBUG
2743void print_dl_stats(struct seq_file *m, int cpu)
2744{
2745 print_dl_rq(m, cpu, &cpu_rq(cpu)->dl);
2746}
2747#endif
2748