Analysis of Linux kernel scheduler source code initialization

void __init sched_init(void)
{
    unsigned long ptr = 0;
    int i;
 
    /*
     * Initialize the global default rt and dl CPU bandwidth control data structure*
     * The rt_bandwidth and dl_bandwidth here are used to control the global DL and RT bandwidth usage to prevent the real-time process from using too much CPU, which will cause starvation of the ordinary CFS process*/
    init_rt_bandwidth(&def_rt_bandwidth, global_rt_period(), global_rt_runtime());
    init_dl_bandwidth(&def_dl_bandwidth, global_rt_period(), global_rt_runtime());
 
#ifdef CONFIG_SMP
    /*
     * Initialize the default root domain *
     * The root domain is an important data structure for global balancing of real-time processes such as dl/rt. Taking rt as an example, * root_domain->cpupri is the highest priority of the RT task running on each CPU within the root domain, as well as * the distribution of tasks of different priorities on the CPU. Through the data of cpupri, in rt enqueue/dequeue
     * When the rt scheduler can ensure that high-priority tasks are run first based on the rt task distribution*/
    init_defrootdomain();
#endif
 
#ifdef CONFIG_RT_GROUP_SCHED
    /*
     * If the kernel supports RT group scheduling (RT_GROUP_SCHED), then bandwidth control for RT tasks can be done using cgroup
     * The granularity is used to control the CPU bandwidth usage of rt tasks in each group*
     * RT_GROUP_SCHED allows RT tasks to control bandwidth as a whole in the form of cpu cgroups. * This can bring greater flexibility to RT bandwidth control (without RT_GROUP_SCHED, only the global * bandwidth usage of RT can be controlled, and the bandwidth of some RT processes cannot be controlled by specifying a group)
     */
    init_rt_bandwidth(&root_task_group.rt_bandwidth,
            global_rt_period(), global_rt_runtime());
#endif /* CONFIG_RT_GROUP_SCHED */
 
    /* Initialize the run queue for each CPU */
    for_each_possible_cpu(i) {
        struct rq *rq;
 
        rq = cpu_rq(i);
        raw_spin_lock_init(&rq->lock);
        /*
         * Initialize the run queue of cfs/rt/dl on rq * Each scheduling type has its own run queue on rq, and each scheduling class manages its own process * When pick_next_task(), the kernel selects tasks from high to low according to the order of scheduling class priority * This ensures that high-priority scheduling class tasks will be run first *
         * Stop and idle are special scheduling types, which are designed for special purposes and do not allow users to * create processes of the corresponding type, so the kernel does not design corresponding run queues in rq */
        init_cfs_rq(&rq->cfs);
        init_rt_rq(&rq->rt);
        init_dl_rq(&rq->dl);
#ifdef CONFIG_FAIR_GROUP_SCHED
        /*
         * CFS group scheduling (group_sched), can control CFS through cpu cgroup * can provide CPU ratio control between groups through cpu.shares (let different cgroups share CPU according to corresponding * ratios), and can also set quotas through cpu.cfs_quota_us (similar to RT's * bandwidth control). CFS group_sched bandwidth control is one of the basic underlying technologies for container implementation*
         * root_task_group is the default root task_group, other cpu cgroups will use it as * parent or ancestor. The initialization here associates root_task_group with the cfs run queue of rq*. What is done here is very interesting. Directly set root_task_group->cfs_rq[cpu] = &rq->cfs
         * In this way, the process under the cpu cgroup root or the sched_entity of cgroup tg will be directly added to rq->cfs
         * In the queue, one layer of search overhead can be reduced.
         */
        root_task_group.shares = ROOT_TASK_GROUP_LOAD;
        INIT_LIST_HEAD(&rq->leaf_cfs_rq_list);
        rq->tmp_alone_branch = &rq->leaf_cfs_rq_list;
        init_cfs_bandwidth(&root_task_group.cfs_bandwidth);
        init_tg_cfs_entry(&root_task_group, &rq->cfs, NULL, i, NULL);
#endif /* CONFIG_FAIR_GROUP_SCHED */
 
        rq->rt.rt_runtime = def_rt_bandwidth.rt_runtime;
#ifdef CONFIG_RT_GROUP_SCHED
        /* Initialize the rt run queue on rq, similar to the group scheduling initialization of CFS above*/
        init_tg_rt_entry(&root_task_group, &rq->rt, NULL, i, NULL);
#endif
 
#ifdef CONFIG_SMP
        /*
         * Here rq is associated with the default def_root_domain. If it is an SMP system, then later in sched_init_smp, the kernel will create a new root_domain and replace this def_root_domain
         */
        rq_attach_root(rq, &def_root_domain);
#endif /* CONFIG_SMP */
    }
 
    /*
     * Register the SCHED_SOFTIRQ soft interrupt service function of CFS* This soft interrupt is prepared for periodic load balancing and nohz idle load balance*/
    init_sched_fair_class();
 
    scheduler_running = 1;
}

