Scheduler -18- (Load Balance 4 EAS)

<kernel v5.4>

EAS(Energy Aware Scheduling)

 

모바일 시스템으로 인해 에너지 절약에 대한 요구, 터치에 대한 빠른 application의 빠른 응답 성능, 그리고 높은 성능 유지 등에 대한 사용자의 요구가 매우 높은데, 기존의 커널 스케줄러 만으로는 각각의 세 항목들을 동시에 만족시키기란 매우 어려운 상황이었다. 이에 대한 시장의 요구를 반영한 솔루션이 안드로이드 진영에서 먼저 시작되어 EAS를 탄생시켰고, 메인 라인 커널에도 업스트림되었다.

  • 참고로 3 가지 항목을 동시(at a time)에 높일 수 없다. 그런 것이 가능할 수는 없다. 다만 환경 조건에 따라 어느 한 쪽에 더 힘을 준다.
  • PM에서 절전을 하는 것 이외에 스케줄러 분야에서는 빠른 응답과 높은 성능 위주로 코드가 튜닝되어 왔는데, EAS 출현 후 에너지 효율에 대해 더 강력한 로직들이 추가되었다.

 

1) 에너지 효율을 달성하기 위해 전력 관리(Power Management) 기술 중 하나인 cpuidle과 관련하여 빅/리틀 클러스터 개념이 탄생되었고 다음과 같이 세 종류의 마이그레이션에 대한 운용 개념이 탄생되었고, 최근의 모바일 시스템은 빅/미디엄/리틀 클러스터를 동시에 사용하는 HMP 방식으로 추세가 바뀌었다. 또한 cpufreq(DVFS)를 통해 에너지 이득을 얻고자 하였다.

  • 클러스터 운용
    • Clustered switching (Cluster migration)
      • 클러스터 단위로 빅/리틀 선택 운용
    • In-kernel switcher (CPU migration)
      • cpu core 단위로 빅/리틀 선택 운용
    • HMP(Heterogeneous multi-processing) 운용
      • 그냥 동시에 같이 운용하고, EAS를 통해 에너지 와 성능에 대해 적절한 cpu를 선택하는 스케줄 방법을 사용한다.
  • DVFS 운용
    • cpu의 유틸 로드에 따라 코어의 주파수를 여러 단계로 변화시켜 절전하는 시스템을 채용하였다.

 

2) 빠른 응답을 달성하기 위해 안드로이드 진영에서는 32ms 단위로 절반씩 deacy되는 특성을 가진 PELT를 WALT로 바꾸어 로드의 상향에 대해 4배, 하향에 대해 8배를 가진 특성을 사용하여 응답성을 높이고, uclamp를 통해 특정 application의 EAS를 통해 적절한 core를 찾아 빠르게 운용된다.

 

3) 높은 성능을 달성하기 위해 EAS는 빅/리틀 코어에 대해 필요 시 빅 코어에 대한 선택을 강화하였다.

  • 태스크의 유틸 로드가 리틀로 마이그레이션 시 capacity 부족으로 인한 misfit 판정 시 리틀로의 마이그레이션을 제한한다.
  • uclamp를 통해 특정 application이 동작 시 유틸 로드 범위를 제한하는 것으로 성능을 위한 빅 클러스터 또는 절전을 위한 리틀 클러스터를 조금 더 선택할 수 있도록 도와준다.

 

EAS component

다음 그림은 EAS를 구성하는 component들을 보여준다. 이들은 모바일 분야에서 치열하게 연구되어 계속 추가되고 있고, 일부는 새로운 기술로 대체되고 있다. (퀄컴, 삼성, 구글, ARM사에서 주도적으로 경쟁하였고 근래에는 서로의 장점을 모아 거의 유사해지고 있다.)

  • EAS Core
    • 스케줄러 내에서 에너지 모델로 동작하는 Task Placement 로직
    • WALT 또는 PELT
  • Schedutil
    • 스케줄러 결합된 새로운 CPUFreq(DVFS) based governor
  • CPUIdle
    • 스케줄러 결합된 새로운 CPUIdle based governor
  • UtilClamp(uclamp)
    • Task Placement와 schedutil에 영향을 준다.
    • 기존 SchedTune을 대체하여 사용한다.

 

Wake 밸런싱과 EA Task Placement

빅/리틀 클러스터를 가진 시스템처럼 Asymetric cpu capacity를 사용하는 시스템에서 깨어난 태스크가 Wake 밸런싱 과정에서 어떠한 cpu에서 동작해야 유리한지 알아본다.

  •                            에너지(J)
  • 파워(W) = ————————–
  •                         시간(second)

 

  •                                           명령어(instruction)
  • 성능(performance) = ——————————
  •                                               시간(second)

 

  • 파워(W)                에너지(J) / 시간(second)                          에너지(J)
  • ———–  =  ————————————————– = —————————— = EAS의 목적
  • 성능(P)          명령어(instruction) / 시간(second)         명령어(instruction)

 

EAS의 경우 성능은 높을 수록 좋고, 파워는 낮을 수록 좋으므로 EAS의 값이 작을 수록 좋다.

 

다음 그림은 wake 밸런스에 의해 깨어날 cpu를 찾는 과정을 보여준다. 깊게 잠든 C2 idle 상태의 cpu 보다 살짝 잠든 WFI 상태의 cpu를 선택하는 모습을 보여준다.

 

다음 그림은 wake 밸런스에 의해 꺠어날 cpu를 찾는 과정을 보여주며, DVFS가 영향을 주는 과정을 보여준다.

 


에너지 효과적인 cpu 찾기

find_energy_efficient_cpu()

kernel/sched/fair.c -1/2-

/*
 * find_energy_efficient_cpu(): Find most energy-efficient target CPU for the
 * waking task. find_energy_efficient_cpu() looks for the CPU with maximum
 * spare capacity in each performance domain and uses it as a potential
 * candidate to execute the task. Then, it uses the Energy Model to figure
 * out which of the CPU candidates is the most energy-efficient.
 *
 * The rationale for this heuristic is as follows. In a performance domain,
 * all the most energy efficient CPU candidates (according to the Energy
 * Model) are those for which we'll request a low frequency. When there are
 * several CPUs for which the frequency request will be the same, we don't
 * have enough data to break the tie between them, because the Energy Model
 * only includes active power costs. With this model, if we assume that
 * frequency requests follow utilization (e.g. using schedutil), the CPU with
 * the maximum spare capacity in a performance domain is guaranteed to be among
 * the best candidates of the performance domain.
 *
 * In practice, it could be preferable from an energy standpoint to pack
 * small tasks on a CPU in order to let other CPUs go in deeper idle states,
 * but that could also hurt our chances to go cluster idle, and we have no
 * ways to tell with the current Energy Model if this is actually a good
 * idea or not. So, find_energy_efficient_cpu() basically favors
 * cluster-packing, and spreading inside a cluster. That should at least be
 * a good thing for latency, and this is consistent with the idea that most
 * of the energy savings of EAS come from the asymmetry of the system, and
 * not so much from breaking the tie between identical CPUs. That's also the
 * reason why EAS is enabled in the topology code only for systems where
 * SD_ASYM_CPUCAPACITY is set.
 *
 * NOTE: Forkees are not accepted in the energy-aware wake-up path because
 * they don't have any useful utilization data yet and it's not possible to
 * forecast their impact on energy consumption. Consequently, they will be
 * placed by find_idlest_cpu() on the least loaded CPU, which might turn out
 * to be energy-inefficient in some use-cases. The alternative would be to
 * bias new tasks towards specific types of CPUs first, or to try to infer
 * their util_avg from the parent task, but those heuristics could hurt
 * other use-cases too. So, until someone finds a better way to solve this,
 * let's keep things simple by re-using the existing slow path.
 */
static int find_energy_efficient_cpu(struct task_struct *p, int prev_cpu)
{
        unsigned long prev_delta = ULONG_MAX, best_delta = ULONG_MAX;
        struct root_domain *rd = cpu_rq(smp_processor_id())->rd;
        unsigned long cpu_cap, util, base_energy = 0;
        int cpu, best_energy_cpu = prev_cpu;
        struct sched_domain *sd;
        struct perf_domain *pd;

        rcu_read_lock();
        pd = rcu_dereference(rd->pd);
        if (!pd || READ_ONCE(rd->overutilized))
                goto fail;

        /*
         * Energy-aware wake-up happens on the lowest sched_domain starting
         * from sd_asym_cpucapacity spanning over this_cpu and prev_cpu.
         */
        sd = rcu_dereference(*this_cpu_ptr(&sd_asym_cpucapacity));
        while (sd && !cpumask_test_cpu(prev_cpu, sched_domain_span(sd)))
                sd = sd->parent;
        if (!sd)
                goto fail;

        sync_entity_load_avg(&p->se);
        if (!task_util_est(p))
                goto unlock;

        for (; pd; pd = pd->next) {
                unsigned long cur_delta, spare_cap, max_spare_cap = 0;
                unsigned long base_energy_pd;
                int max_spare_cap_cpu = -1;

                /* Compute the 'base' energy of the pd, without @p */
                base_energy_pd = compute_energy(p, -1, pd);
                base_energy += base_energy_pd;

                for_each_cpu_and(cpu, perf_domain_span(pd), sched_domain_span(sd)) {
                        if (!cpumask_test_cpu(cpu, p->cpus_ptr))
                                continue;

                        /* Skip CPUs that will be overutilized. */
                        util = cpu_util_next(cpu, p, cpu);
                        cpu_cap = capacity_of(cpu);
                        if (!fits_capacity(util, cpu_cap))
                                continue;

                        /* Always use prev_cpu as a candidate. */
                        if (cpu == prev_cpu) {
                                prev_delta = compute_energy(p, prev_cpu, pd);
                                prev_delta -= base_energy_pd;
                                best_delta = min(best_delta, prev_delta);
                        }

                        /*
                         * Find the CPU with the maximum spare capacity in
                         * the performance domain
                         */
                        spare_cap = cpu_cap - util;
                        if (spare_cap > max_spare_cap) {
                                max_spare_cap = spare_cap;
                                max_spare_cap_cpu = cpu;
                        }
                }

                /* Evaluate the energy impact of using this CPU. */
                if (max_spare_cap_cpu >= 0 && max_spare_cap_cpu != prev_cpu) {
                        cur_delta = compute_energy(p, max_spare_cap_cpu, pd);
                        cur_delta -= base_energy_pd;
                        if (cur_delta < best_delta) {
                                best_delta = cur_delta;
                                best_energy_cpu = max_spare_cap_cpu;
                        }
                }
        }

빅/리틀 처럼 asym cpucapacity를 사용하는 도메인에서 @p태스크가 마이그레이션할 에너지 효과적인(절약 가능한) cpu를 찾아 반환한다. @prev_cpu를 반환할 수도 있고, asym cpucapacity가 아니거나 오버유틸 중인 경우 -1을 반환한다.

  • 코드 라인 11~13에서 perf domain이 없거나 overutilized 된 경우 fail 레이블을 통해 -1을 반환한다.
  • 코드 라인 19~23에서 빅/리틀 같이 asym cpucapacity 도메인이 없거나 해당 도메인을 포함하여 상위 도메인에 @prev_cpu가 속해있지 않으면 fail 레이블을 통해 -1을 반환한다.
  • 코드 라인 25~36에서 perf 도메인을 순회하며 compute_energy() 함수를 통해 태스크를 마이그레이션 후 소비할 에너지를 추정한 값을 알아와서 base_energy_pd 대입하고, 이를 base_energy에 누적한다.
  • 코드 라인 43~46에서 perf 도메인과 스케줄 도메인에 양쪽에 포함된 cpu들을 순회하며 태스크가 지원하지 않는 cpu들과 overutilized된 cpu들은 skip 한다.
    • 태스크 p가 cpu로 마이그레이션한 후를 예측한 cpu의 유틸을 알아와서 util에 대입하고, 이 값이 cpu의 capacity 이내에서 동작할 수 없으면 skip 한다.
  • 코드 라인 49~53에서 순회 중인 cpu에 @prev_cpu인 경우는 언제나 대상이 되어 @prev_cpu로 compute_energy() 함수를 통해 반환된 값에서 base_energy_pd를 뺀 차이를 prev_delta에 대입한다. 그 후 이 값은 best_delta와 비교하여 작은 값을 best_delta로 갱신한다.
  • 코드 라인 59~63에서 cpu에 남은 capacity 여분이 max_spare_cap보다 큰 경우 이를 갱신한다.
  • 코드 라인 67~74에서 capacity 여분이 가장 큰 cpu가 새로운 cpu로 결정된 경우 태스크를 max_spare_cap_cpu로 마이그레이션할 때의 추정되는 에너지 소비량을 알아와서 base_energy_pd를 뺀 후 cur_delta에 대입한다.  이 값이 best_delta 보다 작을 때엔 best_delta로 이 값을 갱신한다.

 

kernel/sched/fair.c -2/2-

unlock:
        rcu_read_unlock();

        /*
         * Pick the best CPU if prev_cpu cannot be used, or if it saves at
         * least 6% of the energy used by prev_cpu.
         */
        if (prev_delta == ULONG_MAX)
                return best_energy_cpu;

        if ((prev_delta - best_delta) > ((prev_delta + base_energy) >> 4))
                return best_energy_cpu;

        return prev_cpu;

fail:
        rcu_read_unlock();

        return -1;
}
  • 코드 라인 8~9에서 @prev_cpu로 결정된 경우가 아니면 best_energy_cpu를 반환한다.
  • 코드 라인 11~12에서 best_energy_cpu가 @prev_cpu보다 6% 이상의 에너지 절약이 되는 경우 best_energy_cpu를 반환한다.
  • 코드 라인 14에서 그냥 @prev_cpu를 반환한다.
  • 코드 라인 16~19에서 fail: 레이블이다. -1을 반환한다.

 

마이그레이션 후 에너지 추정

compute_energy()

kernel/sched/fair.c

/*
 * compute_energy(): Estimates the energy that @pd would consume if @p was
 * migrated to @dst_cpu. compute_energy() predicts what will be the utilization
 * landscape of @pd's CPUs after the task migration, and uses the Energy Model
 * to compute what would be the energy if we decided to actually migrate that
 * task.
 */
compute_energy(struct task_struct *p, int dst_cpu, struct perf_domain *pd)
{
        struct cpumask *pd_mask = perf_domain_span(pd);
        unsigned long cpu_cap = arch_scale_cpu_capacity(cpumask_first(pd_mask));
        unsigned long max_util = 0, sum_util = 0;
        int cpu;

        /*
         * The capacity state of CPUs of the current rd can be driven by CPUs
         * of another rd if they belong to the same pd. So, account for the
         * utilization of these CPUs too by masking pd with cpu_online_mask
         * instead of the rd span.
         *
         * If an entire pd is outside of the current rd, it will not appear in
         * its pd list and will not be accounted by compute_energy().
         */
        for_each_cpu_and(cpu, pd_mask, cpu_online_mask) {
                unsigned long cpu_util, util_cfs = cpu_util_next(cpu, p, dst_cpu);
                struct task_struct *tsk = cpu == dst_cpu ? p : NULL;

                /*
                 * Busy time computation: utilization clamping is not
                 * required since the ratio (sum_util / cpu_capacity)
                 * is already enough to scale the EM reported power
                 * consumption at the (eventually clamped) cpu_capacity.
                 */
                sum_util += schedutil_cpu_util(cpu, util_cfs, cpu_cap,
                                               ENERGY_UTIL, NULL);

                /*
                 * Performance domain frequency: utilization clamping
                 * must be considered since it affects the selection
                 * of the performance domain frequency.
                 * NOTE: in case RT tasks are running, by default the
                 * FREQUENCY_UTIL's utilization can be max OPP.
                 */
                cpu_util = schedutil_cpu_util(cpu, util_cfs, cpu_cap,
                                              FREQUENCY_UTIL, tsk);
                max_util = max(max_util, cpu_util);
        }

        return em_pd_energy(pd->em_pd, max_util, sum_util);
}

태스크 @p가 @dst_cpu로 마이그레이션 후 @pd가 소비할 에너지를 추정한 값을 반환한다.

  • 코드 라인 3~4에서 perf 도메인에 소속한 cpu들 중 첫 cpu의 scale 적용된 cpu capacity를 알아온다.
  • 코드 라인 17~18에서 perf 도메인에 소속한 cpu들 중 online cpu를 순회하며 태스크가 dst_cpu로 마이그레이션 한 후 cpu의 유틸을 예상해온 값을 util_cfs에 대입한다.
  • 코드 라인 27~28에서 순회 중인 cpu에 대해 에너지 산출을 위한 유효 유틸을 알아와서 sum_util에 추가한다.
  • 코드 라인 37~39에서 순회 중인 cpu에 대해 주파수를 선택하기 위한 유효 유틸을 알아와서 cpu_util에 대입하고, max_util도 갱신한다. 단 산출된 유효 유틸은 태스크의 uclamp 된 값으로 제한된다.
  • 코드 라인 42에서 perf 도메인의 cpu들이 소모할 에너지 추정치를 알아와서 반환한다.

 

schedutil_cpu_util()

kernel/sched/cpufreq_schedutil.c

/*
 * This function computes an effective utilization for the given CPU, to be
 * used for frequency selection given the linear relation: f = u * f_max.
 *
 * The scheduler tracks the following metrics:
 *
 *   cpu_util_{cfs,rt,dl,irq}()
 *   cpu_bw_dl()
 *
 * Where the cfs,rt and dl util numbers are tracked with the same metric and
 * synchronized windows and are thus directly comparable.
 *
 * The cfs,rt,dl utilization are the running times measured with rq->clock_task
 * which excludes things like IRQ and steal-time. These latter are then accrued
 * in the irq utilization.
 *
 * The DL bandwidth number otoh is not a measured metric but a value computed
 * based on the task model parameters and gives the minimal utilization
 * required to meet deadlines.
 */
unsigned long schedutil_cpu_util(int cpu, unsigned long util_cfs,
                                 unsigned long max, enum schedutil_type type,
                                 struct task_struct *p)
{
        unsigned long dl_util, util, irq;
        struct rq *rq = cpu_rq(cpu);

        if (!IS_BUILTIN(CONFIG_UCLAMP_TASK) &&
            type == FREQUENCY_UTIL && rt_rq_is_runnable(&rq->rt)) {
                return max;
        }

        /*
         * Early check to see if IRQ/steal time saturates the CPU, can be
         * because of inaccuracies in how we track these -- see
         * update_irq_load_avg().
         */
        irq = cpu_util_irq(rq);
        if (unlikely(irq >= max))
                return max;

        /*
         * Because the time spend on RT/DL tasks is visible as 'lost' time to
         * CFS tasks and we use the same metric to track the effective
         * utilization (PELT windows are synchronized) we can directly add them
         * to obtain the CPU's actual utilization.
         *
         * CFS and RT utilization can be boosted or capped, depending on
         * utilization clamp constraints requested by currently RUNNABLE
         * tasks.
         * When there are no CFS RUNNABLE tasks, clamps are released and
         * frequency will be gracefully reduced with the utilization decay.
         */
        util = util_cfs + cpu_util_rt(rq);
        if (type == FREQUENCY_UTIL)
                util = uclamp_util_with(rq, util, p);

        dl_util = cpu_util_dl(rq);

        /*
         * For frequency selection we do not make cpu_util_dl() a permanent part
         * of this sum because we want to use cpu_bw_dl() later on, but we need
         * to check if the CFS+RT+DL sum is saturated (ie. no idle time) such
         * that we select f_max when there is no idle time.
         *
         * NOTE: numerical errors or stop class might cause us to not quite hit
         * saturation when we should -- something for later.
         */
        if (util + dl_util >= max)
                return max;

        /*
         * OTOH, for energy computation we need the estimated running time, so
         * include util_dl and ignore dl_bw.
         */
        if (type == ENERGY_UTIL)
                util += dl_util;

        /*
         * There is still idle time; further improve the number by using the
         * irq metric. Because IRQ/steal time is hidden from the task clock we
         * need to scale the task numbers:
         *
         *              max - irq
         *   U' = irq + --------- * U
         *                 max
         */
        util = scale_irq_capacity(util, irq, max);
        util += irq;

        /*
         * Bandwidth required by DEADLINE must always be granted while, for
         * FAIR and RT, we use blocked utilization of IDLE CPUs as a mechanism
         * to gracefully reduce the frequency when no tasks show up for longer
         * periods of time.
         *
         * Ideally we would like to set bw_dl as min/guaranteed freq and util +
         * bw_dl as requested freq. However, cpufreq is not yet ready for such
         * an interface. So, we only do the latter for now.
         */
        if (type == FREQUENCY_UTIL)
                util += cpu_bw_dl(rq);

        return min(max, util);
}

