eBPF在CPU调度上的应用

目前的开源项目中，主要是将eBPF应用在网络、安全、系统观测方面。近些年eBPF技术也开始应用在调度器上，实现调度器的可观察、可编程。本文主要介绍一些eBPF技术在调度器上的应用尝试。

调度器简介

在Linux中，调度器被抽象为调度类sched_class，调度类中包括了各种调度处理函数，由各种调度算法实现。

// kernel/sched/sched.h
struct sched_class {

#ifdef CONFIG_UCLAMP_TASK
	int uclamp_enabled;
#endif
	// 将进程加入到调度队列中
	void (*enqueue_task) (struct rq *rq, struct task_struct *p, int flags);
	// 将进程从调度队列中删除
	void (*dequeue_task) (struct rq *rq, struct task_struct *p, int flags);
	// 当进程主动放弃CPU时调用
	void (*yield_task)   (struct rq *rq);
	bool (*yield_to_task)(struct rq *rq, struct task_struct *p);

	// 检查当前进程是否可被强占
	void (*check_preempt_curr)(struct rq *rq, struct task_struct *p, int flags);

	// 从调度类中选出下一个要运行的进程
	struct task_struct *(*pick_next_task)(struct rq *rq);

	// 将进程放回运行队列
	void (*put_prev_task)(struct rq *rq, struct task_struct *p);
	// 选择下一个进程
	void (*set_next_task)(struct rq *rq, struct task_struct *p, bool first);

#ifdef CONFIG_SMP
	// SMP负载均衡
	int (*balance)(struct rq *rq, struct task_struct *prev, struct rq_flags *rf);
	// 为进程选择一个适合的CPU
	int  (*select_task_rq)(struct task_struct *p, int task_cpu, int flags);

	struct task_struct * (*pick_task)(struct rq *rq);

	// 迁移到另外的CPU调度队列中
	void (*migrate_task_rq)(struct task_struct *p, int new_cpu);

	// 用于进程唤醒
	void (*task_woken)(struct rq *this_rq, struct task_struct *task);
	// 修改进程CPU亲和性
	void (*set_cpus_allowed)(struct task_struct *p, struct affinity_context *ctx);
	// 启动、关闭运行队列
	void (*rq_online)(struct rq *rq);
	void (*rq_offline)(struct rq *rq);

	struct rq *(*find_lock_rq)(struct task_struct *p, struct rq *rq);
#endif

	// 由time_tick调用。它可能引起进程切换，驱动运行时（running）抢占
	void (*task_tick)(struct rq *rq, struct task_struct *p, int queued);
	// 在进程创建时调用
	void (*task_fork)(struct task_struct *p);
	// 在进程退出时调用
	void (*task_dead)(struct task_struct *p);

	/*
	 * The switched_from() call is allowed to drop rq->lock, therefore we
	 * cannot assume the switched_from/switched_to pair is serialized by
	 * rq->lock. They are however serialized by p->pi_lock.
	 */
	 // 用于进程切换
	void (*switched_from)(struct rq *this_rq, struct task_struct *task);
	void (*switched_to)  (struct rq *this_rq, struct task_struct *task);
	// 改变进程优先级
	void (*prio_changed) (struct rq *this_rq, struct task_struct *task,
			      int oldprio);

	unsigned int (*get_rr_interval)(struct rq *rq,
					struct task_struct *task);
	// 更新进程调度信息，比如cfs的vruntime
	void (*update_curr)(struct rq *rq);

#ifdef CONFIG_FAIR_GROUP_SCHED
	void (*task_change_group)(struct task_struct *p);
#endif
};

一般系统调度发生在调用cond_resched()、调用schedule()、从系统调用或中断返回时。在系统创建调用器时，会初始化一个调度定时器，定时器每隔一段时间执行一次中断，判断任务是否要调度，并设置标志位，在中断结束后，由调度算法进行调度。在Linux对于普通进程的调度器是基于红黑树的CFS调度算法。

`BPF_PROG_TYPE_SCHED`类型的BPF程序

Roman Gushchin提交的patchset引入了一种新的BPF_PROG_TYPE_SCHED类型的BPF程序，对CFS调度类插入了三个hook：

cfs_check_preempt_tick：，在处理调度定时器tick时调用，attach此处的eBPF程序可以查看哪个进程正在运行。当eBPF返回值小于0时，表示该进程可以继续执行，防止其被抢占；当eBPF返回值大于0时，表示该进程需要被切换，由cfs选择新的进程进行抢占；当eBPF返回0时，eBPF不影响调度。

