2020q3 Homework1 (lab0)

contributed by < jonec76 >

tags: sysprog-2020

作業說明

開發環境

$ uname -a
Linux jonec76-Aspire-M7720 5.4.0-47-generic #51-Ubuntu SMP GNU/Linux

作業要求

實作基本功能，測驗分數達到 100 分，但是加入 make SANITIZE=1 之後只有 95 分 ( trace-17 仍錯)，以下是實作過程。

Jserv 老師上課說：q_reverse 還可以考慮如果 size=2 時，還需要做下面的 while-loop 嗎？

q_insert_head(queue_t *q, char *s)

• 錯誤過程
  • 複製字串出現亂碼
    ​​​​​​​​cmd> ih jkl
    ​​​​​​​​q = [jkl��� qwer���]
    

    原因出於 strncpy(newh->value, s, strlen(s))，在 strncpy man page 提到，以上程式碼會複製 src 的前 n bytes ，但這 n 個 bytes 不包含 null terminator，所以到了 dst 時該字串沒有 null terminator，就在字串的最後面產生亂碼。
    解決方法就是改成 strncpy(newh->value, s, strlen(s)+1) ，讓 strncpy 複製前 n 個 bytes，並且他會在 n+1 的位置放入 '\0'，也就是 null terminator。
• code
  ​​​​bool q_insert_head(queue_t *q, char *s)
  ​​​​{
  ​​​​    if (!q)
  ​​​​        return false;
  ​​​​    list_ele_t *newh = malloc(sizeof(list_ele_t));
  ​​​​    size_t len = strlen(s);
  ​​​​    /* TODO: What should you do if the q is NULL? */
  ​​​​    if (newh == NULL) {
  ​​​​        free(newh);
  ​​​​        return false;
  ​​​​    }
  ​​​​    char *value = malloc((len + 1) * sizeof(char));
  ​​​​    if (value == NULL) {
  ​​​​        free(newh);
  ​​​​        free(value);
  ​​​​        return false;
  ​​​​    }
  ​​​​    newh->value = value;
  ​​​​    strncpy(newh->value, s, len + 1);
  ​​​​    /* Don't forget to allocate space for the string and copy it */
  ​​​​    /* What if either call to malloc returns NULL? */
  ​​​​    q->size++;
  ​​​​    if (q->size == 1) {
  ​​​​        q->tail = newh;
  ​​​​    }
  ​​​​    newh->next = q->head;
  ​​​​    q->head = newh;
  ​​​​    return true;
  ​​​​}
  

q_free(queue_t *q)

• 錯誤過程

  ​​​​# Test of insert_head, insert_tail, size, and sort
  ​​​​ERROR: Freed queue, but 4 blocks are still allocated
  ​​​​---     trace-04-ops    0/6
  

  尚未實作 q_free() 之前，執行 make test 後會發現 trace-04-ops 給了以上的錯誤回應，經過觀察 trace-04-ops 知道它使得 list size 達到 6，但是只做了 4 次的 "rh" 刪除，意思就是說在 04-ops 測試結束時，q->head 仍然有 2 個 list_ele_t 並沒有被刪除。
  於是開始查找，這個 qtest 是如何得知還剩下多少 block？如何在程式結束（主動按下 ctrl+c）時執行的？

  在 main() 裏頭有個 function add_quit_helper(queue_quit) ，會在一開始將 queue_quit 加入 quit_helpers queue，queue_quit 就是當程式離開之前要執行的 function。當程式執行 quit 或者 ctrl+c（還不懂為什麼 ctrl+c 會進入 do_quit_cmd） 時，就會去執行do_quit_cmd，裡頭會執行 quit_helpers 就會執行到 queue_quit。
  在 queue_quit 裡面會執行 q_free() ，並且執行 allocation_check ，這個 function 會回傳曾經 allocated 多少個 block 。在 malloc 時會對變數 allocated_count+1 ，free 會 allocated_count-1，於是只要當 allocated_count 不為 0 時，那就表示還有 block 是沒有被 freed 的。

