Linux程序管理之ARM64的三級排程域

基本原理

schedule domain分為三個層次，從低到高依次為SMT，MC和ALL Cpu。SMT即single multi thread，level0排程域，同一個實體Core中的所有thread都在該排程域中；MC即multi Core，level 1排程域，同一個cluster中的所有實體Core中的CPU都在該排程域中；ALL Cpu，level2排程域，也是最進階别的排程域，該排程域包括SoC中所有的CPU。其中如果不支援超線程，則沒有SMT排程域，如果是單核SoC，則沒有MC排程域，但是包括所有CPU的排程域一定是存在的，也就是說單核系統隻有一個排程域，這個排程域中隻有一個CPU。

下面我們用一個比較典型架構的SoC來做說明：

SoC拓撲

該SoC內建了兩個NUMA Node，每個NUMA Node內建兩個cluster，每個Cluster內建了兩個實體Core，每個實體Core又虛拟出了兩個邏輯CPU。

從Cpu0的視圖來看排程域

Cpu0和Cpu1同屬于一個實體Core，是以他們兩個屬于一級排程域；Cpu0，Cpu1，Cpu2和Cpu3同屬于一個Cluster，是以他們四個屬于二級排程域；Cpu0-Cpu15屬于三級排程域。由此拓撲我們可以歸納出幾個特性要點：

• 一級排程域中的CPU親和性最高。
• 高一級的排程域覆寫低一級的排程域。
• 做負載均衡的時候應該先嘗試在一級排程域做均衡，一級排程域均衡失敗，再考慮二級排程域，二級排程域失敗再考慮三級排程域。

從Cpu8的視圖看排程域

Cpu8和Cpu9同屬于一個實體Core，是以他們兩個屬于一級排程域；Cpu8，Cpu9，Cpu10和Cpu11同屬于一個Cluster，是以他們四個屬于二級排程域；Cpu0-Cpu15屬于三級排程域。由此我們可以知道，對不同的CPU來說，一級排程域和二級排程域可能是不同的，但是三級排程域一定是相同的，都包括所有的CPU。

CPU拓撲

DTS中定義的CPU拓撲最終要反應到軟體上，ARM64的CPU拓撲用結構體struct cpu_topology來描述，本章節會詳細介紹該結構體的定義以及初始化。

cpu_topology結構體定義

struct cpu_topology {
	int thread_id;
	int core_id;
	int cluster_id;
	cpumask_t thread_sibling;
	cpumask_t core_sibling;
};
           

每一個CPU都會維護這麼一個結構體執行個體，用來描述CPU拓撲，從不同的CPU的視角來看，CPU的拓撲是不一樣的。

• thread_id 目前CPU的Thread ID從mpidr_el1寄存器中擷取
• core_id 目前CPU的Core ID從mpidr_el1寄存器中擷取
• cluster_id 目前CPU的Cluster ID從mpidr_el1寄存器中擷取
• 目前CPU的兄弟thread，即在同一個Core中的CPU。這裡要注意的是兄弟thread也包括目前CPU。比如上圖中CPU0的兄弟thread是CPU0和CPU1。
• 目前CPU的兄弟Core，即在同一個Cluster中的CPU。比如上圖中CPU0的兄弟Core實際包括CPU0，CPU1,CPU2和CPU3。

cpu_topology初始化

調用store_cpu_topology接口完成CPU拓撲的初始化，有兩條路調用該接口。

Boot CPU的調用路徑如下：

kernel_init_freeable->smp_prepare_cpus->store_cpu_topology

從CPU的調用路徑如下：

secondary_start_kernel->store_cpu_topology

也就是說每個CPU都會調用store_cpu_topology接口完成CPU拓撲的初始化。

