Try   HackMD

sched_ext(6) : kernel branch breakdown

Overview

sched_ext kernel branch 提供給 scx 一個完整的 bpf 介面得以讓使用者利用 scx 撰寫自己的排程器，相較於將完整排程策略實作在 kernel space 當中， sched_ext 僅僅是提供一個雛形，有預設的排程策略，但實際上會利用 scx 載入的排程器。同時 EXT scheduling class 的優先權和 fair class 是相同的。

Big picture of Linux schedulers

建議可以先看 sched_ext: scheduler architecture and interfaces (Part 2) ，這是 sched_ext 團隊當中開發者之一 ChangWoo Min 所撰寫的文章，對於了解整體架構有很大幫助。

Linux schedulers 主要由兩個部分組成

  • Core kernel scheduler ( core.c )
    定義了所有 scheduling policies 的共通行為，例如定義了發生 timer interrupt 時排程器該做什麼事。
  • Concrete scheduling policies
    定義在 core kernel scheduler 之上，例如 rt.c 、 fair.c 等等。

VFS 和 scheduling class 的差異

實作一個新的 scheduling class 和 VFS 十分類似，都會使用一個共同的介面並讓 core scheduler 進行呼叫，不過背後的概念有差異。

VFS 重點是在如何切割 disk space ，使得數個不同的檔案系統可以同時存在，並且分配到的 disk space 互不交集。而 scheduling 則是專注在如果切割並使用 CPU time ，意思是在某個特定的時間點，只有一個 scheduling policy 可以進行排程。這也是為什麼 scheduling policies 有 hierarchy 的結構。

Interface

sched_ext scheduler 由四個部分組成，由下而上分別是

  1. core kernel scheduler
  2. sched_ext framework
  3. BPF scheduler
  4. BPF's user-space counterpart

以下我們逐一探討每層之間是怎麼互動的，首先是 core kernel scheduler 與 scheduler class 之間的互動。 core kernel scheduler 在 kernel/sched/sched.h 定義了 struct sched_class 此結構，裡面充滿了 function pointers 來作為其他 scheduling class 要實作的介面。 core kernel scheduler 要進行某項操作時就會呼叫對應函式，而根據該時間點是哪個 scheduling class 負責排程，呼叫的 function pointer 就會指向該 scheduling class 實作的函式。

而 sched_ext framework 就是一個新的 scheduling class 。

再來討論 sched_ext framework 如何跟 BPF scheduler 溝通，此處我們可以從將 runnable task 放進 run queue 當中的過程來解析，首先 core kernel scheduler 會呼叫 sched_class.enqueue_task() ，對應到的即是 enqueue_task_scx() 。

Concepts

第一個 commit 為 commit 5052bb0 ，當中敘述了 sched_ext 本來實作的用途，主要有三點

  • 讓排程器實作以及實驗的過程簡化並加速，使得排程策略的演進得以更快速
  • 為不同需求客製化的排程器
  • 加速排程器在 production 環境部署的速度

透過實作一個新的 scheduling class 稱為 SCX ，加上 BPF 的 struct_ops 來定義排程器的 callback functions 。該 class 定義的 struct_ops 稱為 sched_ext_ops 概念上和 struct sched_class 類似。此 kernel branch 實作的目地是將複雜的 sched_class callbacks 映射到簡單的 sched_ext_ops callbacks 。

