2024q1 Homework5 (assessment)

contributed by < stevendd543 >

注意作業書寫規範！

因為自動飲料機而延畢的那一年

看完後我發現裡面有一句話很傳神，「資工系不會寫程式，機械系不會做機械」，其實有時候都會納悶會什麼學了幾年的電腦還是不及其他寫成是厲害的人，後來才發現我少了遇到問題的經歷，做飲料機不像教科書一樣步步引導你學習，他是當你規劃後且實作才會浮現一些當初未全面考量的問題，就像你在數學解題目時遇到不會你只需要往後翻答案，因為這題的解答就在那，自然而然感覺成就感滿滿，但在沒有解答情況下，遇到問題就想逃避，而不從各領域去思考解決，老師常說細節的考慮常常在莽撞的決策中忽略掉，導致簡單的道路被拐彎曲折了。

前四周測驗題探討

研讀第 1 到第 6 週教材

希望投入的期末專題

1、並行程式設計

// the number of non-zero entries ('1' bits)
// https://en.wikichip.org/wiki/population_count
int popcnt(int x)
{
    // No branch. No compiler extension (e.g., hardware extension)

}

TODO: 繼續作答，不要看解答

int: 32-bit or 4B
bitmask
0 1 0 1 0 1 0 1
1 0 1 0 1 0 1 0

0 0 1 1 0 0 1 1
1 1 0 0 1 1 0 0

完成 popcnt

知道 popcnt(x) = x -

⌊ x / 2 ⌋

⌊ x / 2^{2} ⌋

…-

⌊ x / 2^{31} ⌋

後，我從範例 1101 發現一件事，1101->0110->0011->0001，如果以 4-bits 來說每此往右邊位移左邊就會多一個 0，那我就可以把問題分成四份處理，每次右移後就用0111 去做 & 操作四份中每份就會像單一 4-bits 操作一樣完成計算，不過畢竟是在八個區塊計算出來的，八個區塊結果還需要處裡，

int popcnt(int x)
{
    unsigned v; //1101
    v = (x>>1) & 0x77777777; //0110
    x-=v; 
    v = (v>>1) & 0x77777777; //0011
    x-=v;
    v = (v>>1) & 0x77777777; //0001
    x-=v;
    // ___D ___C ___B ___A -> A+B+C+D = ans
    x = (x + (x>>4)) & 0x0f0f0f0f;
    x = (x + (x>>8)) & 0x00ff00ff;
    x = (x + (x>>16)) & 0x000000ff;
    
    return x;
    
}

#include <stdatomic.h> // C11 Atomics
typedef struct __list {
    int val;
    struct __list *next;
} list_t;

