Gentoo 之 WALT负载计算源码分析

dummy@example.com (batsom) — Wed, 27 Mar 2024 13:16:17 +0000

一、WALT简介

WALT(Windows-Assist Load Tracing)，从字面意思来看，是以window作为辅助项来跟踪cpu load，用来表现cpu当前的loading情况，用于后续任务调度、迁移、负载均衡等功能。在 load 的基础上，添加对于demand的记录用于之后的预测。只统计runable和running time。
WALT由Qcom研发，主要用于移动设备对性能功耗要求比较高的场景，在与用户交互时需要尽快响应，要能及时反应负载的增加和减少以驱动频点及时的变化。当前的PELT负载跟踪算法更主要的是体现负载的连续性，对于突变性质的负载的反应不是很友好，负载上升慢，下降也慢。
打开 CONFIG_SCHED_WALT 使能此feature。
辅助计算项 window 的划分方法是将系统自启动开始以一定时间作为一个周期，分别统计不同周期内 Task 的 Loading 情况，并将其更新到Runqueue中；目前 Kernel 中是设置的一个 window 的大小是20ms，统计 5 个window内的Loading情况，当然，这也可以根据具体的项目需求进行配置。

二、相关数据结构

(1) 嵌入在 task_struct 中的 walt_task_struct

/*
 * 'mark_start' 标记窗口内事件的开始（任务唤醒、任务开始执行、任务被抢占）
 * 'sum' 表示任务在当前窗口内的可运行程度。它包含运行时间和等待时间，并按频率进行缩放。//就是在当前窗口的运行时间吧
 * 'sum_history' 跟踪在之前的 RAVG_HIST_SIZE 窗口中看到的 'sum' 的历史记录。任务完全休眠的窗口将被忽略。
 * 'demand' 表示在以前的 sysctl_sched_ravg_hist_size 窗口中看到的最大总和(根据window_policy选的)。 'demand'可以为任务驱动频率的改变。#######
 * 'curr_window_cpu' 代表任务对当前窗口各CPU上cpu繁忙时间的贡献
 * 'prev_window_cpu' 表示任务对前一个窗口中各个 CPU 上的 cpu 繁忙时间的贡献
 * 'curr_window' 表示 curr_window_cpu 中所有条目的总和
 * 'prev_window' 代表 prev_window_cpu 中所有条目的总和
 * 'pred_demand' 代表任务当前预测的cpu繁忙时间
 * 'busy_buckets' 将历史繁忙时间分组到用于预测的不同桶中
 * 'demand_scaled' 表示任务的需求缩放到 1024 //就是上面demand成员缩放到1024
 */
struct walt_task_struct {
    u64        mark_start;
    u32        sum, demand; //sum在 add_to_task_demand 中更新
    u32        coloc_demand; //存的是5个历史窗口的平均值
    u32        sum_history[RAVG_HIST_SIZE_MAX]; 
    u32        *curr_window_cpu, *prev_window_cpu; //这个是per-cpu的
    u32        curr_window, prev_window;
    u32        pred_demand;
    u8        busy_buckets[NUM_BUSY_BUCKETS]; //10个
    u16        demand_scaled;
    u16        pred_demand_scaled;
    u64        active_time; //is_new_task中判断此值是小于100ms就认为是新任务，rollover_task_window是唯一更新位置
    u32        unfilter; //update_history中对其进行赋值，colocate中选核时，是否需要跳过小核判断了它
    u64        cpu_cycles;
    ...
}

(2) 嵌入在 rq 中的 walt_rq

struct walt_rq {
    ...
    struct walt_sched_stats walt_stats;
    u64            window_start;
    u32            prev_window_size;
    u64            task_exec_scale; //walt_sched_init_rq中初始化为1024
    u64            curr_runnable_sum;
    u64            prev_runnable_sum;
    u64            nt_curr_runnable_sum;
    u64            nt_prev_runnable_sum; //nt 应该是walt认为的new task的意思
    u64            cum_window_demand_scaled;
    struct group_cpu_time    grp_time;
    /*
     * #define DECLARE_BITMAP_ARRAY(name, nr, bits) unsigned long name[nr][BITS_TO_LONGS(bits)]
     * unsigned long top_tasks_bitmap[2][BITS_TO_LONGS(1000)]; //只跟踪curr和prev两个窗口的情况。
     */
    DECLARE_BITMAP_ARRAY(top_tasks_bitmap, NUM_TRACKED_WINDOWS, NUM_LOAD_INDICES);
    u8            *top_tasks[NUM_TRACKED_WINDOWS]; //2 指针数组
    u8            curr_table; //只使用两个window进行跟踪，标识哪个是curr的，curr和prev构成一个环形数组，不停翻转
    int            prev_top; //应该是rq->wrq.top_tasks[]中前一个窗最大值的下标
    int            curr_top; //是rq->wrq.top_tasks[]中当前窗最大值的下标
    u64            cycles;
    ...
};

struct walt_sched_stats {
    int nr_big_tasks;
    u64 cumulative_runnable_avg_scaled; //只统计runnable任务的，在update_window_start中赋值给rq->wrq.cum_window_demand_scaled
    u64 pred_demands_sum_scaled;
    unsigned int nr_rtg_high_prio_tasks;
};

三、负载计算函数

1. walt算法负载计算入口函数

 /* event 取 TASK_UPDATE 等，由于每个tick中断中都会调度，一般两次执行统计的 wc-ms 一般不会超过4ms */
void walt_update_task_ravg(struct task_struct *p, struct rq *rq, int event, u64 wallclock, u64 irqtime) //walt.c
{
    u64 old_window_start;

    /* 还没初始化或时间没更新，直接返回 */
    if (!rq->wrq.window_start || p->wts.mark_start == wallclock)
        return;

    lockdep_assert_held(&rq->lock);

    /* 更新ws，返回最新的ws */
    old_window_start = update_window_start(rq, wallclock, event);

    /* 对应还没初始化的情况, ws是per-rq的，ms是per-task的，wc是全局的 */
    if (!p->wts.mark_start) {
        update_task_cpu_cycles(p, cpu_of(rq), wallclock);
        goto done;
    }
    /*更新 rq->wrq.task_exec_scale 和 p->wts.cpu_cycles = cur_cycles; */
    update_task_rq_cpu_cycles(p, rq, event, wallclock, irqtime);

    /*更新任务的负载和历史记录，返回 wc-ms 的差值，也就是距离上次统计任务运行的时间值 */
    update_task_demand(p, rq, event, wallclock);

    /*更新任务和rq的window相关统计信息，记录per-rq的prev和curr两个窗口内任务负载分布情况 */
    update_cpu_busy_time(p, rq, event, wallclock, irqtime);

    /*更新预测需求*/
    update_task_pred_demand(rq, p, event);

    if (event == PUT_PREV_TASK && p->state) {
        p->wts.iowaited = p->in_iowait;
    }

    trace_sched_update_task_ravg(p, rq, event, wallclock, irqtime, &rq->wrq.grp_time);

    trace_sched_update_task_ravg_mini(p, rq, event, wallclock, irqtime, &rq->wrq.grp_time);

done:
    /* 更新per-task的 ms，ms是在动态变化的 */
    p->wts.mark_start = wallclock;

    /*构成一个内核线程，每个窗口执行一次*/
    run_walt_irq_work(old_window_start, rq);
}

此函数中的两个trace解析：
(1) trace_sched_update_task_ravg(p, rq, event, wallclock, irqtime, &rq->wrq.grp_time);

参数原型：
(struct task_struct *p, struct rq *rq, enum task_event evt, u64 wallclock, u64 irqtime, struct group_cpu_time *cpu_time)

打印内容：

-0     [004] d..2 50167.767150: sched_update_task_ravg: wc 50167994699141 ws 50167988000001 delta 6699140
event PICK_NEXT_TASK cpu 4 cur_freq 434 cur_pid 0 task 17043 (kworker/u16:5) ms 50167994687631 delta 11510 
demand 3340045 coloc_demand: 1315008 sum 1235016 irqtime 0 pred_demand 3340045 rq_cs 1112353 rq_ps 4085339 
cur_window 930130 (0 136431 573963 0 219736 0 0 0 ) prev_window 2138941 (222138 156646 973556 0 219811 566790 0 0 ) 
nt_cs 2513 nt_ps 20395 active_time 100000000 grp_cs 0 grp_ps 1691783, grp_nt_cs 0, grp_nt_ps: 0 curr_top 58 prev_top 13