// hook点在`kernel/sched/fair.c`的`check_preempt_tick()`中
static void
check_preempt_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr)
{
 ...
 	ideal_runtime = sched_slice(cfs_rq, curr);
 	delta_exec = curr->sum_exec_runtime - curr->prev_sum_exec_runtime;

	if (bpf_sched_enabled()) {
		int ret = bpf_sched_cfs_check_preempt_tick(curr, delta_exec);

		if (ret < 0)
			return;
		else if (ret > 0)
			resched_curr(rq_of(cfs_rq));
	}
...
}

cfs_check_preempt_wakeup在进程被内核唤醒时被调用。当eBPF返回负值时，将阻止该进程抢占正在运行的进程；返回正值，则进行强制抢占；返回0则不影响，留给后续调度算法决定。

// hook点在`kernel/sched/fair.c`的`check_preempt_wakeup()`中
static void check_preempt_wakeup(struct rq *rq, struct task_struct *p, int wake_flags)
{
...
	/* Idle tasks are by definition preempted by non-idle tasks. */
	if (unlikely(task_has_idle_policy(curr)) &&
	    likely(!task_has_idle_policy(p)))
		goto preempt;
 
	if (bpf_sched_enabled()) {
		int ret = bpf_sched_cfs_check_preempt_wakeup(current, p);

		if (ret < 0)
			return;
		else if (ret > 0)
			goto preempt;
	}
...
}

cfs_wakeup_preempt_entity与cfs_check_preempt_wakeup类似，在新的进程被选中运行时调用，返回值为负数表示不执行抢占，返回值为正式表示强制抢占，返回0不影响。

// hook点在`kernel/sched/fair.c`的`wakeup_preempt_entity()`中
static int
wakeup_preempt_entity(struct sched_entity *curr, struct sched_entity *se)
 {
 	s64 gran, vdiff = curr->vruntime - se->vruntime;
 
	if (bpf_sched_enabled()) {
		int ret = bpf_sched_cfs_wakeup_preempt_entity(curr, se);

		if (ret)
			return ret;
	}

 	if (vdiff <= 0)
 		return -1;
...
}

通过这种对CFS调度器加hook，使用BPF影响CPU调度的方式，Facebook在主网页上获得了很好的延迟以及1%RPS提升。详见Early Patches Bring BPF To The Linux Scheduler、LWN: Controlling the CPU scheduler with BPF。

`sched_ext`调度类

内核中，一般会用一个C结构体包含一组函数指针的方式，抽象一些实现，比如上面的sched_class。eBPF的struct_ops特性允许通过BPF程序实现内核里的这种结构体，来实现额外功能。最初struct_ops是用在TCP的拥塞控制上，而目前也用于实现调度算法的扩展上。

sched_ext项目实现了一个sched_ext调度类（简称为SCX），使用struct sched_ext_ops定义了一组调度处理的函数，eBPF程序通过实现struct sched_ext_ops中的函数来实现调度算法。以下方法中只有name不能为空，其他的都是可选。

// include/linux/sched/ext.h
struct sched_ext_ops {
	/* 为被唤醒的进程选择CPU */
	s32 (*select_cpu)(struct task_struct *p, s32 prev_cpu, u64 wake_flags);

	/* 将进程加入调度队列 */
	void (*enqueue)(struct task_struct *p, u64 enq_flags);

	/* 将进程从调度队列中删除 */
	void (*dequeue)(struct task_struct *p, u64 deq_flags);

	/* 分配调度任务 */
	void (*dispatch)(s32 cpu, struct task_struct *prev);

	/* 任务在CPU上变为runnable，与下面三个方法一起，用于跟踪任务的状态转变。任务会依次经过runable，多次的running、stopping，然后完成执行，变为quiescent*/
	void (*runnable)(struct task_struct *p, u64 enq_flags);
	void (*running)(struct task_struct *p);
	void (*stopping)(struct task_struct *p, bool runnable);
	void (*quiescent)(struct task_struct *p, u64 deq_flags);

	/* yield 让出CPU，to是可选的 */
	bool (*yield)(struct task_struct *from, struct task_struct *to);

	/* Core scheduling的任务排序 */
	bool (*core_sched_before)(struct task_struct *a, struct task_struct *b);

	/* 配置cpu亲和性 */
	void (*set_cpumask)(struct task_struct *p, struct cpumask *cpumask);

	/* cpu空闲状态变化时调用 */
	void (*update_idle)(s32 cpu, bool idle);

