owned this note
owned this note
Published
Linked with GitHub
# 2019q3 Homework2 (lab0)
contributed by < `colinyoyo26` >
:::danger
注意共筆格式的要求
:::
## 實驗環境
- 作業系統: Ubuntu Linux 16.04.6
- 編譯器版本： gcc 7.4.0
## 實作過程
### queue.h
```cpp
typedef struct {
list_ele_t *head;
list_ele_t *tail;
size_t size;
} queue_t;
```
- 增加了 `tail`和 `size`分別為了在 O(1) 時間 insertion 還有 return size
### queue.c
#### q_insert_head
- 一開始從這個 function 開始實作但是沒有檢查以下情況
- null ptr
- fail to malloc
- 原本用分別在兩個 malloc 後用 if 檢查 fail to malloc 後來為了精簡行數改成多用一個 variable 只剩一個 if
:::danger
程式碼縮排是 4 個空白字元，K&R 風格，請連同 HackMD 程式碼列表也改為一致的風格
:notes: jserv
:::
```cpp
bool q_insert_head(queue_t *q, char *s)
{
list_ele_t *newh;
char *str;
if (!q)
return false;
newh = malloc(sizeof(list_ele_t));
str = malloc(strlen(s) * sizeof(char) + 1);
if (!newh || !str) {
free(str);
free(newh);
return false;
}
newh->value = str;
strcpy(newh->value, s);
newh->next = q->head;
q->head = newh;
if (!q->tail)
q->tail = q->head;
q->size++;
return true;
}
```
#### q_insert_tail
- 這部份遇到的問題和 q_insert_head 一樣
```cpp
bool q_insert_tail(queue_t *q, char *s)
{
/* You need to write the complete code for this function */
/* Remember: It should operate in O(1) time */
list_ele_t *newh;
char *str;
if (!q || !s)
return false;
newh = malloc(sizeof(list_ele_t));
str = malloc(strlen(s) * sizeof(char) + 1);
if (!newh || !str) {
free(str);
free(newh);
return false;
}
newh->value = str;
strcpy(newh->value, s);
if (!q->head) {
q->head = newh;
q->tail = newh;
}
q->tail->next = newh;
newh->next = NULL;
q->tail = newh;
q->size++;
return true;
}
```
#### q_remove_head
- 這邊比較大的問題是忘記設置 null char
```cpp
bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
if (!q || !q->head)
return false;
if (bufsize > 0) {
memset(sp, '\0', bufsize);
strncpy(sp, q->head->value, bufsize - 1);
}
list_ele_t *tem = q->head;
q->head = q->head->next;
free(tem->value);
free(tem);
q->size--;
return true;
}
```
#### q_size
- 最後一關卡在這邊忘記檢查 null ptr
```cpp
int q_size(queue_t *q)
{
return !q ? 0 : q->size;
}
```
#### q_reverse
- 原本的 code
```cpp
void q_reverse(queue_t *q)
{
if (!q || q->size < 2)
return;
list_ele_t *cur = q->head, *prev = NULL, *tem;
q->tail = q->head;
while (cur) {
tem = cur;
cur = cur->next;
tem->next = prev;
prev = tem;
}
q->head = prev;
}
```
- ~~後來改成這樣省掉一個 local variable 還有一行 code~~
```cpp
void q_reverse(queue_t *q)
{
if (!q || q->size < 2)
return;
list_ele_t *cur = q->head, *prev = NULL;
q->tail = q->head;
while (cur) {
q->head = cur;
cur = cur->next;
q->head->next = prev;
prev = q->head;
}
}
```
- 上次講到程式優化後想到這邊的問題於是把未經優化的組語拿出來看看
- 用 `gcc -Og -S` 編譯
- 以下是迴圈的部份，其中 `(%rax)` 是從 `%rax` 指向的位址取值
- 可以看出後者反而要 4 次 dereference 而且還多一道指令，不是一個好的作法
##### 前者
```
.L4:
movq 8(%rax), %rcx
movq %rdx, 8(%rax)
movq %rax, %rdx
movq %rcx, %rax
.L3:
testq %rax, %rax
jne .L4
```
##### 後者
```
.L8:
movq %rax, (%rdi)
movq 8(%rax), %rcx
movq %rdx, 8(%rax)
movq (%rdi), %rdx
movq %rcx, %rax
.L7:
testq %rax, %rax
jne .L8
```
#### q_free
- 這邊直接 reuse q_remove_head 的部份避免寫重複的 code
- 原本有檢查 null ptr 但是 free 和 q_remove_head 就沒多寫了
```cpp
void q_free(queue_t *q)
{
while (q_remove_head(q, NULL, 0))
;
free(q);
}
```
qtest signal handling
---
- 從 do_new 流程說明
- 先看了解裡面用到的 time limit 機制以及處理 SIGSEGV 的方法 qtest.c 定義下面兩個 function
```cpp
void sigalrmhandler(int sig)
{
trigger_exception(
"Time limit exceeded. Either you are in an infinite loop, or your "
"code is too inefficient");
}
static void queue_init()
{
fail_count = 0;
q = NULL;
signal(SIGSEGV, sigsegvhandler);
signal(SIGALRM, sigalrmhandler);
}
```
- Llinux Programmer's manual
- alarm() arranges for a SIGALRM signal to be delivered to the calling process in seconds seconds. If seconds is zero, any pending alarm is canceled.
- signal() returns the previous value of the signal handler, or SIG_ERR on error. In the event of an error, errno is set to indicate the cause.
- sigsetjmp() return 0 if returning directly, and nonzero when returning from longjmp(3) or siglongjmp(3) using the saved context.
> 用 signal 搭配 alarm 可以指定秒數呼叫 sigsegvhandler
> 捕捉 SIGSEGV 信號，呼叫 sigsegvhandler
> sigsetjm 會把 stack context 存在 envy 並在目前位址作記號，如果從 siglongjmp 返回則 return nonzero
- C99 對信號的闡述
- SIGSEGV: an invalid access to storage
- C99 關於 signal handler
- The signal function chooses one of three ways in which receipt of the signal number sigis to be subsequently handled. If the value offunc is SIG_DFL, default handlingfor that signal will occur.Ifthe value offuncis SIG_IGN,the signal will be ignored. Otherwise, funcshall point to a function to be called when that signal occurs. An invocation of such a function because of a signal, or (recursively) of any further functionsc alled by that invocation (other than functions in the standard library), is called a signal handler.
> signal 發生時呼叫標準函式庫以外的函式稱作 signal handler
- 寫了以下 program 幫助讀者理解
```cpp
#include <stdio.h>
#include <unistd.h>
#include <stdint.h>
#include <stdlib.h>
#include <signal.h>
#include <setjmp.h>
static jmp_buf env;
void handler(){
printf("time out! now in handler function\n");
siglongjmp(env, 1);
}
int main(int argc, char** argv){
uint32_t limit_time = atoi(argv[1]), sleep_time = atoi(argv[2]);
printf("limit time: %d sleep time:%d\n", limit_time, sleep_time);
signal(SIGALRM, handler);
alarm(limit_time);
if(sigsetjmp(env, 1)){
printf("we'll be here after call siglongjmp\n");
return 0;
}
sleep(sleep_time);
printf("finish on time\n");
return 0;
```
執行結果:
```shell
$ ./a 1 2
limit time: 1 sleep time:2
time out! now in handler function
we'll be here after call siglongjmp
$ ./a 2 1
limit time: 2 sleep time:1
finish on time
```
- 接下來我們看到定義在 qtest.c 內的 do_new 以及 harness.c 內的 error_check exception_setup 以及 trigger_exception
```cpp
bool do_new(int argc, char *argv[])
{
if (argc != 1) {
report(1, "%s takes no arguments", argv[0]);
return false;
}
bool ok = true;
if (q != NULL) {
report(3, "Freeing old queue");
ok = do_free(argc, argv);
}
error_check();
if (exception_setup(true))
q = q_new();
exception_cancel();
qcnt = 0;
show_queue(3);
return ok && !error_check();
}
```
```cpp
/*
Return whether any errors have occurred since last time set error limit
*/
bool error_check()
{
bool e = error_occurred;
error_occurred = false;
return e;
}
/*
* Prepare for a risky operation using setjmp.
* Function returns true for initial return, false for error return
*/
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;
}
}
```
```cpp
void trigger_exception(char *msg)
{
error_occurred = true;
error_message = msg;
if (jmp_ready)
siglongjmp(env, 1);
else
exit(1);
}
```
> 注意 do_new 有先 call error_check 為了把 error_occurred 清成 false
- do_new 檢查完幾個 if statement 就會進入 exception_setup 設置 alarm 然後在 call 我們實作的 q_new
- 如果沒超時就會繼續執行下去
- 如果超時
- 直接跳到 sigalrmhandler 設置 error msg
- call trigger_exception 將 error_occurred 設成 true
- 再從 siglongjmp 返回 exception_setup 進入 if statement 進行錯誤處理，最後 return false
:::danger
應該一併提及目前實作的缺失和可改進之處，著手修改
:notes: jserv
:::
### qtest 缺失以及改進
巨集的使用
---
- 在 harness.h 可以看但以下巨集，其實我們的 malloc 和 free 會調用到 test_malloc 以及 test_free
```cpp
#else
/* Tested program use our versions of malloc and free */
#define malloc test_malloc
#define free test_free
#define strdup test_strdup
#endif
```
- 再來看到定義在 harness.c 的 struct 以及巨，先做簡單的整理
- MAGICHEADER 辨別空間是否 allocated
- MAGICFREE 辨別空間是否已經 free
- MAGICFOOTER 辨別空間是否發生損毀
- FILLCHAR 用來清空 memory content
```cpp
/* 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
```
```cpp
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
```cpp
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;
}
```
- 首先看其中的 code ，在 malloc 時多塞入了 sizeof(block_ele_t) + sizeof(size_t) 的空間很明顯是要多加入這兩個型態的物件，紀錄某些資訊
```cpp
block_ele_t *new_block =
malloc(size + sizeof(block_ele_t) + sizeof(size_t));
```
```cpp
new_block->magic_header = MAGICHEADER;
new_block->payload_size = size;
*find_footer(new_block) = MAGICFOOTER;
```
- 來看到 find_footer 搭配上面一起看，可以看出 malloc 的全部空間中
- 首段先放一個 block_ele_t 紀錄 size 以及 MAGICHEADER
- 尾端放一個 size_t 紀錄 MAGICFOOTER
```cpp
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;
}
```
- 繼續往下看，以下可以看出 unsigned char payload[0] 的作用了，宣告 size 為 0 的 array 是為了方便指定 base address
```cpp
void *p = (void *) &new_block->payload;
```
- 把 memory content 清成 FILLCHAR
``` cpp
memset(p, FILLCHAR, size);
```
- 把 malloc 的空間串起來
- allocated 是 global variable 存放上一個 malloc 的空間
```cpp
new_block->next = allocated;
new_block->prev = NULL;
if (allocated)
allocated->prev = new_block;
allocated = new_block;
allocated_count++;
```
### test_free
```cpp
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--;
}
```
- 先找到真正的 base address
```cpp
block_ele_t *b = find_header(p);
```
- 在 find_header 發現 MAGICHEADER 用來辨別該空間是否 allocated
```cpp
if (b->magic_header != MAGICHEADER) {
report_event(
MSG_ERROR,
"Attempted to free unallocated or corrupted block. Address = %p",
p);
error_occurred = true;
}
```
- 檢查尾端是否有 malloc 時存入的 MAGICFOOTER 辨別空間是否發生不預期的損毀，並指定給 magic_header MAGICFREE 表示已經 free
```cpp
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;
```
## 參考資料
* [afcidk 的共筆](https://hackmd.io/@afcidk/ry4VZS9SN)
* [sigsetjmp函數](http://www.voidcn.com/article/p-knxhrsns-bgz.html)
Google Drive
Gist
Clipboard
Sign in with Wallet