@cpu에 대한 유효 유틸을 산출한다. 산출 타입에 FREQUENCY_UTIL(주파수 설정 목적) 및 ENERGY_UTIL(에너지 산출 목적) 타입을 사용한다.

  • 코드 라인 8~11에서 uclamp를 지원하는 않는 커널 옵션이고, FREQUENCY_UTIL 타입으로 rt 태스크가 동작 중인 경우 최대 성능을 위해 최대 에너지가 필요하므로 @max 값을 반환한다.
  • 코드 라인 18~20에서 irq 유틸이 max를 초과하는 경우 최대 성능을 위해 @max 값을 반환한다.
  • 코드 라인 34~36에서 @util_cfs 및 rt 유틸을 더하고, FREQUENCY_UTIL  타입인 경우 @p 태스크에 설정된 uclamp를 적용한다.
  • 코드 라인 38~50에서 dl 유틸을 알아오고, util과 더한 값이 @max를 초과하는 경우도 @max를 반환한다.
  • 코드 라인 56에서 ENERGY_UTIL 타입인 경우 util 값에 dl_util도 추가한다.
  • 코드 라인 67~68에서 irq 스케일 적용한 유틸을 산출한다.
    • task 클럭에는 irq 타임이 제거된 상태이다. 따라서 @max에서 irq을 뺀 나머지 capacity로 유틸을 곱하고 그 후 다시 irq를 추가한다.
  • 코드 라인 81~82에서 FREQUENCY_UTIL  타입인 경우 dl 밴드위드에 설정한 최소 유틸이 필요하므로 이 값도 util에 추가한다.
  • 코드 라인 84에서 산출된 유틸을 반환한다. 단 @max 값을 초과하지 못하게 제한한다.

 

에너지 소비량 추정

em_pd_energy()

include/linux/energy_model.h

/**
 * em_pd_energy() - Estimates the energy consumed by the CPUs of a perf. domain
 * @pd          : performance domain for which energy has to be estimated
 * @max_util    : highest utilization among CPUs of the domain
 * @sum_util    : sum of the utilization of all CPUs in the domain
 *
 * Return: the sum of the energy consumed by the CPUs of the domain assuming
 * a capacity state satisfying the max utilization of the domain.
 */
static inline unsigned long em_pd_energy(struct em_perf_domain *pd,
                                unsigned long max_util, unsigned long sum_util)
{
        unsigned long freq, scale_cpu;
        struct em_cap_state *cs;
        int i, cpu;

        /*
         * In order to predict the capacity state, map the utilization of the
         * most utilized CPU of the performance domain to a requested frequency,
         * like schedutil.
         */
        cpu = cpumask_first(to_cpumask(pd->cpus));
        scale_cpu = arch_scale_cpu_capacity(cpu);
        cs = &pd->table[pd->nr_cap_states - 1];
        freq = map_util_freq(max_util, cs->frequency, scale_cpu);

        /*
         * Find the lowest capacity state of the Energy Model above the
         * requested frequency.
         */
        for (i = 0; i < pd->nr_cap_states; i++) {
                cs = &pd->table[i];
                if (cs->frequency >= freq)
                        break;
        }

        /*
         * The capacity of a CPU in the domain at that capacity state (cs)
         * can be computed as:
         *
         *             cs->freq * scale_cpu
         *   cs->cap = --------------------                          (1)
         *                 cpu_max_freq
         *
         * So, ignoring the costs of idle states (which are not available in
         * the EM), the energy consumed by this CPU at that capacity state is
         * estimated as:
         *
         *             cs->power * cpu_util
         *   cpu_nrg = --------------------                          (2)
         *                   cs->cap
         *
         * since 'cpu_util / cs->cap' represents its percentage of busy time.
         *
         *   NOTE: Although the result of this computation actually is in
         *         units of power, it can be manipulated as an energy value
         *         over a scheduling period, since it is assumed to be
         *         constant during that interval.
         *
         * By injecting (1) in (2), 'cpu_nrg' can be re-expressed as a product
         * of two terms:
         *
         *             cs->power * cpu_max_freq   cpu_util
         *   cpu_nrg = ------------------------ * ---------          (3)
         *                    cs->freq            scale_cpu
         *
         * The first term is static, and is stored in the em_cap_state struct
         * as 'cs->cost'.
         *
         * Since all CPUs of the domain have the same micro-architecture, they
         * share the same 'cs->cost', and the same CPU capacity. Hence, the
         * total energy of the domain (which is the simple sum of the energy of
         * all of its CPUs) can be factorized as:
         *
         *            cs->cost * \Sum cpu_util
         *   pd_nrg = ------------------------                       (4)
         *                  scale_cpu
         */
        return cs->cost * sum_util / scale_cpu;
}

perf 도메인의 cpu들이 소모할 에너지 추정치를 알아온다. @max_util은 도메인의 cpu들 중 가장 큰 유틸, @sum_util 에는 도메인의 전체 유틸을 전달한다.

  • 코드 라인 13~16에서 perf 도메인의 첫 cpu의 capacity와 @max_util 값으로 pd 테이블을 통해 적절한 주파수를 알아온다.
  • 코드 라인 22~26에서 위에서 찾은 주파수를 초과하는 cpu가 실제 지원하는 주파수가 담긴 cs(em_cap_state 구조체)를 알아온다.
  • 코드 라인 70에서 cs->cost * @sum_util / pd 도메인내 첫 cpu의 scale된 cpu capacity를 반환한다.

 

map_util_freq()

include/linux/sched/cpufreq.h

static inline unsigned long map_util_freq(unsigned long util,
                                        unsigned long freq, unsigned long cap)
{
        return (freq + (freq >> 2)) * util / cap;
}

freq 1.5배 * util/cap을 반환한다.

 

마이그레이션 후 유틸 예측

cpu_util_next()

kernel/sched/fair.c

/*
 * Predicts what cpu_util(@cpu) would return if @p was migrated (and enqueued)
 * to @dst_cpu.
 */
static unsigned long cpu_util_next(int cpu, struct task_struct *p, int dst_cpu)
{
        struct cfs_rq *cfs_rq = &cpu_rq(cpu)->cfs;
        unsigned long util_est, util = READ_ONCE(cfs_rq->avg.util_avg);

        /*
         * If @p migrates from @cpu to another, remove its contribution. Or,
         * if @p migrates from another CPU to @cpu, add its contribution. In
         * the other cases, @cpu is not impacted by the migration, so the
         * util_avg should already be correct.
         */
        if (task_cpu(p) == cpu && dst_cpu != cpu)
                sub_positive(&util, task_util(p));
        else if (task_cpu(p) != cpu && dst_cpu == cpu)
                util += task_util(p);

        if (sched_feat(UTIL_EST)) {
                util_est = READ_ONCE(cfs_rq->avg.util_est.enqueued);

                /*
                 * During wake-up, the task isn't enqueued yet and doesn't
                 * appear in the cfs_rq->avg.util_est.enqueued of any rq,
                 * so just add it (if needed) to "simulate" what will be
                 * cpu_util() after the task has been enqueued.
                 */
                if (dst_cpu == cpu)
                        util_est += _task_util_est(p);

                util = max(util, util_est);
        }

        return min(util, capacity_orig_of(cpu));
}

태스크 @p를 @cpu에서 @dst_cpu로 마이그레이션한 후를 예측한 @cpu의 유틸을 반환한다.

  • 코드 라인 3~4에서 태스크가 소속된 cfs 런큐의 유틸 평균을 알아와 util에 대입한다.
  • 코드 라인 12~15에서 태스크가 @cpu에서 @dst_cpu로 마이그레이션 하므로 태스크의 cpu와 두 cpu가 관련된 경우 로드를 빼거나 추가해야 한다.
    • 태스크의 cpu가 @cpu이고, @dst_cpu와 @cpu가 다른 경우 util에서 태스크의 유틸 평균을 뺀다. (양수로 제한)
    • 태스크의 cpu가 @cpu가 아니면서 @dst_cpu와 @cpu가 같은 경우 util에 태스크의 유틸 평균을 추가한다.
  • 코드 라인 17~30에서 UTIL_EST feature를 사용하는 경우 태스크의 cpu와 @dst_cpu가 같은 경우 cfs 런큐의 util_est에서 태스크의 util_est를 더한 후 이 값을 util과 비교하여 최대값으로 util을 갱신한다.
    • 매우 짧은 시간 실행되는 태스크의 경우 1ms 단위로 갱신되는 PELT 시그널을 사용한 유틸 로드가 적을 수 있다. 따라서 태스크의 디큐 시마다 산출되는 추정 유틸(estimated utilization)과 기존 유틸 중 큰 값을 사용해야 cpu 간의 더 정확한 유틸 비교를 할 수 있다.
    • 참고: sched/fair: Update util_est only on util_avg updates (2018, v4.17-rc1)
  • 코드 라인 32에서 산출한 util 값이 기존 @cpu의 capacity를 초과하면 안되도록 제한하여 반환한다.

 

남은 여유 capacity

capacity_spare_without()

kernel/sched/fair.c

static unsigned long capacity_spare_without(int cpu, struct task_struct *p)
{
        return max_t(long, capacity_of(cpu) - cpu_util_without(cpu, p), 0);
}

태스크가 사용중인 유틸을 제외한 cpu에 남은 여유 capacity를 반환한다.

  • cpu의 capacity – 태스크가 cpu에 기여한 유틸 로드를 제외한 cpu의 유틸 로드

 

cpu_util_without()

kernel/sched/fair.c

/*
 * cpu_util_without: compute cpu utilization without any contributions from *p
 * @cpu: the CPU which utilization is requested
 * @p: the task which utilization should be discounted
 *
 * The utilization of a CPU is defined by the utilization of tasks currently
 * enqueued on that CPU as well as tasks which are currently sleeping after an
 * execution on that CPU.
 *
 * This method returns the utilization of the specified CPU by discounting the
 * utilization of the specified task, whenever the task is currently
 * contributing to the CPU utilization.
 */
static unsigned long cpu_util_without(int cpu, struct task_struct *p)
{
        struct cfs_rq *cfs_rq;
        unsigned int util;

        /* Task has no contribution or is new */
        if (cpu != task_cpu(p) || !READ_ONCE(p->se.avg.last_update_time))
                return cpu_util(cpu);

        cfs_rq = &cpu_rq(cpu)->cfs;
        util = READ_ONCE(cfs_rq->avg.util_avg);

        /* Discount task's util from CPU's util */
        lsub_positive(&util, task_util(p));

        /*
         * Covered cases:
         *
         * a) if *p is the only task sleeping on this CPU, then:
         *      cpu_util (== task_util) > util_est (== 0)
         *    and thus we return:
         *      cpu_util_without = (cpu_util - task_util) = 0
         *
         * b) if other tasks are SLEEPING on this CPU, which is now exiting
         *    IDLE, then:
         *      cpu_util >= task_util
         *      cpu_util > util_est (== 0)
         *    and thus we discount *p's blocked utilization to return:
         *      cpu_util_without = (cpu_util - task_util) >= 0
         *
         * c) if other tasks are RUNNABLE on that CPU and
         *      util_est > cpu_util
         *    then we use util_est since it returns a more restrictive
         *    estimation of the spare capacity on that CPU, by just
         *    considering the expected utilization of tasks already
         *    runnable on that CPU.
         *
         * Cases a) and b) are covered by the above code, while case c) is
         * covered by the following code when estimated utilization is
         * enabled.
         */
        if (sched_feat(UTIL_EST)) {
                unsigned int estimated =
                        READ_ONCE(cfs_rq->avg.util_est.enqueued);

                /*
                 * Despite the following checks we still have a small window
                 * for a possible race, when an execl's select_task_rq_fair()
                 * races with LB's detach_task():
                 *
                 *   detach_task()
                 *     p->on_rq = TASK_ON_RQ_MIGRATING;
                 *     ---------------------------------- A
                 *     deactivate_task()                   \
                 *       dequeue_task()                     + RaceTime
                 *         util_est_dequeue()              /
                 *     ---------------------------------- B
                 *
                 * The additional check on "current == p" it's required to
                 * properly fix the execl regression and it helps in further
                 * reducing the chances for the above race.
                 */
                if (unlikely(task_on_rq_queued(p) || current == p))
                        lsub_positive(&estimated, _task_util_est(p));

                util = max(util, estimated);
        }

        /*
         * Utilization (estimated) can exceed the CPU capacity, thus let's
         * clamp to the maximum CPU capacity to ensure consistency with
         * the cpu_util call.
         */
        return min_t(unsigned long, util, capacity_orig_of(cpu));
}

태스크가 cpu에 기여한 로드가 있는 경우 그 로드를 제외한 cpu의 유틸 로드를 반환한다.

  • 코드 라인 7~8에서 태스크가 동작했었던 cpu가 아닌 경우 @cpu의 런큐에는 태스크가 기여한 유틸 로드가 없다. 따라서 이러한 경우 cpu의 유틸 로드를 반환한다. 또한 태스크의 로드 평균을 한 번도 갱신한 적이 없는 새 태스크인 경우도 마찬가지이다.
  • 코드 라인 10~14에서 @cpu의 유틸에서 태스크의 유틸을 뺀다.
  • 코드 라인 42~67에서 UTIL_EST feature를 사용하는 경우 유틸과 cfs 런큐의 추정 유틸 둘 중 큰 값을 사용한다. 추정 유틸 값도 태스크가 이미 런큐에 있거나 현재 태스크와 동일한 경우 태스크의 추정 유틸을 뺀 값을 사용한다.
  • 코드 라인 74에서 유틸 값을 반환하되 @cpu의 오리지날 capacity보다 큰 경우에는 clamp 한다.

 

cpu_util()

kernel/sched/fair.c

/**
 * Amount of capacity of a CPU that is (estimated to be) used by CFS tasks
 * @cpu: the CPU to get the utilization of
 *
 * The unit of the return value must be the one of capacity so we can compare
 * the utilization with the capacity of the CPU that is available for CFS task
 * (ie cpu_capacity).
 *
 * cfs_rq.avg.util_avg is the sum of running time of runnable tasks plus the
 * recent utilization of currently non-runnable tasks on a CPU. It represents
 * the amount of utilization of a CPU in the range [0..capacity_orig] where
 * capacity_orig is the cpu_capacity available at the highest frequency
 * (arch_scale_freq_capacity()).
 * The utilization of a CPU converges towards a sum equal to or less than the
 * current capacity (capacity_curr <= capacity_orig) of the CPU because it is
 * the running time on this CPU scaled by capacity_curr.
 *
 * The estimated utilization of a CPU is defined to be the maximum between its
 * cfs_rq.avg.util_avg and the sum of the estimated utilization of the tasks
 * currently RUNNABLE on that CPU.
 * This allows to properly represent the expected utilization of a CPU which
 * has just got a big task running since a long sleep period. At the same time
 * however it preserves the benefits of the "blocked utilization" in
 * describing the potential for other tasks waking up on the same CPU.
 *
 * Nevertheless, cfs_rq.avg.util_avg can be higher than capacity_curr or even
 * higher than capacity_orig because of unfortunate rounding in
 * cfs.avg.util_avg or just after migrating tasks and new task wakeups until
 * the average stabilizes with the new running time. We need to check that the
 * utilization stays within the range of [0..capacity_orig] and cap it if
 * necessary. Without utilization capping, a group could be seen as overloaded
 * (CPU0 utilization at 121% + CPU1 utilization at 80%) whereas CPU1 has 20% of
 * available capacity. We allow utilization to overshoot capacity_curr (but not
 * capacity_orig) as it useful for predicting the capacity required after task
 * migrations (scheduler-driven DVFS).
 *
 * Return: the (estimated) utilization for the specified CPU
 */
static inline unsigned long cpu_util(int cpu)
{
        struct cfs_rq *cfs_rq;
        unsigned int util;

        cfs_rq = &cpu_rq(cpu)->cfs;
        util = READ_ONCE(cfs_rq->avg.util_avg);

        if (sched_feat(UTIL_EST))
                util = max(util, READ_ONCE(cfs_rq->avg.util_est.enqueued));

        return min_t(unsigned long, util, capacity_orig_of(cpu));
}

cpu의 유틸 로드 값을 반환한다.

  • 코드 라인 6~7에서 cpu의 cfs 런큐에서 유틸 로드 평균을 알아온다.
  • 코드 라인 9~10에서 런큐에서 태스크가 1ms 미만으로 동작하는 경우 유틸 로드가 정확히 반영되지 않아 실제보다 작은 값이 사용될 수 있다. 따라서 UTIL_EST feature를 사용하는 경우 태스크의 디큐마다 갱신되는 예상 유틸 로드와 비교하여 큰 값을 사용하면 조금 더 정확한 유틸 로드를 알아낼 수 있다.
  • 코드 라인 12에서 유틸 값을 반환하되 @cpu의 오리지날 capacity보다 큰 경우에는 clamp 한다.

 

EAS enable 여부

sched_energy_enabled()

kernel/sched/sched.h

static inline bool sched_energy_enabled(void)
{
        return static_branch_unlikely(&sched_energy_present);
}

EAS(Energy Aware Scheduling) 기능이 enabled 상태인지 여부를 반환한다.

 


Performance Domain

기존 스케줄링 도메인의 계층 구조는 캐시 기반으로 구성되어 있다. 그러나 EAS를 사용하려면 플랫폼에 대한 더 많은 정보를 알아야 하며 특히 캐시기반과 무관하게 cpu들 포함시킬 수 있는 performance 도메인이 구성되어야 할 때가 있다. pd(performance domain)는 리스트로 연결되어 루트 도메인에 attach 된다. 여러 개의 루트 도메인을 사용하는 경우 각 루트 도메인에서 사용하는 pd의 멤버 cpu는 서로 중복되면 안된다.

 

다음 그림과 같이 ARM Cortex-A75 아키텍처에서 멀티플 파티션을 구성할 수 있음을 보여준다.

 

다음 그림은 performance domain을 구성한 예를 간단히 보여준다.

  • 두 개의 루트 도메인(rd)에 리스트 연결용 pd4가 중복됨을 볼 수 있다.

 

다음 그림은 performance domain을 구성한 예를 조금 더 자세히 구조체 레벨에서 보여준다.

  • 실제 데이터를 관리하는 에너지 모델 pd(em_perf_domain)는 중복되지 않고 pd 숫자만큼만 만들어진다.

 

“sched_energy_aware” proc

sched_energy_aware_handler()

kernel/sched/topology.c

int sched_energy_aware_handler(struct ctl_table *table, int write,
                         void __user *buffer, size_t *lenp, loff_t *ppos)
{
        int ret, state;

        if (write && !capable(CAP_SYS_ADMIN))
                return -EPERM;

        ret = proc_dointvec_minmax(table, write, buffer, lenp, ppos);
        if (!ret && write) {
                state = static_branch_unlikely(&sched_energy_present);
                if (state != sysctl_sched_energy_aware) {
                        mutex_lock(&sched_energy_mutex);
                        sched_energy_update = 1;
                        rebuild_sched_domains();
                        sched_energy_update = 0;
                        mutex_unlock(&sched_energy_mutex);
                }
        }

        return ret;
}

에너지 모델을 enable/disable하고 스케줄 도메인을 재구성한다.

  • 코드 라인 6~7에서 CAP_SYS_ADMIN capability가 없으면 권한이 없으므로 -EPERM을 반환한다.
  • 코드 라인 9~19에서 sched_energy_present가 동작 중이면 sysctl_sched_energy_aware로 기록한 값이 변경된 경우 스케줄 도메인을 재구성하며 그 동안 sched_energy_update를 1로 유지한다.
    • “/proc/sys/kernel/sched_energy_aware”

 

rebuild_sched_domains()

kernel/sched/topology.c

void rebuild_sched_domains(void)
{
        get_online_cpus();
        percpu_down_write(&cpuset_rwsem);
        rebuild_sched_domains_locked();
        percpu_up_write(&cpuset_rwsem);
        put_online_cpus();
}

스케줄 도메인들을 재구성한다.

 

rebuild_sched_domains_locked()

kernel/sched/topology.c

/*
 * Rebuild scheduler domains.
 *
 * If the flag 'sched_load_balance' of any cpuset with non-empty
 * 'cpus' changes, or if the 'cpus' allowed changes in any cpuset
 * which has that flag enabled, or if any cpuset with a non-empty
 * 'cpus' is removed, then call this routine to rebuild the
 * scheduler's dynamic sched domains.
 *
 * Call with cpuset_mutex held.  Takes get_online_cpus().
 */
static void rebuild_sched_domains_locked(void)
{
        struct sched_domain_attr *attr;
        cpumask_var_t *doms;
        int ndoms;

        lockdep_assert_cpus_held();
        percpu_rwsem_assert_held(&cpuset_rwsem);

        /*
         * We have raced with CPU hotplug. Don't do anything to avoid
         * passing doms with offlined cpu to partition_sched_domains().
         * Anyways, hotplug work item will rebuild sched domains.
         */
        if (!top_cpuset.nr_subparts_cpus &&
            !cpumask_equal(top_cpuset.effective_cpus, cpu_active_mask))
                return;

        if (top_cpuset.nr_subparts_cpus &&
           !cpumask_subset(top_cpuset.effective_cpus, cpu_active_mask))
                return;

        /* Generate domain masks and attrs */
        ndoms = generate_sched_domains(&doms, &attr);

        /* Have scheduler rebuild the domains */
        partition_and_rebuild_sched_domains(ndoms, doms, attr);
}

스케줄 도메인들을 재구성한다.

 

generate_sched_domains()

kernel/cgroup/cpuset.c -1/2-

