2023q1 Homework3 (fibdrv)

contributed by < lorian0738 >

自我檢查清單

• 研讀上述 Linux 效能分析的提示 描述，在自己的實體電腦運作 GNU/Linux，做好必要的設定和準備工作
  $\to$ 從中也該理解為何不希望在虛擬機器中進行實驗;
• 研讀上述費氏數列相關材料 (包含論文)，摘錄關鍵手法，並思考 clz / ctz 一類的指令對 Fibonacci 數運算的幫助。請列出關鍵程式碼並解說
• 複習 C 語言 數值系統 和 bitwise operation，思考 Fibonacci 數快速計算演算法的實作中如何減少乘法運算的成本;
• 學習指出針對大數運算的加速運算和縮減記憶體操作成本的舉措，紀錄你的認知和疑惑
• 注意到 fibdrv.c 存在著 DEFINE_MUTEX, mutex_trylock, mutex_init, mutex_unlock, mutex_destroy 等字樣，什麼場景中會需要呢？撰寫多執行緒的 userspace 程式來測試，觀察 Linux 核心模組若沒用到 mutex，到底會發生什麼問題。嘗試撰寫使用 POSIX Thread 的程式碼來確認。
  $\to$ 搭配閱讀〈並行和多執行緒程式設計〉

了解更多核心模組

• Linux 核心模組運作原理
• 《The Linux Kernel Module Programming Guide》
• Introduction to Linux kernel driver programming
• Part 1: Introduction
• Part 2: A Character Device

前期準備

• 檢查 Linux 核心版本

  ​​​​$ uname -r
  

  輸出：

  ​​​​5.15.0-67-generic
  

• 安裝 linux-headers 套件

  ​​​​$ sudo apt install linux-headers-`uname -r`
  

  輸出：

  ​​​​正在讀取套件清單... 完成
  ​​​​正在重建相依關係... 完成  
  ​​​​正在讀取狀態資料... 完成  
  ​​​​linux-headers-5.15.0-67-generic is already the newest version (5.15.0-67.74).
  ​​​​升級 0 個，新安裝 0 個，移除 0 個，有 239 個未被升級。
  

• 確認 linux-headers 套件已正確安裝於開發環境

  $ dpkg -L linux-headers-5.4.0-66-generic | grep "/lib/modules"

  ​​​​$ dpkg -L linux-headers-5.15.0-67-generic | grep "/lib/modules"
  

  輸出：

  ​​​​/lib/modules
  ​​​​/lib/modules/5.15.0-67-generic
  ​​​​/lib/modules/5.15.0-67-generic/build
  

• 檢驗目前的使用者身份

  ​​​​$ whoami
  

  輸出：

  ​​​​cyh
  

  預期為「不是 root 的使用者名稱」，例如 jserv (或者你安裝 Ubuntu Linux 指定的登入帳號名稱)。

• 由於測試過程需要用到 sudo，請一併查驗:

  ​​​​$ sudo whoami
  

  輸出：

  ​​​​root
  

  預期輸出是 root

  在下列操作中，請避免用 root 帳號輸入命令，而該善用 sudo
  之後的實驗中，若濫用 root 權限，可能會破壞 GNU/Linux 開發環境 (當然，你還是可重新安裝)，現在開始養成好習慣

• 安裝後續會用得到的工具

  ​​​​$ sudo apt install util-linux strace gnuplot-nox
  

• 取得原始程式碼

  • 先 fork 到自己的 GitHub
  • git clone
  ​​​​$ git clone [e-mail]:lorian0738/fibdrv.git
  ​​​​$ cd fibdrv
  

• 編譯並測試

  ​​​​$ make check
  

  注意：這個指令會先卸載再掛載再卸載，在額外執行時會發現沒有掛載到，故可以僅輸入 $ make 編譯就好

  預期：

  ​​​​綠色的  Passed [-] 字樣，隨後是
  ​​​​f(93) fail
  ​​​​input: 7540113804746346429
  ​​​​expected: 12200160415121876738
  

  實際輸出：

  ​​​​ Passed [-]
  ​​​​f(93) fail
  ​​​​input: 7540113804746346429
  ​​​​expected: 12200160415121876738
  

  => 符合預期

