# 2020q1 Homework1 (lab0)
Contributed by < [AdrianHuang](https://github.com/AdrianHuang/lab0-c) >

###### tags: `linux2020`

## 論文〈[Dude, is my code constant time?](https://eprint.iacr.org/2016/1123.pdf)〉重點
此論文提出一套量測方法與對應原始碼 [dudect](https://github.com/oreparaz/dudect)，用以量測程式執行時間是否能在常數時間 $O(1)$ 完成，其特點如下
- 不侷限某特定 CPU 硬體平台，此特點相當重要。該論文也提及其它相關研究，往往只能在某特定 CPU 架構才能量測 (因為需要更新 CPU 的 [microcode](https://en.wikipedia.org/wiki/Microcode))。
- 該論文使用 [Student's t-distribution](https://en.wikipedia.org/wiki/Student%27s_t-distribution) (使用情境: 取樣大小不大且[標準差](https://en.wikipedia.org/wiki/Standard_deviation)無法得知的情況下) 之 [Student's t-test](https://en.wikipedia.org/wiki/Student%27s_t-test) 方法
> [Welch's t-test](https://en.wikipedia.org/wiki/Welch%27s_t-test)。Welch's t-test 用來測試兩組取樣資料之平均值是否相同，藉此判斷所撰寫的程式碼能否在常數時間 $O(1)$ 完成。

### 實作細節 (比對lab0 Github - [dudect](https://github.com/AdrianHuang/lab0-c/tree/master/dudect)程式碼)
`lab0-c` 的 Welch's test 測試項目有兩個:
* is_insert_tail_const(): 用來測試將字串加到 Queue 尾端的執行時間是否能在常數時間完成。
* is_size_const(): 用來測試取得 Queue 大小時間是否能在常數時間完成。

每個測項又細分兩個階段:
* Pre-processing: 主要測量待測物 (給定的程式碼) 的執行時間 (CPU cycle)，其步驟如下:
* 兩種產生 Queue 方式 (即對照 Welch's Test 所需兩組取樣資料):
* Queue 大小 = 0 ---> 論文提及的`fix class`
* Queue 大小 = n (隨機產生)，並插入 n 個相同的隨機字串至 Queue 開頭 (字串長度=7bytes, 加上結束字元` '\0'` 則為 8bytes) ---> 論文提及的`random class`
* 執行待測物 (`is_insert_tail_const()` 或 `is_size_const()`)，並記錄執行時間 (CPU cycles)

* Statistical test: 將所記錄的CPU執行時間 (CPU cycles) 套用如下 [Welch's test](https://en.wikipedia.org/wiki/Welch%27s_t-test) 公式，用以計算t value。可對照 `lab0-c` 原始碼的 [t_push()](https://github.com/AdrianHuang/lab0-c/blob/master/dudect/ttest.c#L19) 與 [t_compute()](https://github.com/AdrianHuang/lab0-c/blob/master/dudect/ttest.c#L31)。其所計算得出 t value 就可用來判斷測試項目是否在常數時間完成。
$$
t = \frac{\bar{X_0} - \bar{X_1}}{\sqrt{\frac{s^2_1}{N_1} + \frac{s^2_2}{N_2}}}
$$
> $t$ 越接近 0 代表兩組數據的差異越小

### 實驗
執行底下指令及輸出結果:

$ ./qtest -v 3 -f traces/trace-17-complexity.cmd
cmd> # Test if q_insert_tail and q_size is constant time complexity
cmd> option simulation 1
cmd> it
Probably constant time
cmd> size
ERROR: Probably not constant time
cmd> option simulation 0

輸出結果顯示底下`q_size`， 無法在常數時間執行完畢。

/*
 * Return number of elements in queue.
 * Return 0 if q is NULL or empty
 */
int q_size(queue_t *q)
{
    return q ? q->size : 0;
}

**觀察一:**
觀察 `is_insert_tail_const()` 與 `is_size_const()` 執行後的相關數據之前，先解釋底下結構意義

typedef struct {
    double mean[2];
    double m2[2];
    double n[2];
} t_ctx;

means[2]: 對應t value公式$\bar{X_1}$與$\bar{X_2}$。也就是，兩組取樣數據之平均值。
m2[2]: 對應t value公式$s_{1}^2$與$s_{2}^2$ ([sample standard deviation](https://en.wikipedia.org/wiki/Standard_deviation))，但還沒除以`n - 1`。
n[2]: 兩組取樣數據個數。

~~比較Table 1與Table 2的mean: 發現約相差10倍。~~
~~比較Table 1與Table 2的m2: fix class相差18倍，random class相差683倍。~~

Table 3 分別列出 `is_insert_tail_const()` 與 `is_size_cont()` 的 t value 值 (參考 Table 1 與 Table 2 相關數據)。該值如果小於10 (論文設定該值為 `4.5`，程式碼則設為 `10`)，則代表能在常數時間執行完畢，也就是兩組數據 (Fix class 與 Random class) 的分佈是相近的。反之，則無法在常數時間執行完畢，也就是兩組數據的分佈不同。

乍看之下，很難理解為何 `q_size()` 被判斷無法在常數時間完成。

| class | number (t_ctx.n) | mean (t_ctx.mean) | m2 (t_ctx.m2) |
| ------------ | ---------------- | ----------------- | ---------------- |
| Fix Class | 5013 | 276.753242 | 15730275.759824 |
| Random Class | 4997 | 291.998399 | 342294719.987193 |
> $\Uparrow$ **Table 1. `is_insert_tail_const()` 執行 `simulation` 選項數據**

| class | number (t_ctx.n)| mean (t_ctx.mean) | m2 (t_ctx.m2) |
| ------------ | --- | ----------------- | ------------- |
| Fix Class | 5012 | 32.249800 | 870039.249800 |
| Random Class | 4998 | 27.497399 | 501169.466186 |
> $\Uparrow$ **Table 2. `is_size_const()` 執行 `simulation` 選項數據**

| function | fabs (t value) |
| -------- | -------- |
| is_insert_tail_const() | 4.03 |
| is_size_const() | 20.32 |
> $\Uparrow$ **Table 3. t value**

**觀察二:**
重新讀論文並對照dudect與lab0 dudect程式碼，發現有些不同之處:
* 該論文提到在pre-processing階段，會依據設定的百分點(percentile)移除測量數據，對照lab0 dudect沒有找到相關程式碼。還需要一些時間研究，可參考[這段程式碼](https://github.com/oreparaz/dudect/blob/master/src/fixture.c#L57)。 TBD

:::warning
已知現有實作程式碼和論文有出入
:notes: jserv
:::
> 當初在移植到 lab0-c 的時候我不能理解原作者的程式碼，原本要自己重寫一個，後來忘記加上去了 Orz。
>
> 這個問題只會在某些電腦出現，推測可能是測量時間波動較大導致，可能需要請你幫忙看看在已確定 constant time 的情況下 random/fixed class 的狀況。
> 如果是這樣的話，我們就需要按照論文中提到的按照百分點把那些傾向較長時間的結果移除。
> [name=afcidk]

**觀察三:**
測試兩台機器，並觀察其執行CPU cycles分佈，系統配置如下:

| Machine | CPU | OS | Kernel | GCC Version |
| ------- | ---- | --- | --- | --- |
| 2-socket Grantley Server (Broadwell Microarchtecture) | Intel(R) Xeon(R) CPU E5-2695 v4 @ 2.10GHz - 72 cores (HT enabled) | Ubuntu 18.04.3 LTS | 5.3.0-42-generic | 7.5.0 |
| Sony VAIO VPCEA16FW | Intel(R) Core(TM) i5-520M @ 2.40GHz - 4 cores (HT enabled) | Ubuntu 18.04.3 LTS | 5.3.0-42-generic | 7.5.0 |
**註: 觀察一測試數據基於2-socket Grantley Server**

下圖Figure 1顯示在Grantley Server上，跑了'size' simulation測試所得出q_size()數據 (橫軸: 執行q_size所需的CPU Cycles，縱軸: 某特定CPU cycles總次數)。其總結如下:
* CPU Cycles=24時，其總次數有很大差異 (fix class: 2701, random class: 3969)
* CPU Cycles=32-40區間，其總次數也有明顯差異。

由於fix class與random class分佈圖有明顯的差異，其計算所得出之 t value > 10 (此次 t value = 23.48)，所以被判定q_size不能在$O(1)$完成。

> $\Uparrow$ **Figure 1. [Broadwell] Fix Class vs Random Class - Test for q_size()**

下圖Figure 2顯示在Sony VAIO筆電量測數據。其 Fix Class 與 Random Class 分佈相近，因此被判定可在$O(1)$完成。此次 t value = 8.37。
> $\Uparrow$ **Figure 2. [Sony VAIO] Fix Class vs Random Class - Test for q_size()**

看完 dudect 相關 percentile 程式碼後，並將之整合進 [lab0-c](https://github.com/AdrianHuang/lab0-c/commit/aca7f425fc756240cfda3199765f5394649af49c) 之後，其'it'與'size'測試結果皆為`O(1)`。

$ ./qtest -f traces/trace-17-complexity.cmd
cmd> # Test if q_insert_tail and q_size is constant time complexity
cmd> option simulation 1
cmd> it
Probably constant time
cmd> size
Probably constant time
cmd> option simulation 0
Freeing queue

Percentile 概念將處理器執行時間分為三類:
1. first order uncropped: 所有的處理器執行時間都會記錄在這裡。
2. cropped: 定義100個 t_ctx 結構與 percentiles 陣列，並依據所記錄的處理器執行時間，計算出每個 percentiles 陣列元素所對應的處理器執行時間。如果其處理器時間小於該 percentiles 陣列元素的內容，則將此處理器時間加到對應 t_ctx，詳見[程式碼](https://github.com/oreparaz/dudect/blob/master/src/fixture.c#L96)。
3. second order uncropped: first order uncropped 的 fix class 個數如果超過 10000，則計算出此次處理器執行時間與對應的 fix class 或 random class 平均值之差異，並將此差異的平方加到 second order uncropped，詳見[程式碼](https://github.com/oreparaz/dudect/blob/master/src/fixture.c#L104)。

最後，從這三類計算出最大的 t value ，用以判斷是否能在`O(1)`執行完畢。然而，第二類與第三類要被列入計算要看其對應的 fix class 取樣個數是否有超過`enough_measurements` (該定義值為10000)。所以，`lab0-c`不會將第二類與第三類列入計算 (因為只做10000次取樣，並分給 fix class 與 random class)，也就是只計算第一類。

如上述，為何只計算第一類`it`與`size` 就能通過測試 (這個原本lab0-c實做一樣)? 再次檢視程式碼並做許多實驗發現，只要把取樣後的處理器執行時間進行排序，就能通過測試，詳見[程式碼](https://github.com/AdrianHuang/lab0-c/commit/52fcbd12400cb3544692a10665aa55747e961e24)。其 Fix class 與 Random class 分佈圖如Figure 3所示 (兩個分佈圖非常貼近)。

此發現還沒找到真正的原因。可以確定的是，有排序與無排序的處理器執行時間不影響 t value計算。

> $\Uparrow$ **Figure 3. [Broadwell] Fix Class vs Random Class with sorted CPU Cycles - Test for q_size()**
>

另外，從perf測試結果沒發現任何線索，如下所示:

# Note: The result is based on the original lab0-c (the macro 'test_tries' is set to 1)
$ cat traces/trace-17-complexity-size.cmd
# Test if q_insert_tail and q_size is constant time complexity
option simulation 1
size
option simulation 0
$ perf stat ./qtest -f traces/trace-17-complexity-size.cmd
cmd> # Test if q_insert_tail and q_size is constant time complexity
cmd> option simulation 1
cmd> size
ERROR: Probably not constant time
cmd> option simulation 0

 Performance counter stats for './qtest -f traces/trace-17-complexity-size.cmd':

          3,955.52 msec task-clock                #    1.000 CPUs utilized      
                 8      context-switches          #    0.002 K/sec              
                 0      cpu-migrations            #    0.000 K/sec              
               384      page-faults               #    0.097 K/sec              
     8,306,536,077      cycles                    #    2.100 GHz                
    19,039,885,216      instructions              #    2.29  insn per cycle     
     4,525,379,927      branches                  # 1144.067 M/sec              
        16,718,058      branch-misses             #    0.37% of all branches    

       3.955880745 seconds time elapsed

       3.927826000 seconds user
       0.027998000 seconds sys

# Note: The result is based on the original lab0-c + this commit: https://github.com/AdrianHuang/lab0-c/commit/52fcbd12400cb3544692a10665aa55747e961e24
$ perf stat ./qtest -f traces/trace-17-complexity-size.cmd
cmd> # Test if q_insert_tail and q_size is constant time complexity
cmd> option simulation 1
cmd> size
Probably constant time
cmd> option simulation 0
Freeing queue

 Performance counter stats for './qtest -f traces/trace-17-complexity-size.cmd':

          3,988.70 msec task-clock                #    1.000 CPUs utilized      
                10      context-switches          #    0.003 K/sec              
                 0      cpu-migrations            #    0.000 K/sec              
             3,268      page-faults               #    0.819 K/sec              
     8,376,216,682      cycles                    #    2.100 GHz                
    19,353,128,561      instructions              #    2.31  insn per cycle     
     4,593,320,800      branches                  # 1151.583 M/sec              
        17,119,556      branch-misses             #    0.37% of all branches    

       3.989095454 seconds time elapsed

       3.961015000 seconds user
       0.028007000 seconds sys

**觀察四: 使用不同GCC版本測試**
實驗發現用gcc version 8.3.0編譯版本 (不加[此patch](https://github.com/AdrianHuang/lab0-c/commit/52fcbd12400cb3544692a10665aa55747e961e24))，'size'都能通過測試，但'it'偶爾無法通過測試，如下所示:

$ readelf -p .comment qtest-8.3.0

String dump of section '.comment':
  [     0]  GCC: (Ubuntu 8.3.0-26ubuntu1~18.04) 8.3.0

$ ./qtest-8.3.0 -f traces/trace-17-complexity.cmd
cmd> # Test if q_insert_tail and q_size is constant time complexity
cmd> option simulation 1
cmd> it
ERROR: Probably not constant time
cmd> size
Probably constant time
cmd> option simulation 0

用objdump比對gcc 7.5.0與gcc 8.3.0編譯出來的ELF。其中，快速比對q_size差異，如下所示:

只有最後 return 指令不一樣。其中，repz retq可參考此[網頁](http://repzret.org/p/repzret/)解說。

$ diff qtest-q_size-7.5.0.disasm qtest-q_size-8.3.0.disasm
1,6c1,6
< 00000000000050c6 <q_size>:
<     50c6:   b8 00 00 00 00          mov    $0x0,%eax
<     50cb:   48 85 ff                test   %rdi,%rdi
<     50ce:   74 03                   je     50d3 <q_size+0xd>
<     50d0:   8b 47 10                mov    0x10(%rdi),%eax
<     50d3:   f3 c3                   repz retq
---
> 00000000000050a5 <q_size>:
>     50a5:   b8 00 00 00 00          mov    $0x0,%eax
>     50aa:   48 85 ff                test   %rdi,%rdi
>     50ad:   74 03                   je     50b2 <q_size+0xd>
>     50af:   8b 47 10                mov    0x10(%rdi),%eax
>     50b2:   c3                      retq

為了讓 gcc 7.5.0 編譯出來 q_size()的 return 指令為 'retq'，將 q_size 改成:

/*
 * Return number of elements in queue.
 * Return 0 if q is NULL or empty
 */
int q_size(queue_t *q)
{
    return q->size;
}

$ readelf -p  .comment qtest

String dump of section '.comment':
  [     0]  GCC: (Ubuntu 7.5.0-3ubuntu1~18.04) 7.5.0

$ objdump -D qtest | less
...
00000000000050c6 <q_size>:
    50c6:       8b 47 10                mov    0x10(%rdi),%eax
    50c9:       c3                      retq
...

其測試結果依然報錯:

$ ./qtest -f traces/trace-17-complexity-size.cmd
cmd> # Test if q_insert_tail and q_size is constant time complexity
cmd> option simulation 1
cmd> size
ERROR: Probably not constant time
cmd> option simulation 0

## Reference
* [Welch's t-test](https://en.wikipedia.org/wiki/Welch%27s_t-test)
* [Student's t-test](https://www.youtube.com/watch?v=pTmLQvMM-1M&t=192s)