這個 patch 主要是實作 core framework ，之後還有數個 patch 是用來調校效能或者提供 cgroup 排程功能，有幾個點值得注意

  • 在 sched_ext_ops 當中只有 .name 成員為必要的，其他 operation 都是可自行選擇是否實作，若沒有實作則有預設行為替代
  • 定義一個新的 policy constant SCHED_EXT ，任務可以透過 sched_setscheduler(2) 與該 policy constant 來使用 sched_ext 的功能。但如果 BPF scheduler 並未被載入，則 SCHED_EXT 和 SCHED_NORMAL 是相同的。
  • 為了將 sched_ext_ops callbacks 和 scheduler core 串接在一起，透過 FIFO 的 dispatch queues ，預設上有一個 global dsq (SCX_DSQ_GLOBAL) 以及 per-CPU dsq (SCX_DSQ_LOCAL) ，在排程策略實作當中 SCX_DSQ_GLOBAL 不一定需要被使用，而 SCX_DSQ_LOCAL 當中若有任務則 sched_ext 會從當中抽取任務出來執行。 BPF scheduler 可以透過 scx_bpf_create_dsq() 和 scx_bpf_destroy_dsq() 來管理任意數目的 dsq 。
  • 保證系統 integrity ，透過利用 p->scx.ops_state 追蹤每個任務的 ownership 並且所有任務都會被放在 scx_tasks list 上，若排程器被移除則所有任務會被放回 CFS 。詳細可見 p->scx.ops_state 和 scx_tasks 。
  • enable path 在沒有任何 blocking 的情況下將所有任務轉為 sched_ext 可排程的任務，以避免 partially switched state 可能造成的問題。 disable path 同樣不能信任 BPF scheduler ，所以他也需要保證任務的進展沒有 blocking 。詳細可見 scx_ops_enable() 和 scx_ops_disable_workfn() 。若 sched_ext 被取消，則 static_branches 可以用來從 hot paths 把所有 entry points 關閉。
  • scx_bpf_get_idle_cpumask() 和相關函式都可以被 BPF scheduler 使用，使得排程器可以透過 generic helpers 使用 idle masks 。
  • p->scx.kf_mask 是用來追蹤並允許哪些 kernel function helpers 是可用的。 init/exit sequences 保證某些 kfunc 不管在 BPF scheduler 的哪種狀態都可以安全地被呼叫。
  • SCHED_CHANGE_BLOCK()
  • 在 Uni-Processor 架構中， put_prev_task_scx()/pick_next_task_scx() 在必要時都會呼叫 balance_scx() 。要在 put_prev_task_scx() 當中判斷是否該呼叫 balance_scx() 則是透過 SCX_TASK_DEQD_FOR_SLEEP ，可以閱讀 put_prev_task_scx() 的 comment 。
  • SCX_CALL_OP*() 是我們在使用 scx_ops 操作時應該呼叫的。
  • scx_bpf_dispatch(), scx_bpf_pick_idle_cpu(), scx_bpf_task_running(), scx_bpf_task_cpu() 都利用 KF_RCU 使得排程器更容易呼叫他們。
  • move_task_to_local_dsq() 透過 rq->scx.extra_enq_flags 來攜帶 enqueue flags 。
  • ops.set_weight() 使得 BPF scheduler 可以追蹤 weight changes 而不需要在 p->scx.weight 上進行 polling 。

該 patch 幾個重點改動的程式碼包括以下

最關鍵的檔案有數個，包括 kernel/sched/ext.h, kernel/sched/ext.c, include/linux/sched/ext.h ，尤其在 kernel/sched 底下的各個目錄幾乎都有進行改動來使 sched_ext 運作。

其中可以特別注意 dsq 也就是 struct scx_dispatch_q 以及 struct sched_ext_entity ， 後者會被遷入在 task_struct 當中使得系統中的任務可以被 BPF scheduler 進行排程，當中 slice, dsq_vtime, disallow 成員皆是可以被 BPF scheduler 更動的。

BPF scheduler 當中經常實作自己的 task context ，很少直接利用 struct task_struct ，為何如此？是因為 task_struct 的 memory footage 太大嗎？

並且任務的 ownership 會在 SCX core 和 BPF scheduler 之間轉移，因此利用 sched_ext_entity->ops_state 來追蹤任務的 ownership ，定義在 kernel/sched/ext.c 當中，主要有四種狀態分別是 SCX_OPSS_NONE, SCX_OPSS_QUEUEING, SCX_OPSS_QUEUED, SCX_OPSS_DISPATCHING 。

struct scx_dsp_ctx 當中有 struct rq 結構體的指標。

struct rq 和 struct scx_dispatch_q 的作用差別在哪？為何要有兩種不同 queue 的實作？

