【WALT】top task 相关代码详解

代码版本：Linux4.9 android-msm-crosshatch-4.9-android12

@

结构体

我们先来看看与 top task 有关的结构体。

#define NUM_TRACKED_WINDOWS 2
#define NUM_LOAD_INDICES 1000

#define DECLARE_BITMAP_ARRAY(name,nr,bits) \
	unsigned long name[nr][BITS_TO_LONGS(bits)]
	
struct rq { 
	……
#ifdef CONFIG_SCHED_WALT
	……
	struct load_subtractions load_subs[NUM_TRACKED_WINDOWS];
	DECLARE_BITMAP_ARRAY(top_tasks_bitmap,
			NUM_TRACKED_WINDOWS, NUM_LOAD_INDICES);
	u8 *top_tasks[NUM_TRACKED_WINDOWS];
	u8 curr_table;
	int prev_top;
	int curr_top;
#endif
	……
}

top_tasks_bitmap 是一个位图，一个位有 2 种状态，即 0 和 1。位图本质上是数组，适用于大规模数据，但数据状态又不是很多的情况，通常是用来判断某个数据存不存在的。

top_tasks_bitmap 的作用是可以快速找到当前 CPU 的运行队列在上一个窗口（prev）和当前窗口（curr）中有哪些区间在执行任务。

• 区间：一个窗口被分为了 NUM_LOAD_INDICES 个区间。（默认为 1000 个）

在一个 CPU 的运行队列的结构体中，通过 top_tasks 数组来跟踪 prev 和 curr 两个窗口的 top task 情况，通过 curr_table 来标识哪一个 top_tasks 是 curr 的。curr_table 非 0 即 1。

prev_top 和 curr_top 的值为 prev 窗口 和 curr 窗口中最后一个任务执行结束时的时间所处区间的下标。换句话说，它们指示了 prev 窗口 和 curr 窗口中最后一个还在执行任务的区间。

初始化 & 清理函数

#define NUM_TRACKED_WINDOWS 2
#define NUM_LOAD_INDICES 1000

void walt_sched_init(struct rq *rq)
{
	……
	for (j = 0; j < NUM_TRACKED_WINDOWS; j++) {
		memset(&rq->load_subs[j], 0,
				sizeof(struct load_subtractions));
		rq->top_tasks[j] = kcalloc(NUM_LOAD_INDICES,
				sizeof(u8), GFP_NOWAIT);
		/* No other choice */
		BUG_ON(!rq->top_tasks[j]);
		clear_top_tasks_bitmap(rq->top_tasks_bitmap[j]);
	}
	……
}

static const unsigned int top_tasks_bitmap_size =
		BITS_TO_LONGS(NUM_LOAD_INDICES + 1) * sizeof(unsigned long);
		
void clear_top_tasks_bitmap(unsigned long *bitmap)
{
	memset(bitmap, 0, top_tasks_bitmap_size);
	__set_bit(NUM_LOAD_INDICES, bitmap);
}

static inline void clear_top_tasks_table(u8 *table)
{
	memset(table, 0, NUM_LOAD_INDICES * sizeof(u8));
}

初始化就是分配内存。如果分配是从一个原子上下文中进行的，例如中断处理程序，使用 GFP_NOWAIT 。这个 标志可以防止直接回收和IO或文件系统操作。因此，在内存压力下， GFP_NOWAIT 分配 可能会失败。（该段话来自《内存分配指南》）

更新 top task

#define MIN_SCHED_RAVG_WINDOW 20000000
#define NUM_LOAD_INDICES 1000
__read_mostly unsigned int sched_load_granule =
			MIN_SCHED_RAVG_WINDOW / NUM_LOAD_INDICES;
			
static u32 load_to_index(u32 load)
{
	u32 index = load / sched_load_granule;
	return min(index, (u32)(NUM_LOAD_INDICES - 1));
}

