Try   HackMD

2023q1 Homework1 (lab0)

contributed by < Tonr01 >

開發環境

gcc (Ubuntu 11.3.0-1ubuntu1~22.04) 11.3.0

架構:                   x86_64
CPU 作業模式:            32-bit, 64-bit
Address sizes:          39 bits physical, 48 bits virtual
Byte Order:             Little Endian
CPU(s):                 16
On-line CPU(s) list:    0-15
供應商識別號:            GenuineIntel
Model name:             11th Gen Intel(R) Core(TM) i7-11800H @ 2.30GHz
    CPU 家族:           6
    型號:               141
    每核心執行緒數:       2
    每通訊端核心數:       8
    Socket(s):          1
    製程:               1
    CPU max MHz:        4600.0000
    CPU min MHz:        800.0000
    BogoMIPS:           4608.00

Virtual machine 建立

  • 建立虛擬機

    Image Not Showing Possible Reasons
    • The image was uploaded to a note which you don't have access to
    • The note which the image was originally uploaded to has been deleted
    Learn More →

  • 設定硬碟大小

    image

  • 設定存儲裝置,並選擇下載好的 Ubuntu 版本

    image

Ubuntu磁區分割

Ubuntu Linux 磁碟分割和目錄的類型和定義說明

image

因為是在虛擬機上分割磁區,不會有 EFIBios ,所以都須自己分割出來

安裝必要檔案

作業要求

  • q_new: 建立新的「空」佇列;
  • q_free: 釋放佇列所佔用的記憶體;
  • q_insert_head: 在佇列開頭 (head) 插入 (insert) 給定的新節點 (以 LIFO 準則);
  • q_insert_tail: 在佇列尾端 (tail) 插入 (insert) 給定的新節點 (以 FIFO 準則);
  • q_remove_head: 在佇列開頭 (head) 移去 (remove) 給定的節點;
  • q_remove_tail: 在佇列尾端 (tail) 移去 (remove) 給定的節點;
  • q_release_element: 釋放特定節點的記憶體空間;
  • q_size: 計算目前佇列的節點總量;
  • q_delete_mid: 移走佇列中間的節點,
  • q_delete_dup: 在已經排序的狀況,移走佇列中具備重複內容的節點
  • q_swap: 交換佇列中鄰近的節點
  • q_reverse: 以反向順序重新排列鏈結串列,該函式不該配置或釋放任何鏈結串列節點,換言之,它只能重排已經存在的節點;
  • q_reverseK: 類似 q_reverse,但指定每 k 個節點為一組,進行反向順序排列
  • q_sort: 以遞增順序來排序鏈結串列的節點
  • q_merge: 合併所有已排序的佇列,並合而為一個新的已排序佇列
  • q_descend:

queue.c 開發過程

q_new

思路

一開始最簡單的想法是,配置記憶體給head,並檢查是否配置成功。

程式碼

出現了 Segmentation fault occurred. You dereferenced a NULL or invalid pointermake ,再看完程式碼的 comment Notice: sometimes, Cppcheck would find the potential NULL pointer bugs 與巨集後,發現我忽略了 pointer 的指向。

struct list_head *q_new()
{
    struct list_head *head =
        (struct list_head *) malloc(sizeof(struct list_head));

    if (!head) {
        free(head);
        return NULL;
    }

    return head;
}

於是加入 INIT_LIST_HEAD(head); ,將 head 的 prev 與 next 都指向自己。

struct list_head *q_new()
{
    struct list_head *head =
        (struct list_head *) malloc(sizeof(struct list_head));

    if (!head) {
        free(head);
        return NULL;
    }

+    INIT_LIST_HEAD(head);

    return head;
}

q_free

思路

一開始先檢查 list 是否存在,若不存在則無須進行 q_free ,再看完 list.h 定義的巨集後,發現 list_for_each_entry_safe 適合用來走訪每個 entry ,再使用 q_release_element(entry); 來釋放該 entryentry->valueentry->list ,最後將 head 也釋放掉,釋放整個 list。

程式碼

void q_free(struct list_head *l)
{
    if (!l)
        return;

    element_t *entry, *safe;

    list_for_each_entry_safe (entry, safe, l, list)
        q_release_element(entry);

    free(l);
}

