2019q3 Homework2 (lab0)

contributed by < 93i7xo2 >

tags: sysprog2019

作業要求

• 在 GitHub 上 fork lab0-c
  • 參閱 GitHub 設定指引
• 詳細閱讀 C Programming Lab (英文閱讀正是我們想強化的議題，你應該在共筆上摘要題目要求)，依據指示著手修改 queue.[ch] 和連帶的檔案，測試後用 Git 管理各項修改。
  • 在提交程式前，務必詳閱 如何寫好 Git Commit Message
  • 不用理會 Autolab 和檔案下載的描述，這兩者都是 CMU 專屬
• 除了修改程式，也要編輯「作業區」，增添開發紀錄和 GitHub 連結，提及如何逐步達到要求，以及如何改善效能
  • 解釋自動評分系統運作的原理
  • 提及 qtest 的行為和裡頭的技巧，特別是 signal handler
  • 解析 Valgrind 的運作原理和針對本程式的使用
  • 根據 dudect 工具以及提出的對應論文 Dude, is my code constant time?，探討一種以實驗而非理論驗證時間複雜度的方法
  • 留意 MAGICHEADER, MAGICFREE, MAGICFOOTER, FILLCHAR 等巨集的使用，並探討其動機和用法
• 截止日期：
  • Oct 2, 2019 (含) 之前
  • 越早在 GitHub 上有動態、越早接受 code review，評分越高

開發環境

$ uname -a
Linux ubuntu 5.0.0-29-generic #31~18.04.1-Ubuntu SMP Thu Sep 12 18:29:21 UTC 2019 x86_64 x86_64 x86_64 GNU/Linux

$ gcc --version
gcc (Ubuntu 7.4.0-1ubuntu1~18.04.1) 7.4.0

實作過程

實作下列要求

queue.h

修改queue_t的結構以便實作O(1)時間的q_insert_tail、q_size

typedef struct {
    list_ele_t *head;         /* Linked list of elements */
                              /*
                                You will need to add more fields to this structure
                                to efficiently implement q_size and q_insert_tail
                              */
    int count;                /* Number of elements in linked list */
    list_ele_t *last_element; /* The last element in linked list */
} queue_t;

queue.c

q_new

建立一個新的queue。因應q_size和q_insert_tail的實作，在queue_t創立時紀錄元素個數和最後一個元素。

queue_t *q_new()
{
    queue_t *q = malloc(sizeof(queue_t));
    if (q) {
        q->head = NULL;
        q->count = 0;
        q->last_element = q->head;
    }
    return q;
}

q_free

void q_free(queue_t *q)
{
    /* Free queue structure */
    if (!q)
        return;

    list_ele_t *temp, *target = q->head;
    while (target != NULL) {
        temp = target;
        target = target->next;
        free(temp->value);
        free(temp);
    }
    free(q);
}

q_insert_head

在queue的開頭插入新的元素。插入的元素如果是第一個也是最後一個，須同時修改last_element

bool q_insert_head(queue_t *q, char *s)
{
    if (!q)
        return false;

    /* Create a new element. */
    list_ele_t *newh = malloc(sizeof(list_ele_t));
    if (!newh)
        return false;
    newh->value = (char *) malloc(sizeof(char) * strlen(s) + 1);
    if (!newh->value) {
        free(newh);
        return false;
    }
    strcpy(newh->value, (const char *) s);

    /* Attach new element at the head of linked list. */
    newh->next = q->head;
    q->head = newh;
    q->count++;

    /* Mark it as last element if it's a first element. */
    if (!newh->next)
        q->last_element = newh;

    return true;
}

q_insert_tail

在queue的尾端插入新的元素，須在O(1)時間內完成

從刪除 linked-list node 看程式設計的品味提到的有品味code，用此方式實作一遍O(n)的q_insert_tail，因無法很流暢的寫出來，所以用註解的方式保留下。

