owned this note   changed 7 days ago  
Linked with GitHub

2025-03-11 討論簡記

回顧上週討論

2025-03-04

貢獻 Linux 核心的第一手經驗

Linux 核心經驗分享

stable kernel tree
LTS
merge window vs. next tree
A guide to the Kernel Development Process

min heap 的應用案例: priority queue
inlining calls
git bisect

EricccTaiwan

Q: 發現並非改錯字的小錯誤，是比較大的更動，想要發 patch 進行修正，是直接發 patch 嘛?

A: 若是簡短的 code (100行左右) 可以直接發 patch 。比較大的更動，建議先發 RFC (Request For Comment) 給 maintainer 討論/尋求建議。但能否被接受，還是取決於 maintainer 的個性，需要透過 commit message (靜態分析，數學推導 …) 去說服 maintainer 收錄這份 patch 。

The canonical patch format

The summary phrase may be prefixed by tags enclosed in square brackets: “Subject: [PATCH <tag>…] <summary phrase>”. The tags are not considered part of the summary phrase, but describe how the patch should be treated. Common tags might include a version descriptor if the multiple versions of the patch have been sent out in response to comments (i.e., “v1, v2, v3”), or “RFC” to indicate a request for comments.

BigMickey69

Q: Linux 核心中會不會有找不到 maintainer 或是 maintainer 很混的話怎麼辦?

A: Maintainer 找不到人的情況是會發生的，但一個系統不會只有一個 maintainer，就像一棵樹狀結構，一個 maintainer 只是一枝樹枝，他的上面還有很多管理者，而那些人通常都全職在維護核心(或許九成全職、一成自願)，所以不會真的完全找不到人。

Q: 假設意見與 Maintainer 不合時但認為自己還是正確的該怎麼辦?

A: 可以往上找權力更大的 Maintainer 與他商量看看。

eleanorLYJ

Q: 既然 overcommit 會讓 kmalloc 發生失誤的機率變很低，那要怎麼說服 maintainer 去收你的相關 patch ?

A: 由於 kmalloc 發生失誤的情況很少，所以需要在 commit message 裡說明是怎樣的特定情況會導致失敗發生。

NeedToDebugMyLife

Q: 在程式上的精簡是否是可以被接受的修正，如果這個精簡是對整體效率或時間複雜度沒有太大影響的話?

A. 這種 patch 就跟修改註解錯字類似，對於 kernel 整體的運作沒有太多的幫助。但每個 maintainer 的接受程度不同，如果是在處理 bug 時順便做出的修正，那對於大多數的 maintainer 而言是可以被接受的。

JeffBla

Q: min heap 優化的動機和緣起是什麼？對於第一次的 patch 有在這方面著墨，想知道是什麼因緣際會下，能夠對此做出相對重要的貢獻？

A: 因為 sorting 在 kernel 相對冷門，面對熱門甚至是拿著薪水維護 kernel 的專業工程師，為了想對 kernel 也同樣盡點心力，先從冷門處著手。

salmoniscute

format.c

static size_t apm_string_size(apm_size size, unsigned int radix);

apm_string_size 函式可以計算表示一個特定大小數字所需的空間。對於相同的參數（apm_size 和 radix），它總是計算出相同的空間大小，不考慮實際數值。例如：

當 apm_size 為 1，基數為 10 時，在 64 位系統上總是分配 22 byte
當 apm_size 為 2，基數為 10 時，在 64 位系統上總是分配 41 byte

