2023q1 Homework1 (lab0)

contributed by < qwe661234 >

Implement queue.c

queue structure

Doubly-linked list and its value is string.

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.

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.

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'

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.

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.

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.

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.

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.

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.

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

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

#define ADD_COMMAND(cmd, msg) add_cmd(#cmd, do_##cmd, msg)

You should explain why it works.

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.

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 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

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.

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.

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.

// 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.

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.

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;
}