2018q3 Homework3 (review)
===
contributed by < [p61402](https://github.com/p61402) >
###### tags: `sysprog`
## 第 2 週 測驗題 4
### 問題描述
考慮到以下程式碼:
```clike=
int B = 2;
void func(int *p) { p = &B; }
int main() {
int A = 1, C = 3;
int *ptrA = &A;
func(ptrA);
printf("%d\n", *ptrA);
return 0;
}
```
該如何修改，才能讓 `func` 得以變更到 `main` 裡頭 `ptrA` 的內含值？
:::success
延伸問題: 在 GitHub 找出使用 the pointer to the pointer 的 C 語言程式碼，並加以討論
:::
### 想法
上述程式碼中，`ptrA`指向`A`的記憶體位址`&A`，而指標`p`指向`ptrA`所指的記憶體，因此改變`p`的值並無法改變`ptrA`指向的值。由此可知，將`p`指向的值改為`B`的記憶體位址`&B`，`ptrA`所指向的值依然不會被改變。
因此若要改變`ptrA`指向的值，必須宣告另一個指標指向`ptrA`的記憶體位址，將此記憶體所存放的值改為`B`的記憶體位址`&B`。
這時就需要透過 a pointer to pointer，宣告一個指標`p`指向指標`ptrA`的記憶體位址，將`p` dereference 的值改為`&B`，就可以改變`ptrA`的內含值。
```clike=
int B = 2;
void func(int **p) { *p = &B; }
int main() {
int A = 1, C = 3;
int *ptrA = &A;
func(&ptrA);
printf("%d\n", *ptrA);
return 0;
}
```
### 延伸問題
在 [curl](https://github.com/curl/curl) 專案中的 [/src/tool_doswin.c](https://github.com/curl/curl/blob/master/src/tool_doswin.c) 原始碼，使用函式[`sanitize_file_name`](https://github.com/curl/curl/blob/master/src/tool_doswin.c#L135)將檔案或路徑名稱進行「消毒」，意思是將所有不符合命名規範的字元以下標線 (underscores) 代替，例如：`f?*foo => f__foo`。以下為此函式的宣告：
```clike
SANITIZEcode sanitize_file_name(char **const sanitized,
const char *file_name, int flags)
```
此函式的第一個參數為`char **const sanitized`，用來傳遞修改後的檔名或路徑，而第二個參數`const char *file_name`則是欲修正檔名或路徑。由於程式碼冗長，以下只取重點部分來進行討論。
```clike=
char *p, *target;
size_t len;
SANITIZEcode sc;
size_t max_sanitized_len;
if(!sanitized)
eturn SANITIZE_ERR_BAD_ARGUMENT;
*sanitized = NULL;
if(!file_name)
return SANITIZE_ERR_BAD_ARGUMENT;
```
若宣告一個指標變數`char *str`，假設指標`sanitized`指向指標`str`的記憶體位址，那麼`*sanitized = NULL;`則是將指標`sanitized` dereference 的值，也就是指標`str`指向的值設為`NULL`。
```clike=
len = strlen(file_name);
if(len > max_sanitized_len) {
if(!(flags & SANITIZE_ALLOW_TRUNCATE) || truncate_dryrun(file_name, max_sanitized_len))
return SANITIZE_ERR_INVALID_PATH;
len = max_sanitized_len;
}
target = malloc(len + 1);
if(!target)
return SANITIZE_ERR_OUT_OF_MEMORY;
strncpy(target, file_name, len);
target[len] = '\0';
```
配置記憶體給`target`變數，並將`file_name`複製到`target`中。
```clike=
if(!(flags & SANITIZE_ALLOW_RESERVED)) {
sc = rename_if_reserved_dos_device_name(&p, target, flags);
free(target);
if(sc)
return sc;
target = p;
len = strlen(target);
if(len > max_sanitized_len) {
free(target);
return SANITIZE_ERR_INVALID_PATH;
}
}
*sanitized = target;
return SANITIZE_ERR_OK;
```
在經過一連串處理後，最後將指標`target`所指向的記憶體位址指派給 value of `sanitized`，就可以成功透過指標的指標修改函式外的變數。
---
## 第 2 週 測驗題 5
### 問題描述
以下程式是合法 C99 程式嗎？
```C
#include <stdio.h>
int main() { return (********puts)("Hello"); }
```
請搭配 C 語言規格書解釋
繼續思考以下是否合法:
```C
#include <stdio.h>
int main() { return (**&puts)("Hello"); }
```
繼續變形:
```C
#include <stdio.h>
int main() { return (&**&puts)("Hello"); }
```
也會合法嗎？為什麼？請翻閱 C 語言規格書解說。
### 想法
#### 第一段程式碼
```C
#include <stdio.h>
int main() { return (********puts)("Hello"); }
```
- C99 [6.3.2.1]
A function designator is an expression that has function type. Except when it is the
operand of the sizeof operator) or the unary & operator, a function designator with
type ‘‘function returning type’’ is converted to an expression that has type ‘‘pointer to
function returning type’’.
- C99 [6.5.3.2]
The unary * operator denotes indirection. If the operand points to a function, the result is
a function designator; if it points to an object, the result is an lvalue designating the
object. If the operand has type ‘‘pointer to type’’, the result has type ‘‘type’’. If an
invalid value has been assigned to the pointer, the behavior of the unary * operator is
undefined.)
根據以上 C 語言規格書的描述，`*puts`是一個 function designator，會被轉成「指向函式回傳型別的指標」，由於`*`是 right associative operator，因此運算順序由右至左，可以將原式寫成`*(*(*(*(*(*(*(*puts)))))))`，依此類推`(********puts)`最後的結果仍然是一個 function designator。
因此`(********puts)("Hello")`的結果會等同於`puts("Hello")`，不論左方有幾個`*`。
#### 第二段程式碼
```C
#include <stdio.h>
int main() { return (**&puts)("Hello"); }
```
- C99 [6.5.3.2]
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.
- C99 [6.5.3.2]
The unary & operator yields the address of its operand. If the operand has type ‘‘type’’,
the result has type ‘‘pointer to type’’. If the operand is the result of a unary * operator,
neither that operator nor the & operator is evaluated and the result is as if both were
omitted, except that the constraints on the operators still apply and the result is not an
lvalue.
- C99 [6.5.3.2] 註釋 84
Thus, &*E is equivalent to E (even if E is a null pointer), and &(E1[E2]) to ((E1)+(E2)). It is
always true that if E is a function designator or an lvalue that is a valid operand of the unary & operator, *&E is a function designator or an lvalue equal to E.
由於`*`以及`&`都是 right associative operator，因此`(**&puts)`等同於`(*(*(&puts)))`。
因為`puts`是 function designator，所以`(*&(puts))`也是 function designator 等同於`puts`，所以可以化簡為`*(puts)`。
再根據第一段程式碼所得到的結論，`*(puts)`也是一個 function designator 等同於 `puts`，所以`(**&puts)("Hello")`依然會等同於`puts("Hello")`。
#### 第三段程式碼
```C
#include <stdio.h>
int main() { return (&**&puts)("Hello"); }
```
根據前兩段程式碼得出的結論，`(&**&puts)`可以寫成`(&*(*&(puts)))`，`*&(puts)`等同於`puts`，`&*(puts)`也等同於`puts`，所以`(&**&puts)("Hello")`的結果依舊與`puts("Hello")`相同。
---
## 第 3 週 測驗題 1
### 題目敘述
考慮以下程式碼:
```C=
#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 換為以下:
```C=10
printf("Address of t.x is %p", &t.x);
```
會發生什麼事？
==作答區==
* `(a)` 印出類似 `0x7ffd144e8ad4` 的輸出，也就是 `t` 結構物件的位址;
* `(b)` 印出類似 `0x7ffd144e8ad4` 的輸出，和 `t` 結構物件差距 4 bytes;
* `(c)` 可以印出數值，但這與編譯器實作有關，不能解讀;
* `(d)` 編譯失敗，不能這樣宣告結構體的成員;
* `(e)` 編譯失敗，不能將指標指向沒有對齊 1 byte 的結構體成員;
參考資料: [Portable Bit Fields in packetC](https://link.springer.com/content/pdf/10.1007/978-1-4302-4159-1_34.pdf)
:::success
延伸問題: 解釋原因，並且找出 C99/C11 規格書對應的描述
:::
### 想法與延伸問題
- C99 [6.7.2.1]
A member of a structure or union may have any object type other than a variably modified type. In addition, a member may be declared to consist of a specified number of bits (including a sign bit, if any). Such a member is called a **bit-field**; its width is preceded by a colon.
- C99 [6.5.3.2]
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.
根據 C 語言規格書的描述，`struct`以及`union`內的變數可以宣告為指定大小的 bit，稱為 **bit-field**。
但是`&`運算子所能操作的運算元不能夠是具有 bit-field 的物件，因此執行以下程式碼會產生錯誤。
```C=10
printf("Address of t.x is %p", &t.x);
```
```bash
error: cannot take address of bit-field ‘x’
printf("%p\n", &t.x);
^
```
---
## 第 3 週 測驗題 2
### 問題描述
考慮以下程式碼，在 little-endian 硬體上，會返回 `1`，反之，在 big-endian 硬體上會返回 `0`:
```C
int main() {
union { int a; char b;
} c = { .a = K1 };
return c.b == K2;
}
```
補完上述程式碼。
==作答區==
K1 = ?
* `(a)` 0
* `(b)` 1
* `(c)` -1
* `(d)` 254
K2 = ?
* `(a)` 0
* `(b)` 1
* `(c)` 254
:::success
延伸問題: 解釋運作原理，並找出類似的程式碼
:::
### 想法
`union`雖然一次只能使用其中一個成員，但是配置的記憶體是固定的，`union`的大小會相當於其中最大的成員所佔的記憶體大小，以上述程式碼為例，`int`佔 4 bytes，`char`只佔 1 byte，因此此`union`的大小會等於 4 bytes，如下方程式碼所示：
```clike=
int endian()
{
union {
int a;
char b;
} c;
printf("sizeof(c) = %ld\n", sizeof(c));
printf("sizeof(c.a) = %ld\n", sizeof(c.a));
printf("sizeof(c.b) = %ld\n", sizeof(c.b));
}
```
```bash=
# output
sizeof(c) = 4
sizeof(c.a) = 4
sizeof(c.b) = 1
```
:::info
思考 C 語言提供 union 的用意，以及實務上會怎麼用
:notes: jserv
:::
> union 在嵌入式系統中，可以提供同一個數值不同的存取介面 [[source](https://segmentfault.com/q/1010000009731399)]，例如：
> ```clike=
> typedef union {
> unsigned int num;
> struct {
> unsigned char byte0;
> unsigned char byte1;
> unsigned char byte2;
> unsigned char byte3;
> } bytes;
> } Demo;
>
> int main()
> {
> Demo demo = { .num = 0x12345678 };
> demo.bytes.byte0 = 0xAA;
> }
> ```
> 利用 gdb 來觀察：
> ```gdb
> (gdb) b main
> Breakpoint 1 at 0x4004da: file union_application.c, line 15.
> (gdb) r
> Starting program: /home/qoo/Documents/jserv/union_application
> Breakpoint 1, main () at union_application.c:15
> 15 Demo demo = { .num = 0x12345678 };
> ```
> ```gdb
> (gdb) n
> 17 demo.bytes.byte0 = 0xAA;
> (gdb) p/x demo
> $1 = {num = 0x12345678, bytes = {byte0 = 0x78, byte1 = 0x56, byte2 = 0x34, byte3 = 0x12}}
> (gdb) n
> 18 }
> (gdb) p/x demo
> $2 = {num = 0x123456aa, bytes = {byte0 = 0xaa, byte1 = 0x56, byte2 = 0x34, byte3 = 0x12}}
> ```
> 可以直接讀取或更改整個 value，或是只更改其中一個 byte。
>
> 觀察各個 byte 的值可得知系統為 little endian。
>
> [name=p61402]
#### little endian vs big endian
在 little endian 中，lsb 會被放在較低的記憶體空間，msb 則被放在較高的記憶體空間。
而 big endian 正好相反，msb 被放在較低的記憶體位址，lsb 被放在較高的記憶體位址。
由於`c.a`與`c.b`共用同一段記憶體，因此當`c.a=0x00000001`時，在 little endian 的系統`0x01`會被存放在較低的記憶體位址，在 big endian 的系統`0x01`則會被存放在較高的記憶體位址。
由於`char`只佔一個 byte，`c.b`在 little endian 的系統中會取得`0x01`，但在 big endian 的系統中會取得`0x00`。如下圖所示：
以下程式碼在`c.a = 1`時，將`c.a`以及`c.b`的值從低位址往高位址印出。
在 little endian 的系統中，`c.a`的值等於`0x01000000`，而`c.b`的值會等於`0x01`。
```clike=
void show_mem_rep(char *name, char *start, int n)
{
int i;
printf("%s = ", name);
printf("0x");
for (i = 0; i < n; i++)
printf("%.2x", start[i]);
printf("\n");
}
int endian()
{
union {
int a;
char b;
} c = { .a = 1 };
show_mem_rep("c.a", (char *)&c.a, sizeof(c.a));
show_mem_rep("c.b", (char *)&c.b, sizeof(c.b));
}
```
:::success
善用 GDB script，你可以不用避免無謂的 printf
:notes: jserv
:::
```bash
# output
c.a = 0x01000000
c.b = 0x01
```
### 延伸問題
[Little and Big Endian Mystery](https://www.geeksforgeeks.org/little-and-big-endian-mystery/) 這篇文章提供了一個快速判斷系統是 little endian 還是 big endian 的方法。
```clike=
#include <stdio.h>
int main()
{
unsigned int i = 1;
char *c = (char*)&i;
if (*c)
printf("Little endian");
else
printf("Big endian");
getchar();
return 0;
}
```
上述程式碼中，`i`是一個 4 bytes 的`int`物件，而`c`則是指向`i`記憶體位址的指標，但是`c`是一個`char`型別的指標。
因此若將`c` dereference 只會得到第一個 byte 的值，因此在 little endian 系統中`*c = 0x01`，在 big endian 系統中則 `*c = 0x00`。
---
## 第 3 週 測驗題 4
### 題目敘述
考慮以下程式碼:
```C
#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 = &((F1)->next);
newrec = malloc(sizeof(record));
newrec->value = F2(value);
newrec->next = F3;
F4 = newrec;
}
```
函式 `insert_sorted` 的作用是在 r 所指向已依據數值排序的 linked list 中，安插給定的字串，考慮到 string literal 的生命週期，應該在新建立的節點中，複製給定的字串。
請補完上述程式碼。
==作答區==
F1 = ?
* `(a)` r
* `(b)` **r
* `(c)` *r
* `(d)` r->next
* `(e)` *r->next
F2 = ?
* `(a)` 無
* `(b)` strdup
* `(c)` strcpy
* `(d)` strlen
* `(e)` strcmp
F3 = ?
* `(a)` r
* `(b)` **r
* `(c)` *r
* `(d)` r->next
* `(e)` *r->next
F4 = ?
* `(a)` **r
* `(b)` *r
* `(c)` r
* `(d)` r->next
* `(e)` *r->next
:::success
延伸問題: 解釋運作原理，並新增刪除和搜尋節點的程式，附上完整的測試計畫
:::
### 想法
在`insert_sorted`函式中，使用了 pointer to pointer 的概念，`r`為指向一個指標的指標，而`*r`則為指向的指標的值，為 linked list 最前端的記憶體位址。
```clike
int strcmp(const char *s1, const char *s2);
```
根據 manual page 上定義，函式`strcmp`會回傳一個`int`，回傳值有三種可能：
- 小於 0 ： s1 與 s2 第一個不 match 的字元 c1 < c2
- 等於 0 ： s1 與 s2 完全 match
- 大於 0 ： s1 與 s2 第一個不 match 的字元 c1 > c2
也可以 s1 與 s2 的 lexicographic order 來解釋，若 s1 的 lexicographic order < s2 的 lexicographic order，則回傳值小於 0。
因此以下這段程式碼可以用來在 linked list 中尋找第一個不小於`value`的字串。
```clike
while (*r && strcmp(value, (*r)->value) > 0)
r = &((F1)->next);
```
舉個例子，若 linked list 為`a->c->d`，而`value="b"`，`r`就會等於`c`的記憶體位址。
所以`F1`應該為`*r`，這樣`(*r)->next`就會等於`c`這個 node 的記憶體位址，由於`r`是一個 pointer to pointer，所以要指派為`&((*r)->next)`。
而以下這段程式碼為`newrec`配置一段記憶體，而`newrec->value`為一個`char *`，因此同樣必須配置記憶體才能夠使用，在所有選項中只有`strdup`有配置記憶體，因此`F2`應為`strdup`。
```clike
newrec = malloc(sizeof(record));
newrec->value = F2(value);
```
利用以下這張圖就能夠快速釐清目前的情況：
`r`指向 linked list 的`head`，而`head`指向`C`這個 node 的記憶體位址。
此時要將一個新的 node `newrec`插入`A`與`C`之間，先將`newrec->next`設為`&c`，也就是`*r`，`newrec->next = *r;`，因此`F3`為`*r`。
接著要將`A->next`設為`newrec`，由於`A->next`的值與`head`的值相同，因此將`head`設為`newrec`相當於更改`A->next`的值，所以利用`*r`更改`head`的值，`*r->newrec`，`F4`為`*r`。
完成程式碼如下：
```clike=
#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;
}
```
### 延伸問題
#### [sorted_linked_list.h](https://github.com/p61402/sorted_linked_list/blob/master/sorted_linked_list.h)
```clike=
#include <stdbool.h>
typedef struct rec {
char *value;
struct rec *next;
} record;
typedef struct {
record *head;
} sorted_list;
sorted_list* new_list();
bool insert_sorted(record **r, const char *value);
bool delete_element(record **r, char *value);
record* find(record **r, char *value);
void free_list(record **r);
void traverse(record **head);
```
#### [sorted_linked_list.c](https://github.com/p61402/sorted_linked_list/blob/master/sorted_linked_list.c)
```clike=
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include "sorted_linked_list.h"
sorted_list* new_list()
{
sorted_list *l = malloc(sizeof(sorted_list));
if (l)
l->head = NULL;
return l;
}
bool insert_sorted(record **r, const char *value)
{
record *newrec = NULL;
while (*r && strcmp(value, (*r)->value) > 0)
r = &((*r)->next);
newrec = malloc(sizeof(record));
if (!newrec)
return false;
newrec->value = strdup(value);
if (!(newrec->value))
return false;
if (*r)
newrec->next = *r;
else
newrec->next = NULL;
*r = newrec;
return true;
}
bool delete_element(record **r, char *value)
{
while (*r && strcmp(value, (*r)->value) > 0)
r = &((*r)->next);
if (*r && strcmp(value, (*r)->value) == 0)
{
*r = (*r)->next;
return true;
}
return false;
}
record* find(record **r, char *value)
{
record *tar = malloc(sizeof(record));
tar = NULL;
while (*r && strcmp(value, (*r)->value) > 0)
r = &((*r)->next);
if (*r && strcmp(value, (*r)->value) == 0)
tar = *r;
return tar;
}
void free_list(record **r)
{
record *cur = *r;
while (cur)
{
record *temp = cur->next;
free(cur->value);
free(cur);
cur = temp;
}
*r = NULL;
}
void traverse(record **head)
{
record *cur = *head;
while (cur)
{
printf("%s->", cur->value);
cur = cur->next;
}
printf("NULL\n");
}
```
#### [linked_list_test.c](https://github.com/p61402/sorted_linked_list/blob/master/linked_list_test.c)
```clike=
#include <stdio.h>
#include <assert.h>
#include "sorted_linked_list.h"
void test_insert();
void test_delete();
void test_find();
void test_free();
int main()
{
printf("Start testing.\n");
test_insert();
test_delete();
test_find();
test_free();
printf("All tests passed.\n");
}
void test_insert()
{
printf("Start test_insert().\n");
bool status;
sorted_list *l = new_list();
assert(l != NULL);
assert(l->head == NULL);
status = insert_sorted(&(l->head), "a");
assert(status == true);
assert(l->head != NULL);
assert(l->head->value != NULL);
status = insert_sorted(&(l->head), "b");
assert(status == true);
assert(l->head->next != NULL);
assert(l->head->next->value != NULL);
status = insert_sorted(&(l->head), "c");
assert(status == true);
assert(l->head->next->next != NULL);
assert(l->head->next->next->value != NULL);
printf("test_insert() passed.\n");
}
void test_delete()
{
printf("Start test_delete().\n");
bool status;
sorted_list *l = new_list();
status = delete_element(&(l->head), "x");
assert(status == false);
insert_sorted(&(l->head), "a");
insert_sorted(&(l->head), "b");
insert_sorted(&(l->head), "c");
status = delete_element(&(l->head), "b");
assert(status == true);
status = delete_element(&(l->head), "a");
assert(status == true);
status = delete_element(&(l->head), "c");
assert(status == true);
assert(l->head == NULL);
printf("test_delete() passed.\n");
}
void test_find()
{
printf("Start test_find().\n");
sorted_list *l = new_list();
insert_sorted(&(l->head), "b");
insert_sorted(&(l->head), "c");
insert_sorted(&(l->head), "d");
record *node = find(&(l->head), "a");
assert(node == NULL);
node = find(&(l->head), "e");
assert(node == NULL);
node = find(&(l->head), "b");
assert(node != NULL);
node = find(&(l->head), "c");
assert(node != NULL);
printf("test_find() passed.\n");
}
void test_free()
{
printf("Start test_free().\n");
sorted_list *l = new_list();
insert_sorted(&(l->head), "a");
insert_sorted(&(l->head), "b");
insert_sorted(&(l->head), "c");
free_list(&(l->head));
printf("test_free() passed.\n");
}
```
:::info
在test_free()中，不知道如何檢查記憶體是否已經被釋放。
根據 stackoverflow [這篇文章](https://stackoverflow.com/questions/8300853/how-to-check-if-a-pointer-is-freed-already-in-c)的描述，似乎沒有辦法檢查一個指標所指向記憶體是否被釋放。
:::
#### [Makefile](https://github.com/p61402/sorted_linked_list/blob/master/Makefile)
```make
CC = gcc
CFLAGS = -O0 -g -Wall -Werror
test: sorted_linked_list.h sorted_linked_list.c linked_list_test.c
$(CC) $(CFLAGS) -o test sorted_linked_list.c linked_list_test.c
./test
```
測試：
```bash
$ make test
Start testing.
Start test_insert().
test_insert() passed.
Start test_delete().
test_delete() passed.
Start test_find().
test_find() passed.
Start test_free().
test_free() passed.
All tests passed.
```
Sign in with Wallet
Connect another wallet