Linux 核心專題: RCU 實作

執行人: eleanorLYJ
專題解說錄影

Reviewed by dcciou

是否有考慮過如何在維持CTP的優點下改善其成本的問題

Reviewed by yuyuan0625

1. 下文記憶體使用量段落的圖片無法讀取，可能要再重新貼上
2. 想請問為何在更多的 reader 的情境，slot-list 就沒有明顯有快取優勢呢?

Reviewed by Ackerman666

感覺這句話有點不嚴謹，應該是始於 writer 修改資料後呼叫 synchronize_rcu()

RCU 寬限期（RCU Grace Period，以下縮寫GP）：這是一個時間窗口，開始於 writer 開始修改 RCU 保護資料

Reviewed by Shiang1212

操作：提供 O(1) 無鎖讀取，並由序列化 writer 在 O(N log(M)) 時間內垃圾收集未引用的值。

請問這裡的 N、M 是指什麼？請附上說明。

任務簡介

Userspace RCU 已成功將 Linux 核心的 RCU 的機制帶到若干應用場域，不過其程式碼規模龐大、整合較困難，且授權條款較嚴格 (LGPL 2.1)，於是本任務嘗試評估 ctp: C Thread Primitives，探討是否可作為 userspace RCU 的替代選擇。

TODO: 理解 RCU

閱讀 Linux 核心設計: RCU 同步機制, Is Parallel Programming Hard, And, If So, What Can You Do About It? 的第九章 Deferred Processing，紀錄自己的認知和相關問題

RCU（Read-Copy-Update）是一種高效的同步機制，主要用於多執行緒環境中讀多寫少，並且 reader 端要求高效但對新舊資料不敏感的場景。RCU 允許多個 reader 並行讀取共享資料，而不需要阻塞寫操作，從而效能提升。

RCU 兩個主要元件

1. RCU 讀側臨界區（RCU Read-Side Critical Section，以下縮寫 cs）：這是一段由 rcu_read_lock() 和 rcu_read_unlock() 包圍的程式碼區域，處於這段區域內的 reader 可以安全地讀取 RCU 保護的共享資料。

2. RCU 寬限期（RCU Grace Period，以下縮寫GP）：這是一個時間窗口，開始於 writer 開始修改 RCU 保護資料，至在GP開始前所有的 reader 結束的時間區間。RCU 保證所有在 GP 開始之前進入 cs 的 reader 都已經完成。synchronize_rcu() 用於等待一個寬限期的結束。

藉此確保每個 reader 對於不同物件保有前後一致的讀取。 (coherent view of each object)

補充 RCU 核心 API

RCU 基礎

為了實作 RCU 的特性，RCU 有了三個重要基礎:

1. publish-subscribe 機制
2. 等待已經存在的 RCU readers
3. 維護最近更新物件的多個版本

publish-subscribe 機制

reader 的讀取視為對目前版本的 RCU 保護資料的訂閱，而 updater 的操作則視為發布新版本。

RCU 的 publish-subscribe 機制是藉由兩個 primitive 達成的:

Publish

Updater 用 rcu_assign_pointer() 這 primitive 做到確保在實際 publish 前這 pointer 的 store 操作的順序正確，這意味著用 memory barrier 防止 pointer 更新之後再執行寫入的操作。

在 Linux kernel, rcu_assign_pointer() 是按照 smp_store_release() 定義的。

updater 程式碼範例:

new_value->a = 1;  
new_value->b = 2;  
new_value->c = 3;  
rcu_assign_pointer(global_ptr, new_value); // 保證將 new_value assign 給 pointer 發生於 line 1-3 之後

注意用語：

• access 是「存取」，而非「訪問」

務必詳閱 https://hackmd.io/@sysprog/it-vocabulary

Subscribe
Reader 用 rcu_dereference() 這 primitive 做到確保實際資料被訪問 前 load 操作順序正確，而這代表有使用 memory barrier，確保資料的一致性。

reader 程式碼範例:

struct data *ptr = rcu_dereference(global_ptr); 
int value = ptr->value;

• rcu_dereference(global_ptr) 這行程式碼確保 global_ptr 被安全地讀取，並且其指向的資料在此之後的讀取操作是有序的，沒有被重新排序。
• ptr->value: 實際讀取到 global_ptr 所指向的資料

等待已經存在的 RCU readers

這一部分是更深入的討論寬限期(GP)的規則

對於 RCU reader
(1) 如果給定 RCU 讀側臨界區間 (cs) 的任何部分先於 GP 的開始，則該 cs 的整體會先於該 GP 的結束。

(2) 如果給定 RCU cs 的任何部分在 GP 結束之後，則該 cs 的整個部分在該 GP 開始之後。

RCU 禁止讀端臨界區與寬限期完全重疊

以下圖片為例說明 cs 與 GP 的執行順序的關係，並且說明為什麼最終 r1 的值為1，而 r2 的值是0。

P0() 是 reader，P1() 是 updater。

P0() 進入 RCU 的 cs (rcu_read_lock()) 並且在這個區域內讀取變數 x 和 y。

P1() 修改變數 x 並設置為 1，然後呼叫 synchronize_rcu() 開始 RCU GP。在 GP 結束後，P1() 修改變數 y 並設置為 1。

因為P1() 在 GP 開始之前將 x 設置為 1，所以 r1 讀取到 1。P1() 在 GP 結束後將 y 設置為 1，所以 r2 讀取到寬限期開始之前的值，即 0。

注意用語: call 是「呼叫」，而非「調用」。
參見 資訊科技詞彙翻譯 和 詞彙對照表