	/* 当cpu重新对BPF调度器可用时调用。和下面的cpu_release是一对，cpu_release是当cpu对BPF调度器不可用时调用,一般出现在更高等级的sched_class对cpu的抢占的情况 */
	void (*cpu_acquire)(s32 cpu, struct scx_cpu_acquire_args *args);
	void (*cpu_release)(s32 cpu, struct scx_cpu_release_args *args);

	/* cpu上、下线时调用 */
	void (*cpu_online)(s32 cpu);
	void (*cpu_offline)(s32 cpu);

	/* 从task进入BPF调度器，到退出BPF调度器的一些操作 */
	s32 (*prep_enable)(struct task_struct *p, struct scx_enable_args *args);
	void (*enable)(struct task_struct *p, struct scx_enable_args *args);
	void (*cancel_enable)(struct task_struct *p,
			      struct scx_enable_args *args);
	void (*disable)(struct task_struct *p);

	/* cgroup相关的操作触发的调度逻辑 */
	s32 (*cgroup_init)(struct cgroup *cgrp,
			   struct scx_cgroup_init_args *args);
	void (*cgroup_exit)(struct cgroup *cgrp);
	s32 (*cgroup_prep_move)(struct task_struct *p,
				struct cgroup *from, struct cgroup *to);
	void (*cgroup_move)(struct task_struct *p,
			    struct cgroup *from, struct cgroup *to);
	void (*cgroup_cancel_move)(struct task_struct *p,
				   struct cgroup *from, struct cgroup *to);
	void (*cgroup_set_weight)(struct cgroup *cgrp, u32 weight);

	// BPF调度器初始化/退出的逻辑
	s32 (*init)(void);
	void (*exit)(struct scx_exit_info *info);

	/* dispatch()可分配的最大任务数 */
	u32 dispatch_max_batch;
	u64 flags;
	u32 timeout_ms;
	char name[SCX_OPS_NAME_LEN];
};

sched_ext调度类的调度过程为：

1）当任务被唤醒，调用ops.select_cpu()获取cpu选择（并不是最终调度到的CPU），如果cpu在idle状态，则同时唤醒cpu。

2）一旦CPU被选中，调用ops.enqueue()入队。

sched_ext使用简单的FIFO队列，sched_ext中称为DSQ，队列分为两类：一类是全局队列SCX_DSQ_GLOBAL；一类是per-cpu的本地队列SCX_DSQ_LOCAL。默认情况下有一个SCX_DSQ_GLOBAL，每个cpu有一个SCX_DSQ_LOCAL。也可以通过scx_bpf_create_dsq()与scx_bpf_destroy_dsq()创建自定义的队列。
ops.enqueue可以立即将任务通过helper函数scx_bpf_dispatch()加入到SCX_DSQ_GLOBAL或SCX_DSQ_LOCAL；也可以通过指定DSQ的ID，将其加入到自定义的队列中；或者是在BPF程序中进行排队（下面的qmap例子中就是这种情况）。

3）当CPU准备好进行调度，会先从它的SCX_DSQ_LOCAL中获取任务，如果SCX_DSQ_LOCAL为空，则从SCX_DSQ_GLOBAL中获取任务。如果还是没有可执行的任务，就会调用ops.dispatch()。ops.dispatch()可以使用如下的helper函数，为local DSQ生成任务：

scx_bpf_dispatch()将一个任务分配到DSQ中，可以是任意的DSQ（SCX_DSQ_LOCAL, SCX_DSQ_LOCAL_ON | cpu, SCX_DSQ_GLOBAL或者自定义DSQ）。任务的分配不是立即生效的，最多会有ops.dispatch_max_batch个待分配的任务。
scx_bpf_consume() 将一个任务从non-local DSQ转移到调度的DSQ中。

4）调用ops.dispatch()后，如果SCX_DSQ_LOCAL中存在任务，则运行。如果为空，则依次执行：

从SCX_DSQ_GLOBAL中获取任务
如果ops.dispatch()已经进行相应的分配，则重复步骤3
如果之前的任务为SCX的任务，且可运行，则运行之前的任务
idle

tools/sched_ext/下有大量用例，其中scx_example_qmap[.bpf].c使用BPF_MAP_TYPE_QUEUE实现了五个FIFO的调度，按照“先调度1个queue0上的任务，再调度2个queue1上的任务，再调度4个queue2上的任务，依次类推”的方式进行调度，下面介绍下是如何实现的。

当进程被唤醒时，调用enqueue()将进程加入ebpf map中排队

