# 2018q3 Homework3 (review)
contributed by < `happyincent` >
## Environment
```
$ $ cat <(echo "CPU: " `lscpu | grep "Model name" | cut -d':' -f2 | sed "s/ //"`) <(echo "OS: " `lsb_release -d | cut -f2`) <(echo "Kernel: " `uname -a | cut -d' ' -f1,3,14`) <(echo "gcc: " `gcc --version | head -n1`) <(echo "bash: " `bash --version | head -n1`)
CPU: Intel(R) Xeon(R) CPU E5520 @ 2.27GHz
OS: Ubuntu 16.04.5 LTS
Kernel: Linux 4.15.0-36-generic x86_64
gcc: gcc (Ubuntu 5.4.0-6ubuntu1~16.04.10) 5.4.0 20160609
bash: GNU bash, version 4.3.48(1)-release (x86_64-pc-linux-gnu)
```
## 第二周測驗 [`2`](https://hackmd.io/s/BJA6LjbK7#%E6%B8%AC%E9%A9%97-2)
解析
```c
void (*signal(int sig, void (*handler)(int))) (int);
```
#### 拆開來看
* `signal` 是一個 function (有兩個參數 `sig`, `handler`)
* handler 是 a pointer to a function (參數為 int)
* `signal` returns a pointer to a function (有一個 `int` 的參數) returns void
#### 使用 typedef
GNU extension 使用 typedef 定義 sighandler_t 這個 function pointer type
[manpage: signal(2)](http://man7.org/linux/man-pages/man2/signal.2.html)
```c
typedef void (*sighandler_t)(int);
sighandler_t signal(int signum, sighandler_t handler);
```
#### signal's return value
* 7.14 Signal handling ([c99](http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1256.pdf))
* SIG_DFL
* `default handling for that signal`
* SIG_ERR
* `If signal cannot be honored, a value of SIG_ERR is returned and a positive value is stored in errno.`
* SIG_IGN
* `the signal will be ignored`
* glibc - [Basic Signal Handling](https://www.gnu.org/software/libc/manual/html_node/Basic-Signal-Handling.html#Basic-Signal-Handling) 的 example
```c
// Note that if a given signal was previously set to be ignored,
// this code avoids altering that setting.
if (signal (SIGINT, termination_handler) == SIG_IGN)
signal (SIGINT, SIG_IGN);
```
* 小實驗
```c
#include <stdio.h>
#include <stdlib.h>
#include <signal.h>
#include <unistd.h>
typedef void (*sighandler_t)(int);
static void exit_with_handler_param(int param);
int main()
{
sighandler_t old = NULL;
sighandler_t stop = (sighandler_t)(exit_with_handler_param);
old = signal(SIGINT, SIG_IGN);
printf("Old Handler: SIG_DFL, addr = %p = %p = %p\n", old, SIG_DFL, (sighandler_t)0);
old = signal(SIGINT, SIG_DFL);
printf("Old Handler: SIG_IGN, addr = %p = %p = %p\n", old, SIG_IGN, (sighandler_t)1);
signal(SIGINT, stop);
old = signal(SIGINT, SIG_IGN);
printf("Old Handler: stop, addr = %p = %p\n", old, stop);
signal(SIGTSTP, old);
sleep(100);
}
static void exit_with_handler_param(int param)
{
exit(param);
}
```
```
$ $ gcc -g -Wall a.c && ./a.out
Old Handler: SIG_DFL, addr = (nil) = (nil) = (nil)
Old Handler: SIG_IGN, addr = 0x1 = 0x1 = 0x1
Old Handler: stop, addr = 0x4006d4 = 0x4006d4
^C^C^C^C^C^Z
[4]+ Stopped ./a.out
$ echo $?
20
```
* 從結果可以看到 SIGINT 預設的 handling 為 SIG_DFL
* SIGINT 做最後一次 signal 後 handling 為 SIG_IGN (old handler 為 stop)
* Ctrl-Z (SIGTSTP) 後以 echo $? 看到 ./a.out 的 exit status 為 20
```
$ cat /usr/include/x86_64-linux-gnu/bits/signum.h | grep SIGTSTP
#define SIGTSTP 20 /* Keyboard stop (POSIX). */
```
* GNU bash [Exit Status](https://www.gnu.org/software/bash/manual/html_node/Exit-Status.html)
* a fatal signal whose number is N, uses the value 128+N as the exit status.
```
$ python3 -c 'input()' || echo $?
^Z
[8]+ Stopped python3 -c 'input()'
148
```
---
## 第二周測驗 [`4`](https://hackmd.io/s/BJA6LjbK7#%E6%B8%AC%E9%A9%97-4)
考慮到以下程式碼:
```c
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 的內含值？
#### 題目問題
* main 傳入 ptrA (A 的位址) 給 func
* 進到 func 後 push **p** (value 為 ptrA) 到 func 的 stack
* 在 func 內更改 p 為 global int B 的位址
* 離開 func 後，func 的 stack 連帶其中的 p 被 pop 掉
* 因此 main 中的 ptrA、&A 一直都沒有被修改
* [Scope and Lifetime of Variables in C](https://blog.feabhas.com/2010/09/scope-and-lifetime-of-variables-in-c/)
* Function parameter 為 automatic storage duration, [6.9.1](http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1256.pdf)
#### 修改方法
1. 變更 main 裡頭 ptrA 的內含值
```c
void func(int **p) { *p = &B; }
func(&ptrA);
```
* `p` = function stack 中存放 main 中 `ptrA` 的位址
* `*p` = main 中 ptrA (一個可以被 dereference 成 integer 的 pointer) 的值
* 更改 *p 即是更改 main 中的 ptrA
* 執行 func 後
* `ptrA` 被改為 B 的位址 (!= &A)
* `*ptrA` 等於 B，而 A (*&A) 則沒被修改
2. 若**不需變更 main 裡頭 ptrA 的內含值**且不需保留 main 中 A 的值
```c
void func(int *p) { *p = B; }
func(ptrA);
```
* `p` = function stack 中存放 main 中 integer `A` 的位址
* `*p` = main 中的 `*ptrA` = main 中的 integer `A`
* 更改 *p 即是更改 main 中的 *ptrA、A
* 執行 func 後
* `*ptrA` 等於 A 等於 B (ptrA、&A 不變)
#### GitHub 使用 the pointer to the pointer 的 C 語言程式碼
* [scrcpy](https://github.com/Genymobile/scrcpy)
* https://github.com/topics/c 中找到 scrcpy 專案 (Display and control your Android device)
* [file_handler.h](https://github.com/Genymobile/scrcpy/blob/master/app/src/file_handler.h) (部分)
```c
#define REQUEST_QUEUE_SIZE 16
struct request_queue {
struct request *reqs[REQUEST_QUEUE_SIZE];
int tail;
int head;
};
```
* [file_handler.c](https://github.com/Genymobile/scrcpy/blob/master/app/src/file_handler.c) (部分)
```c
struct request {
file_handler_action_t action;
const char *file;
};
static SDL_bool request_queue_take(struct request_queue *queue, struct request **req) {
if (request_queue_is_empty(queue)) {
return SDL_FALSE;
}
// transfer ownership
*req = queue->reqs[queue->tail];
queue->tail = (queue->tail + 1) % REQUEST_QUEUE_SIZE;
return SDL_TRUE;
}
static int run_file_handler(void *data) {
...
struct request *req;
SDL_bool non_empty = request_queue_take(&file_handler->queue, &req);
SDL_assert(non_empty);
...
request_free(req);
...
}
```
* 在 file_handler.c 中的 function `request_queue_take` 發現 the pointer to the pointer
* 因為 `struct request_queue ` 中的 `struct request *reqs[REQUEST_QUEUE_SIZE];` 是在 function `request_new` 中使用 malloc 配置的，所以程式中是使用 **指標** 在操作 request
* `run_file_handler` 中將 **indeterminate** 的指標 `req` 的位址丟入 `request_queue_take`
* `request_queue_take` 修改 `req` 的位址為 request_queue 中 tail request 的位址
* 之後操作的 `req` 便是先前 malloc 過存放在 heap 中的記憶體位址
* 因此可以用來傳入 `request_free` 進行 `free`
* 因為有更動 `req` 位址的需求，所以 call function 時需以 the pointer to the pointer 的方式傳遞參數
* 不同於修改方法 2 的情境: ptrA 為 initialized，且沒有更動 ptrA 位址的需求
---
## 第二周測驗 [`8`](https://hackmd.io/s/BJA6LjbK7#%E6%B8%AC%E9%A9%97-8)
以下程式碼改寫自 Linux 核心原始程式碼，請對照註解 (預期功能)，指出實作上的問題，假設輸入 value 不會超過 32-bit。
```c
/*
* Convert a signed n-bit integer to signed 32-bit integer.
* Common cases are done through the compiler,
* the screwed things has to be done by hand.
*/
static int32_t snto32(uint32_t value, unsigned n) {
switch (n) {
case 8: return ((int8_t) value);
case 16: return ((int16_t) value);
case 32: return ((int32_t) value);
}
return value & (1 << (n - 1)) ? value | (-1 << n) : value;
}
```
#### 程式碼解讀
解讀
* Common cases
* Cast operators (6.5.4)
* Exact-width integer types (7.18.1.1)
* The typedef name `intN_t` designates a signed integer type with width N, no padding bits, and a two’s complement representation.
* These types are optional. However, if an implementation provides integer types with widths of 8, 16, 32, or 64 bits, it shall define the corresponding typedef names.
* Other cases
* `value & (1 << (n - 1))` : 找出第 n 個 bit 為 1 or 0 (負 or 正)
* 第 n 個 bit 為 1 時 : `value | (-1 << n)`
* 將第 n+1 ~ 32 bit 設為 1
* e.g., n = 4, 0xe = -2 (2's complement), `0x0000000e -> 0xfffffffe`
* 第 n 個 bit 為 0 時 : `value`
* 直接 return 傳入的 value
#### 問題
:::info
傳入 `uint32_t value` 並非 `n-bit` 且 第 n 個 bit 為 0 時，`snto32` 的 return value 不會是 n-bit
:::
* e.g., n = 4, `0x000000f7 -> 0x000000f7` (並非預期的 `0x00000007`)
* 將 return 的部分改為 `return check ? value | (~0U << n) :` **`value ^ (value & (~0U << n));`** 即可處理這個問題
* 然而在 `git log -p ./drivers/hid/hid-core.c` 找到有關 snto32 的最新改動為
* commit message: don't use negative operands when shift [[08585e4](https://github.com/torvalds/linux/commit/08585e43d22802666a466af1ca5795085e74d60d)]
```c
- return value & (1 << (n - 1)) ? value | (-1 << n) : value;
+ return value & (1 << (n - 1)) ? value | (~0U << n) : value;
```
* 在同個專案中[搜尋 snto32](https://github.com/torvalds/linux/search?q=snto32&unscoped_q=snto32)，分別在三個檔案出現: `hid-core.c`, `hid-logitech-hidpp.c`, `hid.h`、四種使用前先處理的方式: `hid_field_extract` 或 `s32ton` 或 `!(value & 0xfffffff0)` 或 `直接給值`
* 只有在 `hid-logitech-hidpp.c` 出現的 `hid_snto32(data[6], 8);` 時是直接給值
* `/* Logitech M560 mouse report - data[6] = whee */`
* 我猜測 function snto32 相信使用者會先確認: n-bit value 在第 n bit 為 0 的情況下第 n+1 ~ 32 bit 都會是 0，因此不需做額外的處理
#### undefined behavior
* 在 C99 的 6.5.7 中提到: `If the value of the right operand is` **`negative`** `or is greater than or equal to the width of the promoted left operand, the behavior is undefined.`
* 在 snto32 function 中若 `n=0`，`value & (1 << (n - 1))` 就屬於這個情境
* 在 [ISO/IEC 9899:201x](http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1548.pdf) 的 6.5.7 中增加了:
```
The result of E1 << E2 is E1 left-shifted E2 bit positions; ... If E1 has a signed
type and nonnegative value, ...; otherwise, the behavior is undefined.
```
* 在題目中的 snto32 function 中 `-1 << n` 就屬於這個情境
---
## 第三周測驗 [`2`](https://hackmd.io/s/BkyQskjK7#%E6%B8%AC%E9%A9%97-2)
考慮以下程式碼，在 little-endian 硬體上，會返回 `1`，反之，在 big-endian 硬體上會返回 `0`:
```c
int main() {
union { int a; char b;
} c = { .a = 1 };
return c.b == 1;
}
```
#### union
* member 間共用記憶體，大小為最大 member type 的 size
* 6.7.2.1
* A union is a type consisting of a sequence of members whose storage overlap
* The size of a union is sufficient to contain the largest of its members
* There may be unnamed padding at the end of a structure or union
```c
union {
unsigned int a : 2;
int b : 2;
} d = { .a = 3 };
printf("%x\n", d.a); // 3
printf("%x\n", d.b); // ffffffff (-1)
printf("%lu\n", sizeof(d)); // 4 bytes
```
```
(gdb) x/4xb &d
0x7ffffffee300: 0x03 0x00 0x00 0x00
```
#### 運作原理
* 執行環境為 Intel CPU (little-endian)
* 透過 [`<netinet/in.h>`](https://github.com/bminor/glibc/blob/master/inet/netinet/in.h) 中的 `htonl` 可以將 host byte order 轉為 network byte order (big-endian)
* 底層使用 [`<bits/byteswap.h>`](https://github.com/bminor/glibc/blob/master/bits/byteswap.h) 的 `__builtin_bswap32` 或 `__bswap_constant_32`
```c
#define __bswap_constant_32(x) \
((((x) & 0xff000000u) >> 24) | (((x) & 0x00ff0000u) >> 8) \
| (((x) & 0x0000ff00u) << 8) | (((x) & 0x000000ffu) << 24))
```
* [glibc doc](https://www.gnu.org/software/libc/manual/html_node/Byte-Order.html), [Beej's Guide to Network Programming](https://beej-zhtw-gitbook.netdpi.net/htons,_htonl,_ntohs,_ntohl.html)
* 程式碼
```c
#include <stdio.h>
#include <netinet/in.h>
int main()
{
union { int a; char b;
} c = { .a = 1 }, c1;
c1.a = htonl( (uint32_t)c.b );
printf("little-endian: return %d\n", c.b); // 1
printf("big-endian: return %d\n", c1.b); // 0
}
```
```
gdb-peda$ x/4xb &c
0x7ffffffee330: 0x01 0x00 0x00 0x00
# Address: 低 <---> 高
gdb-peda$ x/4xb &c1
0x7ffffffee340: 0x00 0x00 0x00 0x01
```
#### 類似的程式碼
* 使用 [Predefined Macros](https://gcc.gnu.org/onlinedocs/cpp/Common-Predefined-Macros.html) : `#if __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__`
```c
int main()
{
return __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__;
}
```
* Test with godbolt.org
* x86-64 (ARM) gcc >= 4.6.4, x86-64 clang >= 3.2
* 使用 htons (htonl)
```c
#include <netinet/in.h>
// #include <winsock2.h>
#define IS_BIG_ENDIAN (1 == htons(1))
int main()
{
return !IS_BIG_ENDIAN;
}
```
* Tested
* godbolt.org - x86-64 gcc >= 4.1.2
* Windows 10 - gcc 5.1.0 mingw32
* one-line endianness detection [[source](http://esr.ibiblio.org/?p=5095)]
```c
#include <stdint.h>
#define IS_BIG_ENDIAN (*(uint16_t *)"\0\xff" < 0x100)
```
* need <stdint.h> (C99)
* 不相容 `#if` preprocessor macro
* 原理
```c
#include <stdio.h>
#include <stdint.h>
#include <netinet/in.h>
int main()
{
char *arr = "\0\xff";
uint8_t *p8 = (uint8_t *)arr;
uint16_t *p16 = (uint16_t *)arr;
printf("%02x %02x\n", *p8, *(p8+1) ); // 00 ff
printf("%04x\n", *p16 ); // ff00
printf("%s\n", *p16 < 0x100 ? "true" : "false" ); // false
printf("%04x\n", htons(*p16) ); // 00ff
printf("%s\n", htons(*p16) < 0x100 ? "true" : "false"); // true
}
```
---
## 第三周測驗 [`4`](https://hackmd.io/s/BkyQskjK7#%E6%B8%AC%E9%A9%97-4)
* 函式 insert_sorted 的作用是在 r 所指向已依據數值排序的 linked list 中，安插給定的字串，考慮到 string literal 的生命週期，應該在新建立的節點中，複製給定的字串。
* 新增刪除和搜尋節點的程式，附上完整的測試計畫
#### Makefile
```Makefile
.PHONY: all test clean
CC = gcc
CFLAGS = -O0 -g -Wall -Werror -std=gnu11
all: mytest
myrec.o: myrec.c myrec.h
mytest: mytest.c myrec.o
test: mytest
valgrind --leak-check=full ./mytest
clean:
rm -f *.o mytest
```
#### myrec.h
```c
#ifndef _MYREC_H
#define _MYREC_H
#include <stdbool.h>
typedef struct rec {
char *value;
struct rec *next;
} record;
void insert_sorted(record **r, const char *value);
void remove_rec(record **r);
void print_rec(record *r);
bool search_rec(record **r, const char *str);
#endif
```
#### myrec.c
```c
#include "myrec.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
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;
}
void remove_rec(record **r)
{
record *delrec = *r;
if (delrec != NULL) {
*r = delrec->next;
free(delrec->value);
free(delrec);
}
}
void print_rec(record *r)
{
printf("[ ");
for (; r != NULL; r = r->next)
printf("%s ", r->value);
printf("]\n");
}
bool search_rec(record **r, const char *str)
{
while (*r && strcmp(str, (*r)->value) != 0)
r = &((*r)->next);
return (*r == NULL) ? false : true;
}
```
#### mytest.c
```c
#include "myrec.h"
#include <stdio.h>
int main()
{
setbuf(stdout, NULL);
record *rec = NULL;
char *str[3] = { "bb", "ccc", "a" };
for (int i=0; i<3; ++i) {
insert_sorted(&rec, str[i]);
printf("--------- insert %3s: ", str[i]);
print_rec(rec);
}
char *str2[4] = { str[0], "www", str[2], "ddl" };
for (int i=0; i<4; ++i) {
printf("--------- search %3s: ", str2[i]);
printf("%s\n", search_rec(&rec, str2[i]) ? "exist" : "not exist");
}
remove_rec(&rec);
printf("--------- pop one: ");
print_rec(rec);
while (rec != NULL)
remove_rec(&rec);
printf("--------- pop all: ");
print_rec(rec);
}
```
#### 執行結果
```
$ make clean test
rm -f *.o mytest
gcc -O0 -g -Wall -Werror -std=gnu11 -c -o myrec.o myrec.c
gcc -O0 -g -Wall -Werror -std=gnu11 mytest.c myrec.o -o mytest
valgrind --leak-check=full ./mytest
==28162== Memcheck, a memory error detector
==28162== Copyright (C) 2002-2015, and GNU GPL'd, by Julian Seward et al.
==28162== Using Valgrind-3.11.0 and LibVEX; rerun with -h for copyright info
==28162== Command: ./mytest
==28162==
--------- insert bb: [ bb ]
--------- insert ccc: [ bb ccc ]
--------- insert a: [ a bb ccc ]
--------- search bb: exist
--------- search www: not exist
--------- search a: exist
--------- search ddl: not exist
--------- pop one: [ bb ccc ]
--------- pop all: [ ]
==28162==
==28162== HEAP SUMMARY:
==28162== in use at exit: 0 bytes in 0 blocks
==28162== total heap usage: 6 allocs, 6 frees, 57 bytes allocated
==28162==
==28162== All heap blocks were freed -- no leaks are possible
==28162==
==28162== For counts of detected and suppressed errors, rerun with: -v
==28162== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
```
Sign in with Wallet
Connect another wallet