查閱 kernel/sched/sche.h ，原本的 struct rq 多了一個成員 struct scx_rq scx ，該結構體定義在同一個檔案當中，特別的是成員多數和原本 struct rq 重複，目前認為可能是開發者認為原本 rq 結構過大且多數成員為 scx 不需要的，因此抽離一個結構體實作。
原本的 rq 依然保存是為了符合 core scheduling 的 scheduling class interface 實作。

同時因為任務依舊被原先的 rq 給紀錄，因此 PELT 等機制才能順利運行。

(TODO: 詳細解析 rq 、 dsq 等結構體之關係， dsq 在 sched_ext 之中扮演舉足輕重的角色，許多函式和它都直接相關)

另外在 kernel/sched/ext.c 當中所定義的 scheduling class ext 是將 sched_ext 和 core scheduling 串接在一起的介面，多數的操作都有實作除了以下幾個

  • wakeup_preempt : 此函式在 ext 當中的實作為 NOOP ，由於在該時間點任務並沒有被綁定在任何 CPU 上。 Preemption 的實作方式是將 task 的 time slice 設為 0 藉此觸發目標 CPU 的 reschedule 。
  • migrate_task_rq : 由於任務和 CPU 之間的映射關係是短暫的，所以沒必要
  • task_fork/dead : 直接使用 core sched 的方法。
  • task_woken : 不需要。

特別注意 dispatch path 和 enqueue path
(TODO: 解析 dispatch path 和 enqueue path )

enqueue path

在 ext 當中的 enqueue path 由 core sched 當中呼叫 p->sched_class->enqueue_task 來觸發，呼叫的時機點有數個（此處我不了解 core sched 當中呼叫 enqueue_task 的理由，應再持續探討）。對應到 ext.c 當中的 enqueue_task_scx() ，首先取得任務的 sticky_cpu ，若 enq_flags 的 ENQUEUE_RESTORE 有被設定且 task_current(rq, q) ，則將 sticky_cpu 設為當前 rq 的 CPU 。若 SCX_TASK_QUEUED 已經被設定則直接回傳，沒有的話就將 task 狀態變更為 runnable 並且設定 enq_flags 當中的 SCX_TASK_QUEUED ，此時若開發者有實作 scx_runnable 就執行它，接著若 SCX_ENQ_WAKEUP 有被設定則呼叫 touch_core_sched(rq, q) ，最後才執行 do_enqueue_task(rq, p, enq_flags, sticky_cpu) 。

我認為需要特別探討 touch_core_sched(rq, q) 的作用，它是用來更新 core scheduling 當中決定 task ordering 的 timestamp 。會更新 p->scx.core_sched_at ，該成員會在 scx_prio_less() 當中被使用來進行 core scheduling 當中 global 或 local-DSQ 的 FIFO ordering 。呼叫時機是在任務狀態變為 runnable 時或者它用完它在當前 CPU 上的 timeslice 。
實作當中會先判斷 sched_core_disabled() 是否成立，若否才將 p->scx.core_sched_at 更新為 rq_clock_task(rq) 。

此處有提及呼叫 sched_core_disabled() 成本相較呼叫 sched_core_enabled() 還要小，詳細可以參考兩函式實作。但這兩個函式依舊都有用到，這兩個邏輯上是否剛好相反？

接下來探討 do_enqueue_task() 的實作，若 sticky_cpu == cpu_of(rq) 也就是在 enqueue_task_scx() 當中 enq_flags 的 ENQUEUE_RESTORE 有被設定的情況，則直接進行 dispatch_enqueue(&rq->scx.local_dsq, p, enq_flags) 。

若 !scx_rq_online() 則直接呼叫 touch_core_sched() 並將任務的 timeslice 變更為 SCX_SLICE_DFL ，代表當前的 slice 已經結束。之後判斷 scx_ops_bypassing() 是否成立，若是則直接分配給 local DSQ 或 global DSQ 。

之後若 p->scx.ddsp_dsq_id != SCX_DSQ_INVALID 成立，則直接進行 direct_dispatch(p, enq_flags) 。（為何？）