• 觀察產生的 fibdrv.ko

  ​​​​$ modinfo fibdrv.ko
  

  預期可得以下輸出:

  ​​​​description:    Fibonacci engine driver
  ​​​​author:         National Cheng Kung University, Taiwan
  ​​​​license:        Dual MIT/GPL
  ​​​​name:           fibdrv
  ​​​​vermagic:       5.4.0-45-generic SMP mod_unload 
  

  實際輸出：

  ​​​​filename:       /home/cyh/linux2023/fibdrv/fibdrv.ko
  ​​​​version:        0.1
  ​​​​description:    Fibonacci engine driver
  ​​​​author:         National Cheng Kung University, Taiwan
  ​​​​license:        Dual MIT/GPL
  ​​​​srcversion:     9A01E3671A116ADA9F2BB0A
  ​​​​depends:        
  ​​​​retpoline:      Y
  ​​​​name:           fibdrv
  ​​​​vermagic:       5.15.0-67-generic SMP mod_unload modversions 
  

  好奇 vermagic 是什麼，但維基百科沒有，網站中提到：

  ​​​​Linux的vermagic用於內核模塊的版本檢查，其值由kernel Makefile中的“VERMAGIC_STRING”來表示，在編譯kernel的過程中生成。
  ​​​​總的來說，在vermagic中，只有內核版本是一定會被包含的，而其它的要看具體的kernel配置。
  ​​​​VERMAGIC_STRING = <UTS_RELEASE> ["SMP"] ["preempt"] ["mod_unload"]["modversions"]
  

  因此可能是因為 kernel 配置不同而比預期輸出多了 modversions

• 觀察 fibdrv.ko 核心模組在 Linux 核心掛載後的行為

  • 要先透過 insmod 將模組載入核心後才會有下面的裝置檔案 /dev/fibonacci
    ​​​​​​​​$ sudo insmod fibdrv.ko
    

    (註：Makefile 中 load 也有一樣的功能，可直接下 make load 在終端機)
  ​​​​$ ls -l /dev/fibonacci
  

  輸出：

  ​​​​crw------- 1 root root 511, 0  3月  8 16:49 /dev/fibonacci
  

  ​​​​$ cat /sys/class/fibonacci/fibonacci/dev
  

  輸出：

  ​​​​511:0
  

  新建立的裝置檔案 /dev/fibonacci，注意到 236 這個數字，在你的電腦也許會有出入。試著對照 fibdrv.c，找尋彼此的關聯。

  ​​​​$ cat /sys/module/fibdrv/version 
  

  輸出：

  ​​​​0.1
  

  預期輸出是 0.1(相同)，這和 fibdrv.c 透過 MODULE_VERSION 所指定的版本號碼相同。

  ​​​​$ lsmod | grep fibdrv
  

  輸出：

  ​​​​fibdrv                 16384  0
  

  ​​​​$ cat /sys/module/fibdrv/refcnt
  

  輸出：

  ​​​​0
  

  這兩道命令的輸出都是 0，意味著目前的 reference counting。

Linux 效能分析

查看行程的 CPU affinity

查看指定行程的處理器親和性 (PID = process ID)

第一種（十六進位）

$ taskset -p PID

輸入：

$ taskset -p 1

輸出：

pid 1's current affinity mask: ff

十六進位的 ff 轉成二進位的格式會是 11111111，這 8 個 1 分別代表該行程可以在第 0 到第 7 個 CPU 核中執行，最低（LSB; 最右邊）的位元代表第 0 個 CPU 核

第二種（直接輸出列表）

輸入：

$ taskset -cp 1

輸出：

pid 1's current affinity list: 0-7

限定 CPU 給特定的程式使用

使用 isolcpus 這個 Linux 核心起始參數，讓特定的 CPU 核在開機時就被保留下來
設定的方式：

1. 開機時使用 boot loader 所提供的自訂開機參數功能，手動加入 isolcpus=cpu_id 參數
2. 直接加在 GRUB 的設定檔中

於是只有那些被 taskset 特別指定的行程可使用這些 CPU 核

選擇直接加在 GRUB 設定檔中，保留第 0 個 CPU 核：

參考網站：1 2

1. 先備份
   ​​​​$ sudo cp /etc/default/grub /etc/default/grub.bak
   

2. 開啟 GRUB 檔
   ​​​​$ sudo vi /etc/default/grub
   

3. 添加 isolcpus 參數
   ​​​​GRUB_CMDLINE_LINUX="isolcpus=1,3"
   

