contributed by < hankluo6
>
1
程式碼等價於下方 python 程式:
概念上是利用牛頓法找出 n >> s
的 square root,其中 s
為一個偶數,迴圈內會持續減少 s
的值,直到 s
等於 0 時的答案即為 。
而表格提供一個近似 的起始值,藉由表格可以幫助我們在只需幾次迭代便能找到答案。
psieve
中的每個 bit 都代表一個數字,且不包含偶數。故 max
為所有可能出現的數字數量,而 bytes
為總共需要的 byte 數量,因為每個 byte 可表示 8 個數字 (bits),所以 bytes
需要位移。
根據 Sieve of Eratosthenes 演算法將每個合數位置的 bit 設置為 COMPOSITE
。psieve
陣列型態為 uint8_t
,所以每個陣列元素可以存 8 個數字,(mul >> 1) & mask
即為該數字在陣列中的位置。
is_prime
檢查在 val
能否被質數表中的任一數整除。quad
為 psieve
陣列中的某個元素取反,此時內容為 1 的位元對應的數字即為質數,透過 __builtin_ctzll
找出該位元的位置,並透過 (next << 1) + 1
便能得到實際的數字。每檢查完一個位元後,會將該位元設置為 0,便能在檢查所有 sizeof(ull)
位元後,跳出迴圈,並將 base address prev
往後移動,繼續檢查下個元素。
getnextpalin
將長度分成偶數跟奇數討論,每次逐步增加最靠近中間的位置的數字,當數字為 9 時,則增加其兩側數字。而當該長度所有數字都跑過後,需要將 buf
擴充,並增加 len
,原本程式是將 buf
內的最高值 (99…99) + 2,但此時 buf
已經被重置為 00…00,回傳值會變成 2 而不是正確的數字。
故需作以下更改:
轉成字串的好處在於可以快速的取得下一個迴文數值,但可以不需要將數值轉成字串再來計算,觀察數值有 位數個數的數值 ,其中 為奇數,可發現 的前 位數數字與後 位數數字相反。故我們可從前 位數數字推得後面 位數數字,而正中間位數則可為 1 ~ 9 任意數字。
而當 為偶數時,可以不用考慮,因為我們知道所有偶位數的數字除了 11 外沒有其他回文質數。
2
同時被 reader 及 writer 存取的共用資源。
config_dom
為主要管理 hazard pointer 的結構。
reader thread 在讀取共用資源時,會建立一個 hazard pointer 指向此共用資源,而這些 hazard pointer 以 linked list 的方式存在 domain_t
內的 pointers
中。
writer thread 要釋放共用資源的空間時,如果該空間還有 reader 正在讀取,則將此 reader 對應的 hazard pointer 放到 retired
linked list 當中,等待讀取完後再釋放空間。
deallocator
用來將共用資源的空間釋放,此例中為釋放 config_t
的函式。
以 struct hp_t
表示 hazard pointer,為 singly linked list,因為 hazard pointer 可能同時被多個 reader 及 writer 存取,所以存取 list 的函式需使用 atomic operator。
reader thread 會透過 load
讀取 shared_config
,並在讀取完後呼叫 drop
。
load
嘗試在 dom->pointer
這個 list 上找尋沒被使用的 node 當作 hazard pointer,如果在 list 上找不到則分配一個新的 node 當作 hazard pointer。hazard pointer 指向的值即為 reader 要讀取的記憶體位置。而在建立 hazard pointer 的過程中,該共用記憶體位置的值可能被更改,故 load
內的 atomic_cas
為記憶體被更改時,將剛剛建立的 hazard pointer 內的值清空,並重新分配新的 hazard pointer。
drop
會在 reader 讀取完資料後,將 hazard pointer 的值設定成 NULL
,表示該 pointer 可再被其他 reader 使用。
writer thread 建立一個新的 config,並將其透過 swap
與先前的 config 交換。
swap
利用 atomic_exchange
將新舊 config 交換,並呼叫 cleanup_ptr
嘗試釋放舊的 config。
cleanup_ptr
會判斷現在是否還有 reader 的 hazard pointer 正在指向此記憶體,如果沒有則可以直接呼叫 deallocator
釋放該空間。而如果還有 reader 在使用,則根據 flag
的值分成兩種方法:
flag & DEFER_DEALLOC
: 將要釋放的空間放到 retire list 中,等待最後被釋放。flag & DEFER_DEALLOC == 0
: busy wating 等待所有 reader 都讀取完該空間,在釋放。在 macOS Monterey 12.2 執行程式時需加上環境變數 MallocNanoZone=0
。
reference
可以看到問題出在 print_config
,從 ThreadSanitizer 輸出中可看到 thread 13 分配的 new_config
與 thread 12 的 print_config
有 data race。但 print_config
印的是自己執行緒上新分配的 new_config
,與其他執行緒的 new_config
是不會產生 data race 的。
可以推測 thread 12 分配的 new_config
在 thread 12 呼叫第二次 print_config
之前,已經被其他執行緒釋放,而 thread 13 新分配的 new_config
剛好使用到 thread 12 的 new_config
被釋放的空間,產生 data race。
故必須確保在第二次 print_config
之前,new_config
不能被釋放。
一個簡單的方法為建立副本用來讀取,便能防止 data race,但當共用的資料大小很大時,此方法會降低效能。而另一個方法為一樣使用 hazard pointer 保護 new_config
。但不論哪種方法似乎都不太適合,因為 writer thread 本身功能應為寫入資料,而非讀取資料。
後續的實作: hp_list,若你想到改進方案,請提交 pull request
linux2022