/*
 * generate_sched_domains()
 *
 * This function builds a partial partition of the systems CPUs
 * A 'partial partition' is a set of non-overlapping subsets whose
 * union is a subset of that set.
 * The output of this function needs to be passed to kernel/sched/core.c
 * partition_sched_domains() routine, which will rebuild the scheduler's
 * load balancing domains (sched domains) as specified by that partial
 * partition.
 *
 * See "What is sched_load_balance" in Documentation/admin-guide/cgroup-v1/cpusets.rst
 * for a background explanation of this.
 *
 * Does not return errors, on the theory that the callers of this
 * routine would rather not worry about failures to rebuild sched
 * domains when operating in the severe memory shortage situations
 * that could cause allocation failures below.
 *
 * Must be called with cpuset_mutex held.
 *
 * The three key local variables below are:
 *    cp - cpuset pointer, used (together with pos_css) to perform a
 *         top-down scan of all cpusets. For our purposes, rebuilding
 *         the schedulers sched domains, we can ignore !is_sched_load_
 *         balance cpusets.
 *  csa  - (for CpuSet Array) Array of pointers to all the cpusets
 *         that need to be load balanced, for convenient iterative
 *         access by the subsequent code that finds the best partition,
 *         i.e the set of domains (subsets) of CPUs such that the
 *         cpus_allowed of every cpuset marked is_sched_load_balance
 *         is a subset of one of these domains, while there are as
 *         many such domains as possible, each as small as possible.
 * doms  - Conversion of 'csa' to an array of cpumasks, for passing to
 *         the kernel/sched/core.c routine partition_sched_domains() in a
 *         convenient format, that can be easily compared to the prior
 *         value to determine what partition elements (sched domains)
 *         were changed (added or removed.)
 *
 * Finding the best partition (set of domains):
 *      The triple nested loops below over i, j, k scan over the
 *      load balanced cpusets (using the array of cpuset pointers in
 *      csa[]) looking for pairs of cpusets that have overlapping
 *      cpus_allowed, but which don't have the same 'pn' partition
 *      number and gives them in the same partition number.  It keeps
 *      looping on the 'restart' label until it can no longer find
 *      any such pairs.
 *
 *      The union of the cpus_allowed masks from the set of
 *      all cpusets having the same 'pn' value then form the one
 *      element of the partition (one sched domain) to be passed to
 *      partition_sched_domains().
 */
static int generate_sched_domains(cpumask_var_t **domains,
                        struct sched_domain_attr **attributes)
{
        struct cpuset *cp;      /* top-down scan of cpusets */
        struct cpuset **csa;    /* array of all cpuset ptrs */
        int csn;                /* how many cpuset ptrs in csa so far */
        int i, j, k;            /* indices for partition finding loops */
        cpumask_var_t *doms;    /* resulting partition; i.e. sched domains */
        struct sched_domain_attr *dattr;  /* attributes for custom domains */
        int ndoms = 0;          /* number of sched domains in result */
        int nslot;              /* next empty doms[] struct cpumask slot */
        struct cgroup_subsys_state *pos_css;
        bool root_load_balance = is_sched_load_balance(&top_cpuset);

        doms = NULL;
        dattr = NULL;
        csa = NULL;

        /* Special case for the 99% of systems with one, full, sched domain */
        if (root_load_balance && !top_cpuset.nr_subparts_cpus) {
                ndoms = 1;
                doms = alloc_sched_domains(ndoms);
                if (!doms)
                        goto done;

                dattr = kmalloc(sizeof(struct sched_domain_attr), GFP_KERNEL);
                if (dattr) {
                        *dattr = SD_ATTR_INIT;
                        update_domain_attr_tree(dattr, &top_cpuset);
                }
                cpumask_and(doms[0], top_cpuset.effective_cpus,
                            housekeeping_cpumask(HK_FLAG_DOMAIN));

                goto done;
        }

        csa = kmalloc_array(nr_cpusets(), sizeof(cp), GFP_KERNEL);
        if (!csa)
                goto done;
        csn = 0;

        rcu_read_lock();
        if (root_load_balance)
                csa[csn++] = &top_cpuset;
        cpuset_for_each_descendant_pre(cp, pos_css, &top_cpuset) {
                if (cp == &top_cpuset)
                        continue;
                /*
                 * Continue traversing beyond @cp iff @cp has some CPUs and
                 * isn't load balancing.  The former is obvious.  The
                 * latter: All child cpusets contain a subset of the
                 * parent's cpus, so just skip them, and then we call
                 * update_domain_attr_tree() to calc relax_domain_level of
                 * the corresponding sched domain.
                 *
                 * If root is load-balancing, we can skip @cp if it
                 * is a subset of the root's effective_cpus.
                 */
                if (!cpumask_empty(cp->cpus_allowed) &&
                    !(is_sched_load_balance(cp) &&
                      cpumask_intersects(cp->cpus_allowed,
                                         housekeeping_cpumask(HK_FLAG_DOMAIN))))
                        continue;

                if (root_load_balance &&
                    cpumask_subset(cp->cpus_allowed, top_cpuset.effective_cpus))
                        continue;

                if (is_sched_load_balance(cp) &&
                    !cpumask_empty(cp->effective_cpus))
                        csa[csn++] = cp;

                /* skip @cp's subtree if not a partition root */
                if (!is_partition_root(cp))
                        pos_css = css_rightmost_descendant(pos_css);
        }
        rcu_read_unlock();

        for (i = 0; i < csn; i++)
                csa[i]->pn = i;
        ndoms = csn;

스케줄 도메인을 생성한다.

  • 코드 라인 13에서 cgroup의 top cpuset에 있는 “cpuset.sched_load_balance” 설정 값 여부에 따라 해당 cpu들이 싱글 스케줄 도메인에 소속되어 로드 밸런스에 참여한다. (디폴트=1)
    • 위의 값이 1인 경우 cgroup의 “cpuset.cpus”에 속한 cpu들이 기본 로드 밸런스에서 동작한다. (디폴트=모든 cpu) 위의 값이 0인 경우 기본 로드 밸런스에서 제외된다. 이 때에는 별도의 파티션 도메인을 만들 때 구성원으로 참여 시킬 수 있다.
  • 코드 라인 20~35에서 별도의 서브 파티션이 없는 경우 해당 cpu들을 대상으로 로드 밸런싱에 참여하게 하도록 싱글 스케줄 도메인을 구성한 후 done 레이블로 이동한다.
  • 코드 라인 37~39에서 이미 생성된 cpuset 수 만큼 cpuset 구조체 포인터를 할당하여 csa에 대입한다.
  • 코드 라인 43~44에서 싱글 스케줄 도메인이 포함되는 경우 첫 번째 csa[0]는 top cpuset을 가리키게 한다.
  • 코드 라인 45~67에서 cpuset들을 대상으로 child 우선 방향으로 순회하며 다음 cpuset들은 제외한다.
    • top cpuset인 경우
    • 순회 중인 cpuset에 cpu들을 지정하였으면서, 로드 밸런싱이 설정되지 않았거나 “isolcpus=” 커널 파라미터로 지정된 cpu들로 다 사용할 수 있는 cpu가 없는 경우
    • 루트에서 로드 밸런싱이 동작하면서 지정한 cpu들은 모두 루트의 effective cpu들에 포함된 경우
  • 코드 라인 69~71에서 순회 중인 cpuset이 기본 로드 밸런싱이 설정되었고 effective_cpus들이 있는 경우 해당 cpuset을 csa[]에 추가한다.
  • 코드 라인 74~75에서 cpuset이 파티션 루트가 아닌 하위 cpuset들은 한꺼번에 skip 한다.
  • 코드 라인 79~81에서 위 루프에서 지정하여 사용가능한 csa[]->pn에 일련번호를 0부터 대입하고, 도메인의 수를 결정한다.

 

kernel/cgroup/cpuset.c -2/2-

restart:
        /* Find the best partition (set of sched domains) */
        for (i = 0; i < csn; i++) {
                struct cpuset *a = csa[i];
                int apn = a->pn;

                for (j = 0; j < csn; j++) {
                        struct cpuset *b = csa[j];
                        int bpn = b->pn;

                        if (apn != bpn && cpusets_overlap(a, b)) {
                                for (k = 0; k < csn; k++) {
                                        struct cpuset *c = csa[k];

                                        if (c->pn == bpn)
                                                c->pn = apn;
                                }
                                ndoms--;        /* one less element */
                                goto restart;
                        }
                }
        }

        /*
         * Now we know how many domains to create.
         * Convert <csn, csa> to <ndoms, doms> and populate cpu masks.
         */
        doms = alloc_sched_domains(ndoms);
        if (!doms)
                goto done;

        /*
         * The rest of the code, including the scheduler, can deal with
         * dattr==NULL case. No need to abort if alloc fails.
         */
        dattr = kmalloc_array(ndoms, sizeof(struct sched_domain_attr),
                              GFP_KERNEL);

        for (nslot = 0, i = 0; i < csn; i++) {
                struct cpuset *a = csa[i];
                struct cpumask *dp;
                int apn = a->pn;

                if (apn < 0) {
                        /* Skip completed partitions */
                        continue;
                }

                dp = doms[nslot];

                if (nslot == ndoms) {
                        static int warnings = 10;
                        if (warnings) {
                                pr_warn("rebuild_sched_domains confused: nslot %d, ndoms %d, csn %d, i %d, apn %d\n",
                                        nslot, ndoms, csn, i, apn);
                                warnings--;
                        }
                        continue;
                }

                cpumask_clear(dp);
                if (dattr)
                        *(dattr + nslot) = SD_ATTR_INIT;
                for (j = i; j < csn; j++) {
                        struct cpuset *b = csa[j];

                        if (apn == b->pn) {
                                cpumask_or(dp, dp, b->effective_cpus);
                                cpumask_and(dp, dp, housekeeping_cpumask(HK_FLAG_DOMAIN));
                                if (dattr)
                                        update_domain_attr_tree(dattr + nslot, b);

                                /* Done with this partition */
                                b->pn = -1;
                        }
                }
                nslot++;
        }
        BUG_ON(nslot != ndoms);

done:
        kfree(csa);

        /*
         * Fallback to the default domain if kmalloc() failed.
         * See comments in partition_sched_domains().
         */
        if (doms == NULL)
                ndoms = 1;

        *domains    = doms;
        *attributes = dattr;
        return ndoms;
}
  • 코드 라인 1~22에서 restart: 레이블이다. cpuset들에서 effective_cpus가 중첩되는 도메인을 제거한 수를 알아낸다.
    • csn 수 만큼 i, j, k 이터레이터를 가진 3 중첩 루프를 사용한다.
    • 처음 i, j로 2 중첩 루프를 돌면서 csa[i]->pn 값과 csn[j]->pn 값이 다르고 csa[i]->effiective_cpus와 csa[j]->effective_cpus가 중첩되는 경우에 한해 k로 3 중첩 루프를 돌면서 j, k에 해당하는 pn이 같을 때 k에 해당하는 pn에 i에 해당하는 pn 값으로 대입한다. 그 후 도메인 수(ndoms)를 감소시키고 restart: 레이블로 이동하여 다시 시작한다.
  • 코드 라인 28~37에서 중첩 도메인을 제거한 최종 결정된 도메인 수 만큼 도메인 마스크와 도메인 속성을 할당한다.
  • 코드 라인 39~78에서 원래 도메인 수(csn)만큼 nslot으로 1차 순회하고, 다시 nslot부터 원래 도메인 수까지(csn) 2차 순회하며 같은 pn에 대해 effective_cpus를 더해 update_domain_attr_tree() 함수를 호출한다.
    • 한 번 생성한 파티션은 다시 만들지 않도록 pn에 -1을 대입한다.
  • 코드 라인 81~92에서 done: 레이블이다. 임시로 만들어 사용했던 csa[] 배열을 할당 해제하고, 출력 인자 *domains에 결정된 도메인 수만큼 중복된 도메인을 합친 cpu 마스크를 반환하고, 출력인자 *dattr에는 결정된 도메인 수만큼의 도메인 속성을 반환한다.
  • 코드 라인 93에서 최종 결정된 도메인 수를 반환한다.

 

다음 그립은 generate_sched_domains() 함수에서 오버랩된 cpu를 가진 도메인을 묶어 도메인 수를 줄인 과정을 보여준다.

 

update_domain_attr_tree()

kernel/cgroup/cpuset.c

static void update_domain_attr_tree(struct sched_domain_attr *dattr,
                                    struct cpuset *root_cs)
{
        struct cpuset *cp;
        struct cgroup_subsys_state *pos_css;

        rcu_read_lock();
        cpuset_for_each_descendant_pre(cp, pos_css, root_cs) {
                /* skip the whole subtree if @cp doesn't have any CPU */
                if (cpumask_empty(cp->cpus_allowed)) {
                        pos_css = css_rightmost_descendant(pos_css);
                        continue;
                }

                if (is_sched_load_balance(cp))
                        update_domain_attr(dattr, cp);
        }
        rcu_read_unlock();
}

도메인 속성 @dattr을 @root_cs 이하 모든 cpuset에 적용한다.

  • 코드 라인 8~14에서 @root_cs 이하 child 우선으로 순회하며 지정된 cpu가 없는 경우 skip 한다.
    • “cpuset.cpus”
  • 코드 라인 16~17에서 로드 밸런싱이 설정된 cpuset인 경우 도메인 속성을 갱신한다.
    • “cpuset.sched_load_balance”

 

partition_and_rebuild_sched_domains()

kernel/sched/topology.c

static void
partition_and_rebuild_sched_domains(int ndoms_new, cpumask_var_t doms_new[],
                                    struct sched_domain_attr *dattr_new)
{
        mutex_lock(&sched_domains_mutex);
        partition_sched_domains_locked(ndoms_new, doms_new, dattr_new);
        rebuild_root_domains();
        mutex_unlock(&sched_domains_mutex);
}

분할된 스케줄 도메인들과 루트 도메인들을 재구성한다.

 

partition_sched_domains()

kernel/sched/topology.c

/*
 * Call with hotplug lock held
 */
void partition_sched_domains(int ndoms_new, cpumask_var_t doms_new[],
                             struct sched_domain_attr *dattr_new)
{
        mutex_lock(&sched_domains_mutex);
        partition_sched_domains_locked(ndoms_new, doms_new, dattr_new);
        mutex_unlock(&sched_domains_mutex);
}

분할된 스케줄 도메인들을 재구성한다.

 

partition_sched_domains_locked()

kernel/sched/topology.c -1/2-

/*
 * Partition sched domains as specified by the 'ndoms_new'
 * cpumasks in the array doms_new[] of cpumasks. This compares
 * doms_new[] to the current sched domain partitioning, doms_cur[].
 * It destroys each deleted domain and builds each new domain.
 *
 * 'doms_new' is an array of cpumask_var_t's of length 'ndoms_new'.
 * The masks don't intersect (don't overlap.) We should setup one
 * sched domain for each mask. CPUs not in any of the cpumasks will
 * not be load balanced. If the same cpumask appears both in the
 * current 'doms_cur' domains and in the new 'doms_new', we can leave
 * it as it is.
 *
 * The passed in 'doms_new' should be allocated using
 * alloc_sched_domains.  This routine takes ownership of it and will
 * free_sched_domains it when done with it. If the caller failed the
 * alloc call, then it can pass in doms_new == NULL && ndoms_new == 1,
 * and partition_sched_domains() will fallback to the single partition
 * 'fallback_doms', it also forces the domains to be rebuilt.
 *
 * If doms_new == NULL it will be replaced with cpu_online_mask.
 * ndoms_new == 0 is a special case for destroying existing domains,
 * and it will not create the default domain.
 *
 * Call with hotplug lock and sched_domains_mutex held
 */
void partition_sched_domains_locked(int ndoms_new, cpumask_var_t doms_new[],
                                    struct sched_domain_attr *dattr_new)
{
        bool __maybe_unused has_eas = false;
        int i, j, n;
        int new_topology;

        lockdep_assert_held(&sched_domains_mutex);

        /* Always unregister in case we don't destroy any domains: */
        unregister_sched_domain_sysctl();

        /* Let the architecture update CPU core mappings: */
        new_topology = arch_update_cpu_topology();

        if (!doms_new) {
                WARN_ON_ONCE(dattr_new);
                n = 0;
                doms_new = alloc_sched_domains(1);
                if (doms_new) {
                        n = 1;
                        cpumask_and(doms_new[0], cpu_active_mask,
                                    housekeeping_cpumask(HK_FLAG_DOMAIN));
                }
        } else {
                n = ndoms_new;
        }

        /* Destroy deleted domains: */
        for (i = 0; i < ndoms_cur; i++) {
                for (j = 0; j < n && !new_topology; j++) {
                        if (cpumask_equal(doms_cur[i], doms_new[j]) &&
                            dattrs_equal(dattr_cur, i, dattr_new, j)) {
                                struct root_domain *rd;

                                /*
                                 * This domain won't be destroyed and as such
                                 * its dl_bw->total_bw needs to be cleared.  It
                                 * will be recomputed in function
                                 * update_tasks_root_domain().
                                 */
                                rd = cpu_rq(cpumask_any(doms_cur[i]))->rd;
                                dl_clear_root_domain(rd);
                                goto match1;
                        }
                }
                /* No match - a current sched domain not in new doms_new[] */
                detach_destroy_domains(doms_cur[i]);
match1:
                ;
        }

        n = ndoms_cur;
        if (!doms_new) {
                n = 0;
                doms_new = &fallback_doms;
                cpumask_and(doms_new[0], cpu_active_mask,
                            housekeeping_cpumask(HK_FLAG_DOMAIN));
        }

        /* Build new domains: */
        for (i = 0; i < ndoms_new; i++) {
                for (j = 0; j < n && !new_topology; j++) {
                        if (cpumask_equal(doms_new[i], doms_cur[j]) &&
                            dattrs_equal(dattr_new, i, dattr_cur, j))
                                goto match2;
                }
                /* No match - add a new doms_new */
                build_sched_domains(doms_new[i], dattr_new ? dattr_new + i : NULL);
match2:
                ;
        }

분할된 스케줄 도메인들을 재구성한다.

  • 코드 라인 11에서 “/proc/sys/kernel/sched_domain” 디렉토리를 등록 해제한다.
  • 코드 라인 14에서 cpu topology 변경 여부를 알아온다. (1=변경)
  • 코드 라인 16~27에서 두 번째 인자 doms_new가 지정되지 않은 경우 isolcpus를 제외한 active cpu들로 1개의 도메인을 할당한다. doms_new가 지정된 경우 도메인 수로 첫 번째 인자 ndoms_new 에서 받은 값을 사용한다.
  • 코드 라인 30~51에서 기존 동작 중인 도메인들을 순회하며 토플로지 변경이 있으면 기존 도메인을 detach한 후 제거한다. 만일 토플로지 변경이 없으면 기존 도메인들 중 기존 cpu와 속성이 같은 경우 detach 및 제거하지 않고 루트 도메인의 dl 밴드위드만 클리어하고, 다른 경우에만 기존 도메인을 detach한 후 제거한다.
  • 코드 라인 53~59에서 새로운 도메인이 요청되지 않은 경우 isolcpus를 제외한 active cpu들로 구성하는 1개의fallback_doms을 지정한다.
  • 코드 라인 62~72에서 새 도메인들을 순회하며 토플로지 변경이 있으면 도메인을 새로 만든다. 만일 토플로지 변경이 없으면 기존 도메인들 중 cpu 및 속성이 같은 경우 새로 만들지 않고,다른 경우에만 도메인을 새로 만든다.

 

kernel/sched/topology.c -2/2-

#if defined(CONFIG_ENERGY_MODEL) && defined(CONFIG_CPU_FREQ_GOV_SCHEDUTIL)
        /* Build perf. domains: */
        for (i = 0; i < ndoms_new; i++) {
                for (j = 0; j < n && !sched_energy_update; j++) {
                        if (cpumask_equal(doms_new[i], doms_cur[j]) &&
                            cpu_rq(cpumask_first(doms_cur[j]))->rd->pd) {
                                has_eas = true;
                                goto match3;
                        }
                }
                /* No match - add perf. domains for a new rd */
                has_eas |= build_perf_domains(doms_new[i]);
match3:
                ;
        }
        sched_energy_set(has_eas);
#endif

        /* Remember the new sched domains: */
        if (doms_cur != &fallback_doms)
                free_sched_domains(doms_cur, ndoms_cur);

        kfree(dattr_cur);
        doms_cur = doms_new;
        dattr_cur = dattr_new;
        ndoms_cur = ndoms_new;

        register_sched_domain_sysctl();
}
  • 코드 라인 3~15에서 EAS를 위해 새 도메인 수 만큼 순회하며 다음의 EAS 동작 변경으로 인한 스케줄 도메인 변경이 진행 중인 경우 perf 도메인을 만든다. 만일 스케줄 도메인 변경이 진행중이 아닌 경우 새 도메인들 중 cpu들이 같고  첫 번째 cpu의 perf 도메인도 이미 있는 경우 perf 도메인을 만들지 않고, 그 외의 경우 perf 도메인을 새로 만든다.
    • “/proc/sys/kernel/sched_energy_aware”
  • 코드 라인 16에서 EAS를 enable/disable 시키고 다음과 같은 로그 중 하나를 출력한다.
    • “sched_energy_set: starting EAS”
    • “sched_energy_set: stopping EAS”
  • 코드 라인 20~23에서 기존 도메인들과 속성들을 할당 해제한다.
  • 코드 라인 24~26에서 새 도메인과 속성 정보를 전역 변수에 지정한다.
  • 코드 라인 28에서 “/proc/sys/kernel/sched_domain” 디렉토리를 등록한다.

 

build_perf_domains()

kernel/sched/topology.c

