contributed by < 2020leon >
archive: 2022-04-16 07:34:12 UTC+0
1
完整程式碼如下。
XXXXX
處如下:
1
程式碼運作原理2
所回答之完整程式碼如下。
陳述式 | 答案 |
---|---|
DDD |
idx++ |
KKK |
mask + 1 |
TTT |
&lfr->ring[tail & mask].idx |
HHH |
head + actual |
2
程式碼運作原理本題以環狀結構實現容量有限的佇列( queue ),用以解決生產者消費者問題。環狀結構可以簡單以下圖表示。
source: https://doc.dpdk.org/guides/prog_guide/ring_lib.html
上圖為一切斷的環,以 FIFO 的方式儲存資料。每當有新資料加入時,便會在上圖右側之處加入。若到達邊緣則再從左方持續加入,直到滿為止。而當有資料要從結構中移除時,則從上圖左側移除。
在本題中所對應的結構如下。
其中 head
和 tail
分別對應到上方左邊以及右邊的箭頭, mask
隱含環狀結構大小之意, flags
則指出生產者消費者模式(分別為 SPSC 、 SPMC 、 MPSC 及 MPMC),最後 ring
則是環狀結構本體。
下方分別理解 lfring_alloc
, lfring_dequeue
和 lfring_enqueue
。
lfring_alloc
lfring_alloc
可視為結構的建構子。由實做可見 mask
的值為 ringsz - 1
,而 ringsz
又為 2 的冪,因此可驗證上述所言「 mask
隱含環狀結構大小之意」。在此將 ringsz
設為 2 的冪的考量為,索引值可藉由與 mask
進行位元且運算來取代與 ringsz
做取餘運算,精進程式效能。
以 bitwise-AND 取代 modulo 運算不只是「精進」效能,更是確保關鍵操作的執行時間,modulo 和 div 在現代處理器雖然有很大的改進,但沒辦法保證一定在固定的 CPU cycle 內完成
jservImage Not Showing Possible ReasonsLearn More →
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
lfring_dequeue
lfring_dequeue
首先檢查仍可利用的空間。若沒有任何可用空間,在單生產者模式下便會直接返回;若在多生產者模式下,由於 tail
的值會被多個生產者更改,在前方所快取的 tail
變數不一定為最新的 tail
,因此會利用 find_tail()
再次取得最新的 tail
,若仍無空間便返回。在此之後, actual
的值便會確定。 actual
為一紀錄實際可取元素數的變數。
接下來便來到內部的 for
迴圈,一一將位於環中 head 位置的元素取出並存於 elems
中。
最後,在單消費者模式下,由於只會有現在的緒更動環的 head
,因此可在更動環的 head
後直接進行收尾。在多消費者模式下,因為會有多個消費者更動環的 head
,因此需在主邏輯結束後檢查所快取的 head
是否同環的 head
,若是則收尾,否則更新快取的 head
後,再次從檢查仍可利用的空間開始。
lfring_enqueue
lfring_enqueue
針對單生產者和多生產者有著不同的策略。若為單生產者,則確認是否有空間插入資料,若無則返回,若有則依據目前最大容量依序將欲插入之資料放入環中,更新環的 tail
後返回。
若為多生產者模式,亦先確認是否有空間插入資料,若無空間則返回。若有空間,由於多個生產者會更動環的 tail
,因此需檢查快取的 tail
所對應的 slot 是否為空。若所對應的 slot 不為空的話,則依據不為空的原因來更新快取的 tail
:如是因為其他的生產者插入少許新資料導致,則更新快取的 tail
以查看下一個 slot 的狀態;如是因為其他的生產者插入多個新資料導致,則更新快取的 tail
以查看最新的 tail
所對應之 slot 的狀態。在此,「多個」係指其他生產者所插入的資料數大於等於環的空間。
在確保現在快取的 tail
對應之 slot 為空後,最後再經由 lf_compare_exchange()
確保沒有任何其他生產者對於該 slot 插入資料才實際更新將資料插入環中。
3
當 module 被載入 kernel 後,便會執行 dont_trace_init
函式。其功能為將已經初始化的 dont_trace_task
加入全域的 workqueue 中,並在 JIFFIES_DELAY
後執行所指定的函式,在此即 periodic_routine
。
periodic_routine
的功能為利用 check()
刪除所有 tracer 和 tracee ,並再次將 dont_trace_task
加入全域的 workqueue 中,待 JIFFIES_DELAY
後再執行自己。
check
和其所呼叫的函式即為本模組的關鍵所在。其中 is_tracer
函式用於檢查 process 是否有追蹤其他的 process 。其技巧為檢查 task->ptraced
中是否有元素被繼承為 struct task_struct
。在確定該 process 為 tracer 後,則藉 kill_tracee(&task->ptraced)
和 kill_task(task)
立即中止其所有 tracee 和該 process 。
kill_task
發送中止訊號 SIGKILL
至所指定的 task
中。其呼叫的函式 send_sig
之第三個引數是指「不要忽略由 kernel 所發出之訊號」。
在該文章中所提及的其中一個方法為設置 ptrace_scope ,將 ptrace_scope 設為最高級別的 3 可避免任何人的追蹤。