Gentoo 之 WALT 负载计算

WALT（Window Assisted Load Tracking窗口辅助负载跟踪算法）的核心算法思想是：以时间窗口长度window为单位，跟踪CPU使用情况，用前面N个窗口的CPU使用情况预测当前窗口的CPU需求。窗口默认长度是20ms，walt_ravg_window = (20000000 / TICK_NSEC) * TICK_NSEC，进程负载计算默认是5个历史窗口(#define RAVG_HIST_SIZE_MAX 5)，CPU负载计算只用一个历史窗口。要理解WALT算法需要理解几个概念：WALT时间、cpu_scale、freq_scale。

WALT时间是什么呢，是进程占用CPU时间吗？想象一下，有两个进程，在一个时间窗口内，A进程在2.6G频率上运行了5ms，B进程在小核500M频率上运行了5ms。如果仅考虑CPU占用时间，那么它们的负载是相同的，这显然与实际情况不符。所以WALT时间，不仅要考虑CPU占用时间，还要考虑所在CPU的运算能力、运行频率。函数scale_exec_time()用于计算WALT时间，参数delta是CPU运行时间，rq是进程所在运行队列（与CPU对应），SCHED_CAPACITY_SHIFT是10。

static u64 scale_exec_time(u64 delta, struct rq *rq)
{
    unsigned long capcurr = capacity_curr_of(cpu_of(rq));
 
    return (delta * capcurr) >> SCHED_CAPACITY_SHIFT;
}
 
unsigned long capacity_curr_of(int cpu)
{
    return cpu_rq(cpu)->cpu_capacity_orig *
           arch_scale_freq_capacity(NULL, cpu)
           >> SCHED_CAPACITY_SHIFT;
} 

capacity_curr_of()中cpu_capacity_orig的值最终来源于per_cpu变量cpu_scale。

#define arch_scale_cpu_capacity scale_cpu_capacity
static void update_cpu_capacity(struct sched_domain *sd, int cpu)
{
    unsigned long capacity = arch_scale_cpu_capacity(sd, cpu);
    struct sched_group *sdg = sd->groups;
    struct max_cpu_capacity *mcc;
    unsigned long max_capacity;
    int max_cap_cpu;
    unsigned long flags;
 
    cpu_rq(cpu)->cpu_capacity_orig = capacity;
    ...............................................................
}
unsigned long scale_cpu_capacity(struct sched_domain *sd, int cpu)
{
    return per_cpu(cpu_scale, cpu);
}

capacity_curr_of()中arch_scale_freq_capacity()最终是获取的per_cpu变量freq_scale。

#define arch_scale_freq_capacity cpufreq_scale_freq_capacity
unsigned long cpufreq_scale_freq_capacity(struct sched_domain *sd, int cpu)
{
    return per_cpu(freq_scale, cpu);
}

上面计算WALT时间的代码，可以简化为如下的运算公式：

cpu_scale是当前CPU运算能力尺度化。市面上有各种各样的CPU，它们的运算能力各不相同，同一系列的CPU也会迭代升级运算能力，如果以CPU实际运算能力为参数，很难做到算法的统一。内核用CPU运算能力尺度化来解决该问题，定义系统中最高运算能力核的cpu_scale为1024，其它核的cpu_scale为该(CPU运算能力/最大核运算能力)*1024。CPU各个核的cpu_scale都由SOC厂商给出，MTK平台可以cat各cpu目录下cpu_capacity节点查看cpu_scale。

freq_scale是某CPU当前频率运算能力的瓷都化，系统定义当前核最高频率运行时的freq_scale为1024，其它频率的freq_scale为当前频率运算能力/最高频率运算能力*1024。为什么用频率的运算能力比，而不是频率比呢？是因为有些厂商的CPU是CONFIG_NONLINER_FREQ_CTL类型的，它的运算能力与频率不是正比关系。例如MTK的某些SOC就是这样的芯片，它的运算能力与频率不成正比，只能查表来看某频点运算能力。

综上，我们可以把WALT时间的运算公式做如下表示：

从上面的公式可以看出，进程只有在最大核的最高频点上运行时，其CPU占用时间才会等于WALT时间，其它情况WALT时间都是CPU占用时间按一定比例缩短的结果。

1.进程负载计算

进程的task_struct中有一个ravg类型的变量用于保存WALT相关的信息。其中mark_start是上一次统计的时间，sum指进程在当前窗口已经运行的WALT时间，数组sum_history[RAVG_HIST_SIZE_MAX]保存进程在前5个历史窗口期内的WALT时间，demand是由sum_history[]历史数据推算出的值。

struct ravg {
    u64 mark_start;
    u32 sum, demand;
    u32 sum_history[RAVG_HIST_SIZE_MAX];
    u32 curr_window, prev_window;
    u16 active_windows;
};

在进程切换等情况下，会统计WALT时间，有三种情况。情况一，如果当前时间(wallclock)与上次统计时间(mark_start)在一个时间窗口内，只需要将wallclock - mark_start转换为WALT时间后累加到ravg.sum即可。情况二，如果当前时间(wallclock)与上次统计时间(mark_start)跨了一个窗口，首先计算mark_start到当前窗口起始位置这部分WALT时间，并累加到ravg.sum后调用update_history()，将ravg.sum存入历史窗口。然后计算当前窗口起始时间到现在(wallclock)的这部分WALT时间，并赋值到ravg.sum。情况三，如果当前时间(wallclock)与上次统计时间(mark_start)跨了多个窗口，首先计算mark_start到它下一个窗口起始位置这部分WALT时间，并累加到ravg.sum后调用update_history()，将ravg.sum存入历史窗口。然后计算中间跨过窗口的WALT时间并更新到历史窗口中，最后计算当前窗口起始时间到现在(wallclock)的这部分WALT时间，并赋值到ravg.sum。

//进程切换时更新负载
static void __sched notrace __schedule(bool preempt)
{
    struct task_struct *prev, *next;
    unsigned long *switch_count;
    struct pin_cookie cookie;
    struct rq *rq;
    int cpu;
    u64 wallclock;
    ................................................................
    next = pick_next_task(rq, prev, cookie);
    wallclock = walt_ktime_clock();
    walt_update_task_ravg(prev, rq, PUT_PREV_TASK, wallclock, 0);
    walt_update_task_ravg(next, rq, PICK_NEXT_TASK, wallclock, 0);
    clear_tsk_need_resched(prev);
    clear_preempt_need_resched();
    ................................................................
}
 
void walt_update_task_ravg(struct task_struct *p, struct rq *rq,
         int event, u64 wallclock, u64 irqtime)
{
    if (walt_disabled || !rq->window_start)
        return;
 
    lockdep_assert_held(&rq->lock);
    //更新窗口起始位置
    update_window_start(rq, wallclock);
 
    if (!p->ravg.mark_start)
        goto done;
    //更新进程负载
    update_task_demand(p, rq, event, wallclock);
    update_cpu_busy_time(p, rq, event, wallclock, irqtime);
 
done:
    trace_walt_update_task_ravg(p, rq, event, wallclock, irqtime);
 
    p->ravg.mark_start = wallclock;
}
 
//更新窗口起始位置
static void update_window_start(struct rq *rq, u64 wallclock)
{
    s64 delta;
    int nr_windows;
 
    delta = wallclock - rq->window_start;
    ..............................................................
    if (delta < walt_ravg_window)
        return;
 
    nr_windows = div64_u64(delta, walt_ravg_window);
    rq->window_start += (u64)nr_windows * (u64)walt_ravg_window;
 
    rq->cum_window_demand = rq->cumulative_runnable_avg;
}
 
static void update_task_demand(struct task_struct *p, struct rq *rq,
         int event, u64 wallclock)
{
    u64 mark_start = p->ravg.mark_start;
    u64 delta, window_start = rq->window_start;
    int new_window, nr_full_windows;
    u32 window_size = walt_ravg_window;
 
    new_window = mark_start < window_start;
    ................................................................
    //情况一
    if (!new_window) {
        /* The simple case - busy time contained within the existing
         * window. */
        add_to_task_demand(rq, p, wallclock - mark_start);
        return;
    }
    //情况二、三代码相同，只是情况二nr_full_windows为0
    delta = window_start - mark_start;
    nr_full_windows = div64_u64(delta, window_size);
    window_start -= (u64)nr_full_windows * (u64)window_size;
    //计算mark_start到它下一个窗口起始位置之间的WALT时间
    add_to_task_demand(rq, p, window_start - mark_start);
 
    /* Push new sample(s) into task's demand history */
    update_history(rq, p, p->ravg.sum, 1, event);
    //计算中间跨越窗口的WALT时间
    if (nr_full_windows)
        update_history(rq, p, scale_exec_time(window_size, rq),
                   nr_full_windows, event);
 
    /* Roll window_start back to current to process any remainder
     * in current window. */
    window_start += (u64)nr_full_windows * (u64)window_size;
 
    /* 计算当前窗口起始时间到现在之间的WALT时间 */
    mark_start = window_start;
    add_to_task_demand(rq, p, wallclock - mark_start);
}

demand值是在update_history()中更新的，有四种策略可选：WINDOW_STATS_RECENT，用本次更新进来的值；WINDOW_STATS_MAX，用所有历史记录中的最大值；WINDOW_STATS_AVG，用历史记录中的平均值；WINDOW_STATS_MAX_RECENT_AVG，本次更新进来的值与历史平均值中较大的那个。

#define WINDOW_STATS_RECENT        0
#define WINDOW_STATS_MAX        1
#define WINDOW_STATS_MAX_RECENT_AVG    2
#define WINDOW_STATS_AVG        3
#define WINDOW_STATS_INVALID_POLICY    4
 
static void update_history(struct rq *rq, struct task_struct *p,
             u32 runtime, int samples, int event)
{
    u32 *hist = &p->ravg.sum_history[0];
    int ridx, widx;
    u32 max = 0, avg, demand;
    u64 sum = 0;
 
    /* Ignore windows where task had no activity */
    if (!runtime || is_idle_task(p) || exiting_task(p) || !samples)
            goto done;
 
    /* Push new 'runtime' value onto stack */
    widx = walt_ravg_hist_size - 1;
    ridx = widx - samples;
    for (; ridx >= 0; --widx, --ridx) {
        hist[widx] = hist[ridx];
        sum += hist[widx];
        if (hist[widx] > max)
            max = hist[widx];
    }
 
    for (widx = 0; widx < samples && widx < walt_ravg_hist_size; widx++) {
        hist[widx] = runtime;
        sum += hist[widx];
        if (hist[widx] > max)
            max = hist[widx];
    }
 
    p->ravg.sum = 0;
 
    if (walt_window_stats_policy == WINDOW_STATS_RECENT) {
        demand = runtime;
    } else if (walt_window_stats_policy == WINDOW_STATS_MAX) {
        demand = max;
    } else {
        avg = div64_u64(sum, walt_ravg_hist_size);
        if (walt_window_stats_policy == WINDOW_STATS_AVG)
            demand = avg;
        else
            demand = max(avg, runtime);
    }
    ....................................................................
    if (!task_has_dl_policy(p) || !p->dl.dl_throttled) {
        if (task_on_rq_queued(p))
            fixup_cumulative_runnable_avg(rq, p, demand);
        else if (rq->curr == p)
            fixup_cum_window_demand(rq, demand);
    }
 
    p->ravg.demand = demand;
    ....................................................................
}

进程负载的计算公式如下，可以看出1024就是满负载时的值，进程满负载必须满足：在整个时间窗口内都处于运行状态，并且所在核是大核，运行频率是大核最高频率。

static inline unsigned long task_util(struct task_struct *p)
{
#ifdef CONFIG_SCHED_WALT
    if (!walt_disabled && (sysctl_sched_use_walt_task_util ||
                p->prio < sched_use_walt_nice)) {
        unsigned long demand = p->ravg.demand;
        return (demand << SCHED_CAPACITY_SHIFT) / walt_ravg_window;
    }
#endif
    return p->se.avg.util_avg;
}

2.CPU负载计算

CPU负载计算是在update_cpu_busy_time()中完成的，计算方法与进程负载类似。不同的是，CPU负载计算只用了一个历史窗口，就是运行队列中的prev_runnable_sum。

static inline unsigned long cpu_util_freq(int cpu)
{
    unsigned long util = cpu_rq(cpu)->cfs.avg.util_avg;
    unsigned long capacity = capacity_orig_of(cpu);
 
#ifdef CONFIG_SCHED_WALT
    if (!walt_disabled && sysctl_sched_use_walt_cpu_util)
        util = div64_u64(cpu_rq(cpu)->prev_runnable_sum,
                walt_ravg_window >> SCHED_CAPACITY_SHIFT);
#endif
    return (util >= capacity) ? capacity : util;
}