2024q1 Homework5 (assessment)

contributed by < jujuegg >

測驗題改進

第一周 / 測驗一

本測驗是在鏈結串列上實作 quick sort，且是非遞迴版本的，使用堆疊來模擬原本的遞迴呼叫。

優化方案

或許 begin 與 end 也可以用鏈結串列來儲存?

動機：程式利用 i 來存取這兩個陣列，但 i 在執行程式的過程中並不會大範圍跳躍，最多連續加 2 而已，可以避免宣告不必要的記憶體空間。

使用 Linux 核心風格的 List API 改寫

程式碼

首先把 quick_sort.h 裡面宣告的結構改成用 list_head，以及把上個作業的 list.h 拿過來使用，有些重複的函式就統一使用內建的 API。

  typedef struct __node {
-     struct __node *left, *right;
-     struct __node *next;
+     struct list_head list;
      long value;
  } node_t;

我建立了另一個結構 begin_t，它的作用是儲存那些尚未完成排序的串列的 「head」，然後再將此節點存入另一個鏈結串列中，並不像原本的程式碼是用陣列來模擬堆疊。原諒我不會取名。

typedef struct begins {
    struct list_head list;
    struct list_head *head;
} begin_t;

現在要使用 Linux 的 API，所以變數形態要更換，且因為使用雙向鏈結串列，所以不須留下 end。

- node_t *begin[max_level], *end[max_level];
- node_t *result = NULL, *left = NULL, *right = NULL;

+ struct list_head *begins = malloc(sizeof(struct list_head));
+ struct list_head *result = malloc(sizeof(struct list_head));
+ struct list_head *left = malloc(sizeof(struct list_head));
+ struct list_head *right = malloc(sizeof(struct list_head));
+ struct list_head *mid = malloc(sizeof(struct list_head));

一開始把整個串列的 head 放進 begins 中。
now 是用來模擬堆疊的 top 的位置。
begins 則是目前所有未完成排序的串列所在的堆疊。

begin_t *all = new_begin(*head);
list_add_tail(&all->list, begins);
    
struct list_head *now = begins->next;

now_entry_head 是這輪要處理的未完成排序的串列的 head。

struct list_head *now_entry_head = list_entry(now, begin_t, list)->head;

pivot 放入中間的串列。

node_t *pivot = list_first_entry(now_entry_head, node_t, list);
list_del(&pivot->list);
list_add(&pivot->list, mid);

中間將資料依照大小區分為 left 與 right 的過程因為與之前無異，所以省略不提。

因為要依序將 left、pivot、right 放入 begins 中，所以會需要額外在堆疊中增加 2 個節點，而 left 就會直接將目前正在處理排序的鏈結串列取代，分別 push pivot 和 right。
注意如果 left 或 right 裡沒有東西，也會需要 push 空串列的 head 進去。

// 1
list_splice_tail_init(left, now_entry_head);
INIT_LIST_HEAD(left);

// 2            
begin_t *mid_begin = new_begin(mid);
list_add_tail(&mid_begin->list, begins);
INIT_LIST_HEAD(mid);

// 3
begin_t *right_begin = new_begin(right);
list_add_tail(&right_begin->list, begins);
INIT_LIST_HEAD(right);

top 的指標往上 2 格。pop 時則是往下一格。

// push 2 elements into stack
now = now->next->next;
// pop 1 element out of stack
now = now->prev;

操作大致上是這樣，注意當要 pop begins 的節點時，由於內部是儲存鏈結串列的頭，所以要記得呼叫 list_free 來釋放記憶體空間。

實驗結果

• 原本的程式的記憶體用量

• 使用鏈結串列實作堆疊的記憶體使用量

在 100000 筆資料的情況下，用鏈結串列去實作堆疊可以節省約 0.8 MB 的記憶體。

閱讀心得 - 因為自動飲料機而延畢的那一年

「資工系的學生不會寫程式，機械系的學生不會做機械」，我覺得這句話在 2024 還是可以非常貼切的表達臺灣的教育，當然我並不是要把自己的無能推卸給這個教育體制，實際上我身邊還是有非常多厲害的人可以做出對世界有貢獻的事情。