摘要: RCU 寬限期 的順序保證 (Summary of RCU Grace-Period Ordering Guarantees)

以下討論四個可能情況，圖示中的左方塊都是 RCU reader，右方塊是 RCU updater。

第一種情況:
reader 在 updater 開始刪除之前執行，因此該 reader 可能擁有對已刪除資料元素的參考。因此，updater 在 reader 完成之前不得釋放該元素。

第二種情況:
reader 直到刪除完成後才開始執行。reader 不可能獲得對已刪除的資料元素的引用，因此可以在 reader 完成之前釋放該元素。

第三種情況與第二種情況類似，但說明即使 reader 不可能獲得對元素的引用，仍然允許推遲該元素的釋放，直到 reader 完成之後。

在第四個也是最後一個場景中，reader 在 updater 開始刪除資料元素之前進入 cs，但該元素在 reader 完成之前被（錯誤地）釋放，然而，正確的 RCU 實作不會允許第四種情況發生!

維護最近更新物件的多個版本

由於 無同步(synchronization-free)的 reader 提供的時間同步非常弱，RCU 透過空間同步進行補償。

多個弱一致性的板本會帶來一些意外，以下為例:
reader 存取同時也在更新的鏈結串列

1. 在圖中的第一行中，reader 引用 A
2. 在第二行中，它前進到 B，到目前為止已經看到了 A，然後是 B
3. 在第三行中，updater 刪除元素 A
4. 在第四行中，updater 將元素 E 新增至串列末端
5. 在最後一行中，reader 完成了存取，看到了元素 A 到 E
   

不同時間存取的 reader 會得到不同結果，例如再一次存取鏈結會得到 B 到 D 的結果，但在這特殊情況取得 A 到 E 的結果也是合法的。倘若 RCU 的不一致性會造成問題，可以用更強的同步機制或是使用 timestamps 與 versioning 等方式處理，但這些處理會造成成本增加。

TODO: 探討 CTP 實作 RCU 哪些關鍵特徵

CTP 專案建構在 thread-safe variable （TSV），確保 reader 執行緒在無 lock 的情況下運行，且不會被 writer 阻塞。另一方面，writer 會等待最後引用的 reader 執行緒完成讀取後才會寫入。

什麼是 thread-safe variable(tsv)?

CTP 專案中提及的 tsv 本身並不是一個廣泛被認可的理論概念，但它像是結合了 thread safety和 thread specific data 的概念，確保多個執行緒安全並行存取變數的具體實作。

在 CTP 中，提供一種機制能確保資料在多執行緒中保持一致性並且防止 race condition 等問題，其中在某實作中(如 slot-list)，每個 reader 執行緒可以有自己的 slot 能夠儲存目前的副本，這類似於特定執行緒的資料，但透過安全機制更新和管理這些值。

根據 Using Thread Safe Variables to Protect Data，得知關於 tsv 好處：

• 避免常見的多執行緒錯誤，如在存取變數之前忘記取得鎖的常見錯誤。
• 易於資料傳遞，只需傳遞 thread-safe variable handle，即可在函數之間傳遞受保護的資料，而無需同時傳遞 thread-lock handle 和受保護的變數。

data 是「資料」

CTP 使用兩種主要實作來實作執行緒安全變數: slot-pair 與 slot-list

ctp 目前有六個函式能被使用

int thread_safe_var_init(thread_safe_var *vpp, thread_safe_var_dtor_f dtor): 初始化 tsv 變數的所有成員
thread_safe_var_destroy
int thread_safe_var_get(thread_safe_var vp, void **res, uint64_t *version): reader 取得變數的目前值與其版本，此外管理引用計數 (reference counting) 和 slot 選擇。
void thread_safe_var_release(thread_safe_var vp): 清掉執行緒上的特定資料
int thread_safe_var_set(thread_safe_var vp, void *data, uint64_t *new_version): data 是要寫入結構為 value * 的值(new_value)，vp 是 Pointer to thread-safe global variable 與 new_version 則會填入 new_value 的版本號。返回 0 代表成功。管理記憶體並確保只有在 readers 完成讀取後才更新。
int thread_safe_var_wait(thread_safe_var vp) : 當還沒有任何資料被寫入時，reader 需要等待，直到資料被寫入。

TODO: Slot-Pair 與 Slot-List 的差異

Slot-Pair

結構：每個 tsv 都有兩個 slot，一個用於目前資料，另一個用於上一個或下一個資料
操作：具有 O(1) 無鎖和 spin-less 讀取以及 O(1) 序列化(serialized)寫入。

reader 行為：
reader 呼叫 free() 和值析構函數(value destructor)，並且可能需要向潛在等待的 writer 發出訊號，這涉及獲取互斥鎖。儘管這在技術上是阻塞的，但它通常是在無競爭的資源上。

writer 行為：
writer 將"上一個" slot 切換到"目前" slot。讀者從目前指定的 slot 讀取。
writer 會等待，直到前一個 slot 沒有活躍的 reader 為止。該值是引用計數的，因此當最後一個引用被刪除時會自動釋放。

Slot-List

操作：提供 O(1) 無鎖讀取，並由序列化 writer 在 O(N log(M)) 時間內垃圾收集未引用的值。

結構：維護引用值的鏈結串列，串列的頭部始終是目前值。它還維護一個 subscription slots ，每個 reader 執行緒都有一個 slot。第一次讀取時，reader 分配一個 slot 並將值串列的頭部複製到其 slot 中。

reader 行為：
subscription slots 分配是無鎖的。reader 中的所有內容都是無鎖的

