Try   HackMD

2025q1 Homework4 (quiz3+4)

contributed by < tsaiiuo >

作業書寫規範:

  • 無論標題和內文中,中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)
  • 文字訊息 (尤其是程式執行結果) 請避免用圖片來表示,否則不好搜尋和分類
  • 共筆書寫請考慮到日後協作,避免過多的個人色彩,用詞儘量中性
  • 不要在筆記內加入 [TOC] : 筆記左上方已有 Table of Contents (TOC) 功能,不需要畫蛇添足
  • 不要變更預設的 CSS 也不要加入任何佈景主題: 這是「開發紀錄」,用於評分和接受同儕的檢閱
  • 在筆記中貼入程式碼時,避免非必要的行號,也就是該手動將 c=cpp= 變更為 ccpp。行號只在後續討論明確需要行號時,才要出現,否則維持精簡的展現。可留意「你所不知道的 C 語言: linked list 和非連續記憶體」裡頭程式碼展現的方式
  • HackMD 不是讓你張貼完整程式碼的地方,GitHub 才是!因此你在開發紀錄只該列出關鍵程式碼 (善用 diff 標示),可附上對應 GitHub commit 的超連結,列出程式碼是為了「檢討」和「便於他人參與討論」
  • 留意科技詞彙的使用,請參見「資訊科技詞彙翻譯」及「詞彙對照表
  • 不要濫用 :::info, :::success, :::warning 等標示,儘量用清晰的文字書寫。:::danger 則僅限授課教師作為批注使用
  • 避免過多的中英文混用,已有明確翻譯詞彙者,例如「鏈結串列」(linked list) 和「佇列」(queue),就使用該中文詞彙,英文則留給變數名稱、人名,或者缺乏通用翻譯詞彙的場景
  • 在中文敘述中,使用全形標點符號,例如該用「,」,而非 ","。注意書名號的使用,即 ,非「小於」和「大於」符號
  • 避免使用不必要的 emoji 字元

Q3

測驗 1

解釋上述程式碼運作原理

先研讀程式碼,回答答案。
ceil_div : 可以透過

nd=n+d1d 的概念實作,因此AAAA(n + d - 1) / d
INTMAX : 這就比較直觀 BBBB0x7fffffff
mpi_mul_naive : 實現天真乘法(透過兩數逐位相乘,並累加各項乘積,同時處理進位。),第 n 位和第二個 mpi_t 的第 m 位而言,他們乘起來的數字要加到第 n + m 位,因此 CCCCn + m
mpi_fdiv_qr : 實現長除法,這邊須將餘數左移一位(跟實際的長除法一樣),因此 DDDD1
mpi_gcd:用 mpi_fdiv_qr 做輾轉相除法用於計算計算兩個整數的最大公因數根據公式可以得知答案
例子:

gcd(46189,2310)
   = gcd(2310, 46189 mod 2310)
   = gcd(2310,2299)           (因 46189 ÷ 2310 = 19,餘數 46189 – 19×2310 = 2299)
   = gcd(2299,2310 mod 2299)
   = gcd(2299,11)           (2310 ÷ 2299 = 1,餘數 2310 – 1×2299 = 11)
   = gcd(11,2299 mod 11)
   = gcd(11,0)            (2299 ÷ 11 = 209,餘數 2299 – 209×11 = 0)
   = 11

因此EEEEmpi_gcd(rop, op2, r)

這項實作依賴遞迴呼叫,請避免使用並降低記憶體開銷

void mpi_gcd(mpi_t rop, const mpi_t op1, const mpi_t op2)
{
    mpi_t a, b, q, r;

    mpi_init(a);
    mpi_init(b);
    mpi_init(q);
    mpi_init(r);

    mpi_set(a, op1);
    mpi_set(b, op2);

    /* 當 b 不為 0 時,持續進行除法以取餘數 */
    while (mpi_cmp_u32(b, 0) != 0) {
        /* 計算 a / b,獲得餘數 r */
        mpi_fdiv_qr(q, r, a, b);

        /* 將 a, b 更新:令 a = b, b = r */
        mpi_set(a, b);
        mpi_set(b, r);
    }

    mpi_set(rop, a);

    mpi_clear(a);
    mpi_clear(b);
    mpi_clear(q);
    mpi_clear(r);
}

因為 op1op2 皆為不可變更的,因此需要多定義 ab 代替 op1op2 去進行運算。

測驗 2