q_insert_head

思路

首先先檢查 list 是否存在,再配置記憶體給新的 entry,並檢查 entryentry->value 的空間是否配置成功,將節點的value值用strdup(s);將s的值複製給它,最後將new_elementlist_add加入到list開頭的位置上。

程式碼

有出現 Test of malloc failure 錯誤訊息,才發現 entry 裡的 entry->value 的空間也可能配置失敗,於是加入配置記憶體的檢查。

bool q_insert_head(struct list_head *head, char *s)
{
    if (!head)
        return false;

    element_t *new_element = malloc(sizeof(element_t));

    if (!new_element)
        return false;

    new_element->value = strdup(s);

    list_add(&new_element->list, head);

    return true;
}

修改後。

bool q_insert_head(struct list_head *head, char *s)
{
    if (!head)
        return false;

    element_t *new_element = malloc(sizeof(element_t));

    if (!new_element)
        return false;

    new_element->value = strdup(s);

+    if (!new_element->value) {
+        free(new_element);
+      return false;
+   }

    list_add(&new_element->list, head);

    return true;
}

q_insert_tail

思路

大致上與 q_insert_head 思路一樣,首先先檢查 list 是否存在,再配置記憶體給新的 entry,並檢查 entryentry->value 的空間是否配置成功,將 entry->valuestrdup(s); 將s的值複製給它,最後將 new_elementlist_add_tail 加入到list最後的位置上。

程式碼

bool q_insert_head(struct list_head *head, char *s)
{
    if (!head)
        return false;

    element_t *new_element = malloc(sizeof(element_t));

    if (!new_element)
        return false;

    new_element->value = strdup(s);

    if (!new_element->value) {
        free(new_element);
        return false;
    }

    list_add_tail(&new_element->list, head);

    return true;
}

q_remove_head

思路

一開始先檢查 list 使否存在與 list 是否為空,再使用 list_first_entry 找出第一個 entry 的位置,再使用 list_del_init 將此 entry remove ,並將此 entry 的 prev 與 next 都指向自己,最後將 entry->valuestrncpy 複製到 sp 裡。

程式碼

element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head))
        return NULL;

    element_t *target = list_first_entry(head, element_t, list);
    list_del_init(&target->list);

    if (sp) {
        strncpy(sp, target->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }

    return target;
}

q_remove_tail

思路

大致上與 q_remove_head 思路一樣,一開始先檢查 list 使否存在與 list 是否為空,再使用 list_last_entry 找出最後一個 entry 的位置,再使用 list_del_init 將此 entry remove ,並將此 entry 的 prev 與 next 都指向自己,最後將 entry->valuestrncpy 複製到 sp 裡。

程式碼

element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head))
        return NULL;

    element_t *target = list_last_entry(head, element_t, list);
    list_del_init(&target->list);

    if (sp) {
        strncpy(sp, target->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }

    return target;
}

q_size

思路

一開始先檢查 list 使否存在與 list 是否為空,再宣告一個節點用 list_for_each 去走訪 list ,並紀錄 list 大小。

程式碼

int q_size(struct list_head *head)
{
    if (!head || list_empty(head))
        return 0;

    int size = 0;
    struct list_head *li;

    list_for_each (li, head)
        size++;

    return size;
}

q_delete_mid

思路

我的想法是用 two-pointer 的方式實作,首先宣告兩個 pointer prenex 分別代表 list 的頭跟尾的位置,這兩個 pointer 會一直往中心移動,會有兩種 case

  • Case 1:Size of list 為奇數 (5個節點),此時當 prenex 在同個位置的節點即為中心點。

  • Case 2:Size of list 為偶數 (6個節點),此時當 prenex 交錯時, pre 即為中心點。

list_del 將該節點從 list 中分離出來,再用 list_entry 取得 entry 位置,最後釋放該 entry

程式碼

bool q_delete_mid(struct list_head *head)
{
    if (!head || list_empty(head))
        return false;

    struct list_head *pre = head->prev;
    struct list_head *nex = head->next;

    // Find the middle of list
    do {
        pre = pre->prev;
        nex = nex->next;
    } while (pre != nex && pre != nex->next);

    list_del(pre);
    element_t *target = list_entry(pre, element_t, list);
    q_release_element(target);

    return true;
}