void *add_tail(list_t *head, void *data)
{
    
    list_t *node = (list_t*)calloc(1,sizeof(list_t));
    list_t **p;
    node->val = (int)data;
    node->next = NULL;
    
    list_t *tail = NULL;
    p = &head->next;
    while(1) {
        list_t *old = atomic_load_explicit(p, memory_order_acquire);
        if (old == NULL){
            if(atomic_compare_exchange_strong(p, &tail, node, memory_order_release, memory_order_relaxed) {
                break;
            }
        }
        p = &old->next;
    }
}

bool remove(list_t *head, list_t *node)
{
    int v;
    for(list_t **tmp = &head; *tmp; tmp = *tmp->next){    
        v = atomic_load(*tmp);
        if(v == node->val && node == *tmp){
             return atomic_compare_exchange_weak(&(*tmp)->next,
                                                   &node,
                                                   *tmp->next->next);
        }
    }
    return false;
}
// Implement concurrent add_tail and remove

#include <stdatomic.h> // C11 Atomics

#define N_THREAD 10


typedef struct __list {
    int val;
    struct __list *next;
} list_t;


Atomic_ list_t* HP[N_THREAD];


bool protect(int tid, list_t *p){
    do {
        old = atomic_load_explicit(&p,memory_order_required);
        if (old == NULL)
            return false;
        atomic_store_explicit(&HP[tid], &p, memory_order_release);
    } while(old != atomic_load_explicit(&p,memory_order_required);)
    return true;
}
void *add_tail(list_t *head, void *data)
{
    
    list_t *node = (list_t*)calloc(1,sizeof(list_t));
    list_t *p;
    node->val = (int)data;
    node->next = NULL;
    
    list_t *tail = NULL;
    _Atomic(list_t*) *p = (_Atomic(list_t*) *)&head->next;;
    
    while(1) {
        if(protect(tid, p)){
            list_t *old = atomic_load_explicit(&p, memory_order_acquire);
            if (old == NULL) {
                if(atomic_compare_exchange_strong(&p, &tail, node, memory_order_release, memory_order_relaxed) {
                    break;
            } else {
                if(protect(tid, p->next)){
                    p = atomic_load_explicit(&old->next, memory_order_acquire);
                }
            } 
            
        }
        
    }
}

bool remove(list_t *head, list_t *node)
{
    int v;
    list_t *p = head;
    while(1) {
        if(protect(tid, p))
    }
    for(; *tmp; tmp = *tmp->next){    
        v = atomic_load(*tmp);
        if(v == node->val && node == *tmp){
             return atomic_compare_exchange_weak(&(*tmp)->next,
                                                   &node,
                                                   *tmp->next->next);
        }
    }
    return false;
}
// Implement concurrent add_tail and remove

TODO: 繼續作答

TODO: Quiz 10 + Quiz 12

Quiz 10

測驗一

AAAA = atomic_fetch_or
BBBB = get(filter, h1) && get(filter, h2)
CCCC = SIGHUP

測驗二

AAAA = atomic_compare_exchange_strong(&ctx->is_freeing, &old, True) // 防止其他 thread 試圖 free 掉正在 free 的 node
BBBB = atomic_compare_exchange_strong(&ctx->is_freeing, &old, True)
CCCC = atomic_compare_exchange_strong (&ctx->head, &old_head, new_head,)

測驗三

DDDD = EPOLLIN ｜EPOLLOUT
EEEE = epoll_wait
bloom filter
!atomic_compare_exchange_strong(&ctx->head, &old_head, new_head)

疑問: old_head 已經被 HP 卡住，為何還需要 exchange 來確認目前是否相同? 不能直接將 &ctx->head 儲存 new_head 嗎

cas(&mu->val, LOCKED_NO_WAITER, LOCKED) != UNLOCKED 如果終究回傳 expected 這會成立嗎?

Quiz 12

測驗 1

AAAA = &futex_word
BBBB =

測驗 2

在解釋程式碼結構前，先理解 lap 在ring buffer 中扮演什麼角色以及它的用途。

struct chan_item {
    _Atomic uint32_t lap;
    void *data;
};

lap 是存放在每一個緩衝資料格內的一個成員，他主要用來記錄目前此格資料的使用狀況，可以發現lap主要出現在傳送與接收資料的時候，首先有兩個特殊的 head 與 tail 他在高位 32 bits 暗藏了 lap 的值，我們知道 tail 用來放入資料 head 用來取出資料，從trysend_buf中可以發現，他會先取得 channel 尾端的 item 位置之後再將其位置紀錄的 lap 與存放在 tail 高位的 lap 做比對，這裡重點有幾個，存放在 tail 變數中的是獨立的，與 channel item 內存放的並不相同，為了區分頭尾，此不等式若比較失敗就表示無法加入或者無法寄送資料到 channel 內。

這裡可發現 tail 放入資料後都會 +1 ，在 +1 前每個 channel item 的 lap 都是 0，而且 tail 高位存放的 lap 還沒到尾端不會 +2 所以也是 0。

在看這張圖假設 head 取了兩個元素就會對 channel item lap +1 變成 2，如此一來當 ring buffer tail 走了一圈 +2 後就知道原本上一輪寫入的資料已經被取用，因此可以將其視為空格進行填入資料。換作是 head 也是同樣判斷方式，但是要等到資料放入 lap 變為 1 時才可讀取，這也是為何當初 channel_init 要將其 head 設為 1 的原因。

ch->head = (uint64_t) 1 << 32;
ch->tail = 0;

    tail = atomic_load_explicit(&ch->tail, memory_order_acquire);
    uint32_t pos = tail, lap = tail >> 32;
    item = ch->ring + pos;

    if (atomic_load_explicit(&item->lap, memory_order_acquire) != lap) {
        errno = EAGAIN;
        return -1;
    }

channel 的資料結構

struct chan_item {
    _Atomic uint32_t lap;
    void *data;
};

struct chan {
    _Atomic bool closed;
    _Atomic(void **) datap;
    struct mutex send_mtx, recv_mtx;
    _Atomic uint32_t send_ftx, recv_ftx;
    _Atomic size_t send_waiters, recv_waiters;
    
    size_t cap;
    _Atomic uint64_t head, tail;
    struct chan_item ring[0];
};

typedef void *(*chan_alloc_func_t)(size_t);

strcut chan 主要是用來實現 go channel 的一些機制，它分成緩衝與非緩衝通道。非緩衝通道並非完全沒有空間，只是他只能存放一個元素，直到他被取出否則他 routine 將無法推入新的元素而被暫停，此法更 mutex lock 一樣可以保護共享變數。

bool closed: 用來表示 channel 是否還能使用
(void **)datap: 用於無緩衝通道交換數據
send or recv mtx: 用於保證最多只有一個存取權
send or recv waiters:用於緩衝通道，表示在 futex wait 的 thead 數量
send_ftx, recv_ftx: 用於管理等待的 thread
























WARNING: ThreadSanitizer: data race (pid=123819)
  Read of size 8 at 0x7ff2c99be2a8 by thread T1:
    #0 reader /home/dong/linux2024/gcftx/main.c:42 (channel_test+0x2e94)

  Previous write of size 8 at 0x7ff2c99be2a8 by thread T81:
    #0 chan_send_unbuf /home/dong/linux2024/gcftx/chan.c:180 (channel_test+0x266d)
    #1 chan_send /home/dong/linux2024/gcftx/chan.c:261 (channel_test+0x2c8d)
    #2 writer /home/dong/linux2024/gcftx/main.c:31 (channel_test+0x2da5)

  Location is stack of thread T1.

  Thread T1 (tid=123821, running) created by main thread at:
    #0 pthread_create ../../../../src/libsanitizer/tsan/tsan_interceptors_posix.cpp:962 (libtsan.so.0+0x5ea79)
    #1 create_threads /home/dong/linux2024/gcftx/main.c:70 (channel_test+0x309f)
    #2 test_chan /home/dong/linux2024/gcftx/main.c:101 (channel_test+0x3356)
    #3 main /home/dong/linux2024/gcftx/main.c:115 (channel_test+0x34fb)

  Thread T81 (tid=123901, running) created by main thread at:
    #0 pthread_create ../../../../src/libsanitizer/tsan/tsan_interceptors_posix.cpp:962 (libtsan.so.0+0x5ea79)
    #1 create_threads /home/dong/linux2024/gcftx/main.c:70 (channel_test+0x309f)
    #2 test_chan /home/dong/linux2024/gcftx/main.c:102 (channel_test+0x3381)
    #3 main /home/dong/linux2024/gcftx/main.c:115 (channel_test+0x34fb)

SUMMARY: ThreadSanitizer: data race /home/dong/linux2024/gcftx/main.c:42 in reader

以上是發現是在 unbuf 時產生 race condition，因此會去探討在所有在無 buffer 情況下的共享變數，不過在檢查的時候發現反而是每個 thread 的區域 msg 接收資料的時候出現 data race。










    // sender
if (!atomic_compare_exchange_strong_explicit(&ch->datap, &ptr, &data,
                                                 memory_order_acq_rel,
                                                 memory_order_acquire)) 
    *ptr = data;  // data race

    // reader 
atomic_fetch_add(&msg_count[a->msg],1);  // data race

為何非 shared memory 也會有 data race 發生?

由此可發現只有在 channel 還有資料的時候才會發生 data race，初步認為是 *ptr 的存取造成的 data race，因為前面條件不成立時 ptr = ch->datap，因此為了避免在此處操作有衝突將其改成以下原子操作 82dfeeb。

// recv
atomic_store(data, *ptr);
// send
atomic_store(&ptr, &data);

ptr 是指向 unbuffer 的變數也就是 channel，不管是從 channel 儲存資料至 thread data 或是 thread data 儲存到 channel 都以原子操作完成即可避免 threads data race。我們知道 senders 或 readers 之間都有 futex 管理，不管是在 critical section 或者作為 channel 資料有無的管理都可以達成，但 sender 與 reader 間是沒有 critical section，所以會有資料被對方清除的可能導致最後不是每一個 msg 都能成功傳遞，主要導因為 unbuffer 不用 ring buffer 一樣在對 data 讀寫之後會儲存一個 lap 在資料結構上，提供給下一個使用者是否可存取資料，以上步驟將會同時發生，但 unbuffer 的防範機制在於以下。

   if (!atomic_compare_exchange_strong_explicit(&ch->datap, &ptr, data,
                                                 memory_order_acq_rel,	                                                 memory_order_acq_rel,
                                                 memory_order_acquire)) {	                                                 memory_order_acquire)) {
        atomic_store_explicit(data, *ptr, memory_order_release);
        atomic_store_explicit(&ch->datap, NULL, memory_order_release);	        atomic_store_explicit(&ch->datap, NULL, memory_order_release);
   }

sender 與 reader 都一樣只要通道還有資料就不對通到直接修改值，而是先取得通道資料或寫入資料後將通道設為 NULL，因此假設兩個 thread 同時進入這個條件區域可能在讀取或寫入前就被改成 NULL，造成讀取失敗。

疑問一: 為何在此部分要判斷 read 大於 queue，read 不是應該是

測驗 3

const 只能 read-only ?

typedef union {
    volatile uint32_t w;
    volatile const uint32_t r;
} counter_t;

if (self->head.r >= SPSC_QUEUE_SIZE)
        self->head.w = 0;

:::
c 語言的 union 與 struct 差異在於 union 中的成員記憶體位置是共享同一個地方，他不但可以合法的以不同形態存取成員，也能達到 atomic。