Try   HackMD

2025q1 Homework1 (lab0)

contributed by < horseface1110 >
{%hackmd NrmQUGbRQWemgwPfhzXj6g %}

開發環境

$ gcc --version
gcc (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0
$ lscpu
Architecture:            x86_64
  CPU op-mode(s):        32-bit, 64-bit
  Address sizes:         40 bits physical, 48 bits virtual
  Byte Order:            Little Endian
CPU(s):                  1
  On-line CPU(s) list:   0
Vendor ID:               GenuineIntel
  Model name:            QEMU Virtual CPU version 2.5+
    CPU family:          15
    Model:               107
    Thread(s) per core:  1
    Core(s) per socket:  1
    Socket(s):           1
    Stepping:            1
    BogoMIPS:            5199.99
    Flags:               fpu de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush mmx fxsr sse sse2 syscall nx lm constant_tsc nopl xtopo
                         logy cpuid tsc_known_freq pni ssse3 cx16 sse4_1 sse4_2 x2apic popcnt aes hypervisor lahf_lm cpuid_fault pti
Virtualization features:
  Hypervisor vendor:     KVM
  Virtualization type:   full
Caches (sum of all):
  L1d:                   32 KiB (1 instance)
  L1i:                   32 KiB (1 instance)
  L2:                    4 MiB (1 instance)
  L3:                    16 MiB (1 instance)
NUMA:
  NUMA node(s):          1
  NUMA node0 CPU(s):     0
Vulnerabilities:
  Itlb multihit:         KVM: Mitigation: VMX unsupported
  L1tf:                  Mitigation; PTE Inversion
  Mds:                   Vulnerable: Clear CPU buffers attempted, no microcode; SMT Host state unknown
  Meltdown:              Mitigation; PTI
  Spec store bypass:     Vulnerable
  Spectre v1:            Mitigation; usercopy/swapgs barriers and __user pointer sanitization
  Spectre v2:            Mitigation; Retpolines, STIBP disabled, RSB filling
  Srbds:                 Not affected
  Tsx async abort:       Not affected

針對佇列操作的程式碼實作

q_free

commit：76f27e2

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

發現list.h有一個function：q_release_element，之前忘記檢查head是否為空，新增

if (!head || list_empty(head)) {
        free(head);
        return;
    }

q_insert_head

commit：9359749
一開始的用list_empty()檢查是否為空，新分配空間後，再檢查是否有成功分配，最後用list_add添加節點在頭部。
但發現無法正確執行插入，我想是沒有檢查是否成功放入值到新的節點
所以新增了檢查的函式。

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

q_remove_head

commit：f8f5cf2

  • 實作細節：
    移除並返回鏈結串列的第一個節點（head->next）。
    若提供了 sp，則將該節點的 value 字串複製到 sp 中。
  • 問題：一開始看不懂sp要做什麼

q_insert_tail、q_remove_tail

commit：c2cd219
inser_tail跟remove_tail是一起做的

  • 功能描述：

    • q_remove_head() 與 q_remove_tail() 分別負責從雙向循環鏈結串列的頭部與尾部移除元素。若有提供 sp 緩衝區，則會將被移除節點的字串值安全地複製至 sp。

  • 實作細節：

    • 空串列檢查：在移除前，會先檢查鏈結串列是否為空，避免對空串列進行操作。
    • 字串值複製：若提供了 sp 且節點的值不為空，會使用安全的字串複製方式，確保不會超出緩衝區大小，並保證字串結尾為 '\0'。
    • 移除節點：透過 list_del() 將目標節點從鏈結串列中移除，並確保鏈結結構的正確性。
    • 節點返回：函式會返回已移除的節點指標，供外部進行記憶體釋放或後續處理。

q_delete_mid

Commit：6f51bb3

  • 實作細節：
    • 功能：刪除雙向循環鏈結串列中的中間節點，成功返回 true，否則返回 false。
    • 檢查 head 是否為空或空串列。
    • 使用快慢指標找到中間節點。
    • 移除節點並釋放 value 和節點記憶體。

邏輯重點：偶數個節點的話，是刪除正中間的下一個，一開始寫錯，會抓到前一個

q_sort

commit：f2e792f

  • 會用到q_size…
  • 實作細節：
    這段程式碼實作了雙向循環鏈結串列的歸併排序，主要包含以下函式：
    • compare()
      比較兩個節點的值，根據 descend 判斷排序方向（遞減或遞增）。
    • merge()
      合併兩個已排序的鏈結串列，並維持 prev 和 next 的正確連接，最後恢復循環結構。
    • q_merge_two_lists()
      使用遞迴將鏈結串列分割為左右兩部分，分別排序後再合併。
    • q_sort()
      主排序函式，檢查特殊情況、暫時斷開循環、執行遞迴排序，最後恢復循環鏈結。
      重點：確保每次分割與合併後，鏈結串列的 prev 和 next 指標正確，避免結構損壞或無窮遞迴。
  • 遇到的問題：
    • 起初的compare function沒有固定好回傳ture / false分別代表什麼，後來大改。
    • q_merge_two_lists()一開始沒有做好分割串列，導致分割後的串列仍舊相連，在執行時出現無窮迴圈
    • merge()：邏輯錯誤，導致出現segmentation fault，最後使用pointer to pointer編寫。
    • 最大的問題！！即使沒有呼叫q_size()，但還是會用到，我q_size()沒有先寫，

merge

struct list_head *merge(struct list_head *left, struct list_head *right, bool descend){
    left->prev->next = NULL;
    right->prev->next = NULL;

    struct list_head *head = NULL, *ptr = head, *current = head;
    /*head 是 dummy node，ptr是目前被移出的節點，current是新串列的尾巴*/

    while(left && right){
        if(compare(left, right, descend)){
            ptr = left;
            left = left->next;
            list_del_init(ptr);
            current->next = ptr;
            ptr->prev = current;
            current = current->next;
            
        }else{
            ptr = right;
            right = right->next;
            list_del_init(ptr);
            current->next = ptr;
            ptr->prev = current;
            current = current->next;
        }
    }
    if(left){
        current->next = left;
    }else{
        current->next = right;
    }
    return head;

}

segmetation fault

q_ascend、q_descend

Commit：8feb2a4

  • 實作細節：

    • 此函式從右往左遍歷雙向循環鏈結串列，刪除右側存在更大值的節點。先檢查串列是否為空或僅有一個節點，若是則直接返回。遍歷時，從倒數第二個節點開始，max 初始化為最後一個節點。若當前節點小於 max，則刪除並釋放記憶體；否則更新 max。遍歷至 head 為止，最後返回 0 表示完成。

  • 困難：

    • 一開始用current = head並在迴圈中current = current->prev，不直觀，改為head = head->prev->prev
    • 原本手刻element_t釋放節點，後來發現q_release_element
    • 直接從倒數第二個開始檢查，若大於等於max，保留並更新max；小於max，則刪除
      但會遇到
l = [c a d c b a]
cmd> descend
l = [ ... ]
ERROR:  Queue has more than 0 elements
Freeing queue

更改為return q_size(head)即可

q_reverse_segment

  • 目標：反轉一個區間內的節點順序
  • 排序：
    • 先使用 q_sort() 對鏈結串列進行排序，確保相同元素相鄰，便於後續判斷重複。
    • 歷與判斷：使用遍歷邏輯依序比對相鄰節點的值：
    • 發現重複時，刪除該節點，並標記當前為重複狀態。
    • 遇到重複結尾時，將標記為重複的起始節點刪除，確保所有重複元素被移除。
    • 記憶體釋放：每次刪除節點時，確保釋放其佔用的記憶體，避免洩漏。
  • 困難：因為輸入的第一個節點也是需要被反轉的，所以不能用以前的head->next邏輯當第一個節點。在這邊錯了蠻多次的

q_reverse

直接使用q_reverseK

q_reverseK

Commit：853e3cd




-   struct list_head *start = NULL, *end = NULL, *current = NULL;

+   struct list_head *start = head, *end = NULL, *current = start;

遇到segmentation fault
發現：index = 0 要放在 index == k 時
current會指向現在檢查到的最後一個，但 q_reverse_segment後，他指向的node不變，導致錯誤

q_merge

q_merge一次合併兩個queue，直到全部都合併完，使用了merge_lists_with_sentinel_node，前半部分跟merge很像，但不用斷頭，直接用L1的頭當回傳的頭，最後把L2的頭初始化
##3 q_descend
直接從倒數第二個開始檢查，若大於等於max，保留並更新max；小於max，則刪除
但會遇到

l = [c a d c b a]
cmd> descend
l = [ ... ]
ERROR:  Queue has more than 0 elements
Freeing queue

更改為return q_size(head)即可

q_delete_dup

Commit：853e3cd

  • 實作細節：
    • 排序：先使用 q_sort() 對鏈結串列進行排序，確保相同元素相鄰，便於後續判斷重複。
    • 遍歷與判斷：使用遍歷邏輯依序比對相鄰節點的值：
    • 發現重複時，刪除該節點，並標記當前為重複狀態。
    • 遇到重複結尾時，將標記為重複的起始節點刪除，確保所有重複元素被移除。
    • 記憶體釋放：每次刪除節點時，確保釋放其佔用的記憶體，避免洩漏。
  • 錯誤：
queue.c:152:43: error: passing argument 1 of ‘strcmp’ makes pointer from integer without a cast [-Werror=int-conversion]
  152 |         if(*entry->value != head & strcmp(*entry->value, *safe->value) == 0){
      |                                           ^~~~~~~~~~~~~
      |                                           |
      |                                           char

Strcmp的參數為指標
錯誤：

queue.c:152:26: error: comparison between pointer and integer [-Werror]
  152 |         if(*entry->value != head & strcmp(*entry->value, *safe->value) == 0){

*entry->value 改為 entry->list.next
錯誤：

queue.c:161:22: error: passing argument 1 of ‘list_del’ from incompatible pointer type [-Werror=incompatible-pointer-types]
  161 |             list_del(entry);
      |                      ^~~~~
      |                      |
      |                      element_t *

list_del(entry->list.next->prev);，目標：移除當下的node
最後：需要先sort才能使用
錯誤：

l = [b r b r b r a]
cmd>
cmd> dedup
ERROR: Duplicate strings are in queue or distinct strings are not in queue
l = [a]
Freeing queue

swap

/* Swap every two adjacent nodes */

void q_swap(struct list_head *head)

{

    // https://leetcode.com/problems/swap-nodes-in-pairs/

    q_reverseK(head, 2);

}

reverseK修好就好了

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

lab0 dudect程式碼的缺陷

Commit 156c254
rebase後，commit 遇到問題，說是printf出壞東西

oloomb@oloomb:~/linux2025/tmp/tmp/lab0-c$ git commit -a
--- modified dudect/fixture.c
+++ expected coding style
@@ -75,7 +75,7 @@ static void update_statistics(const int6
         /* do a t-test on the execution time */
         t_push(t, difference, classes[i]);
     }
-}
+}

 static bool report(void)
 {
[!] dudect/fixture.c does not follow the consistent coding style.

Make sure you indent as the following:
    clang-format -i dudect/fixture.c

Following files were changed:
  - dudect/fixture.c : 1 insertions(+), 1 deletions(-)
Running fmtscan...
No dictionary found.

[!] Check format strings for spelling

執行sudo apt install wamerican後問題解決，是他的字典

原本的diot中沒有先進行排序，就直接進入update_statistics，導致依據這些閾值裁剪的操作失準。這會使得統計上下文中 t 值、t_cropped 的數據累計出錯，進而導致最終的 t-test 結果不可靠，也就是說可能錯誤判定目標函式是否具有常數時間行為。所以我在這邊加了一個排序prepare_percentiles(exec_times);，但出現segmentation fault ，我猜想問題是在使用 t_cropped 或 t_second_order 前，沒有分配及初始化它們導致的。

static void init_once(void)
{
    init_dut();
    t_init(t);
+    for (size_t i = 0; i < DUDECT_NUMBER_PERCENTILES; i++) {
+        t_cropped[i] = malloc(sizeof(t_context_t));
+       if (!t_cropped[i]) die();
+        t_init(t_cropped[i]);
+    }
+    t_second_order = malloc(sizeof(t_context_t));
+    if (!t_second_order) die();
+    t_init(t_second_order);
}

Commit db4bd7b
雖然這樣可以通過測驗，但我心裡不踏實，因為只對exec_time排序，讓exec_time和classes脫鉤了。所以我改了prepare_percentiles，用結構保存 exec_times 與 classes 的對偶型別

typedef struct {
        int64_t exec_time;
        uint8_t cls;
    } pair_t;

再把有效區間複製資料到 pairs 陣列，排序完後再更新原始陣列

Last changed by 
 
horseface1110
0
77

Read more

2025q1 Homework2 (quiz1+2)

contributed by &lt; horseface1110 &gt;

Mar 26, 2025
linux2025-ideas

Mar 10, 2025
Read more from horseface1110
Published on HackMD