replace_right
/replace_left
hint
start w/1
, not 0
struct st_node **pparent
to deal w/judgement of left/right child第一部份 (1.) align_up()
的定義。第二部份 (2, 3.) 通用式 (即第 9
行) 的原理。第三部分 (4, 5.) 為特殊情況 ( alignment
為二的冪) 下,針對運算進行最佳化。
align_up()
針對 sz
除以 alignment
所得到的餘數非零時,會有「無條件進位」到 alignment
倍數的動作;而當餘數為零時,則保持 sz
不變,以數學表示如下:
a
的情況下, 與 align_up(s,a)
的圖形皆為離散的階梯函數樣子,此時將 左移即可與 align_up(s,a)
疊合。
align_up()
疊合,則必須左移 (即變數 mask
) ,此時 align_up()
,得到通用式 (第 9
行)。7
行 (s + m) & ~m
,原意就是將 中對於除數 之餘數 去除,前提為 是二的冪。
m
的位元在記憶體上的樣子,剛好是整個黃色區域填滿 1
,此時用 ~
運算,將 m
的位元反轉,搭配 &
運算,可以將白色區域內的位元保留,黃色區域內的位元歸零,此動作就是我們要的 。TSan
(ThreadSanitizer
) 編譯,在之後程式執行時可檢查 data race 的發生。TSan
警告有 data race 發生。從訊息中可以得到 data race 發生的記憶體位置為 0x7b4000000000
,在 qsort_mt.c:132
配置的 c.pool
之中。
c.pool
為 struct qsort
組成之陣列,其中的成員 st
應該要被 mtx_st
所保護。
但在 qsort_mt.c:211
的位置進行 st
的寫入動作前,並未持有 mtx_st
,與 qsort_mt.c:343
位置的讀取動作有 data race 發生的可能。
修正很簡單,就是在 st
執行寫入動作前,先爭取到 mtx_st
即可。