我們在整個大學學了哪些東西？凡是資工人都能講出來的 6 個科目，不能否認這些知識是以後出社會開始解決問題的必備條件，但是就僅此而已。真正教你如何實際這些知識來創作的課程卻非常的少，這導致甚麼，我變得只會讀書，甚至也不能說得上是會讀書。

好，那我努力讀書，終於可以上成大研究所，成功躋身台灣頂大的的行列，結果嘞，修了 jserv 的課才發現自己根本就是個菜逼，看了那麼多 linux 的程式碼，那些以前從來沒看過的 API，還不是要從頭開始學。到了現在我終於知道，現在的我，就是一個不被社會需要的人。

那為甚麼會有這些問題呢，因為我以前都活在我的想像中，想像我可以憑藉學歷找到好工作養活自己，想像成大研究所的學歷超級有用，但是我活在現實世界啊，這裡不是遊戲，死掉不能重來，也不能刷首抽，因為我不是歐皇，我就是跟普通人一樣。

---

後來我逐漸明白，我除了要把我的專業研讀到極致，還需要了解其周邊跟其他領域有關的知識才有辦法讓一間公司願意讓我做事然後給我錢。舉例來說，做遊戲畫面的工程師會需要精通電腦繪圖等相關領域，但因為現在有 GPU 的存在，他也必需了解程式並行處理的機制，才有辦法讓他的程式最大化的使用硬體資源，並真正做到加速的效果。

我之前一直很抗拒學習跟我的專業無關的知識，但現在我知道，想要拉開跟別人的差距，就只能不斷的學習，並且做出一些「有用」的專案，擺爛是沒有用的。

---

但這件事本身是非常恐怖的一件事，簡單來說就是害怕失敗，我很常做一件事遇到瓶頸，且好一段時間想不出解決辦法的時候(就如文中作者遇到冰塊分配的問題)，就會開始思考自己是不是從一開始就走錯路了，但是頭都洗下去了，現在回頭還來的及嗎？

而且如果一遇到事情就想要逃避，以後出社會一定會遇到更多更棘手的問題，那以後遇到這些問題的時候，全部都要逃跑嗎，這樣自己要怎麼進步。

「你該學習的不是看到事情要完蛋了就去避免失敗，而是應該學習如何處理與承受失敗，你才能變得比以前更強大。」

失敗並不可怕，實際上你只會損失你付出的時間，金錢，精力，可是你可以從中學習到「成功」所無法獲得的東西。大家都說，失敗為成功之母，那些成功人士真的是一次失敗都沒經歷過就成功的嗎，可能或許真的有可能是吧，但我想清楚，自己根本不可能成為這種人，我能做的就只有從這些「失敗」中獲取經驗，才能拼湊出通往「成功」的道路。

沒有人想要失敗，我能做的只有努力，跟調整心態，讓自己認為這只是一個考驗。

---

「這個世界比任何人都殘酷，也比任何人都公平，犧牲了多少就會得到多少」，很多事情不是得不到，而是有沒有付出相對應的努力，自己一個人可以做到的事情非常有限，很多時候會需要別人的幫助，但是在渴望得到別人的幫助以前，自己必須要有所做為，要告訴別人幫忙的理由是甚麼。

付出不一定會有成果，但是沒有付出就沒有成果，雖然我從小就知道這個道理，但是我真正付諸行動的時間，又到底有多久呢。

研讀 課程教材

你所不知道的 C 語言：數值系統篇

balanced ternary

雖然使用平衡三進位可以很快速地轉換正負值，但對於加法來說是否會需要額外的步驟或硬體呢?

$(-1{)}_{10}=(00T{)}_{bal3}$

$(0{)}_{10}=(000{)}_{bal3}$

$(1{)}_{10}=(001{)}_{bal3}$

$(2{)}_{10}=(01T{)}_{bal3}$

$(3{)}_{10}=(010{)}_{bal3}$

$(4{)}_{10}=(011{)}_{bal3}$