static bool build_perf_domains(const struct cpumask *cpu_map)
{
        int i, nr_pd = 0, nr_cs = 0, nr_cpus = cpumask_weight(cpu_map);
        struct perf_domain *pd = NULL, *tmp;
        int cpu = cpumask_first(cpu_map);
        struct root_domain *rd = cpu_rq(cpu)->rd;
        struct cpufreq_policy *policy;
        struct cpufreq_governor *gov;

        if (!sysctl_sched_energy_aware)
                goto free;

        /* EAS is enabled for asymmetric CPU capacity topologies. */
        if (!per_cpu(sd_asym_cpucapacity, cpu)) {
                if (sched_debug()) {
                        pr_info("rd %*pbl: CPUs do not have asymmetric capacities\n",
                                        cpumask_pr_args(cpu_map));
                }
                goto free;
        }

        for_each_cpu(i, cpu_map) {
                /* Skip already covered CPUs. */
                if (find_pd(pd, i))
                        continue;

                /* Do not attempt EAS if schedutil is not being used. */
                policy = cpufreq_cpu_get(i);
                if (!policy)
                        goto free;
                gov = policy->governor;
                cpufreq_cpu_put(policy);
                if (gov != &schedutil_gov) {
                        if (rd->pd)
                                pr_warn("rd %*pbl: Disabling EAS, schedutil is mandatory\n",
                                                cpumask_pr_args(cpu_map));
                        goto free;
                }

                /* Create the new pd and add it to the local list. */
                tmp = pd_init(i);
                if (!tmp)
                        goto free;
                tmp->next = pd;
                pd = tmp;

                /*
                 * Count performance domains and capacity states for the
                 * complexity check.
                 */
                nr_pd++;
                nr_cs += em_pd_nr_cap_states(pd->em_pd);
        }

        /* Bail out if the Energy Model complexity is too high. */
        if (nr_pd * (nr_cs + nr_cpus) > EM_MAX_COMPLEXITY) {
                WARN(1, "rd %*pbl: Failed to start EAS, EM complexity is too high\n",
                                                cpumask_pr_args(cpu_map));
                goto free;
        }

        perf_domain_debug(cpu_map, pd);

        /* Attach the new list of performance domains to the root domain. */
        tmp = rd->pd;
        rcu_assign_pointer(rd->pd, pd);
        if (tmp)
                call_rcu(&tmp->rcu, destroy_perf_domain_rcu);

        return !!pd;

free:
        free_pd(pd);
        tmp = rd->pd;
        rcu_assign_pointer(rd->pd, NULL);
        if (tmp)
                call_rcu(&tmp->rcu, destroy_perf_domain_rcu);

        return false;
}

1개의 도메인에 해당하는 @cpu_map 비트마스크 멤버로 perf 도메인들을 구성한다. (1개의 도메인내에 파티션이 하나 이상 존재할 수 있다.)

  • 코드 라인 10~11에서 다음 EAS 기능이 disable된 경우 free 레이블로 이동한다.
    • “/proc/sys/kernel/sched_energy_aware”
  • 코드 라인 14~20에서 빅/리틀 같은 asym cpu capacity 도메인이 없는 경우 EAS 기능을 동작시킬 수 없으므로 정보를 출력한 후 free 레이블로 이동한다.
  • 코드 라인 22~25에서 cpu_map 비트마스크에 설정된 cpu 비트만큼 순회하며 해당 cpu가 멤버인 perf 도메인이 이미 만들어져 있는 경우 skip 한다.
  • 코드 라인 27~29에서 cpufreq policy를 가져온다. 만일 schedutil이 활성화되지 않아 가져올 수 없으면 EAS를 사용하지 못하므로 free 레이블로 이동한다.
  • 코드 라인 30~37에서 policy의 governor가 schedutil인 경우에만 EAS를 사용할 수 있다. 따라서 schedutil이 아닌 경우 free 레이블로 이동한다.
  • 코드 라인 40~44에서 perf 도메인을 만들고 리스트 연결한다.
  • 코드 라인 50~52에서 perf 도메인 수를 증가시키고, em_pd의 cap_states 수를 증가시키고 계속 순회한다.
  • 코드 라인 55~59에서 만일 너무 많은 pd가 구성되는 경우 에너지모델이 너무 복잡해지므로 free 레이블로 이동한다.
    • (cap state 수 + cpu 수) * pd 수 > 2048개
  • 코드 라인 61에서 pd 정보를 디버그 출력한다.
  • 코드 라인 64~67에서 rcu를 사용하여 루트 도메인의 기존 domain은 제거하고, 새롭게 생성한 perf 도메인을 지정한다.
  • 코드 라인 69에서 pd 생성 여부를 반환한다.
  • 코드 라인 71~78에서 free: 레이블이다. pd를 제거하고, 루트 도메인이 null pd를 지정하게한 후 false를 반환한다.

 

EM_MAX_COMPLEXITY

kernel/sched/topology.c

/*
 * EAS can be used on a root domain if it meets all the following conditions:
 *    1. an Energy Model (EM) is available;
 *    2. the SD_ASYM_CPUCAPACITY flag is set in the sched_domain hierarchy.
 *    3. the EM complexity is low enough to keep scheduling overheads low;
 *    4. schedutil is driving the frequency of all CPUs of the rd;
 *
 * The complexity of the Energy Model is defined as:
 *
 *              C = nr_pd * (nr_cpus + nr_cs)
 *
 * with parameters defined as:
 *  - nr_pd:    the number of performance domains
 *  - nr_cpus:  the number of CPUs
 *  - nr_cs:    the sum of the number of capacity states of all performance
 *              domains (for example, on a system with 2 performance domains,
 *              with 10 capacity states each, nr_cs = 2 * 10 = 20).
 *
 * It is generally not a good idea to use such a model in the wake-up path on
 * very complex platforms because of the associated scheduling overheads. The
 * arbitrary constraint below prevents that. It makes EAS usable up to 16 CPUs
 * with per-CPU DVFS and less than 8 capacity states each, for example.
 */
#define EM_MAX_COMPLEXITY 2048

(cap state 수 + cpu 수) * pd 수가 2048개를 초과하는 경우 너무 복잡하여 EAS를 사용할 수 없다.

 

pd_init()

kernel/sched/topology.c

static struct perf_domain *pd_init(int cpu)
{
        struct em_perf_domain *obj = em_cpu_get(cpu);
        struct perf_domain *pd;

        if (!obj) {
                if (sched_debug())
                        pr_info("%s: no EM found for CPU%d\n", __func__, cpu);
                return NULL;
        }

        pd = kzalloc(sizeof(*pd), GFP_KERNEL);
        if (!pd)
                return NULL;
        pd->em_pd = obj;

        return pd;
}

performance 도메인을 할당하고 초기화한 후 반환한다.

 

find_pd()

kernel/sched/topology.c

static struct perf_domain *find_pd(struct perf_domain *pd, int cpu)
{
        while (pd) {
                if (cpumask_test_cpu(cpu, perf_domain_span(pd)))
                        return pd;
                pd = pd->next;
        }

        return NULL;
}

performance 도메인들 내에 속한 @cpu를 찾는다.

  • performance 도메인들은 리스트로 연결되어 있다.

 


Perf 도메인에 EM(Energy Model) 추가

다음은 cpufreq 디바이스 드라이버 초기화 루틴을 통해 dev_pm_opp_of_register_em() 함수를 호출하여 perf 도메인에 em을 추가한 경로 예를 본다.

  • cpufreq_init() – drivers/cpufreq/cpufreq-dt.c
    • dev_pm_opp_of_register_em()
      • em_register_perf_domain()

 

em_register_perf_domain()

kernel/power/energy_model.c

/**
 * em_register_perf_domain() - Register the Energy Model of a performance domain
 * @span        : Mask of CPUs in the performance domain
 * @nr_states   : Number of capacity states to register
 * @cb          : Callback functions providing the data of the Energy Model
 *
 * Create Energy Model tables for a performance domain using the callbacks
 * defined in cb.
 *
 * If multiple clients register the same performance domain, all but the first
 * registration will be ignored.
 *
 * Reteturn 0 on success
 */
int em_register_perf_domain(cpumask_t *span, unsigned int nr_states,
                                                struct em_data_callback *cb)
{
        unsigned long cap, prev_cap = 0;
        struct em_perf_domain *pd;
        int cpu, ret = 0;

        if (!span || !nr_states || !cb)
                return -EINVAL;

        /*
         * Use a mutex to serialize the registration of performance domains and
         * let the driver-defined callback functions sleep.
         */
        mutex_lock(&em_pd_mutex);

        for_each_cpu(cpu, span) {
                /* Make sure we don't register again an existing domain. */
                if (READ_ONCE(per_cpu(em_data, cpu))) {
                        ret = -EEXIST;
                        goto unlock;
                }

                /*
                 * All CPUs of a domain must have the same micro-architecture
                 * since they all share the same table.
                 */
                cap = arch_scale_cpu_capacity(cpu);
                if (prev_cap && prev_cap != cap) {
                        pr_err("CPUs of %*pbl must have the same capacity\n",
                                                        cpumask_pr_args(span));
                        ret = -EINVAL;
                        goto unlock;
                }
                prev_cap = cap;
        }

        /* Create the performance domain and add it to the Energy Model. */
        pd = em_create_pd(span, nr_states, cb);
        if (!pd) {
                ret = -EINVAL;
                goto unlock;
        }

        for_each_cpu(cpu, span) {
                /*
                 * The per-cpu array can be read concurrently from em_cpu_get().
                 * The barrier enforces the ordering needed to make sure readers
                 * can only access well formed em_perf_domain structs.
                 */
                smp_store_release(per_cpu_ptr(&em_data, cpu), pd);
        }

        pr_debug("Created perf domain %*pbl\n", cpumask_pr_args(span));
unlock:
        mutex_unlock(&em_pd_mutex);

        return ret;
}
EXPORT_SYMBOL_GPL(em_register_perf_domain);

perf 도메인에 em을 등록한다.

  • 코드 라인 8~9에서 인자들이 0인 경우 -EINVAL 에러를 반환한다.
  • 코드 라인 17~22에서 @span 비트마스크의 cpu들을 순회하며 em_data에 이미 값이 지정된 경우 -EEXIST 에러를 반환한다.
  • 코드 라인 28~36에서 순회 중인 cpu들의 cpu capacity가 서로 다른 경우 -EINVAL 에러를 반환한다.
  • 코드 라인 39~43에서 em perf 도메인을 생성하고 em들을 추가한다.
  • 코드 라인 45~52에서 @span 비트마스크의 cpu들을 순회하며 em_data에 pd를 지정한다.
  • 코드 라인 54~58에서 pd 생성에 대한 디버그 출력을한 후 결과 값을 반환한다. (성공 시 0)

 

em_create_pd()

kernel/power/energy_model.c -1/2-

static struct em_perf_domain *em_create_pd(cpumask_t *span, int nr_states,
                                                struct em_data_callback *cb)
{
        unsigned long opp_eff, prev_opp_eff = ULONG_MAX;
        unsigned long power, freq, prev_freq = 0;
        int i, ret, cpu = cpumask_first(span);
        struct em_cap_state *table;
        struct em_perf_domain *pd;
        u64 fmax;

        if (!cb->active_power)
                return NULL;

        pd = kzalloc(sizeof(*pd) + cpumask_size(), GFP_KERNEL);
        if (!pd)
                return NULL;

        table = kcalloc(nr_states, sizeof(*table), GFP_KERNEL);
        if (!table)
                goto free_pd;

        /* Build the list of capacity states for this performance domain */
        for (i = 0, freq = 0; i < nr_states; i++, freq++) {
                /*
                 * active_power() is a driver callback which ceils 'freq' to
                 * lowest capacity state of 'cpu' above 'freq' and updates
                 * 'power' and 'freq' accordingly.
                 */
                ret = cb->active_power(&power, &freq, cpu);
                if (ret) {
                        pr_err("pd%d: invalid cap. state: %d\n", cpu, ret);
                        goto free_cs_table;
                }

                /*
                 * We expect the driver callback to increase the frequency for
                 * higher capacity states.
                 */
                if (freq <= prev_freq) {
                        pr_err("pd%d: non-increasing freq: %lu\n", cpu, freq);
                        goto free_cs_table;
                }

                /*
                 * The power returned by active_state() is expected to be
                 * positive, in milli-watts and to fit into 16 bits.
                 */
                if (!power || power > EM_CPU_MAX_POWER) {
                        pr_err("pd%d: invalid power: %lu\n", cpu, power);
                        goto free_cs_table;
                }

                table[i].power = power;
                table[i].frequency = prev_freq = freq;

                /*
                 * The hertz/watts efficiency ratio should decrease as the
                 * frequency grows on sane platforms. But this isn't always
                 * true in practice so warn the user if a higher OPP is more
                 * power efficient than a lower one.
                 */
                opp_eff = freq / power;
                if (opp_eff >= prev_opp_eff)
                        pr_warn("pd%d: hertz/watts ratio non-monotonically decreasing: em_cap_state %d >= em_cap_state%dd
\n",
                                        cpu, i, i - 1);
                prev_opp_eff = opp_eff;
        }

em perf 도메인을 생성한다.

  • 코드 라인 6에서 em 정보는 @span 비트마스크의 첫 번째 cpu를 사용한다.
  • 코드 라인 11~12에서 em data 콜백에 (*active_power) 후크 함수가 지정되지 않은 경우 null을 반환한다.
  • 코드 라인 14~20에서 em_perf_domai과 @nr_state 만큼의 테이블을 생성한다.
  • 코드 라인 23~33에서 @nr_states 만큼 순회하며 (*active_power) 후크 함수를 통해 pd 도메인의 첫 번째 cpu에 대한 첫 번째 opp 데이터의 power(mW) 및 frequency(khz) 정보를 알아온다.
  • 코드 라인 39~42에서 frequency 테이블은 항상 증가하여야 한다. 만일 frequency가 증가되지 않은 경우 에러를 출력하고 free_cs_table 레이블로 이동한다.
  • 코드 라인 48~51에서 power 값은 1~0xffff까지 사용한다. 만일 범위 밖인 경우 에러를 출력하고 free_cs_table 레이블로 이동한다.
  • 코드 라인 53~54에서 테이블에 power와 frequency를 추가한다.
  • 코드 라인 62~67에서 operating performance point effective 값을 구한다. (freq / power) 이 값이 감소되지 않는 경우 경고 메시지를 출력한다.

 

kernel/power/energy_model.c -2/2-

        /* Compute the cost of each capacity_state. */
        fmax = (u64) table[nr_states - 1].frequency;
        for (i = 0; i < nr_states; i++) {
                table[i].cost = div64_u64(fmax * table[i].power,
                                          table[i].frequency);
        }

        pd->table = table;
        pd->nr_cap_states = nr_states;
        cpumask_copy(to_cpumask(pd->cpus), span);

        em_debug_create_pd(pd, cpu);

        return pd;

free_cs_table:
        kfree(table);
free_pd:
        kfree(pd);

        return NULL;
}
  • 코드 라인 2~6에서 @nr_states 만큼 순회하며 각 테이블의 cost 값을 산출한다.
    •                                            최대 주파수
    • cost =  power(mW)  * ———————–
    •                                                주파수
  • 코드 라인 8~10에서 em perf 도메인에 테이블과 @nr_states 및 @span 정보를 대입한다.
  • 코드 라인 12에서 em perf 도메인을 위한 sysfs를 생성한다.
  • 코드 라인 14에서 생성된 em perf 도메인을 반환한다.

 

주파수와 파워 알아오기

_get_cpu_power()

drivers/opp/of.c

/*
 * Callback function provided to the Energy Model framework upon registration.
 * This computes the power estimated by @CPU at @kHz if it is the frequency
 * of an existing OPP, or at the frequency of the first OPP above @kHz otherwise
 * (see dev_pm_opp_find_freq_ceil()). This function updates @kHz to the ceiled
 * frequency and @mW to the associated power. The power is estimated as
 * P = C * V^2 * f with C being the CPU's capacitance and V and f respectively
 * the voltage and frequency of the OPP.
 *
 * Returns -ENODEV if the CPU device cannot be found, -EINVAL if the power
 * calculation failed because of missing parameters, 0 otherwise.
 */
static int __maybe_unused _get_cpu_power(unsigned long *mW, unsigned long *kHz,
                                         int cpu)
{
        struct device *cpu_dev;
        struct dev_pm_opp *opp;
        struct device_node *np;
        unsigned long mV, Hz;
        u32 cap;
        u64 tmp;
        int ret;

        cpu_dev = get_cpu_device(cpu);
        if (!cpu_dev)
                return -ENODEV;

        np = of_node_get(cpu_dev->of_node);
        if (!np)
                return -EINVAL;

        ret = of_property_read_u32(np, "dynamic-power-coefficient", &cap);
        of_node_put(np);
        if (ret)
                return -EINVAL;

        Hz = *kHz * 1000;
        opp = dev_pm_opp_find_freq_ceil(cpu_dev, &Hz);
        if (IS_ERR(opp))
                return -EINVAL;

        mV = dev_pm_opp_get_voltage(opp) / 1000;
        dev_pm_opp_put(opp);
        if (!mV)
                return -EINVAL;

        tmp = (u64)cap * mV * mV * (Hz / 1000000);
        do_div(tmp, 1000000000);

        *mW = (unsigned long)tmp;
        *kHz = Hz / 1000;

        return 0;
}

@khz를 포함하는 바로 상위의 주파수에 해당하는 cpu 파워를 알아온다. (입력 인자: @cpu, @mw, 출력 인자: @mw, @khz)

  • 코드 라인 12~14에서 cpu 디바이스가 없으면 -ENODEV 에러를 반환한다.
  • 코드 라인 16~18에서 cpu 노드 정보를 가져온다.
  • 코드 라인 20~23에서 “dynamic-power-coefficient” 속성을 읽어와서 cap에 담아둔다.
    • cpu의 에너지 효율로 리틀 cpu보다 빅 cpu의 값이 더 크다.
  • 코드 라인 25~28에서 요청한 주파수로 인접 상위 opp 데이터를 찾아온다.
  • 코드 라인 30~33에서 opp 데이터에서 volatage를 알아와서 mV로 변환한다.
  • 코드 라인 35~36에서 mW로 변환한다.
    • mW = cap * mV^2 * Mhz / 1000000000
  • 코드 라인 38~39에서 변환한 mW를 출력인자에 대입한다. 또한 주파수도 Khz로 변환하여 출력인자에 대입한다.
  • 코드 라인 41에서 성공 값 0을 반환한다.

 

다음 그림은 _get_cpu_power() 함수를 통해 요청한 주파수를 포함한 상위 인접 opp 데이터에서 mW 및 kHz를 알아오는 과정을 보여준다.

 

dynamic-power-coefficient 속성

디바이스트리의 cpu 노드에서 사용하는 “dynamic-power-coefficient” 속성값은 다음과 같이 산출되고, opp 데이터(전압, 주파수)에서 이 값을 곱해 파워(uW)를 알아내기 위해 사용된다.

 

Energy Model Sysfs

다음은 2개의 perf 도메인을 구성한 모습을 보여준다.

/sys/devices/system/cpu/energy_model
.                             ├── pd0
.                             │   ├── cost
.                             │   ├── cpus
.                             │   ├── frequency
.                             │   └── power
.                             └── pd4
.                                 ├── cost
.                                 ├── cpus
.                                 ├── frequency
.                                 └── power

 

OPP(Operating Performance Point)

다음 그림은 rk3399chip을 사용하는 rock960 보드의 opp 관련 디바이스 트리로부터 cost를 산출한 모습을 보여준다.

  • cpu 4개의 리틀 클러스터(약 400M, 600M, 800M, 1G, 1.2G, 1.4Ghz)
  • cpu 2개의 빅 클러스터(약 400M, 600M, 800M, 1G, 1.2G, 1.4G, 1.6G, 1.8Ghz)

 

참고

 

 

Scheduler -17- (Load Balance 3 NUMA)

<kernel v5.4>

NUMA 밸런싱

NUMA 밸런싱을 시작하면 동작 중인 태스크가 사용하는 메모리 페이지들의 일부 영역(약 256M)을 주기적으로 NUMA hinting faults가 발생하도록 언매핑한다. 그 후 특정 태스크가 이 영역에 접근하는 경우 NUMA hinting faults가 발생하고 이를 통해 각 태스크가 어떤 cpu 노드 또는 메모리 노드에 액세스를 하는지 그 빈도 수를 누마 faults라 하고, 이를 스캔 윈도우 주기마다 태스크 및 누마 그룹 통계로 기록하여 사용한다. 이러한 값을 사용하여 누마 페이지 마이그레이션에 이용한다.

 

NUMA 메모리 Fault score

 

다음 그림과 같이 누마 그룹의 weight와 태스크의 weight 두 기준에 대한 함수 호출관계를 보여준다.

 

group_weight()

kernel/sched/fair.c

static inline unsigned long group_weight(struct task_struct *p, int nid,
                                         int dist)
{
        struct numa_group *ng = deref_task_numa_group(p);
        unsigned long faults, total_faults;

        if (!ng)
                return 0;

        total_faults = ng->total_faults;

        if (!total_faults)
                return 0;

        faults = group_faults(p, nid);
        faults += score_nearby_nodes(p, nid, dist, false);

        return 1000 * faults / total_faults;
}

