2025q1 Homework2 (quiz1+2)

< Urbaner3 >

連結與參少材料

week1 week2 2025q1 第 1 週測驗題

week1

quiz 1

先說明題目，包含一個單向的鏈結串列原型，程式碼，稱作 list.h 和 quiz1a.c 。把 list_t, list_item_t 定義放在 list.h 裡面。仔細看有兩個函式， list_size 和 list_insert_before 。再跟據 macro 拆解程式碼， main 進行文字互動函式 test_suite 會配合 macro 進行一連串的測試就是 test_list 代表的內容。用 gcc 生成 quiz1a.i 程式碼

參考雙倍指標，linked lisr 下方約八個段落 void append(int value, list_entry_t **head) 類似 list_insert_before ，後者的 p 相當於前者的 direct 變量，找到 before 停下來。注意迴圈用法，對應相反邏輯的條件。l 是指向 head 的開頭物件， item 是 new。可推算 AAAA, BBBB, CCCC。
雙倍指標，打包再打包的概念，包起 dereference 的內容。不管哪種都會讓串列變成樹。一個追趕的演算法，只是追和被追有沒有用 next 連在一起而已。下方有示意圖。^[1]; ^[2]。或說，讓 *p 指標用來存取所有的 next，另外，prev 也可以用類似的操作。雙指標不是物件的指標，是走遍指標的指標變數。

for (p = &l->head; *p != before; p = &(*p)->next);
l->1  2   3   4   5   6  7  8
           be->
          *p->
          *p->it
l->1  2   3   4   5   6  7  8
	  .->it
	  it->4
l->1  2   3   it  4   5  6  7  8

虛線做法說明

reset: *p := 3->next = it
reset: it := item->next = before

AAAA = &l->head
BBBB = before
CCCC = &(*p)->next
DDDD = item->next
都和教材 append 的程式碼相對應，只有 DDDD 是新增的。

解釋上方程式碼運作原理

善用 gcc -E quiz1a.c > quiz1a.i, gcc -g -o quiz1a quiz1a.c 處理錯誤。因為有兩個巨集，影響預編譯的結果。而且是合成影響。
main -> test_suite -> [my_run_test(test_list);] = do-while(0) -> [test()] = test_list()
說真的，一步到位我還是有點暈，但預處理器成功了。test_list 函式有三步驟。

測試開頭插入

像堆疊一樣，倒數插入 items[i] ，從 i=0 到 999，但都插入在開頭，所以從開頭會是 999 數回 0。在 list_insert_before 函式執行之前， list_reset 只是建立節點，沒有串聯成串列，所有節點都是孤單的節點。注意 do-while(0) 是假迴圈，因為不會重複執行，只剩下名字。理頭都是預留給可能的錯誤，去判斷並回傳錯誤。如果 test_list 結束，測試成功回傳 NULL。

其他兩段測試

其實仔細看，只有一個測試，最後一段是類似測試但實作。一次說明，這次插入尾端，從 0 到 9999 。檢察長度，和各節點數值。就結束了。輸出測試成功， run 次數 1，一次成功，一杆進洞。那個巨集是模仿 assert 和 printf 實作的。最後的 return !!result; 注意是字串對布林變數的 1, 0 真假反轉。用 felo search 有詳細說明，容易邏輯死亡，小心服用。摘錄一段：

In C, the expression return !!NULL; involves the use of the logical NOT operator (!) applied twice to the NULL macro.

在現有的程式碼基礎上，撰寫合併排序操作

嘗試運用 macro 測試在 static list_t *list_setup 函式中，但 macro 會被預處理的 return 影響，就算另外新增變數儲存也沒辦法。這是設計的問題。我發現我函式呼叫，即使不傳回串列頭的指標，初始構建和測試仍然可行。於是修改回傳型別配合 macro ，也算是發現 macro 的一大缺點。

test point chosen

context:

#0  list_size (mylist=0x55555555bee0 <l>) at quiz1a.c:90
#1  0x000055555555532b in test_list () at quiz1a.c:55
#2  0x0000555555555422 in test_suite () at quiz1a.c:78
#3  0x00005555555554f5 in main () at quiz1a.c:107

當有錯務時，回報機制在位址的錯誤，沒有辦法存取到。應該說是分頁錯誤的問題， gdb 可以讀取錯誤訊息，但是被 printf 的錯誤訊息中斷了。也就是兩個都要回傳，但不能同時回傳。

