2019q1 Homework2 (lab0)

contributed by < ArielWu0203 >

tags: `linux_2019`

Overview

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

a queue is a pointer of type queue_t *.
Two special cases:
- a NULL queue is one for which the pointer has value NULL.
```
queue_t *q = NULL;
```
- An empty queue is one pointing to a valid structure, but the head field has value NULL.
```
queue_t *q = malloc(queue_t);// address is valid
q->head = NULL;
```

Programming Task

q new : Create a new, empty queue.

q free : Free all storage used by a queue.

q insert head : Attempt to insert a new element at the head of the queue (LIFO discipline).

q insert tail : Attempt to insert a new element at the tail of the queue (FIFO discipline).

q remove head : Attempt to remove the element at the head of the queue.

q size : Compute the number of elements in the queue.

q reverse: Reorder the list so that the queue elements are reversed in order. This function should not allocate or free any list elements (either directly or via calls to other functions that allocate or free list elements.) Instead, it should rearrange the existing elements.
意思是改變 pointer 就好，不能 free 或是 allocate elements 。

實作

queue.h:
為了 q_insert_tail and q_size require O(1),
所以加入了 *tail and size field.






/* Queue structure */
typedef struct {
    list_ele_t *head;
    list_ele_t *tail;
    int size;
} queue_t;

q new :

void * malloc(int n);
n 為要求的 bytes 數。malloc成功時，則返回 address，malloc 失敗時，則返回 NULL。

malloc 後分配得到的空間是未初始化的。所以在要使用空間時，需用 memset 來初始化為 0。

void * memset (void * p,int c,int n) ;

p 為 address，c 為需要初始化的值(這裡我設定為 0)，n 為需要被初始化的 bytes 數。

queue_t *q_new()
{
    queue_t *q = malloc(sizeof(queue_t));
    if (q == NULL)  // q is a NULL ponter.
        return NULL;

    memset(q, 0, sizeof(queue_t));
    q->head = NULL;
    q->tail = NULL;
    q->size = 0;
    return q;
}

q free:

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

    list_ele_t **indirect = &(q->head);
    list_ele_t *prev = (*indirect);

    while ((*indirect) != NULL) {
        if ((*indirect)->value != NULL)
            free((*indirect)->value);
        (*indirect) = (*indirect)->next;
        free(prev);
        q->size--;
        prev = (*indirect);
    }
    q->tail = NULL;
    free(q);
}

q insert head:




























bool q_insert_head(queue_t *q, char *s)
{
    list_ele_t *newh;
    if (q == NULL)
        return false;

    newh = malloc(sizeof(list_ele_t));
    if (newh == NULL)
        return false;

    memset(newh, 0, sizeof(list_ele_t));
    /* +1 is the end of string (00) */
    newh->value = malloc(sizeof(char) * strlen(s) + 1);
    if (newh->value == NULL) {
        free(newh);
        return false;
    }
    memset(newh->value, 0, sizeof(char) * strlen(s) + 1);
    strncpy(newh->value, s, strlen(s));

    if (q->size == 0)
        q->tail = newh;

    newh->next = q->head;
    q->head = newh;
    q->size++;
    return true;
}

q insert tail:

































bool q_insert_tail(queue_t *q, char *s)
{
    list_ele_t *newh;
    if (q == NULL)
        return false;

    newh = malloc(sizeof(list_ele_t));
    if (newh == NULL)
        return false;

    memset(newh, 0, sizeof(list_ele_t));
    /* +1 is the end of string (00) */
    newh->value = malloc(sizeof(char) * strlen(s) + 1);
    if (newh->value == NULL) {
        free(newh);
        return false;
    }
    memset(newh->value, 0, sizeof(char) * strlen(s) + 1);
    strncpy(newh->value, s, strlen(s));

    if (q->size == 0) {
        q->head = newh;
        q->tail = newh;
        newh->next = NULL;
        q->size++;
        return true;
    }
    q->tail->next = newh;
    q->tail = newh;
    newh->next = NULL;
    q->size++;
    return true;
}

q remove head :

























bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    if (q == NULL || q->size == 0)
        return false;

    list_ele_t **indirect = &(q->head);

    if (sp != NULL) {
        memset(sp, '\0', bufsize);
        strncpy(sp, (*indirect)->value, bufsize - 1);
    }

    list_ele_t *prev = (*indirect);

    if ((*indirect)->value != NULL)
        free((*indirect)->value);
    (*indirect) = (*indirect)->next;
    free(prev);
    --(q->size);

    if (q->size == 0)
        q->tail = NULL;

    return true;
}

q size :







int q_size(queue_t *q)
{
    /* in O(1) time */
    if (q == NULL)
        return 0;
    return q->size;
}

q reverse:





















void q_reverse(queue_t *q)
{
    if (q == NULL || q->size == 0 || q->size == 1)
        return;

    q->tail = q->head;
    list_ele_t **indirect = &(q->head);
    list_ele_t *prev = (*indirect);
    list_ele_t *curr = (*indirect)->next;

    while (curr != NULL) {
        (*indirect) = curr->next;
        curr->next = prev;
        prev = curr;
        curr = (*indirect);
    }
    (*indirect) = prev;

    q->tail->next = NULL;
    return;
}