4. 更新
   ​​​​sudo update-grub
   

5. 輸出：
   ​​​​Sourcing file `/etc/default/grub'
   ​​​​Sourcing file `/etc/default/grub.d/init-select.cfg'
   ​​​​Generating grub configuration file ...
   ​​​​Found linux image: /boot/vmlinuz-5.15.0-67-generic
   ​​​​Found initrd image: /boot/initrd.img-5.15.0-67-generic
   ​​​​Found linux image: /boot/vmlinuz-5.15.0-60-generic
   ​​​​Found initrd image: /boot/initrd.img-5.15.0-60-generic
   ​​​​Memtest86+ needs a 16-bit boot, that is not available on EFI, exiting
   ​​​​Warning: os-prober will not be executed to detect other bootable partitions.
   ​​​​Systems on them will not be added to the GRUB boot configuration.
   ​​​​Check GRUB_DISABLE_OS_PROBER documentation entry.
   ​​​​Adding boot menu entry for UEFI Firmware Settings ...
   ​​​​done
   

6. 重新開機確認
   輸入：
   ​​​​$ taskset -p 1
   

   輸出：
   ​​​​pid 1's current affinity mask: fe
   

   第 0 個 CPU 核已被保留！

以特定的 CPU 執行程式

首先編譯產生執行檔

$ make

接著利用 taskset 將執行檔綁定在特定 cpu
因為前面保留第 0 個 cpu：

$ sudo taskset 0x1 ./client

其中 0x1 表示第 0 個 cpu

排除干擾效能分析的因素

1. 抑制 address space layout randomization (ASLR)

   ​​​​$ sudo sh -c "echo 0 > /proc/sys/kernel/randomize_va_space"
   

2. 設定 scaling_governor 為 performance。準備以下 shell script，檔名為 performance.sh

   首先以 sudo vi performance.sh 建立檔案並填入以下：

   ​​​​for i in /sys/devices/system/cpu/cpu*/cpufreq/scaling_governor
   ​​​​do
   ​​​​    echo performance > ${i}
   ​​​​done
   

   再執行

   ​​​​$ sudo sh performance.sh
   

3. 針對 Intel 處理器，關閉 turbo mode

   ​​​​$ sudo sh -c "echo 1 > /sys/devices/system/cpu/intel_pstate/no_turbo"
   

   turbo boost：

   it lets the CPU run at its base clock speed when handling light workloads, then jump to a higher clock speed for heavy workloads.

   因此這會讓 CPU 至少一直以基本時脈速度運行，對效能測試會有影響

核心模式的時間測量

ktime_t

參考教材以新的資料結構 ktime_t 測量時間，如下：

static long long fib_time_proxy(long long k)
{
    kt = ktime_get();
    long long result = fib_sequence(k);
    kt = ktime_sub(ktime_get(), kt);

    return result;
}

/* calculate the fibonacci number at given offset */
static ssize_t fib_read(struct file *file,
                        char *buf,
                        size_t size,
                        loff_t *offset)
{
    return (ssize_t) fib_time_proxy(*offset);
}

/* write operation is skipped */
static ssize_t fib_write(struct file *file,
                         const char *buf,
                         size_t size,
                         loff_t *offset)
{
    return ktime_to_ns(kt); // output fib time
}

改完後下 make check 指令會看到：

-Writing to /dev/fibonacci, returned the sequence 0
-Writing to /dev/fibonacci, returned the sequence 0
-Writing to /dev/fibonacci, returned the sequence 0
-Writing to /dev/fibonacci, returned the sequence 0
-Writing to /dev/fibonacci, returned the sequence 0
-Writing to /dev/fibonacci, returned the sequence 0
-Writing to /dev/fibonacci, returned the sequence 0
-Writing to /dev/fibonacci, returned the sequence 0
...

client.c 中，原本 write 的部份：

    for (int i = 0; i <= offset; i++) {
        sz = write(fd, write_buf, strlen(write_buf));
        printf("Writing to " FIB_DEV ", returned the sequence %lld\n", sz);
    }

其中在 unistd.h 中可見

/* Write N bytes of BUF to FD.  Return the number written, or -1.

   This function is a cancellation point and therefore not marked with
   __THROW.  */
