# 2018q3 Homework3 (review) contributed by <[pjchiou](https://github.com/pjchiou)> --- ## Week2 - #2 指標篇 提到 signal 系統呼叫的原型宣告: ```cpp void (*signal(int sig, void (*handler)(int))) (int); ``` |Declaration|Description| |:-|:-| |==signal()==|signal is a function| |signal(==int sig, void (*handler)(int)==)|with 2 arguments| |signal(==int sig==, void (*handler)(int) )|the first argument is a int `sig`| |signal(int sig, ==void (*handler)(int)== )|the second argument is a function pointer `handler`| |signal(int sig, ==void== (*handler)(==int==) )|handler points to a function with 1 argument int and returns void| |==void (*signal==(int sig, void (*handler)(int)))==(int)==;|signal returns a function pointer points to a function with 1 argument int and returns void.| - signal is a function with 2 arguments. - the first argument is a int `sig` - the second argument is a function pointer `handler` - handler needs 1 argument int and return void. - signal returns a function pointer points to a function with 1 argument int and returns void. 這個函式的使用在我們的第 2 個作業內的程式碼 qtest.c 就有。 ```cpp static void queue_init() { fail_count = 0; q = NULL; signal(SIGSEGV, sigsegvhandler); signal(SIGALRM, sigalrmhandler); } ``` 會在程式執行時期若接收到 - SIGSEGV 訊號就執行 `segsegvhandler` 函式 - SIGALRM 訊號就執行 `signalrmhandler` 函式 而這兩個函式是自定義的 exception handler 。 --- ## Week2 - #6 考慮以下程式碼: ```cpp int **arr = malloc(3 * sizeof(int *)); for (int i = 0; i < 3; i++) arr[i] = malloc(4 * sizeof(int)); ``` 如果要 free() 時，是否需要兩層的迴圈呢？倘若有人只是 free(arr); 會發生什麼事？又，該如何改善？ 這段程式如果畫成圖長這個樣子 ```graphviz digraph malloc{ node[shape=record] arr [label="arr", shape=plaintext] arr_a [label="<ptr0> arr[0]|<ptr1> arr[1]|<ptr2> arr[2]"] data1 [label="<ptr1>|||"] data2 [label="<ptr2>|||"] data3 [label="<ptr3>|||"] arr -> arr_a:ptr0:nw arr_a:ptr0 -> data1:ptr1:nw arr_a:ptr1 -> data2:ptr2:nw arr_a:ptr2 -> data3:ptr3:nw } ``` 可以看出如果只 free(arr) 的話，將會造成 memory leak 。 我們用以下指令進行編繹後測試的結果 ``` clang -O0 -g -fsanitize=address -fno-omit-frame-pointer free_ori.c ``` ```cpp=1 #include <stdio.h> #include <stdlib.h> int main() { int **arr = malloc(3 * sizeof(int *)); for (int i = 0; i < 3; i++) arr[i] = malloc(4 * sizeof(int)); /*for (int i = 0; i < 3; i++) free(arr[i]);*/ free(arr); return (0); } ``` 故意將 #9~10 的內層 free 拿掉，出現以下訊息 :::danger ================================================================= \==9692==ERROR: LeakSanitizer: detected memory leaks Direct leak of 48 byte(s) in 3 object(s) allocated from: #0 0x4d9bd0 in malloc (/home/pjchiou/builder/a.out+0x4d9bd0) #1 0x512120 in main /home/pjchiou/builder/free_ori.c:7:14 #2 0x7f481c340b96 in __libc_start_main /build/glibc-OTsEL5/glibc-2.27/csu/../csu/libc-start.c:310 SUMMARY: AddressSanitizer: 48 byte(s) leaked in 3 allocation(s). ::: 跟預期的一樣，改成兩層 free 後就沒有 ERROR 出現。 ### 改善 我們既然已經知道我們要的空間是 3*4 個 int ，不如一開始就 malloc 足夠的空間，再用指標去指向我們要的位置。 參考以下程式 ```cpp=1 #include <stdio.h> #include <stdlib.h> int main() { int *p = malloc(sizeof(int) * 3 * 4), *matrix[3]; for (int i = 0; i < 3; i++) matrix[i] = p + i * 4; free(*matrix); return (0); } ``` 這段程式畫成圖長這樣 ```graphviz digraph malloc{ node[shape=record] arr [label="p", shape=plaintext] arr_a [label="<ptr0> matrix[0]|<ptr1> matrix[1]|<ptr2> matrix[2]"] data [label="<ptr0>||||<ptr1>||||<ptr2>|||"] matptr [label="matrix", shape=plaintext] arr -> data:ptr0:nw arr_a:ptr0 -> data:ptr0:nw arr_a:ptr1 -> data:ptr1:nw arr_a:ptr2 -> data:ptr2:nw matptr -> arr_a:ptr0:nw } ``` 如此一來只需要 free 一次，可以減少 malloc 時 meta data 的使用。 :::info 或許利用前置處理器可以將其擴展成==實際上還是連續記憶體的 k 維陣列==，但我還在想要怎麼寫。 ::: --- ## Week3 - #1 考慮以下程式碼: ```cpp #include <stdio.h> #include <stdint.h> struct test { unsigned int x : 5; unsigned int y : 5; unsigned int z; }; int main() { struct test t; printf("Offset of z in struct test is %ld\n", (uintptr_t) &t.z - (uintptr_t) &t); return 0; } ``` 在 GNU/Linux x86_64 環境中執行，得到以下輸出: ``` Offset of z in struct test is 4 ``` 倘若將第 10 和第 11 換為以下: printf("Address of t.x is %p", &t.x); 會發生什麼事？ 這違反了 [C11](http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1548.pdf) 中 6.5.3.2 節 Address and indirection operators 的限制，這個限制提到 :::warning The operand of the unary & operator shall be either a function designator, the result of a [] or unary * operator, or an lvalue that designates an object that is not a bit-field and is not declared with the register storage-class specifier. ::: 以下兩種==不能==用 `&` 運算子 - bit-field - declared with register-storage specifier --- ## Week3 - #2 考慮以下程式碼，在 little-endian 硬體上，會返回 1，反之，在 big-endian 硬體上會返回 0: ```cpp int main() { union { int a; char b; } c = { .a = 1 }; return c.b == 1; } ``` ### 原理 假設有個佔 4 bytes 的整數 `0x12345678` ，在 little-endian 與 big-endian 的硬體上，分別會是這麼存 ```graphviz digraph { node[shape=record] littleptr [label="little-endian", shape=plaintext] little [label="0x78|0x56|0x34|0x12"] bigptr [label="big-endian", shape=plaintext] big [label="0x12|0x34|0x56|0x78"] } ``` 兩者完全相反，所以在上述的變數在記憶體內會是 ```graphviz digraph { node[shape=record] littleptr [label="little-endian", shape=plaintext] little [label="0x01|0x00|0x00|0x00"] bigptr [label="big-endian", shape=plaintext] big [label="0x00|0x00|0x00|0x01"] } ``` 而如果用 `char` 存取，只會取 1 個 byte ，在 little-endian 下會取到 0x01 ； 反之會取到 0x00 。 類似的程式在判斷硬體是 little-endian 或 big-endian 的時候有很多，例如 - [C program to check little vs. big endian](https://stackoverflow.com/questions/12791864/c-program-to-check-little-vs-big-endian) - [What is Big Endian and Little Endian? How to detect it in C?](http://www.equestionanswers.com/c/c-big-little-endian.php) - [google](https://www.google.com.tw/search?client=ubuntu&hs=F0Z&ei=HwW5W_nyOsjW8QWWnaRI&q=c+endian+check&oq=c+endian+check&gs_l=psy-ab.3..0i7i30i19k1j0i19k1j0i8i30i19k1l8.6677.6755.0.6912.2.2.0.0.0.0.75.149.2.2.0....0...1c.1.64.psy-ab..0.2.149...0i8i7i30i19k1.0.csHdVQO2jtY) --- ## Week3 - #4 考慮以下程式碼: ```cpp=1 #include <stdlib.h> #include <string.h> typedef struct rec { char *value; struct rec *next; } record; void insert_sorted(record **r, const char *value) { record *newrec = NULL; while (*r && strcmp(value, (*r)->value) > 0) r = &((*r)->next); newrec = malloc(sizeof(record)); newrec->value = strdup(value); newrec->next = *r; *r = newrec; } ``` 函式 insert_sorted 的作用是在 r 所指向已依據數值排序的 linked list 中，安插給定的字串，考慮到 string literal 的生命週期，應該在新建立的節點中，複製給定的字串。 我們來看這個程式畫成圖的樣子，假設 linked list 內已有 `aa`->`bb`->`dd` ，現在要插入 `cc` ```graphviz digraph insert{ node[shape=record] aa [label="<value> aa|<ptr> next=bb"] bb [label="<value> bb|<ptr> next=dd"] dd [label="<value> dd|<ptr> next=NULL"] cc [label="<value> cc|<ptr> next=NULL"] r [label="r", shape=plaintext] aa:ptr -> bb:value:nw bb:ptr -> dd:value:nw r -> bb:ptr:nw } ``` 第 16 行，把 `cc` 的 next 值改為 *r ```graphviz digraph insert{ node[shape=record] aa [label="<value> aa|<ptr> next=bb"] bb [label="<value> bb|<ptr> next=dd"] dd [label="<value> dd|<ptr> next=NULL"] cc [label="<value> cc|<ptr> next=dd"] r [label="r", shape=plaintext] aa:ptr -> bb:value:nw bb:ptr -> dd:value:nw cc:ptr -> dd:value:nw r -> bb:ptr:nw } ``` 第 17 行，把`*r` 也就是 `bb` 的 next 值改為 `cc` ```graphviz digraph insert{ node[shape=record] aa [label="<value> aa|<ptr> next=bb"] bb [label="<value> bb|<ptr> next=cc"] dd [label="<value> dd|<ptr> next=NULL"] cc [label="<value> cc|<ptr> next=dd"] r [label="r", shape=plaintext] aa:ptr -> bb:value:nw bb:ptr -> cc:value:nw cc:ptr -> dd:value:nw r -> bb:ptr:nw } ``` 注意 `r` 指向的位置，與我們常見的方法不一樣(雖然效果是等價的)。 ### 刪除節點的程式 ```cpp=1 void delete_node(record **r, const char *value) { if (!value) { printf("Can not delete a NULL in list.\n"); return; } while (*r && strcmp(value, (*r)->value) > 0) r = &((*r)->next); if (!(*r) || strcmp(value, (*r)->value) != 0) { printf("%s is not in this list.\n", value); return; } record *ptr = *r; *r = (*r)->next; free(ptr->value); free(ptr); } ``` - 因為這是一個排序過的 linked list 所以在 #8 中，我們不用看過全部的 list 就知道有沒有在其中。 ### 蒐尋節點 ```cpp=1 void search_node(record *r, const char *value) { if (!value) { printf("NULL is not in this list.\n"); return; } int i; for (i = 1; r && strcmp(value, r->value) > 0; i++) r = r->next; if (r && strcmp(value, r->value) == 0) printf("%s is at %d position.\n", value, i); else printf("Can not find %s in this list.\n", value); } ``` [測試程式](https://github.com/pjchiou/list) :::info 如果還有時間，再把它改成像作業二的測試方式，可支援自動測試。 :::