$(5{)}_{10}=(1TT{)}_{bal3}$

$(6{)}_{10}=(1T0{)}_{bal3}$

$(7{)}_{10}=(1T1{)}_{bal3}$

$(8{)}_{10}=(10T{)}_{bal3}$

$(9{)}_{10}=(100{)}_{bal3}$

可以觀察到，各位元始終保持著

$T$ /

$0$ /

$1$ 的循環，原理與一般的加法器無異。

bitwise 加法操作

x + y = (x ^ y + (x & y) << 1) // 位元和 + 進位

實際上我們熟知的很多二元操作都可以使用 bitwise 的方式去達成，程式碼也會看起來更加簡潔。

DETECT 0 or \0

不知道為何要先「取得最低位元是否為 0 ，並將其他位元設為 1」，如果只是要抓到 32-bit 中，某 1 個 byte 的位置是不是 0 的話，那為何不直接反轉位元然後與 0xff 做 & 運算就好。

將你的想法實作出來再比較，記得要考慮有效的 uint32_t 範圍。 jserv

你所不知道的C語言：指標篇

void *

還是不太懂 void 指標存在的意義，既然我想要存取這個指標所指到的變數的值之前，都需要將指標轉型後才能使用，為何還需要多一個步驟？

如果是為了在宣告函式時可以接受多個型態的參數，但是函式內部的實作卻又要先將該指標轉型才能做使用，不知道有沒有可以直接對 void 指標執行的操作？

Pointers vs. Arrays

int a[3];
struct { double v[3]; double length; } b[17];
int calendar[12][31];

(gdb) p &b
$5 = (struct {...} (*)[17]) 0x601060 <b>
(gdb) p &b+1
$6 = (struct {...} (*)[17]) 0x601280 <a>
(gdb) p &b[0]+1
$8 = (struct {...} *) 0x601080 <b+32>

為何 &b+1 是 a[3] 的所在處，但 gdb 仍在前面顯示 (struct {...} (*)[17]) ?

快慢指標 vs. 單一指標

單一指標在走訪佇列第二次時，比較容易遭受 cache miss 的影響。

你所不知道的 C 語言: bitwise 操作

英文字元大小寫轉換

利用 ascii code 的設計，英文字母大小寫的十進位表示剛好相差 32。

('A' | ' ') // 得到小寫
('a' & '_') // 得到大寫
('A' ^ ' ') // 大小寫互換

對第 n 個 bit 操作

a |= (1 << n)     // Set 
a &= ~(1 << n)    // Clear
a ^= (1 << n)     // Convert

我想投入的期末專案

透過 Netfilter 自動過濾廣告

首先要設計一個可以接收並丟棄封包的應用程式，禁用 conntrack 可以讓程式在單位時間內接收的封包變多，在 iptables 防火牆的 INPUT 中可以設置丟棄封包的過濾器。

有另一種更快的丟棄方式是在封包被 routing 之前就丟棄他們 (PREROUTING)，這樣可以減少進到 routing 階段所需的時間。

在 How to drop 10 million packets per second 中提到，目前比較新的工具是 nftables，而不是 iptables。

如果可以在 traffic control 階段就丟棄封包，甚至會比 PREROUTING 更快。

最後，使用 XDP (eXpress Data Path) 甚至可以讓我們在網路驅動程式中運行丟棄封包的程式碼，這樣的速度是最快的。

vwifi 虛擬無線網路裝置驅動程式和實驗環境

會想要做這個主題是因為我本身的研究領域與 Wi-Fi 有關，而了解這個工具的架構可以讓我在往後實驗中更得心應手，我也可以將自己的專業知識應用到這個期末專題中。

IBSS
SSID
802.11ac

TCP/IP
TCP 3-way handshake?
https://hackmd.io/@sysprog/SyrtOTNb0

L7 filter

TODO: 重現 https://github.com/RicheyJang/RJFireWall 實驗和探討原理，目標是建構基於 Netfilter, Netlink 的 Linux 傳輸層狀態檢測防火牆
TODO: Ubuntun 24.04 (w/ Linux v6.8)

L4