태스크의 누마 그룹에 누적된 메모리 faults 값을 해당 누마 그룹의 전체 faults에 대한 가중치 값으로 변환하여 알아온다.  (1000 = 100%)

  • 코드 라인 4~8에서 태스크가 가리키는 누마 그룹이 없으면 0을 반환한다.
  • 코드 라인 10~13에서 누마 그룹의 전체 faults 값이 0인 경우 함수를 빠져나간다.
  • 코드 라인 15에서 누마 그룹에서 관리하고 있는 @nid 노드의 faults 값을 알아온다.
  • 코드 라인 16에서 누마 그룹에서 관리하고 있는 faults에 대해 @nid 노드를 중심으로 전체 노드에 대한 faults 값을 거리별로 반비례 누적시킨 후 알아온 score 값을 faults에 추가한다.
  • 코드 라인 18에서 누마 그룹의 전체 faults에 대해 알아온 faults의 비율을 0~1000 사이 값으로 반환한다.

 

다음 그림은 특정 노드의 faults 값과 다른 노드들의 faults를 score로 변환한 값의 전체 faults에 대한 비율을 산출하는 과정을 보여준다.

 

deref_task_numa_group()

kernel/sched/fair.c

/*
 * For functions that can be called in multiple contexts that permit reading
 * ->numa_group (see struct task_struct for locking rules).
 */
static struct numa_group *deref_task_numa_group(struct task_struct *p)
{
        return rcu_dereference_check(p->numa_group, p == current ||
                (lockdep_is_held(&task_rq(p)->lock) && !READ_ONCE(p->on_cpu)));
}

태스크에 지정된 누마 그룹을 알아온다.

 

group_faults()

kernel/sched/fair.c

static inline unsigned long group_faults(struct task_struct *p, int nid)
{
        struct numa_group *ng = deref_task_numa_group(p);

        if (!ng)
                return 0;

        return ng->faults[task_faults_idx(NUMA_MEM, nid, 0)] +
                ng->faults[task_faults_idx(NUMA_MEM, nid, 1)];
}

태스크가 가리키는 누마 그룹에 누적된 @nid의 메모리 폴트 값을 알아온다.

  • 코드 라인 5~6에서 태스크에 누마 그룹이 설정되지 않은 경우 0을 반환한다.
  • 코드 라인 8~9에서 누마 그룹의 NUMA_MEM의 해당 노드의 두 개 faults[] stat을 더해서 반환한다.

 

task_faults_idx()

kernel/sched/fair.c

/*
 * The averaged statistics, shared & private, memory & CPU,
 * occupy the first half of the array. The second half of the
 * array is for current counters, which are averaged into the
 * first set by task_numa_placement.
 */
static inline int task_faults_idx(enum numa_faults_stats s, int nid, int priv)
{
        return NR_NUMA_HINT_FAULT_TYPES * (s * nr_node_ids + nid) + priv;
}

태스크에서 요청한 누마 @nid의 요청한 타입의 폴트 수를 알아온다.  @priv가 0인 경우 shared stat, 1인 경우 private 카운터 값을 반환한다.

  • 예) 4개의 노드, NUMA_CPU stat, nid=2, priv=0
    • 인덱스 = 2 * (1 * 4 + 2) + 0 = 12
  • 예) 4개의 노드, NUMA_CPU stat, nid=3, priv=0
    • 인덱스 = 2 * (1 * 4 + 3) + 0 = 14

 

task_weight()

kernel/sched/fair.c

/*
 * These return the fraction of accesses done by a particular task, or
 * task group, on a particular numa node.  The group weight is given a
 * larger multiplier, in order to group tasks together that are almost
 * evenly spread out between numa nodes.
 */
static inline unsigned long task_weight(struct task_struct *p, int nid,
                                        int dist)
{
        unsigned long faults, total_faults;

        if (!p->numa_faults)
                return 0;

        total_faults = p->total_numa_faults;

        if (!total_faults)
                return 0;

        faults = task_faults(p, nid);
        faults += score_nearby_nodes(p, nid, dist, true);

        return 1000 * faults / total_faults;
}

태스크에서 관리하고 있는 누마 faults 값을 태스크의 전체 faults에 대한 가중치 값으로 변환하여 알아온다.  (1000 = 100%)

  • 코드 라인 6~7에서 태스크의 누마 메모리 faults가 0인 경우 0을 반환한다.
  • 코드 라인 9~12에서 태스크의 전체 누마 faults 값이 0인 경우 0을 반환한다.
  • 코드 라인 14에서 태스크가 관리하고 있는 누마 faults에 대해 @nid 노드에 해당하는 faults 값을 알아온다.
  • 코드 라인 15에서 태스크에 관리하고 있는 누마 faults에 대해 @nid 노드를 중심으로 다른 노드들에 대한 faults 값을 거리별로 반비례 누적시킨 후 score로 알아온 값을 faults에 추가한다.
  • 코드 라인 17에서 태스크의 전체 누마 faults에 대해 알아온 faults의 비율을 0~1000 사이 값으로 반환한다.

 

task_faults()

kernel/sched/fair.c

static inline unsigned long task_faults(struct task_struct *p, int nid)
{
        if (!p->numa_faults)
                return 0;

        return p->numa_faults[task_faults_idx(NUMA_MEM, nid, 0)] +
                p->numa_faults[task_faults_idx(NUMA_MEM, nid, 1)];
}

태스크에 누적된 @nid의 메모리 폴트 값을 알아온다.

  • faults[] 배열은 4개의 타입 x 노드 수 x 2개와 같은 방법으로 구성되어 있다.
    • faults[4][nid][2]
    • 4개의 타입은 다음과 같다.
      • NUMA_MEM(0), NUMA_CPU(1), NUMA_MEMBUF(2), NUMA_CPUBUF(3)
  • faults[] 값들은 시간에 따라 exponential decay 된다.

 

다음 그림은 group_faults() 함수와 task_faults() 함수가 faults 데이터를 가져오는 곳을 보여준다.

 

태스크의 특정 노드에 대한 faults score 산출

score_nearby_nodes()

kernel/sched/fair.c

/* Handle placement on systems where not all nodes are directly connected. */
static unsigned long score_nearby_nodes(struct task_struct *p, int nid,
                                        int maxdist, bool task)
{
        unsigned long score = 0;
        int node;

        /*
         * All nodes are directly connected, and the same distance
         * from each other. No need for fancy placement algorithms.
         */
        if (sched_numa_topology_type == NUMA_DIRECT)
                return 0;

        /*
         * This code is called for each node, introducing N^2 complexity,
         * which should be ok given the number of nodes rarely exceeds 8.
         */
        for_each_online_node(node) {
                unsigned long faults;
                int dist = node_distance(nid, node);

                /*
                 * The furthest away nodes in the system are not interesting
                 * for placement; nid was already counted.
                 */
                if (dist == sched_max_numa_distance || node == nid)
                        continue;

                /*
                 * On systems with a backplane NUMA topology, compare groups
                 * of nodes, and move tasks towards the group with the most
                 * memory accesses. When comparing two nodes at distance
                 * "hoplimit", only nodes closer by than "hoplimit" are part
                 * of each group. Skip other nodes.
                 */
                if (sched_numa_topology_type == NUMA_BACKPLANE &&
                                        dist >= maxdist)
                        continue;

                /* Add up the faults from nearby nodes. */
                if (task)
                        faults = task_faults(p, node);
                else
                        faults = group_faults(p, node);

                /*
                 * On systems with a glueless mesh NUMA topology, there are
                 * no fixed "groups of nodes". Instead, nodes that are not
                 * directly connected bounce traffic through intermediate
                 * nodes; a numa_group can occupy any set of nodes.
                 * The further away a node is, the less the faults count.
                 * This seems to result in good task placement.
                 */
                if (sched_numa_topology_type == NUMA_GLUELESS_MESH) {
                        faults *= (sched_max_numa_distance - dist);
                        faults /= (sched_max_numa_distance - LOCAL_DISTANCE);
                }

                score += faults;
        }

        return score;
}

태스크에 대해 @nid 노드를 중심으로 전체 노드에 대한 faults 값을 거리별로 반비례 누적시킨 후 score로 반환한다. 백본 타입의 누마 토플로지를 사용하는 경우 @max_dist 이상은 skip 한다. @task가 1인 경우 태스크에서 관리하고 있는 numa faults 값을 사용하고, 0인 경우 태스크가 가리키는 누마 그룹에서 관리하고 있는 faults를 사용한다. (0=누마 direct 방식, score가 클 수록 fault가 더 많다. @nid와 더 가까운 노드들은 더 중요하므로 faults 값을 더 많이 반영한다)

  • 코드 라인 12~13에서 full 메시 형태로 모든 노드가 연결되어 있는 경우 score 0을 반환한다.
  • 코드 라인 19~28에서 온라인 노드를 순회하며 요청한 노드 @nid와의 거리가 가장 멀거나 같은 노드인 경우는 skip 한다.
  • 코드 라인 37~39에서 누마 토플로지가 백플레인 타입이면서 @nid와의 거리가 @maxdist 이상인 노드의 경우는 skip 한다.
  • 코드 라인 42~45에서 순회 중인 노드의 태스크의 누마 메모리 fault를 알아온다.
  • 코드 라인 55~58에서 누마 토플로지가 glueless 타입인 경우 다음과 같이 거리가 멀리 있을수록 faults 비율을 반비례하게 줄여 적용한다.즉 멀리있는 노드 끼리의 메모리 faults는중요하지않지만 가까이 있는 노드끼리의 메모리 faults는 더 중요하게 판단한다는 의미이다.
    •                     (최대 distance – 순회 중인 노드의 distance)
    • = faults * —————————————————–
    •                                           (최대 distance – 10)
  • 코드 라인 60~63에서 faults를 score에 누적시키고, 모든 노드에 대해 누적이 완료되면 score를 반환한다.

 

다음 그림은 특정 태스크가 사용하는 누마 그룹의 노드 0번에 대한 메모리 faults score를 산출하는 모습을 보여준다.


누마 밸런싱

 

다음 그림은 태스크에 대한 누마 밸런싱이 시작한 후 누마 스캔을 통해 누마 페이지로 변경하고, 태스크가 누마 페이지에 접근할 때의 함수 호출 과정을 보여준다.

태스크에 대한 NUMA 밸런싱 초기화

init_numa_balancing()

kernel/sched/fair.c

void init_numa_balancing(unsigned long clone_flags, struct task_struct *p)
{
        int mm_users = 0;
        struct mm_struct *mm = p->mm;

        if (mm) {
                mm_users = atomic_read(&mm->mm_users);
                if (mm_users == 1) {
                        mm->numa_next_scan = jiffies + msecs_to_jiffies(sysctl_numa_balancing_scan_delay);
                        mm->numa_scan_seq = 0;
                }
        }
        p->node_stamp                   = 0;
        p->numa_scan_seq                = mm ? mm->numa_scan_seq : 0;
        p->numa_scan_period             = sysctl_numa_balancing_scan_delay;
        /* Protect against double add, see task_tick_numa and task_numa_work */
        p->numa_work.next               = &p->numa_work;
        p->numa_faults                  = NULL;
        RCU_INIT_POINTER(p->numa_group, NULL);
        p->last_task_numa_placement     = 0;
        p->last_sum_exec_runtime        = 0;

        init_task_work(&p->numa_work, task_numa_work);

        /* New address space, reset the preferred nid */
        if (!(clone_flags & CLONE_VM)) {
                p->numa_preferred_nid = NUMA_NO_NODE;
                return;
        }

        /*
         * New thread, keep existing numa_preferred_nid which should be copied
         * already by arch_dup_task_struct but stagger when scans start.
         */
        if (mm) {
                unsigned int delay;

                delay = min_t(unsigned int, task_scan_max(current),
                        current->numa_scan_period * mm_users * NSEC_PER_MSEC);
                delay += 2 * TICK_NSEC;
                p->node_stamp = delay;
        }
}

태스크에 대한 NUMA 밸런싱을 초기화한다.

  • 코드 라인 6~12에서 유저 태스크의 경우 mm_users가 1인 경우 다음 누마 스캔 시각(numa_next_scan)을 sysctl_numa_balancing_scan_delay(디폴트 1초) 시간 후에 수행하도록 설정한다.
  • 코드 라인 13~23에서 태스크의 numa 관련 멤버들을 초기화한다. 누마 스캔 주기(numa_scan_period)는 sysctl_numa_balancing_scan_delay(디폴트 1초)로 지정한다.
  • 코드 라인 26~29에서 가상 주소 공간을 부모 태스크로 부터 clone하여 새로운 가상 주소 공간을 사용하는 태스크의 경우 새로운 누마 밸런싱을 위해 누마 우선 노드 지정을 클리어한다.
  • 코드 라인 35~42에서 유저 태스크의 경우 p->node_stamp에 위에서 설정한 누마 스캔 주기(numa_scan_period) * mm_users 시간 + 2 틱을 나노초로 대입한다.

 

스케줄 틱에서 호출

task_tick_numa()

kernel/sched/fair.c

static void task_tick_numa(struct rq *rq, struct task_struct *curr)
{
        struct callback_head *work = &curr->numa_work;
        u64 period, now;

        /*
         * We don't care about NUMA placement if we don't have memory.
         */
        if (!curr->mm || (curr->flags & PF_EXITING) || work->next != work)
                return;

        /*
         * Using runtime rather than walltime has the dual advantage that
         * we (mostly) drive the selection from busy threads and that the
         * task needs to have done some actual work before we bother with
         * NUMA placement.
         */
        now = curr->se.sum_exec_runtime;
        period = (u64)curr->numa_scan_period * NSEC_PER_MSEC;

        if (now > curr->node_stamp + period) {
                if (!curr->node_stamp)
                        curr->numa_scan_period = task_scan_start(curr);
                curr->node_stamp += period;

                if (!time_before(jiffies, curr->mm->numa_next_scan))
                        task_work_add(curr, work, true);
        }
}

정기 스케줄 틱을 통해 호출되며 cfs 태스크의 누마 메모리 faults를 스캔한다.

  • 코드 라인 9~10에서 유저 태스크가 아니거나 종료 중이거나 또 다른 워크가 존재하는 경우 함수를 빠져나간다.
  • 코드 라인 18~28에서 태스크의 총 실행 시간 기준 numa_scan_period 주기를 초과한 경우이다. node_stamp는 주기만큼 추가하고, 처음인 경우 누마 스캔 주기(numa_scan_period)를 누마 그룹으로 부터 scan 주기를 알아와 설정한다. 다음 스캔 시각(numa_next_scan)을 넘긴 경우 p->task_works 리스트에 누마 워크를 추가한다.
    • 추가된 work는 커널에서 유저로 복귀 시 다음과 같은 경로로 호출되어 실행된다.
      • arch/arm64/entry.S – work_pending: 레이블 -> do_notify_resume() -> do_signal() -> get_signal() -> task_work_run() 함수에서 펜딩 워크들이 호출되어 실행된다.

 

누마 스캔 작업

task_numa_work()

kernel/sched/fair.c -1/2-

/*
 * The expensive part of numa migration is done from task_work context.
 * Triggered from task_tick_numa().
 */
static void task_numa_work(struct callback_head *work)
{
        unsigned long migrate, next_scan, now = jiffies;
        struct task_struct *p = current;
        struct mm_struct *mm = p->mm;
        u64 runtime = p->se.sum_exec_runtime;
        struct vm_area_struct *vma;
        unsigned long start, end;
        unsigned long nr_pte_updates = 0;
        long pages, virtpages;

        SCHED_WARN_ON(p != container_of(work, struct task_struct, numa_work));

        work->next = work;
        /*
         * Who cares about NUMA placement when they're dying.
         *
         * NOTE: make sure not to dereference p->mm before this check,
         * exit_task_work() happens _after_ exit_mm() so we could be called
         * without p->mm even though we still had it when we enqueued this
         * work.
         */
        if (p->flags & PF_EXITING)
                return;

        if (!mm->numa_next_scan) {
                mm->numa_next_scan = now +
                        msecs_to_jiffies(sysctl_numa_balancing_scan_delay);
        }

        /*
         * Enforce maximal scan/migration frequency..
         */
        migrate = mm->numa_next_scan;
        if (time_before(now, migrate))
                return;

        if (p->numa_scan_period == 0) {
                p->numa_scan_period_max = task_scan_max(p);
                p->numa_scan_period = task_scan_start(p);
        }

        next_scan = now + msecs_to_jiffies(p->numa_scan_period);
        if (cmpxchg(&mm->numa_next_scan, migrate, next_scan) != migrate)
                return;

        /*
         * Delay this task enough that another task of this mm will likely win
         * the next time around.
         */
        p->node_stamp += 2 * TICK_NSEC;

        start = mm->numa_scan_offset;
        pages = sysctl_numa_balancing_scan_size;
        pages <<= 20 - PAGE_SHIFT; /* MB in pages */
        virtpages = pages * 8;     /* Scan up to this much virtual space */
        if (!pages)
                return;

누마 스캔 주기마다 동작하는 cost가 높은 작업으로 태스크의 vma 영역을 NUMA hinting fault가 발생하도록 매핑을 변경한다. 한 번 처리할 때마다 sysctl_numa_balancing_scan_size  만큼씩 영역을 처리한다.

  • 코드 라인 23~24에서 이미 태스크가 종료가 진행 중인 경우 함수를 빠져나간다.
  • 코드 라인 26~29에서 다음 누마 스캔 시각(numa_next_scan)가 설정되지 않은 경우 현재 시각에 sysctl_numa_balancing_scan_delay(디폴트 1초)를 추가하여 설정한다.
  • 코드 라인 34~36에서 누마 스캔 시각이 지나지 않은 경우 함수를 빠져나간다.
  • 코드 라인 38~41에서 누마 스캔 주기(numa_scan_period)가 설정되지 않은 경우 numa_scan_period_max와 numa_scanm_period를 초기 설정한다.
  • 코드 라인 43~45에서 다음 누마 스캔 시각(numa_next_scan)에 현재 시각 + 누마 스캔 주기(numa_scan_period)로 설정한다. 만일 다른 cpu 등에서 이 값을 먼저 교체한 경우 현재 cpu는 처리를 양보하기 위해 함수를 빠져나간다.
  • 코드 라인 51에서 p->node_stamp에 2 틱 만큼의 시간을 추가한다.
  • 코드 라인 53~58에서 스캔을 시작할 주소와 누마 스캔 사이즈를 알아와서 바이트 단위로 변경하여 pages에 대입한다. 이 함수가 호출되어 한 번에 처리할 영역 사이즈이다. 그리고 이 값의 8배를 virtpages에 대입하는데, 역시 한 번 처리할 때마다 사용할 스캔 영역의 크기이다.

 

kernel/sched/fair.c -2/2-

        if (!down_read_trylock(&mm->mmap_sem))
                return;
        vma = find_vma(mm, start);
        if (!vma) {
                reset_ptenuma_scan(p);
                start = 0;
                vma = mm->mmap;
        }
        for (; vma; vma = vma->vm_next) {
                if (!vma_migratable(vma) || !vma_policy_mof(vma) ||
                        is_vm_hugetlb_page(vma) || (vma->vm_flags & VM_MIXEDMAP)) {
                        continue;
                }

                /*
                 * Shared library pages mapped by multiple processes are not
                 * migrated as it is expected they are cache replicated. Avoid
                 * hinting faults in read-only file-backed mappings or the vdso
                 * as migrating the pages will be of marginal benefit.
                 */
                if (!vma->vm_mm ||
                    (vma->vm_file && (vma->vm_flags & (VM_READ|VM_WRITE)) == (VM_READ)))
                        continue;

                /*
                 * Skip inaccessible VMAs to avoid any confusion between
                 * PROT_NONE and NUMA hinting ptes
                 */
                if (!(vma->vm_flags & (VM_READ | VM_EXEC | VM_WRITE)))
                        continue;

                do {
                        start = max(start, vma->vm_start);
                        end = ALIGN(start + (pages << PAGE_SHIFT), HPAGE_SIZE);
                        end = min(end, vma->vm_end);
                        nr_pte_updates = change_prot_numa(vma, start, end);

                        /*
                         * Try to scan sysctl_numa_balancing_size worth of
                         * hpages that have at least one present PTE that
                         * is not already pte-numa. If the VMA contains
                         * areas that are unused or already full of prot_numa
                         * PTEs, scan up to virtpages, to skip through those
                         * areas faster.
                         */
                        if (nr_pte_updates)
                                pages -= (end - start) >> PAGE_SHIFT;
                        virtpages -= (end - start) >> PAGE_SHIFT;

                        start = end;
                        if (pages <= 0 || virtpages <= 0)
                                goto out;

                        cond_resched();
                } while (end != vma->vm_end);
        }

out:
        /*
         * It is possible to reach the end of the VMA list but the last few
         * VMAs are not guaranteed to the vma_migratable. If they are not, we
         * would find the !migratable VMA on the next scan but not reset the
         * scanner to the start so check it now.
         */
        if (vma)
                mm->numa_scan_offset = start;
        else
                reset_ptenuma_scan(p);
        up_read(&mm->mmap_sem);

        /*
         * Make sure tasks use at least 32x as much time to run other code
         * than they used here, to limit NUMA PTE scanning overhead to 3% max.
         * Usually update_task_scan_period slows down scanning enough; on an
         * overloaded system we need to limit overhead on a per task basis.
         */
        if (unlikely(p->se.sum_exec_runtime != runtime)) {
                u64 diff = p->se.sum_exec_runtime - runtime;
                p->node_stamp += 32 * diff;
        }
}
  • 코드 라인 3~8에서 mm 내에서 누마 스캔할 가상 주소가 포함된 vma를 알아온다. vma가 발견되지 않은 경우 시작 주소를 0으로 변경하고, vma로 mmap 매핑의 처음을 사용한다.
  • 코드 라인 9~30에서 vma를 순회하며 다음 경우에 한하여 skip 한다.(누마밸런싱은 페이지의 migration과 함께 한다)
    • migratable(페이지 이동) 하지 않은 vma 영역
    • migration 시 fault 되도록 정책(MPOL_F_MOF)된 vma 영역이 아닌 경우
    • hugetlb 페이지 영역
    • VM_MIXEDMAP 플래그를 사용한 영역으로 struct page 및 pure PFN 페이지가 포함가능한 영역
    • vma->vm_mm 이 지정되지 않은 경우
    • read only 파일 매핑인 경우
    • rwx(read/write/excute)가 하나도 설정되지 않은 영역
  • 코드 라인 32~55에서 순회 중인 vma 영역의 끝까지 페이지 매핑 protection을 PAGE_NONE으로 변경하여 NUMA hinting fault를 유발할 수 있게 한다. 매핑 변경이 성공한 경우 해당 vma 영역은 sysctl_numa_balancing_scan_size 에서 감소시키고, 스캔 영역 크기는 최대 sysctl_numa_balancing_scan_size의 8배 크기로 제한한다.
  • 코드 라인 58~68에서 out: 레이블이다. vma 영역을 모두 처리하지 않은 경우 다음 스캔 시작 지점을 해당 vma의 끝 주소부터 시작하게 설정해 둔다. vma 영역 모두 끝난 경우 다시 처음 부터 시작될 수 있게 리셋한다.
  • 코드 라인 77~80에서 이 함수가 처리되는 동안 태스크의 총 실행 누적 시간이 변경된 경우 그 차이분 만큼의 32배를 곱해 p->node_stamp에 기록한다.

 

