2019q1 Homework1 (lab0)

contributed by < atlantis0914 >

作業要求

• 詳細閱讀 C Programming Lab 摘要題目要求，依據指示著手修改 queue.[ch]和連帶的檔案。
• 解釋自動評分系統運作的原理
• 提及 qtest 的行為和裡頭的技巧

C Programming Lab

此作業主要檢視：

• C語言的動態記憶體管理。

原文提到關鍵字 Explicit memory management，可以參考CMU的投影片：
Dynamic memory allocation Page 4:
節錄如下：
Explicit allocator：應用程式動態allocate記憶體，需自行free。
例： C語言的malloc與free。
Implicit allocator：應用程式動態allocate記憶體，不需自行free。
例： 大部分支援Gargage collection的程式語言如：Java, ML以及Lisp。

• 操作Poniter-based的資料結構。

Pointer-based data structure:
指的是類似Linked list這類資料型態的實作中，包含了pointers指向相同的型態。

• 熟悉C語言的string。
• 透過修改資料型態，使得部分對於此資料結構的操作性能提昇。
• 使得程式碼能夠處理特殊的輸入，例如NULL pointer。

Programming Task

此作業的目標為利用Linked list實作queue，包含基本的如 inserd head, insert tail, remove head以及free之類的操作，queue.h實作了queue與Linked list的資料結構：

typedef struct ELE {
    char *value;
    struct ELE *next;
} list_ele_t;

typedef struct {
    list_ele_t *head;
} queue_t;

示意圖：

一個Linked list組成的queue，包含List head與List tail， queue中的元素(element)以List表示。然而要對此Linked list中的資料作操作與管理的話，需要再實作一層封裝，也就這裡的queue_t結構。目前queue_t只有一個成員，為指向List head的指標。

實作下列函式：

• q_new : 新建一個空的queue結構。
  作業要求部份操作時間複雜度必須為
  $O(1)$，因此新增queue_t的資料結構成員：

typedef struct {
    list_ele_t *head;
    list_ele_t *tail;
    size_t size;
} queue_t;

queue_t *q_new()
{
    queue_t *q = malloc(sizeof(queue_t));
    /* What if malloc returned NULL? */
    if(q) {
        q->head = NULL;
        q->tail = NULL;
        q->size = 0;
    }
    return q;
}

• q_free:將指定的queue進行free的動作，包含list中的內容。
  這裡將queue以pointer型態傳入函式，程式碼需要檢查此pointer是否為NULL。

void q_free(queue_t *q)
{
    if(q == NULL) {
        q->head = NULL;
        return;
    }
    while(q->head) {
        list_ele_t *cur = q->head;
        q->head = cur->next;
        free(cur->value);
        free(cur);
    }
    free(q);
}

• q_insert_head: 在queue所指向的List head的位置新增一個List，即新增一個元素至此
  queue中。

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

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

    size_t len = strlen(s);
    newh->value = malloc(len+1);
    if(newh->value == NULL) {
        free(newh);
        return false;
    }
    strncpy(newh->value, s, len);
    newh->value[len] = '\0';
    newh->next = q->head;
    q->head = newh;
    if(q->tail == NULL) {
        q->tail = newh->next;
    }
    q->size++;
    return true;
}

• q_insert_tail: 在queue所指向的List tail的位置新增一個List，注意此操作必須在
  $O(1)$的時間複雜度完成。

bool q_insert_tail(queue_t *q, char *s)
{
    if(q == NULL) {
        return false;
    }
    list_ele_t *newt;
    newt = malloc(sizeof(list_ele_t));
    if(newt == NULL) {
        return false;
    }
    size_t len = strlen(s);
    newt->value = malloc(len+1);
    if(newt->value == NULL) {
        free(newt);
        return false;
    }
    strncpy(newt->value, s, len);
    newt->value[len] = '\0';
    if(q->tail == NULL) {
        q->tail = q->head = newt;
    }
    else {
        q->tail->next = newt;
        q->tail = newt;
    }
    newt->next = NULL;
    q->size++;
    return true;
}

• q_remove_head: 從queue所指向的List head的位置移除一個list。注意此函式的第二個參數若不為NULL pointer的話，需將此list所指向的字串，以第三個參數bufsize所要求的長度存放置該pointer所指向的位置，以達到pop的效果。

bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    /* You need to fix up this code. */
    if(q == NULL || q->head == NULL) {
        return false;
    }
    list_ele_t *oldh = q->head;
    if(sp) {
        memcpy(sp, oldh->value, bufsize-1);
        sp[bufsize-1] = '\0';
    }
    free(oldh->value);
    q->head = q->head->next;
    free(oldh);
    q->size--;
    return true;
}

• q_size:計算此queue的總長度。注意操作必須在
  $O(1)$的時間複雜度完成。

int q_size(queue_t *q)
{
    if(q && q->head) {
        return q->size;
    }
    return 0;
}

• q_reverse:將此queue中所有元素反向排列。注意題目要求不得以宣告額外的記憶體空間。

void q_reverse(queue_t *q)
{
    if(q == NULL || q->head == NULL) {
        return;
    }
    q->tail = q->head;
    list_ele_t *oldh = q->head;
    while(q->head->next) {
        list_ele_t *newh = q->head->next;
        if(q->head == q->tail) {
            q->head->next = NULL;
            q->head = newh;
        }
        else {
            q->head->next = oldh;
            oldh = q->head;
            q->head = newh;
        }
    }
    if(q->head != q->tail) {
        q->head->next = oldh;
    }
}

提及 qtest 的行為和裡頭的技巧

在qtest.c中使用了signal來處理process收到特定的訊號時的後續行為，並且搭配setjmp與longjmp使得程式碼能從例外(exception)發生後恢復正常運行。

為了理解setjmp與longjmp的運作，設計新的實驗並搭配gdb追蹤過程：

仿造qtest.c中，程式碼處理signal以及setjmp與longjmp之間的行為，撰寫jump.c：

#include <signal.h>
#include <stdio.h>
#include <setjmp.h>

static jmp_buf env;

void sigsegvhandler(int sig)
{
    siglongjmp(env, 1);
}

void test(void)
{
    printf("Enter test func\n");
    if(sigsetjmp(env, 1)) {
        printf("Got here from long jump\n");
    }
    else {
        printf("Got here from function call\n");
    }
    printf("Leave test func\n");
}

int main()
{
    signal(SIGSEGV, sigsegvhandler);
    test();
    return 0;
}

在main進入時，呼叫signal使得process收到SIGSEGV時，進入事先準備好的sigsegvhandler執行。test函式呼叫sigsetjmp時，設定好程式碼從siglongjmp返回的位置。 注意到sigsetjmp傳入的參數以及回傳值，可以參考man:

SYNOPSIS

​​​​   int setjmp(jmp_buf env);
​​​​   int sigsetjmp(sigjmp_buf env, int savesigs);

DESCRIPTION

The setjmp() function saves various information about the calling environment (typically, the stack pointer, the instruction pointer, possibly the values of other registers and the signal mask) in the buffer env for later use by longjmp(). In this case, setjmp() returns 0.

setjmp將process當前的stack pointer, instruction pointer以及其他暫存器的內容儲存在env內。此時setjmp會回傳0。

再來看longjmp：

SYNOPSIS

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

Following a successful longjmp(), execution continues as if setjmp() had returned for a second time. This "fake" return can be distinguished from a true setjmp() call because the "fake" return returns the value provided in val. If the programmer mistakenly passes the value 0 in val, the "fake" return will instead return 1.

longjmp利用setjmp已經儲存好的env內容，回到setjmp一開始被呼叫的位置，導致setjmp被執行兩次，而第二次的回傳值取決於longjmp的第二個參數val。

實際搭配gdb執行程式碼:

$ gcc jump.c -O0 -g -Wall -Werror -o jump
$ gdb jump

先讓斷點停在test函式最後的位置，然後執行r:

Starting program: /home/annj/lab0-c/jump 
Enter test func
Got here from function call
Leave test func

Breakpoint 1, test () at jump.c:22
22	}
(gdb) 

可以看到sigsetjmp第一次被執行後回傳0，所以程式碼印出Got here from function call。

此時利用gdb發送SIGSEGV給process:

(gdb) signal SIGSEGV
Continuing with signal SIGSEGV.
Got here from long jump
Leave test func

Breakpoint 1, test () at jump.c:22
22	}
(gdb)

可以看到sigsetjmp被執行第二次，此時回傳值取決於sigsegvhandler內的siglongjmp的參數val，因此程式碼印出Got here from long jump。

