2023q1 Homework1 (lab0)

contributed by < ItisCaleb >

開發環境

6.1.12-arch1-1

$ gcc --version                                              
gcc (GCC) 12.2.1 20230201
Copyright (C) 2022 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

$ lscpu                                                      
Architecture:            x86_64
  CPU op-mode(s):        32-bit, 64-bit
  Address sizes:         39 bits physical, 48 bits virtual
  Byte Order:            Little Endian
CPU(s):                  12
  On-line CPU(s) list:   0-11
Vendor ID:               GenuineIntel
  Model name:            12th Gen Intel(R) Core(TM) i5-12400
    CPU family:          6
    Model:               151
    Thread(s) per core:  2
    Core(s) per socket:  6
    Socket(s):           1
    Stepping:            2
    CPU(s) scaling MHz:  19%
    CPU max MHz:         5600.0000
    CPU min MHz:         800.0000
    BogoMIPS:            4993.00

開發過程

目前在修正 dudect 後，自動測試程式可以得到 100 分
但程式碼還需要去進行改進

q_new

依循作業書寫規範，中英文間用一個半形空白字元區隔。

jserv

呼叫 malloc 來配置 list_head 的記憶體空間
並且使用 list.h 裡的 INIT_LIST_HEAD 初始化新的 list

struct list_head *q_new()
{
    struct list_head *q = malloc(sizeof(struct list_head));
    if (!q)
        return NULL;
    INIT_LIST_HEAD(q);
    return q;
}

q_free

使用 list_for_each_entry_safe 來走訪 list 裡的每個元素
並且一一釋放記憶體空間
最後將l ist 的 head 所佔用的空間釋放

void q_free(struct list_head *l)
{
    if (!l)
        return;
    element_t *ele, *safe;
    list_for_each_entry_safe (ele, safe, l, list)
        q_release_element(ele);
    free(l);
}

q_insert_head/q_insert_tail

兩個函式的實作幾乎相同，所以 q_insert_tail 直接呼叫 q_insert_head
先用 malloc 分配一個 element_t 的記憶體空間
並且使用 strdup 來複製字串 s 到 ele->value 裡
最後使用 list_add 來將 ele 加入到 list 的頭部/尾端

bool q_insert_head(struct list_head *head, char *s)
{
    if (!head)
        return false;
    element_t *ele = malloc(sizeof(element_t));
    if (!ele)
        return false;
    ele->value = strdup(s);
    if (!ele->value) {
        free(ele);
        return false;
    }
    list_add(&ele->list, head);
    return true;
}

bool q_insert_tail(struct list_head *head, char *s)
{
    return q_insert_head(head->prev, s);
}

commit 2a2a0fa

q_remove_head/q_remove_tail

兩個函式的實作幾乎相同，所以 q_remove_tail 直接呼叫 q_remove_head
首先使用 list_entry / list_last_entry 來獲得list頭部
接著使用 list_del 來使 ele->value 從list中移除
然後先比較 ele->value 及 bufsize 的大小，將較小的作為字串複製的長度
並透過 strncpy 將 ele->value 複製到 sp 上
最後將字串結尾改成\0

element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head))
        return NULL;
    element_t *ele = list_entry(head->next, element_t, list);
    list_del(&ele->list);
    if (sp) {
        size_t len = strlen(ele->value);
        len = len < bufsize - 1 ? len : bufsize - 1;
        strncpy(sp, ele->value, len);
        *(sp + len) = '\0';
    }
    return ele;
}

element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
    return q_remove_head(head->prev->prev, sp, bufsize);
}

commit 2a2a0fa

q_size

使用 list_for_each 走訪 list 的每個節點
並將次數累加到 len 上後回傳

int q_size(struct list_head *head)
{
    if (head == NULL)
        return 0;
    int len = 0;
    struct list_head *li;
    list_for_each (li, head) {
        len++;
    }
    return len;
}

q_delete_mid

先透過 q_size 取得 list 的長度，除 2 後獲得中間的位置
之後走訪 list 的節點直到到達中間的位置
接著把中間的節點從 list 中移除
最後透過 list_entry 取得節點的元素並且釋放元素所佔的記憶體空間

