---
tags: linux2023
---
# 2023q1 Homework1 (lab0)
contributed by < [`qwe661234`](https://github.com/qwe661234) >
## Implement queue.c
### queue structure
Doubly-linked list and its value is string.
```c
struct list_head {
struct list_head *prev;
struct list_head *next;
};
typedef struct {
char *value;
struct list_head list;
} element_t;
```
### q_insert_head
Add new queue node to the end of the list by `list_add`.
If `malloc` fails to allocate space for string that store in new node, you should free the memory of new node. Otherwise, it would cause memory leak.
```c
bool q_insert_head(struct list_head *head, char *s)
{
if (!head)
return false;
element_t *ele = (element_t *) malloc(sizeof(element_t));
if (!ele)
return false;
size_t slen = strlen(s);
char *str = (char *) malloc((slen + 1) * sizeof(char));
if (!str) {
free(ele);
return false;
}
strncpy(str, s, slen);
str[slen] = '\0';
ele->value = str;
list_add(&ele->list, head);
return true;
}
```
### q_insert_tail
Expect for adding new queue node to the end of the list by `list_add_tail`, other operations are the same as `q_insert_head`.
```c
bool q_insert_tail(struct list_head *head, char *s)
{
if (!head)
return false;
element_t *ele = (element_t *) malloc(sizeof(element_t));
if (!ele)
return false;
size_t slen = strlen(s);
char *str = (char *) malloc((slen + 1) * sizeof(char));
if (!str) {
free(ele);
return false;
}
strncpy(str, s, slen);
str[slen] = '\0';
ele->value = str;
list_add_tail(&ele->list, head);
return true;
}
```
### q_remove_head
Get first node of queue by `list_first_entry`.
Check if the buffer size - 1 is larger than the length of copy string. Otherwise, it would overflow destination buffer.
Undefined behavior for `strncpy`
1. memory dest and memory src overlap
2. one of dest and src does not point to char
3. size of dest is less than `bufsize`
4. size of src is less than size of dest, but src is not terminate with `'\0'`
```c
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);
if (sp) {
size_t slen = strlen(target->value);
if (slen <= bufsize - 1) {
strncpy(sp, target->value, slen);
sp[slen] = '\0';
} else {
strncpy(sp, target->value, bufsize - 1);
sp[bufsize - 1] = '\0';
}
}
list_del(&target->list);
return target;
}
```
### q_remove_tail
Except for getting first node of queue by `list_last_entry`, other operations are the same as `q_remove_head`.
```c
element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head))
return NULL;
element_t *target = list_last_entry(head, element_t, list);
if (sp) {
size_t slen = strlen(target->value);
if (slen <= bufsize - 1) {
strncpy(sp, target->value, slen);
sp[slen] = '\0';
} else {
strncpy(sp, target->value, bufsize - 1);
sp[bufsize - 1] = '\0';
}
}
list_del(&target->list);
return target;
}
```
### q_delete_mid
If queue is singular, delete the only node in queue.
If queue is non-singular, use two pointer to get middle node. The first pointer is point to the first node and the second pointer is point to the last node. The first pointer iterate from the first to the the last node and the last pointer iterate oppositely. When these two pointers point to the same node or the firat pointer cross the second pointer, the node pointed by the second pointer would be the middle node.
Becasue these two pointers meet the terminal condition in the beginning, we use `do while`.
```c
bool q_delete_mid(struct list_head *head)
{
if (!head || list_empty(head))
return NULL;
element_t *target;
if (!list_is_singular(head)) {
// More than one node in the queue
struct list_head *front = head->next, *back = head->prev;
do {
front = front->next;
back = back->prev;
} while (front != back && front->prev != back);
target = list_entry(front, element_t, list);
list_del(front);
} else {
// Only one node in the queue
target = list_entry(head->next, element_t, list);
list_del(head->next);
}
free(target->value);
free(target);
return true;
}
```
### q_delete_dup
A queue node would be delete in two condition:
1. node value is equal to next node value
2. node value is not equal to next node value, but it is equal to previous node value.
```c
bool q_delete_dup(struct list_head *head)
{
if (!head)
return false;
bool flag = false;
element_t *entry, *safe;
list_for_each_entry_safe (entry, safe, head, list) {
if (&safe->list != head && !strcmp(entry->value, safe->value)) {
flag = true;
list_del(&entry->list);
free(entry->value);
free(entry);
} else if (flag) {
flag = false;
list_del(&entry->list);
free(entry->value);
free(entry);
}
}
return true;
}
```
### q_swap
Iterate the queue and record the number of iterated node. If the number is even, move current node to the position which is previos to previous node.
```c
void q_swap(struct list_head *head)
{
if (!head || list_empty(head))
return;
int count = 0;
struct list_head *node, *prev = head;
list_for_each (node, head) {
count++;
if (count % 2 == 0) {
list_move(node, prev);
node = node->next;
prev = node;
}
}
}
```
### q_reverse
#### Modified version:
Except for the last node, move node to the queue tail from node is previous to the last node to the first node.
This version is more concise.
```c
void q_reverse(struct list_head *head)
{
if (!head || list_empty(head))
return;
struct list_head *cur = head->prev->prev, *next;
while(cur != head) {
next = cur->prev;
list_move_tail(cur, head);
cur = next;
}
}
```
### q_sort
Sort the queue by merge sort.
I want to create another head to maintain when I divide the queue, but `malloc` is disallowed in `q_sort`. Therefore, I remove queue head and pass the first node and the last node as parameters.
Because the `mergeSort` only return the first node of sorted queue, we should iterate sorted queue to find out the last node. Then, connect removed queue head to the first node and the last node of sorted queue.
```c
struct list_head *merge(struct list_head *l1, struct list_head *l2)
{
struct list_head *return_head, *cur;
if (strcmp(list_entry(l1, element_t, list)->value,
list_entry(l2, element_t, list)->value) < 0) {
return_head = l1;
l1 = l1->next;
} else {
return_head = l2;
l2 = l2->next;
}
cur = return_head;
while (l1 && l2) {
if (strcmp(list_entry(l1, element_t, list)->value,
list_entry(l2, element_t, list)->value) < 0) {
cur->next = l1;
l1->prev = cur;
l1 = l1->next;
} else {
cur->next = l2;
l2->prev = cur;
l2 = l2->next;
}
cur = cur->next;
}
if (l1) {
cur->next = l1;
l1->prev = cur;
} else if (l2) {
cur->next = l2;
l2->prev = cur;
}
return return_head;
}
struct list_head *mergeSort(struct list_head *head, struct list_head *tail)
{
if (head == tail)
return head;
struct list_head *front = head, *back = tail;
do {
front = front->next;
back = back->prev;
} while (front != back && front->prev != back);
if (front != back) {
back->next = NULL;
front->prev = NULL;
} else {
front = front->next;
back->next = NULL;
front->prev = NULL;
}
struct list_head *l1 = mergeSort(head, back);
struct list_head *l2 = mergeSort(front, tail);
return merge(l1, l2);
}
void q_sort(struct list_head *head)
{
if (!head || list_empty(head))
return;
struct list_head *front = head->next, *back = head->prev;
front->prev = NULL;
back->next = NULL;
front = mergeSort(front, back);
back = front;
while (back->next)
back = back->next;
head->next = front;
front->prev = head;
head->prev = back;
back->next = head;
}
```
### q_reverseK
### q_sort
### q_merge
### q_descend
## Command list
All commands store in a command list, and it is a singly-linked list
### Data Structure of command list
* name: command name
* operation: do_command function
* documentation: command information show in command help
```c
typedef struct CELE cmd_ele, *cmd_ptr;
struct CELE {
char *name;
cmd_function operation;
char *documentation;
cmd_ptr next;
};
```
### ADD_COMMAND Macro
`ADD_COMMAD` automatically link command `xxx` to its operation function `do_xxx`
```c
#define ADD_COMMAND(cmd, msg) add_cmd(#cmd, do_##cmd, msg)
```
:::warning
You should explain why it works.
:notes: jserv
:::
### add_cmd
`cmd_list` is the head of command list
what `while` loop in funciton `add_cmd` does is sorting commands in alphabetical order. The operaion like insertion sort, find out the suit position from the head of list and insert new command element into command list.
```c
void add_cmd(char *name, cmd_function operation, char *documentation)
{
cmd_ptr next_cmd = cmd_list;
cmd_ptr *last_loc = &cmd_list;
while (next_cmd && strcmp(name, next_cmd->name) > 0) {
last_loc = &next_cmd->next;
next_cmd = next_cmd->next;
}
cmd_ptr ele = (cmd_ptr) malloc_or_fail(sizeof(cmd_ele), "add_cmd");
ele->name = name;
ele->operation = operation;
ele->documentation = documentation;
ele->next = next_cmd;
*last_loc = ele;
}
```
## Add new command shuffle for qtest
### q_shuffle
Follow [the modern shuffle algorithm](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle) to shuffle queue.
* Each round:
1. choose tail node and record node previous to it.
2. remove tail node.
3. generate random number, this number represent node number from `0` ~ `n - 1`
* node number of the first node of queue is `0`.
* `n` means node number of tail node.
4. find out the node that its number is equal to the random number and swap the node for tail node.
5. set tail node to recorded node.
* Terminal:
tail node is equal to the frist node
```c
void q_shuffle(struct list_head *head)
{
if (!head || list_empty(head))
return;
srand(time(NULL));
int size = q_size(head);
struct list_head *cur, *tail = head, *target = head->prev;
for (int i = size - 1; i > 0; i--) {
long random_num = rand() % i;
cur = head->next;
list_del(target);
while (random_num) {
cur = cur->next;
random_num--;
}
list_move_tail(target, cur);
list_move_tail(cur, tail);
tail = tail->prev;
target = tail->prev;
}
}
```
### do_shuffle
When user call command shuffle, funciton `do_shuffle` would be called.
```c
static bool do_shuffle(int argc, char *argv[])
{
if (!l_meta.l)
report(3, "Warning: Calling sort on null queue");
error_check();
int cnt = q_size(l_meta.l);
if (cnt < 2)
report(3, "Warning: Calling sort 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();
}
```
### Add command shuffle
Function `ADD_COMAND` connect command `parameter1` to `do_parameter1` automatically, so when user call command `shuffle`, then function `do_shuffle` would be called.
`parameter2` is the information of command. When user call command `help`, the `"| shuffle queue"` will show in the information of the command `shuffle`.
```c
ADD_COMMAND(shuffle, " | shuffle queue");
```
## Explain how select system call work in this program, and examine the console.c implementation.
The select system call's I/O event model is I/O multiplexer. When we call select, the fd set is copied from userspace to kernel space before iterating through all socket fd. If all of the socket fd fail to satisfy the condition, the kernel thread will release CPU resources; otherwise, the kernel thread will be woken up when the event occurs. Even if the select system call returns, we must still determine which socket fd is ready.
The select system call is used in this program to monitor the file-reading and connection events. When an event occurs, we use the function `FD_ISSET` to determine which socket fd is ready. If the event is a connection event, we will use the accept system call to establish a connection with the client and respond to its request.
```c
// command line 事件
if (readfds && FD_ISSET(infd, readfds)) {
/* Commandline input available */
FD_CLR(infd, readfds);
result--;
set_echo(0);
char *cmdline = readline();
if (cmdline)
interpret_cmd(cmdline);
}
// 連線事件
else if (readfds && FD_ISSET(web_fd, readfds)) {
FD_CLR(web_fd, readfds);
result--;
struct sockaddr_in clientaddr;
socklen_t clientlen = sizeof(clientaddr);
web_connfd =
accept(web_fd, (struct sockaddr *) &clientaddr, &clientlen);
char *p = web_recv(web_connfd, &clientaddr);
char *buffer = "HTTP/1.1 200 OK\r\nContent-Type: text/plain\r\n\r\n";
web_send(web_connfd, buffer);
if (p)
interpret_cmd(p);
free(p);
close(web_connfd);
}
```
## Substitute epoll for select
* Drawbacks of select
1. Everytime the select is called, we must copy fd_set from userspace to kernel space, which will incur significant overhead if the number of fd is large.
2. The limit of fd_set size is 1024.
3. We need to iterate the fd_set to determine which socket fd is ready, the time complexity of this operation is O(n).
Epoll is more flexible than select. Epoll manages multiple socket fds using an epoll fd, and there is no limit to the number of fds in epoll. Furthermore, epoll copies the socket fd in userspace to the event table in kernel space, allowing userspace and kernel space to watch the same memory content by only one copy. When the socket fd is ready, epoll triggers the fd via the callback function, allowing us to learn which socket fd is ready without iterating, reducing the time complexity of this operation to O(1).
To replace select with epoll, we must first modify the function `do_web`. The first step is to create an epoll instance using the function `epoll_create`. Next, because the server socket fd `web_fd` is our polling target, we add it to epoll with function `epoll_ctl`. In this case, we use the `EPOLL_CTL_ADD` operator, which performs the same function as `FD_SET` by adding the fd to epoll and causing epoll to monitor its I/O event.
```c
static int web_fd;
static int epoll_fd = -1;
#define EPOLL_SIZE 256
static bool do_web(int argc, char *argv[])
{
int port = 9999;
if (argc == 2) {
if (argv[1][0] >= '0' && argv[1][0] <= '9')
port = atoi(argv[1]);
}
web_fd = web_open(port);
if (web_fd > 0) {
if ((epoll_fd = epoll_create(EPOLL_SIZE)) < 0) {
report(1, "ERROR: Fail to create epoll");
return false;
}
struct epoll_event ev = {.events = EPOLLIN | EPOLLET};
ev.data.fd = web_fd;
if (epoll_ctl(epoll_fd, EPOLL_CTL_ADD, web_fd, &ev) < 0)
report(1, "Fail to control epoll");
printf("Listener (fd=%d) was added to epoll.\n", epoll_fd);
printf("listen on port %d, fd is %d\n", port, web_fd);
use_linenoise = false;
} else {
perror("ERROR");
exit(web_fd);
}
return true;
}
```
We must modify `cmd_select` after we have modified `do_web`. The function `epoll_wait` is used to determine whether or not events occur; its return value is the number of the ready event, and event information is stored in a data structure called `struct epoll_event`. We usually use a for loop to iterate through all of the ready events and handle them appropriately.
```c
int web_connfd;
static struct epoll_event events[EPOLL_SIZE];
static int cmd_select()
{
if (cmd_done())
return 0;
if (buf_stack->fd == STDIN_FILENO && !block_flag) {
if (prompt_flag) {
printf("%s", prompt);
fflush(stdout);
prompt_flag = true;
}
}
if (epoll_fd == -1) {
set_echo(0);
char *cmdline = readline();
if (cmdline)
interpret_cmd(cmdline);
} else {
int epoll_events_count;
while ((epoll_events_count =
epoll_wait(epoll_fd, events, EPOLL_SIZE, -1)) > 0) {
for (int i = 0; i < epoll_events_count; i++) {
/* EPOLLIN event for listener (new client connection) */
struct sockaddr_in clientaddr;
socklen_t clientlen = sizeof(clientaddr);
while ((web_connfd =
accept(web_fd, (struct sockaddr *) &clientaddr,
&clientlen)) > 0) {
char *p = web_recv(web_connfd, &clientaddr);
char *buffer =
"HTTP/1.1 200 OK\r\n"
"Content-Type: text/html\r\n\r\n"
"<html><head>"
"<link rel=\"shortcut icon\" href=\"#\">"
"</head><body>\n";
web_send(web_connfd, buffer);
if (p)
interpret_cmd(p);
free(p);
close(web_connfd);
}
}
}
}
return 0;
}
```
Sign in with Wallet
Connect another wallet