• code

  ​​​​void q_free(queue_t *q)
  ​​​​{
  ​​​​    if (!q)
  ​​​​        return;
  
  ​​​​    if (q->head == NULL) {
  ​​​​        free(q);
  ​​​​        return;
  ​​​​    }
  ​​​​    do {
  ​​​​        list_ele_t *tmp = q->head;
  ​​​​        char *tmp_value = tmp->value;
  ​​​​        q->head = q->head->next;
  ​​​​        free(tmp_value);
  ​​​​        free(tmp);
  ​​​​    } while (q->head != NULL);
  
  ​​​​    free(q);
  ​​​​}
  

q_sort()

Jserv 老師上課說：我們應該思考，當 list 的 size 應該大於多少時，才做 q_sort？因為做 linked-list 的 sort 成本過大

• 錯誤過程

  • Disallowed malloc
    最一開始的想法是把 q->head 這條 list 的所有 value 複製到一個新的陣列，並且使用 c library 提供的 qsort() 來完成，但是在 make test 時遇到 “Disallowed malloc” 錯誤。
    在 qtest.c 裏頭的 do_sort 看到了以下的程式碼

    ​​​​​​  set_noallocate_mode(true);
    ​​​​​​  if (exception_setup(true))
    ​​​​​​      q_sort(q);
    ​​​​​​  exception_cancel();
    ​​​​​​  set_noallocate_mode(false);
    

    於是再去看 set_noallocate_mode(true); 裏頭的程式碼，可以看到他是將 noallocate_mode 設為 true，再去找 noallocate_mode 用在哪裡，可以發現跟 void *test_malloc 有關。
    得到的結論是，當 qtest 在執行時，因為在 harness 可以找到 #define malloc test_malloc，也就是自行額外定義 malloc() ，當在程式裡面執行 malloc() 時，其實都是執行 void *test_malloc() ，而該 function 在分配一塊所需空間並且回傳 pointer 之前，會先做一連串的檢查，因為在 do_sort() 裡面有將 noallocate_mode 設定為 true，所以會進到 *test_malloc() 的

    ​​​​​​if (noallocate_mode) {
    ​​​​​​      report_event(MSG_FATAL, "Calls to malloc disallowed");
    ​​​​​​      return NULL;
    ​​​​​​}
    

    也就可以在該作業規定 "在 sort 時不能額外分配新的空間，只能用 q->head list 內部做 swap"。

  • Time limit exceeded

    • 在跑 qsort 時無法通過 trace-15-perf 、 trace-16-perf 的測驗，原因是因為實作的 ih 不夠有效率的儲存資料

      • trace-16-perf

        原本是透過 insertion sort 來實作 q->head 的排序，但是在這個測試 ih 大量的 data，於是想說用 q1 上課的 測驗題 提到的 optimizing merge-sort 去 sort，即通過此測驗。

        ​​​​​​​​​​​​list_ele_t *left, *right, *tail, *half;
        ​​​​​​​​​​​​left = right = tail = half = start;
        ​​​​​​​​​​​​while(tail){
        ​​​​​​​​​​​​    if(tail->next!=NULL )
        ​​​​​​​​​​​​        tail = tail->next;
        ​​​​​​​​​​​​    if(tail->next!=NULL )
        ​​​​​​​​​​​​        tail = tail->next;
        ​​​​​​​​​​​​    else break;
        ​​​​​​​​​​​​    half = half->next;
        ​​​​​​​​​​​​}
        ​​​​​​​​​​​​right = half->next;
        ​​​​​​​​​​​​half->next = NULL;
        ​​​​​​​​​​​​left = sort(left);
        ​​​​​​​​​​​​right = sort(right);
        

        原本的 merge-sort 會產生出 T(n) = T(n-1)+n 的時間複雜度，也就是 O(n^2)，於是在這邊將該程式改成 T(n) = 2T(n/2)+n 的方法，讓 merge-sort 的 left 以及 right 都是目前 size 的一半，並且去跑遞迴。

  • code

    ​​​​​​void q_sort(queue_t *q)
    ​​​​{
    ​​​​​​  if (!q)
    ​​​​​​      return;
    ​​​​​​  q->head = mergeSortList(q->head);
    ​​​​}
    
    ​​​​list_ele_t *mergeSortList(list_ele_t *start)
    ​​​​{
    ​​​​​​  if (!start || !start->next)
    ​​​​​​      return start;
    ​​​​​​  list_ele_t *left, *right, *tail, *half;
    ​​​​​​  left = tail = half = start;
    ​​​​​​  while (tail) {
    ​​​​​​      if (tail->next != NULL)
    ​​​​​​          tail = tail->next;
    ​​​​​​      if (tail->next != NULL)
    ​​​​​​          tail = tail->next;
    ​​​​​​      else
    ​​​​​​          break;
    ​​​​​​      half = half->next;
    ​​​​​​  }
    ​​​​​​  right = half->next;
    ​​​​​​  half->next = NULL;
    ​​​​​​  left = mergeSortList(left);
    ​​​​​​  right = mergeSortList(right);
    
    
    ​​​​​​  for (list_ele_t *merge = NULL; left || right;) {
    ​​​​​​      if (!right || (left && strcasecmp(left->value, right->value) <= 0)) {
    ​​​​​​          if (!merge) {
    ​​​​​​              start = merge = left;
    ​​​​​​          } else {
    ​​​​​​              merge->next = left;
    ​​​​​​              merge = merge->next;
    ​​​​​​          }
    ​​​​​​          left = left->next;
    ​​​​​​      } else {
    ​​​​​​          if (!merge) {
    ​​​​​​              start = merge = right;
    ​​​​​​          } else {
    ​​​​​​              merge->next = right;
    ​​​​​​              merge = merge->next;
    ​​​​​​          }
    ​​​​​​          right = right->next;
    ​​​​​​      }
    ​​​​​​  }
    ​​​​​​  return start;
    ​​​​}
    