本來是走訪 list 的元素
後來想了一下發現只要走訪到中間後再取得元素就好

bool q_delete_mid(struct list_head *head)
{
    // https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/
    if (!head || list_empty(head))
        return false;
    int m_pos = q_size(head) / 2, pos = 0;
    struct list_head *li, *safe;
    list_for_each_safe (li, safe, head)
        if (m_pos == pos++) {
            list_del(li);
            q_release_element(list_entry(li, element_t, list));
            return true;
        }
    return false;
}

用快慢指標去重新實作

bool q_delete_mid(struct list_head *head)
{
    // https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/
    if (!head || list_empty(head))
        return false;
    struct list_head *slow = head->next, *fast;
    for (fast = head->next; fast != head && fast->next != head;
         fast = fast->next->next) {
        slow = slow->next;
    }
    list_del(slow);
    q_release_element(list_entry(slow, element_t, list));
    return true;
}

q_delete_dup

走訪 list 的每個節點
並且如果下一個節點的內容跟現在的重複便持續刪除，接著將 flag 設成 true
如果 flag 為 true 則把現在的節點刪除

bool q_delete_dup(struct list_head *head)
{
    // https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
    if (!head || list_empty(head))
        return false;
    struct list_head *li, *safe;
    list_for_each_safe (li, safe, head) {
        element_t *ele = list_entry(li, element_t, list);
        struct list_head *ptr = li->next;
        bool flag = false;
        while (ptr != head &&
               strcmp(ele->value, list_entry(ptr, element_t, list)->value) ==
                   0) {
            list_del(ptr);
            q_release_element(list_entry(ptr, element_t, list));
            ptr = li->next;
            flag = true;
        }
        safe = li->next;
        if (flag) {
            list_del(li);
            q_release_element(list_entry(li, element_t, list));
        }
    }
    return true;
}

q_swap

走訪每一個節點並計數
如果 i 為奇數則把現在的節點移除
並以往前兩個的節點作為 head 重新加入 list
以此來達成交換

void q_swap(struct list_head *head)
{
    // https://leetcode.com/problems/swap-nodes-in-pairs/
    if (!head)
        return;
    struct list_head *li, *safe;
    int i = 0;
    list_for_each_safe (li, safe, head) {
        if (i & 1) {
            list_del(li);
            list_add(li, li->prev->prev);
        }
        i++;
    }
}

q_reverse

走訪每一個節點直到 list 的尾端的節點
並且把現在的節點從 list 移除後以原本尾端的節點作為 head 重新加入 list

void q_reverse(struct list_head *head)
{
    if (!head)
        return;
    struct list_head *li, *safe, *last = head->prev;
    list_for_each_safe (li, safe, head) {
        if (li == last)
            return;
        list_del(li);
        list_add(li, last);
    }
}

q_reverseK

走訪 list 的每個節點並計數
每 k 個為一個 sublist
並使 khead 作為這個 sublist 的頭部
使用 q_reverse 把這個 sublist 反向排列
最後當走訪到下一個 sublist 時要把 khead->next連接上去
因為在 q_reverse 之後 khead->next 是連接到 khead->prev 的

void q_reverseK(struct list_head *head, int k)
{
    // https://leetcode.com/problems/reverse-nodes-in-k-group/
    if (!head)
        return;
    LIST_HEAD(khead);
    khead.next = head;
    struct list_head *li, *safe;
    int i = k;
    list_for_each_safe (li, safe, head) {
        if (i == k) {
            khead.next->next = li;
            khead.next = li;
        } else if (i == 1) {
            khead.prev = li;
            q_reverse(&khead);
            i = k;
            continue;
        }
        i--;
    }
}

q_sort

Merge Sort
先用快慢指標把 list 分成兩半
並且用 first 跟 second 分別做為這兩半的 head
接著便遞迴下去直到分割成只有一個節點的 list
最後兩兩合併