想要知道sigsetjmp將哪些內容存放至env，使用gdb將env印出。
在此之前先了解一下env的結構，一樣使用gdb:

(gdb) ptype jmp_buf
type = struct __jmp_buf_tag {
    __jmp_buf __jmpbuf;
    int __mask_was_saved;
    __sigset_t __saved_mask;
} [1]
(gdb) ptype __jmp_buf
type = long [8]

jmp_buf是一個指向jmp_buf_tag的指標型態，成員__jmp_buf是一個長度為8的陣列，每個元素的型態是long。推測__jmp_buf就是man中說明用來儲存stack pointer, instruction pointer以及其他暫存器內容的變數。

再來看env的內容：

(gdb) print env
$1 = {{__jmpbuf = {0, 1239389241773116054, 93824992232992, 140737488346928, 0, 0, 1239389241773116054, 4928737514184624790}, __mask_was_saved = 1, __saved_mask = {__val = {0 <repeats 16 times>}}}}
(gdb) 

搭配參照目前的register的內容：

(gdb) info register
rax            0x10	16
rbx            0x0	0
rcx            0x7ffff7af4154	140737348845908
rdx            0x7ffff7dd18c0	140737351850176
rsi            0x555555756260	93824994337376
rdi            0x1	1
rbp            0x7fffffffde40	0x7fffffffde40
rsp            0x7fffffffde40	0x7fffffffde40
r8             0x7ffff7fe24c0	140737354015936
r9             0x7fffffffde40	140737488346688
r10            0x8	8
r11            0x246	582
r12            0x555555554620	93824992232992
r13            0x7fffffffdf30	140737488346928
r14            0x0	0
r15            0x0	0
rip            0x555555554791	0x555555554791 <test+75>
eflags         0x206	[ PF IF ]
cs             0x33	51
ss             0x2b	43
ds             0x0	0
es             0x0	0
fs             0x0	0
gs             0x0	0
(gdb) 

當下列印出來的暫存器的內容並不等於第一次呼叫sigsetjmp時，存入env的值，只是希望對jmp_buf印出的內容能有感覺。

$1 = {{__jmpbuf = {0,
                   1239389241773116054, 
                   93824992232992, 
                   140737488346928, 
                   0, 
                   0, 
                   1239389241773116054, 
                   4928737514184624790},
                   __mask_was_saved = 1,
                   __saved_mask = {__val = {0 <repeats 16 times>}}}}

可以看到env的__jmpbuf[2]與__jmpbuf[3]與r12和r13一致，至於其他內容呢？
__jmpbuf[1]與__jmpbuf[6]的值雖一致，但無法在register列表中找出有關連的，同樣的__jmpbuf[7]也是一樣的狀況，完全無法得知這些數值的意義。

因此希望觀察程式碼進入sigsetjmp時，將哪些數值存放到env，或者對這些數值做了其他操作。
再次透過gdb，斷點訂在test函式內，呼叫sigsetjmp的位置，執行r之後再單步執行進入sigsetjmp，由於這部份是使用assembly實作，可以使用disas看到sigsetjmp的內容：

(gdb) disas
Dump of assembler code for function __sigsetjmp:
=> 0x00007ffff7a22b70 <+0>:	mov    %rbx,(%rdi)
   0x00007ffff7a22b73 <+3>:	mov    %rbp,%rax
   0x00007ffff7a22b76 <+6>:	xor    %fs:0x30,%rax
   0x00007ffff7a22b7f <+15>:	rol    $0x11,%rax
   0x00007ffff7a22b83 <+19>:	mov    %rax,0x8(%rdi)
   0x00007ffff7a22b87 <+23>:	mov    %r12,0x10(%rdi)
   0x00007ffff7a22b8b <+27>:	mov    %r13,0x18(%rdi)
   0x00007ffff7a22b8f <+31>:	mov    %r14,0x20(%rdi)
   0x00007ffff7a22b93 <+35>:	mov    %r15,0x28(%rdi)
   0x00007ffff7a22b97 <+39>:	lea    0x8(%rsp),%rdx
   0x00007ffff7a22b9c <+44>:	xor    %fs:0x30,%rdx
   0x00007ffff7a22ba5 <+53>:	rol    $0x11,%rdx
   0x00007ffff7a22ba9 <+57>:	mov    %rdx,0x30(%rdi)
   0x00007ffff7a22bad <+61>:	mov    (%rsp),%rax
   0x00007ffff7a22bb1 <+65>:	nop
   0x00007ffff7a22bb2 <+66>:	xor    %fs:0x30,%rax
   0x00007ffff7a22bbb <+75>:	rol    $0x11,%rax
   0x00007ffff7a22bbf <+79>:	mov    %rax,0x38(%rdi)
   0x00007ffff7a22bc3 <+83>:	jmpq   0x7ffff7a22bd0 <__sigjmp_save>