extern ssize_t write (int __fd, const void *__buf, size_t __n) __wur
    __attr_access ((__read_only__, 2, 3));

可知 write 的功能是將存在 BUF 的 N 個 bytes 傳給 FD，回傳寫入的字數

其中 BUF 的意思是 buffer
FD 根據維基百科，指的是 file descriptor：檔案描述子，為 Unix 或 Unix-like 作業系統常用的詞，是一個檔案或讀寫操作的行程唯一標識符 (process-unique identifier)，例如 pipe 或 network socket，通常為非負整數，負數保留於沒有值或是錯誤。

這個函式也作為一個 cancellation point，問了 chatGPT：

Cancellation point 是指在多線程編程中，一個可以取消執行緒運行的特定點。
當執行緒到達這個點時，它可以檢查是否有取消請求，如果有，則可以將自己取消。
Cancellation point 是一個非常重要的概念，因為它可以讓程序更加靈活地處理
取消請求，避免出現死鎖或無法取消的情況。

在 POSIX 環境下，許多系統函數都是 cancellation point，
例如 pthread_join()、read()、write() 等。

看不懂為什麼很多字前面後面都要加上__，有待釐清…

還是不知道要怎麼做，因此參考了同學的想法，因為要做完計算 kt 的值才會是對的，因此先用 read 做計算，再 call wite 的函式才會對

read：

/* Read NBYTES into BUF from FD.  Return the
   number read, -1 for errors or 0 for EOF.

   This function is a cancellation point and therefore not marked with
   __THROW.  */
extern ssize_t read (int __fd, void *__buf, size_t __nbytes) __wur
    __fortified_attr_access (__write_only__, 2, 3);

因此改成：

    for (int i = 0; i <= offset; i++) {
        sz = read(fd, buf, 1);
        long long time = write(fd, write_buf, strlen(write_buf));
        printf("Writing to " FIB_DEV ", returned the sequence %lld\n", time);
    }

改完以後輸出：

-Writing to /dev/fibonacci, returned the sequence 87
-Writing to /dev/fibonacci, returned the sequence 61
-Writing to /dev/fibonacci, returned the sequence 46
-Writing to /dev/fibonacci, returned the sequence 46
-Writing to /dev/fibonacci, returned the sequence 46
-Writing to /dev/fibonacci, returned the sequence 46
-Writing to /dev/fibonacci, returned the sequence 46
-Writing to /dev/fibonacci, returned the sequence 46
-Writing to /dev/fibonacci, returned the sequence 46
...

但這樣改的話迴圈中 sz = read(fd, buf, 1); 的 sz 沒有用到，會 commit 不了，因為程式會認為它佔用空間卻沒有實質影響。可以直接寫在後面的迴圈就好，而計算時間後應該輸出成檔案再用 gnuplot 繪製。

gnuplot

根據教材 gnuplot 語法解說和示範 可知應該將想繪製的資料做成 txt 或 csv 檔再用附檔名為 gp 的檔案讀取繪圖

• 首先準備 csv 檔：(於 client.c 的檔案中)

  ​​​​    // prepare csv for gnuplot
  ​​​​    FILE *fp = fopen("time.csv", "w+");
  ​​​​    if (fp == NULL) {
  ​​​​        fprintf(stderr, "fopen() failed.\n");
  ​​​​        exit(EXIT_FAILURE);
  ​​​​    }
  

  w+ 表示為了讀出和寫入而打開檔案，在檔案已存在的前提下，會把原來的內容覆蓋掉; 如果檔案不存在就創建一個新的。（參考）
  若開啟失敗則報錯

  ​​​​fprintf(fp, "nth Fibonacci, Fast Doubling\n");
  

  將 nth Fibonacci 和 Fast Doubling 寫入檔案的第一列作為標題

  ​​​​    for (int i = 0; i <= offset; i++) {
  ​​​​        lseek(fd, i, SEEK_SET);
  ​​​​        sz = read(fd, buf, 1);
  ​​​​        long long time = write(fd, write_buf, strlen(write_buf));
  ​​​​        printf("Reading from " FIB_DEV
  ​​​​               " at offset %d, returned the sequence "
  ​​​​               "%lld.\n",
  ​​​​               i, sz);
  ​​​​        fprintf(fp, "%d, %lld\n", i, time);
  ​​​​    }
  

  迴圈中首先計算 Fibonacci，算完後取得花費時間 time，再將該迴圈計算第 i 個費波那契數與取得的 time 逐列寫入檔案中

  ​​​​    fclose(fp);
  

  最後關閉檔案