解釋上述程式碼運作原理

先研讀程式碼,回答問題

#define DETECT_CHAR(X, mask) DETECT_NULL(AAAA)

用 X 與 mask 做 XOR 運算,產生一個新值,這樣在各個 byte 中若有 byte 等於 d(即 mask 中對應的 byte),則 XOR 後該 byte 會變為 0,再交由 DETECT_NULL 檢查是否存在 0 byte,因此 AAAA(X) ^ (mask)

unsigned long *asrc = (unsigned long *) src;
unsigned long mask = d << 8 | d;
mask |= mask << 16;
for (unsigned int i = 32; i < LBLOCKSIZE * 8; i <<= 1)
    mask |= BBBB;

這段程式碼目的是建立一個 word(unsigned long)大小的 mask,其中每個 byte 都填滿了目標字元 d 的值。這個 mask 之後會用來在一次讀入多個 byte 時,用意是透過 XOR 與位元運算來檢測該 word 中是否含有目標字元(d)。
而上面程式碼如何製作 mask 我用以下一個範例去 trace code 看看:
這邊假設 d = 'w' , 即 0x77,且 LBLOCKSIZE = 8(64位元的系統)

初始計算:
d = 0x77
d<<8 = 0x7700
mask = 0x7700 | 0x77 = 0x7777

擴展到 32 位元:
mask<<16 = 0x7777 << 16 = 0x77770000
mask |= mask<<16 → 0x7777 | 0x77770000 = 0x77777777

擴展到 64 位元:
進入迴圈,初始 i = 32,
mask<<32(i) = 0x77777777 << 32 = 0x7777777700000000
mask |= mask<<32 → 0x77777777 | 0x7777777700000000 = 0x77777777_77777777
然後 i <<= 1 變成 64,迴圈結束。

因此 BBBBmask << i

while (len >= LBLOCKSIZE) {
    if (DETECT_CHAR(CCCC, mask))
        break;
    asrc++;
    len -= LBLOCKSIZE;
}

這段程式碼就是以 word 為單位配合 DETECT_CHAR 檢查是否有符合的目標字元若有則中止,反之則檢查下一個 word(這邊的 ++ 會加上 sizeof(unsigned long) 也就是一個 word 的大小),因此 CCCC 應該為 *asrc (上面有一段 unsigned long *asrc = (unsigned long *) src; )

userspace context 測試

此段用意在理解 getcontextmakecontextsetcontext

getcontext(&ctx_main);

可以取得目前程式的上下文並且存入參數的指標中

// 取得一個可修改的 context,再設定其執行函式為 func() if (getcontext(&ctx_func) == -1) { perror("getcontext"); exit(1); } ctx_func.uc_stack.ss_sp = malloc(8192); if (ctx_func.uc_stack.ss_sp == NULL) { perror("malloc"); exit(1); } ctx_func.uc_stack.ss_size = 8192; ctx_func.uc_stack.ss_flags = 0; // 當 ctx_func 執行完畢,會回到 ctx_main ctx_func.uc_link = &ctx_main; makecontext(&ctx_func, func, 0);

先呼叫 getcontext(&ctx_func),以取得一個現有的上下文(用意在取得合法的 ucontext_t結構體),並分配堆疊空間。設定 uc_link 為 &ctx_main,表示當 func() 執行結束(或呼叫 setcontext() 跳轉)後,會返回主 context。呼叫 getcontext(&ctx_func) 初始化 ctx_func,再用 makecontext(&ctx_func, func, 0) 指定執行函式為 func()。

完整測試函式:

#define _XOPEN_SOURCE 700
#include <stdio.h>
#include <ucontext.h>
#include <stdlib.h>

ucontext_t ctx_main, ctx_func;

void func() {
    printf("In func(): start\n");
    // 切換回主 context
    if (setcontext(&ctx_main) == -1) {
        perror("setcontext");
        exit(1);
    }
    // 此處不會執行到,因為 setcontext 不返回
    printf("In func(): end\n");
}