字段解析：
wc：为参数4 wallclock;
ws: 为 window_start，取自 rq->wrq.window_start;
delta：取自 wallclock - rq->wrq.window_start 的差值。
event：task_event_names[参数3], 字符串表示的事件类型
cpu：取自 rq->cpu
cur_freq：取自 rq->wrq.task_exec_scale，update_task_rq_cpu_cycles()中，若不使用 use_cycle_counter，赋值为 cpu_capaticy * (freq / maxfreq)
cur_pid: 取自 rq->curr->pid
task：取自参数1 p 的 p->pid
kworker/u16:5：取自参数1 p 的 p->comm
ms：是 mark_start 取自 p->wts.mark_start
delta：打印中有两个同名的delta，这是第二个，取自 wallclock - p->wts.mark_start
demand：取自 p->wts.demand，单位是ns，就是根据 p->wts.sum 取平均或和最近窗口两者之间的最大值
coloc_demand：取自 p->wts.coloc_demand
sum：取自 p->wts.sum，表示最近一个窗口运行时间之和，单位ns，在将其更新到history数组后，清0.
irqtime：取自参数4
pred_demand：取自 p->wts.pred_demand
rq_cs：取自 rq->wrq.curr_runnable_sum 表示
rq_ps：取自 rq->wrq.prev_runnable_sum 表示
cur_window：取自 p->wts.curr_window，表示任务在当前窗口中所有cpu上的运行时间之和，是后面数组的累加。
(0 136431 573963 0 219736 0 0 0 )：取自 p->wts.curr_window_cpu per-cpu的，表示任务在当前窗口中在每个cpu上运行的时间
prev_window：取自 p->wts.prev_window
(222138 156646 973556 0 219811 566790 0 0 )：取自 p->wts.prev_window_cpu 也是per-cpu的，表示任务在前一个窗口中在每个cpu上运行的时间
nt_cs：取自 rq->wrq.nt_curr_runnable_sum nt应该表示的是new task的缩写
nt_ps：取自 rq->wrq.nt_prev_runnable_sum
active_time：取自 p->wts.active_time is_new_task()中判断它，唯一更新位置rollover_task_window()中调用is_new_task()判断是新任务时 p->wts.active_time += task_rq(p)->wrq.prev_window_size;
grp_cs：取自 cpu_time ? cpu_time->curr_runnable_sum : 0 根据最后一个参数来判断是更新rq的还是更新rtg group的
grp_ps：取自 cpu_time ? cpu_time->prev_runnable_sum : 0
grp_nt_cs：取自 cpu_time ? cpu_time->nt_curr_runnable_sum : 0
grp_nt_ps：取自 cpu_time ? cpu_time->nt_prev_runnable_sum : 0
curr_top：取自 rq->wrq.curr_top 记录的是当前窗口中 rq->wrq.top_tasks[]中最大值的下标
prev_top：取自 rq->wrq.prev_top 记录的是前一个窗口中 rq->wrq.top_tasks[]中最大值的下标

(2) trace_sched_update_task_ravg_mini(p, rq, event, wallclock, irqtime, &rq->wrq.grp_time);

参数原型：
(struct task_struct *p, struct rq *rq, enum task_event evt, u64 wallclock, u64 irqtime, struct group_cpu_time *cpu_time)

打印内容：

-0 [005] d..2 280546.887141: sched_update_task_ravg_mini: wc 112233604355205 ws 112233596000001 delta 8355204
event PUT_PREV_TASK cpu 5 task 0 (swapper/5) ms 112233604337548 delta 17657 demand 2400000 rq_cs 1374618 rq_ps 1237818
cur_window 0 prev_window 0 grp_cs 0 grp_ps 0

字段解析：
wc：取自参数 wallclock
ws：取自 rq->wrq.window_start
delta：取自 wallclock - rq->wrq.window_start
event：取自 task_event_names[evt]
cpu：取自 rq->cpu
task：取自 p->pid
swapper/5：取自 p->comm
ms：取自 p->wts.mark_start
delta：两个同名，这是第二个，取自 wallclock - p->wts.mark_start
demand：取自 p->wts.demand
rq_cs：取自 rq->wrq.curr_runnable_sum
rq_ps：取自 rq->wrq.prev_runnable_sum
cur_window：取自 p->wts.curr_window
prev_window：取自 p->wts.prev_window
grp_cs：取自 cpu_time ? cpu_time->curr_runnable_sum : 0
grp_ps：取自 cpu_time ? cpu_time->prev_runnable_sum : 0

2. walt_update_task_ravg 的调用路径

tick_setup_sched_timer //tick_sched.c timer到期回调函数中指定 tick_sched_timer
        update_process_times //time.c tick中断中调用
            scheduler_tick //core.c 周期定时器中断，传参(rq->curr, rq, TASK_UPDATE, wallclock, 0)
        //任务显式阻塞或设置 TIF_NEED_RESCHED 并且在中断或返回用户空间调度点或preempt_enable()
            __schedule //core.c 在这个主调度器函数中调用了三次，若选出的prev != next，调用两次，分别传参(prev, rq, PUT_PREV_TASK, wallclock, 0)和(next, rq, PICK_NEXT_TASK, wallclock, 0)，若选出的prev == next，传参(prev, rq, TASK_UPDATE, wallclock, 0)
__irq_enter //hardirq.h __handle_domain_irq()中调用，中断入口：handle_arch_irq=gic_handle_irq-->handle_domain_irq
__do_softirq //softirq.c
    account_irq_enter_time //vtime.h
    account_irq_exit_time //vtime.h
        irqtime_account_irq //cputime.c 若curr是idle task，并且是在硬中断或软中断上下文则调用，否则调用walt_sched_account_irqstart
            walt_sched_account_irqend //walt.c，传参(curr, rq, IRQ_UPDATE, wallclock, delta);
    move_queued_task
    __migrate_swap_task
    try_to_wake_up //core.c 当新选出的cpu和任务之前运行的不是同一个cpu调用
    dl_task_offline_migration
    push_dl_task
    pull_dl_task
    detach_task
    push_rt_task
    pull_rt_task
        set_task_cpu //core.c 若新选出的cpu和任务之前的cpu不是同一个cpu，对任务进行迁移，然后调用，此时task->on_rq = TASK_ON_RQ_MIGRATING
            fixup_busy_time //walt.c 连续调用三次，分别传参 (task_rq(p)->curr, task_rq(p), TASK_UPDATE, wallclock, 0)和(dest_rq->curr, dest_rq, TASK_UPDATE, wallclock, 0)和(p, task_rq(p), TASK_MIGRATE, wallclock, 0)
cpufreq_freq_transition_end //cpufreq.c set_cpu_freq()中在设置频点前调用cpufreq_freq_transition_begin，设置后调用这个函数
    cpufreq_notify_post_transition //cpufreq.c 相同参数调用两次      
        notifier_trans_block.notifier_call //回调，对应val=CPUFREQ_POSTCHANGE时通知
            cpufreq_notifier_trans //walt.c 两层循环，对freq_domain_cpumask中的每一个cpu，对cluster中的每一个cpu，都调用，传参(rq->curr, rq, TASK_UPDATE, wallclock, 0)
sync_cgroup_colocation //walt.c cpu_cgrp_subsys.attach=cpu_cgroup_attach-->walt_schedgp_attach中对每一个cpuset都调用
sched_group_id_write //qc_vas.c 对应/proc//sched_group_id
    __sched_set_group_id //传参group_id=0才调用
        remove_task_from_group //walt.c 传参(rq, p->wts.grp, p, REM_TASK)
    __sched_set_group_id //传参group_id非0才调用
        add_task_to_group //walt.c 传参(rq, grp, p, ADD_TASK)
            transfer_busy_time //walt.c 连续调用两次，分别传参(rq->curr, rq, TASK_UPDATE, wallclock, 0)和(p, rq, TASK_UPDATE, wallclock, 0)
    fixup_busy_time    //当task的cpu和参数cpu不是同一个时调用
    walt_proc_user_hint_handler //walt.c /proc/sys/kernel/sched_user_hint作用load = load * (sched_user_hint / 100) 维持1s后清0
        walt_migration_irq_work.func //walt.c irq_work 结构的回调
walt_update_task_ravg //又回来了，work的响应函数中queue work，构成一个"内核线程不"停执行
    run_walt_irq_work //walt.c 若新的window_start和旧的不是同一个就调用
        walt_cpufreq_irq_work.func //walt.c irq_work 结构的回调
            walt_irq_work //walt.c 对每个cluster的每个cpu都调用，传参(rq->curr, rq, TASK_UPDATE, wallclock, 0)
    wake_up_q
    wake_up_process
    wake_up_state
    default_wake_function
        try_to_wake_up
            walt_try_to_wake_up //walt.h 连续调用两次，分别传参(rq->curr, rq, TASK_UPDATE, wallclock, 0)和(p, rq, TASK_WAKE, wallclock, 0)
                walt_update_task_ravg

walt_update_task_ravg 通过参数 event 可以控制哪些事件不更新负载。

3. update_window_start 函数

/* 唯一调用路径：walt_update_task_ravg --> this */
static u64 update_window_start(struct rq *rq, u64 wallclock, int event) //walt.c
{
    s64 delta;
    int nr_windows;
    u64 old_window_start = rq->wrq.window_start;

    delta = wallclock - rq->wrq.window_start;
    if (delta < 0) {
        printk_deferred("WALT-BUG CPU%d; wallclock=%llu is lesser than window_start=%llu", rq->cpu, wallclock, rq->wrq.window_start);
        SCHED_BUG_ON(1);
    }

    /* sched_ravg_window 默认是20ms, 不足一个窗口就不更新，直接退出*/
    if (delta < sched_ravg_window)
        return old_window_start;

    /* 下面是delta大于一个window的，计算历经的整窗的个数 */
    nr_windows = div64_u64(delta, sched_ravg_window);
    rq->wrq.window_start += (u64)nr_windows * (u64)sched_ravg_window; /* 更新ws */

    rq->wrq.cum_window_demand_scaled = rq->wrq.walt_stats.cumulative_runnable_avg_scaled;
    rq->wrq.prev_window_size = sched_ravg_window;

    return old_window_start;
}