• 寫 gp 檔
  首先下指令：

  ​​​​$ gnuplot
  

  會出現：

  ​​​​        G N U P L O T
  ​​​​        Version 5.4 patchlevel 2    last modified 2021-06-01 
  
  ​​​​        Copyright (C) 1986-1993, 1998, 2004, 2007-2021
  ​​​​        Thomas Williams, Colin Kelley and many others
  
  ​​​​        gnuplot home:     http://www.gnuplot.info
  ​​​​        faq, bugs, etc:   type "help FAQ"
  ​​​​        immediate help:   type "help"  (plot window: hit 'h')
  
  ​​​​Terminal type is now 'unknown'
  ​​​​gnuplot> 
  

  不知道 Terminal type 是什麼意思，搜尋後得知 gnuplot 無法識別有效的終端機，因此要輸入以下進行設定：

  ​​​​gnuplot> set terminal 
  

  會輸出：

  ​​​​Available terminal types:
  ​​​​   cairolatex  LaTeX picture environment using graphicx package and Cairo backend
  ​​​​       canvas  HTML Canvas object
  ​​​​          cgm  Computer Graphics Metafile
  ​​​​      context  ConTeXt with MetaFun (for PDF documents)
  ​​​​      domterm  DomTerm terminal emulator with embedded SVG
  ​​​​       dpu414  Seiko DPU-414 thermal printer [small medium large]
  ​​​​         dumb  ascii art for anything that prints text
  ​​​​          dxf  dxf-file for AutoCad (default size 120x80)
  ​​​​          emf  Enhanced Metafile format
  ​​​​     epscairo  eps terminal based on cairo
  ​​​​     epslatex  LaTeX picture environment using graphicx package
  ​​​​ epson_180dpi  Epson LQ-style 180-dot per inch (24 pin) printers
  ​​​​  epson_60dpi  Epson-style 60-dot per inch printers
  ​​​​  epson_lx800  Epson LX-800, Star NL-10, NX-1000, PROPRINTER ...
  ​​​​          fig  FIG graphics language V3.2 for XFIG graphics editor
  ​​​​          gif  GIF images using libgd and TrueType fonts
  ​​​​       hp500c  HP DeskJet 500c, [75 100 150 300] [rle tiff]
  ​​​​         hpdj  HP DeskJet 500, [75 100 150 300]
  ​​​​         hpgl  HP7475 and relatives [number of pens] [eject]
  ​​​​       hpljii  HP Laserjet series II, [75 100 150 300]
  ​​​​         hppj  HP PaintJet and HP3630 [FNT5X9 FNT9X17 FNT13X25]
  ​​​​Press return for more: 
  ​​​​...
  

  因為找不到 wxt, qt, x11, aqua 等可以直接看輸出圖形的形式，因此直接將圖片輸出另存成 png 檔

  可以利用 help 取得更多資訊，例如：

  ​​​​gnuplot> help terminal png
  

  輸出：

  ​​​​  Syntax:
  ​​​​   set terminal png 
  ​​​​          {{no}enhanced}
  ​​​​          {{no}transparent} {{no}interlace}
  ​​​​          {{no}truecolor} {rounded|butt}
  ​​​​          {linewidth <lw>} {dashlength <dl>}
  ​​​​          {tiny | small | medium | large | giant}
  ​​​​          {font "<face> {,<pointsize>}"} {fontscale <scale>}
  ​​​​          {size <x>,<y>} {{no}crop}
  ​​​​          {background <rgb_color>}
  
  ​​​​ PNG, JPEG and GIF images are created using the external library libgd.
  ​​​​ PNG plots may be viewed interactively by piping the output to the
  ​​​​ 'display' program from the ImageMagick package as follows:
  ​​​​                set term png
  ​​​​                set output '| display png:-'
  ​​​​ You can view the output from successive plot commands interactively by typing
  ​​​​ <space> in the display window.  To save the current plot to a file,
  ​​​​ left click in the display window and choose `save`.
  
  ​​​​ `transparent` instructs the driver to make the background color transparent.
  ​​​​ Default is `notransparent`.
  ​​​​Press return for more: 
  
  ​​​​ `interlace` instructs the driver to generate interlaced PNGs.
  ​​​​ Default is `nointerlace`.
  
  ​​​​ The `linewidth` and `dashlength` options are scaling factors that affect all
  ​​​​ lines drawn, i.e. they are multiplied by values requested in various drawing
  ​​​​ commands.
  
  ​​​​ By default output png images use 256 indexed colors. The `truecolor` option
  ​​​​ instead creates TrueColor images with 24 bits of color information per pixel.
  ​​​​ Transparent fill styles require the `truecolor` option. See `fillstyle`.
  ​​​​ A transparent background is possible in either indexed or TrueColor images.
  
  ​​​​ `butt` instructs the driver to use a line drawing method that does
  ​​​​ not overshoot the desired end point of a line.  This setting is only
  ​​​​ applicable for line widths greater than 1.  This setting is most useful when
  ​​​​ drawing horizontal or vertical lines.  Default is `rounded`.
  
  ​​​​ The details of font selection are complicated.
  ​​​​ Two equivalent simple examples are given below:
  ​​​​      set term png font arial 11
  ​​​​      set term png font "arial,11"
  ​​​​Press return for more: 
  ​​​​ For more information please see the separate section under `fonts`.
  
  ​​​​ The output plot size <x,y> is given in pixels---it defaults to 640x480.
  ​​​​ Please see additional information under `canvas` and `set size`.
  ​​​​ Blank space at the edges of the finished plot may be trimmed using the `crop`
  ​​​​ option, resulting in a smaller final image size. Default is `nocrop`.
  

  進行設定：

  ​​​​gnuplot> set terminal png enhanced truecolor
  

  輸出：

  ​​​​Terminal type is now 'png'
  ​​​​Options are 'truecolor nocrop enhanced size 640,480 font "arial,12.0" '
  

  接著直接寫腳本後續利用比較方便，輸入 vim gnuplot.gp 或直接用 VS code 創建檔案：

  ​​​​set title "fibonacci time"
  ​​​​set xlabel "nth fibonacci"
  ​​​​set ylabel "ns"
  ​​​​set terminal png font " Times_New_Roman,12 "
  ​​​​set output "time.png"
  
  ​​​​plot "time.csv" using 1:2 with linespoints linewidth 2 title "fast doubling"
  

  設定圖片標題、座標軸名稱、字體字形、輸出檔案名稱、以及要用來繪製圖形的行列

  最後輸入以下繪圖：

  ​​​​$ gnuplot gnuplot.gp
  

  終於得到圖片：
  

  

  註：因為是寫完 Fast Doubling 才開始研究計算時間的方法，因此這邊輸出的圖行為 Fast Doubling 的時間，也尚未考慮其他影響時間的因素，因排版關係 Fast Doubling 的實作也在此部份後面(連結)

