← 記事一覧

scx_simple

sched_extのサンプルスケジューラscx_simpleを読み、CPU選択・キュー操作・実行時間の扱いを整理したノートです。

目次

sched_ext

  • ./tools/sched_ext/*.bpf.cにBPFの実装がある。
  • *.cはユーザー空間のローダーであり、中にはロジック本体を担うやつもありそう

scx_simple.bpf.c

  • this scheduler should work reasonably well on CPUs with a uniform L3 cache topology

  • 私が使ってるRyzen 9 9955HXでは、CCD(Core Complex Die)が二つあるので、scx_simpleは適してないかも。Ryzen 9 9955HXのlstopo

  • scx_simpleのハンドラ. 必須なのは.nameのみであり、そのほかは欠けている場合にはscxのデフォルト実装が利用される。

SCX_OPS_DEFINE(simple_ops,
	       .select_cpu		= (void *)simple_select_cpu,
	       .enqueue			= (void *)simple_enqueue,
	       .dispatch		= (void *)simple_dispatch,
	       .running			= (void *)simple_running,
	       .stopping		= (void *)simple_stopping,
	       .enable			= (void *)simple_enable,
	       .init			= (void *)simple_init,
	       .exit			= (void *)simple_exit,
	       .name			= "simple");
  • simple_select_cpu
    • scx_bpf_select_cpu_dfl()はidleCPUがなかったらprev_cpuを返す
    • idle CPUがある場合には、そのCPUのlocal DSQに直接enqueueする
    • idle CPUがない場合には、scx coreへのヒントとしてcpu(prev_cpu)を返す
s32 BPF_STRUCT_OPS(simple_select_cpu, struct task_struct *p, s32 prev_cpu, u64 wake_flags)
{
	bool is_idle = false;
	s32 cpu;

	cpu = scx_bpf_select_cpu_dfl(p, prev_cpu, wake_flags, &is_idle);
	if (is_idle) {
		stat_inc(0);	/* count local queueing */
		scx_bpf_dsq_insert(p, SCX_DSQ_LOCAL, SCX_SLICE_DFL, 0);
	}

	return cpu;
}
  • simple_enqueue
    • fifoの場合: 何もせず独自global DSQにenqueueする
    • vtime考慮の場合: vtimeを設定した上で独自global DSQにenqueueする
      • なお、vtime(これまで消費した重みつきCPU時間)が短いほど優先される。
        • vtimeの初期値は、task生成時のvtime_nowであり、これは相対的な値
      • vtimeをkeyとしてpriority queue(rb tree)で管理されている
      • この時、vtimeが他のタスクと比べてSCX_SLICE_DFL以上に短い場合には、vtimeの差が SCX_SLICE_DFLとなるように、vtimeを増やす。つまり、次回以降に必要以上にスケジュールされやすくするのを防ぐ
      • sleepしてた状態のタスクが貯金できる予算を1 slice分に制限する
void BPF_STRUCT_OPS(simple_enqueue, struct task_struct *p, u64 enq_flags)
{
	stat_inc(1);	/* count global queueing */

	if (fifo_sched) {
		scx_bpf_dsq_insert(p, SHARED_DSQ, SCX_SLICE_DFL, enq_flags);
	} else {
		u64 vtime = p->scx.dsq_vtime;

		/*
		 * Limit the amount of budget that an idling task can accumulate
		 * to one slice.
		 */
		if (time_before(vtime, vtime_now - SCX_SLICE_DFL))
			vtime = vtime_now - SCX_SLICE_DFL;

		scx_bpf_dsq_insert_vtime(p, SHARED_DSQ, SCX_SLICE_DFL, vtime,
					 enq_flags);
	}
}
  • simple_dispatch
    • dispatchをcallしたCPUのlocal DSQに、独自 global DSQ からタスクを一つ移動させる
void BPF_STRUCT_OPS(simple_dispatch, s32 cpu, struct task_struct *prev)
{
	scx_bpf_dsq_move_to_local(SHARED_DSQ);
}
  • simple_running
    • taskがCPUで実行され始めた時に実行される
    • taskのvtimeがvtime_now(global variable)より大きい場合には、vtime_nowを更新する
    • fifoの場合には何もしない
void BPF_STRUCT_OPS(simple_running, struct task_struct *p)
{
	if (fifo_sched)
		return;

	/*
	 * Global vtime always progresses forward as tasks start executing. The
	 * test and update can be performed concurrently from multiple CPUs and
	 * thus racy. Any error should be contained and temporary. Let's just
	 * live with it.
	 */
	if (time_before(vtime_now, p->scx.dsq_vtime))
		vtime_now = p->scx.dsq_vtime;
}
  • simple_stopping
    • taskがCPUから剥がれた時に実行される
    • vtimeを加算する処理を行う。scx.sliceは残りのtime slice
      • デフォルトではscx.sliceは0なので、頻繁にyieldするタスクに不利
    • fifoの場合には何もしない
void BPF_STRUCT_OPS(simple_stopping, struct task_struct *p, bool runnable)
{
	if (fifo_sched)
		return;

	/*
	 * Scale the execution time by the inverse of the weight and charge.
	 *
	 * Note that the default yield implementation yields by setting
	 * @p->scx.slice to zero and the following would treat the yielding task
	 * as if it has consumed all its slice. If this penalizes yielding tasks
	 * too much, determine the execution time by taking explicit timestamps
	 * instead of depending on @p->scx.slice.
	 */
	p->scx.dsq_vtime += (SCX_SLICE_DFL - p->scx.slice) * 100 / p->scx.weight;
}
  • simple_enable
    • タスクがsched_extの管理下にはいる時に実行される
      • 新しいタスクが生成された時
void BPF_STRUCT_OPS(simple_enable, struct task_struct *p)
{
	p->scx.dsq_vtime = vtime_now;
}
  • simple_init
    • scx scheduler登録時に実行される
    • scx_simple専用の独自DSQを作る
s32 BPF_STRUCT_OPS_SLEEPABLE(simple_init)
{
	return scx_bpf_create_dsq(SHARED_DSQ, -1);
}
  • simple_exit
    • scx scheduler登録解除時に実行される
    • UEIはUser Exit Info らしい。
      • scx schedulerが終了した理由をuserspaceに伝えるための仕組み
    • userspaceからはueiをBPF Map経由で読める
void BPF_STRUCT_OPS(simple_exit, struct scx_exit_info *ei)
{
	UEI_RECORD(uei, ei);
}

#define UEI_DEFINE(__name)							\
	char RESIZABLE_ARRAY(data, __name##_dump);				\
	const volatile u32 __name##_dump_len;					\
	struct user_exit_info __name SEC(".data")

#define UEI_RECORD(__uei_name, __ei) ({						\
	bpf_probe_read_kernel_str(__uei_name.reason,				\
				  sizeof(__uei_name.reason), (__ei)->reason);	\
	bpf_probe_read_kernel_str(__uei_name.msg,				\
				  sizeof(__uei_name.msg), (__ei)->msg);		\
	bpf_probe_read_kernel_str(__uei_name##_dump,				\
				  __uei_name##_dump_len, (__ei)->dump);		\
	if (bpf_core_field_exists((__ei)->exit_code))				\
		__uei_name.exit_code = (__ei)->exit_code;			\
	/* use __sync to force memory barrier */				\
	__sync_val_compare_and_swap(&__uei_name.kind, __uei_name.kind,		\
				    (__ei)->kind);				\
})

Appendix