q_remove_head(queue_t *q, char *sp, size_t bufsize)

• 錯誤過程

  • ERROR: Freed queue, but 3 blocks are still allocated

    當 free 了 list_ele_t *tmp 之後，卻沒有 free tmp->value 此 char pointer 指到的空間。

  • ERROR: copying of string in remove_head overflowed destination buffer.

    ​​​​​​​​if (i != string_length + STRINGPAD) {
    ​​​​​​​​    report(1,
    ​​​​​​​​           "ERROR: copying of string in remove_head overflowed "
    ​​​​​​​​           "destination buffer.");
    ​​​​​​​​    ok = false;
    ​​​​​​​​}
    ​​​​​​​​發現在執行 `trace-06-strings` 會有以上錯誤，去看了之後發現是在這邊出錯，`i=31` 但是 `string_length + STRINGPAD=30+1024`，這和 `trace-06-strings` 裡頭的 `option length 30` 有關係。
    ​​​​​​​​
    ​​​​​​​​options length=30，意思是最大呈現出字串的長度為 30，在該行設定完 length=30 的下一行，是 `rh meerkat_panda_squirrel_vulture` ，這行進來的 `argv[1]` 參數是 30 個字，而試著用 `gdb` 去找錯誤，發現在 `removes[31]` 的位置並不是 'X'，而是 "w"，也就是 pop 出來的字 "meerkat_panda_squirrel_vulture_wolf" 的第 31 個位置 w，於是修改成以下程式碼
    ​​​​​​​​```cpp
    ​​​​​​​​strncpy(sp, tmp->value, bufsize);
    ​​​​​​​​sp[bufsize-1] = '\0';
    

    使得複製最大只到 bufsize(含 null terminator) 的大小位置，因為這段複製的 src 有可能不包含 '\0'，所以根據 strncpy 並不會在 dst 的最後一個位置加入 '\0'，這部分需要自行處理。

  • Program received signal SIGSEGV, Segmentation fault.

    在 trace-09-robust 偵測出以下程式碼產生問題

    ​​​​​​​​sp[bufsize - 1] = '\0';
    

    於是去看了 trace-09-robust 裡頭的 op，發現 rhq 的設計，是希望單純移除 head 而不要複製，這邊會在 do_remove_head_quiet 的 function 傳入 bufsize=0 的參數，所以加入 if-condition 去偵測即可。

  • code

    ​​​​​​​​bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
    ​​​​​​​​{
    ​​​​​​​​    /* TODO: You need to fix up this code. */
    ​​​​​​​​    /* TODO: Remove the above comment when you are about to implement. */
    ​​​​​​​​    if (q == NULL || q->size == 0)
    ​​​​​​​​        return false;
    ​​​​​​​​    q->size--;
    ​​​​​​​​    list_ele_t *tmp = q->head;
    ​​​​​​​​    if (bufsize != 0) {
    ​​​​​​​​        strncpy(sp, tmp->value, bufsize);
    ​​​​​​​​        sp[bufsize - 1] = '\0';
    ​​​​​​​​    }
    ​​​​​​​​    q->head = q->head->next;
    ​​​​​​​​    free(tmp->value);
    ​​​​​​​​    free(tmp);
    ​​​​​​​​    return true;
    ​​​​​​​​}
    

queue_t *q_new()

• 錯誤過程

  • Program received signal SIGSEGV, Segmentation fault.
    在 trace-10-malloc 偵測出以下程式碼產生問題

    ​​​​​​​​queue_t *q = malloc(sizeof(queue_t));
    ​​​​​​​​q->head = NULL;
    

    於是去觀察 "option malloc 50" 裡頭的參數，這項 op 會使得 fail_probability=50（初始值是 0 ），也就是他會有 0.5 的機率會產生 malloc 失敗（在 test_malloc 會回傳 NULL 給 pointer），加入 NULL check 即可。

• code
  ​​​​queue_t *q_new()
  ​​​​{
  ​​​​    queue_t *q = malloc(sizeof(queue_t));
  ​​​​    /* TODO: What if malloc returned NULL? */
  ​​​​    if (!q)
  ​​​​        return q;
  ​​​​    q->head = NULL;
  ​​​​    q->size = 0;
  ​​​​    return q;
  ​​​​}
  

其他錯誤

• 使用 make SANITIZER=1 後再跑 make test，會在 trace-17 出現以下的錯誤，評量分數只有 95，仍在找尋解決辦法。

  126215ERROR: AddressSanitizer: global-buffer-overflow on address 0x5647678ad960 at pc 0x56476789d9be bp 0x7fff5b8849d0 sp 0x7fff5b8849c0

• git commit fail to pass static analysis

  偵測到以下程式碼會有 memory leak 的問題

  ​​​​newh->value = malloc((len + 1) * sizeof(char));
  ​​​​if (newh->value == NULL)
  ​​​​    return false;
  

  參考了 simple-rules-to-avoid-memory-leaks-in-c 裡面提到的，在 malloc 一塊記憶體給一變數後，如果沒有 free() 該空間，則會發生 memory leak 的問題。另外，也有提到在 malloc 的時候，應將記憶體空間 malloc 給一個 char 變數，再透過 assign 的方式讓 pointer(這邊是 newh->value) 指到該空間作操作。
  於是將程式碼改成

  ​​​​char *value = malloc((len + 1) * sizeof(char));
  ​​​​if (value == NULL) {
  ​​​​    free(newh);
  ​​​​    free(value);
  ​​​​    return false;
  ​​​​}
  ​​​​newh->value = value;
  

研讀論文 Dude, is my code constant time?，解釋本程式的 “simulation” 模式是如何透過以實驗而非理論分析，達到驗證時間複雜度，需要解釋 Student’s t-distribution 及程式實作的原理;

• 說明

  在 trace-17 檔案裡頭可以看到會使用 simulation mode 去測試函式 insert_tail 以及 q_size。
  以 is_insert_tail_const 為例，裡頭可以看到 doit 函式做了一連串的運算並把時間記錄下來，程式碼如下

  ​​​​prepare_inputs(input_data, classes);
  ​​​​measure(before_ticks, after_ticks, input_data, mode);
  ​​​​differentiate(exec_times, before_ticks, after_ticks);
  ​​​​update_statistics(exec_times, classes);
  ​​​​bool ret = report();
  

  prepare_inputs 裡頭的 randombytes(input_data, number_measurements * chunk_size); 能夠使 input_data 的每個 element 獲得 0~255 的亂數( 參考 stack )，這部分是透過讀取 fd = open("/dev/urandom", O_RDONLY); 將亂數後放入 input_data，另外，也隨機產生 classes (0~1) 以及 random_string。

  在 measure 時，將會執行 insert_tail 若干次，每次插入的資料是 random_string * insert_tail[i] 筆，並且將執行前後的 cpucycles
  記錄下來，並在 differentiate 獲得執行時間。

  update_staticstics 是將執行時間隨機的加入 class0 或者 class1 裡面，並且更新該 class 的平均數、m2(變異數)，最後當計算出 t-value 大於 10 時，則會回報 "ERROR: Probably not constant time"。其原理是使用 Welch t-testing 檢測兩個 class 的分佈相近程度，若該函式執行時間是常數時間的話，則 input 不管大小如何都不會影響其執行時間。

• 如何產生隨機的 input_data

  ​​​​for (size_t i = 0; i < number_measurements; i++) {
  ​​​​    classes[i] = randombit();
  ​​​​    if (classes[i] == 0)
  ​​​​        *(uint16_t *) (input_data + i * chunk_size) = 0x00;
  ​​​​}
  

  classes[i] 會隨機的得到 0 或 1 的值，接著若是 0 的話，會將 0x00 放入對應的位置。原先的 input_data 是 uint8_t，也就是每格大小為 1 byte，但這邊轉型成 input_data + i * chunk_size 指向的是一個 2 bytes 的大小位置，依據 little endian 規則，0x00 會從最低位開始放（目前指標指導的位置），接著後面就是補 0。
  接著看 measure 裡頭的程式碼

  ​​​​dut_insert_head(
  ​​​​    get_random_string(),
  ​​​​    *(uint16_t *) (input_data + i * chunk_size) % 10000);
  ​​​​)
  

  可以看到這邊取值時，是取出指標目前指到的 2 bytes 的值出來，所以數字範圍才會是從 0 到 65535。
  接著，思考同學的 pr commit:master (#42)，原先的做法是將 chunk 的前面 2 個 bytes 清為 0，新的 pr 的做法是將整個 chunk 都清空，這樣的優點在目前的隨機取值似乎無法體現出來，如下

  ​​​​*(uint16_t *) (input_data + i * chunk_size) % 10000);
  

  但若是將 *(uint16_t *) 改成 *(uint32_t *)，也就是希望能夠使亂數的範圍更大（0~

  $2^{32}$）時，因為每次取出 4 bytes，此時若是舊的方法則會有未清空的部分（因為舊的方法只清空每個 chunk 的起始 2 bytes），是此 pr 的一項改進。

• 更改 update_statistics 計算方式

  • 這邊其實是有疑問的，(發現自己想法錯誤)。舊的 code 如下

    ​​​​​​​​// t_push(t_ctx *ctx, double x, uint8_t class)
    
    ​​​​​​​​double delta = x - ctx->mean[class];
    ​​​​​​​​ctx->mean[class] = ctx->mean[class] + delta / ctx->n[class];
    ​​​​​​​​ctx->m2[class] = ctx->m2[class] + delta * (x - ctx->mean[class]);
    

    每次會傳入一個執行時間 x，並且將此 x 去更新對應的 class 的 mean，然而，計算標準差的公式中的平均值，應該是整個 class 的平均值，而不是像此 "動態" 調整過後的平均值。

    但是看了同學的筆記 (oscardshiang) 以及 welfords-method 才知道這樣計算方式的優點，是能夠減少 overflow 的風險，以及能以 single pass 將 data 遍歷一遍即可得出平均值以及標準差。
    算平均值的部分較為直觀，故以下僅摘錄計算標準差的部分，在 t_push 裡頭能看到

    ​​​​​​​​double delta = x - ctx->mean[class];
    ​​​​​​​​ctx->m2[class] = ctx->m2[class] + delta * (x - ctx->mean[class]);
    

    上述的 code 若做了移項，即可知道 delta * (x - ctx->mean[class]) 化成數學式如下

    $\sum _{k=1}^N(x_i-{\bar{x}}_N{)}^2-\sum _{k=1}^{N-1}(x_i-{\bar{x}}_{N-1}{)}^2$

    也就是程式碼的

    $m{2}_N-m{2}_{N-1}$，接著經過一連串的化減（可參考 welfords-method）才得到下面式子
    $(x_n-{\bar{m}}_{n-1})(x_n-{\bar{m}}_n)$

    其中

    ${\bar{m}}_n$ 表示算到第 n 個值的 mean 平均數，也就是 code 中的 delta * (x - ctx->mean[class])

TODO

• 運用 Valgrind 排除 qtest 實作的記憶體錯誤，並透過 Massif 視覺化 “simulation” 過程中的記憶體使用量，需要設計對應的實驗
• 挑戰題