---
tags: sysprog
---
# 2019q3 Homework1 (lab0)
contributed by < `yxguo2536` >
## 實驗環境
作業系統 ： Ubuntu 18.04.3
gcc 編譯器 ：gcc 7.4.0
## 實做
根據 C Programming Lab 要求，修改 queue.c 的以下 function和 queue.h 的 資料結構:
1. typedef struct queue_t
2. q_new
3. q_free
4. q_insert_head
5. q_insert_tail
6. q_remove_head
7. q_size
8. q_reverse
### sturct queue_t
原本的 queue_t 為 ：
```clike
typedef struct {
list_ele_t *head;
} queue_t;
```
而後為了實做 $O(1)$ 的 q_insert_tail 和 q_size，增加了2個成員 :
```clike
typedef struct {
list_ele_t *head;
list_ele_t *tail;
int size;
} queue_t;
```
### q_new
* 初始化 queue 列表
* 注意要檢查 malloc 有沒有成功
```clike
queue_t *q_new()
{
queue_t *q = malloc(sizeof(queue_t));
if (!q)
return NULL;
q->head = NULL;
q->tail = NULL;
q->size = 0;
return q;
}
```
### q_free
* 釋放所有 queue 列表的 node 和 queue 本身
```clike
void q_free(queue_t *q)
{
if (!q)
return;
while (q->head) {
list_ele_t *node = q->head;
q->head = q->head->next;
free(node->value);
free(node);
}
free(q);
}
```
### q_insert_head
* 新增一個 node 到 queue 開頭
* 如果第二次 malloc 失敗了，需要先釋放第一次 malloc 的空間再返回
* 如果 queue 是空的，那最後不只要把 head 指向新 node，也要把 tail 指向新 node
```clike
bool q_insert_head(queue_t *q, char *s)
{
if (!q)
return false;
char *newStr = malloc(strlen(s) + 1);
if (!newStr)
return false;
strcpy(newStr, s);
list_ele_t *newh = malloc(sizeof(list_ele_t));
if (!newh) {
free(newStr);
return false;
}
newh->value = newStr;
newh->next = q->head;
if (!q->size)
q->tail = newh;
q->head = newh;
q->size++;
return true;
}
```
### q_insert_tail
* 新增一個 node 到 queue 的結尾
* 同 q_insert_head，需要注意第二次 malloc 失敗時要釋放第一次 malloc 的空間後才能返回
* 不同於 q_insert_head，如果對空的 queue 下 it 指令，會造成 SIGSEGV，而自動評分系統沒考量到這種狀況。 這個錯誤成因在於：當 q_new 的初始化 `q->tail = NULL;` 後碰到`q->tail->next = newh;`，要去存取 `NULL->next` 而導致錯誤。 為解決此問題，需要根據「queue是否為初始狀態」做不同的處理。
```clike
bool q_insert_tail(queue_t *q, char *s)
{
if (!q)
return false;
char *newStr = malloc(strlen(s) + 1);
if (!newStr)
return false;
strcpy(newStr, s);
list_ele_t *newh = malloc(sizeof(list_ele_t));
if (!newh) {
free(newStr);
return false;
}
newh->value = newStr;
newh->next = NULL;
if (!q->size) {
q->head = newh;
q->tail = newh;
} else {
q->tail->next = newh;
q->tail = q->tail->next;
}
q->size++;
return true;
}
```
### q_remove_head
* 調整 queue 列表，移除第一個 node。當然前提是至少有一個 node
```clike
bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
if (!q || !q->head)
return false;
list_ele_t *node = q->head;
q->head = q->head->next;
q->size--;
if (sp) {
strncpy(sp, node->value, bufsize - 1);
sp[bufsize - 1] = '\0';
}
free(node->value);
free(node);
return true;
}
```
### q_size
* 回傳 queue 中的 node 數量
* 要特別判斷 queue 是否存在，不存在則當「 node 數為 0」 處理
```clike
int q_size(queue_t *q)
{
if (!q)
return 0;
return q->size;
}
```
### q_reverse
* 在不額外配置記憶體空間的情況下，反轉從 head 到 tail 的排序順序
* 在此使用 head 和額外 2 個指標進行排序反轉
```clike
void q_reverse(queue_t *q)
{
if (!q || !q->head)
return;
list_ele_t *prev = NULL;
list_ele_t *cur = q->head;
q->tail = q->head;
while (cur) {
q->head = cur;
cur = cur->next;
q->head->next = prev;
prev = q->head;
}
}
```
參考資料：
1. [afcidk的共筆](https://hackmd.io/@afcidk/ry4VZS9SN#q_reverse)
## 自動評分系統運作原理
## 巨集的使用
當初在開發的時候，我曾以 gdb 去查看 back trace，那時發現程式碼中應該呼叫 malloc 的中斷點，竟然是先跳到 test_malloc ，然後才又跳到 malloc。
於是找了一下這 test_malloc 到底從哪來的，後來發現在 harness.h 裡面有這幾行巨集：
```clike
#ifdef INTERNAL
.
.
.
#else
#define malloc test_malloc
#define free test_free
#define strdup test_strdup
#endif
```
也就是說，在編譯時的 preprocessor 階段，當你沒有定義 INTERNAL，這 3 個標準函式就會通過字串處理被調包成其他函式。
所以就要繼續找找看，到底有哪些地方有引入 harness.h、有哪些地方的 malloc 是有被調包的 ：
* qtest.c
```
#define INTERNAL 1
#include "harness.h"
```
* queue.c
```
#include "harness.h"
```
* harness.c
```
#define INTERNAL 1
#include "harness.h"
```
可以看到，雖然引入了 harness.h 的程式碼有三處，但其中 qtest.c 和 harness.c 都不會被調包，因為他們有事先宣告 INTERNAL。
再來，我們進入 harness.c 的實做，看看 test_malloc / free 到底都多幫我們做了些什麼事：
```clike
/* Value at start of every allocated block */
#define MAGICHEADER 0xdeadbeef
/* Value when deallocate block */
#define MAGICFREE 0xffffffff
/* Value at end of every block */
#define MAGICFOOTER 0xbeefdead
/* Byte to fill newly malloced space with */
#define FILLCHAR 0x55
```
```clike
typedef struct BELE {
struct BELE *next;
struct BELE *prev;
size_t payload_size;
size_t magic_header; /* Marker to see if block seems legitimate */
unsigned char payload[0];
/* Also place magic number at tail of every block */
} block_ele_t;
```
### test_malloc
```clike
void *test_malloc(size_t size)
{
if (noallocate_mode) {
report_event(MSG_FATAL, "Calls to malloc disallowed");
return NULL;
}
if (fail_allocation()) {
report_event(MSG_WARN, "Malloc returning NULL");
return NULL;
}
block_ele_t *new_block =
malloc(size + sizeof(block_ele_t) + sizeof(size_t));
if (new_block == NULL) {
report_event(MSG_FATAL, "Couldn't allocate any more memory");
error_occurred = true;
}
new_block->magic_header = MAGICHEADER;
new_block->payload_size = size;
*find_footer(new_block) = MAGICFOOTER;
void *p = (void *) &new_block->payload;
memset(p, FILLCHAR, size);
new_block->next = allocated;
new_block->prev = NULL;
if (allocated)
allocated->prev = new_block;
allocated = new_block;
allocated_count++;
return p;
}
static block_ele_t *allocated = NULL;
```
test_malloc 配置的空間，示意圖如下 :
從程式碼中我們看到：
* 如果我們原本想要呼叫`malloc(100)`，那麼實際執行時會跟系統要求 `100 + sizeof(block_ele_t) + sizeof(size_t)` 大小的空間
```clike
block_ele_t *new_block =
malloc(size + sizeof(block_ele_t) + sizeof(size_t));
```
* block_ele_t 的作用，基本上就是在空間的開頭用一些空間紀錄原本malloc的資訊：
```clike
new_block->magic_header = MAGICHEADER;
new_block->payload_size = size;
```
* 並且，它還很貼心的幫我們把所有用過的 malloc 都串連起來統一管理：
```clike
new_block->next = allocated;
new_block->prev = NULL;
if (allocated)
allocated->prev = new_block;
allocated = new_block;
allocated_count++;
```
串連方式其實就是 queue 的 insert_head，只是 block_ele_t 為 doubly linked list 結構
* 而配置空間的主要區塊，我們實際拿來存放資料的空間，也會被填上 FILLCHAR ( 0x55 ) 做初始化：
```clike
void *p = (void *) &new_block->payload;
memset(p, FILLCHAR, size);
```
其中，這個payload 當初的宣告的型態是`char[0]`，我後來做了小實驗發現 `sizeof(char[0])` 結果為0。根本沒空間，不能紀錄資料的。
不過正因為他不佔空間，`new_block->payload`就等同於指向 block_ele_t 的尾端、size的開頭，以便我們將其填入 0x55
當然，也有另一種等效寫法：
```clike
void *p2 = (void *) (new_block+1);
memset(p, FILLCHAR, size);
```
* 除了開頭有 block_ele_t 幫我們標注 header，空間結尾也有地方標注 footer ：
```clike
*find_footer(new_block) = MAGICFOOTER;
```
```clike
/* Given pointer to block, find its footer */
static size_t *find_footer(block_ele_t *b)
{
size_t *p = (size_t *) ((size_t) b + b->payload_size + sizeof(block_ele_t));
return p;
}
```
這裡可以跟一開始 malloc 的片段做對比：
```clike
block_ele_t *new_block =
malloc(size + sizeof(block_ele_t) + sizeof(size_t));
```
我們可以知道 `b + b->payload_size + sizeof(block_ele_t)`，基本上就是想讓指標跳到 `sizeof(size_t)`的地方。
不過接下來我就懷疑了：這樣真的能指到 size_t 的地方嗎 ?
如果在做記憶體位移，`p+1`的位移「單位」，完全是取決於指標的型態：如果是 `char *p = 0x100`，則 `p+1 == 0x101` ; 如果是 `int *p = 0x100`，則 `p+1 == 0x104`。而因為 size_t 是 8 bytes，所以上述程式碼難道不該寫成 `b + ( b->payload_size + sizeof(block_ele_t) / 8 )` ？
後來才想通：上述的 (size_t) 轉型等於把接下來的操作從「記憶體位移」轉換成「算術運算」。誠然如果是位移，0x100 + 1 = ? 得看指標型態決定單位，但轉換成算術運算後就變成單純的 256 + 1 = ? 的問題了。 而之後的 (size_t*) 轉型則再把「算術運算」轉換成「記憶體位移」，所以 257 → 0x101，這就完成了以 1 為單位的記憶體位移。
### test_free
```clike
void test_free(void *p)
{
if (noallocate_mode) {
report_event(MSG_FATAL, "Calls to free disallowed");
return;
}
if (p == NULL) {
return;
}
block_ele_t *b = find_header(p);
size_t footer = *find_footer(b);
if (footer != MAGICFOOTER) {
report_event(MSG_ERROR,
"Corruption detected in block with address %p when "
"attempting to free it",
p);
error_occurred = true;
}
b->magic_header = MAGICFREE;
*find_footer(b) = MAGICFREE;
memset(p, FILLCHAR, b->payload_size);
/* Unlink from list */
block_ele_t *bn = b->next;
block_ele_t *bp = b->prev;
if (bp)
bp->next = bn;
else
allocated = bn;
if (bn)
bn->prev = bp;
free(b);
allocated_count--;
}
```
* 一開始，得先從輸入 `p` 找到實際 malloc 回傳的開頭 `b`
```clike
```
* 在 find_header() 裡面會檢查 MAGICHEADER 的完整性
```clike
if (b->magic_header != MAGICHEADER) {
report_event(
MSG_ERROR,
"Attempted to free unallocated or corrupted block. Address = %p",
p);
error_occurred = true;
}
```
出了 find_header() 會緊接著呼叫 find_footer()，而後再檢查 MAGICFOOTER 的完整性
```clike
size_t footer = *find_footer(b);
if (footer != MAGICFOOTER) {
report_event(MSG_ERROR,
"Corruption detected in block with address %p when "
"attempting to free it",
p);
error_occurred = true;
}
```
>這裡的設計我覺得有小瑕疵：find_header() 裡面會檢查 MAGICHEADER ; find_footer() 裡面卻不檢查 MAGICFOOTER。
>而且在find_header()裡出現的錯誤訊息是"Attempted to free ..."，但 free 明明是 test_free() 的工作而不是 find_header() 該管的，所以我覺得 header、footer 的檢查應該統一寫在 test_free() 裡面會比較好
>[name=yxguo]
* 然後，藉由改變 header、footer 的值，標注此 block 為 free 狀態
```clike
b->magic_header = MAGICFREE;
*find_footer(b) = MAGICFREE;
```
* 再把實際存放 data 的空間清空，初始化成 FILLCHAR
```clike
memset(p, FILLCHAR, b->payload_size);
```
* 最後，把該 block 從 doubly linked list 紀錄中刪除
```clike
block_ele_t *bn = b->next;
block_ele_t *bp = b->prev;
if (bp)
bp->next = bn;
else
allocated = bn;
if (bn)
bn->prev = bp;
```
### 結論
觀察 test_malloc / test_free 對 MAGICHEADER、MAGICFREE、MAGICFOOTER、FILLCHAR 這些巨集的使用，基本上可以理解為 「malloc 後做xxx標記，free前檢查有沒有xxx」和「free後做ooo標記，malloc前檢查是不是ooo」
所以這些 magic number 其實就是一種「通關密語」，它不一定要是 0xdeadbeef ，它也可以是 0x01、0x02、0x03 等等，反正只要 malloc 和 free 雙方有先 say 好就行。
參考資料 ：
1. [colinyoyo26的共筆](https://hackmd.io/@colinyoyo26/2019q3lab0#%E5%B7%A8%E9%9B%86%E7%9A%84%E4%BD%BF%E7%94%A8)
2. [afcidk的共筆](https://hackmd.io/@afcidk/ry4VZS9SN#%E7%82%BA%E4%BB%80%E9%BA%BC%E9%9C%80%E8%A6%81-function-hooking)
## Signal
作業系統中有 Signal 的機制，可以傳送訊號給其他程式，比如：用鍵盤按下 Ctrl+C ，作業系統會傳一個 SIGINT 訊號給程式（行程），而程式收到了訊號後就一定得暫停當下的作業，優先處理訊號。
至於如何「處理」，程式會有預設行為，根據不同訊號有不同處理行為，比如：
|Signal | Description | Default Action|
|-|-|-|
|SIGSEGV |Invalid memory reference|terminate the process|
|SIGALRM |Timer signal from alarm()| terminate the process|
|SIGWINCH|Window resize signal|ignore the signal|
但既然是「預設」，代表其實我們可以更改他的行為，比如你想要在收到 SIGINT 後先寫個log檔、做些善後再退出。
而 qtest.c 裡面就改變了 SIGSEGV 和 SIGALAM 的行為：
```clike
static void queue_init()
{
fail_count = 0;
q = NULL;
signal(SIGSEGV, sigsegvhandler);
signal(SIGALRM, sigalrmhandler);
}
```
```clike
void sigsegvhandler(int sig)
{
trigger_exception(
"Segmentation fault occurred. You dereferenced a NULL or invalid "
"pointer");
}
```
```clike
void sigalrmhandler(int sig)
{
trigger_exception(
"Time limit exceeded. Either you are in an infinite loop, or your "
"code is too inefficient");
}
```
可以看到，現在程式收到 SIGSEGV 和 SIGALRM 後的處理流程都一樣的 — 呼叫 trigger_exception：
```clike
void trigger_exception(char *msg)
{
error_occurred = true;
error_message = msg;
if (jmp_ready)
siglongjmp(env, 1);
else
exit(1);
}
```
而 trigger_exception() 的行為，基本上就是記錄即將打印的錯誤訊息，然後呼叫 siglongjmp()
根據 [man page](https://linux.die.net/man/3/siglongjmp) 描述：
>longjmp() restores the environment saved by the last call of setjmp(3) with the corresponding env argument.
所以 siglongjmp() 得跟 sigsetjmp() 一起探討，既然在 trigger_exception 會使用到 siglongjmp()，那就得看看什麼時候設定了 sigsetjmp()
* harness.c
```clike=
bool exception_setup(bool limit_time)
{
if (sigsetjmp(env, 1)) {
/* Got here from longjmp */
jmp_ready = false;
if (time_limited) {
alarm(0);
time_limited = false;
}
if (error_message) {
report_event(MSG_ERROR, error_message);
}
error_message = "";
return false;
} else {
/* Got here from initial call */
jmp_ready = true;
if (limit_time) {
alarm(time_limit);
time_limited = true;
}
return true;
}
}
```
再根據 [man page](https://linux.die.net/man/3/sigsetjmp) 所說：
>setjmp() and sigsetjmp() return 0 if returning directly, and nonzero when returning from longjmp(3) or siglongjmp(3) using the saved context.
也就是說，上述 line 3 是一個關鍵：這裡會被執行 2 次，第一次是在初始設定，回傳值0，執行`else{ ... }` ; 第二次是 setlongjmp() 回來，回傳值1，執行`if{ ... }`。
如果是從 setlongjmp() 返回的，會呼叫 report_event() 把錯誤訊息打印在終端，但因為這裡帶的參數只是 MSG_ERROR，所以不會終止程式。 （ 要是MSG_FATAL 才會終止 ）
* report.c
```clike
void report_event(message_t msg, char *fmt, ...)
{
va_list ap;
bool fatal = msg == MSG_FATAL;
// ...
if (fatal) {
if (fatal_fun)
fatal_fun();
exit(1);
}
}
```
這也說明了為什麼 qtest 收到 SIGSEGV 後還是會繼續執行。
<br>
現在，我們知道 qtest 會更改訊號處理流程，當 SIGSEGV 或 SIGALRM 發生，就會回到 exception_setup() 裡面繼續執行。 那下一步我們就要了解， exception_setup() 是在哪裡被 setup 的：
* qtest.c
```clike
bool do_new(int argc, char *argv[])
{
// ...
if (exception_setup(true))
q = q_new();
exception_cancel();
// ...
}
bool do_free(int argc, char *argv[])
{
// ...
if (exception_setup(true))
q_free(q);
exception_cancel();
// ...
}
bool do_insert_head(int argc, char *argv[])
{
// ...
if (exception_setup(true)) {
// ...
}
exception_cancel();
// ...
}
.
.
.
```
可以看到，在 qtest.c 裡面，呼叫 q_xxx() 前都會設立返回點，只要在 q_xxx() 裡面出現 SIGALRM 或 SIGSEGV，就會中斷執行跳回 exception_setup()
而在 qtest.c 的最後，會再呼叫 exception_cancel() 設 `jmp_ready` 為假，藉此擋掉對 siglongjmp() 的呼叫：
* harness.c
```clike
void exception_cancel()
{
if (time_limited) {
alarm(0);
time_limited = false;
}
jmp_ready = false;
error_message = "";
}
void trigger_exception(char *msg)
{
error_occurred = true;
error_message = msg;
if (jmp_ready)
siglongjmp(env, 1);
else
exit(1);
}
```
所以 exception_cancel() 後就算再發生 SIGALRM 或 SIGSEGV，也不會再有機會 回到 exception_setup() 裡面。
### 參考資料
1. [signal - Linux man page](http://man7.org/linux/man-pages/man7/signal.7.html)
2. [siglongjmp - Linux man page](https://linux.die.net/man/3/siglongjmp)
3. [sigsetjmp - Linux man page](https://linux.die.net/man/3/sigsetjmp)
## Valgrind 運作原理
進行中
## dudect
進行中
Sign in with Wallet
Connect another wallet