Result



$ make test
...
---TOTAL    100/100

自動評分系統運作的原理

在 Makefile 中:


test: qtest scripts/driver.py
	scripts/driver.py

所以我去找了 scripts/driver.py:

在 135 行中 :


optlist, args = getopt.getopt(args, 'hp:t:v:A', ['valgrind'])

getopt 是用來處理命令行參數，
'hp:t:v:A' 表示為 -h -p (參數) -t (參數) -v (參數) -A
'valgrind' 表示為 --valgrind

在 usage(name) function 中:
是用來輸出參數的使用方法。







$ ./scripts/driver.py -h

Usage: ./scripts/driver.py [-h] [-p PROG] [-t TID] [-v VLEVEL] [--valgrind]
  -h        Print this message
  -p PROG   Program to test
  -t TID    Trace ID to test
  -v VLEVEL Set verbosity level (0-3)

verbosity level 表示輸出的詳細程度。
-A : 最後會輸出每個 trace file 的分數 (以 JASON string 形式)

可以用不同的參數來測試，預設為
-p (./qtest)
-t (trace directory 中的所有檔案)
-v 0
-valgrind (false)
-A (false)

console.{c,h} : Implements command-line interpreter for qtest
report.{c,h} : Implements printing of information at different levels of verbosity

harness.[ch]

在 README 中有提到 :
harness.{c,h} : Customized version of malloc and free to provide rigorous testing framework (藉由改版過後的 malloc 和 free 來嚴格維護記憶體的使用)
改版過後的 malloc 和 free 是什麼? 去看了 harness.h 後發現:



#define malloc test_malloc
#define free test_free
#define strdup test_strdup

所以在 qtest.c 裡使用的 malloc 和 free 都是 call test_malloc & test_free function。

test_malloc function 中:

































void *test_malloc(size_t size)
{
    ...
    
    /* 除了原本就要配置的空間大小，
     * 再加上 block 來 maintain 空間的使用，
     * 也在最後加了 sizeof(size_t) 當作 magic footer 的空間。
     */
     
    block_ele_t *new_block = malloc(size + sizeof(block_ele_t) + sizeof(size_t));
    ...
    new_block->magic_header = MAGICHEADER;
    
    /* 原本的空間大小 */
    new_block->payload_size = size;
    
    /* 找到 magic_footer 應該要放入的起始 address ，並把值填入。 */
    *find_footer(new_block) = MAGICFOOTER;
    
    /* allocate 原本就要的空間大小 
     * FILLCAHR 為 magic number，作為初始化用。 
     */
    void *p = (void *) &new_block->payload;
    memset(p, FILLCHAR, size);
    
    new_block->next = allocated;
    new_block->prev = NULL;
    if (allocated)
        allocated->prev = new_block;
    allocated = new_block;
    allocated_count++;
    return p;
}

*find_footer function 中:






static size_t *find_footer(block_ele_t *b)
{
    /* 找到 magic_footer 的 address 並回傳 */
    size_t *p = (size_t *) ((size_t) b + b->payload_size + sizeof(block_ele_t));
    return p;
}

test_free function 中:
































void test_free(void *p)
{
    ...
    /* 找到 block 的開頭和結尾 */
    block_ele_t *b = find_header(p);
    size_t footer = *find_footer(b);
    /* 偵錯 */
    if (footer != MAGICFOOTER) {
        report_event(MSG_ERROR,
                     "Corruption detected in block with address %p when "
                     "attempting to free it",
                     p);
        error_occurred = true;
    }
    /* 將 block field value 換成 free */
    b->magic_header = MAGICFREE;
    *find_footer(b) = MAGICFREE;
    memset(p, FILLCHAR, b->payload_size);

    /* Unlink from list */
    block_ele_t *bn = b->next;
    block_ele_t *bp = b->prev;
    if (bp)
        bp->next = bn;
    else
        allocated = bn;
    if (bn)
        bn->prev = bp;

    free(b);
    allocated_count--;
}

巨集的使用

從上面的 code 中，可以發現 MAGICHEADER MAGICFREE MAGICFOOTER 用來檢測在 malloc 和 free 時有沒有出錯，還有 FILLCAHR 作為初始化用。 (這些皆為 magic number )

題外話 : 認真看了一下 #define MAGICHEADER 0xdeadbeef 這行，覺得這取名也太特別了，就去 google 了一下，意外查到有趣的小知識，有興趣可以點 link & magic number–wiki

qtest 的行為和裡頭的技巧

signal

Reference:SIGNAL(2)



typedef void (*sighandler_t)(int);
// dclare signaler_t as  pointer to function(int) returning void.
sighandler_t signal(int signum, sighandler_t handler);

當接收到不同的 signum 參數，會有 handler 來處理。
SIGSEGV : Invalid memory reference.(想要取一個 NULL 或是不存在的 pointer)
SIGALRM : Timer signal from ALARM(2).


unsigned int alarm(unsigned int seconds);

在 harness.c 中:















/*
 * 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)) {
        ...
        if (limit_time) {
            alarm(time_limit); // 這裡 time_limit 為 1 (static int time_limit = 1;)
            time_limited = true;
        }
        return true;
    }
}

Valgrind

Valgrind is a GPL'd system for debugging and profiling Linux programs. With Valgrind's tool suite, you can automatically detect many memory management and threading bugs.
reference

運作原理

Valid-value (V) bits : 會記住哪些 variable 是否有值。
Valid-address (A) bits : 會記住哪些空間被分配出去。
Reference:
Details of Memcheck's checking machinery

本程式的使用

Guide to valgrind

參數

--quiet : 只打印錯誤
--leak-check=full --show-leak-kinds=all : check for leak.

memory lost

definitely lost:
heap-allocated memory that was never freed to which the program no longer has a pointer. Valgrind knows that you once had the pointer, but have since lost track of it. This memory is definitely orphaned.
indirectly lost:
heap-allocated memory that was never freed to which the only pointers to it also are lost. For example, if you orphan a linked list, the first node would be definitely lost, the subsequent nodes would be indirectly lost.
possibly lost:
heap-allocated memory that was never freed to which valgrind cannot be sure whether there is a pointer or not.
still reachable: heap-allocated memory that was never freed to which the program still has a pointer at exit (typically this means a global variable points to it).

使用問題 : 若我執行下列程式，會有 ERROR: Time limit exceeded. 和 ERROR: Freed queue, but 1 blocks are still allocated 訊息。

$ valgrind ./qtest 
cmd>new
cmd>new
q = []
cmd>ih dolphin 1000000
cmd>ih dolphin 1000000
ERROR: Time limit exceeded.  Either you are in an infinite loop, or your code is too inefficient
Insertion of dolphin failed
q = [dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin ... ]
cmd>quit 
cmd>quit
Freeing queue
ERROR: Freed queue, but 1 blocks are still allocated
==4389== 48 bytes in 1 blocks are definitely lost in loss record 1 of 2
==4389==    at 0x4C2DB8F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==4389==    by 0x404CF5: test_malloc (harness.c:130)
==4389==    by 0x405251: q_insert_head (queue.c:86)
==4389==    by 0x4014F9: do_insert_head (qtest.c:166)
==4389==    by 0x403A9C: interpret_cmda (console.c:218)
==4389==    by 0x403B3D: interpret_cmd (console.c:239)
==4389==    by 0x4049AA: cmd_select (console.c:605)
==4389==    by 0x404B0E: run_console (console.c:642)
==4389==    by 0x40263A: main (qtest.c:583)
==4389== 
==4389== 56 bytes in 1 blocks are still reachable in loss record 2 of 2
==4389==    at 0x4C2DB8F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==4389==    by 0x404CF5: test_malloc (harness.c:130)
==4389==    by 0x405203: q_insert_head (queue.c:77)
==4389==    by 0x4014F9: do_insert_head (qtest.c:166)
==4389==    by 0x403A9C: interpret_cmda (console.c:218)
==4389==    by 0x403B3D: interpret_cmd (console.c:239)
==4389==    by 0x4049AA: cmd_select (console.c:605)
==4389==    by 0x404B0E: run_console (console.c:642)
==4389==    by 0x40263A: main (qtest.c:583)
==4389==

是超過了可執行時間，所以我去找了 sigalrmhandler (處理 SIGALRM signal 的 handler function )，發現 call trigger_exception function :









void trigger_exception(char *msg)
{
    error_occurred = true;
    error_message = msg;
    if (jmp_ready)
        siglongjmp(env, 1);
    else
        exit(1);
}

int sigsetjmp(sigjmp_buf env, int savesigs); :
link

save stack context for nonlocal goto (意思是會存目前的stack)

return 0 if returning directly, and nonzero when returning from longjmp(3) or siglongjmp(3) using the saved context.
- env : 存 stack
- savesigs : 不為 0 時，也會把 signals 存起來。
void siglongjmp(sigjmp_buf env, int val);
:
link

siglongjmp() also restores the signal mask that was saved by sigsetjmp(3)

了解了 siglongjmp 和 siglongjmp 後，在 harness.c 中找到了 siglongjmp :

























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

會 jump 到最近一次的 exception_setup，因為藉由 valgrind 發現出錯的地方在 do_insert_head (qtest.c:166) :













bool do_insert_head(int argc, char *argv[])
{
    ...
    if (exception_setup(true)) {
        for (r = 0; ok && r < reps; r++) {
            bool rval = q_insert_head(q, inserts);
            ...
        }
    }
    exception_cancel();
    show_queue(3);
    return ok;
}

重新回到上次儲存的 stack，這次 exception_setup(true) 回傳 false ，不再 malloc 了，但是上一次exception_setup(true) 回傳的是 true，所以 malloc a block，因為是 dynamic allocate，所以 stack 還原了，但是 block 卻沒有 free !

dudect 工具

Statistcal analysis (not static anaylysis)
Leakage detection techniques take two sets of measurements for two different input data classes.
常用的 leakage deteciotion : fix-vs-random tests
the first class input data is fixed to a constant value, and the second class input data is chosen at random for each measurement.
t-test : Welch’s t-test