可以看到，rq->wrq.window_start、rq->wrq.cum_window_demand_scaled 是最先更新的。然后返回旧的 window_start，

4. update_task_cpu_cycles 函数

static void update_task_cpu_cycles(struct task_struct *p, int cpu, u64 wallclock) //walt.c
{
    if (use_cycle_counter)
        p->wts.cpu_cycles = read_cycle_counter(cpu, wallclock);
}

在 p->wts.mark_start 为0的时候，调用这个函数，应该是做初始化的。

5. update_task_rq_cpu_cycles 函数
'

/* 唯一调用路径 walt_update_task_ravg --> this */
static void update_task_rq_cpu_cycles(struct task_struct *p, struct rq *rq, int event, u64 wallclock, u64 irqtime) //walt.c
{
    u64 cur_cycles;
    u64 cycles_delta;
    u64 time_delta;
    int cpu = cpu_of(rq);

    lockdep_assert_held(&rq->lock);

    if (!use_cycle_counter) {
        /* freq / maxfreq * cpu_capacity, arch_scale_cpu_capacity 为函数 topology_get_cpu_scale */
        rq->wrq.task_exec_scale = DIV64_U64_ROUNDUP(cpu_cur_freq(cpu) * arch_scale_cpu_capacity(cpu), rq->wrq.cluster->max_possible_freq);
        return;
    }

    cur_cycles = read_cycle_counter(cpu, wallclock); /*return rq->wrq.cycles;*/

    /*
     * 如果当前任务是空闲任务并且 irqtime == 0，CPU 确实空闲并且它的循环计数器可能没有增加。
     * 我们仍然需要估计的 CPU 频率来计算 IO 等待时间。 在这种情况下使用先前计算的频率。
     */
    if (!is_idle_task(rq->curr) || irqtime) {
        if (unlikely(cur_cycles < p->wts.cpu_cycles)) //这应该是溢出了
            cycles_delta = cur_cycles + (U64_MAX - p->wts.cpu_cycles);
        else
            cycles_delta = cur_cycles - p->wts.cpu_cycles;

        cycles_delta = cycles_delta * NSEC_PER_MSEC;

        if (event == IRQ_UPDATE && is_idle_task(p))
            /*
             * 在空闲任务的 mark_start 和 IRQ 处理程序进入时间之间的时间是 CPU 周期计数器停止时间段。
             * 在 IRQ 处理程序进入 walt_sched_account_irqstart() 时，补充空闲任务的 cpu 周期计数器，因
             * 此cycles_delta 现在表示 IRQ 处理程序期间增加的周期，而不是从进入空闲到 IRQ 退出之间的时间段。
             * 因此使用 irqtime 作为时间增量。
             */
            time_delta = irqtime;
        else
            time_delta = wallclock - p->wts.mark_start;
        SCHED_BUG_ON((s64)time_delta < 0);

        /* (cycles_delta * cpu_capacity) / (time_delta * max_freq) = cycles_delta/time_delta * cpu_capacity/max_freq*/
        rq->wrq.task_exec_scale = DIV64_U64_ROUNDUP(cycles_delta * arch_scale_cpu_capacity(cpu), time_delta * rq->wrq.cluster->max_possible_freq);

        trace_sched_get_task_cpu_cycles(cpu, event, cycles_delta, time_delta, p);
    }

    p->wts.cpu_cycles = cur_cycles;
}

其中Trace:

trace_sched_get_task_cpu_cycles(cpu, event, cycles_delta, time_delta, p);

参数原型：

(int cpu, int event, u64 cycles, u64 exec_time, struct task_struct *p)

打印内容：

shell svc 7920-7921 [006] d..4 53723.502493: sched_get_task_cpu_cycles: cpu=6 event=2 cycles=105682000000 exec_time=78229 freq=1350931 legacy_freq=2035200
max_freq=2035200 task=19304 (kworker/u16:5)

字段解析：

前4个字段直接来自参数，
freq：取自 cycles/exec_time, 其中 cycles 是乘以了 NSEC_PER_MSEC 的，exec_time 的单位是ns。
legacy_freq：取自 cpu_rq(cpu)->wrq.cluster->max_possible_freq，单位KHz
max_freq：取自 cpu_rq(cpu)->wrq.cluster->max_possible_freq * cpu_rq(cpu)->cpu_capacity_orig / SCHED_CAPACITY_SCALE
task：取自 p->pid
kworker/u16:5：取自 p->comm

6. update_history 解析

update_task_demand 中若判断不需要更新 task 的 p->wts.sum, 但是又有新窗口产生时，调用这个函数更新历史负载。

/*
 * 当一个任务的新窗口开始时调用，记录最近结束的窗口的 CPU 使用率。 通常'samples'应该是1。
 * 比如说，当一个实时任务同时运行而不抢占几个窗口时，它可以 > 1，也就是说连续运行3个窗口才
 * 更新的话，samples就传3。
 *
 * update_task_demand()调用传参：(rq, p, p->wts.sum, 1, event)  sum 是几5个窗口的
 */
static void update_history(struct rq *rq, struct task_struct *p, u32 runtime, int samples, int event) //walt.c
{
    u32 *hist = &p->wts.sum_history[0];
    int ridx, widx;
    u32 max = 0, avg, demand, pred_demand;
    u64 sum = 0;
    u16 demand_scaled, pred_demand_scaled;

    /* Ignore windows where task had no activity */
    if (!runtime || is_idle_task(p) || !samples)
        goto done;

    /* Push new 'runtime' value onto stack */
    /* hist[5]中的元素向后移动samples个位置，runtime值插入到hist[0]中，hist[0]是最新的时间 */
    widx = sched_ravg_hist_size - 1; /* 5-1=4 */
    ridx = widx - samples; //widx=4, samples=1, ridx=3; samples=2, ridx=2
    for (; ridx >= 0; --widx, --ridx) {
        hist[widx] = hist[ridx];
        sum += hist[widx];  //此循环 sum = hist[4] + hist[3] + hist[2] + hist[1]
        if (hist[widx] > max)
            max = hist[widx]; //max保存最近4个窗中的最大值
    }

    /*
     * 若samples=1, hist[0] = runtime
     * 若samples=2, hist[0] = runtime, hist[1] = runtime
     * ...
     */
    for (widx = 0; widx < samples && widx < sched_ravg_hist_size; widx++) {
        hist[widx] = runtime; //hist[0]中存放的是最近的一个窗中运行的时间
        sum += hist[widx]; //sum再加上hist[0]
        if (hist[widx] > max)
            max = hist[widx]; //max保存的是最近5个窗中最大的值了
    }

    /* 将p->wts.sum放入history数组后就清0了, 也说明这个sum是一个窗的sum值 */
    p->wts.sum = 0;

    /*可以通过 sched_window_stats_policy 文件进行配置下面4种window policy */
    if (sysctl_sched_window_stats_policy == WINDOW_STATS_RECENT) { //为0，返回最近一个窗口的运行时间值
        demand = runtime;
    } else if (sysctl_sched_window_stats_policy == WINDOW_STATS_MAX) { //为1，返回最近5个窗口运行时间的最大值
        demand = max;
    } else {
        avg = div64_u64(sum, sched_ravg_hist_size); //求最近5个窗口运行时间的平均值
        if (sysctl_sched_window_stats_policy == WINDOW_STATS_AVG) //为3，返回最近5个窗口平均运行时间值
            demand = avg;
        else
            demand = max(avg, runtime); //为2，默认配置，返回最近5个窗口平均运行时间值 与 最近1个窗口运行时间值中的较大的那个
    }

    pred_demand = predict_and_update_buckets(p, runtime);

    /* demand_scaled = demand/(window_size/1024) == (demand / window_size) * 1024
     * 传参demand可以认为是p的负载了
     */
    demand_scaled = scale_demand(demand);
    /* pred_demand_scaled = pred_demand/(window_size/1024) == (pred_demand / window_size) * 1024 */
    pred_demand_scaled = scale_demand(pred_demand);

    /*
     * 限流的deadline调度类任务出队列时不改变p->on_rq。 由于出队递减 walt stats 避免再次递减它。
     * 当窗口滚动时，累积窗口需求被重置为累积可运行平均值（来自运行队列上的任务的贡献）。如果当前任务已经出队，
     * 则它的需求不包括在累积可运行平均值中。所以将任务需求单独添加到累积窗口需求中。
     */
    /*这里增加的是rq上的统计值，不是per-entity的了*/
    if (!task_has_dl_policy(p) || !p->dl.dl_throttled) {
        if (task_on_rq_queued(p)) {
            fixup_walt_sched_stats_common(rq, p, demand_scaled, pred_demand_scaled); /*这里加的是demand_scaled的差值*/
        } else if (rq->curr == p) {
            walt_fixup_cum_window_demand(rq, demand_scaled);
        }
    }

    /*赋值给per-entiry上的统计值，demand_scaled 对 p->wts.demand_scaled 的赋值一定要保证，这是walt负载跟踪算法重要的部分*/
    p->wts.demand = demand; /* 对应一个窗中运行的时间(根据window policy不同而有差异) */
    p->wts.demand_scaled = demand_scaled; /* 对应一个窗中运行的时间(根据window policy不同而有差异)缩放到1024 */ #############
    p->wts.coloc_demand = div64_u64(sum, sched_ravg_hist_size); /*5个窗口运行时间之和除以5，即5个窗口的平均运行时间*/
    p->wts.pred_demand = pred_demand;
    p->wts.pred_demand_scaled = pred_demand_scaled;

    /* demand_scaled 大于指定的阈值时，会做一些事情 */
    if (demand_scaled > sysctl_sched_min_task_util_for_colocation) {
        p->wts.unfilter = sysctl_sched_task_unfilter_period; /*单位是ns，默认值是100ms*/
    } else {
        if (p->wts.unfilter)
            p->wts.unfilter = max_t(int, 0, p->wts.unfilter - rq->wrq.prev_window_size); //相当于衰减一个窗口的大小
    }

done:
    trace_sched_update_history(rq, p, runtime, samples, event);
}

