contributed by < BooleanII
>
改進你的漢語表達。
手邊沒有閒置的電腦可以安裝 Ubuntu 實體機,先以 Win10 WSL 虛擬機獲得 Ubuntu 22.04.03 LTS測試。
每天用 Linux,自然就會變強,拿出你的決心來。
購置新的電腦安裝 Ubuntu 實體機,安裝前須先關閉 bitlocker
與快速開機設定,否則會免費驗一次 bitlocker 解除流程,硬碟磁碟區可使用壓縮硬碟方式從 C 槽分割出想要的空間。 boot loader
位址選擇硬碟的根目錄,並將方才分割出的空間指定為 /
目錄, home 與 swap 目錄空間不需額外指派,安裝完成後重新開機進入 Ubuntu 系統就大功告成了。剩餘的環境建安裝流程相較 WSL2 順利不少。
參照教學流程安裝 linux-tools-common 後, perf list 命令獲得的結果共列出四樣東西需要安裝,然而每一樣 package 皆無法在 WSL 下順利安裝。在網路上找到許多方法,但實際操作僅有手動下載 WSL2 Kernel 並編譯 perf 可以解決問題。
q_insert_head
使用自行建立的 e_new 函式 malloc 新的資料節點,佇列成員以 INIT_LIST_HEAD 進行初始化。字串使用 strncpy 取代 strcpy 避免不安全的記憶體操作 字串使用 strncpy 進行複製,避免 strcpy 的不安全記憶體操作風險。
改進你的漢語表達。
依據 CERN Common vulnerabilities guide for C programmers 建議而移除 gets / sprintf / strcpy 等不安全的函式
q_insert_tail
與 q_insert_head 大同小異,改呼叫 list_add_tail
函式以 FIFO 方式加入。
q_free
透過 list_for_each_entry_safe 巨集,可走訪整個佇列並對佇列內容進行更動,巨集所使用的變數如下:
由於 element_t
結構體中, value 成員與資料節點使用 malloc 獲得,故需對這兩者的記憶體位置進行釋放,最後也要記得將 head 的記憶體位置釋放。
q_remove_head
使用 strncpy
進行字串的複製,會遇到當資料節點的字串長度小於 bufsize 時,剩餘的長度資料會被填0替代,故加入判斷式避免 sp 的字串與原始資料不符。
q_delete_mid
留意資訊科技詞彙翻譯
分別使用兩個 list_head 指標( forward, backward )以相反的方向走訪佇列,當兩個指標相遇時, foward 的位置即為要刪除的資料節點。
q_swap
參考 millaker,發現使用 list_del 後的程式碼看起來簡潔一些。基於他的程式碼再做點改進,呼叫 list_add 讓整個思路更加明瞭。後來發現到這個其實就是 list_move 函式…
使用作業指定的程式碼縮排風格
q_reverseK
輸入參數 k 的群組節點數量應大於1才需要進行 reverse 動作。一開始想到的方法是用 for 迴圈找出群組的起始與結束節點,再從兩端進行節點的互換,但這麼做會用到大量的暫存參數。換個角度思考,可以將群組切割為群組佇列,再使用先前實作的 q_reverse
進行反轉。
lins.h 中提供的 list_cut_position
可以實作佇列切割的功能,輸入參數說明如下:
@head_to
:切割後的佇列指標,傳入前可不需執行 INIT_LIST_HEAD
初始化,函式執行後將儲存來源佇列的第一個資料節點到切割的資料節點@head_from
:來源佇列指標,函式執行後將儲存切割的資料節點後方剩餘的資料節點@node
:切割的資料節點。須注意 list_cut_position 的例外條件有二,第一個為來源佇列無資料節點;第二個為切割的資料節點是來源佇列的頭節點。
群組佇列反轉後,使用 list.h 中的 list_splice_tail
儲存於暫存的佇列中,並重複切割、反轉與儲存 head 剩餘的群組佇列,如來源佇列的剩餘節點數量不足以組成一個群組,仍執行佇列分割但不進行反轉,最後呼叫 list_splice
將群組佇列接回到原始的佇列中。深刻感受到 list.h 提供許多好用的函式,搞懂並活用可以加快寫作業的速度。
q_descend
給定的佇列具備雙向且環狀的屬性,你不該說「反向」,改用更精準的詞彙,寧可用更多的詞彙和描述,務必降低誤解,此乃工程協作之關鍵素養。
在 leetcode 進行測試確認函式的邏輯,發現可以透過反向往 prev
方向走訪佇列來實作。當左方 prev 的資料節點小於等於當下的資料節點時( q_ascend
的判斷機制則為大於等於),呼叫 list_del
將該節點自佇列中 remove
,並重複上述行為直到佇列的開頭。走訪方式參考 list_for_each_safe
進行實作。
測試程式功能時,發現在離開 qtest 或執行 free 命令, qtest 會顯示有空間未被正常釋放,顯示題目的需求為 delete
非 remove
,建議將函式的描述用詞進行修改避免混淆。
q_delete_dup
參照 leetcode 82. Remove Duplicates from Sorted List II
題目說明,刪除已完成排序
佇列中的 value
相同的節點。
由於是對已完成排序的佇列進行處理,內容為相同 vaule 的節點必定相鄰,讓實作的方法簡單很多。透過 list_for_each_safe 走訪整個佇列,以 list_head 結構體 dup_beg
與 dup_end
紀錄相同 value 節點的起始節點與結束節點, dup_beg 與 dup_end 相同時代表目前無兩個以上 value 相同的節點。若遇到內容為相同 value 的節點時,則 dep_end 會指向該節點。
若走訪的節點 visit 與下一個節點 visit_next 的字串不同,且 dup_beg 與 dup_end 指向的節點也不同時,代表有重複的節點要進行刪除,將 dup_beg 到 dup_end 之間的節點移至 head_delete 下,並參照 q_free 的實作方法把 head_delete 中的節點刪除。
由於 list_for_each_safe 的結束條件為 visit!=head ,需要處理走訪到最後一個節點時的特殊案例,避免 head 與最後一個節點的 value 進行比較引發 segmentation fault 。
q_merge
函式功能參照 leetcode 23. Merge k Sorted Lists
題目內容,將已完成排序的佇列合併至第一個佇列。 需注意此函式的輸入僅有 struct list_head 指標與決定合併順序的 bool 參數,這是因為 qtest 中的所有佇列使用 queue_contex_t 結構體進行儲存,其架構與 linux kernel 的環狀佇列相似,第一個開頭結構體中未儲存資料。
queue_contex_t 結構體的 chain 成員用於實現 queue_context_t 環狀佇列,函式的 head 輸入即為此成員; q 成員則是資料佇列的 head ; id 成員用於標示 queue_contex_t 節點的代號; size 成員用於儲存 q 成員中的資料節點數量 (不包含head)。
由於所有的資料佇列皆已完成排序,可透過走訪 queue_contex_t 佇列,比較每個資料佇列的第一個資料節點,依據函式輸入的 descend 參數,找出所有資料佇列中最小或最大的資料節點。透過 list_del 與 list_splice_tail 函式將該資料節點取出並加入用於暫時儲存最終合併的 sorted 佇列中。當所有的資料佇列內皆無資料節點,代表已完成佇列合併,可呼叫 list_splice 函式將 sorted 佇列中的節點儲存至 queue_contex_t 佇列的第一個資料節點內。
後記:
一開始想到的合併方式較為繁瑣難以透過簡潔的程式碼達成,合併流程是將在 queue_contex_t chain 中走訪到的第一個佇列作為 sorted 佇列,透過走訪 sorted 佇列的資料節點與下一個合併對象的佇列資料節點進行比較,當找到可以合併的資料節點時,改走訪合併對象的佇列,透過 list_del 與 list_splice 將可合併的資料節點進行合併。當合併對象佇列的資料節點不滿足合併條件時,再回到 sorted 佇列走訪剩餘的節點,若合併對象佇列在 sorted 佇列走訪到末端節點時仍有資料節點,則將剩餘的資料節點直接使用 list_splice_tail 合併。單寫完流程描述就覺得很複雜…
時序攻擊 (Timing attack) 使用程式的執行時間,破解密碼系統以取得正確的系統密碼或金鑰。為了避免此問題的發生,可透過人工進行 code review 或利用自動檢查工具,確認程式碼的執行時間與輸入內容無相關性。
自動檢查工具常見使用靜態程式碼分析,確認程式的執行流程或記憶體存取狀態,然而此缺點為受限於需對硬體建立模型,否則難以準確估算程式的實際運算時間。本篇論文的作者提出使用預先定義好的測試數據,對程式碼實際運作時間分佈進行統計分析。簡單來說與其單純使用理論進行分析,不如直接用測試數據量測執行時間,透過統計學的方式確認是否滿足 constant time 。
論文作者提出的方法分為三大步驟
建立測試資料
測試數據共分為常數資料
與亂數資料
兩大種類。前者通常會設計為可以使執行時間大幅變動的邊角案例 (corner case) ,測試過程中會將常數資料與亂數資料會被隨機且交錯的進行測試,降低受到其他並行行程 (concurrent process) 的影響。
量測實際運作時間
精確的實際運作時間量測可透過 CPU 運算週期計數器或 MPU 的 timer 計數器實現,但須注意應將輸入資料的準備時間排除,而獲得的實際運作時間在進行統計前可先進行下列兩項後處理 (post-processing) :
the two timing distributions are equal
』 作為驗證程式是否滿足 constant time 的虛無假說 (null hypothesis) ,虛無假說是一種統計學上進行假說檢定 (hypothesis testing) 的假說種類,而假說檢定是推論統計中用於檢定現有數據是否足以支持特定假設的方法。對於實驗結果使用到 Cumulative Distribution Function (CDF) 進行分析,其在維基百科的中文名稱為累積分布函數或機率分布函數,簡稱為分佈函數。其函數的定義為取一隨機變數數值 x ,其小於 X 的機率即為分佈函數。乍看之下與 Percentile Rank (俗稱 PR 值)很像,但兩者並不全然相同, PR 值是對具體數值統計總量
,而 CDF 指的是該取樣某一數值時,得到小於等於該數值的機率
。
以一個班級的學生數學成績作為例子,分數 87 分的 PR 值假設為 90% ,代表該班級總共有 90% 的學生分數小於等於 87 分;而 CDF 則代表在該班級進行抽樣,抽到的小於或等於87分的機率值為 0.9 。
論文的測試實驗程式碼應用功能有 memcmp
、 AES128實作
與 Curve25519計算
共三種,確認其提出的檢查工具 dudect 可正確判斷該程式碼的運算時間是否為 constant time 。
本篇論文的 discussion 提到幾個重點值得省思:
perf stat
命令用於統計目標程式的性能分析,支援多次執行針對特定或一系列的 event 進行統計分析。依照 Linux 效能分析工具: Perf 練習 perf 使用方式時,發現對下列範例程式執行 perf stat 的結果不太一樣。
在自己電腦上執行的統計結果多了 cpu_core 與 cpu_atom 字眼,經過查詢後得知 Intel 在第 12 代處理器導入 異質運算 (Heterogeneous Computing) 架構, CPU 會同時具備高運算能力的 performance core(cpu_core) 與高效能的 efficiency core(cpu_atom) 兩種核,此電腦搭載的 i3-1215U 處理器有 2 個 performance core 和 4 個 efficiency core , perf 在進行效能分析時會將兩種核納入統計。
最左端的數字即為在該核發生的分析項目平均次數,中間為執行過程中發生分析項目的平均比例,由於是多次執行同個程式進行統計,故括號中的 ± 數值代表標準差,而最右邊的則是代表在不同類型的核上發生的佔比。
有別於 perf stat
針對程式碼整體的 event 進行分析, perf record
與 perf report
可針對函式級別進行 event 統計,進行更精細的效能分析與調整, perf record
執行後會於該資料夾下產生 perf.data
儲存分析結果。如要針對特定的 event 進行分析,可使用 -e
選項達成,以 cache miss event 為例,透過下列命令流程可得知程式執行過程,在 main 函式中發生的 cache miss 佔了多少百分比。
從上述執行結果可觀查到, samples 數量與 Event count 數量並不相等。主要的原因為此處的 samples 是依據寫入 perf.data 的資料量,與 event 量測所獲得的最小 sample 資料大小估算獲得。實際 event 發生次數應參考 perf report 中的 Event count
資訊。
perf 使用的取樣機制共有兩種:
-F
命令調整取樣頻率,最大頻率可參照 /proc/sys/kernel/perf_event_max_sample_rate
的設定。請注意,若設定過低有可能導致獲得的 event 數量低於實際數量的情況。將範例程式改寫如下,新增 foo 與 add 兩個函式組成,並使用 perf record 觀察 cach miss 的情形。
從 perf report 輸出結果,可看到程式分別在 core 與 atom 處理器上進行運算,並可從結果上觀察到 add 與 foo 函式運算過程中遇到 cache miss 佔了多少百分比,請注意此處的 overhead 計算方式,並不包含呼叫的子函式。
若想要觀察子函式呼叫情形,可在執行 perf record 時使用 -g
命令,將記錄程式執行期間的呼叫圖 (call-graph) 資訊。透過 perf report 的輸出,我們可以觀察到在 foo 函式中, add 函式被呼叫的情況。值得注意的是,此處的 overhead 資訊被分為兩個部份:self 與 children ,且 children 的總和大於 100% 。這是因為 children overhead 包含了函式本身 (self) 與所有被呼叫的子函式的 overhead 總和。以 foo 函式為例,其自身的 overhead 為 33.06% ,而 add 函式的 overhead 為 33.37% 。將兩者相加即可得到 foo 函式的 children overhead 。這樣的資訊有助於我們識別哪個函式的 overhead 最為突出。
我們再修改了下範例程式碼,觀察當一個函式於多個函式中呼叫時,在呼叫圖中是如何被呈現的。修改後的程式碼在 foo 與 main 函式中,各呼叫一次 add 函式。