/*
 * Called by boot processor to activate the rest.
 *
 * In SMP architecture, BSP needs to bring up all other non-boot cp
 */
void __init smp_init(void)
{
    int num_nodes, num_cpus;
    unsigned int cpu;
 
    /* Create an idle thread for each CPU */
    idle_threads_init();
    /* Register cpuhp thread to the kernel */
    cpuhp_threads_init();
 
    pr_info("Bringing up secondary CPUs ...\n");
 
    /*
     * FIXME: This should be done in userspace --RR
     *
     * If the CPU is not online, bring it up with cpu_up
     */
    for_each_present_cpu(cpu) {
        if (num_online_cpus() >= setup_max_cpus)
            break;
        if (!cpu_online(cpu))
            cpu_up(cpu);
    }
     
    .............
}

/*
 * Topology list, bottom-up.
 *
 * Linux default physical topology *
 * There are only three levels of physical topology here, and the NUMA domain is automatically detected in sched_init_numa() * If a NUMA domain exists, the corresponding NUMA scheduling domain will be added *
 * Note: The default default_topology scheduling domain may have some problems. For example, some platforms do not have DIE domains (Intel platforms), so LLC and DIE domains may overlap. * Therefore, after the scheduling domain is established, the kernel will scan all scheduling in cpu_attach_domain(). * If there is a scheduling overlap, it will destroy the overlapping scheduling domain corresponding to destroy_sched_domain*/
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, },
};

/*
 * NUMA scheduling domain initialization (create a new sched_domain_topology physical topology structure based on hardware information)
 *
 * The kernel does not actively add NUMA topology by default, you need to configure it (if NUMA is enabled)
 * If NUMA is enabled, it is necessary to determine whether to add the * sched_domain_topology_level domain based on the hardware topology information (only after adding this domain will the kernel create the NUMA DOMAIN when initializing * sched_domain later)
 */
void sched_init_numa(void)
{
    ................
    /*
     * Here, we will check whether there is a NUMA domain (even multiple NUMA domains) based on the distance, and then update it to the physical topology structure based on the * situation. When you create a scheduling domain later, you will use this new *physical topology to create a new scheduling domain*/
    for (j = 1; j < level; i++, j++) {
        tl[i] = (struct sched_domain_topology_level){
            .mask = sd_numa_mask,
            .sd_flags = cpu_numa_flags,
            .flags = SDTL_OVERLAP,
            .numa_level = j,
            SD_INIT_NAME(NUMA)
        };
    }
 
    sched_domain_topology = tl;
 
    sched_domains_numa_levels = level;
    sched_max_numa_distance = sched_domains_numa_distance[level - 1];
 
    init_numa_topology_type();
}

/*
 * Set up scheduler domains and groups. For now this just excludes isolated
 * CPUs, but could be used to exclude other special cases in the future.
 */
int sched_init_domains(const struct cpumask *cpu_map)
{
    int err;
 
    zalloc_cpumask_var(&sched_domains_tmpmask, GFP_KERNEL);
    zalloc_cpumask_var(&sched_domains_tmpmask2, GFP_KERNEL);
    zalloc_cpumask_var(&fallback_doms, GFP_KERNEL);
 
    arch_update_cpu_topology();
    ndoms_cur = 1;
    doms_cur = alloc_sched_domains(ndoms_cur);
    if (!doms_cur)
        doms_cur = &fallback_doms;
    /*
     * doms_cur[0] indicates the cpumask that the scheduling domain needs to overwrite
     *
     * If isolcpus= is used to isolate some CPUs in the system, these CPUs will not be added to the scheduling * domain, that is, these CPUs will not participate in load balancing (load balancing here includes DL/RT and CFS).
     * Here, isolate is used by cpu_map & housekeeping_cpumask(HK_FLAG_DOMAIN)
     * cpu is removed, so as to ensure that the isolate cpu is not included in the established scheduling domain
     */
    cpumask_and(doms_cur[0], cpu_map, housekeeping_cpumask(HK_FLAG_DOMAIN));
    /* Implementation function of establishing scheduling domain*/
    err = build_sched_domains(doms_cur[0], NULL);
    register_sched_domain_sysctl();
 
    return err;
}

/*
 * Build sched domains for a given set of CPUs and attach the sched domains
 * to the individual CPUs
 */