bool q_insert_tail(queue_t *q, char *s)
{
    if (!q)
        return false;

    /* Create a new element. */
    list_ele_t *newh = malloc(sizeof(list_ele_t));
    if (!newh)
        return false;
    newh->value = (char *) malloc(sizeof(char) * strlen(s) + 1);
    if (!newh->value) {
        free(newh);
        return false;
    }
    strcpy(newh->value, (const char *) s);
    newh->next = NULL;

    /* Insert element at tail of queue, with time complexity of O(n) */
    /* The *prev* pointer points to the address of thing we'll update */
    /*list_ele_t **prev = &(q->head);
    while (*prev != NULL)
        prev = &(*prev)->next;
    *prev = newh;
    q->count++;*/

    /* Insert element at tail of queue, with time complexity of O(1) */
    q->last_element->next = newh;
    q->last_element = newh;
    q->count++;

    return true;
}

q_remove_head

移除queue開頭的元素，並將該元素的值複製至指定位置

bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    if (q == NULL || q->head == NULL)
        return false;
    if (sp) {
        /* May be bufsize is greater than actual size of value */
        int realBufsize = strlen(q->head->value) < bufsize - 1
                              ? strlen(q->head->value)
                              : bufsize - 1;
        memcpy((void *) sp, (const void *) q->head->value, realBufsize);
        *(sp + realBufsize) = '\0';
    }
    list_ele_t *target = q->head;
    q->head = q->head->next;
    q->count--;
    free(target->value);
    free(target);

    /* Mark last element as NULL if queue is empty */
    if (!q->head)
        q->last_element = NULL;

    return true;
}

首次make test過了但過不了make valgrind，考慮到bufsize有可能比元素內的字串還要大，補上相關程式碼後就過了。

節錄strncpy的介紹：

http://www.cplusplus.com/不推這家

Copies at most count characters of the character array pointed to by src to the character array pointed to by dest, stopping at the first null character.
Zeroes out the rest of the destination buffer, which can be a performance concern.
 If the first count characters were non-null, dest will not contain a null terminated string!

colinyoyo26和a9502854519都使用strncpy處理字串複製，各使用不同的方法插入null character。

• a9502854519

  ​​​​    if (sp != NULL) {
  ​​​​        strncpy(sp, node->value, bufsize - 1);
  ​​​​        sp[bufsize - 1] = '\0';
  ​​​​    }
  

• colinyoyo26

  ​​​​    if (bufsize > 0) {
  ​​​​        memset(sp, '\0', bufsize);
  ​​​​        strncpy(sp, q->head->value, bufsize - 1);
  ​​​​    }
  

q_size

須在O(1)時間內完成，一樣留下了O(n)的實作。

int q_size(queue_t *q)
{
    if (q == NULL)
        return 0;

    /* With time complexity of O(n) */
    /*int count = 0;
    list_ele_t **target = &(q->head);
    while(*target != NULL){
        target = &(*target)->next;
        count++;
    }
    return count;*/

    /* With time complexity of O(1) */
    return q->count;
}

q_reverse

反轉queue的順序，不得新增或移除任何queue中的元素，或是呼叫q_insert_head, q_insert_tail, q_remove_head，必須重新排序queue內的元素

void q_reverse(queue_t *q)
{
    if (q == NULL)
        return;

    list_ele_t *prev = NULL;
    list_ele_t *temp;
    list_ele_t *current = q->last_element = q->head;
    while (current != NULL) {
        temp = current->next;
        current->next = prev;
        prev = current;
        current = temp;
    }
    q->head = prev;
}

colinyoyo26以q->head取代temp，不僅省掉一個local variable也少一行assignment statement。

    list_ele_t *cur = q->head, *prev = NULL;
    q->tail = q->head;

    while (cur) {
        q->head = cur;
        cur = cur->next;
        q->head->next = prev;
        prev = q->head;
    }

qtest signal handling

排版參照uccuser159的共筆

C99規格書

• 7.14 Signal handling <signal.h>

