---
tag: linux2022
---
# 2022q1 Homework1 (lab0)
contributed by < `yaohwang99` >
## 實驗環境
```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): 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
```
## [作業要求](https://hackmd.io/@sysprog/linux2022-lab0)
詳細閱讀 [lab0](https://hackmd.io/@sysprog/linux2022-lab0) 說明，依據指示著手修改 queue.[ch] 和連帶的檔案，測試後用 Git 管理各項修改。
* `q_new`: 建立新的「空」佇列
* `q_free`: 釋放佇列所佔用的記憶體
* `q_insert_head`: 在佇列開頭 (head) 插入 (insert) 給定的新節點 (以 LIFO 準則)
* `q_insert_tail`: 在佇列尾端 (tail) 插入 (insert) 給定的新節點 (以 FIFO 準則)
* `q_remove_head`: 在佇列開頭 (head) 移去 (remove) 給定的節點
* `q_release_element`: 釋放特定節點的記憶體空間
* `q_size`: 計算目前佇列的節點總量
* `q_delete_mid`: 移走佇列中間的節點
* `q_delete_dup`: 在已經排序的狀況，移走佇列中具備重複內容的節點
* `q_swap`: 交換佇列中鄰近的節點
* `q_reverse`: 以反向順序重新排列鏈結串列，該函式不該配置或釋放任何鏈結串列節點，換言之，它只能重排已經存在的節點
* `q_sort`: 以==遞增順序==來排序鏈結串列的節點
## 針對佇列的操作
### q_new
Create empty queue.
* Return NULL if could not allocate space
* `malloc()` will return NULL if allocate failed.
* `next` and `prev` both points to `head` because it is a circular list
```c
struct list_head *q_new()
{
struct list_head *head = malloc(sizeof(struct list_head));
if(!head)
return NULL;
head->next = head;
head->prev = head;
return head;
}
```
### q_size
* Return number of elements in queue.
* Return 0 if q is NULL or empty
> Copy `q_size()` from [lab0](https://hackmd.io/@sysprog/linux2022-lab0)
```cpp
int q_size(struct list_head *head)
{
if (!head)
return 0;
int len = 0;
struct list_head *li;
list_for_each (li, head)
len++;
return len;
}
```
### q_insert_head
Attempt to insert element at head of queue.
> Use strlen and strcpy to copy string.
Attempted to insert node by writing the code myself, but later discovered that we can use `list_add()` from `list.h`. Because the list is circular, the insert procedure will always be the same.
First attempt:
```c
bool q_insert_head(struct list_head *head, char *s)
{
char *tmp = malloc((strlen(s)+1)*sizeof(char));
element_t *n = malloc(sizeof(element_t));
if(!tmp||!n)
return false;
n->value = strcpy(tmp,s);
list_add(&n->list, head);
return true;
}
```
Because `strcpy` causes memory leak, use `strdup`:
```c
bool q_insert_head(struct list_head *head, char *s)
{
char *tmp = strdup(s);
element_t *n = malloc(sizeof(element_t));
if (!tmp || !n)
return false;
n->value = tmp;
list_add(&n->list, head);
return true;
}
```
:::danger
You should explain why it matters.
:notes: jserv
:::
:::info
:bulb:The strcpy() function does not stop until it sees `'\0'` in the source string. If the source string is longer than dst string, strcpy() will overwrite some unallocated memory contiguous to the intended destination.
Reference: [Common vulnerabilities guide for C programmers](https://security.web.cern.ch/recommendations/en/codetools/c.shtml)
:::
### q_insert_tail
Same as `q_insert_head()`
```c
bool q_insert_tail(struct list_head *head, char *s)
{
char *tmp = strdup(s);
element_t *n = malloc(sizeof(element_t));
if (!tmp || !n)
return false;
n->value = tmp;
list_add_tail(&n->list, head);
return true;
}
```
---
### Read `list.h`
Because I didn't read though `list.h`, I spent a lot of time writing `q_insert()`. I decide to read through `list.h` before continuing.
---
### q_free
Use`list_for_each_entry_safe()` to safely remove element.
```c
void q_free(struct list_head *l)
{
if (!l)
return;
element_t *entry;
element_t *safe;
list_for_each_entry_safe (entry, safe, l, list) {
list_del_init(&entry->list);
q_release_element(entry);
}
free(l);
}
```
### q_remove_head
Fix "Error: Failed to store removed value"
> The error occurs because we need to copy the value of deleted element to sp.
Cannot use strndup() because that makes sp point to other memory.
Use strncpy() to copy the value to sp.
```c
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if (!head)
return NULL;
if (list_empty(head))
return NULL;
element_t *tmp = list_first_entry(head, element_t, list);
strncpy(sp, tmp->value, bufsize - 1);
list_del_init(&tmp->list);
return tmp;
}
```
### q_remove_tail
Same as `q_remove_head()`
```c
element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
if (!head)
return NULL;
if (list_empty(head))
return NULL;
element_t *tmp = list_last_entry(head, element_t, list);
strncpy(sp, tmp->value, bufsize - 1);
list_del_init(&tmp->list);
return tmp;
}
```
### q_del_mid
Use two pointer from head and tail and move torward mid, remove target when they point to mid.
```c
bool q_delete_mid(struct list_head *head)
{
// https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/
if (!head)
return false;
if (list_empty(head))
return false;
element_t *front = list_entry(head->next, element_t, list),
*back = list_entry(head->prev, element_t, list);
for (; front != back && front->list.next != &back->list;
front = list_entry(front->list.next, element_t, list),
back = list_entry(back->list.prev, element_t, list)) {
}
list_del_init(&back->list);
q_release_element(back);
return true;
}
```
### q_delete_dup
Use two pointer to sequence of identical values and move them to rec.
Call q_free() to delete rec.
```c
bool q_delete_dup(struct list_head *head)
{
// https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
if (!head)
return false;
if (list_empty(head))
return false;
if (list_is_singular(head))
return true;
struct list_head *rec = q_new();
struct list_head *front = head->next;
struct list_head *back = head->next->next;
while (front != head && back != head) {
element_t *back_entry = list_entry(back, element_t, list);
element_t *front_entry = list_entry(front, element_t, list);
while (strcmp(front_entry->value, back_entry->value) == 0) {
back = back->next;
if (back == head)
break;
back_entry = list_entry(back, element_t, list);
}
if (front->next != back) {
struct list_head *prev = front->prev;
rec->next->prev = back->prev;
back->prev->next = rec->next;
front->prev = rec;
rec->next = front;
prev->next = back;
back->prev = prev;
}
front = back;
back = back->next;
}
q_free(rec);
return true;
}
```
### q_reverse
Use prev, next, and curr to reverse list.
```c
void q_reverse(struct list_head *head)
{
if (!head)
return;
if (list_empty(head))
return;
if (list_is_singular(head))
return;
struct list_head *curr = head;
struct list_head *prev = head->prev;
struct list_head *next = head->next;
do {
curr->prev = next;
curr->next = prev;
prev = curr;
curr = next;
next = next->next;
} while (curr != head);
}
```
### q_sort
1. Find the middle point to divide the list into two halves.
2. Call merge_sort for first half.
3. Call mergeSort for second half.
4. Merge the two halves sorted in step 2 and 3.
```c
void merge(struct list_head **li, struct list_head **mi, struct list_head **ri)
{
struct list_head *l_start = *li;
struct list_head *l_end = *mi;
struct list_head *r_start = (*mi)->next;
struct list_head *r_end = *ri;
struct list_head *walk = (*li)->prev;
struct list_head *head = (*li)->prev;
struct list_head *tail = (*ri)->next;
element_t *l_entry = list_entry(l_start, element_t, list);
element_t *r_entry = list_entry(r_start, element_t, list);
while (true) {
if (strcmp(l_entry->value, r_entry->value) > 0) {
struct list_head *next_r_start = r_start->next;
list_del_init(r_start);
list_add(r_start, walk);
walk = walk->next;
if (r_start == r_end) {
break;
}
r_start = next_r_start;
r_entry = list_entry(r_start, element_t, list);
} else {
struct list_head *next_l_start = l_start->next;
list_del_init(l_start);
list_add(l_start, walk);
walk = walk->next;
if (l_start == l_end) {
break;
}
l_start = next_l_start;
l_entry = list_entry(l_start, element_t, list);
}
}
*li = head->next;
*ri = tail->prev;
}
void merge_sort(struct list_head **li, struct list_head **ri)
{
if (*li == *ri)
return;
struct list_head *front = *li, *back = *ri;
for (; front != back && front->next != back;
front = front->next, back = back->prev) {
}
merge_sort(li, &back->prev);
merge_sort(&back, ri);
struct list_head **mi = &back->prev;
merge(li, mi, ri);
}
/*
* 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)
{
merge_sort(&head->next, &head->prev);
}
```
## `make test` result:
Need to fix some error in allocating memory and string copy.
Everything else pass.
```shell
+++ TESTING trace trace-07-string:
--- trace-07-string 0/6
# Test of truncated strings
+++ TESTING trace trace-10-robust:
# Test operations on NULL queue
Segmentation fault occurred. You dereferenced a NULL or invalid pointer
--- trace-10-robust 0/6
+++ TESTING trace trace-11-malloc:
# Test of malloc failure on insert_head
ERROR: Freed queue, but 10 blocks are still allocated
--- trace-11-malloc 0/6
+++ TESTING trace trace-12-malloc:
# Test of malloc failure on insert_tail
ERROR: Freed queue, but 11 blocks are still allocated
--- trace-12-malloc 0/6
```
## Fix error
### `q_remove_head()` and `q_remove_tail()`
If `sp` is NULL, do nothing.
Compare `strlen(tmp->value)` with `bufsize-1`. Copy `tmp->value` to `sp` and set last element of sp to `'\0'`.
```c
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if (!head)
return NULL;
if (list_empty(head))
return NULL;
element_t *tmp = list_first_entry(head, element_t, list);
list_del_init(&tmp->list);
if (!sp)
return tmp;
size_t len = strlen(tmp->value);
len = len > bufsize - 1 ? bufsize - 1 : len;
strncpy(sp, tmp->value, len);
sp[len] = '\0';
return tmp;
}
```
### `q_insert_head()` and `q_insert_tail()`
Return `false` when `strdup()` failed (`malloc` failed).
Free `tmp` and return `false` when `malloc` for new element failed.
```c
bool q_insert_head(struct list_head *head, char *s)
{
if (!head)
return false;
if (!s)
return false;
char *tmp = strdup(s);
if (!tmp)
return false;
element_t *n = malloc(sizeof(element_t));
if (!n) {
free(tmp);
return false;
}
n->value = tmp;
list_add(&n->list, head);
return true;
}
```
### `q_sort()`
Return if queue is empty.
```c
void q_sort(struct list_head *head)
{
if (!head)
return;
merge_sort(&head->next, &head->prev);
}
```
## Add sort from [list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c)
Create list_sort.h file, copy-paste the code from [list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) and modify the code to suit our need.
1. Initiate `head` to `NULL` in line 19 in `merge()` to avoid compile warning/error.
```c=19
struct list_head *head = NULL, **tail = &head;
```
2. Include needed library, define `list_cmp_func_t`, `likely()`,`unlikely()` and compare function `compare_entry` for comparison.
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "harness.h"
#include "queue.h"
#define likely(x) __builtin_expect((x), 1)
#define unlikely(x) __builtin_expect((x), 0)
typedef int list_cmp_func_t(void *, struct list_head *, struct list_head *);
int compare_entry(void *priv, struct list_head *a, struct list_head *b)
{
element_t *ca = list_entry(a, element_t, list);
element_t *cb = list_entry(b, element_t, list);
return strcmp(ca->value, cb->value);
}
3. Define the funtion called by qtest, `priv` is always `NULL`, it is unused.
```c
void linux_q_sort(struct list_head *head)
{
if (!head)
return;
void *priv = NULL;
list_cmp_func_t *cmp = compare_entry;
list_sort(priv, head, cmp);
}
```
4. Add command for `linux_q_sort()` in qtest.c
```c
ADD_COMMAND(
lsort,
" | Sort queue in ascending order by linux list sort");
```
5. Add `do_lsort()` by modifying `do_sort()` in qtest.c.
```c
bool do_lsort(int argc, char *argv[])
{
...
if (exception_setup(true))
linux_q_sort(l_meta.l);
...
}
```
:::warning
DON'T DO THAT. You can introduce single `sort` command with different options, which allow run-time switching.
:notes: jserv
:::
### Update
Delete the lsort command and change the sort command for different option.
```c
bool do_sort(int argc, char *argv[])
{
if (argc > 2) {
report(1, "%s takes 0 or 1 arguments", argv[0]);
return false;
}
...
if (argc == 1) {
if (exception_setup(true))
q_sort(l_meta.l);
} else {
if (exception_setup(true))
linux_q_sort(l_meta.l);
}
...
}
```
### Compare `sort`
Compare the two method with `traces/trace-sort.cmd`
:::info
result: 0.58/0.68=0.85, the sort from linux is about 15% faster.
:::
```
# Test performance of sort and linux sort with random orders
option fail 0
option malloc 0
new
ih RAND 500000
time sort 0
new
ih RAND 500000
time sort 0
new
ih RAND 500000
time sort 0
new
ih RAND 500000
time sort 0
new
ih RAND 500000
time sort 0
new
ih RAND 500000
time sort
new
ih RAND 500000
time sort
new
ih RAND 500000
time sort
new
ih RAND 500000
time sort
new
ih RAND 500000
time sort
# Exit program
quit
```
## Implement shuffle
### Add shuffle command
1. In qtest.c, add the following code.
```c
ADD_COMMAND(shuffle, " | Shuffle queue.");
```
2. Add do_shuffle() command like do_sort().
```c
bool do_shuffle(int argc, char *argv[])
{
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();
set_noallocate_mode(true);
if (exception_setup(true))
q_shuffle(l_meta.l);
exception_cancel();
set_noallocate_mode(false);
bool ok = true;
show_queue(3);
return ok && !error_check();
}
```
### Implement [Fisher-Yates shuffle algorithm](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle)
Add the following code in list_sort.h.
>Pre-allocate array to store pointers to achieve O(n) time complexity.
```c
void q_shuffle(struct list_head *head)
{
if (!head)
return;
if (list_empty(head))
return;
if (list_is_singular(head))
return;
srand(time(NULL));
int len = q_size(head);
struct list_head *target = head->next;
struct list_head *tail = head->prev;
struct list_head **list_arr = malloc(len * sizeof(struct list_head *));
if (!list_arr) {
printf("list_arr malloc failed\n");
return;
}
for (int i = 0; i < len; ++i) {
list_arr[i] = target;
target = target->next;
}
while (len) {
int random = rand() % len;
if (random == len - 1) {
tail = tail->prev;
len--;
continue;
}
target = list_arr[random];
struct list_head *target_prev = target->prev;
struct list_head *tail_next = tail->next;
list_del_init(tail);
list_add(tail, target_prev);
list_del_init(target);
target->prev = tail_next->prev;
tail_next->prev = target;
target->next = tail_next;
target->prev->next = target;
list_arr[random] = tail;
list_arr[len - 1] = target;
tail = tail_next->prev->prev;
len--;
}
free(list_arr);
}
```
## Web server
Reference: [lab0-c](https://hackmd.io/@sysprog/linux2022-lab0#%E6%95%B4%E5%90%88-tiny-web-server), [2020leon](https://hackmd.io/@6649/linux2022-lab0#%E5%AF%A6%E5%81%9A%E4%BC%BA%E6%9C%8D%E5%99%A8%EF%BC%88-web-%EF%BC%89)
1. Split `tiny.c `into `tiny.c` and `tiny.h`. Include `tiny.h` in other file.
2. Fix error detected by cppcheck (unused function, variable scope, potential sscanf() error).
3. Declare `extern int listenfd;` `extern bool noise;` because we need to use them in other script.
4. Add do_web() and web command to qtest.c.
5. Modify cmd_select() and run_console() according to [lab0-c](https://hackmd.io/@sysprog/linux2022-lab0#%E6%95%B4%E5%90%88-tiny-web-server).
### `process()`
The web server has to respond something to form a connection. Otherwise, the browser will display "unable to connect".
```c
void handle_request(int fd)
{
writen(fd, "server", strlen("server"));
}
char *process(int fd, struct sockaddr_in *clientaddr)
{
#ifdef LOG_ACCESS
printf("accept request, fd is %d, pid is %d\n", fd, getpid());
#endif
http_request req;
parse_request(fd, &req);
int status = 200;
char *p = req.filename;
/* Change '/' to ' ' */
while (*p) {
++p;
if (*p == '/') {
*p = ' ';
}
}
handle_request(fd);
#ifdef LOG_ACCESS
log_access(status, clientaddr, &req);
#endif
char *ret = malloc(strlen(req.filename) + 1);
strncpy(ret, req.filename, strlen(req.filename) + 1);
return ret;
}
```
result:
```
$ ./qtest
cmd> web
listen on port 9999
cmd>
cmd> accept request, fd is 4, pid is 39369
127.0.0.1:35274 200 - '.'
Unknown command '.'
cmd> accept request, fd is 4, pid is 39369
127.0.0.1:35276 200 - 'favicon.ico'
Unknown command 'favicon.ico'
cmd> accept request, fd is 4, pid is 39369
127.0.0.1:35278 200 - 'new'
l = []
cmd> accept request, fd is 4, pid is 39369
127.0.0.1:35280 200 - 'favicon.ico'
Unknown command 'favicon.ico'
cmd> accept request, fd is 4, pid is 39369
127.0.0.1:35282 200 - 'ih RAND 1000'
l = [hvvbiggpa joxngrm mlffsdmqe fvrhq jaagnqc lthyhwy vnbszvyp hvxnn wslmpadd uvmudn aqequ uyqxnpl ducxibkr fwrtkloq huflsrb eqvizffok lqsikqw fpxkqvj wqrepu pwtppmtx ngrevsif pwycz proyuyrrd ivbnpkkcp swfonxhn aulxklec niyet djrvwrsta hvoxh inshjpjir ... ]
cmd> accept request, fd is 4, pid is 39369
127.0.0.1:35284 200 - 'favicon.ico'
Unknown command 'favicon.ico'
cmd> accept request, fd is 4, pid is 39369
127.0.0.1:35286 200 - 'sort'
l = [acuvclab adgvveq aemil afifxh afphp afqfwyuw afsoa aglveoklb agzctnrn ahwjyg aioknms ajehvsj ajryccr ajvito akccvrhb almzz alskvrh alvklner amafepe amerbmi amgaeqf amwvf aneqyycc anjfcq anmdao aorjbzlg apkbzaer apnbdw apnlt aqequ ... ]
cmd> accept request, fd is 4, pid is 39369
127.0.0.1:35288 200 - 'favicon.ico'
Unknown command 'favicon.ico'
Error limit exceeded. Stopping command execution
```
TODO:
1. We cannot connect to the server until at least one command is executed after the `web` command.
2. Fix 'favicon.ico' error.
## 參考資訊
- 共筆格式參考：[共筆示範](https://hackmd.io/@cccccs100203/linux2020-lab0)
Sign in with Wallet
Connect another wallet