sched_fair.c 27 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990991992993994995996997998999100010011002100310041005100610071008100910101011101210131014101510161017101810191020102110221023102410251026102710281029103010311032103310341035103610371038103910401041104210431044104510461047104810491050105110521053105410551056105710581059106010611062106310641065106610671068106910701071107210731074107510761077107810791080108110821083108410851086108710881089109010911092109310941095109610971098109911001101110211031104110511061107
  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. /*
  20. * Preemption granularity:
  21. * (default: 2 msec, units: nanoseconds)
  22. *
  23. * NOTE: this granularity value is not the same as the concept of
  24. * 'timeslice length' - timeslices in CFS will typically be somewhat
  25. * larger than this value. (to see the precise effective timeslice
  26. * length of your workload, run vmstat and monitor the context-switches
  27. * field)
  28. *
  29. * On SMP systems the value of this is multiplied by the log2 of the
  30. * number of CPUs. (i.e. factor 2x on 2-way systems, 3x on 4-way
  31. * systems, 4x on 8-way systems, 5x on 16-way systems, etc.)
  32. */
  33. unsigned int sysctl_sched_granularity __read_mostly = 2000000000ULL/HZ;
  34. /*
  35. * SCHED_BATCH wake-up granularity.
  36. * (default: 10 msec, units: nanoseconds)
  37. *
  38. * This option delays the preemption effects of decoupled workloads
  39. * and reduces their over-scheduling. Synchronous workloads will still
  40. * have immediate wakeup/sleep latencies.
  41. */
  42. unsigned int sysctl_sched_batch_wakeup_granularity __read_mostly =
  43. 10000000000ULL/HZ;
  44. /*
  45. * SCHED_OTHER wake-up granularity.
  46. * (default: 1 msec, units: nanoseconds)
  47. *
  48. * This option delays the preemption effects of decoupled workloads
  49. * and reduces their over-scheduling. Synchronous workloads will still
  50. * have immediate wakeup/sleep latencies.
  51. */
  52. unsigned int sysctl_sched_wakeup_granularity __read_mostly = 1000000000ULL/HZ;
  53. unsigned int sysctl_sched_stat_granularity __read_mostly;
  54. /*
  55. * Initialized in sched_init_granularity():
  56. */
  57. unsigned int sysctl_sched_runtime_limit __read_mostly;
  58. /*
  59. * Debugging: various feature bits
  60. */
  61. enum {
  62. SCHED_FEAT_FAIR_SLEEPERS = 1,
  63. SCHED_FEAT_SLEEPER_AVG = 2,
  64. SCHED_FEAT_SLEEPER_LOAD_AVG = 4,
  65. SCHED_FEAT_PRECISE_CPU_LOAD = 8,
  66. SCHED_FEAT_START_DEBIT = 16,
  67. SCHED_FEAT_SKIP_INITIAL = 32,
  68. };
  69. unsigned int sysctl_sched_features __read_mostly =
  70. SCHED_FEAT_FAIR_SLEEPERS *1 |
  71. SCHED_FEAT_SLEEPER_AVG *1 |
  72. SCHED_FEAT_SLEEPER_LOAD_AVG *1 |
  73. SCHED_FEAT_PRECISE_CPU_LOAD *1 |
  74. SCHED_FEAT_START_DEBIT *1 |
  75. SCHED_FEAT_SKIP_INITIAL *0;
  76. extern struct sched_class fair_sched_class;
  77. /**************************************************************
  78. * CFS operations on generic schedulable entities:
  79. */
  80. #ifdef CONFIG_FAIR_GROUP_SCHED
  81. /* cpu runqueue to which this cfs_rq is attached */
  82. static inline struct rq *rq_of(struct cfs_rq *cfs_rq)
  83. {
  84. return cfs_rq->rq;
  85. }
  86. /* currently running entity (if any) on this cfs_rq */
  87. static inline struct sched_entity *cfs_rq_curr(struct cfs_rq *cfs_rq)
  88. {
  89. return cfs_rq->curr;
  90. }
  91. /* An entity is a task if it doesn't "own" a runqueue */
  92. #define entity_is_task(se) (!se->my_q)
  93. static inline void
  94. set_cfs_rq_curr(struct cfs_rq *cfs_rq, struct sched_entity *se)
  95. {
  96. cfs_rq->curr = se;
  97. }
  98. #else /* CONFIG_FAIR_GROUP_SCHED */
  99. static inline struct rq *rq_of(struct cfs_rq *cfs_rq)
  100. {
  101. return container_of(cfs_rq, struct rq, cfs);
  102. }
  103. static inline struct sched_entity *cfs_rq_curr(struct cfs_rq *cfs_rq)
  104. {
  105. struct rq *rq = rq_of(cfs_rq);
  106. if (unlikely(rq->curr->sched_class != &fair_sched_class))
  107. return NULL;
  108. return &rq->curr->se;
  109. }
  110. #define entity_is_task(se) 1
  111. static inline void
  112. set_cfs_rq_curr(struct cfs_rq *cfs_rq, struct sched_entity *se) { }
  113. #endif /* CONFIG_FAIR_GROUP_SCHED */
  114. static inline struct task_struct *task_of(struct sched_entity *se)
  115. {
  116. return container_of(se, struct task_struct, se);
  117. }
  118. /**************************************************************
  119. * Scheduling class tree data structure manipulation methods:
  120. */
  121. /*
  122. * Enqueue an entity into the rb-tree:
  123. */
  124. static inline void
  125. __enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
  126. {
  127. struct rb_node **link = &cfs_rq->tasks_timeline.rb_node;
  128. struct rb_node *parent = NULL;
  129. struct sched_entity *entry;
  130. s64 key = se->fair_key;
  131. int leftmost = 1;
  132. /*
  133. * Find the right place in the rbtree:
  134. */
  135. while (*link) {
  136. parent = *link;
  137. entry = rb_entry(parent, struct sched_entity, run_node);
  138. /*
  139. * We dont care about collisions. Nodes with
  140. * the same key stay together.
  141. */
  142. if (key - entry->fair_key < 0) {
  143. link = &parent->rb_left;
  144. } else {
  145. link = &parent->rb_right;
  146. leftmost = 0;
  147. }
  148. }
  149. /*
  150. * Maintain a cache of leftmost tree entries (it is frequently
  151. * used):
  152. */
  153. if (leftmost)
  154. cfs_rq->rb_leftmost = &se->run_node;
  155. rb_link_node(&se->run_node, parent, link);
  156. rb_insert_color(&se->run_node, &cfs_rq->tasks_timeline);
  157. update_load_add(&cfs_rq->load, se->load.weight);
  158. cfs_rq->nr_running++;
  159. se->on_rq = 1;
  160. }
  161. static inline void
  162. __dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
  163. {
  164. if (cfs_rq->rb_leftmost == &se->run_node)
  165. cfs_rq->rb_leftmost = rb_next(&se->run_node);
  166. rb_erase(&se->run_node, &cfs_rq->tasks_timeline);
  167. update_load_sub(&cfs_rq->load, se->load.weight);
  168. cfs_rq->nr_running--;
  169. se->on_rq = 0;
  170. }
  171. static inline struct rb_node * first_fair(struct cfs_rq *cfs_rq)
  172. {
  173. return cfs_rq->rb_leftmost;
  174. }
  175. static struct sched_entity * __pick_next_entity(struct cfs_rq *cfs_rq)
  176. {
  177. return rb_entry(first_fair(cfs_rq), struct sched_entity, run_node);
  178. }
  179. /**************************************************************
  180. * Scheduling class statistics methods:
  181. */
  182. /*
  183. * We rescale the rescheduling granularity of tasks according to their
  184. * nice level, but only linearly, not exponentially:
  185. */
  186. static long
  187. niced_granularity(struct sched_entity *curr, unsigned long granularity)
  188. {
  189. u64 tmp;
  190. /*
  191. * Negative nice levels get the same granularity as nice-0:
  192. */
  193. if (likely(curr->load.weight >= NICE_0_LOAD))
  194. return granularity;
  195. /*
  196. * Positive nice level tasks get linearly finer
  197. * granularity:
  198. */
  199. tmp = curr->load.weight * (u64)granularity;
  200. /*
  201. * It will always fit into 'long':
  202. */
  203. return (long) (tmp >> NICE_0_SHIFT);
  204. }
  205. static inline void
  206. limit_wait_runtime(struct cfs_rq *cfs_rq, struct sched_entity *se)
  207. {
  208. long limit = sysctl_sched_runtime_limit;
  209. /*
  210. * Niced tasks have the same history dynamic range as
  211. * non-niced tasks:
  212. */
  213. if (unlikely(se->wait_runtime > limit)) {
  214. se->wait_runtime = limit;
  215. schedstat_inc(se, wait_runtime_overruns);
  216. schedstat_inc(cfs_rq, wait_runtime_overruns);
  217. }
  218. if (unlikely(se->wait_runtime < -limit)) {
  219. se->wait_runtime = -limit;
  220. schedstat_inc(se, wait_runtime_underruns);
  221. schedstat_inc(cfs_rq, wait_runtime_underruns);
  222. }
  223. }
  224. static inline void
  225. __add_wait_runtime(struct cfs_rq *cfs_rq, struct sched_entity *se, long delta)
  226. {
  227. se->wait_runtime += delta;
  228. schedstat_add(se, sum_wait_runtime, delta);
  229. limit_wait_runtime(cfs_rq, se);
  230. }
  231. static void
  232. add_wait_runtime(struct cfs_rq *cfs_rq, struct sched_entity *se, long delta)
  233. {
  234. schedstat_add(cfs_rq, wait_runtime, -se->wait_runtime);
  235. __add_wait_runtime(cfs_rq, se, delta);
  236. schedstat_add(cfs_rq, wait_runtime, se->wait_runtime);
  237. }
  238. /*
  239. * Update the current task's runtime statistics. Skip current tasks that
  240. * are not in our scheduling class.
  241. */
  242. static inline void
  243. __update_curr(struct cfs_rq *cfs_rq, struct sched_entity *curr, u64 now)
  244. {
  245. unsigned long delta, delta_exec, delta_fair;
  246. long delta_mine;
  247. struct load_weight *lw = &cfs_rq->load;
  248. unsigned long load = lw->weight;
  249. if (unlikely(!load))
  250. return;
  251. delta_exec = curr->delta_exec;
  252. #ifdef CONFIG_SCHEDSTATS
  253. if (unlikely(delta_exec > curr->exec_max))
  254. curr->exec_max = delta_exec;
  255. #endif
  256. curr->sum_exec_runtime += delta_exec;
  257. cfs_rq->exec_clock += delta_exec;
  258. delta_fair = calc_delta_fair(delta_exec, lw);
  259. delta_mine = calc_delta_mine(delta_exec, curr->load.weight, lw);
  260. if (cfs_rq->sleeper_bonus > sysctl_sched_stat_granularity) {
  261. delta = calc_delta_mine(cfs_rq->sleeper_bonus,
  262. curr->load.weight, lw);
  263. if (unlikely(delta > cfs_rq->sleeper_bonus))
  264. delta = cfs_rq->sleeper_bonus;
  265. cfs_rq->sleeper_bonus -= delta;
  266. delta_mine -= delta;
  267. }
  268. cfs_rq->fair_clock += delta_fair;
  269. /*
  270. * We executed delta_exec amount of time on the CPU,
  271. * but we were only entitled to delta_mine amount of
  272. * time during that period (if nr_running == 1 then
  273. * the two values are equal)
  274. * [Note: delta_mine - delta_exec is negative]:
  275. */
  276. add_wait_runtime(cfs_rq, curr, delta_mine - delta_exec);
  277. }
  278. static void update_curr(struct cfs_rq *cfs_rq, u64 now)
  279. {
  280. struct sched_entity *curr = cfs_rq_curr(cfs_rq);
  281. unsigned long delta_exec;
  282. if (unlikely(!curr))
  283. return;
  284. /*
  285. * Get the amount of time the current task was running
  286. * since the last time we changed load (this cannot
  287. * overflow on 32 bits):
  288. */
  289. delta_exec = (unsigned long)(now - curr->exec_start);
  290. curr->delta_exec += delta_exec;
  291. if (unlikely(curr->delta_exec > sysctl_sched_stat_granularity)) {
  292. __update_curr(cfs_rq, curr, now);
  293. curr->delta_exec = 0;
  294. }
  295. curr->exec_start = now;
  296. }
  297. static inline void
  298. update_stats_wait_start(struct cfs_rq *cfs_rq, struct sched_entity *se, u64 now)
  299. {
  300. se->wait_start_fair = cfs_rq->fair_clock;
  301. se->wait_start = now;
  302. }
  303. /*
  304. * Task is being enqueued - update stats:
  305. */
  306. static void
  307. update_stats_enqueue(struct cfs_rq *cfs_rq, struct sched_entity *se, u64 now)
  308. {
  309. s64 key;
  310. /*
  311. * Are we enqueueing a waiting task? (for current tasks
  312. * a dequeue/enqueue event is a NOP)
  313. */
  314. if (se != cfs_rq_curr(cfs_rq))
  315. update_stats_wait_start(cfs_rq, se, now);
  316. /*
  317. * Update the key:
  318. */
  319. key = cfs_rq->fair_clock;
  320. /*
  321. * Optimize the common nice 0 case:
  322. */
  323. if (likely(se->load.weight == NICE_0_LOAD)) {
  324. key -= se->wait_runtime;
  325. } else {
  326. u64 tmp;
  327. if (se->wait_runtime < 0) {
  328. tmp = -se->wait_runtime;
  329. key += (tmp * se->load.inv_weight) >>
  330. (WMULT_SHIFT - NICE_0_SHIFT);
  331. } else {
  332. tmp = se->wait_runtime;
  333. key -= (tmp * se->load.weight) >> NICE_0_SHIFT;
  334. }
  335. }
  336. se->fair_key = key;
  337. }
  338. /*
  339. * Note: must be called with a freshly updated rq->fair_clock.
  340. */
  341. static inline void
  342. __update_stats_wait_end(struct cfs_rq *cfs_rq, struct sched_entity *se, u64 now)
  343. {
  344. unsigned long delta_fair = se->delta_fair_run;
  345. #ifdef CONFIG_SCHEDSTATS
  346. {
  347. s64 delta_wait = now - se->wait_start;
  348. if (unlikely(delta_wait > se->wait_max))
  349. se->wait_max = delta_wait;
  350. }
  351. #endif
  352. if (unlikely(se->load.weight != NICE_0_LOAD))
  353. delta_fair = (u64)delta_fair * se->load.weight >> NICE_0_SHIFT;
  354. add_wait_runtime(cfs_rq, se, delta_fair);
  355. }
  356. static void
  357. update_stats_wait_end(struct cfs_rq *cfs_rq, struct sched_entity *se, u64 now)
  358. {
  359. unsigned long delta_fair;
  360. delta_fair = (unsigned long)min((u64)(2*sysctl_sched_runtime_limit),
  361. (u64)(cfs_rq->fair_clock - se->wait_start_fair));
  362. se->delta_fair_run += delta_fair;
  363. if (unlikely(abs(se->delta_fair_run) >=
  364. sysctl_sched_stat_granularity)) {
  365. __update_stats_wait_end(cfs_rq, se, now);
  366. se->delta_fair_run = 0;
  367. }
  368. se->wait_start_fair = 0;
  369. se->wait_start = 0;
  370. }
  371. static inline void
  372. update_stats_dequeue(struct cfs_rq *cfs_rq, struct sched_entity *se, u64 now)
  373. {
  374. update_curr(cfs_rq, now);
  375. /*
  376. * Mark the end of the wait period if dequeueing a
  377. * waiting task:
  378. */
  379. if (se != cfs_rq_curr(cfs_rq))
  380. update_stats_wait_end(cfs_rq, se, now);
  381. }
  382. /*
  383. * We are picking a new current task - update its stats:
  384. */
  385. static inline void
  386. update_stats_curr_start(struct cfs_rq *cfs_rq, struct sched_entity *se, u64 now)
  387. {
  388. /*
  389. * We are starting a new run period:
  390. */
  391. se->exec_start = now;
  392. }
  393. /*
  394. * We are descheduling a task - update its stats:
  395. */
  396. static inline void
  397. update_stats_curr_end(struct cfs_rq *cfs_rq, struct sched_entity *se, u64 now)
  398. {
  399. se->exec_start = 0;
  400. }
  401. /**************************************************
  402. * Scheduling class queueing methods:
  403. */
  404. static void
  405. __enqueue_sleeper(struct cfs_rq *cfs_rq, struct sched_entity *se, u64 now)
  406. {
  407. unsigned long load = cfs_rq->load.weight, delta_fair;
  408. long prev_runtime;
  409. if (sysctl_sched_features & SCHED_FEAT_SLEEPER_LOAD_AVG)
  410. load = rq_of(cfs_rq)->cpu_load[2];
  411. delta_fair = se->delta_fair_sleep;
  412. /*
  413. * Fix up delta_fair with the effect of us running
  414. * during the whole sleep period:
  415. */
  416. if (sysctl_sched_features & SCHED_FEAT_SLEEPER_AVG)
  417. delta_fair = div64_likely32((u64)delta_fair * load,
  418. load + se->load.weight);
  419. if (unlikely(se->load.weight != NICE_0_LOAD))
  420. delta_fair = (u64)delta_fair * se->load.weight >> NICE_0_SHIFT;
  421. prev_runtime = se->wait_runtime;
  422. __add_wait_runtime(cfs_rq, se, delta_fair);
  423. delta_fair = se->wait_runtime - prev_runtime;
  424. /*
  425. * Track the amount of bonus we've given to sleepers:
  426. */
  427. cfs_rq->sleeper_bonus += delta_fair;
  428. schedstat_add(cfs_rq, wait_runtime, se->wait_runtime);
  429. }
  430. static void
  431. enqueue_sleeper(struct cfs_rq *cfs_rq, struct sched_entity *se, u64 now)
  432. {
  433. struct task_struct *tsk = task_of(se);
  434. unsigned long delta_fair;
  435. if ((entity_is_task(se) && tsk->policy == SCHED_BATCH) ||
  436. !(sysctl_sched_features & SCHED_FEAT_FAIR_SLEEPERS))
  437. return;
  438. delta_fair = (unsigned long)min((u64)(2*sysctl_sched_runtime_limit),
  439. (u64)(cfs_rq->fair_clock - se->sleep_start_fair));
  440. se->delta_fair_sleep += delta_fair;
  441. if (unlikely(abs(se->delta_fair_sleep) >=
  442. sysctl_sched_stat_granularity)) {
  443. __enqueue_sleeper(cfs_rq, se, now);
  444. se->delta_fair_sleep = 0;
  445. }
  446. se->sleep_start_fair = 0;
  447. #ifdef CONFIG_SCHEDSTATS
  448. if (se->sleep_start) {
  449. u64 delta = now - se->sleep_start;
  450. if ((s64)delta < 0)
  451. delta = 0;
  452. if (unlikely(delta > se->sleep_max))
  453. se->sleep_max = delta;
  454. se->sleep_start = 0;
  455. se->sum_sleep_runtime += delta;
  456. }
  457. if (se->block_start) {
  458. u64 delta = now - se->block_start;
  459. if ((s64)delta < 0)
  460. delta = 0;
  461. if (unlikely(delta > se->block_max))
  462. se->block_max = delta;
  463. se->block_start = 0;
  464. se->sum_sleep_runtime += delta;
  465. }
  466. #endif
  467. }
  468. static void
  469. enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se,
  470. int wakeup, u64 now)
  471. {
  472. /*
  473. * Update the fair clock.
  474. */
  475. update_curr(cfs_rq, now);
  476. if (wakeup)
  477. enqueue_sleeper(cfs_rq, se, now);
  478. update_stats_enqueue(cfs_rq, se, now);
  479. __enqueue_entity(cfs_rq, se);
  480. }
  481. static void
  482. dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se,
  483. int sleep, u64 now)
  484. {
  485. update_stats_dequeue(cfs_rq, se, now);
  486. if (sleep) {
  487. se->sleep_start_fair = cfs_rq->fair_clock;
  488. #ifdef CONFIG_SCHEDSTATS
  489. if (entity_is_task(se)) {
  490. struct task_struct *tsk = task_of(se);
  491. if (tsk->state & TASK_INTERRUPTIBLE)
  492. se->sleep_start = now;
  493. if (tsk->state & TASK_UNINTERRUPTIBLE)
  494. se->block_start = now;
  495. }
  496. cfs_rq->wait_runtime -= se->wait_runtime;
  497. #endif
  498. }
  499. __dequeue_entity(cfs_rq, se);
  500. }
  501. /*
  502. * Preempt the current task with a newly woken task if needed:
  503. */
  504. static void
  505. __check_preempt_curr_fair(struct cfs_rq *cfs_rq, struct sched_entity *se,
  506. struct sched_entity *curr, unsigned long granularity)
  507. {
  508. s64 __delta = curr->fair_key - se->fair_key;
  509. /*
  510. * Take scheduling granularity into account - do not
  511. * preempt the current task unless the best task has
  512. * a larger than sched_granularity fairness advantage:
  513. */
  514. if (__delta > niced_granularity(curr, granularity))
  515. resched_task(rq_of(cfs_rq)->curr);
  516. }
  517. static inline void
  518. set_next_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, u64 now)
  519. {
  520. /*
  521. * Any task has to be enqueued before it get to execute on
  522. * a CPU. So account for the time it spent waiting on the
  523. * runqueue. (note, here we rely on pick_next_task() having
  524. * done a put_prev_task_fair() shortly before this, which
  525. * updated rq->fair_clock - used by update_stats_wait_end())
  526. */
  527. update_stats_wait_end(cfs_rq, se, now);
  528. update_stats_curr_start(cfs_rq, se, now);
  529. set_cfs_rq_curr(cfs_rq, se);
  530. }
  531. static struct sched_entity *pick_next_entity(struct cfs_rq *cfs_rq, u64 now)
  532. {
  533. struct sched_entity *se = __pick_next_entity(cfs_rq);
  534. set_next_entity(cfs_rq, se, now);
  535. return se;
  536. }
  537. static void
  538. put_prev_entity(struct cfs_rq *cfs_rq, struct sched_entity *prev, u64 now)
  539. {
  540. /*
  541. * If still on the runqueue then deactivate_task()
  542. * was not called and update_curr() has to be done:
  543. */
  544. if (prev->on_rq)
  545. update_curr(cfs_rq, now);
  546. update_stats_curr_end(cfs_rq, prev, now);
  547. if (prev->on_rq)
  548. update_stats_wait_start(cfs_rq, prev, now);
  549. set_cfs_rq_curr(cfs_rq, NULL);
  550. }
  551. static void entity_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr)
  552. {
  553. struct rq *rq = rq_of(cfs_rq);
  554. struct sched_entity *next;
  555. u64 now = __rq_clock(rq);
  556. /*
  557. * Dequeue and enqueue the task to update its
  558. * position within the tree:
  559. */
  560. dequeue_entity(cfs_rq, curr, 0, now);
  561. enqueue_entity(cfs_rq, curr, 0, now);
  562. /*
  563. * Reschedule if another task tops the current one.
  564. */
  565. next = __pick_next_entity(cfs_rq);
  566. if (next == curr)
  567. return;
  568. __check_preempt_curr_fair(cfs_rq, next, curr, sysctl_sched_granularity);
  569. }
  570. /**************************************************
  571. * CFS operations on tasks:
  572. */
  573. #ifdef CONFIG_FAIR_GROUP_SCHED
  574. /* Walk up scheduling entities hierarchy */
  575. #define for_each_sched_entity(se) \
  576. for (; se; se = se->parent)
  577. static inline struct cfs_rq *task_cfs_rq(struct task_struct *p)
  578. {
  579. return p->se.cfs_rq;
  580. }
  581. /* runqueue on which this entity is (to be) queued */
  582. static inline struct cfs_rq *cfs_rq_of(struct sched_entity *se)
  583. {
  584. return se->cfs_rq;
  585. }
  586. /* runqueue "owned" by this group */
  587. static inline struct cfs_rq *group_cfs_rq(struct sched_entity *grp)
  588. {
  589. return grp->my_q;
  590. }
  591. /* Given a group's cfs_rq on one cpu, return its corresponding cfs_rq on
  592. * another cpu ('this_cpu')
  593. */
  594. static inline struct cfs_rq *cpu_cfs_rq(struct cfs_rq *cfs_rq, int this_cpu)
  595. {
  596. /* A later patch will take group into account */
  597. return &cpu_rq(this_cpu)->cfs;
  598. }
  599. /* Iterate thr' all leaf cfs_rq's on a runqueue */
  600. #define for_each_leaf_cfs_rq(rq, cfs_rq) \
  601. list_for_each_entry(cfs_rq, &rq->leaf_cfs_rq_list, leaf_cfs_rq_list)
  602. /* Do the two (enqueued) tasks belong to the same group ? */
  603. static inline int is_same_group(struct task_struct *curr, struct task_struct *p)
  604. {
  605. if (curr->se.cfs_rq == p->se.cfs_rq)
  606. return 1;
  607. return 0;
  608. }
  609. #else /* CONFIG_FAIR_GROUP_SCHED */
  610. #define for_each_sched_entity(se) \
  611. for (; se; se = NULL)
  612. static inline struct cfs_rq *task_cfs_rq(struct task_struct *p)
  613. {
  614. return &task_rq(p)->cfs;
  615. }
  616. static inline struct cfs_rq *cfs_rq_of(struct sched_entity *se)
  617. {
  618. struct task_struct *p = task_of(se);
  619. struct rq *rq = task_rq(p);
  620. return &rq->cfs;
  621. }
  622. /* runqueue "owned" by this group */
  623. static inline struct cfs_rq *group_cfs_rq(struct sched_entity *grp)
  624. {
  625. return NULL;
  626. }
  627. static inline struct cfs_rq *cpu_cfs_rq(struct cfs_rq *cfs_rq, int this_cpu)
  628. {
  629. return &cpu_rq(this_cpu)->cfs;
  630. }
  631. #define for_each_leaf_cfs_rq(rq, cfs_rq) \
  632. for (cfs_rq = &rq->cfs; cfs_rq; cfs_rq = NULL)
  633. static inline int is_same_group(struct task_struct *curr, struct task_struct *p)
  634. {
  635. return 1;
  636. }
  637. #endif /* CONFIG_FAIR_GROUP_SCHED */
  638. /*
  639. * The enqueue_task method is called before nr_running is
  640. * increased. Here we update the fair scheduling stats and
  641. * then put the task into the rbtree:
  642. */
  643. static void
  644. enqueue_task_fair(struct rq *rq, struct task_struct *p, int wakeup, u64 now)
  645. {
  646. struct cfs_rq *cfs_rq;
  647. struct sched_entity *se = &p->se;
  648. for_each_sched_entity(se) {
  649. if (se->on_rq)
  650. break;
  651. cfs_rq = cfs_rq_of(se);
  652. enqueue_entity(cfs_rq, se, wakeup, now);
  653. }
  654. }
  655. /*
  656. * The dequeue_task method is called before nr_running is
  657. * decreased. We remove the task from the rbtree and
  658. * update the fair scheduling stats:
  659. */
  660. static void
  661. dequeue_task_fair(struct rq *rq, struct task_struct *p, int sleep, u64 now)
  662. {
  663. struct cfs_rq *cfs_rq;
  664. struct sched_entity *se = &p->se;
  665. for_each_sched_entity(se) {
  666. cfs_rq = cfs_rq_of(se);
  667. dequeue_entity(cfs_rq, se, sleep, now);
  668. /* Don't dequeue parent if it has other entities besides us */
  669. if (cfs_rq->load.weight)
  670. break;
  671. }
  672. }
  673. /*
  674. * sched_yield() support is very simple - we dequeue and enqueue
  675. */
  676. static void yield_task_fair(struct rq *rq, struct task_struct *p)
  677. {
  678. struct cfs_rq *cfs_rq = task_cfs_rq(p);
  679. u64 now = __rq_clock(rq);
  680. /*
  681. * Dequeue and enqueue the task to update its
  682. * position within the tree:
  683. */
  684. dequeue_entity(cfs_rq, &p->se, 0, now);
  685. enqueue_entity(cfs_rq, &p->se, 0, now);
  686. }
  687. /*
  688. * Preempt the current task with a newly woken task if needed:
  689. */
  690. static void check_preempt_curr_fair(struct rq *rq, struct task_struct *p)
  691. {
  692. struct task_struct *curr = rq->curr;
  693. struct cfs_rq *cfs_rq = task_cfs_rq(curr);
  694. unsigned long gran;
  695. if (unlikely(rt_prio(p->prio))) {
  696. update_curr(cfs_rq, rq_clock(rq));
  697. resched_task(curr);
  698. return;
  699. }
  700. gran = sysctl_sched_wakeup_granularity;
  701. /*
  702. * Batch tasks prefer throughput over latency:
  703. */
  704. if (unlikely(p->policy == SCHED_BATCH))
  705. gran = sysctl_sched_batch_wakeup_granularity;
  706. if (is_same_group(curr, p))
  707. __check_preempt_curr_fair(cfs_rq, &p->se, &curr->se, gran);
  708. }
  709. static struct task_struct * pick_next_task_fair(struct rq *rq, u64 now)
  710. {
  711. struct cfs_rq *cfs_rq = &rq->cfs;
  712. struct sched_entity *se;
  713. if (unlikely(!cfs_rq->nr_running))
  714. return NULL;
  715. do {
  716. se = pick_next_entity(cfs_rq, now);
  717. cfs_rq = group_cfs_rq(se);
  718. } while (cfs_rq);
  719. return task_of(se);
  720. }
  721. /*
  722. * Account for a descheduled task:
  723. */
  724. static void put_prev_task_fair(struct rq *rq, struct task_struct *prev, u64 now)
  725. {
  726. struct sched_entity *se = &prev->se;
  727. struct cfs_rq *cfs_rq;
  728. for_each_sched_entity(se) {
  729. cfs_rq = cfs_rq_of(se);
  730. put_prev_entity(cfs_rq, se, now);
  731. }
  732. }
  733. /**************************************************
  734. * Fair scheduling class load-balancing methods:
  735. */
  736. /*
  737. * Load-balancing iterator. Note: while the runqueue stays locked
  738. * during the whole iteration, the current task might be
  739. * dequeued so the iterator has to be dequeue-safe. Here we
  740. * achieve that by always pre-iterating before returning
  741. * the current task:
  742. */
  743. static inline struct task_struct *
  744. __load_balance_iterator(struct cfs_rq *cfs_rq, struct rb_node *curr)
  745. {
  746. struct task_struct *p;
  747. if (!curr)
  748. return NULL;
  749. p = rb_entry(curr, struct task_struct, se.run_node);
  750. cfs_rq->rb_load_balance_curr = rb_next(curr);
  751. return p;
  752. }
  753. static struct task_struct *load_balance_start_fair(void *arg)
  754. {
  755. struct cfs_rq *cfs_rq = arg;
  756. return __load_balance_iterator(cfs_rq, first_fair(cfs_rq));
  757. }
  758. static struct task_struct *load_balance_next_fair(void *arg)
  759. {
  760. struct cfs_rq *cfs_rq = arg;
  761. return __load_balance_iterator(cfs_rq, cfs_rq->rb_load_balance_curr);
  762. }
  763. static int cfs_rq_best_prio(struct cfs_rq *cfs_rq)
  764. {
  765. struct sched_entity *curr;
  766. struct task_struct *p;
  767. if (!cfs_rq->nr_running)
  768. return MAX_PRIO;
  769. curr = __pick_next_entity(cfs_rq);
  770. p = task_of(curr);
  771. return p->prio;
  772. }
  773. static int
  774. load_balance_fair(struct rq *this_rq, int this_cpu, struct rq *busiest,
  775. unsigned long max_nr_move, unsigned long max_load_move,
  776. struct sched_domain *sd, enum cpu_idle_type idle,
  777. int *all_pinned, unsigned long *total_load_moved)
  778. {
  779. struct cfs_rq *busy_cfs_rq;
  780. unsigned long load_moved, total_nr_moved = 0, nr_moved;
  781. long rem_load_move = max_load_move;
  782. struct rq_iterator cfs_rq_iterator;
  783. cfs_rq_iterator.start = load_balance_start_fair;
  784. cfs_rq_iterator.next = load_balance_next_fair;
  785. for_each_leaf_cfs_rq(busiest, busy_cfs_rq) {
  786. struct cfs_rq *this_cfs_rq;
  787. long imbalance;
  788. unsigned long maxload;
  789. int this_best_prio, best_prio, best_prio_seen = 0;
  790. this_cfs_rq = cpu_cfs_rq(busy_cfs_rq, this_cpu);
  791. imbalance = busy_cfs_rq->load.weight -
  792. this_cfs_rq->load.weight;
  793. /* Don't pull if this_cfs_rq has more load than busy_cfs_rq */
  794. if (imbalance <= 0)
  795. continue;
  796. /* Don't pull more than imbalance/2 */
  797. imbalance /= 2;
  798. maxload = min(rem_load_move, imbalance);
  799. this_best_prio = cfs_rq_best_prio(this_cfs_rq);
  800. best_prio = cfs_rq_best_prio(busy_cfs_rq);
  801. /*
  802. * Enable handling of the case where there is more than one task
  803. * with the best priority. If the current running task is one
  804. * of those with prio==best_prio we know it won't be moved
  805. * and therefore it's safe to override the skip (based on load)
  806. * of any task we find with that prio.
  807. */
  808. if (cfs_rq_curr(busy_cfs_rq) == &busiest->curr->se)
  809. best_prio_seen = 1;
  810. /* pass busy_cfs_rq argument into
  811. * load_balance_[start|next]_fair iterators
  812. */
  813. cfs_rq_iterator.arg = busy_cfs_rq;
  814. nr_moved = balance_tasks(this_rq, this_cpu, busiest,
  815. max_nr_move, maxload, sd, idle, all_pinned,
  816. &load_moved, this_best_prio, best_prio,
  817. best_prio_seen, &cfs_rq_iterator);
  818. total_nr_moved += nr_moved;
  819. max_nr_move -= nr_moved;
  820. rem_load_move -= load_moved;
  821. if (max_nr_move <= 0 || rem_load_move <= 0)
  822. break;
  823. }
  824. *total_load_moved = max_load_move - rem_load_move;
  825. return total_nr_moved;
  826. }
  827. /*
  828. * scheduler tick hitting a task of our scheduling class:
  829. */
  830. static void task_tick_fair(struct rq *rq, struct task_struct *curr)
  831. {
  832. struct cfs_rq *cfs_rq;
  833. struct sched_entity *se = &curr->se;
  834. for_each_sched_entity(se) {
  835. cfs_rq = cfs_rq_of(se);
  836. entity_tick(cfs_rq, se);
  837. }
  838. }
  839. /*
  840. * Share the fairness runtime between parent and child, thus the
  841. * total amount of pressure for CPU stays equal - new tasks
  842. * get a chance to run but frequent forkers are not allowed to
  843. * monopolize the CPU. Note: the parent runqueue is locked,
  844. * the child is not running yet.
  845. */
  846. static void task_new_fair(struct rq *rq, struct task_struct *p)
  847. {
  848. struct cfs_rq *cfs_rq = task_cfs_rq(p);
  849. struct sched_entity *se = &p->se;
  850. u64 now = rq_clock(rq);
  851. sched_info_queued(p);
  852. update_stats_enqueue(cfs_rq, se, now);
  853. /*
  854. * Child runs first: we let it run before the parent
  855. * until it reschedules once. We set up the key so that
  856. * it will preempt the parent:
  857. */
  858. p->se.fair_key = current->se.fair_key -
  859. niced_granularity(&rq->curr->se, sysctl_sched_granularity) - 1;
  860. /*
  861. * The first wait is dominated by the child-runs-first logic,
  862. * so do not credit it with that waiting time yet:
  863. */
  864. if (sysctl_sched_features & SCHED_FEAT_SKIP_INITIAL)
  865. p->se.wait_start_fair = 0;
  866. /*
  867. * The statistical average of wait_runtime is about
  868. * -granularity/2, so initialize the task with that:
  869. */
  870. if (sysctl_sched_features & SCHED_FEAT_START_DEBIT)
  871. p->se.wait_runtime = -(sysctl_sched_granularity / 2);
  872. __enqueue_entity(cfs_rq, se);
  873. inc_nr_running(p, rq, now);
  874. }
  875. #ifdef CONFIG_FAIR_GROUP_SCHED
  876. /* Account for a task changing its policy or group.
  877. *
  878. * This routine is mostly called to set cfs_rq->curr field when a task
  879. * migrates between groups/classes.
  880. */
  881. static void set_curr_task_fair(struct rq *rq)
  882. {
  883. struct task_struct *curr = rq->curr;
  884. struct sched_entity *se = &curr->se;
  885. u64 now = rq_clock(rq);
  886. struct cfs_rq *cfs_rq;
  887. for_each_sched_entity(se) {
  888. cfs_rq = cfs_rq_of(se);
  889. set_next_entity(cfs_rq, se, now);
  890. }
  891. }
  892. #else
  893. static void set_curr_task_fair(struct rq *rq)
  894. {
  895. }
  896. #endif
  897. /*
  898. * All the scheduling class methods:
  899. */
  900. struct sched_class fair_sched_class __read_mostly = {
  901. .enqueue_task = enqueue_task_fair,
  902. .dequeue_task = dequeue_task_fair,
  903. .yield_task = yield_task_fair,
  904. .check_preempt_curr = check_preempt_curr_fair,
  905. .pick_next_task = pick_next_task_fair,
  906. .put_prev_task = put_prev_task_fair,
  907. .load_balance = load_balance_fair,
  908. .set_curr_task = set_curr_task_fair,
  909. .task_tick = task_tick_fair,
  910. .task_new = task_new_fair,
  911. };
  912. #ifdef CONFIG_SCHED_DEBUG
  913. void print_cfs_stats(struct seq_file *m, int cpu, u64 now)
  914. {
  915. struct rq *rq = cpu_rq(cpu);
  916. struct cfs_rq *cfs_rq;
  917. for_each_leaf_cfs_rq(rq, cfs_rq)
  918. print_cfs_rq(m, cpu, cfs_rq, now);
  919. }
  920. #endif