writer 行為：
writer 對引用值的鏈結串列執行垃圾回收(Garbage Collection, GC)。值在最後一個引用被刪除後的第一次寫入時被釋放，因為它們被 writer 回收。

API 的實作

在 threead_safe_global.h 中表示， thread_safe_var 將替代 thread_safe_var_s *

typedef struct thread_safe_var_s *thread_safe_var;

thread_safe_var_wait(thread_safe_var vp)

這是 slot-pair 與 slot-list 共有的函式，其目的是等著 writer 第一次將值寫入。

倘若已經 能從 vp 取得到值，那就不用等了，直接 return 0。
其餘狀況，先鎖定 waiter_lock，之後使用 pthread_cond_wait() 阻塞，直到能讀到 writer 第一次寫入值，之後用 pthread_cond_signal() 喚醒等待在指定條件變數上的一個執行緒，之後同樣再用 pthread_cond_signal() 逐一喚起其他的 waiter。

    if (thread_safe_var_get(vp, &junk, NULL) == 0 && junk != NULL)
        return 0;

    pthread_mutex_lock(&vp->waiter_lock);
    while (thread_safe_var_get(vp, &junk, NULL) == 0 && junk == NULL) {
        if (pthread_cond_wait(&vp->waiter_cv, &vp->waiter_lock) != 0) {
            pthread_mutex_unlock(&vp->waiter_lock);
            return err;
        }
    }

最後，跟 futex 一樣，為了防止 thundering herd problem (驚群問題)，呼叫 pthread_cond_signal(&vp->waiter_cv) ，而不是用廣播的方式，確保所有等待的 reader 執行緒是逐一喚醒。

    pthread_cond_signal(&vp->waiter_cv);
    pthread_mutex_unlock(&vp->waiter_lock);

slot-pair

tsv 中有兩個 slot，一個 slot 存 "current" value，另一個 存 "previous"/"next" value 。
writer 將 "previous" slot 放入下一個 "current" slot，而 reader 從看起來是 "current" slot 中讀取。

資料結構

核心的資料在 vwrapper 中，var 為 vwrapper 的 wrapper, 而在 thread_safe_var_s 中存有 一對 slot 另外還有多個條件變數與鎖。

/* This is an element on the list of referenced values */
struct value {
    volatile struct value   *next;      /* previous (still ref'd) value */
    void                    *value;     /* actual value */
    volatile uint64_t       version;    /* version number */
    volatile uint32_t       referenced; /* for mark and sweep */
};

/*
 * Each thread that has read this thread-safe global variable gets one
 * of these.
 */
struct slot {
    volatile struct value       *value; /* reference to last value read */
    volatile uint32_t           in_use; /* atomic */
    thread_safe_var             vp;     /* for cleanup from thread key dtor */
    /* We could add a pthread_t here */
};

/*
 * Slots are allocated in arrays that are linked into one larger logical
 * array.
 */
struct slots {
    volatile struct slots   *next;      /* atomic */
    struct slot             *slot_array;/* atomic */
    volatile uint32_t       slot_count; /* atomic */
    uint32_t                slot_base;  /* logical index of slot_array[0] */
};

struct thread_safe_var_s {
    pthread_key_t           tkey;           /* to detect thread exits */
    pthread_mutex_t         write_lock;     /* one writer at a time */
    pthread_mutex_t         waiter_lock;    /* to signal waiters */
    pthread_cond_t          waiter_cv;      /* to signal waiters */
    var_dtor_t              dtor;           /* value destructor */
    volatile struct value   *values;        /* atomic ref'd value list head */
    volatile struct slots   *slots;         /* atomic reader subscription slots */
    volatile uint32_t       next_slot_idx;  /* atomic index of next new slot */
    volatile uint32_t       slots_in_use;   /* atomic count of live readers */
    uint32_t                nvalues;        /* writer-only; for housekeeping */
};

thread_safe_var_get

此函數目的: reader 會取 tsv (vp)的版本號得知目前 slot 是哪個，接著讀取這 slot 的值 (wrapper)，並且將引用計數加一，接著 reader 將會保留此 wrapper 當作執行緒的特定資料。

以下一步步講解函式組成:
get 的快速路徑為，如果這個執行緒擁有的 wrapper (pthread_getspecific(vp->tkey)) 與 tsv 的 next_version - 1 一致，就將 wrapper 的版本與實際值（ptr）存回參數中，並結束函式。

    if ((wrapper = pthread_getspecific(vp->tkey)) != NULL &&
        wrapper->version == atomic_read_64(&vp->next_version) - 1) {
        /* Fast path */
        *version = wrapper->version;
        *res = wrapper->ptr;
        return 0;
    }

在確定 slot 為目前最新的 slot 的迴圈中，會與 writers 競爭。先讀取 version 之後讀取 slot (v)，之後判斷如果 atomic_read_64(&vp->next_version) == (*version + 1) 代表中途是否有其他執行緒在競爭，如果等於，這就確定 slot。反之不等於並且如果 slot 的 活躍 reader (nreader) 是 0，就 signal_writer()通知 writer 寫入，其方式是使用 vp->cv 條件變數告知 writer ，而 reader 則繼續在此迴圈，直到確定好 slot。

static int signal_writer(thread_safe_var vp)
{
    pthread_mutex_lock(&vp->cv_lock);
    err = pthread_cond_signal(&vp->cv);
    return pthread_mutex_unlock(&vp->cv_lock);
}

選擇好 slot 後，就可以將 slot 中的 vwrapper 引用加一，並將 vwrapper 的值寫進 *version 與 *res 中。