commit

commit 時沒有先用 clang-format -i 確認格式，才注意到註解應該都要在 // 後空一格再寫、#include 的順序是有照字母排的，這樣確實比較好看

考慮 copy_to_user

教材提到：進行效能分析時，要考慮到 copy_to_user 函式的時間開銷，特別留意到資料大小成長後造成的量測誤差

Fibonacci

以 Fast Doubling 手法改寫

考慮到硬體加速 F(n) 的手法

clz / ctz 一類的指令

在 fibdrv.c 中 static long long fib_sequence(long long k) 計算 Fibonacci 的值：

    for (int i = 2; i <= k; i++) {
        f[i] = f[i - 1] + f[i - 2];
    }

而教材中提到 Fast Doubling 手法：

$$\begin{array}{rl}F(2k)& =F(k)[2F(k+1)-F(k)]\\ F(2k+1)& =F(k+1{)}^2+F(k{)}^2\end{array}$$
示範案例:
求解

$F(10)$:10₁₀ = 1010₂

i	start	4	3	2	1	result
n	-	1010	1010	1010	1010	-
F(m)	F(0)	F(0*2+1)	F(1*2)	F(2*2+1)	F(5*2)	F(10)
a	0	1	1	5	55	55
b	1	1	2	8	89	-

可以更快速的計算，參考給的 sudo code 後改寫如下：