q_delete_dup

思路

先用 list_for_each_entry_safe 去走訪每個元素 ,分別用 targettemp 去紀錄第一個元素與下一個元素,再檢查它們是否相同,若相同,則釋放掉 target,用一個二元變數 dup 去紀錄是否有重複,若 dup == true ,則 target 也為重複的元素,再將其釋放。

在實作時出現 Segmentation fault occurred. You dereferenced a NULL or invalid pointer ,發現是因為在比較時, temp 存取去到 head ,所以加入了 target->list.next != head 去使 temp 不會去存取到 head

程式碼

bool q_delete_dup(struct list_head *head)
{
    if (!head || list_empty(head))
        return false;

    bool dup = false;
    element_t *target, *temp;

    list_for_each_entry_safe (target, temp, head, list) {
        if (target->list.next != head && !strcmp(target->value, temp->value)) {
            dup = true;
            list_del(&target->list);
            q_release_element(target);
        } else if (dup) {
            dup = false;
            list_del(&target->list);
            q_release_element(target);
        }
    }

    return true;
}

q_reverse

思路

想到的方法為逐一將 list 走訪,每走訪一個 entry 就將該 entry 從 list 中分離出來,再加入到 list 的第一個位置。

程式碼

void q_reverse(struct list_head *head)
{
    element_t *entry, *safe;
    list_for_each_entry_safe (entry, safe, head, list)
        list_move(&entry->list, head);
}

q_reversek

思路

作法跟 q_reverse 類似,但不像 q_reverse 總是將節點插入第一個位置,這裡使用一個 pointer insert 指向一組 k 個節點的第一個插入位置,再使用 count 去紀錄走訪的節點數,當走訪的節點數恰 k 個時,將 pointer insert 指向下一組 k 個節點的第一個插入位置,也就是上一組的最後一個節點(目前節點的 prev)。

程式碼

void q_reverseK(struct list_head *head, int k)
{
    if (!head || list_empty(head))
        return;

    struct list_head *node = NULL, *safe = NULL, *insert = head;
    int count = 0;

    list_for_each_safe(node, safe, head) {
        if (k > count) 
            list_move(node, insert);
        else {
            count = 0;
            insert = node->prev;
        }
        count++;
    }    
}

q_swap

思路

q_swap 其實就是 q_reverseK(2) ,於是用q_reverseK 去實作。

程式碼

void q_swap(struct list_head *head)
{
    if (!head || list_empty(head))
        return;

    q_reverseK(head, 2);
}

q_descend

思路

從 list 最尾端開始往前做,設 target 為最後一個元素、 prevtarget 的前一個元素、 size 紀錄 list 中剩餘元素個數。

  • 若後面的元素比前一個元素大,則將前一個元素移出 list。
  • 繼續往前找,直到找到比現在的 target 還大的元素,再將 target 指向此元素。
  • 重複以上步驟直到到 head 為止。

程式碼

在跑測試時,在執行 q_free 後尚有未被刪除的元素,發現因為將元素移出 list 後,並未將其釋放而造成錯誤。

int q_descend(struct list_head *head)
{
    if (!head || list_empty(head))
        return 0;

    int size = q_size(head);
    struct list_head *target = head->prev, *prev = target->prev;

    while (target->prev !=head) {
        element_t *t = list_entry(target, element_t, list);
        element_t *p = list_entry(prev, element_t, list);

        if (strcmp(p->value, t->value) < 0) {
            list_del_init(&p->list);
            prev = target->prev;
            size--;
        }
        else {
            target = prev;
            prev = target->prev;
        }
    }

    return size;
}

修改後

int q_descend(struct list_head *head)
{
    if (!head || list_empty(head))
        return 0;

    int size = q_size(head);
    struct list_head *target = head->prev, *prev = target->prev;

    while (target->prev !=head) {
        element_t *t = list_entry(target, element_t, list);
        element_t *p = list_entry(prev, element_t, list);

        if (strcmp(p->value, t->value) < 0) {
-           list_del_init(&p->list);
+           list_del(&p->list);
+           q_release_element(p);
            prev = target->prev;
            size--;
        }
        else {
            target = prev;
            prev = target->prev;
        }
    }

    return size;
}

