# 2025q1 Homework1 (ideas)
contributed by < `liangchingyun` >

## Linux 排程器研究

## 改進 Linux 核心的 lib/list_sort.c

## 裝置驅動程式開發
### Linux 核心專題: [虛擬無線網路裝置驅動程式](https://hackmd.io/@sysprog/rJ-LF4nNC)
[vwifi](https://github.com/sysprog21/vwifi) 是一個具體而微的 WiFi 裝置驅動程式，採用 cfg80211 框架，目前支援掃描、連接等 cfg80211 的介面操作，並得以正確處理 Tx/Rx 封包。

---
#### TODO: 支援 Linux v6.8+
##### scan_width
Problem：
`cfg80211_inform_bss` 中的 `scan_width` 在 v.6.7 以後的版本已被移除，原因是掃描頻寬目前都是以 20MHz 為主，因此不需要另外描述掃描頻寬。

Solution：
確保程式碼中有用到 `scan_width` 的部份只在 v.6.7 前做運用。

##### cfg80211_beacon_data
Problem：
`cfg80211_beacon_data` 在 v.6.7 以後的版本以後被加到 `cfg80211_ap_settings` 中。

Solution:
加入 `cfg80211_ap_update` ，其中包含更動的兩個參數及 `cfg80211_beacon_data` 。 回呼函式中有用到 `cfg80211_beacon_data` 的部份也進行調整。

---
#### TODO: 建立背景知識
1. 《[802.11 Wireless Networks: The Definitive Guide, 2/e](https://www.oreilly.com/library/view/80211-wireless-networks/0596100523/)》
2. 〈[Lightweight and Fast WiFi Access in Virtual Machines](http://osseu2023.sched.com/event/1OGgh)〉, Open Source Summit Europe 2023
---
#### TODO: Emulate rate and mcs
有一些回呼函式還沒有被實作，例如 station dump (顯示與 Wi-Fi AP 連接的 station 的相關資訊，包括資料傳輸率和 MCS )。

Modulation 可以控制資源單位可以攜帶幾個 symbol (bits) ，因此會影響資料傳輸率。

採用 802.11n (HT) 做為 PHY，設置如下 :
Modulation : 64-QAM
Data Bandwidth : 20MHz
Number of Spatial Streams : 4

參照 802.11n (HT) 調變對照表可得:
Number of Data Subcarriers : 52
Number of Coded Bits per Subcarrier per Stream : 6
Coding : 5/6
OFDM Symbol Duration : 3.2 us
Guard Interval Duration : 0.8 us

代入上方計算資料傳輸率的公式可得 data rate = 260 Mbps ，藉此驗證程式所計算出來的結果是否相符。

---
#### TODO: 實作 vwifi_{set,get}_tx_power

在結構體 `vwifi_vif` 上新增 `tx_power` 以描述裝置的傳輸功率。

在 `cfg80211_ops` 的架構上新增實作 `vwifi_set_tx_power` 及 `vwifi_get_tx_power` 兩個回呼函式，則使用者可以透過 **iw dev [interface] set txpower [auto/limit/fixed] [transmit power (mBm)]** 設定裝置傳輸功率。

Problem:
在使用 `iw` 指令時，會導致 `et_tx_power` 的輸入參數 `wdev` 為 NULL，詳見 [cfg80211: allow per interface TX power setting](https://github.com/torvalds/linux/commit/c8442118ad9cd05cfe3b993f058e70ab25b1009a) 。

Solution:
新增函式 `wiphy_get_vwifi_vif` 改以利用參數 `wiphy` 取得裝置的 virtual interface，而非 `wdev` 。

==改進方向==
加上距離位置設定，就可以推得 station 所收到 Wi-fi AP 的訊號。

---
#### TODO: 實作 Ad-hoc (IBSS) mode
實作輕量化的傳輸行為模式

##### 新增 AD-HOC interface type
當一個裝置被設定為 Ad-hoc mode ，就可以跟其他處在同一個 Ad-hoc 網路的裝置任意傳輸，而不用直接連線。

在 `wiphy` 上新增 `NL80211_IFTYPE_ADHOC` interface type，使 Linux 系統能知道此裝置已成為 Ad-hoc (IBSS) 模式（透過 `vwifi_change_iface` 的 operation 切換）。使用者可透過命令 **iw dev [interface] set type ibss** 將裝置切換成 IBSS 模式。

##### 實作 IBSS join 與 leave 機制

加入、離開特定頻段的 IBSS 網路。

1. 建立結構體來存放資訊。
2. 建立 `ibss_list` 以便快速找到所有的 IBSS 裝置。

##### 實作 AD-HOC 封包傳遞機制
在轉送前要確認 source 和 destination 是否處於相同 IBSS cell，以及確認是否在該 IBSS cell 的同個 BSS 中。

##### Ping Test
測試：
1. 同 IBSS cell 中 ping 特定裝置
2. ping 處於不同 IBSS cell 的裝置
兩者處於不同 IBSS，無法通訊。傳輸裝置會三度嘗試用 ARP Request 請求 mac address，但沒有裝置回應。
3. ping 處於 STA mode 的裝置
如預期般失敗。

##### 使 IBSS 支援掃描
`ah_inform_bss(vif)`
執行 scan 可發現該 bss 資訊

---

### Linux 核心專題: [虛擬攝影機裝置](https://hackmd.io/@sysprog/HJBxRsRr0)
使用 V4l2 框架以及 Linux Frambuffer API
運作流程：將資料寫入虛擬 Frambuffer 中，影片播放程式可以透過 /dev/videoX 來播放影片

#### V4l2 (Video4Linux version 2)
Linux 下關於視訊設備的驅動框架，支援的設備有：
1. Video capture device (ex. 攝影機)
2. Video output device (ex. 螢幕)
3. Radio device （沒有影像，只有聲音）

兩種角度來看 V4L2 框架
1. userspace 角度
常見的 ioctl 參數
* VIDIOC_QUERYCAP: 詢問 V4L2 裝置的 capability
* VIDIOC_S_INPUT / VIDIOC_G_INPUT: 設置、取得目前的輸入來源
* VIDIOC_S_FMT / VIDIOC_G_FMT: 設置、取得 V4L2 裝置的 format (ex. resolution)
2. 驅動程式開發者角度
* 關係綁定
* 將 V4L2 框架所提供的結構體嵌入到自己所定義的結構體中
* 透過 V4L2 框架所提供的函式將自定義的結構體跟 V4L2 框架作綁定
* ioctl 等函數綁定
* 實作特定函式並且將函式跟 V4L2 框架綁定
* 當某見事情發生時，驅動框架就會呼叫綁定的程式

#### Linux Frambuffer API
Frambuffer: RAM 中的一段連續記憶體，CPU 或 GPU 會把要顯示的影像放到 Framebuffer 中，讓 Display 裝置顯示。

---
#### TODO: 在 Linux v6.8+ 運作
Problem:
在其版本上無法成功編譯

Solution:
1. 修正呼叫函式時所用的參數數量: `class_create(owner, name)` --> `class_create(name)`
2. 修正 `struct vb2_queue` 的 member 名稱: `min_buffers_needed` --> `min_queued_buffers`
3. 修改初始化 `struct fb_info` 的方式: `info->flags = FBINFO_FLAG_DEFAULT;` --> `fb_data->info = framebuffer_alloc(0, &dev->vdev.dev);`
注意：不可以直接改成定值，以防 Linux 核心哪天將初始值改掉。
---
#### TODO: 修正記憶體操作
Problem:
有多個載入模組時所配置的記憶體位置在卸載時沒有被釋放，導致 memory leak。

Solution:
使用 `rcu_varrier()` 來解決來不及釋放的記憶體問題。

---

### Linux 核心專題: [改進 LKMPG](https://hackmd.io/@sysprog/SJS4uStUA)
LKMPG (Linux Kernel Module Programming Guide)

---
#### TODO: 閱讀 LKMPG 並紀錄問題 (含可改進之處)
Problem:
tasklet 在運作時是 non-blocking 的，因此一定會讓 `tasklet_fn` 全部完成後才會繼續做其他事，且在 tasklet 中不宜使用 delay 或 sleep 等操作。

Solution:
將範例中的 delay 時間做調整。

---

#### TODO: 加上 simrupt 到 LKMPG 來說明 tasklet, mutex, kfifo 等使用方式

##### 使用 [simrupt](https://github.com/sysprog21/simrupt)
simrupt 是一個 Linux 核心模組，用於展示延遲工作 (deferred work) 和以下核心概念實作：
* Circular Buffer (環形緩衝區)：儲存和處理資料流。
* Mutex Lock (互斥鎖)：保護臨界區避免多執行緒競爭。
* IRQ (中斷請求) 和 SoftIRQ (軟中斷)：處理硬體中斷和軟體中斷。
* Tasklet 和 Workqueue (工作佇列)：處理延遲任務。
* Kernel Thread (核心執行緒)：建立並管理核心的背景任務。

##### Tasklet

`tasklet` 是 Linux kernel 中的一中軟中斷機制，用於中斷上下文中處理較長時間的任務，相關的定義及函式都存在 [linux/interrupt.h](https://github.com/torvalds/linux/blame/master/include/linux/interrupt.h) 中。

##### Mutex
process 使用 mutex 時，必須先持有 mutex 才得以進入 CS (critical section) 存取資源，
結束後再釋放 mutex 讓其他 process 使用。

若無使用 mutex 確保 critical section 的單一存取，有可能會發生 [race condition](https://zh.wikipedia.org/zh-tw/%E7%AB%B6%E7%88%AD%E5%8D%B1%E5%AE%B3)。


##### kfifo
> [linux/kfifo.h](https://github.com/torvalds/linux/blob/master/include/linux/kfifo.h)
> [linux/kfifo.c](https://github.com/torvalds/linux/blob/master/lib/kfifo.c)

* Linux 核心中的 Ring Buffer 機制。
* 若只有單一讀取端與單一寫入端，二者沒有共享被修改的控制變數的情況下，不需要並行控制。
* 生產者-消費者模式的資料傳遞；中斷上下文與 process 上下文間的資料傳遞。
* 寫滿後自動從開頭覆寫，達到記憶體重複使用，減少記憶體配置與釋放的頻率。

## 記憶體管理
### Linux 核心專題: [rhashtable 及核心記憶體管理研究](https://hackmd.io/@sysprog/rkOByUtI0)
Rhashtable (Relativistic hash tables)

在過去的 hash tables 中，若需要進行同步的存取，會需要 mutex locks 來做存取的控制。但在多核處理器的環境底下， mutex locks 導致使執行序相互等待，效率下降。

* Read-Copy Update (RCU)
一種同步方法，適用於讀取次數比修改次數多的環境。

Problem:
Bucket 數量太少，每個 bucket 後面接的鏈結串列很長，節點讀取很花時間
--> 擴張 hash table 使 bucket 增加
--> 要做 resizing ，影響讀取效率

---
#### TODO: 閱讀 [rhashtable](https://hackmd.io/@linjohn/rhashtable)，紀錄核心記憶體管理相關問題
##### Table shrinking
縮小 hash table，減少 bucket 數量。

> Step 0: 原本的 hash table 有奇數、偶數的 bucket：

> Step 1: 建立新的 hash table 指標，指向目前 hash table 第一個 bucket 的第一個節點：

> Step 2: 把奇數 bucket 的最後一個節點連接到偶數 bucket 的第一個節點：

> Step 3: 把原始 hash table 的指標刪除
注意：可能還有 readers 在查找資料，因此須等一段時間，確保所有 readers 皆已查找完畢，再進行刪除。

> Step 4: 發布新的 hash table ，確認接下來的 readers 都讀到最新的內容

##### Table expansion

> Step 1: 新的 hash table ，奇數 bucket 連接到舊有的奇數節點，偶數 bucket 連接到舊有的偶數節點

> Step 2: 將舊有的 hash table 指標指向新的 hash table

> Step 3: 等 readers 全部讀取完，刪除舊的指標

> Step 4: 做指標的修改 (unzip)，第一個節點會往下尋找在新的 hash table 與它在相同 bucket 中的節點

> Step 5: 持續上個步驟直到所有節點都指向新的 hash table

---
#### TODO: 確保 [rhashtable](https://hackmd.io/@linjohn/rhashtable) 對應的程式碼可運作於 Linux v6.8

比較 RP, DDDS, rwlock 在兩種情況下效能的差異。
1. No resizing and $2^{13}$ buckets
2. Continuous resizing between $2^{13}$ and $2^{14}$ buckets

在過去的版本的 rhashtable 結構體中，若要插入、刪除或 resize 的操作，需要使用 mutex lock 來保護 hash table ，防止操作被同步。而最新版本的中則使用 per-bucket spinlocks ，只鎖定正在被修改的 bucket 而非整個 hash table ，使其他的 bucket 則可以繼續進行原本的操作。

---

### Linux 核心專題: [高效記憶體配置器](https://hackmd.io/@sysprog/rkZQsLhLR)

## 亂數產生器
### Linux 核心專題: [亂數產生器研究](https://hackmd.io/@sysprog/BkhlALt8A)