---
tags: Linux Kernel
---
# 2022q1 Homework5 (quiz5)
contributed by < `kevinshieh0225` >
> [第 5 週測驗題目](https://hackmd.io/@sysprog/linux2022-quiz5)
> [GitHub](https://github.com/kevinshieh0225/linux2022-hazard-pointer)
## 測驗 `2`：[Hazard Pointer](https://hackmd.io/@sysprog/linux2022-quiz5#測驗-2)
> 以下說明參考測驗 `2` 之說明，並補充前備知識
在並行程式設計中，當我們在存取共用的記憶體物件時，需要考慮到其他執行緒是否有可能也正在存取同一個物件，若要釋放該記憶體物件時，不考慮這個問題，會引發嚴重的後果，例如 [dangling pointer](https://www.wikiwand.com/en/Dangling_pointer)。
> Dangling pointers and wild pointers in computer programming are pointers that do not point to a valid object of the appropriate type. These are special cases of memory safety violations.
使用 mutex 是最簡單且直觀的方法：存取共用記憶體時，acquire lock 即可保證沒有其他執行緒正在存取同一物件，也就可安全地釋放記憶體。但若我們正在存取的是一種 [lock-free](https://hackmd.io/@sysprog/concurrency/https%3A%2F%2Fhackmd.io%2F%40sysprog%2Fconcurrency-lockfree) 資料結構，當然就不能恣意地使用 lock，因為會違反 lock-free 特性，即無論任何執行緒失敗，其他執行緒都能可繼續執行。於是乎，我們需要某種同為 lock-free 的記憶體物件回收機制。
> lock-free: 強調以系統的觀點來看，只要執行足夠長的時間，至少會有一個執行緒會有進展 (progress)
> [Compare-and-swap](https://en.wikipedia.org/wiki/Compare-and-swap)
對於 C 這樣缺乏內建 concurrent GC 機制的程式語言來說，若要實作 lock-free 演算法，就要自行處理記憶體釋放的議題。
> 1. [ABA 問題](https://en.wikipedia.org/wiki/ABA_problem)：執行緒`1` 希望 pop（A -> B -> C）的佇列變成（B -> C），執行了 `compare_and_swap(target=&head, newvalue=B, expected=A)` 。但是如果有另一個執行緒`2` 他已經執行兩次 pop 並且又把 A push 回去、把 B 釋放了（A -> C），那執行緒`1` 會誤以為佇列在我操作中間沒有被操作，而錯誤把空指標 `B` 指派為新的首節點。
>
> 2. Problem without automatic garbage collection：在進行指標指派中途如果有其他執行緒將指標釋放了，那可能導致執行上的非預期結果。
[Hazard pointer](https://en.wikipedia.org/wiki/Hazard_pointer) 是其中一種解決方案，其原理是讀取端執行緒對指標進行識別，指標 (特別是指向的記憶體區塊) 若要釋放時，會事先保存，延遲到確認沒有讀取端執行緒，才進行真正的釋放。
> [Lock-Free Data Structures with Hazard Pointers](https://erdani.org/publications/cuj-2004-12.pdf)
> Each reader thread owns a single-writer/multi-reader shared pointer called "hazard pointer." When a reader thread assigns the address of a map to its hazard pointer, it is basically announcing to other threads (writers), "I am reading this map. You can replace it if you want, but don't change its contents and certainly keep your deleteing hands off it."
在 hazard pointer 架構中，每個 thread 首先需要各自維護的兩個關鍵集合是:
- hazard pointer: 儲存此 thread 正在存取的指標，因此該指標不能直接被釋放
- retire list: 被這個 thread 要求釋放的指標，但實際尚未釋放
要安全的釋放記憶體，其基本想法就是:
- 每個執行緒放在 hazard pointer 中的指標尚不能被釋放
- 每個執行緒要求釋放的指標先放在 retire list 中
- 掃描 retire list 可以得知所有執行緒皆不使用的指標，則可將其真正的釋放給作業系統
:::warning
測驗題的程式碼已有更新，可見 [hp_list](https://github.com/sysprog21/concurrent-programs/tree/master/hp_list)，注意仍可改進，使用 relaxed memory model
:notes: jserv
:::
### [hptr.h](https://github.com/kevinshieh0225/linux2022-hazard-pointer/blob/main/hptr.h)
`hptr.h` 提供一個 lock-free 的 linked list 操作的結構體與介面，此介面同時提供給 `hazard pointer list` 和 `retired list` 使用。
```c
/* hazard ptr struct
*
* @ptr: resouce currently used by thread
* @next: linked-list structure
*/
typedef struct __hp {
uintptr_t ptr;
struct __hp *next;
} hp_t;
/* Allocate a new node with specified value and append to list
*
* @head: hplist head
* @ptr: add tracted resource
* @return: the node containing the newly added value.
*/
static hp_t *list_append(hp_t **head, uintptr_t ptr);
/* Attempt to find an empty node to store value, otherwise append a new node.
*
* @head: hplist head
* @ptr: add tracted resource
* @return: the node containing the newly added value.
*/
hp_t *list_insert_or_append(hp_t **head, uintptr_t ptr);
/* Remove a node from the hplist with the specified value
*
* @head: hplist head
* @ptr: removed target
* @return: if successfully remove return true,
* else if [1. ptr not in list 2. ptr has been remove return] false
*/
bool list_remove(hp_t **head, uintptr_t ptr);
/* Returns 1 if the list currently contains an node with the specified value
*
* @head: hplist head
* @ptr: tracted resource
* @return: if successfully remove return true,
* else if [1. ptr not in list 2. ptr has been remove return] false
*/
bool list_contains(hp_t **head, uintptr_t ptr);
```
特別說明 `list_insert_or_append` 和 `list_remove`：
`list_insert_or_append` 尋訪 list 節點，利用 `atomic_load` 將該節點值載入，如果該節點為 0 ，並且利用 `atomic_cas` 確認並未被其他執行緒競爭以插入新節點，如果尋訪後都沒有成功，再進行 `list_append`。
`list_remove` 尋訪 list 節點確認是否有我們要刪除的目標，如果有目標節點的話，利用`atomic_cas` 確認並未被其他執行緒先刪除，以更換 nullptr。
### [domain.h](https://github.com/kevinshieh0225/linux2022-hazard-pointer/blob/main/domain.h)
透過 `domain.h` 對 `hp list` 和 `retire list` 進行操作。分為以下指令：
```c
/* domain struct
*
* @pointers: hazard pointer list
* @retired: retire list
* @deallocator: function
*/
typedef struct {
hp_t *pointers;
hp_t *retired;
void (*deallocator)(void *);
} domain_t;
/* Create a new domain on the heap */
domain_t *domain_new(void (*deallocator)(void *));
/* Free a previously allocated domain */
void domain_free(domain_t *dom);
/*
* Load a safe pointer to a shared object. This pointer must be passed to
* `drop` once it is no longer needed. Returns 0 (NULL) on error.
*/
uintptr_t load(domain_t *dom, const uintptr_t *prot_ptr)
{
const uintptr_t nullptr = 0;
while (1) {
uintptr_t val = atomic_load(prot_ptr);
hp_t *node = list_insert_or_append(&dom->pointers, val);
/* 當記憶體配置失敗時，list_insert_or_append 回傳 null */
if (!node)
return 0;
/* Hazard pointer inserted successfully */
if (atomic_load(prot_ptr) == val)
return val;
/*
* This pointer is being retired by another thread - remove this hazard
* pointer and try again. We first try to remove the hazard pointer we
* just used. If someone else used it to drop the same pointer, we walk
* the list.
*/
uintptr_t tmp = val;
if (!atomic_cas(&node->ptr, &tmp, &nullptr))
list_remove(&dom->pointers, val);
}
}
/*
* Drop a safe pointer to a shared object. This pointer (`safe_val`) must have
* come from `load`
*/
void drop(domain_t *dom, uintptr_t safe_val);
/* deallocate ptr savely */
static void cleanup_ptr(domain_t *dom, uintptr_t ptr, int flags)
{
/* if hplist doesn't contain ptr, deallocate straight away
* else if flag mode == 1, add to retired list to wait
* else wait until hplist doesn't remain ptr to deallocate
*/
if (!list_contains(&dom->pointers, ptr)) {
dom->deallocator((void *) ptr);
} else if (flags & DEFER_DEALLOC) { /* Defer deallocation for later */
list_insert_or_append(&dom->retired, ptr);
} else { /* Spin until all readers are done, then deallocate */
while (list_contains(&dom->pointers, ptr))
;
dom->deallocator((void *) ptr);
}
}
/* Swaps the contents of a shared pointer with a new pointer. The old value will
* be deallocated by calling the `deallocator` function for the domain, provided
* when `domain_new` was called. If `flags` is 0, this function will wait
* until no more references to the old object are held in order to deallocate
* it. If flags is `DEFER_DEALLOC`, the old object will only be deallocated
* if there are already no references to it; otherwise the cleanup will be done
* the next time `cleanup` is called.
*/
void swap(domain_t *dom, uintptr_t *prot_ptr, uintptr_t new_val, int flags);
/* Forces the cleanup of old objects from retired list that have not been
* deallocated yet. Just like `swap`,
* if `flags` is 0, this function will wait until there are no more
* references to each object.
* If `flags` is `DEFER_DEALLOC`, only objects that already have no living
* references will be deallocated.
*/
void cleanup(domain_t *dom, int flags);
```
幾個比較容易混淆的函式解釋：
- `load` 將資源加入 `hplist`，並透過 `drop` 移出 `hplist`。這個 hplist 並未限定一個資源只能載入一次，所以說幾個 thread 在使用這份資源，`hplist` 中就會有幾個此資源的 `hp`。所以所有 `load` 進 `hplist` 來的資源都應可執行對應個 `drop`。而當 `hplist` 不再記載此資源時，便可以將此資源刪除。
- `cleanup_ptr` 指定特定資源刪除，搭配 `swap` 使用；而 `cleanup` 是要刪除 retired list 上的所有資源。
- `swap` 使用新資源取代舊資源，並利用 `cleanup_ptr` 刪除該資源。
:::info
利用 `swap` 提供 `writer_thread` 更新共享資源的方式，帶來一個好處：
因為我們是先做新舊資源交換，在讓舊資源等待釋放，所以克服了 writer 需要 等待 reader 完成的 starving。
:::
### [read / write thread](https://github.com/kevinshieh0225/linux2022-hazard-pointer/blob/main/rwthread.c)
`config_t` 是本次實驗使用的共享資源，利用 `create_config` 初始化共享資源、`delete_config` 刪除、`print_config` 顯示共享地址資訊。
其中我們看到 `init`：
```c
void init()
{
shared_config = create_config();
config_dom = domain_new(delete_config);
if (!config_dom)
err(EXIT_FAILURE, "domain_new");
}
```
`shared_config` 是共享資源物件，`config_dom` 是 `hplist`，這點出幾個重點：
- 這次實作每個 thread 共用一個 `domain_t config_dom` 也就是說在這個實作中沒有各自的 `retired list`，`hplist` 和 `retired list` 是大家一同管理。
- 這次實作沒有特別使用到 `cleanup`，行程結束後就一起 deallocate 了。
```c
/* Reader thread
*
* thread implement N_ITERS times reading
* If load fail, return error
*
* print config and drop the safe_config out of hplist from config_dom
*/
static void *reader_thread(void *arg)
{
(void) arg;
unsigned long pid = gettid();
for (int i = 0; i < N_ITERS; ++i) {
config_t *safe_config =
(config_t *) load(config_dom, (uintptr_t *) &shared_config);
if (!safe_config)
err(EXIT_FAILURE, "load");
print_config(pid, "read config ", safe_config);
drop(config_dom, (uintptr_t) safe_config);
nanosleep(&req_r, &rem_r);
}
return NULL;
}
/* Writer thread
*
* thread implement N_ITERS times writing
* first creating new config on random uintptr
* and print by "updating config" signature
*
* use swap to write in new value to config_dom and use flag == 0
* and print by "updated config " signature
*/
static void *writer_thread(void *arg)
{
(void) arg;
unsigned long pid = gettid();
for (int i = 0; i < N_ITERS / 2; ++i) {
config_t *new_config = create_config();
new_config->v1 = rand();
new_config->v2 = rand();
new_config->v3 = rand();
print_config(pid, "updating config", new_config);
swap(config_dom, (uintptr_t *) &shared_config, (uintptr_t) new_config,
0);
print_config(pid, "updated config ", new_config);
nanosleep(&req_w, &rem_w);
}
return NULL;
}
```
參考 [`bakudr18`](https://hackmd.io/@bakudr18/r1Lbsu27q#%E6%B8%AC%E9%A9%97-2) 使用了 [nanosleep](https://man7.org/linux/man-pages/man2/nanosleep.2.html) 讓每次 read 成功後暫停 thread 執行時間 150 ns 、 write 成功後暫停 50 ns，讓 reader 與 writer 比較容易能交互執行。
```
185643 read config : { 0x00000000, 0x00000000, 0x00000000 }
185643 read config : { 0x00000000, 0x00000000, 0x00000000 }
185644 updating config : { 0x6b8b4567, 0x327b23c6, 0x643c9869 }
185644 updated config : { 0x6b8b4567, 0x327b23c6, 0x643c9869 }
185643 read config : { 0x6b8b4567, 0x327b23c6, 0x643c9869 }
185644 updating config : { 0x66334873, 0x74b0dc51, 0x19495cff }
185644 updated config : { 0x66334873, 0x74b0dc51, 0x19495cff }
185643 read config : { 0x66334873, 0x74b0dc51, 0x19495cff }
185644 updating config : { 0x2ae8944a, 0x625558ec, 0x238e1f29 }
185643 read config : { 0x66334873, 0x74b0dc51, 0x19495cff }
185644 updated config : { 0x2ae8944a, 0x625558ec, 0x238e1f29 }
185643 read config : { 0x2ae8944a, 0x625558ec, 0x238e1f29 }
185644 updating config : { 0x46e87ccd, 0x3d1b58ba, 0x507ed7ab }
185644 updated config : { 0x46e87ccd, 0x3d1b58ba, 0x507ed7ab }
185643 read config : { 0x46e87ccd, 0x3d1b58ba, 0x507ed7ab }
185643 read config : { 0x46e87ccd, 0x3d1b58ba, 0x507ed7ab }
```
### Multiple Reader / Multiple Writer
先試試 multiple reader = 3 沒問題，但 multiple writer = 3 出現 data race 和 heap-use-after-free 的警告。
```
WARNING: ThreadSanitizer: data race (pid=188669)
Write of size 8 at 0x7b0400001008 by thread T3:
#0 free ../../../../src/libsanitizer/tsan/tsan_interceptors_posix.cpp:707 (libtsan.so.0+0x35f25)
#1 delete_config <null> (rwt.o+0x1dbc)
#2 cleanup_ptr <null> (rwt.o+0x1b03)
#3 swap <null> (rwt.o+0x1bc2)
#4 writer_thread <null> (rwt.o+0x2148)
Previous read of size 4 at 0x7b0400001008 by thread T2:
#0 print_config <null> (rwt.o+0x1dfb)
#1 writer_thread <null> (rwt.o+0x215f)
Thread T3 (tid=188673, running) created by main thread at:
#0 pthread_create ../../../../src/libsanitizer/tsan/tsan_interceptors_posix.cpp:962 (libtsan.so.0+0x5ea79)
#1 main <null> (rwt.o+0x2253)
Thread T2 (tid=188672, finished) created by main thread at:
#0 pthread_create ../../../../src/libsanitizer/tsan/tsan_interceptors_posix.cpp:962 (libtsan.so.0+0x5ea79)
#1 main <null> (rwt.o+0x2253)
SUMMARY: ThreadSanitizer: data race (/home/masamaloka/linux2022/linux2022-hazard-pointer/rwt.o+0x1dbc) in delete_config
==================
==================
WARNING: ThreadSanitizer: heap-use-after-free (pid=188669)
Read of size 4 at 0x7b0400001804 by thread T3:
#0 print_config <null> (rwt.o+0x1e13)
#1 writer_thread <null> (rwt.o+0x215f)
Previous write of size 8 at 0x7b0400001800 by thread T2:
#0 free ../../../../src/libsanitizer/tsan/tsan_interceptors_posix.cpp:707 (libtsan.so.0+0x35f25)
#1 delete_config <null> (rwt.o+0x1dbc)
#2 cleanup_ptr <null> (rwt.o+0x1b03)
#3 swap <null> (rwt.o+0x1bc2)
#4 writer_thread <null> (rwt.o+0x2148)
Thread T3 (tid=188673, running) created by main thread at:
#0 pthread_create ../../../../src/libsanitizer/tsan/tsan_interceptors_posix.cpp:962 (libtsan.so.0+0x5ea79)
#1 main <null> (rwt.o+0x2253)
Thread T2 (tid=188672, finished) created by main thread at:
#0 pthread_create ../../../../src/libsanitizer/tsan/tsan_interceptors_posix.cpp:962 (libtsan.so.0+0x5ea79)
#1 main <null> (rwt.o+0x2253)
SUMMARY: ThreadSanitizer: heap-use-after-free (/home/masamaloka/linux2022/linux2022-hazard-pointer/rwt.o+0x1e13) in print_config
==================
```
我嘗試將 thread PID 和使用的記憶體位置 `printf` 出來是符合輸出預期的，依據觀察 data race 的執行區域發生在兩個以上的 `writer_thread` 第一次輸出與第二次輸出錯開的時候：
```
31697 updating config : { 0x7545e146, 0x515f007c, 0x5bd062c2 }
31698 updating config : { 0x12200854, 0x4db127f8, 0x0216231b }
31697 updated config : { 0x7545e146, 0x515f007c, 0x5bd062c2 }
31698 updated config : { 0x12200854, 0x4db127f8, 0x0216231b }
```
當我把 `writer_thread` 第二次輸出註解時，data race 便被解除。
依據網路上相關的[線索](https://stackoverflow.com/questions/23587318/printf-preventing-race-conditions)說明，`printf` 的成本代價很高（須使用 system call，並且用 mutex lock 來確保單一執行緒執行），故使用 `printf` 在多執行緒下將改變執行環境，更好的方式是將要輸出的結果先存在一個資料空間，最後再一同把執行結果輸出。這正是老師的 [Concurrent Linked List With Hazard Pointer](https://github.com/sysprog21/concurrent-programs/tree/master/hp_list) 教材中使用的方法。
### 改進方向
在閱讀 [Lock-Free Data Structures with Hazard Pointers](https://erdani.org/publications/cuj-2004-12.pdf) 後有幾個認為此實作能改進之處：
本次實作的 hplist 和 retired 是所有執行緒共用的，這和原本 HPlist 的設計有些不同，原本的 HPlist 只會提供一個執行緒一個 `hplist* head`，每個 thread 各自管理自己的 `retired list`。這使的程式設計的情境不同。因為在本次實作中的 write thread 是直接將資源換新，隨即把舊資源刪除，不會發生兩個 thread 同時要釋放同一份資源的情形；但今天如果 retired list 各自維護，那就有可能兩個行程序希望同時釋放同一筆資源的衝突。
> Nothing up our sleeves! Now, the `Scan` function will perform a set difference between the point the current thread’s retired list, and all hazard pointers for all threads. What does that set difference mean? Let’s think of it for a second: it’s the set of all old pMap_ pointers that this thread considers useless, except those that are found among the hazard pointers of all threads. But, hey, these are exactly the goners! By definition of the retired list and that of the hazard pointers, if a pointer is retired and not marked as “hazardous” (i.e. “in use”) by any thread, the set intersection of the two sets yields precisely the pointers that can be `deleted`
另外論文提及能夠使用 hashmap 的方式設計 hazard pointer list，讓 `delete` 在搜尋節點為常數時間，而讓完整的 retired list 內容刪除理想上只需要 $O(R)$ 的時間複雜度。
在 [quiz6](https://hackmd.io/@sysprog/linux2022-quiz6#%E6%B8%AC%E9%A9%97-2) 的第二題老師實作了一份 [lock-free hashmap](https://gist.github.com/jserv/c3823ea893e08607b432827a11ec4b69)，可以納入 hazard pointer 的實作中。
## [Concurrent Linked List With Hazard Pointer](https://github.com/sysprog21/concurrent-programs/tree/master/hp_list)
討論本實作中的一些手段與技巧，另外探討 memory ordering：在本次實作中的 atomic instruction 的 ordering 限制都是用高度最強的 `__ATOMIC_SEQ_CST` ，然而並不是所有情況都有需要用這麼強的限制。
> [6.55 Built-in Functions for Memory Model Aware Atomic Operations](https://gcc.gnu.org/onlinedocs/gcc/_005f_005fatomic-Builtins.html)
> [std::memory_order](https://en.cppreference.com/w/cpp/atomic/memory_order)
```
__ATOMIC_RELAXED
Implies no inter-thread ordering constraints.
__ATOMIC_CONSUME
This is currently implemented using the stronger __ATOMIC_ACQUIRE
memory order because of a deficiency in C++11’s semantics for
memory_order_consume.
__ATOMIC_ACQUIRE
Creates an inter-thread happens-before constraint from the release
(or stronger) semantic store to this acquire load. Can prevent
hoisting of code to before the operation.
__ATOMIC_RELEASE
Creates an inter-thread happens-before constraint to acquire
(or stronger) semantic loads that read from this release store.
Can prevent sinking of code to after the operation.
__ATOMIC_ACQ_REL
Combines the effects of both __ATOMIC_ACQUIRE and __ATOMIC_RELEASE.
__ATOMIC_SEQ_CST
Enforces total ordering with all other __ATOMIC_SEQ_CST operations.
```
### Code Structure
管理的資源為 `list_node_t`，`list_t` 是 `list_node_t` 的資源串列，並也包含著 `list_hp_t`，所有的 thread 都從 `list_t` 讀寫資源。
`list_hp_t` 是本實作的 hp_list 和 retire_list 結構體。其中 hp_list 增加了 tid() 的執行緒索引，執行緒可以根據被分配到的索引去管理並寫入 hp_list index。
### Trace statistic
為了避免 printf 造成的執行成本，此實作將操作次數存入 `struct runtime_statistics` 中，最後再把紀錄結果一次輸出。
使用 `atomic_fetch_add` 讓執行緒們共同紀錄一份共享結構體。
```c
/* example of recording
* use # to Stringification, ## to concatenation
*
* https://hackmd.io/@sysprog/c-prog/c-preprocessor#開發物件導向程式時，善用前置處理器可大幅簡化開發
*/
#define TRACE(ops) \
do { \
if (TRACE_##ops) \
atomic_fetch_add(&stats.ops, 1); \
} while (0)
```
:::warning
`atomic_fetch_add` 的巨集展開如下：
`#define atomic_fetch_add(x, a) __atomic_fetch_add(x, a, __ATOMIC_SEQ_CST)`
在這個案例中應不需要用到 `__ATOMIC_SEQ_CST` 的強度。只要確保 atomic 了，執行的先後順序並不影響輸出結果，用 `__ATOMIC_RELAXED` 就好
:::
### allignment to avoid false sharing
這次實作的 `hp_list` 透過 `alignas(128)` 強制使的 `hp`, `rt` 需要對齊 128 排列，這些串列頻繁在執行緒間讀寫，為了避免 cacheline 重疊的抓取了兩筆獨立的資料，而發生 [false sharing](https://mechanical-sympathy.blogspot.com/2011/07/false-sharing.html) 的情形：
```c
struct list_hp {
int max_hps;
alignas(128) atomic_uintptr_t *hp[HP_MAX_THREADS];
alignas(128) retirelist_t *rl[HP_MAX_THREADS * CLPAD];
list_hp_deletefunc_t *deletefunc;
};
```
為了對齊，結構體的操作也需要改變，以 `list_hp_new` 為例：
```c
/* Create a new hazard pointer array of size 'max_hps' (or a reasonable
* default value if 'max_hps' is 0). The function 'deletefunc' will be
* used to delete objects protected by hazard pointers when it becomes
* safe to retire them.
*/
list_hp_t *list_hp_new(size_t max_hps, list_hp_deletefunc_t *deletefunc)
{
list_hp_t *hp = aligned_alloc(128, sizeof(*hp));
assert(hp);
if (max_hps == 0)
max_hps = HP_MAX_HPS;
*hp = (list_hp_t){.max_hps = max_hps, .deletefunc = deletefunc};
for (int i = 0; i < HP_MAX_THREADS; i++) {
hp->hp[i] = calloc(CLPAD * 2, sizeof(hp->hp[i][0]));
hp->rl[i * CLPAD] = calloc(1, sizeof(*hp->rl[0]));
for (int j = 0; j < hp->max_hps; j++)
atomic_init(&hp->hp[i][j], 0);
hp->rl[i * CLPAD]->list = calloc(HP_MAX_RETIRED, sizeof(uintptr_t));
}
return hp;
}
```
實作中使用 `aligned_alloc(128, sizeof(*hp))` 取代原本的 `alloc`。
:::warning
還在研究 CLPAD 是什麼。
:::
### `list_hp_retire`
```c
/* Retire an object that is no longer in use by any thread, calling
* the delete function that was specified in list_hp_new().
*
* Progress condition: wait-free bounded (by the number of threads squared)
*/
void list_hp_retire(list_hp_t *hp, uintptr_t ptr)
{
retirelist_t *rl = hp->rl[tid() * CLPAD];
rl->list[rl->size++] = ptr;
assert(rl->size < HP_MAX_RETIRED);
if (rl->size < HP_THRESHOLD_R)
return;
for (size_t iret = 0; iret < rl->size; iret++) {
uintptr_t obj = rl->list[iret];
bool can_delete = true;
for (int itid = 0; itid < HP_MAX_THREADS && can_delete; itid++) {
for (int ihp = hp->max_hps - 1; ihp >= 0; ihp--) {
if (atomic_load(&hp->hp[itid][ihp]) == obj) {
can_delete = false;
break;
}
}
}
if (can_delete) {
size_t bytes = (rl->size - iret) * sizeof(rl->list[0]);
memmove(&rl->list[iret], &rl->list[iret + 1], bytes);
rl->size--;
hp->deletefunc((void *) obj);
}
}
}
```
- 先把欲刪除節點放在 retirelist ，如果超過最大容納空間時，一次性進行標記與刪除。
- 逐一對 retirelist 物件檢查，如果物件還紀錄在 hplist 裡就不刪除。
- 要刪除時把 rl 後面的物件向前補上空缺，並釋放該物件。
:::warning
如果為了補刪除的缺向前補齊，`iret` 索引值是不是也要相應減一？否則原本 `rl->listp[iret+1]` 的物件不會被檢查到。
:::
pull request 紀錄小抄
> [git rebase](https://git-scm.com/docs/git-rebase)
> [Git 刪除已 Push 至遠端分支的 Commit 教學與範例](https://officeguide.cc/git-delete-commit-in-remote-branch-tutorial-examples/)
> [How to Write a Git Commit Message](https://cbea.ms/git-commit/)
### `list_insert`, `list_delete`, `__list_find`
關於 `get_marked` 的巨集的功能應該如同論文中提到的：在刪除前必須對刪除資料做標記，否則如果兩筆資料同時要刪除，會產生衝突。
> Nothing up our sleeves! Now, the `Scan` function will perform a set difference between the point the current thread’s retired list, and all hazard pointers for all threads. What does that set difference mean? Let’s think of it for a second: it’s the set of all old pMap_ pointers that this thread considers useless, except those that are found among the hazard pointers of all threads. But, hey, these are exactly the goners! By definition of the retired list and that of the hazard pointers, if a pointer is retired and not marked as “hazardous” (i.e. “in use”) by any thread, the set intersection of the two sets yields precisely the pointers that can be `deleted`
Sign in with Wallet
Connect another wallet