使用 diffgit diff 產生程式碼差異的列表
:notes: jserv

q_sort

思路

我選擇採用 merge sort,因為 merge sort 為 stable sorting algorithm ,而其最壞的時間複雜度只有

O(nlogn) ,這裡參考了 Linked List Sort 的實作方法,將 merge sort 分成三個部份,分別是:

  • mergelist
    • 主要是做 merge 的部份,採用非遞迴的方式將兩個 list 以遞增的形式串接在一起。
  • mergesort
    • 主要是做 split 的部份,使用兩個指標,分別是 fastslow ,採用 Floyd Cycle Detection Algorithm ,當較快的指標到達終點時,較慢的指標會恰好在中心位置,並以遞迴的方式將 list 拆解,再呼叫 mergelist 將拆解後的 list 排序並重新組合成一條 list。
  • q_sort
    • 因為採用 Floyd Cycle Detection Algorithm 的方式,所以原本的環狀佇列結構會導致找不到中心位置,於是先將原本的環狀 doubly-linked list 轉換成 singly-linked list,等做完 merge sort 後,再將 singly-linked list 轉回環狀 doubly-linked list。

注意連字號的位置,書寫為 "doubly-linked list"
:notes: jserv
👌 (以修改)

程式碼

  • mergelist
struct list_head *mergelist(struct list_head *l1, struct list_head *l2)
{
    struct list_head temp;
    struct list_head *t = &temp;

    while (l1 && l2) {
        element_t *ele1 = list_entry(l1, element_t, list);
        element_t *ele2 = list_entry(l2, element_t, list);
        if (strcmp(ele1->value, ele2->value) < 0) {
            t->next = l1;
            t = t->next;
            l1 = l1->next;
        } else {
            t->next = l2;
            t = t->next;
            l2 = l2->next;
        }
    }

    // Connect the remain list
    if (l1)
        t->next = l1;
    if (l2)
        t->next = l2;

    return temp.next;
}
  • mergesort
struct list_head *mergesort(struct list_head *head)
{
    if (!head->next)
        return head;

    struct list_head *fast = head->next;
    struct list_head *slow = head;

    // split list
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }

    // Fast is the middle of list
    fast = slow->next;
    slow->next = NULL;

    struct list_head *left = mergesort(head);
    struct list_head *right = mergesort(fast);

    // Merge sorted left and sorted right
    return mergelist(left, right);
}
  • q_sort
