页次： 1
一、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)
打印内容：
<idle>-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)
打印内容：
<idle>-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/<pid>/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_ravgwalt_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值，若ms<ws为真
* @ full_window：bool值，若ws-ms>window_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间隔执行一次
<idle>-0 [002] d..2 48262.320451: walt_window_rollover: window_start=48262548000001
<idle>-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);
}离线
页次： 1