2024q1 Homework1 (lab0)

contributed by < Terry7Wei7 >

Reviewed by vax-r

• 未完成任何指定事項
• github repository 未提交任何 commmit

Reviewed by vestata

1. github repository 未提交 commit
2. Git 命令筆記與此開發紀錄無直接相關，故可省略。
3. 在開發紀錄中應使用 diff 標示修改過的程式碼。

問題

筆電安裝雙系統（windows/ubuntu_linux）

因後續檢視perf需求,故重新安裝ubuntu22.04

前置作業

$ gcc --version
gcc (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0
Copyright (C) 2021 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:         45 bits physical, 48 bits virtual
  Byte Order:            Little Endian
CPU(s):                  2
  On-line CPU(s) list:   0,1
Vendor ID:               GenuineIntel
  Model name:            Intel(R) Core(TM) i7-6700HQ CPU @ 2.60GHz
    CPU family:          6
    Model:               94
    Thread(s) per core:  1
    Core(s) per socket:  1
    Socket(s):           2
    Stepping:            3
    BogoMIPS:            5183.99

cppcheck version

terry@terry-virtual-machine:~$ cppcheck --version
Cppcheck 2.7

複製 id_rsa 到剪貼簿

$ cat ~/.ssh/id_rsa.pub | xclip -selection clipboard

git 命令筆記

命令	作用
git init	初始化一個新的 Git 儲存庫。
git clone <repository>	複製一個遠端儲存庫到本地。
git add <filename>	將檔案的變更添加到暫存區。
git add .	將所有檔案的變更添加到暫存區。
git commit -m "Commit message"	提交暫存區的變更到本地儲存庫。
git status	檢查儲存庫的狀態，顯示已修改、已追蹤、未追蹤等檔案的狀態。
git log	顯示提交的歷史記錄。
git log -p	顯示提交的歷史記錄，包括每次提交的詳細差異。
git shortlog	生成一個簡化的提交歷史報告，按照作者進行分組。
git branch	顯示本地分支列表。
git branch <branch_name>	建立新分支。
git checkout <branch_name>	切換到指定的分支。
git merge <branch_name>	合併指定分支到目前分支。
git pull	從遠端儲存庫拉取最新的變更。
git push	推送本地變更到遠端儲存庫。
git diff	顯示工作目錄與暫存區之間、暫存區與最後提交之間的差異。
git reset HEAD <filename>	取消對指定檔案的暫存。
git rm <filename>	從工作目錄和暫存區中刪除檔案。
git mv <old_filename> <new_filename>	更改檔案名稱。
git blame <filename>	逐行顯示指定檔案對應的最新修改是由誰進行及其提交資訊。
git revert <commit_sha>	建立一個新的提交，該提交會撤銷之前的一次或多次提交的變更。
git rebase <base_branch>	用於將一個分支的修改應用到另一個分支。
git show <commit_sha>	顯示一個特定提交的詳細信息，包括提交的作者、日期、變更的文件、差異等。

補齊指定的佇列操作

牛刀小試

make test
scripts/driver.py -c
---	Trace		Points
+++ TESTING trace trace-01-ops:
# Test of insert_head and remove_head
Segmentation fault occurred.  You dereferenced a NULL or invalid pointer---	trace-01-ops	0/5
+++ TESTING trace trace-02-ops:
# Test of insert_head, insert_tail, remove_head, remove_tail, and delete_mid
Segmentation fault occurred.  You dereferenced a NULL or invalid pointer---	trace-02-ops	0/6
+++ TESTING trace trace-03-ops:
# Test of insert_head, insert_tail, remove_head, reverse and merge
Segmentation fault occurred.  You dereferenced a NULL or invalid pointer---	trace-03-ops	0/6
+++ TESTING trace trace-04-ops:
# Test of insert_head, insert_tail, size, swap, and sort
Segmentation fault occurred.  You dereferenced a NULL or invalid pointer---	trace-04-ops	0/6
+++ TESTING trace trace-05-ops:
# Test of insert_head, insert_tail, remove_head, reverse, size, swap, and sort
Segmentation fault occurred.  You dereferenced a NULL or invalid pointer---	trace-05-ops	0/6
+++ TESTING trace trace-06-ops:
# Test of insert_head, insert_tail, delete duplicate, sort, descend and reverseK
Segmentation fault occurred.  You dereferenced a NULL or invalid pointer---	trace-06-ops	0/6
+++ TESTING trace trace-07-string:
# Test of truncated strings
Segmentation fault occurred.  You dereferenced a NULL or invalid pointer---	trace-07-string	0/6
+++ TESTING trace trace-08-robust:
# Test operations on empty queue
ERROR: Computed queue size as -1, but correct value is 0
---	trace-08-robust	0/6
+++ TESTING trace trace-09-robust:
# Test remove_head with NULL argument
Segmentation fault occurred.  You dereferenced a NULL or invalid pointer---	trace-09-robust	0/6
+++ TESTING trace trace-10-robust:
# Test operations on NULL queue
---	trace-10-robust	6/6
+++ TESTING trace trace-11-malloc:
# Test of malloc failure on insert_head
Segmentation fault occurred.  You dereferenced a NULL or invalid pointer---	trace-11-malloc	0/6
+++ TESTING trace trace-12-malloc:
# Test of malloc failure on insert_tail
Segmentation fault occurred.  You dereferenced a NULL or invalid pointer---	trace-12-malloc	0/6
+++ TESTING trace trace-13-malloc:
# Test of malloc failure on new
---	trace-13-malloc	6/6
+++ TESTING trace trace-14-perf:
# Test performance of insert_tail, reverse, and sort
Segmentation fault occurred.  You dereferenced a NULL or invalid pointer---	trace-14-perf	0/6
+++ TESTING trace trace-15-perf:
# Test performance of sort with random and descending orders
# 10000: all correct sorting algorithms are expected pass
# 50000: sorting algorithms with O(n^2) time complexity are expected failed
# 100000: sorting algorithms with O(nlogn) time complexity are expected pass
Segmentation fault occurred.  You dereferenced a NULL or invalid pointer---	trace-15-perf	0/6
+++ TESTING trace trace-16-perf:
# Test performance of insert_tail
Segmentation fault occurred.  You dereferenced a NULL or invalid pointer---	trace-16-perf	0/6
+++ 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
ERROR: Probably not constant time or wrong implementation
ERROR: Probably not constant time or wrong implementation
ERROR: Probably not constant time or wrong implementation
ERROR: Probably not constant time or wrong implementation
---     trace-17-complexity     0/5
---	TOTAL		12/100
make: *** [Makefile:60: test] Error 1

q_new, q_free

 /* Create an empty queue */
 struct list_head *q_new()
 {
-    return NULL;
+    struct list_head *tmp = (struct list_head *) malloc(sizeof(*tmp));
+    if (!tmp) {
+        return NULL;
+    }
+    INIT_LIST_HEAD(tmp);
+    return tmp;
 }

/* Free all storage used by queue */
 /* Free all storage used by queue */
-void q_free(struct list_head *head) {}
+void q_free(struct list_head *l)
+{
+    if (!l)
+        return;
+
+    element_t *curr, *safe;
+    list_for_each_entry_safe (curr, safe, l, list) {
+        if (curr->value)
+            free(curr->value);
+        free(curr);
+    }
+    free(l);
+}

q_insert_head, q_insert_tail

 /* Insert an element at head of queue */
 bool q_insert_head(struct list_head *head, char *s)
 {
+    if (!head)
+        return false;
+
+    element_t *new_node = (element_t *) malloc(sizeof(*new_node));
+    if (!new_node)
+        return false;
+
+    size_t len = strlen(s);
+    new_node->value = (char *) malloc(sizeof(char) * (len + 1));
+    if (!new_node->value) {
+        free(new_node);
+        return false;
+    }
+
+    strncpy(new_node->value, s, len + 1);
+
+    list_add(&new_node->list, head);
     return true;
 }

q_remove_head, q_remove_tail

 /* Remove an element from head of queue */
 element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
 {
-    return NULL;
+    if (!head || head == head->next)
+        return NULL;
+    element_t *removed = list_entry(head->next, element_t, list);
+    if (sp) {
+        strncpy(sp, removed->value, bufsize);
+        sp[bufsize - 1] = '\0';
+    }
+
+    list_del(&removed->list);
+    return removed;
 }

I-HSIN Cheng
善用 diff 而非單純寫上 -, + 來表示程式碼更動，並且列出的更動應是優化的部分而非最初的實作。

---

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

### dudect 工具介紹： 用於評估代碼是否在給定平台上以恆定時間運行。 基於泄漏檢測技術，實現簡潔、易於使用和易於維護的工具。

計時攻擊和泄漏檢測：

計時攻擊是一種側信道攻擊，通過測量加密實現的執行時間來推斷密鑰或密碼等秘密信息。
泄漏檢測測試執行時間，檢查兩個不同輸入數據類別的執行時間分佈是否統計上不同。

泄漏檢測的步驟：

測量執行時間：重複測量加密函數的執行時間，使用兩個不同輸入數據類別。
後處理：對每個測量進行一些後處理，如裁剪或更高級別的預處理。
應用統計檢驗：使用統計檢驗檢查兩個定時分佈是否相等。

使用台灣慣用科技詞彙書寫，且該切合論文內容。

I-HSIN Cheng
TODO : 完成指令論文的閱讀和實驗