End of assembler dump.
(gdb) 

根據x86的calling convention: rdi, rsi, rdx, rcx, r8與r9存放著caller呼叫函式時，傳入的前6個參數，因此rdi的值就是指向env的記憶體位址，而從0x00007ffff7a22b87 <+19>到0x00007ffff7a22b87 <+35>的程式碼可以推測在做這樣的事：

env[0].__jmpbuf[1] = rax;
env[0].__jmpbuf[2] = r12;
env[0].__jmpbuf[3] = r13;
env[0].__jmpbuf[4] = r14;
env[0].__jmpbuf[5] = r15;

至於0x00007ffff7a22b83 <+19>: mov %rax,0x8(%rdi)將什麼樣的數值存放至env[0].__jmpbuf[1]呢？
觀察0x00007ffff7a22b73 <+3>到0x00007ffff7a22b73 <+15>:

   0x00007ffff7a22b73 <+3>:	mov    %rbp,%rax
   0x00007ffff7a22b76 <+6>:	xor    %fs:0x30,%rax
   0x00007ffff7a22b7f <+15>:	rol    $0x11,%rax

可以看到rax的數值做了xor的加密動作，使用的key為%fs:0x30內的數值，然後作了做算數位移運算。所以我們從print env觀察到的數值有部份被加密了。

關於xor加密可以參考：
XOR cipher
只要得知金鑰(key)，就可以反向得到原始的數值。

理解並驗證jmp_buf中的數值

再次根據x86的calling convention，可以知道函式被呼叫之前，return address會被push至stack，因此0x00007ffff7a22b97 <+39>到0x00007ffff7a22b97 <+57>這段程式碼推測在將return address作加密的動作:

關於x86的calling convention，可以參考CMU的課程講義：
Machine Prog: Procedures

   0x00007ffff7a22b97 <+39>:	lea    0x8(%rsp),%rdx
   0x00007ffff7a22b9c <+44>:	xor    %fs:0x30,%rdx
   0x00007ffff7a22ba5 <+53>:	rol    $0x11,%rdx
   0x00007ffff7a22ba9 <+57>:	mov    %rdx,0x30(%rdi)

為了驗證推測，重新改寫jump.c的test函式:

void test(void)
{
    long enc_eip = 0;
    printf("Enter test func\n");
    if(sigsetjmp(env, 1)) {
        printf("Got here from long jump\n");
    }
    else {
        printf("Got here from function call\n");
    }
    
    enc_eip = env[0].__jmpbuf[7];
    asm("ror $17, %0;"
        "xor %%fs:0x30, %0" : "=r"(enc_eip) : "0"(enc_eip));

    printf("EIP saved by setjmp:%lx\n", enc_eip);
    printf("Leave test func\n");
}

利用inline assembly仿造原本的加密流程，寫一段解密的程式碼，並將之前推測可能是加密過的return address的數值傳入，可以得到：

(gdb) r
Starting program: /home/annj/lab0-c/jump 
Enter test func
Got here from function call
EIP saved by setjmp:5555555547b3

Breakpoint 1, test () at jump.c:26
26	    printf("Leave test func\n");

從結果發現sigsetjmp保存的return address為0x5555555547b3，利用gdb檢查一下：

(gdb) disas
Dump of assembler code for function test:
   ...
   0x00005555555547a2 <+28>:	mov    $0x1,%esi
   0x00005555555547a7 <+33>:	lea    0x200892(%rip),%rdi        # 0x555555755040 <env>
   0x00005555555547ae <+40>:	callq  0x555555554640 <__sigsetjmp@plt>
   0x00005555555547b3 <+45>:	test   %eax,%eax
   0x00005555555547b5 <+47>:	je     0x5555555547c5 <test+63>
   ...

可以看到0x00005555555547b3 <+45>: test %eax,%eax剛好是sigsetjmp保存的return address，因此驗證之前的推測。

inline assembly可以參考：
關於GNU Inline Assembly