上學期修習台大黎士瑋老師開的「虛擬機器」課程。剛好那時在投入 rv32emu 的系統模擬(system emulation) 開發。課程中學到的東西也持續引導我如何持續改進 rv32emu,比如能不能支援 vhost 加速 virtio 裝置模擬、巢狀虛擬化 (nested virtualization),等議題。這些議題較爲進階,可持續關注。
以下提供一些正在或需要改善的地方:
rootfs.cpio
越來越大會導致解壓縮越來越久進而影響開機速度)。/dev
目錄底下 block device。這份期末簡報或許對陸續參與開發 rv32emu 的人有些幫助 (至少能夠快速掌握關鍵元件)。簡報內還附 WebAssembly 移植的經驗以及 Emscripten 編譯器 CFLAG 的介紹。
2024 年專題: 實作多核 RISC-V 處理器模擬環境並運作 Linux 核心
課程的目的並非在於訓練工程師,而是培養能與工程師有效溝通的人才。因此,我們對各位未來的期望是:
改寫自 給我的學生
\(\to\) 無效的溝通案例,有人即便學習多年的理工,但他人很難從言行看得出其專業。
為何 Linux 和 FreeBSD 一類 POSIX 相容的作業系統,不直接提供記憶體管理的系統呼叫呢?核心只提供 brk, sbrk, mmap 等系統呼叫。
這裡的 brk 不是 Berkshire Hathaway Inc.
探討記憶體配置器的實作,務必理解 free list 的寓意。
參見 CS107, Lecture 24 Explicit Free List Allocator
使用 Digit-by-digit 方法,單純加減與位移運算來開平方根。先觀察其規律
\[
(a+b)^2 = a^2+(2a+b)b
\]
三元平方和
\(\begin{align}
(a+b+c)^2
&= ((a+b)+c)^2 \\
&= (a+b)^2 + (a+b)c +c(a+b) + c^2 \\
&= (a+b)^2 + (2(a+b)+c)c \\
&= a^2 + (2a+b)b + (2(a+b)+c)c
\end{align}\)
四元平方和
\(\begin{align}
(a+b+c+d)^2
&= ((a+b+c)+d)^2 \\
&= (a+b+c)^2 + (a+b+c)d + d(a+b+c) + d^2 \\
&= (a+b+c)^2 + (2(a+b+c)+d)d \\
&= a^2 + (2a+b)b + (2(a+b)+c)c + (2(a+b+c)+d)d
\end{align}\)
考慮一般化的平方和
\[
N^2 = (a_n+a_{n-1}+\dots+a_{1}+a_0)^2
\]
觀察規律可以發現 \(m\) 元平方和可以藉由 \(1\) 到 \(m-1\) 元平方和總和,同時加上一項
\[
Y_{m}=\left[\left(2\sum^{n}_{i=m+1} a_{i}\right) + a_{m}\right]a_{m} = \left( 2P_{m+1}+ a_{m}\right)a_{m}
\]
其中 \(P_{m+1}=a_n+a_{n-1}+\dots+a_{m+2}+a_{m+1}\) 而 \(P_0=N\) 且
\[
P_{m} = P_{m+1} + a_{m},\quad \text{for } 1\leq m<n
\]
總結上述兩個觀察的結果:
數值系統在二進位表示下為:
\[
x = (00b_0b_2\dots b_{n-1}b_n)_2^2
\]
\(b_0\) 為最高位為 \(1\) 之位元,二進位轉十進位如下:
\[
\sum_{i=0}^n b_i\times 2^{n-i}
\]
假設 \(N^2\) 可以用二進位系統逼近:
\[
\begin{align}
N^2
&\approx (b_n\times 2^0 + b_{n-1}\times 2^{1}+\dots b_ 1\times2^{n-1} +b_0\times2^n)^2 \\
&= (a_n + a_{n-1} + \dots a_1 + a_0)^2
\end{align}
\]
其中 \(b_i\in\lbrace 0,1\rbrace,\text{ for }i=0,1\dots,n\) 且 \(P_m=P_{m+1}+a_{m}=P_{m+1}+b_{m}\times 2^{m}\)。故逼近過程只要從 \(m=n\) 也就是最高位元為 \(1\) 開始計算到最低位元 \(m=0\),確認 \(a_m=2^m\) 或是 \(a_m=0\) 對 \(0 \leq m < n\) ,藉由上述 \(P_m=P_{m+1}+b_{m}\times 2^{m}\) 可以確認有兩種可能:
\[
P_m=
\begin{cases}
P_{m+1}+2^{m}, &\text{if }P_m^2 \leq N^2,\\
P_{m+1}, &\text{otherwise.}
\end{cases}
\]
舉例來說,設 \(N^2=10\) 則 \(N^2=(10)_{10}=(1010)_2=(b_3\times2^3+b_1\times 2^1)\) ,最高位元 \(b_3\) 從 \(m=3\) 開始計算。
故 \(N=P_0= a_1 + a_0 = 2^1+2^0= 3\) ,因此 \(10\) 的整數平方根為 \(3\)。
令 \(X_m=N^2-Y_m\) 為差值表實際值與逼近值的誤差,其中 \(Y_m=\left( 2P_{m+1}+ a_{m}\right)a_{m}\) 運用以下性質可以縮減上述計算過程:
由於 \(Y_m=2a_mP_{m+1}+a_m^2\) 與 \(a_m=2^m\) 則可以將 \(Y_m\) 表示為
\[
Y_m = P_{m+1}2^{m+1} + (2^{m})^2
\]
令 \(c_m =2a_mP_{m+1}= P_{m+1}2^{m+1}\) 與 \(d_m = a_m^2=(2^{m})^2\) 。重新將 \(Y_m\) 表示為
\[
Y_m =
\begin{cases}
c_m+d_m, &\text{ if }a_m =2^m, \\
0, &\text{ if } a_m = 0.
\end{cases}
\]
同時藉由 \(P_{m} = P_{m+1}+a_{m}\) 則
\[
\begin{align}
c_m
&= P_{m+1}2^{m+1} \\
&= (P_m-a_m)2^{m}2 \\
&= 2P_m2^{m} - 2a_m2^{m} \\
&= 2c_{m-1} - 2a_m2^m.
\end{align}
\]
如果 \(a_m\neq 0\) 則
\[
c_{m-1} = c_m/2 +d_m.
\]
同時
\[
d_m = (2^m)^2 = (2\times2^{m-1})^2 = 4(2^{m-1})^2
\]
則 \(d_{m-1} = d_m/4\)。
總結迭代關係為
\[
c_{m-1} =
\begin{cases}
c_m/2 +d_m, &\text{ if } a_m\neq 0, \\
c_m/2, &\text{ if } a_m = 0.
\end{cases}
\]
與
\[
d_{m-1} = d_m/4
\]
則可以藉由 \(c_{-1}\) 得知平方根為
\[
c_{-1} = P_02^0 = P_0 = N.
\]
Linux 核心中的整數平方根函數實作於 lib/math/int_sqrt.c 中,使用 Digit-by-digit calculation 方法來計算開平方根:
/**
* int_sqrt - computes the integer square root
* @x: integer of which to calculate the sqrt
*
* Computes: floor(sqrt(x))
*/
unsigned long int_sqrt(unsigned long x)
{
unsigned long b, m, y = 0;
if (x <= 1)
return x;
m = 1UL << (__fls(x) & ~1UL);
while (m != 0) {
b = y + m;
y >>= 1;
if (x >= b) {
x -= b;
y += m;
}
m >>= 2;
}
return y;
}
__fls
用於找到輸入 x 的最高有效位(Most Significant Bit, MSB),並設定變數 m 為 2 的冪值。接著使用 Digit-by-digit calculation 方法迴圈計算開平方根,直到 m 變為 0。
延伸閱讀: 位元操作的應用
考慮以下 C 程式: (檔名 div3.c
)
int div3(int x) { return x / 3; }
開啟最佳化編譯:
$ gcc -O3 -S div3.c
可得到 div3.s
的輸出,針對 x86-64 處理器架構:
div3:
movslq %edi, %rax
sarl $31, %edi
imulq $1431655766, %rax, %rax
shrq $32, %rax
subl %edi, %eax
ret
原本的「除以 3」去哪?這個 1431655766
數值是什麼?
在 Arm64 有類似的輸出:
div3:
mov w8, #21846
movk w8, #21845, lsl #16
smull x8, w0, w8
lsr x9, x8, #63
lsr x8, x8, #32
add w0, w8, w9
ret
編譯器最佳化的依據是什麼?
來自學員貢獻的程式碼:
typeof
運算子 (最初是 GNU extension,後來納入 C23 標準) 而無法定義 list_for_each_entry
巨集,致使 Cppcheck 靜態分析拋出錯誤。感謝 lumynou5案例: Dennis40816
由於先前 commit 未符合CONTRIBUTING.md 的規範與七條原則,我針對相對應 commit 進行 git rabase -i
加以修正。
首先,針對原先第一條 commit,我應當將 q_new
, q_free
與 q_insert_head
, q_insert_tail
分別置於兩則不同 commit,以達到CONTRIBUTING.md 中 Git commit style 所要求之
Each commit should encapsulate a single, coherent change.
以下是更正過後的 commit:
第二則 commit 應當說明實作手法,例如讓 q_insert_head
和 q_insert_tail
共用程式碼片段。注意 CONTRIBUTING.md 的規範:
Use the body to explain what and why, not how.
再者,對於本來的第二條 commit,我應避免濫用 finish 一詞:
to complete something or come to the end of an activity:
q_remove_head
和 q_remove_tail
仍有改進空間。在工程領域,不要輕易說 "finish"。
以下是更正後的 commit :
commit 91aca2d
最後,對於原來的第三則 commit,我改進英語書寫。並遵循 CONTRIBUTING.md 的規範,針對 "what" 與 "how" 進行著重探討。
以下是更正後的 commit :
commit 3769f55
如何寫出正確的 git commit message ?
TODO: 改進後,使用 git rebase -i
和 git push --force
發布於 GitHub,並檢討項目下方列出對應的 commit 超連結
檢討:
From 2eb50d2b59d204dfdfce1418928d1832b3825554 Mon Sep 17 00:00:00 2001
From: bevmmf <bevis30401@gmail.com>
Date: Mon, 24 Feb 2025 11:09:41 +0800
Subject: [PATCH 1/3] Finish 4 functions :
q_new,q_free,q_insert_head,q_insert_tail
Through the work on that 4 functions,i get familiar with the doubly
linked list in linux as well as API about list.h.
There is one problem i meet about not initialize the tool pointer like trav on static analysis.
It was solved by initialing.
commit message 的主題 (subject) 列出 4 個函式,沒必要置入於同一 commit,注意 CONTRIBUTING.md 的規範:
Group Related Changes Together Each commit should encapsulate a single, coherent change. e.g., if you are addressing two separate bugs, create two distinct commits. This approach produces focused, small commits that simplify understanding, enable quick rollbacks, and foster efficient peer reviews. By taking advantage of Git’s staging area and selective file staging, you can craft granular commits that make collaboration smoother and more transparent.
可將 q_new
和 q_free
置入同一 commit,而 q_insert_head
和 q_insert_tail
放入另一 commit。
"There is one problem i meet about not initialize the tool pointer like trav on static analysis." 超過一行 72 個字元的限制,務必更新 lab0-c
以得到 Git hooks 的檢查修正。
注意 CONTRIBUTING.md 的規範:
Use the body to explain what and why, not how.
應當說明實作手法,例如讓 q_insert_head
和 q_insert_tail
共用程式碼片段。
檢討:
From 1dc27b39ba6230db3cee5ae72e807fa740ef488b Mon Sep 17 00:00:00 2001
From: bevmmf <bevis30401@gmail.com>
Date: Mon, 24 Feb 2025 11:57:22 +0800
Subject: [PATCH 2/3] Update 2 functions q_remove_head,q_remove_tail
I finsh the 2 functions :
q_remove_head
q_remove_tail
It is verified with executing qtest and experimenting.
Through doing it,i learn the function strncpy in string.h.
避免濫用 finish 一詞:
to complete something or come to the end of an activity:
q_remove_head
和 q_remove_tail
仍有改進空間。在工程領域,不要輕易說 "finish"。
檢討:
From e546273f2117f84329b7c4ff9a3343dfb4c2be23 Mon Sep 17 00:00:00 2001
From: bevmmf <bevis30401@gmail.com>
Date: Tue, 25 Feb 2025 10:05:48 +0800
Subject: [PATCH 3/3] Implement q_reverse and q_swap functions
Successfully implemented q_reverse without issues. However, encountered
problems with q_swap. Initially, execution got stuck, so I used gdb to debug
and discovered an infinite loop.
After reviewing the overall program logic and finding no major structural
issues, I suspected a problem with the swap2node function. I conducted a
static test on swap2node and confirmed a logical error. The issue was that
only the target node was handled without considering its neighboring nodes.
After fixing this, the function now works correctly.
改進英語書寫,這是 ChatGPT 一類的工具可直接幫助你的地方。而且,既然你宣稱使用 GDB,應當分析原本的程式為何會出問題 (可列出 stack frame) 並討論後續處置。
這次在課堂上被老師問到關於 q_swap()
的實作,重新審視自己的程式碼發現雖然可以運作但是程式碼的可讀性太低,因此這次重新實作 q_swap()
加入了 Linux 核心風格的鏈結串列 API , 靈感來自 2 月 25 日測驗。
首先要修正的是老師提到的若鏈結串列為空或 singular 的情況下不用作兩兩互換,可以使用 list_empty()
以及 list_singular()
作處理。再來是節點兩兩互換的部份,我觀察到了一個好用的操作 list_move()
,它可以將指定節點從原本的串列移除並插入到指定串列。
至於 if 條件判斷則是要處理鏈結串列節點個數為奇數的情況,這個部份還可以作修正。
commit ca748f4
void q_swap(struct list_head *head)
{
list_head *node;
if (list_empty(head) || list_is_singular(head))
return;
list_for_each (node, head) {
if (node->next != head)
list_move(node->next, node->prev);
}
}
接著第二個議題是網頁伺服器與命令列輸入共存的實作,在原先 web.c 實作的 web_eventmux
函式當中,會有透過 read 系統呼叫來讀取 socket 的內容,但是 read 這個系統呼叫預設為 Blocking-I/O ,因此會影響原先命令列輸入讀取鍵盤內容的功能。
參考: 檔案系統概念以及實作手法
Blocking-I/O Model 有分成兩個階段,首先是等待 I/O 資料準備就緒,最後是實際將核心空間的資料搬移到使用者空間。以上述問題來說,我們需要同時等待 socket 以及 keyboard 的資料到來,但是原先的 read 只能等待其中一者,因此我們需要另一個系統呼叫 select 。
select 可以同時監視多個 file descripter ,直到其中一者的 I/O 資料準備就緒,隨後再使用 read 系統呼叫讀取在核心空間當中的資料。有了 select 的好處是可以在單工程式中監視多個 I/O 事件。
struct sockaddr_in clientaddr;
socklen_t clientlen = sizeof(clientaddr);
int web_connfd =
accept(server_fd, (struct sockaddr *) &clientaddr, &clientlen);
+ fd_set listenset_2;
+ FD_ZERO(&listenset_2);
+ FD_SET(STDIN_FILENO, &listenset_2);
+ FD_SET(web_connfd, &listenset_2);
+ max_fd = STDIN_FILENO > web_connfd ? STDIN_FILENO : web_connfd;
+ int result = select(max_fd + 1, &listenset_2, NULL, NULL, NULL);
+ if (result < 0)
+ return -1;
+ if (FD_ISSET(STDIN_FILENO, &listenset_2)) {
+ FD_CLR(STDIN_FILENO, &listenset_2);
+ return 0;
+ } else {
+ FD_CLR(web_connfd, &listenset_2);
+ }
請問自我評量沒滿分,是否就拿不到認證碼。
你可對表單反覆提交答覆,直到拿到認證碼為止
關於 swap 與 reversek 有什麼相似處 ?
swap 是將整條鏈結串列每兩個節點編隊一組做順序交換,若鏈結串列節點數為奇數個,則不更動最後一個節點。
reverseK 是將整條鏈結串列每 K 個一組,組內順序反轉,所以可以把 swap 當作是 reverseK 在 K=2 的特例。
TODO: 善用既有的函式,撰寫更精簡的程式碼。
void q_swap(struct list_head *head)
{
if (list_empty(head) || list_is_singular(head))
return;
struct list_head* cur = head->next, *nextpair;
while (cur!=head && cur->next!=head) {
nextpair = cur->next->next;
list_move(cur, cur->next);
cur = nextpair;
}
}
void q_reverseK(struct list_head *head, int k)
{
if (list_empty(head) || list_is_singular(head) || k == 1)
return;
struct list_head *prev = head, *cur, *next;
int count = q_size(head);
while (count >= k) {
cur = prev->next;
next = cur->next;
/*
* Reverse k nodes by moving the i-th node
* to the front of the k-group each round.
*/
for (int i = 1; i < k; i++) {
list_move(next, prev);
next = cur->next;
}
prev = cur;
count -= k;
}
}
使用指定的程式碼縮排格式,詳見: CONTRIBUTING.md
外層迴圈將鏈結串列分成 k 個一組,內層迴圈則將該組最後一個節點移至最前面,重複 k-1 輪,如此一來便能達到組內 reverese 的效果。
因為swap 是 reverseK 在 K=2 的特例,因此 q_swap()
也可以下述方式實作:
void q_swap(struct list_head *head)
{
q_reverseK(head, 2);
}
從泰勒定理可以得知,假設函數 \(f\) 為二次可微連續函數,和 \(p\) 為 \(f(p) = 0\) 的一解,令 \(p_0 = p - h\) 為 \(p\) 附近之一點,其中 \(h\) 為足夠小的正數,則對 \(p_0\) 的一階泰勒多項式為:
\[ 0 = f(p) = f(p_0 + h) = f(p_0) + h f'(p_0) + \frac{h^2}{2} f''(\xi). \]
其中,\(\xi\) 位於 \(p\) 與 \(p_0+h\) 之間。
怎樣才能得到 \(\frac{h^2}{2} f''(\xi) ?\)
在 \(p\) 點附近的泰勒多項式逼近為:
\[0 = f(p) = f(p_0 + h) = f(p_0) + h f'(p_0) + \frac{h^2}{2} f''(p_0) + \dots +\frac{h^n}{n!} f^n(p_0)+ \dots\]
不難發現,二階導數項開始每個項對整個函數的值影響非常小(因為 \(h\) 足夠小),於是我們可以嘗試用一個項的形式來表示。
假設F,G兩函式在閉區間[a,b]連續,在開區間(a,b)可微,且對於所有的 \(x \in (a,b)\), \(G'(x) \neq 0\), 則至少存在一個 \(\xi\) 使得 \(\frac{F(b) - F(a)}{G(b) - G(a)} = \frac{F'(\xi)}{G'(\xi)}\)
Step 1 :
泰勒展開式的餘項 \(R_n\) 定義為:
\[ R_n:=f(p) - \sum_{k=0}^n \frac{f^{(k)}(p_0)}{k!} h^k = \sum_{k=n+1}^\infty\frac{f^{(k)}(p_0)}{k!}h^k \]
其中:
Step 2:
\(F(x) = \sum_{k=0}^n \frac{f^{(k)}(x)}{k!} (p - x)^k\)
\(G(x) = (p - x)^{n+1}\)
注意到 \(F(p) = f(p)\) 以及 \(F(p_0) = \sum_{k=0}^n \frac{f^{(k)}(p_0)}{k!} h^k\)
Step3:
\(F(p) - F(p_0)= R_n = \frac{F'(\xi)}{G'(\xi)}[G(p) - G(p_0)]\), 對於 \(\xi \in (p_0, p)\)
\(F'(\xi) = \frac{f^{(n+1)}(\xi)(p-\xi)^{n}}{n!}\)
\(G'(\xi) = -(n+1)(p-\xi)^{n}\)
其中 \(\xi\) 為 \(p_0\) 和 \(p\) 之間的一點,由平均值定理得來。將 \(h\) 的一次項移至等號左側則有:
\[-h f'(p_0) = f(p_0) + \frac{h^2}{2} f''(\xi).\]
只要 \(f'(p_0) \neq 0\),等式兩側同除以 \(-f'(p_0)\) 得:
\[h = -\frac{f(p_0)}{f'(p_0)} - \frac{h^2 f''(\xi)}{2 f'(p_0)}.\]
故 \(p_0 + h\) 可以寫為:
\[p = p_0 + h = p_0 - \frac{f(p_0)}{f'(p_0)} - \frac{h^2 f''(\xi)}{2 f'(p_0)} = p_0 - \frac{f(p_0)}{f'(p_0)} + \mathcal{O}(h^2).\]
\(\mathcal{O}(h^2)\) 表示剩餘項的量級為 \(h^{2}\),即當 \(h\) 很小時,剩餘項的大小與 \(h^{2}\) 成正比。這意味著,當 \(h\) 趨近於 \(0\) 時,該項對整體的影響變得非常微小。
從上述推導的過程中,得知 \(p\) 點可以由附近點 \(p_0\) 與該點斜率和函數值逼近:
\[p \approx p_0 - \frac{f(p_0)}{f'(p_0)}.\]