void l_merge_two(struct list_head *first,
                 struct list_head *second,
                 struct list_head *head)
{
    while (!list_empty(first) && !list_empty(second)) {
        element_t *ele1 = list_entry(first->next, element_t, list);
        element_t *ele2 = list_entry(second->next, element_t, list);
        if (strcmp(ele1->value, ele2->value) <= 0)
            list_move_tail(first->next, head);
        else
            list_move_tail(second->next, head);
    }
    if (!list_empty(first))
        list_splice_tail_init(first, head);
    else
        list_splice_tail_init(second, head);
}


/* Sort elements of queue in ascending order */
void q_sort(struct list_head *head)
{
    if (!head || list_empty(head) || list_is_singular(head))
        return;
    struct list_head *slow = head, *fast = head;
    do {
        slow = slow->next;
        fast = fast->next->next;
    } while (fast != head && fast->next != head);

    LIST_HEAD(first);
    LIST_HEAD(second);
    list_splice_tail_init(head, &second);
    list_cut_position(&first, &second, slow);
    q_sort(&first);
    q_sort(&second);
    l_merge_two(&first, &second, head);
}

q_descend

從 list 的尾端反向走訪
並不斷紀錄最大的元素
如果有元素比紀錄到的小便從 list 中移除並且釋放記憶體
最後回傳沒有被刪除的元素的數量

int q_descend(struct list_head *head)
{
    // https://leetcode.com/problems/remove-nodes-from-linked-list/
    if (!head || list_empty(head) || list_is_singular(head))
        return 0;
    struct list_head *cur = head, *safe;
    element_t *max = NULL;
    int sum = 0;
    do {
        cur = cur->prev;
        safe = cur->prev;
        element_t *ele = list_entry(cur, element_t, list);
        if (!max || strcmp(ele->value, max->value) >= 0) {
            max = ele;
            sum++;
        } else {
            list_del(cur);
            q_release_element(ele);
            cur = safe->next;
        }
    } while (safe != head);

    return sum;
}

q_merge

把每個 list 都接到第一個 list 後面並且累加在內的元素數量
然後使用 Merge Sort 去排序

int q_merge(struct list_head *head)
{
    // https://leetcode.com/problems/merge-k-sorted-lists/
    if (!head || list_empty(head))
        return 0;
    queue_contex_t *first = list_first_entry(head, queue_contex_t, chain),
                   *ctx = NULL;
    int sum = first->size;
    list_for_each_entry (ctx, head, chain) {
        if (ctx == first)
            continue;
        sum += ctx->size;
        list_splice_tail_init(ctx->q, first->q);
    }
    q_sort(first->q);
    return sum;
}

qtest

使用make valgrind 發現 qtest 有 Memory Leak 的情況
觀察了一下 qtest.c
發現在函式 q_quit 中第一行為 return true
把這行刪掉即可使 qtest 在退出時正確釋放記憶體

static bool q_quit(int argc, char *argv[])
{
    return true;
    report(3, "Freeing queue");
    if (current && current->size > BIG_LIST_SIZE)
        set_cautious_mode(false);
    ...
}

如果在 queue 為 NULL 的情況下使用一些如 reverseK, descend 等指令
會出現 NULL pointer dereference 的情況
已進行修改為 qtest.c 加上 NULL check
並提交 pull request

Fix some NULL pointer dereference in qtest when the queue is NULL

dudect

實驗的原理為測量兩組資料執行的時間並且透過 t-test 去分析
如果兩組資料平均執行時間的統計差異超過一定閥值的話
則程式的複雜度便不為常數時間

How does this work? In a nutshell, this code takes two different inputs, runs the piece of code many times for each input and measures how much time it takes. If there is a statistical difference on the (average) time it takes to run with different inputs, the implementation is deemed not time constant.
Reference: dudect(Questions)

要注意的是 dudect 並不保證通過實驗的程式絕對為常數時間
如果需要更嚴謹的結果也需要去透過其他的測試去測量

My code passes this tests. Does it mean it is really time constant? Absolutely not. The test implemented is perhaps the simplest form of leakage detection. For serious assessment, you should also run many other tests, with specially crafted input vectors. The test harness implemented here is not yet that comprehensive. You're encourage to submit an implementation that is not constant time yet passes the test–in that way we can improve the test suite. The more you know about the implementation, the better you can design input vectors. For inspiration, see these RSA test vectors.
Reference: dudect(Questions)