接著表示讀取完畢，將 slot 的活躍 reader 減一，然而此時，活躍 reader 等於 0，如果執行緒的最新版不是此目前 slot 的版本，那就要 signal_write ，因為代表有 writer 在等待。這樣的作法是要確保讀寫操作的同步，避免競爭。

if (atomic_dec_32_nv(&v->nreaders) == 0 &&
    atomic_read_64(&vp->next_version) != (*version + 1))
    signal_writer(vp);

最後設置新的 wrapper。

pthread_setspecific(vp->tkey, wrapper);

thread_safe_var_set

首先，構建一個新的 wrapper 變數來保存新的值。

wrapper = calloc(1, sizeof(*wrapper)
wrapper->dtor = vp->dtor;
wrapper->nref = 0;
wrapper->ptr = cfdata;

接著，使用 pthread_mutex_lock(&vp->write_lock) 來鎖定寫入操作，這也起到 memory barrier 的作用，以確保之前的寫操作完成，寫入操作是序列化。隨後，將新 wrapper 的版本號設置為 vp->next_version，也將這個版本號返回給 new_version。

接著，獲取下一個 slot v。

如果是這 tsv 第一次寫入，則將這新 wrapper 設置在兩個 slot 上。每個 slot 的 wrapper 引用計數(nref) 增加一次，並將這些 slot 的 wrapper 更新為新的 wrapper。然後，將 vp->next_version 增加一，並藉由 pthread_cond_signal(&vp->waiter_cv)通知等待的 reader ，讀取新的值。最後，解鎖寫入操作並結束函式。

如果這不是第一次寫入，則這新 wrapper 的引用計數增加一次。然後，等待直到 slot 沒有活躍的 reader。如果有活躍的 reader，則使用 pthread_cond_wait(&vp->cv, &vp->cv_lock) 不斷等待，直到所有 reader 釋放 cv。

while (atomic_read_32(&v->nreaders) > 0) {
    pthread_cond_wait(&vp->cv, &vp->cv_lock)) != 0);

接著，解鎖 cv_lock 後，將 v->wrapper 更新為新的 wrapper，並將 v->version 和 vp->next_version 都增加一。最後，釋放舊的 wrapper，並解鎖 write_lock。

這個過程與 QSBR（Quiescent State Based Reclamation）很相似，只有在最後一個活躍的 reader 不再讀取後，才能寫入新值並回收舊值。

如何確保上述流程可正確運作？

slot-list

資料結構

struct value {
    volatile struct value   *next;      /* 指向之前的（仍引用的）值 */
    void                    *value;     /* 實際值 */
    volatile uint64_t       version;    /* 版本 */
    volatile uint32_t       referenced; /* 用於標記和清除 */
};

/*
 * 每個讀取此 tsv 的執行緒都會獲得其中一個。
 */
struct slot {
    volatile struct value       *value; /* 最後讀取的值的引用 */
    volatile uint32_t           in_use; 
    thread_safe_var             vp;     /* for cleanup from thread key dtor */
};

/*
 * slots 被分配在一個陣列中，而這陣列會被連結到一個更大的邏輯陣列。
 */

struct slots {
    volatile struct slots   *next;      
    struct slot             *slot_array;
    volatile uint32_t       slot_count; 
    uint32_t                slot_base;  /* slot_array[0] 的索引*/
};

struct thread_safe_var_s {
    pthread_key_t           tkey;           /* 檢測執行緒退出 */
    pthread_mutex_t         write_lock;     /* 一次一個 writer */
    pthread_mutex_t         waiter_lock;    /* 向 waiters 發出訊號時用 */
    pthread_cond_t          waiter_cv;      /* 向 waiters 發出訊號 */
    var_dtor_t              dtor;           /* value destructor */
    volatile struct value   *values;        /* atomic 引用值得鏈結串列的頭 */
    volatile struct slots   *slots;         /* atomic reader 的 subscription slots */
    volatile uint32_t       next_slot_idx;  /* atomic 的下一個新 slot的索引 */
    volatile uint32_t       slots_in_use;   /* atomic 的活著 reader 數 */
    uint32_t                nvalues;        /* writer-only; for housekeeping */
};

int thread_safe_var_get(thread_safe_var vp, void **res, uint64_t *version)

• 將 vp->tkey 寫入 slot 變數
• 如果還沒寫入任何值進此執行緒的特定資料過 (pthread_getspecific(vp->tkey) == NULL)，用 get_free_slot 尋找空的 slot，倘若都沒有空的 slot 才用 grow_slot 去產出一個新的 slot，之後將 slot 寫入此執行緒的特定資料。

if ((slot = pthread_getspecific(vp->tkey)) == NULL) {
    /* First time for this thread -> O(N) slow path (subscribe thread) */
    slot_idx = atomic_inc_32_nv(&vp->next_slot_idx) - 1; 
    if ((slot = get_free_slot(vp)) == NULL) {
        /* Slower path still: grow slots array list */
        err = grow_slots(vp, slot_idx, 2);  /* O(log N) */
        slot = get_slot(vp, slot_idx);      /* O(N) */
        atomic_write_32(&slot->in_use, 1);
    }
    slots_in_use = atomic_inc_32_nv(&vp->slots_in_use);
    if ((err = pthread_setspecific(vp->tkey, slot)) != 0)
        return err;
}

接著在迴圈中反覆確認，slot 的 value 就是 vp->tkey->values 的首位, 也就是目前最新的值，倘若不是，就將 slot->value 的值寫進 vp->tkey->values 的首位。