若上述的情況都沒有發生，才會將任務 enqueue 到 BPF scheduler 上，使用 BPF scheduler 實作的 enqueue method 。

static_branch_unlikely() 和 unlikely() 差異在哪？

dispatch_enqueue()

判斷參數當中的 dsq 是否和 SCX_DSQ_LOCAL 相同，若相同則 is_local 被設置為 true 。若非 is_local ，則先檢查 dsq->id 是否無效，以此決定是否將 dsq 轉為 global dsq 。

接下來檢查是否有人將 vtime ordering 套用在 built-in dsq 當中，若有則觸發 error 並將 enq_flags 的 SCX_ENQ_DSQ_PRIO 取消。此處的註解有寫 SCX_DSQ_LOCAL 和 SCX_DSQ_GLOBAL 只會從他們各自的 FIFO queues 當中進行 consume ，因此我們禁止 internal DSQs 使用 vtime ordering 或任何 priority ordering 。

為何只有 !is_local 情境才要使用 spinlock ？

若 DSQ 使用 priority ordering ，則會進行對應紅黑樹操作，首先找出任務 p 在紅黑樹當中的前一個節點 (透過 rb_prev()) ，然後把 p->scx.dsq_node 加入在該節點鍵結串列前方。

DSQ 是鍵節串列， rq 是紅黑樹。

最後是從當前狀態轉移出去，利用 atomic_long_set_release() 來呼應 waiter 的 load_acquire() 操作。最後若 is_local 成立，找出 dsq 對應的 rq 並把 rq->curr->scx.slice 設為 0 表示讓出該 CPU 並將 preempt 設為 true 。

若 preempt || sched_class_above(&ext_sched_class, rq->curr->sched_class) 則觸發 resched_curr(rq) 。

dequeue path

core schedule 當中的函式 dequeue_task() 會觸發 dequeue 流程，首先若 core scheduling 是被啟動的話則呼叫 sched_core_dequeue() ，該函式第一件事就是檢查對應任務是否已經被 enqueued ，透過檢查它的 core_node 是否在紅黑樹上可以知道。若在的話則把它拔除。
接著若符合特定條件，則將 rq 對應之 CPU 上最後一個任務搬遷，之後把該 CPU 強制 idle ，呼叫 resched_curr(rq) 。此處我不理解註解所述

Reschedule to create an accounting edge for forced idle, and re-examine whether the core is still in forced idle state.

接著若 flags & DEQUEUE_CLOCK 沒被設定，則更新指定 rq 的 clock 。若 flag & DEQUEUE_SAVE 沒被設定，則更新排程資訊與呼叫 psi_dequeue() 。 PSI 的詳細概念我不懂，應再詳細探討。 kernel/sched/psi.c

接著若 sched_class 是 scx 則會對應到 ext.c 當中的 dequeue_task_scx() 。此處主要行為會將原本在 rq 上處於 running 的任務 dequeue 並停止運行，同時我們希望 running <-> stopping 的狀態轉移被包含在 runnable <-> quiescent 過程之中，

在 core.c 當中透過 DEFINE_STATIC_KEY_FALSE(sched_uclamp_used) 定義一個 static key ，什麼是 static key ? 此處的用意是為了減少 fast path 當中 uclamp overhead 。什麼是 uclamp ?

此處和 enqueue path 當中都會針對 rq->scx.nr_running 進行加一的操作，之後再呼叫 sub_nr_running(1)/add_nr_running(1) 更新原本 rq 的資料，猜測是開發者不想過度改動 kernel/sched/sched.h 的取捨，否則此操作應包含在同一函式當中。

最後呼叫 dispatch_dequeue() 函式來完成 dequeue path ，注意該函式的 signature 如下

static void dispatch_dequeue(struct rq *rq, struct task_struct *p)

當中做的第一件事是判斷任務 p 被放置的 dsq 是否和 rq 當中包含的 dsq 相同，若相同則 is_local 變數會被設為 true 。若此任務 p 是直接從 BPF scheduler 派發到 local dsq 中，則目前 p 還沒被放置到任何 dsq 上，檢查並確保 p->scx.holding_cpu 被設置為 -1 即可回傳。