static void update_top_tasks(struct task_struct *p, struct rq *rq,
		u32 old_curr_window, int new_window, bool full_window)
{
	u8 curr = rq->curr_table;
	u8 prev = 1 - curr;
	u8 *curr_table = rq->top_tasks[curr];
	u8 *prev_table = rq->top_tasks[prev];
	int old_index, new_index, update_index;
	u32 curr_window = p->ravg.curr_window;
	u32 prev_window = p->ravg.prev_window;
	bool zero_index_update;

	if (old_curr_window == curr_window && !new_window)
		return;

	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->curr_top)
				rq->curr_top = new_index;
		}

		if (!curr_table[old_index])
			__clear_bit(NUM_LOAD_INDICES - old_index - 1,
				rq->top_tasks_bitmap[curr]);

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

		return;
	}

	update_index = load_to_index(prev_window);

	if (full_window) {
		if (prev_window) {
			prev_table[update_index] += 1;
			rq->prev_top = update_index;
		}

		if (prev_table[update_index] == 1)
			__set_bit(NUM_LOAD_INDICES - update_index - 1,
				rq->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->prev_top)
				rq->prev_top = update_index;

			if (!prev_table[old_index])
				__clear_bit(NUM_LOAD_INDICES - old_index - 1,
						rq->top_tasks_bitmap[prev]);

			if (prev_table[update_index] == 1)
				__set_bit(NUM_LOAD_INDICES - update_index - 1,
						rq->top_tasks_bitmap[prev]);
		}
	}

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

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

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

update_top_tasks() 只在 update_cpu_busy_time() 中使用，是这个函数的最后一步。

在 p->ravg.curr_window 变化或任务进入新窗口时，开始更新任务所在运行队列的 top task。

首先根据旧的 curr_window 和新的 curr_window 计算他们的索引。load_to_index() 其实就是将窗口分成 NUM_LOAD_INDICES 个区间（默认为 1000），然后计算新旧两个执行时间处于哪个区间内，这个区间的下标就是 new_index 和 old_index。

1. 任务仍在旧窗口中，即任务在旧窗口中多执行了一段时间

   • zero_index_update = !old_curr_window && curr_window：

     这条语句主要是在 old_index == new_index 时判断 old_curr_window 是否为 0 且 curr_window 是否不为 0 的。

     如果 old_curr_window == 0 且 curr_window != 0，则 zero_index_update 为 true，反之为 false。

   • 新旧下标不同 或 zero_index_update 为 true 时：

     1. 如果 old_curr_window 不为 0，就让 curr_table[old_index] 的值减 1；
     2. 如果 curr_window 不为 0，就让 curr_table[new_index] 的值加 1；
     3. 如果 new_index 比 rq->curr_top 还大，就把 rq->curr_top 的值设置为 new_index。

   • 如果 curr_table[old_index] 已经为 0：

     通过 __clear_bit() 将 rq->top_tasks_bitmap[curr][NUM_LOAD_INDICES - old_index - 1] 这一位置 0。

   • 如果 curr_table[new_index] 正好为 1（如果大于 1 就不进行以下操作了）：

     通过 __set_bit() 将 rq->top_tasks_bitmap[curr][NUM_LOAD_INDICES - new_index - 1] 这一位置 1。

   执行完以上操作就直接结束 top task 的更新。

2. 任务进入新窗口

   先得到旧窗口中任务执行时间 prev_window 所对应的下标，然后开始更新 prev 的信息

   1. 旧窗口经过了超过一个完整窗口的时间

      • 如果 prev_window 不为 0：

        让 prev_table[update_index] 的值减加 1，且让 rq->prev_top 的值直接为 update_index（因为更早的已经更新了，现在才更新肯定是更晚的）；

      • 如果 curr_table[new_index] 正好为 1（如果大于 1 就不进行以下操作了）：

        通过 __set_bit() 将 rq->top_tasks_bitmap[prev][NUM_LOAD_INDICES - update_index - 1] 这一位置 1。

   2. 旧窗口没有经过一个完整窗口的时间

      • zero_index_update = !old_curr_window && prev_window：

        这条语句主要是在 old_index == update_index 时判断 old_curr_window 是否为 0 且 prev_window 是否不为 0 的。

        如果 old_curr_window == 0 且 prev_window != 0，则 zero_index_update 为 true，反之为 false。

      • 新旧下标不同 或 zero_index_update 为 true 时：

        1. 如果 old_curr_window 不为 0，就让 prev_table[old_index] 的值减 1；
        2. prev_table[update_index] 的值直接加 1；
        3. 如果 update_index 比 rq->prev_top 还大，就把 rq->prev_top 的值设置为 update_index；
        4. 如果 curr_table[old_index] 已经为 0，通过 __clear_bit() 将 rq->top_tasks_bitmap[prev][NUM_LOAD_INDICES - old_index - 1] 这一位置 0；
        5. 如果 curr_table[new_index] 正好为 1，通过 __set_bit() 将 rq->top_tasks_bitmap[prev][NUM_LOAD_INDICES - update_index - 1] 这一位置 1。

   更新完 prev 的信息，开始更新 curr 的信息。

   • 如果 curr_window 不为 0：
     1. curr_table[new_index] 的值直接加 1；
     2. 如果 new_index 比 rq->curr_top 还大，就把 rq->curr_top 的值设置为 new_index；
     3. 如果 curr_table[new_index] 正好为 1，通过 __set_bit() 将 rq->top_tasks_bitmap[curr][NUM_LOAD_INDICES - new_index - 1] 这一位置 1。