Student's t-test

Student's t-test 是一種用於比較兩個樣本均值是否有顯著差異的統計檢驗方法，可以用於解決實驗數據中小樣本數量的問題。

在進行 t-test 時，我們通常有兩個樣本，每個樣本都有一組觀察值。我們希望知道這兩個樣本是否來自同一總體分佈。為此，我們首先計算每個樣本的平均值和標準差，然後使用這些統計量計算t值，這是兩個樣本均值之間的標準化差異。 t值的大小取決於樣本的大小、差異的大小以及每個樣本的標準差。如果t值很大，這意味著兩個樣本的均值之間的差異很顯著，而如果t值很小，則這兩個樣本的均值之間可能沒有顯著差異。

在計算t值後，我們可以將它與臨界值進行比較，以確定差異是否顯著。臨界值取決於樣本大小和所選的顯著性水平（通常為0.05）。如果 t 值超過了臨界值，我們可以拒絕假設，即這兩個樣本來自不同的總體分佈。

ChatGPT

dudect 的細節

在論文中總共分為三個部份

• Measure execution time
  首先需要去測量程式的執行時間(CPU Cycles)
  所以我們便使用兩組測資
  一組為固定測資 (fix class)，另一組則為隨機測資(random class)
  而固定測資可以選擇邊緣測資去觸發程式的特例處理
  最後為了降低環境對測量的影響（如 OS、外部程式），每次測試的測資是隨機選擇的

In the original leakage detection paper [CKN00] the authors propose
to interleave the sequence of classes during the evaluation. We extend this
suggestion and randomize this sequence to prevent interference due to any
concurrent process that may be executing in parallel.
Reference: Dude, is my code constant time? page 2

• Apply post-processing
  當進行測量後，可以在統計分析之前先預處理得到的數據(CPU Cycles)
  我們可以去除掉明顯超過一定閥值的數據，因為這些數據可能是由於外部環境的干擾而形成的誤差
  或是使用其他更高階的 pre-processing

• Apply statistical test
  最後一步便是對先前測量得到的數據(CPU Cycles)做 t-test
  若是進行分析後得到的結果 t 超過某個閥值
  我們便能斷定測試的程式執行時間不為常數時間

lab-0 的 dudect

在把 queue.c 實作完之後
會發現經由測試 dudect 測試的 q_insert_head 及 q_insert_tail 並不為常數時間
在本課程的教材中有提到 lab-0 的 dudect 缺少對 percentiles 的處理
透過觀察原本的程式碼會發現 percentiles 原本是作為對測量後得到的數據作預處理的閾值
我們把 percentiles 引進 lab-0 之後 dudect 便能正確分析 q_insert_head 及 q_insert_tail 的執行時間

static int64_t percentile(int64_t *a, double which, size_t size)
{
    qsort(a, size, sizeof(int64_t), (int (*)(const void *, const void *)) cmp);
    size_t array_position = (size_t) ((double) size * (double) which);
    assert(array_position >= 0);
    assert(array_position < size);
    return a[array_position];
}

/*
 set different thresholds for cropping measurements.
 the exponential tendency is meant to approximately match
 the measurements distribution, but there's not more science
 than that.
*/
static void prepare_percentiles(int64_t *percentiles, int64_t *exec_times)
{
    for (size_t i = 0; i < NUMBER_PERCENTILES; i++) {
        percentiles[i] = percentile(
            exec_times,
            1 - (pow(0.5, 10 * (double) (i + 1) / NUMBER_PERCENTILES)),
            N_MEASURES);
    }
}

static void update_statistics(const int64_t *exec_times,
                              uint8_t *classes,
                              int64_t *percentiles,
                              t_context_t *ttest_ctxs[])
{
    for (size_t i = 0; i < N_MEASURES; i++) {
        int64_t difference = exec_times[i];
        /* CPU cycle counter overflowed or dropped measurement */
        if (difference <= 0)
            continue;

        /* do a t-test on the execution time */
        t_push(ttest_ctxs[0], difference, classes[i]);
        // t-test on cropped execution times, for several cropping thresholds.
        for (size_t crop_index = 0; crop_index < NUMBER_PERCENTILES;
             crop_index++) {
            if (difference < percentiles[crop_index]) {
                t_push(ttest_ctxs[crop_index + 1], difference, classes[i]);
            }
        }
    }
}

