2018q3 Homework2 (lab0)
===
contributed by < [`ChingChieh`](https://github.com/ChingChieh) >
###### tags: `sysprog2018`
## 開發紀錄
### 環境
* 系統版本：unbuntu 18.04.1
* gcc 版本：gcc (Ubuntu 7.3.0-16ubuntu3) 7.3.0
## 過程
### queue_t
```c
typedef struct {
list_ele_t *head;
list_ele_t *tail;
size_t size;
} queue_t;
```
因為 [q_insert_tail](#q_insert_tail) 和 [q_size](#q_size) 要達到 $O(1)$ 所以需要額外記住 queue size 和 tail 位子
---
### q_size
```c
int q_size(queue_t *q)
{
/* You need to write the code for this function */
/* Remember: It should operate in O(1) time */
if (q == NULL || q->head == NULL) {
return 0;
}
return q->size;
}
```
---
### q_free
```c
void q_free(queue_t *q)
{
if (q == NULL) {
return;
}
list_ele_t *tmp_next;
while (q->head != NULL) {
tmp_next = q->head->next;
free(q->head->value);
free(q->head);
q->head = tmp_next;
}
free(q);
}
```
要記得先free(q->head->value)再free(q->head)
因為我一開始就沒有用strdup的方式複製字串，所以沒遇到free(q->head->value)會錯誤的問題
---
### q_insert_head
```c=
bool q_insert_head(queue_t *q, char *s)
{
list_ele_t *newh;
/* What should you do if the q is NULL? */
if (q == NULL) {
return false;
}
newh = (list_ele_t *) malloc(sizeof(list_ele_t));
if (newh == NULL) {
return false;
}
size_t s_len = strlen(s) + 1; // Don't forget the \0!!!!!!!
/* Don't forget to allocate space for the string and copy it */
newh->value = (char *) malloc(s_len * sizeof(char));
if (newh->value == NULL) {
free(newh);
return false;
}
strcpy(newh->value, s);
/* What if either call to malloc returns NULL? */
newh->next = q->head;
if (newh->next == NULL) { // Change the tail
q->tail = newh;
}
q->head = newh;
q->size++;
return true;
}
```
要記得malloc的時候要多給他一個 char 的空間存 '\0'
---
### q_insert_tail
```c=
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 */
if (q == NULL) {
return false;
}
list_ele_t *newt;
newt = (list_ele_t *) malloc(sizeof(list_ele_t));
if (newt == NULL) {
return false;
}
long int slen = strlen(s) + 1;
newt->value = (char *) malloc(sizeof(char) * slen);
if (newt->value == NULL) {
free(newt);
return false;
}
strcpy(newt->value, s);
if (q->tail != NULL) {
q->tail->next = newt;
} else {
q->head = newt;
}
q->tail = newt;
newt->next = NULL;
q->size++;
return true;
}
```
---
### q_remove_head
```c=
bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
if (q == NULL || q->head == NULL || bufsize <= 0) {
return false;
}
if (sp != NULL) {
strncpy(sp, q->head->value, bufsize - 1);
sp[bufsize - 1] = '\0';
}
list_ele_t *headnext = q->head->next;
free(q->head->value);
free(q->head);
q->head = headnext;
q->size--;
return true;
}
```
---
### q_reverse
```c
void q_reverse(queue_t *q)
{
if (q == NULL || q->size < 2) {
return;
}
q->tail = q->head;
list_ele_t *prev = NULL;
list_ele_t *temp;
list_ele_t *curr = q->head;
while (curr != NULL) {
temp = curr->next;
curr->next = prev;
prev = curr;
curr = temp;
}
q->head = prev;
}
```
## 進度
```
$ make test
scripts/driver.py
...
...
--- trace-15-perf 7/7
--- TOTAL 100/100
```
## makefile
* rm *~ 意思
* 把檔案結尾是~的檔案刪掉，這種檔案是 editor 產生的備用檔。如果在 .vimrc 設定set backup也可以產生這種備用檔
## 遭遇問題
1. [queue.c:79]: (error) Memory leak: newh
* 原因:當要對 queue 做 insert 的時候總共要 `malloc()` 兩次，如果回傳結果是 NULL 就 return false，但在第二次檢查的時候忘記把第一次 `malloc()` 的空間 free 掉
```clike=
newh = (list_ele_t *) malloc(sizeof(list_ele_t));
if (newh == NULL) {
return false;
}
newh->value = (char *) malloc(s_len * sizeof(char));
if (newh->value == NULL) {
free(newh); //要記得 free 掉之前成功 malloc 的空間
return false;
}
```
## 自動評分系統運作原理
## qtest行為＆技巧
用有沒有 define INTERNAL 來判斷是否使用自定義的malloc和free
在 harrness.h 裡面有
```c
#ifdef INTERNAL
...
#else
#define malloc test_malloc
#define free test_free
#endif
```
帶表如果有先定義INTERNAL就不會把 malloc、free 改成 test_malloc、test_free
---
### 如何偵測buffer overflow
test_malloc 程式碼:
```c=
void *test_malloc(size_t size)
{
...
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;
}
```
每次呼叫test_malloc(size)分配的空間:
```c
malloc(size + sizeof(block_ele_t) + sizeof(size_t));
```
test_malloc return 的是指向size起始address的pointer:
```c
void *p = (void *) &new_block->payload;
```
這裡用到的技巧是arrays of length zero，通常是用在struct的最後一個element，這樣的好處是可以把payload當成block_ele_t後面記憶體位址的開頭
此外再用find_footer()定出size結尾的記憶體位址，然後把後面那塊sizeof(size_t)記憶體的值改成MAGICFOOTER
```c
static size_t *find_footer(block_ele_t *b)
{
size_t *p = (size_t *) ((size_t) b + b->payload_size + sizeof(block_ele_t));
//payload_size 是使用者可以用的空間大小
return p;
}
*find_footer(new_block) = MAGICFOOTER;
```
加上之前把magic_header的值設成MAGICHEADER，所以使用者能合法使用的空間就像被兩塊記憶體空間夾在中間，使用超出size的空間就會改到MAGICFOOTER或MAGICHEADER因此可以在test_free時被偵測出來
Sign in with Wallet
Connect another wallet