void store_cpu_topology(unsigned int cpuid)
{
	struct cpu_topology *cpuid_topo = &cpu_topology[cpuid];
	u64 mpidr;

	if (cpuid_topo->cluster_id != -1)
		goto topology_populated;

	mpidr = read_cpuid_mpidr();

	/* Uniprocessor systems can rely on default topology values */
	if (mpidr & MPIDR_UP_BITMASK)
		return;

	/* Create cpu topology mapping based on MPIDR. */
	if (mpidr & MPIDR_MT_BITMASK) {
		/* Multiprocessor system : Multi-threads per core */
		cpuid_topo->thread_id  = MPIDR_AFFINITY_LEVEL(mpidr, 0);
		cpuid_topo->core_id    = MPIDR_AFFINITY_LEVEL(mpidr, 1);
		cpuid_topo->cluster_id = MPIDR_AFFINITY_LEVEL(mpidr, 2) |
					 MPIDR_AFFINITY_LEVEL(mpidr, 3) << 8;
	} else {
		/* Multiprocessor system : Single-thread per core */
		cpuid_topo->thread_id  = -1;
		cpuid_topo->core_id    = MPIDR_AFFINITY_LEVEL(mpidr, 0);
		cpuid_topo->cluster_id = MPIDR_AFFINITY_LEVEL(mpidr, 1) |
					 MPIDR_AFFINITY_LEVEL(mpidr, 2) << 8 |
					 MPIDR_AFFINITY_LEVEL(mpidr, 3) << 16;
	}

	pr_debug("CPU%u: cluster %d core %d thread %d mpidr %#016llx\n",
		 cpuid, cpuid_topo->cluster_id, cpuid_topo->core_id,
		 cpuid_topo->thread_id, mpidr);

topology_populated:
	update_siblings_masks(cpuid);
}
           

• 從mpidr_el1寄存器擷取thread_id，core_id和cluster_id。
• 調用update_siblings_masks接口更新sibling

static void update_siblings_masks(unsigned int cpuid)
{
	struct cpu_topology *cpu_topo, *cpuid_topo = &cpu_topology[cpuid];
	int cpu;

	/* update core and thread sibling masks */
	for_each_possible_cpu(cpu) {
		cpu_topo = &cpu_topology[cpu];

		if (cpuid_topo->cluster_id != cpu_topo->cluster_id)
			continue;

		cpumask_set_cpu(cpuid, &cpu_topo->core_sibling);
		if (cpu != cpuid)
			cpumask_set_cpu(cpu, &cpuid_topo->core_sibling);

		if (cpuid_topo->core_id != cpu_topo->core_id)
			continue;

		cpumask_set_cpu(cpuid, &cpu_topo->thread_sibling);
		if (cpu != cpuid)
			cpumask_set_cpu(cpu, &cpuid_topo->thread_sibling);
	}
}
           

• 如果clusterID相同，說明是兄弟core，更新core_sibling。
• 如果coreID相同，說明是兄弟thread，更新core_sibling。

排程域的初始化

kernel_init_freeable->sched_init_smp->init_sched_domains(cpu_active_mask);

static int init_sched_domains(const struct cpumask *cpu_map)
{
	int err;

	arch_update_cpu_topology();
	ndoms_cur = 1;
	doms_cur = alloc_sched_domains(ndoms_cur);
	if (!doms_cur)
		doms_cur = &fallback_doms;
	cpumask_andnot(doms_cur[0], cpu_map, cpu_isolated_map);
	err = build_sched_domains(doms_cur[0], NULL);
	register_sched_domain_sysctl();

	return err;
}
           

• 根據cpu_active_mask和cpu_isolated_map計算得到需要做排程域初始化的CPU。cpu_active_mask記錄處于active狀态的CPU，cpu_isolated_map定義不需要加入排程域的CPU。
• 調用 build_sched_domains做排程域初始化。

在介紹build_sched_domains函數之前，我們先來看一個資料結構：

static struct sched_domain_topology_level default_topology[] = {
#ifdef CONFIG_SCHED_SMT
	{ cpu_smt_mask, cpu_smt_flags, SD_INIT_NAME(SMT) },
#endif
#ifdef CONFIG_SCHED_MC
	{ cpu_coregroup_mask, cpu_core_flags, SD_INIT_NAME(MC) },
#endif
	{ cpu_cpu_mask, SD_INIT_NAME(DIE) },
	{ NULL, },
};