517	./stdio-common/vfprintf-internal.c: No such file or directory.
(gdb) frame 3
#3  0x000055555555569e in main () at merge.c:137
137	    printf("ERROR: %s\n", result);
(gdb) p result
$7 = 0x5 <error: Cannot access memory at address 0x5>
(gdb) type result
Undefined command: "type".  Try "help".
(gdb) ptype result
type = char *
(gdb) p *result
Cannot access memory at address 0x5

# second test

(gdb) where
#0  list_size (mylist=0x55555555bfb8 <lsa>) at merge.c:90
#1  0x000055555555526a in list_setup (l=0x55555555bfb8 <lsa>, 
    l_items=0x55555555bf00 <a_items>, length=5, array=0x7fffffffd7e0)
    at merge.c:24
#2  0x0000555555555678 in main () at merge.c:135
(gdb) l
85	  list_item_t *curr;
86	  curr = mylist->head;
87	  int count = 0;
88	  while (curr) {
89	    count++;
90	    curr = curr->next;
91	  }
92	  return count;
93	}
94	
(gdb) p count
$1 = 1
(gdb) p curr
$2 = (list_item_t *) 0x55555555bf00 <a_items>
(gdb) p curr->next
$3 = (struct list_item *) 0x55555555bf10 <a_items+16>
(gdb) p curr->next->next
$4 = (struct list_item *) 0x55555555bf20 <a_items+32>
(gdb) p *curr->next->next
$5 = {value = 5, next = 0x55555555bf30 <a_items+48>}

修改程式碼，前置處理器部分：

#define setup_run_test(test, l, l_items, length, array) \
    do {                                               \
        char *message = test(l, l_items, length, array); \
        tests_run++;                                   \
        if (message)                                   \
            return message;                            \
    } while (0)

並對 list_setup 加上 return NULL，完成回傳值，如果通過測試的話。原來直接輸入參數就可以但一定要注意資料的層數，結構都必須是全域的。

_GI__IO_puts (str=0x5555555560ac "ALL TESTS of List PASSED") at ./libio/ioputs.c:33
33	./libio/ioputs.c: No such file or directory.
(gdb) 
35	in ./libio/ioputs.c
(gdb) 
__strlen_avx2 () at ../sysdeps/x86_64/multiarch/strlen-avx2.S:50
50	../sysdeps/x86_64/multiarch/strlen-avx2.S: No such file or directory.

如果 printf 正常的話，用 cont, step, until N, 跳過迴圈和一些步驟。完成偵錯程序。

quiz 2

code
為了最高效率，參考 GPT 的解釋，關於二元樹，我也會參考演算法網站，想清楚再作答。
The provided code snippet outlines a structure and function prototypes for managing memory allocation using a binary search tree (BST) approach. This method is often utilized in memory allocators to efficiently manage free memory blocks. Below is a detailed explanation of the code structure and its relevance to Linux memory management.
Code Structure Explanation

Structure Definition:

The block structure represents a memory block in the allocator. It contains:

size: The size of the memory block.
l and r: Pointers to the left and right children in the binary search tree, respectively. This allows the blocks to be organized in a way that facilitates efficient searching, insertion, and deletion.

Function Prototypes:

find_free_tree(block_t **root, block_t *target): This function is likely intended to locate a specific free block in the tree based on the target block.
find_predecessor_free_tree(block_t **root, block_t *node): This function may be designed to find the predecessor of a given node in the tree, which is useful for operations like deletion or rebalancing.

Memory Management:

The remove_free_tree(block_t **root, block_t *target) function is intended to remove a specified block from the free tree. The implementation details are not provided, but typically, this would involve finding the target block in the tree and adjusting pointers to maintain the BST properties.

This code implements a simple binary tree data structure specifically designed for managing "free" blocks of memory. Here's a higher-level overview of its functionality:

Tree Structure: The block_t structure represents a node in the binary tree. Each node contains the size of the block and pointers to its left and right children.

Finding Nodes: The find_free_tree function (not fully provided) is supposed to locate a node in the tree that matches a given target block.

Removing Nodes: The main function, remove_free_tree, is responsible for removing a specified block from the tree. It handles three cases:

If the node has both children, it finds its in-order predecessor (the largest node in the left subtree) to replace it.
If the node has only one child, it directly replaces the node with its child.
If the node is a leaf (no children), it sets the pointer to NULL, effectively removing it from the tree.
Assertions: Throughout the code, assertions are used to ensure that operations maintain the tree's integrity, checking that nodes are not incorrectly linked after removals.

Memory Management: After a block is removed from the tree, its left and right pointers are set to NULL to prevent dangling pointers.