while (atomic_read_ptr((volatile void **)&slot->value) !=
           (newest = atomic_read_ptr((volatile void **)&vp->values)))
    atomic_write_ptr((volatile void **)&slot->value, newest);

grow_slots(thread_safe_var vp, uint32_t slot_idx, int tries)

slot_idx 為期望該 slot 的在 slots 索引位置，tries 為次數上限。無鎖定方式增長 slot_array。

首先去計算目前總 vp->slots 這鏈結串列的 slot 總數，每一個 slots 結構中有包含 slot_count，因此迭代鏈結串列並加總 slot_count 即能得知。

volatile struct slots **slotsp;
struct slots *new_slots;

for (slotsp = &vp->slots;
     atomic_read_ptr((volatile void **)slotsp) != NULL;
     slotsp = &((struct slots *)atomic_read_ptr((volatile void **)slotsp))->next)
    nslots += (*slotsp)->slot_count;

倘若總 slot 數超過期望slot的索引位置，返回 0，表示成功。而嘗試次數超過預期就回傳 EAGAIN，以外就新建 new_slots 分配新的記憶體。

if (nslots > slot_idx)
    return 0;

if (tries < 1)
    return EAGAIN;

if ((new_slots = calloc(1, sizeof(*new_slots))) == NULL)
    return errno;

EAGAIN 為錯誤碼，定義於 C 標準函式庫裡，EAGAIN 被定義在 /usr/include/asm-generic/errno-bash.h

#define EAGAIN 11 /* Try again */

確定要新增 slot 的數量(additions)。如果目前沒有任何 slot，初始 addition 數量設為 4。否則，初始設置為目前 nslots 的 1.5 倍。這可能是一種增量擴展策略。最終期望能夠增加的 slot 數能夠超過 slot_idx。 接著就是初始化新的 slot_array：

additions = (nslots == 0) ? 4 : nslots + nslots / 2;
while (slot_idx >= nslots + additions) {
    additions += additions + additions / 2;
    tries++;
}

new_slots->slot_array = calloc(additions, sizeof(*new_slots->slot_array));
// Then initialize the new slot_array

slot_idx - nslots 為 slot_idx 在 new_slots 中的索引值，將它標記為有使用。

atomic_write_32(&new_slots->slot_array[slot_idx - nslots].in_use, 1);

嘗試將 new_slots 加入到 &vp->slots 的最後一位

if (atomic_cas_ptr((volatile void **)slotsp, NULL, new_slots) != NULL) {
    free(new_slots->slot_array);
    free(new_slots);
}

最後做遞迴，倘若此次擴展的 slot 數超過 slot_idx，會在下次遞迴中結束，倘若此競爭失敗，就再次嘗試擴展。

return grow_slots(vp, slot_idx, tries - 1);

thread_safe_var_set

建構 new_value (存data 進去)之後，new_value->next 指向 values 的開頭，之後也確定 new_version 了

new_value->value = data;
new_value->next = atomic_read_ptr((volatile void **)&vp->values);
if (new_value->next == NULL)
    new_value->version = 1;
else
    new_value->version = new_value->next->version + 1;

*new_version = new_value->version;

接著確定 new_value 為 vp->values 的開頭，並且 vp 上 的 nvalues 加一。

/* Publish the new value */
atomic_write_ptr((volatile void **)&vp->values, new_value);
vp->nvalues++;

同樣有記得要去 pthread_cond_signal(&vp->waiter_cv); 呼叫在等待的執行緒。

呼叫 mark_values(vp) 對舊值執行垃圾回收(Garabage Collection, GC)，標記仍在使用的值並識別可以釋放的值。下一段介紹更多。

old_values = mark_values(vp);

接著，呼叫 sched_yield() 放棄 CPU，允許其他執行緒（最好是 reader ）運作，接著解鎖 write_lock、釋放不再使用的舊值的記憶體，如果已設置，則呼叫析構函數 dtor，最終返回解鎖寫鎖的狀態。

mark_value

mark_values 的目的是標記目前被引用的值，並回收那些不再被引用的舊值，基於 mark-and-sweep 的 GC。以下透過如何不把 thread_safe_var_set 剛寫入的值給回收掉的角度，去理解 mark_value。

mark-and-sweep 主要兩階段:

• 1. 標記階段 (mark phase):

先走訪 tsv (變數名稱: vp)上所有的 value 這些值儲存在 old_values_array 中，接著走訪所有的 slots 中的 value，如果這 value 也有出現在 old_values_array，被認為還有被引用，在第二階段時就不會被回收掉。

for (i = 0, v = atomic_read_ptr((volatile void **)&vp->values); i < vp->nvalues && v != NULL; v = v->next, i++)
    old_values_array[i] = v;
qsort(old_values_array, vp->nvalues, sizeof(old_values_array[0]),value_cmp);
vp->values->referenced = 1; /* curr value is always in use */

為了加速，使用 qsort 為 old_values_array 做排序，之後用二分搜尋法判斷某 value 是否存在在 old_values_array。

for (slots = atomic_read_ptr((volatile void **)&vp->slots); slots != NULL;) {
    for (i = 0; i < slots->slot_count; i++) {
        slot = &slots->slot_array[i];
        v = atomic_read_ptr((volatile void **)&slot->value);

        if (v == NULL || v == vp->values) /* vp->values 中的最新值總是被設定為 referenced，確保了它不會被誤刪除 */
            continue;
        if ((value_binary_search(old_values_array, vp->nvalues, v)) != NULL) {
            v->referenced = 1;
        }
    }
    slots = slots->next;
}

• 2. 清除階段 (sweep phase):

