# 2019q1 Homework1 (lab0)
contributed by < `evanjack2002` >
###### tags: `linux2019`
## [F01: lab0](https://hackmd.io/s/BJA8EgFB4)
### 作業要求
- 在 GitHub 上 fork lab0-c
- 詳細閱讀 [C Programming Lab](https://www.cs.cmu.edu/~213/labs/cprogramminglab.pdf)
- 依據指示著手修改 `queue.[ch]` 和連帶的檔案
- 用 Git 管理各項修改
- 務必詳閱 如何寫好 Git Commit Message
- 除了修改程式，也要編輯「作業區」，增添開發紀錄和 GitHub 連結，提及如何逐步達到要求，以及如何改善效能
- 解釋自動評分系統運作的原理
- 提及 qtest 的行為和裡頭的技巧
- 截止日期：Mar 3, 2019 (含) 之前
## 詳細閱讀 [C Programming Lab](https://www.cs.cmu.edu/~213/labs/cprogramminglab.pdf)
### Knowlege base
1. C programming
2. Linked lists
3. Asympotic (big-Oh) notation
4. Linux Man pages
### Overview
The **queue** contents are represented as a **singly-linked list**, with **each element** represented by a structure of type `list_ele_t`, having fields `value` and `next`, storing **a pointer to a string** and **a pointer to the next list element**, respectively.
### Programming Task
Your task is to modify the code in `queue.h` and `queue.c` to fully implement the following functions.
- `q_new`:Create a new, empty queue.
- `q_free`:Free all storage used by a queue.
- `q_inserthead`:Attempt to insert a new element at the head of the queue (LIFO discipline).
- `q_inserttail`:Attempt to insert a new element at the tail of the queue (FIFO discipline).
- `q_removehead`:Attempt to remove the element at the head of the queue.
- `q_size`:Compute the number of elements in the queue.
- `q_reverse`:Reorder the list so that the queue elements are reversed in order. This function should notallocate or free any list elements (either directly or via calls to other functions that allocate or free listelements.) Instead, it should rearrange the existing elements.
Two of the functions: `q_insert_tail` and `q_size` will require some effort on your part to meet therequired performance standards. We require that your implementations operate in time $O(1)$.
## 解釋自動評分系統運作的原理
- 透過 `driver.py` python script，呼叫 `subprocess.call` 去執行 `qtest` ，並使用 `qtest` 的參數 `-f` 來輸入測試項目的檔案。
```python
fname = "%s/%s.cmd" % (self.traceDirectory, self.traceDict[tid])
vname = "%d" % self.verbLevel
clist = [self.command, self.qtest, "-v", vname, "-f", fname]
try:
retcode = subprocess.call(clist)
```
- 共15個測試項目 trace-01~15，前5個項目各6分，後10個項目各7分，透過 `qtest` 執行成功與否累加積分，總分100。
`maxScores = [0, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7]`
```python
ok = self.runTrace(t)
maxval = self.maxScores[t]
tval = maxval if ok else 0
print("---\t%s\t%d/%d" % (tname, tval, maxval))
score += tval
maxscore += maxval
```
```shell
$ tree ./traces/
./traces/
├── trace-01-ops.cmd
├── trace-02-ops.cmd
├── trace-03-ops.cmd
├── trace-04-ops.cmd
├── trace-05-ops.cmd
├── trace-06-string.cmd
├── trace-07-robust.cmd
├── trace-08-robust.cmd
├── trace-09-robust.cmd
├── trace-10-malloc.cmd
├── trace-11-malloc.cmd
├── trace-12-malloc.cmd
├── trace-13-perf.cmd
├── trace-14-perf.cmd
├── trace-15-perf.cmd
```
## 提及 qtest 的行為和裡頭的技巧
- 透過建立 cmd linked list，根據 cmd 執行對應的 operation，如： `ih` command 的operation 為 `do_insert_head()`。
```clike
add_cmd("ih", do_insert_head, ...);
```
```clike
while (next_cmd && strcmp(argv[0], next_cmd->name) != 0)
next_cmd = next_cmd->next;
if (next_cmd) {
ok = next_cmd->operation(argc, argv);
```
- 透過 `exception_setup(true)` 與 `exception_cancel()` ，實做執行時間超過 time_limit 的 exception。
```clike
if (exception_setup(true))
rval = q_remove_head(q, removes, string_length + 1);
exception_cancel();
```
- `exception_setup(true)`
- 用 `sigsetjmp` 建立返回 jump 點。
- 並啟動 `alarm(time_limit)` timer。
- `sigalrmhandler`
- 如果 alarm timer 到期，會觸發 `SIGALRM` signal。
- 註冊對應 `SIGALRM` 的 signal handler 為 `sigalrmhandler`。
- `sigalrmhandler` 會呼叫 `siglongjmp`，做 "*nonlocal goto*" 到之前建立的 jump 點。
- `exception_cancel()`
- 如果執行的 function（e.q. 上面的 `q_remove_head()`)，在沒有超過 time_limit 時，執行到 `exception_cancel()`。
- `exception_cancel()` 會設定 `alarm(0)` 來停止 alarm timer。
- 透過 Preprocesser，替換 `malloc()` 和 `free()`。
```clike
#define malloc test_malloc
#define free test_free
```
- 透過替換 `malloc` 的 `test_malloc`，來做很多應用。
- 如讓 `option malloc xx` command，使 `malloc()` 有機率回傳 NULL 要不到記憶體配置的狀況。
```clike
static bool fail_allocation()
{
double weight = (double) random() / RAND_MAX;
return (weight < 0.01 * fail_probability);
}
```
## 實做
### q_new()
```clike=
queue_t *q_new()
{
queue_t *q = malloc(sizeof(queue_t));
/* What if malloc returned NULL? */
if (q == NULL)
return NULL;
q->head = NULL;
q->tail = NULL;
q->size = 0;
return q;
}
```
### q_free()
```clike=
void q_free(queue_t *q)
{
/* How about freeing the list elements and the strings? */
/* Free queue structure */
list_ele_t *e;
if (!q)
return;
while (q->head) {
e = q->head;
q->head = q->head->next;
free(e->value);
free(e);
};
free(q);
}
```
### q_insert_head()
```clike=
bool q_insert_head(queue_t *q, char *s)
{
list_ele_t *newh;
unsigned int len;
/* What should you do if the q is NULL? */
if (!q)
return false;
newh = malloc(sizeof(list_ele_t));
if (!newh)
return false;
/* Don't forget to allocate space for the string and copy it */
/* What if either call to malloc returns NULL? */
memset(newh, 0, sizeof(*newh));
len = strlen(s);
newh->value = malloc(sizeof(char) * (len + 1));
if (!newh->value) {
free(newh);
return false;
}
if (q->head == NULL) {
q->tail = newh;
}
strcpy(newh->value, s);
newh->value[len] = '\0';
newh->next = q->head;
q->head = newh;
q->size++;
return true;
}
```
### q_insert_tail()
In time $O(1)$
```clike=
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 *e;
unsigned int len;
if (!q)
return false;
e = malloc(sizeof(list_ele_t));
if (!e)
return false;
len = strlen(s);
e->value = malloc(sizeof(char) * (len + 1));
if (!e->value) {
free(e);
return false;
}
strcpy(e->value, s);
e->value[len] = '\0';
e->next = NULL;
q->tail->next = e;
q->tail = e;
q->size++;
return true;
}
```
### q_remove_head()
```clike=
bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
/* You need to fix up this code. */
unsigned int len;
list_ele_t *e;
if (!q || !q->head)
return false;
e = q->head;
q->head = q->head->next;
if (q->head == NULL)
q->tail = NULL;
if (sp) {
memset(sp, 0, bufsize);
len = strlen(e->value);
if (bufsize > len + 1)
strcpy(sp, e->value);
else
strncpy(sp, e->value, bufsize - 1);
}
free(e->value);
free(e);
q->size--;
return true;
}
```
### q_reverse()
```clike=
void q_reverse(queue_t *q)
{
/* You need to write the code for this function */
list_ele_t *e = NULL;
list_ele_t *rh = NULL; /* reverse head */
if (!q || !q->head)
return;
while (q->head) {
e = q->head;
q->head = q->head->next;
if (rh == NULL) {
rh = e;
rh->next = NULL;
q->tail = rh;
} else {
e->next = rh;
rh = e;
}
}
q->head = rh;
}
```
### q_size()
In time $O(1)$
```clike=
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)
return 0;
return q->size;
}
```
### structure queue_t
```clike=
/* Queue structure */
typedef struct {
list_ele_t *head; /* Linked list of elements */
/*
You will need to add more fields to this structure
to efficiently implement q_size and q_insert_tail
*/
list_ele_t *tail;
unsigned int size;
} queue_t;
```
## 疑問
```shell
valgrind: qtest valgrind_existence
$(eval patched_file := $(shell mktemp /tmp/qtest.XXXXXX))
cp qtest $(patched_file)
chmod u+x $(patched_file)
sed -i "s/alarm/isnan/g" $(patched_file)
```
- `sed -i "s/alarm/isnan/g" $(patched_file)` 用於在 binary 裡，替換 `alarm` 文字成 `isnan` 文字，是為了讓 valgrind 不會有 alarm timer 中順利進行。
- 但不懂為何這樣可行？
## Note
- `sigsetjmp` and `siglongjmp` man page
```clike
#include <setjmp.h>
int setjmp(jmp_buf env);
int sigsetjmp(sigjmp_buf env, int savesigs);
void longjmp(jmp_buf env, int val);
void siglongjmp(sigjmp_buf env, int val);
```
- The functions described on this page are used for performing "nonlocal gotos": **transferring execution from one function to a predetermined location in another function**.
- `sigsetjmp()` and `siglongjmp()` also perform nonlocal gotos, but provide predictable handling of the process signal mask.
- [Linux 核心設計 (Spring 2019) 進度表](http://wiki.csie.ncku.edu.tw/linux/schedule)
:::danger
參考資料應該列出「第一手材料」
:notes: jserv
> 謝謝老師，我在去找找。
:::
- [Linux 核心設計: 第 1 週發展回顧](https://hackmd.io/s/B1RmWVGUE)
- `apt install build-essential git-core cppcheck clang-format valgrind`
Sign in with Wallet
Connect another wallet