• 7.14.1 Specify signal handling

  Synopsis

  #include <signal.h>
  void (*signal(int sig, void (*func)(int)))(int);
  

  The signal function chooses one of three ways in which receipt of the signal number sig is to be subsequently handled. If the value of func is SIG_DFL, default handling for that signal will occur. If the value of func is SIG_IGN, the signal will be ignored.Otherwise, func shall point to a function to be called when that signal occurs. An invocation of such a function because of a signal, or (recursively) of any further functions called by that invocation (other than functions in the standard library), is called a signal handler.

  試著讀懂function declaration

  ​​​​cdecl> void (*signal(int sig, void (*func)(int)))(int)
  ​​​​syntax error
  

  • What's the meaning of this piece of code? void (*signal(int sig, void (*func)(int)))(int);

  When a signal occurs and func points to a function, it is implementation-defined whether the equivalent of signal(sig, SIG_DFL); is executed or the implementation prevents some implementation-defined set of signals (at least including sig) from occurring until the current signal handling has completed; in the case of SIGILL, the implementation may alternatively define that no action is taken. Then the equivalent of (*func)(sig); is executed. If and when the function returns, if the value of sig is SIGFPE, SIGILL, SIGSEGV, or any other implementation-defined value corresponding to a computational exception, the behavior is undefined; otherwise the program will resume execution at the point it was interrupted.

  用gdb看segmentation fault發生時在magic_handler內的return address指向*p = 0xdead;，貿然return會產生infinite loop

  ​​​​#include <signal.h>
  
  ​​​​void magic_handler(int s) {
  ​​​​    return;
  ​​​​}
  
  ​​​​int main(void) {
  ​​​​    int *p = NULL;
  ​​​​    signal(SIGSEGV, magic_handler);
  ​​​​    *p = 0xdeadbeef;
  ​​​​    return 0;
  ​​​​}
  

  要在segmentation fault後繼續執行執行程式能用setjump()和longjmp()返回指定位置。

  • Best practices for recovering from a segmentation fault
  • How to write a signal handler to catch SIGSEGV?

• 7.13.1.1 The setjmp macro

  Synopsis

  ​#include <setjmp.h>
  int setjmp(jmp_buf env);
  

  Description

  The setjmp macro saves its calling environment in its jmp_buf argument for later use by the longjmp function.

  Returns

  If the return is from a direct invocation, the setjmp macro returns the value zero. If the return is from a call to the longjmp function, the setjmp macro returns a nonzero value.

• 7.13.2.1 The longjmp function

  Synopsis

  ​#include <setjmp.h>
  ​void longjmp(jmp_buf env, int val);
  

Linux Programmer’s Manual詳述setjmp和longjmp的實作行為。

Linux Programmer's Manual

• ALARM(2)

  SYNOPSIS

  #include <unistd.h>
  unsigned int alarm(unsigned int seconds);
  

  alarm() arranges for a SIGALRM signal to be delivered to the calling process in seconds seconds.
  If seconds is zero, any pending alarm is canceled.

• SIGNAL(2)
  The behavior of signal() varies across UNIX versions, and has also varied historically across different versions of Linux. Avoid its use:
  use sigaction(2) instead. See Portability below.

  signal() sets the disposition of the signal signum to handler, which is either SIG_IGN, SIG_DFL, or the address of a programmer-defined function (a "signal handler").

• SIGNAL(7)

  DESCRIPTION

  Linux supports both POSIX reliable signals (hereinafter "standard signals") and POSIX real-time signals.

  • Signal mask and pending signals
    A signal may be blocked, which means that it will not be delivered until it is later unblocked. Between the time when it is generated and when it is delivered a signal is said to be pending.

    Each thread in a process has an independent signal mask, which indicates the set of signals that the thread is currently blocking. A thread can manipulate its signal mask using pthread_sigmask(3). In a traditional single-threaded application, sigprocmask(2) can be used to manipulate the signal mask.

  換言之，process signal mask是用來表示在thread中目前blocked signal set
  How are signals handled in Linux

