sched_fair.c 45 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990991992993994995996997998999100010011002100310041005100610071008100910101011101210131014101510161017101810191020102110221023102410251026102710281029103010311032103310341035103610371038103910401041104210431044104510461047104810491050105110521053105410551056105710581059106010611062106310641065106610671068106910701071107210731074107510761077107810791080108110821083108410851086108710881089109010911092109310941095109610971098109911001101110211031104110511061107110811091110111111121113111411151116111711181119112011211122112311241125112611271128112911301131113211331134113511361137113811391140114111421143114411451146114711481149115011511152115311541155115611571158115911601161116211631164116511661167116811691170117111721173117411751176117711781179118011811182118311841185118611871188118911901191119211931194119511961197119811991200120112021203120412051206120712081209121012111212121312141215121612171218121912201221122212231224122512261227122812291230123112321233123412351236123712381239124012411242124312441245124612471248124912501251125212531254125512561257125812591260126112621263126412651266126712681269127012711272127312741275127612771278127912801281128212831284128512861287128812891290129112921293129412951296129712981299130013011302130313041305130613071308130913101311131213131314131513161317131813191320132113221323132413251326132713281329133013311332133313341335133613371338133913401341134213431344134513461347134813491350135113521353135413551356135713581359136013611362136313641365136613671368136913701371137213731374137513761377137813791380138113821383138413851386138713881389139013911392139313941395139613971398139914001401140214031404140514061407140814091410141114121413141414151416141714181419142014211422142314241425142614271428142914301431143214331434143514361437143814391440144114421443144414451446144714481449145014511452145314541455145614571458145914601461146214631464146514661467146814691470147114721473147414751476147714781479148014811482148314841485148614871488148914901491149214931494149514961497149814991500150115021503150415051506150715081509151015111512151315141515151615171518151915201521152215231524152515261527152815291530153115321533153415351536153715381539154015411542154315441545154615471548154915501551155215531554155515561557155815591560156115621563156415651566156715681569157015711572157315741575157615771578157915801581158215831584158515861587158815891590159115921593159415951596159715981599160016011602160316041605160616071608160916101611161216131614161516161617161816191620162116221623162416251626162716281629163016311632163316341635163616371638163916401641164216431644164516461647164816491650165116521653165416551656165716581659166016611662166316641665166616671668166916701671167216731674167516761677167816791680168116821683168416851686168716881689169016911692169316941695169616971698169917001701170217031704170517061707170817091710171117121713171417151716171717181719172017211722172317241725172617271728172917301731173217331734173517361737173817391740174117421743174417451746174717481749175017511752175317541755175617571758175917601761176217631764176517661767176817691770177117721773177417751776177717781779178017811782178317841785178617871788178917901791179217931794179517961797179817991800180118021803180418051806180718081809181018111812181318141815181618171818181918201821182218231824182518261827182818291830183118321833183418351836183718381839184018411842184318441845184618471848184918501851185218531854185518561857185818591860186118621863186418651866186718681869187018711872187318741875187618771878
  1. /*
  2. * Completely Fair Scheduling (CFS) Class (SCHED_NORMAL/SCHED_BATCH)
  3. *
  4. * Copyright (C) 2007 Red Hat, Inc., Ingo Molnar <mingo@redhat.com>
  5. *
  6. * Interactivity improvements by Mike Galbraith
  7. * (C) 2007 Mike Galbraith <efault@gmx.de>
  8. *
  9. * Various enhancements by Dmitry Adamushko.
  10. * (C) 2007 Dmitry Adamushko <dmitry.adamushko@gmail.com>
  11. *
  12. * Group scheduling enhancements by Srivatsa Vaddagiri
  13. * Copyright IBM Corporation, 2007
  14. * Author: Srivatsa Vaddagiri <vatsa@linux.vnet.ibm.com>
  15. *
  16. * Scaled math optimizations by Thomas Gleixner
  17. * Copyright (C) 2007, Thomas Gleixner <tglx@linutronix.de>
  18. *
  19. * Adaptive scheduling granularity, math enhancements by Peter Zijlstra
  20. * Copyright (C) 2007 Red Hat, Inc., Peter Zijlstra <pzijlstr@redhat.com>
  21. */
  22. #include <linux/latencytop.h>
  23. /*
  24. * Targeted preemption latency for CPU-bound tasks:
  25. * (default: 5ms * (1 + ilog(ncpus)), units: nanoseconds)
  26. *
  27. * NOTE: this latency value is not the same as the concept of
  28. * 'timeslice length' - timeslices in CFS are of variable length
  29. * and have no persistent notion like in traditional, time-slice
  30. * based scheduling concepts.
  31. *
  32. * (to see the precise effective timeslice length of your workload,
  33. * run vmstat and monitor the context-switches (cs) field)
  34. */
  35. unsigned int sysctl_sched_latency = 5000000ULL;
  36. /*
  37. * Minimal preemption granularity for CPU-bound tasks:
  38. * (default: 1 msec * (1 + ilog(ncpus)), units: nanoseconds)
  39. */
  40. unsigned int sysctl_sched_min_granularity = 1000000ULL;
  41. /*
  42. * is kept at sysctl_sched_latency / sysctl_sched_min_granularity
  43. */
  44. static unsigned int sched_nr_latency = 5;
  45. /*
  46. * After fork, child runs first. If set to 0 (default) then
  47. * parent will (try to) run first.
  48. */
  49. unsigned int sysctl_sched_child_runs_first __read_mostly;
  50. /*
  51. * sys_sched_yield() compat mode
  52. *
  53. * This option switches the agressive yield implementation of the
  54. * old scheduler back on.
  55. */
  56. unsigned int __read_mostly sysctl_sched_compat_yield;
  57. /*
  58. * SCHED_OTHER wake-up granularity.
  59. * (default: 1 msec * (1 + ilog(ncpus)), units: nanoseconds)
  60. *
  61. * This option delays the preemption effects of decoupled workloads
  62. * and reduces their over-scheduling. Synchronous workloads will still
  63. * have immediate wakeup/sleep latencies.
  64. */
  65. unsigned int sysctl_sched_wakeup_granularity = 1000000UL;
  66. const_debug unsigned int sysctl_sched_migration_cost = 500000UL;
  67. static const struct sched_class fair_sched_class;
  68. /**************************************************************
  69. * CFS operations on generic schedulable entities:
  70. */
  71. #ifdef CONFIG_FAIR_GROUP_SCHED
  72. /* cpu runqueue to which this cfs_rq is attached */
  73. static inline struct rq *rq_of(struct cfs_rq *cfs_rq)
  74. {
  75. return cfs_rq->rq;
  76. }
  77. /* An entity is a task if it doesn't "own" a runqueue */
  78. #define entity_is_task(se) (!se->my_q)
  79. static inline struct task_struct *task_of(struct sched_entity *se)
  80. {
  81. #ifdef CONFIG_SCHED_DEBUG
  82. WARN_ON_ONCE(!entity_is_task(se));
  83. #endif
  84. return container_of(se, struct task_struct, se);
  85. }
  86. /* Walk up scheduling entities hierarchy */
  87. #define for_each_sched_entity(se) \
  88. for (; se; se = se->parent)
  89. static inline struct cfs_rq *task_cfs_rq(struct task_struct *p)
  90. {
  91. return p->se.cfs_rq;
  92. }
  93. /* runqueue on which this entity is (to be) queued */
  94. static inline struct cfs_rq *cfs_rq_of(struct sched_entity *se)
  95. {
  96. return se->cfs_rq;
  97. }
  98. /* runqueue "owned" by this group */
  99. static inline struct cfs_rq *group_cfs_rq(struct sched_entity *grp)
  100. {
  101. return grp->my_q;
  102. }
  103. /* Given a group's cfs_rq on one cpu, return its corresponding cfs_rq on
  104. * another cpu ('this_cpu')
  105. */
  106. static inline struct cfs_rq *cpu_cfs_rq(struct cfs_rq *cfs_rq, int this_cpu)
  107. {
  108. return cfs_rq->tg->cfs_rq[this_cpu];
  109. }
  110. /* Iterate thr' all leaf cfs_rq's on a runqueue */
  111. #define for_each_leaf_cfs_rq(rq, cfs_rq) \
  112. list_for_each_entry_rcu(cfs_rq, &rq->leaf_cfs_rq_list, leaf_cfs_rq_list)
  113. /* Do the two (enqueued) entities belong to the same group ? */
  114. static inline int
  115. is_same_group(struct sched_entity *se, struct sched_entity *pse)
  116. {
  117. if (se->cfs_rq == pse->cfs_rq)
  118. return 1;
  119. return 0;
  120. }
  121. static inline struct sched_entity *parent_entity(struct sched_entity *se)
  122. {
  123. return se->parent;
  124. }
  125. /* return depth at which a sched entity is present in the hierarchy */
  126. static inline int depth_se(struct sched_entity *se)
  127. {
  128. int depth = 0;
  129. for_each_sched_entity(se)
  130. depth++;
  131. return depth;
  132. }
  133. static void
  134. find_matching_se(struct sched_entity **se, struct sched_entity **pse)
  135. {
  136. int se_depth, pse_depth;
  137. /*
  138. * preemption test can be made between sibling entities who are in the
  139. * same cfs_rq i.e who have a common parent. Walk up the hierarchy of
  140. * both tasks until we find their ancestors who are siblings of common
  141. * parent.
  142. */
  143. /* First walk up until both entities are at same depth */
  144. se_depth = depth_se(*se);
  145. pse_depth = depth_se(*pse);
  146. while (se_depth > pse_depth) {
  147. se_depth--;
  148. *se = parent_entity(*se);
  149. }
  150. while (pse_depth > se_depth) {
  151. pse_depth--;
  152. *pse = parent_entity(*pse);
  153. }
  154. while (!is_same_group(*se, *pse)) {
  155. *se = parent_entity(*se);
  156. *pse = parent_entity(*pse);
  157. }
  158. }
  159. #else /* !CONFIG_FAIR_GROUP_SCHED */
  160. static inline struct task_struct *task_of(struct sched_entity *se)
  161. {
  162. return container_of(se, struct task_struct, se);
  163. }
  164. static inline struct rq *rq_of(struct cfs_rq *cfs_rq)
  165. {
  166. return container_of(cfs_rq, struct rq, cfs);
  167. }
  168. #define entity_is_task(se) 1
  169. #define for_each_sched_entity(se) \
  170. for (; se; se = NULL)
  171. static inline struct cfs_rq *task_cfs_rq(struct task_struct *p)
  172. {
  173. return &task_rq(p)->cfs;
  174. }
  175. static inline struct cfs_rq *cfs_rq_of(struct sched_entity *se)
  176. {
  177. struct task_struct *p = task_of(se);
  178. struct rq *rq = task_rq(p);
  179. return &rq->cfs;
  180. }
  181. /* runqueue "owned" by this group */
  182. static inline struct cfs_rq *group_cfs_rq(struct sched_entity *grp)
  183. {
  184. return NULL;
  185. }
  186. static inline struct cfs_rq *cpu_cfs_rq(struct cfs_rq *cfs_rq, int this_cpu)
  187. {
  188. return &cpu_rq(this_cpu)->cfs;
  189. }
  190. #define for_each_leaf_cfs_rq(rq, cfs_rq) \
  191. for (cfs_rq = &rq->cfs; cfs_rq; cfs_rq = NULL)
  192. static inline int
  193. is_same_group(struct sched_entity *se, struct sched_entity *pse)
  194. {
  195. return 1;
  196. }
  197. static inline struct sched_entity *parent_entity(struct sched_entity *se)
  198. {
  199. return NULL;
  200. }
  201. static inline void
  202. find_matching_se(struct sched_entity **se, struct sched_entity **pse)
  203. {
  204. }
  205. #endif /* CONFIG_FAIR_GROUP_SCHED */
  206. /**************************************************************
  207. * Scheduling class tree data structure manipulation methods:
  208. */
  209. static inline u64 max_vruntime(u64 min_vruntime, u64 vruntime)
  210. {
  211. s64 delta = (s64)(vruntime - min_vruntime);
  212. if (delta > 0)
  213. min_vruntime = vruntime;
  214. return min_vruntime;
  215. }
  216. static inline u64 min_vruntime(u64 min_vruntime, u64 vruntime)
  217. {
  218. s64 delta = (s64)(vruntime - min_vruntime);
  219. if (delta < 0)
  220. min_vruntime = vruntime;
  221. return min_vruntime;
  222. }
  223. static inline int entity_before(struct sched_entity *a,
  224. struct sched_entity *b)
  225. {
  226. return (s64)(a->vruntime - b->vruntime) < 0;
  227. }
  228. static inline s64 entity_key(struct cfs_rq *cfs_rq, struct sched_entity *se)
  229. {
  230. return se->vruntime - cfs_rq->min_vruntime;
  231. }
  232. static void update_min_vruntime(struct cfs_rq *cfs_rq)
  233. {
  234. u64 vruntime = cfs_rq->min_vruntime;
  235. if (cfs_rq->curr)
  236. vruntime = cfs_rq->curr->vruntime;
  237. if (cfs_rq->rb_leftmost) {
  238. struct sched_entity *se = rb_entry(cfs_rq->rb_leftmost,
  239. struct sched_entity,
  240. run_node);
  241. if (!cfs_rq->curr)
  242. vruntime = se->vruntime;
  243. else
  244. vruntime = min_vruntime(vruntime, se->vruntime);
  245. }
  246. cfs_rq->min_vruntime = max_vruntime(cfs_rq->min_vruntime, vruntime);
  247. }
  248. /*
  249. * Enqueue an entity into the rb-tree:
  250. */
  251. static void __enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
  252. {
  253. struct rb_node **link = &cfs_rq->tasks_timeline.rb_node;
  254. struct rb_node *parent = NULL;
  255. struct sched_entity *entry;
  256. s64 key = entity_key(cfs_rq, se);
  257. int leftmost = 1;
  258. /*
  259. * Find the right place in the rbtree:
  260. */
  261. while (*link) {
  262. parent = *link;
  263. entry = rb_entry(parent, struct sched_entity, run_node);
  264. /*
  265. * We dont care about collisions. Nodes with
  266. * the same key stay together.
  267. */
  268. if (key < entity_key(cfs_rq, entry)) {
  269. link = &parent->rb_left;
  270. } else {
  271. link = &parent->rb_right;
  272. leftmost = 0;
  273. }
  274. }
  275. /*
  276. * Maintain a cache of leftmost tree entries (it is frequently
  277. * used):
  278. */
  279. if (leftmost)
  280. cfs_rq->rb_leftmost = &se->run_node;
  281. rb_link_node(&se->run_node, parent, link);
  282. rb_insert_color(&se->run_node, &cfs_rq->tasks_timeline);
  283. }
  284. static void __dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
  285. {
  286. if (cfs_rq->rb_leftmost == &se->run_node) {
  287. struct rb_node *next_node;
  288. next_node = rb_next(&se->run_node);
  289. cfs_rq->rb_leftmost = next_node;
  290. }
  291. rb_erase(&se->run_node, &cfs_rq->tasks_timeline);
  292. }
  293. static struct sched_entity *__pick_next_entity(struct cfs_rq *cfs_rq)
  294. {
  295. struct rb_node *left = cfs_rq->rb_leftmost;
  296. if (!left)
  297. return NULL;
  298. return rb_entry(left, struct sched_entity, run_node);
  299. }
  300. static struct sched_entity *__pick_last_entity(struct cfs_rq *cfs_rq)
  301. {
  302. struct rb_node *last = rb_last(&cfs_rq->tasks_timeline);
  303. if (!last)
  304. return NULL;
  305. return rb_entry(last, struct sched_entity, run_node);
  306. }
  307. /**************************************************************
  308. * Scheduling class statistics methods:
  309. */
  310. #ifdef CONFIG_SCHED_DEBUG
  311. int sched_nr_latency_handler(struct ctl_table *table, int write,
  312. struct file *filp, void __user *buffer, size_t *lenp,
  313. loff_t *ppos)
  314. {
  315. int ret = proc_dointvec_minmax(table, write, filp, buffer, lenp, ppos);
  316. if (ret || !write)
  317. return ret;
  318. sched_nr_latency = DIV_ROUND_UP(sysctl_sched_latency,
  319. sysctl_sched_min_granularity);
  320. return 0;
  321. }
  322. #endif
  323. /*
  324. * delta /= w
  325. */
  326. static inline unsigned long
  327. calc_delta_fair(unsigned long delta, struct sched_entity *se)
  328. {
  329. if (unlikely(se->load.weight != NICE_0_LOAD))
  330. delta = calc_delta_mine(delta, NICE_0_LOAD, &se->load);
  331. return delta;
  332. }
  333. /*
  334. * The idea is to set a period in which each task runs once.
  335. *
  336. * When there are too many tasks (sysctl_sched_nr_latency) we have to stretch
  337. * this period because otherwise the slices get too small.
  338. *
  339. * p = (nr <= nl) ? l : l*nr/nl
  340. */
  341. static u64 __sched_period(unsigned long nr_running)
  342. {
  343. u64 period = sysctl_sched_latency;
  344. unsigned long nr_latency = sched_nr_latency;
  345. if (unlikely(nr_running > nr_latency)) {
  346. period = sysctl_sched_min_granularity;
  347. period *= nr_running;
  348. }
  349. return period;
  350. }
  351. /*
  352. * We calculate the wall-time slice from the period by taking a part
  353. * proportional to the weight.
  354. *
  355. * s = p*P[w/rw]
  356. */
  357. static u64 sched_slice(struct cfs_rq *cfs_rq, struct sched_entity *se)
  358. {
  359. u64 slice = __sched_period(cfs_rq->nr_running + !se->on_rq);
  360. for_each_sched_entity(se) {
  361. struct load_weight *load;
  362. struct load_weight lw;
  363. cfs_rq = cfs_rq_of(se);
  364. load = &cfs_rq->load;
  365. if (unlikely(!se->on_rq)) {
  366. lw = cfs_rq->load;
  367. update_load_add(&lw, se->load.weight);
  368. load = &lw;
  369. }
  370. slice = calc_delta_mine(slice, se->load.weight, load);
  371. }
  372. return slice;
  373. }
  374. /*
  375. * We calculate the vruntime slice of a to be inserted task
  376. *
  377. * vs = s/w
  378. */
  379. static u64 sched_vslice(struct cfs_rq *cfs_rq, struct sched_entity *se)
  380. {
  381. return calc_delta_fair(sched_slice(cfs_rq, se), se);
  382. }
  383. /*
  384. * Update the current task's runtime statistics. Skip current tasks that
  385. * are not in our scheduling class.
  386. */
  387. static inline void
  388. __update_curr(struct cfs_rq *cfs_rq, struct sched_entity *curr,
  389. unsigned long delta_exec)
  390. {
  391. unsigned long delta_exec_weighted;
  392. schedstat_set(curr->exec_max, max((u64)delta_exec, curr->exec_max));
  393. curr->sum_exec_runtime += delta_exec;
  394. schedstat_add(cfs_rq, exec_clock, delta_exec);
  395. delta_exec_weighted = calc_delta_fair(delta_exec, curr);
  396. curr->vruntime += delta_exec_weighted;
  397. update_min_vruntime(cfs_rq);
  398. }
  399. static void update_curr(struct cfs_rq *cfs_rq)
  400. {
  401. struct sched_entity *curr = cfs_rq->curr;
  402. u64 now = rq_of(cfs_rq)->clock;
  403. unsigned long delta_exec;
  404. if (unlikely(!curr))
  405. return;
  406. /*
  407. * Get the amount of time the current task was running
  408. * since the last time we changed load (this cannot
  409. * overflow on 32 bits):
  410. */
  411. delta_exec = (unsigned long)(now - curr->exec_start);
  412. if (!delta_exec)
  413. return;
  414. __update_curr(cfs_rq, curr, delta_exec);
  415. curr->exec_start = now;
  416. if (entity_is_task(curr)) {
  417. struct task_struct *curtask = task_of(curr);
  418. cpuacct_charge(curtask, delta_exec);
  419. account_group_exec_runtime(curtask, delta_exec);
  420. }
  421. }
  422. static inline void
  423. update_stats_wait_start(struct cfs_rq *cfs_rq, struct sched_entity *se)
  424. {
  425. schedstat_set(se->wait_start, rq_of(cfs_rq)->clock);
  426. }
  427. /*
  428. * Task is being enqueued - update stats:
  429. */
  430. static void update_stats_enqueue(struct cfs_rq *cfs_rq, struct sched_entity *se)
  431. {
  432. /*
  433. * Are we enqueueing a waiting task? (for current tasks
  434. * a dequeue/enqueue event is a NOP)
  435. */
  436. if (se != cfs_rq->curr)
  437. update_stats_wait_start(cfs_rq, se);
  438. }
  439. static void
  440. update_stats_wait_end(struct cfs_rq *cfs_rq, struct sched_entity *se)
  441. {
  442. schedstat_set(se->wait_max, max(se->wait_max,
  443. rq_of(cfs_rq)->clock - se->wait_start));
  444. schedstat_set(se->wait_count, se->wait_count + 1);
  445. schedstat_set(se->wait_sum, se->wait_sum +
  446. rq_of(cfs_rq)->clock - se->wait_start);
  447. #ifdef CONFIG_SCHEDSTATS
  448. if (entity_is_task(se)) {
  449. trace_sched_stat_wait(task_of(se),
  450. rq_of(cfs_rq)->clock - se->wait_start);
  451. }
  452. #endif
  453. schedstat_set(se->wait_start, 0);
  454. }
  455. static inline void
  456. update_stats_dequeue(struct cfs_rq *cfs_rq, struct sched_entity *se)
  457. {
  458. /*
  459. * Mark the end of the wait period if dequeueing a
  460. * waiting task:
  461. */
  462. if (se != cfs_rq->curr)
  463. update_stats_wait_end(cfs_rq, se);
  464. }
  465. /*
  466. * We are picking a new current task - update its stats:
  467. */
  468. static inline void
  469. update_stats_curr_start(struct cfs_rq *cfs_rq, struct sched_entity *se)
  470. {
  471. /*
  472. * We are starting a new run period:
  473. */
  474. se->exec_start = rq_of(cfs_rq)->clock;
  475. }
  476. /**************************************************
  477. * Scheduling class queueing methods:
  478. */
  479. #if defined CONFIG_SMP && defined CONFIG_FAIR_GROUP_SCHED
  480. static void
  481. add_cfs_task_weight(struct cfs_rq *cfs_rq, unsigned long weight)
  482. {
  483. cfs_rq->task_weight += weight;
  484. }
  485. #else
  486. static inline void
  487. add_cfs_task_weight(struct cfs_rq *cfs_rq, unsigned long weight)
  488. {
  489. }
  490. #endif
  491. static void
  492. account_entity_enqueue(struct cfs_rq *cfs_rq, struct sched_entity *se)
  493. {
  494. update_load_add(&cfs_rq->load, se->load.weight);
  495. if (!parent_entity(se))
  496. inc_cpu_load(rq_of(cfs_rq), se->load.weight);
  497. if (entity_is_task(se)) {
  498. add_cfs_task_weight(cfs_rq, se->load.weight);
  499. list_add(&se->group_node, &cfs_rq->tasks);
  500. }
  501. cfs_rq->nr_running++;
  502. se->on_rq = 1;
  503. }
  504. static void
  505. account_entity_dequeue(struct cfs_rq *cfs_rq, struct sched_entity *se)
  506. {
  507. update_load_sub(&cfs_rq->load, se->load.weight);
  508. if (!parent_entity(se))
  509. dec_cpu_load(rq_of(cfs_rq), se->load.weight);
  510. if (entity_is_task(se)) {
  511. add_cfs_task_weight(cfs_rq, -se->load.weight);
  512. list_del_init(&se->group_node);
  513. }
  514. cfs_rq->nr_running--;
  515. se->on_rq = 0;
  516. }
  517. static void enqueue_sleeper(struct cfs_rq *cfs_rq, struct sched_entity *se)
  518. {
  519. #ifdef CONFIG_SCHEDSTATS
  520. struct task_struct *tsk = NULL;
  521. if (entity_is_task(se))
  522. tsk = task_of(se);
  523. if (se->sleep_start) {
  524. u64 delta = rq_of(cfs_rq)->clock - se->sleep_start;
  525. if ((s64)delta < 0)
  526. delta = 0;
  527. if (unlikely(delta > se->sleep_max))
  528. se->sleep_max = delta;
  529. se->sleep_start = 0;
  530. se->sum_sleep_runtime += delta;
  531. if (tsk) {
  532. account_scheduler_latency(tsk, delta >> 10, 1);
  533. trace_sched_stat_sleep(tsk, delta);
  534. }
  535. }
  536. if (se->block_start) {
  537. u64 delta = rq_of(cfs_rq)->clock - se->block_start;
  538. if ((s64)delta < 0)
  539. delta = 0;
  540. if (unlikely(delta > se->block_max))
  541. se->block_max = delta;
  542. se->block_start = 0;
  543. se->sum_sleep_runtime += delta;
  544. if (tsk) {
  545. if (tsk->in_iowait) {
  546. se->iowait_sum += delta;
  547. se->iowait_count++;
  548. trace_sched_stat_iowait(tsk, delta);
  549. }
  550. /*
  551. * Blocking time is in units of nanosecs, so shift by
  552. * 20 to get a milliseconds-range estimation of the
  553. * amount of time that the task spent sleeping:
  554. */
  555. if (unlikely(prof_on == SLEEP_PROFILING)) {
  556. profile_hits(SLEEP_PROFILING,
  557. (void *)get_wchan(tsk),
  558. delta >> 20);
  559. }
  560. account_scheduler_latency(tsk, delta >> 10, 0);
  561. }
  562. }
  563. #endif
  564. }
  565. static void check_spread(struct cfs_rq *cfs_rq, struct sched_entity *se)
  566. {
  567. #ifdef CONFIG_SCHED_DEBUG
  568. s64 d = se->vruntime - cfs_rq->min_vruntime;
  569. if (d < 0)
  570. d = -d;
  571. if (d > 3*sysctl_sched_latency)
  572. schedstat_inc(cfs_rq, nr_spread_over);
  573. #endif
  574. }
  575. static void
  576. place_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int initial)
  577. {
  578. u64 vruntime = cfs_rq->min_vruntime;
  579. /*
  580. * The 'current' period is already promised to the current tasks,
  581. * however the extra weight of the new task will slow them down a
  582. * little, place the new task so that it fits in the slot that
  583. * stays open at the end.
  584. */
  585. if (initial && sched_feat(START_DEBIT))
  586. vruntime += sched_vslice(cfs_rq, se);
  587. if (!initial) {
  588. /* sleeps upto a single latency don't count. */
  589. if (sched_feat(NEW_FAIR_SLEEPERS)) {
  590. unsigned long thresh = sysctl_sched_latency;
  591. /*
  592. * Convert the sleeper threshold into virtual time.
  593. * SCHED_IDLE is a special sub-class. We care about
  594. * fairness only relative to other SCHED_IDLE tasks,
  595. * all of which have the same weight.
  596. */
  597. if (sched_feat(NORMALIZED_SLEEPER) &&
  598. (!entity_is_task(se) ||
  599. task_of(se)->policy != SCHED_IDLE))
  600. thresh = calc_delta_fair(thresh, se);
  601. vruntime -= thresh;
  602. }
  603. }
  604. /* ensure we never gain time by being placed backwards. */
  605. vruntime = max_vruntime(se->vruntime, vruntime);
  606. se->vruntime = vruntime;
  607. }
  608. static void
  609. enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int wakeup)
  610. {
  611. /*
  612. * Update run-time statistics of the 'current'.
  613. */
  614. update_curr(cfs_rq);
  615. account_entity_enqueue(cfs_rq, se);
  616. if (wakeup) {
  617. place_entity(cfs_rq, se, 0);
  618. enqueue_sleeper(cfs_rq, se);
  619. }
  620. update_stats_enqueue(cfs_rq, se);
  621. check_spread(cfs_rq, se);
  622. if (se != cfs_rq->curr)
  623. __enqueue_entity(cfs_rq, se);
  624. }
  625. static void __clear_buddies(struct cfs_rq *cfs_rq, struct sched_entity *se)
  626. {
  627. if (cfs_rq->last == se)
  628. cfs_rq->last = NULL;
  629. if (cfs_rq->next == se)
  630. cfs_rq->next = NULL;
  631. }
  632. static void clear_buddies(struct cfs_rq *cfs_rq, struct sched_entity *se)
  633. {
  634. for_each_sched_entity(se)
  635. __clear_buddies(cfs_rq_of(se), se);
  636. }
  637. static void
  638. dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int sleep)
  639. {
  640. /*
  641. * Update run-time statistics of the 'current'.
  642. */
  643. update_curr(cfs_rq);
  644. update_stats_dequeue(cfs_rq, se);
  645. if (sleep) {
  646. #ifdef CONFIG_SCHEDSTATS
  647. if (entity_is_task(se)) {
  648. struct task_struct *tsk = task_of(se);
  649. if (tsk->state & TASK_INTERRUPTIBLE)
  650. se->sleep_start = rq_of(cfs_rq)->clock;
  651. if (tsk->state & TASK_UNINTERRUPTIBLE)
  652. se->block_start = rq_of(cfs_rq)->clock;
  653. }
  654. #endif
  655. }
  656. clear_buddies(cfs_rq, se);
  657. if (se != cfs_rq->curr)
  658. __dequeue_entity(cfs_rq, se);
  659. account_entity_dequeue(cfs_rq, se);
  660. update_min_vruntime(cfs_rq);
  661. }
  662. /*
  663. * Preempt the current task with a newly woken task if needed:
  664. */
  665. static void
  666. check_preempt_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr)
  667. {
  668. unsigned long ideal_runtime, delta_exec;
  669. ideal_runtime = sched_slice(cfs_rq, curr);
  670. delta_exec = curr->sum_exec_runtime - curr->prev_sum_exec_runtime;
  671. if (delta_exec > ideal_runtime) {
  672. resched_task(rq_of(cfs_rq)->curr);
  673. /*
  674. * The current task ran long enough, ensure it doesn't get
  675. * re-elected due to buddy favours.
  676. */
  677. clear_buddies(cfs_rq, curr);
  678. }
  679. }
  680. static void
  681. set_next_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
  682. {
  683. /* 'current' is not kept within the tree. */
  684. if (se->on_rq) {
  685. /*
  686. * Any task has to be enqueued before it get to execute on
  687. * a CPU. So account for the time it spent waiting on the
  688. * runqueue.
  689. */
  690. update_stats_wait_end(cfs_rq, se);
  691. __dequeue_entity(cfs_rq, se);
  692. }
  693. update_stats_curr_start(cfs_rq, se);
  694. cfs_rq->curr = se;
  695. #ifdef CONFIG_SCHEDSTATS
  696. /*
  697. * Track our maximum slice length, if the CPU's load is at
  698. * least twice that of our own weight (i.e. dont track it
  699. * when there are only lesser-weight tasks around):
  700. */
  701. if (rq_of(cfs_rq)->load.weight >= 2*se->load.weight) {
  702. se->slice_max = max(se->slice_max,
  703. se->sum_exec_runtime - se->prev_sum_exec_runtime);
  704. }
  705. #endif
  706. se->prev_sum_exec_runtime = se->sum_exec_runtime;
  707. }
  708. static int
  709. wakeup_preempt_entity(struct sched_entity *curr, struct sched_entity *se);
  710. static struct sched_entity *pick_next_entity(struct cfs_rq *cfs_rq)
  711. {
  712. struct sched_entity *se = __pick_next_entity(cfs_rq);
  713. if (cfs_rq->next && wakeup_preempt_entity(cfs_rq->next, se) < 1)
  714. return cfs_rq->next;
  715. if (cfs_rq->last && wakeup_preempt_entity(cfs_rq->last, se) < 1)
  716. return cfs_rq->last;
  717. return se;
  718. }
  719. static void put_prev_entity(struct cfs_rq *cfs_rq, struct sched_entity *prev)
  720. {
  721. /*
  722. * If still on the runqueue then deactivate_task()
  723. * was not called and update_curr() has to be done:
  724. */
  725. if (prev->on_rq)
  726. update_curr(cfs_rq);
  727. check_spread(cfs_rq, prev);
  728. if (prev->on_rq) {
  729. update_stats_wait_start(cfs_rq, prev);
  730. /* Put 'current' back into the tree. */
  731. __enqueue_entity(cfs_rq, prev);
  732. }
  733. cfs_rq->curr = NULL;
  734. }
  735. static void
  736. entity_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr, int queued)
  737. {
  738. /*
  739. * Update run-time statistics of the 'current'.
  740. */
  741. update_curr(cfs_rq);
  742. #ifdef CONFIG_SCHED_HRTICK
  743. /*
  744. * queued ticks are scheduled to match the slice, so don't bother
  745. * validating it and just reschedule.
  746. */
  747. if (queued) {
  748. resched_task(rq_of(cfs_rq)->curr);
  749. return;
  750. }
  751. /*
  752. * don't let the period tick interfere with the hrtick preemption
  753. */
  754. if (!sched_feat(DOUBLE_TICK) &&
  755. hrtimer_active(&rq_of(cfs_rq)->hrtick_timer))
  756. return;
  757. #endif
  758. if (cfs_rq->nr_running > 1 || !sched_feat(WAKEUP_PREEMPT))
  759. check_preempt_tick(cfs_rq, curr);
  760. }
  761. /**************************************************
  762. * CFS operations on tasks:
  763. */
  764. #ifdef CONFIG_SCHED_HRTICK
  765. static void hrtick_start_fair(struct rq *rq, struct task_struct *p)
  766. {
  767. struct sched_entity *se = &p->se;
  768. struct cfs_rq *cfs_rq = cfs_rq_of(se);
  769. WARN_ON(task_rq(p) != rq);
  770. if (hrtick_enabled(rq) && cfs_rq->nr_running > 1) {
  771. u64 slice = sched_slice(cfs_rq, se);
  772. u64 ran = se->sum_exec_runtime - se->prev_sum_exec_runtime;
  773. s64 delta = slice - ran;
  774. if (delta < 0) {
  775. if (rq->curr == p)
  776. resched_task(p);
  777. return;
  778. }
  779. /*
  780. * Don't schedule slices shorter than 10000ns, that just
  781. * doesn't make sense. Rely on vruntime for fairness.
  782. */
  783. if (rq->curr != p)
  784. delta = max_t(s64, 10000LL, delta);
  785. hrtick_start(rq, delta);
  786. }
  787. }
  788. /*
  789. * called from enqueue/dequeue and updates the hrtick when the
  790. * current task is from our class and nr_running is low enough
  791. * to matter.
  792. */
  793. static void hrtick_update(struct rq *rq)
  794. {
  795. struct task_struct *curr = rq->curr;
  796. if (curr->sched_class != &fair_sched_class)
  797. return;
  798. if (cfs_rq_of(&curr->se)->nr_running < sched_nr_latency)
  799. hrtick_start_fair(rq, curr);
  800. }
  801. #else /* !CONFIG_SCHED_HRTICK */
  802. static inline void
  803. hrtick_start_fair(struct rq *rq, struct task_struct *p)
  804. {
  805. }
  806. static inline void hrtick_update(struct rq *rq)
  807. {
  808. }
  809. #endif
  810. /*
  811. * The enqueue_task method is called before nr_running is
  812. * increased. Here we update the fair scheduling stats and
  813. * then put the task into the rbtree:
  814. */
  815. static void enqueue_task_fair(struct rq *rq, struct task_struct *p, int wakeup)
  816. {
  817. struct cfs_rq *cfs_rq;
  818. struct sched_entity *se = &p->se;
  819. for_each_sched_entity(se) {
  820. if (se->on_rq)
  821. break;
  822. cfs_rq = cfs_rq_of(se);
  823. enqueue_entity(cfs_rq, se, wakeup);
  824. wakeup = 1;
  825. }
  826. hrtick_update(rq);
  827. }
  828. /*
  829. * The dequeue_task method is called before nr_running is
  830. * decreased. We remove the task from the rbtree and
  831. * update the fair scheduling stats:
  832. */
  833. static void dequeue_task_fair(struct rq *rq, struct task_struct *p, int sleep)
  834. {
  835. struct cfs_rq *cfs_rq;
  836. struct sched_entity *se = &p->se;
  837. for_each_sched_entity(se) {
  838. cfs_rq = cfs_rq_of(se);
  839. dequeue_entity(cfs_rq, se, sleep);
  840. /* Don't dequeue parent if it has other entities besides us */
  841. if (cfs_rq->load.weight)
  842. break;
  843. sleep = 1;
  844. }
  845. hrtick_update(rq);
  846. }
  847. /*
  848. * sched_yield() support is very simple - we dequeue and enqueue.
  849. *
  850. * If compat_yield is turned on then we requeue to the end of the tree.
  851. */
  852. static void yield_task_fair(struct rq *rq)
  853. {
  854. struct task_struct *curr = rq->curr;
  855. struct cfs_rq *cfs_rq = task_cfs_rq(curr);
  856. struct sched_entity *rightmost, *se = &curr->se;
  857. /*
  858. * Are we the only task in the tree?
  859. */
  860. if (unlikely(cfs_rq->nr_running == 1))
  861. return;
  862. clear_buddies(cfs_rq, se);
  863. if (likely(!sysctl_sched_compat_yield) && curr->policy != SCHED_BATCH) {
  864. update_rq_clock(rq);
  865. /*
  866. * Update run-time statistics of the 'current'.
  867. */
  868. update_curr(cfs_rq);
  869. return;
  870. }
  871. /*
  872. * Find the rightmost entry in the rbtree:
  873. */
  874. rightmost = __pick_last_entity(cfs_rq);
  875. /*
  876. * Already in the rightmost position?
  877. */
  878. if (unlikely(!rightmost || entity_before(rightmost, se)))
  879. return;
  880. /*
  881. * Minimally necessary key value to be last in the tree:
  882. * Upon rescheduling, sched_class::put_prev_task() will place
  883. * 'current' within the tree based on its new key value.
  884. */
  885. se->vruntime = rightmost->vruntime + 1;
  886. }
  887. /*
  888. * wake_idle() will wake a task on an idle cpu if task->cpu is
  889. * not idle and an idle cpu is available. The span of cpus to
  890. * search starts with cpus closest then further out as needed,
  891. * so we always favor a closer, idle cpu.
  892. * Domains may include CPUs that are not usable for migration,
  893. * hence we need to mask them out (rq->rd->online)
  894. *
  895. * Returns the CPU we should wake onto.
  896. */
  897. #if defined(ARCH_HAS_SCHED_WAKE_IDLE)
  898. #define cpu_rd_active(cpu, rq) cpumask_test_cpu(cpu, rq->rd->online)
  899. static int wake_idle(int cpu, struct task_struct *p)
  900. {
  901. struct sched_domain *sd;
  902. int i;
  903. unsigned int chosen_wakeup_cpu;
  904. int this_cpu;
  905. struct rq *task_rq = task_rq(p);
  906. /*
  907. * At POWERSAVINGS_BALANCE_WAKEUP level, if both this_cpu and prev_cpu
  908. * are idle and this is not a kernel thread and this task's affinity
  909. * allows it to be moved to preferred cpu, then just move!
  910. */
  911. this_cpu = smp_processor_id();
  912. chosen_wakeup_cpu =
  913. cpu_rq(this_cpu)->rd->sched_mc_preferred_wakeup_cpu;
  914. if (sched_mc_power_savings >= POWERSAVINGS_BALANCE_WAKEUP &&
  915. idle_cpu(cpu) && idle_cpu(this_cpu) &&
  916. p->mm && !(p->flags & PF_KTHREAD) &&
  917. cpu_isset(chosen_wakeup_cpu, p->cpus_allowed))
  918. return chosen_wakeup_cpu;
  919. /*
  920. * If it is idle, then it is the best cpu to run this task.
  921. *
  922. * This cpu is also the best, if it has more than one task already.
  923. * Siblings must be also busy(in most cases) as they didn't already
  924. * pickup the extra load from this cpu and hence we need not check
  925. * sibling runqueue info. This will avoid the checks and cache miss
  926. * penalities associated with that.
  927. */
  928. if (idle_cpu(cpu) || cpu_rq(cpu)->cfs.nr_running > 1)
  929. return cpu;
  930. for_each_domain(cpu, sd) {
  931. if ((sd->flags & SD_WAKE_IDLE)
  932. || ((sd->flags & SD_WAKE_IDLE_FAR)
  933. && !task_hot(p, task_rq->clock, sd))) {
  934. for_each_cpu_and(i, sched_domain_span(sd),
  935. &p->cpus_allowed) {
  936. if (cpu_rd_active(i, task_rq) && idle_cpu(i)) {
  937. if (i != task_cpu(p)) {
  938. schedstat_inc(p,
  939. se.nr_wakeups_idle);
  940. }
  941. return i;
  942. }
  943. }
  944. } else {
  945. break;
  946. }
  947. }
  948. return cpu;
  949. }
  950. #else /* !ARCH_HAS_SCHED_WAKE_IDLE*/
  951. static inline int wake_idle(int cpu, struct task_struct *p)
  952. {
  953. return cpu;
  954. }
  955. #endif
  956. #ifdef CONFIG_SMP
  957. #ifdef CONFIG_FAIR_GROUP_SCHED
  958. /*
  959. * effective_load() calculates the load change as seen from the root_task_group
  960. *
  961. * Adding load to a group doesn't make a group heavier, but can cause movement
  962. * of group shares between cpus. Assuming the shares were perfectly aligned one
  963. * can calculate the shift in shares.
  964. *
  965. * The problem is that perfectly aligning the shares is rather expensive, hence
  966. * we try to avoid doing that too often - see update_shares(), which ratelimits
  967. * this change.
  968. *
  969. * We compensate this by not only taking the current delta into account, but
  970. * also considering the delta between when the shares were last adjusted and
  971. * now.
  972. *
  973. * We still saw a performance dip, some tracing learned us that between
  974. * cgroup:/ and cgroup:/foo balancing the number of affine wakeups increased
  975. * significantly. Therefore try to bias the error in direction of failing
  976. * the affine wakeup.
  977. *
  978. */
  979. static long effective_load(struct task_group *tg, int cpu,
  980. long wl, long wg)
  981. {
  982. struct sched_entity *se = tg->se[cpu];
  983. if (!tg->parent)
  984. return wl;
  985. /*
  986. * By not taking the decrease of shares on the other cpu into
  987. * account our error leans towards reducing the affine wakeups.
  988. */
  989. if (!wl && sched_feat(ASYM_EFF_LOAD))
  990. return wl;
  991. for_each_sched_entity(se) {
  992. long S, rw, s, a, b;
  993. long more_w;
  994. /*
  995. * Instead of using this increment, also add the difference
  996. * between when the shares were last updated and now.
  997. */
  998. more_w = se->my_q->load.weight - se->my_q->rq_weight;
  999. wl += more_w;
  1000. wg += more_w;
  1001. S = se->my_q->tg->shares;
  1002. s = se->my_q->shares;
  1003. rw = se->my_q->rq_weight;
  1004. a = S*(rw + wl);
  1005. b = S*rw + s*wg;
  1006. wl = s*(a-b);
  1007. if (likely(b))
  1008. wl /= b;
  1009. /*
  1010. * Assume the group is already running and will
  1011. * thus already be accounted for in the weight.
  1012. *
  1013. * That is, moving shares between CPUs, does not
  1014. * alter the group weight.
  1015. */
  1016. wg = 0;
  1017. }
  1018. return wl;
  1019. }
  1020. #else
  1021. static inline unsigned long effective_load(struct task_group *tg, int cpu,
  1022. unsigned long wl, unsigned long wg)
  1023. {
  1024. return wl;
  1025. }
  1026. #endif
  1027. static int
  1028. wake_affine(struct sched_domain *this_sd, struct rq *this_rq,
  1029. struct task_struct *p, int prev_cpu, int this_cpu, int sync,
  1030. int idx, unsigned long load, unsigned long this_load,
  1031. unsigned int imbalance)
  1032. {
  1033. struct task_struct *curr = this_rq->curr;
  1034. struct task_group *tg;
  1035. unsigned long tl = this_load;
  1036. unsigned long tl_per_task;
  1037. unsigned long weight;
  1038. int balanced;
  1039. if (!(this_sd->flags & SD_WAKE_AFFINE) || !sched_feat(AFFINE_WAKEUPS))
  1040. return 0;
  1041. if (sync && (curr->se.avg_overlap > sysctl_sched_migration_cost ||
  1042. p->se.avg_overlap > sysctl_sched_migration_cost))
  1043. sync = 0;
  1044. /*
  1045. * If sync wakeup then subtract the (maximum possible)
  1046. * effect of the currently running task from the load
  1047. * of the current CPU:
  1048. */
  1049. if (sync) {
  1050. tg = task_group(current);
  1051. weight = current->se.load.weight;
  1052. tl += effective_load(tg, this_cpu, -weight, -weight);
  1053. load += effective_load(tg, prev_cpu, 0, -weight);
  1054. }
  1055. tg = task_group(p);
  1056. weight = p->se.load.weight;
  1057. /*
  1058. * In low-load situations, where prev_cpu is idle and this_cpu is idle
  1059. * due to the sync cause above having dropped tl to 0, we'll always have
  1060. * an imbalance, but there's really nothing you can do about that, so
  1061. * that's good too.
  1062. *
  1063. * Otherwise check if either cpus are near enough in load to allow this
  1064. * task to be woken on this_cpu.
  1065. */
  1066. balanced = !tl ||
  1067. 100*(tl + effective_load(tg, this_cpu, weight, weight)) <=
  1068. imbalance*(load + effective_load(tg, prev_cpu, 0, weight));
  1069. /*
  1070. * If the currently running task will sleep within
  1071. * a reasonable amount of time then attract this newly
  1072. * woken task:
  1073. */
  1074. if (sync && balanced)
  1075. return 1;
  1076. schedstat_inc(p, se.nr_wakeups_affine_attempts);
  1077. tl_per_task = cpu_avg_load_per_task(this_cpu);
  1078. if (balanced || (tl <= load && tl + target_load(prev_cpu, idx) <=
  1079. tl_per_task)) {
  1080. /*
  1081. * This domain has SD_WAKE_AFFINE and
  1082. * p is cache cold in this domain, and
  1083. * there is no bad imbalance.
  1084. */
  1085. schedstat_inc(this_sd, ttwu_move_affine);
  1086. schedstat_inc(p, se.nr_wakeups_affine);
  1087. return 1;
  1088. }
  1089. return 0;
  1090. }
  1091. static int select_task_rq_fair(struct task_struct *p, int sync)
  1092. {
  1093. struct sched_domain *sd, *this_sd = NULL;
  1094. int prev_cpu, this_cpu, new_cpu;
  1095. unsigned long load, this_load;
  1096. struct rq *this_rq;
  1097. unsigned int imbalance;
  1098. int idx;
  1099. prev_cpu = task_cpu(p);
  1100. this_cpu = smp_processor_id();
  1101. this_rq = cpu_rq(this_cpu);
  1102. new_cpu = prev_cpu;
  1103. /*
  1104. * 'this_sd' is the first domain that both
  1105. * this_cpu and prev_cpu are present in:
  1106. */
  1107. for_each_domain(this_cpu, sd) {
  1108. if (cpumask_test_cpu(prev_cpu, sched_domain_span(sd))) {
  1109. this_sd = sd;
  1110. break;
  1111. }
  1112. }
  1113. if (unlikely(!cpumask_test_cpu(this_cpu, &p->cpus_allowed)))
  1114. goto out;
  1115. /*
  1116. * Check for affine wakeup and passive balancing possibilities.
  1117. */
  1118. if (!this_sd)
  1119. goto out;
  1120. idx = this_sd->wake_idx;
  1121. imbalance = 100 + (this_sd->imbalance_pct - 100) / 2;
  1122. load = source_load(prev_cpu, idx);
  1123. this_load = target_load(this_cpu, idx);
  1124. if (wake_affine(this_sd, this_rq, p, prev_cpu, this_cpu, sync, idx,
  1125. load, this_load, imbalance))
  1126. return this_cpu;
  1127. /*
  1128. * Start passive balancing when half the imbalance_pct
  1129. * limit is reached.
  1130. */
  1131. if (this_sd->flags & SD_WAKE_BALANCE) {
  1132. if (imbalance*this_load <= 100*load) {
  1133. schedstat_inc(this_sd, ttwu_move_balance);
  1134. schedstat_inc(p, se.nr_wakeups_passive);
  1135. return this_cpu;
  1136. }
  1137. }
  1138. out:
  1139. return wake_idle(new_cpu, p);
  1140. }
  1141. #endif /* CONFIG_SMP */
  1142. /*
  1143. * Adaptive granularity
  1144. *
  1145. * se->avg_wakeup gives the average time a task runs until it does a wakeup,
  1146. * with the limit of wakeup_gran -- when it never does a wakeup.
  1147. *
  1148. * So the smaller avg_wakeup is the faster we want this task to preempt,
  1149. * but we don't want to treat the preemptee unfairly and therefore allow it
  1150. * to run for at least the amount of time we'd like to run.
  1151. *
  1152. * NOTE: we use 2*avg_wakeup to increase the probability of actually doing one
  1153. *
  1154. * NOTE: we use *nr_running to scale with load, this nicely matches the
  1155. * degrading latency on load.
  1156. */
  1157. static unsigned long
  1158. adaptive_gran(struct sched_entity *curr, struct sched_entity *se)
  1159. {
  1160. u64 this_run = curr->sum_exec_runtime - curr->prev_sum_exec_runtime;
  1161. u64 expected_wakeup = 2*se->avg_wakeup * cfs_rq_of(se)->nr_running;
  1162. u64 gran = 0;
  1163. if (this_run < expected_wakeup)
  1164. gran = expected_wakeup - this_run;
  1165. return min_t(s64, gran, sysctl_sched_wakeup_granularity);
  1166. }
  1167. static unsigned long
  1168. wakeup_gran(struct sched_entity *curr, struct sched_entity *se)
  1169. {
  1170. unsigned long gran = sysctl_sched_wakeup_granularity;
  1171. if (cfs_rq_of(curr)->curr && sched_feat(ADAPTIVE_GRAN))
  1172. gran = adaptive_gran(curr, se);
  1173. /*
  1174. * Since its curr running now, convert the gran from real-time
  1175. * to virtual-time in his units.
  1176. */
  1177. if (sched_feat(ASYM_GRAN)) {
  1178. /*
  1179. * By using 'se' instead of 'curr' we penalize light tasks, so
  1180. * they get preempted easier. That is, if 'se' < 'curr' then
  1181. * the resulting gran will be larger, therefore penalizing the
  1182. * lighter, if otoh 'se' > 'curr' then the resulting gran will
  1183. * be smaller, again penalizing the lighter task.
  1184. *
  1185. * This is especially important for buddies when the leftmost
  1186. * task is higher priority than the buddy.
  1187. */
  1188. if (unlikely(se->load.weight != NICE_0_LOAD))
  1189. gran = calc_delta_fair(gran, se);
  1190. } else {
  1191. if (unlikely(curr->load.weight != NICE_0_LOAD))
  1192. gran = calc_delta_fair(gran, curr);
  1193. }
  1194. return gran;
  1195. }
  1196. /*
  1197. * Should 'se' preempt 'curr'.
  1198. *
  1199. * |s1
  1200. * |s2
  1201. * |s3
  1202. * g
  1203. * |<--->|c
  1204. *
  1205. * w(c, s1) = -1
  1206. * w(c, s2) = 0
  1207. * w(c, s3) = 1
  1208. *
  1209. */
  1210. static int
  1211. wakeup_preempt_entity(struct sched_entity *curr, struct sched_entity *se)
  1212. {
  1213. s64 gran, vdiff = curr->vruntime - se->vruntime;
  1214. if (vdiff <= 0)
  1215. return -1;
  1216. gran = wakeup_gran(curr, se);
  1217. if (vdiff > gran)
  1218. return 1;
  1219. return 0;
  1220. }
  1221. static void set_last_buddy(struct sched_entity *se)
  1222. {
  1223. if (likely(task_of(se)->policy != SCHED_IDLE)) {
  1224. for_each_sched_entity(se)
  1225. cfs_rq_of(se)->last = se;
  1226. }
  1227. }
  1228. static void set_next_buddy(struct sched_entity *se)
  1229. {
  1230. if (likely(task_of(se)->policy != SCHED_IDLE)) {
  1231. for_each_sched_entity(se)
  1232. cfs_rq_of(se)->next = se;
  1233. }
  1234. }
  1235. /*
  1236. * Preempt the current task with a newly woken task if needed:
  1237. */
  1238. static void check_preempt_wakeup(struct rq *rq, struct task_struct *p, int sync)
  1239. {
  1240. struct task_struct *curr = rq->curr;
  1241. struct sched_entity *se = &curr->se, *pse = &p->se;
  1242. struct cfs_rq *cfs_rq = task_cfs_rq(curr);
  1243. update_curr(cfs_rq);
  1244. if (unlikely(rt_prio(p->prio))) {
  1245. resched_task(curr);
  1246. return;
  1247. }
  1248. if (unlikely(p->sched_class != &fair_sched_class))
  1249. return;
  1250. if (unlikely(se == pse))
  1251. return;
  1252. /*
  1253. * Only set the backward buddy when the current task is still on the
  1254. * rq. This can happen when a wakeup gets interleaved with schedule on
  1255. * the ->pre_schedule() or idle_balance() point, either of which can
  1256. * drop the rq lock.
  1257. *
  1258. * Also, during early boot the idle thread is in the fair class, for
  1259. * obvious reasons its a bad idea to schedule back to the idle thread.
  1260. */
  1261. if (sched_feat(LAST_BUDDY) && likely(se->on_rq && curr != rq->idle))
  1262. set_last_buddy(se);
  1263. set_next_buddy(pse);
  1264. /*
  1265. * We can come here with TIF_NEED_RESCHED already set from new task
  1266. * wake up path.
  1267. */
  1268. if (test_tsk_need_resched(curr))
  1269. return;
  1270. /*
  1271. * Batch and idle tasks do not preempt (their preemption is driven by
  1272. * the tick):
  1273. */
  1274. if (unlikely(p->policy != SCHED_NORMAL))
  1275. return;
  1276. /* Idle tasks are by definition preempted by everybody. */
  1277. if (unlikely(curr->policy == SCHED_IDLE)) {
  1278. resched_task(curr);
  1279. return;
  1280. }
  1281. if (!sched_feat(WAKEUP_PREEMPT))
  1282. return;
  1283. if (sched_feat(WAKEUP_OVERLAP) && (sync ||
  1284. (se->avg_overlap < sysctl_sched_migration_cost &&
  1285. pse->avg_overlap < sysctl_sched_migration_cost))) {
  1286. resched_task(curr);
  1287. return;
  1288. }
  1289. find_matching_se(&se, &pse);
  1290. BUG_ON(!pse);
  1291. if (wakeup_preempt_entity(se, pse) == 1)
  1292. resched_task(curr);
  1293. }
  1294. static struct task_struct *pick_next_task_fair(struct rq *rq)
  1295. {
  1296. struct task_struct *p;
  1297. struct cfs_rq *cfs_rq = &rq->cfs;
  1298. struct sched_entity *se;
  1299. if (unlikely(!cfs_rq->nr_running))
  1300. return NULL;
  1301. do {
  1302. se = pick_next_entity(cfs_rq);
  1303. /*
  1304. * If se was a buddy, clear it so that it will have to earn
  1305. * the favour again.
  1306. */
  1307. __clear_buddies(cfs_rq, se);
  1308. set_next_entity(cfs_rq, se);
  1309. cfs_rq = group_cfs_rq(se);
  1310. } while (cfs_rq);
  1311. p = task_of(se);
  1312. hrtick_start_fair(rq, p);
  1313. return p;
  1314. }
  1315. /*
  1316. * Account for a descheduled task:
  1317. */
  1318. static void put_prev_task_fair(struct rq *rq, struct task_struct *prev)
  1319. {
  1320. struct sched_entity *se = &prev->se;
  1321. struct cfs_rq *cfs_rq;
  1322. for_each_sched_entity(se) {
  1323. cfs_rq = cfs_rq_of(se);
  1324. put_prev_entity(cfs_rq, se);
  1325. }
  1326. }
  1327. #ifdef CONFIG_SMP
  1328. /**************************************************
  1329. * Fair scheduling class load-balancing methods:
  1330. */
  1331. /*
  1332. * Load-balancing iterator. Note: while the runqueue stays locked
  1333. * during the whole iteration, the current task might be
  1334. * dequeued so the iterator has to be dequeue-safe. Here we
  1335. * achieve that by always pre-iterating before returning
  1336. * the current task:
  1337. */
  1338. static struct task_struct *
  1339. __load_balance_iterator(struct cfs_rq *cfs_rq, struct list_head *next)
  1340. {
  1341. struct task_struct *p = NULL;
  1342. struct sched_entity *se;
  1343. if (next == &cfs_rq->tasks)
  1344. return NULL;
  1345. se = list_entry(next, struct sched_entity, group_node);
  1346. p = task_of(se);
  1347. cfs_rq->balance_iterator = next->next;
  1348. return p;
  1349. }
  1350. static struct task_struct *load_balance_start_fair(void *arg)
  1351. {
  1352. struct cfs_rq *cfs_rq = arg;
  1353. return __load_balance_iterator(cfs_rq, cfs_rq->tasks.next);
  1354. }
  1355. static struct task_struct *load_balance_next_fair(void *arg)
  1356. {
  1357. struct cfs_rq *cfs_rq = arg;
  1358. return __load_balance_iterator(cfs_rq, cfs_rq->balance_iterator);
  1359. }
  1360. static unsigned long
  1361. __load_balance_fair(struct rq *this_rq, int this_cpu, struct rq *busiest,
  1362. unsigned long max_load_move, struct sched_domain *sd,
  1363. enum cpu_idle_type idle, int *all_pinned, int *this_best_prio,
  1364. struct cfs_rq *cfs_rq)
  1365. {
  1366. struct rq_iterator cfs_rq_iterator;
  1367. cfs_rq_iterator.start = load_balance_start_fair;
  1368. cfs_rq_iterator.next = load_balance_next_fair;
  1369. cfs_rq_iterator.arg = cfs_rq;
  1370. return balance_tasks(this_rq, this_cpu, busiest,
  1371. max_load_move, sd, idle, all_pinned,
  1372. this_best_prio, &cfs_rq_iterator);
  1373. }
  1374. #ifdef CONFIG_FAIR_GROUP_SCHED
  1375. static unsigned long
  1376. load_balance_fair(struct rq *this_rq, int this_cpu, struct rq *busiest,
  1377. unsigned long max_load_move,
  1378. struct sched_domain *sd, enum cpu_idle_type idle,
  1379. int *all_pinned, int *this_best_prio)
  1380. {
  1381. long rem_load_move = max_load_move;
  1382. int busiest_cpu = cpu_of(busiest);
  1383. struct task_group *tg;
  1384. rcu_read_lock();
  1385. update_h_load(busiest_cpu);
  1386. list_for_each_entry_rcu(tg, &task_groups, list) {
  1387. struct cfs_rq *busiest_cfs_rq = tg->cfs_rq[busiest_cpu];
  1388. unsigned long busiest_h_load = busiest_cfs_rq->h_load;
  1389. unsigned long busiest_weight = busiest_cfs_rq->load.weight;
  1390. u64 rem_load, moved_load;
  1391. /*
  1392. * empty group
  1393. */
  1394. if (!busiest_cfs_rq->task_weight)
  1395. continue;
  1396. rem_load = (u64)rem_load_move * busiest_weight;
  1397. rem_load = div_u64(rem_load, busiest_h_load + 1);
  1398. moved_load = __load_balance_fair(this_rq, this_cpu, busiest,
  1399. rem_load, sd, idle, all_pinned, this_best_prio,
  1400. tg->cfs_rq[busiest_cpu]);
  1401. if (!moved_load)
  1402. continue;
  1403. moved_load *= busiest_h_load;
  1404. moved_load = div_u64(moved_load, busiest_weight + 1);
  1405. rem_load_move -= moved_load;
  1406. if (rem_load_move < 0)
  1407. break;
  1408. }
  1409. rcu_read_unlock();
  1410. return max_load_move - rem_load_move;
  1411. }
  1412. #else
  1413. static unsigned long
  1414. load_balance_fair(struct rq *this_rq, int this_cpu, struct rq *busiest,
  1415. unsigned long max_load_move,
  1416. struct sched_domain *sd, enum cpu_idle_type idle,
  1417. int *all_pinned, int *this_best_prio)
  1418. {
  1419. return __load_balance_fair(this_rq, this_cpu, busiest,
  1420. max_load_move, sd, idle, all_pinned,
  1421. this_best_prio, &busiest->cfs);
  1422. }
  1423. #endif
  1424. static int
  1425. move_one_task_fair(struct rq *this_rq, int this_cpu, struct rq *busiest,
  1426. struct sched_domain *sd, enum cpu_idle_type idle)
  1427. {
  1428. struct cfs_rq *busy_cfs_rq;
  1429. struct rq_iterator cfs_rq_iterator;
  1430. cfs_rq_iterator.start = load_balance_start_fair;
  1431. cfs_rq_iterator.next = load_balance_next_fair;
  1432. for_each_leaf_cfs_rq(busiest, busy_cfs_rq) {
  1433. /*
  1434. * pass busy_cfs_rq argument into
  1435. * load_balance_[start|next]_fair iterators
  1436. */
  1437. cfs_rq_iterator.arg = busy_cfs_rq;
  1438. if (iter_move_one_task(this_rq, this_cpu, busiest, sd, idle,
  1439. &cfs_rq_iterator))
  1440. return 1;
  1441. }
  1442. return 0;
  1443. }
  1444. #endif /* CONFIG_SMP */
  1445. /*
  1446. * scheduler tick hitting a task of our scheduling class:
  1447. */
  1448. static void task_tick_fair(struct rq *rq, struct task_struct *curr, int queued)
  1449. {
  1450. struct cfs_rq *cfs_rq;
  1451. struct sched_entity *se = &curr->se;
  1452. for_each_sched_entity(se) {
  1453. cfs_rq = cfs_rq_of(se);
  1454. entity_tick(cfs_rq, se, queued);
  1455. }
  1456. }
  1457. /*
  1458. * Share the fairness runtime between parent and child, thus the
  1459. * total amount of pressure for CPU stays equal - new tasks
  1460. * get a chance to run but frequent forkers are not allowed to
  1461. * monopolize the CPU. Note: the parent runqueue is locked,
  1462. * the child is not running yet.
  1463. */
  1464. static void task_new_fair(struct rq *rq, struct task_struct *p)
  1465. {
  1466. struct cfs_rq *cfs_rq = task_cfs_rq(p);
  1467. struct sched_entity *se = &p->se, *curr = cfs_rq->curr;
  1468. int this_cpu = smp_processor_id();
  1469. sched_info_queued(p);
  1470. update_curr(cfs_rq);
  1471. if (curr)
  1472. se->vruntime = curr->vruntime;
  1473. place_entity(cfs_rq, se, 1);
  1474. /* 'curr' will be NULL if the child belongs to a different group */
  1475. if (sysctl_sched_child_runs_first && this_cpu == task_cpu(p) &&
  1476. curr && entity_before(curr, se)) {
  1477. /*
  1478. * Upon rescheduling, sched_class::put_prev_task() will place
  1479. * 'current' within the tree based on its new key value.
  1480. */
  1481. swap(curr->vruntime, se->vruntime);
  1482. resched_task(rq->curr);
  1483. }
  1484. enqueue_task_fair(rq, p, 0);
  1485. }
  1486. /*
  1487. * Priority of the task has changed. Check to see if we preempt
  1488. * the current task.
  1489. */
  1490. static void prio_changed_fair(struct rq *rq, struct task_struct *p,
  1491. int oldprio, int running)
  1492. {
  1493. /*
  1494. * Reschedule if we are currently running on this runqueue and
  1495. * our priority decreased, or if we are not currently running on
  1496. * this runqueue and our priority is higher than the current's
  1497. */
  1498. if (running) {
  1499. if (p->prio > oldprio)
  1500. resched_task(rq->curr);
  1501. } else
  1502. check_preempt_curr(rq, p, 0);
  1503. }
  1504. /*
  1505. * We switched to the sched_fair class.
  1506. */
  1507. static void switched_to_fair(struct rq *rq, struct task_struct *p,
  1508. int running)
  1509. {
  1510. /*
  1511. * We were most likely switched from sched_rt, so
  1512. * kick off the schedule if running, otherwise just see
  1513. * if we can still preempt the current task.
  1514. */
  1515. if (running)
  1516. resched_task(rq->curr);
  1517. else
  1518. check_preempt_curr(rq, p, 0);
  1519. }
  1520. /* Account for a task changing its policy or group.
  1521. *
  1522. * This routine is mostly called to set cfs_rq->curr field when a task
  1523. * migrates between groups/classes.
  1524. */
  1525. static void set_curr_task_fair(struct rq *rq)
  1526. {
  1527. struct sched_entity *se = &rq->curr->se;
  1528. for_each_sched_entity(se)
  1529. set_next_entity(cfs_rq_of(se), se);
  1530. }
  1531. #ifdef CONFIG_FAIR_GROUP_SCHED
  1532. static void moved_group_fair(struct task_struct *p)
  1533. {
  1534. struct cfs_rq *cfs_rq = task_cfs_rq(p);
  1535. update_curr(cfs_rq);
  1536. place_entity(cfs_rq, &p->se, 1);
  1537. }
  1538. #endif
  1539. /*
  1540. * All the scheduling class methods:
  1541. */
  1542. static const struct sched_class fair_sched_class = {
  1543. .next = &idle_sched_class,
  1544. .enqueue_task = enqueue_task_fair,
  1545. .dequeue_task = dequeue_task_fair,
  1546. .yield_task = yield_task_fair,
  1547. .check_preempt_curr = check_preempt_wakeup,
  1548. .pick_next_task = pick_next_task_fair,
  1549. .put_prev_task = put_prev_task_fair,
  1550. #ifdef CONFIG_SMP
  1551. .select_task_rq = select_task_rq_fair,
  1552. .load_balance = load_balance_fair,
  1553. .move_one_task = move_one_task_fair,
  1554. #endif
  1555. .set_curr_task = set_curr_task_fair,
  1556. .task_tick = task_tick_fair,
  1557. .task_new = task_new_fair,
  1558. .prio_changed = prio_changed_fair,
  1559. .switched_to = switched_to_fair,
  1560. #ifdef CONFIG_FAIR_GROUP_SCHED
  1561. .moved_group = moved_group_fair,
  1562. #endif
  1563. };
  1564. #ifdef CONFIG_SCHED_DEBUG
  1565. static void print_cfs_stats(struct seq_file *m, int cpu)
  1566. {
  1567. struct cfs_rq *cfs_rq;
  1568. rcu_read_lock();
  1569. for_each_leaf_cfs_rq(cpu_rq(cpu), cfs_rq)
  1570. print_cfs_rq(m, cpu, cfs_rq);
  1571. rcu_read_unlock();
  1572. }
  1573. #endif