shuffle

用 Fisher-Yates Shuffle 去實作 shuffle 指令

把隨機選到的節點直接接到 list 的尾端
因為選擇的範圍是 len 所以不會選到重複的節點

void q_shuffle(struct list_head *head)
{
    if (!head || list_empty(head))
        return;
    int len = q_size(head);
    struct list_head *ptr;
    while (len) {
        ptr = head->next;
        for (int i = rand() % len; i > 0; i--)
            ptr = ptr->next;
        list_move_tail(ptr, head);
        len--;
    }
}

這是用[1,2,3]去執行 shuffle 一萬次的結果
自由度為5
並且設顯著水準

$\alpha$ 為 0.05

Expectation:  166666
Observation:  {'123': 166339, '132': 167262, '213': 166269, '231': 166302, '312': 167085, '321': 166743}
chi square sum:  5.60246240984964

可以看到 chi-squared sum 約為5.6
查卡方分佈表表後的 p value 介於0.3~0.5
明顯大於我們設的顯著水準 0.05
因此我們不拒絕虛無假設

$H_0$
而同時圖表也顯示結果大致符合 Uniform distribution

Linux 的 list_sort.c

先從 list_sort 的參數開始

• priv -> 要塞進cmp裡的物件
• head -> 要排序 list 的 head
• cmp -> 自訂的比較函式

/**
 * list_sort - sort a list
 * @priv: private data, opaque to list_sort(), passed to @cmp
 * @head: the list to sort
 * @cmp: the elements comparison function
 *

cmp

接收三個參數

• priv
• a -> list_head
• b -> list_head

如果是要讓 a 排在 b
則必須回傳 >0 (回傳a>b可以讓他變成遞增排列)
而如果是 a 排在 b之前
則是回傳 <=0
這樣子做可以支援兩種形式的 cmp
像是 strcmp 的 <0 =0 >0
或是回傳 0/1 的 boolean 形式

merge_sort

lib/list_sort: Optimize number of calls to comparison function
演算法會去保證 merge 時的 list 至少長度為2:1
當有兩個長度為

$2^k$ 的 sublist 的時候，只有等到出現下一個

$2^k$ 的 sublist 才會把前者合併
因為如果用一般的 fully-eager bottom-up mergesort
也就是每遇到兩個 list 就 merge
當整體的長度略大於2的冪(n=1028)
那最後一次 merge 的兩個 list 就會極為不平衡 (1024:4)
使得浪費很多不必要的時間在比較上

同時只要這2:1的 list 都能放進 cache 就能去避免 cache thrashing 的發生

* This mergesort is as eager as possible while always performing at least
* 2:1 balanced merges.  Given two pending sublists of size 2^k, they are
* merged to a size-2^(k+1) list as soon as we have 2^k following elements.
*
* Thus, it will avoid cache thrashing as long as 3*2^k elements can
* fit into the cache.  Not quite as good as a fully-eager bottom-up
* mergesort, but it does use 0.2*n fewer comparisons, so is faster in
* the common case that everything fits into L1.

在實作上何時決定merge是用變數 count (pending 裡的節點數量) 去決定的
而每當 count 增加的時候，我們就把一個節點放進 pending 裡
同時 count 增加代表著我們會把第k個 bit 設成 1 並把 k-1 ~ 0 的bit清除

 0 -> 1 -> 2 -> 3 -> 4 -> 5
000  001  010  011  100  101

而在增加的過程中
我們會把兩個

$2^k$ 的 sublist 合併成一個

$2^{k+1}$ 的list
只有當 count 增加到2的冪我們才不會合併

0 -> 1 | 000 -> 001  no merge
1 -> 2 | 001 -> 010  no merge
2 -> 3 | 010 -> 011  merge k=0
3 -> 4 | 011 -> 100  no merge
4 -> 5 | 100 -> 101  merge k=0
5 -> 6 | 101 -> 110  merge k=1
6 -> 7 | 110 -> 111  merge k=0
7 -> 8 | 111 -> 1000 no merge

在實作上也有說明函式是怎麼去處理資料的

• list 跟 sublist 都會變成 null-terminated，且不再去維護 list 的 prev
• pending 是一個反向的 list ，每一個節點都是準備去被 merge 的 sublist
• 每個 sublist 長度都是 2 的冪
• 在 pending 中的 sublist 順序是依照長度跟時間，越小且越新的 sublist 會排在最前面
• 每種大小的 sublist 只會有 0~2 個
• 一對 sublist 在總長度跟在 pending 中的節點數量一樣時就會被合併(每當 count 增加到 sublist 長度的奇數倍)，這樣可以確保每次 merge 的長度都是 2:1 (ex: 兩個長度為 2 的 sublist 會在 count 增加到6的時候合併成長度為 4 的 sublist)
• 每一輪都會做以下的事情
  – 合併兩個長度由 count 去決定的 sublist ，並重新加入到 pending 裡
  – 然後把一個節點放進 pending 裡

* Data structure invariants:
* - All lists are singly linked and null-terminated; prev
*   pointers are not maintained.
* - pending is a prev-linked "list of lists" of sorted
*   sublists awaiting further merging.
* - Each of the sorted sublists is power-of-two in size.
* - Sublists are sorted by size and age, smallest & newest at front.
* - There are zero to two sublists of each size.
* - A pair of pending sublists are merged as soon as the number
*   of following pending elements equals their size (i.e.
*   each time count reaches an odd multiple of that size).
*   That ensures each later final merge will be at worst 2:1.
* - Each round consists of:
*   - Merging the two sublists selected by the highest bit
*     which flips when count is incremented, and
*   - Adding an element from the input as a size-1 sublist.

接著我們來看實際的程式碼

初始化

struct list_head *list = head->next, *pending = NULL;
size_t count = 0;	/* Count of pending */

