# 2019q1 Homework1 (lab0)
contributed by < `atlantis0914` >
## 作業要求
* 詳細閱讀 [C Programming Lab](http://www.cs.cmu.edu/~213/labs/cprogramminglab.pdf) 摘要題目要求，依據指示著手修改 `queue.[ch]`和連帶的檔案。
* 解釋自動評分系統運作的原理
* 提及 `qtest` 的行為和裡頭的技巧
### C Programming Lab
此作業主要檢視：
* C語言的動態記憶體管理。
:::info
原文提到關鍵字 Explicit memory management，可以參考CMU的投影片：
[Dynamic memory allocation](https://www.cs.cmu.edu/afs/cs/academic/class/15213-f10/www/lectures/17-allocation-basic.pdf) Page 4:
節錄如下：
**Explicit allocator**：應用程式動態allocate記憶體，需自行free。
例： C語言的malloc與free。
**Implicit allocator**：應用程式動態allocate記憶體，不需自行free。
例： 大部分支援Gargage collection的程式語言如：Java, ML以及Lisp。
:::
* 操作Poniter-based的資料結構。
:::info
[Pointer-based data structure](http://www2.hawaii.edu/~sdunan/study_guides/topic11.html):
指的是類似Linked list這類資料型態的實作中，包含了pointers指向相同的型態。
:::
* 熟悉C語言的string。
* 透過修改資料型態，使得部分對於此資料結構的操作性能提昇。
* 使得程式碼能夠處理特殊的輸入，例如NULL pointer。
#### Programming Task
此作業的目標為利用Linked list實作queue，包含基本的如 inserd head, insert tail, remove head以及free之類的操作，queue.h實作了queue與Linked list的資料結構：
```clike=
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`的資料結構成員：
```clike=
typedef struct {
list_ele_t *head;
list_ele_t *tail;
size_t size;
} queue_t;
```
```clike=
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。
```clike=
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中。
```clike=
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)$的時間複雜度完成。
```clike=
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`的效果。
```clike=
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)$的時間複雜度完成。
```clike=
int q_size(queue_t *q)
{
if(q && q->head) {
return q->size;
}
return 0;
}
```
* `q_reverse`:將此queue中所有元素反向排列。注意題目要求不得以宣告額外的記憶體空間。
```clike=
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`：
```clike=
#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`:
:::info
**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`：
:::info
**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執行程式碼:
```shell=
$ gcc jump.c -O0 -g -Wall -Werror -o jump
$ gdb jump
```
先讓斷點停在`test`函式最後的位置，然後執行`r`:
```shell=
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:
```shell=
(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:
```shell=
(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`的內容：
```shell=
(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的內容：
```shell=
(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`印出的內容能有感覺。
```shell=
$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`的內容：
```shell=
(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>`的程式碼可以推測在做這樣的事：
```clike=
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>`:
```shell=
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](https://en.wikipedia.org/wiki/XOR_cipher)
只要得知金鑰(key)，就可以反向得到原始的數值。
### 理解並驗證`jmp_buf`中的數值
再次根據x86的calling convention，可以知道函式被呼叫之前，return address會被push至stack，因此`0x00007ffff7a22b97 <+39>`到`0x00007ffff7a22b97 <+57>`這段程式碼推測在將return address作加密的動作:
:::info
關於x86的calling convention，可以參考CMU的課程講義：
[Machine Prog: Procedures](https://www.cs.cmu.edu/~213/lectures/07-machine-procedures.pdf)
:::
```shell=
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`函式:
```clike=
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的數值傳入，可以得到：
```shell=
(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檢查一下：
```shell=
(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，因此驗證之前的推測。
:::info
inline assembly可以參考：
[關於GNU Inline Assembly](http://wen00072.github.io/blog/2015/12/10/about-inline-asm/)
:::
Sign in with Wallet
Connect another wallet