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} - {\overset{―}{x}}_{N})^{2} - \sum_{k = 1}^{N - 1} (x_{i} - {\overset{―}{x}}_{N - 1})^{2}$
  
  也就是程式碼的
  $m 2_{N} - m 2_{N - 1}$ ，接著經過一連串的化減（可參考 welfords-method）才得到下面式子
  
  $(x_{n} - {\overset{―}{m}}_{n - 1}) (x_{n} - {\overset{―}{m}}_{n})$
  
  其中
  ${\overset{―}{m}}_{n}$ 表示算到第 n 個值的 mean 平均數，也就是 code 中的 delta * (x - ctx->mean[class])

TODO

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

2020q3 Homework1 (lab0)

tags: sysprog-2020

開發環境

作業要求

q_insert_head(queue_t *q, char *s)

q_free(queue_t *q)

q_sort()

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

queue_t *q_new()

其他錯誤

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

TODO

Read more

Untitled

2020_OS_Fall_HW2: ETL process

深度學習系統與平行計算技術

ML 學習

tags: `sysprog-2020`

`q_insert_head(queue_t q, char s)`

`q_free(queue_t *q)`

`q_sort()`

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

`queue_t *q_new()`

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