void q_sort(struct list_head *head)
{
    if (!head || list_empty(head))
        return;

    // Turn the list into Singly linked list
    head->prev->next = NULL;
    head->next = mergesort(head->next);

    // Turn the list into doubly circular linked list
    struct list_head *temp = head, *next = head->next;
    while (next) {
        next->prev = temp;
        temp = next;
        next = next->next;
    }
    temp->next = head;
    head->prev = temp;

q_merge

思路

一開始有兩種想法,第一種是使用 mergelist 迭代的將兩條 list 合併成一條,但因為 mergelist 實作的關係,輸入需要是沒有 head 的兩條 list ,所以在迭代前都需要先對 list head 做處理,而在合併後還須將 list 變回 doubly-linked list,以上步驟會讓程式碼變得較為冗長。於是採用第二種方法,第二種為先將所有 list 串接在一起,再對這條 list 做 q_sort ,這樣一來就無須對 head 做變更,整體程式碼可以較為簡短。

cur 表示第一條 queue, temp 為指向下一條佇列的指標,迭代的將後面的佇列連接到第一條佇列後面,最後再對這條佇列做 q_sort ,最後回傳佇列長度。

程式碼

int q_merge(struct list_head *head)
{
    if (!head || list_empty(head))
        return 0;

    queue_contex_t *cur = list_entry(head->next, queue_contex_t, chain);

    for (struct list_head *temp = head->next->next; temp != head;
         temp = temp->next) {
        queue_contex_t *t = list_entry(temp, queue_contex_t, chain);
        list_splice_init(t->q, cur->q);
    }

    q_sort(cur->q);
    return q_size(cur->q);
}

引入 list_sort.c 比較自己的 sort.c 效能差異

引入list_sort 檔案及修改

首先引入 list_sort.h ,刪除不必要的 header

/* SPDX-License-Identifier: GPL-2.0 */
#ifndef _LINUX_LIST_SORT_H
#define _LINUX_LIST_SORT_H

#include <stdint.h>
#include "list.h"

list_sort.c 使到兩個巨集 likelyunlikely,定義於<linux/compiler.h>,將其定義加入 list_sort.h 中,在 merge_final 函式中宣告了 u8 count = 0; ,將其改成 uint_8 count = 0;

# define likely(x)	__builtin_expect(!!(x), 1)
# define unlikely(x)	__builtin_expect(!!(x), 0)

最後是將 list_sort.o 寫入 makefile 裡。

OBJS := qtest.o report.o console.o harness.o queue.o list_sort.o\
        random.o dudect/constant.o dudect/fixture.o dudect/ttest.o \
        shannon_entropy.o \
        linenoise.o web.o

qtest 中先複製一份 do_sortlist_sort 使用,在 list_sort.h 中有定義函式,於是需要自己實作,這個函式是用來比較字串大小,回傳值為 int

typedef int __attribute__((nonnull(2,3))) (*list_cmp_func_t)(void *,
		const struct list_head *, const struct list_head *);

所以在 qtest 中加入 cmp 函式實作。

int cmp(void *priv, const struct list_head *list1, const struct list_head *list2)
{
    element_t *list1_entry = list_entry(list1, element_t, list);
    element_t *list2_entry = list_entry(list2, element_t, list);
    return strcmp(list1_entry->value, list2_entry->value)   ;
}

qtest 中的命令 mysortlist_sort 都能正常執行。

效能比較

這裡用 qtest 中的 time 進行時間的比較,有三種測資,分別用命令 RAND 加入100000、300000、500000筆隨機資料給 queue 。

測試指令

加入自己寫的 trace-mysort.cmdtrace-list_sort.cmd 到測試資料中, ./qtest -v 3 -f traces/trace-list_sort.cmd 會執行以下命令。

option fail 0
option malloc 0
new
ih RAND 100000/300000/500000
time mysort/list_sort
free

my_sort

測試次數 100000筆 300000筆 500000筆
1 0.042 0.196 0.407
2 0.041 0.194 0.419
3 0.042 0.200 0.430
average 0.0417 0.1967 0.4187

list_sort

測試次數 100000筆 300000筆 500000筆
1 0.041 0.170 0.368
2 0.043 0.170 0.388
3 0.039 0.171 0.364
average 0.041 0.1703 0.3733

效能差距

100000筆 300000筆 500000筆
效能差距 2% 14% 11%

因為測試資料都是隨機生成的,加上測試次數不多,所以以 Perf 來分析效能。

測試方式不足以反映出上述實作的特性。
:notes: jserv
👌 (以修改)

Linux 效能分析工具: Perf 來分析效能

環境安裝

$ cat "/boot/config-`uname -r`" | grep "PERF_EVENT"

用此指令確認是否安裝 perf。

$ uname -r
5.19.0-43-generic

確認 kernel 版本。

$ sudo apt-get install linux-tools-5.19.0-43-generic linux-cloud-tools-5.19.0-43-generic

安裝 perf。

$ cat /proc/sys/kernel/perf_event_paranoid

確認 perf 權限。

  • 2 : 不允許任何量測。但部份用來查看或分析已存在的紀錄的指令仍可使用,如 perf ls、perf report、perf timechart、 perf trace。
  • 1 : 不允許 CPU events data。但可以使用 perf stat、perf record 並取得 Kernel profiling data。
  • 0 : 不允許 raw tracepoint access。但可以使用 perf stat、perf record 並取得 CPU events data。
  • -1: 權限全開。
$ sudo sh -c " echo -1 > /proc/sys/kernel/perf_event_paranoid"

將權限全開

$ sudo sh -c " echo 0 > /proc/sys/kernel/kptr_restrict"

最後如果要檢測 cache miss event,需要先取消 kernel pointer 的禁用。

測試指令

使用./qtest -v 3 -f traces/trace-list_sort.cmd 會執行以下命令,這裡以500000筆隨機資料做測試。

option fail 0
option malloc 0
new
ih RAND 500000
time mysort/list_sort
free

執行 perf stat --repeat 5 -e cache-misses,cache-references,instructions,cycles ./qtest -f traces/trace-mysort.cmd ,會執行5次上述命令,再去觀察其效能。

my_sort

Performance counter stats for './qtest -f traces/trace-mysort.cmd' (5 runs):

        16,049,539      cache-misses              #   48.666 % of all cache refs      ( +-  0.18% )
        32,954,397      cache-references                                              ( +-  0.04% )
     2,203,807,317      instructions              #    0.74  insn per cycle           ( +-  0.00% )
     2,958,082,501      cycles                                                        ( +-  0.37% )

           0.65370 +- 0.00448 seconds time elapsed  ( +-  0.69% )

list_sort

Performance counter stats for './qtest -f traces/trace-list_sort.cmd' (5 runs):

        14,022,127      cache-misses              #   54.505 % of all cache refs      ( +-  0.43% )
        25,688,333      cache-references                                              ( +-  0.10% )
     2,251,606,244      instructions              #    0.81  insn per cycle           ( +-  0.00% )
     2,867,416,957      cycles                                                        ( +-  0.90% )

           0.61738 +- 0.00504 seconds time elapsed  ( +-  0.82% )

效能

event data my_sort list_sort
cache-misses 16,049,539 14,022,127
cache-references 32,954,397 25,688,333
instructions 2,203,807,317 2,251,606,244
cycles 2,958,082,501 2,867,416,95

花費時間

測試次數 my_sort 花費時間 list_sort 花費時間
1 0.357 0.398
2 0.361 0.412
3 0.362 0.407
4 0.364 0.411
5 0.365 0.402
average 0.3618 0.406

可以看出 list_sort 的 cache-misses 比 my_sort 少很多, list_sort 所需的 instructions 與 cycles 都比 my_sort 少, my_sort 只能達到 list_sort 的 89% 效能 (0.3618/0.406 = 0.89) 。

在 qtest 提供新的命令並實作 shuffle

利用 Fisher–Yates shuffle 演算法來實作洗牌(shuffle)

  1. 先用 q_size 取得佇列的大小 len。
  2. 隨機從 0 ~ (len - 1) 中抽出一個數字 random,抽到的數字為節點的位置,再將該節點加到佇列最後位置。
  3. 隨著 len 大小變小,直到所有的節點都已經被抽到過,shuffle 就結束。

shuffle 流程

len random queue result
0–5 5 A B C D E F F
0–4 3 A B C D E F D
0–3 1 A B C E F D B
0–2 1 A C E F D B C
0–1 0 A E F D B C A
0–0 0 E F D B C A E

shuffle 實作

len 為佇列的大小,random 為隨機數,也同時代表被抽到的節點位置,將 node 移動到第 random 個節點位置,再將該節點移動到佇列最後的位置,當每個節點都做過一輪就結束。

void shuffle(struct list_head *head)
{
    if (!head || list_empty(head))
        return;

    int len = q_size(head);

    while (len) {
        int random = rand() % len;
        struct list_head *node = head->next;

        while (random) {
            node = node->next;
            random--;
        }

        list_move_tail(node, head);
        len--;
    }
}

shuffle 加入到 qtest 裡面,這裡的 do_shuffle 是參考 do_reverse 的實作,因為這兩個函式都是用來改變佇列的位置。

bool do_shuffle(int argc, char *argv[])
{
    if (argc != 1) {
        report(1, "%s takes no arguments", argv[0]);
        return false;
    }

    if (!current || !current->q)
        report(3, "Warning: Calling shuffle on null queue");
    error_check();

    set_noallocate_mode(true);
    if (current && exception_setup(true))
        shuffle(current->q);
    exception_cancel();

    set_noallocate_mode(false);
    q_show(3);
    return !error_check();
}

執行結果

# do 5 times shuffle
l = []
l = [A]
l = [A B]
l = [A B C]
l = [A B C D]
l = [A B C D E]
l = [A B C D E F]
# shuffle
l = [E F D C B A]
l = [B A F E C D]
l = [E F B C A D]
l = [C F D E A B]
l = [B D F A E C]
l = NULL
Freeing queue

研讀論文〈Dude, is my code constant time?〉,解釋本程式的 “simulation” 模式

研讀論文〈Dude, is my code constant time?〉

Introduction

這篇論文主要闡述提供了一個新的工具 dudect ,可以不限定任何平台去檢測部份的程式碼是否達到 constant time ,提供 leakage detection 的方法。

Leakage detection

這個方法會先去測量兩種不同的輸入的執行時間,並用統計學去判定這兩種執行時間的差異性,其中一種輸入為固定的數值,另一種為隨機數值。在進行統計分析前會先裁掉極值,這些極值可能是測量的誤差或是程式執行被中斷導致。

Statistical test

這裡採用 Welch's t-test ,為 Student's t-test 的改編版, Welch's t-test 處理兩個樣本間不同的標準差與樣本大小會比較可靠,這個方法會去計算兩個樣本的均值是否相等,並計算出 t 值。其中

X¯ 為樣本均值,
sX¯
為標準差。

Pre-processing

這裡提到的預處理指的是在進行統計分析前裁剪掉極值的動作,而裁剪的方法為裁剪掉大於

p 百分比的測量值。這部份也就是 simulation 的缺陷,因為沒有將極值裁剪掉,導致影響到測量的速度。

解釋 Simulation 模式

首先在 trace-17-complexity.cmd 會先執行 option simulation 1 ,先開啟 simulation mode ,再呼叫 it, ih, rh, rt 四個函式。以呼叫 ih 為例,在 qtest 中會執行 bool do_ih 函式。

if (simulation) {
        if (argc != 1) {
            report(1, "%s does not need arguments in simulation mode", argv[0]);
            return false;
        }
        bool ok = is_insert_head_const();
        if (!ok) {
            report(1,
                   "ERROR: Probably not constant time or wrong implementation");
            return false;
        }
        report(1, "Probably constant time");
        return ok;
    }

可以看到決定執行時間是否為 constant time 且程式正確執行,由函式 is_insert_head_const 決定,此函式在 fixture.h 定義。

bool is_##op##_const(void) { return test_const(#op, DUT(op)); }

fixture.cis_##op##_const 會回傳函式 test_const 的結果 resultresult 為函式 doit 的回傳值。

result = doit(mode);

其中 result 由兩個函式的回傳值做 AND 而來, measure(), report()

static bool doit(int mode)
{
    ...
    bool ret = measure(before_ticks, after_ticks, input_data, mode);
    ...
    ret &= report();
    ...
    return ret;
}

首先為函式measure ,主要對四種模式 it, ih, rh, rt 進行執行正確性的判定,判定依據為執行完該函式,其改變後的佇列大小是否正確。

if (before_size != after_size - 1)
    return false;

再來是函式 report ,主要是用來判定執行時間是否為 constant time 。

/* Definitely not constant time */
if (max_t > t_threshold_bananas)
    return false;

/* Probably not constant time. */
if (max_t > t_threshold_moderate)
    return false;

/* For the moment, maybe constant time. */
return true;

解決 Simulation 實作的缺陷

首先將參數

p 百分比 percentiles 加入到宣告中,但因為作者有多宣告了一種結構,而 Simulation 實作是將宣告直接寫在函式中,於是這裡將 percentilest_context_t 結構中宣告。

/* 作者宣告 */ 
typedef struct {
  int64_t *ticks;
  int64_t *exec_times;
  uint8_t *input_data;
  uint8_t *classes;
  dudect_config_t *config;
  ttest_ctx_t *ttest_ctxs[DUDECT_TESTS];
  int64_t *percentiles;  <------
} dudect_ctx_t;
typedef struct {
    double mean[2];
    double m2[2];
    double n[2];
+   int64_t *percentiles;
} t_context_t;

再將相關程式引入到專案中,詳細修改在 commit 中。

測試結果

加入了 percentiles 的實作後,測試都能在 constant time 內完成。

---	Trace		Points
+++ TESTING trace trace-17-complexity:
# Test if time complexity of q_insert_tail, q_insert_head, q_remove_tail, and q_remove_head is constant
Probably constant time
Probably constant time
Probably constant time
Probably constant time
---     trace-17-complexity     5/5
---	TOTAL		5/5