若 is_local 不成立，會嘗試獲取 dsq->lock 該 raw spin lock ，之後同樣檢查 p->scx.holding_cpu 的值並確保它為 -1 ，同時將任務從 dsq 中移除。最後清空 p->scx.dsq 。

此處註解說由於持有 dsq->lock ，因此 p->holding_cpu 和 p->scx.dsq_node 都不該被改變，但函式當中的行為明顯是在改變這兩個變數的值或成員，為何如此？

(TODO: 解析 dispatch_to_local_dsq() ，該函式和 dispath_dequeue() 會出現競爭關係)

yield_task_scx

ext scheduling class 的 yield_task 函式實作是 yield_task_scx ，實作簡潔如下

static void yield_task_scx(struct rq *rq)
{
	struct task_struct *p = rq->curr;

	if (SCX_HAS_OP(yield))
		SCX_CALL_OP_2TASKS_RET(SCX_KF_REST, yield, p, NULL);
	else
		p->scx.slice = 0;
}

透過 rq->curr 獲取當前任務，之後若 BPF scheduler 有實作 yield 函式，則呼叫它，若無則將該任務 scx 的 slice 設為 0。

至於 yield_to_task_scx 預設行為是直接回傳 false 。

pick_next_task_scx

相當有趣的函式，若是 UP 架構下的實作如下

#ifndef CONFIG_SMP
	/* UP workaround - see the comment at the head of put_prev_task_scx() */
	if (unlikely(rq->curr->sched_class != &ext_sched_class))
		balance_scx(rq, rq->curr, NULL);
#endif

若當前任務的 scheduling class 不屬於 ext scheduling class 則執行 balance_scx 。要理解此處的實作要先了解 put_prev_task_scx() 。

由於 ext scheduling class 會在 dispatch 時將任務在 CPU 之間轉移，而 dispatch 由 balance operation 來執行，但在 UP 當中不會呼叫 balance operation 。我們可以在 put_prev_task_scx() 之後的操作當中呼叫 balance operation 。有兩種情況

  1. 若前一個任務在 ext scheduling class 當中，則 pick_next_task() 之後會立即呼叫 put_prev_task() 。同時間 put_prev_task() 可能在其他地方也被呼叫，我們可以透過區分 previous task 的 state 來區分 caller 的不同。若它的 state 依然為 queued 或 dequeued with SCX_DEQ_SLEEP ，則 caller 即是 pick_next_task() ，則 balance operation 會在此函式（ put_prev_task() ） 當中被呼叫。
  2. 若前一個 task 並非 ext scheduling class ，則接下來第一個呼叫的函式一定是 pick_next_task() ，因此在該函式當中呼叫 balance operation 。

此處我們無法將兩個 case 合為一個是因為若 previous task 是 ext scheduling class ，則它必須走完整個 put_prev_task_scx() 。

回到解析 pick_next_task_scx() ，若是 SMP 架構則先透過 first_local_task() 取得 rq 當中 local dsq 的第一個任務，之後透過 set_next_task_scx() 將該任務狀態更新（目前不確定是執行還是狀態更新，尚須探討）。
之後檢查確認任務的 time slice 非 0 後就回傳該任務。

put_prev_task_scx()

若在 SMP 架構底下，首先嘗試呼叫 ops->stopping ，接著若 caller 為 core scheduling 當中的 put_prev_task_balance() ，可以先看到該函式實作

static void put_prev_task_balance(struct rq *rq, struct task_struct *prev,
				  struct rq_flags *rf)
{
#ifdef CONFIG_SMP
	const struct sched_class *class;
	/*
	 * We must do the balancing pass before put_prev_task(), such
	 * that when we release the rq->lock the task is in the same
	 * state as before we took rq->lock.
	 *
	 * We can terminate the balance pass as soon as we know there is
	 * a runnable task of @class priority or higher.
	 */
	for_class_range(class, prev->sched_class, &idle_sched_class) {
		if (class->balance(rq, prev, rf))
			break;
	}
#endif

	put_prev_task(rq, prev);
}

