---
tags: linux2022
---
# 2022q1 Homework1 (lab0)
contributed by < [ShienF](https://github.com/ShienF/lab0-c) >
## 實驗環境
```shell
$ gcc --version
gcc (Ubuntu 9.3.0-17ubuntu1~20.04) 9.3.0
$ lscpu
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Byte Order: Little Endian
CPU(s): 8
On-line CPU(s) list: 0-7
Thread(s) per core: 2
Core(s) per socket: 4
Socket(s): 1
NUMA node(s): 1
Vendor ID: GenuineIntel
CPU family: 6
Model: 158
Model name: Intel(R) Core(TM) i7-7700HQ CPU @ 2.80GHz
Stepping: 9
CPU MHz: 2800.000
CPU max MHz: 3800.0000
CPU min MHz: 800.0000
BogoMIPS: 5599.85
Virtualization: VT-x
L1d cache: 128 KiB
L1i cache: 128 KiB
L2 cache: 1 MiB
L3 cache: 6 MiB
NUMA node0 CPU(s): 0-7
```
## 作業要求
> [lab0](https://hackmd.io/@sysprog/linux2022-lab0)
## 開發前準備
### Makefile
`##` 指的是我另補充的註解
```cmake=
CC = gcc
## kind of macro in c, but use with this: $()
CFLAGS = -O1 -g -Wall -Werror -Idudect -I.
## CFLAGS:Extra flags to give to the C compiler
GIT_HOOKS := .git/hooks/applied
## := will be assigned immediately while = will be eassigned in the end
DUT_DIR := dudect
all: $(GIT_HOOKS) qtest
tid := 0
# Control test case option of valgrind
ifeq ("$(tid)","0")
TCASE :=
else
TCASE := -t $(tid)
endif
# Control the build verbosity
ifeq ("$(VERBOSE)","1")
Q :=
VECHO = @true
else
Q := @
VECHO = @printf
endif
## @ don't show the command
# Enable sanitizer(s) or not
ifeq ("$(SANITIZER)","1")
# https://github.com/google/sanitizers/wiki/AddressSanitizerFlags
CFLAGS += -fsanitize=address -fno-omit-frame-pointer -fno-common
LDFLAGS += -fsanitize=address
## LDFLAGS: Extra flags to give to compilers when they are supposed to invoke the linker,\
## ‘ld’, such as -L.
## += means concatenate
endif
$(GIT_HOOKS):
@scripts/install-git-hooks
@echo
## echo means show in the termianl; @ means don't show this "echo" command
OBJS := qtest.o report.o console.o harness.o queue.o \
random.o dudect/constant.o dudect/fixture.o dudect/ttest.o \
linenoise.o
deps := $(OBJS:%.o=.%.o.d)
qtest: $(OBJS)
$(VECHO) " LD\t$@\n"
$(Q)$(CC) $(LDFLAGS) -o $@ $^ -lm
## $@ means the file name of the target of the rule.
## $^ means the names of all the prerequisites, with spaces between them.
## $< means the name of the first prerequisite.
%.o: %.c
@mkdir -p .$(DUT_DIR)
$(VECHO) " CC\t$@\n"
$(Q)$(CC) -o $@ $(CFLAGS) -c -MMD -MF .$@.d $<
## -MMD means avoid to create header file
## % means every string
## target: dependencies
## to do the commands
check: qtest
./$< -v 3 -f traces/trace-eg.cmd
test: qtest scripts/driver.py
scripts/driver.py -c
valgrind_existence:
@which valgrind 2>&1 > /dev/null || (echo "FATAL: valgrind not found"; exit 1)
valgrind: valgrind_existence
# Explicitly disable sanitizer(s)
$(MAKE) clean SANITIZER=0 qtest
$(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)
scripts/driver.py -p $(patched_file) --valgrind $(TCASE)
@echo
@echo "Test with specific case by running command:"
@echo "scripts/driver.py -p $(patched_file) --valgrind -t <tid>"
## shell means execute at shell
clean:
rm -f $(OBJS) $(deps) *~ qtest /tmp/qtest.*
rm -rf .$(DUT_DIR)
rm -rf *.dSYM
(cd traces; rm -f *~)
-include $(deps)
```
## 開發過程
### q_new
因為要創立一個新的 queue ，所以要配置一個空間給串起這個 queue 的 `struct list_head`。
在配置空間後要注意是否為 NULL（無法配置記憶體），若非 NULL 則要對此 `struct list_head` 初始化，否則若下一步為刪除 queue 有可能會造成不如預期的結果。
```c
/*
* Create empty queue.
* Return NULL if could not allocate space.
*/
struct list_head *q_new()
{
struct list_head *head;
head = malloc(sizeof(struct list_head));
if (!head) {
free(head);
return NULL;
} else {
INIT_LIST_HEAD(head);
return head;
}
}
```
### q_free
在釋放 queue 的記憶體空間時，原本的想法為運用 `list.h` 裡的 `list_for_each_safe` 迭代 queue 裡每個 `struct list_head` 的地址，但參考了 [eric88525](https://hackmd.io/@eric88525/linux2022-lab0)，透過`list_for_each_entry_safe`迭代每個 queue 的主體： `element_t` 的地址，再釋放掉才是正確的，否則會漏釋放 `element_t` 除了 `struct list_head` 的其他成員，如 `char *`。
另外在宣告 `element_t *` 時，是不需要再對其配置記憶體空間的，因為此指標只是用來存取迭代時的指標。宣告後也注意要初始化，避免造成不如預期的結果。
最後還釐清了一件事：`free`了指標，意思是指標指向的內容被清掉，指標本身仍存在。
```c
/* Free all storage used by queue */
void q_free(struct list_head *l)
{
if (!l)
return;
element_t *node = NULL, *safe = NULL;
list_for_each_entry_safe (node, safe, l, list) {
q_release_element(node);
}
free(l);
}
```
### q_insert_head ＆ q_insert_tail
在原有的 queue 裡插入新的元素時，因為傳進此 function 的參數為 string，因此需要配置一個queue主體：`element_t` 的記憶體空間，再把此 string assign 給此 queue（`element_t` 裡的 `char *value`）。
一開始的作法並未配置string的空間，得到以下 error。
:::danger
ERROR: Need to allocate separate string for each queue element
:::
參考了 [Chao-Shun-Cheng](https://hackmd.io/@Chao-Shun-Cheng/linux2022-lab0)，配置了字串長度的記憶體空間，最後利用 `list.h` 裡的 `list_add` 將新的 `element_t->list` 加入原有的 `head` 裡。
`strlen` 並不含`'\0'`，因此在配置記憶體空間時需多加一。
第三個 `if` 要注意若 `element->value` 未配置成功，前面配置的 `element_t` 也需釋放。
`q_insert_head` 及 `q_insert_tail`可以透過`list_add` 及 `list_add_tail` 來區別。
```c
/*
* Attempt to insert element at head of queue.
* Return true if successful.
* Return false if q is NULL or could not allocate space.
* Argument s points to the string to be stored.
* The function must explicitly allocate space and copy the string into it.
*/
bool q_insert_head(struct list_head *head, char *s)
{
if (!head)
return false;
element_t *element = malloc(sizeof(element_t));
if (!element)
return false;
int len = strlen(s);
element->value = malloc(sizeof(char) * len + 1);
if (!element->value) {
free(element);
return false;
}
strncpy(element->value, s, len + 1);
list_add(&element->list, head);
return true;
}
```
### q_remove_head ＆ q_remove_tail
刪除 queue 裡第一個元素，並回傳此第一個元素。利用 `list.h` 裡的 `list_first_entry` 將第一個 `element_t` 的地址取出，用來之後取出其成員 `char *value` 及 function 的回傳值。
再運用`list.h` 裡的 `list_del` 把 `head->next` ，注意根據[你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list#Linked-list-%E5%9C%A8-Linux-%E6%A0%B8%E5%BF%83%E5%8E%9F%E5%A7%8B%E7%A8%8B%E5%BC%8F%E7%A2%BC)其中的==Linked list 在 Linux 核心原始程式碼==， `head` 本身並不為 `element_t`。所以要移除的元素為 `head->next`。
另外應盡量避免 `strcpy` 改用 `strncpy` 較為安全。 `strncpy` 的數量應包含 `'\0'`。`sp`的結尾應含有 `'\0'`。
`q_remove_head` 及 `q_remove_tail`可以透過`list_first_entry`，`list_last_entry`，以及 `list_del(head->next)`，`list_del(head->prev)` 來區別。
```c
/*
* Attempt to remove element from head of queue.
* Return target element.
* Return NULL if queue is NULL or empty.
* If sp is non-NULL and an element is removed, copy the removed string to *sp
* (up to a maximum of bufsize-1 characters, plus a null terminator.)
*
* NOTE: "remove" is different from "delete"
* The space used by the list element and the string should not be freed.
* The only thing "remove" need to do is unlink it.
*
* REF:
* https://english.stackexchange.com/questions/52508/difference-between-delete-and-remove
*/
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head))
return NULL;
element_t *target = list_first_entry (head, element_t, list);
list_del(head->next);
if (sp) {
strncpy(sp, target->value, bufsize);
sp[bufsize - 1] = '\0';
}
return target;
}
```
### q_release_element
```c
/*
* WARN: This is for external usage, don't modify it
* Attempt to release element.
*/
void q_release_element(element_t *e)
{
free(e->value);
free(e);
}
```
### q_size
運用`list.h` 裡的 `list_for_each` 迭代 queue 裡的`struct head_list`，迭代次數即為 queue 裡的元素個數。
```c
/*
* Return number of elements in queue.
* Return 0 if q is NULL or empty
*/
int q_size(struct list_head *head)
{
if (!head || list_empty(head))
return 0;
int len = 0;
struct list_head *li;
list_for_each (li, head)
len++;
return len;
}
```
### q_delete_mid
參考[你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list#Linked-list-%E5%9C%A8-Linux-%E6%A0%B8%E5%BF%83%E5%8E%9F%E5%A7%8B%E7%A8%8B%E5%BC%8F%E7%A2%BC)其中的==案例探討: Leetcode 2095. Delete the Middle Node of a Linked List==，利用指標的指標 `**indir` 來簡化程式碼。首先將 `**indir` 初始化為指向 `head->next` 的指標，利用快慢指標的概念，快指標走兩步，慢指標的指標走一步，當快指標走到 `head` 時（不含 `head` 的元素個數為偶數時），或快指標走到的元素下一元素為 `head` 時（不含 `head` 的元素個數為奇數時），慢指標的指標即為指向 mid 的指標的指標，因為快指標走的步數為慢指標的指標的兩倍。
注意 queue 裡的元素都是由 `head->next` 為起始。
為了避免上述==案例探討==中提到 heap-use-after-free 的問題，迴圈結束後另外宣告一個指標來接慢指標，再運用`list.h` 裡的 `list_del` 將 mid 的前後指標互相接上，再使用 `q_release_element` 釋放其記憶體空間。
```c
/*
* Delete the middle node in list.
* The middle node of a linked list of size n is the
* ⌊n / 2⌋th node from the start using 0-based indexing.
* If there're six element, the third member should be return.
* Return true if successful.
* Return false if list is NULL or empty.
*/
bool q_delete_mid(struct list_head *head)
{
if (!head || list_empty(head))
return false;
struct list_head **indir = &head->next;
for (struct list_head *fast = head->next;
fast != head && fast->next != head; fast = fast->next->next)
indir = &(*indir)->next;
struct list_head *del = *indir;
list_del(del);
element_t *del_element = list_entry (del, element_t, list);
q_release_element(del_element);
return true;
}
```
### q_delete_dup
跟 [LeetCode 82. Remove Duplicates from Sorted List II](https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/) 相同，要刪掉 ascending list 中重複的元素，運用`list.h` 裡的 `list_for_each_entry_safe` 迭代，除了每個 `element_t` 的地址之外，還可以先得之下一個 `element_t` 的地址，如此可以檢查當前及下個元素的字串是否相同。
另外利用變數 `check` 確認在上一個迴圈是否有重複的字串，若有則當前的元素也必須刪除，因為此當前元素即為上一個迴圈的下一個 `element_t`。
第一個 `if` 若未判斷下個 `element_t` 是否為 `head` 則會出現錯誤，參考 [laneser](https://hackmd.io/@laneser/linux2022_lab0)，新增了此條件。
```c
/*
* Delete all nodes that have duplicate string,
* leaving only distinct strings from the original list.
* Return true if successful.
* Return false if list is NULL.
*
* Note: this function always be called after sorting, in other words,
* list is guaranteed to be sorted in ascending order.
* // https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
*/
bool q_delete_dup(struct list_head *head)
{
if (!head)
return false;
element_t *element, *next_element;
bool check = 0;
list_for_each_entry_safe (element, next_element, head, list) {
if (&next_element->list != head &&
strcmp(next_element->value, element->value) == 0) {
list_del(&element->list);
q_release_element(element);
check = 1;
} else if (check) {
list_del(&element->list);
q_release_element(element);
check = 0;
}
}
return true;
}
```
### q_swap
思考一陣子想不出解法，於是參考 [cwl0429](https://hackmd.io/yJclgTuVRzeVCjHH9FtUVw#q_free)：在迴圈裡透過`list.h` 裡的 `list_move` 將現在這個元素 `cur` 移動到下一個元素 `cur->next` 的後面，就可以達到兩兩交換的結果。
另外由於兩兩指標交換，上ㄧ次迭代時的`cur` 位置已經向後移一個，上一次迭代結束後又向後移一個，總共後移兩次，如此剛好能達成被交換過的 pair 不會再被交換。
```c
/*
* Attempt to swap every two adjacent nodes.
// https://leetcode.com/problems/swap-nodes-in-pairs/
*/
void q_swap(struct list_head *head)
{
if (!head)
return;
struct list_head *cur;
for (cur = head->next; cur != head && cur->next != head; cur = cur->next)
list_move(cur, cur->next);
}
```
### q_reverse
運用`list.h` 裡的 `list_for_each_safe` 迭代 queue 裡的 `strurct head_list` 的地址，將每個 `strurct head_list` 的 next 指標及 prev 指標互換，迭代完成後，再處理 queue 的 `head` 的 next 指標及 prev 指標。
```c
/*
* Reverse elements in queue
* No effect if q is NULL or empty
* This function should not allocate or free any list elements
* (e.g., by calling q_insert_head, q_insert_tail, or q_remove_head).
* It should rearrange the existing ones.
*/
void q_reverse(struct list_head *head)
{
if (!head || list_empty(head))
return;
struct list_head *node, *next;
list_for_each_safe (node, next, head) {
node->next = node->prev;
node->prev = next;
}
head->next = head->prev;
head->prev = next;
}
```
##### 二更
```c
void q_reverse(struct list_head *head)
{
if (!head || list_empty(head))
return;
struct list_head *node, *next;
list_for_each_safe (node, next, head) {
list_move (node, head);
}
}
```
### q_sort
依作業要求時間複雜度必須為 $O(nlogn)$，所以參考了你所不知道的 [C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list#Linked-list-%E5%9C%A8-Linux-%E6%A0%B8%E5%BF%83%E5%8E%9F%E5%A7%8B%E7%A8%8B%E5%BC%8F%E7%A2%BC)其中的==Merge Sort 的實作==，將 sorting 分成三個 function：`merge_two_lists`, `merge_sort`, `q_sort`
* `merge_two_lists`
目的為將兩個串列依據順序合併，用兩個指標分別指著兩串列開頭，比較指標的內容，將較小的放到新的串列裡，該指標移至下一個位置。
運用指標的指標技巧 `struct list_head **indir`，指向新串列的下一個可用節點，就不需要配置額外的記憶體。而 `struct list_head **temp` 可以用來指向 L1, L2 的目前節點，程式碼更加簡化。
特別注意的是因為迭代的是 `struct list_head` 的地址，但要比較的值其實是鑲嵌在 `struct list_head` 的 `element_t` 的成員，因此需要運用`list.h` 裡的 `list_entry` 求出 `element_t` 的地址。
當迴圈迭代完成，最終會剩下一個節點尚未被加入新串列，採 bit-wsie `|` 找出非空的節點且能加速運算。
```c
struct list_head *merge_two_lists(struct list_head *L1, struct list_head *L2)
{
struct list_head *head = NULL;
struct list_head **indir = &head, **temp = NULL;
element_t *L1_ele, *L2_ele;
for (; L1 && L2; *temp = (*temp)->next) {
L1_ele = list_entry (L1, element_t, list);
L2_ele = list_entry (L2, element_t, list);
temp = strcmp(L1_ele->value, L2_ele->value) < 0 ? &L1 : &L2;
*indir = *temp;
indir = &(*indir)->next;
}
*indir = (struct list_head *) ((uintptr_t) L1 | (uintptr_t) L2);
return head;
}
```
* `merge_sort`
採遞迴方式，在傳入的一條串列中，利用快慢指標方式找出第一個與中間節點，再讓 `merge_two_lists` 將第一個節點開頭的串列及中間節點開頭的串列，合併成一個有序的串列。終止條件為當串列本身是空，或只有一個節點時。
需要注意的是原本的串列是 circular linked-list，而在 `merge_two_lists` 以及此函式裡在迭代兩個串列時的中止條件為走到尾巴，所以在找到第一個節點開頭及中間節點開頭的串列後，要把第一個節點的串列尾巴指向 `NULL` ，否則串列的尾巴會是串列開頭。這裡參考了 [cwl0429](https://hackmd.io/yJclgTuVRzeVCjHH9FtUVw#q_free)。
```c
struct list_head *merge_sort(struct list_head *head)
{
if (!head || !head->next)
return head;
struct list_head *slow = head, *fast;
for (fast = head->next; fast && fast->next; fast = fast->next->next)
slow = slow->next;
struct list_head *left, *right;
right = slow->next;
slow->next = NULL;
left = merge_sort(head);
right = merge_sort(right);
return merge_two_lists(left, right);
}
```
* 補充：當 n 為 2 的冪，此法遞迴呼叫次數為 2n-1 次（2 * 切幾刀 + 1）。
* `q_sort`
首先將串列的尾巴指向 `NULL` ，如同上個函式說明，為了符合`merge_two_lists` 以及 `merge_sort` 裡迴圈的終止條件。
由於 `head` 並未存 queue 的內容，所以由 `head->next` 為開頭的串列傳到 `merge_sort` 裡排序。
排序完成後因為前面的函式僅更新 `next` 的單向指標，必須再迭代一次排序後的串列，將 `prev` 指標更新，也需將 `head` 接到串列尾巴，讓串列成為 doubly circular linked-list，以維持 `struct list_head` 的型態。
##### 二更
補上第 20 行，以免漏接了一個指標。
```c=
/*
* Sort elements of queue in ascending order
* No effect if q is NULL or empty. In addition, if q has only one
* element, do nothing.
*/
void q_sort(struct list_head *head)
{
if (!head || list_empty(head) || list_is_singular(head)) {
return;
}
head->prev->next = NULL;
head->next = merge_sort(head->next);
struct list_head *tmp = NULL, *prev = head;
for (tmp = head->next; tmp->next != NULL; tmp = tmp->next) {
tmp->prev = prev;
prev = prev->next;
}
tmp->prev = prev;
tmp->next = head;
head->prev = tmp;
}
```
Sign in with Wallet
Connect another wallet