其中Trace:

trace_sched_update_history(rq, p, runtime, samples, event);

参数原型：

(struct rq *rq, struct task_struct *p, u32 runtime, int samples, enum task_event evt)

打印内容：

sched_update_history: 24647 (kworker/u16:15): runtime 279389 samples 1 event TASK_WAKE demand 717323
coloc_demand 717323 pred_demand 279389 (hist: 279389 88058 520130 1182596 1516443) cpu 1 nr_big 0

字段解析：

24647：取自 p->pid
kworker/u16:15：取自 p->comm
runtime：来自参数3，表示最近一个窗口中的运行时间，也是 p->wts.sum 的值
samples：来自参数4，表示更新几个窗的历史
event：取自 task_event_names[event]
demand：取自 p->wts.demand，是scale之前的根据不同window policy计算出来的负载值
coloc_demand：取自 p->wts.coloc_demand，即5个窗口的平均值
pred_demand：取自 p->wts.pred_demand，表示预测的负载需求
(hist: 279389 88058 520130 1182596 1516443)：取自 p->wts.sum_history[5]，是任务在最近5个窗口中分别运行的时间
cpu：取自 rq->cpu
nr_big：取自 rq->wrq.walt_stats.nr_big_tasks

用于预测任务的 demand 的 bucket 相关更新：

static inline u32 predict_and_update_buckets(struct task_struct *p, u32 runtime) //walt.c
{

    int bidx;
    u32 pred_demand;

    if (!sched_predl) //为1
        return 0;

    /* 根据传入的时间值获得一个桶的下标，桶一共有10个成员 */
    bidx = busy_to_bucket(runtime);
    /* 使用 p->wts.busy_buckets 用于计算 */
    pred_demand = get_pred_busy(p, bidx, runtime);
    /* 更新 p->wts.busy_buckets */
    bucket_increase(p->wts.busy_buckets, bidx);

    return pred_demand;
}

static inline int busy_to_bucket(u32 normalized_rt)
{
    int bidx;

    bidx = mult_frac(normalized_rt, NUM_BUSY_BUCKETS, max_task_load()); /*args1*10/16; arg1*arg2/arg3*/
    bidx = min(bidx, NUM_BUSY_BUCKETS - 1); //min(p->wts.sum * 10 / 16, 9) 运行一个满窗是桶10，运行1ms-2ms返回1

    /* 合并最低的两个桶。 最低频率落入第二桶，因此继续预测最低桶是没有用的。*/
    if (!bidx)
        bidx++;

    return bidx;
}

/*
 * get_pred_busy - 计算运行队列上的任务的预测需求
 *
 * @p：正在更新预测的任务
 * @start: 起始桶。 返回的预测不应低于此桶。
 * @runtime：任务的运行时间。 返回的预测不应低于此运行时。
 * 注意：@start 可以从@runtime 派生。 传入它只是为了在某些情况下避免重复计算。
 *
 * 根据传入的@runtime 为任务@p 返回一个新的预测繁忙时间。该函数搜索表示繁忙时间等于或大于@runtime
 * 的桶，并尝试找到用于预测的桶。 一旦找到，它会搜索历史繁忙时间并返回落入桶中的最新时间。 如果不
 * 存在这样的繁忙时间，则返回该桶的中间值。
 */
/*假设传参是p->wts.sum=8ms,那么传参就是(p, 5, 8)，*/
static u32 get_pred_busy(struct task_struct *p, int start, u32 runtime)
{
    int i;
    u8 *buckets = p->wts.busy_buckets; //10个元素
    u32 *hist = p->wts.sum_history; //5个元素
    u32 dmin, dmax;
    u64 cur_freq_runtime = 0;
    int first = NUM_BUSY_BUCKETS, final; //从最大值10开始找
    u32 ret = runtime;

    /* skip prediction for new tasks due to lack of history */
    /* 由于累积运行时间小于100ms的新任务缺少历史运行时间，不对其进行预测 */
    if (unlikely(is_new_task(p)))
        goto out;

    /* find minimal bucket index to pick */
    /* 找到最小的桶下标进行pick, 只要桶中有数据就选择 */
    for (i = start; i < NUM_BUSY_BUCKETS; i++) {
        if (buckets[i]) {
            first = i;
            break;
        }
    }

    /* 若没找到桶下标，就直接返回 runtime，注意 runtime 可能大于10 */
    if (first >= NUM_BUSY_BUCKETS)
        goto out;

    /* 计算用于预测的桶 */
    final = first;

    /* 确定预测桶的需求范围 */
    if (final < 2) {
        /* 最低的两个桶合并 */
        dmin = 0;
        final = 1;
    } else {
        dmin = mult_frac(final, max_task_load(), NUM_BUSY_BUCKETS); //final * 20 / 10, max_task_load返回一个满窗
    }
    dmax = mult_frac(final + 1, max_task_load(), NUM_BUSY_BUCKETS); //(final + 1) * 20 / 10

    /*
     * search through runtime history and return first runtime that falls
     * into the range of predicted bucket.
     * 搜索运行历史并返回落在预测桶范围内的第一个运行。在最近的5个窗口中查找
     */
    for (i = 0; i < sched_ravg_hist_size; i++) {
        if (hist[i] >= dmin && hist[i] < dmax) {
            ret = hist[i];
            break;
        }
    }
    /* no historical runtime within bucket found, use average of the bin 
     * 若找不到存储桶内的历史运行时间，就使用垃圾桶的平均值 */
    if (ret < dmin)
        ret = (dmin + dmax) / 2;
    /*
     * 在窗口中间更新时，运行时间可能高于所有记录的历史记录。 始终至少预测运行时间。
     */
    ret = max(runtime, ret);
out:
    /* 由于 cur_freq_runtime 是0，所以 pct 恒为0 */
    trace_sched_update_pred_demand(p, runtime, mult_frac((unsigned int)cur_freq_runtime, 100,  sched_ravg_window), ret);

    return ret;
}

/*
 * bucket_increase - 更新所有桶的计数
 *
 * @buckets：跟踪任务繁忙时间的桶数组
 * @idx: 要被递增的桶的索引
 *
 * 每次完成一个完整的窗口时，运行时间落入 (@idx) 的桶计数增加。 所有其他桶的计数都会衰减。 
 * 根据桶中的当前计数，增加和衰减的速率可能不同。
 */
/*传参： (p->wts.busy_buckets, bidx)*/
static inline void bucket_increase(u8 *buckets, int idx)
{
    int i, step;

    for (i = 0; i < NUM_BUSY_BUCKETS; i++) { //10
        if (idx != i) { //不相等就衰减
            if (buckets[i] > DEC_STEP) //2
                buckets[i] -= DEC_STEP; //2
            else
                buckets[i] = 0;
        } else { //相等
            step = buckets[i] >= CONSISTENT_THRES ? INC_STEP_BIG : INC_STEP; //16 16 8
            if (buckets[i] > U8_MAX - step) //255-step
                buckets[i] = U8_MAX; //255
            else
                buckets[i] += step; //就是加step，上面判断是为了不要溢出
        }
    }
}

其中Trace:

trace_sched_update_pred_demand(p, runtime, mult_frac((unsigned int)cur_freq_runtime, 100, sched_ravg_window), ret);

参数原型：

(struct task_struct *p, u32 runtime, int pct, unsigned int pred_demand)

打印内容：

sched_update_pred_demand: 1174 (Binder:1061_2): runtime 556361 pct 0 cpu 1 pred_demand 556361 (buckets: 0 255 0 0 0 0 0 0 0 0)

字段解析：

1174：取自 p->pid
Binder:1061_2：取自 p->comm
runtime：取自参数2
pct：取自参数3
cpu：取自task_cpu(p)
pred_demand：取自参数4
(buckets: 0 255 0 0 0 0 0 0 0 0)：取自 p->wts.busy_buckets[10]

/* 
 * update_history --> this，如果task在rq上才会调用传参: (rq, p, demand_scaled, pred_demand_scaled)，参数是缩放到0--1024后的
 * 也就是说这个函数里面计算的包含 runnable 的
 */