int main(void) {
    // 取得主 context
   
    if (getcontext(&ctx_main) == -1) {
        perror("getcontext");
        exit(1);
    }
    printf("Init\n");
    // 初始化 ctx_func,並設定堆疊空間
    ctx_func.uc_stack.ss_sp = malloc(8192);
    if (ctx_func.uc_stack.ss_sp == NULL) {
        perror("malloc");
        exit(1);
    }
    ctx_func.uc_stack.ss_size = 8192;
    ctx_func.uc_stack.ss_flags = 0;
    // 當 ctx_func 執行完畢,會回到 ctx_main
    // ctx_func.uc_link = &ctx_main;

    // 取得一個可修改的 context,再設定其執行函式為 func()
    if (getcontext(&ctx_func) == -1) {
        perror("getcontext");
        exit(1);
    }
    // 設定 ctx_func 執行 func();此處沒有參數
    makecontext(&ctx_func, func, 0);

    printf("In main(): before setcontext to func\n");
    // 切換到 ctx_func 執行 func(),切換後不會回到這行(除非從 ctx_func 的 uc_link 返回)
    if (setcontext(&ctx_func) == -1) {
        perror("setcontext");
        exit(1);
    }
    printf("In main(): after setcontext\n");

    free(ctx_func.uc_stack.ss_sp);
    return 0;
}

測驗 3

解釋上述程式碼運作原理

結構體

typedef struct Env {
    int status;          /* Current status of the thread */
    ucontext_t state;    /* Context for saving and restoring thread execution */
    int state_reentered; /* Indicate if the context has been reentered */
    int ipc_sender;      /* Identifier of the thread that sent an IPC message */
    int ipc_value;       /* Value received from an IPC message */
} Env;

程式碼本身是要實現可搶先 (preemptible) 的 user-level thread(使用者層執行緒)運作

int coro_create(coro_entry entry, void *args)
{
    /* Search for an available environment slot */
    int env;
    for (env = 0; env < NENV; env++) {
        if (envs[env].status == ENV_UNUSED) /* Found a free environment */
            break;
    }
    if (env == NENV) /* No free environments available */
        return -1;
    envs[env].status = AAAA;

    /* Initialize the context for the new user-level thread */
    getcontext(&envs[env].state);
    make_stack(&envs[env].state);
    envs[env].state.uc_link = &exiter;
    makecontext(&envs[env].state, (void (*)(void)) entry, 1, args);

    /* Return the identifier of the newly created user-level thread */
    return env;
}

這段程式碼是要創立一個 user-level thread ,使找到 ENV_UNUSED 狀態的執行緒時,將他的狀態設置為可執行,因此 AAAAENV_RUNNABLE

static void coro_schedule(void)
{
    int attempts = 0;
    while (attempts < NENV) {
        int candidate = (curenv + BBBB) % NENV;
        if (envs[candidate].status == ENV_RUNNABLE) {
            curenv = candidate;
            /* Request delivery of TIMERSIG after 10 ms */
            timer_settime(timer, 0, &ts, NULL);
            setcontext(&envs[curenv].state);
        }
        attempts++;
    }
    exit(0);
}

這段程式碼是要實現簡單的 round-robin 排程,應該為搜索下一個,BBBBattempts + 1

void coro_yield(void)
{
    envs[curenv].state_reentered = 0;
    getcontext(&envs[curenv].state);
    if (envs[curenv].state_reentered++ == 0) {
        /* Context successfully saved; schedule the next user-level thread to
         * run.
	 */
        CCCC();
    }
    /* Upon re-entry, simply resume execution */
}

這段程式碼是要實現讓當前執行緒主動放棄 CPU,並進入排程。在呼叫 getcontext() 取得當前 context 後,根據 state_reentered 判斷是否是第一次保存該 context,如果是則呼叫排程,因此 CCCCcoro_shedule

static void preempt(int signum UNUSED,
                    siginfo_t *si UNUSED,
                    void *context UNUSED)
{
    DDDD();
}

這段程式碼當是要實現 preemption 信號傳來時,讓當前執行緒釋放。符合規範的函式名稱且以 coro_ 開頭,因此 DDDDyield

Q4

測驗 1

解釋上述程式碼運作原理

參見Fast CRC32 提到的 "Half-Byte Algorithm",我們可將 8-bit 表格查詢拆分為二次 4-bit 查詢,並且有提供產生器,則實際執行一次產生器即可得到所有答案。

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

#define POLY 0x82F63B78

void generate_crc32c_table(void) {
    printf("static const uint32_t crc32c_table[16] = {\n");
    for (uint32_t i = 0; i < 16; ++i) {
        uint32_t crc = i;
        for (int j = 0; j < 4; ++j) {
            if (crc & 1)
                crc = (crc >> 1) ^ POLY;
            else
                crc = (crc >> 1);
        }
        printf("    0x%08x%s", crc, (i % 4 == 3) ? ",\n" : ", ");
    }
    printf("};\n");
}

