# POSIX Thread-safe Linked List

## POSIX 執行緒
首先先了解在`ll.h `裡的`pthread.h `內容和搞清楚什麼是thread-safe linked list：**POSIX執行緒（POSIX Threads，縮寫為Pthreads）是POSIX的執行緒標準，定義了創建和操縱執行緒的一套API。** 簡單來說，我們如果要將c語言的程式平行化，最基本的方式就是使用 POSIX 執行緒（簡稱 pthread）來實做多執行緒的程式。以下是一個pthread 函式庫的用法的實際範例：

#include <stdio.h>
#include <pthread.h>
#include <unistd.h>

// 執行緒函數
void* child(void* data) {
  char *str = (char*) data; // 取得輸入資料
  for(int i = 0;i < 3;++i) {
    printf("%s\n", str); // 每秒輸出文字
    sleep(1);
  }
  pthread_exit(NULL); // 離開子執行緒
}

// 主程式
int main() {
  pthread_t t; // 宣告 pthread 變數
  pthread_create(&t, NULL, child, "Child"); // 建立子執行緒

  // 主執行緒工作
  for(int i = 0;i < 3;++i) {
    printf("Master\n"); // 每秒輸出文字
    sleep(1);
  }

  pthread_join(t, NULL); // 等待子執行緒執行完成
  return 0;
}

pthread 的 pthread_create 函數可以用來建立新的執行緒，並以函數指標指定子執行緒所要執行的函數，子執行緒在建立之後，就會以平行的方式執行，在子執行緒的執行期間，主執行緒還是可以正常執行自己的工作，最後主執行緒再以 pthread_join 函數等待子執行緒執行結束，處理後續收尾的動作。其程式執行結果如下：

$ gcc test.c -lpthread -o test
$ ./test
Master
Child
Master
Child
Master
Child

使用`gcc `編譯時須加上`-lpthread `，例如：` gcc test.c -lpthread -o test `

## 互斥鎖（Mutex）
在平行化的程式中，如果發生多個執行緒需要同時存取同一個位置的資料時，就有可能會因為同時存取而產生錯誤，在下面這個例子中，我們定義一個全域變數 counter，用來紀錄某個量的總和，而我們希望在多個執行緒中同時計算，然後統一將加總的結果放在其中。

#include <stdio.h>
#include <pthread.h>
#include <unistd.h>

// 計數器
int counter = 0;

// 執行緒函數
void* child() {
  for(int i = 0;i < 3;++i) {
    int tmp = counter;
    sleep(1); // 故意讓它延遲一下
    counter = tmp + 1;
    printf("Counter = %d\n", counter);
  }
  pthread_exit(NULL);
}

// 主程式
int main() {
  pthread_t t1, t2;
  pthread_create(&t1, NULL, child, NULL);
  pthread_create(&t2, NULL, child, NULL);
  pthread_join(t1, NULL);
  pthread_join(t2, NULL);
  return 0;
}

在這段程式碼中，我們放了兩個子執行緒，每個子執行緒用迴圈跑了三次計算，所以最後的 counter 預期應該是 6，但由於我們將 counter 的值取出來，計算出新的值之後在放回去，兩個子執行緒同時都這樣做的話，計算結果就會不如預期：

$ gcc test.c -lpthread -o test
$ ./test
Counter = 1
Counter = 1
Counter = 2
Counter = 2
Counter = 3
Counter = 3

這個問題的解決方法就是加入一個互斥鎖（mutex），將那些不可以被多個執行緒同時執行的程式碼片段，用互斥鎖包起來，當一個執行緒執行到該處時，就會先上鎖，避免其他的執行緒進入，若其他的執行緒同時也要執行該處的程式碼時，就必須等待先前的執行緒執行完之後，才能接著進入（也就是排隊輪流使用的概念），這樣就可以避免多個執行緒混雜執行，讓結果出錯的問題。

