Try   HackMD

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 ，實質上都是指標。

練習題:

*(int32_t * const) (0x67a9) = 0xaa6;

透過(int32_t * const) (0x67a9) ， 0x67a9 被轉為 32 bit 的型態(指標是 32 bit 儲存的) 轉為指向 int32_t 類型的指標，之後透過 * 符號，將這個指標內的值修改為 0xaa6。

因為老家沒有 linux 電腦，先使用線上編譯器嘗試:

#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 檢查：

main () at test.c:5
5           *(int32_t * const) (0x67a9) = 0xaa6;
(gdb) x 0x67a9
0x67a9: Cannot access memory at address 0x67a9

gdb 無法檢查這個位址，我嘗試先分配一塊空間出來：

int32_t *temp = malloc(sizeof(int));

$1 = (int32_t *) 0x5555555592a0
接下來我嘗試直接寫入這個區域：

*(int32_t * const) (0x5555555592a0) = 0xaa6;
    printf("%d", *(int32_t * const) (0x5555555592a0));

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:
int main() {
    int a = 1;
    void *tmp = &a;
    printf("%d",*tmp);
    return 0;
}

但這樣可以正常執行(因為有強制轉型為指向 int 的指標)

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:

可以宣告一個函式，並讓一個指標指向他：

#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 ，可以定義特定樣子（包含的參數、回傳的型態）的函式，舉例來說：

#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 的函式 的指標。

甚至可以把函式指標弄成陣列（陣列內也是函式指標，因此陣列是指標的指標?）：

#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);
}

也可改寫成：

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:

計算偏移量：

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

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

省去迴圈

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:
第一次迴圈時:

val = (val << 1) | (x & 0x1); // val = 0000 | (1100 & 0001) => val = 0000
x >>= 1; //x = 0110

第二次：

val = (val << 1) | (x & 0x1); // val = 0000 | (0110 & 0001) => val = 0000
x >>= 1; //x = 0011

第三次：

val = (val << 1) | (x & 0x1); // val = 0000 | (0011 & 0001) => val = 0001
x >>= 1; //x = 0001

第三次：

val = (val << 1) | (x & 0x1); // val = 0010 | (0001 & 0001) => val = 0011
x >>= 1; //x = 0000

可以發現，越前面被 (x & 0x1) 設定成 1 的位元，最後會被推到 val 越後面的位元，因此這個函式就是在進行反轉。

如何不用迴圈完成？

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）:

stack:

用來儲存 function 的呼叫、傳入的參數或區域變數，stack 的大小是在編譯完成就固定了，因此如果 stack 使用的記憶體過多會發生 stack overflow。

heap:

heap 則是動態分配的記憶體區域，如使用 malloc（）等方法動態分配的，但需要注意分配的記憶體必須釋放，否則可能引起 memory leak。

memory leak 實驗：

文章中提到， memory leak 可能是由未釋放空間導致。

一段簡單的程式碼：

 void f(void)
 {
     void* s;
     s = malloc(5000); 
     return; 
 }
 int main(void)
 {
     while (1) f(); 
     return 0;
 }

這段程式碼中，f() 會不斷被呼叫，然而其申請的 5000 byte 空間不會被釋放就返回了，當程式執行一段時間後，因為沒辦法再從 heap 分配更多空間，因此會被強致結束。

而如果在返回前加入 free(s)，則程式真的就會不段重複執行，因為每次都有把空間釋放，不會發生無法分配空間的問題。

gdb 的對齊實驗：

$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 ""

之後檢查 malloc 為何這樣分配？

你所不知道的 C 語言：函式呼叫篇

看不懂前面，先複習組合語言

buffer overflow 實驗：

$ gcc -o bof -fno-stack-protector -g -no-pie test.c

-fno-stack-protector 是取消記憶體保護，-no-pie 是把讓程式從固定位置載入的功能取消，這樣攻擊比較容易成功。

下面可以看到回傳位址在 +62 處

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 函是的位址

gdb-peda$ p evil
$2 = {int ()} 0x401176 <evil>

透過文章方法，輸入 abcdef… 來確認到回傳指令的偏移量：

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 來完成：

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 檢查：

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 函是的位址)

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 教學 作為主要教材：

UDP

建立 socket:
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 內有進行必要的填充，兩者大小相同。

bind(socket_fd, (const struct sockaddr *)&serverAddr, sizeof(serverAddr));
接收資料：

綁定完成後，可以使用 recvfrom 來接收資料，如下：

if (recvfrom(socket_fd, buf, sizeof(buf), 0, (struct sockaddr *)&clientAddr, &len) < 0) {
            break;
}

其中 clientAddr 和 serverAddr 相同，儲存一些 ip、port 之類的資料，這樣資料才能透過這些資訊回傳。

傳輸資料：

使用 sendto 回傳資料，參數內容基本上和 recvfrom

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 都有收到回覆

sleep(10);

此外，我並沒有設定 client 端的資料，client 也沒有 bind 到某個 port，卻能成功執行？

檢查後發現是回傳到 127.0.0.1:41173，port 每次不同，這是代表原本就要 bind 到某個 port 嗎？

假設我有先進行綁定：

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 進行監聽 （聽有沒有人要建立連線）

int listen(int sockfd, int backlog);

backlog 代表最大連線數

在 client 端，則要使用 connect 進行連接，代連線建立完成就會被放到 complete connection queue。

int connect(int sockfd, const struct sockaddr *addr,
            socklen_t addrlen);

接下來使用 access 就可以獲取 complete connection queue 的資料（所以會被處理的資料都是已經建好連線了）

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

Last changed by 
 
劉家成
4
348

Read more

2024q1 Homework2 (quiz1+2)

contributed by < fatcatorange >

Jun 12, 2024
ktcp

研讀 Linux 核心設計: 針對事件驅動的 I/O 模型演化 時，難以理解 epoll 操作的行為，因此嘗試實做一個使用 epoll 的簡易伺服器：

Jun 6, 2024
Linux 核心設計: RCU 同步機制

以概念來說，RCU 要使用在有大量讀取要求，但只有少量的寫入要求，且不會太在意讀取到舊資料的情況。

May 8, 2024
2024q1 Homework6 (integration)

contributed by < fatcatorange >

May 5, 2024
Read more from 劉家成
Published on HackMD