reset_ptenuma_scan()

kernel/sched/fair.c

static void reset_ptenuma_scan(struct task_struct *p)
{
        /*
         * We only did a read acquisition of the mmap sem, so
         * p->mm->numa_scan_seq is written to without exclusive access
         * and the update is not guaranteed to be atomic. That's not
         * much of an issue though, since this is just used for
         * statistical sampling. Use READ_ONCE/WRITE_ONCE, which are not
         * expensive, to avoid any form of compiler optimizations:
         */
        WRITE_ONCE(p->mm->numa_scan_seq, READ_ONCE(p->mm->numa_scan_seq) + 1);
        p->mm->numa_scan_offset = 0;
}

누마 스캔 시작 주소를 0으로 리셋한다.

 

NUMA fault 영역으로 변경

change_prot_numa()

mm/mempolicy.c

/*
 * This is used to mark a range of virtual addresses to be inaccessible.
 * These are later cleared by a NUMA hinting fault. Depending on these
 * faults, pages may be migrated for better NUMA placement.
 *
 * This is assuming that NUMA faults are handled using PROT_NONE. If
 * an architecture makes a different choice, it will need further
 * changes to the core.
 */
unsigned long change_prot_numa(struct vm_area_struct *vma,
                        unsigned long addr, unsigned long end)
{
        int nr_updated;

        nr_updated = change_protection(vma, addr, end, PAGE_NONE, 0, 1);
        if (nr_updated)
                count_vm_numa_events(NUMA_PTE_UPDATES, nr_updated);

        return nr_updated;
}

vma 영역의 가상 주소 @addr ~ @end 범위를 NUMA hinging fault가 발생하게 PROT_NONE 매핑 속성으로 변경한다.

  • PROT_NONE 매핑 속성
    • NUMA 밸런싱을 위해 강제로 액세스 불가능 형태로 바꾸어 이 페이지에 처음 접근할 때에 한하여 numa fault가 발생하게 한다.

 


NUMA 페이지 접근

 

다음 그림은 태스크가 누마 페이지에 접근하여 faults 통계를 갱신하고 밸런싱을 하는 함수 호출과정을 보여준다.

NUMA faults 동작

task_numa_fault()

fault 핸들러 handle_mm_fault() -> __handle_mm_fault() -> handle_pte_fault() -> do_numa_page() 함수로 부터 진입된다.

kernel/sched/fair.c

/*
 * Got a PROT_NONE fault for a page on @node.
 */
void task_numa_fault(int last_cpupid, int mem_node, int pages, int flags)
{
        struct task_struct *p = current;
        bool migrated = flags & TNF_MIGRATED;
        int cpu_node = task_node(current);
        int local = !!(flags & TNF_FAULT_LOCAL);
        struct numa_group *ng;
        int priv;

        if (!static_branch_likely(&sched_numa_balancing))
                return;

        /* for example, ksmd faulting in a user's mm */
        if (!p->mm)
                return;

        /* Allocate buffer to track faults on a per-node basis */
        if (unlikely(!p->numa_faults)) {
                int size = sizeof(*p->numa_faults) *
                           NR_NUMA_HINT_FAULT_BUCKETS * nr_node_ids;

                p->numa_faults = kzalloc(size, GFP_KERNEL|__GFP_NOWARN);
                if (!p->numa_faults)
                        return;

                p->total_numa_faults = 0;
                memset(p->numa_faults_locality, 0, sizeof(p->numa_faults_locality));
        }

        /*
         * First accesses are treated as private, otherwise consider accesses
         * to be private if the accessing pid has not changed
         */
        if (unlikely(last_cpupid == (-1 & LAST_CPUPID_MASK))) {
                priv = 1;
        } else {
                priv = cpupid_match_pid(p, last_cpupid);
                if (!priv && !(flags & TNF_NO_GROUP))
                        task_numa_group(p, last_cpupid, flags, &priv);
        }

        /*
         * If a workload spans multiple NUMA nodes, a shared fault that
         * occurs wholly within the set of nodes that the workload is
         * actively using should be counted as local. This allows the
         * scan rate to slow down when a workload has settled down.
         */
        ng = deref_curr_numa_group(p);
        if (!priv && !local && ng && ng->active_nodes > 1 &&
                                numa_is_active_node(cpu_node, ng) &&
                                numa_is_active_node(mem_node, ng))
                local = 1;

        /*
         * Retry to migrate task to preferred node periodically, in case it
         * previously failed, or the scheduler moved us.
         */
        if (time_after(jiffies, p->numa_migrate_retry)) {
                task_numa_placement(p);
                numa_migrate_preferred(p);
        }

        if (migrated)
                p->numa_pages_migrated += pages;
        if (flags & TNF_MIGRATE_FAIL)
                p->numa_faults_locality[2] += pages;

        p->numa_faults[task_faults_idx(NUMA_MEMBUF, mem_node, priv)] += pages;
        p->numa_faults[task_faults_idx(NUMA_CPUBUF, cpu_node, priv)] += pages;
        p->numa_faults_locality[local] += pages;
}

누마 hinting fault가 발생하고 마이그레이션 후에 이 함수가 호출되었다. 이 함수에서는 numa fault 관련 통계들을 증가시킨다.

  • 코드 라인 10~11에서 누마 밸런싱이 설정되지 않은 경우 함수를 빠져나간다.
  • 코드 라인 14~15에서 유저 태스크가 아닌 경우 함수를 빠져나간다.
  • 코드 라인 18~28에서 처음에 한하여 태스크에 numa_faults[]를 할당하고, total_numa_faults 및 numa_faults_locality[]를 클리어한다.
    • 4 가지 타입 * 노드 수 * 2 (private|shared) 만큼 배열을 할당한다.
  • 코드 라인 34~40에서 priv 값을 다음과 같이 설정한다.
    • 처음 접근 시 priv=1
    • 처음 접근이 아닌 경우 priv 값은 태스크에 설정된 pid가 lastcpupid와 같은 pid 사용 여부이다. 단 priv가 0이고 TNF_NO_GROUP 플래그를 사용하는 경우 누마 그룹을 통해 priv를 알아온다.
  • 코드 라인 48~52에서 priv가 0이고 리모트 노드에서 누마 그룹의 active 노드가 2개 이상이며, mem_node와 cpu_node가 모두 active 상태인 경우 local에 1을 대입한다.
  • 코드 라인 58~61에서 현재 시각이 numa_migrate_retry 시각을 넘긴 경우 태스크를 preferred 노드로 옮기는 것을 재시도한다.
  • 코드 라인 63~64에서 TNF_MIGRATED 플래그를 사용한 경우 numa_pages_migrated에 페이지 수를 추가한다.
  • 코드 라인 65~66에서 TNF_MIGRATE_FAIL 플래그를 사용한 경우 numa_faults_locality[2]에 페이지 수를 추가한다.
    • numa_faults_locality[]
      • 0=remote
      • 1=local
      • 2=failed to migrate
  • 코드 라인 68~70에서 numa_faults[]에 페이지 수를 추가하여 갱신하고, numa_faults_locality[]의 로컬에도 페이지 수를 추가한다.

 

task_numa_group()

kernel/sched/fair.c -1/2-

static void task_numa_group(struct task_struct *p, int cpupid, int flags,
                        int *priv)
{
        struct numa_group *grp, *my_grp;
        struct task_struct *tsk;
        bool join = false;
        int cpu = cpupid_to_cpu(cpupid);
        int i;

        if (unlikely(!deref_curr_numa_group(p))) {
                unsigned int size = sizeof(struct numa_group) +
                                    4*nr_node_ids*sizeof(unsigned long);

                grp = kzalloc(size, GFP_KERNEL | __GFP_NOWARN);
                if (!grp)
                        return;

                refcount_set(&grp->refcount, 1);
                grp->active_nodes = 1;
                grp->max_faults_cpu = 0;
                spin_lock_init(&grp->lock);
                grp->gid = p->pid;
                /* Second half of the array tracks nids where faults happen */
                grp->faults_cpu = grp->faults + NR_NUMA_HINT_FAULT_TYPES *
                                                nr_node_ids;

                for (i = 0; i < NR_NUMA_HINT_FAULT_STATS * nr_node_ids; i++)
                        grp->faults[i] = p->numa_faults[i];

                grp->total_faults = p->total_numa_faults;

                grp->nr_tasks++;
                rcu_assign_pointer(p->numa_group, grp);
        }

        rcu_read_lock();
        tsk = READ_ONCE(cpu_rq(cpu)->curr);

        if (!cpupid_match_pid(tsk, cpupid))
                goto no_join;

        grp = rcu_dereference(tsk->numa_group);
        if (!grp)
                goto no_join;

        my_grp = deref_curr_numa_group(p);
        if (grp == my_grp)
                goto no_join;

        /*
         * Only join the other group if its bigger; if we're the bigger group,
         * the other task will join us.
         */
        if (my_grp->nr_tasks > grp->nr_tasks)
                goto no_join;

        /*
         * Tie-break on the grp address.
         */
        if (my_grp->nr_tasks == grp->nr_tasks && my_grp > grp)
                goto no_join;

        /* Always join threads in the same process. */
        if (tsk->mm == current->mm)
                join = true;

        /* Simple filter to avoid false positives due to PID collisions */
        if (flags & TNF_SHARED)
                join = true;

        /* Update priv based on whether false sharing was detected */
        *priv = !join;

        if (join && !get_numa_group(grp))
                goto no_join;

        rcu_read_unlock();

        if (!join)
                return;

누마 hinting faults을 통해 누마 마이그레이션에 대한 누마 faults 관련 stat을 갱신한다. 만일 요청한 태스크 @p가 처음 접근한 경우엔 태스크에 누마 그룹을 생성한다. 출력 인자 @priv에 1이 단일 접근인 경우이고, 0이 출력되면 공유 접근한 상태이다.

  • 코드 라인 10~34에서 처음인 경우 태스크에 누마 그룹을 할당한 후 내부 멤버들을 초기화한다. 또한 누마 그룹내 faults[] 배열을 할당하고 역시 초기화한다.
  • 코드 라인 36~61에서 다음에 해당하는 경우 no_join 레이블을 통해 함수를 빠져나간다.
    • 현재 cpu에서 동작 중인 태스크와 cpupid의 pid가 서로 다른 경우
    • 현재 태스크의 누마 그룹이 지정되지 않은 경우
    • 현재 태스크의 누마 그룹과 요청한 태스크의 누마 그룹이 서로 같은 경우
    • 현재 태스크의 누마 그룹에서 동작 중인 태스크의 수 보다 요청한 태스크의 그룹에서 동작 중인 태스크의 수 보다 큰 경우
    • 현재 태스크의 누마 그룹에서 동작 중인 태스크의 수와 요청한 태스크의 그룹에서 동작 중인 태스크의 수가 동일한 경우 두 그룹의 주소를 비교하여 요청한 태스크의 그룹 주소가 더 큰 경우
  • 코드 라인 64~69에서 다음의 경우에 한해 join=true로 설정한다.
    • 현재 태스크와 요청한 태스크의 프로세스가 동일한 경우
    • TNF_SHARED 플래그를 사용한 경우
  • 코드 라인 72에서 출력 인자 *priv에는 join의 반대 값을 대입한다.
  • 코드 라인 74~75에서 join=true일 때 현재 태스크의 그룹의 참조 카운터를 1 증가시킨다.
  • 코드 라인 79~80에서 join=false인 경우 함수를 빠져나간다.

 

kernel/sched/fair.c -2/2-

        BUG_ON(irqs_disabled());
        double_lock_irq(&my_grp->lock, &grp->lock);

        for (i = 0; i < NR_NUMA_HINT_FAULT_STATS * nr_node_ids; i++) {
                my_grp->faults[i] -= p->numa_faults[i];
                grp->faults[i] += p->numa_faults[i];
        }
        my_grp->total_faults -= p->total_numa_faults;
        grp->total_faults += p->total_numa_faults;

        my_grp->nr_tasks--;
        grp->nr_tasks++;

        spin_unlock(&my_grp->lock);
        spin_unlock_irq(&grp->lock);

        rcu_assign_pointer(p->numa_group, grp);

        put_numa_group(my_grp);
        return;

no_join:
        rcu_read_unlock();
        return;
}
  • 코드 라인 2에서 현재 태스크의 누마 그룹과 요청한 태스크의 그룹 둘 모두 한꺼번에 스핀락을 건다.
  • 코드 라인 4~12에서 4 종류의 누마 fault stats를 순회하며 태스크의 누마 faults 값을 이동시키고, tatal_faults와 nr_tasks 수도 이동시킨다. (요청한 태스크의 누마 그룹 -> 현재 태스크의 누마 그룹)
  • 코드 라인 14~15에서 두 스핀락을 해제한다.
  • 코드 라인 19~20에서 요청한 태스크의 누마 그룹 참조 카운터를 1 감소시킨 후 정상적으로 함수를 빠져나간다.
  • 코드 라인 22~24에서 no_join: 레이블이다. 함수를 빠져나간다.

 

numa_is_active_node()

kernel/sched/fair.c

static bool numa_is_active_node(int nid, struct numa_group *ng)
{
        return group_faults_cpu(ng, nid) * ACTIVE_NODE_FRACTION > ng->max_faults_cpu;
}

누마 그룹 @ng의 faults 통계를 보고 누마 노드 @nid에 대한 활성화 여부를 반환한다.

  • faults 수 * 3배한 값이 누마 그룹 @ng의 max_faults_cpu보다 큰지 여부를 반환한다.

 

ACTIVE_NODE_FRACTION

kernel/sched/fair.c

/*
 * A node triggering more than 1/3 as many NUMA faults as the maximum is
 * considered part of a numa group's pseudo-interleaving set. Migrations
 * between these nodes are slowed down, to allow things to settle down.
 */
#define ACTIVE_NODE_FRACTION 3

 

최적의 누마 노드로 태스크 이동

task_numa_placement()

kernel/sched/fair.c -1/2-

static void task_numa_placement(struct task_struct *p)
{
        int seq, nid, max_nid = NUMA_NO_NODE;
        unsigned long max_faults = 0;
        unsigned long fault_types[2] = { 0, 0 };
        unsigned long total_faults;
        u64 runtime, period;
        spinlock_t *group_lock = NULL;
        struct numa_group *ng;

        /*
         * The p->mm->numa_scan_seq field gets updated without
         * exclusive access. Use READ_ONCE() here to ensure
         * that the field is read in a single access:
         */
        seq = READ_ONCE(p->mm->numa_scan_seq);
        if (p->numa_scan_seq == seq)
                return;
        p->numa_scan_seq = seq;
        p->numa_scan_period_max = task_scan_max(p);

        total_faults = p->numa_faults_locality[0] +
                       p->numa_faults_locality[1];
        runtime = numa_get_avg_runtime(p, &period);

        /* If the task is part of a group prevent parallel updates to group stats */
        ng = deref_curr_numa_group(p);
        if (ng) {
                group_lock = &ng->lock;
                spin_lock_irq(group_lock);
        }
  • 코드 라인 16~18에서 누마 스캔 시퀀스에 변동이 없으면 함수를 빠져나간다.
  • 코드 라인 19~20에서 바뀐 누마 스캔 시퀀스를 갱신하고, 누마 스캔 주기 최대치를 갱신한다.
  • 코드 라인 22~23에서 태스크에 대한 numa_faults_locality 값을 알아온다. (remote + local)
  • 코드 라인 24에서 태스크의 지난 누마 placement 사이클 동안의 런타임을 알아오고 period에는 기간을 알아온다.
    • 평균 런타임은 runtime / period를 해야 알 수 있다.
  • 코드 라인 27~31에서 태스크에 대한 누마 그룹이 있는 경우 그룹 스핀 락을 획득한다.

 

kernel/sched/fair.c -2/2-

        /* Find the node with the highest number of faults */
        for_each_online_node(nid) {
                /* Keep track of the offsets in numa_faults array */
                int mem_idx, membuf_idx, cpu_idx, cpubuf_idx;
                unsigned long faults = 0, group_faults = 0;
                int priv;

                for (priv = 0; priv < NR_NUMA_HINT_FAULT_TYPES; priv++) {
                        long diff, f_diff, f_weight;

                        mem_idx = task_faults_idx(NUMA_MEM, nid, priv);
                        membuf_idx = task_faults_idx(NUMA_MEMBUF, nid, priv);
                        cpu_idx = task_faults_idx(NUMA_CPU, nid, priv);
                        cpubuf_idx = task_faults_idx(NUMA_CPUBUF, nid, priv);

                        /* Decay existing window, copy faults since last scan */
                        diff = p->numa_faults[membuf_idx] - p->numa_faults[mem_idx] / 2;
                        fault_types[priv] += p->numa_faults[membuf_idx];
                        p->numa_faults[membuf_idx] = 0;

                        /*
                         * Normalize the faults_from, so all tasks in a group
                         * count according to CPU use, instead of by the raw
                         * number of faults. Tasks with little runtime have
                         * little over-all impact on throughput, and thus their
                         * faults are less important.
                         */
                        f_weight = div64_u64(runtime << 16, period + 1);
                        f_weight = (f_weight * p->numa_faults[cpubuf_idx]) /
                                   (total_faults + 1);
                        f_diff = f_weight - p->numa_faults[cpu_idx] / 2;
                        p->numa_faults[cpubuf_idx] = 0;

                        p->numa_faults[mem_idx] += diff;
                        p->numa_faults[cpu_idx] += f_diff;
                        faults += p->numa_faults[mem_idx];
                        p->total_numa_faults += diff;
                        if (ng) {
                                /*
                                 * safe because we can only change our own group
                                 *
                                 * mem_idx represents the offset for a given
                                 * nid and priv in a specific region because it
                                 * is at the beginning of the numa_faults array.
                                 */
                                ng->faults[mem_idx] += diff;
                                ng->faults_cpu[mem_idx] += f_diff;
                                ng->total_faults += diff;
                                group_faults += ng->faults[mem_idx];
                        }
                }

                if (!ng) {
                        if (faults > max_faults) {
                                max_faults = faults;
                                max_nid = nid;
                        }
                } else if (group_faults > max_faults) {
                        max_faults = group_faults;
                        max_nid = nid;
                }
        }

        if (ng) {
                numa_group_count_active_nodes(ng);
                spin_unlock_irq(group_lock);
                max_nid = preferred_group_nid(p, max_nid);
        }

        if (max_faults) {
                /* Set the new preferred node */
                if (max_nid != p->numa_preferred_nid)
                        sched_setnuma(p, max_nid);
        }

        update_task_scan_period(p, fault_types[0], fault_types[1]);
}
  • 코드 라인 2~8에서 온라인 노드를 순회하고, 다시 그 내부에서 누마 hint fault 타입 수(private, shared)만큼 순회한다.
  • 코드 라인 17~19에서 태스크에 대한 누마 faults들 중 membuf에서 mem의 절반을 뺀 값을 diff에 대입하고, 순회 중인 fault 타입의 임시 배열 fault_types[]에 membuf의 값을 추가하고, membuf는 클리어한다.
  • 코드 라인 28~32에서 누마 placement 사이클 동안의 평균 런타임을 16비트 정확도의 이진화 정수 값에 태스크의 fault 중 numa_faults[cpubuf_idx] 비율 만큼 곱한 값을 f_weight에 담고 최종 p->numa_faults[cpu_idx]의 절반을 뺀 값을 f_diff에 담는다. 그 후 p->numa_faults[cpubuf_idx]는 클리어한다.
  • 코드 라인 34~37에서 mem_idx 및 cpu_idx의 p->numa_faults[] 값에 diff 및 f_diff 값을 추가하고, 이렇게 누적된 p->numa_faults[mem_idx] 값을 faults에 다시 누적하고, p->total_numa_fuautls에 diff를 누적한다.
  • 코드 라인 38~50에서 누마 그룹의 faults, faults_cpu, total_faults 들에 대해서도 diff 만큼 추가하고, group_faults에는 ng->faults[mem_idx]를 누적시킨다.
  • 코드 라인 53~61에서 max_faults와 max_nid를 갱신한다.
  • 코드 라인 64~68에서 누마 그룹의 최대 faults 수와 active 노드 수를 갱신하고, 태스크에 가장 적합한 우선 노드를 알아와서 max_nid에 대입한다.
  • 코드 라인 70~74에서 태스크의 우선 노드로 max_nid를 지정한다.
  • 코드 라인 76에서 태스크의 누마 스캔 주기의 증/감을 갱신한다.

 