#include <stdio.h>
#include <pthread.h>
#include <unistd.h>

// 計數器
int counter = 0;

// 加入 Mutex
pthread_mutex_t mutex1 = PTHREAD_MUTEX_INITIALIZER;

// 子執行緒函數
void* child() {
  for(int i = 0;i < 3;++i) {
    pthread_mutex_lock( &mutex1 ); // 上鎖
    int tmp = counter;
    sleep(1);
    counter = tmp + 1;
    pthread_mutex_unlock( &mutex1 ); // 解鎖
    printf("Counter = %d\n", counter);
  }
  pthread_exit(NULL);
}

// 主程式
int main() {
  pthread_t t1, t2;
  pthread_create(&t1, NULL, child, NULL);
  pthread_create(&t2, NULL, child, NULL);
  pthread_join(t1, NULL);
  pthread_join(t2, NULL);
  return 0;
}

執行結果：

$ ./test
Counter = 1
Counter = 2
Counter = 3
Counter = 4
Counter = 5
Counter = 6

https://gist.github.com/viking/2521704

ll.c之程式碼執行結果：

$ gcc -I"include" -Wall ll.c -lpthread   -o ll
$ ./ll
PASS Test 1!
PASS Test 2!
PASS Test 3!
PASS Test 4!
PASS Test 5!
PASS Test 6!
PASS Test 7!
PASS Test 8!
PASS Test 9!
PASS Test 10!
PASS Test 11!
PASS Test 12!
PASS Test 13!
(ll: 1 5 6), length: 3
PASSED all 14 tests!

---
## 以 [concurrent-ll](https://github.com/jserv/concurrent-ll) 中 main.c 為參考對 [ll](https://github.com/r-medina/ll) 做測試 <small>[GitHub](https://github.com/happyincent/ll)</small>

$ cat <(echo "CPU:    " `lscpu | grep "Model name" | cut -d':' -f2 | sed "s/  //"`) <(echo "OS:     " `lsb_release -d | cut -f2`) <(echo "Kernel: " `uname -a | cut -d' ' -f1,3,14`) <(echo "gcc:    " `gcc --version | head -n1`)
CPU:     Intel(R) Xeon(R) CPU E5520 @ 2.27GHz
OS:      Ubuntu 16.04.5 LTS
Kernel:  Linux 4.15.0-43-generic x86_64
gcc:     gcc (Ubuntu 5.4.0-6ubuntu1~16.04.11) 5.4.0 20160609

### Illegal instruction (core dumped)

$ gdb -q --args ./bin/test "-n 2"
Reading symbols from ./bin/test...done.
(gdb) r
Starting program: /home/itlab/Desktop/ll/bin/test -n\ 2
[Thread debugging using libthread_db enabled]
Using host libthread_db library "/lib/x86_64-linux-gnu/libthread_db.so.1".
[New Thread 0x7ffff77ef700 (LWP 31597)]
[New Thread 0x7ffff6fee700 (LWP 31598)]

Thread 3 "test" received signal SIGILL, Illegal instruction.
[Switching to Thread 0x7ffff6fee700 (LWP 31598)]
__GI___pthread_rwlock_unlock (rwlock=rwlock@entry=0x7ffff00083c0) at pthread_rwlock_unlock.c:38
38      pthread_rwlock_unlock.c: No such file or directory.

(gdb) info threads
  Id   Target Id         Frame
  1    Thread 0x7ffff7fda700 (LWP 29705) "test" 0x00007ffff7bcac1d in nanosleep () at ../sysdeps/unix/syscall-template.S:84
  2    Thread 0x7ffff77ef700 (LWP 29709) "test" 0x00007ffff7bc6730 in futex_wait (private=<optimized out>, expected=6, futex_word=0x7fffe8004e5c) at ../sysdeps/unix/sysv/linux/futex-internal.h:61
