sched.h 46 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145114611471148114911501151115211531154115511561157115811591160116111621163116411651166116711681169117011711172117311741175117611771178117911801181118211831184118511861187118811891190119111921193119411951196119711981199120012011202120312041205120612071208120912101211121212131214121512161217121812191220122112221223122412251226122712281229123012311232123312341235123612371238123912401241124212431244124512461247124812491250125112521253125412551256125712581259126012611262126312641265126612671268126912701271127212731274127512761277127812791280128112821283128412851286128712881289129012911292129312941295129612971298129913001301130213031304130513061307130813091310131113121313131413151316131713181319132013211322132313241325132613271328132913301331133213331334133513361337133813391340134113421343134413451346134713481349135013511352135313541355135613571358135913601361136213631364136513661367136813691370137113721373137413751376137713781379138013811382138313841385138613871388138913901391139213931394139513961397139813991400140114021403140414051406140714081409141014111412141314141415141614171418141914201421142214231424142514261427142814291430143114321433143414351436143714381439144014411442144314441445144614471448144914501451145214531454145514561457145814591460146114621463146414651466146714681469147014711472147314741475147614771478147914801481148214831484148514861487148814891490149114921493149414951496149714981499150015011502150315041505150615071508150915101511151215131514151515161517151815191520152115221523152415251526152715281529153015311532153315341535153615371538153915401541154215431544154515461547154815491550155115521553155415551556155715581559156015611562156315641565156615671568156915701571157215731574157515761577157815791580158115821583158415851586158715881589159015911592159315941595159615971598159916001601160216031604160516061607160816091610161116121613161416151616161716181619162016211622162316241625162616271628162916301631163216331634163516361637163816391640164116421643164416451646164716481649165016511652165316541655165616571658165916601661166216631664166516661667166816691670167116721673167416751676167716781679168016811682168316841685168616871688168916901691169216931694169516961697169816991700170117021703170417051706170717081709171017111712171317141715171617171718171917201721172217231724172517261727172817291730173117321733173417351736173717381739174017411742174317441745174617471748174917501751175217531754175517561757175817591760176117621763176417651766176717681769177017711772177317741775177617771778177917801781178217831784178517861787178817891790179117921793179417951796179717981799180018011802180318041805180618071808180918101811181218131814181518161817
  1. #include <linux/sched.h>
  2. #include <linux/sched/sysctl.h>
  3. #include <linux/sched/rt.h>
  4. #include <linux/u64_stats_sync.h>
  5. #include <linux/sched/deadline.h>
  6. #include <linux/binfmts.h>
  7. #include <linux/mutex.h>
  8. #include <linux/spinlock.h>
  9. #include <linux/stop_machine.h>
  10. #include <linux/irq_work.h>
  11. #include <linux/tick.h>
  12. #include <linux/slab.h>
  13. #include "cpupri.h"
  14. #include "cpudeadline.h"
  15. #include "cpuacct.h"
  16. #ifdef CONFIG_SCHED_DEBUG
  17. #define SCHED_WARN_ON(x) WARN_ONCE(x, #x)
  18. #else
  19. #define SCHED_WARN_ON(x) ((void)(x))
  20. #endif
  21. struct rq;
  22. struct cpuidle_state;
  23. /* task_struct::on_rq states: */
  24. #define TASK_ON_RQ_QUEUED 1
  25. #define TASK_ON_RQ_MIGRATING 2
  26. extern __read_mostly int scheduler_running;
  27. extern unsigned long calc_load_update;
  28. extern atomic_long_t calc_load_tasks;
  29. extern void calc_global_load_tick(struct rq *this_rq);
  30. extern long calc_load_fold_active(struct rq *this_rq, long adjust);
  31. #ifdef CONFIG_SMP
  32. extern void cpu_load_update_active(struct rq *this_rq);
  33. #else
  34. static inline void cpu_load_update_active(struct rq *this_rq) { }
  35. #endif
  36. /*
  37. * Helpers for converting nanosecond timing to jiffy resolution
  38. */
  39. #define NS_TO_JIFFIES(TIME) ((unsigned long)(TIME) / (NSEC_PER_SEC / HZ))
  40. /*
  41. * Increase resolution of nice-level calculations for 64-bit architectures.
  42. * The extra resolution improves shares distribution and load balancing of
  43. * low-weight task groups (eg. nice +19 on an autogroup), deeper taskgroup
  44. * hierarchies, especially on larger systems. This is not a user-visible change
  45. * and does not change the user-interface for setting shares/weights.
  46. *
  47. * We increase resolution only if we have enough bits to allow this increased
  48. * resolution (i.e. 64bit). The costs for increasing resolution when 32bit are
  49. * pretty high and the returns do not justify the increased costs.
  50. *
  51. * Really only required when CONFIG_FAIR_GROUP_SCHED is also set, but to
  52. * increase coverage and consistency always enable it on 64bit platforms.
  53. */
  54. #ifdef CONFIG_64BIT
  55. # define NICE_0_LOAD_SHIFT (SCHED_FIXEDPOINT_SHIFT + SCHED_FIXEDPOINT_SHIFT)
  56. # define scale_load(w) ((w) << SCHED_FIXEDPOINT_SHIFT)
  57. # define scale_load_down(w) ((w) >> SCHED_FIXEDPOINT_SHIFT)
  58. #else
  59. # define NICE_0_LOAD_SHIFT (SCHED_FIXEDPOINT_SHIFT)
  60. # define scale_load(w) (w)
  61. # define scale_load_down(w) (w)
  62. #endif
  63. /*
  64. * Task weight (visible to users) and its load (invisible to users) have
  65. * independent resolution, but they should be well calibrated. We use
  66. * scale_load() and scale_load_down(w) to convert between them. The
  67. * following must be true:
  68. *
  69. * scale_load(sched_prio_to_weight[USER_PRIO(NICE_TO_PRIO(0))]) == NICE_0_LOAD
  70. *
  71. */
  72. #define NICE_0_LOAD (1L << NICE_0_LOAD_SHIFT)
  73. /*
  74. * Single value that decides SCHED_DEADLINE internal math precision.
  75. * 10 -> just above 1us
  76. * 9 -> just above 0.5us
  77. */
  78. #define DL_SCALE (10)
  79. /*
  80. * These are the 'tuning knobs' of the scheduler:
  81. */
  82. /*
  83. * single value that denotes runtime == period, ie unlimited time.
  84. */
  85. #define RUNTIME_INF ((u64)~0ULL)
  86. static inline int idle_policy(int policy)
  87. {
  88. return policy == SCHED_IDLE;
  89. }
  90. static inline int fair_policy(int policy)
  91. {
  92. return policy == SCHED_NORMAL || policy == SCHED_BATCH;
  93. }
  94. static inline int rt_policy(int policy)
  95. {
  96. return policy == SCHED_FIFO || policy == SCHED_RR;
  97. }
  98. static inline int dl_policy(int policy)
  99. {
  100. return policy == SCHED_DEADLINE;
  101. }
  102. static inline bool valid_policy(int policy)
  103. {
  104. return idle_policy(policy) || fair_policy(policy) ||
  105. rt_policy(policy) || dl_policy(policy);
  106. }
  107. static inline int task_has_rt_policy(struct task_struct *p)
  108. {
  109. return rt_policy(p->policy);
  110. }
  111. static inline int task_has_dl_policy(struct task_struct *p)
  112. {
  113. return dl_policy(p->policy);
  114. }
  115. /*
  116. * Tells if entity @a should preempt entity @b.
  117. */
  118. static inline bool
  119. dl_entity_preempt(struct sched_dl_entity *a, struct sched_dl_entity *b)
  120. {
  121. return dl_time_before(a->deadline, b->deadline);
  122. }
  123. /*
  124. * This is the priority-queue data structure of the RT scheduling class:
  125. */
  126. struct rt_prio_array {
  127. DECLARE_BITMAP(bitmap, MAX_RT_PRIO+1); /* include 1 bit for delimiter */
  128. struct list_head queue[MAX_RT_PRIO];
  129. };
  130. struct rt_bandwidth {
  131. /* nests inside the rq lock: */
  132. raw_spinlock_t rt_runtime_lock;
  133. ktime_t rt_period;
  134. u64 rt_runtime;
  135. struct hrtimer rt_period_timer;
  136. unsigned int rt_period_active;
  137. };
  138. void __dl_clear_params(struct task_struct *p);
  139. /*
  140. * To keep the bandwidth of -deadline tasks and groups under control
  141. * we need some place where:
  142. * - store the maximum -deadline bandwidth of the system (the group);
  143. * - cache the fraction of that bandwidth that is currently allocated.
  144. *
  145. * This is all done in the data structure below. It is similar to the
  146. * one used for RT-throttling (rt_bandwidth), with the main difference
  147. * that, since here we are only interested in admission control, we
  148. * do not decrease any runtime while the group "executes", neither we
  149. * need a timer to replenish it.
  150. *
  151. * With respect to SMP, the bandwidth is given on a per-CPU basis,
  152. * meaning that:
  153. * - dl_bw (< 100%) is the bandwidth of the system (group) on each CPU;
  154. * - dl_total_bw array contains, in the i-eth element, the currently
  155. * allocated bandwidth on the i-eth CPU.
  156. * Moreover, groups consume bandwidth on each CPU, while tasks only
  157. * consume bandwidth on the CPU they're running on.
  158. * Finally, dl_total_bw_cpu is used to cache the index of dl_total_bw
  159. * that will be shown the next time the proc or cgroup controls will
  160. * be red. It on its turn can be changed by writing on its own
  161. * control.
  162. */
  163. struct dl_bandwidth {
  164. raw_spinlock_t dl_runtime_lock;
  165. u64 dl_runtime;
  166. u64 dl_period;
  167. };
  168. static inline int dl_bandwidth_enabled(void)
  169. {
  170. return sysctl_sched_rt_runtime >= 0;
  171. }
  172. extern struct dl_bw *dl_bw_of(int i);
  173. struct dl_bw {
  174. raw_spinlock_t lock;
  175. u64 bw, total_bw;
  176. };
  177. static inline
  178. void __dl_clear(struct dl_bw *dl_b, u64 tsk_bw)
  179. {
  180. dl_b->total_bw -= tsk_bw;
  181. }
  182. static inline
  183. void __dl_add(struct dl_bw *dl_b, u64 tsk_bw)
  184. {
  185. dl_b->total_bw += tsk_bw;
  186. }
  187. static inline
  188. bool __dl_overflow(struct dl_bw *dl_b, int cpus, u64 old_bw, u64 new_bw)
  189. {
  190. return dl_b->bw != -1 &&
  191. dl_b->bw * cpus < dl_b->total_bw - old_bw + new_bw;
  192. }
  193. extern struct mutex sched_domains_mutex;
  194. #ifdef CONFIG_CGROUP_SCHED
  195. #include <linux/cgroup.h>
  196. struct cfs_rq;
  197. struct rt_rq;
  198. extern struct list_head task_groups;
  199. struct cfs_bandwidth {
  200. #ifdef CONFIG_CFS_BANDWIDTH
  201. raw_spinlock_t lock;
  202. ktime_t period;
  203. u64 quota, runtime;
  204. s64 hierarchical_quota;
  205. u64 runtime_expires;
  206. int idle, period_active;
  207. struct hrtimer period_timer, slack_timer;
  208. struct list_head throttled_cfs_rq;
  209. /* statistics */
  210. int nr_periods, nr_throttled;
  211. u64 throttled_time;
  212. #endif
  213. };
  214. /* task group related information */
  215. struct task_group {
  216. struct cgroup_subsys_state css;
  217. #ifdef CONFIG_FAIR_GROUP_SCHED
  218. /* schedulable entities of this group on each cpu */
  219. struct sched_entity **se;
  220. /* runqueue "owned" by this group on each cpu */
  221. struct cfs_rq **cfs_rq;
  222. unsigned long shares;
  223. #ifdef CONFIG_SMP
  224. /*
  225. * load_avg can be heavily contended at clock tick time, so put
  226. * it in its own cacheline separated from the fields above which
  227. * will also be accessed at each tick.
  228. */
  229. atomic_long_t load_avg ____cacheline_aligned;
  230. #endif
  231. #endif
  232. #ifdef CONFIG_RT_GROUP_SCHED
  233. struct sched_rt_entity **rt_se;
  234. struct rt_rq **rt_rq;
  235. struct rt_bandwidth rt_bandwidth;
  236. #endif
  237. struct rcu_head rcu;
  238. struct list_head list;
  239. struct task_group *parent;
  240. struct list_head siblings;
  241. struct list_head children;
  242. #ifdef CONFIG_SCHED_AUTOGROUP
  243. struct autogroup *autogroup;
  244. #endif
  245. struct cfs_bandwidth cfs_bandwidth;
  246. };
  247. #ifdef CONFIG_FAIR_GROUP_SCHED
  248. #define ROOT_TASK_GROUP_LOAD NICE_0_LOAD
  249. /*
  250. * A weight of 0 or 1 can cause arithmetics problems.
  251. * A weight of a cfs_rq is the sum of weights of which entities
  252. * are queued on this cfs_rq, so a weight of a entity should not be
  253. * too large, so as the shares value of a task group.
  254. * (The default weight is 1024 - so there's no practical
  255. * limitation from this.)
  256. */
  257. #define MIN_SHARES (1UL << 1)
  258. #define MAX_SHARES (1UL << 18)
  259. #endif
  260. typedef int (*tg_visitor)(struct task_group *, void *);
  261. extern int walk_tg_tree_from(struct task_group *from,
  262. tg_visitor down, tg_visitor up, void *data);
  263. /*
  264. * Iterate the full tree, calling @down when first entering a node and @up when
  265. * leaving it for the final time.
  266. *
  267. * Caller must hold rcu_lock or sufficient equivalent.
  268. */
  269. static inline int walk_tg_tree(tg_visitor down, tg_visitor up, void *data)
  270. {
  271. return walk_tg_tree_from(&root_task_group, down, up, data);
  272. }
  273. extern int tg_nop(struct task_group *tg, void *data);
  274. extern void free_fair_sched_group(struct task_group *tg);
  275. extern int alloc_fair_sched_group(struct task_group *tg, struct task_group *parent);
  276. extern void online_fair_sched_group(struct task_group *tg);
  277. extern void unregister_fair_sched_group(struct task_group *tg);
  278. extern void init_tg_cfs_entry(struct task_group *tg, struct cfs_rq *cfs_rq,
  279. struct sched_entity *se, int cpu,
  280. struct sched_entity *parent);
  281. extern void init_cfs_bandwidth(struct cfs_bandwidth *cfs_b);
  282. extern void __refill_cfs_bandwidth_runtime(struct cfs_bandwidth *cfs_b);
  283. extern void start_cfs_bandwidth(struct cfs_bandwidth *cfs_b);
  284. extern void unthrottle_cfs_rq(struct cfs_rq *cfs_rq);
  285. extern void free_rt_sched_group(struct task_group *tg);
  286. extern int alloc_rt_sched_group(struct task_group *tg, struct task_group *parent);
  287. extern void init_tg_rt_entry(struct task_group *tg, struct rt_rq *rt_rq,
  288. struct sched_rt_entity *rt_se, int cpu,
  289. struct sched_rt_entity *parent);
  290. extern struct task_group *sched_create_group(struct task_group *parent);
  291. extern void sched_online_group(struct task_group *tg,
  292. struct task_group *parent);
  293. extern void sched_destroy_group(struct task_group *tg);
  294. extern void sched_offline_group(struct task_group *tg);
  295. extern void sched_move_task(struct task_struct *tsk);
  296. #ifdef CONFIG_FAIR_GROUP_SCHED
  297. extern int sched_group_set_shares(struct task_group *tg, unsigned long shares);
  298. #ifdef CONFIG_SMP
  299. extern void set_task_rq_fair(struct sched_entity *se,
  300. struct cfs_rq *prev, struct cfs_rq *next);
  301. #else /* !CONFIG_SMP */
  302. static inline void set_task_rq_fair(struct sched_entity *se,
  303. struct cfs_rq *prev, struct cfs_rq *next) { }
  304. #endif /* CONFIG_SMP */
  305. #endif /* CONFIG_FAIR_GROUP_SCHED */
  306. #else /* CONFIG_CGROUP_SCHED */
  307. struct cfs_bandwidth { };
  308. #endif /* CONFIG_CGROUP_SCHED */
  309. /* CFS-related fields in a runqueue */
  310. struct cfs_rq {
  311. struct load_weight load;
  312. unsigned int nr_running, h_nr_running;
  313. u64 exec_clock;
  314. u64 min_vruntime;
  315. #ifndef CONFIG_64BIT
  316. u64 min_vruntime_copy;
  317. #endif
  318. struct rb_root tasks_timeline;
  319. struct rb_node *rb_leftmost;
  320. /*
  321. * 'curr' points to currently running entity on this cfs_rq.
  322. * It is set to NULL otherwise (i.e when none are currently running).
  323. */
  324. struct sched_entity *curr, *next, *last, *skip;
  325. #ifdef CONFIG_SCHED_DEBUG
  326. unsigned int nr_spread_over;
  327. #endif
  328. #ifdef CONFIG_SMP
  329. /*
  330. * CFS load tracking
  331. */
  332. struct sched_avg avg;
  333. u64 runnable_load_sum;
  334. unsigned long runnable_load_avg;
  335. #ifdef CONFIG_FAIR_GROUP_SCHED
  336. unsigned long tg_load_avg_contrib;
  337. #endif
  338. atomic_long_t removed_load_avg, removed_util_avg;
  339. #ifndef CONFIG_64BIT
  340. u64 load_last_update_time_copy;
  341. #endif
  342. #ifdef CONFIG_FAIR_GROUP_SCHED
  343. /*
  344. * h_load = weight * f(tg)
  345. *
  346. * Where f(tg) is the recursive weight fraction assigned to
  347. * this group.
  348. */
  349. unsigned long h_load;
  350. u64 last_h_load_update;
  351. struct sched_entity *h_load_next;
  352. #endif /* CONFIG_FAIR_GROUP_SCHED */
  353. #endif /* CONFIG_SMP */
  354. #ifdef CONFIG_FAIR_GROUP_SCHED
  355. struct rq *rq; /* cpu runqueue to which this cfs_rq is attached */
  356. /*
  357. * leaf cfs_rqs are those that hold tasks (lowest schedulable entity in
  358. * a hierarchy). Non-leaf lrqs hold other higher schedulable entities
  359. * (like users, containers etc.)
  360. *
  361. * leaf_cfs_rq_list ties together list of leaf cfs_rq's in a cpu. This
  362. * list is used during load balance.
  363. */
  364. int on_list;
  365. struct list_head leaf_cfs_rq_list;
  366. struct task_group *tg; /* group that "owns" this runqueue */
  367. #ifdef CONFIG_CFS_BANDWIDTH
  368. int runtime_enabled;
  369. u64 runtime_expires;
  370. s64 runtime_remaining;
  371. u64 throttled_clock, throttled_clock_task;
  372. u64 throttled_clock_task_time;
  373. int throttled, throttle_count;
  374. struct list_head throttled_list;
  375. #endif /* CONFIG_CFS_BANDWIDTH */
  376. #endif /* CONFIG_FAIR_GROUP_SCHED */
  377. };
  378. static inline int rt_bandwidth_enabled(void)
  379. {
  380. return sysctl_sched_rt_runtime >= 0;
  381. }
  382. /* RT IPI pull logic requires IRQ_WORK */
  383. #ifdef CONFIG_IRQ_WORK
  384. # define HAVE_RT_PUSH_IPI
  385. #endif
  386. /* Real-Time classes' related field in a runqueue: */
  387. struct rt_rq {
  388. struct rt_prio_array active;
  389. unsigned int rt_nr_running;
  390. unsigned int rr_nr_running;
  391. #if defined CONFIG_SMP || defined CONFIG_RT_GROUP_SCHED
  392. struct {
  393. int curr; /* highest queued rt task prio */
  394. #ifdef CONFIG_SMP
  395. int next; /* next highest */
  396. #endif
  397. } highest_prio;
  398. #endif
  399. #ifdef CONFIG_SMP
  400. unsigned long rt_nr_migratory;
  401. unsigned long rt_nr_total;
  402. int overloaded;
  403. struct plist_head pushable_tasks;
  404. #ifdef HAVE_RT_PUSH_IPI
  405. int push_flags;
  406. int push_cpu;
  407. struct irq_work push_work;
  408. raw_spinlock_t push_lock;
  409. #endif
  410. #endif /* CONFIG_SMP */
  411. int rt_queued;
  412. int rt_throttled;
  413. u64 rt_time;
  414. u64 rt_runtime;
  415. /* Nests inside the rq lock: */
  416. raw_spinlock_t rt_runtime_lock;
  417. #ifdef CONFIG_RT_GROUP_SCHED
  418. unsigned long rt_nr_boosted;
  419. struct rq *rq;
  420. struct task_group *tg;
  421. #endif
  422. };
  423. /* Deadline class' related fields in a runqueue */
  424. struct dl_rq {
  425. /* runqueue is an rbtree, ordered by deadline */
  426. struct rb_root rb_root;
  427. struct rb_node *rb_leftmost;
  428. unsigned long dl_nr_running;
  429. #ifdef CONFIG_SMP
  430. /*
  431. * Deadline values of the currently executing and the
  432. * earliest ready task on this rq. Caching these facilitates
  433. * the decision wether or not a ready but not running task
  434. * should migrate somewhere else.
  435. */
  436. struct {
  437. u64 curr;
  438. u64 next;
  439. } earliest_dl;
  440. unsigned long dl_nr_migratory;
  441. int overloaded;
  442. /*
  443. * Tasks on this rq that can be pushed away. They are kept in
  444. * an rb-tree, ordered by tasks' deadlines, with caching
  445. * of the leftmost (earliest deadline) element.
  446. */
  447. struct rb_root pushable_dl_tasks_root;
  448. struct rb_node *pushable_dl_tasks_leftmost;
  449. #else
  450. struct dl_bw dl_bw;
  451. #endif
  452. };
  453. #ifdef CONFIG_SMP
  454. /*
  455. * We add the notion of a root-domain which will be used to define per-domain
  456. * variables. Each exclusive cpuset essentially defines an island domain by
  457. * fully partitioning the member cpus from any other cpuset. Whenever a new
  458. * exclusive cpuset is created, we also create and attach a new root-domain
  459. * object.
  460. *
  461. */
  462. struct root_domain {
  463. atomic_t refcount;
  464. atomic_t rto_count;
  465. struct rcu_head rcu;
  466. cpumask_var_t span;
  467. cpumask_var_t online;
  468. /* Indicate more than one runnable task for any CPU */
  469. bool overload;
  470. /*
  471. * The bit corresponding to a CPU gets set here if such CPU has more
  472. * than one runnable -deadline task (as it is below for RT tasks).
  473. */
  474. cpumask_var_t dlo_mask;
  475. atomic_t dlo_count;
  476. struct dl_bw dl_bw;
  477. struct cpudl cpudl;
  478. /*
  479. * The "RT overload" flag: it gets set if a CPU has more than
  480. * one runnable RT task.
  481. */
  482. cpumask_var_t rto_mask;
  483. struct cpupri cpupri;
  484. unsigned long max_cpu_capacity;
  485. };
  486. extern struct root_domain def_root_domain;
  487. #endif /* CONFIG_SMP */
  488. /*
  489. * This is the main, per-CPU runqueue data structure.
  490. *
  491. * Locking rule: those places that want to lock multiple runqueues
  492. * (such as the load balancing or the thread migration code), lock
  493. * acquire operations must be ordered by ascending &runqueue.
  494. */
  495. struct rq {
  496. /* runqueue lock: */
  497. raw_spinlock_t lock;
  498. /*
  499. * nr_running and cpu_load should be in the same cacheline because
  500. * remote CPUs use both these fields when doing load calculation.
  501. */
  502. unsigned int nr_running;
  503. #ifdef CONFIG_NUMA_BALANCING
  504. unsigned int nr_numa_running;
  505. unsigned int nr_preferred_running;
  506. #endif
  507. #define CPU_LOAD_IDX_MAX 5
  508. unsigned long cpu_load[CPU_LOAD_IDX_MAX];
  509. #ifdef CONFIG_NO_HZ_COMMON
  510. #ifdef CONFIG_SMP
  511. unsigned long last_load_update_tick;
  512. #endif /* CONFIG_SMP */
  513. unsigned long nohz_flags;
  514. #endif /* CONFIG_NO_HZ_COMMON */
  515. #ifdef CONFIG_NO_HZ_FULL
  516. unsigned long last_sched_tick;
  517. #endif
  518. /* capture load from *all* tasks on this cpu: */
  519. struct load_weight load;
  520. unsigned long nr_load_updates;
  521. u64 nr_switches;
  522. struct cfs_rq cfs;
  523. struct rt_rq rt;
  524. struct dl_rq dl;
  525. #ifdef CONFIG_FAIR_GROUP_SCHED
  526. /* list of leaf cfs_rq on this cpu: */
  527. struct list_head leaf_cfs_rq_list;
  528. #endif /* CONFIG_FAIR_GROUP_SCHED */
  529. /*
  530. * This is part of a global counter where only the total sum
  531. * over all CPUs matters. A task can increase this counter on
  532. * one CPU and if it got migrated afterwards it may decrease
  533. * it on another CPU. Always updated under the runqueue lock:
  534. */
  535. unsigned long nr_uninterruptible;
  536. struct task_struct *curr, *idle, *stop;
  537. unsigned long next_balance;
  538. struct mm_struct *prev_mm;
  539. unsigned int clock_skip_update;
  540. u64 clock;
  541. u64 clock_task;
  542. atomic_t nr_iowait;
  543. #ifdef CONFIG_SMP
  544. struct root_domain *rd;
  545. struct sched_domain *sd;
  546. unsigned long cpu_capacity;
  547. unsigned long cpu_capacity_orig;
  548. struct callback_head *balance_callback;
  549. unsigned char idle_balance;
  550. /* For active balancing */
  551. int active_balance;
  552. int push_cpu;
  553. struct cpu_stop_work active_balance_work;
  554. /* cpu of this runqueue: */
  555. int cpu;
  556. int online;
  557. struct list_head cfs_tasks;
  558. u64 rt_avg;
  559. u64 age_stamp;
  560. u64 idle_stamp;
  561. u64 avg_idle;
  562. /* This is used to determine avg_idle's max value */
  563. u64 max_idle_balance_cost;
  564. #endif
  565. #ifdef CONFIG_IRQ_TIME_ACCOUNTING
  566. u64 prev_irq_time;
  567. #endif
  568. #ifdef CONFIG_PARAVIRT
  569. u64 prev_steal_time;
  570. #endif
  571. #ifdef CONFIG_PARAVIRT_TIME_ACCOUNTING
  572. u64 prev_steal_time_rq;
  573. #endif
  574. /* calc_load related fields */
  575. unsigned long calc_load_update;
  576. long calc_load_active;
  577. #ifdef CONFIG_SCHED_HRTICK
  578. #ifdef CONFIG_SMP
  579. int hrtick_csd_pending;
  580. struct call_single_data hrtick_csd;
  581. #endif
  582. struct hrtimer hrtick_timer;
  583. #endif
  584. #ifdef CONFIG_SCHEDSTATS
  585. /* latency stats */
  586. struct sched_info rq_sched_info;
  587. unsigned long long rq_cpu_time;
  588. /* could above be rq->cfs_rq.exec_clock + rq->rt_rq.rt_runtime ? */
  589. /* sys_sched_yield() stats */
  590. unsigned int yld_count;
  591. /* schedule() stats */
  592. unsigned int sched_count;
  593. unsigned int sched_goidle;
  594. /* try_to_wake_up() stats */
  595. unsigned int ttwu_count;
  596. unsigned int ttwu_local;
  597. #endif
  598. #ifdef CONFIG_SMP
  599. struct llist_head wake_list;
  600. #endif
  601. #ifdef CONFIG_CPU_IDLE
  602. /* Must be inspected within a rcu lock section */
  603. struct cpuidle_state *idle_state;
  604. #endif
  605. };
  606. static inline int cpu_of(struct rq *rq)
  607. {
  608. #ifdef CONFIG_SMP
  609. return rq->cpu;
  610. #else
  611. return 0;
  612. #endif
  613. }
  614. #ifdef CONFIG_SCHED_SMT
  615. extern struct static_key_false sched_smt_present;
  616. extern void __update_idle_core(struct rq *rq);
  617. static inline void update_idle_core(struct rq *rq)
  618. {
  619. if (static_branch_unlikely(&sched_smt_present))
  620. __update_idle_core(rq);
  621. }
  622. #else
  623. static inline void update_idle_core(struct rq *rq) { }
  624. #endif
  625. DECLARE_PER_CPU_SHARED_ALIGNED(struct rq, runqueues);
  626. #define cpu_rq(cpu) (&per_cpu(runqueues, (cpu)))
  627. #define this_rq() this_cpu_ptr(&runqueues)
  628. #define task_rq(p) cpu_rq(task_cpu(p))
  629. #define cpu_curr(cpu) (cpu_rq(cpu)->curr)
  630. #define raw_rq() raw_cpu_ptr(&runqueues)
  631. static inline u64 __rq_clock_broken(struct rq *rq)
  632. {
  633. return READ_ONCE(rq->clock);
  634. }
  635. static inline u64 rq_clock(struct rq *rq)
  636. {
  637. lockdep_assert_held(&rq->lock);
  638. return rq->clock;
  639. }
  640. static inline u64 rq_clock_task(struct rq *rq)
  641. {
  642. lockdep_assert_held(&rq->lock);
  643. return rq->clock_task;
  644. }
  645. #define RQCF_REQ_SKIP 0x01
  646. #define RQCF_ACT_SKIP 0x02
  647. static inline void rq_clock_skip_update(struct rq *rq, bool skip)
  648. {
  649. lockdep_assert_held(&rq->lock);
  650. if (skip)
  651. rq->clock_skip_update |= RQCF_REQ_SKIP;
  652. else
  653. rq->clock_skip_update &= ~RQCF_REQ_SKIP;
  654. }
  655. #ifdef CONFIG_NUMA
  656. enum numa_topology_type {
  657. NUMA_DIRECT,
  658. NUMA_GLUELESS_MESH,
  659. NUMA_BACKPLANE,
  660. };
  661. extern enum numa_topology_type sched_numa_topology_type;
  662. extern int sched_max_numa_distance;
  663. extern bool find_numa_distance(int distance);
  664. #endif
  665. #ifdef CONFIG_NUMA_BALANCING
  666. /* The regions in numa_faults array from task_struct */
  667. enum numa_faults_stats {
  668. NUMA_MEM = 0,
  669. NUMA_CPU,
  670. NUMA_MEMBUF,
  671. NUMA_CPUBUF
  672. };
  673. extern void sched_setnuma(struct task_struct *p, int node);
  674. extern int migrate_task_to(struct task_struct *p, int cpu);
  675. extern int migrate_swap(struct task_struct *, struct task_struct *);
  676. #endif /* CONFIG_NUMA_BALANCING */
  677. #ifdef CONFIG_SMP
  678. static inline void
  679. queue_balance_callback(struct rq *rq,
  680. struct callback_head *head,
  681. void (*func)(struct rq *rq))
  682. {
  683. lockdep_assert_held(&rq->lock);
  684. if (unlikely(head->next))
  685. return;
  686. head->func = (void (*)(struct callback_head *))func;
  687. head->next = rq->balance_callback;
  688. rq->balance_callback = head;
  689. }
  690. extern void sched_ttwu_pending(void);
  691. #define rcu_dereference_check_sched_domain(p) \
  692. rcu_dereference_check((p), \
  693. lockdep_is_held(&sched_domains_mutex))
  694. /*
  695. * The domain tree (rq->sd) is protected by RCU's quiescent state transition.
  696. * See detach_destroy_domains: synchronize_sched for details.
  697. *
  698. * The domain tree of any CPU may only be accessed from within
  699. * preempt-disabled sections.
  700. */
  701. #define for_each_domain(cpu, __sd) \
  702. for (__sd = rcu_dereference_check_sched_domain(cpu_rq(cpu)->sd); \
  703. __sd; __sd = __sd->parent)
  704. #define for_each_lower_domain(sd) for (; sd; sd = sd->child)
  705. /**
  706. * highest_flag_domain - Return highest sched_domain containing flag.
  707. * @cpu: The cpu whose highest level of sched domain is to
  708. * be returned.
  709. * @flag: The flag to check for the highest sched_domain
  710. * for the given cpu.
  711. *
  712. * Returns the highest sched_domain of a cpu which contains the given flag.
  713. */
  714. static inline struct sched_domain *highest_flag_domain(int cpu, int flag)
  715. {
  716. struct sched_domain *sd, *hsd = NULL;
  717. for_each_domain(cpu, sd) {
  718. if (!(sd->flags & flag))
  719. break;
  720. hsd = sd;
  721. }
  722. return hsd;
  723. }
  724. static inline struct sched_domain *lowest_flag_domain(int cpu, int flag)
  725. {
  726. struct sched_domain *sd;
  727. for_each_domain(cpu, sd) {
  728. if (sd->flags & flag)
  729. break;
  730. }
  731. return sd;
  732. }
  733. DECLARE_PER_CPU(struct sched_domain *, sd_llc);
  734. DECLARE_PER_CPU(int, sd_llc_size);
  735. DECLARE_PER_CPU(int, sd_llc_id);
  736. DECLARE_PER_CPU(struct sched_domain_shared *, sd_llc_shared);
  737. DECLARE_PER_CPU(struct sched_domain *, sd_numa);
  738. DECLARE_PER_CPU(struct sched_domain *, sd_asym);
  739. struct sched_group_capacity {
  740. atomic_t ref;
  741. /*
  742. * CPU capacity of this group, SCHED_CAPACITY_SCALE being max capacity
  743. * for a single CPU.
  744. */
  745. unsigned int capacity;
  746. unsigned long next_update;
  747. int imbalance; /* XXX unrelated to capacity but shared group state */
  748. unsigned long cpumask[0]; /* iteration mask */
  749. };
  750. struct sched_group {
  751. struct sched_group *next; /* Must be a circular list */
  752. atomic_t ref;
  753. unsigned int group_weight;
  754. struct sched_group_capacity *sgc;
  755. /*
  756. * The CPUs this group covers.
  757. *
  758. * NOTE: this field is variable length. (Allocated dynamically
  759. * by attaching extra space to the end of the structure,
  760. * depending on how many CPUs the kernel has booted up with)
  761. */
  762. unsigned long cpumask[0];
  763. };
  764. static inline struct cpumask *sched_group_cpus(struct sched_group *sg)
  765. {
  766. return to_cpumask(sg->cpumask);
  767. }
  768. /*
  769. * cpumask masking which cpus in the group are allowed to iterate up the domain
  770. * tree.
  771. */
  772. static inline struct cpumask *sched_group_mask(struct sched_group *sg)
  773. {
  774. return to_cpumask(sg->sgc->cpumask);
  775. }
  776. /**
  777. * group_first_cpu - Returns the first cpu in the cpumask of a sched_group.
  778. * @group: The group whose first cpu is to be returned.
  779. */
  780. static inline unsigned int group_first_cpu(struct sched_group *group)
  781. {
  782. return cpumask_first(sched_group_cpus(group));
  783. }
  784. extern int group_balance_cpu(struct sched_group *sg);
  785. #if defined(CONFIG_SCHED_DEBUG) && defined(CONFIG_SYSCTL)
  786. void register_sched_domain_sysctl(void);
  787. void unregister_sched_domain_sysctl(void);
  788. #else
  789. static inline void register_sched_domain_sysctl(void)
  790. {
  791. }
  792. static inline void unregister_sched_domain_sysctl(void)
  793. {
  794. }
  795. #endif
  796. #else
  797. static inline void sched_ttwu_pending(void) { }
  798. #endif /* CONFIG_SMP */
  799. #include "stats.h"
  800. #include "auto_group.h"
  801. #ifdef CONFIG_CGROUP_SCHED
  802. /*
  803. * Return the group to which this tasks belongs.
  804. *
  805. * We cannot use task_css() and friends because the cgroup subsystem
  806. * changes that value before the cgroup_subsys::attach() method is called,
  807. * therefore we cannot pin it and might observe the wrong value.
  808. *
  809. * The same is true for autogroup's p->signal->autogroup->tg, the autogroup
  810. * core changes this before calling sched_move_task().
  811. *
  812. * Instead we use a 'copy' which is updated from sched_move_task() while
  813. * holding both task_struct::pi_lock and rq::lock.
  814. */
  815. static inline struct task_group *task_group(struct task_struct *p)
  816. {
  817. return p->sched_task_group;
  818. }
  819. /* Change a task's cfs_rq and parent entity if it moves across CPUs/groups */
  820. static inline void set_task_rq(struct task_struct *p, unsigned int cpu)
  821. {
  822. #if defined(CONFIG_FAIR_GROUP_SCHED) || defined(CONFIG_RT_GROUP_SCHED)
  823. struct task_group *tg = task_group(p);
  824. #endif
  825. #ifdef CONFIG_FAIR_GROUP_SCHED
  826. set_task_rq_fair(&p->se, p->se.cfs_rq, tg->cfs_rq[cpu]);
  827. p->se.cfs_rq = tg->cfs_rq[cpu];
  828. p->se.parent = tg->se[cpu];
  829. #endif
  830. #ifdef CONFIG_RT_GROUP_SCHED
  831. p->rt.rt_rq = tg->rt_rq[cpu];
  832. p->rt.parent = tg->rt_se[cpu];
  833. #endif
  834. }
  835. #else /* CONFIG_CGROUP_SCHED */
  836. static inline void set_task_rq(struct task_struct *p, unsigned int cpu) { }
  837. static inline struct task_group *task_group(struct task_struct *p)
  838. {
  839. return NULL;
  840. }
  841. #endif /* CONFIG_CGROUP_SCHED */
  842. static inline void __set_task_cpu(struct task_struct *p, unsigned int cpu)
  843. {
  844. set_task_rq(p, cpu);
  845. #ifdef CONFIG_SMP
  846. /*
  847. * After ->cpu is set up to a new value, task_rq_lock(p, ...) can be
  848. * successfuly executed on another CPU. We must ensure that updates of
  849. * per-task data have been completed by this moment.
  850. */
  851. smp_wmb();
  852. #ifdef CONFIG_THREAD_INFO_IN_TASK
  853. p->cpu = cpu;
  854. #else
  855. task_thread_info(p)->cpu = cpu;
  856. #endif
  857. p->wake_cpu = cpu;
  858. #endif
  859. }
  860. /*
  861. * Tunables that become constants when CONFIG_SCHED_DEBUG is off:
  862. */
  863. #ifdef CONFIG_SCHED_DEBUG
  864. # include <linux/static_key.h>
  865. # define const_debug __read_mostly
  866. #else
  867. # define const_debug const
  868. #endif
  869. extern const_debug unsigned int sysctl_sched_features;
  870. #define SCHED_FEAT(name, enabled) \
  871. __SCHED_FEAT_##name ,
  872. enum {
  873. #include "features.h"
  874. __SCHED_FEAT_NR,
  875. };
  876. #undef SCHED_FEAT
  877. #if defined(CONFIG_SCHED_DEBUG) && defined(HAVE_JUMP_LABEL)
  878. #define SCHED_FEAT(name, enabled) \
  879. static __always_inline bool static_branch_##name(struct static_key *key) \
  880. { \
  881. return static_key_##enabled(key); \
  882. }
  883. #include "features.h"
  884. #undef SCHED_FEAT
  885. extern struct static_key sched_feat_keys[__SCHED_FEAT_NR];
  886. #define sched_feat(x) (static_branch_##x(&sched_feat_keys[__SCHED_FEAT_##x]))
  887. #else /* !(SCHED_DEBUG && HAVE_JUMP_LABEL) */
  888. #define sched_feat(x) (sysctl_sched_features & (1UL << __SCHED_FEAT_##x))
  889. #endif /* SCHED_DEBUG && HAVE_JUMP_LABEL */
  890. extern struct static_key_false sched_numa_balancing;
  891. extern struct static_key_false sched_schedstats;
  892. static inline u64 global_rt_period(void)
  893. {
  894. return (u64)sysctl_sched_rt_period * NSEC_PER_USEC;
  895. }
  896. static inline u64 global_rt_runtime(void)
  897. {
  898. if (sysctl_sched_rt_runtime < 0)
  899. return RUNTIME_INF;
  900. return (u64)sysctl_sched_rt_runtime * NSEC_PER_USEC;
  901. }
  902. static inline int task_current(struct rq *rq, struct task_struct *p)
  903. {
  904. return rq->curr == p;
  905. }
  906. static inline int task_running(struct rq *rq, struct task_struct *p)
  907. {
  908. #ifdef CONFIG_SMP
  909. return p->on_cpu;
  910. #else
  911. return task_current(rq, p);
  912. #endif
  913. }
  914. static inline int task_on_rq_queued(struct task_struct *p)
  915. {
  916. return p->on_rq == TASK_ON_RQ_QUEUED;
  917. }
  918. static inline int task_on_rq_migrating(struct task_struct *p)
  919. {
  920. return p->on_rq == TASK_ON_RQ_MIGRATING;
  921. }
  922. #ifndef prepare_arch_switch
  923. # define prepare_arch_switch(next) do { } while (0)
  924. #endif
  925. #ifndef finish_arch_post_lock_switch
  926. # define finish_arch_post_lock_switch() do { } while (0)
  927. #endif
  928. static inline void prepare_lock_switch(struct rq *rq, struct task_struct *next)
  929. {
  930. #ifdef CONFIG_SMP
  931. /*
  932. * We can optimise this out completely for !SMP, because the
  933. * SMP rebalancing from interrupt is the only thing that cares
  934. * here.
  935. */
  936. next->on_cpu = 1;
  937. #endif
  938. }
  939. static inline void finish_lock_switch(struct rq *rq, struct task_struct *prev)
  940. {
  941. #ifdef CONFIG_SMP
  942. /*
  943. * After ->on_cpu is cleared, the task can be moved to a different CPU.
  944. * We must ensure this doesn't happen until the switch is completely
  945. * finished.
  946. *
  947. * In particular, the load of prev->state in finish_task_switch() must
  948. * happen before this.
  949. *
  950. * Pairs with the smp_cond_load_acquire() in try_to_wake_up().
  951. */
  952. smp_store_release(&prev->on_cpu, 0);
  953. #endif
  954. #ifdef CONFIG_DEBUG_SPINLOCK
  955. /* this is a valid case when another task releases the spinlock */
  956. rq->lock.owner = current;
  957. #endif
  958. /*
  959. * If we are tracking spinlock dependencies then we have to
  960. * fix up the runqueue lock - which gets 'carried over' from
  961. * prev into current:
  962. */
  963. spin_acquire(&rq->lock.dep_map, 0, 0, _THIS_IP_);
  964. raw_spin_unlock_irq(&rq->lock);
  965. }
  966. /*
  967. * wake flags
  968. */
  969. #define WF_SYNC 0x01 /* waker goes to sleep after wakeup */
  970. #define WF_FORK 0x02 /* child wakeup after fork */
  971. #define WF_MIGRATED 0x4 /* internal use, task got migrated */
  972. /*
  973. * To aid in avoiding the subversion of "niceness" due to uneven distribution
  974. * of tasks with abnormal "nice" values across CPUs the contribution that
  975. * each task makes to its run queue's load is weighted according to its
  976. * scheduling class and "nice" value. For SCHED_NORMAL tasks this is just a
  977. * scaled version of the new time slice allocation that they receive on time
  978. * slice expiry etc.
  979. */
  980. #define WEIGHT_IDLEPRIO 3
  981. #define WMULT_IDLEPRIO 1431655765
  982. extern const int sched_prio_to_weight[40];
  983. extern const u32 sched_prio_to_wmult[40];
  984. /*
  985. * {de,en}queue flags:
  986. *
  987. * DEQUEUE_SLEEP - task is no longer runnable
  988. * ENQUEUE_WAKEUP - task just became runnable
  989. *
  990. * SAVE/RESTORE - an otherwise spurious dequeue/enqueue, done to ensure tasks
  991. * are in a known state which allows modification. Such pairs
  992. * should preserve as much state as possible.
  993. *
  994. * MOVE - paired with SAVE/RESTORE, explicitly does not preserve the location
  995. * in the runqueue.
  996. *
  997. * ENQUEUE_HEAD - place at front of runqueue (tail if not specified)
  998. * ENQUEUE_REPLENISH - CBS (replenish runtime and postpone deadline)
  999. * ENQUEUE_MIGRATED - the task was migrated during wakeup
  1000. *
  1001. */
  1002. #define DEQUEUE_SLEEP 0x01
  1003. #define DEQUEUE_SAVE 0x02 /* matches ENQUEUE_RESTORE */
  1004. #define DEQUEUE_MOVE 0x04 /* matches ENQUEUE_MOVE */
  1005. #define ENQUEUE_WAKEUP 0x01
  1006. #define ENQUEUE_RESTORE 0x02
  1007. #define ENQUEUE_MOVE 0x04
  1008. #define ENQUEUE_HEAD 0x08
  1009. #define ENQUEUE_REPLENISH 0x10
  1010. #ifdef CONFIG_SMP
  1011. #define ENQUEUE_MIGRATED 0x20
  1012. #else
  1013. #define ENQUEUE_MIGRATED 0x00
  1014. #endif
  1015. #define RETRY_TASK ((void *)-1UL)
  1016. struct sched_class {
  1017. const struct sched_class *next;
  1018. void (*enqueue_task) (struct rq *rq, struct task_struct *p, int flags);
  1019. void (*dequeue_task) (struct rq *rq, struct task_struct *p, int flags);
  1020. void (*yield_task) (struct rq *rq);
  1021. bool (*yield_to_task) (struct rq *rq, struct task_struct *p, bool preempt);
  1022. void (*check_preempt_curr) (struct rq *rq, struct task_struct *p, int flags);
  1023. /*
  1024. * It is the responsibility of the pick_next_task() method that will
  1025. * return the next task to call put_prev_task() on the @prev task or
  1026. * something equivalent.
  1027. *
  1028. * May return RETRY_TASK when it finds a higher prio class has runnable
  1029. * tasks.
  1030. */
  1031. struct task_struct * (*pick_next_task) (struct rq *rq,
  1032. struct task_struct *prev,
  1033. struct pin_cookie cookie);
  1034. void (*put_prev_task) (struct rq *rq, struct task_struct *p);
  1035. #ifdef CONFIG_SMP
  1036. int (*select_task_rq)(struct task_struct *p, int task_cpu, int sd_flag, int flags);
  1037. void (*migrate_task_rq)(struct task_struct *p);
  1038. void (*task_woken) (struct rq *this_rq, struct task_struct *task);
  1039. void (*set_cpus_allowed)(struct task_struct *p,
  1040. const struct cpumask *newmask);
  1041. void (*rq_online)(struct rq *rq);
  1042. void (*rq_offline)(struct rq *rq);
  1043. #endif
  1044. void (*set_curr_task) (struct rq *rq);
  1045. void (*task_tick) (struct rq *rq, struct task_struct *p, int queued);
  1046. void (*task_fork) (struct task_struct *p);
  1047. void (*task_dead) (struct task_struct *p);
  1048. /*
  1049. * The switched_from() call is allowed to drop rq->lock, therefore we
  1050. * cannot assume the switched_from/switched_to pair is serliazed by
  1051. * rq->lock. They are however serialized by p->pi_lock.
  1052. */
  1053. void (*switched_from) (struct rq *this_rq, struct task_struct *task);
  1054. void (*switched_to) (struct rq *this_rq, struct task_struct *task);
  1055. void (*prio_changed) (struct rq *this_rq, struct task_struct *task,
  1056. int oldprio);
  1057. unsigned int (*get_rr_interval) (struct rq *rq,
  1058. struct task_struct *task);
  1059. void (*update_curr) (struct rq *rq);
  1060. #define TASK_SET_GROUP 0
  1061. #define TASK_MOVE_GROUP 1
  1062. #ifdef CONFIG_FAIR_GROUP_SCHED
  1063. void (*task_change_group) (struct task_struct *p, int type);
  1064. #endif
  1065. };
  1066. static inline void put_prev_task(struct rq *rq, struct task_struct *prev)
  1067. {
  1068. prev->sched_class->put_prev_task(rq, prev);
  1069. }
  1070. static inline void set_curr_task(struct rq *rq, struct task_struct *curr)
  1071. {
  1072. curr->sched_class->set_curr_task(rq);
  1073. }
  1074. #define sched_class_highest (&stop_sched_class)
  1075. #define for_each_class(class) \
  1076. for (class = sched_class_highest; class; class = class->next)
  1077. extern const struct sched_class stop_sched_class;
  1078. extern const struct sched_class dl_sched_class;
  1079. extern const struct sched_class rt_sched_class;
  1080. extern const struct sched_class fair_sched_class;
  1081. extern const struct sched_class idle_sched_class;
  1082. #ifdef CONFIG_SMP
  1083. extern void update_group_capacity(struct sched_domain *sd, int cpu);
  1084. extern void trigger_load_balance(struct rq *rq);
  1085. extern void set_cpus_allowed_common(struct task_struct *p, const struct cpumask *new_mask);
  1086. #endif
  1087. #ifdef CONFIG_CPU_IDLE
  1088. static inline void idle_set_state(struct rq *rq,
  1089. struct cpuidle_state *idle_state)
  1090. {
  1091. rq->idle_state = idle_state;
  1092. }
  1093. static inline struct cpuidle_state *idle_get_state(struct rq *rq)
  1094. {
  1095. SCHED_WARN_ON(!rcu_read_lock_held());
  1096. return rq->idle_state;
  1097. }
  1098. #else
  1099. static inline void idle_set_state(struct rq *rq,
  1100. struct cpuidle_state *idle_state)
  1101. {
  1102. }
  1103. static inline struct cpuidle_state *idle_get_state(struct rq *rq)
  1104. {
  1105. return NULL;
  1106. }
  1107. #endif
  1108. extern void sysrq_sched_debug_show(void);
  1109. extern void sched_init_granularity(void);
  1110. extern void update_max_interval(void);
  1111. extern void init_sched_dl_class(void);
  1112. extern void init_sched_rt_class(void);
  1113. extern void init_sched_fair_class(void);
  1114. extern void resched_curr(struct rq *rq);
  1115. extern void resched_cpu(int cpu);
  1116. extern struct rt_bandwidth def_rt_bandwidth;
  1117. extern void init_rt_bandwidth(struct rt_bandwidth *rt_b, u64 period, u64 runtime);
  1118. extern struct dl_bandwidth def_dl_bandwidth;
  1119. extern void init_dl_bandwidth(struct dl_bandwidth *dl_b, u64 period, u64 runtime);
  1120. extern void init_dl_task_timer(struct sched_dl_entity *dl_se);
  1121. unsigned long to_ratio(u64 period, u64 runtime);
  1122. extern void init_entity_runnable_average(struct sched_entity *se);
  1123. extern void post_init_entity_util_avg(struct sched_entity *se);
  1124. #ifdef CONFIG_NO_HZ_FULL
  1125. extern bool sched_can_stop_tick(struct rq *rq);
  1126. /*
  1127. * Tick may be needed by tasks in the runqueue depending on their policy and
  1128. * requirements. If tick is needed, lets send the target an IPI to kick it out of
  1129. * nohz mode if necessary.
  1130. */
  1131. static inline void sched_update_tick_dependency(struct rq *rq)
  1132. {
  1133. int cpu;
  1134. if (!tick_nohz_full_enabled())
  1135. return;
  1136. cpu = cpu_of(rq);
  1137. if (!tick_nohz_full_cpu(cpu))
  1138. return;
  1139. if (sched_can_stop_tick(rq))
  1140. tick_nohz_dep_clear_cpu(cpu, TICK_DEP_BIT_SCHED);
  1141. else
  1142. tick_nohz_dep_set_cpu(cpu, TICK_DEP_BIT_SCHED);
  1143. }
  1144. #else
  1145. static inline void sched_update_tick_dependency(struct rq *rq) { }
  1146. #endif
  1147. static inline void add_nr_running(struct rq *rq, unsigned count)
  1148. {
  1149. unsigned prev_nr = rq->nr_running;
  1150. rq->nr_running = prev_nr + count;
  1151. if (prev_nr < 2 && rq->nr_running >= 2) {
  1152. #ifdef CONFIG_SMP
  1153. if (!rq->rd->overload)
  1154. rq->rd->overload = true;
  1155. #endif
  1156. }
  1157. sched_update_tick_dependency(rq);
  1158. }
  1159. static inline void sub_nr_running(struct rq *rq, unsigned count)
  1160. {
  1161. rq->nr_running -= count;
  1162. /* Check if we still need preemption */
  1163. sched_update_tick_dependency(rq);
  1164. }
  1165. static inline void rq_last_tick_reset(struct rq *rq)
  1166. {
  1167. #ifdef CONFIG_NO_HZ_FULL
  1168. rq->last_sched_tick = jiffies;
  1169. #endif
  1170. }
  1171. extern void update_rq_clock(struct rq *rq);
  1172. extern void activate_task(struct rq *rq, struct task_struct *p, int flags);
  1173. extern void deactivate_task(struct rq *rq, struct task_struct *p, int flags);
  1174. extern void check_preempt_curr(struct rq *rq, struct task_struct *p, int flags);
  1175. extern const_debug unsigned int sysctl_sched_time_avg;
  1176. extern const_debug unsigned int sysctl_sched_nr_migrate;
  1177. extern const_debug unsigned int sysctl_sched_migration_cost;
  1178. static inline u64 sched_avg_period(void)
  1179. {
  1180. return (u64)sysctl_sched_time_avg * NSEC_PER_MSEC / 2;
  1181. }
  1182. #ifdef CONFIG_SCHED_HRTICK
  1183. /*
  1184. * Use hrtick when:
  1185. * - enabled by features
  1186. * - hrtimer is actually high res
  1187. */
  1188. static inline int hrtick_enabled(struct rq *rq)
  1189. {
  1190. if (!sched_feat(HRTICK))
  1191. return 0;
  1192. if (!cpu_active(cpu_of(rq)))
  1193. return 0;
  1194. return hrtimer_is_hres_active(&rq->hrtick_timer);
  1195. }
  1196. void hrtick_start(struct rq *rq, u64 delay);
  1197. #else
  1198. static inline int hrtick_enabled(struct rq *rq)
  1199. {
  1200. return 0;
  1201. }
  1202. #endif /* CONFIG_SCHED_HRTICK */
  1203. #ifdef CONFIG_SMP
  1204. extern void sched_avg_update(struct rq *rq);
  1205. #ifndef arch_scale_freq_capacity
  1206. static __always_inline
  1207. unsigned long arch_scale_freq_capacity(struct sched_domain *sd, int cpu)
  1208. {
  1209. return SCHED_CAPACITY_SCALE;
  1210. }
  1211. #endif
  1212. #ifndef arch_scale_cpu_capacity
  1213. static __always_inline
  1214. unsigned long arch_scale_cpu_capacity(struct sched_domain *sd, int cpu)
  1215. {
  1216. if (sd && (sd->flags & SD_SHARE_CPUCAPACITY) && (sd->span_weight > 1))
  1217. return sd->smt_gain / sd->span_weight;
  1218. return SCHED_CAPACITY_SCALE;
  1219. }
  1220. #endif
  1221. static inline void sched_rt_avg_update(struct rq *rq, u64 rt_delta)
  1222. {
  1223. rq->rt_avg += rt_delta * arch_scale_freq_capacity(NULL, cpu_of(rq));
  1224. sched_avg_update(rq);
  1225. }
  1226. #else
  1227. static inline void sched_rt_avg_update(struct rq *rq, u64 rt_delta) { }
  1228. static inline void sched_avg_update(struct rq *rq) { }
  1229. #endif
  1230. struct rq_flags {
  1231. unsigned long flags;
  1232. struct pin_cookie cookie;
  1233. };
  1234. struct rq *__task_rq_lock(struct task_struct *p, struct rq_flags *rf)
  1235. __acquires(rq->lock);
  1236. struct rq *task_rq_lock(struct task_struct *p, struct rq_flags *rf)
  1237. __acquires(p->pi_lock)
  1238. __acquires(rq->lock);
  1239. static inline void __task_rq_unlock(struct rq *rq, struct rq_flags *rf)
  1240. __releases(rq->lock)
  1241. {
  1242. lockdep_unpin_lock(&rq->lock, rf->cookie);
  1243. raw_spin_unlock(&rq->lock);
  1244. }
  1245. static inline void
  1246. task_rq_unlock(struct rq *rq, struct task_struct *p, struct rq_flags *rf)
  1247. __releases(rq->lock)
  1248. __releases(p->pi_lock)
  1249. {
  1250. lockdep_unpin_lock(&rq->lock, rf->cookie);
  1251. raw_spin_unlock(&rq->lock);
  1252. raw_spin_unlock_irqrestore(&p->pi_lock, rf->flags);
  1253. }
  1254. #ifdef CONFIG_SMP
  1255. #ifdef CONFIG_PREEMPT
  1256. static inline void double_rq_lock(struct rq *rq1, struct rq *rq2);
  1257. /*
  1258. * fair double_lock_balance: Safely acquires both rq->locks in a fair
  1259. * way at the expense of forcing extra atomic operations in all
  1260. * invocations. This assures that the double_lock is acquired using the
  1261. * same underlying policy as the spinlock_t on this architecture, which
  1262. * reduces latency compared to the unfair variant below. However, it
  1263. * also adds more overhead and therefore may reduce throughput.
  1264. */
  1265. static inline int _double_lock_balance(struct rq *this_rq, struct rq *busiest)
  1266. __releases(this_rq->lock)
  1267. __acquires(busiest->lock)
  1268. __acquires(this_rq->lock)
  1269. {
  1270. raw_spin_unlock(&this_rq->lock);
  1271. double_rq_lock(this_rq, busiest);
  1272. return 1;
  1273. }
  1274. #else
  1275. /*
  1276. * Unfair double_lock_balance: Optimizes throughput at the expense of
  1277. * latency by eliminating extra atomic operations when the locks are
  1278. * already in proper order on entry. This favors lower cpu-ids and will
  1279. * grant the double lock to lower cpus over higher ids under contention,
  1280. * regardless of entry order into the function.
  1281. */
  1282. static inline int _double_lock_balance(struct rq *this_rq, struct rq *busiest)
  1283. __releases(this_rq->lock)
  1284. __acquires(busiest->lock)
  1285. __acquires(this_rq->lock)
  1286. {
  1287. int ret = 0;
  1288. if (unlikely(!raw_spin_trylock(&busiest->lock))) {
  1289. if (busiest < this_rq) {
  1290. raw_spin_unlock(&this_rq->lock);
  1291. raw_spin_lock(&busiest->lock);
  1292. raw_spin_lock_nested(&this_rq->lock,
  1293. SINGLE_DEPTH_NESTING);
  1294. ret = 1;
  1295. } else
  1296. raw_spin_lock_nested(&busiest->lock,
  1297. SINGLE_DEPTH_NESTING);
  1298. }
  1299. return ret;
  1300. }
  1301. #endif /* CONFIG_PREEMPT */
  1302. /*
  1303. * double_lock_balance - lock the busiest runqueue, this_rq is locked already.
  1304. */
  1305. static inline int double_lock_balance(struct rq *this_rq, struct rq *busiest)
  1306. {
  1307. if (unlikely(!irqs_disabled())) {
  1308. /* printk() doesn't work good under rq->lock */
  1309. raw_spin_unlock(&this_rq->lock);
  1310. BUG_ON(1);
  1311. }
  1312. return _double_lock_balance(this_rq, busiest);
  1313. }
  1314. static inline void double_unlock_balance(struct rq *this_rq, struct rq *busiest)
  1315. __releases(busiest->lock)
  1316. {
  1317. raw_spin_unlock(&busiest->lock);
  1318. lock_set_subclass(&this_rq->lock.dep_map, 0, _RET_IP_);
  1319. }
  1320. static inline void double_lock(spinlock_t *l1, spinlock_t *l2)
  1321. {
  1322. if (l1 > l2)
  1323. swap(l1, l2);
  1324. spin_lock(l1);
  1325. spin_lock_nested(l2, SINGLE_DEPTH_NESTING);
  1326. }
  1327. static inline void double_lock_irq(spinlock_t *l1, spinlock_t *l2)
  1328. {
  1329. if (l1 > l2)
  1330. swap(l1, l2);
  1331. spin_lock_irq(l1);
  1332. spin_lock_nested(l2, SINGLE_DEPTH_NESTING);
  1333. }
  1334. static inline void double_raw_lock(raw_spinlock_t *l1, raw_spinlock_t *l2)
  1335. {
  1336. if (l1 > l2)
  1337. swap(l1, l2);
  1338. raw_spin_lock(l1);
  1339. raw_spin_lock_nested(l2, SINGLE_DEPTH_NESTING);
  1340. }
  1341. /*
  1342. * double_rq_lock - safely lock two runqueues
  1343. *
  1344. * Note this does not disable interrupts like task_rq_lock,
  1345. * you need to do so manually before calling.
  1346. */
  1347. static inline void double_rq_lock(struct rq *rq1, struct rq *rq2)
  1348. __acquires(rq1->lock)
  1349. __acquires(rq2->lock)
  1350. {
  1351. BUG_ON(!irqs_disabled());
  1352. if (rq1 == rq2) {
  1353. raw_spin_lock(&rq1->lock);
  1354. __acquire(rq2->lock); /* Fake it out ;) */
  1355. } else {
  1356. if (rq1 < rq2) {
  1357. raw_spin_lock(&rq1->lock);
  1358. raw_spin_lock_nested(&rq2->lock, SINGLE_DEPTH_NESTING);
  1359. } else {
  1360. raw_spin_lock(&rq2->lock);
  1361. raw_spin_lock_nested(&rq1->lock, SINGLE_DEPTH_NESTING);
  1362. }
  1363. }
  1364. }
  1365. /*
  1366. * double_rq_unlock - safely unlock two runqueues
  1367. *
  1368. * Note this does not restore interrupts like task_rq_unlock,
  1369. * you need to do so manually after calling.
  1370. */
  1371. static inline void double_rq_unlock(struct rq *rq1, struct rq *rq2)
  1372. __releases(rq1->lock)
  1373. __releases(rq2->lock)
  1374. {
  1375. raw_spin_unlock(&rq1->lock);
  1376. if (rq1 != rq2)
  1377. raw_spin_unlock(&rq2->lock);
  1378. else
  1379. __release(rq2->lock);
  1380. }
  1381. #else /* CONFIG_SMP */
  1382. /*
  1383. * double_rq_lock - safely lock two runqueues
  1384. *
  1385. * Note this does not disable interrupts like task_rq_lock,
  1386. * you need to do so manually before calling.
  1387. */
  1388. static inline void double_rq_lock(struct rq *rq1, struct rq *rq2)
  1389. __acquires(rq1->lock)
  1390. __acquires(rq2->lock)
  1391. {
  1392. BUG_ON(!irqs_disabled());
  1393. BUG_ON(rq1 != rq2);
  1394. raw_spin_lock(&rq1->lock);
  1395. __acquire(rq2->lock); /* Fake it out ;) */
  1396. }
  1397. /*
  1398. * double_rq_unlock - safely unlock two runqueues
  1399. *
  1400. * Note this does not restore interrupts like task_rq_unlock,
  1401. * you need to do so manually after calling.
  1402. */
  1403. static inline void double_rq_unlock(struct rq *rq1, struct rq *rq2)
  1404. __releases(rq1->lock)
  1405. __releases(rq2->lock)
  1406. {
  1407. BUG_ON(rq1 != rq2);
  1408. raw_spin_unlock(&rq1->lock);
  1409. __release(rq2->lock);
  1410. }
  1411. #endif
  1412. extern struct sched_entity *__pick_first_entity(struct cfs_rq *cfs_rq);
  1413. extern struct sched_entity *__pick_last_entity(struct cfs_rq *cfs_rq);
  1414. #ifdef CONFIG_SCHED_DEBUG
  1415. extern void print_cfs_stats(struct seq_file *m, int cpu);
  1416. extern void print_rt_stats(struct seq_file *m, int cpu);
  1417. extern void print_dl_stats(struct seq_file *m, int cpu);
  1418. extern void
  1419. print_cfs_rq(struct seq_file *m, int cpu, struct cfs_rq *cfs_rq);
  1420. #ifdef CONFIG_NUMA_BALANCING
  1421. extern void
  1422. show_numa_stats(struct task_struct *p, struct seq_file *m);
  1423. extern void
  1424. print_numa_stats(struct seq_file *m, int node, unsigned long tsf,
  1425. unsigned long tpf, unsigned long gsf, unsigned long gpf);
  1426. #endif /* CONFIG_NUMA_BALANCING */
  1427. #endif /* CONFIG_SCHED_DEBUG */
  1428. extern void init_cfs_rq(struct cfs_rq *cfs_rq);
  1429. extern void init_rt_rq(struct rt_rq *rt_rq);
  1430. extern void init_dl_rq(struct dl_rq *dl_rq);
  1431. extern void cfs_bandwidth_usage_inc(void);
  1432. extern void cfs_bandwidth_usage_dec(void);
  1433. #ifdef CONFIG_NO_HZ_COMMON
  1434. enum rq_nohz_flag_bits {
  1435. NOHZ_TICK_STOPPED,
  1436. NOHZ_BALANCE_KICK,
  1437. };
  1438. #define nohz_flags(cpu) (&cpu_rq(cpu)->nohz_flags)
  1439. extern void nohz_balance_exit_idle(unsigned int cpu);
  1440. #else
  1441. static inline void nohz_balance_exit_idle(unsigned int cpu) { }
  1442. #endif
  1443. #ifdef CONFIG_IRQ_TIME_ACCOUNTING
  1444. struct irqtime {
  1445. u64 hardirq_time;
  1446. u64 softirq_time;
  1447. u64 irq_start_time;
  1448. struct u64_stats_sync sync;
  1449. };
  1450. DECLARE_PER_CPU(struct irqtime, cpu_irqtime);
  1451. static inline u64 irq_time_read(int cpu)
  1452. {
  1453. struct irqtime *irqtime = &per_cpu(cpu_irqtime, cpu);
  1454. unsigned int seq;
  1455. u64 total;
  1456. do {
  1457. seq = __u64_stats_fetch_begin(&irqtime->sync);
  1458. total = irqtime->softirq_time + irqtime->hardirq_time;
  1459. } while (__u64_stats_fetch_retry(&irqtime->sync, seq));
  1460. return total;
  1461. }
  1462. #endif /* CONFIG_IRQ_TIME_ACCOUNTING */
  1463. #ifdef CONFIG_CPU_FREQ
  1464. DECLARE_PER_CPU(struct update_util_data *, cpufreq_update_util_data);
  1465. /**
  1466. * cpufreq_update_util - Take a note about CPU utilization changes.
  1467. * @rq: Runqueue to carry out the update for.
  1468. * @flags: Update reason flags.
  1469. *
  1470. * This function is called by the scheduler on the CPU whose utilization is
  1471. * being updated.
  1472. *
  1473. * It can only be called from RCU-sched read-side critical sections.
  1474. *
  1475. * The way cpufreq is currently arranged requires it to evaluate the CPU
  1476. * performance state (frequency/voltage) on a regular basis to prevent it from
  1477. * being stuck in a completely inadequate performance level for too long.
  1478. * That is not guaranteed to happen if the updates are only triggered from CFS,
  1479. * though, because they may not be coming in if RT or deadline tasks are active
  1480. * all the time (or there are RT and DL tasks only).
  1481. *
  1482. * As a workaround for that issue, this function is called by the RT and DL
  1483. * sched classes to trigger extra cpufreq updates to prevent it from stalling,
  1484. * but that really is a band-aid. Going forward it should be replaced with
  1485. * solutions targeted more specifically at RT and DL tasks.
  1486. */
  1487. static inline void cpufreq_update_util(struct rq *rq, unsigned int flags)
  1488. {
  1489. struct update_util_data *data;
  1490. data = rcu_dereference_sched(*this_cpu_ptr(&cpufreq_update_util_data));
  1491. if (data)
  1492. data->func(data, rq_clock(rq), flags);
  1493. }
  1494. static inline void cpufreq_update_this_cpu(struct rq *rq, unsigned int flags)
  1495. {
  1496. if (cpu_of(rq) == smp_processor_id())
  1497. cpufreq_update_util(rq, flags);
  1498. }
  1499. #else
  1500. static inline void cpufreq_update_util(struct rq *rq, unsigned int flags) {}
  1501. static inline void cpufreq_update_this_cpu(struct rq *rq, unsigned int flags) {}
  1502. #endif /* CONFIG_CPU_FREQ */
  1503. #ifdef arch_scale_freq_capacity
  1504. #ifndef arch_scale_freq_invariant
  1505. #define arch_scale_freq_invariant() (true)
  1506. #endif
  1507. #else /* arch_scale_freq_capacity */
  1508. #define arch_scale_freq_invariant() (false)
  1509. #endif