contributed by < linjohnss > GitHub: rcuhashbash 目標 Linux 核心提供一套 Resizable, Scalable, Concurrent Hash Table，名為 rhashtable (見 include/linux/rhashtable.h 及 lib/rhashtable.c)，描述於論文〈Resizable, Scalable, Concurrent Hash Tables via Relativistic Programming〉。摘譯 LWN 文章，並佐以原論文，描述 rhashtable 何以落實高效的並行雜湊表，搭配撰寫 Linux 核心模組作為試驗 Relativistic hash tables, part 1: Algorithms hash table 在 Linux 的應用場景 在 Linux 的 file system 中，利用 hash table 儲存 mount 的 root dentry ，因此 lookup_mount 可以利用 hash_get 取得 mount 的 root dentry

contributed by < linjohnss > 2022q1 第 6 週測驗題 測驗 1 利用 clone 實做 user level 的 thread 函式庫 程式碼實做原理 函數使用

contributed by < linjohnss > 2022q1 第 5 週測驗題 測驗 1 實作利用 Sieve of Eratosthenes，嘗試找出第 1500 個回文質數，有效位數是 15 演算法: sieve of Eratosthenes 給定要找的質數範圍 n，找出 $\sqrt n$ 內的所有質數，並依序剔除每著質數在範圍 n 內的所有倍數，留下來的數字即為和為內的所有質數。

contributed by < linjohnss > 作業要求 自我檢查清單 [ ] 研讀上述 ==Linux 效能分析的提示== 描述，在自己的實體電腦運作 GNU/Linux，做好必要的設定和準備工作 $\to$ 從中也該理解為何不希望在虛擬機器中進行實驗; [ ] 研讀上述費氏數列相關材料 (包含論文)，摘錄關鍵手法，並思考 clz / ctz 一類的指令對 Fibonacci 數運算的幫助。請列出關鍵程式碼並解說 [ ] 複習 C 語言 數值系統 和 bitwise operation，思考 Fibonacci 數快速計算演算法的實作中如何減少乘法運算的成本; [ ] 研讀 KYG-yaya573142 的報告，指出針對大數運算，有哪些加速運算和縮減記憶體操作成本的舉措？

測驗題目 測驗 1 程式碼運作原理 功能 輸入大於 0 的無號整數，計算 $\lceil log_2(x) \rceil$ 實做 int ceil_log2(uint32_t x) {

測驗題目 測驗 1 程式碼運作原理 功能 產生連續的 bitmask GENMASK(6, 4) 產生 01110000~2~ GENMASK(39, 21) 產生 0x000000ffffe00000 (64 位元)

contributed by < linjohnss > 測驗題目 測驗 1 無號整數取平均值 程式運作原理 兩個無號整數取平均，代表在實做過程中我們不需要考慮 sign bit 的問題，但仍需考慮 overflow 的問題。 第一個等價實作 #include <stdint.h>

contributed by < linjohnss > 作業要求 針對 Queue 的操作 滿足 $ make test 自動評分系統的所有項目 也可以用 $ ./qtest -f traces/trace-XX-CAT.cmd 來針對單一項目測試 q_new: 建立新的「空」佇列 q_free: 釋放佇列所佔用的記憶體 q_insert_head: 在佇列開頭 (head) 插入 (insert) 給定的新節點 (以 LIFO 準則)

contributed by < linjohnss > 測驗題目 測驗 1 Leetcode 1. Two Sum 變數結構 變數節有 4 種：

公式  $$ \begin{split} &w為寬，l為長\ &A，B，C，D為原始輸入座標\ &A'，B'，C'，D'為修正後座標\ &I為\triangle ABD重心\ &J為\triangle BCD重心\ &L為\square ABCD重心\\\