將那些 tsv 的 values 沒有被標記的值從鍊結串列中移除，並將這些 values 加入 old_values 鍊結串列中。 而那些有在標記階段的有標記的 values，重設 referenced 為 0，為了下一次做 GC 有機會被回收。

for (p = &vp->values; *p != NULL;) {
    v = *p;

    if (!v->referenced) {
        *p = v->next;
        v->next = old_values;
        old_values = v; // 將 v 接到 old_values 的頭
        vp->nvalues--;
        continue;
    }

    v->referenced = 0;
    p = &v->next;
}

理解 mark_values 的關鍵在於理解 mark_values 函數如何區分目前有效的值和無效的值。

在發佈新值之前，slot-list 實作不會等待顯式寬限期。相反，它依賴於 mark_values() 確定哪些值可以安全回收。

TODO: CTP 與 Userspace RCU 的效能評估

注意 Userspace RCU 的 flavor 和 CTP 的 slot-{pair,list}

$ lscpu

Architecture:            x86_64
  CPU op-mode(s):        32-bit, 64-bit
  Address sizes:         39 bits physical, 48 bits virtual
  Byte Order:            Little Endian
CPU(s):                  12
  On-line CPU(s) list:   0,2,4,6,8-11
  Off-line CPU(s) list:  1,3,5,7
Vendor ID:               GenuineIntel
  Model name:            12th Gen Intel(R) Core(TM) i5-12450H
    CPU family:          6
    Model:               154
    Thread(s) per core:  1
    Core(s) per socket:  8
    Socket(s):           1
    Stepping:            3
    CPU max MHz:         4400.0000
    CPU min MHz:         0.0000
    BogoMIPS:            4992.00
arch_capabilities
Virtualization features: 
  Virtualization:        VT-x
Caches (sum of all):     
  L1d:                   320 KiB (8 instances)
  L1i:                   384 KiB (8 instances)
  L2:                    7 MiB (5 instances)
  L3:                    12 MiB (1 instance)
NUMA:                    
  NUMA node(s):          1
  NUMA node0 CPU(s):     0,2,4,6,8-11

關閉 hyperthreading 設定
根據論壇討論: Disable hyperthreading from within Linux (no access to BIOS)

$ cat /sys/devices/system/cpu/smt/active
1
$ echo off | sudo tee /sys/devices/system/cpu/smt/control
$ cat /sys/devices/system/cpu/smt/active
0

與授課教師，討論測試結果異常，可能原因出自於，我的處理器有分 P-cores 與 E-cores，因此以下的測試，都集中於 P-cores 進行。

如何分辨 P-core 與 E-core

雖然從 intel 的問答區 how to know a core is P-core or E-core，得知無直接得知哪一核為 P-core 或 E-core，但從reddit 討論 :how to identify p-cores and e-cores 得知以下操作

$ lscpu --all --extended
CPU NODE SOCKET CORE L1d:L1i:L2:L3 ONLINE    MAXMHZ   MINMHZ      MHZ
  0    0      0    0 0:0:0:0          yes 4400.0000 400.0000  865.329
  1    -      -    - -                 no         -        -        -
  2    0      0    1 4:4:1:0          yes 4400.0000 400.0000 1200.428
  3    -      -    - -                 no         -        -        -
  4    0      0    2 8:8:2:0          yes 4400.0000 400.0000  921.834
  5    -      -    - -                 no         -        -        -
  6    0      0    3 12:12:3:0        yes 4400.0000 400.0000 1223.704
  7    -      -    - -                 no         -        -        -
  8    0      0    4 20:20:5:0        yes 3300.0000 400.0000 1302.425
  9    0      0    5 21:21:5:0        yes 3300.0000 400.0000  400.000
 10    0      0    6 22:22:5:0        yes 3300.0000 400.0000 1106.814
 11    0      0    7 23:23:5:0        yes 3300.0000 400.0000 1177.823

查看 MAXMHZ 列，便能得知
我有 4 P-cores 為 Cores 0, 2, 4 與 6，而 4 E-cores 為 Cores 8, 9, 10 與 11。

power management

cpufreq-set(1)

cpufreq-set - A small tool which allows to modify cpufreq settings.

-c 設定處理器編號
-g 設定 cpufreq governor
--max, --min: 設定 cpufreq governor 可以選擇的新的最高, 最低 CPU 頻率。

接著逐一設定 p-core:
以下我設定處理器編號為 0 的 P-core 使用的 CPUfreq 策略為 perfromace ，從而避免其他 governor（如 powersave）通常發生的動態頻率調整。這確保了可預測的最佳性能:

$ sudo cpufreq-set -c 0 -g performance --max 4400000  --min 4200000 

用以下迴圈檢查是否設定成功

$ for core in 0 2 4 6; do echo "Core $core:"; sudo cpufreq-info -c $core; done

實驗重現步驟

除了上述的設定，以下闡述關於我測試檔的使用方式。
取得程式碼:

$ git clone https://github.com/eleanorLYJ/ctp

測試 ctp 必要條件為建構 libtsgv.so， 因此需要在 ctp 目錄中使用 make 獲取該檔案。而主要測試檔案存於 ctp/test， 故再切目錄至test。

$ make
$ cd test

記憶體與吞吐量長條圖

1. 使用 make 生成執行檔。

$ make

2. 執行以下命令產生性能結果：

$ ./run_perf.sh {RUN_MODE(0)} {NUM_READERS} {NUM_WRITERS} {VALID_CPUS} {OUTPUT_DIR} {FIFO_PRIORITY}

範例：

$ ./run_perf.sh 0 7 1 0,2,4,6 output 90