static long long fib_sequence(long long k)
{
    /* FIXME: C99 variable-length array (VLA) is not allowed in Linux kernel. */
    long long a = 0, b = 1;
    int leading_zero = __builtin_clzll(k);
    k = k << leading_zero;

    for (int len = 64 - leading_zero; len > 0; len--) {
        long long t1 = a * (2 * b - a);
        long long t2 = b * b + a * a;
        a = t1;
        b = t2;
        if (((k >> 63) & 1) == 1) {
            t1 = a + b;
            a = b;
            b = t1;
        }
        k = k << 1;
    }

    return a;
}

首先計算 k 的 leading zero bits 個數，左移 k 使 MSB 移至最高位(前面的 0 都可以略過計算)。
迴圈中先求出 F(2k) 和 F(2k+1) 的值分別紀錄在 t1 和 t2，確認現在是做到 2k 還是 2k+1，若最高位為0，則表示是 2k，回傳 t1；若最高位為 1，則表示是 2k+1，回傳 t2，紀錄 a 為 2k+1的值、b 為 F(2k+2) = F(2k) + F(2k+1)，方便後續計算，最後將 k 左移一位，表示乘以 2。

但要將這段修改 commit 時卻得到訊息：

Following files need to be cleaned up:
fibdrv.c
fibdrv.c:39:17: portability: Shifting signed 64-bit value by 63 bits is implementation-defined behaviour [shiftTooManyBitsSigned]
        if (((k >> 63) & 1) == 1) {
                ^

Fail to pass static analysis.

才想到因為 k 是有號數，移動有號數造成 SAR (arithmetic right-shift)算術右移；移動無號數是 SHR (logical right-shift) 邏輯位移。
而我原本想做的是邏輯右移，但在有號的情況下，做算數位移最高位元不會變，因此不能右移 63 個位元。
改成將 1 左移到 64位元的最高位元，與 k 做 ＆ 運算，若非 0 則表示現在 k 的最高位為 1

        if (k & (unsigned long long) 1 << 63) {
            t1 = a + b;
            a = b;
            b = t1;
        }

gnuplot 繪圖

上述方法使用硬體加速直接計算 leading zero bits，繪圖比較

原本想法是在程式中將已經做好的 csv 讀取後再與新獲得的時間重新做一個新的 csv 檔
經過同學友善提示之後，直接將沒有用 clz 計算的時間輸出成另一個檔名再用 Linux 的 paste 功能合併成一個檔案(合併在右邊)，如下：

paste -d ", " time.csv time2.csv > time_fd.csv

-d 表示更改兩個檔案資料之間的分隔，原本預設是 tab，這裡改成逗號
再來寫兩個想要合併的檔案，在 > 之後寫合併的檔名

然而這樣做出來的檔案會僅以逗號分隔，但是 csv 檔應該要用逗號加空白分隔，例如預期：
1, 1, 1
但會做出
1, 1,1
這會導致 gnuplot 在讀 csv 檔的時候讀不到第三欄
目前為了確認繪製正確先手動加入空白分隔，應該要找到更自動化的方法解決這個問題

目前解法 1：在做成要合併的 csv 前就加好空格
目前解法 2：放棄使用 csv 檔，改用 txt 檔也能畫圖

更改 gnuplot.gp ：

set title "fibonacci time"
set xlabel "nth fibonacci"
set ylabel "ns"
set terminal png font " Times_New_Roman,12 "
set output "time_fd.png"

plot \
"time_fd.csv" using 1:2 with linespoints linewidth 2 title "fast doubling", \
"time_fd.csv" using 1:3 with linespoints linewidth 2 title "fast doubling without clz" 

輸出圖形：

可看出運用 clz 的加速效果

但這張圖沒有綁定 cpu 再進行測定，透過上述綁定後再測：

可看出在某些情況下用 clz 會表現的比較好

但對於下面這張圖跑的時間整體比上面那張還久有點困惑，照理來說跑在獨立的 cpu 整體表現應該要比較好，與同學們討論後認為可能是因為這都只是跑一次的結果，應該要平均比較準確，且只跑 100 個有點少，速度原本就非常快，且還沒有做大數運算，可能要跑多一點再觀察

也輸出了與一開始作法的比較圖，比更改後的表現還好，應該要能跑更多之後再來測

計算 F₉₃ (包含) 之後的 Fibonacci 數 (功能受限)

減少 copy to user 傳送的資料量

逐步縮減 Fibonacci 的執行時間，過程中要充分量化