static void fixup_walt_sched_stats_common(struct rq *rq, struct task_struct *p, u16 updated_demand_scaled, u16 updated_pred_demand_scaled)
{
    /* p->wts.demand_scaled 约是由 p->wts.sum scale后得来的(window plicy策略影响), 后者是一个窗口中任务运行的时长。新的减旧的，结果处于[-1024,1024] */
    s64 task_load_delta = (s64)updated_demand_scaled - p->wts.demand_scaled;
    /* p->wts.pred_demand_scaled 是由桶算法预测得来的 */
    s64 pred_demand_delta = (s64)updated_pred_demand_scaled - p->wts.pred_demand_scaled;

    /* 直接加上传入的增量，注意增量可能是负数，一个进程的负载变低了，差值就是负数了*/
    fixup_cumulative_runnable_avg(&rq->wrq.walt_stats, task_load_delta, pred_demand_delta);
    /*累加demand_scaled的增量*/
    walt_fixup_cum_window_demand(rq, task_load_delta); /*上下两个函数都是对rq->wrq.中的成员赋值*/
}

/*
 * 如果task在rq上调用路径：update_history --> fixup_cumulative_runnable_avg 传参：(&rq->wrq.walt_stats, task_load_delta, pred_demand_delta)
 * 传参为时间差值。
 */
static inline void fixup_cumulative_runnable_avg(struct walt_sched_stats *stats, s64 demand_scaled_delta, s64 pred_demand_scaled_delta)
{
    /*
     * 增量差值可正可负，rq 的 cumulative_runnable_avg_scaled 初始化后就只有在这里有赋值了。
     * 这里根据根据当前窗口负载值快速变化。
     */
    stats->cumulative_runnable_avg_scaled += demand_scaled_delta;
    BUG_ON((s64)stats->cumulative_runnable_avg_scaled < 0);

    stats->pred_demands_sum_scaled += pred_demand_scaled_delta;
    BUG_ON((s64)stats->pred_demands_sum_scaled < 0);
}

说明 rq->wrq.walt_stats.cumulative_runnable_avg_scaled 和 rq->wrq.walt_stats.pred_demands_sum_scaled 统计的只是 runnable 状态的负载值。这里加上有符号的delta值，可以快速的反应runnable状态的负载的变化。

/* 
 * 如果task在rq上调用路径：update_history --> fixup_walt_sched_stats_common --> this 传参：(rq, task_load_delta)
 * 如果rq->curr == p 时调用路径：update_history --> this 传参：(rq, demand_scaled)
 * 说明这里面更新的成员统计的级包括 runnable 的分量，也保留 running 的分量
 */
static inline void walt_fixup_cum_window_demand(struct rq *rq, s64 scaled_delta)
{
    rq->wrq.cum_window_demand_scaled += scaled_delta;

    if (unlikely((s64)rq->wrq.cum_window_demand_scaled < 0))
        rq->wrq.cum_window_demand_scaled = 0;
}

rq->wrq.cum_window_demand_scaled 统计的既包括 runnable 的又包括 running 的。runnable 的累加的是差值，而 running 的累加的直接是 demand_scaled 的值，若是一部分 runnable 的任务变成 running 了，前者减少，后者增加，体现在结果上可能是不变的。

7. update_task_demand 函数

/*
 * 计算任务的cpu需求和/或更新任务的cpu需求历史
 *
 * ms = p->wts.mark_start
 * wc = wallclock
 * ws = rq->wrq.window_start
 *
 * 三种可能：
 *  a) 任务事件包含在一个窗口中。 16ms per-window, window_start < mark_start < wallclock
 *       ws    ms    wc
 *       |    |    |
 *       V    V    V
 *       |---------------|
 *
 * 在这种情况下，如果事件是合适的 p->wts.sum 被更新（例如：event == PUT_PREV_TASK）
 *
 * b) 任务事件跨越两个窗口。mark_start < window_start < wallclock
 *
 *       ms    ws     wc
 *       |    |     |
 *       V    V     V
 *      ------|-------------------
 *
 * 在这种情况下，如果事件是合适的 p->wts.sum 更新为 (ws - ms) ，然后记录一个新的窗口的采样，如果事件是合
 * 适的然后将 p->wts.sum 设置为 (wc - ws) 。
 *
 * c) 任务事件跨越两个以上的窗口。
 *
 *        ms ws_tmp                   ws  wc
 *        |  |                       |   |
 *        V  V                       V   V
 *        ---|-------|-------|-------|-------|------
 *           |                   |
 *           |<------ nr_full_windows ------>|
 *
 * 在这种情况下，如果事件是合适的，首先 p->wts.sum 更新为 (ws_tmp - ms) ，p->wts.sum 被记录，然后，如果
 * event 是合适的 window_size 的 'nr_full_window' 样本也被记录，最后如果 event 是合适的，p->wts.sum 更新
 * 到 (wc - ws)。
 *
 * 重要提示：保持 p->wts.mark_start 不变，因为 update_cpu_busy_time() 依赖它！
 *
 */
/* walt_update_task_ravg-->this 唯一调用位置 */
static u64 update_task_demand(struct task_struct *p, struct rq *rq, int event, u64 wallclock) //walt.c
{
    u64 mark_start = p->wts.mark_start; //进来时还没更新
    u64 delta, window_start = rq->wrq.window_start; //进来时已经更新了
    int new_window, nr_full_windows;
    u32 window_size = sched_ravg_window; //20ms
    u64 runtime;

    new_window = mark_start < window_start; //若为真说明经历了新窗口
    /* 若判断不需要更新负载，直接更新历史 p->wts.sum_history[]，而没有更新 p->wts.sum */
    if (!account_busy_for_task_demand(rq, p, event)) {
        if (new_window) {
            /*
             * 如果计入的时间没有计入繁忙时间，并且新的窗口开始，
             * 则只需要关闭前一个窗口与预先存在的需求。 多个窗口
             * 可能已经过去，但由于空窗口被丢弃，因此没有必要考虑这些。
             *
             * 如果被累积的时间没有被计入繁忙时间，并且有新的窗口开始，
             * 则只需要与预先存在需求的前一个窗口被关闭。 虽然可能有多
             * 个窗口已经流逝了，但由于WALT算法是空窗口会被丢弃掉，因
             * 此没有必要考虑这些。
             */
            update_history(rq, p, p->wts.sum, 1, event);
        }
        return 0;
    }
    /* 下面是需要更新的情况了 */

    /* (1) 还是同一个窗口，对应上面的情况a */
    if (!new_window) {
        /* 简单的情况 - 包含在现有窗口中的繁忙时间。*/
        return add_to_task_demand(rq, p, wallclock - mark_start);
    }

    /* (2) 下面就是跨越了窗口，先求情况b */
    /* 繁忙时间至少跨越两个窗口。 暂时将 window_start 倒回到 mark_start 之后的第一个窗口边界。*/
    delta = window_start - mark_start;
    nr_full_windows = div64_u64(delta, window_size);
    window_start -= (u64)nr_full_windows * (u64)window_size;

    /* Process (window_start - mark_start) first */
    /* 这里累加的是  情况b/情况c 中ws_tmp-ms这段的delta值 */
    runtime = add_to_task_demand(rq, p, window_start - mark_start);

    /* Push new sample(s) into task's demand history */
    /* 将最开始的不足一个window窗口大小的delta计算出来的p->wts.sum放入历史数组中 */
    update_history(rq, p, p->wts.sum, 1, event);

    /* (3) 下面就对应情况c了，由于c和b都有最开始不足一个窗口的一段，在上面计算b时一并计算了 */
    if (nr_full_windows) {
        u64 scaled_window = scale_exec_time(window_size, rq); //等于直接return window_size

        /* 一下子更新 nr_full_windows 个窗口的负载到历史窗口负载中，每个窗口都是满窗 */
        update_history(rq, p, scaled_window, nr_full_windows, event);
        /* runtime 累积运行时间进行累加 ==>只要搞清什么时候标记ms和什么时候调用这个函数计算负载，就可以知道计算的是哪段的 ######## */
        runtime += nr_full_windows * scaled_window;
    }

    /* 将 window_start 滚回当前以处理当前窗口，以便于计算当前窗口中的剩余部分。*/
    window_start += (u64)nr_full_windows * (u64)window_size;

    /* 这里是计算情况b和情况c的wc-ws段 */
    mark_start = window_start;

    runtime += add_to_task_demand(rq, p, wallclock - mark_start); //runtime 继续累加

    /* 返回值表示此次 update_task_demand 更新的时间值，是 wc-ms 的差值 */
    return runtime;
}

此函数中始终没有更新回去 p->wts.mark_start，其是在 walt_update_task_ravg 函数最后更新的。rq->wrq.window_start 在上面第一个函数中就更新了。