以上命令，將限制 0 2 4 6 編碼的 cpu 執行程式碼，之後使用不同的方法（5 urcu + 2 ctp）生成 1 個 writer 和 7 個 reader 的記憶體與吞吐量長條圖，並且將中間結果存於 output 目錄，並且設定 FIFO 優先級（整數值）為 90。

記憶體與吞吐量折線圖

使用 make 生成可執行文件。
執行以下命令生成性能結果：

$ ./run_perf.sh {RUN_MODE(1)} {NUM_READERS} {NUM_WRITERS} {VALID_CPUS} {OUTPUT_DIR} {FIFO_PRIORITY}

範例：

$ ./run_perf.sh 1 100 1 0,2,4,6 output 90

以上命令，這將使用不同的方法（5 urcu + 2 ctp）生成 1 個寫入者和多個讀取者 [1, 100] 的不同組合而成的的記憶體與吞吐量折線圖，並且將中間結果存於 output 目錄，並且設定 FIFO 優先級（整數值）為 90。

建立 7 個 reader 執行緒 1 個 writer 執行緒，測 URCU 與 CTP

以下測試是建立 7 個 reader 執行緒，1 個 writer 執行緒，在主執行緒建立完所有的執行緒後，會等待 1 秒，接著改變終止變數，讓所有的執行緒就要停止計算讀取 tsv 或對 tsv 寫入隨機資料的計數。

其中 5 個 flavor 的 URCU 中，qsbr 具比較特別的寫法，在 reader 執行緒中，每 1024 次讀取會進入一次 quiescent_state (呼叫 rcu_quiescent_state)，藉此writer 能夠檢測到 GP 的結束，從而判斷記憶體的回收時機。

throughput

比較不同實作 1 秒內 7 個 readers 的讀取次數的總和的直條圖

同時，比較不同實作 1 秒內 1 個 writer 的讀取次數的總和的直條圖

以下是在我設定 CPU affinity, 關閉 hperthreading, 設定 taskset 等操作之前的圖 (固定 2 writers，搭配 1 到 10 個 reader)

出現了只有一個執行的 reader 執行緒總讀取最多，增加執行緒後總讀取次數卻下降的奇怪現象

推估有幾個問題造成的:

1. Cache Coherency Overhead
2. Context Switching
3. CPU mitgration

我期待設定 cpu affinity 後能減少 context switch 與 CPU mitgration 帶來的影響。

我在各個測試檔中設定 CPU affinity

• commit 37d7785: Add functions to set and check thread CPU affinity
• Commit bd58843: Enhance Validation and Diagnostics in CTP Testing

設定 cpu affinity 中，兩個重要的函式

pthread_setaffinity_np, pthread_getaffinity_np: set/get CPU affinity of a thread

除了設定 cpu affinity 之後 ,使用 taskset 控制執行緒在指定 CPU 上的運行,另外關閉 hyperthread 讓 CPU 一次只處理一個執行緒。在此之後重新畫的折線圖。

以下說明 設定 cpu affinity 對我測試的作用:

其環境沒有關閉 hyperthread，也沒有設定 taskset 的結果:
perf stat -e cycles,instructions,cache-references,cache-misses,context-switches,cpu-migrations {.exe} 7 2

Benchmark	qsbr	signal	mb	memb	bp	slotpair	slotlist
Cycles(core/atom)	66M/55M	118M/86M	94M/63M	114M/77M	71M/52M	114M/72M	121M/77M
Cache Misses (core/atom)	93k/72k	87k/71k	96k/42k	79k/55k	101k/53k	185k/78k	219k/137k
context-switches	48k	50k	69k	46k	51k	49k	52k
CPU Migrations	1040	1261	992	987	1296	6638	1,0552

以下為在測試檔中設定 cpu affinity 後，之後可以看到 cycles,Cache Misses, context-switches 與 cpu-mitgrations 次數都下降

Program	qsbr	signal	mb	memb	bp	slotpair	slotlist
Cycles (core/atom)	2.776B/3.687B	4.526B/68.07M	5.32B/4.014B	3.557B/7.597B	3.324B/3.726B	3.162B/6.289B	4.929B/5.75B
Cache Misses (core/atom)	46.28k/54.29k	57.18k/60.60k	62.64k/36.96k	43.65k/44.42k	52.10k/71.09k	128.60k/240.79k	146.68k/131.63k
Context Switches	42.47k	43.19k	66.15k	45.04k	45.77k	35.54k	47.76k
CPU Migrations	12	10	10	12	13	7	8

建立 [1, 100] 個 reader 執行緒，1 個 writer 執行緒 測 urcu 與 CTP

在讀取吞吐量測試中，qsbr 和 bp 表現最佳，一秒內的讀取次數範圍在 555,000 到 655,000 次之間。這表明它們在高頻率讀取的操作具有優異的表現。mb 的讀取表現次好，但在初期從 1 到 10 個讀取者時，其讀取次數有顯著下降，隨後變得平穩，保持在第三高的讀取次數。相比之下，memb 和 signal 表現中等，而 slotpair 和 slotlist 的讀取表現最差。

TODO: 探討為什麼是 3 readers 和 1 writer 的組合讀取總量特別低

在寫入吞吐量測試中，CTP 方法（slotpair 和 slotlist）表現最佳，一秒內的寫入次數範圍在 30,000 到 41,000 次之間。其餘方法在 reader 增加到 2 以後，寫入次數驟降到十位數。

記憶體使用量

Wikipedia 不可簡稱 wiki。
參見 CS:APP 第 6 章的描述及〈每位程式開發者都該有的記憶體知識〉。