把 list 變成 null-terminated

/* Convert to a null-terminated singly-linked list. */
head->prev->next = NULL;

當 list 不為 NULL 的時候會不斷執行下面的程式

do {
    ...
} while (list);

先去找 count 裡為 0 的 LSB
因為那個 bit 在 count 增加後便是我們要的 bit k

/* Find the least-significant clear bit in count */
for (bits = count; bits & 1; bits >>= 1)
	tail = &(*tail)->prev;

接著我們便進行 merge(count 不為

$2^n-1$的時候，因為增加後會變成

$2^n$)
當 merge 完後我們便把新的 sublist 加回到在 pending 中原來的位置

if (likely(bits)) {
    struct list_head *a = *tail, *b = a->prev;

    a = merge(priv, cmp, b, a);
    /* Install the merged result in place of the inputs */
    a->prev = b->prev;
    *tail = a;
}

每一輪的最後我們便把 list 中的一個節點放進 pending中
並且 count 加一

list->prev = pending;
pending = list;
list = list->next;
pending->next = NULL;
count++;

當 list 裡面都沒東西後
我們在 pending 中有可能還會有 sublist 沒有被 merge
於是我們就把剩下的東西 merge 掉

list = pending;
pending = pending->prev;
for (;;) {
	struct list_head *next = pending->prev;

	if (!next)
		break;
	list = merge(priv, cmp, pending, list);
	pending = next;
}

最後我們會使用 merge_final 把 merge 好的東西放回 list
以及把 list 每個節點的 prev 都重新接上
並且變回 circular doubly-linked list

merge_final(priv, cmp, head, pending, list);

/* Finish linking remainder of list b on to tail */
tail->next = b;
do {
	/*
	* If the merge is highly unbalanced (e.g. the input is
	* already sorted), this loop may run many iterations.
	* Continue callbacks to the client even though no
	* element comparison is needed, so the client's cmp()
	* routine can invoke cond_resched() periodically.
		 */
    if (unlikely(!++count))
	    cmp(priv, b, b);
    b->prev = tail;
    tail = b;
    b = b->next;
} while (b);

/* And the final links to make a circular doubly-linked list */
tail->next = head;
head->prev = tail;