/* update_task_demand --> this */
static int account_busy_for_task_demand(struct rq *rq, struct task_struct *p, int event) //walt.c
{
    /* (1) 不需要统计 idle task 的 demand，直接返回*/
    if (is_idle_task(p))
        return 0;

    /*
     * 当一个任务被唤醒时，它正在完成一段非繁忙时间。 同样，如果等待时间
     * 不被视为繁忙时间，那么当任务开始运行或迁移时，它并未运行并且正在完成
     * 一段非繁忙时间。
     */
    /*就是这些情况跳过统计，!SCHED_ACCOUNT_WAIT_TIME 恒为假，所以是只判断了 TASK_WAKE */
    /* (2) 是唤醒事件 或 不需要计算walit事件并且事件是pick和migrate, 不需要更新 */
    if (event == TASK_WAKE || (!SCHED_ACCOUNT_WAIT_TIME && (event == PICK_NEXT_TASK || event == TASK_MIGRATE)))
        return 0;

    /* (3) idle进程退出的时候也不需要统计 */
    if (event == PICK_NEXT_TASK && rq->curr == rq->idle)
        return 0;

    /*
     * TASK_UPDATE can be called on sleeping task, when its moved between related groups
     */
    /*context_switch()的时候更改的rq->curr*/
    /* (4) 若是update事件，且p是curr任务，需要更新。否则若p在队列上需要更新，不在队列上不需要更新 */
    if (event == TASK_UPDATE) {
        if (rq->curr == p)
            return 1;

        return p->on_rq ? SCHED_ACCOUNT_WAIT_TIME : 0; //这里可调整是否记录任务在rq上的等待的时间
    }

    /* (5) 都不满足，默认是需要更新 */
    return 1;
}

p是idle task，或事件是 TASK_WAKE，或idle任务退出时的 PICK_NEXT_TASK 事件，或事件是 TASK_UPDATE 但是 p 不是curr任务也没有在rq上，就不需要计算busy time。只有事件是 TASK_UPDATE，且任务p是 rq->curr 任务或者 p是在rq 上等待，则需要更新。若不需要更新的话，又产生了新的窗口，那就调用 update_history()更新负载历史就退出了。

/* update_task_demand --> this 唯一调用路径也是在 walt_update_task_ravg 中 */
static u64 add_to_task_demand(struct rq *rq, struct task_struct *p, u64 delta) //walt.c
{
    /* delta = (delta * rq->wrq.task_exec_scale) >> 10, 由于 rq->wrq.task_exec_scale 初始化为1024，所以还是delta*/
    delta = scale_exec_time(delta, rq);
    /* 这里更新了 p->wts.sum，并将最大值钳位在一个窗口大小*/
    p->wts.sum += delta;
    if (unlikely(p->wts.sum > sched_ravg_window))
        p->wts.sum = sched_ravg_window;

    return delta;
}

更新 p->wts.sum 值，并且返回 delta 值。这也是 sum 的唯一更新位置，唯一调用路径也是从 walt_update_task_ravg 函数调用下来的。

8. update_cpu_busy_time 函数

/* walt_update_task_ravg --> this 这是唯一调用路径，传参(p, rq, event, wallclock, irqtime)*/
static void update_cpu_busy_time(struct task_struct *p, struct rq *rq, int event, u64 wallclock, u64 irqtime)
{
    int new_window, full_window = 0;
    int p_is_curr_task = (p == rq->curr);
    u64 mark_start = p->wts.mark_start;
    u64 window_start = rq->wrq.window_start; //walt_update_task_ravg-->update_window_start 最先更新的rq->wrq.window_start
    u32 window_size = rq->wrq.prev_window_size;
    u64 delta;
    u64 *curr_runnable_sum = &rq->wrq.curr_runnable_sum;
    u64 *prev_runnable_sum = &rq->wrq.prev_runnable_sum;
    u64 *nt_curr_runnable_sum = &rq->wrq.nt_curr_runnable_sum;
    u64 *nt_prev_runnable_sum = &rq->wrq.nt_prev_runnable_sum;
    bool new_task;
    struct walt_related_thread_group *grp;
    int cpu = rq->cpu;
    u32 old_curr_window = p->wts.curr_window;

    new_window = mark_start < window_start;
    if (new_window)
        full_window = (window_start - mark_start) >= window_size;

    /* 处理每个任务的窗口翻转。 我们不关心空闲任务。*/
    if (!is_idle_task(p)) {
        if (new_window)
            /* 将 p->wts 的 curr_window 赋值给 prev_window，然后将 curr_window 清0 */
            rollover_task_window(p, full_window);
    }

    new_task = is_new_task(p); //运行时间小于5个窗口的任务

    /* p是curr任务并且有了个新窗口才执行 */
    if (p_is_curr_task && new_window) {
        /* rq的一些成员，prev_*_sum=curr_*_sum, 然后将 curr_*_sum 赋值为0 */
        rollover_cpu_window(rq, full_window);
        rollover_top_tasks(rq, full_window); //这里面已经更新了rq->wrq.curr_table ############
    }

    /* 判断是否需要记录 */
    if (!account_busy_for_cpu_time(rq, p, irqtime, event))
        goto done;
    /*----下面就是需要计算的了----*/

    grp = p->wts.grp;
    if (grp) {
        struct group_cpu_time *cpu_time = &rq->wrq.grp_time;
        /* 注意：指向更改了! */
        curr_runnable_sum = &cpu_time->curr_runnable_sum;
        prev_runnable_sum = &cpu_time->prev_runnable_sum;

        nt_curr_runnable_sum = &cpu_time->nt_curr_runnable_sum;
        nt_prev_runnable_sum = &cpu_time->nt_prev_runnable_sum;
    }

    if (!new_window) {
        /*
         * account_busy_for_cpu_time() = 1 所以忙时间需要计入当前窗口。 
         * 没有翻转，因为我们没有启动一个新窗口。 这方面的一个例子是当
         * 任务开始执行然后在同一窗口内休眠时。
         */
        if (!irqtime || !is_idle_task(p) || cpu_is_waiting_on_io(rq))
            delta = wallclock - mark_start;
        else
            delta = irqtime;
        delta = scale_exec_time(delta, rq); //等于直接return delta
        *curr_runnable_sum += delta;
        if (new_task)
            *nt_curr_runnable_sum += delta;

        if (!is_idle_task(p)) {
            p->wts.curr_window += delta;
            p->wts.curr_window_cpu[cpu] += delta;
        }

        goto done;
    }
    /*----下面就是有一个新窗口的情况了----*/

    if (!p_is_curr_task) {
        /*
         * account_busy_for_cpu_time() = 1 所以忙时间需要计入当前窗口。
         * 一个新窗口也已启动，但 p 不是当前任务，因此窗口不会翻转 
         * - 只需拆分并根据需要将计数分为 curr 和 prev。 仅在为当前任
         * 务处理新窗口时才会翻转窗口。
         *
         * irqtime 不能由不是当前正在运行的任务的任务计算。
         */

        if (!full_window) {
            /* 一个完整的窗口还没有过去，计算对上一个完成的窗口的部分贡献。*/
            delta = scale_exec_time(window_start - mark_start, rq);
            p->wts.prev_window += delta;
            p->wts.prev_window_cpu[cpu] += delta;
        } else {
            /* 由于至少一个完整的窗口已经过去，对前一个窗口的贡献是一个完整的窗口(window_size) */
            delta = scale_exec_time(window_size, rq);
            p->wts.prev_window = delta;
            p->wts.prev_window_cpu[cpu] = delta;
        }

        *prev_runnable_sum += delta;
        if (new_task)
            *nt_prev_runnable_sum += delta;

        /* 只占当前窗口的一部分繁忙时间 */
        delta = scale_exec_time(wallclock - window_start, rq);
        *curr_runnable_sum += delta;
        if (new_task)
            *nt_curr_runnable_sum += delta;

        p->wts.curr_window = delta; /*对当前窗的贡献直接复制给当前窗*/
        p->wts.curr_window_cpu[cpu] = delta;

        goto done;
    }
    /*----下面p是当前任务的情况了----*/

    if (!irqtime || !is_idle_task(p) || cpu_is_waiting_on_io(rq)) {
        /*
         * account_busy_for_cpu_time() = 1 所以忙时间需要计入当前窗口。 一个新窗口已经启动， 
         * p 是当前任务，因此需要翻转。 如果以上三个条件中的任何一个为真，那么这个繁忙的时
         * 间就不能算作 irqtime。
         *
         * 空闲任务的繁忙时间不需要计算。
         *
         * 一个例子是一个任务开始执行，然后在新窗口开始后休眠。
         */

        if (!full_window) {
            /* 一个完整的窗口还没有过去，计算对上一个完整的窗口的部分贡献。*/
            delta = scale_exec_time(window_start - mark_start, rq); //等效直接返回window_start - mark_start
            if (!is_idle_task(p)) {
                p->wts.prev_window += delta;
                p->wts.prev_window_cpu[cpu] += delta;
            }
        } else {
            /* 由于至少一个完整的窗口已经过去，对前一个窗口的贡献是完整的窗口（window_size）*/
            delta = scale_exec_time(window_size, rq);
            if (!is_idle_task(p)) {
                p->wts.prev_window = delta;
                p->wts.prev_window_cpu[cpu] = delta;
            }
        }

        /* 在这里通过覆盖 prev_runnable_sum 和 curr_runnable_sum 中的值来完成翻转。*/
        *prev_runnable_sum += delta;
        if (new_task)
            *nt_prev_runnable_sum += delta;

        /* 计算在当前窗口忙时的一片时间 */
        delta = scale_exec_time(wallclock - window_start, rq);
        *curr_runnable_sum += delta;
        if (new_task)
            *nt_curr_runnable_sum += delta;

        if (!is_idle_task(p)) {
            p->wts.curr_window = delta;
            p->wts.curr_window_cpu[cpu] = delta;
        }

        goto done;
    }
    /*---- 下面就对应 irqtime && is_idle_task(p) && ！cpu_is_waiting_on_io(rq) 的情况了，并且累积上面的条件 ----*/

    if (irqtime) {
        /*
         * account_busy_for_cpu_time() = 1 所以忙时间需要计入当前窗口。
         * 一个新窗口已经启动，p 是当前任务，因此需要翻转。 当前任务必
         * 须是空闲任务，因为不为其他任何任务计算irqtime。
         *
         * 空闲一段时间后，每次我们处理 IRQ 活动时都会计算 Irqtime，因
         * 此我们知道 IRQ 繁忙时间为 wallclock - irqtime。
         */

        SCHED_BUG_ON(!is_idle_task(p));
        mark_start = wallclock - irqtime;

        /*
         * 滚动窗口。 如果 IRQ 繁忙时间只是在当前窗口中，那么这就是所有需要计算的。
         */
        if (mark_start > window_start) {
            *curr_runnable_sum = scale_exec_time(irqtime, rq); //等效于直接返回irqtime，因为是idle线程，之前应该是0的
            return;
        }
        /*---下面是ms<=ws---*/

        /*
         * IRQ 繁忙时间跨越多个窗口。 先处理当前窗口开始前的忙时间。
         */
        delta = window_start - mark_start;
        if (delta > window_size)
            delta = window_size;
        delta = scale_exec_time(delta, rq);
        *prev_runnable_sum += delta; //这直接加不会超过一个窗的大小吗？

        /* Process the remaining IRQ busy time in the current window.  处理当前窗口中剩余的 IRQ 忙时间。*/
        delta = wallclock - window_start;
        rq->wrq.curr_runnable_sum = scale_exec_time(delta, rq);

        return;
    }

done:
    if (!is_idle_task(p))
        update_top_tasks(p, rq, old_curr_window, new_window, full_window);
}