Overall, this code is designed to efficiently manage dynamic memory blocks by maintaining a structured representation of free memory in a binary tree format.

Just BST helo_algo 演算法筆記

參考 bevmmf 同學的作業才知道，自己狀況不佳。蠻大起大落的，簡單明瞭的和複雜無比的，對我來講，我是沒有在區分的，這特質有好壞，但就善用吧。這是一份基礎的二元樹作業，我心裡卻覺得好像是記憶體的說明佔了大量地篇幅，總之簡單地事情，簡單明瞭的處理即可。

此題背景為 dyynamic memory allocator 的實現，特別是顯式配置器（explicit allocator）。allocator 必須滿足多個條件，包括處理任意請求序列、立即滿足需求、僅使用heap空間、確保地址對齊（例如 32 位系統為 8 位元組對齊，64 位系統為 16 位元組對齊），並且不得修改已配置的區塊。目標是在吞吐率（單位時間內完成的配置和釋放請求數量）和空間利用率（𝑈𝑘=𝑚𝑎𝑥𝑖<𝑘 𝑃𝑖𝐻𝑘 ，其中
𝑃𝑖 是過去請求的有效荷載總和，𝐻𝑘 是目前heap大小）之間找到平衡。為了提升空間區域性（spatial locality），allocator利用分頁（paging）特性，確保每個分頁僅存放特定大小類別（size-class）的空間，避免自由區塊地址分散導致效能下降。此題背景為 dyynamic memory allocator 的實現，特別是顯式配置器（explicit allocator）。allocator 必須滿足多個條件，包括處理任意請求序列、立即滿足需求、僅使用heap空間、確保地址對齊（例如 32 位系統為 8 位元組對齊，64 位系統為 16 位元組對齊），並且不得修改已配置的區塊。目標是在吞吐率（單位時間內完成的配置和釋放請求數量）和空間利用率（，其中 𝑃𝑖 是過去請求的有效荷載總和，𝐻𝑘 是目前heap大小）之間找到平衡。為了提升空間區域性（spatial locality），allocator利用分頁（paging）特性，確保每個分頁僅存放特定大小類別（size-class）的空間，避免自由區塊地址分散導致效能下降。，其中 𝑃𝑖 是過去請求的有效荷載總和，𝐻𝑘 是目前heap大小）之間找到平衡。為了提升空間區域性（spatial locality），allocator利用分頁（paging）特性，確保每個分頁僅存放特定大小類別（size-class）的空間，避免自由區塊地址分散導致效能下降。

為什麼選擇 BST 架構實作allocator?

能夠快速搜尋合適區塊，向左或右。
支援動態操作
可擴展性

補充連結提供了，各種資料結構的記憶體分配方式，讓我受教了。

quiz 3

optimized quick sort; related to w2 quiz1
24q1a zone vax-r 這是去年一樣的題目，可以得到填空題答案。就不一一贅述。從為什麼改良快速排序的原因討論，它多了左右兩個陣列，節省步驟。不過有個問題，就是取捨，分裂少，快但有未移動。分裂多，慢但保證排序完整。加上從範例推測， pivot 取離平均遠一些可能排序較完整。他是單和 pivot 比。
鏈結串列的圖解，這裡可以用分號區隔節點，而不是箭號，讓人覺得是一整個結構。

