topology.c 58 KB

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281291301311321331341351361371381391401411421431441451461471481491501511521531541551561571581591601611621631641651661671681691701711721731741751761771781791801811821831841851861871881891901911921931941951961971981992002012022032042052062072082092102112122132142152162172182192202212222232242252262272282292302312322332342352362372382392402412422432442452462472482492502512522532542552562572582592602612622632642652662672682692702712722732742752762772782792802812822832842852862872882892902912922932942952962972982993003013023033043053063073083093103113123133143153163173183193203213223233243253263273283293303313323333343353363373383393403413423433443453463473483493503513523533543553563573583593603613623633643653663673683693703713723733743753763773783793803813823833843853863873883893903913923933943953963973983994004014024034044054064074084094104114124134144154164174184194204214224234244254264274284294304314324334344354364374384394404414424434444454464474484494504514524534544554564574584594604614624634644654664674684694704714724734744754764774784794804814824834844854864874884894904914924934944954964974984995005015025035045055065075085095105115125135145155165175185195205215225235245255265275285295305315325335345355365375385395405415425435445455465475485495505515525535545555565575585595605615625635645655665675685695705715725735745755765775785795805815825835845855865875885895905915925935945955965975985996006016026036046056066076086096106116126136146156166176186196206216226236246256266276286296306316326336346356366376386396406416426436446456466476486496506516526536546556566576586596606616626636646656666676686696706716726736746756766776786796806816826836846856866876886896906916926936946956966976986997007017027037047057067077087097107117127137147157167177187197207217227237247257267277287297307317327337347357367377387397407417427437447457467477487497507517527537547557567577587597607617627637647657667677687697707717727737747757767777787797807817827837847857867877887897907917927937947957967977987998008018028038048058068078088098108118128138148158168178188198208218228238248258268278288298308318328338348358368378388398408418428438448458468478488498508518528538548558568578588598608618628638648658668678688698708718728738748758768778788798808818828838848858868878888898908918928938948958968978988999009019029039049059069079089099109119129139149159169179189199209219229239249259269279289299309319329339349359369379389399409419429439449459469479489499509519529539549559569579589599609619629639649659669679689699709719729739749759769779789799809819829839849859869879889899909919929939949959969979989991000100110021003100410051006100710081009101010111012101310141015101610171018101910201021102210231024102510261027102810291030103110321033103410351036103710381039104010411042104310441045104610471048104910501051105210531054105510561057105810591060106110621063106410651066106710681069107010711072107310741075107610771078107910801081108210831084108510861087108810891090109110921093109410951096109710981099110011011102110311041105110611071108110911101111111211131114111511161117111811191120112111221123112411251126112711281129113011311132113311341135113611371138113911401141114211431144114511461147114811491150115111521153115411551156115711581159116011611162116311641165116611671168116911701171117211731174117511761177117811791180118111821183118411851186118711881189119011911192119311941195119611971198119912001201120212031204120512061207120812091210121112121213121412151216121712181219122012211222122312241225122612271228122912301231123212331234123512361237123812391240124112421243124412451246124712481249125012511252125312541255125612571258125912601261126212631264126512661267126812691270127112721273127412751276127712781279128012811282128312841285128612871288128912901291129212931294129512961297129812991300130113021303130413051306130713081309131013111312131313141315131613171318131913201321132213231324132513261327132813291330133113321333133413351336133713381339134013411342134313441345134613471348134913501351135213531354135513561357135813591360136113621363136413651366136713681369137013711372137313741375137613771378137913801381138213831384138513861387138813891390139113921393139413951396139713981399140014011402140314041405140614071408140914101411141214131414141514161417141814191420142114221423142414251426142714281429143014311432143314341435143614371438143914401441144214431444144514461447144814491450145114521453145414551456145714581459146014611462146314641465146614671468146914701471147214731474147514761477147814791480148114821483148414851486148714881489149014911492149314941495149614971498149915001501150215031504150515061507150815091510151115121513151415151516151715181519152015211522152315241525152615271528152915301531153215331534153515361537153815391540154115421543154415451546154715481549155015511552155315541555155615571558155915601561156215631564156515661567156815691570157115721573157415751576157715781579158015811582158315841585158615871588158915901591159215931594159515961597159815991600160116021603160416051606160716081609161016111612161316141615161616171618161916201621162216231624162516261627162816291630163116321633163416351636163716381639164016411642164316441645164616471648164916501651165216531654165516561657165816591660166116621663166416651666166716681669167016711672167316741675167616771678167916801681168216831684168516861687168816891690169116921693169416951696169716981699170017011702170317041705170617071708170917101711171217131714171517161717171817191720172117221723172417251726172717281729173017311732173317341735173617371738173917401741174217431744174517461747174817491750175117521753175417551756175717581759176017611762176317641765176617671768176917701771177217731774177517761777177817791780178117821783178417851786178717881789179017911792179317941795179617971798179918001801180218031804180518061807180818091810181118121813181418151816181718181819182018211822182318241825182618271828182918301831183218331834183518361837183818391840184118421843184418451846184718481849185018511852185318541855185618571858185918601861186218631864186518661867186818691870187118721873187418751876187718781879188018811882188318841885188618871888188918901891189218931894189518961897189818991900190119021903190419051906190719081909191019111912191319141915191619171918191919201921192219231924192519261927192819291930193119321933193419351936193719381939194019411942194319441945194619471948194919501951195219531954195519561957195819591960196119621963196419651966196719681969197019711972197319741975197619771978197919801981198219831984198519861987198819891990199119921993199419951996199719981999200020012002200320042005200620072008200920102011201220132014201520162017201820192020202120222023202420252026202720282029203020312032203320342035203620372038203920402041204220432044204520462047204820492050205120522053205420552056205720582059206020612062206320642065206620672068206920702071207220732074207520762077207820792080208120822083208420852086208720882089209020912092209320942095209620972098209921002101210221032104210521062107210821092110211121122113211421152116211721182119212021212122212321242125212621272128212921302131213221332134213521362137213821392140214121422143214421452146214721482149215021512152215321542155215621572158215921602161216221632164216521662167216821692170217121722173217421752176217721782179218021812182218321842185218621872188218921902191219221932194219521962197219821992200220122022203220422052206220722082209221022112212221322142215221622172218221922202221222222232224222522262227222822292230223122322233223422352236223722382239224022412242224322442245224622472248224922502251225222532254225522562257225822592260226122622263226422652266226722682269227022712272227322742275227622772278227922802281228222832284228522862287228822892290229122922293229422952296229722982299230023012302230323042305230623072308230923102311231223132314231523162317231823192320
  1. // SPDX-License-Identifier: GPL-2.0
  2. /*
  3. * Scheduler topology setup/handling methods
  4. */
  5. #include "sched.h"
  6. #include <trace/hooks/sched.h>
  7. DEFINE_MUTEX(sched_domains_mutex);
  8. #ifdef CONFIG_LOCKDEP
  9. EXPORT_SYMBOL_GPL(sched_domains_mutex);
  10. #endif
  11. /* Protected by sched_domains_mutex: */
  12. static cpumask_var_t sched_domains_tmpmask;
  13. static cpumask_var_t sched_domains_tmpmask2;
  14. #ifdef CONFIG_SCHED_DEBUG
  15. static int __init sched_debug_setup(char *str)
  16. {
  17. sched_debug_enabled = true;
  18. return 0;
  19. }
  20. early_param("sched_debug", sched_debug_setup);
  21. static inline bool sched_debug(void)
  22. {
  23. return sched_debug_enabled;
  24. }
  25. #define SD_FLAG(_name, mflags) [__##_name] = { .meta_flags = mflags, .name = #_name },
  26. const struct sd_flag_debug sd_flag_debug[] = {
  27. #include <linux/sched/sd_flags.h>
  28. };
  29. #undef SD_FLAG
  30. static int sched_domain_debug_one(struct sched_domain *sd, int cpu, int level,
  31. struct cpumask *groupmask)
  32. {
  33. struct sched_group *group = sd->groups;
  34. unsigned long flags = sd->flags;
  35. unsigned int idx;
  36. cpumask_clear(groupmask);
  37. printk(KERN_DEBUG "%*s domain-%d: ", level, "", level);
  38. printk(KERN_CONT "span=%*pbl level=%s\n",
  39. cpumask_pr_args(sched_domain_span(sd)), sd->name);
  40. if (!cpumask_test_cpu(cpu, sched_domain_span(sd))) {
  41. printk(KERN_ERR "ERROR: domain->span does not contain CPU%d\n", cpu);
  42. }
  43. if (group && !cpumask_test_cpu(cpu, sched_group_span(group))) {
  44. printk(KERN_ERR "ERROR: domain->groups does not contain CPU%d\n", cpu);
  45. }
  46. for_each_set_bit(idx, &flags, __SD_FLAG_CNT) {
  47. unsigned int flag = BIT(idx);
  48. unsigned int meta_flags = sd_flag_debug[idx].meta_flags;
  49. if ((meta_flags & SDF_SHARED_CHILD) && sd->child &&
  50. !(sd->child->flags & flag))
  51. printk(KERN_ERR "ERROR: flag %s set here but not in child\n",
  52. sd_flag_debug[idx].name);
  53. if ((meta_flags & SDF_SHARED_PARENT) && sd->parent &&
  54. !(sd->parent->flags & flag))
  55. printk(KERN_ERR "ERROR: flag %s set here but not in parent\n",
  56. sd_flag_debug[idx].name);
  57. }
  58. printk(KERN_DEBUG "%*s groups:", level + 1, "");
  59. do {
  60. if (!group) {
  61. printk("\n");
  62. printk(KERN_ERR "ERROR: group is NULL\n");
  63. break;
  64. }
  65. if (!cpumask_weight(sched_group_span(group))) {
  66. printk(KERN_CONT "\n");
  67. printk(KERN_ERR "ERROR: empty group\n");
  68. break;
  69. }
  70. if (!(sd->flags & SD_OVERLAP) &&
  71. cpumask_intersects(groupmask, sched_group_span(group))) {
  72. printk(KERN_CONT "\n");
  73. printk(KERN_ERR "ERROR: repeated CPUs\n");
  74. break;
  75. }
  76. cpumask_or(groupmask, groupmask, sched_group_span(group));
  77. printk(KERN_CONT " %d:{ span=%*pbl",
  78. group->sgc->id,
  79. cpumask_pr_args(sched_group_span(group)));
  80. if ((sd->flags & SD_OVERLAP) &&
  81. !cpumask_equal(group_balance_mask(group), sched_group_span(group))) {
  82. printk(KERN_CONT " mask=%*pbl",
  83. cpumask_pr_args(group_balance_mask(group)));
  84. }
  85. if (group->sgc->capacity != SCHED_CAPACITY_SCALE)
  86. printk(KERN_CONT " cap=%lu", group->sgc->capacity);
  87. if (group == sd->groups && sd->child &&
  88. !cpumask_equal(sched_domain_span(sd->child),
  89. sched_group_span(group))) {
  90. printk(KERN_ERR "ERROR: domain->groups does not match domain->child\n");
  91. }
  92. printk(KERN_CONT " }");
  93. group = group->next;
  94. if (group != sd->groups)
  95. printk(KERN_CONT ",");
  96. } while (group != sd->groups);
  97. printk(KERN_CONT "\n");
  98. if (!cpumask_equal(sched_domain_span(sd), groupmask))
  99. printk(KERN_ERR "ERROR: groups don't span domain->span\n");
  100. if (sd->parent &&
  101. !cpumask_subset(groupmask, sched_domain_span(sd->parent)))
  102. printk(KERN_ERR "ERROR: parent span is not a superset of domain->span\n");
  103. return 0;
  104. }
  105. static void sched_domain_debug(struct sched_domain *sd, int cpu)
  106. {
  107. int level = 0;
  108. if (!sched_debug_enabled)
  109. return;
  110. if (!sd) {
  111. printk(KERN_DEBUG "CPU%d attaching NULL sched-domain.\n", cpu);
  112. return;
  113. }
  114. printk(KERN_DEBUG "CPU%d attaching sched-domain(s):\n", cpu);
  115. for (;;) {
  116. if (sched_domain_debug_one(sd, cpu, level, sched_domains_tmpmask))
  117. break;
  118. level++;
  119. sd = sd->parent;
  120. if (!sd)
  121. break;
  122. }
  123. }
  124. #else /* !CONFIG_SCHED_DEBUG */
  125. # define sched_debug_enabled 0
  126. # define sched_domain_debug(sd, cpu) do { } while (0)
  127. static inline bool sched_debug(void)
  128. {
  129. return false;
  130. }
  131. #endif /* CONFIG_SCHED_DEBUG */
  132. /* Generate a mask of SD flags with the SDF_NEEDS_GROUPS metaflag */
  133. #define SD_FLAG(name, mflags) (name * !!((mflags) & SDF_NEEDS_GROUPS)) |
  134. static const unsigned int SD_DEGENERATE_GROUPS_MASK =
  135. #include <linux/sched/sd_flags.h>
  136. 0;
  137. #undef SD_FLAG
  138. static int sd_degenerate(struct sched_domain *sd)
  139. {
  140. if (cpumask_weight(sched_domain_span(sd)) == 1)
  141. return 1;
  142. /* Following flags need at least 2 groups */
  143. if ((sd->flags & SD_DEGENERATE_GROUPS_MASK) &&
  144. (sd->groups != sd->groups->next))
  145. return 0;
  146. /* Following flags don't use groups */
  147. if (sd->flags & (SD_WAKE_AFFINE))
  148. return 0;
  149. return 1;
  150. }
  151. static int
  152. sd_parent_degenerate(struct sched_domain *sd, struct sched_domain *parent)
  153. {
  154. unsigned long cflags = sd->flags, pflags = parent->flags;
  155. if (sd_degenerate(parent))
  156. return 1;
  157. if (!cpumask_equal(sched_domain_span(sd), sched_domain_span(parent)))
  158. return 0;
  159. /* Flags needing groups don't count if only 1 group in parent */
  160. if (parent->groups == parent->groups->next)
  161. pflags &= ~SD_DEGENERATE_GROUPS_MASK;
  162. if (~cflags & pflags)
  163. return 0;
  164. return 1;
  165. }
  166. #if defined(CONFIG_ENERGY_MODEL) && defined(CONFIG_CPU_FREQ_GOV_SCHEDUTIL)
  167. DEFINE_STATIC_KEY_FALSE(sched_energy_present);
  168. unsigned int sysctl_sched_energy_aware = 1;
  169. DEFINE_MUTEX(sched_energy_mutex);
  170. bool sched_energy_update;
  171. #ifdef CONFIG_PROC_SYSCTL
  172. int sched_energy_aware_handler(struct ctl_table *table, int write,
  173. void *buffer, size_t *lenp, loff_t *ppos)
  174. {
  175. int ret, state;
  176. if (write && !capable(CAP_SYS_ADMIN))
  177. return -EPERM;
  178. ret = proc_dointvec_minmax(table, write, buffer, lenp, ppos);
  179. if (!ret && write) {
  180. state = static_branch_unlikely(&sched_energy_present);
  181. if (state != sysctl_sched_energy_aware) {
  182. mutex_lock(&sched_energy_mutex);
  183. sched_energy_update = 1;
  184. rebuild_sched_domains();
  185. sched_energy_update = 0;
  186. mutex_unlock(&sched_energy_mutex);
  187. }
  188. }
  189. return ret;
  190. }
  191. #endif
  192. static void free_pd(struct perf_domain *pd)
  193. {
  194. struct perf_domain *tmp;
  195. while (pd) {
  196. tmp = pd->next;
  197. kfree(pd);
  198. pd = tmp;
  199. }
  200. }
  201. static struct perf_domain *find_pd(struct perf_domain *pd, int cpu)
  202. {
  203. while (pd) {
  204. if (cpumask_test_cpu(cpu, perf_domain_span(pd)))
  205. return pd;
  206. pd = pd->next;
  207. }
  208. return NULL;
  209. }
  210. static struct perf_domain *pd_init(int cpu)
  211. {
  212. struct em_perf_domain *obj = em_cpu_get(cpu);
  213. struct perf_domain *pd;
  214. if (!obj) {
  215. if (sched_debug())
  216. pr_info("%s: no EM found for CPU%d\n", __func__, cpu);
  217. return NULL;
  218. }
  219. pd = kzalloc(sizeof(*pd), GFP_KERNEL);
  220. if (!pd)
  221. return NULL;
  222. pd->em_pd = obj;
  223. return pd;
  224. }
  225. static void perf_domain_debug(const struct cpumask *cpu_map,
  226. struct perf_domain *pd)
  227. {
  228. if (!sched_debug() || !pd)
  229. return;
  230. printk(KERN_DEBUG "root_domain %*pbl:", cpumask_pr_args(cpu_map));
  231. while (pd) {
  232. printk(KERN_CONT " pd%d:{ cpus=%*pbl nr_pstate=%d }",
  233. cpumask_first(perf_domain_span(pd)),
  234. cpumask_pr_args(perf_domain_span(pd)),
  235. em_pd_nr_perf_states(pd->em_pd));
  236. pd = pd->next;
  237. }
  238. printk(KERN_CONT "\n");
  239. }
  240. static void destroy_perf_domain_rcu(struct rcu_head *rp)
  241. {
  242. struct perf_domain *pd;
  243. pd = container_of(rp, struct perf_domain, rcu);
  244. free_pd(pd);
  245. }
  246. static void sched_energy_set(bool has_eas)
  247. {
  248. if (!has_eas && static_branch_unlikely(&sched_energy_present)) {
  249. if (sched_debug())
  250. pr_info("%s: stopping EAS\n", __func__);
  251. static_branch_disable_cpuslocked(&sched_energy_present);
  252. } else if (has_eas && !static_branch_unlikely(&sched_energy_present)) {
  253. if (sched_debug())
  254. pr_info("%s: starting EAS\n", __func__);
  255. static_branch_enable_cpuslocked(&sched_energy_present);
  256. }
  257. }
  258. /*
  259. * EAS can be used on a root domain if it meets all the following conditions:
  260. * 1. an Energy Model (EM) is available;
  261. * 2. the SD_ASYM_CPUCAPACITY flag is set in the sched_domain hierarchy.
  262. * 3. no SMT is detected.
  263. * 4. the EM complexity is low enough to keep scheduling overheads low;
  264. *
  265. * The complexity of the Energy Model is defined as:
  266. *
  267. * C = nr_pd * (nr_cpus + nr_ps)
  268. *
  269. * with parameters defined as:
  270. * - nr_pd: the number of performance domains
  271. * - nr_cpus: the number of CPUs
  272. * - nr_ps: the sum of the number of performance states of all performance
  273. * domains (for example, on a system with 2 performance domains,
  274. * with 10 performance states each, nr_ps = 2 * 10 = 20).
  275. *
  276. * It is generally not a good idea to use such a model in the wake-up path on
  277. * very complex platforms because of the associated scheduling overheads. The
  278. * arbitrary constraint below prevents that. It makes EAS usable up to 16 CPUs
  279. * with per-CPU DVFS and less than 8 performance states each, for example.
  280. */
  281. #define EM_MAX_COMPLEXITY 2048
  282. static bool build_perf_domains(const struct cpumask *cpu_map)
  283. {
  284. int i, nr_pd = 0, nr_ps = 0, nr_cpus = cpumask_weight(cpu_map);
  285. struct perf_domain *pd = NULL, *tmp;
  286. int cpu = cpumask_first(cpu_map);
  287. struct root_domain *rd = cpu_rq(cpu)->rd;
  288. bool eas_check = false;
  289. if (!sysctl_sched_energy_aware)
  290. goto free;
  291. /*
  292. * EAS is enabled for asymmetric CPU capacity topologies.
  293. * Allow vendor to override if desired.
  294. */
  295. trace_android_rvh_build_perf_domains(&eas_check);
  296. if (!per_cpu(sd_asym_cpucapacity, cpu) && !eas_check) {
  297. if (sched_debug()) {
  298. pr_info("rd %*pbl: CPUs do not have asymmetric capacities\n",
  299. cpumask_pr_args(cpu_map));
  300. }
  301. goto free;
  302. }
  303. /* EAS definitely does *not* handle SMT */
  304. if (sched_smt_active()) {
  305. pr_warn("rd %*pbl: Disabling EAS, SMT is not supported\n",
  306. cpumask_pr_args(cpu_map));
  307. goto free;
  308. }
  309. for_each_cpu(i, cpu_map) {
  310. /* Skip already covered CPUs. */
  311. if (find_pd(pd, i))
  312. continue;
  313. /* Create the new pd and add it to the local list. */
  314. tmp = pd_init(i);
  315. if (!tmp)
  316. goto free;
  317. tmp->next = pd;
  318. pd = tmp;
  319. /*
  320. * Count performance domains and performance states for the
  321. * complexity check.
  322. */
  323. nr_pd++;
  324. nr_ps += em_pd_nr_perf_states(pd->em_pd);
  325. }
  326. /* Bail out if the Energy Model complexity is too high. */
  327. if (nr_pd * (nr_ps + nr_cpus) > EM_MAX_COMPLEXITY) {
  328. WARN(1, "rd %*pbl: Failed to start EAS, EM complexity is too high\n",
  329. cpumask_pr_args(cpu_map));
  330. goto free;
  331. }
  332. perf_domain_debug(cpu_map, pd);
  333. /* Attach the new list of performance domains to the root domain. */
  334. tmp = rd->pd;
  335. rcu_assign_pointer(rd->pd, pd);
  336. if (tmp)
  337. call_rcu(&tmp->rcu, destroy_perf_domain_rcu);
  338. return !!pd;
  339. free:
  340. free_pd(pd);
  341. tmp = rd->pd;
  342. rcu_assign_pointer(rd->pd, NULL);
  343. if (tmp)
  344. call_rcu(&tmp->rcu, destroy_perf_domain_rcu);
  345. return false;
  346. }
  347. #else
  348. static void free_pd(struct perf_domain *pd) { }
  349. #endif /* CONFIG_ENERGY_MODEL && CONFIG_CPU_FREQ_GOV_SCHEDUTIL*/
  350. static void free_rootdomain(struct rcu_head *rcu)
  351. {
  352. struct root_domain *rd = container_of(rcu, struct root_domain, rcu);
  353. cpupri_cleanup(&rd->cpupri);
  354. cpudl_cleanup(&rd->cpudl);
  355. free_cpumask_var(rd->dlo_mask);
  356. free_cpumask_var(rd->rto_mask);
  357. free_cpumask_var(rd->online);
  358. free_cpumask_var(rd->span);
  359. free_pd(rd->pd);
  360. kfree(rd);
  361. }
  362. void rq_attach_root(struct rq *rq, struct root_domain *rd)
  363. {
  364. struct root_domain *old_rd = NULL;
  365. unsigned long flags;
  366. raw_spin_lock_irqsave(&rq->lock, flags);
  367. if (rq->rd) {
  368. old_rd = rq->rd;
  369. if (cpumask_test_cpu(rq->cpu, old_rd->online))
  370. set_rq_offline(rq);
  371. cpumask_clear_cpu(rq->cpu, old_rd->span);
  372. /*
  373. * If we dont want to free the old_rd yet then
  374. * set old_rd to NULL to skip the freeing later
  375. * in this function:
  376. */
  377. if (!atomic_dec_and_test(&old_rd->refcount))
  378. old_rd = NULL;
  379. }
  380. atomic_inc(&rd->refcount);
  381. rq->rd = rd;
  382. cpumask_set_cpu(rq->cpu, rd->span);
  383. if (cpumask_test_cpu(rq->cpu, cpu_active_mask))
  384. set_rq_online(rq);
  385. raw_spin_unlock_irqrestore(&rq->lock, flags);
  386. if (old_rd)
  387. call_rcu(&old_rd->rcu, free_rootdomain);
  388. }
  389. void sched_get_rd(struct root_domain *rd)
  390. {
  391. atomic_inc(&rd->refcount);
  392. }
  393. void sched_put_rd(struct root_domain *rd)
  394. {
  395. if (!atomic_dec_and_test(&rd->refcount))
  396. return;
  397. call_rcu(&rd->rcu, free_rootdomain);
  398. }
  399. static int init_rootdomain(struct root_domain *rd)
  400. {
  401. if (!zalloc_cpumask_var(&rd->span, GFP_KERNEL))
  402. goto out;
  403. if (!zalloc_cpumask_var(&rd->online, GFP_KERNEL))
  404. goto free_span;
  405. if (!zalloc_cpumask_var(&rd->dlo_mask, GFP_KERNEL))
  406. goto free_online;
  407. if (!zalloc_cpumask_var(&rd->rto_mask, GFP_KERNEL))
  408. goto free_dlo_mask;
  409. #ifdef HAVE_RT_PUSH_IPI
  410. rd->rto_cpu = -1;
  411. raw_spin_lock_init(&rd->rto_lock);
  412. init_irq_work(&rd->rto_push_work, rto_push_irq_work_func);
  413. #endif
  414. init_dl_bw(&rd->dl_bw);
  415. if (cpudl_init(&rd->cpudl) != 0)
  416. goto free_rto_mask;
  417. if (cpupri_init(&rd->cpupri) != 0)
  418. goto free_cpudl;
  419. return 0;
  420. free_cpudl:
  421. cpudl_cleanup(&rd->cpudl);
  422. free_rto_mask:
  423. free_cpumask_var(rd->rto_mask);
  424. free_dlo_mask:
  425. free_cpumask_var(rd->dlo_mask);
  426. free_online:
  427. free_cpumask_var(rd->online);
  428. free_span:
  429. free_cpumask_var(rd->span);
  430. out:
  431. return -ENOMEM;
  432. }
  433. /*
  434. * By default the system creates a single root-domain with all CPUs as
  435. * members (mimicking the global state we have today).
  436. */
  437. struct root_domain def_root_domain;
  438. void init_defrootdomain(void)
  439. {
  440. init_rootdomain(&def_root_domain);
  441. atomic_set(&def_root_domain.refcount, 1);
  442. }
  443. static struct root_domain *alloc_rootdomain(void)
  444. {
  445. struct root_domain *rd;
  446. rd = kzalloc(sizeof(*rd), GFP_KERNEL);
  447. if (!rd)
  448. return NULL;
  449. if (init_rootdomain(rd) != 0) {
  450. kfree(rd);
  451. return NULL;
  452. }
  453. return rd;
  454. }
  455. static void free_sched_groups(struct sched_group *sg, int free_sgc)
  456. {
  457. struct sched_group *tmp, *first;
  458. if (!sg)
  459. return;
  460. first = sg;
  461. do {
  462. tmp = sg->next;
  463. if (free_sgc && atomic_dec_and_test(&sg->sgc->ref))
  464. kfree(sg->sgc);
  465. if (atomic_dec_and_test(&sg->ref))
  466. kfree(sg);
  467. sg = tmp;
  468. } while (sg != first);
  469. }
  470. static void destroy_sched_domain(struct sched_domain *sd)
  471. {
  472. /*
  473. * A normal sched domain may have multiple group references, an
  474. * overlapping domain, having private groups, only one. Iterate,
  475. * dropping group/capacity references, freeing where none remain.
  476. */
  477. free_sched_groups(sd->groups, 1);
  478. if (sd->shared && atomic_dec_and_test(&sd->shared->ref))
  479. kfree(sd->shared);
  480. kfree(sd);
  481. }
  482. static void destroy_sched_domains_rcu(struct rcu_head *rcu)
  483. {
  484. struct sched_domain *sd = container_of(rcu, struct sched_domain, rcu);
  485. while (sd) {
  486. struct sched_domain *parent = sd->parent;
  487. destroy_sched_domain(sd);
  488. sd = parent;
  489. }
  490. }
  491. static void destroy_sched_domains(struct sched_domain *sd)
  492. {
  493. if (sd)
  494. call_rcu(&sd->rcu, destroy_sched_domains_rcu);
  495. }
  496. /*
  497. * Keep a special pointer to the highest sched_domain that has
  498. * SD_SHARE_PKG_RESOURCE set (Last Level Cache Domain) for this
  499. * allows us to avoid some pointer chasing select_idle_sibling().
  500. *
  501. * Also keep a unique ID per domain (we use the first CPU number in
  502. * the cpumask of the domain), this allows us to quickly tell if
  503. * two CPUs are in the same cache domain, see cpus_share_cache().
  504. */
  505. DEFINE_PER_CPU(struct sched_domain __rcu *, sd_llc);
  506. DEFINE_PER_CPU(int, sd_llc_size);
  507. DEFINE_PER_CPU(int, sd_llc_id);
  508. DEFINE_PER_CPU(struct sched_domain_shared __rcu *, sd_llc_shared);
  509. DEFINE_PER_CPU(struct sched_domain __rcu *, sd_numa);
  510. DEFINE_PER_CPU(struct sched_domain __rcu *, sd_asym_packing);
  511. DEFINE_PER_CPU(struct sched_domain __rcu *, sd_asym_cpucapacity);
  512. DEFINE_STATIC_KEY_FALSE(sched_asym_cpucapacity);
  513. static void update_top_cache_domain(int cpu)
  514. {
  515. struct sched_domain_shared *sds = NULL;
  516. struct sched_domain *sd;
  517. int id = cpu;
  518. int size = 1;
  519. sd = highest_flag_domain(cpu, SD_SHARE_PKG_RESOURCES);
  520. if (sd) {
  521. id = cpumask_first(sched_domain_span(sd));
  522. size = cpumask_weight(sched_domain_span(sd));
  523. sds = sd->shared;
  524. }
  525. rcu_assign_pointer(per_cpu(sd_llc, cpu), sd);
  526. per_cpu(sd_llc_size, cpu) = size;
  527. per_cpu(sd_llc_id, cpu) = id;
  528. rcu_assign_pointer(per_cpu(sd_llc_shared, cpu), sds);
  529. sd = lowest_flag_domain(cpu, SD_NUMA);
  530. rcu_assign_pointer(per_cpu(sd_numa, cpu), sd);
  531. sd = highest_flag_domain(cpu, SD_ASYM_PACKING);
  532. rcu_assign_pointer(per_cpu(sd_asym_packing, cpu), sd);
  533. sd = lowest_flag_domain(cpu, SD_ASYM_CPUCAPACITY);
  534. rcu_assign_pointer(per_cpu(sd_asym_cpucapacity, cpu), sd);
  535. }
  536. /*
  537. * Attach the domain 'sd' to 'cpu' as its base domain. Callers must
  538. * hold the hotplug lock.
  539. */
  540. static void
  541. cpu_attach_domain(struct sched_domain *sd, struct root_domain *rd, int cpu)
  542. {
  543. struct rq *rq = cpu_rq(cpu);
  544. struct sched_domain *tmp;
  545. /* Remove the sched domains which do not contribute to scheduling. */
  546. for (tmp = sd; tmp; ) {
  547. struct sched_domain *parent = tmp->parent;
  548. if (!parent)
  549. break;
  550. if (sd_parent_degenerate(tmp, parent)) {
  551. tmp->parent = parent->parent;
  552. if (parent->parent)
  553. parent->parent->child = tmp;
  554. /*
  555. * Transfer SD_PREFER_SIBLING down in case of a
  556. * degenerate parent; the spans match for this
  557. * so the property transfers.
  558. */
  559. if (parent->flags & SD_PREFER_SIBLING)
  560. tmp->flags |= SD_PREFER_SIBLING;
  561. destroy_sched_domain(parent);
  562. } else
  563. tmp = tmp->parent;
  564. }
  565. if (sd && sd_degenerate(sd)) {
  566. tmp = sd;
  567. sd = sd->parent;
  568. destroy_sched_domain(tmp);
  569. if (sd)
  570. sd->child = NULL;
  571. }
  572. sched_domain_debug(sd, cpu);
  573. rq_attach_root(rq, rd);
  574. tmp = rq->sd;
  575. rcu_assign_pointer(rq->sd, sd);
  576. dirty_sched_domain_sysctl(cpu);
  577. destroy_sched_domains(tmp);
  578. update_top_cache_domain(cpu);
  579. }
  580. struct s_data {
  581. struct sched_domain * __percpu *sd;
  582. struct root_domain *rd;
  583. };
  584. enum s_alloc {
  585. sa_rootdomain,
  586. sa_sd,
  587. sa_sd_storage,
  588. sa_none,
  589. };
  590. /*
  591. * Return the canonical balance CPU for this group, this is the first CPU
  592. * of this group that's also in the balance mask.
  593. *
  594. * The balance mask are all those CPUs that could actually end up at this
  595. * group. See build_balance_mask().
  596. *
  597. * Also see should_we_balance().
  598. */
  599. int group_balance_cpu(struct sched_group *sg)
  600. {
  601. return cpumask_first(group_balance_mask(sg));
  602. }
  603. /*
  604. * NUMA topology (first read the regular topology blurb below)
  605. *
  606. * Given a node-distance table, for example:
  607. *
  608. * node 0 1 2 3
  609. * 0: 10 20 30 20
  610. * 1: 20 10 20 30
  611. * 2: 30 20 10 20
  612. * 3: 20 30 20 10
  613. *
  614. * which represents a 4 node ring topology like:
  615. *
  616. * 0 ----- 1
  617. * | |
  618. * | |
  619. * | |
  620. * 3 ----- 2
  621. *
  622. * We want to construct domains and groups to represent this. The way we go
  623. * about doing this is to build the domains on 'hops'. For each NUMA level we
  624. * construct the mask of all nodes reachable in @level hops.
  625. *
  626. * For the above NUMA topology that gives 3 levels:
  627. *
  628. * NUMA-2 0-3 0-3 0-3 0-3
  629. * groups: {0-1,3},{1-3} {0-2},{0,2-3} {1-3},{0-1,3} {0,2-3},{0-2}
  630. *
  631. * NUMA-1 0-1,3 0-2 1-3 0,2-3
  632. * groups: {0},{1},{3} {0},{1},{2} {1},{2},{3} {0},{2},{3}
  633. *
  634. * NUMA-0 0 1 2 3
  635. *
  636. *
  637. * As can be seen; things don't nicely line up as with the regular topology.
  638. * When we iterate a domain in child domain chunks some nodes can be
  639. * represented multiple times -- hence the "overlap" naming for this part of
  640. * the topology.
  641. *
  642. * In order to minimize this overlap, we only build enough groups to cover the
  643. * domain. For instance Node-0 NUMA-2 would only get groups: 0-1,3 and 1-3.
  644. *
  645. * Because:
  646. *
  647. * - the first group of each domain is its child domain; this
  648. * gets us the first 0-1,3
  649. * - the only uncovered node is 2, who's child domain is 1-3.
  650. *
  651. * However, because of the overlap, computing a unique CPU for each group is
  652. * more complicated. Consider for instance the groups of NODE-1 NUMA-2, both
  653. * groups include the CPUs of Node-0, while those CPUs would not in fact ever
  654. * end up at those groups (they would end up in group: 0-1,3).
  655. *
  656. * To correct this we have to introduce the group balance mask. This mask
  657. * will contain those CPUs in the group that can reach this group given the
  658. * (child) domain tree.
  659. *
  660. * With this we can once again compute balance_cpu and sched_group_capacity
  661. * relations.
  662. *
  663. * XXX include words on how balance_cpu is unique and therefore can be
  664. * used for sched_group_capacity links.
  665. *
  666. *
  667. * Another 'interesting' topology is:
  668. *
  669. * node 0 1 2 3
  670. * 0: 10 20 20 30
  671. * 1: 20 10 20 20
  672. * 2: 20 20 10 20
  673. * 3: 30 20 20 10
  674. *
  675. * Which looks a little like:
  676. *
  677. * 0 ----- 1
  678. * | / |
  679. * | / |
  680. * | / |
  681. * 2 ----- 3
  682. *
  683. * This topology is asymmetric, nodes 1,2 are fully connected, but nodes 0,3
  684. * are not.
  685. *
  686. * This leads to a few particularly weird cases where the sched_domain's are
  687. * not of the same number for each CPU. Consider:
  688. *
  689. * NUMA-2 0-3 0-3
  690. * groups: {0-2},{1-3} {1-3},{0-2}
  691. *
  692. * NUMA-1 0-2 0-3 0-3 1-3
  693. *
  694. * NUMA-0 0 1 2 3
  695. *
  696. */
  697. /*
  698. * Build the balance mask; it contains only those CPUs that can arrive at this
  699. * group and should be considered to continue balancing.
  700. *
  701. * We do this during the group creation pass, therefore the group information
  702. * isn't complete yet, however since each group represents a (child) domain we
  703. * can fully construct this using the sched_domain bits (which are already
  704. * complete).
  705. */
  706. static void
  707. build_balance_mask(struct sched_domain *sd, struct sched_group *sg, struct cpumask *mask)
  708. {
  709. const struct cpumask *sg_span = sched_group_span(sg);
  710. struct sd_data *sdd = sd->private;
  711. struct sched_domain *sibling;
  712. int i;
  713. cpumask_clear(mask);
  714. for_each_cpu(i, sg_span) {
  715. sibling = *per_cpu_ptr(sdd->sd, i);
  716. /*
  717. * Can happen in the asymmetric case, where these siblings are
  718. * unused. The mask will not be empty because those CPUs that
  719. * do have the top domain _should_ span the domain.
  720. */
  721. if (!sibling->child)
  722. continue;
  723. /* If we would not end up here, we can't continue from here */
  724. if (!cpumask_equal(sg_span, sched_domain_span(sibling->child)))
  725. continue;
  726. cpumask_set_cpu(i, mask);
  727. }
  728. /* We must not have empty masks here */
  729. WARN_ON_ONCE(cpumask_empty(mask));
  730. }
  731. /*
  732. * XXX: This creates per-node group entries; since the load-balancer will
  733. * immediately access remote memory to construct this group's load-balance
  734. * statistics having the groups node local is of dubious benefit.
  735. */
  736. static struct sched_group *
  737. build_group_from_child_sched_domain(struct sched_domain *sd, int cpu)
  738. {
  739. struct sched_group *sg;
  740. struct cpumask *sg_span;
  741. sg = kzalloc_node(sizeof(struct sched_group) + cpumask_size(),
  742. GFP_KERNEL, cpu_to_node(cpu));
  743. if (!sg)
  744. return NULL;
  745. sg_span = sched_group_span(sg);
  746. if (sd->child)
  747. cpumask_copy(sg_span, sched_domain_span(sd->child));
  748. else
  749. cpumask_copy(sg_span, sched_domain_span(sd));
  750. atomic_inc(&sg->ref);
  751. return sg;
  752. }
  753. static void init_overlap_sched_group(struct sched_domain *sd,
  754. struct sched_group *sg)
  755. {
  756. struct cpumask *mask = sched_domains_tmpmask2;
  757. struct sd_data *sdd = sd->private;
  758. struct cpumask *sg_span;
  759. int cpu;
  760. build_balance_mask(sd, sg, mask);
  761. cpu = cpumask_first_and(sched_group_span(sg), mask);
  762. sg->sgc = *per_cpu_ptr(sdd->sgc, cpu);
  763. if (atomic_inc_return(&sg->sgc->ref) == 1)
  764. cpumask_copy(group_balance_mask(sg), mask);
  765. else
  766. WARN_ON_ONCE(!cpumask_equal(group_balance_mask(sg), mask));
  767. /*
  768. * Initialize sgc->capacity such that even if we mess up the
  769. * domains and no possible iteration will get us here, we won't
  770. * die on a /0 trap.
  771. */
  772. sg_span = sched_group_span(sg);
  773. sg->sgc->capacity = SCHED_CAPACITY_SCALE * cpumask_weight(sg_span);
  774. sg->sgc->min_capacity = SCHED_CAPACITY_SCALE;
  775. sg->sgc->max_capacity = SCHED_CAPACITY_SCALE;
  776. }
  777. static int
  778. build_overlap_sched_groups(struct sched_domain *sd, int cpu)
  779. {
  780. struct sched_group *first = NULL, *last = NULL, *sg;
  781. const struct cpumask *span = sched_domain_span(sd);
  782. struct cpumask *covered = sched_domains_tmpmask;
  783. struct sd_data *sdd = sd->private;
  784. struct sched_domain *sibling;
  785. int i;
  786. cpumask_clear(covered);
  787. for_each_cpu_wrap(i, span, cpu) {
  788. struct cpumask *sg_span;
  789. if (cpumask_test_cpu(i, covered))
  790. continue;
  791. sibling = *per_cpu_ptr(sdd->sd, i);
  792. /*
  793. * Asymmetric node setups can result in situations where the
  794. * domain tree is of unequal depth, make sure to skip domains
  795. * that already cover the entire range.
  796. *
  797. * In that case build_sched_domains() will have terminated the
  798. * iteration early and our sibling sd spans will be empty.
  799. * Domains should always include the CPU they're built on, so
  800. * check that.
  801. */
  802. if (!cpumask_test_cpu(i, sched_domain_span(sibling)))
  803. continue;
  804. sg = build_group_from_child_sched_domain(sibling, cpu);
  805. if (!sg)
  806. goto fail;
  807. sg_span = sched_group_span(sg);
  808. cpumask_or(covered, covered, sg_span);
  809. init_overlap_sched_group(sd, sg);
  810. if (!first)
  811. first = sg;
  812. if (last)
  813. last->next = sg;
  814. last = sg;
  815. last->next = first;
  816. }
  817. sd->groups = first;
  818. return 0;
  819. fail:
  820. free_sched_groups(first, 0);
  821. return -ENOMEM;
  822. }
  823. /*
  824. * Package topology (also see the load-balance blurb in fair.c)
  825. *
  826. * The scheduler builds a tree structure to represent a number of important
  827. * topology features. By default (default_topology[]) these include:
  828. *
  829. * - Simultaneous multithreading (SMT)
  830. * - Multi-Core Cache (MC)
  831. * - Package (DIE)
  832. *
  833. * Where the last one more or less denotes everything up to a NUMA node.
  834. *
  835. * The tree consists of 3 primary data structures:
  836. *
  837. * sched_domain -> sched_group -> sched_group_capacity
  838. * ^ ^ ^ ^
  839. * `-' `-'
  840. *
  841. * The sched_domains are per-CPU and have a two way link (parent & child) and
  842. * denote the ever growing mask of CPUs belonging to that level of topology.
  843. *
  844. * Each sched_domain has a circular (double) linked list of sched_group's, each
  845. * denoting the domains of the level below (or individual CPUs in case of the
  846. * first domain level). The sched_group linked by a sched_domain includes the
  847. * CPU of that sched_domain [*].
  848. *
  849. * Take for instance a 2 threaded, 2 core, 2 cache cluster part:
  850. *
  851. * CPU 0 1 2 3 4 5 6 7
  852. *
  853. * DIE [ ]
  854. * MC [ ] [ ]
  855. * SMT [ ] [ ] [ ] [ ]
  856. *
  857. * - or -
  858. *
  859. * DIE 0-7 0-7 0-7 0-7 0-7 0-7 0-7 0-7
  860. * MC 0-3 0-3 0-3 0-3 4-7 4-7 4-7 4-7
  861. * SMT 0-1 0-1 2-3 2-3 4-5 4-5 6-7 6-7
  862. *
  863. * CPU 0 1 2 3 4 5 6 7
  864. *
  865. * One way to think about it is: sched_domain moves you up and down among these
  866. * topology levels, while sched_group moves you sideways through it, at child
  867. * domain granularity.
  868. *
  869. * sched_group_capacity ensures each unique sched_group has shared storage.
  870. *
  871. * There are two related construction problems, both require a CPU that
  872. * uniquely identify each group (for a given domain):
  873. *
  874. * - The first is the balance_cpu (see should_we_balance() and the
  875. * load-balance blub in fair.c); for each group we only want 1 CPU to
  876. * continue balancing at a higher domain.
  877. *
  878. * - The second is the sched_group_capacity; we want all identical groups
  879. * to share a single sched_group_capacity.
  880. *
  881. * Since these topologies are exclusive by construction. That is, its
  882. * impossible for an SMT thread to belong to multiple cores, and cores to
  883. * be part of multiple caches. There is a very clear and unique location
  884. * for each CPU in the hierarchy.
  885. *
  886. * Therefore computing a unique CPU for each group is trivial (the iteration
  887. * mask is redundant and set all 1s; all CPUs in a group will end up at _that_
  888. * group), we can simply pick the first CPU in each group.
  889. *
  890. *
  891. * [*] in other words, the first group of each domain is its child domain.
  892. */
  893. static struct sched_group *get_group(int cpu, struct sd_data *sdd)
  894. {
  895. struct sched_domain *sd = *per_cpu_ptr(sdd->sd, cpu);
  896. struct sched_domain *child = sd->child;
  897. struct sched_group *sg;
  898. bool already_visited;
  899. if (child)
  900. cpu = cpumask_first(sched_domain_span(child));
  901. sg = *per_cpu_ptr(sdd->sg, cpu);
  902. sg->sgc = *per_cpu_ptr(sdd->sgc, cpu);
  903. /* Increase refcounts for claim_allocations: */
  904. already_visited = atomic_inc_return(&sg->ref) > 1;
  905. /* sgc visits should follow a similar trend as sg */
  906. WARN_ON(already_visited != (atomic_inc_return(&sg->sgc->ref) > 1));
  907. /* If we have already visited that group, it's already initialized. */
  908. if (already_visited)
  909. return sg;
  910. if (child) {
  911. cpumask_copy(sched_group_span(sg), sched_domain_span(child));
  912. cpumask_copy(group_balance_mask(sg), sched_group_span(sg));
  913. } else {
  914. cpumask_set_cpu(cpu, sched_group_span(sg));
  915. cpumask_set_cpu(cpu, group_balance_mask(sg));
  916. }
  917. sg->sgc->capacity = SCHED_CAPACITY_SCALE * cpumask_weight(sched_group_span(sg));
  918. sg->sgc->min_capacity = SCHED_CAPACITY_SCALE;
  919. sg->sgc->max_capacity = SCHED_CAPACITY_SCALE;
  920. return sg;
  921. }
  922. /*
  923. * build_sched_groups will build a circular linked list of the groups
  924. * covered by the given span, will set each group's ->cpumask correctly,
  925. * and will initialize their ->sgc.
  926. *
  927. * Assumes the sched_domain tree is fully constructed
  928. */
  929. static int
  930. build_sched_groups(struct sched_domain *sd, int cpu)
  931. {
  932. struct sched_group *first = NULL, *last = NULL;
  933. struct sd_data *sdd = sd->private;
  934. const struct cpumask *span = sched_domain_span(sd);
  935. struct cpumask *covered;
  936. int i;
  937. lockdep_assert_held(&sched_domains_mutex);
  938. covered = sched_domains_tmpmask;
  939. cpumask_clear(covered);
  940. for_each_cpu_wrap(i, span, cpu) {
  941. struct sched_group *sg;
  942. if (cpumask_test_cpu(i, covered))
  943. continue;
  944. sg = get_group(i, sdd);
  945. cpumask_or(covered, covered, sched_group_span(sg));
  946. if (!first)
  947. first = sg;
  948. if (last)
  949. last->next = sg;
  950. last = sg;
  951. }
  952. last->next = first;
  953. sd->groups = first;
  954. return 0;
  955. }
  956. /*
  957. * Initialize sched groups cpu_capacity.
  958. *
  959. * cpu_capacity indicates the capacity of sched group, which is used while
  960. * distributing the load between different sched groups in a sched domain.
  961. * Typically cpu_capacity for all the groups in a sched domain will be same
  962. * unless there are asymmetries in the topology. If there are asymmetries,
  963. * group having more cpu_capacity will pickup more load compared to the
  964. * group having less cpu_capacity.
  965. */
  966. static void init_sched_groups_capacity(int cpu, struct sched_domain *sd)
  967. {
  968. struct sched_group *sg = sd->groups;
  969. WARN_ON(!sg);
  970. do {
  971. int cpu, max_cpu = -1;
  972. sg->group_weight = cpumask_weight(sched_group_span(sg));
  973. if (!(sd->flags & SD_ASYM_PACKING))
  974. goto next;
  975. for_each_cpu(cpu, sched_group_span(sg)) {
  976. if (max_cpu < 0)
  977. max_cpu = cpu;
  978. else if (sched_asym_prefer(cpu, max_cpu))
  979. max_cpu = cpu;
  980. }
  981. sg->asym_prefer_cpu = max_cpu;
  982. next:
  983. sg = sg->next;
  984. } while (sg != sd->groups);
  985. if (cpu != group_balance_cpu(sg))
  986. return;
  987. update_group_capacity(sd, cpu);
  988. }
  989. /*
  990. * Initializers for schedule domains
  991. * Non-inlined to reduce accumulated stack pressure in build_sched_domains()
  992. */
  993. static int default_relax_domain_level = -1;
  994. int sched_domain_level_max;
  995. static int __init setup_relax_domain_level(char *str)
  996. {
  997. if (kstrtoint(str, 0, &default_relax_domain_level))
  998. pr_warn("Unable to set relax_domain_level\n");
  999. return 1;
  1000. }
  1001. __setup("relax_domain_level=", setup_relax_domain_level);
  1002. static void set_domain_attribute(struct sched_domain *sd,
  1003. struct sched_domain_attr *attr)
  1004. {
  1005. int request;
  1006. if (!attr || attr->relax_domain_level < 0) {
  1007. if (default_relax_domain_level < 0)
  1008. return;
  1009. request = default_relax_domain_level;
  1010. } else
  1011. request = attr->relax_domain_level;
  1012. if (sd->level > request) {
  1013. /* Turn off idle balance on this domain: */
  1014. sd->flags &= ~(SD_BALANCE_WAKE|SD_BALANCE_NEWIDLE);
  1015. }
  1016. }
  1017. static void __sdt_free(const struct cpumask *cpu_map);
  1018. static int __sdt_alloc(const struct cpumask *cpu_map);
  1019. static void __free_domain_allocs(struct s_data *d, enum s_alloc what,
  1020. const struct cpumask *cpu_map)
  1021. {
  1022. switch (what) {
  1023. case sa_rootdomain:
  1024. if (!atomic_read(&d->rd->refcount))
  1025. free_rootdomain(&d->rd->rcu);
  1026. fallthrough;
  1027. case sa_sd:
  1028. free_percpu(d->sd);
  1029. fallthrough;
  1030. case sa_sd_storage:
  1031. __sdt_free(cpu_map);
  1032. fallthrough;
  1033. case sa_none:
  1034. break;
  1035. }
  1036. }
  1037. static enum s_alloc
  1038. __visit_domain_allocation_hell(struct s_data *d, const struct cpumask *cpu_map)
  1039. {
  1040. memset(d, 0, sizeof(*d));
  1041. if (__sdt_alloc(cpu_map))
  1042. return sa_sd_storage;
  1043. d->sd = alloc_percpu(struct sched_domain *);
  1044. if (!d->sd)
  1045. return sa_sd_storage;
  1046. d->rd = alloc_rootdomain();
  1047. if (!d->rd)
  1048. return sa_sd;
  1049. return sa_rootdomain;
  1050. }
  1051. /*
  1052. * NULL the sd_data elements we've used to build the sched_domain and
  1053. * sched_group structure so that the subsequent __free_domain_allocs()
  1054. * will not free the data we're using.
  1055. */
  1056. static void claim_allocations(int cpu, struct sched_domain *sd)
  1057. {
  1058. struct sd_data *sdd = sd->private;
  1059. WARN_ON_ONCE(*per_cpu_ptr(sdd->sd, cpu) != sd);
  1060. *per_cpu_ptr(sdd->sd, cpu) = NULL;
  1061. if (atomic_read(&(*per_cpu_ptr(sdd->sds, cpu))->ref))
  1062. *per_cpu_ptr(sdd->sds, cpu) = NULL;
  1063. if (atomic_read(&(*per_cpu_ptr(sdd->sg, cpu))->ref))
  1064. *per_cpu_ptr(sdd->sg, cpu) = NULL;
  1065. if (atomic_read(&(*per_cpu_ptr(sdd->sgc, cpu))->ref))
  1066. *per_cpu_ptr(sdd->sgc, cpu) = NULL;
  1067. }
  1068. #ifdef CONFIG_NUMA
  1069. enum numa_topology_type sched_numa_topology_type;
  1070. static int sched_domains_numa_levels;
  1071. static int sched_domains_curr_level;
  1072. int sched_max_numa_distance;
  1073. static int *sched_domains_numa_distance;
  1074. static struct cpumask ***sched_domains_numa_masks;
  1075. int __read_mostly node_reclaim_distance = RECLAIM_DISTANCE;
  1076. #endif
  1077. /*
  1078. * SD_flags allowed in topology descriptions.
  1079. *
  1080. * These flags are purely descriptive of the topology and do not prescribe
  1081. * behaviour. Behaviour is artificial and mapped in the below sd_init()
  1082. * function:
  1083. *
  1084. * SD_SHARE_CPUCAPACITY - describes SMT topologies
  1085. * SD_SHARE_PKG_RESOURCES - describes shared caches
  1086. * SD_NUMA - describes NUMA topologies
  1087. *
  1088. * Odd one out, which beside describing the topology has a quirk also
  1089. * prescribes the desired behaviour that goes along with it:
  1090. *
  1091. * SD_ASYM_PACKING - describes SMT quirks
  1092. */
  1093. #define TOPOLOGY_SD_FLAGS \
  1094. (SD_SHARE_CPUCAPACITY | \
  1095. SD_SHARE_PKG_RESOURCES | \
  1096. SD_NUMA | \
  1097. SD_ASYM_PACKING)
  1098. static struct sched_domain *
  1099. sd_init(struct sched_domain_topology_level *tl,
  1100. const struct cpumask *cpu_map,
  1101. struct sched_domain *child, int dflags, int cpu)
  1102. {
  1103. struct sd_data *sdd = &tl->data;
  1104. struct sched_domain *sd = *per_cpu_ptr(sdd->sd, cpu);
  1105. int sd_id, sd_weight, sd_flags = 0;
  1106. #ifdef CONFIG_NUMA
  1107. /*
  1108. * Ugly hack to pass state to sd_numa_mask()...
  1109. */
  1110. sched_domains_curr_level = tl->numa_level;
  1111. #endif
  1112. sd_weight = cpumask_weight(tl->mask(cpu));
  1113. if (tl->sd_flags)
  1114. sd_flags = (*tl->sd_flags)();
  1115. if (WARN_ONCE(sd_flags & ~TOPOLOGY_SD_FLAGS,
  1116. "wrong sd_flags in topology description\n"))
  1117. sd_flags &= TOPOLOGY_SD_FLAGS;
  1118. /* Apply detected topology flags */
  1119. sd_flags |= dflags;
  1120. *sd = (struct sched_domain){
  1121. .min_interval = sd_weight,
  1122. .max_interval = 2*sd_weight,
  1123. .busy_factor = 16,
  1124. .imbalance_pct = 117,
  1125. .cache_nice_tries = 0,
  1126. .flags = 1*SD_BALANCE_NEWIDLE
  1127. | 1*SD_BALANCE_EXEC
  1128. | 1*SD_BALANCE_FORK
  1129. | 0*SD_BALANCE_WAKE
  1130. | 1*SD_WAKE_AFFINE
  1131. | 0*SD_SHARE_CPUCAPACITY
  1132. | 0*SD_SHARE_PKG_RESOURCES
  1133. | 0*SD_SERIALIZE
  1134. | 1*SD_PREFER_SIBLING
  1135. | 0*SD_NUMA
  1136. | sd_flags
  1137. ,
  1138. .last_balance = jiffies,
  1139. .balance_interval = sd_weight,
  1140. .max_newidle_lb_cost = 0,
  1141. .next_decay_max_lb_cost = jiffies,
  1142. .child = child,
  1143. #ifdef CONFIG_SCHED_DEBUG
  1144. .name = tl->name,
  1145. #endif
  1146. };
  1147. cpumask_and(sched_domain_span(sd), cpu_map, tl->mask(cpu));
  1148. sd_id = cpumask_first(sched_domain_span(sd));
  1149. /*
  1150. * Convert topological properties into behaviour.
  1151. */
  1152. /* Don't attempt to spread across CPUs of different capacities. */
  1153. if ((sd->flags & SD_ASYM_CPUCAPACITY) && sd->child)
  1154. sd->child->flags &= ~SD_PREFER_SIBLING;
  1155. if (sd->flags & SD_SHARE_CPUCAPACITY) {
  1156. sd->imbalance_pct = 110;
  1157. } else if (sd->flags & SD_SHARE_PKG_RESOURCES) {
  1158. sd->imbalance_pct = 117;
  1159. sd->cache_nice_tries = 1;
  1160. #ifdef CONFIG_NUMA
  1161. } else if (sd->flags & SD_NUMA) {
  1162. sd->cache_nice_tries = 2;
  1163. sd->flags &= ~SD_PREFER_SIBLING;
  1164. sd->flags |= SD_SERIALIZE;
  1165. if (sched_domains_numa_distance[tl->numa_level] > node_reclaim_distance) {
  1166. sd->flags &= ~(SD_BALANCE_EXEC |
  1167. SD_BALANCE_FORK |
  1168. SD_WAKE_AFFINE);
  1169. }
  1170. #endif
  1171. } else {
  1172. sd->cache_nice_tries = 1;
  1173. }
  1174. /*
  1175. * For all levels sharing cache; connect a sched_domain_shared
  1176. * instance.
  1177. */
  1178. if (sd->flags & SD_SHARE_PKG_RESOURCES) {
  1179. sd->shared = *per_cpu_ptr(sdd->sds, sd_id);
  1180. atomic_inc(&sd->shared->ref);
  1181. atomic_set(&sd->shared->nr_busy_cpus, sd_weight);
  1182. }
  1183. sd->private = sdd;
  1184. return sd;
  1185. }
  1186. /*
  1187. * Topology list, bottom-up.
  1188. */
  1189. static struct sched_domain_topology_level default_topology[] = {
  1190. #ifdef CONFIG_SCHED_SMT
  1191. { cpu_smt_mask, cpu_smt_flags, SD_INIT_NAME(SMT) },
  1192. #endif
  1193. #ifdef CONFIG_SCHED_MC
  1194. { cpu_coregroup_mask, cpu_core_flags, SD_INIT_NAME(MC) },
  1195. #endif
  1196. { cpu_cpu_mask, SD_INIT_NAME(DIE) },
  1197. { NULL, },
  1198. };
  1199. static struct sched_domain_topology_level *sched_domain_topology =
  1200. default_topology;
  1201. #define for_each_sd_topology(tl) \
  1202. for (tl = sched_domain_topology; tl->mask; tl++)
  1203. void set_sched_topology(struct sched_domain_topology_level *tl)
  1204. {
  1205. if (WARN_ON_ONCE(sched_smp_initialized))
  1206. return;
  1207. sched_domain_topology = tl;
  1208. }
  1209. #ifdef CONFIG_NUMA
  1210. static const struct cpumask *sd_numa_mask(int cpu)
  1211. {
  1212. return sched_domains_numa_masks[sched_domains_curr_level][cpu_to_node(cpu)];
  1213. }
  1214. static void sched_numa_warn(const char *str)
  1215. {
  1216. static int done = false;
  1217. int i,j;
  1218. if (done)
  1219. return;
  1220. done = true;
  1221. printk(KERN_WARNING "ERROR: %s\n\n", str);
  1222. for (i = 0; i < nr_node_ids; i++) {
  1223. printk(KERN_WARNING " ");
  1224. for (j = 0; j < nr_node_ids; j++)
  1225. printk(KERN_CONT "%02d ", node_distance(i,j));
  1226. printk(KERN_CONT "\n");
  1227. }
  1228. printk(KERN_WARNING "\n");
  1229. }
  1230. bool find_numa_distance(int distance)
  1231. {
  1232. int i;
  1233. if (distance == node_distance(0, 0))
  1234. return true;
  1235. for (i = 0; i < sched_domains_numa_levels; i++) {
  1236. if (sched_domains_numa_distance[i] == distance)
  1237. return true;
  1238. }
  1239. return false;
  1240. }
  1241. /*
  1242. * A system can have three types of NUMA topology:
  1243. * NUMA_DIRECT: all nodes are directly connected, or not a NUMA system
  1244. * NUMA_GLUELESS_MESH: some nodes reachable through intermediary nodes
  1245. * NUMA_BACKPLANE: nodes can reach other nodes through a backplane
  1246. *
  1247. * The difference between a glueless mesh topology and a backplane
  1248. * topology lies in whether communication between not directly
  1249. * connected nodes goes through intermediary nodes (where programs
  1250. * could run), or through backplane controllers. This affects
  1251. * placement of programs.
  1252. *
  1253. * The type of topology can be discerned with the following tests:
  1254. * - If the maximum distance between any nodes is 1 hop, the system
  1255. * is directly connected.
  1256. * - If for two nodes A and B, located N > 1 hops away from each other,
  1257. * there is an intermediary node C, which is < N hops away from both
  1258. * nodes A and B, the system is a glueless mesh.
  1259. */
  1260. static void init_numa_topology_type(void)
  1261. {
  1262. int a, b, c, n;
  1263. n = sched_max_numa_distance;
  1264. if (sched_domains_numa_levels <= 2) {
  1265. sched_numa_topology_type = NUMA_DIRECT;
  1266. return;
  1267. }
  1268. for_each_online_node(a) {
  1269. for_each_online_node(b) {
  1270. /* Find two nodes furthest removed from each other. */
  1271. if (node_distance(a, b) < n)
  1272. continue;
  1273. /* Is there an intermediary node between a and b? */
  1274. for_each_online_node(c) {
  1275. if (node_distance(a, c) < n &&
  1276. node_distance(b, c) < n) {
  1277. sched_numa_topology_type =
  1278. NUMA_GLUELESS_MESH;
  1279. return;
  1280. }
  1281. }
  1282. sched_numa_topology_type = NUMA_BACKPLANE;
  1283. return;
  1284. }
  1285. }
  1286. }
  1287. #define NR_DISTANCE_VALUES (1 << DISTANCE_BITS)
  1288. void sched_init_numa(void)
  1289. {
  1290. struct sched_domain_topology_level *tl;
  1291. unsigned long *distance_map;
  1292. int nr_levels = 0;
  1293. int i, j;
  1294. /*
  1295. * O(nr_nodes^2) deduplicating selection sort -- in order to find the
  1296. * unique distances in the node_distance() table.
  1297. */
  1298. distance_map = bitmap_alloc(NR_DISTANCE_VALUES, GFP_KERNEL);
  1299. if (!distance_map)
  1300. return;
  1301. bitmap_zero(distance_map, NR_DISTANCE_VALUES);
  1302. for (i = 0; i < nr_node_ids; i++) {
  1303. for (j = 0; j < nr_node_ids; j++) {
  1304. int distance = node_distance(i, j);
  1305. if (distance < LOCAL_DISTANCE || distance >= NR_DISTANCE_VALUES) {
  1306. sched_numa_warn("Invalid distance value range");
  1307. return;
  1308. }
  1309. bitmap_set(distance_map, distance, 1);
  1310. }
  1311. }
  1312. /*
  1313. * We can now figure out how many unique distance values there are and
  1314. * allocate memory accordingly.
  1315. */
  1316. nr_levels = bitmap_weight(distance_map, NR_DISTANCE_VALUES);
  1317. sched_domains_numa_distance = kcalloc(nr_levels, sizeof(int), GFP_KERNEL);
  1318. if (!sched_domains_numa_distance) {
  1319. bitmap_free(distance_map);
  1320. return;
  1321. }
  1322. for (i = 0, j = 0; i < nr_levels; i++, j++) {
  1323. j = find_next_bit(distance_map, NR_DISTANCE_VALUES, j);
  1324. sched_domains_numa_distance[i] = j;
  1325. }
  1326. bitmap_free(distance_map);
  1327. /*
  1328. * 'nr_levels' contains the number of unique distances
  1329. *
  1330. * The sched_domains_numa_distance[] array includes the actual distance
  1331. * numbers.
  1332. */
  1333. /*
  1334. * Here, we should temporarily reset sched_domains_numa_levels to 0.
  1335. * If it fails to allocate memory for array sched_domains_numa_masks[][],
  1336. * the array will contain less then 'nr_levels' members. This could be
  1337. * dangerous when we use it to iterate array sched_domains_numa_masks[][]
  1338. * in other functions.
  1339. *
  1340. * We reset it to 'nr_levels' at the end of this function.
  1341. */
  1342. sched_domains_numa_levels = 0;
  1343. sched_domains_numa_masks = kzalloc(sizeof(void *) * nr_levels, GFP_KERNEL);
  1344. if (!sched_domains_numa_masks)
  1345. return;
  1346. /*
  1347. * Now for each level, construct a mask per node which contains all
  1348. * CPUs of nodes that are that many hops away from us.
  1349. */
  1350. for (i = 0; i < nr_levels; i++) {
  1351. sched_domains_numa_masks[i] =
  1352. kzalloc(nr_node_ids * sizeof(void *), GFP_KERNEL);
  1353. if (!sched_domains_numa_masks[i])
  1354. return;
  1355. for (j = 0; j < nr_node_ids; j++) {
  1356. struct cpumask *mask = kzalloc(cpumask_size(), GFP_KERNEL);
  1357. int k;
  1358. if (!mask)
  1359. return;
  1360. sched_domains_numa_masks[i][j] = mask;
  1361. for_each_node(k) {
  1362. if (sched_debug() && (node_distance(j, k) != node_distance(k, j)))
  1363. sched_numa_warn("Node-distance not symmetric");
  1364. if (node_distance(j, k) > sched_domains_numa_distance[i])
  1365. continue;
  1366. cpumask_or(mask, mask, cpumask_of_node(k));
  1367. }
  1368. }
  1369. }
  1370. /* Compute default topology size */
  1371. for (i = 0; sched_domain_topology[i].mask; i++);
  1372. tl = kzalloc((i + nr_levels + 1) *
  1373. sizeof(struct sched_domain_topology_level), GFP_KERNEL);
  1374. if (!tl)
  1375. return;
  1376. /*
  1377. * Copy the default topology bits..
  1378. */
  1379. for (i = 0; sched_domain_topology[i].mask; i++)
  1380. tl[i] = sched_domain_topology[i];
  1381. /*
  1382. * Add the NUMA identity distance, aka single NODE.
  1383. */
  1384. tl[i++] = (struct sched_domain_topology_level){
  1385. .mask = sd_numa_mask,
  1386. .numa_level = 0,
  1387. SD_INIT_NAME(NODE)
  1388. };
  1389. /*
  1390. * .. and append 'j' levels of NUMA goodness.
  1391. */
  1392. for (j = 1; j < nr_levels; i++, j++) {
  1393. tl[i] = (struct sched_domain_topology_level){
  1394. .mask = sd_numa_mask,
  1395. .sd_flags = cpu_numa_flags,
  1396. .flags = SDTL_OVERLAP,
  1397. .numa_level = j,
  1398. SD_INIT_NAME(NUMA)
  1399. };
  1400. }
  1401. sched_domain_topology = tl;
  1402. sched_domains_numa_levels = nr_levels;
  1403. sched_max_numa_distance = sched_domains_numa_distance[nr_levels - 1];
  1404. init_numa_topology_type();
  1405. }
  1406. void sched_domains_numa_masks_set(unsigned int cpu)
  1407. {
  1408. int node = cpu_to_node(cpu);
  1409. int i, j;
  1410. for (i = 0; i < sched_domains_numa_levels; i++) {
  1411. for (j = 0; j < nr_node_ids; j++) {
  1412. if (node_distance(j, node) <= sched_domains_numa_distance[i])
  1413. cpumask_set_cpu(cpu, sched_domains_numa_masks[i][j]);
  1414. }
  1415. }
  1416. }
  1417. void sched_domains_numa_masks_clear(unsigned int cpu)
  1418. {
  1419. int i, j;
  1420. for (i = 0; i < sched_domains_numa_levels; i++) {
  1421. for (j = 0; j < nr_node_ids; j++)
  1422. cpumask_clear_cpu(cpu, sched_domains_numa_masks[i][j]);
  1423. }
  1424. }
  1425. /*
  1426. * sched_numa_find_closest() - given the NUMA topology, find the cpu
  1427. * closest to @cpu from @cpumask.
  1428. * cpumask: cpumask to find a cpu from
  1429. * cpu: cpu to be close to
  1430. *
  1431. * returns: cpu, or nr_cpu_ids when nothing found.
  1432. */
  1433. int sched_numa_find_closest(const struct cpumask *cpus, int cpu)
  1434. {
  1435. int i, j = cpu_to_node(cpu);
  1436. for (i = 0; i < sched_domains_numa_levels; i++) {
  1437. cpu = cpumask_any_and(cpus, sched_domains_numa_masks[i][j]);
  1438. if (cpu < nr_cpu_ids)
  1439. return cpu;
  1440. }
  1441. return nr_cpu_ids;
  1442. }
  1443. #endif /* CONFIG_NUMA */
  1444. static int __sdt_alloc(const struct cpumask *cpu_map)
  1445. {
  1446. struct sched_domain_topology_level *tl;
  1447. int j;
  1448. for_each_sd_topology(tl) {
  1449. struct sd_data *sdd = &tl->data;
  1450. sdd->sd = alloc_percpu(struct sched_domain *);
  1451. if (!sdd->sd)
  1452. return -ENOMEM;
  1453. sdd->sds = alloc_percpu(struct sched_domain_shared *);
  1454. if (!sdd->sds)
  1455. return -ENOMEM;
  1456. sdd->sg = alloc_percpu(struct sched_group *);
  1457. if (!sdd->sg)
  1458. return -ENOMEM;
  1459. sdd->sgc = alloc_percpu(struct sched_group_capacity *);
  1460. if (!sdd->sgc)
  1461. return -ENOMEM;
  1462. for_each_cpu(j, cpu_map) {
  1463. struct sched_domain *sd;
  1464. struct sched_domain_shared *sds;
  1465. struct sched_group *sg;
  1466. struct sched_group_capacity *sgc;
  1467. sd = kzalloc_node(sizeof(struct sched_domain) + cpumask_size(),
  1468. GFP_KERNEL, cpu_to_node(j));
  1469. if (!sd)
  1470. return -ENOMEM;
  1471. *per_cpu_ptr(sdd->sd, j) = sd;
  1472. sds = kzalloc_node(sizeof(struct sched_domain_shared),
  1473. GFP_KERNEL, cpu_to_node(j));
  1474. if (!sds)
  1475. return -ENOMEM;
  1476. *per_cpu_ptr(sdd->sds, j) = sds;
  1477. sg = kzalloc_node(sizeof(struct sched_group) + cpumask_size(),
  1478. GFP_KERNEL, cpu_to_node(j));
  1479. if (!sg)
  1480. return -ENOMEM;
  1481. sg->next = sg;
  1482. *per_cpu_ptr(sdd->sg, j) = sg;
  1483. sgc = kzalloc_node(sizeof(struct sched_group_capacity) + cpumask_size(),
  1484. GFP_KERNEL, cpu_to_node(j));
  1485. if (!sgc)
  1486. return -ENOMEM;
  1487. #ifdef CONFIG_SCHED_DEBUG
  1488. sgc->id = j;
  1489. #endif
  1490. *per_cpu_ptr(sdd->sgc, j) = sgc;
  1491. }
  1492. }
  1493. return 0;
  1494. }
  1495. static void __sdt_free(const struct cpumask *cpu_map)
  1496. {
  1497. struct sched_domain_topology_level *tl;
  1498. int j;
  1499. for_each_sd_topology(tl) {
  1500. struct sd_data *sdd = &tl->data;
  1501. for_each_cpu(j, cpu_map) {
  1502. struct sched_domain *sd;
  1503. if (sdd->sd) {
  1504. sd = *per_cpu_ptr(sdd->sd, j);
  1505. if (sd && (sd->flags & SD_OVERLAP))
  1506. free_sched_groups(sd->groups, 0);
  1507. kfree(*per_cpu_ptr(sdd->sd, j));
  1508. }
  1509. if (sdd->sds)
  1510. kfree(*per_cpu_ptr(sdd->sds, j));
  1511. if (sdd->sg)
  1512. kfree(*per_cpu_ptr(sdd->sg, j));
  1513. if (sdd->sgc)
  1514. kfree(*per_cpu_ptr(sdd->sgc, j));
  1515. }
  1516. free_percpu(sdd->sd);
  1517. sdd->sd = NULL;
  1518. free_percpu(sdd->sds);
  1519. sdd->sds = NULL;
  1520. free_percpu(sdd->sg);
  1521. sdd->sg = NULL;
  1522. free_percpu(sdd->sgc);
  1523. sdd->sgc = NULL;
  1524. }
  1525. }
  1526. static struct sched_domain *build_sched_domain(struct sched_domain_topology_level *tl,
  1527. const struct cpumask *cpu_map, struct sched_domain_attr *attr,
  1528. struct sched_domain *child, int dflags, int cpu)
  1529. {
  1530. struct sched_domain *sd = sd_init(tl, cpu_map, child, dflags, cpu);
  1531. if (child) {
  1532. sd->level = child->level + 1;
  1533. sched_domain_level_max = max(sched_domain_level_max, sd->level);
  1534. child->parent = sd;
  1535. if (!cpumask_subset(sched_domain_span(child),
  1536. sched_domain_span(sd))) {
  1537. pr_err("BUG: arch topology borken\n");
  1538. #ifdef CONFIG_SCHED_DEBUG
  1539. pr_err(" the %s domain not a subset of the %s domain\n",
  1540. child->name, sd->name);
  1541. #endif
  1542. /* Fixup, ensure @sd has at least @child CPUs. */
  1543. cpumask_or(sched_domain_span(sd),
  1544. sched_domain_span(sd),
  1545. sched_domain_span(child));
  1546. }
  1547. }
  1548. set_domain_attribute(sd, attr);
  1549. return sd;
  1550. }
  1551. /*
  1552. * Ensure topology masks are sane, i.e. there are no conflicts (overlaps) for
  1553. * any two given CPUs at this (non-NUMA) topology level.
  1554. */
  1555. static bool topology_span_sane(struct sched_domain_topology_level *tl,
  1556. const struct cpumask *cpu_map, int cpu)
  1557. {
  1558. int i;
  1559. /* NUMA levels are allowed to overlap */
  1560. if (tl->flags & SDTL_OVERLAP)
  1561. return true;
  1562. /*
  1563. * Non-NUMA levels cannot partially overlap - they must be either
  1564. * completely equal or completely disjoint. Otherwise we can end up
  1565. * breaking the sched_group lists - i.e. a later get_group() pass
  1566. * breaks the linking done for an earlier span.
  1567. */
  1568. for_each_cpu(i, cpu_map) {
  1569. if (i == cpu)
  1570. continue;
  1571. /*
  1572. * We should 'and' all those masks with 'cpu_map' to exactly
  1573. * match the topology we're about to build, but that can only
  1574. * remove CPUs, which only lessens our ability to detect
  1575. * overlaps
  1576. */
  1577. if (!cpumask_equal(tl->mask(cpu), tl->mask(i)) &&
  1578. cpumask_intersects(tl->mask(cpu), tl->mask(i)))
  1579. return false;
  1580. }
  1581. return true;
  1582. }
  1583. /*
  1584. * Find the sched_domain_topology_level where all CPU capacities are visible
  1585. * for all CPUs.
  1586. */
  1587. static struct sched_domain_topology_level
  1588. *asym_cpu_capacity_level(const struct cpumask *cpu_map)
  1589. {
  1590. int i, j, asym_level = 0;
  1591. bool asym = false;
  1592. struct sched_domain_topology_level *tl, *asym_tl = NULL;
  1593. unsigned long cap;
  1594. /* Is there any asymmetry? */
  1595. cap = arch_scale_cpu_capacity(cpumask_first(cpu_map));
  1596. for_each_cpu(i, cpu_map) {
  1597. if (arch_scale_cpu_capacity(i) != cap) {
  1598. asym = true;
  1599. break;
  1600. }
  1601. }
  1602. if (!asym)
  1603. return NULL;
  1604. /*
  1605. * Examine topology from all CPU's point of views to detect the lowest
  1606. * sched_domain_topology_level where a highest capacity CPU is visible
  1607. * to everyone.
  1608. */
  1609. for_each_cpu(i, cpu_map) {
  1610. unsigned long max_capacity = arch_scale_cpu_capacity(i);
  1611. int tl_id = 0;
  1612. for_each_sd_topology(tl) {
  1613. if (tl_id < asym_level)
  1614. goto next_level;
  1615. for_each_cpu_and(j, tl->mask(i), cpu_map) {
  1616. unsigned long capacity;
  1617. capacity = arch_scale_cpu_capacity(j);
  1618. if (capacity <= max_capacity)
  1619. continue;
  1620. max_capacity = capacity;
  1621. asym_level = tl_id;
  1622. asym_tl = tl;
  1623. }
  1624. next_level:
  1625. tl_id++;
  1626. }
  1627. }
  1628. return asym_tl;
  1629. }
  1630. /*
  1631. * Build sched domains for a given set of CPUs and attach the sched domains
  1632. * to the individual CPUs
  1633. */
  1634. static int
  1635. build_sched_domains(const struct cpumask *cpu_map, struct sched_domain_attr *attr)
  1636. {
  1637. enum s_alloc alloc_state = sa_none;
  1638. struct sched_domain *sd;
  1639. struct s_data d;
  1640. struct rq *rq = NULL;
  1641. int i, ret = -ENOMEM;
  1642. struct sched_domain_topology_level *tl_asym;
  1643. bool has_asym = false;
  1644. if (WARN_ON(cpumask_empty(cpu_map)))
  1645. goto error;
  1646. alloc_state = __visit_domain_allocation_hell(&d, cpu_map);
  1647. if (alloc_state != sa_rootdomain)
  1648. goto error;
  1649. tl_asym = asym_cpu_capacity_level(cpu_map);
  1650. /* Set up domains for CPUs specified by the cpu_map: */
  1651. for_each_cpu(i, cpu_map) {
  1652. struct sched_domain_topology_level *tl;
  1653. int dflags = 0;
  1654. sd = NULL;
  1655. for_each_sd_topology(tl) {
  1656. if (tl == tl_asym) {
  1657. dflags |= SD_ASYM_CPUCAPACITY;
  1658. has_asym = true;
  1659. }
  1660. if (WARN_ON(!topology_span_sane(tl, cpu_map, i)))
  1661. goto error;
  1662. sd = build_sched_domain(tl, cpu_map, attr, sd, dflags, i);
  1663. if (tl == sched_domain_topology)
  1664. *per_cpu_ptr(d.sd, i) = sd;
  1665. if (tl->flags & SDTL_OVERLAP)
  1666. sd->flags |= SD_OVERLAP;
  1667. if (cpumask_equal(cpu_map, sched_domain_span(sd)))
  1668. break;
  1669. }
  1670. }
  1671. /* Build the groups for the domains */
  1672. for_each_cpu(i, cpu_map) {
  1673. for (sd = *per_cpu_ptr(d.sd, i); sd; sd = sd->parent) {
  1674. sd->span_weight = cpumask_weight(sched_domain_span(sd));
  1675. if (sd->flags & SD_OVERLAP) {
  1676. if (build_overlap_sched_groups(sd, i))
  1677. goto error;
  1678. } else {
  1679. if (build_sched_groups(sd, i))
  1680. goto error;
  1681. }
  1682. }
  1683. }
  1684. /* Calculate CPU capacity for physical packages and nodes */
  1685. for (i = nr_cpumask_bits-1; i >= 0; i--) {
  1686. if (!cpumask_test_cpu(i, cpu_map))
  1687. continue;
  1688. for (sd = *per_cpu_ptr(d.sd, i); sd; sd = sd->parent) {
  1689. claim_allocations(i, sd);
  1690. init_sched_groups_capacity(i, sd);
  1691. }
  1692. }
  1693. /* Attach the domains */
  1694. rcu_read_lock();
  1695. for_each_cpu(i, cpu_map) {
  1696. rq = cpu_rq(i);
  1697. sd = *per_cpu_ptr(d.sd, i);
  1698. /* Use READ_ONCE()/WRITE_ONCE() to avoid load/store tearing: */
  1699. if (rq->cpu_capacity_orig > READ_ONCE(d.rd->max_cpu_capacity))
  1700. WRITE_ONCE(d.rd->max_cpu_capacity, rq->cpu_capacity_orig);
  1701. cpu_attach_domain(sd, d.rd, i);
  1702. }
  1703. rcu_read_unlock();
  1704. if (has_asym)
  1705. static_branch_inc_cpuslocked(&sched_asym_cpucapacity);
  1706. if (rq && sched_debug_enabled) {
  1707. pr_info("root domain span: %*pbl (max cpu_capacity = %lu)\n",
  1708. cpumask_pr_args(cpu_map), rq->rd->max_cpu_capacity);
  1709. }
  1710. trace_android_vh_build_sched_domains(has_asym);
  1711. ret = 0;
  1712. error:
  1713. __free_domain_allocs(&d, alloc_state, cpu_map);
  1714. return ret;
  1715. }
  1716. /* Current sched domains: */
  1717. static cpumask_var_t *doms_cur;
  1718. /* Number of sched domains in 'doms_cur': */
  1719. static int ndoms_cur;
  1720. /* Attribues of custom domains in 'doms_cur' */
  1721. static struct sched_domain_attr *dattr_cur;
  1722. /*
  1723. * Special case: If a kmalloc() of a doms_cur partition (array of
  1724. * cpumask) fails, then fallback to a single sched domain,
  1725. * as determined by the single cpumask fallback_doms.
  1726. */
  1727. static cpumask_var_t fallback_doms;
  1728. /*
  1729. * arch_update_cpu_topology lets virtualized architectures update the
  1730. * CPU core maps. It is supposed to return 1 if the topology changed
  1731. * or 0 if it stayed the same.
  1732. */
  1733. int __weak arch_update_cpu_topology(void)
  1734. {
  1735. return 0;
  1736. }
  1737. cpumask_var_t *alloc_sched_domains(unsigned int ndoms)
  1738. {
  1739. int i;
  1740. cpumask_var_t *doms;
  1741. doms = kmalloc_array(ndoms, sizeof(*doms), GFP_KERNEL);
  1742. if (!doms)
  1743. return NULL;
  1744. for (i = 0; i < ndoms; i++) {
  1745. if (!alloc_cpumask_var(&doms[i], GFP_KERNEL)) {
  1746. free_sched_domains(doms, i);
  1747. return NULL;
  1748. }
  1749. }
  1750. return doms;
  1751. }
  1752. void free_sched_domains(cpumask_var_t doms[], unsigned int ndoms)
  1753. {
  1754. unsigned int i;
  1755. for (i = 0; i < ndoms; i++)
  1756. free_cpumask_var(doms[i]);
  1757. kfree(doms);
  1758. }
  1759. /*
  1760. * Set up scheduler domains and groups. For now this just excludes isolated
  1761. * CPUs, but could be used to exclude other special cases in the future.
  1762. */
  1763. int sched_init_domains(const struct cpumask *cpu_map)
  1764. {
  1765. int err;
  1766. zalloc_cpumask_var(&sched_domains_tmpmask, GFP_KERNEL);
  1767. zalloc_cpumask_var(&sched_domains_tmpmask2, GFP_KERNEL);
  1768. zalloc_cpumask_var(&fallback_doms, GFP_KERNEL);
  1769. arch_update_cpu_topology();
  1770. ndoms_cur = 1;
  1771. doms_cur = alloc_sched_domains(ndoms_cur);
  1772. if (!doms_cur)
  1773. doms_cur = &fallback_doms;
  1774. cpumask_and(doms_cur[0], cpu_map, housekeeping_cpumask(HK_FLAG_DOMAIN));
  1775. err = build_sched_domains(doms_cur[0], NULL);
  1776. register_sched_domain_sysctl();
  1777. return err;
  1778. }
  1779. /*
  1780. * Detach sched domains from a group of CPUs specified in cpu_map
  1781. * These CPUs will now be attached to the NULL domain
  1782. */
  1783. static void detach_destroy_domains(const struct cpumask *cpu_map)
  1784. {
  1785. unsigned int cpu = cpumask_any(cpu_map);
  1786. int i;
  1787. if (rcu_access_pointer(per_cpu(sd_asym_cpucapacity, cpu)))
  1788. static_branch_dec_cpuslocked(&sched_asym_cpucapacity);
  1789. rcu_read_lock();
  1790. for_each_cpu(i, cpu_map)
  1791. cpu_attach_domain(NULL, &def_root_domain, i);
  1792. rcu_read_unlock();
  1793. }
  1794. /* handle null as "default" */
  1795. static int dattrs_equal(struct sched_domain_attr *cur, int idx_cur,
  1796. struct sched_domain_attr *new, int idx_new)
  1797. {
  1798. struct sched_domain_attr tmp;
  1799. /* Fast path: */
  1800. if (!new && !cur)
  1801. return 1;
  1802. tmp = SD_ATTR_INIT;
  1803. return !memcmp(cur ? (cur + idx_cur) : &tmp,
  1804. new ? (new + idx_new) : &tmp,
  1805. sizeof(struct sched_domain_attr));
  1806. }
  1807. /*
  1808. * Partition sched domains as specified by the 'ndoms_new'
  1809. * cpumasks in the array doms_new[] of cpumasks. This compares
  1810. * doms_new[] to the current sched domain partitioning, doms_cur[].
  1811. * It destroys each deleted domain and builds each new domain.
  1812. *
  1813. * 'doms_new' is an array of cpumask_var_t's of length 'ndoms_new'.
  1814. * The masks don't intersect (don't overlap.) We should setup one
  1815. * sched domain for each mask. CPUs not in any of the cpumasks will
  1816. * not be load balanced. If the same cpumask appears both in the
  1817. * current 'doms_cur' domains and in the new 'doms_new', we can leave
  1818. * it as it is.
  1819. *
  1820. * The passed in 'doms_new' should be allocated using
  1821. * alloc_sched_domains. This routine takes ownership of it and will
  1822. * free_sched_domains it when done with it. If the caller failed the
  1823. * alloc call, then it can pass in doms_new == NULL && ndoms_new == 1,
  1824. * and partition_sched_domains() will fallback to the single partition
  1825. * 'fallback_doms', it also forces the domains to be rebuilt.
  1826. *
  1827. * If doms_new == NULL it will be replaced with cpu_online_mask.
  1828. * ndoms_new == 0 is a special case for destroying existing domains,
  1829. * and it will not create the default domain.
  1830. *
  1831. * Call with hotplug lock and sched_domains_mutex held
  1832. */
  1833. void partition_sched_domains_locked(int ndoms_new, cpumask_var_t doms_new[],
  1834. struct sched_domain_attr *dattr_new)
  1835. {
  1836. bool __maybe_unused has_eas = false;
  1837. int i, j, n;
  1838. int new_topology;
  1839. lockdep_assert_held(&sched_domains_mutex);
  1840. /* Always unregister in case we don't destroy any domains: */
  1841. unregister_sched_domain_sysctl();
  1842. /* Let the architecture update CPU core mappings: */
  1843. new_topology = arch_update_cpu_topology();
  1844. if (!doms_new) {
  1845. WARN_ON_ONCE(dattr_new);
  1846. n = 0;
  1847. doms_new = alloc_sched_domains(1);
  1848. if (doms_new) {
  1849. n = 1;
  1850. cpumask_and(doms_new[0], cpu_active_mask,
  1851. housekeeping_cpumask(HK_FLAG_DOMAIN));
  1852. }
  1853. } else {
  1854. n = ndoms_new;
  1855. }
  1856. /* Destroy deleted domains: */
  1857. for (i = 0; i < ndoms_cur; i++) {
  1858. for (j = 0; j < n && !new_topology; j++) {
  1859. if (cpumask_equal(doms_cur[i], doms_new[j]) &&
  1860. dattrs_equal(dattr_cur, i, dattr_new, j)) {
  1861. struct root_domain *rd;
  1862. /*
  1863. * This domain won't be destroyed and as such
  1864. * its dl_bw->total_bw needs to be cleared. It
  1865. * will be recomputed in function
  1866. * update_tasks_root_domain().
  1867. */
  1868. rd = cpu_rq(cpumask_any(doms_cur[i]))->rd;
  1869. dl_clear_root_domain(rd);
  1870. goto match1;
  1871. }
  1872. }
  1873. /* No match - a current sched domain not in new doms_new[] */
  1874. detach_destroy_domains(doms_cur[i]);
  1875. match1:
  1876. ;
  1877. }
  1878. n = ndoms_cur;
  1879. if (!doms_new) {
  1880. n = 0;
  1881. doms_new = &fallback_doms;
  1882. cpumask_and(doms_new[0], cpu_active_mask,
  1883. housekeeping_cpumask(HK_FLAG_DOMAIN));
  1884. }
  1885. /* Build new domains: */
  1886. for (i = 0; i < ndoms_new; i++) {
  1887. for (j = 0; j < n && !new_topology; j++) {
  1888. if (cpumask_equal(doms_new[i], doms_cur[j]) &&
  1889. dattrs_equal(dattr_new, i, dattr_cur, j))
  1890. goto match2;
  1891. }
  1892. /* No match - add a new doms_new */
  1893. build_sched_domains(doms_new[i], dattr_new ? dattr_new + i : NULL);
  1894. match2:
  1895. ;
  1896. }
  1897. #if defined(CONFIG_ENERGY_MODEL) && defined(CONFIG_CPU_FREQ_GOV_SCHEDUTIL)
  1898. /* Build perf. domains: */
  1899. for (i = 0; i < ndoms_new; i++) {
  1900. for (j = 0; j < n && !sched_energy_update; j++) {
  1901. if (cpumask_equal(doms_new[i], doms_cur[j]) &&
  1902. cpu_rq(cpumask_first(doms_cur[j]))->rd->pd) {
  1903. has_eas = true;
  1904. goto match3;
  1905. }
  1906. }
  1907. /* No match - add perf. domains for a new rd */
  1908. has_eas |= build_perf_domains(doms_new[i]);
  1909. match3:
  1910. ;
  1911. }
  1912. sched_energy_set(has_eas);
  1913. #endif
  1914. /* Remember the new sched domains: */
  1915. if (doms_cur != &fallback_doms)
  1916. free_sched_domains(doms_cur, ndoms_cur);
  1917. kfree(dattr_cur);
  1918. doms_cur = doms_new;
  1919. dattr_cur = dattr_new;
  1920. ndoms_cur = ndoms_new;
  1921. register_sched_domain_sysctl();
  1922. }
  1923. /*
  1924. * Call with hotplug lock held
  1925. */
  1926. void partition_sched_domains(int ndoms_new, cpumask_var_t doms_new[],
  1927. struct sched_domain_attr *dattr_new)
  1928. {
  1929. mutex_lock(&sched_domains_mutex);
  1930. partition_sched_domains_locked(ndoms_new, doms_new, dattr_new);
  1931. mutex_unlock(&sched_domains_mutex);
  1932. }