numa_get_avg_runtime()

kernel/sched/fair.c

/*
 * Get the fraction of time the task has been running since the last
 * NUMA placement cycle. The scheduler keeps similar statistics, but
 * decays those on a 32ms period, which is orders of magnitude off
 * from the dozens-of-seconds NUMA balancing period. Use the scheduler
 * stats only if the task is so new there are no NUMA statistics yet.
 */
static u64 numa_get_avg_runtime(struct task_struct *p, u64 *period)
{
        u64 runtime, delta, now;
        /* Use the start of this time slice to avoid calculations. */
        now = p->se.exec_start;
        runtime = p->se.sum_exec_runtime;

        if (p->last_task_numa_placement) {
                delta = runtime - p->last_sum_exec_runtime;
                *period = now - p->last_task_numa_placement;

                /* Avoid time going backwards, prevent potential divide error: */
                if (unlikely((s64)*period < 0))
                        *period = 0;
        } else {
                delta = p->se.avg.load_sum;
                *period = LOAD_AVG_MAX;
        }

        p->last_sum_exec_runtime = runtime;
        p->last_task_numa_placement = now;

        return delta;
}

태스크 @p의 지난 누마 placement 사이클 동안의 런타임을 알아온다. 출력 인자 *period에는 지난 누마 placement 사이클이 담긴다.

  • 코드 라인 5~6에서 태스크의 이번 스케줄 실행 시각과 총 누적 실행 시간을 알아온다.
    • p->exec_start는 태스크가 스케줄되거나, 매 스케줄 틱마다 현재 시각(런큐 클럭)으로 갱신한다.
    • p->se.sum_exec_runtime에는 스케줄 틱마다 태스크의 총 누적 실행 시간이 담겨있다.
  • 코드 라인 8~18에서 task_numa_placement 함수를 통해 갱신된 적이 있는지 여부에 따라 다음과 같이 처리한다.
    • 갱신된 적이 있으면 태스크의 총 누적 실행 시간에서 지난 갱신 되었던 총 실행 시간을 뺀 delta 값을 알아오고, 출력 인자 *period에는 현재 시각에서 지난 갱신 시각을 뺀 기간을 반환한다.
    • 갱신된 적이 없으면 태스크의 로드 합을 delta에 담고, 출력 인자 *perido에 전체 기간(LOAD_AVG_MAX)를 담는다.
  • 코드 라인 20~21에서 처음 알아온 runtime과 now를 갱신한다.
  • 코드 라인 23에서 delta 실행 시간을 반환한다.

 

numa_group_count_active_nodes()

kernel/sched/fair.c

/*
 * Find out how many nodes on the workload is actively running on. Do this by
 * tracking the nodes from which NUMA hinting faults are triggered. This can
 * be different from the set of nodes where the workload's memory is currently
 * located.
 */
static void numa_group_count_active_nodes(struct numa_group *numa_group)
{
        unsigned long faults, max_faults = 0;
        int nid, active_nodes = 0;

        for_each_online_node(nid) {
                faults = group_faults_cpu(numa_group, nid);
                if (faults > max_faults)
                        max_faults = faults;
        }

        for_each_online_node(nid) {
                faults = group_faults_cpu(numa_group, nid);
                if (faults * ACTIVE_NODE_FRACTION > max_faults)
                        active_nodes++;
        }

        numa_group->max_faults_cpu = max_faults;
        numa_group->active_nodes = active_nodes;
}

@numa_group의 max_faults_cpu와 active_nodes를 갱신해온다.

  • 코드 라인 6~10에서 모든 온라인 노드들을 순회하며 @numa_group의 faults들 중 가장 큰 값을 max_faults에 알아온다.
  • 코드 라인 12~16에서 모든 온라인 노드들을 순회하며 @numa_group의 faults에 액티브 비율을 적용한 값이 max_faults를 초과하는 도드들의 수를 active_nodes에 알아온다.
  • 코드 라인 18~19에서 @numa_group의 max_faults_cpu와 active_nodes를 갱신한다.

 

태스크에 적절한 우선 노드 찾기

preferred_group_nid()

kernel/sched/fair.c -1/2-

/*
 * Determine the preferred nid for a task in a numa_group. This needs to
 * be done in a way that produces consistent results with group_weight,
 * otherwise workloads might not converge.
 */
static int preferred_group_nid(struct task_struct *p, int nid)
{
        nodemask_t nodes;
        int dist;

        /* Direct connections between all NUMA nodes. */
        if (sched_numa_topology_type == NUMA_DIRECT)
                return nid;

        /*
         * On a system with glueless mesh NUMA topology, group_weight
         * scores nodes according to the number of NUMA hinting faults on
         * both the node itself, and on nearby nodes.
         */
        if (sched_numa_topology_type == NUMA_GLUELESS_MESH) {
                unsigned long score, max_score = 0;
                int node, max_node = nid;

                dist = sched_max_numa_distance;

                for_each_online_node(node) {
                        score = group_weight(p, node, dist);
                        if (score > max_score) {
                                max_score = score;
                                max_node = node;
                        }
                }
                return max_node;
        }

태스크에 가장 적절한 누마 우선 노드를 알아온다. 누마 노드 타입에 따라 다음과 같이 알아온다.

  • direct 노드 타입의 경우 @nid를 반환한다.
  • glueless mesh 노드 타입의 경우 모든 노드에서 태스크 @p에 대한 그룹 weight가 가장 큰 노드를 선택한다.
  • backplain 노드 타입의 경우 가장 큰 distance부터 시작하여 노드들 중 다른 노드들과의 그룹 faults가 가장 큰 노드를 선택한다. 그룹 faults가 없는 경우 다음 distance를 진행한다.

 

  • 코드 라인 7~8에서 누마 direct 노드 타입의 경우 인자로 전달받은 @nid를 우선 노드로 사용하기 위해 반환한다.
  • 코드 라인 15~29에서 누마 glueless mesh 노드 타입의 경우 태스크 @p와 각 노드 간에 그룹 weight가 가장 큰 노드를 우선 노드로 사용하기 위해 반환한다.

 

kernel/sched/fair.c -2/2-

        /*
         * Finding the preferred nid in a system with NUMA backplane
         * interconnect topology is more involved. The goal is to locate
         * tasks from numa_groups near each other in the system, and
         * untangle workloads from different sides of the system. This requires
         * searching down the hierarchy of node groups, recursively searching
         * inside the highest scoring group of nodes. The nodemask tricks
         * keep the complexity of the search down.
         */
        nodes = node_online_map;
        for (dist = sched_max_numa_distance; dist > LOCAL_DISTANCE; dist--) {
                unsigned long max_faults = 0;
                nodemask_t max_group = NODE_MASK_NONE;
                int a, b;

                /* Are there nodes at this distance from each other? */
                if (!find_numa_distance(dist))
                        continue;

                for_each_node_mask(a, nodes) {
                        unsigned long faults = 0;
                        nodemask_t this_group;
                        nodes_clear(this_group);

                        /* Sum group's NUMA faults; includes a==b case. */
                        for_each_node_mask(b, nodes) {
                                if (node_distance(a, b) < dist) {
                                        faults += group_faults(p, b);
                                        node_set(b, this_group);
                                        node_clear(b, nodes);
                                }
                        }

                        /* Remember the top group. */
                        if (faults > max_faults) {
                                max_faults = faults;
                                max_group = this_group;
                                /*
                                 * subtle: at the smallest distance there is
                                 * just one node left in each "group", the
                                 * winner is the preferred nid.
                                 */
                                nid = a;
                        }
                }
                /* Next round, evaluate the nodes within max_group. */
                if (!max_faults)
                        break;
                nodes = max_group;
        }
        return nid;
}
  • 코드 라인 11~18에서 누마 백플레인 노드 타입인 경우이다. 로컬을 제외한 리모트 최장거리부터 최단거리까지 1씩 줄여가며 순회하며 누마 디스턴스에 사용하지 않는 거리들은 skip 한다.
    • 예) 30, 29, 28, … 11 까지 감소하며 누마 디스턴스인 30, 25, 20, 15을 제외하고는 skip 한다.
  • 코드 라인 20~32에서 누마 온라인 노드들을 대상으로 순회하며 순회하는 노드가 다른 노드들과의 거리가 dist 보다 작을 때 태스크에 대한 그룹 faults를 누적하고, 누적한 그룹을 this_group에 마크하고, nodes에서는 제거한다.
  • 코드 라인 35~44에서 max_faults를 갱신하고, 갱신한 노드를 nid에 대입하고, 마크된 this_group을 max-group에 대입한다.
  • 코드 라인 47~49에서 max-faults가 0인 경우 함수를 빠져나가고, 존재하는 경우 nodes에 max_group을 대입하고, 다음 distance를 진행하도록 한다.
  • 코드 라인 51에서 태스크가 가장 많은 접근(max_faults)을 기록한 nid 노드를 반환한다.

 

누마 스캔 주기 증/감 갱신

update_task_scan_period()

kernel/sched/fair.c

/*
 * Increase the scan period (slow down scanning) if the majority of
 * our memory is already on our local node, or if the majority of
 * the page accesses are shared with other processes.
 * Otherwise, decrease the scan period.
 */
static void update_task_scan_period(struct task_struct *p,
                        unsigned long shared, unsigned long private)
{
        unsigned int period_slot;
        int lr_ratio, ps_ratio;
        int diff;

        unsigned long remote = p->numa_faults_locality[0];
        unsigned long local = p->numa_faults_locality[1];

        /*
         * If there were no record hinting faults then either the task is
         * completely idle or all activity is areas that are not of interest
         * to automatic numa balancing. Related to that, if there were failed
         * migration then it implies we are migrating too quickly or the local
         * node is overloaded. In either case, scan slower
         */
        if (local + shared == 0 || p->numa_faults_locality[2]) {
                p->numa_scan_period = min(p->numa_scan_period_max,
                        p->numa_scan_period << 1);

                p->mm->numa_next_scan = jiffies +
                        msecs_to_jiffies(p->numa_scan_period);

                return;
        }

        /*
         * Prepare to scale scan period relative to the current period.
         *       == NUMA_PERIOD_THRESHOLD scan period stays the same
         *       <  NUMA_PERIOD_THRESHOLD scan period decreases (scan faster)
         *       >= NUMA_PERIOD_THRESHOLD scan period increases (scan slower)
         */
        period_slot = DIV_ROUND_UP(p->numa_scan_period, NUMA_PERIOD_SLOTS);
        lr_ratio = (local * NUMA_PERIOD_SLOTS) / (local + remote);
        ps_ratio = (private * NUMA_PERIOD_SLOTS) / (private + shared);

        if (ps_ratio >= NUMA_PERIOD_THRESHOLD) {
                /*
                 * Most memory accesses are local. There is no need to
                 * do fast NUMA scanning, since memory is already local.
                 */
                int slot = ps_ratio - NUMA_PERIOD_THRESHOLD;
                if (!slot)
                        slot = 1;
                diff = slot * period_slot;
        } else if (lr_ratio >= NUMA_PERIOD_THRESHOLD) {
                /*
                 * Most memory accesses are shared with other tasks.
                 * There is no point in continuing fast NUMA scanning,
                 * since other tasks may just move the memory elsewhere.
                 */
                int slot = lr_ratio - NUMA_PERIOD_THRESHOLD;
                if (!slot)
                        slot = 1;
                diff = slot * period_slot;
        } else {
                /*
                 * Private memory faults exceed (SLOTS-THRESHOLD)/SLOTS,
                 * yet they are not on the local NUMA node. Speed up
                 * NUMA scanning to get the memory moved over.
                 */
                int ratio = max(lr_ratio, ps_ratio);
                diff = -(NUMA_PERIOD_THRESHOLD - ratio) * period_slot;
        }

        p->numa_scan_period = clamp(p->numa_scan_period + diff,
                        task_scan_min(p), task_scan_max(p));
        memset(p->numa_faults_locality, 0, sizeof(p->numa_faults_locality));
}

태스크 @p의 NUMA 스캔 주기를 증/감하여 갱신한다. 누마 로컬 또는 private 접근 비율이 스레졸드(70%) 이상인 증가되어 스캔 주기가 길어지고, 반대로 누마 리모트 또는 shared의 접근 비율이 스레졸드(70%) 이상인 경우 감소되어 스캔 주기는 짧아진다.

  • 코드 라인 8~9에서 리모트 및 로컬 누마 노드로의 접근 수를 알아온다.
  • 코드 라인 18~26에서 아직 접근된 수가 없거나 마이그레이션 실패한 경우가 있으면 누마 스캔 주기를 2배 증가시키고, 다음 스캔 시각을 결정한 후 함수를 빠져나간다.
  • 코드 라인 34에서 누마 스캔 주기를 NUMA_PERIOD_SLOTS(10) 단위로 올림 정렬한 값을 period_slot에 담는다.
  • 코드 라인 35에서 로컬/리모트 중 로컬 접근 비율을 구한다.
  • 코드 라인 36에서 private/shared 중 private 접근 비율을 구한다.
  • 코드 라인 38~65에서 누마 스캔 주기를 증감 시킬 diff 값을 다음과 같이 구한다.
    • private 비율 >= 70%일 때 초과 값을 period_slot에 곱한다. (증가)
    • local 비율 >= 70% 초과 값을 period_slot에 곱한다. (증가)
    • local 비율 또는 private 비율 중 큰 값에서 스레졸드 값을 뺀 후 period_slot에 곱한다. (음수 -> 감소)
  • 코드 라인 67~68에서 누마 스캔 주기에 diff를 반영한다.(증/감)
  • 코드 라인 69에서 numa_faults_locality[]를 0으로 클리어한다.

 


누마 우선 노드로의 마이그레이션

numa_migrate_preferred()

kernel/sched/fair.c

/* Attempt to migrate a task to a CPU on the preferred node. */
static void numa_migrate_preferred(struct task_struct *p)
{
        unsigned long interval = HZ;

        /* This task has no NUMA fault statistics yet */
        if (unlikely(p->numa_preferred_nid == NUMA_NO_NODE || !p->numa_faults))
                return;

        /* Periodically retry migrating the task to the preferred node */
        interval = min(interval, msecs_to_jiffies(p->numa_scan_period) / 16);
        p->numa_migrate_retry = jiffies + interval;

        /* Success if task is already running on preferred CPU */
        if (task_node(p) == p->numa_preferred_nid)
                return;

        /* Otherwise, try migrate to a CPU on the preferred node */
        task_numa_migrate(p);
}

누마 우선 노드로 태스크를 마이그레이션 시도한다.

  • 코드 라인 7~8에서 낮은 확률로 태스크의 우선 노드가 설정되지 않았거나 누마 밸런싱용 fault 통계가 아직 시작되지 않은 경우 함수를 빠져나간다.
  • 코드 라인 11~12에서 최대 1초 이내의 누마 스캔 주기 /16을 현재 시각에서 추가하여 태스크의 numa_migrate_retry에 대입한다.
  • 코드 라인 15~16에서 이미 태스크가 누마 우선 노드를 사용 중이면 함수를 빠져나간다.
  • 코드 라인 19에서 태스크를 마이그레이션 시도한다.

 

task_numa_migrate()

kernel/sched/fair.c -1/2-

static int task_numa_migrate(struct task_struct *p)
{
        struct task_numa_env env = {
                .p = p,

                .src_cpu = task_cpu(p),
                .src_nid = task_node(p),

                .imbalance_pct = 112,

                .best_task = NULL,
                .best_imp = 0,
                .best_cpu = -1,
        };
        unsigned long taskweight, groupweight;
        struct sched_domain *sd;
        long taskimp, groupimp;
        struct numa_group *ng;
        struct rq *best_rq;
        int nid, ret, dist;

        /*
         * Pick the lowest SD_NUMA domain, as that would have the smallest
         * imbalance and would be the first to start moving tasks about.
         *
         * And we want to avoid any moving of tasks about, as that would create
         * random movement of tasks -- counter the numa conditions we're trying
         * to satisfy here.
         */
        rcu_read_lock();
        sd = rcu_dereference(per_cpu(sd_numa, env.src_cpu));
        if (sd)
                env.imbalance_pct = 100 + (sd->imbalance_pct - 100) / 2;
        rcu_read_unlock();

        /*
         * Cpusets can break the scheduler domain tree into smaller
         * balance domains, some of which do not cross NUMA boundaries.
         * Tasks that are "trapped" in such domains cannot be migrated
         * elsewhere, so there is no point in (re)trying.
         */
        if (unlikely(!sd)) {
                sched_setnuma(p, task_node(p));
                return -EINVAL;
        }

        env.dst_nid = p->numa_preferred_nid;
        dist = env.dist = node_distance(env.src_nid, env.dst_nid);
        taskweight = task_weight(p, env.src_nid, dist);
        groupweight = group_weight(p, env.src_nid, dist);
        update_numa_stats(&env.src_stats, env.src_nid);
        taskimp = task_weight(p, env.dst_nid, dist) - taskweight;
        groupimp = group_weight(p, env.dst_nid, dist) - groupweight;
        update_numa_stats(&env.dst_stats, env.dst_nid);

        /* Try to find a spot on the preferred nid. */
        task_numa_find_cpu(&env, taskimp, groupimp);
  • 코드 라인 3~14에서 태스크의 마이그레이션을 위해 관련 함수에서 인자 전달 목적으로 사용될 구조체 내에 태스크를 소스로 구성한다.
  • 코드 라인 31~45에서 태스크의 cpu에 대한 누마 스케줄 도메인이 여부에 따라 다음과 같이 수행한다.
    • 있을 때 imbalance_pct의 100% 초과분을 절반으로 줄인다.
    • 없을 때 태스크의 누마 우선 노드만을 지정한 후 -EINVAL 값을 반환한다.
  • 코드 라인 47에서 dst_nid에 태스크의 누마 우선 노드를 지정한다.
  • 코드 라인 48~51에서 소스 노드측의 러너블 로드와 capacity를 알아온다.
  • 코드 라인 52~54에서 데스트 노드측의 러너블 로드와 capacity를 알아온다.
  • 코드 라인 57에서 데스트 노드내에서 가장 적절한 cpu를 찾는다.

 

kernel/sched/fair.c -2/2-

        /*
         * Look at other nodes in these cases:
         * - there is no space available on the preferred_nid
         * - the task is part of a numa_group that is interleaved across
         *   multiple NUMA nodes; in order to better consolidate the group,
         *   we need to check other locations.
         */
        ng = deref_curr_numa_group(p);
        if (env.best_cpu == -1 || (ng && ng->active_nodes > 1)) {
                for_each_online_node(nid) {
                        if (nid == env.src_nid || nid == p->numa_preferred_nid)
                                continue;

                        dist = node_distance(env.src_nid, env.dst_nid);
                        if (sched_numa_topology_type == NUMA_BACKPLANE &&
                                                dist != env.dist) {
                                taskweight = task_weight(p, env.src_nid, dist);
                                groupweight = group_weight(p, env.src_nid, dist);
                        }

                        /* Only consider nodes where both task and groups benefit */
                        taskimp = task_weight(p, nid, dist) - taskweight;
                        groupimp = group_weight(p, nid, dist) - groupweight;
                        if (taskimp < 0 && groupimp < 0)
                                continue;

                        env.dist = dist;
                        env.dst_nid = nid;
                        update_numa_stats(&env.dst_stats, env.dst_nid);
                        task_numa_find_cpu(&env, taskimp, groupimp);
                }
        }

        /*
         * If the task is part of a workload that spans multiple NUMA nodes,
         * and is migrating into one of the workload's active nodes, remember
         * this node as the task's preferred numa node, so the workload can
         * settle down.
         * A task that migrated to a second choice node will be better off
         * trying for a better one later. Do not set the preferred node here.
         */
        if (ng) {
                if (env.best_cpu == -1)
                        nid = env.src_nid;
                else
                        nid = cpu_to_node(env.best_cpu);

                if (nid != p->numa_preferred_nid)
                        sched_setnuma(p, nid);
        }

        /* No better CPU than the current one was found. */
        if (env.best_cpu == -1)
                return -EAGAIN;

        best_rq = cpu_rq(env.best_cpu);
        if (env.best_task == NULL) {
                ret = migrate_task_to(p, env.best_cpu);
                WRITE_ONCE(best_rq->numa_migrate_on, 0);
                if (ret != 0)
                        trace_sched_stick_numa(p, env.src_cpu, env.best_cpu);
                return ret;
        }

        ret = migrate_swap(p, env.best_task, env.best_cpu, env.src_cpu);
        WRITE_ONCE(best_rq->numa_migrate_on, 0);

        if (ret != 0)
                trace_sched_stick_numa(p, env.src_cpu, task_cpu(env.best_task));
        put_task_struct(env.best_task);
        return ret;
}
  • 코드 라인 8에서 태스크의 누마 그룹을 알아온다.
  • 코드 라인 9~12에서 best_cpu를 찾지 못하였거나 2개 이상의 active 누마 그룹이 있는 경우 모든 온라인 노드를 순회한다. 단 소스 노드와 누마 우선 노드는 skip 한다.
  • 코드 라인 14~19에서 두 소스 노드와 데스트 노드가 백플레인 타입으로 연결되었고 두 노드간의 거리가 env.dist가 아닌 경우 소스 노드에 대한 taskweight과 groupweight을 구한다.
  • 코드 라인 22~25에서 순회 중인 노드에 대한 태스크 weight과 순회 중인 노드에 대한 그룹 weight 둘 다 0보다 작은 경우는 skip 한다.
  • 코드 라인 27~30에서 순회 중인 노드의 러너블 로드와 capacity를 구한 후 idlest cpu를 찾아 env->best_cpu에 알아온다.
  • 코드 라인 42~50에서 태스크의 누마 그룹이 있는 경우 마이그레이트 할 cpu를 찾은 경우 해당 노드, 못 찾은 경우 원래 소스 노드로 태스크의 우선 노드를 결정한다.
  • 코드 라인 53~54에서 마이그레이트할 best cpu를 찾지 못한 경우 -EAGAIN을 반환한다.
  • 코드 라인 56~63에서 env.best_task가 지정되지 않은 경우 best cpu로 태스크를 마이그레이션한 후 그 결과를 갖고 함수를 빠져나간다.
  • 코드 라인 65~71에서 두 개의 태스크를 서로 교체한 후 그 결과를 갖고 함수를 빠져나간다.

 

