# 2022q1 Homework1 (lab0)
contributed by < `idoleat` >

## Working Environment
:::spoiler
<summary>Details (click to expand)</summary>

$ uname -r        
5.16.10-arch1-1

$ gcc --version
gcc (GCC) 11.2.0
Copyright (C) 2021 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

$ valgrind --version
valgrind-3.18.1

$ cppcheck --version
Cppcheck 2.7

$ aspell --version
@(#) International Ispell Version 3.1.20 (but really Aspell 0.60.8)

:::

## 作業要求
- [x] 在 GitHub 上 fork [lab0-c](https://github.com/sysprog21/lab0-c)
* 參閱 [Git 教學和 GitHub 設定指引](https://hackmd.io/@sysprog/git-with-github) ^附教學影片^
- [ ] 依據上述指示著手修改 `queue.[ch]` 和連帶的檔案，測試後用 Git 管理各項修改，要能滿足 `$ make test` 自動評分系統的所有項目。
* 在提交程式變更前，務必詳閱 [如何寫好 Git Commit Message](https://blog.louie.lu/2017/03/21/%E5%A6%82%E4%BD%95%E5%AF%AB%E4%B8%80%E5%80%8B-git-commit-message/)
* 詳閱「[你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list)」並應用裡頭提及的手法，例如 pointer to pointer (指向某個指標的指標，或說 indirect pointer)，讓程式碼更精簡且有效
* 研讀 Linux 核心原始程式碼的 [lib/list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) 並嘗試引入到 `lab0-c` 專案，比較你自己實作的 merge sort 和 Linux 核心程式碼之間效能落差
- [ ] 在 `qtest` 提供新的命令 `shuffle`，允許藉由 [Fisher–Yates shuffle](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle) 演算法，對佇列中所有節點進行洗牌 (shuffle) 操作
- [ ] 在 `qtest` 提供新的命令 `web`，提供 web 伺服器功能，注意: web 伺服器運作過程中，`qtest` 仍可接受其他命令
* 可依據前述說明，嘗試整合 [tiny-web-server](https://github.com/7890/tiny-web-server)
- [ ] 除了修改程式，也要編輯「[作業區](https://hackmd.io/@sysprog/linux2022-homework1)」，增添開發紀錄和 GitHub 連結，除了提及你如何逐步達到自動評分程式的要求外，共筆也要涵蓋以下:
* 開啟 [Address Sanitizer](https://github.com/google/sanitizers/wiki/AddressSanitizer)，修正 `qtest` 執行過程中的錯誤
* 先執行 `qtest` 再於命令提示列輸入 `help` 命令，會使 開啟 [Address Sanitizer](https://github.com/google/sanitizers/wiki/AddressSanitizer) 觸發錯誤，應予以排除
* 運用 Valgrind 排除 `qtest` 實作的記憶體錯誤，並透過 Massif 視覺化 "simulation" 過程中的記憶體使用量，需要設計對應的實驗
* 解釋 [select](http://man7.org/linux/man-pages/man2/select.2.html) 系統呼叫在本程式的使用方式，並分析 [console.c](https://github.com/sysprog21/lab0-c/blob/master/console.c) 的實作，說明其中運用 CS:APP [RIO 套件](http://csapp.cs.cmu.edu/2e/ch10-preview.pdf) 的原理和考量點。可對照參考 [CS:APP 第 10 章重點提示](https://hackmd.io/@sysprog/H1TtmVTTz)
* 研讀論文〈[Dude, is my code constant time?](https://eprint.iacr.org/2016/1123.pdf)〉，解釋本程式的 "simulation" 模式是如何透過以實驗而非理論分析，達到驗證時間複雜度，需要解釋 [Student's t-distribution](https://en.wikipedia.org/wiki/Student%27s_t-distribution) 及程式實作的原理。注意：現有實作存在若干致命缺陷，請討論並提出解決方案;
- [ ] 指出現有程式的缺陷 (提示: 和 [RIO 套件](http://csapp.cs.cmu.edu/2e/ch10-preview.pdf) 有關) 或者可改進之處 (例如更全面地使用 Linux 核心風格的鏈結串列 API)，嘗試實作並提交 pull request

## Queue Operations
### `q_new()`

/*
 * Create empty queue.
 * Return NULL if could not allocate space.
 */
struct list_head *q_new()
{
    struct list_head *h = malloc(sizeof(struct list_head));
    if (h == NULL)
        return NULL;

    INIT_LIST_HEAD(h);  // Todo: what about using LIST_HEAD(head)?
    return h;
}

~~Initially, I thought a `list_head *` points to NULL would be an empty queue, but according to the comment it's the situation that could not allocate space. Seems that we still need an empty `element_t`. It's kind of weird to have an element containing nothing in a new queue since it makes the size of a new queue 1.(But not the real size because head is `NULL` and would make `q_size()` report 0 at this point)~~
After the class on 2/22, I found that there's really no need to allocate a whole `element_t`. But my original thoughts was wrong as well. It's not a `list_head` points to NULL. It's an initialized head.

For initializing the list head, besides using Linux kernel API `INIT_LIST_HEAD`, I found there's another macro `LIST_HEAD` (it's not kernel API though).

Memory leaks on `return &(q->list)` reported by Cppcheck need to be fix. I got a quick fix suggested by *King Bur* and *Pin Lin* in [this post](https://www.facebook.com/groups/system.software2022/posts/1982813305233403/). Adding `// cppcheck-suppress nullPointer` inline and `--inline-suppr` as a `cppcheck` command argument can suppress the warning according to the [manual](http://cppcheck.net/manual.html). Or just maybe it really has memory leak. Listed in Todo. (@jasperlin1996 mentioned this in his [note](https://hackmd.io/@jasperlin1996/linux2022-lab0#q_insert_head) as well)

### `q_insert_head()` and `q_insert_tail()`

bool q_insert_head(struct list_head *head, char *s)
{
    element_t *q = malloc(sizeof(element_t));
    if (q == NULL)
        return false;

    q->value = malloc(sizeof(char) * (strlen(s) + 1));
    if (q->value == NULL) {
        free(q);
        return false;
    }

    strncpy(q->value, s, strlen(s) + 1);
    list_add(&(q->list), head);
    return true;
}

After allocating `element_t` and `value` in `element_t`, we should check if they are allocated successfully or not. Noted that the return value of `strlen()` doesn't include `\0`. I've seen others suggesting using `memcpy` to copy strings. I'm not sure if that's it's a better way. I'll experiment that later. Listed in Todo.

I've noticed that comparing to a queue implemented with non-circular doubly-linked list, which has explicit tail pointer, circular doubly-linked list can shrink down the complexity of implementation. We don't need to determine the queue is empty or not here.

Insert an element to tail is pretty much the same. Just substitute `lisr_add` to `list_add_tail` thanks to the convenient Linux API.

### `q_remove_head()` and `q_remove_tail()`

#### Fix my mis-usage of `head`

element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if (head == NULL || list_empty(head))
        return NULL;
	
    element_t *entry = list_entry(head, element_t, list);
    if (sp != NULL) {
        strncpy(sp, entry->value, bufsize);
        sp[bufsize - 1] = '\0';
    }

    list_del(head);
    return entry;
}

Not sure what goes wrong but this piece of code produces segment fault (dereferenced NULL or invalid pointer) in `strncpy` according to gdb debug message. If I substitute `strncpy` with `strndup("test", bufsize - 1)` or even comment out the line, I'll get this instead:

ERROR: Attempted to free unallocated block.  Address = 0xdeadbeef

Program received signal SIGSEGV, Segmentation fault.
0x0000555555559dc2 in find_header (p=0xdeadbeef) at harness.c:103
103	    if (b->magic_header != MAGICHEADER) {

Since `free()` is substituted to `test_free()` in `harness.c`, let's see what look into it.

/* Value at start of every allocated block */
#define MAGICHEADER 0xdeadbeef

Since every block allocated start with `0xdeadbeef`, any block not starting with `0xdeadbeef` is not a legitimate block.
~~ok...I still don't know why. Maybe there's something wrong already while inserting...~~
Cppcheck says that

queue.c:98:24: error: Null pointer dereference: (struct element_t*)0 [nullPointer]
    element_t *entry = list_entry(head, element_t, list);

So the answer is that I forgot the `head` is just a head to enter the queue, like what we get in `q_new()`. Sounds hilarious but I was troubled with this mistake *a whole day*. I should use Cppcheck earlier next time. My skill on solving segment fault is not trust worthy. Maybe in a memory inexpensive environment we can allocate a whole `element_t` for head and set `"this is a head"` for its value so that this won't happened (I'm not sure I can call it a fault tolerance design or not).

Corrected code:

element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if (head == NULL || list_empty(head))
        return NULL;
	
    element_t *first_entry = list_first_entry(head, element_t, list);
    if (sp != NULL) {
        sp = strncpy(sp, first_entry->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }

    list_del(&first_entry->list);
    return first_entry;
}

I saw some others use `list_entry(head->next, element_t, list)` instead of `list_first_entry`. I think using `list_first_entry` is a more semantic way though.

#### Cppcheck: Null pointer dereference

Actually the error message from cppcheck wasn't indicating that I used `head` in the wrong way. In @Jasperlin1996's [note](https://hackmd.io/@jasperlin1996/linux2022-lab0#q_remove_head), he not only deep dived into the issue, also submitted a PR. Worth taking some time give it a read.

### `q_free()`

#### Recursive free
(WIP)
In the iterative way, the address of next `list_head` should be put in a temporary pointer (either in a loop-scoped variable or in a function local variable) before freeing the current element. It seems tedious to do so. So I come up with an idea to walk through whole list to the end, freeing elements from the tail back to the head. Since the previous element is known already, there is no need to remember anything before freeing elements. This is the recursive way.

To make it more efficient, I want to make it into a tail recursion. Otherwise, the stack might get overflowed by test cases with 1000000-elements queue, according to the lab-0 document.

#### Using `list_for_each_entry_safe()`

void q_free(struct list_head *l)
{
    if (l == NULL)
        return;
    element_t *entry, *tmp;
    list_for_each_entry_safe (entry, tmp, l, list) {
        q_release_element(entry);
    }
    free(l);
}

Return if the list is null.
There are 4 APIs to iterate though a list:
`list_for_each`
`list_for_each_entry`
`list_for_each_safe`
`list_for_each_entry_safe`
The first two don't allow you modify the entry while iterating. The later two allow because there's an extra pointer to get the next node first before anything changed. By using list_for_each_entry_safe and q_release_element() all the elements are freed. Lastly, free the head itself.

Even though it passed the test but I'm still wondering what's the point of remove head/tail instead of deleting it? The unlinked node becomes unaccessable. When will it get freed?
Ans: In `qtest.c`, the return value of `q_remove_head()` and `q_remove_tail()`, which are the removed nodes, will be released by calling `q_release_element()`.

### `q_delete_mid()`

bool q_delete_mid(struct list_head *head)
{
    if (head == NULL || list_empty(head))
        return false;

    element_t *entry, *tmp;
    int size = q_size(head);
    list_for_each_entry_safe (entry, tmp, head, list) {
        size -= 2;
        if (size <= 0) {
            list_del(&entry->list);
            q_release_element(entry);
            return true;
        }
    }

    return false;
}

There are two ways to find the middle in my mind. One is iterating from two ends toward each other and meeting at the middle. The other is iterating from same side but one is 2 times faster than the other. To utilize the list API the most, with the goal to iterate to the exact node to delete, I use a counter to count down 2 at once. When it's equal or less than 0, the `entry` is the one we want to delete.

### `q_delete_dup()`

(WIP)
I'm trying to come up with the best solution.

### `q_reverse()`

void q_reverse(struct list_head *head)
{
    if (head == NULL || list_empty(head))
        return;

    struct list_head *node, *tmp;
    list_for_each_safe (node, tmp, head) {
        node_np_swap(node);
    }
    node_np_swap(head);
}

`node_np_swap()` means swapping the `next` and `prev` in a list node. It's defined as:

void inline node_np_swap(struct list_head *node)
{
    struct list_head *tmp;
    tmp = node->next;
    node->next = node->prev;
    node->prev = tmp;
}

The idea is that every node in the list just turns around and the job is done. The node includes the head itself because the first(`head->next`) and the last(`head->prev`) needs to be swapped as well. If the list is not doubly linked and circular, the situation could be more complex.

I would like to use XOR to swap but `^` is not a valid operator for `list_head *` After checking ISO 9899 standard, it says
> 6.3.2.3 Pointers
> Any pointer type may be converted to an integer type. Except as previously specified, the result is implementation-defined. If the result cannot be represented in the integer type, the behavior is undefined. The result need not be in the range of values of any integer type.

### `q_swap()`

void q_swap(struct list_head *head)
{
    // https://leetcode.com/problems/swap-nodes-in-pairs
    if (head == NULL)
        return;

    struct list_head *iterator = head->prev;
    bool last = true;
    int size = q_size(head);
    if ((size & 1) == 1) {
        list_move(iterator, head);
        size -= 1;
    }
    while (size--) {
        iterator = head->prev;
        if (last)
            iterator = iterator->prev;
        list_move(iterator, head);
        last = !last;
    }
}

The code looks tedious because of there are extra parts dealing with odd queue size and witch to move. I've seen @jasperlin1996 done it in [a cleaner way](https://hackmd.io/@jasperlin1996/linux2022-lab0#q_swap) by writing the restrictions in `for` condition statement.

(WIP)
There may be a way to write a better one by using `list_head **`

### `q_sort()`

(WIP)
~~I choose heap sort here because it's doable here. Also, it's an unstable sort although the time complexity is O(n). I want to test how unstable is an unstable sort.~~ No, heap sort is not O(nlogn) on linked list because element look up in linked list is O(n). This will make the total time complexity become O(n^2^logn).

Todo: compare the memory usage and execution time of both top-down and bottom-up way.

### Extra: Concurrent FIFO queue

I'm interested in finding ways to divide jobs for programs (effortlessly ideally) to run on multiple machines. This may be a good chance to practice and trying out my new ideas and others' idea.
https://www.youtube.com/watch?v=BowcTNnkO7E

## Comparing with `list_sort.c` in Linux kernel
You can modify the code to challenge the design