窗口翻滚时更新 top task

static void rollover_top_tasks(struct rq *rq, bool full_window)
{
	u8 curr_table = rq->curr_table;
	u8 prev_table = 1 - curr_table;
	int curr_top = rq->curr_top;

	clear_top_tasks_table(rq->top_tasks[prev_table]);
	clear_top_tasks_bitmap(rq->top_tasks_bitmap[prev_table]);

	if (full_window) {
		curr_top = 0;
		clear_top_tasks_table(rq->top_tasks[curr_table]);
		clear_top_tasks_bitmap(
				rq->top_tasks_bitmap[curr_table]);
	}

	rq->curr_table = prev_table;
	rq->prev_top = curr_top;
	rq->curr_top = 0;
}

rollover_top_tasks() 同样也只在 update_cpu_busy_time() 中使用，是在任务进入新窗口时且任务是运行队列中正在执行的任务时执行。

该函数主要就是将 curr 的信息转移到 prev 上，然后把 curr 的信息都清空。值得注意的是，如果旧窗口经过了一个完整窗口时间以上，prev 的信息也要清空。

两个运行队列 top task 的相互转移

static void
migrate_top_tasks(struct task_struct *p, struct rq *src_rq, struct rq *dst_rq)
{
	int index;
	int top_index;
	u32 curr_window = p->ravg.curr_window;
	u32 prev_window = p->ravg.prev_window;
	u8 src = src_rq->curr_table;
	u8 dst = dst_rq->curr_table;
	u8 *src_table;
	u8 *dst_table;

	if (curr_window) {
		src_table = src_rq->top_tasks[src];
		dst_table = dst_rq->top_tasks[dst];
		index = load_to_index(curr_window);
		src_table[index] -= 1;
		dst_table[index] += 1;

		if (!src_table[index])
			__clear_bit(NUM_LOAD_INDICES - index - 1,
				src_rq->top_tasks_bitmap[src]);

		if (dst_table[index] == 1)
			__set_bit(NUM_LOAD_INDICES - index - 1,
				dst_rq->top_tasks_bitmap[dst]);

		if (index > dst_rq->curr_top)
			dst_rq->curr_top = index;

		top_index = src_rq->curr_top;
		if (index == top_index && !src_table[index])
			src_rq->curr_top = get_top_index(
				src_rq->top_tasks_bitmap[src], top_index);
	}

	if (prev_window) {
		src = 1 - src;
		dst = 1 - dst;
		src_table = src_rq->top_tasks[src];
		dst_table = dst_rq->top_tasks[dst];
		index = load_to_index(prev_window);
		src_table[index] -= 1;
		dst_table[index] += 1;

		if (!src_table[index])
			__clear_bit(NUM_LOAD_INDICES - index - 1,
				src_rq->top_tasks_bitmap[src]);

		if (dst_table[index] == 1)
			__set_bit(NUM_LOAD_INDICES - index - 1,
				dst_rq->top_tasks_bitmap[dst]);

		if (index > dst_rq->prev_top)
			dst_rq->prev_top = index;

		top_index = src_rq->prev_top;
		if (index == top_index && !src_table[index])
			src_rq->prev_top = get_top_index(
				src_rq->top_tasks_bitmap[src], top_index);
	}
}