* 3    Thread 0x7ffff6fee700 (LWP 29710) "test" __GI___pthread_rwlock_unlock (rwlock=rwlock@entry=0x7ffff0005710) at pthread_rwlock_unlock.c:38

(gdb) backtrace
#0  __GI___pthread_rwlock_unlock (rwlock=rwlock@entry=0x7ffff0005710) at pthread_rwlock_unlock.c:38
#1  0x0000000000401272 in ll_select_n_min_1 (list=list@entry=0x604010, node=node@entry=0x7ffff6fedee0, n=967, n@entry=977, lt=lt@entry=l_write) at src/ll.c:177
#2  0x0000000000401301 in ll_insert_n (list=0x604010, val=val@entry=0x7ffff6fedf20, n=977) at src/ll.c:204
#3  0x0000000000401382 in ll_insert_last (list=<optimized out>, val=val@entry=0x7ffff6fedf20) at src/ll.c:245
#4  0x0000000000401963 in test (data=0x6040a8) at src/test.c:156
#5  0x00007ffff7bc16ba in start_thread (arg=0x7ffff6fee700) at pthread_create.c:333
#6  0x00007ffff78f741d in clone () at ../sysdeps/unix/sysv/linux/x86_64/clone.S:109

註解掉 `test.c` 中的 `ll_remove_search`

$ ./bin/test -n 2
Thread 0
  #operations   : 32673356
  #inserts   : 1
  #removes   : 0
Thread 1
  #operations   : 5396980
  #inserts   : 1
  #removes   : 0
Duration      : 1001 (ms)
#txs     : 38070336 (38032303.696304 / s)
Expected size: 1025 Actual size: 1025

保留 `test.c` 中的 `ll_remove_search`, 註解掉 `ll_remove_search` 中的 `free(node);`

$ ./bin/test -n 2
Thread 0
  #operations   : 172293
  #inserts   : 17540
  #removes   : 17539
Thread 1
  #operations   : 171544
  #inserts   : 17481
  #removes   : 17480
Duration      : 1000 (ms)
#txs     : 343837 (343837.000000 / s)
Expected size: 1025 Actual size: 1025

由上述結果得知 `ll_remove_search` 在 ==刪除、free node== 時沒有 LOCK 同時又有其他 thread 存取該 node 就會出錯

