# 2024q1 Homework5 (assessment)
contributed by <`fatcatorange` >
## 因為自動飲料機而延畢的那一年
在這篇文章中，我首先看到了現實的一面，我一直有一個做出讓很多人使用的產品的夢想，因此我在大學、研究所期間學習了遊戲設計、網頁前後端等領域，但這篇文章和我的實作過程中都發現，在缺乏資金和實力真的不到頂尖的情況下，真的很難成功。
但看到一半時，我不禁佩服起了這些人，即使遇到這樣的困難還是堅持做下去，換做是我，看到第一個掉杯機花那麼久的時間作不出來，我應該就果斷放棄了，這大概也是我這麼爛的原因，因為以前失敗的經驗，遇到困難總是先覺得自己辦不到。
「你最大的問題在太害怕失敗了，既然都已經決定要延畢做飲料機了，那就要好好做，才不會辜負當初自己的期望」 這句話我已經在我的第一個作業共筆中看過類似留言，我真的很怕失敗，我也不知道怎麼辦，當我想做好一件事，真的開始做時又會顧慮東顧慮西，怕沒辦法在 deadline 前做出來、怕其他課或事情被拖延，到最後甚麼都做不好。
後半部分，大部分就是他們完成飲料機的過程，大部分我看不懂，因為牽涉到一些電路之類的東西，最後完成的結果也沒辦法商用化，但作者似乎還是覺得很滿意了。
作者提到，資工系的不會寫程式，電工系不會焊電路，這我看完文章之後非常有體悟，我常常刷題，自以為程式能力還可以，但真的要把這些程式能力拿去應用，我肯定不行，我甚至看不懂他用 nodejs 控制電路板的部分，這樣根本不能稱作會寫程式。
「儘管世界如此殘酷，但人卻不一樣，當你真心想做到一件事，付出足夠的犧牲，這個世界會聽見並做出回應，周遭的人漸漸願意相信你、花時間幫助你，你的付出並不見得會有結果，但是加上許多人的幫助，可能一切就不一樣了。」，也許是我還沒有付出足夠多的努力，這段話我沒有感覺到共鳴。
## 1~6 周教材研讀
### 你所不知道的 C 語言: linked list 和非連續記憶體
各名詞的解釋:
* object: 程式執行期間資料儲存的區域都可以稱為 object
* 所有儲存資料的區域都是，包含指標 (指標儲存的就是這個變數儲存的位址，自然也是物件。
* C 永遠是 call by value
* type: 根據規格書 6.2.5 描述:
```
The meaning of a value stored in an object or returned by a function is determined by the
type of the expression used to access it.
```
物件怎麼儲存或函式的回傳由 type 決定。
* 所有儲存資料的區域都是，包含指標 (指標儲存的就是這個變數儲存的位址，自然也是物件。
* 算術和指標 type 統稱為 scale type，可使用 i++ 等操作。
* 陣列、structure 等則稱為 aggregate type。
* 如果不知道物件大小，稱為 imcomplete type，這種 type 可以宣告指標，但不能建立實體 (也就是有宣告，但沒有定義裡面的樣子)。
* function, array, pointer 實際上都是 derived declarator types ，實質上都是指標。
練習題:
```c
*(int32_t * const) (0x67a9) = 0xaa6;
```
透過(int32_t * const) (0x67a9) ， 0x67a9 ~~被轉為 32 bit 的型態(指標是 32 bit 儲存的)~~ 轉為指向 int32_t 類型的指標，之後透過 * 符號，將這個指標內的值修改為 0xaa6。
:::warning
因為老家沒有 linux 電腦，先使用線上編譯器嘗試:
```c
#include <stdio.h>
#include <stdint.h>
int main() {
*(int32_t * const) (0x67a9) = 0xaa6;
printf("%d", *(int32_t * const) (0x67a9));
return 0;
}
```
出現 segmentation fault， 之後再使用 linux 電腦嘗試。
仍出現 segmentation fault，使用 gdb 檢查：
```shell
main () at test.c:5
5 *(int32_t * const) (0x67a9) = 0xaa6;
(gdb) x 0x67a9
0x67a9: Cannot access memory at address 0x67a9
```
gdb 無法檢查這個位址，我嘗試先分配一塊空間出來：
```c
int32_t *temp = malloc(sizeof(int));
```
`$1 = (int32_t *) 0x5555555592a0`
接下來我嘗試直接寫入這個區域：
```c
*(int32_t * const) (0x5555555592a0) = 0xaa6;
printf("%d", *(int32_t * const) (0x5555555592a0));
```
```shell
6 int32_t *temp = malloc(sizeof(int));
(gdb) n
7 *(int32_t * const) (0x5555555592a0) = 0xaa6;
(gdb) n
8 printf("%d", *(int32_t * const) (0x5555555592a0));
(gdb) print *(0x5555555592a0)
$1 = 2726
(gdb) n
9 return 0;
(gdb) print *temp
$2 = 2726
```
結論是，真的可以直接寫資料進固定位址，但前提是程式必須能控制那會記憶體區域，我不理解這樣的作法會在什麼樣的場合用到（或許可以省下指標的空間？）
:::
* *void
*void 透過讓使用者必須強制轉型才能存取
舉例來說，下面的程式碼會出現錯誤告知嘗試 dereference void pointer:
```c
int main() {
int a = 1;
void *tmp = &a;
printf("%d",*tmp);
return 0;
}
```
但這樣可以正常執行(因為有強制轉型為指向 int 的指標)
```c
int main() {
// Write C code here
int a = 1;
void *tmp = &a;
printf("%d",*(int*) tmp);
return 0;
}
```
指標的指標:
當我們希望在函式中改變一個指標指向的位置，因為 c 是 call by value, 因此只會傳入這個指標的複製進去，在函式內僅會對這個複製的指標修改。
因此，透過指標的指標，複製一個指向某個位址的指標，這樣就可以真的修改這個指標指向的位址。
forward declaration 搭配指標的技巧:
前面提到 imcomplete type 可以宣告指標，因此如果宣告一個 struct， 並在其他函式中透過指標操作，不管之後這個 struct 怎麼修改都不會影響這個函式。
Pointers vs. Arrays
兩者不能切換的情況：
* extern char x[ ] != extern char *x
* char x[10] != char *x (char *x = malloc(10 * sizeof(char)) 也不行嗎？)
function array:
可以宣告一個函式，並讓一個指標指向他：
```c
#include <stdio.h>
void call(int a, int b) {
printf("%d", a * b);
}
int main() {
void (*callJimmy)(int,int);
callJimmy = call;
callJimmy(20,4);
}
```
透過 typedef ，可以定義特定樣子（包含的參數、回傳的型態）的函式，舉例來說：
```c
#include <stdio.h>
void call(int a, int b) {
printf("%d", a * b);
}
typedef int (*callJimmy)(int,int);
int main() {
callJimmy fptr;
fptr = call;
fptr(20,4);
}
```
這裡 callJimmy 就被定義成一種指向 `回傳為 int，輸入是兩個 int 的函式` 的指標。
甚至可以把函式指標弄成陣列（陣列內也是函式指標，因此陣列是指標的指標?）：
```c
#include <stdio.h>
void add(int a, int b) {
printf("%d", a + b);
}
void sub(int a,int b) {
printf("%d", a - b);
}
typedef void (*callJimmy)(int,int);
int main() {
callJimmy fptr[2] = {add,sub};
fptr[0](5,6);
fptr[1](5,6);
}
```
也可改寫成：
```c
int main() {
callJimmy fptr[2] = {add,sub};
(*(fptr))(5,6);
(*(fptr + 1))(5,6);
}
```
針對指標的修飾 (qualifier)
char * const pContent; 代表指向一個 char ，並且宣告後就不能修改
const char * pContent; 則代表指向一個 const char，可以改為指向其他 const char。
offsetof:
計算偏移量：
```c
struct ssj {
int sj;
float super;
};
typedef void (*callJimmy)(int,int);
int main() {
struct ssj *strong;
printf("%ld", offsetof(struct ssj, super));
}
```
結果為 4，如果傳入 sj 則為 0。
因為資料 sj 欄位佔了 4 byte ， sj 是開頭， super 在 sj 後面，所以是 4。
## 你所不知道的 C 語言：數值系統篇
二進位轉換：
大寫和小寫英文字母只有一個 0100000 的差距
轉小寫：
('A' | ' ')、('a' | ' ') =>a
'A'=>1000001
' '=>0100000
__
1100001 => a
'a'=>1100001
' '=>0100000
__
1100001 => a
轉大寫：
（'a' & '_')、（'A' & '_')
'a'=>1100001
'_'=>1011111
--
1000001 => A
'A'=>1000001
'_'=>1011111
--
1000001 => A
大小顛倒：
('a' ^ ' ')、('A' ^ ' ')
'a'=>1100001
' '=>0100000
--
1100001 => a
'A'=>1000001
' '=>0100000
--
1100001 => a
xor swap(當記憶體資源稀少時可使用)
範例：
*x = 1001
*y = 1101
```c
void xorSwap(int *x, int *y) {
*x ^= *y; // x = 0100
*y ^= *x; // y = 1001
*x ^= *y; // x = 1101
}
```
避免 overflow:
(x + y)/2 可能造成 overflow
(x + y)/2
=>(x + y) >> 1 (右移 1 功能與 /2 相同)
=>(x ^ y + (x & y) << 1) >> 1 (x ^ y 是相加不進位，x & y = 1 代表要進位，左移 1 代表把進位的部份加一)
=>(x & y) + ((x ^ y) >> 1 )
0110 //6
1111 //15
0110 + 0100 = 1010 //10
省去迴圈
```c
int func(unsigned int x) {
int val = 0; int i = 0;
for (i = 0; i < 32; i++) {
val = (val << 1) | (x & 0x1);
x >>= 1;
}
return val;
}
```
假設以比較小範圍來看（假設只有 4 bits)
若 x 是 1100:
第一次迴圈時:
```c
val = (val << 1) | (x & 0x1); // val = 0000 | (1100 & 0001) => val = 0000
x >>= 1; //x = 0110
```
第二次：
```c
val = (val << 1) | (x & 0x1); // val = 0000 | (0110 & 0001) => val = 0000
x >>= 1; //x = 0011
```
第三次：
```c
val = (val << 1) | (x & 0x1); // val = 0000 | (0011 & 0001) => val = 0001
x >>= 1; //x = 0001
```
第三次：
```c
val = (val << 1) | (x & 0x1); // val = 0010 | (0001 & 0001) => val = 0011
x >>= 1; //x = 0000
```
可以發現，越前面被 (x & 0x1) 設定成 1 的位元，最後會被推到 val 越後面的位元，因此這個函式就是在進行反轉。
如何不用迴圈完成？
```c
new = num;
new = ((new & 0xffff0000) >> 16) | ((new & 0x0000ffff) << 16);
new = ((new & 0xff00ff00) >> 8) | ((new & 0x00ff00ff) << 8);
new = ((new & 0xf0f0f0f0) >> 4) | ((new & 0x0f0f0f0f) << 4);
new = ((new & 0xcccccccc) >> 2) | ((new & 0x33333333) << 2);
new = ((new & 0xaaaaaaaa) >> 1) | ((new & 0x55555555) << 1);
```
## 你所不知道的 C 語言: bitwise 操作
abs(n) => ((n>>31) ^ n) - (n>>31)
當 n 為正數，n>>31 為 0000..00，xor n 仍為 n
當 n 為負數，n>>31 為 1111..11，xor n 為 ~(n)，再 - (-1)（即 1111..11） 就是 abs(n)
set a bit:
`a |= (1<<n)`
不管原本該位元是 0 or 1，or 後結果都是 1
clear a bit:
`b &= ~(1 << n);`
假設要 clear 第3個 bit：
1<<3=>000...01000 => ~(1 << 3) => 111...10111
因此除了第三位外，其餘位元保留，而第三位因為是 0 ，& 的結果必定為 0。
toggle a bit:
`c ^= (1 << n)`
10011011
00010000
--
10001011 -> 原本是 1， xor 完變 0 ，否則變 1。
## 你所不知道的 C 語言：記憶體管理、對齊及硬體特性
heap 和 stack（部份參考 [記憶體分配:stack與heap](https://hackmd.io/@Ben1102/B1gfGLT3u)）:
stack:
用來儲存 function 的呼叫、傳入的參數或區域變數，stack 的大小是在編譯完成就固定了，因此如果 stack 使用的記憶體過多會發生 stack overflow。
heap:
heap 則是動態分配的記憶體區域，如使用 malloc（）等方法動態分配的，但需要注意分配的記憶體必須釋放，否則可能引起 memory leak。
memory leak 實驗：
文章中提到， memory leak 可能是由未釋放空間導致。
一段簡單的程式碼：
```c
void f(void)
{
void* s;
s = malloc(5000);
return;
}
int main(void)
{
while (1) f();
return 0;
}
```
這段程式碼中，f() 會不斷被呼叫，然而其申請的 5000 byte 空間不會被釋放就返回了，當程式執行一段時間後，因為沒辦法再從 heap 分配更多空間，因此會被強致結束。
而如果在返回前加入 free(s)，則程式真的就會不段重複執行，因為每次都有把空間釋放，不會發生無法分配空間的問題。
gdb 的對齊實驗：
```shell
$1 = 0x5555555592a0 ""
(gdb) n
7 for (int i = 0; i < 10000; ++i) {
(gdb) print z
No symbol "z" in current context.
(gdb) n
9 z = malloc(sizeof(char));
(gdb) print z
$2 = 0x5555555592c0 ""
(gdb) n
7 for (int i = 0; i < 10000; ++i) {
(gdb) n
9 z = malloc(sizeof(char));
(gdb) print z
$3 = 0x5555555592e0 ""
```
:::warning
之後檢查 malloc 為何這樣分配？
:::
## 你所不知道的 C 語言：函式呼叫篇
:::danger
看不懂前面，先複習組合語言
:::
buffer overflow 實驗：
```shell
$ gcc -o bof -fno-stack-protector -g -no-pie test.c
```
-fno-stack-protector 是取消記憶體保護，-no-pie 是把讓程式從固定位置載入的功能取消，這樣攻擊比較容易成功。
下面可以看到回傳位址在 +62 處
```c
gdb-peda$ pd main
Dump of assembler code for function main:
0x0000000000401190 <+0>: endbr64
0x0000000000401194 <+4>: push rbp
0x0000000000401195 <+5>: mov rbp,rsp
0x0000000000401198 <+8>: sub rsp,0x10
0x000000000040119c <+12>: lea rax,[rip+0xe69] # 0x40200c
0x00000000004011a3 <+19>: mov rdi,rax
0x00000000004011a6 <+22>: call 0x401060 <puts@plt>
0x00000000004011ab <+27>: lea rax,[rbp-0xa]
0x00000000004011af <+31>: mov rdi,rax
0x00000000004011b2 <+34>: mov eax,0x0
0x00000000004011b7 <+39>: call 0x401080 <gets@plt>
0x00000000004011bc <+44>: lea rax,[rbp-0xa]
0x00000000004011c0 <+48>: mov rdi,rax
0x00000000004011c3 <+51>: call 0x401060 <puts@plt>
0x00000000004011c8 <+56>: mov eax,0x0
0x00000000004011cd <+61>: leave
=> 0x00000000004011ce <+62>: ret
End of assembler dump.
gdb-peda$
```
指向了 `aaaa...a`
```
0000| 0x7fffffffd8c8 ('a' <repeats 140 times>)
0008| 0x7fffffffd8d0 ('a' <repeats 132 times>)
0016| 0x7fffffffd8d8 ('a' <repeats 124 times>)
0024| 0x7fffffffd8e0 ('a' <repeats 116 times>)
0032| 0x7fffffffd8e8 ('a' <repeats 108 times>)
0040| 0x7fffffffd8f0 ('a' <repeats 100 times>)
0048| 0x7fffffffd8f8 ('a' <repeats 92 times>)
0056| 0x7fffffffd900 ('a' <repeats 84 times>)
[------------------------------------------------------------------------------]
Legend: code, data, rodata, value
Stopped reason: SIGSEGV
0x00000000004011ce in main () at test.c:14
14 }
gdb-peda$ p $rsp
$1 = (void *) 0x7fffffffd8c8
gdb-peda$ x/g 0x7fffffffd8c8
warning: Unable to display strings with size 'g', using 'b' instead.
0x7fffffffd8c8: 'a' <repeats 140 times>
```
檢查 evil 函是的位址
```shell
gdb-peda$ p evil
$2 = {int ()} 0x401176 <evil>
```
透過文章方法，輸入 abcdef.... 來確認到回傳指令的偏移量：
```shell
egend: code, data, rodata, value
Stopped reason: SIGSEGV
0x00000000004011ce in main () at test.c:14
14 }
gdb-peda$ p $rsp
$1 = (void *) 0x7fffffffd8c8
gdb-peda$ x/s 0x7fffffffd8c8
0x7fffffffd8c8: "ttuvwxyzabcdefghijklmnop"
```
t 前面有 18 個字母，輸入 18 個 a 來完成：
```shell
echo -ne "aaaaaaaaaaaaaaaaaa\x76\x11\x40\x00\x00\x00\x00\x00"
aaaaaaaaaaaaaaaaaav@jason@jason-System-Product-Name:~/linux-2024/test$ echo -ne "aaaaaaaaaaaaaaaaaa\x76\x11\x40\x00\x00\x00\x00\x00" > payload
jason@jason-System-Product-Name:~/linux-2024/test$ ./bof < payload
Input:
aaaaaaaaaaaaaaaaaav@
程式記憶體區段錯誤 (核心已傾印)
```
失敗，透過 gdb 檢查：
```shell
gdb-peda$ x/s 0x7fffffffd8c8
0x7fffffffd8c8: "\\x76\\x11\\x40\\x00\\x00\\x00\\x00\\x00"
gdb-peda$ *p evil
Undefined command: "". Try "help".
gdb-peda$ p evil
$2 = {int ()} 0x401176 <evil>
```
問題似乎是因為字串被轉換了？ 我輸入的 `\` 全部被轉成 `\\` 了。
我嘗試直接把 stack 的頭改成 0x401176 (evil 函是的位址)
```shell
gdb-peda$ p 0x7fffffffd8c8
$14 = 0x7fffffffd8c8
gdb-peda$ p *0x7fffffffd8c8
$15 = 0xf7c29d90
gdb-peda$ set *0x7fffffffd8c8 = 0x401176
gdb-peda$ p *0x7fffffffd8c8
$16 = 0x401176
```
出現以下錯誤：
```
[-------------------------------------code-------------------------------------]
Invalid $PC address: 0x7fff00401176
```
---
## 5/6 1對1 討論後研究：
### socket programming
因為覺得連最基本的 socket programming 都不熟悉，因此從此處開始研究：
以 [github 上的 socket programming 教學](https://github.com/davidleitw/socket) 作為主要教材：
#### UDP
##### 建立 socket:
```c
int socket_fd = socket(AF_INET, SOCK_DGRAM, 0);
```
第一、二個參數分別代表 ipv4 和 udp 第三個是別名? 通常填入 0
建立好後，要設定 socket address ，因為這裡使用 ipv4，因此可以使用 `socket_in`來儲存資料。
例如可以這樣設定：
```
struct sockaddr_in serverAddr = {
.sin_family = AF_INET, //IPV4
.sin_addr.s_addr = INADDR_ANY, //不限 ip
.sin_port = serverPort
};
```
##### 綁定：
完成後要把這個 socket 的 fd 綁定給某個 ip 或 port，這裡需要注意的是因為 bind 欄位預設是要輸入 sockaddr，但我們使用的是 sockaddr_in ，因此要進行強致轉型（ sockaddr_in 內有進行必要的填充，兩者大小相同。
```c
bind(socket_fd, (const struct sockaddr *)&serverAddr, sizeof(serverAddr));
```
##### 接收資料：
綁定完成後，可以使用 `recvfrom` 來接收資料，如下：
```c
if (recvfrom(socket_fd, buf, sizeof(buf), 0, (struct sockaddr *)&clientAddr, &len) < 0) {
break;
}
```
其中 clientAddr 和 serverAddr 相同，儲存一些 ip、port 之類的資料，這樣資料才能透過這些資訊回傳。
##### 傳輸資料：
使用 `sendto` 回傳資料，參數內容基本上和 recvfrom
```c
sendto(socket_fd, conv, sizeof(conv), 0, (struct sockaddr *)&clientAddr, sizeof(clientAddr));
```
也就是說， socket 綁定完成後通過 recvfrom 等待資料，並透過 sendto 函式進行回傳。
而 user 端就只要做跟 server 端相同的事，只是改為先傳輸，再等回傳。
奇怪的是，我原本以為程式執行到 recvfrom 就會卡住，收到資料後往下執行，然後迴圈再執行回 recvfrom 等待，因此我原本想法是如果 server 正在執行資料處理，那這時候其他用戶傳資料過來應該沒辦法收到，因此我做了以下實驗，先開啟 1 個 client，當 server 接收到資料後，先 sleep 10 秒鐘，而我就在這 10 秒鐘再開啟一個 client 端的程式傳輸資料，我預期應該只有第一個 client 會接收到資料，但實際上兩個 client 都有收到回覆
```c
sleep(10);
```
此外，我並沒有設定 client 端的資料，client 也沒有 bind 到某個 port，卻能成功執行？
檢查後發現是回傳到 `127.0.0.1:41173`，port 每次不同，這是代表原本就要 bind 到某個 port 嗎？
假設我有先進行綁定：
```c
struct sockaddr_in clientAddr = {
.sin_family = AF_INET, //IPV4
.sin_addr.s_addr = INADDR_ANY, //不限 ip
.sin_port = htons(54321)
};
if (bind(socket_fd, (const struct sockaddr *)&clientAddr, sizeof(clientAddr)) < 0) {
perror("Bind socket failed!");
close(socket_fd);
exit(0);
}
```
這次就成功抓到 port 54321 的資料，因此似乎在創建 socket 時，除非有綁定，否則就會自動分配一個 port 給他？
#### TCP
相比 UDP ， TCP 必須建立連線，因此在 server 端要先透過 listen 進行監聽 （聽有沒有人要建立連線）
```c
int listen(int sockfd, int backlog);
```
`backlog` 代表最大連線數
在 client 端，則要使用 connect 進行連接，代連線建立完成就會被放到 complete connection queue。
```c
int connect(int sockfd, const struct sockaddr *addr,
socklen_t addrlen);
```
接下來使用 `access` 就可以獲取 complete connection queue 的資料（所以會被處理的資料都是已經建好連線了）
```c
int accept(int sockfd, struct sockaddr *restrict addr,
socklen_t *restrict addrlen);
```
### ktcp
https://hackmd.io/@fatCatOrange/ktcp
### RCU
關於 RCU 的筆記：https://hackmd.io/FxDhzUmKRnKKBl1RSFkpsg
ktime
stack 使用量？
1.2.4
MRE: https://en.wikipedia.org/wiki/Minimal_reproducible_example
Sign in with Wallet
Connect another wallet