在呼叫 class->balance() 時，實際對應到的是 balance_scx() ，因此由 balance_scx() 來決定任務 p 是否繼續執行，若是的話則將 p 設為 runnable 並且呼叫 dispatch_enqueue() 將任務 p 分配到 local dsq 上並回傳。上述都不成立的話則判斷任務的 flags 是否有設置 SCX_TASK_QUEUED ，成立則先將任務在該 rq 上設為 runnable ，並判斷任務 p 的 timeslice 是否大於零，若有則表示 p 可能被更高優先權的 scheduling class 給中斷或者有其他情況打斷它的執行，因此呼叫 dispatch_enqueue() 將 p 放在 local dsq 的最前端。

若 put_prev_task() 是在 pick_next_task() path 當中， balance_scx() 應當已經從 local dsq 取出可執行的任務，若 local dsq 為空則告訴 ops.enqueue() 任務 p 就是當前 CPU 唯一可執行的任務。此時 ops.enqueue() 應該將 p 放入 local dsq 當中以確保接下來的 pick_next_task_scx() 可以拿到任務。

balance_scx()

在 SMP 架構底下， core scheduling 呼叫 ext scheduling 的 balance operation 就會對應到此函式。首先函式會呼叫 balance_one(rq, prev, rf, true) ，在當中會確保 BPF scheduler 知道自己目前又取得 core 的控制權，因為有時前一個任務並非 ext scheduling class ，則轉移回來之後必須通知 BPF scheduler 。

若前一任務也是 ext scheduling class ，若該任務依舊有 time slice ，則直接回傳 true ，告訴 put_prev_task_scx() 將前一個任務放到 local dsq 上，不進行 balance 的動作否則只是增加 latency 。如果 BPF scheduler 想自行操控此處的行為則需要自己實作 ->cpu_released() option 。

當 core scheduling 對 remote CPU 進行平衡時，不會呼叫 put_prev_task_scx() 同時也不會設定 SCX_TASK_BAL_KEEP 的 flag ，之後該函式進行一系列檢查來確保 caller 的 rq 有任務可以運行（此處為推測，應深入探討）。

之後 balance_scx() 若是在 SMT 架構，則 core scheduling 呼叫完 balance operation 後緊接著就是 put_prev_task_scx() 和 pick_task_scx() 以及 SMT sibling 也會進行 pick_task_scx() ，因此對 sibling CPU 也進行平衡（利用 balance_one() ）。

balance_one()

若 scx_ops_cpu_preempt 和 rq 的 cpu_released 皆被設定為 true ，則代表該 CPU 前一個執行任務的 scheduling class 並非 ext scheduling class ，此時需要通知 BPF scheduler 它重新取得 CPU 的控制權。若前一任務本來就屬於 ext scheduling class ，則更新 rq 的 scx 相關數據，之後檢查前一任務是否還留有 time slice 能執行，有的話拿取更多新的任務只會增加 latency ，不如直接將前一任務透過 put_prev_task_scx() 放回 local dsq 當中。 BPF scheduler 可以透過實作 ->cpu_released() 來改變此處的行為。當對於一個 remote CPU 進行負載平衡時，不會有對應的 put_prev_task_scx() 同時 SCX_TASK_BAL_KEEP 也不會被設定。於是我們利用 pick_task_scx() 來進行相同的檢查並挑選 rq->curr 。

若該 rq 上的 local dsq 早已有任務在其中，或者從 global dsq 當中進行 consume_dispatch_q() 成功，則直接回傳。

若上述情況都沒發生，則會進入 dispatch loop ，此處是對於 BPF scheudler 十分重要的部分，有機會因此此處的行為簡化 BPF scheduler 的實作。

此處是利用 do while loop 來實作，會嘗試利用 ops.dispatch() 獲取可執行的任務，若依舊為空則重試。迴圈一開始先將 dspc->nr_tasks 設為 0 ，其中 dspc 為 struct scx_dsp_ctx ，該結構體定義如下，注意每個 CPU 都有一個自己的 struct scx_dsp_ctx