參考 [concurrent-ll/lock/list.c](https://github.com/jserv/concurrent-ll/blob/master/src/lock/list.c) 對 `ll.c` 中的 `ll_remove_search()` 及新加入的 `ll_search()` 進行修改如下:

int ll_remove_search(ll_t *list, int cond(void *, void *), void *val) {
    if (list == NULL)
        return -1;

    RWLOCK(l_write, list->m);
    
    if (list->hd == NULL) {
        RWUNLOCK(list->m);
        return -1;
    }

    ll_node_t *tmp = NULL;
    ll_node_t *prev = NULL;
    ll_node_t *node = list->hd;

    RWLOCK(l_write, node->m);
    
    if (cond(node->val, val)) { // list->hd->val == val
        tmp = node->nxt;
        if (tmp != NULL)
            RWLOCK(l_write, tmp->m);
        
        list->hd = tmp;
        (list->len)--;

        if (tmp != NULL)
            RWUNLOCK(tmp->m);
        RWUNLOCK(list->m);

        list->val_teardown(node->val);
        RWUNLOCK(node->m);
        pthread_rwlock_destroy(&(node->m));
        free(node);

        return list->len;
    }

    prev = node;
    node = node->nxt;
    
    if (node != NULL)
        RWLOCK(l_write, node->m);
    RWUNLOCK(list->m);

    while (node != NULL) {
        if (cond(node->val, val)) {
            tmp = node->nxt;
            if (tmp != NULL)
                RWLOCK(l_write, tmp->m);
            
            prev->nxt = tmp;

            if (tmp != NULL)
                RWUNLOCK(tmp->m);
            RWUNLOCK(prev->m);

            list->val_teardown(node->val);
            RWUNLOCK(node->m);
            pthread_rwlock_destroy(&(node->m));
            free(node);

            RWLOCK(l_write, list->m);
            (list->len)--;
            RWUNLOCK(list->m);

            return list->len;
        }

        RWUNLOCK(prev->m);
        prev = node;
        node = node->nxt;
        if (node != NULL)
            RWLOCK(l_write, node->m);
    }

    RWUNLOCK(prev->m);
    return -1;
}

註解掉 test.c 中的 ll_search

/* Wait on barrier */
    barrier_cross(d->barrier);
    // start the test
    while (*running) {

        // generate a value (node that rand_max is expected to be a power of 2)
        the_value = my_random(&seeds[0], &seeds[1], &seeds[2]) & rand_max;
        // generate the operation
        op = my_random(&seeds[0], &seeds[1], &seeds[2]) & 0xff;
        if (op < read_thresh) {
            // do a find operation
            // ll_search(the_list, num_equals, &the_value);
        } else if (last == -1) {
            // do a write operation
            if (ll_insert_last(the_list, &the_value) != -1) {
                d->num_insert++;
                last = 1;
            }
        } else {
            // do a delete operation
            if (ll_remove_search(the_list, num_equals, &the_value) != -1) {
                d->num_remove++;
                last = -1;
            }
        }
        d->num_operations++;
    }

增加 thread 數量會發生 ==Segmentation fault==

itlab@ITLabHP:~/Desktop/ll$ ./bin/test -n 2
Thread 0
  #operations   : 94120
  #inserts   : 9193
  #removes   : 9193
Thread 1
  #operations   : 95547
  #inserts   : 9589
  #removes   : 9588
Duration      : 1000 (ms)
#txs     : 189667 (189667.000000 / s)
Expected size: 1024 Actual size: 1024

itlab@ITLabHP:~/Desktop/ll$ ./bin/test -n 128
...
Thread 127
  #operations   : 2362
  #inserts   : 226
  #removes   : 226
Duration      : 1000 (ms)
#txs     : 288003 (288003.000000 / s)
Expected size: 1099 Actual size: 1099

itlab@ITLabHP:~/Desktop/ll$ ./bin/test -n 256
Segmentation fault (core dumped)

GDB 結果

itlab@ITLabHP:~/Desktop/ll$ gdb -q --args ./bin/test "-n 256"
Reading symbols from ./bin/test...done.
(gdb) r
Starting program: /home/itlab/Desktop/ll/bin/test -n\ 256
...

Thread 236 "test" received signal SIGSEGV, Segmentation fault.
[Switching to Thread 0x7ffd7c7a0700 (LWP 8921)]
0x0000000000401792 in num_equals (n=0x7ffff77eef20, m=0x7ffd7c79ff20) at src/test.c:103
103         return *(unsigned long *)n == *(unsigned long *)m;

(gdb) p *(unsigned long *)n
Cannot access memory at address 0x7ffff77eef20

(gdb) up 1
#1  0x00000000004014b4 in ll_remove_search (list=0x604010, cond=cond@entry=0x40178f <num_equals>, val=val@entry=0x7ffd7c79ff20) at src/ll.c:321
321             if (node->val != NULL && cond(node->val, val)) {

(gdb) info threads
  Id   Target Id         Frame
  1    Thread 0x7ffff7fda700 (LWP 8683) "test" 0x00007ffff78f1747 in munmap () at ../sysdeps/unix/syscall-template.S:84
* 236  Thread 0x7ffd7c7a0700 (LWP 8921) "test" 0x0000000000401792 in num_equals (n=0x7ffff77eef20, m=0x7ffd7c79ff20) at src/test.c:103

將所有 `struct ll_node` 中的 val 從 `void *` 改為 `int`

int num_equals(int n, int m) {
    return n == m;
}

執行結果

// start the test
while (*running) {

    // generate a value (node that rand_max is expected to be a power of 2)
    the_value = my_random(&seeds[0], &seeds[1], &seeds[2]) & rand_max;
    // generate the operation
    op = my_random(&seeds[0], &seeds[1], &seeds[2]) & 0xff;
    if (op < read_thresh) {
        // do a find operation
        ll_search(the_list, num_equals, the_value);
    } else if (last == -1) {
        // do a write operation
        ll_insert_last(the_list, the_value);
        d->num_insert++;
        last = 1;
    } else {
        // do a delete operation
        if (ll_remove_search(the_list, num_equals, the_value) != -1) {
            d->num_remove++;
            last = -1;
        }
    }
    d->num_operations++;
}

itlab@ITLabHP:~/Desktop/ll$ ./bin/test -n 1024 | tail -n7
Thread 1023
  #operations   : 4
  #inserts   : 1
  #removes   : 0
Duration      : 1000 (ms)
#txs     : 5579 (5579.000000 / s)
Expected size: 1628 Actual size: 1628

---

### 發現問題
用valgrind分析:

$ valgrind --track-origins=yes --leak-check=full ./test -n300
...
==3623== Thread 63:
==3623== Conditional jump or move depends on uninitialised value(s)
==3623==    at 0x109575: ll_remove_search (ll.c:328)
==3623==    by 0x109B9D: test (test.c:162)
==3623==    by 0x4E436DA: start_thread (pthread_create.c:463)
==3623==    by 0x517C88E: clone (clone.S:95)
==3623==  Uninitialised value was created by a stack allocation
==3623==    at 0x4E438B9: advise_stack_range (allocatestack.c:386)
==3623==    by 0x4E438B9: start_thread (pthread_create.c:552)
...

另一個輸出:

$ valgrind --track-origins=yes --leak-check=full ./test -n300
...
==2354== Thread 288:
==2354== Invalid read of size 8
==2354==    at 0x109862: num_equals (ll.c:499)
==2354==    by 0x109572: ll_remove_search (ll.c:328)
==2354==    by 0x109B9D: test (test.c:162)
==2354==    by 0x4E436DA: start_thread (pthread_create.c:463)
==2354==    by 0x517C88E: clone (clone.S:95)
==2354==  Address 0x604beb0 is not stack'd, malloc'd or (recently) free'd
...

Valgrind 好用的地方在於可以一步步看出是哪邊出了問題，於是我發現問題出在 ll_remove_search 裡面:

int ll_remove_search(ll_t *list, int cond(void *, void *), void *val)

...
    while (node->nxt != NULL) {                                                                                                   
        if (node->val != NULL) {        
            if(cond(node->val, val)){
                last->nxt = node->nxt;

                RWUNLOCK(node->m);
                free(node);
                RWUNLOCK(last->m);
                    
                //RWLOCK(l_write, list->m);
                (list->len)--;
                RWUNLOCK(list->m);
                return list->len;
            }   
        }   
...

因為 Valgrind 告訴我錯誤出在 if 那邊，但我一開始不知道是前面錯還後面錯所以分開寫，後來再偵錯一次發現是下面那的 if 才是造成 ==Conditional jump or move depends on uninitialised value(s)== 的原因那既然問題不是出在 node->val 那就是 val 了，於是又要追朔到最開始呼叫 ll_remove_search 的 test function 了。

void *test(void *data){
    ...
    unsigned long the_value;
    ...
        while (*running) {

        // generate a value (node that rand_max is expected to be a power of 2)
        the_value = my_random(&seeds[0], &seeds[1], &seeds[2]) & rand_max;
        // generate the operation
        op = my_random(&seeds[0], &seeds[1], &seeds[2]) & 0xff;
        if (op < read_thresh) {
            // do a find operation
            // ll_search(the_list, num_equals, &the_value);
        } else if (last == -1) {
            // do a write operation
            if (ll_insert_last(the_list, &the_value) != -1) {
                d->num_insert++;
                last = 1;
            }   
        } else {
            // do a delete operation
            if (ll_remove_search(the_list, num_equals, &the_value) != -1) {
                d->num_remove++;
                last = -1; 
            }   
        }   
        d->num_operations++;
    }   
    ...
}

於是我懷疑是第 3 行的 the_value 的 address 傳入 ll_remove_search 後裡面的值被釋放掉了，所以為了確保他一直存在所以我改 the_value 的前面加上 static

static unsigned long the_value;

然後就沒再出現 segmentation fault ，但為什麼 the_value 的值會被洗掉目前還不是很確定，但我用 valgrind 測試是沒有錯誤了。

$ valgrind --track-origins=yes --leak-check=full ./test -n300
...
==24167== Command: ./test -n300
==24167== 
Expected size: 1321 Actual size: 1321
==24167== 
==24167== LEAK SUMMARY:
==24167==    definitely lost: 0 bytes in 0 blocks
==24167==    indirectly lost: 0 bytes in 0 blocks
==24167==      possibly lost: 0 bytes in 0 blocks
==24167==    still reachable: 95,200 bytes in 1,322 blocks
==24167==         suppressed: 0 bytes in 0 blocks
==24167== Reachable blocks (those to which a pointer was found) are not shown.
==24167== To see them, rerun with: --leak-check=full --show-leak-kinds=all
==24167== 
==24167== For counts of detected and suppressed errors, rerun with: -v
==24167== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0) 
...

此外我也實際測試增加更多的thread也都可以順利的執行。我覺得會 debug 這麼久是因為一開始都是以為是 lock 沒有鎖好，造成 race condition 才會出錯。

### 發現 memory leak
在參考老師的 [concurrent-ll](https://github.com/jserv/concurrent-ll) 時，發現 lock 裡面 main.c 的 test 結束時沒有 free 用 posix_memalign 要的空間。
又是 valgrind 提醒了我:

==28738== 192 bytes in 3 blocks are definitely lost in loss record 2 of 4
==28738==    at 0x4C320A6: memalign (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==28738==    by 0x10994F: seed_rand (random.h:39)
==28738==    by 0x10994F: test (test.c:118)
==28738==    by 0x4E436DA: start_thread (pthread_create.c:463)
==28738==    by 0x517C88E: clone (clone.S:95)
==28738== 
==28738== LEAK SUMMARY:
==28738==    definitely lost: 192 bytes in 3 blocks
==28738==    indirectly lost: 0 bytes in 0 blocks
==28738==      possibly lost: 0 bytes in 0 blocks
==28738==    still reachable: 73,960 bytes in 1,027 blocks
==28738==         suppressed: 0 bytes in 0 blocks

* random.h 裡面

void *memalign(size_t size, size_t alignment)
{
    void *buffer;
    posix_memalign(&buffer, alignment, size);
    return buffer;
}
unsigned long *seed_rand()
{
    unsigned long *seeds;
    seeds = (unsigned long *)memalign(64, 64);  // allocate 64 byte and return a pointer to the allocated memory                  
    seeds[0] = getticks() % 123456789;          // which is mutiple of 64
    seeds[1] = getticks() % 362436069;
    seeds[2] = getticks() % 521288629;
    return seeds;
}

* main.c 裡面
在 test 結束時加上 free(seeds) 即可

void *test(void *data){
...
seeds = seed_rand();
...
free(seeds);
return NULL;
...
}

---

#### 測試ll_inserts_last和ll_search還有ll_insert_n功能：
將test.c中的`void *test(void *data) ` 改成如下：

while (*running) {

        // generate a value (node that rand_max is expected to be a power of 2)
        the_value = my_random(&seeds[0], &seeds[1], &seeds[2]) & rand_max;
        // generate the operation
        op = my_random(&seeds[0], &seeds[1], &seeds[2]) & 0xff;
        if (op < read_thresh) {
            // do a find operation
             ll_search(the_list, num_equals, &the_value);
             d->num_search++;

        } else if (last == -1) {
            // do a write operation
            if (ll_insert_last(the_list, &the_value) != -1) {
                d->num_insert++;
                last = 1;
            }
        } else {
            // do a delete operation
            //if (ll_remove_search(the_list, num_equals, &the_value) != -1) {
            //    d->num_remove++;
              //  last = -1;
         //   }
            if (ll_insert_n( the_list,&the_value,100 )!=-1){
              d->num_insert_n++;
                last = -1;

            }

        }

執行結果：

$ bin/test -n 300
...
Thread 295
  #operations   : 113
  #inserts   : 15
  #search  : 84
  #insert_n   : 14
Thread 296
  #operations   : 135
  #inserts   : 14
  #search  : 108
  #insert_n   : 13
Thread 297
  #operations   : 79
  #inserts   : 9
  #search  : 62
  #insert_n   : 8
Thread 298
  #operations   : 95
  #inserts   : 9
  #search  : 78
  #insert_n   : 8
Thread 299
  #operations   : 96
  #inserts   : 11
  #search  : 75
  #insert_n   : 10
Duration      : 1000 (ms)
#txs     : 36453 (36453.000000 / s)
Expected size: 4810 Actual size: 8381

但測試超過1024個thread便會產生`core dumped `

$ bin/test -n 1024
程式記憶體區段錯誤 (core dumped)

但在gdb的環境下測試**有時候**是不會有問題的：

...

Thread 1019
  #operations   : 14
  #inserts   : 2
  #search  : 11
  #insert_n   : 1
Thread 1020
  #operations   : 15
  #inserts   : 1
  #search  : 13
  #insert_n   : 1
Thread 1021
  #operations   : 15
  #inserts   : 2
  #search  : 12
  #insert_n   : 1
Thread 1022
[Thread 0x7ffdc65e4700 (LWP 4503) exited]
  #operations   : 10
  #inserts   : 0
  #search  : 10
  #insert_n   : 0
Thread 1023
  #operations   : 10
  #inserts   : 1
  #search  : 9
  #insert_n   : 0
Duration      : 1000 (ms)
#txs     : 21241 (21241.000000 / s)
Expected size: 3520 Actual size: 5400

但仍會出現問題：

Thread 167 "test" received signal SIGSEGV, Segmentation fault.
[Switching to Thread 0x7ffea3f9f700 (LWP 6139)]
0x0000000000401792 in num_equals (n=0x7fff9a7fbf20, m=0x7ffea3f9ef20) at src/test.c:104
104         return *(unsigned long *)n == *(unsigned long *)m;
(gdb)

利用valgrind發現，問題是出現在

 at 0x4C2DB8F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==8926==    by 0x4011A1: ll_new_node (ll.c:132)
==8926==    by 0x4012C3: ll_insert_n (ll.c:195)
==8926==    by 0x401381: ll_insert_last (ll.c:245)
==8926==    by 0x4019B2: test (test.c:136)
==8926==    by 0x4E416B9: start_thread (pthread_create.c:333)

也就是

 ll_node_t *new_node = ll_new_node(val);

...
 return ll_insert_n(list, val, list->len);
 
 if (ll_insert_last(the_list, (int *)the_value) == -1)
 

我覺得問題應該是出在val到底該用什麼型態才好，我嘗試將`val `改為`int * val `並且將test.c中的將每個函是的回傳值改為`ll_insert_last(the_list, (int *)the_value) `但還是出現了core dumped，看樣子`val `也不能是`int * `再試著改改看！

### 測試1萬個thread

$ bin/test -n10000
Thread 9999
  #operations   : 4
  #inserts   : 0
  #search  : 4
  #insert_n   : 0
Duration      : 1018 (ms)
#txs     : 80800 (79371.316306 / s)
Expected size: 12502 Actual size: 17543