# sched_ext(6) : kernel branch breakdown
## Overview
sched_ext kernel branch 提供給 scx 一個完整的 bpf 介面得以讓使用者利用 scx 撰寫自己的排程器，相較於將完整排程策略實作在 kernel space 當中， sched_ext 僅僅是提供一個雛形，有預設的排程策略，但實際上會利用 scx 載入的排程器。同時 EXT scheduling class 的優先權和 fair class 是相同的。
## Related files
* [/tools/sched_ext/](https://)
* [/tools/testing/selftests/sched_ext/]()
* [/kernel/sched/ext.c]()
* [/kernel/sched/ext.h]()
## Big picture of Linux schedulers
建議可以先看 [sched_ext: scheduler architecture and interfaces (Part 2)](https://blogs.igalia.com/changwoo/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](https://) 定義了 `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](https://github.com/sched-ext/sched_ext/commit/5052bb0c352d7a4b78c665969a533639d9773562) ，當中敘述了 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 幾個重點改動的程式碼包括以下
* [include/linux/sched.h]() 當中的 `task_struct` 新增一個成員 `struct sched_ext_entity scx;`
* [include/uapi/linux/sched.h]() 當中定義一個 scheduling class `SCHED_EXT` 對應的數字為 7 。
* [init/init_task.c]() 當中的 `init_task` 新增成員 `scx` 的初始化。
* [kernel/bpf/bpf_struct_ops_types.h]() 當中定義 `BPF_STRUCT_OPS_TYPE(sched_ext_ops)` 。
* [kernel/sched/core.c]() 當中進行 p->scx
的初始化。以及在 `sched_fork(), __setscheduler_prio()` 判斷 `task_on_scx(p)` 是否成立。
* [kernel/sched/debug.c]() 當中定義 sched_ext 的 debugfs 。
最關鍵的檔案有數個，包括 [kernel/sched/ext.h](https://), [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 更動的。
:::warning
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` 結構體的指標。
:::warning
`struct rq` 和 `struct scx_dispatch_q` 的作用差別在哪？為何要有兩種不同 queue 的實作？
查閱 [kernel/sched/sche.h](https://) ，原本的 `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](https://) 當中所定義的 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)` 。
:::warning
此處有提及呼叫 `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 。
:::warning
`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 。
:::warning
為何只有 `!is_local` 情境才要使用 spinlock ？
:::
若 DSQ 使用 priority ordering ，則會進行對應紅黑樹操作，首先找出任務 `p` 在紅黑樹當中的前一個節點 (透過 `rb_prev()`) ，然後把 `p->scx.dsq_node` 加入在該節點鍵結串列前方。
:::info
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](https://elixir.bootlin.com/linux/latest/source/kernel/sched/psi.c)
接著若 `sched_class` 是 `scx` 則會對應到 ext.c 當中的 `dequeue_task_scx()` 。此處主要行為會將原本在 `rq` 上處於 `running` 的任務 dequeue 並停止運行，同時我們希望 running <-> stopping 的狀態轉移被包含在 runnable <-> quiescent 過程之中，
:::warning
在 core.c 當中透過 `DEFINE_STATIC_KEY_FALSE(sched_uclamp_used)` 定義一個 static key ，什麼是 static key ? 此處的用意是為了減少 fast path 當中 uclamp overhead 。什麼是 uclamp ?
:::
:::warning
此處和 enqueue path 當中都會針對 `rq->scx.nr_running` 進行加一的操作，之後再呼叫 `sub_nr_running(1)/add_nr_running(1)` 更新原本 `rq` 的資料，猜測是開發者不想過度改動 [kernel/sched/sched.h](https://) 的取捨，否則此操作應包含在同一函式當中。
:::
最後呼叫 `dispatch_dequeue()` 函式來完成 dequeue path ，注意該函式的 signature 如下
```c
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` 。
:::warning
此處註解說由於持有 `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` ，實作簡潔如下
```c
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 架構下的實作如下
```c
#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()` ，可以先看到該函式實作
```c
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`
```c
/* 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 上運行。
:::warning
此處讓我發現 iterator 和透過迴圈走訪，看似相似但實際上是不同的行為。
:::
:::warning
任務 `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](https://) 可見到此結構體的定義
```c
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](https://elixir.bootlin.com/linux/latest/source/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 上。參數原型如下
```c
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)` 。
Sign in with Wallet
Connect another wallet