值更新当前窗口和前一个窗口的busy时间，主要用于更新任务的： p->wts.curr_window、p->wts.curr_window_cpu[cpu]，更新rq 的 rq->wrq.curr_runnable_sum、rq->wrq.prev_runnable_sum，若是一个walt认为的新任务，还更新 rq->wrq.nt_curr_runnable_sum、rq->wrq.nt_prev_runnable_sum。然后是更新 top-task 的一些成员

下面分别是对 task、cpu、top_tasks 维护的 window 进行更新。有一个新的窗口到来时更新，若更新时已经经历了一个或多个完整的window，那么对prev和curr window 相关的描述结构进行清理备用。

static u32 empty_windows[NR_CPUS];
/* 将 p->wts 的 curr_window 赋值给 prev_window，然后将 curr_window 清0 */
static void rollover_task_window(struct task_struct *p, bool full_window)
{
    u32 *curr_cpu_windows = empty_windows; //数组，每个cpu一个
    u32 curr_window;
    int i;

    /* Rollover the sum */
    curr_window = 0;

    /* 若经历了一个full_window, prev和curr window都清理待用 */
    if (!full_window) {
        curr_window = p->wts.curr_window;
        curr_cpu_windows = p->wts.curr_window_cpu;
    }

    p->wts.prev_window = curr_window;
    p->wts.curr_window = 0;

    /* Roll over individual CPU contributions 滚动每个 CPU 的贡献 */
    for (i = 0; i < nr_cpu_ids; i++) {
        p->wts.prev_window_cpu[i] = curr_cpu_windows[i];
        p->wts.curr_window_cpu[i] = 0;
    }

    if (is_new_task(p))
        p->wts.active_time += task_rq(p)->wrq.prev_window_size; //active_time 的唯一更新位置, walt认为的新任务
}

清理的是任务的 p->wts.prev_window_cpu、p->wts.curr_window、p->wts.prev_window_cpu[]、p->wts.curr_window_cpu[]

/*
 * rq的一些成员，prev_*_sum=curr_*_sum, 然后将 curr_*_sum 赋值为0，将curr赋值给prev,
 * 若是有经历了多个窗口curr和prev窗口都需要清理待用。
 */
static void rollover_cpu_window(struct rq *rq, bool full_window)
{
    u64 curr_sum = rq->wrq.curr_runnable_sum;
    u64 nt_curr_sum = rq->wrq.nt_curr_runnable_sum;
    u64 grp_curr_sum = rq->wrq.grp_time.curr_runnable_sum;
    u64 grp_nt_curr_sum = rq->wrq.grp_time.nt_curr_runnable_sum;

    if (unlikely(full_window)) {
        curr_sum = 0;
        nt_curr_sum = 0;
        grp_curr_sum = 0;
        grp_nt_curr_sum = 0;
    }

    rq->wrq.prev_runnable_sum = curr_sum;
    rq->wrq.nt_prev_runnable_sum = nt_curr_sum;
    rq->wrq.grp_time.prev_runnable_sum = grp_curr_sum;
    rq->wrq.grp_time.nt_prev_runnable_sum = grp_nt_curr_sum;

    rq->wrq.curr_runnable_sum = 0;
    rq->wrq.nt_curr_runnable_sum = 0;
    rq->wrq.grp_time.curr_runnable_sum = 0;
    rq->wrq.grp_time.nt_curr_runnable_sum = 0;
}

清理的是 rq->wrq 的和 rq->wrq.grp_time 的 prev_runnable_sum、curr_runnable_sum、nt_prev_runnable_sum、nt_curr_runnable_sum

static void rollover_top_tasks(struct rq *rq, bool full_window)
{
    /* 跟踪的是2个，构成一个环形数组 */
    u8 curr_table = rq->wrq.curr_table;
    u8 prev_table = 1 - curr_table;
    int curr_top = rq->wrq.curr_top;

    /*将prev window的数据结构清理后待用*/
    clear_top_tasks_table(rq->wrq.top_tasks[prev_table]); //memset(arg, 0, NUM_LOAD_INDICES * sizeof(u8));
    clear_top_tasks_bitmap(rq->wrq.top_tasks_bitmap[prev_table]);//将bit数组的内容清0,然后将 NUM_LOAD_INDICES bit设置为1

    /*若是已经经历了多个window,那么之前标记的curr window也是旧窗口了，需要清理待用*/
    if (full_window) {
        curr_top = 0;
        clear_top_tasks_table(rq->wrq.top_tasks[curr_table]);
        clear_top_tasks_bitmap(rq->wrq.top_tasks_bitmap[curr_table]);
    }

    /*两个window的下标进行翻转，curr-->prev,prev-->curr*/
    rq->wrq.curr_table = prev_table;
    rq->wrq.prev_top = curr_top;
    rq->wrq.curr_top = 0;
}

清理的是 rq->wrq 的 top_task 相关的成员。

然后调用 account_busy_for_cpu_time 判断清理后任务的和cpu的是否还需要更新上去

/* update_cpu_busy_time-->this, 传参(rq, p, irqtime, event) */
static int account_busy_for_cpu_time(struct rq *rq, struct task_struct *p, u64 irqtime, int event)
{
    if (is_idle_task(p)) {
        /* TASK_WAKE && TASK_MIGRATE is not possible on idle task!  idle task不可能出现唤醒和迁移 */
        if (event == PICK_NEXT_TASK)
            return 0;

        /* PUT_PREV_TASK, TASK_UPDATE && IRQ_UPDATE are left */
        return irqtime || cpu_is_waiting_on_io(rq);
    }

    if (event == TASK_WAKE)
        return 0;

    if (event == PUT_PREV_TASK || event == IRQ_UPDATE)
        return 1;

    /*
     * TASK_UPDATE can be called on sleeping task, when its moved between related groups
     * TASK_UPDATE 当它在相关组之间移动时可能在睡眠的任务上调用，
     */
    if (event == TASK_UPDATE) {
        if (rq->curr == p)
            return 1;

        return p->on_rq ? SCHED_FREQ_ACCOUNT_WAIT_TIME : 0; //在rq上和或正在迁移是1，但是冒号前后都是0
    }

    /* TASK_MIGRATE, PICK_NEXT_TASK left */
    return SCHED_FREQ_ACCOUNT_WAIT_TIME; //0
}

top_task 维护的窗口更新：

/* 
 * update_cpu_busy_time-->this 若p不是idle任务，就调用，传参(p, rq, old_curr_window, new_window, full_window) 
 * @ old_curr_window：取自 p->wts.curr_window，表示p在窗口翻转前在当前窗口的运行时间
 * @ new_window：bool值，若mswindow_size为真
 */
