contributed by < zoanana990
>
lsmod
的輸出結果有一欄名為 Used by
,這是 "each module's use count and a list of referring modules",但如何實作出來呢?模組間的相依性和實際使用次數 (reference counting) 在 Linux 核心如何追蹤呢?
搭配閱讀 The Linux driver implementer’s API guide » Driver Basics
fibdrv.c
存在著 DEFINE_MUTEX
, mutex_trylock
, mutex_init
, mutex_unlock
, mutex_destroy
等字樣,什麼場景中會需要呢?撰寫多執行緒的 userspace 程式來測試,觀察 Linux 核心模組若沒用到 mutex,到底會發生什麼問題。嘗試撰寫使用 POSIX Thread 的程式碼來確認。電腦配置
嘗試編譯:
觀察產生的核心模組:
掛載核心模組:
研讀上述 Linux 效能分析的提示 描述,在自己的實體電腦運作 GNU/Linux,做好必要的設定和準備工作
→ 從中也該理解為何不希望在虛擬機器中進行實驗;
閱讀文章提示的幾個排程器:
Memory Manager:virtual memory 到 physical memory 間的映射
linux
中最高位元為虛擬記憶體的 index bits,它將用來進入較低級別的表格。最低的幾個位元組是 offsethugelbfs
,是一個偽檔案系統,它使用記憶體作為他的後備除存空間;第二種是 THP
。 與 hugelbfs
不同,THP
管理名稱類的映射Hypervisor:VM 到實體硬體間的映射
hypervisor
翻譯成超管理器,Hypervisor 是 Supervisor 的Supervisorclz / ctz
以下數學公式利用 C 語言進行實做,這邊會集中說明三種方法,首先說明費氏數列的定義:
在這個作業中不考慮前 項的和,也就是論文中所提到的 k-Ordered Fibonacci Numbers
原始碼如下
這造成大量的重複運算,並不是一個好方法,因此我們接下來介紹疊代法
將費氏數列的前一項令為 a
、a
的前一項令為 b
,則可知費氏數列的值可以改寫為
上式可以簡化為矩陣形式,矩陣形式為:
其中為 Q-Matrix,在論文中提到,利用數學歸納法可以得到
這邊有閱讀老師給的資料 Fast-Doubling,但是沒有非常清楚。因此有另外看一個影片這個影片詳細解釋了位元組與 Fast Doubling 的關係,其定義如下:
轉換成聯立方程式:
下面是我的理解,以 為例,15
的二進位為 0…01111,可將計算過程
圖示化如下:
f(8) = f(7) + f(6)
,計算方式連同上圖可將其圖示化如下:對比老師給的範例 f(10)
,其二進位為 0…01010,對比我們舉例的 f(15)
可以以下表呈現:
bit | bit | ||
---|---|---|---|
0 | 1 | ||
1 | 1 | ||
0 | 1 | ||
1 | 1 |
上表歸納出若是該位元數為 1,則代表需要使用定義解,0 則代表僅須使用公式解
實做字串疊代法之前,需要先實做字串相加、字串長度、字串複製等函式,主體為字串相加。
字串相加概念主要列為以下三點:
strlen
,需要自己實做F_8 = "13"
。程式碼如下:
這邊參考兩種方式,一種是 linux kernel,另外一種是 glibc
linux kernel 的方式很簡單,就是用 for 迴圈的方式檢測每個字元是不是結束字元
glibc 的方式就聰明且嚴謹許多,這個例子在你所不知道的C語言:數值系統篇有被提到,其主要改進方法如下:
- Data alignment is the aligning of elements according to their natural alignment. To ensure natural alignment, it may be necessary to insert some padding between structure elements or after the last element of a structure.
'\0'
,解釋如下所示:
在數值系統篇當中,可以看到這個巨集是用來偵測 0 的, 0 也是中止符號的 ASCII 碼,若是 DETECT(0)
則輸出值不為 0 ,這是就可以判斷是哪個字出現中止符號字串複製的想法就是相每個字元複製到指定的字串中,最後在加上結束字元
目前透過字串可以得到第500項的費氏數列,其效能如下圖所示
如果以相同的程式碼印到第10000項,其曲線為
首先對比老師的疊代法與我開發的字串疊代法的效能
缺點與改進
INT_MAX
(2147483647) 為例,int
僅需要 4 bytes 就可以表示,但是 char 卻需要用 10 bytes 表示。此時就會造成空間浪費,若要避免浪費空間,不能以字串相加的形式,也就是 "123456" + "456789" 等,需要以 123 + 456 的方式進行,但是出現新的問題,也就是字元相加溢位的問題上面提到,這種計算方式過於浪費空間。這邊想到,既然都要做整數運算,不如直接使用大型整數型態進行運算,這邊使用 unsigned long long
進行,但是這仍然會產生溢位的問題,因此自定義結構,如下所示:
其中 *num
進行大數運算,但是 *num
是動態陣列,因此需要 size
控制其大小,這邊可以重新實做 fib_add
的函式
這邊主要有一個巨集 DETECT_OVERFLOW
是偵測有沒有無號長整數 (unsigned long long) 溢位的,上面的使用方式會有問題,這邊先看原本的巨集,這個巨集的想法是參考 CSAPP 第二章:
這會導致第二次溢位的時候無法成功偵測,舉例來說:
依照原本的方式進行加法預期結果如下
但是實際情況是這樣的
因為 (x) + (y)
並不是他的和,和應該是 (x) + (y) + (carry)
,因此進行對應的修改之後即可
可改用 gcc 的 Built-in Functions to Perform Arithmetic with Overflow Checking
這邊採用比較直覺的方式,以 f(96)
舉例說明:
f(96)
無法裝在一個 unsigned long long
中,這邊採用陣列的方式進行,可以知道 f(96)[1] = 2
, f(96)[0] = 14787220707439219840
,則 f(96)
為 f(96)[1] * (ULL_MAX + 1) + f(96[0])
而這個加法與乘法採用字串形式放上 User Space 的效能比較,前 100 項:
MSB
計算 MSB
在 Fast-Doubling
的實做可以有效避免使用過多的分支預測尋找最高位數,因此這裡依照 GCC 的方式進行撰寫
減法使用的方式微小學生的直式減法,以下舉例:
先由最右邊的開始減,如果值不夠就往大的借
這樣就完成了,程式碼如下所示:
左移的想法很簡單,然而實作時需要考慮左移大位數(64以上),也就是如果要左移 64 位元時的實作,我的作法是,移64位元的時候等同左移一個 index
,舉例來說:
會變成上面這樣,而左移 0 ~ 63 位元的值,則是使用一般的左移,因此如果今天是左移 94 位的情況下,會進行 1 個 index 的左移以及 30 位的左移,這樣即可實現大數乘法
這邊乘法的實作是希望利用位元左移及加法進行,利用上面左移的想法可知,這裡實現大數乘法的方式極其簡單,並沒有用到特別複雜的十進位,然而這裡的缺點是對於每個位元都要進行分支預測,這樣會使程式的速度下降。
回顧前面提到的公式,主要為以下兩個:
其程式碼如下:
結果探討:
前面自己重新撰寫許多 gcc 內建的函式,主要是避免 kernel module 不支援,照裡參考 Memory Allocation Guide 裡的說明
如果是想要配少量的記憶體,可以使用 kmalloc
,若是想要使用大量連續的虛擬記憶體,則可以使用 vmalloc
You can allocate small chunks using kmalloc or kmem_cache_alloc families, large virtually contiguous areas using vmalloc and its derivatives, or you can directly request pages from the page allocator with alloc_pages. It is also possible to use more specialized allocators, for instance cma_alloc or zs_malloc.
然而,kernel 在分配記憶體的時候,會查看 GFP flags
這邊還有另外一個細節,就是 kernel 對於 Memory API 來說有其他更安全的方式進行記憶體分配
這邊經由老師提示後發現有己的函式可以改用內建函式,如 clz
, DETECT_OVERFLOW
等等,可以使用 __builtin_clz
與 __builtin_add_overflow
進行替換
在 fibnum.h
中,會進行以下改動:
在 fibnum.c
的函式 fib_add
中,會進行以下改動:
這邊如果無腦將 malloc
轉成 kmalloc
在執行的時候 kernel 會直接當掉,這邊推測原因是 kmalloc
的記憶體分配失敗,導致一直出現 Segmentation Fault
。這邊有兩個想法解決這個問題,一個是使用 vmalloc
另外一個是對 kmalloc
分配失敗時給予對應的解決辦法。
由第 9 週課程問答簡記的提示進行巨集定義,對於程式在 User Mode
與 Kernel Model
時會對應產生不同程式碼:
除了 MALLOC
以外,也對於 MALLOC
與 REALLOC
失敗時產生警訊,若是配置失敗則可以使用 dmesg
產生訊息
kmalloc
對於 Iteration
的順利完成,其結果如下:
進行 Fast Doubling 的移植時發現,模組無法順利產生
這邊使用 dmesg
查看錯誤程式碼:
這邊可以看到是 REALLOC
失敗了,這邊對於 fib_resize
函式進行調整。若是 realloc
失敗,則將原本的記憶體釋放,重新配置,程式碼如下:
但是仍舊無法成功驅動模組,因此我們研究錯誤碼:
由上可知,儘管增加了應對記憶體分配失敗的手段,重新分配時仍然會失敗