int main(void) {
    generate_crc32c_table();
    return 0;
}
static const uint32_t crc32c_table[16] = {
    0x00000000,     0x105ec76f,     0x20bd8ede,     0x30e349b1,
    0x417b1dbc,     0x5125dad3,     0x61c69362,     0x7198540d,
    0x82f63b78,     0x92a8fc17,     0xa24bb5a6,     0xb21572c9,
    0xc38d26c4,     0xd3d3e1ab,     0xe330a81a,     0xf36e6f75,
};

AAAA0xc38d26c4
BBBB0xd3d3e1ab
CCCC0xe330a81a
DDDD0xf36e6f75

在 Linux 核心原始程式碼中找到 CRC32 的應用案例至少 3 處,並探討其原始程式碼

在 Linux 的 lib 中就有一個 crc32.c 的檔案,其中

u32 crc32_le_base(u32 crc, const u8 *p, size_t len)
{
	while (len--)
		crc = (crc >> 8) ^ crc32table_le[(crc & 255) ^ *p++];
	return crc;
}
EXPORT_SYMBOL(crc32_le_base);

函式針對 little-endian 進行計算,結合查表(crc32table_le)快速查得校驗值。

u32 crc32c_base(u32 crc, const u8 *p, size_t len)
{
	while (len--)
		crc = (crc >> 8) ^ crc32ctable_le[(crc & 255) ^ *p++];
	return crc;
}
EXPORT_SYMBOL(crc32c_base);

與 crc32_le_base 類似,但此處計算 CRC32C 校驗值,CRC32C 使用不同的多項式(通常為 0x82F63B78),查表中用 crc32ctable_le 來計算。

linux/blob/master/fs/jffs2/fs.c

....
ri->hdr_crc = cpu_to_je32(crc32(0, ri, sizeof(struct jffs2_unknown_node)-4));
...

在更新 inode 屬性時,JFFS2 需要保存或更新該 inode 的原始數據,這些數據包括 inode 的號碼、版本、擁有者、時間戳、檔案大小等資訊。為了防止這些資料在寫入 flash 或從 flash 中讀取時發生損壞,程式使用了 CRC32 校驗碼來計算和保存校驗值。

Flash 存儲設備(如 NAND flash)在寫入或讀取過程中容易發生資料錯誤,使用 CRC32 可以快速檢查讀取到的資料是否正確

linux/tools/pcmcia/crc32hash.c

// SPDX-License-Identifier: GPL-2.0-only
/* crc32hash.c - derived from linux/lib/crc32.c, GNU GPL v2 */
/* Usage example:
$ ./crc32hash "Dual Speed"
*/

#include <string.h>
#include <stdio.h>
#include <ctype.h>
#include <stdlib.h>

static unsigned int crc32(unsigned char const *p, unsigned int len)
{
	int i;
	unsigned int crc = 0;
	while (len--) {
		crc ^= *p++;
		for (i = 0; i < 8; i++)
			crc = (crc >> 1) ^ ((crc & 1) ? 0xedb88320 : 0);
	}
	return crc;
}

int main(int argc, char **argv) {
	unsigned int result;
	if (argc != 2) {
		printf("no string passed as argument\n");
		return -1;
	}
	result = crc32((unsigned char const *)argv[1], strlen(argv[1]));
	printf("0x%x\n", result);
	return 0;
}

這段程式碼是計算該字串的 CRC32 校驗值,並以十六進位數形式印出來。使用 CRC32 作為一種雜湊或校驗演算法,將任意字串映射為一個 32 位元的校驗值,根據範例推測用途為快速驗證字串。

測驗 3

socket函式理解

int socket(int domain, int type, int protocol);
//範例:建立一個 IPv4 的 TCP socket
int sockfd = socket(AF_INET, SOCK_STREAM, 0);
if (sockfd < 0) {
    perror("socket");
    exit(1);
}
int bind(int sockfd, const struct sockaddr *addr, socklen_t addrlen);

將建立的 socket 與指定的本機位址(IP 與埠號)綁定。

int listen(int sockfd, int backlog);

啟動監聽( backlog 指定排隊等待連線的最大數)

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

透過監聽 socket 接受一個連線,建立一個新的 socket 對象用於與該客戶端通訊。
read()/write()
在建立連線之後,用來讀取或寫入資料。