static int
build_sched_domains(const struct cpumask *cpu_map, struct sched_domain_attr *attr)
{
    enum s_alloc alloc_state = sa_none;
    struct sched_domain *sd;
    struct s_data d;
    struct rq *rq = NULL;
    int i, ret = -ENOMEM;
    struct sched_domain_topology_level *tl_asym;
    bool has_asym = false;
 
    if (WARN_ON(cpumask_empty(cpu_map)))
        goto error;
 
    /*
     * Most processes in Linux are CFS-scheduled, so sched_domain in CFS will be frequently accessed and modified (such as nohz_idle and various statistics in sched_domain), so sched_domain
     * The design needs to give priority to efficiency, so the kernel uses the percpu method to implement sched_domain
     * Each level of sd between CPUs is an independently applied percpu variable, so that the characteristics of percpu can be used to solve the concurrency competition problem between them* (1. No lock protection is required 2. No cacheline pseudo-sharing)
     */
    alloc_state = __visit_domain_allocation_hell(&d, cpu_map);
    if (alloc_state != sa_rootdomain)
        goto error;
 
    tl_asym = asym_cpu_capacity_level(cpu_map);
 
    /*
     * Set up domains for CPUs specified by the cpu_map:
     *
     * Here we will traverse all CPUs in cpu_map and create corresponding physical topology structures for these CPUs (
     * for_each_sd_topology)'s multi-level scheduling domain.
     *
     * When the scheduling domain is established, the span corresponding to the cpu in the scheduling domain at this level will be obtained through tl->mask(cpu) (that is, the cpu and other corresponding cpu form this scheduling domain). The sd corresponding to the CPU in the same scheduling domain will be initialized to the same at the beginning (including sd->pan,
     * sd->imbalance_pct and sd->flags).
     */
    for_each_cpu(i, cpu_map) {
        struct sched_domain_topology_level *tl;
 
        sd = NULL;
        for_each_sd_topology(tl) {
            int dflags = 0;
 
            if (tl == tl_asym) {
                dflags |= SD_ASYM_CPUCAPACITY;
                has_asym = true;
            }
 
            sd = build_sched_domain(tl, cpu_map, attr, sd, dflags, i);
 
            if (tl == sched_domain_topology)
                *per_cpu_ptr(d.sd, i) = sd;
            if (tl->flags & SDTL_OVERLAP)
                sd->flags |= SD_OVERLAP;
            if (cpumask_equal(cpu_map, sched_domain_span(sd)))
                break;
        }
    }
 
    /*
     * Build the groups for the domains
     *
     * Create a dispatch group *
     * We can see the role of sched_group from the implementation of two scheduling domains* 1. NUMA domain 2. LLC domain*
     * numa sched_domain->span will include all CPUs on the NUMA domain. When balancing is required, * NUMA domains should not be based on CPUs, but on sockets, that is, only socket1 and socket2
     * The CPU will be migrated between the two sockets only when there is an extreme imbalance. If sched_domain is used to implement this * abstraction, it will lead to insufficient flexibility (as can be seen in the MC domain below), so the kernel will use sched_group to * represent a CPU set, and each socket belongs to a sched_group. Migration is allowed only when the two sched_groups are unbalanced*
     * The MC domain is similar. The CPU may be hyperthreaded, but the performance of the hyperthreading is not equivalent to that of the physical core. A pair* of hyperthreads roughly equals 1.2 times the performance of a physical core. Therefore, when scheduling, we need to consider the balance between hyperthreading* pairs, that is, we must first satisfy the balance between CPUs, and then the balance of hyperthreading within the CPU. At this time, sched_group is used for abstraction. One sched_group represents one physical CPU (two hyperthreads). At this time, LLC ensures the balance between CPUs, thus avoiding an extreme situation: the balance between hyperthreads but the imbalance on physical cores. At the same time, it can ensure that when scheduling and selecting cores, the kernel will give priority to physical threads. Only after the physical threads are used up, will it consider using another hyperthread, so that the system can make better use of the CPU computing power.
    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
     *
     * sched_group_capacity is used to indicate the CPU power available to sg*
     * sched_group_capacity takes into account the different computing power of each CPU (different maximum frequency settings,
     * ARM big and small cores, etc.), remove the CPU used by the RT process (sg is prepared for CFS, so it is necessary to * remove the CPU computing power used by the DL/RT process on the CPU), etc., leaving the available computing power for CFS sg (because * when load balancing, not only the load on the CPU should be considered, but also the CFS on this sg
     * Available computing power. If there are fewer processes on this sg, but sched_group_capacity is also small, processes should not be migrated to this sg)
     */
    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();
    /*
     * Bind each CPU's rq to rd (root_domain), and check if sd overlaps. * If so, destroy_sched_domain() is used to remove it (so we can see that * Intel servers have only 3 scheduling domains, and the DIE domain actually overlaps with the LLC domain, so it will be removed here)
     */
    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 (has_asym)
        static_branch_inc_cpuslocked(&sched_asym_cpucapacity);
 
    if (rq && sched_debug_enabled) {
        pr_info("root domain 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;
}