update_numa_stats()

kernel/sched/fair.c

/*
 * XXX borrowed from update_sg_lb_stats
 */
static void update_numa_stats(struct numa_stats *ns, int nid)
{
        int cpu;

        memset(ns, 0, sizeof(*ns));
        for_each_cpu(cpu, cpumask_of_node(nid)) {
                struct rq *rq = cpu_rq(cpu);

                ns->load += cpu_runnable_load(rq);
                ns->compute_capacity += capacity_of(cpu);
        }

}

누마 stat을 갱신한다. 해당 노드의 러너블 로드와 capacity를 알아온다.

  • 코드 라인 5에서 누마 stat을 모두 0으로 클리어한다.
  • 코드 라인 6~11에서 @nid 노드에 대한 cpu들을 순회하며 러너블 로드와 capacity를 누적한다.

 

태스크를 누마 이동할 cpu 찾기

task_numa_find_cpu()

kernel/sched/fair.c

static void task_numa_find_cpu(struct task_numa_env *env,
                                long taskimp, long groupimp)
{
        long src_load, dst_load, load;
        bool maymove = false;
        int cpu;

        load = task_h_load(env->p);
        dst_load = env->dst_stats.load + load;
        src_load = env->src_stats.load - load;

        /*
         * If the improvement from just moving env->p direction is better
         * than swapping tasks around, check if a move is possible.
         */
        maymove = !load_too_imbalanced(src_load, dst_load, env);

        for_each_cpu(cpu, cpumask_of_node(env->dst_nid)) {
                /* Skip this CPU if the source task cannot migrate */
                if (!cpumask_test_cpu(cpu, env->p->cpus_ptr))
                        continue;

                env->dst_cpu = cpu;
                task_numa_compare(env, taskimp, groupimp, maymove);
        }
}

태스크를 누마 이동할 cpu를 찾아온다. cpu는 env->best_cpu에 알아오고, 교체할 태스크는 env->best_task에 알아온다.

  • 코드 라인 8~10에서 태스크가 마이그레이션된 후의 로드 값을 결정한다.
    • 마이그레이션될 데스트 노드에 태스크 로드를 추가하고,
    • 마이그레이션할 소스 노드에서는 태스크 로드를 감소시킨다.
  • 코드 라인 16에서 마이그레이션 후의 소스 노드와 데스트 노드 간의 로드가 차이가 적은지 여부를 maymove에 대입한다.
  • 코드 라인 18~25에서 데스트 노드의 cpu들을 순회하고 태스크가 지원하는 cpu에 대해서만 로드를 비교하여 idlest cpu를 찾아 env->best_cpu에 기록한다.

 

load_too_imbalanced()

kernel/sched/fair.c

static bool load_too_imbalanced(long src_load, long dst_load,
                                struct task_numa_env *env)
{
        long imb, old_imb;
        long orig_src_load, orig_dst_load;
        long src_capacity, dst_capacity;

        /*
         * The load is corrected for the CPU capacity available on each node.
         *
         * src_load        dst_load
         * ------------ vs ---------
         * src_capacity    dst_capacity
         */
        src_capacity = env->src_stats.compute_capacity;
        dst_capacity = env->dst_stats.compute_capacity;

        imb = abs(dst_load * src_capacity - src_load * dst_capacity);

        orig_src_load = env->src_stats.load;
        orig_dst_load = env->dst_stats.load;

        old_imb = abs(orig_dst_load * src_capacity - orig_src_load * dst_capacity);

        /* Would this change make things worse? */
        return (imb > old_imb);
}

태스크를 마이그레이션 했을 때의 소스 로드와 데스트 로드의 차이 값과 태스크를 마이그레이션 하기 전의 오리지날 소스 로드와 오리지날 데스트 로드의 차이를 비교한 결과를 반환한다. (1=마이그레이션 후가 더 불균형 상태, 0=마이그레이션 후 밸런스 상태)

  • 코드 라인 15~18에서 소스 로드와 데스트 로드에 노드 capacity 비율을 적용한 두 값의 차이를 imb에 대입한다.
  • 코드 라인 20~23에서 오리지날 소스 로드와 오리지날 데스트 로드에 노드 capacity 비율을 적용한 두 값의 차이를 old_imb에 대입한다.
  • 코드 라인 26에서 마이그레이션 후의 imb가 마이그레이션 전의 old_imb보다 큰 경우 오히려 더 불균형 상태로 판단되어 1을 반환하고, 그렇지 않은 경우 이미 밸런스로 판단하여 0을 반환한다.

 

task_numa_compare()

kernel/sched/fair.c -1/2-

/*
 * This checks if the overall compute and NUMA accesses of the system would
 * be improved if the source tasks was migrated to the target dst_cpu taking
 * into account that it might be best if task running on the dst_cpu should
 * be exchanged with the source task
 */
static void task_numa_compare(struct task_numa_env *env,
                              long taskimp, long groupimp, bool maymove)
{
        struct numa_group *cur_ng, *p_ng = deref_curr_numa_group(env->p);
        struct rq *dst_rq = cpu_rq(env->dst_cpu);
        long imp = p_ng ? groupimp : taskimp;
        struct task_struct *cur;
        long src_load, dst_load;
        int dist = env->dist;
        long moveimp = imp;
        long load;

        if (READ_ONCE(dst_rq->numa_migrate_on))
                return;

        rcu_read_lock();
        cur = rcu_dereference(dst_rq->curr);
        if (cur && ((cur->flags & PF_EXITING) || is_idle_task(cur)))
                cur = NULL;

        /*
         * Because we have preemption enabled we can get migrated around and
         * end try selecting ourselves (current == env->p) as a swap candidate.
         */
        if (cur == env->p)
                goto unlock;

        if (!cur) {
                if (maymove && moveimp >= env->best_imp)
                        goto assign;
                else
                        goto unlock;
        }

        /*
         * "imp" is the fault differential for the source task between the
         * source and destination node. Calculate the total differential for
         * the source task and potential destination task. The more negative
         * the value is, the more remote accesses that would be expected to
         * be incurred if the tasks were swapped.
         */
        /* Skip this swap candidate if cannot move to the source cpu */
        if (!cpumask_test_cpu(env->src_cpu, cur->cpus_ptr))
                goto unlock;

        /*
         * If dst and source tasks are in the same NUMA group, or not
         * in any group then look only at task weights.
         */
        cur_ng = rcu_dereference(cur->numa_group);
        if (cur_ng == p_ng) {
                imp = taskimp + task_weight(cur, env->src_nid, dist) -
                      task_weight(cur, env->dst_nid, dist);
                /*
                 * Add some hysteresis to prevent swapping the
                 * tasks within a group over tiny differences.
                 */
                if (cur_ng)
                        imp -= imp / 16;
        } else {
                /*
                 * Compare the group weights. If a task is all by itself
                 * (not part of a group), use the task weight instead.
                 */
                if (cur_ng && p_ng)
                        imp += group_weight(cur, env->src_nid, dist) -
                               group_weight(cur, env->dst_nid, dist);
                else
                        imp += task_weight(cur, env->src_nid, dist) -
                               task_weight(cur, env->dst_nid, dist);
        }

        if (maymove && moveimp > imp && moveimp > env->best_imp) {
                imp = moveimp;
                cur = NULL;
                goto assign;
        }

        /*
         * If the NUMA importance is less than SMALLIMP,
         * task migration might only result in ping pong
         * of tasks and also hurt performance due to cache
         * misses.
         */
        if (imp < SMALLIMP || imp <= env->best_imp + SMALLIMP / 2)
                goto unlock;
  • 코드 라인 3~10에서 env->p 태스크의 누마 그룹이 있는 경우 @groupimp, 없는 경우 @taskimp를 imp 및 moveimp에 대입한다.
  • 코드 라인 13~14에서 누마 마이그레이션이 진행 중인 경우 함수를 빠져나간다.
  • 코드 라인 17~19에서 dst 런큐에서 동작 중인 태스크가 이미 종료 중이거나 idle 상태인 경우 cur에 null을 대입한다.
  • 코드 라인 25~26에서 cur가 env->p와 동일한 경우 unlock 레이블로 이동한다.
  • 코드 라인 28~33에서 cur가 없는 경우 @maymove 이면서 moveimp 가 env->best_imp 이상인 경우 assign 레이블로 이동하고, 그렇지 않은 경우 unlock 레이블로 이동한다.
  • 코드 라인 43~44에서 src cpu가 cur 태스크가 허용하는 cpu에 없는 경우 unlock 레이블로 이동한다.
  • 코드 라인 50~71에서 cur 태스크와 env->p가 같은 누마 그룹에 있을 때와 그렇지 않을 때의 imp 값은 다음과 같이 산출한다.
    • 같은 경우 @task_imp + 소스 노드에서의 cur 태스크 weight – 데스트 노드에서의 cur 태스크 비중을 구한 후 1/16 만큼 감소시킨다.
    • 다른 경우 소스 노드에서의 cur 그룹 weight – 데스트 노드에서의 cur 그룹 weight을 imp에 추가한다. 만일 하나라도 그룹이 없으면 소스 노드에서의 cur 태스크 weight – 데스트 노드에서의 cur 태스크 weight을 imp에 추가한다.
  • 코드 라인 73~77에서 @maymove이고 moveimp가 imp나 env->best_imp보다 더 큰 경우 imp에 moveimp를 대입하고, cur에 null을 대입한 후 assign 레이블로 이동한다.
  • 코드 라인 85~86에서 마이그레이션으로 서로 ping-pong 하지 못하게 누마 importance 값이 너무 작은 경우  unlock 레이블로 이동한다.

 

kernel/sched/fair.c -2/2-

        /*
         * In the overloaded case, try and keep the load balanced.
         */
        load = task_h_load(env->p) - task_h_load(cur);
        if (!load)
                goto assign;

        dst_load = env->dst_stats.load + load;
        src_load = env->src_stats.load - load;

        if (load_too_imbalanced(src_load, dst_load, env))
                goto unlock;

assign:
        /*
         * One idle CPU per node is evaluated for a task numa move.
         * Call select_idle_sibling to maybe find a better one.
         */
        if (!cur) {
                /*
                 * select_idle_siblings() uses an per-CPU cpumask that
                 * can be used from IRQ context.
                 */
                local_irq_disable();
                env->dst_cpu = select_idle_sibling(env->p, env->src_cpu,
                                                   env->dst_cpu);
                local_irq_enable();
        }

        task_numa_assign(env, cur, imp);
unlock:
        rcu_read_unlock();
}
  • 코드 라인 4~6에서 env->p 태스크의 로드에서 cur 태스크의 로드를 뺀 로드를 load에 대입하고, 이 값이 0인 경우 assign 레이블로 이동한다.
  • 코드 라인 8~12에서 태스크를 마이그레이션 후에 로드가 더 불균형해지는 경우 마이그레이션을 포기하도록 unlock 레이블로 이동한다.
  • 코드 라인 14~28에서 assign: 레이블이다. cur가 없는 경우 env->dst_cpu에 idle cpu를 찾아오되 env->dst_cpu, env->src_cpu 및 캐시 공유 도메인 내 cpu들 순으로 처리한다.
  • 코드 라인 30에서 누마 best cpu, task 및 imp를 지정한다.
  • 코드 라인 31~32에서 unlock: 레이블이다. rcu read 락을 해제한 후 함수를 빠져나간다.

 

task_numa_assign()

kernel/sched/fair.c

static void task_numa_assign(struct task_numa_env *env,
                             struct task_struct *p, long imp)
{
        struct rq *rq = cpu_rq(env->dst_cpu);

        /* Bail out if run-queue part of active NUMA balance. */
        if (xchg(&rq->numa_migrate_on, 1))
                return;

        /*
         * Clear previous best_cpu/rq numa-migrate flag, since task now
         * found a better CPU to move/swap.
         */
        if (env->best_cpu != -1) {
                rq = cpu_rq(env->best_cpu);
                WRITE_ONCE(rq->numa_migrate_on, 0);
        }

        if (env->best_task)
                put_task_struct(env->best_task);
        if (p)
                get_task_struct(p);

        env->best_task = p;
        env->best_imp = imp;
        env->best_cpu = env->dst_cpu;
}

누마 마이그레이션용 best cpu, task 및 imp를 지정한다.

  • 코드 라인 4~8에서 dst_cpu가 이미 누마 마이그레이션이 진행 중인 경우 함수를 빠져나간다.
  • 코드 라인 14~17에서 best_cpu를 처음 결정하는 경우 누마 마이그레이션 진행중 표시를 제거한다.
  • 코드 라인 19~20에서 기존에 설정되었던 best_task의 참조는 1 감소시킨다.
  • 코드 라인 21~24에서 태스크 @p를 best_task로 지정한다.
  • 코드 라인 25~26에서 @imp를 best_imp로 지정하고, dst_cpu를 best_cpu로 지정한다.

 


구조체

task_struct 구조체 (NUMA 밸런싱 부분)

include/linux/sched.h

struct task_struct {
...
#ifdef CONFIG_NUMA_BALANCING
        int                             numa_scan_seq;
        unsigned int                    numa_scan_period;
        unsigned int                    numa_scan_period_max;
        int                             numa_preferred_nid;
        unsigned long                   numa_migrate_retry;
        /* Migration stamp: */
        u64                             node_stamp;
        u64                             last_task_numa_placement;
        u64                             last_sum_exec_runtime;
        struct callback_head            numa_work;

        /*
         * This pointer is only modified for current in syscall and
         * pagefault context (and for tasks being destroyed), so it can be read
         * from any of the following contexts:
         *  - RCU read-side critical section
         *  - current->numa_group from everywhere
         *  - task's runqueue locked, task not running
         */
        struct numa_group __rcu         *numa_group;

        /*
         * numa_faults is an array split into four regions:
         * faults_memory, faults_cpu, faults_memory_buffer, faults_cpu_buffer
         * in this precise order.
         *
         * faults_memory: Exponential decaying average of faults on a per-node
         * basis. Scheduling placement decisions are made based on these
         * counts. The values remain static for the duration of a PTE scan.
         * faults_cpu: Track the nodes the process was running on when a NUMA
         * hinting fault was incurred.
         * faults_memory_buffer and faults_cpu_buffer: Record faults per node
         * during the current scan window. When the scan completes, the counts
         * in faults_memory and faults_cpu decay and these values are copied.
         */
        unsigned long                   *numa_faults;
        unsigned long                   total_numa_faults;

        /*
         * numa_faults_locality tracks if faults recorded during the last
         * scan window were remote/local or failed to migrate. The task scan
         * period is adapted based on the locality of the faults with different
         * weights depending on whether they were shared or private faults
         */
        unsigned long                   numa_faults_locality[3];

        unsigned long                   numa_pages_migrated;
#endif /* CONFIG_NUMA_BALANCING */
...
}
  • numa_scan_seq
    • 누마 스캔 주기마다 증가되는 시퀀스
  • numa_scan_period
    • 누마 스캔 주기
  • numa_scan_period_max
    • 누마 스캔 최대 주기
  • numa_preferred_nid
    • 누마 우선 노드
  • numa_migrate_retry
    • 누마 migration 재시도 수
  • node_stamp
    • 다음 누마 스캔 시각이 담긴다.
  • last_task_numa_placement
    • 누마 placement 지난 갱신 시각
  • last_sum_exec_runtime
    • 누마 placement용 누적 실행 시간
  • numa_work
    • 누마 밸런싱 work이 담기는 callback head
  • *numa_group
    • 누마 그룹 구조체를 가리킨다.
  • *numa_faults
    • 다음 4 종류의 영역이 있고, 각각 노드별 및 private/shared 별 누마 faults 값이 담긴다. (예: 6 개의노드인 경우 배열은 4 * 6 * 2 = 48개가 할당된다)
      • faults_memory
        • 메모리 노드에 대한 누마 faults의 exponential decay 된 값이 누적된다.
      • faults_cpu
        • cpu 노드에 대한 누마 faults의 exponential decay 된 값이 누적된다.
      • faults_memory_buffer
        • 메모리 노드에 대한 누마 faults가 누적되고, 스캔 윈도우 주기마다 클리어된다.
      • faults_cpu_buffer
        • cpu 노드에 대한 누마 faults가 누적되고, 스캔 윈도우 주기마다 클리어된다.
  • total_numa_faults
    • 누마 faults의 exponential decay 된 값이 누적된다.
  • numa_faults_locality[3]
    • 다음과 같이 노드 지역성별로 numa faults 값이 담기며, 누마 스캔 주기마다 클리어된다.
      • remote
      • local
      • failed to migrate
  • numa_pages_migrated
    • 누마 마이그레이션 페이지 수

 

numa_group 구조체

kernel/sched/fair.c

struct numa_group {
        refcount_t refcount;

        spinlock_t lock; /* nr_tasks, tasks */
        int nr_tasks;
        pid_t gid;
        int active_nodes;

        struct rcu_head rcu;
        unsigned long total_faults;
        unsigned long max_faults_cpu;
        /*
         * Faults_cpu is used to decide whether memory should move
         * towards the CPU. As a consequence, these stats are weighted
         * more by CPU use than by memory faults.
         */
        unsigned long *faults_cpu;
        unsigned long faults[0];
};
  • refcount
    • 태스크들의 누마 그룹에 대한 참조 카운터
  • nr_tasks
    • 이 누마 그룹에 조인한 태스크 수
  • gid
    • 그룹 id
  • active_nodes
    • 페이지가 일정 부분 액세스를 하는 노드 수로 노드들 중 faults 수가 max_faults의 1/3 이상인 노드 수이다.
  • rcu
  • total_faults
    • 이 그룹의 전체 numa faults
    • 태스크의 numa 밸런싱 참여 시 추가되고, 태스크가 종료될 때 태스크의 누마 faults가 감소한다.
  • max_faults_cpu
  • *faults_cpu
  • faults[]
    • 누마 faults로 태스크에 저장되는 것과 동일하게 4 종류의 영역에 각각 노드별 및 private/shared 별로 numa faults 값이 담긴다.

 

numa_stats 구조체

kernel/sched/fair.c

/* Cached statistics for all CPUs within a node */
struct numa_stats {
        unsigned long load;

        /* Total compute capacity of CPUs on a node */
        unsigned long compute_capacity;
};
  • load
    • 노드 내 cpu들의 러너블 로드 합계
  • compute_capacity
    • 노드 내 cpu들의 scaled cpu capactiy 합계

 

task_numa_env 구조체

kernel/sched/fair.c

struct task_numa_env {
        struct task_struct *p;

        int src_cpu, src_nid;
        int dst_cpu, dst_nid;

        struct numa_stats src_stats, dst_stats;

        int imbalance_pct;
        int dist;

        struct task_struct *best_task;
        long best_imp;
        int best_cpu;
};
  • *p
    • 마이그레이션 할 태스크
  • src_cpu
    • 소스 cpu
  • src_nid
    • 소느 노드 id
  • dst_cpu
    • 데스트(목적지) cpu
  • dst_nid
    • 데스트(목적지) 노드 id
  • src_stats
    • 소스 노드의 러너블 로드와 scaled cpu capacity가 담긴다.
  • dst_stats
    • 데스트(목적지) 노드의 러너블 로드와 scaled cpu capacity가 담긴다.
  • imbalance_pct
    • 불균형 스레졸드 값(100 이상 = 100% 이상)
  • dist
    • 노드 distance
  • *best_task
    • swap할 best 태스크
  • best_imp
    • 중요(importance)도
  • best_cpu
    • 마이그레이션할 최적의 cpu

 

참고