static void update_top_tasks(struct task_struct *p, struct rq *rq, u32 old_curr_window, int new_window, bool full_window)
{
    /* 只使用两个窗口进行跟踪，当前是0，perv就是1，当前是1，prev就是0，两个数据结构构成一个环形缓存区 */
    u8 curr = rq->wrq.curr_table;
    u8 prev = 1 - curr;
    u8 *curr_table = rq->wrq.top_tasks[curr];
    u8 *prev_table = rq->wrq.top_tasks[prev];
    int old_index, new_index, update_index;
    u32 curr_window = p->wts.curr_window;
    u32 prev_window = p->wts.prev_window;
    bool zero_index_update;

    /* 两个窗的运行时间相等或新窗口还没有到来 */
    if (old_curr_window == curr_window && !new_window)
        return;

    /* 在一个窗中运行的时间越长，index就越大, 参数是一个窗口中的运行时长*/
    old_index = load_to_index(old_curr_window);
    new_index = load_to_index(curr_window);

    if (!new_window) {
        zero_index_update = !old_curr_window && curr_window;
        if (old_index != new_index || zero_index_update) {
            if (old_curr_window)
                curr_table[old_index] -= 1; //上一个窗口的累计值衰减
            if (curr_window)
                curr_table[new_index] += 1; //新窗口的累计值增加
            if (new_index > rq->wrq.curr_top)
                rq->wrq.curr_top = new_index; //更新rq->wrq.curr_top成员
        }

        if (!curr_table[old_index])
            __clear_bit(NUM_LOAD_INDICES - old_index - 1, rq->wrq.top_tasks_bitmap[curr]); //这个bit数组表示此运行时间下有没有计数值

        if (curr_table[new_index] == 1)
            __set_bit(NUM_LOAD_INDICES - new_index - 1, rq->wrq.top_tasks_bitmap[curr]);

        return;
    }
    /*---下面是new_window!=0的情况了---*/

    /*
     * 对于此任务来说窗口已经翻转。 当我们到达这里时，curr/prev 交换已经发生。 
     * 所以我们需要对新索引使用 prev_window 。
     */
    update_index = load_to_index(prev_window);

    if (full_window) { //至少有一个满窗
        /*
         * 这里有两个案例。 要么'p' 运行了整个窗口，要么根本不运行。 在任何一种情况下，
         * prev 表中都没有条目。 如果 'p' 运行整个窗口，我们只需要在 prev 表中创建一个
         * 新条目。 在这种情况下，update_index 将对应于 sched_ravg_window，因此我们可
         * 以无条件地更新顶部索引。
         */
        if (prev_window) {
            prev_table[update_index] += 1;
            rq->wrq.prev_top = update_index;
        }

        if (prev_table[update_index] == 1)
            __set_bit(NUM_LOAD_INDICES - update_index - 1, rq->wrq.top_tasks_bitmap[prev]);
    } else { //产生了新窗口，但是还没达到一个满窗
        zero_index_update = !old_curr_window && prev_window;
        if (old_index != update_index || zero_index_update) {
            if (old_curr_window)
                prev_table[old_index] -= 1;

            prev_table[update_index] += 1;

            if (update_index > rq->wrq.prev_top)
                rq->wrq.prev_top = update_index;

            /* 减为0是清理对应bit，首次设置为1时设置相应bit。top_tasks_bitmap[]在任务迁移时有使用 */
            if (!prev_table[old_index])
                __clear_bit(NUM_LOAD_INDICES - old_index - 1, rq->wrq.top_tasks_bitmap[prev]);
            if (prev_table[update_index] == 1)
                __set_bit(NUM_LOAD_INDICES - update_index - 1, rq->wrq.top_tasks_bitmap[prev]);
        }
    }

    if (curr_window) {
        curr_table[new_index] += 1;

        if (new_index > rq->wrq.curr_top)
            rq->wrq.curr_top = new_index;

        if (curr_table[new_index] == 1)
            __set_bit(NUM_LOAD_INDICES - new_index - 1, rq->wrq.top_tasks_bitmap[curr]);
    }
}

top_tasks 的维护中也使用到了桶，新窗运行时间对应的 curr_table[]成员加1，之前窗口运行时间对应的 prev_table[] 成员减1。

9. update_task_pred_demand 函数

/*
 * 在窗口翻转时计算任务的预测需求。如果任务当前窗口繁忙时间超过预测需求，则在此处更新以反映任务需求。
 */
void update_task_pred_demand(struct rq *rq, struct task_struct *p, int event)
{
    u32 new, old;
    u16 new_scaled;

    if (!sched_predl) //1
        return;

    if (is_idle_task(p))
        return;

    if (event != PUT_PREV_TASK && event != TASK_UPDATE &&
            (!SCHED_FREQ_ACCOUNT_WAIT_TIME || (event != TASK_MIGRATE && event != PICK_NEXT_TASK)))
        return;

    /*
     * 当它在相关组之间移动时，TASK_UPDATE 可以在睡眠任务上调用。
     */
    if (event == TASK_UPDATE) {
        if (!p->on_rq && !SCHED_FREQ_ACCOUNT_WAIT_TIME)
            return;
    }

    new = calc_pred_demand(p);
    old = p->wts.pred_demand;

    if (old >= new)
        return;
    /*---下面就是 new > old 的情况---*/

    new_scaled = scale_demand(new); //new/window_size*1024
    /* p是on rq的状态并且不是已经被throttle的deadline任务 */
    if (task_on_rq_queued(p) && (!task_has_dl_policy(p) || !p->dl.dl_throttled))
        fixup_walt_sched_stats_common(rq, p, p->wts.demand_scaled, new_scaled);

    p->wts.pred_demand = new;
    p->wts.pred_demand_scaled = new_scaled;
}

注意，这里再次调用了 fixup_walt_sched_stats_common，在 walt_update_task_ravg 函数中，在 update_history 中已经调用过一次，进入条件也相同，也是p在队列上。

static inline u32 calc_pred_demand(struct task_struct *p)
{
    /* 预测的需求比当前窗口的大，就返回预测的需求 */
    if (p->wts.pred_demand >= p->wts.curr_window)
        return p->wts.pred_demand;

    return get_pred_busy(p, busy_to_bucket(p->wts.curr_window), p->wts.curr_window);
}

get_pred_busy 和 busy_to_bucket 两个函数上面都有列出。

10. run_walt_irq_work 函数

static inline void run_walt_irq_work(u64 old_window_start, struct rq *rq) //walt.c
{
    u64 result;

    /*若是还是同一个窗，直接退出*/
    if (old_window_start == rq->wrq.window_start)
        return;

    /* 
     * atomic64_cmpxchg(*ptr, old, new) 函数功能是：将old和ptr指向的内容比较，如果相等，
     * 则将new写入到ptr指向的内存中，并返回old，如果不相等，则返回ptr指向的内容。
     */
    result = atomic64_cmpxchg(&walt_irq_work_lastq_ws, old_window_start, rq->wrq.window_start);
    if (result == old_window_start) {
        walt_irq_work_queue(&walt_cpufreq_irq_work); //触发回调 walt_irq_work()，构成一个"内核线程"，循环往复执行

        trace_walt_window_rollover(rq->wrq.window_start);
    }
}

walt_irq_work_queue 会触发 walt_irq_work() 被调用，这个函数中又会调用 walt_update_task_ravg，walt_update_task_ravg 函数会在每个tick中调用，这里这样实现可能是针对没有tick的场景使用。

其中Trace:

trace_walt_window_rollover(rq->wrq.window_start);

参数原型：

(u64 window_start)

打印内容：

//20ms间隔执行一次
-0 [002] d..2 48262.320451: walt_window_rollover: window_start=48262548000001
-0 [001] d.h2 48262.340457: walt_window_rollover: window_start=48262568000001

字段解析：

window_start 就是打印 rq->wrq.window_start 的记录的时间值，单位是ns.

四、总结

WALT负载计算算法是基于窗口的，对window有一个rollover的操作，只跟踪curr和prev两个窗口，curr窗口的下标由 wrq.curr_table 指向，两个窗口构成一个唤醒缓冲区，prev和curr进行不断切换。
walt_update_task_ravg 函数通过其 event 成员决定对哪些事件计算负载，再根据其调用路径和其调用函数对是否是在rq上，是否是p=rq->curr可以判断统计的是哪部分的负载。
预测负载这块，对于任务和CPU都使用了桶，任务是10个桶，对于cpu的curr和prev两个窗口分别是1000个成员，命中累加，不命中衰减。
walt_update_task_ravg 在tick的调用路径中有调用，应该是为了无tick情况下walt仍然能正常工作，使用irq_work构成一个内核线程以一个窗口的周期来更新窗口。

五、补充

task util的获取：task_util() WALT: p->wts.demand_scaled；PELT: p->se.avg.util_avg
cpu util的获取：cpu_util_cum() WALT: rq->wrq.cum_window_demand_scaled；PELT: rq->cfs.avg.util_avg
task_util() 函数

static inline unsigned long task_util(struct task_struct *p)
{
#ifdef CONFIG_SCHED_WALT
    if (likely(!walt_disabled && sysctl_sched_use_walt_task_util))
        return p->wts.demand_scaled;
#endif
    return READ_ONCE(p->se.avg.util_avg);
}

Gentoo中文社区 / Gentoo 之 WALT负载计算源码分析

Gentoo 之 WALT负载计算源码分析