/* dispatch buf */
struct scx_dsp_buf_ent {
	struct task_struct	*task;
	unsigned long		qseq;
	u64			dsq_id;
	u64			enq_flags;
};

static u32 scx_dsp_max_batch;

struct scx_dsp_ctx {
	struct rq		*rq;
	struct rq_flags		*rf;
	u32			cursor;
	u32			nr_tasks;
	struct scx_dsp_buf_ent	buf[];
};

之後呼叫 BPF scheduler 實作的 dispatch method ，然後呼叫 flush_dispatch_buf ，此處可能會喪失 rq lock （為何？），因此 local dsq 在 dispatch 後依舊可能為空。之後同樣檢查 rq->scx.local_dsq.nr 是否有值，或能否從 global dsq 成功執行 consume_dispatch_q() ，若能則跳出迴圈並回傳 true 。由於排程過程有機會被卡死在這個迴圈當中，因此有設定一個 threshold 為 nr_loop ，當執行 nr_loop 次後會呼叫 scx_bpf_kick_cpu 並跳出迴圈嘗試重新執行一次排程過程。

consume_dispatch_q()

透過 nldsq_for_each_task 聚集走訪對應 dsq 上所有任務，若任務所屬的 rq 和傳入此函式的 rq 相同則代表該任務是 local 的，則呼叫 consume_local_task() ，若任務在其他 CPU 上，則先透過 task_can_run_on_remote_rq() 檢查任務能否在 remote CPU 上運行。

此處讓我發現 iterator 和透過迴圈走訪，看似相似但實際上是不同的行為。

任務 p 能否在特定 CPU 上執行由 p->cpus_ptr 來決定，那最初 p->cpus_ptr 如何設定？過程當中如何變更？

select_task_rq_scx()

若 wake_flags 當中的 WF_EXEC 被設置，代表任務 p 正在進行 exec(2) 的過程或者準備進行，此時若對 p 做 migration 非常好的時機，因為此時的 cache 和 memory footprint 非常小。若回傳和 prev_cpu 不同的 CPU 會立刻觸發 migration ，但在 ext scheduling class 當中當前任務處在哪個 rq 當中不代表該任務一定會在對應 CPU 上執行，因此回傳不同於 prev_cpu 的值不一定有效。

接著若 BPF scheduler 有實作 select_cpu 函式（通常都會實作），首先取得當前 CPU 的 direct_dispatch_task 指向的任務（應當沒有，若有則會觸發警告），之後將該任務指標指向 p 後再呼叫 select_cpu ，之後再將 direct_dispatch_task 設為 NULL 。（此處應該是有可能被其他函式打斷，應探討 direct_dispatch_task 之作用）。

若沒實作 select_cpu ， ext scheduling class 的預設行為是呼叫 scx_select_cpu_dfl() 來挑選 CPU 。

set_cpus_allowed_scx()

調整任務對應可用的 cpu set ，一開始設定是在 p->cpus_mask 當中，但當前有效的 cpu set 都是在 p->cpus_ptr ，這兩個值有可能暫時性的不同，永遠會告訴 BPF scheduler 有效值，因此是 p->cpus_ptr 。

此函式的其中一個參數型別為 struct affinity_context * ，參閱 kernel/sched/sched.h 可見到此結構體的定義

struct affinity_context {
	const struct cpumask *new_mask;
	struct cpumask *user_mask;
	unsigned int flags;
};

首先呼叫 core scheduling 當中的 set_cpus_allowed_common() ，關於該函式可以自行查閱 linux kernel source code ，在註解當中有寫到任何 scheduling class 的 set_cpus_allowed() 函式都需要執行該函式當中的行為，不管是否直接呼叫該函式。不外乎就是改變 p->cpus_ptr 和 p->cpus_mask 的值。另外會透過 cpumask_weight() 對任務 p 而言可用的 cpu 數量（此處可以深入探討實作細節）。

關於 bitmap weight 的計算，也就是 population count ，在之前作業有探討過，而在這邊的程式碼當中可以一路追朔到 include/asm-generic/bitops/const_hweight.h 當中的 __const_hweight8 。

pick_task_scx()

