SMP负载均衡CPU域初始化之sched_group拓扑关系建立
本篇文章主要讲解4.9和4.14 Linux Kernel中sched_group拓扑关系建立过程。
在Linux Kernel中build_sched_domians()方法是真正开始建立调度域拓扑关系的函数，其中包括建立sched_group的拓扑关系：
static int build_sched_domains(const struct cpumask *cpu_map,
struct sched_domain_attr *attr)
{
......
/* Build the groups for the domains */
for_each_cpu(i, cpu_map) {
for (sd = *per_cpu_ptr(d.sd, i); sd; sd = sd->parent) {
sd->span_weight = cpumask_weight(sched_domain_span(sd));
if (sd->flags & SD_OVERLAP) {
if (build_overlap_sched_groups(sd, i))
goto error;
} else {
if (build_sched_groups(sd, i))
goto error;
}
}
}
......
}
该段代码的含义是：对于每个包含在cpu_map（即cpu_active_mask）中的CPU，遍历其在每个SDTL层级中的调度域，然后调用build_overlap_sched_groups()或build_sched_groups()方法建立该CPU在该SDTL层级下的sched_group的拓扑关系。假设SDTL只包含MC、DIE两个层级，则sched_group建立的拓扑关系如下图（本图来自《奔跑吧Linux内核》）：
下面我们结合着sched_group的拓扑关系图主要分析build_sched_groups()方法的实现，首先分析4.9 Linux Kernel中的实现：
static int build_sched_groups(struct sched_domain *sd, int cpu)
{
struct sched_group *first = NULL, *last = NULL;
struct sd_data *sdd = sd->private;---------------------------1
const struct cpumask *span = sched_domain_span(sd);----------2
struct cpumask *covered;
int i;
get_group(cpu, sdd, &sd->groups);----------------------------3
atomic_inc(&sd->groups->ref);
if (cpu != cpumask_first(span))------------------------------4
return 0;
lockdep_assert_held(&sched_domains_mutex);
covered = sched_domains_tmpmask;
cpumask_clear(covered);-------------------------------------5
for_each_cpu(i, span) {
struct sched_group *sg;
int group, j;
if (cpumask_test_cpu(i, covered))-------------------6
continue;
group = get_group(i, sdd, &sg);---------------------7
cpumask_setall(sched_group_mask(sg));
for_each_cpu(j, span) {
if (get_group(j, sdd, NULL) != group)--------8
continue;
cpumask_set_cpu(j, covered);-----------------9
cpumask_set_cpu(j, sched_group_cpus(sg));----10
}
if (!first)
first = sg;
if (last)
last->next = sg;
last = sg;
}
last->next = first;
return 0;
}
下面具体分析该函数：
1、获取当前sched_domain对应的SDTL层级中的struct sd_data数据结构；
2、获取当前sched_domain中包含的兄弟CPU的bitmap；
3、get_group()方法获取当前CPU对应的sched_group并存放在sd->groups指针中，我们来看一下get_group()方法的实现；
static int get_group(int cpu, struct sd_data *sdd, struct sched_group **sg)
{
struct sched_domain *sd = *per_cpu_ptr(sdd->sd, cpu);
struct sched_domain *child = sd->child;
if (child)
cpu = cpumask_first(sched_domain_span(child));
if (sg) {
*sg = *per_cpu_ptr(sdd->sg, cpu);
(*sg)->sgc = *per_cpu_ptr(sdd->sgc, cpu);
atomic_set(&(*sg)->sgc->ref, 1); /* for claim_allocations */
}
return cpu;
}
在build_sched_groups()方法中有3、7、8三个地方调用了get_group()方法，该方法是build_sched_groups()方法实现的核心方法。
get_count()的返回值是CPU，但是如果child存在，则返回的是child sched_domain span中的第一个CPU；如果child不存在，则返回的是当前传进来的CPU。
那如何理解sched_domain之间的父子关系呢？
上文中我们已经假设当前SDTL只包含MC、DIE两个层级，那么MC层级的sched_domain是DIE层级的sched_domain的子sched_domain;那么DIE层级的sched_domain是MC层级的sched_domain的父sched_domain。因此如果当前我们处理的是MC层级的sched_domain（即get_group()方法中struct sched_domain *sd = *per_cpu_ptr(sdd->sd, cpu)得到的是MC层级的sched_domain），那么child不存在，直接返回当前传进来的CPU；如果当前我们处理的是DIE层级的sched_domain（即get_group()方法中struct sched_domain *sd = *per_cpu_ptr(sdd->sd, cpu)得到的是DIE层级的sched_domain），那么child存在，则返回的是child sched_domain span中的第一个CPU（即对应的MC层级中sched_domain span中的第一个CPU）。
下面接着分析build_sched_groups()方法：
4、只处理该sched_domain中第一个CPU的情况，因为没必要重复计算其他兄弟CPU。为什么呢?
我们看到build_sched_groups()方法中有一个for_each_cpu(i, span)循环，在for_each_cpu(i, span)循环中有如下代码：
static int build_sched_groups(struct sched_domain *sd, int cpu)
{
......
for_each_cpu(i, span) {
......
if (!first)
first = sg;
if (last)
last->next = sg;
last = sg;
......
}
last->next = first;
......
}
通过这段代码，我们可以清楚的发现：我们只需要在build_sched_groups()方法中处理该sched_domain中第一个CPU的情况，通过for_each_cpu(i, span)循环，就可以将兄弟CPU的sched_group通过指针串联起来，从而形成兄弟CPU sched_group的拓扑关系，如下图（本图来自《奔跑吧Linux内核》）：
通过该拓扑关系图，我们可以看到兄弟sched_domain的groups指针都指向同一个sched_group链表，既然在build_sched_groups()方法中只处理当前sched_domain兄弟CPU中的第一个CPU的情况，那么其他兄弟CPU sched_domain中的group指针是怎样指向sched_group链表的呢？
这其实是在build_sched_groups()方法中的3代码中实现的：
static int build_sched_groups(struct sched_domain *sd, int cpu)
{
......
get_group(cpu, sdd, &sd->groups);----------------------------3
atomic_inc(&sd->groups->ref);
if (cpu != cpumask_first(span))------------------------------4
return 0;
......
}
我们可以看到在4之前调用了3（即get_group(cpu, sdd, &sd->groups)）,该处调用get_group()目的就是为了让兄弟CPU sched_domain中的group指针指向sched_group链表。
5、clear一下covered这个cpumask；
6、7、8、9、10这几处的代码配合使用。
static int build_sched_groups(struct sched_domain *sd, int cpu)
{
......
for_each_cpu(i, span) {
struct sched_group *sg;
int group, j;
if (cpumask_test_cpu(i, covered))-------------------6
continue;
group = get_group(i, sdd, &sg);---------------------7
cpumask_setall(sched_group_mask(sg));
for_each_cpu(j, span) {
if (get_group(j, sdd, NULL) != group)--------8
continue;
cpumask_set_cpu(j, covered);-----------------9
cpumask_set_cpu(j, sched_group_cpus(sg));----10
}
......
return 0;
}
7处的返回值：如果是MC层级，则返回的是i的值；如果是DIE层级，则返回的是child sched_domain span中的第一个CPU。8处代码的含义需要结合图3.10来分析（本图来自《奔跑吧Linux内核》）：
假设现在是MC层级，以domain_mc_0为例分析8处的代码。首先7处代码的返回值是CPU0， 由于MC层级没有child层级，因此8处代码每次循环的返回值都不一样（即只有两次循环，返回值分别是cpu0, cpu1），因此当返回值为cpu0时，会执行的9和10，当返回值为cpu1时，不会执行9和10，即group_mc_0中的cpumask只包含cpu0；在下一次进行for_each_cpu(i, span)循环时，i=cpu1，由于cpu1不包含在covered中，因此可以执行到7，此时7处的返回值为CPU1，经过8处代码的过滤只有j=cpu1时，才能执行到9和10，即group_mc_1中的cpumask只包含cpu1。
假设现在是DIE层级，以domain_die_0为例分析8处代码。for_each_cpu(i, span)第一次循环时i=cpu0。由于DIE层级存在child层级（即MC层级），则7处返回的是cpu0在DIE层级child层级（即MC层级）对应的sched_domain（即domain_mc_0） span中的第一个cpu（即cpu0）。在for_each_cpu(j, span)第一次循环时j=cpu0，8处的get_group()的返回值为domain_mc_0 span中的第一个cpu（即cpu0），因此可以执行到9和10；for_each_cpu(j, span)第二次循环时j=cpu1，8处的get_group()的返回值为domain_mc_1 span中的第一个cpu（即cpu0），因此可以执行到9和10；for_each_cpu(j, span)第三、四次循环时j分别为cpu2，cpu3，8处的get_group()的返回值为domain_mc_2和domain_mc_3 span中的第一个cpu（即cpu2），因此不能执行到9和10，因此DIE层级的group_die_0的cpumask中只包含CPU0和CPU1。当 for_each_cpu(i, span)第二次循环时i=cpu1，在7处发现cpu1已经包含在了covered中，因此就不再执行下面的代码。for_each_cpu(i, span)的第三和第四次循环参考第一和第二次循环。
下面我们来看一下build_sched_groups()方法在4.14 Linux Kernel中的实现：
static int build_sched_groups(struct sched_domain *sd, int cpu)
{
struct sched_group *first = NULL, *last = NULL;
struct sd_data *sdd = sd->private;
const struct cpumask *span = sched_domain_span(sd);
struct cpumask *covered;
int i;
lockdep_assert_held(&sched_domains_mutex);
covered = sched_domains_tmpmask;
cpumask_clear(covered);
for_each_cpu_wrap(i, span, cpu) {
struct sched_group *sg;
if (cpumask_test_cpu(i, covered))
continue;
sg = get_group(i, sdd);
cpumask_or(covered, covered, sched_group_span(sg));
if (!first)
first = sg;
if (last)
last->next = sg;
last = sg;
}
last->next = first;
sd->groups = first;
return 0;
}
在4.14 Linux Kernel中，理解build_sched_groups()方法方法的实现，关键是要理解for_each_cpu_wrap()的实现:
#define for_each_cpu_wrap(cpu, mask, start) \
for ((cpu) = cpumask_next_wrap((start)-1, (mask), (start), false); \
(cpu) < nr_cpumask_bits; \
(cpu) = cpumask_next_wrap((cpu), (mask), (start), true))
for_each_cpu_wrap()的实现主要依赖于cpumask_next_wrap()的实现：
int cpumask_next_wrap(int n, const struct cpumask *mask, int start, bool wrap)
{
int next;
again:
next = cpumask_next(n, mask);
if (wrap && n < start && next >= start) {
return nr_cpumask_bits;
} else if (next >= nr_cpumask_bits) {
wrap = true;
n = -1;
goto again;
}
return next;
}
EXPORT_SYMBOL(cpumask_next_wrap);
我们还是以图3.10为例来分析cpumask_next_wrap()方法为什么要如此实现。
cpumask_next()方法要不返回mask中的某个cpu，要不返回>=nr_cpumask_bits。
首先假设#define for_each_cpu_wrap(cpu, mask, start)中的第二个参数mask为cpu0|cpu1|cpu2， 第三个参数start为cpu1。
那么在我们开始遍历mask时，由于start为cpu1，则cpu0将会被遗漏，因此在cpumask_next_wrap()方法中当next >= nr_cpumask_bits时，我们设置wrap=true, n=-1同时跳转到again处重新使用cpumask_next()方法获取cpu，此时返回的刚好是cpu0，因此cpu0被遗漏的情况可以避免掉。