整理，補完：參考：[https://hackmd.io/@bevmmf/linux2025-homework2]
再參考，eric 同學的作業，

我欣賞它點出疑惑再開始寫作業，我常常容易有疑惑，卻不是把它整理下來，進一步思考問題，而是混亂，找不到重點，或續這是我作業和考試沒有進展理由的之一吧。

list_entry(pivot, node_t, list)->value; // HHHH

week2

quiz 1

quick sort
linux
class_text

AAAA= list_first_entry
BBBB=list_del
CCCC=list_move
DDDD=list_move(
EEEE=list_splice_tail_init
FFFF=list_splice_init
ana_Mickey
Shan

quiz 2

開平方根運算 clz2()
試看

tech

次重要想想，clz fib kernel hw

#include <stdio.h>
#include <stdint.h>

#define clz32(x) clz2(x, 0) // Macro to start the count

// Filled in constants to get the desired output
static const int mask[] = {0, 8, 12, 16};   // GGGG = 16
static const int magic[] = {0, 1, 0, 5};    // HHHH = 0, IIII = 5

unsigned clz2(uint32_t x, int c) {
    if (!x && !c)
        return 32; // If both x and c are zero, return 32 (all bits are zero)

    uint32_t upper = (x >> (16 >> c)); // Shift x to get upper bits
    uint32_t lower = (x & (0xFFFF >> mask[c])); // Get lower bits using mask

    if (c == 3) // JJJJ = 3
        return upper ? magic[upper] : 4 + magic[lower]; // KKKK = 4
    return upper ? clz2(upper, c + 1) : (16 >> c) + clz2(lower, c + 1); // LLLL = 1
}

int main() {
    printf("clz32(0x00000F00) = %u\n", clz32(0x00000F00)); // Expected output: 20
    printf("clz32(0x00000001) = %u\n", clz32(0x00000001)); // Expected output: 31
    return 0;
}

Summary of Changes:
GGGG: Changed to 16 to allow the upper bits to shift correctly.
HHHH: Changed to 0 to handle cases appropriately in the magic array.
JJJJ: Changed to 3 for the branching logic.
KKKK: Set to 4 in the return statement calculation.
LLLL: Set to 1 to properly manage recursion depth handling.
With these constants, your function should now produce the expected output. Compile and run the code to see the results!

idea:

MMMM: ~1 (bitwise NOT of 1). This mask ensures that you keep everything but the least significant bit.
NNNN: Since we're shifting y right by one bit each iteration of the loop, this should be 1, which will effectively divide y by 2 on each iteration.
PPPP: For m in the loop, since you're halving it each time, you can set this to 1 as well, meaning you will also right shift m by one bit.

我重新回去看，<bitwise> ，比如題目註解有 set bit 我沒有注意是增加位元的意思。邏輯和直覺沒有連結，這樣子會不順，不行。有三種 mask ，再想想 magic 是什麼？並且實測發現 cond ? A : B 如果 cond 是一個變數，那變數為零的時候，判斷為真，執行A選項，注意是零為真，跟邏輯的判斷不一樣。
與朋友<jouae>討論後半開根號計算之後，結論是，這個來源於 linux_kernel ，他提到多次的減法和右移，模擬減法，我無法理解所以先測試結果。

Initial: x=25, y=0, m=16
Iteration 1: b=16, y=0, x≥b so x=9, y=16, m=4
Iteration 2: b=20, y=8, x<b so no change to x, m=1
Iteration 3: b=9, y=4, x=b so x=0, y=5, m=0
Result: 5
63 in binary is 111111, so clz64(63) = 64 - 6 = 58
shift = (64 - 1 - 58) & ~1 = 5 & ~1 = 4 (this ensures shift is even)
m = 1ULL << 4 = 16
Iteration 1: b=0+16=16, y=0>>1=0, 63≥16 so x=63-16=47, y=0+16=16, m=16>>2=4
Iteration 2: b=16+4=20, y=16>>1=8, 47≥20 so x=47-20=27, y=8+4=12, m=4>>2=1
Iteration 3: b=12+1=13, y=12>>1=6, 27≥13 so x=27-13=14, y=6+1=7, m=1>>2=0
Loop exits, return y=7
1048576 = 2^20, so clz64(1048576) = 64 - 21 = 43
shift = (64 - 1 - 43) & ~1 = 20 & ~1 = 20 (already even)
m = 1ULL << 20 = 1048576
Following through the algorithm, we should get 1024

但實測結果是 3和 1023 而不是 7和 1024 這說明這個演算法是 floor 不是 ceiling 。我又打 sqrti(65) = 8 確認了。
Commit 30493cc 說這個奇怪的算法是費曼流傳下來的，還留了一個維基的連結，嗯，這下有意思了。我用 blame 看到的。

quiz 3

two sum, Hash table. 22q1 w1qz1 freshLiver, Risheng, qwe661234, Destiny0504

參考實驗, material 瞭解，這裡直接書寫我的意見和看法。

AAAA = map->bits
AAA = n->next = first;
BBBB = map->bits
CCCC = first->pprev
BBB : n->pprev= &h->first;
DDDD = n->pprev next or pprev
EEEE = n->pprev;

graphiz 範例：

blocks ↩︎
line_text ↩︎

2025q1 Homework2 (quiz1+2)

連結與參少材料

week1

quiz 1

解釋上方程式碼運作原理

測試開頭插入

其他兩段測試

在現有的程式碼基礎上，撰寫合併排序操作

test point chosen

quiz 2

為什麼選擇 BST 架構實作allocator?

quiz 3

week2

quiz 1

quiz 2

quiz 3

graphiz 範例：

Read more

2025w17 Taigibun

2025q1 Homework5 (assessment)

藍圖

2025q1 list sort analysis