• SETJMP(3)

  Synopsis

  ​​​​#include <setjmp.h>
  ​​​​int setjmp(jmp_buf env);
  ​​​​int sigsetjmp(sigjmp_buf env, int savesigs);
  ​​​​void longjmp(jmp_buf env, int val);
  ​​​​void siglongjmp(sigjmp_buf env, int val);
  

  Description

  The longjmp() function uses the information saved in env to transfer control back to the point where setjmp() was called and to restore ("rewind") the stack to its state at the time of the setjmp() call.
  In addition, and depending on the implementation (see NOTES), the values of some other registers and the process signal mask may be restored to their state at the time of the setjmp() call.

  • sigsetjmp() and siglongjmp()
    sigsetjmp() and siglongjmp() also perform nonlocal gotos, but provide predictable handling of the process signal mask.

    If, and only if, the savesigs argument provided to sigsetjmp() is nonzero, the process's current signal mask is saved in env and will be restored if a siglongjmp() is later performed with this env.

  setjmp會保存calling environment(instruction pointer, stack pointer…)並return 0，在接下來呼叫longjmp如同在setjmp處return val，用return value控制程式流程。

  Notes

  先看看當下glibc的版本

  $ ldd --version
  ldd (Ubuntu GLIBC 2.27-3ubuntu1) 2.27
  

  POSIX does not specify whether setjmp() will save the signal mask (to be later restored during longjmp()). In System V it will not. In 4.3BSD it will, and there is a function _setjmp() that will not. The behavior under Linux depends on the glibc version and the setting of feature test macros.

  Since glibc 2.19, <setjmp.h> exposes only the System V version of setjmp(). Programs that need the BSD semantics should replace calls to setjmp() with calls to sigsetjmp() with a nonzero savesigs argument.

harness.h

在qtest.c可見queue的相關操作do_new、do_free、do_insert_head等由harness.c的幾個function所包覆。

/*
  Return whether any errors have occurred since last time set error limit
 */
bool error_check()
{
    bool e = error_occurred;
    error_occurred = false;
    return e;
}

/*
 * Prepare for a risky operation using setjmp.
 * Function returns true for initial return, false for error return
 */
bool exception_setup(bool limit_time)
{
    if (sigsetjmp(env, 1)) {
        /* Got here from longjmp */
        jmp_ready = false;
        if (time_limited) {
            alarm(0);
            time_limited = false;
        }
        if (error_message) {
            report_event(MSG_ERROR, error_message);
        }
        error_message = "";
        return false;
    } else {
        /* Got here from initial call */
        jmp_ready = true;
        if (limit_time) {
            alarm(time_limit);
            time_limited = true;
        }
        return true;
    }
}

/*
 * Call once past risky code
 */
void exception_cancel()
{
    if (time_limited) {
        alarm(0);
        time_limited = false;
    }
    jmp_ready = false;
    error_message = "";
}

/*
 * Use longjmp to return to most recent exception setup
 */
void trigger_exception(char *msg)
{
    error_occurred = true;
    error_message = msg;
    if (jmp_ready)
        siglongjmp(env, 1);
    else
        exit(1);
}

介紹這些function的功能，以q_new()這段為例

    error_check();
    if (exception_setup(true))
        q = q_new();
    exception_cancel();
    qcnt = 0;
    show_queue(3);
    return ok && !error_check();
}

• bool exception_setup(bool limit_time)
  以sigsetjmp(env, 1)為分歧點

  • 非透過siglongjmp跳回
    設定time_limit秒後觸發SIGALRM signal，jmp_ready=true，回傳true繼續執行接下來的函式。
  • 透過siglongjmp跳回
    印出error_message，回傳false，接序執行。

• void trigger_exception(char *msg)
error_occurred=true，在非預期情況下被呼叫直接exit(1)，否則直接呼叫siglongjmp

• void exception_cancel()
  清空error_message，time_limited==true則取消alram。

  在沒有設定alarm的情況下呼叫alarm(0)會有事嗎

• error_check()
  返回error_occurred並重設error_occurred，類似Test-and-set，

所以q_new()只要在執行時超過設定秒數、或是segmentation fault連帶呼叫signal handler內的trigger_exception()去設定error_occurred，最後!error_check();會是false。

自動評分系統運作

待補

Valgrind 的運作原理

待補

Reference

colinyoyo26的共筆
hankchang805的共筆