閱讀 Wikipedia: CPU cache

• Instruction cache (I-cache): 用於加速可執行指令的存取
• Data cache (D-cache): 用於加速資料存取和儲存；資料快取通常被組織為更多快取層級的層次結構（L1、L2 等)

補 CS:APP ch6

perf stat 輸出解讀

用 perf 測快取使用量

perf stat -e cache-references,cache-misses,L1-dcache-loads,L1-dcache-stores,LLC-load-misses,LLC-store-misses

我每一次測的圖形都不盡相同，我認為是因為我是寫入隨機值的原因，而以下就討論各方法的相對位置

Cache Misses:
CTP 方法的 cache miss 數量較高，這表明其資料載入效率較低，可能是因為頻繁的寫入操作導致更多的資料需要從主記憶體載入。

L1 DCache Load Misses:
CTP 方法的 load miss 數量較高，而 bp 和 qsbr 的數量較低，顯示出它們在資料載入方面的效率更高。

LL Load Misses:
CTP 方法相較其他方法更容易出現異常高的 load miss 數，這可能影響其效能，而在大部分情況下，所有方法的 load miss 數位於中間部分。

L1 DCache Store Misses: 所有方法的 store miss 數量均等於 2，顯示出在寫入操作上的一致性。

LL Store Misses: CTP 方法的 store miss 數量較低，這表明其在寫入操作上的效率較高。bp 和 qsbr 的 store miss 數量較高，而 mb、memb 和 signal 位於中間部分。

建立 [1, 100] 個 reader 執行緒，1 個 writer 執行緒測試 bullet-proof URCU 是否註冊執行緒會影響效能

在撰寫 urcu 測試檔中，發現 urcu README 談到 bullet-proof 的 urcu (bp) 可以不用 ruc_init() 與註冊(reigster)執行緒。

urcu_bp_init(), and urcu_bp_unregister_thread() all become nops, whereas calling urcu_bp_register_thread() becomes optional.

我發現了在計算 throughput 時，bp 將 rcu_register_thread() 與 rcu_unregister_thread() 移除，整體的 throughput 會下降 ， 因此有了以下的折線圖

我將淺藍色線 (bp_no_reg) 為使用bp uruc 同架構的程式碼，但 rcu_init()、 rcu_register_thread() 與 rcu_unregister_thread() 移除。

writer 讀寫次數最大 103 最低到 4，然而兩測試檔測到的寫入量都太少，因此從圖片無法看出

從圖中能看出，少了 rcu_init()、 rcu_register_thread() 與 rcu_unregister_thread() 的 bp_no_reg 的吞吐量測試變得非常地不穩定，而這還需要更多的細討論原因。

TODO: 看 bullet-proof urcu 中，呼叫 rcu_register_thread() 會動用到哪一塊原始碼。

TODO: 評估 CTP 的限制和改進方案

修改部分為 slotlist 的 grow_slots()，此函式考慮在多執行緒中無鎖擴增 slots。會發生該函式的主要競爭條位置在 slotsp (vp->slots 的最後一個 slots)上，此使用該 atomic_cas_ptr 函式嘗試寫入，這確保一次只有一個執行緒可以成功更新 slot_array 。如果一個執行緒由於另一個執行緒競爭失敗而無法更新，它將進行清理並遞迴重試。以下修改目的是要減少不必要的遞迴次數。

    /* Add new slots to logical array of slots */
    if (atomic_cas_ptr((volatile void **)slotsp, NULL, new_slots) != NULL) {
        free(new_slots->slot_array);
        free(new_slots);
+        grow_slots(vp, slot_idx, tries - 1);
    }
-    return grow_slots(vp, slot_idx, tries - 1);
+    return 0
}

測試 7 readers 與 1 writer 的讀取或寫入次數

	before	after
reader counts	425055	466009
writer counts	319918	333802

總結

CTP 與 URCU 相比

CTP 優點

1. 更簡單的 writer 邏輯：CTP 具有更簡單的 writer 邏輯，因為 CTP 依賴於引用計數，而不是管理多個資料版本和寬限期。
2. 寫入操作較好：在測試中，CTP 的 store miss 次數較低，這表明在寫入操作上，CTP 具有較高的效率，因為它避免了頻繁的快取儲存失敗
3. API 簡單使用，使用者不需要進行大量的程式碼修改

CTP 缺點

1. 缺少豐富並行處理資料結構，如 linked list, queue, hash 等
2. 讀取操作較差: 在測試中，CTP 的 load miss 次數較高，特別是在 L1 DCache load miss 和 LLC load miss 方面。這表明在讀取操作上，CTP 的效率不如 URCU。

闡述更多記憶體使用量的分析。

ok

結論

從分析程式碼，能得知 slor-pair 僅維護兩個版本的值，實作簡單， slot-list 維護多版本的值，然而在測試結果中，兩者的優勢與劣勢都相似，適合讀寫比例較均衡且需要立即記憶體釋放的場景。

根據測試結果，URCU 方法適合高讀取且低寫入的應用情境，如查詢系統。具體資料顯示，一秒鐘 qsbr 和 bp 的讀取次數範圍在 555,000 到 655,000 次之間，而 CTP 方法在這方面較差，讀取次數範圍在 355,000 到 450,000 次之間，但在寫入次數上顯著優於 URCU 方法，大概落在 30000～41000 之間，而 urcu 都降至個位數，因此 CTP 方法，儘管其在記憶體載入效率（如 cache miss 和 load miss）方面的表現不如 URCU 方法，但在高頻寫入操作下，CTP 方法能提供更好的效能和效率。