contributed by < nosba0957
>
計算平方根的原理為
乘開後得到
分成幾個部分觀察
所以可以將 表示為
將 定義為 ,而 就是我們要求的平方根 。所以接下來要找出所有組成平方根 的所有 。我們可以得知
其中 。找到平方根的方式就是讓 ,所以透過每一輪比較 來決定 是否要加入到 ,也就是決定 的值為 或是 。
因為每輪計算 的運算成本太高,所以改為紀錄每輪的差值 ,計算本輪差值的方式為 , 為上一輪計算完的差值。
再將 拆為 ,
每輪的 , 都會更新,所以試著計算 的下一輪, 輪的結果
綜合上述方式,要從最大的位元開始測試,即從 開始試到 ,初始情況為
在程式碼中 z
是 ,m
是 ,x
為 ,b
是 。
for 迴圈的初始情況先將 也就是 m
。首先 (31 - __builtin_clz(x))
可以找到最高位的 1 距離 lsb 的長度。接下來 & ~1UL
讓 (31 - __builtin_clz(x))
算出來的長度調整為偶數,如此一來 1UL
經過位移後,m
必為2的冪且有整數平方根。接下來每次迴圈都會執行 m >>= 2
,對應到上面敘述的 。
迴圈內,z >>= 1
對應到先前敘述的 的計算,先計算 ,是否要將 加入則是由 的值決定,也就是判斷 x >= b
,成立後才執行 z += m
,即為 這段敘述。
__builtin_clz
學習 第二週測驗題 使用二分搜尋法找到最靠近 MSB 並且被設為 1 的位置。接下來將 (31 - __builtin_clz(x))
替換為 (32 - fls(x))
。
無分支的實作會需要另一個變數 move
協助運算。以第一行計算為例,透過 !!
將 x & 0xFFFF0000
的值轉為 0 或 1。
0xFFFFFFFF
,再加 1 會得到 0。0xFFFFFFFE
,再加 1 得到 0XFFFFFFFF
。而 0xFFFFFFFF
就可以作為 mask 和 16 進行 bitwise AND 運算。
在 block/blk-wbt.c 可以找到,從文件開頭可以知道主要是處理 buffered writeback throttling,在 LWN 有找到作者一開始嘗試的情況。大量的 background buffered writeback 會導致 foreground 活動也受影響(下面例子是用開啟 chrome)。
When we do background buffered writeback, it should have little impact
on foreground activity. That's the definition of background activity…
But for as long as I can remember, heavy buffered writers have not
behaved like that.
command 是「命令」,而非「指令」(instruction)
一開始作者使用指令 製作檔案,並且嘗試開啟 chrome,發現要等到 writeback 結束 chrome 才會開啟。
這段程式碼看最後一行 mod_timer
可以知道是調整計時器的倒數時間。
因為 10 不能表示為二的冪,所以透過精確度的計算找到可以使用 來估算除以 10。這邊使用的方式是透過找到 後再乘上 8 即可找到 。
接下來再除 128,可以得到 。
這邊 d0
,d1
,d2
是要處理右移後被捨棄的位元。但這裡應該要對 n
做 bitwise AND 而不是對 q
,因為被右移的是 n
。
下面是另一種表示方式,和上面方式不太一樣。首先計算 x
為 ,但這裡不清楚為何需要 (in | 1)
。再計算 q
為 ,而其中 。接下來四次執行 q = (q >> 8) + x;
是為了讓 q
逼近 ,最後再透過 q >> 3
就可以得到 。而最後 mod
計算,(q & ~0x7)
相當於 div << 3
,所以最後一行程式碼可以看成 in - (8 * div + 2 * div)
。
透過使用 objdump -S
產生組合語言,查看 intel ice lake and tiger lake 的表。以下是使用 /
和 %
。
1 個 push
花費 3 clock cycles。5 個 mov
(r,r) 共花費 5 clock cycles。4 個 mov
(r,m) 共花費 8 clock cycles。5 個 mov
(m,r) 共花費 15 clock cycles。2 個 movslq
(r,r) 花費 2 clock cycles。2 個 imul
共花費 6 clock cycles。2 個 shr
花費 2 clock cycles。4 個 sar
花費 4 clock cycles。3 個 sub
(r,r) 花費 3 clock cycles。2 個 add
(r,r) 花費 2 clock cycles。1 個 pop
花費 3 clock cycles。
總共 53 個 clock cycles。
以下是改為使用 shift/add 方式的組合語言。
1 個 push
花費 3 clock cycles。12 個 mov
(r,r) 花費 12 clock cycles。13 個 mov
(m,r) 花費 26 clock cycles。21 個 mov
(r,m) 花費 63 clock cycles。1 個 or
花費 1 clock cycles。7 個 shr
花費 7 clock cycles。8 個 add
花費 8 clock cycles。2 個 sub
花費 2 clock cycles。1 個 and
花費 1 clock cycles。1 個 pop
花費 3 clock cycles。
總共 126 clock cycles。
參考延伸閱讀 Modulus without Division, a tutorial。先分析 mod 3
的情況。
首先
All of the above rules are actually special cases of a single general rule. Given that
a is represented in number base b
a mod m = ( (b mod m)⌊a/b⌋ + (a mod b) ) mod m
可以得知若要將 a
改為用 b
進位表示(十進位,八進位 …)
觀察上面式子,想要實作 % 3
可以透過將 a
轉為 4 進位,因為 為 即為 。所以整式為
其中可以發現 是取出 a
在四進位中的第一個 digit。而 便是 a
將第一個 digit 移去後剩下的值。所以如果重複執行 直到 a
小於 4,其意思就是將 a
轉為四進位後,把所有 digit 相加。
這個程式碼是基於上面所述以四進位來計算 mod 3
,但計算方式不同。本來的原理是透過計算四進位的所有 digit 總和,而這個方式改為依序計算 進位(內文為 base-)的 digit。接下來再計算 base- 的 digit 總和,再依序算到四進位的 digit 總和。可以透過最一開始的式子證明
用同餘的形式表示
可以再推算
所以要撰寫 mod 9
的方式和 mod 3
類似,但因 9 並非 ,所以需要找到某數為 且為 9 的倍數。所以找到以 為除數來取餘數。
首先找到 63 的餘數,和尋找 3 的餘數方式相同,找 3 的餘數要先計算四進位(base-4)的所有 digit 和,而找 63 的餘數就要先找 base-64 的所有 digit 和,即為 a = (a >> 6) + (a & 0x3F);
。接下來因為 63 的餘數範圍為 0~62,所以再對此餘數 mod 9
,這邊是透過減法撰寫。
TODO: 證明針對 2 的冪 +/- 1 的 modulo 運算可找到對應不依賴除法運算的實作。
判斷 ilog2 就是找到二進位最高位的 1 的位置,版本二是透過二分搜尋法來找。版本三是透過 __builtin_clz
得到最靠近 MSB 的第一個 set bit 前有幾個 0,31 - __builtin_clz
就可以得到最靠近 MSB 的 set bit 到 LSB 共有幾個 bits,就是 ilog2 的結果。
在 ksm.c 中有找到 ilog2
的使用。KSM 是 Kernel Samepage Merging 的縮寫,主要用來找到有相同內容的 page,將他們替代為同一份共享的 write-protected page。
這邊的 ilog2
是用來取得 KSM_RUN_OFFLINE
的 set bit 位置。KSM_RUN_OFFLINE
的值為 4,所以 ilog2
會得到 2。offline 是指某記憶體區塊若要被 kernel 移除(remove),則會被標記為 offlined
。而 wait_on_bit
是讓此 thread 等待直到 ilog2(KSM_RUN_OFFLINE)
位置的 bit 設為 0,才能繼續下一步。
從這篇文章中可以看到作者在製作飲料機的過程中經歷,過程中有許多失敗和挫折,但他還是不放棄的繼續做下去,很值得我學習。製作飲料機和我們學習 Linux 核心的精神很類似,有許多細節和設計都是很重要的卻也很難注意到的。在前幾週的 Linux 核心課程中,我深深體會到自己的不足,學習到軟體開發的態度。以前寫作業都是隨便寫,能跑得出正確答案就好。而現在寫作業需要閱讀大量資料,發現自己連英文閱讀都有點問題,還要注意許多細節,連實驗次數是如何訂定的也要注意,程式語法要直接參考規格書而不是 google 搜尋。
這堂課帶給我的不僅是誠實認知到電腦科學相關知識的不足,也讓我認知到我有許多心態需要改變。老師有說過,真強者是不怕世俗的批評,但我從寫開發紀錄時就發現我不太敢寫出自己的看法,每次寫下一句話就要花很久的時間思考,原因就是怕被批評、害怕別人看法、害怕失敗。老師在第一週就有提到一句話
大部分的人一輩子洞察力不彰,原因之一是怕講錯被笑。想了一點點就不敢繼續也沒記錄或分享,時間都花在讀書查資料看別人怎麼想。看完就真的沒有自己的洞察了
雖然看到這句話想要努力改變,但我在第五週看完老師 code review 後,反而變得更不敢發表自己的意見,因為我發現自己雖然寫了很多作業,但根本沒有掌握細節,許多地方都是似懂非懂。所以後來更害怕自己被批評,讀了論文怕自己哪裡沒讀清楚,怕寫上去後是錯的,所以不敢寫,拖延一段時間後又責怪自己沒有付出夠多的時間寫作業。所以我認為我在這六週表現不好,但看完〈因為自動飲料機而延畢的那一年〉,我了解到自己遇到的挫折和失敗幾乎不值一提,並且增加了許多勇氣,希望能一路堅持到期末。
Linux 核心模組運作原理 提到在新建立的裝置檔案 /dev/fibonacci
的數字會不同。
在 fibdrv.c 中看到註解,於是尋找 register_chrdev
這個函式。先在 fs.h 中找到該函式,接下來在 Linux Kernel API 中看到 major
這個參數,當其為 0 時,會動態配置 device number。
在講解 __MODULE_INFO
的巨集展開時提到
上述巨集的定義根據 MODULE 是否有被定義,MODULE 是在此核心模組被編譯時期所定義,若此模組編譯時已內建於核心則不會被定義。繼續將上述巨集展開
不理解此處,是指 MODULE
在編譯時會自動新增定義嗎?是由誰新增的?
注意看巨集展開,你可嘗試建構 fibdrv 並留意產生的 C 檔案,觀察其內容。 :notes: jserv
模組載入時可以直接使用 init_module()
這個函式名稱是因為原始程式碼中使用 module_init
巨集,展開後會透過 GCC extension alias 連結 init_module()
和我們自訂的模組初始化函式。
fibdrv.ko
是如何植入到 Linux 核心insmod
會使用系統呼叫 finit_module
,再觀察此系統呼叫的程式碼,發現會使用 kernel_read_file 函式透過 file descriptor fd
來讀取檔案。
RISC-V auipc, jalr
TODO:
Known issues