先撰寫一個測試程式碼:

#include <arpa/inet.h>
#include <netinet/in.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>

int main(void) {
    int server_fd = socket(AF_INET, SOCK_STREAM, 0);
    if (server_fd < 0) {
        perror("socket");
        exit(1);
    }

    int on = 1;
    if (setsockopt(server_fd, SOL_SOCKET, SO_REUSEADDR, &on, sizeof(on)) < 0) {
        perror("setsockopt");
        exit(1);
    }

    struct sockaddr_in addr;
    addr.sin_family = AF_INET;
    addr.sin_port = htons(8888);
    addr.sin_addr.s_addr = htonl(INADDR_ANY);
    if (bind(server_fd, (struct sockaddr *)&addr, sizeof(addr)) < 0) {
        perror("bind");
        exit(1);
    }

    if (listen(server_fd, 10) < 0) {
        perror("listen");
        exit(1);
    }

    printf("Server listening on port 8888\n");

    while (1) {
        struct sockaddr_in client_addr;
        socklen_t client_len = sizeof(client_addr);
        int client_fd = accept(server_fd, (struct sockaddr *)&client_addr, &client_len);
        if (client_fd < 0) {
            perror("accept");
            continue;
        }
        printf("Client connected: %s:%d\n",
               inet_ntoa(client_addr.sin_addr),
               ntohs(client_addr.sin_port));

        char buf[1024];
        int n = read(client_fd, buf, sizeof(buf));
        if (n > 0) {
            buf[n] = '\0';
            printf("Received: %s\n", buf);
            n = write(client_fd, buf, n);  // echo 給 client
        }
        close(client_fd);
    }
    close(server_fd);
    return 0;
}

這段程式碼可以達成回聲的效果,伺服器持續可接受多個連線,並能與多個 client 反覆互動,但無法讓 client 間互相通訊。

select函式理解

void FD_ZERO(fd_set *set);
void FD_SET(int fd, fd_set *set);

FD_ZERO 會將一個 fd_set 結構「清空」
FD_SET 會將指定的檔案描述符加入到 fd_set 集合中。這個檔案描述符會在後續的 select() 呼叫中被檢查,看是否有特定的 I/O 事件發生(例如可讀、可寫)。

int select(int nfds, fd_set *readfds, fd_set *writefds,
           fd_set *exceptfds, struct timeval *timeout);

nfds : 監控中最高檔案描述符 + 1。

readfds : 指向要檢查「可讀」狀態的 fd_set。

writefds : 要檢查「可寫」狀態的集合,若不需要檢查,所以傳入 NULL。

exceptfds : 用來檢查例外或錯誤狀態,若不需要檢查,傳入 NULL。

timeout : 指向等待時間的結構指標。

解釋上述程式碼運作原理

根據 select 的理解可以得到以下的解答:

IIII : 是目前監控的所有描述符中最大的數值加 1,因此答案為 max_fd

JJJJ : 則為指向要監控的可讀描述符集合的指標,因此答案為 &rfds.

改進網路聊天室的文字呈現介面

目前是使用 ANSI 控制碼去控制使用者顏色辨識不同使用者

#define MAX_BUF 1024 //將 MAX_BUF 事先定義好以便維護

const char *colors[] = {
    "\033[1;31m", // red
    "\033[1;32m", // green
    "\033[1;33m", // yellow
    "\033[1;34m", // blue
    "\033[1;35m", // magenta
    "\033[1;36m", // cyan
    "\033[1;37m"  // white
};

int client_color[FD_SETSIZE] = {0,1,2,3,4,5,6....};

並且在散播訊息時顯現出使用者的 file descriptor 當作使用者編號

/* Format the message to improve presentation:
    * use ANSI escape code */
char formatted[2 * MAX_BUF];
snprintf(formatted, sizeof(formatted), "%s[User %d]:\033[0m %s",
colors[client_color[fd]], fd, buf);
int f_len = strlen(formatted);
...
/* write to them */
if (write(dest_fd, formatted, f_len) < 0) {
...

並且有新連線時通知所有使用者

/* create a buffer */
char buf[20] = "New connection \n";
/* Format the message to improve presentation:
    * use ANSI escape code */
char formatted[50];
snprintf(formatted, sizeof(formatted), "\n%s[User %d]:\033[0m %s",
colors[client_color[new_fd]], new_fd, buf);
int f_len = strlen(formatted);

成效:

image