---
description: Developmant Notes.
tags: linux2022
---
# 2022q1 Homework1 (lab0)
contributed by < [Herakleos](https://github.com/Herakleos/lab0-c) >
## Environment
```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
Address sizes: 39 bits physical, 48 bits virtual
CPU(s): 4
On-line CPU(s) list: 0-3
Thread(s) per core: 2
Core(s) per socket: 2
Socket(s): 1
NUMA node(s): 1
Vendor ID: GenuineIntel
CPU family: 6
Model: 142
Model name: Intel(R) Core(TM) i5-7200U CPU @ 2.50GHz
Stepping: 9
CPU MHz: 799.743
CPU max MHz: 3100.0000
CPU min MHz: 400.0000
BogoMIPS: 5399.81
Virtualization: VT-x
L1d cache: 64 KiB
L1i cache: 64 KiB
L2 cache: 512 KiB
L3 cache: 3 MiB
```
---
## Requirements
* Fork [lab0-c](https://github.com/sysprog21/lab0-c) from Github.
* Modify `queue.[ch]`, and several files to meet the requirements of the automatic test.
* [How to write a good 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/).
* Read 「[你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list)」 carefully to improve your code.
* Read [lib/list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) carefully, and try import to `lab-0c`. Compare the efficiency between the source code and yours.
* Add a new command `shuffle` in `qtest` by using [Fisher–Yates shuffle](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle) to shuffle every nodes in the queue.
* Add a new command `web` in `qtest` to provide functions of web server.
* Try to integrate [tiny-web-server](https://github.com/7890/tiny-web-server).
* Record your developing proccess.
* Use [Address Sanitizer](https://github.com/google/sanitizers/wiki/AddressSanitizer) to fix the problem while running `qtest`.
* Use Valgrind to fix the memory problem while implement `qtest`, by using Massif to visualize the memory usage in the "simulation" progress.
* Describe how to use [select](http://man7.org/linux/man-pages/man2/select.2.html) system call in this program, analyze the [console.c](https://github.com/sysprog21/lab0-c/blob/master/console.c) and describe the concern and concept of using CS:APP [RIO package] in the program.
* Read 〈[Dude, is my code constant time?](https://eprint.iacr.org/2016/1123.pdf)〉carefully, explain how does the program analyze "simulation" with experiment. You need to describe [Student's t-distribution](https://en.wikipedia.org/wiki/Student%27s_t-distribution) and how the program works.
:::warning
There are serveral critical problems now, try to solve it and pull request.
:::
---
## Queue Functions
### `q_new`:
```c
struct list_head *node = malloc(sizeof(struct list_head));
if (!node)
return NULL;
INIT_LIST_HEAD(node);
return node;
```
*"Our program needs to use regular malloc/free"* is written in **qtest.c**. Instead of using `kmalloc(sizeof(struct list_head), GFP_KERNAL)` or `kfree`.
### `q_free`:
```c
// skip empty or NULL check
struct list_head *li, *tmp;
list_for_each_safe (li, tmp, l) {
element_t *delete = list_entry(li, element_t, list);
list_del(li);
q_release_element(delete);
}
free(l);
```
The correct way to free the node, is to use `q_release_element` in order to release every single element in the node. If you free the node itself may occur *"Freed queue, but ... blocks are still allocated"*
### `q_insert_head`, `q_insert_tail`:
```c
// skip empty or NULL check
element_t *new_head = malloc(sizeof(element_t));
if (!new_head)
return false;
INIT_LIST_HEAD(&new_head->list);
size_t size = sizeof(char) * (strlen(s) + 1); // for NULL terminator
new_head->value = malloc(size);
if (!new_head->value) {
free(new_head);
return false;
}
strncpy(new_head->value, s, size);
list_add(&new_head->list, head);
return true;
```
The `q_insert_tail` is similar to `q_insert_head`, without initialize list head and change the function `list_add` to `list_add_tail`. I also found that,
* Instead of using `strncpy`, `strscpy` is often used in linux kernal.
[string: provide strscpy()](https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/commit/?id=30035e45753b708e7d47a98398500ca005e02b86)
### `q_remove_head`, `q_remove_tail`:
```c
// skip empty or NULL check
element_t *remove = list_first_entry(head, element_t, list);
list_del_init(head->next);
if (sp) {
memset(sp, '\0', bufsize); // plus a null terminator
strncpy(sp, remove->value, (bufsize - 1)); // maximum of bufsize-1
}
return remove;
```
The `q_remove_tail` is much like `q_remove_head`, in spite of using `list_del_init` but `list_del` and replace `list_first_entry` to `list_last_entry`.
### `q_delete_mid`:
```c
// find mid start
struct list_head *forward = head->next, *backward = head->prev;
while (forward != backward) {
forward = forward->next;
if (forward == backward)
break;
backward = backward->prev;
}
return forward;
// find mid end
// skip empty or NULL check
struct list_head *forward = find_mid(head);
element_t *delete = list_entry(forward, element_t, list);
list_del(forward);
q_release_element(delete);
return true;
```
There are two ways to find the middle element. The other one is to set a fast and a slow parameter as following, the method is often used when we got a singly linked list. Since we got a doubly linked structure in the function, traversing from the both side is a better approach.
```c
struct list_head *slow = head, *fast = head->next;
while (fast != head && fast->next != head) {
slow = slow->next;
fast = fast->next->next;
}
return slow;
```
### `q_delete_dup`:
```c
// skip empty or NULL check
int delete = 0;
struct list_head *li, *tmp;
list_for_each_safe (li, tmp, head) {
element_t *current = list_entry(li, element_t, list);
element_t *next = list_entry(li->next, element_t, list);
if ((li->next != head) && !strcmp(current->value, next->value)) {
delete = 1;
list_del(li);
q_release_element(current);
} else if (delete) {
list_del(li);
q_release_element(current);
delete = 0;
}
}
```
While the for each function goes through every element in the **sorted** queue, we are able to create a parameter to check the current element is duplicate or not. Delete the current duplicate element and change the status, the rest of the work belongs to the next round.
### `q_swap`:
```c
// skip empty or NULL check
struct list_head *cur = head->next;
while ((cur != head) && (cur->next != head)) {
struct list_head *tmp = cur->next;
list_del(cur);
list_add(cur, tmp);
cur = cur->next;
}
```
This function is not a typical swap but attempt to swap every two adjacent nodes. This reminds me `list_swap` do `list_del`, `list_replace` and `list_add` at the end. Brillant.
```c
// list_replace start
new->next = old->next;
new->next->prev = new;
new->prev = old->prev;
new->prev->next = new;
// list_replace end
// list_swap start
struct list_head *pos = e2->prev;
list_del(e2);
list_replace(e1, e2);
if (pos == e1)
pos = e2;
list_add(e1, pos);
// list_swap end
```
### `q_reverse`:
```c
// swap function start
char *tmp = *x;
*x = *y;
*y = tmp;
// swap function end
// skip empty or NULL check
struct list_head *forward = head->next, *backward = head->prev;
while (forward != backward) {
element_t *fwd = list_entry(forward, element_t, list);
element_t *bwd = list_entry(backward, element_t, list);
swap(&fwd->value, &bwd->value);
forward = forward->next;
if (forward == backward)
break;
backward = backward->prev;
}
```
Reverse can be seen as "switching the first and the last element, the second and the last-1 element... all the way to the middle".
### `q_sort`:
I devide the sorting proccess to 3 parts:
1. Main:
First, transform the doubly linked list structure to singly, that will be way more easier. We then rebuild the connect after sorting.
```c
// skip empty or NULL check
// to singly linked list
head->prev->next = NULL;
head->next = merge_sort(head->next);
// to doubly linked list
struct list_head *tail = head;
while (tail->next) {
tail->next->prev = tail;
tail = tail->next;
}
tail->next = head;
head->prev = tail;
```
2. Split the queue:
Second, we find the middle element to split the queue, then we sort and merge them.
```c
if (!head || !head->next)
return head;
struct list_head *fast = head->next, *slow = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
fast = slow->next;
slow->next = NULL;
struct list_head *left = merge_sort(head);
struct list_head *right = merge_sort(fast);
return merge(left, right);
```
> More details: [Linked list sort](https://npes87184.github.io/2015-09-12-linkedListSort/)
3. Merge:
The function is modified from `list_sort` in [/lib/list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c).
```c
// merge start
struct list_head *head = NULL, **tail = &head;
for (;;) {
if (strcmp(list_entry(a, element_t, list)->value,
list_entry(b, element_t, list)->value) <= 0) {
*tail = a;
tail = &a->next;
a = a->next;
if (!a) {
*tail = b;
break;
}
} else {
*tail = b;
tail = &b->next;
b = b->next;
if (!b) {
*tail = a;
break;
}
}
}
return head;
// merge end
```
### Github Action:
You did it!
---
## Qtest
### Shuffle
Since the original shuffle algorithm spend too much effort to get the target from the remaining number. The modern approach is to exchange the target with the tail element decreasing each round.
```
for i from n−1 downto 1 do
j ← random integer such that 0 ≤ j ≤ i
exchange a[j] and a[i]
```
1. Add new line in `console_init`.
```c
ADD_COMMAND(shuffle, " | Shuffle every node in queue");
```
2. Add new function `do_shuffle`.
```c
if (argc != 1) {
report(1, "%s takes no arguments", argv[0]);
return false;
}
if (!l_meta.l)
report(3, "Warning: Calling shuffle on null queue");
error_check();
int cnt = q_size(l_meta.l);
if (cnt < 2)
report(3, "Warning: Calling shuffle on single node");
error_check();
struct list_head *li;
for (li = l_meta.l->prev; (li != l_meta.l && cnt > 1); li = li->prev) {
int r = rand() % cnt;
struct list_head *tmp = l_meta.l->next;
for (int i = 0; i < r; i++)
tmp = tmp->next;
// same swap function as above
swap(&list_entry(li, element_t, list)->value,
&list_entry(tmp, element_t, list)->value);
cnt--;
}
show_queue(3);
return !error_check();
```
Noticed that linux kernal has it own random number generator, I tried to trace `get_random_bytes` in [/drivers/char/random.c](https://github.com/torvalds/linux/blob/master/drivers/char/random.c)
### Web
Working on...
## Reading
### [lib/list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c)
### [Dude, is my code constant time?](https://eprint.iacr.org/2016/1123.pdf)
Sign in with Wallet
Connect another wallet