static struct sched_domain_topology_level *sched_domain_topology =
	default_topology;
           

• 如果支援超線程，則打開宏開關CONFIG_SCHED_SMT，cpu_smt_mask定義了最低一級排程域包括哪些CPU，其實就是thread_sibling。
• 如果支援多核，則打開宏CONFIG_SCHED_MC，cpu_coregroup_mask定義了次最低一級排程域包括哪些CPU，起始就是core_sibling。
• cpu_cpu_mask定義了最高一級的排程域包括哪些CPU，起始就是SoC中所有的CPU。

下面我們正式來分析build_sched_domains函數：

static int build_sched_domains(const struct cpumask *cpu_map,
			       struct sched_domain_attr *attr)
{
	enum s_alloc alloc_state;
	struct sched_domain *sd;
	struct s_data d;
	struct rq *rq = NULL;
	int i, ret = -ENOMEM;

	alloc_state = __visit_domain_allocation_hell(&d, cpu_map);
	if (alloc_state != sa_rootdomain)
		goto error;

	/* Set up domains for cpus specified by the cpu_map. */
	for_each_cpu(i, cpu_map) {
		struct sched_domain_topology_level *tl;

		sd = NULL;
		for_each_sd_topology(tl) {
			sd = build_sched_domain(tl, cpu_map, attr, sd, i);
			if (tl == sched_domain_topology)
				*per_cpu_ptr(d.sd, i) = sd;
			if (tl->flags & SDTL_OVERLAP || sched_feat(FORCE_SD_OVERLAP))
				sd->flags |= SD_OVERLAP;
			if (cpumask_equal(cpu_map, sched_domain_span(sd)))
				break;
		}
	}

	/* 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;
			}
		}
	}

	/* Calculate CPU capacity for physical packages and nodes */
	for (i = nr_cpumask_bits-1; i >= 0; i--) {
		if (!cpumask_test_cpu(i, cpu_map))
			continue;

		for (sd = *per_cpu_ptr(d.sd, i); sd; sd = sd->parent) {
			claim_allocations(i, sd);
			init_sched_groups_capacity(i, sd);
		}
	}

	/* Attach the domains */
	rcu_read_lock();
	for_each_cpu(i, cpu_map) {
		rq = cpu_rq(i);
		sd = *per_cpu_ptr(d.sd, i);

		/* Use READ_ONCE()/WRITE_ONCE() to avoid load/store tearing: */
		if (rq->cpu_capacity_orig > READ_ONCE(d.rd->max_cpu_capacity))
			WRITE_ONCE(d.rd->max_cpu_capacity, rq->cpu_capacity_orig);

		cpu_attach_domain(sd, d.rd, i);
	}
	rcu_read_unlock();

	if (rq && sched_debug_enabled) {
		pr_info("span: %*pbl (max cpu_capacity = %lu)\n",
			cpumask_pr_args(cpu_map), rq->rd->max_cpu_capacity);
	}

	ret = 0;
error:
	__free_domain_allocs(&d, alloc_state, cpu_map);
	return ret;
}
           

• 調用__visit_domain_allocation_hell為排程域結構體配置設定空間。我們假設支援超線程和多核，那麼存在三級排程域，是以每個CPU都會配置設定三個排程域，因為從它的視角可以看到三級排程域。
• 排程域的初始化，這裡尤其要注意排程域中的span成員，它用于記錄目前排程域中的所有CPU，通過該接口設定：cpumask_and(sched_domain_span(sd), cpu_map, tl->mask(cpu));
• 排程域父子關系設定，父排程域覆寫子排程域，三級排程域的父子關系顯而易見。
• 排程組初始化，排程組是在排程域中對CPU的抽象，每一個排程組都對應一個CPU。這裡會将每一個排程域中的排程組組成一個環形連結清單，做CPU間的負載均衡的時候，實際上是在排程域中的排程組之間做負載均衡。