為什麼呢？
假設有 apm_digit num2[2] = { a, b }，表示一個大整數 \(b * 2^{64} + a\)。由於 a 和 b 的最大值都是 2^64 - 1（64位系統），此整數的最大可能值為 \((2^{64} - 1) * 2^{64} + (2^{(64 - 1)}\)，即 \(2^{128} - 1\)
以十進制來說，表示這個數字需要的位數約為：
log10(2^128) ≈ 128 * log10(2) ≈ 128 * 0.301 ≈ 39 位數字

return (size_t)(radix_sizes[radix] * (size * APM_DIGIT_SIZE)) + 2;

但是程式碼又另外加 2 為什麼呢？
我猜是 考慮到低位數的影響
假設 size 為 n ，apm_digit num[n] = { a, b, c , ... , 1 }，代表一個大整數：\(1 * 2^{(64*(n-1))} + .... + b * 2^{64} + a\)
假設 \(k\) 為 \(64 * n\)
較低位展開化減後，十進制表示大約需要 \(\lfloor \log_{10}(2^{k-1}) \rfloor\) 個位元
全部加起來後， 十進制表示需要 \(\lfloor \log_{10}(2^{k}) \rfloor\) 個位元
可以證明：
\[ \lfloor \log_{10}(2^{k}) \rfloor \leq \lfloor \log_{10}(2^{k-1}) \rfloor + 1 \]
這表示從 \(2^{k-1}\) 到 \(2^{k}\) 時，最多增加 1 位數。

由於 \(\log_{10}(2) \approx 0.30103 < 1\)，這表示：

  • 如果 \(\log_{10}(2^k)\) 的小數部分加上 \(0.30103\) 仍小於 1，則長度不變。
  • 如果加上 \(0.30103\) 超過 1，則 長度增加 1。

但由於每次最多增加 \(0.30103\)，所以最多增加 1 位數，不可能增加 2 位數。
（可以推知其他進制也是樣，程式碼中提供 2-36）

所以我猜那個 +2 裡面的其中一個 1 是因為進位，另一個可能是給 \0。

可以看到原本的 apm_string_size 函式不管計算數字陣列裡面的值是什麼 ，他只管 size ，即使陣列裡面全部都是 1 ，他配置的空間還是會可以塞得下陣列裡面全部都是最大值的情況。

所以先試著改成以下（以十進位為例）：

if (radix == 10) {
    int highest_digit_bits = APM_DIGIT_BITS - apm_digit_msb_shift(u[real_size-1]);
    unsigned int total_bits = (real_size - 1) * APM_DIGIT_BITS + highest_digit_bits;
    return (size_t)(total_bits * 0.30102999566) + 2;
}

對於陣列中除了最後的數值的其他數值，假設它們都使用了所有 64 位元，即為最大值。
想成一個長度為 n 的陣列，最後一個值是 1 ，剩下的值即使全部都是 \(2^{64} -1\)，剩下的值相加也只會是 \(2^{(64*(n-1))} - 1\)
所以在二進位表示下，最少最少會需要
\[ (n - 1) * 64 \]

對於最高位數字，計算其實際使用的位元數，然後將總位元數乘以 log10(2) 得到十進制位數

範例測試:

apm_digit num2[3] = { 1, 2, 123456789 };

Number in base 10: 
string_size = 60
42010168373378879565782048174555128126049878017

Number in base 10: 
string_size = 49
42010168373378879565782048174555128126049878017

但我還沒嚴謹測試正確性還有效益

3/18 更新

上課聽了教授對於範圍的說明 讓我思考原始碼用法的用意
為什麼 apm_string_size 不考慮實際數值，只考慮 size 而計算出相同的空間大小。

SimonLiu423

Q: 對 Linux 核心做一些修改後，要如何確保會不會造成其他子系統出現預期外的錯誤？有沒有什麼 Unit Test 之類的東西？

A: 這問題很深，可以講一節課，有很多不同測試的 framework、tools 可以用，像是有 test bot 會去隨機執行不同的程式碼…

dingsen-Greenhorn

Q:人生中在 linux kernal 擔任 maintainer 遇到最大的 bug 是什麼，當問題牽扯許多領域時？如何快速的評估重要鑽研方向？

A:以我所 maintain 的 min heap 為例，當有人告訴我在 amd 處理器上會有無法進入休眠模式的錯誤時，是因為某個 sort 原因時，僅管我可能有其他正職需要處理，我還是必須加速盡全力修復，避免我之前提交的心血，被其他高手覆蓋並修復。而遇到問題時，我會請教相關的 maintainer 並期待他會給我正確的指引，這也是我認為擔任 maintainer 的必要能力。

Machine Learning for Load Balancing in the Linux Kernel

bpftune - BPF driven auto-tuning

Best-effort

Linux Kernel Autotuning

Select a repo