1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23#include <linux/latencytop.h>
24#include <linux/sched.h>
25#include <linux/cpumask.h>
26#include <linux/cpuidle.h>
27#include <linux/slab.h>
28#include <linux/profile.h>
29#include <linux/interrupt.h>
30#include <linux/mempolicy.h>
31#include <linux/migrate.h>
32#include <linux/task_work.h>
33
34#include <trace/events/sched.h>
35
36#include "sched.h"
37
38
39
40
41
42
43
44
45
46
47
48
49
50unsigned int sysctl_sched_latency = 6000000ULL;
51unsigned int normalized_sysctl_sched_latency = 6000000ULL;
52
53
54
55
56
57
58
59
60
61
62enum sched_tunable_scaling sysctl_sched_tunable_scaling
63 = SCHED_TUNABLESCALING_LOG;
64
65
66
67
68
69unsigned int sysctl_sched_min_granularity = 750000ULL;
70unsigned int normalized_sysctl_sched_min_granularity = 750000ULL;
71
72
73
74
75static unsigned int sched_nr_latency = 8;
76
77
78
79
80
81unsigned int sysctl_sched_child_runs_first __read_mostly;
82
83
84
85
86
87
88
89
90
91unsigned int sysctl_sched_wakeup_granularity = 1000000UL;
92unsigned int normalized_sysctl_sched_wakeup_granularity = 1000000UL;
93
94const_debug unsigned int sysctl_sched_migration_cost = 500000UL;
95
96
97
98
99
100
101unsigned int __read_mostly sysctl_sched_shares_window = 10000000UL;
102
103#ifdef CONFIG_CFS_BANDWIDTH
104
105
106
107
108
109
110
111
112
113
114unsigned int sysctl_sched_cfs_bandwidth_slice = 5000UL;
115#endif
116
117static inline void update_load_add(struct load_weight *lw, unsigned long inc)
118{
119 lw->weight += inc;
120 lw->inv_weight = 0;
121}
122
123static inline void update_load_sub(struct load_weight *lw, unsigned long dec)
124{
125 lw->weight -= dec;
126 lw->inv_weight = 0;
127}
128
129static inline void update_load_set(struct load_weight *lw, unsigned long w)
130{
131 lw->weight = w;
132 lw->inv_weight = 0;
133}
134
135
136
137
138
139
140
141
142
143
144static int get_update_sysctl_factor(void)
145{
146 unsigned int cpus = min_t(int, num_online_cpus(), 8);
147 unsigned int factor;
148
149 switch (sysctl_sched_tunable_scaling) {
150 case SCHED_TUNABLESCALING_NONE:
151 factor = 1;
152 break;
153 case SCHED_TUNABLESCALING_LINEAR:
154 factor = cpus;
155 break;
156 case SCHED_TUNABLESCALING_LOG:
157 default:
158 factor = 1 + ilog2(cpus);
159 break;
160 }
161
162 return factor;
163}
164
165static void update_sysctl(void)
166{
167 unsigned int factor = get_update_sysctl_factor();
168
169#define SET_SYSCTL(name) \
170 (sysctl_##name = (factor) * normalized_sysctl_##name)
171 SET_SYSCTL(sched_min_granularity);
172 SET_SYSCTL(sched_latency);
173 SET_SYSCTL(sched_wakeup_granularity);
174#undef SET_SYSCTL
175}
176
177void sched_init_granularity(void)
178{
179 update_sysctl();
180}
181
182#define WMULT_CONST (~0U)
183#define WMULT_SHIFT 32
184
185static void __update_inv_weight(struct load_weight *lw)
186{
187 unsigned long w;
188
189 if (likely(lw->inv_weight))
190 return;
191
192 w = scale_load_down(lw->weight);
193
194 if (BITS_PER_LONG > 32 && unlikely(w >= WMULT_CONST))
195 lw->inv_weight = 1;
196 else if (unlikely(!w))
197 lw->inv_weight = WMULT_CONST;
198 else
199 lw->inv_weight = WMULT_CONST / w;
200}
201
202
203
204
205
206
207
208
209
210
211
212
213
214static u64 __calc_delta(u64 delta_exec, unsigned long weight, struct load_weight *lw)
215{
216 u64 fact = scale_load_down(weight);
217 int shift = WMULT_SHIFT;
218
219 __update_inv_weight(lw);
220
221 if (unlikely(fact >> 32)) {
222 while (fact >> 32) {
223 fact >>= 1;
224 shift--;
225 }
226 }
227
228
229 fact = (u64)(u32)fact * lw->inv_weight;
230
231 while (fact >> 32) {
232 fact >>= 1;
233 shift--;
234 }
235
236 return mul_u64_u32_shr(delta_exec, fact, shift);
237}
238
239
240const struct sched_class fair_sched_class;
241
242
243
244
245
246#ifdef CONFIG_FAIR_GROUP_SCHED
247
248
249static inline struct rq *rq_of(struct cfs_rq *cfs_rq)
250{
251 return cfs_rq->rq;
252}
253
254
255#define entity_is_task(se) (!se->my_q)
256
257static inline struct task_struct *task_of(struct sched_entity *se)
258{
259#ifdef CONFIG_SCHED_DEBUG
260 WARN_ON_ONCE(!entity_is_task(se));
261#endif
262 return container_of(se, struct task_struct, se);
263}
264
265
266#define for_each_sched_entity(se) \
267 for (; se; se = se->parent)
268
269static inline struct cfs_rq *task_cfs_rq(struct task_struct *p)
270{
271 return p->se.cfs_rq;
272}
273
274
275static inline struct cfs_rq *cfs_rq_of(struct sched_entity *se)
276{
277 return se->cfs_rq;
278}
279
280
281static inline struct cfs_rq *group_cfs_rq(struct sched_entity *grp)
282{
283 return grp->my_q;
284}
285
286static void update_cfs_rq_blocked_load(struct cfs_rq *cfs_rq,
287 int force_update);
288
289static inline void list_add_leaf_cfs_rq(struct cfs_rq *cfs_rq)
290{
291 if (!cfs_rq->on_list) {
292
293
294
295
296
297
298 if (cfs_rq->tg->parent &&
299 cfs_rq->tg->parent->cfs_rq[cpu_of(rq_of(cfs_rq))]->on_list) {
300 list_add_rcu(&cfs_rq->leaf_cfs_rq_list,
301 &rq_of(cfs_rq)->leaf_cfs_rq_list);
302 } else {
303 list_add_tail_rcu(&cfs_rq->leaf_cfs_rq_list,
304 &rq_of(cfs_rq)->leaf_cfs_rq_list);
305 }
306
307 cfs_rq->on_list = 1;
308
309 update_cfs_rq_blocked_load(cfs_rq, 0);
310 }
311}
312
313static inline void list_del_leaf_cfs_rq(struct cfs_rq *cfs_rq)
314{
315 if (cfs_rq->on_list) {
316 list_del_rcu(&cfs_rq->leaf_cfs_rq_list);
317 cfs_rq->on_list = 0;
318 }
319}
320
321
322#define for_each_leaf_cfs_rq(rq, cfs_rq) \
323 list_for_each_entry_rcu(cfs_rq, &rq->leaf_cfs_rq_list, leaf_cfs_rq_list)
324
325
326static inline struct cfs_rq *
327is_same_group(struct sched_entity *se, struct sched_entity *pse)
328{
329 if (se->cfs_rq == pse->cfs_rq)
330 return se->cfs_rq;
331
332 return NULL;
333}
334
335static inline struct sched_entity *parent_entity(struct sched_entity *se)
336{
337 return se->parent;
338}
339
340static void
341find_matching_se(struct sched_entity **se, struct sched_entity **pse)
342{
343 int se_depth, pse_depth;
344
345
346
347
348
349
350
351
352
353 se_depth = (*se)->depth;
354 pse_depth = (*pse)->depth;
355
356 while (se_depth > pse_depth) {
357 se_depth--;
358 *se = parent_entity(*se);
359 }
360
361 while (pse_depth > se_depth) {
362 pse_depth--;
363 *pse = parent_entity(*pse);
364 }
365
366 while (!is_same_group(*se, *pse)) {
367 *se = parent_entity(*se);
368 *pse = parent_entity(*pse);
369 }
370}
371
372#else
373
374static inline struct task_struct *task_of(struct sched_entity *se)
375{
376 return container_of(se, struct task_struct, se);
377}
378
379static inline struct rq *rq_of(struct cfs_rq *cfs_rq)
380{
381 return container_of(cfs_rq, struct rq, cfs);
382}
383
384#define entity_is_task(se) 1
385
386#define for_each_sched_entity(se) \
387 for (; se; se = NULL)
388
389static inline struct cfs_rq *task_cfs_rq(struct task_struct *p)
390{
391 return &task_rq(p)->cfs;
392}
393
394static inline struct cfs_rq *cfs_rq_of(struct sched_entity *se)
395{
396 struct task_struct *p = task_of(se);
397 struct rq *rq = task_rq(p);
398
399 return &rq->cfs;
400}
401
402
403static inline struct cfs_rq *group_cfs_rq(struct sched_entity *grp)
404{
405 return NULL;
406}
407
408static inline void list_add_leaf_cfs_rq(struct cfs_rq *cfs_rq)
409{
410}
411
412static inline void list_del_leaf_cfs_rq(struct cfs_rq *cfs_rq)
413{
414}
415
416#define for_each_leaf_cfs_rq(rq, cfs_rq) \
417 for (cfs_rq = &rq->cfs; cfs_rq; cfs_rq = NULL)
418
419static inline struct sched_entity *parent_entity(struct sched_entity *se)
420{
421 return NULL;
422}
423
424static inline void
425find_matching_se(struct sched_entity **se, struct sched_entity **pse)
426{
427}
428
429#endif
430
431static __always_inline
432void account_cfs_rq_runtime(struct cfs_rq *cfs_rq, u64 delta_exec);
433
434
435
436
437
438static inline u64 max_vruntime(u64 max_vruntime, u64 vruntime)
439{
440 s64 delta = (s64)(vruntime - max_vruntime);
441 if (delta > 0)
442 max_vruntime = vruntime;
443
444 return max_vruntime;
445}
446
447static inline u64 min_vruntime(u64 min_vruntime, u64 vruntime)
448{
449 s64 delta = (s64)(vruntime - min_vruntime);
450 if (delta < 0)
451 min_vruntime = vruntime;
452
453 return min_vruntime;
454}
455
456static inline int entity_before(struct sched_entity *a,
457 struct sched_entity *b)
458{
459 return (s64)(a->vruntime - b->vruntime) < 0;
460}
461
462static void update_min_vruntime(struct cfs_rq *cfs_rq)
463{
464 u64 vruntime = cfs_rq->min_vruntime;
465
466 if (cfs_rq->curr)
467 vruntime = cfs_rq->curr->vruntime;
468
469 if (cfs_rq->rb_leftmost) {
470 struct sched_entity *se = rb_entry(cfs_rq->rb_leftmost,
471 struct sched_entity,
472 run_node);
473
474 if (!cfs_rq->curr)
475 vruntime = se->vruntime;
476 else
477 vruntime = min_vruntime(vruntime, se->vruntime);
478 }
479
480
481 cfs_rq->min_vruntime = max_vruntime(cfs_rq->min_vruntime, vruntime);
482#ifndef CONFIG_64BIT
483 smp_wmb();
484 cfs_rq->min_vruntime_copy = cfs_rq->min_vruntime;
485#endif
486}
487
488
489
490
491static void __enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
492{
493 struct rb_node **link = &cfs_rq->tasks_timeline.rb_node;
494 struct rb_node *parent = NULL;
495 struct sched_entity *entry;
496 int leftmost = 1;
497
498
499
500
501 while (*link) {
502 parent = *link;
503 entry = rb_entry(parent, struct sched_entity, run_node);
504
505
506
507
508 if (entity_before(se, entry)) {
509 link = &parent->rb_left;
510 } else {
511 link = &parent->rb_right;
512 leftmost = 0;
513 }
514 }
515
516
517
518
519
520 if (leftmost)
521 cfs_rq->rb_leftmost = &se->run_node;
522
523 rb_link_node(&se->run_node, parent, link);
524 rb_insert_color(&se->run_node, &cfs_rq->tasks_timeline);
525}
526
527static void __dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
528{
529 if (cfs_rq->rb_leftmost == &se->run_node) {
530 struct rb_node *next_node;
531
532 next_node = rb_next(&se->run_node);
533 cfs_rq->rb_leftmost = next_node;
534 }
535
536 rb_erase(&se->run_node, &cfs_rq->tasks_timeline);
537}
538
539struct sched_entity *__pick_first_entity(struct cfs_rq *cfs_rq)
540{
541 struct rb_node *left = cfs_rq->rb_leftmost;
542
543 if (!left)
544 return NULL;
545
546 return rb_entry(left, struct sched_entity, run_node);
547}
548
549static struct sched_entity *__pick_next_entity(struct sched_entity *se)
550{
551 struct rb_node *next = rb_next(&se->run_node);
552
553 if (!next)
554 return NULL;
555
556 return rb_entry(next, struct sched_entity, run_node);
557}
558
559#ifdef CONFIG_SCHED_DEBUG
560struct sched_entity *__pick_last_entity(struct cfs_rq *cfs_rq)
561{
562 struct rb_node *last = rb_last(&cfs_rq->tasks_timeline);
563
564 if (!last)
565 return NULL;
566
567 return rb_entry(last, struct sched_entity, run_node);
568}
569
570
571
572
573
574int sched_proc_update_handler(struct ctl_table *table, int write,
575 void __user *buffer, size_t *lenp,
576 loff_t *ppos)
577{
578 int ret = proc_dointvec_minmax(table, write, buffer, lenp, ppos);
579 int factor = get_update_sysctl_factor();
580
581 if (ret || !write)
582 return ret;
583
584 sched_nr_latency = DIV_ROUND_UP(sysctl_sched_latency,
585 sysctl_sched_min_granularity);
586
587#define WRT_SYSCTL(name) \
588 (normalized_sysctl_##name = sysctl_##name / (factor))
589 WRT_SYSCTL(sched_min_granularity);
590 WRT_SYSCTL(sched_latency);
591 WRT_SYSCTL(sched_wakeup_granularity);
592#undef WRT_SYSCTL
593
594 return 0;
595}
596#endif
597
598
599
600
601static inline u64 calc_delta_fair(u64 delta, struct sched_entity *se)
602{
603 if (unlikely(se->load.weight != NICE_0_LOAD))
604 delta = __calc_delta(delta, NICE_0_LOAD, &se->load);
605
606 return delta;
607}
608
609
610
611
612
613
614
615
616
617static u64 __sched_period(unsigned long nr_running)
618{
619 u64 period = sysctl_sched_latency;
620 unsigned long nr_latency = sched_nr_latency;
621
622 if (unlikely(nr_running > nr_latency)) {
623 period = sysctl_sched_min_granularity;
624 period *= nr_running;
625 }
626
627 return period;
628}
629
630
631
632
633
634
635
636static u64 sched_slice(struct cfs_rq *cfs_rq, struct sched_entity *se)
637{
638 u64 slice = __sched_period(cfs_rq->nr_running + !se->on_rq);
639
640 for_each_sched_entity(se) {
641 struct load_weight *load;
642 struct load_weight lw;
643
644 cfs_rq = cfs_rq_of(se);
645 load = &cfs_rq->load;
646
647 if (unlikely(!se->on_rq)) {
648 lw = cfs_rq->load;
649
650 update_load_add(&lw, se->load.weight);
651 load = &lw;
652 }
653 slice = __calc_delta(slice, se->load.weight, load);
654 }
655 return slice;
656}
657
658
659
660
661
662
663static u64 sched_vslice(struct cfs_rq *cfs_rq, struct sched_entity *se)
664{
665 return calc_delta_fair(sched_slice(cfs_rq, se), se);
666}
667
668#ifdef CONFIG_SMP
669static int select_idle_sibling(struct task_struct *p, int cpu);
670static unsigned long task_h_load(struct task_struct *p);
671
672static inline void __update_task_entity_contrib(struct sched_entity *se);
673
674
675void init_task_runnable_average(struct task_struct *p)
676{
677 u32 slice;
678
679 p->se.avg.decay_count = 0;
680 slice = sched_slice(task_cfs_rq(p), &p->se) >> 10;
681 p->se.avg.runnable_avg_sum = slice;
682 p->se.avg.runnable_avg_period = slice;
683 __update_task_entity_contrib(&p->se);
684}
685#else
686void init_task_runnable_average(struct task_struct *p)
687{
688}
689#endif
690
691
692
693
694static void update_curr(struct cfs_rq *cfs_rq)
695{
696 struct sched_entity *curr = cfs_rq->curr;
697 u64 now = rq_clock_task(rq_of(cfs_rq));
698 u64 delta_exec;
699
700 if (unlikely(!curr))
701 return;
702
703 delta_exec = now - curr->exec_start;
704 if (unlikely((s64)delta_exec <= 0))
705 return;
706
707 curr->exec_start = now;
708
709 schedstat_set(curr->statistics.exec_max,
710 max(delta_exec, curr->statistics.exec_max));
711
712 curr->sum_exec_runtime += delta_exec;
713 schedstat_add(cfs_rq, exec_clock, delta_exec);
714
715 curr->vruntime += calc_delta_fair(delta_exec, curr);
716 update_min_vruntime(cfs_rq);
717
718 if (entity_is_task(curr)) {
719 struct task_struct *curtask = task_of(curr);
720
721 trace_sched_stat_runtime(curtask, delta_exec, curr->vruntime);
722 cpuacct_charge(curtask, delta_exec);
723 account_group_exec_runtime(curtask, delta_exec);
724 }
725
726 account_cfs_rq_runtime(cfs_rq, delta_exec);
727}
728
729static void update_curr_fair(struct rq *rq)
730{
731 update_curr(cfs_rq_of(&rq->curr->se));
732}
733
734static inline void
735update_stats_wait_start(struct cfs_rq *cfs_rq, struct sched_entity *se)
736{
737 schedstat_set(se->statistics.wait_start, rq_clock(rq_of(cfs_rq)));
738}
739
740
741
742
743static void update_stats_enqueue(struct cfs_rq *cfs_rq, struct sched_entity *se)
744{
745
746
747
748
749 if (se != cfs_rq->curr)
750 update_stats_wait_start(cfs_rq, se);
751}
752
753static void
754update_stats_wait_end(struct cfs_rq *cfs_rq, struct sched_entity *se)
755{
756 schedstat_set(se->statistics.wait_max, max(se->statistics.wait_max,
757 rq_clock(rq_of(cfs_rq)) - se->statistics.wait_start));
758 schedstat_set(se->statistics.wait_count, se->statistics.wait_count + 1);
759 schedstat_set(se->statistics.wait_sum, se->statistics.wait_sum +
760 rq_clock(rq_of(cfs_rq)) - se->statistics.wait_start);
761#ifdef CONFIG_SCHEDSTATS
762 if (entity_is_task(se)) {
763 trace_sched_stat_wait(task_of(se),
764 rq_clock(rq_of(cfs_rq)) - se->statistics.wait_start);
765 }
766#endif
767 schedstat_set(se->statistics.wait_start, 0);
768}
769
770static inline void
771update_stats_dequeue(struct cfs_rq *cfs_rq, struct sched_entity *se)
772{
773
774
775
776
777 if (se != cfs_rq->curr)
778 update_stats_wait_end(cfs_rq, se);
779}
780
781
782
783
784static inline void
785update_stats_curr_start(struct cfs_rq *cfs_rq, struct sched_entity *se)
786{
787
788
789
790 se->exec_start = rq_clock_task(rq_of(cfs_rq));
791}
792
793
794
795
796
797#ifdef CONFIG_NUMA_BALANCING
798
799
800
801
802
803unsigned int sysctl_numa_balancing_scan_period_min = 1000;
804unsigned int sysctl_numa_balancing_scan_period_max = 60000;
805
806
807unsigned int sysctl_numa_balancing_scan_size = 256;
808
809
810unsigned int sysctl_numa_balancing_scan_delay = 1000;
811
812static unsigned int task_nr_scan_windows(struct task_struct *p)
813{
814 unsigned long rss = 0;
815 unsigned long nr_scan_pages;
816
817
818
819
820
821
822 nr_scan_pages = sysctl_numa_balancing_scan_size << (20 - PAGE_SHIFT);
823 rss = get_mm_rss(p->mm);
824 if (!rss)
825 rss = nr_scan_pages;
826
827 rss = round_up(rss, nr_scan_pages);
828 return rss / nr_scan_pages;
829}
830
831
832#define MAX_SCAN_WINDOW 2560
833
834static unsigned int task_scan_min(struct task_struct *p)
835{
836 unsigned int scan_size = ACCESS_ONCE(sysctl_numa_balancing_scan_size);
837 unsigned int scan, floor;
838 unsigned int windows = 1;
839
840 if (scan_size < MAX_SCAN_WINDOW)
841 windows = MAX_SCAN_WINDOW / scan_size;
842 floor = 1000 / windows;
843
844 scan = sysctl_numa_balancing_scan_period_min / task_nr_scan_windows(p);
845 return max_t(unsigned int, floor, scan);
846}
847
848static unsigned int task_scan_max(struct task_struct *p)
849{
850 unsigned int smin = task_scan_min(p);
851 unsigned int smax;
852
853
854 smax = sysctl_numa_balancing_scan_period_max / task_nr_scan_windows(p);
855 return max(smin, smax);
856}
857
858static void account_numa_enqueue(struct rq *rq, struct task_struct *p)
859{
860 rq->nr_numa_running += (p->numa_preferred_nid != -1);
861 rq->nr_preferred_running += (p->numa_preferred_nid == task_node(p));
862}
863
864static void account_numa_dequeue(struct rq *rq, struct task_struct *p)
865{
866 rq->nr_numa_running -= (p->numa_preferred_nid != -1);
867 rq->nr_preferred_running -= (p->numa_preferred_nid == task_node(p));
868}
869
870struct numa_group {
871 atomic_t refcount;
872
873 spinlock_t lock;
874 int nr_tasks;
875 pid_t gid;
876
877 struct rcu_head rcu;
878 nodemask_t active_nodes;
879 unsigned long total_faults;
880
881
882
883
884
885 unsigned long *faults_cpu;
886 unsigned long faults[0];
887};
888
889
890#define NR_NUMA_HINT_FAULT_TYPES 2
891
892
893#define NR_NUMA_HINT_FAULT_STATS (NR_NUMA_HINT_FAULT_TYPES * 2)
894
895
896#define NR_NUMA_HINT_FAULT_BUCKETS (NR_NUMA_HINT_FAULT_STATS * 2)
897
898pid_t task_numa_group_id(struct task_struct *p)
899{
900 return p->numa_group ? p->numa_group->gid : 0;
901}
902
903
904
905
906
907
908
909static inline int task_faults_idx(enum numa_faults_stats s, int nid, int priv)
910{
911 return NR_NUMA_HINT_FAULT_TYPES * (s * nr_node_ids + nid) + priv;
912}
913
914static inline unsigned long task_faults(struct task_struct *p, int nid)
915{
916 if (!p->numa_faults)
917 return 0;
918
919 return p->numa_faults[task_faults_idx(NUMA_MEM, nid, 0)] +
920 p->numa_faults[task_faults_idx(NUMA_MEM, nid, 1)];
921}
922
923static inline unsigned long group_faults(struct task_struct *p, int nid)
924{
925 if (!p->numa_group)
926 return 0;
927
928 return p->numa_group->faults[task_faults_idx(NUMA_MEM, nid, 0)] +
929 p->numa_group->faults[task_faults_idx(NUMA_MEM, nid, 1)];
930}
931
932static inline unsigned long group_faults_cpu(struct numa_group *group, int nid)
933{
934 return group->faults_cpu[task_faults_idx(NUMA_MEM, nid, 0)] +
935 group->faults_cpu[task_faults_idx(NUMA_MEM, nid, 1)];
936}
937
938
939static unsigned long score_nearby_nodes(struct task_struct *p, int nid,
940 int maxdist, bool task)
941{
942 unsigned long score = 0;
943 int node;
944
945
946
947
948
949 if (sched_numa_topology_type == NUMA_DIRECT)
950 return 0;
951
952
953
954
955
956 for_each_online_node(node) {
957 unsigned long faults;
958 int dist = node_distance(nid, node);
959
960
961
962
963
964 if (dist == sched_max_numa_distance || node == nid)
965 continue;
966
967
968
969
970
971
972
973
974 if (sched_numa_topology_type == NUMA_BACKPLANE &&
975 dist > maxdist)
976 continue;
977
978
979 if (task)
980 faults = task_faults(p, node);
981 else
982 faults = group_faults(p, node);
983
984
985
986
987
988
989
990
991
992 if (sched_numa_topology_type == NUMA_GLUELESS_MESH) {
993 faults *= (sched_max_numa_distance - dist);
994 faults /= (sched_max_numa_distance - LOCAL_DISTANCE);
995 }
996
997 score += faults;
998 }
999
1000 return score;
1001}
1002
1003
1004
1005
1006
1007
1008
1009static inline unsigned long task_weight(struct task_struct *p, int nid,
1010 int dist)
1011{
1012 unsigned long faults, total_faults;
1013
1014 if (!p->numa_faults)
1015 return 0;
1016
1017 total_faults = p->total_numa_faults;
1018
1019 if (!total_faults)
1020 return 0;
1021
1022 faults = task_faults(p, nid);
1023 faults += score_nearby_nodes(p, nid, dist, true);
1024
1025 return 1000 * faults / total_faults;
1026}
1027
1028static inline unsigned long group_weight(struct task_struct *p, int nid,
1029 int dist)
1030{
1031 unsigned long faults, total_faults;
1032
1033 if (!p->numa_group)
1034 return 0;
1035
1036 total_faults = p->numa_group->total_faults;
1037
1038 if (!total_faults)
1039 return 0;
1040
1041 faults = group_faults(p, nid);
1042 faults += score_nearby_nodes(p, nid, dist, false);
1043
1044 return 1000 * faults / total_faults;
1045}
1046
1047bool should_numa_migrate_memory(struct task_struct *p, struct page * page,
1048 int src_nid, int dst_cpu)
1049{
1050 struct numa_group *ng = p->numa_group;
1051 int dst_nid = cpu_to_node(dst_cpu);
1052 int last_cpupid, this_cpupid;
1053
1054 this_cpupid = cpu_pid_to_cpupid(dst_cpu, current->pid);
1055
1056
1057
1058
1059
1060
1061
1062
1063
1064
1065
1066
1067
1068
1069
1070
1071
1072
1073 last_cpupid = page_cpupid_xchg_last(page, this_cpupid);
1074 if (!cpupid_pid_unset(last_cpupid) &&
1075 cpupid_to_nid(last_cpupid) != dst_nid)
1076 return false;
1077
1078
1079 if (cpupid_match_pid(p, last_cpupid))
1080 return true;
1081
1082
1083 if (!ng)
1084 return true;
1085
1086
1087
1088
1089
1090 if (!node_isset(dst_nid, ng->active_nodes))
1091 return false;
1092
1093
1094
1095
1096
1097 if (!node_isset(src_nid, ng->active_nodes))
1098 return true;
1099
1100
1101
1102
1103
1104
1105
1106
1107 return group_faults(p, dst_nid) < (group_faults(p, src_nid) * 3 / 4);
1108}
1109
1110static unsigned long weighted_cpuload(const int cpu);
1111static unsigned long source_load(int cpu, int type);
1112static unsigned long target_load(int cpu, int type);
1113static unsigned long capacity_of(int cpu);
1114static long effective_load(struct task_group *tg, int cpu, long wl, long wg);
1115
1116
1117struct numa_stats {
1118 unsigned long nr_running;
1119 unsigned long load;
1120
1121
1122 unsigned long compute_capacity;
1123
1124
1125 unsigned long task_capacity;
1126 int has_free_capacity;
1127};
1128
1129
1130
1131
1132static void update_numa_stats(struct numa_stats *ns, int nid)
1133{
1134 int smt, cpu, cpus = 0;
1135 unsigned long capacity;
1136
1137 memset(ns, 0, sizeof(*ns));
1138 for_each_cpu(cpu, cpumask_of_node(nid)) {
1139 struct rq *rq = cpu_rq(cpu);
1140
1141 ns->nr_running += rq->nr_running;
1142 ns->load += weighted_cpuload(cpu);
1143 ns->compute_capacity += capacity_of(cpu);
1144
1145 cpus++;
1146 }
1147
1148
1149
1150
1151
1152
1153
1154
1155
1156 if (!cpus)
1157 return;
1158
1159
1160 smt = DIV_ROUND_UP(SCHED_CAPACITY_SCALE * cpus, ns->compute_capacity);
1161 capacity = cpus / smt;
1162
1163 ns->task_capacity = min_t(unsigned, capacity,
1164 DIV_ROUND_CLOSEST(ns->compute_capacity, SCHED_CAPACITY_SCALE));
1165 ns->has_free_capacity = (ns->nr_running < ns->task_capacity);
1166}
1167
1168struct task_numa_env {
1169 struct task_struct *p;
1170
1171 int src_cpu, src_nid;
1172 int dst_cpu, dst_nid;
1173
1174 struct numa_stats src_stats, dst_stats;
1175
1176 int imbalance_pct;
1177 int dist;
1178
1179 struct task_struct *best_task;
1180 long best_imp;
1181 int best_cpu;
1182};
1183
1184static void task_numa_assign(struct task_numa_env *env,
1185 struct task_struct *p, long imp)
1186{
1187 if (env->best_task)
1188 put_task_struct(env->best_task);
1189 if (p)
1190 get_task_struct(p);
1191
1192 env->best_task = p;
1193 env->best_imp = imp;
1194 env->best_cpu = env->dst_cpu;
1195}
1196
1197static bool load_too_imbalanced(long src_load, long dst_load,
1198 struct task_numa_env *env)
1199{
1200 long imb, old_imb;
1201 long orig_src_load, orig_dst_load;
1202 long src_capacity, dst_capacity;
1203
1204
1205
1206
1207
1208
1209
1210
1211 src_capacity = env->src_stats.compute_capacity;
1212 dst_capacity = env->dst_stats.compute_capacity;
1213
1214
1215 if (dst_load < src_load)
1216 swap(dst_load, src_load);
1217
1218
1219 imb = dst_load * src_capacity * 100 -
1220 src_load * dst_capacity * env->imbalance_pct;
1221 if (imb <= 0)
1222 return false;
1223
1224
1225
1226
1227
1228 orig_src_load = env->src_stats.load;
1229 orig_dst_load = env->dst_stats.load;
1230
1231 if (orig_dst_load < orig_src_load)
1232 swap(orig_dst_load, orig_src_load);
1233
1234 old_imb = orig_dst_load * src_capacity * 100 -
1235 orig_src_load * dst_capacity * env->imbalance_pct;
1236
1237
1238 return (imb > old_imb);
1239}
1240
1241
1242
1243
1244
1245
1246
1247static void task_numa_compare(struct task_numa_env *env,
1248 long taskimp, long groupimp)
1249{
1250 struct rq *src_rq = cpu_rq(env->src_cpu);
1251 struct rq *dst_rq = cpu_rq(env->dst_cpu);
1252 struct task_struct *cur;
1253 long src_load, dst_load;
1254 long load;
1255 long imp = env->p->numa_group ? groupimp : taskimp;
1256 long moveimp = imp;
1257 int dist = env->dist;
1258
1259 rcu_read_lock();
1260
1261 raw_spin_lock_irq(&dst_rq->lock);
1262 cur = dst_rq->curr;
1263
1264
1265
1266
1267
1268
1269
1270 if ((cur->flags & PF_EXITING) || is_idle_task(cur))
1271 cur = NULL;
1272 raw_spin_unlock_irq(&dst_rq->lock);
1273
1274
1275
1276
1277
1278 if (cur == env->p)
1279 goto unlock;
1280
1281
1282
1283
1284
1285
1286
1287
1288 if (cur) {
1289
1290 if (!cpumask_test_cpu(env->src_cpu, tsk_cpus_allowed(cur)))
1291 goto unlock;
1292
1293
1294
1295
1296
1297 if (cur->numa_group == env->p->numa_group) {
1298 imp = taskimp + task_weight(cur, env->src_nid, dist) -
1299 task_weight(cur, env->dst_nid, dist);
1300
1301
1302
1303
1304 if (cur->numa_group)
1305 imp -= imp/16;
1306 } else {
1307
1308
1309
1310
1311
1312 if (cur->numa_group)
1313 imp += group_weight(cur, env->src_nid, dist) -
1314 group_weight(cur, env->dst_nid, dist);
1315 else
1316 imp += task_weight(cur, env->src_nid, dist) -
1317 task_weight(cur, env->dst_nid, dist);
1318 }
1319 }
1320
1321 if (imp <= env->best_imp && moveimp <= env->best_imp)
1322 goto unlock;
1323
1324 if (!cur) {
1325
1326 if (env->src_stats.nr_running <= env->src_stats.task_capacity &&
1327 !env->dst_stats.has_free_capacity)
1328 goto unlock;
1329
1330 goto balance;
1331 }
1332
1333
1334 if (imp > env->best_imp && src_rq->nr_running == 1 &&
1335 dst_rq->nr_running == 1)
1336 goto assign;
1337
1338
1339
1340
1341balance:
1342 load = task_h_load(env->p);
1343 dst_load = env->dst_stats.load + load;
1344 src_load = env->src_stats.load - load;
1345
1346 if (moveimp > imp && moveimp > env->best_imp) {
1347
1348
1349
1350
1351
1352
1353 if (!load_too_imbalanced(src_load, dst_load, env)) {
1354 imp = moveimp - 1;
1355 cur = NULL;
1356 goto assign;
1357 }
1358 }
1359
1360 if (imp <= env->best_imp)
1361 goto unlock;
1362
1363 if (cur) {
1364 load = task_h_load(cur);
1365 dst_load -= load;
1366 src_load += load;
1367 }
1368
1369 if (load_too_imbalanced(src_load, dst_load, env))
1370 goto unlock;
1371
1372
1373
1374
1375
1376 if (!cur)
1377 env->dst_cpu = select_idle_sibling(env->p, env->dst_cpu);
1378
1379assign:
1380 task_numa_assign(env, cur, imp);
1381unlock:
1382 rcu_read_unlock();
1383}
1384
1385static void task_numa_find_cpu(struct task_numa_env *env,
1386 long taskimp, long groupimp)
1387{
1388 int cpu;
1389
1390 for_each_cpu(cpu, cpumask_of_node(env->dst_nid)) {
1391
1392 if (!cpumask_test_cpu(cpu, tsk_cpus_allowed(env->p)))
1393 continue;
1394
1395 env->dst_cpu = cpu;
1396 task_numa_compare(env, taskimp, groupimp);
1397 }
1398}
1399
1400static int task_numa_migrate(struct task_struct *p)
1401{
1402 struct task_numa_env env = {
1403 .p = p,
1404
1405 .src_cpu = task_cpu(p),
1406 .src_nid = task_node(p),
1407
1408 .imbalance_pct = 112,
1409
1410 .best_task = NULL,
1411 .best_imp = 0,
1412 .best_cpu = -1
1413 };
1414 struct sched_domain *sd;
1415 unsigned long taskweight, groupweight;
1416 int nid, ret, dist;
1417 long taskimp, groupimp;
1418
1419
1420
1421
1422
1423
1424
1425
1426
1427 rcu_read_lock();
1428 sd = rcu_dereference(per_cpu(sd_numa, env.src_cpu));
1429 if (sd)
1430 env.imbalance_pct = 100 + (sd->imbalance_pct - 100) / 2;
1431 rcu_read_unlock();
1432
1433
1434
1435
1436
1437
1438
1439 if (unlikely(!sd)) {
1440 p->numa_preferred_nid = task_node(p);
1441 return -EINVAL;
1442 }
1443
1444 env.dst_nid = p->numa_preferred_nid;
1445 dist = env.dist = node_distance(env.src_nid, env.dst_nid);
1446 taskweight = task_weight(p, env.src_nid, dist);
1447 groupweight = group_weight(p, env.src_nid, dist);
1448 update_numa_stats(&env.src_stats, env.src_nid);
1449 taskimp = task_weight(p, env.dst_nid, dist) - taskweight;
1450 groupimp = group_weight(p, env.dst_nid, dist) - groupweight;
1451 update_numa_stats(&env.dst_stats, env.dst_nid);
1452
1453
1454 task_numa_find_cpu(&env, taskimp, groupimp);
1455
1456
1457
1458
1459
1460
1461
1462
1463 if (env.best_cpu == -1 || (p->numa_group &&
1464 nodes_weight(p->numa_group->active_nodes) > 1)) {
1465 for_each_online_node(nid) {
1466 if (nid == env.src_nid || nid == p->numa_preferred_nid)
1467 continue;
1468
1469 dist = node_distance(env.src_nid, env.dst_nid);
1470 if (sched_numa_topology_type == NUMA_BACKPLANE &&
1471 dist != env.dist) {
1472 taskweight = task_weight(p, env.src_nid, dist);
1473 groupweight = group_weight(p, env.src_nid, dist);
1474 }
1475
1476
1477 taskimp = task_weight(p, nid, dist) - taskweight;
1478 groupimp = group_weight(p, nid, dist) - groupweight;
1479 if (taskimp < 0 && groupimp < 0)
1480 continue;
1481
1482 env.dist = dist;
1483 env.dst_nid = nid;
1484 update_numa_stats(&env.dst_stats, env.dst_nid);
1485 task_numa_find_cpu(&env, taskimp, groupimp);
1486 }
1487 }
1488
1489
1490
1491
1492
1493
1494
1495
1496
1497 if (p->numa_group) {
1498 if (env.best_cpu == -1)
1499 nid = env.src_nid;
1500 else
1501 nid = env.dst_nid;
1502
1503 if (node_isset(nid, p->numa_group->active_nodes))
1504 sched_setnuma(p, env.dst_nid);
1505 }
1506
1507
1508 if (env.best_cpu == -1)
1509 return -EAGAIN;
1510
1511
1512
1513
1514
1515 p->numa_scan_period = task_scan_min(p);
1516
1517 if (env.best_task == NULL) {
1518 ret = migrate_task_to(p, env.best_cpu);
1519 if (ret != 0)
1520 trace_sched_stick_numa(p, env.src_cpu, env.best_cpu);
1521 return ret;
1522 }
1523
1524 ret = migrate_swap(p, env.best_task);
1525 if (ret != 0)
1526 trace_sched_stick_numa(p, env.src_cpu, task_cpu(env.best_task));
1527 put_task_struct(env.best_task);
1528 return ret;
1529}
1530
1531
1532static void numa_migrate_preferred(struct task_struct *p)
1533{
1534 unsigned long interval = HZ;
1535
1536
1537 if (unlikely(p->numa_preferred_nid == -1 || !p->numa_faults))
1538 return;
1539
1540
1541 interval = min(interval, msecs_to_jiffies(p->numa_scan_period) / 16);
1542 p->numa_migrate_retry = jiffies + interval;
1543
1544
1545 if (task_node(p) == p->numa_preferred_nid)
1546 return;
1547
1548
1549 task_numa_migrate(p);
1550}
1551
1552
1553
1554
1555
1556
1557
1558
1559
1560
1561
1562
1563static void update_numa_active_node_mask(struct numa_group *numa_group)
1564{
1565 unsigned long faults, max_faults = 0;
1566 int nid;
1567
1568 for_each_online_node(nid) {
1569 faults = group_faults_cpu(numa_group, nid);
1570 if (faults > max_faults)
1571 max_faults = faults;
1572 }
1573
1574 for_each_online_node(nid) {
1575 faults = group_faults_cpu(numa_group, nid);
1576 if (!node_isset(nid, numa_group->active_nodes)) {
1577 if (faults > max_faults * 6 / 16)
1578 node_set(nid, numa_group->active_nodes);
1579 } else if (faults < max_faults * 3 / 16)
1580 node_clear(nid, numa_group->active_nodes);
1581 }
1582}
1583
1584
1585
1586
1587
1588
1589
1590
1591#define NUMA_PERIOD_SLOTS 10
1592#define NUMA_PERIOD_THRESHOLD 7
1593
1594
1595
1596
1597
1598
1599
1600static void update_task_scan_period(struct task_struct *p,
1601 unsigned long shared, unsigned long private)
1602{
1603 unsigned int period_slot;
1604 int ratio;
1605 int diff;
1606
1607 unsigned long remote = p->numa_faults_locality[0];
1608 unsigned long local = p->numa_faults_locality[1];
1609
1610
1611
1612
1613
1614
1615 if (local + shared == 0) {
1616 p->numa_scan_period = min(p->numa_scan_period_max,
1617 p->numa_scan_period << 1);
1618
1619 p->mm->numa_next_scan = jiffies +
1620 msecs_to_jiffies(p->numa_scan_period);
1621
1622 return;
1623 }
1624
1625
1626
1627
1628
1629
1630
1631 period_slot = DIV_ROUND_UP(p->numa_scan_period, NUMA_PERIOD_SLOTS);
1632 ratio = (local * NUMA_PERIOD_SLOTS) / (local + remote);
1633 if (ratio >= NUMA_PERIOD_THRESHOLD) {
1634 int slot = ratio - NUMA_PERIOD_THRESHOLD;
1635 if (!slot)
1636 slot = 1;
1637 diff = slot * period_slot;
1638 } else {
1639 diff = -(NUMA_PERIOD_THRESHOLD - ratio) * period_slot;
1640
1641
1642
1643
1644
1645
1646
1647
1648
1649 ratio = DIV_ROUND_UP(private * NUMA_PERIOD_SLOTS, (private + shared + 1));
1650 diff = (diff * ratio) / NUMA_PERIOD_SLOTS;
1651 }
1652
1653 p->numa_scan_period = clamp(p->numa_scan_period + diff,
1654 task_scan_min(p), task_scan_max(p));
1655 memset(p->numa_faults_locality, 0, sizeof(p->numa_faults_locality));
1656}
1657
1658
1659
1660
1661
1662
1663
1664
1665static u64 numa_get_avg_runtime(struct task_struct *p, u64 *period)
1666{
1667 u64 runtime, delta, now;
1668
1669 now = p->se.exec_start;
1670 runtime = p->se.sum_exec_runtime;
1671
1672 if (p->last_task_numa_placement) {
1673 delta = runtime - p->last_sum_exec_runtime;
1674 *period = now - p->last_task_numa_placement;
1675 } else {
1676 delta = p->se.avg.runnable_avg_sum;
1677 *period = p->se.avg.runnable_avg_period;
1678 }
1679
1680 p->last_sum_exec_runtime = runtime;
1681 p->last_task_numa_placement = now;
1682
1683 return delta;
1684}
1685
1686
1687
1688
1689
1690
1691static int preferred_group_nid(struct task_struct *p, int nid)
1692{
1693 nodemask_t nodes;
1694 int dist;
1695
1696
1697 if (sched_numa_topology_type == NUMA_DIRECT)
1698 return nid;
1699
1700
1701
1702
1703
1704
1705 if (sched_numa_topology_type == NUMA_GLUELESS_MESH) {
1706 unsigned long score, max_score = 0;
1707 int node, max_node = nid;
1708
1709 dist = sched_max_numa_distance;
1710
1711 for_each_online_node(node) {
1712 score = group_weight(p, node, dist);
1713 if (score > max_score) {
1714 max_score = score;
1715 max_node = node;
1716 }
1717 }
1718 return max_node;
1719 }
1720
1721
1722
1723
1724
1725
1726
1727
1728
1729
1730 nodes = node_online_map;
1731 for (dist = sched_max_numa_distance; dist > LOCAL_DISTANCE; dist--) {
1732 unsigned long max_faults = 0;
1733 nodemask_t max_group = NODE_MASK_NONE;
1734 int a, b;
1735
1736
1737 if (!find_numa_distance(dist))
1738 continue;
1739
1740 for_each_node_mask(a, nodes) {
1741 unsigned long faults = 0;
1742 nodemask_t this_group;
1743 nodes_clear(this_group);
1744
1745
1746 for_each_node_mask(b, nodes) {
1747 if (node_distance(a, b) < dist) {
1748 faults += group_faults(p, b);
1749 node_set(b, this_group);
1750 node_clear(b, nodes);
1751 }
1752 }
1753
1754
1755 if (faults > max_faults) {
1756 max_faults = faults;
1757 max_group = this_group;
1758
1759
1760
1761
1762
1763 nid = a;
1764 }
1765 }
1766
1767 nodes = max_group;
1768 }
1769 return nid;
1770}
1771
1772static void task_numa_placement(struct task_struct *p)
1773{
1774 int seq, nid, max_nid = -1, max_group_nid = -1;
1775 unsigned long max_faults = 0, max_group_faults = 0;
1776 unsigned long fault_types[2] = { 0, 0 };
1777 unsigned long total_faults;
1778 u64 runtime, period;
1779 spinlock_t *group_lock = NULL;
1780
1781 seq = ACCESS_ONCE(p->mm->numa_scan_seq);
1782 if (p->numa_scan_seq == seq)
1783 return;
1784 p->numa_scan_seq = seq;
1785 p->numa_scan_period_max = task_scan_max(p);
1786
1787 total_faults = p->numa_faults_locality[0] +
1788 p->numa_faults_locality[1];
1789 runtime = numa_get_avg_runtime(p, &period);
1790
1791
1792 if (p->numa_group) {
1793 group_lock = &p->numa_group->lock;
1794 spin_lock_irq(group_lock);
1795 }
1796
1797
1798 for_each_online_node(nid) {
1799
1800 int mem_idx, membuf_idx, cpu_idx, cpubuf_idx;
1801 unsigned long faults = 0, group_faults = 0;
1802 int priv;
1803
1804 for (priv = 0; priv < NR_NUMA_HINT_FAULT_TYPES; priv++) {
1805 long diff, f_diff, f_weight;
1806
1807 mem_idx = task_faults_idx(NUMA_MEM, nid, priv);
1808 membuf_idx = task_faults_idx(NUMA_MEMBUF, nid, priv);
1809 cpu_idx = task_faults_idx(NUMA_CPU, nid, priv);
1810 cpubuf_idx = task_faults_idx(NUMA_CPUBUF, nid, priv);
1811
1812
1813 diff = p->numa_faults[membuf_idx] - p->numa_faults[mem_idx] / 2;
1814 fault_types[priv] += p->numa_faults[membuf_idx];
1815 p->numa_faults[membuf_idx] = 0;
1816
1817
1818
1819
1820
1821
1822
1823
1824 f_weight = div64_u64(runtime << 16, period + 1);
1825 f_weight = (f_weight * p->numa_faults[cpubuf_idx]) /
1826 (total_faults + 1);
1827 f_diff = f_weight - p->numa_faults[cpu_idx] / 2;
1828 p->numa_faults[cpubuf_idx] = 0;
1829
1830 p->numa_faults[mem_idx] += diff;
1831 p->numa_faults[cpu_idx] += f_diff;
1832 faults += p->numa_faults[mem_idx];
1833 p->total_numa_faults += diff;
1834 if (p->numa_group) {
1835
1836
1837
1838
1839
1840
1841
1842 p->numa_group->faults[mem_idx] += diff;
1843 p->numa_group->faults_cpu[mem_idx] += f_diff;
1844 p->numa_group->total_faults += diff;
1845 group_faults += p->numa_group->faults[mem_idx];
1846 }
1847 }
1848
1849 if (faults > max_faults) {
1850 max_faults = faults;
1851 max_nid = nid;
1852 }
1853
1854 if (group_faults > max_group_faults) {
1855 max_group_faults = group_faults;
1856 max_group_nid = nid;
1857 }
1858 }
1859
1860 update_task_scan_period(p, fault_types[0], fault_types[1]);
1861
1862 if (p->numa_group) {
1863 update_numa_active_node_mask(p->numa_group);
1864 spin_unlock_irq(group_lock);
1865 max_nid = preferred_group_nid(p, max_group_nid);
1866 }
1867
1868 if (max_faults) {
1869
1870 if (max_nid != p->numa_preferred_nid)
1871 sched_setnuma(p, max_nid);
1872
1873 if (task_node(p) != p->numa_preferred_nid)
1874 numa_migrate_preferred(p);
1875 }
1876}
1877
1878static inline int get_numa_group(struct numa_group *grp)
1879{
1880 return atomic_inc_not_zero(&grp->refcount);
1881}
1882
1883static inline void put_numa_group(struct numa_group *grp)
1884{
1885 if (atomic_dec_and_test(&grp->refcount))
1886 kfree_rcu(grp, rcu);
1887}
1888
1889static void task_numa_group(struct task_struct *p, int cpupid, int flags,
1890 int *priv)
1891{
1892 struct numa_group *grp, *my_grp;
1893 struct task_struct *tsk;
1894 bool join = false;
1895 int cpu = cpupid_to_cpu(cpupid);
1896 int i;
1897
1898 if (unlikely(!p->numa_group)) {
1899 unsigned int size = sizeof(struct numa_group) +
1900 4*nr_node_ids*sizeof(unsigned long);
1901
1902 grp = kzalloc(size, GFP_KERNEL | __GFP_NOWARN);
1903 if (!grp)
1904 return;
1905
1906 atomic_set(&grp->refcount, 1);
1907 spin_lock_init(&grp->lock);
1908 grp->gid = p->pid;
1909
1910 grp->faults_cpu = grp->faults + NR_NUMA_HINT_FAULT_TYPES *
1911 nr_node_ids;
1912
1913 node_set(task_node(current), grp->active_nodes);
1914
1915 for (i = 0; i < NR_NUMA_HINT_FAULT_STATS * nr_node_ids; i++)
1916 grp->faults[i] = p->numa_faults[i];
1917
1918 grp->total_faults = p->total_numa_faults;
1919
1920 grp->nr_tasks++;
1921 rcu_assign_pointer(p->numa_group, grp);
1922 }
1923
1924 rcu_read_lock();
1925 tsk = ACCESS_ONCE(cpu_rq(cpu)->curr);
1926
1927 if (!cpupid_match_pid(tsk, cpupid))
1928 goto no_join;
1929
1930 grp = rcu_dereference(tsk->numa_group);
1931 if (!grp)
1932 goto no_join;
1933
1934 my_grp = p->numa_group;
1935 if (grp == my_grp)
1936 goto no_join;
1937
1938
1939
1940
1941
1942 if (my_grp->nr_tasks > grp->nr_tasks)
1943 goto no_join;
1944
1945
1946
1947
1948 if (my_grp->nr_tasks == grp->nr_tasks && my_grp > grp)
1949 goto no_join;
1950
1951
1952 if (tsk->mm == current->mm)
1953 join = true;
1954
1955
1956 if (flags & TNF_SHARED)
1957 join = true;
1958
1959
1960 *priv = !join;
1961
1962 if (join && !get_numa_group(grp))
1963 goto no_join;
1964
1965 rcu_read_unlock();
1966
1967 if (!join)
1968 return;
1969
1970 BUG_ON(irqs_disabled());
1971 double_lock_irq(&my_grp->lock, &grp->lock);
1972
1973 for (i = 0; i < NR_NUMA_HINT_FAULT_STATS * nr_node_ids; i++) {
1974 my_grp->faults[i] -= p->numa_faults[i];
1975 grp->faults[i] += p->numa_faults[i];
1976 }
1977 my_grp->total_faults -= p->total_numa_faults;
1978 grp->total_faults += p->total_numa_faults;
1979
1980 my_grp->nr_tasks--;
1981 grp->nr_tasks++;
1982
1983 spin_unlock(&my_grp->lock);
1984 spin_unlock_irq(&grp->lock);
1985
1986 rcu_assign_pointer(p->numa_group, grp);
1987
1988 put_numa_group(my_grp);
1989 return;
1990
1991no_join:
1992 rcu_read_unlock();
1993 return;
1994}
1995
1996void task_numa_free(struct task_struct *p)
1997{
1998 struct numa_group *grp = p->numa_group;
1999 void *numa_faults = p->numa_faults;
2000 unsigned long flags;
2001 int i;
2002
2003 if (grp) {
2004 spin_lock_irqsave(&grp->lock, flags);
2005 for (i = 0; i < NR_NUMA_HINT_FAULT_STATS * nr_node_ids; i++)
2006 grp->faults[i] -= p->numa_faults[i];
2007 grp->total_faults -= p->total_numa_faults;
2008
2009 grp->nr_tasks--;
2010 spin_unlock_irqrestore(&grp->lock, flags);
2011 RCU_INIT_POINTER(p->numa_group, NULL);
2012 put_numa_group(grp);
2013 }
2014
2015 p->numa_faults = NULL;
2016 kfree(numa_faults);
2017}
2018
2019
2020
2021
2022void task_numa_fault(int last_cpupid, int mem_node, int pages, int flags)
2023{
2024 struct task_struct *p = current;
2025 bool migrated = flags & TNF_MIGRATED;
2026 int cpu_node = task_node(current);
2027 int local = !!(flags & TNF_FAULT_LOCAL);
2028 int priv;
2029
2030 if (!numabalancing_enabled)
2031 return;
2032
2033
2034 if (!p->mm)
2035 return;
2036
2037
2038 if (unlikely(!p->numa_faults)) {
2039 int size = sizeof(*p->numa_faults) *
2040 NR_NUMA_HINT_FAULT_BUCKETS * nr_node_ids;
2041
2042 p->numa_faults = kzalloc(size, GFP_KERNEL|__GFP_NOWARN);
2043 if (!p->numa_faults)
2044 return;
2045
2046 p->total_numa_faults = 0;
2047 memset(p->numa_faults_locality, 0, sizeof(p->numa_faults_locality));
2048 }
2049
2050
2051
2052
2053
2054 if (unlikely(last_cpupid == (-1 & LAST_CPUPID_MASK))) {
2055 priv = 1;
2056 } else {
2057 priv = cpupid_match_pid(p, last_cpupid);
2058 if (!priv && !(flags & TNF_NO_GROUP))
2059 task_numa_group(p, last_cpupid, flags, &priv);
2060 }
2061
2062
2063
2064
2065
2066
2067
2068 if (!priv && !local && p->numa_group &&
2069 node_isset(cpu_node, p->numa_group->active_nodes) &&
2070 node_isset(mem_node, p->numa_group->active_nodes))
2071 local = 1;
2072
2073 task_numa_placement(p);
2074
2075
2076
2077
2078
2079 if (time_after(jiffies, p->numa_migrate_retry))
2080 numa_migrate_preferred(p);
2081
2082 if (migrated)
2083 p->numa_pages_migrated += pages;
2084
2085 p->numa_faults[task_faults_idx(NUMA_MEMBUF, mem_node, priv)] += pages;
2086 p->numa_faults[task_faults_idx(NUMA_CPUBUF, cpu_node, priv)] += pages;
2087 p->numa_faults_locality[local] += pages;
2088}
2089
2090static void reset_ptenuma_scan(struct task_struct *p)
2091{
2092 ACCESS_ONCE(p->mm->numa_scan_seq)++;
2093 p->mm->numa_scan_offset = 0;
2094}
2095
2096
2097
2098
2099
2100void task_numa_work(struct callback_head *work)
2101{
2102 unsigned long migrate, next_scan, now = jiffies;
2103 struct task_struct *p = current;
2104 struct mm_struct *mm = p->mm;
2105 struct vm_area_struct *vma;
2106 unsigned long start, end;
2107 unsigned long nr_pte_updates = 0;
2108 long pages;
2109
2110 WARN_ON_ONCE(p != container_of(work, struct task_struct, numa_work));
2111
2112 work->next = work;
2113
2114
2115
2116
2117
2118
2119
2120
2121 if (p->flags & PF_EXITING)
2122 return;
2123
2124 if (!mm->numa_next_scan) {
2125 mm->numa_next_scan = now +
2126 msecs_to_jiffies(sysctl_numa_balancing_scan_delay);
2127 }
2128
2129
2130
2131
2132 migrate = mm->numa_next_scan;
2133 if (time_before(now, migrate))
2134 return;
2135
2136 if (p->numa_scan_period == 0) {
2137 p->numa_scan_period_max = task_scan_max(p);
2138 p->numa_scan_period = task_scan_min(p);
2139 }
2140
2141 next_scan = now + msecs_to_jiffies(p->numa_scan_period);
2142 if (cmpxchg(&mm->numa_next_scan, migrate, next_scan) != migrate)
2143 return;
2144
2145
2146
2147
2148
2149 p->node_stamp += 2 * TICK_NSEC;
2150
2151 start = mm->numa_scan_offset;
2152 pages = sysctl_numa_balancing_scan_size;
2153 pages <<= 20 - PAGE_SHIFT;
2154 if (!pages)
2155 return;
2156
2157 down_read(&mm->mmap_sem);
2158 vma = find_vma(mm, start);
2159 if (!vma) {
2160 reset_ptenuma_scan(p);
2161 start = 0;
2162 vma = mm->mmap;
2163 }
2164 for (; vma; vma = vma->vm_next) {
2165 if (!vma_migratable(vma) || !vma_policy_mof(vma))
2166 continue;
2167
2168
2169
2170
2171
2172
2173
2174 if (!vma->vm_mm ||
2175 (vma->vm_file && (vma->vm_flags & (VM_READ|VM_WRITE)) == (VM_READ)))
2176 continue;
2177
2178
2179
2180
2181
2182 if (!(vma->vm_flags & (VM_READ | VM_EXEC | VM_WRITE)))
2183 continue;
2184
2185 do {
2186 start = max(start, vma->vm_start);
2187 end = ALIGN(start + (pages << PAGE_SHIFT), HPAGE_SIZE);
2188 end = min(end, vma->vm_end);
2189 nr_pte_updates += change_prot_numa(vma, start, end);
2190
2191
2192
2193
2194
2195
2196 if (nr_pte_updates)
2197 pages -= (end - start) >> PAGE_SHIFT;
2198
2199 start = end;
2200 if (pages <= 0)
2201 goto out;
2202
2203 cond_resched();
2204 } while (end != vma->vm_end);
2205 }
2206
2207out:
2208
2209
2210
2211
2212
2213
2214 if (vma)
2215 mm->numa_scan_offset = start;
2216 else
2217 reset_ptenuma_scan(p);
2218 up_read(&mm->mmap_sem);
2219}
2220
2221
2222
2223
2224void task_tick_numa(struct rq *rq, struct task_struct *curr)
2225{
2226 struct callback_head *work = &curr->numa_work;
2227 u64 period, now;
2228
2229
2230
2231
2232 if (!curr->mm || (curr->flags & PF_EXITING) || work->next != work)
2233 return;
2234
2235
2236
2237
2238
2239
2240
2241 now = curr->se.sum_exec_runtime;
2242 period = (u64)curr->numa_scan_period * NSEC_PER_MSEC;
2243
2244 if (now - curr->node_stamp > period) {
2245 if (!curr->node_stamp)
2246 curr->numa_scan_period = task_scan_min(curr);
2247 curr->node_stamp += period;
2248
2249 if (!time_before(jiffies, curr->mm->numa_next_scan)) {
2250 init_task_work(work, task_numa_work);
2251 task_work_add(curr, work, true);
2252 }
2253 }
2254}
2255#else
2256static void task_tick_numa(struct rq *rq, struct task_struct *curr)
2257{
2258}
2259
2260static inline void account_numa_enqueue(struct rq *rq, struct task_struct *p)
2261{
2262}
2263
2264static inline void account_numa_dequeue(struct rq *rq, struct task_struct *p)
2265{
2266}
2267#endif
2268
2269static void
2270account_entity_enqueue(struct cfs_rq *cfs_rq, struct sched_entity *se)
2271{
2272 update_load_add(&cfs_rq->load, se->load.weight);
2273 if (!parent_entity(se))
2274 update_load_add(&rq_of(cfs_rq)->load, se->load.weight);
2275#ifdef CONFIG_SMP
2276 if (entity_is_task(se)) {
2277 struct rq *rq = rq_of(cfs_rq);
2278
2279 account_numa_enqueue(rq, task_of(se));
2280 list_add(&se->group_node, &rq->cfs_tasks);
2281 }
2282#endif
2283 cfs_rq->nr_running++;
2284}
2285
2286static void
2287account_entity_dequeue(struct cfs_rq *cfs_rq, struct sched_entity *se)
2288{
2289 update_load_sub(&cfs_rq->load, se->load.weight);
2290 if (!parent_entity(se))
2291 update_load_sub(&rq_of(cfs_rq)->load, se->load.weight);
2292 if (entity_is_task(se)) {
2293 account_numa_dequeue(rq_of(cfs_rq), task_of(se));
2294 list_del_init(&se->group_node);
2295 }
2296 cfs_rq->nr_running--;
2297}
2298
2299#ifdef CONFIG_FAIR_GROUP_SCHED
2300# ifdef CONFIG_SMP
2301static inline long calc_tg_weight(struct task_group *tg, struct cfs_rq *cfs_rq)
2302{
2303 long tg_weight;
2304
2305
2306
2307
2308
2309
2310 tg_weight = atomic_long_read(&tg->load_avg);
2311 tg_weight -= cfs_rq->tg_load_contrib;
2312 tg_weight += cfs_rq->load.weight;
2313
2314 return tg_weight;
2315}
2316
2317static long calc_cfs_shares(struct cfs_rq *cfs_rq, struct task_group *tg)
2318{
2319 long tg_weight, load, shares;
2320
2321 tg_weight = calc_tg_weight(tg, cfs_rq);
2322 load = cfs_rq->load.weight;
2323
2324 shares = (tg->shares * load);
2325 if (tg_weight)
2326 shares /= tg_weight;
2327
2328 if (shares < MIN_SHARES)
2329 shares = MIN_SHARES;
2330 if (shares > tg->shares)
2331 shares = tg->shares;
2332
2333 return shares;
2334}
2335# else
2336static inline long calc_cfs_shares(struct cfs_rq *cfs_rq, struct task_group *tg)
2337{
2338 return tg->shares;
2339}
2340# endif
2341static void reweight_entity(struct cfs_rq *cfs_rq, struct sched_entity *se,
2342 unsigned long weight)
2343{
2344 if (se->on_rq) {
2345
2346 if (cfs_rq->curr == se)
2347 update_curr(cfs_rq);
2348 account_entity_dequeue(cfs_rq, se);
2349 }
2350
2351 update_load_set(&se->load, weight);
2352
2353 if (se->on_rq)
2354 account_entity_enqueue(cfs_rq, se);
2355}
2356
2357static inline int throttled_hierarchy(struct cfs_rq *cfs_rq);
2358
2359static void update_cfs_shares(struct cfs_rq *cfs_rq)
2360{
2361 struct task_group *tg;
2362 struct sched_entity *se;
2363 long shares;
2364
2365 tg = cfs_rq->tg;
2366 se = tg->se[cpu_of(rq_of(cfs_rq))];
2367 if (!se || throttled_hierarchy(cfs_rq))
2368 return;
2369#ifndef CONFIG_SMP
2370 if (likely(se->load.weight == tg->shares))
2371 return;
2372#endif
2373 shares = calc_cfs_shares(cfs_rq, tg);
2374
2375 reweight_entity(cfs_rq_of(se), se, shares);
2376}
2377#else
2378static inline void update_cfs_shares(struct cfs_rq *cfs_rq)
2379{
2380}
2381#endif
2382
2383#ifdef CONFIG_SMP
2384
2385
2386
2387
2388#define LOAD_AVG_PERIOD 32
2389#define LOAD_AVG_MAX 47742
2390#define LOAD_AVG_MAX_N 345
2391
2392
2393static const u32 runnable_avg_yN_inv[] = {
2394 0xffffffff, 0xfa83b2da, 0xf5257d14, 0xefe4b99a, 0xeac0c6e6, 0xe5b906e6,
2395 0xe0ccdeeb, 0xdbfbb796, 0xd744fcc9, 0xd2a81d91, 0xce248c14, 0xc9b9bd85,
2396 0xc5672a10, 0xc12c4cc9, 0xbd08a39e, 0xb8fbaf46, 0xb504f333, 0xb123f581,
2397 0xad583ee9, 0xa9a15ab4, 0xa5fed6a9, 0xa2704302, 0x9ef5325f, 0x9b8d39b9,
2398 0x9837f050, 0x94f4efa8, 0x91c3d373, 0x8ea4398a, 0x8b95c1e3, 0x88980e80,
2399 0x85aac367, 0x82cd8698,
2400};
2401
2402
2403
2404
2405
2406static const u32 runnable_avg_yN_sum[] = {
2407 0, 1002, 1982, 2941, 3880, 4798, 5697, 6576, 7437, 8279, 9103,
2408 9909,10698,11470,12226,12966,13690,14398,15091,15769,16433,17082,
2409 17718,18340,18949,19545,20128,20698,21256,21802,22336,22859,23371,
2410};
2411
2412
2413
2414
2415
2416static __always_inline u64 decay_load(u64 val, u64 n)
2417{
2418 unsigned int local_n;
2419
2420 if (!n)
2421 return val;
2422 else if (unlikely(n > LOAD_AVG_PERIOD * 63))
2423 return 0;
2424
2425
2426 local_n = n;
2427
2428
2429
2430
2431
2432
2433
2434
2435 if (unlikely(local_n >= LOAD_AVG_PERIOD)) {
2436 val >>= local_n / LOAD_AVG_PERIOD;
2437 local_n %= LOAD_AVG_PERIOD;
2438 }
2439
2440 val *= runnable_avg_yN_inv[local_n];
2441
2442 return val >> 32;
2443}
2444
2445
2446
2447
2448
2449
2450
2451
2452static u32 __compute_runnable_contrib(u64 n)
2453{
2454 u32 contrib = 0;
2455
2456 if (likely(n <= LOAD_AVG_PERIOD))
2457 return runnable_avg_yN_sum[n];
2458 else if (unlikely(n >= LOAD_AVG_MAX_N))
2459 return LOAD_AVG_MAX;
2460
2461
2462 do {
2463 contrib /= 2;
2464 contrib += runnable_avg_yN_sum[LOAD_AVG_PERIOD];
2465
2466 n -= LOAD_AVG_PERIOD;
2467 } while (n > LOAD_AVG_PERIOD);
2468
2469 contrib = decay_load(contrib, n);
2470 return contrib + runnable_avg_yN_sum[n];
2471}
2472
2473
2474
2475
2476
2477
2478
2479
2480
2481
2482
2483
2484
2485
2486
2487
2488
2489
2490
2491
2492
2493
2494
2495
2496
2497
2498
2499
2500
2501static __always_inline int __update_entity_runnable_avg(u64 now,
2502 struct sched_avg *sa,
2503 int runnable)
2504{
2505 u64 delta, periods;
2506 u32 runnable_contrib;
2507 int delta_w, decayed = 0;
2508
2509 delta = now - sa->last_runnable_update;
2510
2511
2512
2513
2514 if ((s64)delta < 0) {
2515 sa->last_runnable_update = now;
2516 return 0;
2517 }
2518
2519
2520
2521
2522
2523 delta >>= 10;
2524 if (!delta)
2525 return 0;
2526 sa->last_runnable_update = now;
2527
2528
2529 delta_w = sa->runnable_avg_period % 1024;
2530 if (delta + delta_w >= 1024) {
2531
2532 decayed = 1;
2533
2534
2535
2536
2537
2538
2539 delta_w = 1024 - delta_w;
2540 if (runnable)
2541 sa->runnable_avg_sum += delta_w;
2542 sa->runnable_avg_period += delta_w;
2543
2544 delta -= delta_w;
2545
2546
2547 periods = delta / 1024;
2548 delta %= 1024;
2549
2550 sa->runnable_avg_sum = decay_load(sa->runnable_avg_sum,
2551 periods + 1);
2552 sa->runnable_avg_period = decay_load(sa->runnable_avg_period,
2553 periods + 1);
2554
2555
2556 runnable_contrib = __compute_runnable_contrib(periods);
2557 if (runnable)
2558 sa->runnable_avg_sum += runnable_contrib;
2559 sa->runnable_avg_period += runnable_contrib;
2560 }
2561
2562
2563 if (runnable)
2564 sa->runnable_avg_sum += delta;
2565 sa->runnable_avg_period += delta;
2566
2567 return decayed;
2568}
2569
2570
2571static inline u64 __synchronize_entity_decay(struct sched_entity *se)
2572{
2573 struct cfs_rq *cfs_rq = cfs_rq_of(se);
2574 u64 decays = atomic64_read(&cfs_rq->decay_counter);
2575
2576 decays -= se->avg.decay_count;
2577 if (!decays)
2578 return 0;
2579
2580 se->avg.load_avg_contrib = decay_load(se->avg.load_avg_contrib, decays);
2581 se->avg.decay_count = 0;
2582
2583 return decays;
2584}
2585
2586#ifdef CONFIG_FAIR_GROUP_SCHED
2587static inline void __update_cfs_rq_tg_load_contrib(struct cfs_rq *cfs_rq,
2588 int force_update)
2589{
2590 struct task_group *tg = cfs_rq->tg;
2591 long tg_contrib;
2592
2593 tg_contrib = cfs_rq->runnable_load_avg + cfs_rq->blocked_load_avg;
2594 tg_contrib -= cfs_rq->tg_load_contrib;
2595
2596 if (!tg_contrib)
2597 return;
2598
2599 if (force_update || abs(tg_contrib) > cfs_rq->tg_load_contrib / 8) {
2600 atomic_long_add(tg_contrib, &tg->load_avg);
2601 cfs_rq->tg_load_contrib += tg_contrib;
2602 }
2603}
2604
2605
2606
2607
2608
2609static inline void __update_tg_runnable_avg(struct sched_avg *sa,
2610 struct cfs_rq *cfs_rq)
2611{
2612 struct task_group *tg = cfs_rq->tg;
2613 long contrib;
2614
2615
2616 contrib = div_u64((u64)sa->runnable_avg_sum << NICE_0_SHIFT,
2617 sa->runnable_avg_period + 1);
2618 contrib -= cfs_rq->tg_runnable_contrib;
2619
2620 if (abs(contrib) > cfs_rq->tg_runnable_contrib / 64) {
2621 atomic_add(contrib, &tg->runnable_avg);
2622 cfs_rq->tg_runnable_contrib += contrib;
2623 }
2624}
2625
2626static inline void __update_group_entity_contrib(struct sched_entity *se)
2627{
2628 struct cfs_rq *cfs_rq = group_cfs_rq(se);
2629 struct task_group *tg = cfs_rq->tg;
2630 int runnable_avg;
2631
2632 u64 contrib;
2633
2634 contrib = cfs_rq->tg_load_contrib * tg->shares;
2635 se->avg.load_avg_contrib = div_u64(contrib,
2636 atomic_long_read(&tg->load_avg) + 1);
2637
2638
2639
2640
2641
2642
2643
2644
2645
2646
2647
2648
2649
2650
2651
2652
2653
2654
2655
2656
2657
2658
2659
2660
2661 runnable_avg = atomic_read(&tg->runnable_avg);
2662 if (runnable_avg < NICE_0_LOAD) {
2663 se->avg.load_avg_contrib *= runnable_avg;
2664 se->avg.load_avg_contrib >>= NICE_0_SHIFT;
2665 }
2666}
2667
2668static inline void update_rq_runnable_avg(struct rq *rq, int runnable)
2669{
2670 __update_entity_runnable_avg(rq_clock_task(rq), &rq->avg, runnable);
2671 __update_tg_runnable_avg(&rq->avg, &rq->cfs);
2672}
2673#else
2674static inline void __update_cfs_rq_tg_load_contrib(struct cfs_rq *cfs_rq,
2675 int force_update) {}
2676static inline void __update_tg_runnable_avg(struct sched_avg *sa,
2677 struct cfs_rq *cfs_rq) {}
2678static inline void __update_group_entity_contrib(struct sched_entity *se) {}
2679static inline void update_rq_runnable_avg(struct rq *rq, int runnable) {}
2680#endif
2681
2682static inline void __update_task_entity_contrib(struct sched_entity *se)
2683{
2684 u32 contrib;
2685
2686
2687 contrib = se->avg.runnable_avg_sum * scale_load_down(se->load.weight);
2688 contrib /= (se->avg.runnable_avg_period + 1);
2689 se->avg.load_avg_contrib = scale_load(contrib);
2690}
2691
2692
2693static long __update_entity_load_avg_contrib(struct sched_entity *se)
2694{
2695 long old_contrib = se->avg.load_avg_contrib;
2696
2697 if (entity_is_task(se)) {
2698 __update_task_entity_contrib(se);
2699 } else {
2700 __update_tg_runnable_avg(&se->avg, group_cfs_rq(se));
2701 __update_group_entity_contrib(se);
2702 }
2703
2704 return se->avg.load_avg_contrib - old_contrib;
2705}
2706
2707static inline void subtract_blocked_load_contrib(struct cfs_rq *cfs_rq,
2708 long load_contrib)
2709{
2710 if (likely(load_contrib < cfs_rq->blocked_load_avg))
2711 cfs_rq->blocked_load_avg -= load_contrib;
2712 else
2713 cfs_rq->blocked_load_avg = 0;
2714}
2715
2716static inline u64 cfs_rq_clock_task(struct cfs_rq *cfs_rq);
2717
2718
2719static inline void update_entity_load_avg(struct sched_entity *se,
2720 int update_cfs_rq)
2721{
2722 struct cfs_rq *cfs_rq = cfs_rq_of(se);
2723 long contrib_delta;
2724 u64 now;
2725
2726
2727
2728
2729
2730 if (entity_is_task(se))
2731 now = cfs_rq_clock_task(cfs_rq);
2732 else
2733 now = cfs_rq_clock_task(group_cfs_rq(se));
2734
2735 if (!__update_entity_runnable_avg(now, &se->avg, se->on_rq))
2736 return;
2737
2738 contrib_delta = __update_entity_load_avg_contrib(se);
2739
2740 if (!update_cfs_rq)
2741 return;
2742
2743 if (se->on_rq)
2744 cfs_rq->runnable_load_avg += contrib_delta;
2745 else
2746 subtract_blocked_load_contrib(cfs_rq, -contrib_delta);
2747}
2748
2749
2750
2751
2752
2753static void update_cfs_rq_blocked_load(struct cfs_rq *cfs_rq, int force_update)
2754{
2755 u64 now = cfs_rq_clock_task(cfs_rq) >> 20;
2756 u64 decays;
2757
2758 decays = now - cfs_rq->last_decay;
2759 if (!decays && !force_update)
2760 return;
2761
2762 if (atomic_long_read(&cfs_rq->removed_load)) {
2763 unsigned long removed_load;
2764 removed_load = atomic_long_xchg(&cfs_rq->removed_load, 0);
2765 subtract_blocked_load_contrib(cfs_rq, removed_load);
2766 }
2767
2768 if (decays) {
2769 cfs_rq->blocked_load_avg = decay_load(cfs_rq->blocked_load_avg,
2770 decays);
2771 atomic64_add(decays, &cfs_rq->decay_counter);
2772 cfs_rq->last_decay = now;
2773 }
2774
2775 __update_cfs_rq_tg_load_contrib(cfs_rq, force_update);
2776}
2777
2778
2779static inline void enqueue_entity_load_avg(struct cfs_rq *cfs_rq,
2780 struct sched_entity *se,
2781 int wakeup)
2782{
2783
2784
2785
2786
2787
2788
2789
2790
2791
2792 if (unlikely(se->avg.decay_count <= 0)) {
2793 se->avg.last_runnable_update = rq_clock_task(rq_of(cfs_rq));
2794 if (se->avg.decay_count) {
2795
2796
2797
2798
2799
2800
2801
2802
2803 se->avg.last_runnable_update -= (-se->avg.decay_count)
2804 << 20;
2805 update_entity_load_avg(se, 0);
2806
2807 se->avg.decay_count = 0;
2808 }
2809 wakeup = 0;
2810 } else {
2811 __synchronize_entity_decay(se);
2812 }
2813
2814
2815 if (wakeup) {
2816 subtract_blocked_load_contrib(cfs_rq, se->avg.load_avg_contrib);
2817 update_entity_load_avg(se, 0);
2818 }
2819
2820 cfs_rq->runnable_load_avg += se->avg.load_avg_contrib;
2821
2822 update_cfs_rq_blocked_load(cfs_rq, !wakeup);
2823}
2824
2825
2826
2827
2828
2829
2830static inline void dequeue_entity_load_avg(struct cfs_rq *cfs_rq,
2831 struct sched_entity *se,
2832 int sleep)
2833{
2834 update_entity_load_avg(se, 1);
2835
2836 update_cfs_rq_blocked_load(cfs_rq, !sleep);
2837
2838 cfs_rq->runnable_load_avg -= se->avg.load_avg_contrib;
2839 if (sleep) {
2840 cfs_rq->blocked_load_avg += se->avg.load_avg_contrib;
2841 se->avg.decay_count = atomic64_read(&cfs_rq->decay_counter);
2842 }
2843}
2844
2845
2846
2847
2848
2849
2850void idle_enter_fair(struct rq *this_rq)
2851{
2852 update_rq_runnable_avg(this_rq, 1);
2853}
2854
2855
2856
2857
2858
2859
2860void idle_exit_fair(struct rq *this_rq)
2861{
2862 update_rq_runnable_avg(this_rq, 0);
2863}
2864
2865static int idle_balance(struct rq *this_rq);
2866
2867#else
2868
2869static inline void update_entity_load_avg(struct sched_entity *se,
2870 int update_cfs_rq) {}
2871static inline void update_rq_runnable_avg(struct rq *rq, int runnable) {}
2872static inline void enqueue_entity_load_avg(struct cfs_rq *cfs_rq,
2873 struct sched_entity *se,
2874 int wakeup) {}
2875static inline void dequeue_entity_load_avg(struct cfs_rq *cfs_rq,
2876 struct sched_entity *se,
2877 int sleep) {}
2878static inline void update_cfs_rq_blocked_load(struct cfs_rq *cfs_rq,
2879 int force_update) {}
2880
2881static inline int idle_balance(struct rq *rq)
2882{
2883 return 0;
2884}
2885
2886#endif
2887
2888static void enqueue_sleeper(struct cfs_rq *cfs_rq, struct sched_entity *se)
2889{
2890#ifdef CONFIG_SCHEDSTATS
2891 struct task_struct *tsk = NULL;
2892
2893 if (entity_is_task(se))
2894 tsk = task_of(se);
2895
2896 if (se->statistics.sleep_start) {
2897 u64 delta = rq_clock(rq_of(cfs_rq)) - se->statistics.sleep_start;
2898
2899 if ((s64)delta < 0)
2900 delta = 0;
2901
2902 if (unlikely(delta > se->statistics.sleep_max))
2903 se->statistics.sleep_max = delta;
2904
2905 se->statistics.sleep_start = 0;
2906 se->statistics.sum_sleep_runtime += delta;
2907
2908 if (tsk) {
2909 account_scheduler_latency(tsk, delta >> 10, 1);
2910 trace_sched_stat_sleep(tsk, delta);
2911 }
2912 }
2913 if (se->statistics.block_start) {
2914 u64 delta = rq_clock(rq_of(cfs_rq)) - se->statistics.block_start;
2915
2916 if ((s64)delta < 0)
2917 delta = 0;
2918
2919 if (unlikely(delta > se->statistics.block_max))
2920 se->statistics.block_max = delta;
2921
2922 se->statistics.block_start = 0;
2923 se->statistics.sum_sleep_runtime += delta;
2924
2925 if (tsk) {
2926 if (tsk->in_iowait) {
2927 se->statistics.iowait_sum += delta;
2928 se->statistics.iowait_count++;
2929 trace_sched_stat_iowait(tsk, delta);
2930 }
2931
2932 trace_sched_stat_blocked(tsk, delta);
2933
2934
2935
2936
2937
2938
2939 if (unlikely(prof_on == SLEEP_PROFILING)) {
2940 profile_hits(SLEEP_PROFILING,
2941 (void *)get_wchan(tsk),
2942 delta >> 20);
2943 }
2944 account_scheduler_latency(tsk, delta >> 10, 0);
2945 }
2946 }
2947#endif
2948}
2949
2950static void check_spread(struct cfs_rq *cfs_rq, struct sched_entity *se)
2951{
2952#ifdef CONFIG_SCHED_DEBUG
2953 s64 d = se->vruntime - cfs_rq->min_vruntime;
2954
2955 if (d < 0)
2956 d = -d;
2957
2958 if (d > 3*sysctl_sched_latency)
2959 schedstat_inc(cfs_rq, nr_spread_over);
2960#endif
2961}
2962
2963static void
2964place_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int initial)
2965{
2966 u64 vruntime = cfs_rq->min_vruntime;
2967
2968
2969
2970
2971
2972
2973
2974 if (initial && sched_feat(START_DEBIT))
2975 vruntime += sched_vslice(cfs_rq, se);
2976
2977
2978 if (!initial) {
2979 unsigned long thresh = sysctl_sched_latency;
2980
2981
2982
2983
2984
2985 if (sched_feat(GENTLE_FAIR_SLEEPERS))
2986 thresh >>= 1;
2987
2988 vruntime -= thresh;
2989 }
2990
2991
2992 se->vruntime = max_vruntime(se->vruntime, vruntime);
2993}
2994
2995static void check_enqueue_throttle(struct cfs_rq *cfs_rq);
2996
2997static void
2998enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
2999{
3000
3001
3002
3003
3004 if (!(flags & ENQUEUE_WAKEUP) || (flags & ENQUEUE_WAKING))
3005 se->vruntime += cfs_rq->min_vruntime;
3006
3007
3008
3009
3010 update_curr(cfs_rq);
3011 enqueue_entity_load_avg(cfs_rq, se, flags & ENQUEUE_WAKEUP);
3012 account_entity_enqueue(cfs_rq, se);
3013 update_cfs_shares(cfs_rq);
3014
3015 if (flags & ENQUEUE_WAKEUP) {
3016 place_entity(cfs_rq, se, 0);
3017 enqueue_sleeper(cfs_rq, se);
3018 }
3019
3020 update_stats_enqueue(cfs_rq, se);
3021 check_spread(cfs_rq, se);
3022 if (se != cfs_rq->curr)
3023 __enqueue_entity(cfs_rq, se);
3024 se->on_rq = 1;
3025
3026 if (cfs_rq->nr_running == 1) {
3027 list_add_leaf_cfs_rq(cfs_rq);
3028 check_enqueue_throttle(cfs_rq);
3029 }
3030}
3031
3032static void __clear_buddies_last(struct sched_entity *se)
3033{
3034 for_each_sched_entity(se) {
3035 struct cfs_rq *cfs_rq = cfs_rq_of(se);
3036 if (cfs_rq->last != se)
3037 break;
3038
3039 cfs_rq->last = NULL;
3040 }
3041}
3042
3043static void __clear_buddies_next(struct sched_entity *se)
3044{
3045 for_each_sched_entity(se) {
3046 struct cfs_rq *cfs_rq = cfs_rq_of(se);
3047 if (cfs_rq->next != se)
3048 break;
3049
3050 cfs_rq->next = NULL;
3051 }
3052}
3053
3054static void __clear_buddies_skip(struct sched_entity *se)
3055{
3056 for_each_sched_entity(se) {
3057 struct cfs_rq *cfs_rq = cfs_rq_of(se);
3058 if (cfs_rq->skip != se)
3059 break;
3060
3061 cfs_rq->skip = NULL;
3062 }
3063}
3064
3065static void clear_buddies(struct cfs_rq *cfs_rq, struct sched_entity *se)
3066{
3067 if (cfs_rq->last == se)
3068 __clear_buddies_last(se);
3069
3070 if (cfs_rq->next == se)
3071 __clear_buddies_next(se);
3072
3073 if (cfs_rq->skip == se)
3074 __clear_buddies_skip(se);
3075}
3076
3077static __always_inline void return_cfs_rq_runtime(struct cfs_rq *cfs_rq);
3078
3079static void
3080dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
3081{
3082
3083
3084
3085 update_curr(cfs_rq);
3086 dequeue_entity_load_avg(cfs_rq, se, flags & DEQUEUE_SLEEP);
3087
3088 update_stats_dequeue(cfs_rq, se);
3089 if (flags & DEQUEUE_SLEEP) {
3090#ifdef CONFIG_SCHEDSTATS
3091 if (entity_is_task(se)) {
3092 struct task_struct *tsk = task_of(se);
3093
3094 if (tsk->state & TASK_INTERRUPTIBLE)
3095 se->statistics.sleep_start = rq_clock(rq_of(cfs_rq));
3096 if (tsk->state & TASK_UNINTERRUPTIBLE)
3097 se->statistics.block_start = rq_clock(rq_of(cfs_rq));
3098 }
3099#endif
3100 }
3101
3102 clear_buddies(cfs_rq, se);
3103
3104 if (se != cfs_rq->curr)
3105 __dequeue_entity(cfs_rq, se);
3106 se->on_rq = 0;
3107 account_entity_dequeue(cfs_rq, se);
3108
3109
3110
3111
3112
3113
3114 if (!(flags & DEQUEUE_SLEEP))
3115 se->vruntime -= cfs_rq->min_vruntime;
3116
3117
3118 return_cfs_rq_runtime(cfs_rq);
3119
3120 update_min_vruntime(cfs_rq);
3121 update_cfs_shares(cfs_rq);
3122}
3123
3124
3125
3126
3127static void
3128check_preempt_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr)
3129{
3130 unsigned long ideal_runtime, delta_exec;
3131 struct sched_entity *se;
3132 s64 delta;
3133
3134 ideal_runtime = sched_slice(cfs_rq, curr);
3135 delta_exec = curr->sum_exec_runtime - curr->prev_sum_exec_runtime;
3136 if (delta_exec > ideal_runtime) {
3137 resched_curr(rq_of(cfs_rq));
3138
3139
3140
3141
3142 clear_buddies(cfs_rq, curr);
3143 return;
3144 }
3145
3146
3147
3148
3149
3150
3151 if (delta_exec < sysctl_sched_min_granularity)
3152 return;
3153
3154 se = __pick_first_entity(cfs_rq);
3155 delta = curr->vruntime - se->vruntime;
3156
3157 if (delta < 0)
3158 return;
3159
3160 if (delta > ideal_runtime)
3161 resched_curr(rq_of(cfs_rq));
3162}
3163
3164static void
3165set_next_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
3166{
3167
3168 if (se->on_rq) {
3169
3170
3171
3172
3173
3174 update_stats_wait_end(cfs_rq, se);
3175 __dequeue_entity(cfs_rq, se);
3176 }
3177
3178 update_stats_curr_start(cfs_rq, se);
3179 cfs_rq->curr = se;
3180#ifdef CONFIG_SCHEDSTATS
3181
3182
3183
3184
3185
3186 if (rq_of(cfs_rq)->load.weight >= 2*se->load.weight) {
3187 se->statistics.slice_max = max(se->statistics.slice_max,
3188 se->sum_exec_runtime - se->prev_sum_exec_runtime);
3189 }
3190#endif
3191 se->prev_sum_exec_runtime = se->sum_exec_runtime;
3192}
3193
3194static int
3195wakeup_preempt_entity(struct sched_entity *curr, struct sched_entity *se);
3196
3197
3198
3199
3200
3201
3202
3203
3204static struct sched_entity *
3205pick_next_entity(struct cfs_rq *cfs_rq, struct sched_entity *curr)
3206{
3207 struct sched_entity *left = __pick_first_entity(cfs_rq);
3208 struct sched_entity *se;
3209
3210
3211
3212
3213
3214 if (!left || (curr && entity_before(curr, left)))
3215 left = curr;
3216
3217 se = left;
3218
3219
3220
3221
3222
3223 if (cfs_rq->skip == se) {
3224 struct sched_entity *second;
3225
3226 if (se == curr) {
3227 second = __pick_first_entity(cfs_rq);
3228 } else {
3229 second = __pick_next_entity(se);
3230 if (!second || (curr && entity_before(curr, second)))
3231 second = curr;
3232 }
3233
3234 if (second && wakeup_preempt_entity(second, left) < 1)
3235 se = second;
3236 }
3237
3238
3239
3240
3241 if (cfs_rq->last && wakeup_preempt_entity(cfs_rq->last, left) < 1)
3242 se = cfs_rq->last;
3243
3244
3245
3246
3247 if (cfs_rq->next && wakeup_preempt_entity(cfs_rq->next, left) < 1)
3248 se = cfs_rq->next;
3249
3250 clear_buddies(cfs_rq, se);
3251
3252 return se;
3253}
3254
3255static bool check_cfs_rq_runtime(struct cfs_rq *cfs_rq);
3256
3257static void put_prev_entity(struct cfs_rq *cfs_rq, struct sched_entity *prev)
3258{
3259
3260
3261
3262
3263 if (prev->on_rq)
3264 update_curr(cfs_rq);
3265
3266
3267 check_cfs_rq_runtime(cfs_rq);
3268
3269 check_spread(cfs_rq, prev);
3270 if (prev->on_rq) {
3271 update_stats_wait_start(cfs_rq, prev);
3272
3273 __enqueue_entity(cfs_rq, prev);
3274
3275 update_entity_load_avg(prev, 1);
3276 }
3277 cfs_rq->curr = NULL;
3278}
3279
3280static void
3281entity_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr, int queued)
3282{
3283
3284
3285
3286 update_curr(cfs_rq);
3287
3288
3289
3290
3291 update_entity_load_avg(curr, 1);
3292 update_cfs_rq_blocked_load(cfs_rq, 1);
3293 update_cfs_shares(cfs_rq);
3294
3295#ifdef CONFIG_SCHED_HRTICK
3296
3297
3298
3299
3300 if (queued) {
3301 resched_curr(rq_of(cfs_rq));
3302 return;
3303 }
3304
3305
3306
3307 if (!sched_feat(DOUBLE_TICK) &&
3308 hrtimer_active(&rq_of(cfs_rq)->hrtick_timer))
3309 return;
3310#endif
3311
3312 if (cfs_rq->nr_running > 1)
3313 check_preempt_tick(cfs_rq, curr);
3314}
3315
3316
3317
3318
3319
3320
3321#ifdef CONFIG_CFS_BANDWIDTH
3322
3323#ifdef HAVE_JUMP_LABEL
3324static struct static_key __cfs_bandwidth_used;
3325
3326static inline bool cfs_bandwidth_used(void)
3327{
3328 return static_key_false(&__cfs_bandwidth_used);
3329}
3330
3331void cfs_bandwidth_usage_inc(void)
3332{
3333 static_key_slow_inc(&__cfs_bandwidth_used);
3334}
3335
3336void cfs_bandwidth_usage_dec(void)
3337{
3338 static_key_slow_dec(&__cfs_bandwidth_used);
3339}
3340#else
3341static bool cfs_bandwidth_used(void)
3342{
3343 return true;
3344}
3345
3346void cfs_bandwidth_usage_inc(void) {}
3347void cfs_bandwidth_usage_dec(void) {}
3348#endif
3349
3350
3351
3352
3353
3354static inline u64 default_cfs_period(void)
3355{
3356 return 100000000ULL;
3357}
3358
3359static inline u64 sched_cfs_bandwidth_slice(void)
3360{
3361 return (u64)sysctl_sched_cfs_bandwidth_slice * NSEC_PER_USEC;
3362}
3363
3364
3365
3366
3367
3368
3369
3370
3371void __refill_cfs_bandwidth_runtime(struct cfs_bandwidth *cfs_b)
3372{
3373 u64 now;
3374
3375 if (cfs_b->quota == RUNTIME_INF)
3376 return;
3377
3378 now = sched_clock_cpu(smp_processor_id());
3379 cfs_b->runtime = cfs_b->quota;
3380 cfs_b->runtime_expires = now + ktime_to_ns(cfs_b->period);
3381}
3382
3383static inline struct cfs_bandwidth *tg_cfs_bandwidth(struct task_group *tg)
3384{
3385 return &tg->cfs_bandwidth;
3386}
3387
3388
3389static inline u64 cfs_rq_clock_task(struct cfs_rq *cfs_rq)
3390{
3391 if (unlikely(cfs_rq->throttle_count))
3392 return cfs_rq->throttled_clock_task;
3393
3394 return rq_clock_task(rq_of(cfs_rq)) - cfs_rq->throttled_clock_task_time;
3395}
3396
3397
3398static int assign_cfs_rq_runtime(struct cfs_rq *cfs_rq)
3399{
3400 struct task_group *tg = cfs_rq->tg;
3401 struct cfs_bandwidth *cfs_b = tg_cfs_bandwidth(tg);
3402 u64 amount = 0, min_amount, expires;
3403
3404
3405 min_amount = sched_cfs_bandwidth_slice() - cfs_rq->runtime_remaining;
3406
3407 raw_spin_lock(&cfs_b->lock);
3408 if (cfs_b->quota == RUNTIME_INF)
3409 amount = min_amount;
3410 else {
3411
3412
3413
3414
3415
3416
3417 if (!cfs_b->timer_active) {
3418 __refill_cfs_bandwidth_runtime(cfs_b);
3419 __start_cfs_bandwidth(cfs_b, false);
3420 }
3421
3422 if (cfs_b->runtime > 0) {
3423 amount = min(cfs_b->runtime, min_amount);
3424 cfs_b->runtime -= amount;
3425 cfs_b->idle = 0;
3426 }
3427 }
3428 expires = cfs_b->runtime_expires;
3429 raw_spin_unlock(&cfs_b->lock);
3430
3431 cfs_rq->runtime_remaining += amount;
3432
3433
3434
3435
3436
3437 if ((s64)(expires - cfs_rq->runtime_expires) > 0)
3438 cfs_rq->runtime_expires = expires;
3439
3440 return cfs_rq->runtime_remaining > 0;
3441}
3442
3443
3444
3445
3446
3447static void expire_cfs_rq_runtime(struct cfs_rq *cfs_rq)
3448{
3449 struct cfs_bandwidth *cfs_b = tg_cfs_bandwidth(cfs_rq->tg);
3450
3451
3452 if (likely((s64)(rq_clock(rq_of(cfs_rq)) - cfs_rq->runtime_expires) < 0))
3453 return;
3454
3455 if (cfs_rq->runtime_remaining < 0)
3456 return;
3457
3458
3459
3460
3461
3462
3463
3464
3465
3466
3467
3468
3469 if (cfs_rq->runtime_expires != cfs_b->runtime_expires) {
3470
3471 cfs_rq->runtime_expires += TICK_NSEC;
3472 } else {
3473
3474 cfs_rq->runtime_remaining = 0;
3475 }
3476}
3477
3478static void __account_cfs_rq_runtime(struct cfs_rq *cfs_rq, u64 delta_exec)
3479{
3480
3481 cfs_rq->runtime_remaining -= delta_exec;
3482 expire_cfs_rq_runtime(cfs_rq);
3483
3484 if (likely(cfs_rq->runtime_remaining > 0))
3485 return;
3486
3487
3488
3489
3490
3491 if (!assign_cfs_rq_runtime(cfs_rq) && likely(cfs_rq->curr))
3492 resched_curr(rq_of(cfs_rq));
3493}
3494
3495static __always_inline
3496void account_cfs_rq_runtime(struct cfs_rq *cfs_rq, u64 delta_exec)
3497{
3498 if (!cfs_bandwidth_used() || !cfs_rq->runtime_enabled)
3499 return;
3500
3501 __account_cfs_rq_runtime(cfs_rq, delta_exec);
3502}
3503
3504static inline int cfs_rq_throttled(struct cfs_rq *cfs_rq)
3505{
3506 return cfs_bandwidth_used() && cfs_rq->throttled;
3507}
3508
3509
3510static inline int throttled_hierarchy(struct cfs_rq *cfs_rq)
3511{
3512 return cfs_bandwidth_used() && cfs_rq->throttle_count;
3513}
3514
3515
3516
3517
3518
3519
3520static inline int throttled_lb_pair(struct task_group *tg,
3521 int src_cpu, int dest_cpu)
3522{
3523 struct cfs_rq *src_cfs_rq, *dest_cfs_rq;
3524
3525 src_cfs_rq = tg->cfs_rq[src_cpu];
3526 dest_cfs_rq = tg->cfs_rq[dest_cpu];
3527
3528 return throttled_hierarchy(src_cfs_rq) ||
3529 throttled_hierarchy(dest_cfs_rq);
3530}
3531
3532
3533static int tg_unthrottle_up(struct task_group *tg, void *data)
3534{
3535 struct rq *rq = data;
3536 struct cfs_rq *cfs_rq = tg->cfs_rq[cpu_of(rq)];
3537
3538 cfs_rq->throttle_count--;
3539#ifdef CONFIG_SMP
3540 if (!cfs_rq->throttle_count) {
3541
3542 cfs_rq->throttled_clock_task_time += rq_clock_task(rq) -
3543 cfs_rq->throttled_clock_task;
3544 }
3545#endif
3546
3547 return 0;
3548}
3549
3550static int tg_throttle_down(struct task_group *tg, void *data)
3551{
3552 struct rq *rq = data;
3553 struct cfs_rq *cfs_rq = tg->cfs_rq[cpu_of(rq)];
3554
3555
3556 if (!cfs_rq->throttle_count)
3557 cfs_rq->throttled_clock_task = rq_clock_task(rq);
3558 cfs_rq->throttle_count++;
3559
3560 return 0;
3561}
3562
3563static void throttle_cfs_rq(struct cfs_rq *cfs_rq)
3564{
3565 struct rq *rq = rq_of(cfs_rq);
3566 struct cfs_bandwidth *cfs_b = tg_cfs_bandwidth(cfs_rq->tg);
3567 struct sched_entity *se;
3568 long task_delta, dequeue = 1;
3569
3570 se = cfs_rq->tg->se[cpu_of(rq_of(cfs_rq))];
3571
3572
3573 rcu_read_lock();
3574 walk_tg_tree_from(cfs_rq->tg, tg_throttle_down, tg_nop, (void *)rq);
3575 rcu_read_unlock();
3576
3577 task_delta = cfs_rq->h_nr_running;
3578 for_each_sched_entity(se) {
3579 struct cfs_rq *qcfs_rq = cfs_rq_of(se);
3580
3581 if (!se->on_rq)
3582 break;
3583
3584 if (dequeue)
3585 dequeue_entity(qcfs_rq, se, DEQUEUE_SLEEP);
3586 qcfs_rq->h_nr_running -= task_delta;
3587
3588 if (qcfs_rq->load.weight)
3589 dequeue = 0;
3590 }
3591
3592 if (!se)
3593 sub_nr_running(rq, task_delta);
3594
3595 cfs_rq->throttled = 1;
3596 cfs_rq->throttled_clock = rq_clock(rq);
3597 raw_spin_lock(&cfs_b->lock);
3598
3599
3600
3601
3602 list_add_rcu(&cfs_rq->throttled_list, &cfs_b->throttled_cfs_rq);
3603 if (!cfs_b->timer_active)
3604 __start_cfs_bandwidth(cfs_b, false);
3605 raw_spin_unlock(&cfs_b->lock);
3606}
3607
3608void unthrottle_cfs_rq(struct cfs_rq *cfs_rq)
3609{
3610 struct rq *rq = rq_of(cfs_rq);
3611 struct cfs_bandwidth *cfs_b = tg_cfs_bandwidth(cfs_rq->tg);
3612 struct sched_entity *se;
3613 int enqueue = 1;
3614 long task_delta;
3615
3616 se = cfs_rq->tg->se[cpu_of(rq)];
3617
3618 cfs_rq->throttled = 0;
3619
3620 update_rq_clock(rq);
3621
3622 raw_spin_lock(&cfs_b->lock);
3623 cfs_b->throttled_time += rq_clock(rq) - cfs_rq->throttled_clock;
3624 list_del_rcu(&cfs_rq->throttled_list);
3625 raw_spin_unlock(&cfs_b->lock);
3626
3627
3628 walk_tg_tree_from(cfs_rq->tg, tg_nop, tg_unthrottle_up, (void *)rq);
3629
3630 if (!cfs_rq->load.weight)
3631 return;
3632
3633 task_delta = cfs_rq->h_nr_running;
3634 for_each_sched_entity(se) {
3635 if (se->on_rq)
3636 enqueue = 0;
3637
3638 cfs_rq = cfs_rq_of(se);
3639 if (enqueue)
3640 enqueue_entity(cfs_rq, se, ENQUEUE_WAKEUP);
3641 cfs_rq->h_nr_running += task_delta;
3642
3643 if (cfs_rq_throttled(cfs_rq))
3644 break;
3645 }
3646
3647 if (!se)
3648 add_nr_running(rq, task_delta);
3649
3650
3651 if (rq->curr == rq->idle && rq->cfs.nr_running)
3652 resched_curr(rq);
3653}
3654
3655static u64 distribute_cfs_runtime(struct cfs_bandwidth *cfs_b,
3656 u64 remaining, u64 expires)
3657{
3658 struct cfs_rq *cfs_rq;
3659 u64 runtime;
3660 u64 starting_runtime = remaining;
3661
3662 rcu_read_lock();
3663 list_for_each_entry_rcu(cfs_rq, &cfs_b->throttled_cfs_rq,
3664 throttled_list) {
3665 struct rq *rq = rq_of(cfs_rq);
3666
3667 raw_spin_lock(&rq->lock);
3668 if (!cfs_rq_throttled(cfs_rq))
3669 goto next;
3670
3671 runtime = -cfs_rq->runtime_remaining + 1;
3672 if (runtime > remaining)
3673 runtime = remaining;
3674 remaining -= runtime;
3675
3676 cfs_rq->runtime_remaining += runtime;
3677 cfs_rq->runtime_expires = expires;
3678
3679
3680 if (cfs_rq->runtime_remaining > 0)
3681 unthrottle_cfs_rq(cfs_rq);
3682
3683next:
3684 raw_spin_unlock(&rq->lock);
3685
3686 if (!remaining)
3687 break;
3688 }
3689 rcu_read_unlock();
3690
3691 return starting_runtime - remaining;
3692}
3693
3694
3695
3696
3697
3698
3699
3700static int do_sched_cfs_period_timer(struct cfs_bandwidth *cfs_b, int overrun)
3701{
3702 u64 runtime, runtime_expires;
3703 int throttled;
3704
3705
3706 if (cfs_b->quota == RUNTIME_INF)
3707 goto out_deactivate;
3708
3709 throttled = !list_empty(&cfs_b->throttled_cfs_rq);
3710 cfs_b->nr_periods += overrun;
3711
3712
3713
3714
3715
3716 if (cfs_b->idle && !throttled)
3717 goto out_deactivate;
3718
3719
3720
3721
3722
3723
3724 cfs_b->timer_active = 1;
3725
3726 __refill_cfs_bandwidth_runtime(cfs_b);
3727
3728 if (!throttled) {
3729
3730 cfs_b->idle = 1;
3731 return 0;
3732 }
3733
3734
3735 cfs_b->nr_throttled += overrun;
3736
3737 runtime_expires = cfs_b->runtime_expires;
3738
3739
3740
3741
3742
3743
3744
3745
3746 while (throttled && cfs_b->runtime > 0) {
3747 runtime = cfs_b->runtime;
3748 raw_spin_unlock(&cfs_b->lock);
3749
3750 runtime = distribute_cfs_runtime(cfs_b, runtime,
3751 runtime_expires);
3752 raw_spin_lock(&cfs_b->lock);
3753
3754 throttled = !list_empty(&cfs_b->throttled_cfs_rq);
3755
3756 cfs_b->runtime -= min(runtime, cfs_b->runtime);
3757 }
3758
3759
3760
3761
3762
3763
3764
3765 cfs_b->idle = 0;
3766
3767 return 0;
3768
3769out_deactivate:
3770 cfs_b->timer_active = 0;
3771 return 1;
3772}
3773
3774
3775static const u64 min_cfs_rq_runtime = 1 * NSEC_PER_MSEC;
3776
3777static const u64 min_bandwidth_expiration = 2 * NSEC_PER_MSEC;
3778
3779static const u64 cfs_bandwidth_slack_period = 5 * NSEC_PER_MSEC;
3780
3781
3782
3783
3784
3785
3786
3787
3788static int runtime_refresh_within(struct cfs_bandwidth *cfs_b, u64 min_expire)
3789{
3790 struct hrtimer *refresh_timer = &cfs_b->period_timer;
3791 u64 remaining;
3792
3793
3794 if (hrtimer_callback_running(refresh_timer))
3795 return 1;
3796
3797
3798 remaining = ktime_to_ns(hrtimer_expires_remaining(refresh_timer));
3799 if (remaining < min_expire)
3800 return 1;
3801
3802 return 0;
3803}
3804
3805static void start_cfs_slack_bandwidth(struct cfs_bandwidth *cfs_b)
3806{
3807 u64 min_left = cfs_bandwidth_slack_period + min_bandwidth_expiration;
3808
3809
3810 if (runtime_refresh_within(cfs_b, min_left))
3811 return;
3812
3813 start_bandwidth_timer(&cfs_b->slack_timer,
3814 ns_to_ktime(cfs_bandwidth_slack_period));
3815}
3816
3817
3818static void __return_cfs_rq_runtime(struct cfs_rq *cfs_rq)
3819{
3820 struct cfs_bandwidth *cfs_b = tg_cfs_bandwidth(cfs_rq->tg);
3821 s64 slack_runtime = cfs_rq->runtime_remaining - min_cfs_rq_runtime;
3822
3823 if (slack_runtime <= 0)
3824 return;
3825
3826 raw_spin_lock(&cfs_b->lock);
3827 if (cfs_b->quota != RUNTIME_INF &&
3828 cfs_rq->runtime_expires == cfs_b->runtime_expires) {
3829 cfs_b->runtime += slack_runtime;
3830
3831
3832 if (cfs_b->runtime > sched_cfs_bandwidth_slice() &&
3833 !list_empty(&cfs_b->throttled_cfs_rq))
3834 start_cfs_slack_bandwidth(cfs_b);
3835 }
3836 raw_spin_unlock(&cfs_b->lock);
3837
3838
3839 cfs_rq->runtime_remaining -= slack_runtime;
3840}
3841
3842static __always_inline void return_cfs_rq_runtime(struct cfs_rq *cfs_rq)
3843{
3844 if (!cfs_bandwidth_used())
3845 return;
3846
3847 if (!cfs_rq->runtime_enabled || cfs_rq->nr_running)
3848 return;
3849
3850 __return_cfs_rq_runtime(cfs_rq);
3851}
3852
3853
3854
3855
3856
3857static void do_sched_cfs_slack_timer(struct cfs_bandwidth *cfs_b)
3858{
3859 u64 runtime = 0, slice = sched_cfs_bandwidth_slice();
3860 u64 expires;
3861
3862
3863 raw_spin_lock(&cfs_b->lock);
3864 if (runtime_refresh_within(cfs_b, min_bandwidth_expiration)) {
3865 raw_spin_unlock(&cfs_b->lock);
3866 return;
3867 }
3868
3869 if (cfs_b->quota != RUNTIME_INF && cfs_b->runtime > slice)
3870 runtime = cfs_b->runtime;
3871
3872 expires = cfs_b->runtime_expires;
3873 raw_spin_unlock(&cfs_b->lock);
3874
3875 if (!runtime)
3876 return;
3877
3878 runtime = distribute_cfs_runtime(cfs_b, runtime, expires);
3879
3880 raw_spin_lock(&cfs_b->lock);
3881 if (expires == cfs_b->runtime_expires)
3882 cfs_b->runtime -= min(runtime, cfs_b->runtime);
3883 raw_spin_unlock(&cfs_b->lock);
3884}
3885
3886
3887
3888
3889
3890
3891static void check_enqueue_throttle(struct cfs_rq *cfs_rq)
3892{
3893 if (!cfs_bandwidth_used())
3894 return;
3895
3896
3897 if (!cfs_rq->runtime_enabled || cfs_rq->curr)
3898 return;
3899
3900
3901 if (cfs_rq_throttled(cfs_rq))
3902 return;
3903
3904
3905 account_cfs_rq_runtime(cfs_rq, 0);
3906 if (cfs_rq->runtime_remaining <= 0)
3907 throttle_cfs_rq(cfs_rq);
3908}
3909
3910
3911static bool check_cfs_rq_runtime(struct cfs_rq *cfs_rq)
3912{
3913 if (!cfs_bandwidth_used())
3914 return false;
3915
3916 if (likely(!cfs_rq->runtime_enabled || cfs_rq->runtime_remaining > 0))
3917 return false;
3918
3919
3920
3921
3922
3923 if (cfs_rq_throttled(cfs_rq))
3924 return true;
3925
3926 throttle_cfs_rq(cfs_rq);
3927 return true;
3928}
3929
3930static enum hrtimer_restart sched_cfs_slack_timer(struct hrtimer *timer)
3931{
3932 struct cfs_bandwidth *cfs_b =
3933 container_of(timer, struct cfs_bandwidth, slack_timer);
3934 do_sched_cfs_slack_timer(cfs_b);
3935
3936 return HRTIMER_NORESTART;
3937}
3938
3939static enum hrtimer_restart sched_cfs_period_timer(struct hrtimer *timer)
3940{
3941 struct cfs_bandwidth *cfs_b =
3942 container_of(timer, struct cfs_bandwidth, period_timer);
3943 ktime_t now;
3944 int overrun;
3945 int idle = 0;
3946
3947 raw_spin_lock(&cfs_b->lock);
3948 for (;;) {
3949 now = hrtimer_cb_get_time(timer);
3950 overrun = hrtimer_forward(timer, now, cfs_b->period);
3951
3952 if (!overrun)
3953 break;
3954
3955 idle = do_sched_cfs_period_timer(cfs_b, overrun);
3956 }
3957 raw_spin_unlock(&cfs_b->lock);
3958
3959 return idle ? HRTIMER_NORESTART : HRTIMER_RESTART;
3960}
3961
3962void init_cfs_bandwidth(struct cfs_bandwidth *cfs_b)
3963{
3964 raw_spin_lock_init(&cfs_b->lock);
3965 cfs_b->runtime = 0;
3966 cfs_b->quota = RUNTIME_INF;
3967 cfs_b->period = ns_to_ktime(default_cfs_period());
3968
3969 INIT_LIST_HEAD(&cfs_b->throttled_cfs_rq);
3970 hrtimer_init(&cfs_b->period_timer, CLOCK_MONOTONIC, HRTIMER_MODE_REL);
3971 cfs_b->period_timer.function = sched_cfs_period_timer;
3972 hrtimer_init(&cfs_b->slack_timer, CLOCK_MONOTONIC, HRTIMER_MODE_REL);
3973 cfs_b->slack_timer.function = sched_cfs_slack_timer;
3974}
3975
3976static void init_cfs_rq_runtime(struct cfs_rq *cfs_rq)
3977{
3978 cfs_rq->runtime_enabled = 0;
3979 INIT_LIST_HEAD(&cfs_rq->throttled_list);
3980}
3981
3982
3983void __start_cfs_bandwidth(struct cfs_bandwidth *cfs_b, bool force)
3984{
3985
3986
3987
3988
3989
3990
3991 while (unlikely(hrtimer_active(&cfs_b->period_timer)) &&
3992 hrtimer_try_to_cancel(&cfs_b->period_timer) < 0) {
3993
3994 raw_spin_unlock(&cfs_b->lock);
3995 cpu_relax();
3996 raw_spin_lock(&cfs_b->lock);
3997
3998 if (!force && cfs_b->timer_active)
3999 return;
4000 }
4001
4002 cfs_b->timer_active = 1;
4003 start_bandwidth_timer(&cfs_b->period_timer, cfs_b->period);
4004}
4005
4006static void destroy_cfs_bandwidth(struct cfs_bandwidth *cfs_b)
4007{
4008
4009 if (!cfs_b->throttled_cfs_rq.next)
4010 return;
4011
4012 hrtimer_cancel(&cfs_b->period_timer);
4013 hrtimer_cancel(&cfs_b->slack_timer);
4014}
4015
4016static void __maybe_unused update_runtime_enabled(struct rq *rq)
4017{
4018 struct cfs_rq *cfs_rq;
4019
4020 for_each_leaf_cfs_rq(rq, cfs_rq) {
4021 struct cfs_bandwidth *cfs_b = &cfs_rq->tg->cfs_bandwidth;
4022
4023 raw_spin_lock(&cfs_b->lock);
4024 cfs_rq->runtime_enabled = cfs_b->quota != RUNTIME_INF;
4025 raw_spin_unlock(&cfs_b->lock);
4026 }
4027}
4028
4029static void __maybe_unused unthrottle_offline_cfs_rqs(struct rq *rq)
4030{
4031 struct cfs_rq *cfs_rq;
4032
4033 for_each_leaf_cfs_rq(rq, cfs_rq) {
4034 if (!cfs_rq->runtime_enabled)
4035 continue;
4036
4037
4038
4039
4040
4041 cfs_rq->runtime_remaining = 1;
4042
4043
4044
4045
4046 cfs_rq->runtime_enabled = 0;
4047
4048 if (cfs_rq_throttled(cfs_rq))
4049 unthrottle_cfs_rq(cfs_rq);
4050 }
4051}
4052
4053#else
4054static inline u64 cfs_rq_clock_task(struct cfs_rq *cfs_rq)
4055{
4056 return rq_clock_task(rq_of(cfs_rq));
4057}
4058
4059static void account_cfs_rq_runtime(struct cfs_rq *cfs_rq, u64 delta_exec) {}
4060static bool check_cfs_rq_runtime(struct cfs_rq *cfs_rq) { return false; }
4061static void check_enqueue_throttle(struct cfs_rq *cfs_rq) {}
4062static __always_inline void return_cfs_rq_runtime(struct cfs_rq *cfs_rq) {}
4063
4064static inline int cfs_rq_throttled(struct cfs_rq *cfs_rq)
4065{
4066 return 0;
4067}
4068
4069static inline int throttled_hierarchy(struct cfs_rq *cfs_rq)
4070{
4071 return 0;
4072}
4073
4074static inline int throttled_lb_pair(struct task_group *tg,
4075 int src_cpu, int dest_cpu)
4076{
4077 return 0;
4078}
4079
4080void init_cfs_bandwidth(struct cfs_bandwidth *cfs_b) {}
4081
4082#ifdef CONFIG_FAIR_GROUP_SCHED
4083static void init_cfs_rq_runtime(struct cfs_rq *cfs_rq) {}
4084#endif
4085
4086static inline struct cfs_bandwidth *tg_cfs_bandwidth(struct task_group *tg)
4087{
4088 return NULL;
4089}
4090static inline void destroy_cfs_bandwidth(struct cfs_bandwidth *cfs_b) {}
4091static inline void update_runtime_enabled(struct rq *rq) {}
4092static inline void unthrottle_offline_cfs_rqs(struct rq *rq) {}
4093
4094#endif
4095
4096
4097
4098
4099
4100#ifdef CONFIG_SCHED_HRTICK
4101static void hrtick_start_fair(struct rq *rq, struct task_struct *p)
4102{
4103 struct sched_entity *se = &p->se;
4104 struct cfs_rq *cfs_rq = cfs_rq_of(se);
4105
4106 WARN_ON(task_rq(p) != rq);
4107
4108 if (cfs_rq->nr_running > 1) {
4109 u64 slice = sched_slice(cfs_rq, se);
4110 u64 ran = se->sum_exec_runtime - se->prev_sum_exec_runtime;
4111 s64 delta = slice - ran;
4112
4113 if (delta < 0) {
4114 if (rq->curr == p)
4115 resched_curr(rq);
4116 return;
4117 }
4118 hrtick_start(rq, delta);
4119 }
4120}
4121
4122
4123
4124
4125
4126
4127static void hrtick_update(struct rq *rq)
4128{
4129 struct task_struct *curr = rq->curr;
4130
4131 if (!hrtick_enabled(rq) || curr->sched_class != &fair_sched_class)
4132 return;
4133
4134 if (cfs_rq_of(&curr->se)->nr_running < sched_nr_latency)
4135 hrtick_start_fair(rq, curr);
4136}
4137#else
4138static inline void
4139hrtick_start_fair(struct rq *rq, struct task_struct *p)
4140{
4141}
4142
4143static inline void hrtick_update(struct rq *rq)
4144{
4145}
4146#endif
4147
4148
4149
4150
4151
4152
4153static void
4154enqueue_task_fair(struct rq *rq, struct task_struct *p, int flags)
4155{
4156 struct cfs_rq *cfs_rq;
4157 struct sched_entity *se = &p->se;
4158
4159 for_each_sched_entity(se) {
4160 if (se->on_rq)
4161 break;
4162 cfs_rq = cfs_rq_of(se);
4163 enqueue_entity(cfs_rq, se, flags);
4164
4165
4166
4167
4168
4169
4170
4171 if (cfs_rq_throttled(cfs_rq))
4172 break;
4173 cfs_rq->h_nr_running++;
4174
4175 flags = ENQUEUE_WAKEUP;
4176 }
4177
4178 for_each_sched_entity(se) {
4179 cfs_rq = cfs_rq_of(se);
4180 cfs_rq->h_nr_running++;
4181
4182 if (cfs_rq_throttled(cfs_rq))
4183 break;
4184
4185 update_cfs_shares(cfs_rq);
4186 update_entity_load_avg(se, 1);
4187 }
4188
4189 if (!se) {
4190 update_rq_runnable_avg(rq, rq->nr_running);
4191 add_nr_running(rq, 1);
4192 }
4193 hrtick_update(rq);
4194}
4195
4196static void set_next_buddy(struct sched_entity *se);
4197
4198
4199
4200
4201
4202
4203static void dequeue_task_fair(struct rq *rq, struct task_struct *p, int flags)
4204{
4205 struct cfs_rq *cfs_rq;
4206 struct sched_entity *se = &p->se;
4207 int task_sleep = flags & DEQUEUE_SLEEP;
4208
4209 for_each_sched_entity(se) {
4210 cfs_rq = cfs_rq_of(se);
4211 dequeue_entity(cfs_rq, se, flags);
4212
4213
4214
4215
4216
4217
4218
4219 if (cfs_rq_throttled(cfs_rq))
4220 break;
4221 cfs_rq->h_nr_running--;
4222
4223
4224 if (cfs_rq->load.weight) {
4225
4226
4227
4228
4229 if (task_sleep && parent_entity(se))
4230 set_next_buddy(parent_entity(se));
4231
4232
4233 se = parent_entity(se);
4234 break;
4235 }
4236 flags |= DEQUEUE_SLEEP;
4237 }
4238
4239 for_each_sched_entity(se) {
4240 cfs_rq = cfs_rq_of(se);
4241 cfs_rq->h_nr_running--;
4242
4243 if (cfs_rq_throttled(cfs_rq))
4244 break;
4245
4246 update_cfs_shares(cfs_rq);
4247 update_entity_load_avg(se, 1);
4248 }
4249
4250 if (!se) {
4251 sub_nr_running(rq, 1);
4252 update_rq_runnable_avg(rq, 1);
4253 }
4254 hrtick_update(rq);
4255}
4256
4257#ifdef CONFIG_SMP
4258
4259static unsigned long weighted_cpuload(const int cpu)
4260{
4261 return cpu_rq(cpu)->cfs.runnable_load_avg;
4262}
4263
4264
4265
4266
4267
4268
4269
4270
4271static unsigned long source_load(int cpu, int type)
4272{
4273 struct rq *rq = cpu_rq(cpu);
4274 unsigned long total = weighted_cpuload(cpu);
4275
4276 if (type == 0 || !sched_feat(LB_BIAS))
4277 return total;
4278
4279 return min(rq->cpu_load[type-1], total);
4280}
4281
4282
4283
4284
4285
4286static unsigned long target_load(int cpu, int type)
4287{
4288 struct rq *rq = cpu_rq(cpu);
4289 unsigned long total = weighted_cpuload(cpu);
4290
4291 if (type == 0 || !sched_feat(LB_BIAS))
4292 return total;
4293
4294 return max(rq->cpu_load[type-1], total);
4295}
4296
4297static unsigned long capacity_of(int cpu)
4298{
4299 return cpu_rq(cpu)->cpu_capacity;
4300}
4301
4302static unsigned long cpu_avg_load_per_task(int cpu)
4303{
4304 struct rq *rq = cpu_rq(cpu);
4305 unsigned long nr_running = ACCESS_ONCE(rq->cfs.h_nr_running);
4306 unsigned long load_avg = rq->cfs.runnable_load_avg;
4307
4308 if (nr_running)
4309 return load_avg / nr_running;
4310
4311 return 0;
4312}
4313
4314static void record_wakee(struct task_struct *p)
4315{
4316
4317
4318
4319
4320
4321 if (time_after(jiffies, current->wakee_flip_decay_ts + HZ)) {
4322 current->wakee_flips >>= 1;
4323 current->wakee_flip_decay_ts = jiffies;
4324 }
4325
4326 if (current->last_wakee != p) {
4327 current->last_wakee = p;
4328 current->wakee_flips++;
4329 }
4330}
4331
4332static void task_waking_fair(struct task_struct *p)
4333{
4334 struct sched_entity *se = &p->se;
4335 struct cfs_rq *cfs_rq = cfs_rq_of(se);
4336 u64 min_vruntime;
4337
4338#ifndef CONFIG_64BIT
4339 u64 min_vruntime_copy;
4340
4341 do {
4342 min_vruntime_copy = cfs_rq->min_vruntime_copy;
4343 smp_rmb();
4344 min_vruntime = cfs_rq->min_vruntime;
4345 } while (min_vruntime != min_vruntime_copy);
4346#else
4347 min_vruntime = cfs_rq->min_vruntime;
4348#endif
4349
4350 se->vruntime -= min_vruntime;
4351 record_wakee(p);
4352}
4353
4354#ifdef CONFIG_FAIR_GROUP_SCHED
4355
4356
4357
4358
4359
4360
4361
4362
4363
4364
4365
4366
4367
4368
4369
4370
4371
4372
4373
4374
4375
4376
4377
4378
4379
4380
4381
4382
4383
4384
4385
4386
4387
4388
4389
4390
4391
4392
4393
4394
4395
4396
4397
4398
4399
4400
4401
4402
4403
4404
4405static long effective_load(struct task_group *tg, int cpu, long wl, long wg)
4406{
4407 struct sched_entity *se = tg->se[cpu];
4408
4409 if (!tg->parent)
4410 return wl;
4411
4412 for_each_sched_entity(se) {
4413 long w, W;
4414
4415 tg = se->my_q->tg;
4416
4417
4418
4419
4420 W = wg + calc_tg_weight(tg, se->my_q);
4421
4422
4423
4424
4425 w = se->my_q->load.weight + wl;
4426
4427
4428
4429
4430 if (W > 0 && w < W)
4431 wl = (w * (long)tg->shares) / W;
4432 else
4433 wl = tg->shares;
4434
4435
4436
4437
4438
4439
4440 if (wl < MIN_SHARES)
4441 wl = MIN_SHARES;
4442
4443
4444
4445
4446 wl -= se->load.weight;
4447
4448
4449
4450
4451
4452
4453
4454
4455 wg = 0;
4456 }
4457
4458 return wl;
4459}
4460#else
4461
4462static long effective_load(struct task_group *tg, int cpu, long wl, long wg)
4463{
4464 return wl;
4465}
4466
4467#endif
4468
4469static int wake_wide(struct task_struct *p)
4470{
4471 int factor = this_cpu_read(sd_llc_size);
4472
4473
4474
4475
4476
4477
4478 if (p->wakee_flips > factor) {
4479
4480
4481
4482
4483
4484 if (current->wakee_flips > (factor * p->wakee_flips))
4485 return 1;
4486 }
4487
4488 return 0;
4489}
4490
4491static int wake_affine(struct sched_domain *sd, struct task_struct *p, int sync)
4492{
4493 s64 this_load, load;
4494 s64 this_eff_load, prev_eff_load;
4495 int idx, this_cpu, prev_cpu;
4496 struct task_group *tg;
4497 unsigned long weight;
4498 int balanced;
4499
4500
4501
4502
4503
4504 if (wake_wide(p))
4505 return 0;
4506
4507 idx = sd->wake_idx;
4508 this_cpu = smp_processor_id();
4509 prev_cpu = task_cpu(p);
4510 load = source_load(prev_cpu, idx);
4511 this_load = target_load(this_cpu, idx);
4512
4513
4514
4515
4516
4517
4518 if (sync) {
4519 tg = task_group(current);
4520 weight = current->se.load.weight;
4521
4522 this_load += effective_load(tg, this_cpu, -weight, -weight);
4523 load += effective_load(tg, prev_cpu, 0, -weight);
4524 }
4525
4526 tg = task_group(p);
4527 weight = p->se.load.weight;
4528
4529
4530
4531
4532
4533
4534
4535
4536
4537
4538 this_eff_load = 100;
4539 this_eff_load *= capacity_of(prev_cpu);
4540
4541 prev_eff_load = 100 + (sd->imbalance_pct - 100) / 2;
4542 prev_eff_load *= capacity_of(this_cpu);
4543
4544 if (this_load > 0) {
4545 this_eff_load *= this_load +
4546 effective_load(tg, this_cpu, weight, weight);
4547
4548 prev_eff_load *= load + effective_load(tg, prev_cpu, 0, weight);
4549 }
4550
4551 balanced = this_eff_load <= prev_eff_load;
4552
4553 schedstat_inc(p, se.statistics.nr_wakeups_affine_attempts);
4554
4555 if (!balanced)
4556 return 0;
4557
4558 schedstat_inc(sd, ttwu_move_affine);
4559 schedstat_inc(p, se.statistics.nr_wakeups_affine);
4560
4561 return 1;
4562}
4563
4564
4565
4566
4567
4568static struct sched_group *
4569find_idlest_group(struct sched_domain *sd, struct task_struct *p,
4570 int this_cpu, int sd_flag)
4571{
4572 struct sched_group *idlest = NULL, *group = sd->groups;
4573 unsigned long min_load = ULONG_MAX, this_load = 0;
4574 int load_idx = sd->forkexec_idx;
4575 int imbalance = 100 + (sd->imbalance_pct-100)/2;
4576
4577 if (sd_flag & SD_BALANCE_WAKE)
4578 load_idx = sd->wake_idx;
4579
4580 do {
4581 unsigned long load, avg_load;
4582 int local_group;
4583 int i;
4584
4585
4586 if (!cpumask_intersects(sched_group_cpus(group),
4587 tsk_cpus_allowed(p)))
4588 continue;
4589
4590 local_group = cpumask_test_cpu(this_cpu,
4591 sched_group_cpus(group));
4592
4593
4594 avg_load = 0;
4595
4596 for_each_cpu(i, sched_group_cpus(group)) {
4597
4598 if (local_group)
4599 load = source_load(i, load_idx);
4600 else
4601 load = target_load(i, load_idx);
4602
4603 avg_load += load;
4604 }
4605
4606
4607 avg_load = (avg_load * SCHED_CAPACITY_SCALE) / group->sgc->capacity;
4608
4609 if (local_group) {
4610 this_load = avg_load;
4611 } else if (avg_load < min_load) {
4612 min_load = avg_load;
4613 idlest = group;
4614 }
4615 } while (group = group->next, group != sd->groups);
4616
4617 if (!idlest || 100*this_load < imbalance*min_load)
4618 return NULL;
4619 return idlest;
4620}
4621
4622
4623
4624
4625static int
4626find_idlest_cpu(struct sched_group *group, struct task_struct *p, int this_cpu)
4627{
4628 unsigned long load, min_load = ULONG_MAX;
4629 unsigned int min_exit_latency = UINT_MAX;
4630 u64 latest_idle_timestamp = 0;
4631 int least_loaded_cpu = this_cpu;
4632 int shallowest_idle_cpu = -1;
4633 int i;
4634
4635
4636 for_each_cpu_and(i, sched_group_cpus(group), tsk_cpus_allowed(p)) {
4637 if (idle_cpu(i)) {
4638 struct rq *rq = cpu_rq(i);
4639 struct cpuidle_state *idle = idle_get_state(rq);
4640 if (idle && idle->exit_latency < min_exit_latency) {
4641
4642
4643
4644
4645
4646 min_exit_latency = idle->exit_latency;
4647 latest_idle_timestamp = rq->idle_stamp;
4648 shallowest_idle_cpu = i;
4649 } else if ((!idle || idle->exit_latency == min_exit_latency) &&
4650 rq->idle_stamp > latest_idle_timestamp) {
4651
4652
4653
4654
4655
4656 latest_idle_timestamp = rq->idle_stamp;
4657 shallowest_idle_cpu = i;
4658 }
4659 } else if (shallowest_idle_cpu == -1) {
4660 load = weighted_cpuload(i);
4661 if (load < min_load || (load == min_load && i == this_cpu)) {
4662 min_load = load;
4663 least_loaded_cpu = i;
4664 }
4665 }
4666 }
4667
4668 return shallowest_idle_cpu != -1 ? shallowest_idle_cpu : least_loaded_cpu;
4669}
4670
4671
4672
4673
4674static int select_idle_sibling(struct task_struct *p, int target)
4675{
4676 struct sched_domain *sd;
4677 struct sched_group *sg;
4678 int i = task_cpu(p);
4679
4680 if (idle_cpu(target))
4681 return target;
4682
4683
4684
4685
4686 if (i != target && cpus_share_cache(i, target) && idle_cpu(i))
4687 return i;
4688
4689
4690
4691
4692 sd = rcu_dereference(per_cpu(sd_llc, target));
4693 for_each_lower_domain(sd) {
4694 sg = sd->groups;
4695 do {
4696 if (!cpumask_intersects(sched_group_cpus(sg),
4697 tsk_cpus_allowed(p)))
4698 goto next;
4699
4700 for_each_cpu(i, sched_group_cpus(sg)) {
4701 if (i == target || !idle_cpu(i))
4702 goto next;
4703 }
4704
4705 target = cpumask_first_and(sched_group_cpus(sg),
4706 tsk_cpus_allowed(p));
4707 goto done;
4708next:
4709 sg = sg->next;
4710 } while (sg != sd->groups);
4711 }
4712done:
4713 return target;
4714}
4715
4716
4717
4718
4719
4720
4721
4722
4723
4724
4725
4726
4727
4728static int
4729select_task_rq_fair(struct task_struct *p, int prev_cpu, int sd_flag, int wake_flags)
4730{
4731 struct sched_domain *tmp, *affine_sd = NULL, *sd = NULL;
4732 int cpu = smp_processor_id();
4733 int new_cpu = cpu;
4734 int want_affine = 0;
4735 int sync = wake_flags & WF_SYNC;
4736
4737 if (sd_flag & SD_BALANCE_WAKE)
4738 want_affine = cpumask_test_cpu(cpu, tsk_cpus_allowed(p));
4739
4740 rcu_read_lock();
4741 for_each_domain(cpu, tmp) {
4742 if (!(tmp->flags & SD_LOAD_BALANCE))
4743 continue;
4744
4745
4746
4747
4748
4749 if (want_affine && (tmp->flags & SD_WAKE_AFFINE) &&
4750 cpumask_test_cpu(prev_cpu, sched_domain_span(tmp))) {
4751 affine_sd = tmp;
4752 break;
4753 }
4754
4755 if (tmp->flags & sd_flag)
4756 sd = tmp;
4757 }
4758
4759 if (affine_sd && cpu != prev_cpu && wake_affine(affine_sd, p, sync))
4760 prev_cpu = cpu;
4761
4762 if (sd_flag & SD_BALANCE_WAKE) {
4763 new_cpu = select_idle_sibling(p, prev_cpu);
4764 goto unlock;
4765 }
4766
4767 while (sd) {
4768 struct sched_group *group;
4769 int weight;
4770
4771 if (!(sd->flags & sd_flag)) {
4772 sd = sd->child;
4773 continue;
4774 }
4775
4776 group = find_idlest_group(sd, p, cpu, sd_flag);
4777 if (!group) {
4778 sd = sd->child;
4779 continue;
4780 }
4781
4782 new_cpu = find_idlest_cpu(group, p, cpu);
4783 if (new_cpu == -1 || new_cpu == cpu) {
4784
4785 sd = sd->child;
4786 continue;
4787 }
4788
4789
4790 cpu = new_cpu;
4791 weight = sd->span_weight;
4792 sd = NULL;
4793 for_each_domain(cpu, tmp) {
4794 if (weight <= tmp->span_weight)
4795 break;
4796 if (tmp->flags & sd_flag)
4797 sd = tmp;
4798 }
4799
4800 }
4801unlock:
4802 rcu_read_unlock();
4803
4804 return new_cpu;
4805}
4806
4807
4808
4809
4810
4811
4812
4813static void
4814migrate_task_rq_fair(struct task_struct *p, int next_cpu)
4815{
4816 struct sched_entity *se = &p->se;
4817 struct cfs_rq *cfs_rq = cfs_rq_of(se);
4818
4819
4820
4821
4822
4823
4824
4825 if (se->avg.decay_count) {
4826 se->avg.decay_count = -__synchronize_entity_decay(se);
4827 atomic_long_add(se->avg.load_avg_contrib,
4828 &cfs_rq->removed_load);
4829 }
4830
4831
4832 se->exec_start = 0;
4833}
4834#endif
4835
4836static unsigned long
4837wakeup_gran(struct sched_entity *curr, struct sched_entity *se)
4838{
4839 unsigned long gran = sysctl_sched_wakeup_granularity;
4840
4841
4842
4843
4844
4845
4846
4847
4848
4849
4850
4851
4852
4853
4854 return calc_delta_fair(gran, se);
4855}
4856
4857
4858
4859
4860
4861
4862
4863
4864
4865
4866
4867
4868
4869
4870
4871static int
4872wakeup_preempt_entity(struct sched_entity *curr, struct sched_entity *se)
4873{
4874 s64 gran, vdiff = curr->vruntime - se->vruntime;
4875
4876 if (vdiff <= 0)
4877 return -1;
4878
4879 gran = wakeup_gran(curr, se);
4880 if (vdiff > gran)
4881 return 1;
4882
4883 return 0;
4884}
4885
4886static void set_last_buddy(struct sched_entity *se)
4887{
4888 if (entity_is_task(se) && unlikely(task_of(se)->policy == SCHED_IDLE))
4889 return;
4890
4891 for_each_sched_entity(se)
4892 cfs_rq_of(se)->last = se;
4893}
4894
4895static void set_next_buddy(struct sched_entity *se)
4896{
4897 if (entity_is_task(se) && unlikely(task_of(se)->policy == SCHED_IDLE))
4898 return;
4899
4900 for_each_sched_entity(se)
4901 cfs_rq_of(se)->next = se;
4902}
4903
4904static void set_skip_buddy(struct sched_entity *se)
4905{
4906 for_each_sched_entity(se)
4907 cfs_rq_of(se)->skip = se;
4908}
4909
4910
4911
4912
4913static void check_preempt_wakeup(struct rq *rq, struct task_struct *p, int wake_flags)
4914{
4915 struct task_struct *curr = rq->curr;
4916 struct sched_entity *se = &curr->se, *pse = &p->se;
4917 struct cfs_rq *cfs_rq = task_cfs_rq(curr);
4918 int scale = cfs_rq->nr_running >= sched_nr_latency;
4919 int next_buddy_marked = 0;
4920
4921 if (unlikely(se == pse))
4922 return;
4923
4924
4925
4926
4927
4928
4929
4930 if (unlikely(throttled_hierarchy(cfs_rq_of(pse))))
4931 return;
4932
4933 if (sched_feat(NEXT_BUDDY) && scale && !(wake_flags & WF_FORK)) {
4934 set_next_buddy(pse);
4935 next_buddy_marked = 1;
4936 }
4937
4938
4939
4940
4941
4942
4943
4944
4945
4946
4947
4948 if (test_tsk_need_resched(curr))
4949 return;
4950
4951
4952 if (unlikely(curr->policy == SCHED_IDLE) &&
4953 likely(p->policy != SCHED_IDLE))
4954 goto preempt;
4955
4956
4957
4958
4959
4960 if (unlikely(p->policy != SCHED_NORMAL) || !sched_feat(WAKEUP_PREEMPTION))
4961 return;
4962
4963 find_matching_se(&se, &pse);
4964 update_curr(cfs_rq_of(se));
4965 BUG_ON(!pse);
4966 if (wakeup_preempt_entity(se, pse) == 1) {
4967
4968
4969
4970
4971 if (!next_buddy_marked)
4972 set_next_buddy(pse);
4973 goto preempt;
4974 }
4975
4976 return;
4977
4978preempt:
4979 resched_curr(rq);
4980
4981
4982
4983
4984
4985
4986
4987
4988
4989 if (unlikely(!se->on_rq || curr == rq->idle))
4990 return;
4991
4992 if (sched_feat(LAST_BUDDY) && scale && entity_is_task(se))
4993 set_last_buddy(se);
4994}
4995
4996static struct task_struct *
4997pick_next_task_fair(struct rq *rq, struct task_struct *prev)
4998{
4999 struct cfs_rq *cfs_rq = &rq->cfs;
5000 struct sched_entity *se;
5001 struct task_struct *p;
5002 int new_tasks;
5003
5004again:
5005#ifdef CONFIG_FAIR_GROUP_SCHED
5006 if (!cfs_rq->nr_running)
5007 goto idle;
5008
5009 if (prev->sched_class != &fair_sched_class)
5010 goto simple;
5011
5012
5013
5014
5015
5016
5017
5018
5019
5020 do {
5021 struct sched_entity *curr = cfs_rq->curr;
5022
5023
5024
5025
5026
5027
5028
5029 if (curr && curr->on_rq)
5030 update_curr(cfs_rq);
5031 else
5032 curr = NULL;
5033
5034
5035
5036
5037
5038
5039 if (unlikely(check_cfs_rq_runtime(cfs_rq)))
5040 goto simple;
5041
5042 se = pick_next_entity(cfs_rq, curr);
5043 cfs_rq = group_cfs_rq(se);
5044 } while (cfs_rq);
5045
5046 p = task_of(se);
5047
5048
5049
5050
5051
5052
5053 if (prev != p) {
5054 struct sched_entity *pse = &prev->se;
5055
5056 while (!(cfs_rq = is_same_group(se, pse))) {
5057 int se_depth = se->depth;
5058 int pse_depth = pse->depth;
5059
5060 if (se_depth <= pse_depth) {
5061 put_prev_entity(cfs_rq_of(pse), pse);
5062 pse = parent_entity(pse);
5063 }
5064 if (se_depth >= pse_depth) {
5065 set_next_entity(cfs_rq_of(se), se);
5066 se = parent_entity(se);
5067 }
5068 }
5069
5070 put_prev_entity(cfs_rq, pse);
5071 set_next_entity(cfs_rq, se);
5072 }
5073
5074 if (hrtick_enabled(rq))
5075 hrtick_start_fair(rq, p);
5076
5077 return p;
5078simple:
5079 cfs_rq = &rq->cfs;
5080#endif
5081
5082 if (!cfs_rq->nr_running)
5083 goto idle;
5084
5085 put_prev_task(rq, prev);
5086
5087 do {
5088 se = pick_next_entity(cfs_rq, NULL);
5089 set_next_entity(cfs_rq, se);
5090 cfs_rq = group_cfs_rq(se);
5091 } while (cfs_rq);
5092
5093 p = task_of(se);
5094
5095 if (hrtick_enabled(rq))
5096 hrtick_start_fair(rq, p);
5097
5098 return p;
5099
5100idle:
5101 new_tasks = idle_balance(rq);
5102
5103
5104
5105
5106
5107 if (new_tasks < 0)
5108 return RETRY_TASK;
5109
5110 if (new_tasks > 0)
5111 goto again;
5112
5113 return NULL;
5114}
5115
5116
5117
5118
5119static void put_prev_task_fair(struct rq *rq, struct task_struct *prev)
5120{
5121 struct sched_entity *se = &prev->se;
5122 struct cfs_rq *cfs_rq;
5123
5124 for_each_sched_entity(se) {
5125 cfs_rq = cfs_rq_of(se);
5126 put_prev_entity(cfs_rq, se);
5127 }
5128}
5129
5130
5131
5132
5133
5134
5135static void yield_task_fair(struct rq *rq)
5136{
5137 struct task_struct *curr = rq->curr;
5138 struct cfs_rq *cfs_rq = task_cfs_rq(curr);
5139 struct sched_entity *se = &curr->se;
5140
5141
5142
5143
5144 if (unlikely(rq->nr_running == 1))
5145 return;
5146
5147 clear_buddies(cfs_rq, se);
5148
5149 if (curr->policy != SCHED_BATCH) {
5150 update_rq_clock(rq);
5151
5152
5153
5154 update_curr(cfs_rq);
5155
5156
5157
5158
5159
5160 rq->skip_clock_update = 1;
5161 }
5162
5163 set_skip_buddy(se);
5164}
5165
5166static bool yield_to_task_fair(struct rq *rq, struct task_struct *p, bool preempt)
5167{
5168 struct sched_entity *se = &p->se;
5169
5170
5171 if (!se->on_rq || throttled_hierarchy(cfs_rq_of(se)))
5172 return false;
5173
5174
5175 set_next_buddy(se);
5176
5177 yield_task_fair(rq);
5178
5179 return true;
5180}
5181
5182#ifdef CONFIG_SMP
5183
5184
5185
5186
5187
5188
5189
5190
5191
5192
5193
5194
5195
5196
5197
5198
5199
5200
5201
5202
5203
5204
5205
5206
5207
5208
5209
5210
5211
5212
5213
5214
5215
5216
5217
5218
5219
5220
5221
5222
5223
5224
5225
5226
5227
5228
5229
5230
5231
5232
5233
5234
5235
5236
5237
5238
5239
5240
5241
5242
5243
5244
5245
5246
5247
5248
5249
5250
5251
5252
5253
5254
5255
5256
5257
5258
5259
5260
5261
5262
5263
5264
5265
5266
5267
5268
5269
5270
5271
5272
5273
5274
5275
5276
5277
5278
5279
5280
5281
5282
5283
5284
5285
5286
5287
5288
5289
5290
5291
5292
5293
5294
5295
5296
5297
5298
5299
5300
5301static unsigned long __read_mostly max_load_balance_interval = HZ/10;
5302
5303enum fbq_type { regular, remote, all };
5304
5305#define LBF_ALL_PINNED 0x01
5306#define LBF_NEED_BREAK 0x02
5307#define LBF_DST_PINNED 0x04
5308#define LBF_SOME_PINNED 0x08
5309
5310struct lb_env {
5311 struct sched_domain *sd;
5312
5313 struct rq *src_rq;
5314 int src_cpu;
5315
5316 int dst_cpu;
5317 struct rq *dst_rq;
5318
5319 struct cpumask *dst_grpmask;
5320 int new_dst_cpu;
5321 enum cpu_idle_type idle;
5322 long imbalance;
5323
5324 struct cpumask *cpus;
5325
5326 unsigned int flags;
5327
5328 unsigned int loop;
5329 unsigned int loop_break;
5330 unsigned int loop_max;
5331
5332 enum fbq_type fbq_type;
5333 struct list_head tasks;
5334};
5335
5336
5337
5338
5339static int task_hot(struct task_struct *p, struct lb_env *env)
5340{
5341 s64 delta;
5342
5343 lockdep_assert_held(&env->src_rq->lock);
5344
5345 if (p->sched_class != &fair_sched_class)
5346 return 0;
5347
5348 if (unlikely(p->policy == SCHED_IDLE))
5349 return 0;
5350
5351
5352
5353
5354 if (sched_feat(CACHE_HOT_BUDDY) && env->dst_rq->nr_running &&
5355 (&p->se == cfs_rq_of(&p->se)->next ||
5356 &p->se == cfs_rq_of(&p->se)->last))
5357 return 1;
5358
5359 if (sysctl_sched_migration_cost == -1)
5360 return 1;
5361 if (sysctl_sched_migration_cost == 0)
5362 return 0;
5363
5364 delta = rq_clock_task(env->src_rq) - p->se.exec_start;
5365
5366 return delta < (s64)sysctl_sched_migration_cost;
5367}
5368
5369#ifdef CONFIG_NUMA_BALANCING
5370
5371static bool migrate_improves_locality(struct task_struct *p, struct lb_env *env)
5372{
5373 struct numa_group *numa_group = rcu_dereference(p->numa_group);
5374 int src_nid, dst_nid;
5375
5376 if (!sched_feat(NUMA_FAVOUR_HIGHER) || !p->numa_faults ||
5377 !(env->sd->flags & SD_NUMA)) {
5378 return false;
5379 }
5380
5381 src_nid = cpu_to_node(env->src_cpu);
5382 dst_nid = cpu_to_node(env->dst_cpu);
5383
5384 if (src_nid == dst_nid)
5385 return false;
5386
5387 if (numa_group) {
5388
5389 if (node_isset(src_nid, numa_group->active_nodes))
5390 return false;
5391
5392
5393 if (node_isset(dst_nid, numa_group->active_nodes))
5394 return true;
5395
5396 return group_faults(p, dst_nid) > group_faults(p, src_nid);
5397 }
5398
5399
5400 if (dst_nid == p->numa_preferred_nid)
5401 return true;
5402
5403 return task_faults(p, dst_nid) > task_faults(p, src_nid);
5404}
5405
5406
5407static bool migrate_degrades_locality(struct task_struct *p, struct lb_env *env)
5408{
5409 struct numa_group *numa_group = rcu_dereference(p->numa_group);
5410 int src_nid, dst_nid;
5411
5412 if (!sched_feat(NUMA) || !sched_feat(NUMA_RESIST_LOWER))
5413 return false;
5414
5415 if (!p->numa_faults || !(env->sd->flags & SD_NUMA))
5416 return false;
5417
5418 src_nid = cpu_to_node(env->src_cpu);
5419 dst_nid = cpu_to_node(env->dst_cpu);
5420
5421 if (src_nid == dst_nid)
5422 return false;
5423
5424 if (numa_group) {
5425
5426 if (node_isset(dst_nid, numa_group->active_nodes))
5427 return false;
5428
5429
5430 if (node_isset(src_nid, numa_group->active_nodes))
5431 return true;
5432
5433 return group_faults(p, dst_nid) < group_faults(p, src_nid);
5434 }
5435
5436
5437 if (src_nid == p->numa_preferred_nid)
5438 return true;
5439
5440 return task_faults(p, dst_nid) < task_faults(p, src_nid);
5441}
5442
5443#else
5444static inline bool migrate_improves_locality(struct task_struct *p,
5445 struct lb_env *env)
5446{
5447 return false;
5448}
5449
5450static inline bool migrate_degrades_locality(struct task_struct *p,
5451 struct lb_env *env)
5452{
5453 return false;
5454}
5455#endif
5456
5457
5458
5459
5460static
5461int can_migrate_task(struct task_struct *p, struct lb_env *env)
5462{
5463 int tsk_cache_hot = 0;
5464
5465 lockdep_assert_held(&env->src_rq->lock);
5466
5467
5468
5469
5470
5471
5472
5473
5474 if (throttled_lb_pair(task_group(p), env->src_cpu, env->dst_cpu))
5475 return 0;
5476
5477 if (!cpumask_test_cpu(env->dst_cpu, tsk_cpus_allowed(p))) {
5478 int cpu;
5479
5480 schedstat_inc(p, se.statistics.nr_failed_migrations_affine);
5481
5482 env->flags |= LBF_SOME_PINNED;
5483
5484
5485
5486
5487
5488
5489
5490
5491
5492 if (!env->dst_grpmask || (env->flags & LBF_DST_PINNED))
5493 return 0;
5494
5495
5496 for_each_cpu_and(cpu, env->dst_grpmask, env->cpus) {
5497 if (cpumask_test_cpu(cpu, tsk_cpus_allowed(p))) {
5498 env->flags |= LBF_DST_PINNED;
5499 env->new_dst_cpu = cpu;
5500 break;
5501 }
5502 }
5503
5504 return 0;
5505 }
5506
5507
5508 env->flags &= ~LBF_ALL_PINNED;
5509
5510 if (task_running(env->src_rq, p)) {
5511 schedstat_inc(p, se.statistics.nr_failed_migrations_running);
5512 return 0;
5513 }
5514
5515
5516
5517
5518
5519
5520
5521 tsk_cache_hot = task_hot(p, env);
5522 if (!tsk_cache_hot)
5523 tsk_cache_hot = migrate_degrades_locality(p, env);
5524
5525 if (migrate_improves_locality(p, env) || !tsk_cache_hot ||
5526 env->sd->nr_balance_failed > env->sd->cache_nice_tries) {
5527 if (tsk_cache_hot) {
5528 schedstat_inc(env->sd, lb_hot_gained[env->idle]);
5529 schedstat_inc(p, se.statistics.nr_forced_migrations);
5530 }
5531 return 1;
5532 }
5533
5534 schedstat_inc(p, se.statistics.nr_failed_migrations_hot);
5535 return 0;
5536}
5537
5538
5539
5540
5541static void detach_task(struct task_struct *p, struct lb_env *env)
5542{
5543 lockdep_assert_held(&env->src_rq->lock);
5544
5545 deactivate_task(env->src_rq, p, 0);
5546 p->on_rq = TASK_ON_RQ_MIGRATING;
5547 set_task_cpu(p, env->dst_cpu);
5548}
5549
5550
5551
5552
5553
5554
5555
5556static struct task_struct *detach_one_task(struct lb_env *env)
5557{
5558 struct task_struct *p, *n;
5559
5560 lockdep_assert_held(&env->src_rq->lock);
5561
5562 list_for_each_entry_safe(p, n, &env->src_rq->cfs_tasks, se.group_node) {
5563 if (!can_migrate_task(p, env))
5564 continue;
5565
5566 detach_task(p, env);
5567
5568
5569
5570
5571
5572
5573
5574 schedstat_inc(env->sd, lb_gained[env->idle]);
5575 return p;
5576 }
5577 return NULL;
5578}
5579
5580static const unsigned int sched_nr_migrate_break = 32;
5581
5582
5583
5584
5585
5586
5587
5588static int detach_tasks(struct lb_env *env)
5589{
5590 struct list_head *tasks = &env->src_rq->cfs_tasks;
5591 struct task_struct *p;
5592 unsigned long load;
5593 int detached = 0;
5594
5595 lockdep_assert_held(&env->src_rq->lock);
5596
5597 if (env->imbalance <= 0)
5598 return 0;
5599
5600 while (!list_empty(tasks)) {
5601 p = list_first_entry(tasks, struct task_struct, se.group_node);
5602
5603 env->loop++;
5604
5605 if (env->loop > env->loop_max)
5606 break;
5607
5608
5609 if (env->loop > env->loop_break) {
5610 env->loop_break += sched_nr_migrate_break;
5611 env->flags |= LBF_NEED_BREAK;
5612 break;
5613 }
5614
5615 if (!can_migrate_task(p, env))
5616 goto next;
5617
5618 load = task_h_load(p);
5619
5620 if (sched_feat(LB_MIN) && load < 16 && !env->sd->nr_balance_failed)
5621 goto next;
5622
5623 if ((load / 2) > env->imbalance)
5624 goto next;
5625
5626 detach_task(p, env);
5627 list_add(&p->se.group_node, &env->tasks);
5628
5629 detached++;
5630 env->imbalance -= load;
5631
5632#ifdef CONFIG_PREEMPT
5633
5634
5635
5636
5637
5638 if (env->idle == CPU_NEWLY_IDLE)
5639 break;
5640#endif
5641
5642
5643
5644
5645
5646 if (env->imbalance <= 0)
5647 break;
5648
5649 continue;
5650next:
5651 list_move_tail(&p->se.group_node, tasks);
5652 }
5653
5654
5655
5656
5657
5658
5659 schedstat_add(env->sd, lb_gained[env->idle], detached);
5660
5661 return detached;
5662}
5663
5664
5665
5666
5667static void attach_task(struct rq *rq, struct task_struct *p)
5668{
5669 lockdep_assert_held(&rq->lock);
5670
5671 BUG_ON(task_rq(p) != rq);
5672 p->on_rq = TASK_ON_RQ_QUEUED;
5673 activate_task(rq, p, 0);
5674 check_preempt_curr(rq, p, 0);
5675}
5676
5677
5678
5679
5680
5681static void attach_one_task(struct rq *rq, struct task_struct *p)
5682{
5683 raw_spin_lock(&rq->lock);
5684 attach_task(rq, p);
5685 raw_spin_unlock(&rq->lock);
5686}
5687
5688
5689
5690
5691
5692static void attach_tasks(struct lb_env *env)
5693{
5694 struct list_head *tasks = &env->tasks;
5695 struct task_struct *p;
5696
5697 raw_spin_lock(&env->dst_rq->lock);
5698
5699 while (!list_empty(tasks)) {
5700 p = list_first_entry(tasks, struct task_struct, se.group_node);
5701 list_del_init(&p->se.group_node);
5702
5703 attach_task(env->dst_rq, p);
5704 }
5705
5706 raw_spin_unlock(&env->dst_rq->lock);
5707}
5708
5709#ifdef CONFIG_FAIR_GROUP_SCHED
5710
5711
5712
5713static void __update_blocked_averages_cpu(struct task_group *tg, int cpu)
5714{
5715 struct sched_entity *se = tg->se[cpu];
5716 struct cfs_rq *cfs_rq = tg->cfs_rq[cpu];
5717
5718
5719 if (throttled_hierarchy(cfs_rq))
5720 return;
5721
5722 update_cfs_rq_blocked_load(cfs_rq, 1);
5723
5724 if (se) {
5725 update_entity_load_avg(se, 1);
5726
5727
5728
5729
5730
5731
5732
5733
5734
5735 if (!se->avg.runnable_avg_sum && !cfs_rq->nr_running)
5736 list_del_leaf_cfs_rq(cfs_rq);
5737 } else {
5738 struct rq *rq = rq_of(cfs_rq);
5739 update_rq_runnable_avg(rq, rq->nr_running);
5740 }
5741}
5742
5743static void update_blocked_averages(int cpu)
5744{
5745 struct rq *rq = cpu_rq(cpu);
5746 struct cfs_rq *cfs_rq;
5747 unsigned long flags;
5748
5749 raw_spin_lock_irqsave(&rq->lock, flags);
5750 update_rq_clock(rq);
5751
5752
5753
5754
5755 for_each_leaf_cfs_rq(rq, cfs_rq) {
5756
5757
5758
5759
5760
5761 __update_blocked_averages_cpu(cfs_rq->tg, rq->cpu);
5762 }
5763
5764 raw_spin_unlock_irqrestore(&rq->lock, flags);
5765}
5766
5767
5768
5769
5770
5771
5772static void update_cfs_rq_h_load(struct cfs_rq *cfs_rq)
5773{
5774 struct rq *rq = rq_of(cfs_rq);
5775 struct sched_entity *se = cfs_rq->tg->se[cpu_of(rq)];
5776 unsigned long now = jiffies;
5777 unsigned long load;
5778
5779 if (cfs_rq->last_h_load_update == now)
5780 return;
5781
5782 cfs_rq->h_load_next = NULL;
5783 for_each_sched_entity(se) {
5784 cfs_rq = cfs_rq_of(se);
5785 cfs_rq->h_load_next = se;
5786 if (cfs_rq->last_h_load_update == now)
5787 break;
5788 }
5789
5790 if (!se) {
5791 cfs_rq->h_load = cfs_rq->runnable_load_avg;
5792 cfs_rq->last_h_load_update = now;
5793 }
5794
5795 while ((se = cfs_rq->h_load_next) != NULL) {
5796 load = cfs_rq->h_load;
5797 load = div64_ul(load * se->avg.load_avg_contrib,
5798 cfs_rq->runnable_load_avg + 1);
5799 cfs_rq = group_cfs_rq(se);
5800 cfs_rq->h_load = load;
5801 cfs_rq->last_h_load_update = now;
5802 }
5803}
5804
5805static unsigned long task_h_load(struct task_struct *p)
5806{
5807 struct cfs_rq *cfs_rq = task_cfs_rq(p);
5808
5809 update_cfs_rq_h_load(cfs_rq);
5810 return div64_ul(p->se.avg.load_avg_contrib * cfs_rq->h_load,
5811 cfs_rq->runnable_load_avg + 1);
5812}
5813#else
5814static inline void update_blocked_averages(int cpu)
5815{
5816}
5817
5818static unsigned long task_h_load(struct task_struct *p)
5819{
5820 return p->se.avg.load_avg_contrib;
5821}
5822#endif
5823
5824
5825
5826enum group_type {
5827 group_other = 0,
5828 group_imbalanced,
5829 group_overloaded,
5830};
5831
5832
5833
5834
5835struct sg_lb_stats {
5836 unsigned long avg_load;
5837 unsigned long group_load;
5838 unsigned long sum_weighted_load;
5839 unsigned long load_per_task;
5840 unsigned long group_capacity;
5841 unsigned int sum_nr_running;
5842 unsigned int group_capacity_factor;
5843 unsigned int idle_cpus;
5844 unsigned int group_weight;
5845 enum group_type group_type;
5846 int group_has_free_capacity;
5847#ifdef CONFIG_NUMA_BALANCING
5848 unsigned int nr_numa_running;
5849 unsigned int nr_preferred_running;
5850#endif
5851};
5852
5853
5854
5855
5856
5857struct sd_lb_stats {
5858 struct sched_group *busiest;
5859 struct sched_group *local;
5860 unsigned long total_load;
5861 unsigned long total_capacity;
5862 unsigned long avg_load;
5863
5864 struct sg_lb_stats busiest_stat;
5865 struct sg_lb_stats local_stat;
5866};
5867
5868static inline void init_sd_lb_stats(struct sd_lb_stats *sds)
5869{
5870
5871
5872
5873
5874
5875
5876 *sds = (struct sd_lb_stats){
5877 .busiest = NULL,
5878 .local = NULL,
5879 .total_load = 0UL,
5880 .total_capacity = 0UL,
5881 .busiest_stat = {
5882 .avg_load = 0UL,
5883 .sum_nr_running = 0,
5884 .group_type = group_other,
5885 },
5886 };
5887}
5888
5889
5890
5891
5892
5893
5894
5895
5896static inline int get_sd_load_idx(struct sched_domain *sd,
5897 enum cpu_idle_type idle)
5898{
5899 int load_idx;
5900
5901 switch (idle) {
5902 case CPU_NOT_IDLE:
5903 load_idx = sd->busy_idx;
5904 break;
5905
5906 case CPU_NEWLY_IDLE:
5907 load_idx = sd->newidle_idx;
5908 break;
5909 default:
5910 load_idx = sd->idle_idx;
5911 break;
5912 }
5913
5914 return load_idx;
5915}
5916
5917static unsigned long default_scale_capacity(struct sched_domain *sd, int cpu)
5918{
5919 return SCHED_CAPACITY_SCALE;
5920}
5921
5922unsigned long __weak arch_scale_freq_capacity(struct sched_domain *sd, int cpu)
5923{
5924 return default_scale_capacity(sd, cpu);
5925}
5926
5927static unsigned long default_scale_cpu_capacity(struct sched_domain *sd, int cpu)
5928{
5929 if ((sd->flags & SD_SHARE_CPUCAPACITY) && (sd->span_weight > 1))
5930 return sd->smt_gain / sd->span_weight;
5931
5932 return SCHED_CAPACITY_SCALE;
5933}
5934
5935unsigned long __weak arch_scale_cpu_capacity(struct sched_domain *sd, int cpu)
5936{
5937 return default_scale_cpu_capacity(sd, cpu);
5938}
5939
5940static unsigned long scale_rt_capacity(int cpu)
5941{
5942 struct rq *rq = cpu_rq(cpu);
5943 u64 total, available, age_stamp, avg;
5944 s64 delta;
5945
5946
5947
5948
5949
5950 age_stamp = ACCESS_ONCE(rq->age_stamp);
5951 avg = ACCESS_ONCE(rq->rt_avg);
5952
5953 delta = rq_clock(rq) - age_stamp;
5954 if (unlikely(delta < 0))
5955 delta = 0;
5956
5957 total = sched_avg_period() + delta;
5958
5959 if (unlikely(total < avg)) {
5960
5961 available = 0;
5962 } else {
5963 available = total - avg;
5964 }
5965
5966 if (unlikely((s64)total < SCHED_CAPACITY_SCALE))
5967 total = SCHED_CAPACITY_SCALE;
5968
5969 total >>= SCHED_CAPACITY_SHIFT;
5970
5971 return div_u64(available, total);
5972}
5973
5974static void update_cpu_capacity(struct sched_domain *sd, int cpu)
5975{
5976 unsigned long capacity = SCHED_CAPACITY_SCALE;
5977 struct sched_group *sdg = sd->groups;
5978
5979 if (sched_feat(ARCH_CAPACITY))
5980 capacity *= arch_scale_cpu_capacity(sd, cpu);
5981 else
5982 capacity *= default_scale_cpu_capacity(sd, cpu);
5983
5984 capacity >>= SCHED_CAPACITY_SHIFT;
5985
5986 sdg->sgc->capacity_orig = capacity;
5987
5988 if (sched_feat(ARCH_CAPACITY))
5989 capacity *= arch_scale_freq_capacity(sd, cpu);
5990 else
5991 capacity *= default_scale_capacity(sd, cpu);
5992
5993 capacity >>= SCHED_CAPACITY_SHIFT;
5994
5995 capacity *= scale_rt_capacity(cpu);
5996 capacity >>= SCHED_CAPACITY_SHIFT;
5997
5998 if (!capacity)
5999 capacity = 1;
6000
6001 cpu_rq(cpu)->cpu_capacity = capacity;
6002 sdg->sgc->capacity = capacity;
6003}
6004
6005void update_group_capacity(struct sched_domain *sd, int cpu)
6006{
6007 struct sched_domain *child = sd->child;
6008 struct sched_group *group, *sdg = sd->groups;
6009 unsigned long capacity, capacity_orig;
6010 unsigned long interval;
6011
6012 interval = msecs_to_jiffies(sd->balance_interval);
6013 interval = clamp(interval, 1UL, max_load_balance_interval);
6014 sdg->sgc->next_update = jiffies + interval;
6015
6016 if (!child) {
6017 update_cpu_capacity(sd, cpu);
6018 return;
6019 }
6020
6021 capacity_orig = capacity = 0;
6022
6023 if (child->flags & SD_OVERLAP) {
6024
6025
6026
6027
6028
6029 for_each_cpu(cpu, sched_group_cpus(sdg)) {
6030 struct sched_group_capacity *sgc;
6031 struct rq *rq = cpu_rq(cpu);
6032
6033
6034
6035
6036
6037
6038
6039
6040
6041
6042
6043
6044
6045
6046 if (unlikely(!rq->sd)) {
6047 capacity_orig += capacity_of(cpu);
6048 capacity += capacity_of(cpu);
6049 continue;
6050 }
6051
6052 sgc = rq->sd->groups->sgc;
6053 capacity_orig += sgc->capacity_orig;
6054 capacity += sgc->capacity;
6055 }
6056 } else {
6057
6058
6059
6060
6061
6062 group = child->groups;
6063 do {
6064 capacity_orig += group->sgc->capacity_orig;
6065 capacity += group->sgc->capacity;
6066 group = group->next;
6067 } while (group != child->groups);
6068 }
6069
6070 sdg->sgc->capacity_orig = capacity_orig;
6071 sdg->sgc->capacity = capacity;
6072}
6073
6074
6075
6076
6077
6078
6079
6080
6081static inline int
6082fix_small_capacity(struct sched_domain *sd, struct sched_group *group)
6083{
6084
6085
6086
6087 if (!(sd->flags & SD_SHARE_CPUCAPACITY))
6088 return 0;
6089
6090
6091
6092
6093 if (group->sgc->capacity * 32 > group->sgc->capacity_orig * 29)
6094 return 1;
6095
6096 return 0;
6097}
6098
6099
6100
6101
6102
6103
6104
6105
6106
6107
6108
6109
6110
6111
6112
6113
6114
6115
6116
6117
6118
6119
6120
6121
6122
6123
6124
6125
6126
6127
6128static inline int sg_imbalanced(struct sched_group *group)
6129{
6130 return group->sgc->imbalance;
6131}
6132
6133
6134
6135
6136
6137
6138
6139
6140static inline int sg_capacity_factor(struct lb_env *env, struct sched_group *group)
6141{
6142 unsigned int capacity_factor, smt, cpus;
6143 unsigned int capacity, capacity_orig;
6144
6145 capacity = group->sgc->capacity;
6146 capacity_orig = group->sgc->capacity_orig;
6147 cpus = group->group_weight;
6148
6149
6150 smt = DIV_ROUND_UP(SCHED_CAPACITY_SCALE * cpus, capacity_orig);
6151 capacity_factor = cpus / smt;
6152
6153 capacity_factor = min_t(unsigned,
6154 capacity_factor, DIV_ROUND_CLOSEST(capacity, SCHED_CAPACITY_SCALE));
6155 if (!capacity_factor)
6156 capacity_factor = fix_small_capacity(env->sd, group);
6157
6158 return capacity_factor;
6159}
6160
6161static enum group_type
6162group_classify(struct sched_group *group, struct sg_lb_stats *sgs)
6163{
6164 if (sgs->sum_nr_running > sgs->group_capacity_factor)
6165 return group_overloaded;
6166
6167 if (sg_imbalanced(group))
6168 return group_imbalanced;
6169
6170 return group_other;
6171}
6172
6173
6174
6175
6176
6177
6178
6179
6180
6181
6182static inline void update_sg_lb_stats(struct lb_env *env,
6183 struct sched_group *group, int load_idx,
6184 int local_group, struct sg_lb_stats *sgs,
6185 bool *overload)
6186{
6187 unsigned long load;
6188 int i;
6189
6190 memset(sgs, 0, sizeof(*sgs));
6191
6192 for_each_cpu_and(i, sched_group_cpus(group), env->cpus) {
6193 struct rq *rq = cpu_rq(i);
6194
6195
6196 if (local_group)
6197 load = target_load(i, load_idx);
6198 else
6199 load = source_load(i, load_idx);
6200
6201 sgs->group_load += load;
6202 sgs->sum_nr_running += rq->cfs.h_nr_running;
6203
6204 if (rq->nr_running > 1)
6205 *overload = true;
6206
6207#ifdef CONFIG_NUMA_BALANCING
6208 sgs->nr_numa_running += rq->nr_numa_running;
6209 sgs->nr_preferred_running += rq->nr_preferred_running;
6210#endif
6211 sgs->sum_weighted_load += weighted_cpuload(i);
6212 if (idle_cpu(i))
6213 sgs->idle_cpus++;
6214 }
6215
6216
6217 sgs->group_capacity = group->sgc->capacity;
6218 sgs->avg_load = (sgs->group_load*SCHED_CAPACITY_SCALE) / sgs->group_capacity;
6219
6220 if (sgs->sum_nr_running)
6221 sgs->load_per_task = sgs->sum_weighted_load / sgs->sum_nr_running;
6222
6223 sgs->group_weight = group->group_weight;
6224 sgs->group_capacity_factor = sg_capacity_factor(env, group);
6225 sgs->group_type = group_classify(group, sgs);
6226
6227 if (sgs->group_capacity_factor > sgs->sum_nr_running)
6228 sgs->group_has_free_capacity = 1;
6229}
6230
6231
6232
6233
6234
6235
6236
6237
6238
6239
6240
6241
6242
6243
6244static bool update_sd_pick_busiest(struct lb_env *env,
6245 struct sd_lb_stats *sds,
6246 struct sched_group *sg,
6247 struct sg_lb_stats *sgs)
6248{
6249 struct sg_lb_stats *busiest = &sds->busiest_stat;
6250
6251 if (sgs->group_type > busiest->group_type)
6252 return true;
6253
6254 if (sgs->group_type < busiest->group_type)
6255 return false;
6256
6257 if (sgs->avg_load <= busiest->avg_load)
6258 return false;
6259
6260
6261 if (!(env->sd->flags & SD_ASYM_PACKING))
6262 return true;
6263
6264
6265
6266
6267
6268
6269 if (sgs->sum_nr_running && env->dst_cpu < group_first_cpu(sg)) {
6270 if (!sds->busiest)
6271 return true;
6272
6273 if (group_first_cpu(sds->busiest) > group_first_cpu(sg))
6274 return true;
6275 }
6276
6277 return false;
6278}
6279
6280#ifdef CONFIG_NUMA_BALANCING
6281static inline enum fbq_type fbq_classify_group(struct sg_lb_stats *sgs)
6282{
6283 if (sgs->sum_nr_running > sgs->nr_numa_running)
6284 return regular;
6285 if (sgs->sum_nr_running > sgs->nr_preferred_running)
6286 return remote;
6287 return all;
6288}
6289
6290static inline enum fbq_type fbq_classify_rq(struct rq *rq)
6291{
6292 if (rq->nr_running > rq->nr_numa_running)
6293 return regular;
6294 if (rq->nr_running > rq->nr_preferred_running)
6295 return remote;
6296 return all;
6297}
6298#else
6299static inline enum fbq_type fbq_classify_group(struct sg_lb_stats *sgs)
6300{
6301 return all;
6302}
6303
6304static inline enum fbq_type fbq_classify_rq(struct rq *rq)
6305{
6306 return regular;
6307}
6308#endif
6309
6310
6311
6312
6313
6314
6315static inline void update_sd_lb_stats(struct lb_env *env, struct sd_lb_stats *sds)
6316{
6317 struct sched_domain *child = env->sd->child;
6318 struct sched_group *sg = env->sd->groups;
6319 struct sg_lb_stats tmp_sgs;
6320 int load_idx, prefer_sibling = 0;
6321 bool overload = false;
6322
6323 if (child && child->flags & SD_PREFER_SIBLING)
6324 prefer_sibling = 1;
6325
6326 load_idx = get_sd_load_idx(env->sd, env->idle);
6327
6328 do {
6329 struct sg_lb_stats *sgs = &tmp_sgs;
6330 int local_group;
6331
6332 local_group = cpumask_test_cpu(env->dst_cpu, sched_group_cpus(sg));
6333 if (local_group) {
6334 sds->local = sg;
6335 sgs = &sds->local_stat;
6336
6337 if (env->idle != CPU_NEWLY_IDLE ||
6338 time_after_eq(jiffies, sg->sgc->next_update))
6339 update_group_capacity(env->sd, env->dst_cpu);
6340 }
6341
6342 update_sg_lb_stats(env, sg, load_idx, local_group, sgs,
6343 &overload);
6344
6345 if (local_group)
6346 goto next_group;
6347
6348
6349
6350
6351
6352
6353
6354
6355
6356
6357
6358 if (prefer_sibling && sds->local &&
6359 sds->local_stat.group_has_free_capacity) {
6360 sgs->group_capacity_factor = min(sgs->group_capacity_factor, 1U);
6361 sgs->group_type = group_classify(sg, sgs);
6362 }
6363
6364 if (update_sd_pick_busiest(env, sds, sg, sgs)) {
6365 sds->busiest = sg;
6366 sds->busiest_stat = *sgs;
6367 }
6368
6369next_group:
6370
6371 sds->total_load += sgs->group_load;
6372 sds->total_capacity += sgs->group_capacity;
6373
6374 sg = sg->next;
6375 } while (sg != env->sd->groups);
6376
6377 if (env->sd->flags & SD_NUMA)
6378 env->fbq_type = fbq_classify_group(&sds->busiest_stat);
6379
6380 if (!env->sd->parent) {
6381
6382 if (env->dst_rq->rd->overload != overload)
6383 env->dst_rq->rd->overload = overload;
6384 }
6385
6386}
6387
6388
6389
6390
6391
6392
6393
6394
6395
6396
6397
6398
6399
6400
6401
6402
6403
6404
6405
6406
6407
6408
6409
6410
6411static int check_asym_packing(struct lb_env *env, struct sd_lb_stats *sds)
6412{
6413 int busiest_cpu;
6414
6415 if (!(env->sd->flags & SD_ASYM_PACKING))
6416 return 0;
6417
6418 if (!sds->busiest)
6419 return 0;
6420
6421 busiest_cpu = group_first_cpu(sds->busiest);
6422 if (env->dst_cpu > busiest_cpu)
6423 return 0;
6424
6425 env->imbalance = DIV_ROUND_CLOSEST(
6426 sds->busiest_stat.avg_load * sds->busiest_stat.group_capacity,
6427 SCHED_CAPACITY_SCALE);
6428
6429 return 1;
6430}
6431
6432
6433
6434
6435
6436
6437
6438
6439static inline
6440void fix_small_imbalance(struct lb_env *env, struct sd_lb_stats *sds)
6441{
6442 unsigned long tmp, capa_now = 0, capa_move = 0;
6443 unsigned int imbn = 2;
6444 unsigned long scaled_busy_load_per_task;
6445 struct sg_lb_stats *local, *busiest;
6446
6447 local = &sds->local_stat;
6448 busiest = &sds->busiest_stat;
6449
6450 if (!local->sum_nr_running)
6451 local->load_per_task = cpu_avg_load_per_task(env->dst_cpu);
6452 else if (busiest->load_per_task > local->load_per_task)
6453 imbn = 1;
6454
6455 scaled_busy_load_per_task =
6456 (busiest->load_per_task * SCHED_CAPACITY_SCALE) /
6457 busiest->group_capacity;
6458
6459 if (busiest->avg_load + scaled_busy_load_per_task >=
6460 local->avg_load + (scaled_busy_load_per_task * imbn)) {
6461 env->imbalance = busiest->load_per_task;
6462 return;
6463 }
6464
6465
6466
6467
6468
6469
6470
6471 capa_now += busiest->group_capacity *
6472 min(busiest->load_per_task, busiest->avg_load);
6473 capa_now += local->group_capacity *
6474 min(local->load_per_task, local->avg_load);
6475 capa_now /= SCHED_CAPACITY_SCALE;
6476
6477
6478 if (busiest->avg_load > scaled_busy_load_per_task) {
6479 capa_move += busiest->group_capacity *
6480 min(busiest->load_per_task,
6481 busiest->avg_load - scaled_busy_load_per_task);
6482 }
6483
6484
6485 if (busiest->avg_load * busiest->group_capacity <
6486 busiest->load_per_task * SCHED_CAPACITY_SCALE) {
6487 tmp = (busiest->avg_load * busiest->group_capacity) /
6488 local->group_capacity;
6489 } else {
6490 tmp = (busiest->load_per_task * SCHED_CAPACITY_SCALE) /
6491 local->group_capacity;
6492 }
6493 capa_move += local->group_capacity *
6494 min(local->load_per_task, local->avg_load + tmp);
6495 capa_move /= SCHED_CAPACITY_SCALE;
6496
6497
6498 if (capa_move > capa_now)
6499 env->imbalance = busiest->load_per_task;
6500}
6501
6502
6503
6504
6505
6506
6507
6508static inline void calculate_imbalance(struct lb_env *env, struct sd_lb_stats *sds)
6509{
6510 unsigned long max_pull, load_above_capacity = ~0UL;
6511 struct sg_lb_stats *local, *busiest;
6512
6513 local = &sds->local_stat;
6514 busiest = &sds->busiest_stat;
6515
6516 if (busiest->group_type == group_imbalanced) {
6517
6518
6519
6520
6521 busiest->load_per_task =
6522 min(busiest->load_per_task, sds->avg_load);
6523 }
6524
6525
6526
6527
6528
6529
6530 if (busiest->avg_load <= sds->avg_load ||
6531 local->avg_load >= sds->avg_load) {
6532 env->imbalance = 0;
6533 return fix_small_imbalance(env, sds);
6534 }
6535
6536
6537
6538
6539 if (busiest->group_type == group_overloaded &&
6540 local->group_type == group_overloaded) {
6541 load_above_capacity =
6542 (busiest->sum_nr_running - busiest->group_capacity_factor);
6543
6544 load_above_capacity *= (SCHED_LOAD_SCALE * SCHED_CAPACITY_SCALE);
6545 load_above_capacity /= busiest->group_capacity;
6546 }
6547
6548
6549
6550
6551
6552
6553
6554
6555
6556 max_pull = min(busiest->avg_load - sds->avg_load, load_above_capacity);
6557
6558
6559 env->imbalance = min(
6560 max_pull * busiest->group_capacity,
6561 (sds->avg_load - local->avg_load) * local->group_capacity
6562 ) / SCHED_CAPACITY_SCALE;
6563
6564
6565
6566
6567
6568
6569
6570 if (env->imbalance < busiest->load_per_task)
6571 return fix_small_imbalance(env, sds);
6572}
6573
6574
6575
6576
6577
6578
6579
6580
6581
6582
6583
6584
6585
6586
6587
6588
6589
6590
6591
6592
6593static struct sched_group *find_busiest_group(struct lb_env *env)
6594{
6595 struct sg_lb_stats *local, *busiest;
6596 struct sd_lb_stats sds;
6597
6598 init_sd_lb_stats(&sds);
6599
6600
6601
6602
6603
6604 update_sd_lb_stats(env, &sds);
6605 local = &sds.local_stat;
6606 busiest = &sds.busiest_stat;
6607
6608 if ((env->idle == CPU_IDLE || env->idle == CPU_NEWLY_IDLE) &&
6609 check_asym_packing(env, &sds))
6610 return sds.busiest;
6611
6612
6613 if (!sds.busiest || busiest->sum_nr_running == 0)
6614 goto out_balanced;
6615
6616 sds.avg_load = (SCHED_CAPACITY_SCALE * sds.total_load)
6617 / sds.total_capacity;
6618
6619
6620
6621
6622
6623
6624 if (busiest->group_type == group_imbalanced)
6625 goto force_balance;
6626
6627
6628 if (env->idle == CPU_NEWLY_IDLE && local->group_has_free_capacity &&
6629 !busiest->group_has_free_capacity)
6630 goto force_balance;
6631
6632
6633
6634
6635
6636 if (local->avg_load >= busiest->avg_load)
6637 goto out_balanced;
6638
6639
6640
6641
6642
6643 if (local->avg_load >= sds.avg_load)
6644 goto out_balanced;
6645
6646 if (env->idle == CPU_IDLE) {
6647
6648
6649
6650
6651
6652
6653
6654 if ((busiest->group_type != group_overloaded) &&
6655 (local->idle_cpus <= (busiest->idle_cpus + 1)))
6656 goto out_balanced;
6657 } else {
6658
6659
6660
6661
6662 if (100 * busiest->avg_load <=
6663 env->sd->imbalance_pct * local->avg_load)
6664 goto out_balanced;
6665 }
6666
6667force_balance:
6668
6669 calculate_imbalance(env, &sds);
6670 return sds.busiest;
6671
6672out_balanced:
6673 env->imbalance = 0;
6674 return NULL;
6675}
6676
6677
6678
6679
6680static struct rq *find_busiest_queue(struct lb_env *env,
6681 struct sched_group *group)
6682{
6683 struct rq *busiest = NULL, *rq;
6684 unsigned long busiest_load = 0, busiest_capacity = 1;
6685 int i;
6686
6687 for_each_cpu_and(i, sched_group_cpus(group), env->cpus) {
6688 unsigned long capacity, capacity_factor, wl;
6689 enum fbq_type rt;
6690
6691 rq = cpu_rq(i);
6692 rt = fbq_classify_rq(rq);
6693
6694
6695
6696
6697
6698
6699
6700
6701
6702
6703
6704
6705
6706
6707
6708
6709
6710
6711
6712
6713 if (rt > env->fbq_type)
6714 continue;
6715
6716 capacity = capacity_of(i);
6717 capacity_factor = DIV_ROUND_CLOSEST(capacity, SCHED_CAPACITY_SCALE);
6718 if (!capacity_factor)
6719 capacity_factor = fix_small_capacity(env->sd, group);
6720
6721 wl = weighted_cpuload(i);
6722
6723
6724
6725
6726
6727 if (capacity_factor && rq->nr_running == 1 && wl > env->imbalance)
6728 continue;
6729
6730
6731
6732
6733
6734
6735
6736
6737
6738
6739
6740
6741 if (wl * busiest_capacity > busiest_load * capacity) {
6742 busiest_load = wl;
6743 busiest_capacity = capacity;
6744 busiest = rq;
6745 }
6746 }
6747
6748 return busiest;
6749}
6750
6751
6752
6753
6754
6755#define MAX_PINNED_INTERVAL 512
6756
6757
6758DEFINE_PER_CPU(cpumask_var_t, load_balance_mask);
6759
6760static int need_active_balance(struct lb_env *env)
6761{
6762 struct sched_domain *sd = env->sd;
6763
6764 if (env->idle == CPU_NEWLY_IDLE) {
6765
6766
6767
6768
6769
6770
6771 if ((sd->flags & SD_ASYM_PACKING) && env->src_cpu > env->dst_cpu)
6772 return 1;
6773 }
6774
6775 return unlikely(sd->nr_balance_failed > sd->cache_nice_tries+2);
6776}
6777
6778static int active_load_balance_cpu_stop(void *data);
6779
6780static int should_we_balance(struct lb_env *env)
6781{
6782 struct sched_group *sg = env->sd->groups;
6783 struct cpumask *sg_cpus, *sg_mask;
6784 int cpu, balance_cpu = -1;
6785
6786
6787
6788
6789
6790 if (env->idle == CPU_NEWLY_IDLE)
6791 return 1;
6792
6793 sg_cpus = sched_group_cpus(sg);
6794 sg_mask = sched_group_mask(sg);
6795
6796 for_each_cpu_and(cpu, sg_cpus, env->cpus) {
6797 if (!cpumask_test_cpu(cpu, sg_mask) || !idle_cpu(cpu))
6798 continue;
6799
6800 balance_cpu = cpu;
6801 break;
6802 }
6803
6804 if (balance_cpu == -1)
6805 balance_cpu = group_balance_cpu(sg);
6806
6807
6808
6809
6810
6811 return balance_cpu == env->dst_cpu;
6812}
6813
6814
6815
6816
6817
6818static int load_balance(int this_cpu, struct rq *this_rq,
6819 struct sched_domain *sd, enum cpu_idle_type idle,
6820 int *continue_balancing)
6821{
6822 int ld_moved, cur_ld_moved, active_balance = 0;
6823 struct sched_domain *sd_parent = sd->parent;
6824 struct sched_group *group;
6825 struct rq *busiest;
6826 unsigned long flags;
6827 struct cpumask *cpus = this_cpu_cpumask_var_ptr(load_balance_mask);
6828
6829 struct lb_env env = {
6830 .sd = sd,
6831 .dst_cpu = this_cpu,
6832 .dst_rq = this_rq,
6833 .dst_grpmask = sched_group_cpus(sd->groups),
6834 .idle = idle,
6835 .loop_break = sched_nr_migrate_break,
6836 .cpus = cpus,
6837 .fbq_type = all,
6838 .tasks = LIST_HEAD_INIT(env.tasks),
6839 };
6840
6841
6842
6843
6844
6845 if (idle == CPU_NEWLY_IDLE)
6846 env.dst_grpmask = NULL;
6847
6848 cpumask_copy(cpus, cpu_active_mask);
6849
6850 schedstat_inc(sd, lb_count[idle]);
6851
6852redo:
6853 if (!should_we_balance(&env)) {
6854 *continue_balancing = 0;
6855 goto out_balanced;
6856 }
6857
6858 group = find_busiest_group(&env);
6859 if (!group) {
6860 schedstat_inc(sd, lb_nobusyg[idle]);
6861 goto out_balanced;
6862 }
6863
6864 busiest = find_busiest_queue(&env, group);
6865 if (!busiest) {
6866 schedstat_inc(sd, lb_nobusyq[idle]);
6867 goto out_balanced;
6868 }
6869
6870 BUG_ON(busiest == env.dst_rq);
6871
6872 schedstat_add(sd, lb_imbalance[idle], env.imbalance);
6873
6874 ld_moved = 0;
6875 if (busiest->nr_running > 1) {
6876
6877
6878
6879
6880
6881
6882 env.flags |= LBF_ALL_PINNED;
6883 env.src_cpu = busiest->cpu;
6884 env.src_rq = busiest;
6885 env.loop_max = min(sysctl_sched_nr_migrate, busiest->nr_running);
6886
6887more_balance:
6888 raw_spin_lock_irqsave(&busiest->lock, flags);
6889
6890
6891
6892
6893
6894 cur_ld_moved = detach_tasks(&env);
6895
6896
6897
6898
6899
6900
6901
6902
6903
6904 raw_spin_unlock(&busiest->lock);
6905
6906 if (cur_ld_moved) {
6907 attach_tasks(&env);
6908 ld_moved += cur_ld_moved;
6909 }
6910
6911 local_irq_restore(flags);
6912
6913 if (env.flags & LBF_NEED_BREAK) {
6914 env.flags &= ~LBF_NEED_BREAK;
6915 goto more_balance;
6916 }
6917
6918
6919
6920
6921
6922
6923
6924
6925
6926
6927
6928
6929
6930
6931
6932
6933
6934
6935
6936
6937 if ((env.flags & LBF_DST_PINNED) && env.imbalance > 0) {
6938
6939
6940 cpumask_clear_cpu(env.dst_cpu, env.cpus);
6941
6942 env.dst_rq = cpu_rq(env.new_dst_cpu);
6943 env.dst_cpu = env.new_dst_cpu;
6944 env.flags &= ~LBF_DST_PINNED;
6945 env.loop = 0;
6946 env.loop_break = sched_nr_migrate_break;
6947
6948
6949
6950
6951
6952 goto more_balance;
6953 }
6954
6955
6956
6957
6958 if (sd_parent) {
6959 int *group_imbalance = &sd_parent->groups->sgc->imbalance;
6960
6961 if ((env.flags & LBF_SOME_PINNED) && env.imbalance > 0)
6962 *group_imbalance = 1;
6963 }
6964
6965
6966 if (unlikely(env.flags & LBF_ALL_PINNED)) {
6967 cpumask_clear_cpu(cpu_of(busiest), cpus);
6968 if (!cpumask_empty(cpus)) {
6969 env.loop = 0;
6970 env.loop_break = sched_nr_migrate_break;
6971 goto redo;
6972 }
6973 goto out_all_pinned;
6974 }
6975 }
6976
6977 if (!ld_moved) {
6978 schedstat_inc(sd, lb_failed[idle]);
6979
6980
6981
6982
6983
6984
6985 if (idle != CPU_NEWLY_IDLE)
6986 sd->nr_balance_failed++;
6987
6988 if (need_active_balance(&env)) {
6989 raw_spin_lock_irqsave(&busiest->lock, flags);
6990
6991
6992
6993
6994
6995 if (!cpumask_test_cpu(this_cpu,
6996 tsk_cpus_allowed(busiest->curr))) {
6997 raw_spin_unlock_irqrestore(&busiest->lock,
6998 flags);
6999 env.flags |= LBF_ALL_PINNED;
7000 goto out_one_pinned;
7001 }
7002
7003
7004
7005
7006
7007
7008 if (!busiest->active_balance) {
7009 busiest->active_balance = 1;
7010 busiest->push_cpu = this_cpu;
7011 active_balance = 1;
7012 }
7013 raw_spin_unlock_irqrestore(&busiest->lock, flags);
7014
7015 if (active_balance) {
7016 stop_one_cpu_nowait(cpu_of(busiest),
7017 active_load_balance_cpu_stop, busiest,
7018 &busiest->active_balance_work);
7019 }
7020
7021
7022
7023
7024
7025 sd->nr_balance_failed = sd->cache_nice_tries+1;
7026 }
7027 } else
7028 sd->nr_balance_failed = 0;
7029
7030 if (likely(!active_balance)) {
7031
7032 sd->balance_interval = sd->min_interval;
7033 } else {
7034
7035
7036
7037
7038
7039
7040 if (sd->balance_interval < sd->max_interval)
7041 sd->balance_interval *= 2;
7042 }
7043
7044 goto out;
7045
7046out_balanced:
7047
7048
7049
7050
7051 if (sd_parent) {
7052 int *group_imbalance = &sd_parent->groups->sgc->imbalance;
7053
7054 if (*group_imbalance)
7055 *group_imbalance = 0;
7056 }
7057
7058out_all_pinned:
7059
7060
7061
7062
7063
7064 schedstat_inc(sd, lb_balanced[idle]);
7065
7066 sd->nr_balance_failed = 0;
7067
7068out_one_pinned:
7069
7070 if (((env.flags & LBF_ALL_PINNED) &&
7071 sd->balance_interval < MAX_PINNED_INTERVAL) ||
7072 (sd->balance_interval < sd->max_interval))
7073 sd->balance_interval *= 2;
7074
7075 ld_moved = 0;
7076out:
7077 return ld_moved;
7078}
7079
7080static inline unsigned long
7081get_sd_balance_interval(struct sched_domain *sd, int cpu_busy)
7082{
7083 unsigned long interval = sd->balance_interval;
7084
7085 if (cpu_busy)
7086 interval *= sd->busy_factor;
7087
7088
7089 interval = msecs_to_jiffies(interval);
7090 interval = clamp(interval, 1UL, max_load_balance_interval);
7091
7092 return interval;
7093}
7094
7095static inline void
7096update_next_balance(struct sched_domain *sd, int cpu_busy, unsigned long *next_balance)
7097{
7098 unsigned long interval, next;
7099
7100 interval = get_sd_balance_interval(sd, cpu_busy);
7101 next = sd->last_balance + interval;
7102
7103 if (time_after(*next_balance, next))
7104 *next_balance = next;
7105}
7106
7107
7108
7109
7110
7111static int idle_balance(struct rq *this_rq)
7112{
7113 unsigned long next_balance = jiffies + HZ;
7114 int this_cpu = this_rq->cpu;
7115 struct sched_domain *sd;
7116 int pulled_task = 0;
7117 u64 curr_cost = 0;
7118
7119 idle_enter_fair(this_rq);
7120
7121
7122
7123
7124
7125 this_rq->idle_stamp = rq_clock(this_rq);
7126
7127 if (this_rq->avg_idle < sysctl_sched_migration_cost ||
7128 !this_rq->rd->overload) {
7129 rcu_read_lock();
7130 sd = rcu_dereference_check_sched_domain(this_rq->sd);
7131 if (sd)
7132 update_next_balance(sd, 0, &next_balance);
7133 rcu_read_unlock();
7134
7135 goto out;
7136 }
7137
7138
7139
7140
7141 raw_spin_unlock(&this_rq->lock);
7142
7143 update_blocked_averages(this_cpu);
7144 rcu_read_lock();
7145 for_each_domain(this_cpu, sd) {
7146 int continue_balancing = 1;
7147 u64 t0, domain_cost;
7148
7149 if (!(sd->flags & SD_LOAD_BALANCE))
7150 continue;
7151
7152 if (this_rq->avg_idle < curr_cost + sd->max_newidle_lb_cost) {
7153 update_next_balance(sd, 0, &next_balance);
7154 break;
7155 }
7156
7157 if (sd->flags & SD_BALANCE_NEWIDLE) {
7158 t0 = sched_clock_cpu(this_cpu);
7159
7160 pulled_task = load_balance(this_cpu, this_rq,
7161 sd, CPU_NEWLY_IDLE,
7162 &continue_balancing);
7163
7164 domain_cost = sched_clock_cpu(this_cpu) - t0;
7165 if (domain_cost > sd->max_newidle_lb_cost)
7166 sd->max_newidle_lb_cost = domain_cost;
7167
7168 curr_cost += domain_cost;
7169 }
7170
7171 update_next_balance(sd, 0, &next_balance);
7172
7173
7174
7175
7176
7177 if (pulled_task || this_rq->nr_running > 0)
7178 break;
7179 }
7180 rcu_read_unlock();
7181
7182 raw_spin_lock(&this_rq->lock);
7183
7184 if (curr_cost > this_rq->max_idle_balance_cost)
7185 this_rq->max_idle_balance_cost = curr_cost;
7186
7187
7188
7189
7190
7191
7192 if (this_rq->cfs.h_nr_running && !pulled_task)
7193 pulled_task = 1;
7194
7195out:
7196
7197 if (time_after(this_rq->next_balance, next_balance))
7198 this_rq->next_balance = next_balance;
7199
7200
7201 if (this_rq->nr_running != this_rq->cfs.h_nr_running)
7202 pulled_task = -1;
7203
7204 if (pulled_task) {
7205 idle_exit_fair(this_rq);
7206 this_rq->idle_stamp = 0;
7207 }
7208
7209 return pulled_task;
7210}
7211
7212
7213
7214
7215
7216
7217
7218static int active_load_balance_cpu_stop(void *data)
7219{
7220 struct rq *busiest_rq = data;
7221 int busiest_cpu = cpu_of(busiest_rq);
7222 int target_cpu = busiest_rq->push_cpu;
7223 struct rq *target_rq = cpu_rq(target_cpu);
7224 struct sched_domain *sd;
7225 struct task_struct *p = NULL;
7226
7227 raw_spin_lock_irq(&busiest_rq->lock);
7228
7229
7230 if (unlikely(busiest_cpu != smp_processor_id() ||
7231 !busiest_rq->active_balance))
7232 goto out_unlock;
7233
7234
7235 if (busiest_rq->nr_running <= 1)
7236 goto out_unlock;
7237
7238
7239
7240
7241
7242
7243 BUG_ON(busiest_rq == target_rq);
7244
7245
7246 rcu_read_lock();
7247 for_each_domain(target_cpu, sd) {
7248 if ((sd->flags & SD_LOAD_BALANCE) &&
7249 cpumask_test_cpu(busiest_cpu, sched_domain_span(sd)))
7250 break;
7251 }
7252
7253 if (likely(sd)) {
7254 struct lb_env env = {
7255 .sd = sd,
7256 .dst_cpu = target_cpu,
7257 .dst_rq = target_rq,
7258 .src_cpu = busiest_rq->cpu,
7259 .src_rq = busiest_rq,
7260 .idle = CPU_IDLE,
7261 };
7262
7263 schedstat_inc(sd, alb_count);
7264
7265 p = detach_one_task(&env);
7266 if (p)
7267 schedstat_inc(sd, alb_pushed);
7268 else
7269 schedstat_inc(sd, alb_failed);
7270 }
7271 rcu_read_unlock();
7272out_unlock:
7273 busiest_rq->active_balance = 0;
7274 raw_spin_unlock(&busiest_rq->lock);
7275
7276 if (p)
7277 attach_one_task(target_rq, p);
7278
7279 local_irq_enable();
7280
7281 return 0;
7282}
7283
7284static inline int on_null_domain(struct rq *rq)
7285{
7286 return unlikely(!rcu_dereference_sched(rq->sd));
7287}
7288
7289#ifdef CONFIG_NO_HZ_COMMON
7290
7291
7292
7293
7294
7295
7296static struct {
7297 cpumask_var_t idle_cpus_mask;
7298 atomic_t nr_cpus;
7299 unsigned long next_balance;
7300} nohz ____cacheline_aligned;
7301
7302static inline int find_new_ilb(void)
7303{
7304 int ilb = cpumask_first(nohz.idle_cpus_mask);
7305
7306 if (ilb < nr_cpu_ids && idle_cpu(ilb))
7307 return ilb;
7308
7309 return nr_cpu_ids;
7310}
7311
7312
7313
7314
7315
7316
7317static void nohz_balancer_kick(void)
7318{
7319 int ilb_cpu;
7320
7321 nohz.next_balance++;
7322
7323 ilb_cpu = find_new_ilb();
7324
7325 if (ilb_cpu >= nr_cpu_ids)
7326 return;
7327
7328 if (test_and_set_bit(NOHZ_BALANCE_KICK, nohz_flags(ilb_cpu)))
7329 return;
7330
7331
7332
7333
7334
7335
7336 smp_send_reschedule(ilb_cpu);
7337 return;
7338}
7339
7340static inline void nohz_balance_exit_idle(int cpu)
7341{
7342 if (unlikely(test_bit(NOHZ_TICK_STOPPED, nohz_flags(cpu)))) {
7343
7344
7345
7346 if (likely(cpumask_test_cpu(cpu, nohz.idle_cpus_mask))) {
7347 cpumask_clear_cpu(cpu, nohz.idle_cpus_mask);
7348 atomic_dec(&nohz.nr_cpus);
7349 }
7350 clear_bit(NOHZ_TICK_STOPPED, nohz_flags(cpu));
7351 }
7352}
7353
7354static inline void set_cpu_sd_state_busy(void)
7355{
7356 struct sched_domain *sd;
7357 int cpu = smp_processor_id();
7358
7359 rcu_read_lock();
7360 sd = rcu_dereference(per_cpu(sd_busy, cpu));
7361
7362 if (!sd || !sd->nohz_idle)
7363 goto unlock;
7364 sd->nohz_idle = 0;
7365
7366 atomic_inc(&sd->groups->sgc->nr_busy_cpus);
7367unlock:
7368 rcu_read_unlock();
7369}
7370
7371void set_cpu_sd_state_idle(void)
7372{
7373 struct sched_domain *sd;
7374 int cpu = smp_processor_id();
7375
7376 rcu_read_lock();
7377 sd = rcu_dereference(per_cpu(sd_busy, cpu));
7378
7379 if (!sd || sd->nohz_idle)
7380 goto unlock;
7381 sd->nohz_idle = 1;
7382
7383 atomic_dec(&sd->groups->sgc->nr_busy_cpus);
7384unlock:
7385 rcu_read_unlock();
7386}
7387
7388
7389
7390
7391
7392void nohz_balance_enter_idle(int cpu)
7393{
7394
7395
7396
7397 if (!cpu_active(cpu))
7398 return;
7399
7400 if (test_bit(NOHZ_TICK_STOPPED, nohz_flags(cpu)))
7401 return;
7402
7403
7404
7405
7406 if (on_null_domain(cpu_rq(cpu)))
7407 return;
7408
7409 cpumask_set_cpu(cpu, nohz.idle_cpus_mask);
7410 atomic_inc(&nohz.nr_cpus);
7411 set_bit(NOHZ_TICK_STOPPED, nohz_flags(cpu));
7412}
7413
7414static int sched_ilb_notifier(struct notifier_block *nfb,
7415 unsigned long action, void *hcpu)
7416{
7417 switch (action & ~CPU_TASKS_FROZEN) {
7418 case CPU_DYING:
7419 nohz_balance_exit_idle(smp_processor_id());
7420 return NOTIFY_OK;
7421 default:
7422 return NOTIFY_DONE;
7423 }
7424}
7425#endif
7426
7427static DEFINE_SPINLOCK(balancing);
7428
7429
7430
7431
7432
7433void update_max_interval(void)
7434{
7435 max_load_balance_interval = HZ*num_online_cpus()/10;
7436}
7437
7438
7439
7440
7441
7442
7443
7444static void rebalance_domains(struct rq *rq, enum cpu_idle_type idle)
7445{
7446 int continue_balancing = 1;
7447 int cpu = rq->cpu;
7448 unsigned long interval;
7449 struct sched_domain *sd;
7450
7451 unsigned long next_balance = jiffies + 60*HZ;
7452 int update_next_balance = 0;
7453 int need_serialize, need_decay = 0;
7454 u64 max_cost = 0;
7455
7456 update_blocked_averages(cpu);
7457
7458 rcu_read_lock();
7459 for_each_domain(cpu, sd) {
7460
7461
7462
7463
7464 if (time_after(jiffies, sd->next_decay_max_lb_cost)) {
7465 sd->max_newidle_lb_cost =
7466 (sd->max_newidle_lb_cost * 253) / 256;
7467 sd->next_decay_max_lb_cost = jiffies + HZ;
7468 need_decay = 1;
7469 }
7470 max_cost += sd->max_newidle_lb_cost;
7471
7472 if (!(sd->flags & SD_LOAD_BALANCE))
7473 continue;
7474
7475
7476
7477
7478
7479
7480 if (!continue_balancing) {
7481 if (need_decay)
7482 continue;
7483 break;
7484 }
7485
7486 interval = get_sd_balance_interval(sd, idle != CPU_IDLE);
7487
7488 need_serialize = sd->flags & SD_SERIALIZE;
7489 if (need_serialize) {
7490 if (!spin_trylock(&balancing))
7491 goto out;
7492 }
7493
7494 if (time_after_eq(jiffies, sd->last_balance + interval)) {
7495 if (load_balance(cpu, rq, sd, idle, &continue_balancing)) {
7496
7497
7498
7499
7500
7501 idle = idle_cpu(cpu) ? CPU_IDLE : CPU_NOT_IDLE;
7502 }
7503 sd->last_balance = jiffies;
7504 interval = get_sd_balance_interval(sd, idle != CPU_IDLE);
7505 }
7506 if (need_serialize)
7507 spin_unlock(&balancing);
7508out:
7509 if (time_after(next_balance, sd->last_balance + interval)) {
7510 next_balance = sd->last_balance + interval;
7511 update_next_balance = 1;
7512 }
7513 }
7514 if (need_decay) {
7515
7516
7517
7518
7519 rq->max_idle_balance_cost =
7520 max((u64)sysctl_sched_migration_cost, max_cost);
7521 }
7522 rcu_read_unlock();
7523
7524
7525
7526
7527
7528
7529 if (likely(update_next_balance))
7530 rq->next_balance = next_balance;
7531}
7532
7533#ifdef CONFIG_NO_HZ_COMMON
7534
7535
7536
7537
7538static void nohz_idle_balance(struct rq *this_rq, enum cpu_idle_type idle)
7539{
7540 int this_cpu = this_rq->cpu;
7541 struct rq *rq;
7542 int balance_cpu;
7543
7544 if (idle != CPU_IDLE ||
7545 !test_bit(NOHZ_BALANCE_KICK, nohz_flags(this_cpu)))
7546 goto end;
7547
7548 for_each_cpu(balance_cpu, nohz.idle_cpus_mask) {
7549 if (balance_cpu == this_cpu || !idle_cpu(balance_cpu))
7550 continue;
7551
7552
7553
7554
7555
7556
7557 if (need_resched())
7558 break;
7559
7560 rq = cpu_rq(balance_cpu);
7561
7562
7563
7564
7565
7566 if (time_after_eq(jiffies, rq->next_balance)) {
7567 raw_spin_lock_irq(&rq->lock);
7568 update_rq_clock(rq);
7569 update_idle_cpu_load(rq);
7570 raw_spin_unlock_irq(&rq->lock);
7571 rebalance_domains(rq, CPU_IDLE);
7572 }
7573
7574 if (time_after(this_rq->next_balance, rq->next_balance))
7575 this_rq->next_balance = rq->next_balance;
7576 }
7577 nohz.next_balance = this_rq->next_balance;
7578end:
7579 clear_bit(NOHZ_BALANCE_KICK, nohz_flags(this_cpu));
7580}
7581
7582
7583
7584
7585
7586
7587
7588
7589
7590
7591static inline int nohz_kick_needed(struct rq *rq)
7592{
7593 unsigned long now = jiffies;
7594 struct sched_domain *sd;
7595 struct sched_group_capacity *sgc;
7596 int nr_busy, cpu = rq->cpu;
7597
7598 if (unlikely(rq->idle_balance))
7599 return 0;
7600
7601
7602
7603
7604
7605 set_cpu_sd_state_busy();
7606 nohz_balance_exit_idle(cpu);
7607
7608
7609
7610
7611
7612 if (likely(!atomic_read(&nohz.nr_cpus)))
7613 return 0;
7614
7615 if (time_before(now, nohz.next_balance))
7616 return 0;
7617
7618 if (rq->nr_running >= 2)
7619 goto need_kick;
7620
7621 rcu_read_lock();
7622 sd = rcu_dereference(per_cpu(sd_busy, cpu));
7623
7624 if (sd) {
7625 sgc = sd->groups->sgc;
7626 nr_busy = atomic_read(&sgc->nr_busy_cpus);
7627
7628 if (nr_busy > 1)
7629 goto need_kick_unlock;
7630 }
7631
7632 sd = rcu_dereference(per_cpu(sd_asym, cpu));
7633
7634 if (sd && (cpumask_first_and(nohz.idle_cpus_mask,
7635 sched_domain_span(sd)) < cpu))
7636 goto need_kick_unlock;
7637
7638 rcu_read_unlock();
7639 return 0;
7640
7641need_kick_unlock:
7642 rcu_read_unlock();
7643need_kick:
7644 return 1;
7645}
7646#else
7647static void nohz_idle_balance(struct rq *this_rq, enum cpu_idle_type idle) { }
7648#endif
7649
7650
7651
7652
7653
7654static void run_rebalance_domains(struct softirq_action *h)
7655{
7656 struct rq *this_rq = this_rq();
7657 enum cpu_idle_type idle = this_rq->idle_balance ?
7658 CPU_IDLE : CPU_NOT_IDLE;
7659
7660 rebalance_domains(this_rq, idle);
7661
7662
7663
7664
7665
7666
7667 nohz_idle_balance(this_rq, idle);
7668}
7669
7670
7671
7672
7673void trigger_load_balance(struct rq *rq)
7674{
7675
7676 if (unlikely(on_null_domain(rq)))
7677 return;
7678
7679 if (time_after_eq(jiffies, rq->next_balance))
7680 raise_softirq(SCHED_SOFTIRQ);
7681#ifdef CONFIG_NO_HZ_COMMON
7682 if (nohz_kick_needed(rq))
7683 nohz_balancer_kick();
7684#endif
7685}
7686
7687static void rq_online_fair(struct rq *rq)
7688{
7689 update_sysctl();
7690
7691 update_runtime_enabled(rq);
7692}
7693
7694static void rq_offline_fair(struct rq *rq)
7695{
7696 update_sysctl();
7697
7698
7699 unthrottle_offline_cfs_rqs(rq);
7700}
7701
7702#endif
7703
7704
7705
7706
7707static void task_tick_fair(struct rq *rq, struct task_struct *curr, int queued)
7708{
7709 struct cfs_rq *cfs_rq;
7710 struct sched_entity *se = &curr->se;
7711
7712 for_each_sched_entity(se) {
7713 cfs_rq = cfs_rq_of(se);
7714 entity_tick(cfs_rq, se, queued);
7715 }
7716
7717 if (numabalancing_enabled)
7718 task_tick_numa(rq, curr);
7719
7720 update_rq_runnable_avg(rq, 1);
7721}
7722
7723
7724
7725
7726
7727
7728static void task_fork_fair(struct task_struct *p)
7729{
7730 struct cfs_rq *cfs_rq;
7731 struct sched_entity *se = &p->se, *curr;
7732 int this_cpu = smp_processor_id();
7733 struct rq *rq = this_rq();
7734 unsigned long flags;
7735
7736 raw_spin_lock_irqsave(&rq->lock, flags);
7737
7738 update_rq_clock(rq);
7739
7740 cfs_rq = task_cfs_rq(current);
7741 curr = cfs_rq->curr;
7742
7743
7744
7745
7746
7747
7748
7749 rcu_read_lock();
7750 __set_task_cpu(p, this_cpu);
7751 rcu_read_unlock();
7752
7753 update_curr(cfs_rq);
7754
7755 if (curr)
7756 se->vruntime = curr->vruntime;
7757 place_entity(cfs_rq, se, 1);
7758
7759 if (sysctl_sched_child_runs_first && curr && entity_before(curr, se)) {
7760
7761
7762
7763
7764 swap(curr->vruntime, se->vruntime);
7765 resched_curr(rq);
7766 }
7767
7768 se->vruntime -= cfs_rq->min_vruntime;
7769
7770 raw_spin_unlock_irqrestore(&rq->lock, flags);
7771}
7772
7773
7774
7775
7776
7777static void
7778prio_changed_fair(struct rq *rq, struct task_struct *p, int oldprio)
7779{
7780 if (!task_on_rq_queued(p))
7781 return;
7782
7783
7784
7785
7786
7787
7788 if (rq->curr == p) {
7789 if (p->prio > oldprio)
7790 resched_curr(rq);
7791 } else
7792 check_preempt_curr(rq, p, 0);
7793}
7794
7795static void switched_from_fair(struct rq *rq, struct task_struct *p)
7796{
7797 struct sched_entity *se = &p->se;
7798 struct cfs_rq *cfs_rq = cfs_rq_of(se);
7799
7800
7801
7802
7803
7804
7805
7806
7807
7808
7809 if (!task_on_rq_queued(p) && p->state != TASK_RUNNING) {
7810
7811
7812
7813
7814 place_entity(cfs_rq, se, 0);
7815 se->vruntime -= cfs_rq->min_vruntime;
7816 }
7817
7818#ifdef CONFIG_SMP
7819
7820
7821
7822
7823
7824 if (se->avg.decay_count) {
7825 __synchronize_entity_decay(se);
7826 subtract_blocked_load_contrib(cfs_rq, se->avg.load_avg_contrib);
7827 }
7828#endif
7829}
7830
7831
7832
7833
7834static void switched_to_fair(struct rq *rq, struct task_struct *p)
7835{
7836#ifdef CONFIG_FAIR_GROUP_SCHED
7837 struct sched_entity *se = &p->se;
7838
7839
7840
7841
7842 se->depth = se->parent ? se->parent->depth + 1 : 0;
7843#endif
7844 if (!task_on_rq_queued(p))
7845 return;
7846
7847
7848
7849
7850
7851
7852 if (rq->curr == p)
7853 resched_curr(rq);
7854 else
7855 check_preempt_curr(rq, p, 0);
7856}
7857
7858
7859
7860
7861
7862
7863static void set_curr_task_fair(struct rq *rq)
7864{
7865 struct sched_entity *se = &rq->curr->se;
7866
7867 for_each_sched_entity(se) {
7868 struct cfs_rq *cfs_rq = cfs_rq_of(se);
7869
7870 set_next_entity(cfs_rq, se);
7871
7872 account_cfs_rq_runtime(cfs_rq, 0);
7873 }
7874}
7875
7876void init_cfs_rq(struct cfs_rq *cfs_rq)
7877{
7878 cfs_rq->tasks_timeline = RB_ROOT;
7879 cfs_rq->min_vruntime = (u64)(-(1LL << 20));
7880#ifndef CONFIG_64BIT
7881 cfs_rq->min_vruntime_copy = cfs_rq->min_vruntime;
7882#endif
7883#ifdef CONFIG_SMP
7884 atomic64_set(&cfs_rq->decay_counter, 1);
7885 atomic_long_set(&cfs_rq->removed_load, 0);
7886#endif
7887}
7888
7889#ifdef CONFIG_FAIR_GROUP_SCHED
7890static void task_move_group_fair(struct task_struct *p, int queued)
7891{
7892 struct sched_entity *se = &p->se;
7893 struct cfs_rq *cfs_rq;
7894
7895
7896
7897
7898
7899
7900
7901
7902
7903
7904
7905
7906
7907
7908
7909
7910
7911
7912
7913
7914
7915
7916
7917
7918
7919
7920 if (!queued && (!se->sum_exec_runtime || p->state == TASK_WAKING))
7921 queued = 1;
7922
7923 if (!queued)
7924 se->vruntime -= cfs_rq_of(se)->min_vruntime;
7925 set_task_rq(p, task_cpu(p));
7926 se->depth = se->parent ? se->parent->depth + 1 : 0;
7927 if (!queued) {
7928 cfs_rq = cfs_rq_of(se);
7929 se->vruntime += cfs_rq->min_vruntime;
7930#ifdef CONFIG_SMP
7931
7932
7933
7934
7935
7936 se->avg.decay_count = atomic64_read(&cfs_rq->decay_counter);
7937 cfs_rq->blocked_load_avg += se->avg.load_avg_contrib;
7938#endif
7939 }
7940}
7941
7942void free_fair_sched_group(struct task_group *tg)
7943{
7944 int i;
7945
7946 destroy_cfs_bandwidth(tg_cfs_bandwidth(tg));
7947
7948 for_each_possible_cpu(i) {
7949 if (tg->cfs_rq)
7950 kfree(tg->cfs_rq[i]);
7951 if (tg->se)
7952 kfree(tg->se[i]);
7953 }
7954
7955 kfree(tg->cfs_rq);
7956 kfree(tg->se);
7957}
7958
7959int alloc_fair_sched_group(struct task_group *tg, struct task_group *parent)
7960{
7961 struct cfs_rq *cfs_rq;
7962 struct sched_entity *se;
7963 int i;
7964
7965 tg->cfs_rq = kzalloc(sizeof(cfs_rq) * nr_cpu_ids, GFP_KERNEL);
7966 if (!tg->cfs_rq)
7967 goto err;
7968 tg->se = kzalloc(sizeof(se) * nr_cpu_ids, GFP_KERNEL);
7969 if (!tg->se)
7970 goto err;
7971
7972 tg->shares = NICE_0_LOAD;
7973
7974 init_cfs_bandwidth(tg_cfs_bandwidth(tg));
7975
7976 for_each_possible_cpu(i) {
7977 cfs_rq = kzalloc_node(sizeof(struct cfs_rq),
7978 GFP_KERNEL, cpu_to_node(i));
7979 if (!cfs_rq)
7980 goto err;
7981
7982 se = kzalloc_node(sizeof(struct sched_entity),
7983 GFP_KERNEL, cpu_to_node(i));
7984 if (!se)
7985 goto err_free_rq;
7986
7987 init_cfs_rq(cfs_rq);
7988 init_tg_cfs_entry(tg, cfs_rq, se, i, parent->se[i]);
7989 }
7990
7991 return 1;
7992
7993err_free_rq:
7994 kfree(cfs_rq);
7995err:
7996 return 0;
7997}
7998
7999void unregister_fair_sched_group(struct task_group *tg, int cpu)
8000{
8001 struct rq *rq = cpu_rq(cpu);
8002 unsigned long flags;
8003
8004
8005
8006
8007
8008 if (!tg->cfs_rq[cpu]->on_list)
8009 return;
8010
8011 raw_spin_lock_irqsave(&rq->lock, flags);
8012 list_del_leaf_cfs_rq(tg->cfs_rq[cpu]);
8013 raw_spin_unlock_irqrestore(&rq->lock, flags);
8014}
8015
8016void init_tg_cfs_entry(struct task_group *tg, struct cfs_rq *cfs_rq,
8017 struct sched_entity *se, int cpu,
8018 struct sched_entity *parent)
8019{
8020 struct rq *rq = cpu_rq(cpu);
8021
8022 cfs_rq->tg = tg;
8023 cfs_rq->rq = rq;
8024 init_cfs_rq_runtime(cfs_rq);
8025
8026 tg->cfs_rq[cpu] = cfs_rq;
8027 tg->se[cpu] = se;
8028
8029
8030 if (!se)
8031 return;
8032
8033 if (!parent) {
8034 se->cfs_rq = &rq->cfs;
8035 se->depth = 0;
8036 } else {
8037 se->cfs_rq = parent->my_q;
8038 se->depth = parent->depth + 1;
8039 }
8040
8041 se->my_q = cfs_rq;
8042
8043 update_load_set(&se->load, NICE_0_LOAD);
8044 se->parent = parent;
8045}
8046
8047static DEFINE_MUTEX(shares_mutex);
8048
8049int sched_group_set_shares(struct task_group *tg, unsigned long shares)
8050{
8051 int i;
8052 unsigned long flags;
8053
8054
8055
8056
8057 if (!tg->se[0])
8058 return -EINVAL;
8059
8060 shares = clamp(shares, scale_load(MIN_SHARES), scale_load(MAX_SHARES));
8061
8062 mutex_lock(&shares_mutex);
8063 if (tg->shares == shares)
8064 goto done;
8065
8066 tg->shares = shares;
8067 for_each_possible_cpu(i) {
8068 struct rq *rq = cpu_rq(i);
8069 struct sched_entity *se;
8070
8071 se = tg->se[i];
8072
8073 raw_spin_lock_irqsave(&rq->lock, flags);
8074
8075
8076 update_rq_clock(rq);
8077 for_each_sched_entity(se)
8078 update_cfs_shares(group_cfs_rq(se));
8079 raw_spin_unlock_irqrestore(&rq->lock, flags);
8080 }
8081
8082done:
8083 mutex_unlock(&shares_mutex);
8084 return 0;
8085}
8086#else
8087
8088void free_fair_sched_group(struct task_group *tg) { }
8089
8090int alloc_fair_sched_group(struct task_group *tg, struct task_group *parent)
8091{
8092 return 1;
8093}
8094
8095void unregister_fair_sched_group(struct task_group *tg, int cpu) { }
8096
8097#endif
8098
8099
8100static unsigned int get_rr_interval_fair(struct rq *rq, struct task_struct *task)
8101{
8102 struct sched_entity *se = &task->se;
8103 unsigned int rr_interval = 0;
8104
8105
8106
8107
8108
8109 if (rq->cfs.load.weight)
8110 rr_interval = NS_TO_JIFFIES(sched_slice(cfs_rq_of(se), se));
8111
8112 return rr_interval;
8113}
8114
8115
8116
8117
8118const struct sched_class fair_sched_class = {
8119 .next = &idle_sched_class,
8120 .enqueue_task = enqueue_task_fair,
8121 .dequeue_task = dequeue_task_fair,
8122 .yield_task = yield_task_fair,
8123 .yield_to_task = yield_to_task_fair,
8124
8125 .check_preempt_curr = check_preempt_wakeup,
8126
8127 .pick_next_task = pick_next_task_fair,
8128 .put_prev_task = put_prev_task_fair,
8129
8130#ifdef CONFIG_SMP
8131 .select_task_rq = select_task_rq_fair,
8132 .migrate_task_rq = migrate_task_rq_fair,
8133
8134 .rq_online = rq_online_fair,
8135 .rq_offline = rq_offline_fair,
8136
8137 .task_waking = task_waking_fair,
8138#endif
8139
8140 .set_curr_task = set_curr_task_fair,
8141 .task_tick = task_tick_fair,
8142 .task_fork = task_fork_fair,
8143
8144 .prio_changed = prio_changed_fair,
8145 .switched_from = switched_from_fair,
8146 .switched_to = switched_to_fair,
8147
8148 .get_rr_interval = get_rr_interval_fair,
8149
8150 .update_curr = update_curr_fair,
8151
8152#ifdef CONFIG_FAIR_GROUP_SCHED
8153 .task_move_group = task_move_group_fair,
8154#endif
8155};
8156
8157#ifdef CONFIG_SCHED_DEBUG
8158void print_cfs_stats(struct seq_file *m, int cpu)
8159{
8160 struct cfs_rq *cfs_rq;
8161
8162 rcu_read_lock();
8163 for_each_leaf_cfs_rq(cpu_rq(cpu), cfs_rq)
8164 print_cfs_rq(m, cpu, cfs_rq);
8165 rcu_read_unlock();
8166}
8167#endif
8168
8169__init void init_sched_fair_class(void)
8170{
8171#ifdef CONFIG_SMP
8172 open_softirq(SCHED_SOFTIRQ, run_rebalance_domains);
8173
8174#ifdef CONFIG_NO_HZ_COMMON
8175 nohz.next_balance = jiffies;
8176 zalloc_cpumask_var(&nohz.idle_cpus_mask, GFP_NOWAIT);
8177 cpu_notifier(sched_ilb_notifier, 0);
8178#endif
8179#endif
8180
8181}
8182