F02: fibdrv

主講人: jserv / 課程討論區: 2019 年系統軟體課程
:mega: 返回「Linux 核心設計」課程進度表

作業說明直播錄影

預期目標

• 撰寫可適用於使用者和核心層級的程式
• 自動測試機制
• 透過工具進行效能分析

費氏數列

• 費氏數列
  • Fast modular Fibonacci
• 影片「什麼是費氏數列」: Part I, Part II, Part III, Part IV
• Fibonacci and Golden Ratio Formulae

撰寫 Linux 核心模組

• Introduction to Linux kernel driver programming
• Part 1: Introduction
• Part 2: A Character Device

測試給定的 fibdrv 模組

• 檢查 Linux 核心版本
  ​​​​$ uname -r
  

  預期是大於等於 4.15 的版本，例如 4.15.0-45-generic。若在你的開發環境中，核心版本低於 4.15 的話，需要更新 Linux 核心，請自行參照相關文件
• 安裝 linux-headers 套件 (注意寫法裡頭有 s)，以 Ubuntu Linux 18.04 LTS 為例:
  ​​​​$ sudo apt install linux-headers-`uname -r`
  

• 確認 linux-headers 套件已正確安裝於開發環境
  ​​​​$ dpkg -L linux-headers-4.15.0-45-generic | grep "/lib/modules"
  

  預期得到以下輸出:
  ​​​​/lib/modules/4.15.0-45-generic/build
  

• 檢驗目前的使用者身份
  ​​​​$ whoami
  

  預期為「不是 root 的使用者名稱，例如 jserv (或者你安裝 Ubuntu Linux 指定的登入帳號名稱)。由於測試過程需要用到 sudo，請一併查驗:
  ​​​​$ sudo whoami
  

  預期輸出是 root
  :notes: 在下列操作中，請避免用 root 帳號輸入命令，而該善用 sudo
• 取得原始程式碼
  ​​​​$ git clone https://github.com/sysprog21/fibdrv
  ​​​​$ cd fibdrv
  

• 編譯並測試
  ​​​​$ make check
  

  預期會看到綠色的 Passed [-] 字樣
• 觀察產生的 fibdrv.ko 核心模組
  ​​​​$ modinfo fibdrv.ko
  

  預期可得以下輸出:
  ​​​​description:    Fibonacci engine driver
  ​​​​author:         National Cheng Kung University, Taiwan
  ​​​​license:        Dual MIT/GPL
  ​​​​name:           fibdrv
  ​​​​vermagic:       4.15.0-45-generic SMP mod_unload 
  

自我檢查清單

• 檔案 fibdrv.c 裡頭的 MODULE_LICENSE, MODULE_AUTHOR, MODULE_DESCRIPTION, MODULE_VERSION 等巨集做了什麼事，可以讓核心知曉呢？ insmod 這命令背後，對應 Linux 核心內部有什麼操作呢？請舉出相關 Linux 核心原始碼並解讀
• 當我們透過 insmod 去載入一個核心模組時，為何 module_init 所設定的函式得以執行呢？Linux 核心做了什麼事呢？
• 試著執行 $ readelf -a fibdrv.ko, 觀察裡頭的資訊和原始程式碼及 modinfo 的關聯，搭配上述提問，解釋像 fibdrv.ko 這樣的 ELF 執行檔案是如何「植入」到 Linux 核心
• 這個 fibdrv 名稱取自 Fibonacci driver 的簡稱，儘管在這裡顯然是為了展示和教學用途而存在，但針對若干關鍵的應用場景，特別去撰寫 Linux 核心模組，仍有其意義，請找出 Linux 核心的案例並解讀。提示: 可參閱 Random numbers from CPU execution time jitter
• 查閱 ktime 相關的 API，並找出使用案例 (需要有核心模組和簡化的程式碼來解說)
• clock_gettime 和 High Resolution TImers (HRT) 的關聯為何？請參閱 POSIX 文件並搭配程式碼解說
• fibdrv 如何透過 Linux Virtual File System 介面，讓計算出來的 Fibonacci 數列得以讓 userspace (使用者層級) 程式 (本例就是 client.c 程式) 得以存取呢？解釋原理，並撰寫或找出相似的 Linux 核心模組範例
• 注意到 fibdrv.c 存在著 DEFINE_MUTEX, mutex_trylock, mutex_init, mutex_unlock, mutex_destroy 等字樣，什麼場景中會需要呢？撰寫多執行緒的 userspace 程式來測試，觀察 Linux 核心模組若沒用到 mutex，到底會發生什麼問題
• 許多現代處理器提供了 clz / ctz 一類的指令，你知道如何透過演算法的調整，去加速 費氏數列 運算嗎？請列出關鍵程式碼並解說

作業要求

• 回答上述「自我檢查清單」的所有問題，需要附上對應的參考資料和必要的程式碼，以第一手材料 (包含自己設計的實驗) 為佳
• 在 GitHub 上 fork fibdrv，目標是改善 fibdrv 計算 Fibinacci 數列的執行效率，過程中需要量化執行時間，可在 Linux 核心模組和使用層級去測量
  • 在 Linux 核心模組中，可用 ktime 系列的 API
  • 在 userspace 可用 clock_gettime 相關 API
  • 分別用 gnuplot 製圖，分析 Fibonacci 數列在核心計算和傳遞到 userspace 的時間開銷，單位需要用 us 或 ns (自行斟酌)
  • 嘗試解讀上述時間分佈，特別是隨著 Fibonacci 數列增長後，對於 Linux 核心的影響
  • 原本的程式碼只能列出到 Fibonacci(100)，請修改程式碼，列出後方更多數值 (注意: 檢查正確性和數值系統的使用)
• 逐步最佳化 Fibonacci 的執行時間，引入 費氏數列 提到的策略，並善用 clz / ctz 一類的指令，過程中都要充分量化

繳交方式

編輯 Homework2 作業區共筆，將你的觀察、上述要求的解說、應用場合探討，以及各式效能改善過程，善用 gnuplot 製圖，紀錄於新建立的共筆

截止日期

Mar 19, 2019 (含) 中午之前
越早在 GitHub 上有動態、越早接受 code review，評分越高