static int get_top_index(unsigned long *bitmap, unsigned long old_top)
{
	// 从索引为 old_top 的 bit 位（包括该位）开始，找到第一个为 1 的 bit 位，返回该位的索引。
	int index = find_next_bit(bitmap, NUM_LOAD_INDICES, old_top);

	if (index == NUM_LOAD_INDICES)
		return 0;

	return NUM_LOAD_INDICES - 1 - index;
}

src 是 source（源头）的缩写，dst 是 destination（目的）的缩写。

migrate_top_tasks() 在 fixup_busy_time() 中被调用，任务在从 src_rq 迁移到 dst_rq 时，需要对两个队列中的 top task 信息进行更新，基本就是将当前任务的 prev 信息与 curr 信息从 scr_rq 上加到 dst_rq 上，然后去掉 scr_rq 上原有的信息。

其中，dst_rq 已经根据任务的 curr_window 和 prev_window 得到了最新的区间下标，而如果 src_rq 的区间下标和最新的一致，它就没法直接得到任务执行之前的区间下标，所以引入了函数 get_top_index()：根据传入的 old_top 找到最近的区间下标，然后返回新的 top_index。

计算 top task 的负载

#define NUM_LOAD_INDICES 1000
#define MIN_SCHED_RAVG_WINDOW 20000000
__read_mostly unsigned int sched_ravg_window = MIN_SCHED_RAVG_WINDOW;
__read_mostly unsigned int sched_load_granule =
		MIN_SCHED_RAVG_WINDOW / NUM_LOAD_INDICES;
		
static u32  top_task_load(struct rq *rq)
{
	int index = rq->prev_top;
	u8 prev = 1 - rq->curr_table;

	if (!index) {
		int msb = NUM_LOAD_INDICES - 1;

		if (!test_bit(msb, rq->top_tasks_bitmap[prev]))
			return 0;
		else
			return sched_load_granule;
	} else if (index == NUM_LOAD_INDICES - 1) {
		return sched_ravg_window;
	} else {
		return (index + 1) * sched_load_granule;
	}
}

• 如果运行队列在上一个窗口中的 prev_top 为 0：

  意味着运行队列上一个窗口中可能没有任务执行，或者任务只在第一个区间内执行。

  在上文解析更新 top task 的 update_top_tasks() 的时候我们提到了 zero_index_update：在 old_index == new_index 时判断 old_curr_window 是否为 0 且 curr_window 是否不为 0 。

  也就是说，要判断第一个区间内有没有任务执行，需要看位图中第一位（NUM_LOAD_INDICES - 1）是否有值。

  • 如果位图中 NUM_LOAD_INDICES - 1 位的值为 0：上一个窗口中运行队列没有任务执行，负载为 0。
  • 如果位图中 NUM_LOAD_INDICES - 1 位的值为 1：上一个窗口中运行队列有任务执行，但只在第一个区间内执行，负载就算第一个区间的时长。

• 如果运行队列在上一个窗口中的 prev_top 为 NUM_LOAD_INDICES - 1：

  也就是说任务基本跑满了整个窗口，负载直接算作一个窗口时长。

• 其他情况：

  就直接把负载当作 (index + 1) * sched_load_granule。

本栏目推荐文章
• 代码随想录 day18 找树左下角的值 路径总和 从中序与后序遍历序列构造二叉树
• 用jacoco统计JAVA项目测试代码覆盖率
• （坚持每天写算法）基础算法复习与学习part1基础算法1-7——高精度减法（处理t=1和t>1代码的写法，t为操作次数）
• GDB调试之源代码查看与管理(六)
• 写代码时如何合理的画图表达逻辑结构
• 十行python代码实现文件去重，去除重复文件的脚本
• [代码随想录] 第四天
• idea 中java代码修改后运行代码不生效
• 一行代码创建网页（html）
• 如何在SAP GUI中快速执行新的事务代码

代码 WALT task top代码walt task top walt update_task_ravg入口 代码 scale_exec_time代码scale walt walt 线程 概念 代码task 频率walt 风格 代码11.29 task5 update_task_demand代码update demand update_task_cpu_cycles代码update cycles 功能walt rtg