// qmap的enqueue实现
void BPF_STRUCT_OPS(qmap_enqueue, struct task_struct *p, u64 enq_flags)
{
	static u32 user_cnt, kernel_cnt;
	struct task_ctx *tctx;
	u32 pid = p->pid;
	// 进程的scx权重，亦是fifo队列的序号
	int idx = weight_to_idx(p->scx.weight);
	void *ring;
	
	...

	// queue_arr是一个BPF_MAP_TYPE_ARRAY_OF_MAPS类型的map，存储了5个BPF_MAP_TYPE_QUEUE，作为5个fifo调度队列
	ring = bpf_map_lookup_elem(&queue_arr, &idx);
	if (!ring) {
		scx_bpf_error("failed to find ring %d", idx);
		return;
	}

	// 将任务push到fifo队列中，如果队列满了，就直接扔到SCX_DSQ_GLOBAL中
	if (bpf_map_push_elem(ring, &pid, 0)) {
		scx_bpf_dispatch(p, SCX_DSQ_GLOBAL, slice_ns, enq_flags);
		return;
	}

	__sync_fetch_and_add(&nr_enqueued, 1);
}

当CPU从SCX_DSQ_LOCAL、SCX_DSQ_GLOBAL获取不到任务后，调用dispatch()重新获取任务

// qmap的dispatch实现
void BPF_STRUCT_OPS(qmap_dispatch, s32 cpu, struct task_struct *prev)
{
	...
	// idx是fifo的序号，cnt记录对应fifo还能调度多少个任务，两者保存在BPF_MAP_TYPE_PERCPU_ARRAY中
	u64 *idx = bpf_map_lookup_elem(&dispatch_idx_cnt, &zero);
	u64 *cnt = bpf_map_lookup_elem(&dispatch_idx_cnt, &one);
	...

	// 循环5个fifo，获取需要调度的任务
	for (i = 0; i < 5; i++) {
		// cnt非正，则继续调度下一个fifo
		if (!*cnt) {
			*idx = (*idx + 1) % 5;
			*cnt = 1 << *idx;
		}
		(*cnt)--;

		// 查找到对应的fifo
		fifo = bpf_map_lookup_elem(&queue_arr, idx);
		if (!fifo) {
			scx_bpf_error("failed to find ring %llu", *idx);
			return;
		}

		// 从fifo中获取对应的任务pid
		if (!bpf_map_pop_elem(fifo, &pid)) {
			struct task_struct *p;

			// bpf_task_from_pid是一个helper函数，根据pid获取对应的task_struct，获取到就进行调度，否则尝试下一个fifo
			p = bpf_task_from_pid(pid);
			if (p) {
				update_core_sched_head_seq(p);
				__sync_fetch_and_add(&nr_dispatched, 1);
				// 通过helper函数scx_bpf_dispatch，将任务推到SCX_DSQ_GLOBAL调度队列中，后续待CPU调度完SCX_DSQ_LOCAL后，从中拿出运行
				scx_bpf_dispatch(p, SCX_DSQ_GLOBAL, slice_ns, 0);
				// 释放task_struct的引用
				bpf_task_release(p);
				return;
			}
		}

		*cnt = 0;
	}
}

qmap实现的功能不止这些，还实现了core-sched的支持、高优先级调度类的抢占、对每第n个任务进行暂停等，在scx_example_qmap.bpf.c的头部注释里有介绍，实现在其他的struct sched_ext_ops方法中。

其他

在LCP 2021，Google有分享过eBPF in CPU Scheduler。主要包括三方面：

1、通过对sched_switch与sched_wakeup的Trace，来获取调度延迟数据，并指导调度
2、Core scheduling中为防止Cross-HT attack，会进行forced idle。通过eBPF统计forced idle的时间。
3、针对Google自己的调度系统ghOST，通过eBPF减少调度延迟。ghOST的目标与sched_ext类似，也是提供一种可开发、易部署的调度器开发框架，但ghOST将调度代码运行在用户空间，而非内核空间。

除此外，在在离线混部的场景下，也能通过eBPF监控调度，检测应用的干扰。比如阿里的开源混部项目koordinator也有这样的方案。

linux

BPF

转载请注明出处

AF_XDP的原理与应用上一篇

KPNG：下一代Kube-Proxy 下一篇

eBPF在CPU调度上的应用

调度器简介

BPF_PROG_TYPE_SCHED类型的BPF程序

sched_ext调度类

其他

`BPF_PROG_TYPE_SCHED`类型的BPF程序

`sched_ext`调度类