core scheduling 會在每個 SMT sibling 上呼叫此函式來決定要在 SMT siblings 上運行的任務。注意 balance_one() 也會在每個 SMT siblings 上被呼叫而 put_prev_task_scx() 只會在當前 CPU 上被呼叫。

由於其他 CPU 並沒有呼叫 put_prev_task_scx() ，因此不能直接挑選它們 local dsq 上的第一個任務，需要特別考慮 rq->curr 來模仿 SCX_TASK_BAL_KEEP 。

函式當中挑選 rq->curr 和 local dsq 的第一個任務來比較，首先確認 curr->scx.flags 當中的 SCX_TASK_QUEUED 是否被設定，若否則直接回傳 first 。

若有被設定則先確認 rq->curr 是否為唯一可以運行的任務，是的話直接回傳，不是的話則檢查 rq->curr 是否還有可運行的 time slice 並且 curr->scx.core_sched_at 應該在 first->scx.core_sched_at 之前，以上條件皆滿足則回傳 rq->curr 。

*_local_dsq 相關函式

move_to_local_dsq()

將一個任務從不同的 rq 搬到 local dsq 上。參數原型如下

static bool move_task_to_local_dsq(struct rq *rq, struct task_struct *p, u64 enq_flags)

共有三個參數， rq , p , enq_flags ，功能分別如下

  • rq : 要將任務搬移至的 rq ，必須為被鎖住的狀態
  • p : 要被搬移的任務

caller 需要做到以下的事

  1. 對於任務 p 需要有 exclusive access 也就是排他的存取權，不管是透過它的 dsq lock 還是利用 SCX_OPSS_DISPATCHING flags 。
  2. 將 p->scx.holding_cpu 設為 raw_smp_processor_id() 。
  3. 存取 task_rq(p) 後，釋放對於 p 的 exclusive access 以避免在 dequeue 時遇到 deadlock 。
  4. 將 rq 和步驟三取得的 task_rq 鎖住
  5. 最後呼叫此函式

回傳 true 代表成功將 p 移動至 rq 上，也有可能在 dequeue 當中的 racing 輸掉而回傳 false 。

在函式當中會檢查 p->scx.holding_cpu 和 raw_smp_processor_id() 是否相同，在該函式進行期間此函式不會改變 p->scx.holding_cpu 的值，因此若是這個比較是不相同的，代表此函式在 dequeue racing 當中輸了，直接回傳 false ，可以參照 dispatch_dequeue() 來詳細理解這部分。

只要 p->scx.holding_cpu 沒有改變，則 p 的 task_rq 不可能被改變，此時確認它是被鎖住的狀態並檢查 rq 代表的 CPU 是否在 p->cpus_ptr 當中，理應在其中。

之後呼叫 deactivate_task(task_rq, p, 0) ，其中會呼叫 dequeue_task(rq, p, flags) (作用尚須探討)。
一連串設定 flags 的操作後呼叫 activate_task(rq, p, 0) ，當中會呼叫 enqueue_task(rq, p, flags) 。

Last changed by 
 
I-HSIN Cheng
https://vax-r.github.io/
0
336

Read more

Rust learning note (2)

Rust 的錯誤大致分為兩種主要的種類， recoverable 和 unrecoverable ，對於 recoverable errors 例如找不到對應檔案，最有可能的處理方式是回報該問題並且重新嘗試該操作，對於 unrecoverable error 來說，那總是代表 bugs 的特徵，此情況會立即將程式停止。

Mar 1, 2025
Concurrency 學習筆記

電腦系統當中把排程任務的基本單元稱為行程，

Dec 20, 2024
eBPF and related tools

eBPF 和原先的 BPF 十分相似，特別的地方在於 eBPF map ，它是一種能夠儲存多種不同資料型態的資料結構，在當中每種不同資料型態被當成不同的二進位記憶體區塊

Nov 15, 2024
Control Groups 解說

官方的定義是 cgroup 將 tasks 集合映射到子系統 (subsystem) 的集合上。 subsystem

Sep 11, 2024
Read more from I-HSIN Cheng
Published on HackMD