# [2022q1](http://wiki.csie.ncku.edu.tw/sysprog/schedule) 第 13 週測驗題
###### tags: `linux2022`

:::info
目的: 檢驗學員對 **[並行和多執行緒程式設計](https://hackmd.io/@sysprog/concurrency)** 和 **[Linux 核心記憶體管理](https://hackmd.io/@sysprog/linux-memory)** 的認知
:::

作答表單:
* ==[測驗 `1`, `2`](https://docs.google.com/forms/d/e/1FAIpQLSdIRW9ajRrJEoXToDyZSMiOuxUmYHvG_Z4AYgbk3taWkKPcsw/viewform)== (Linux 核心設計)
* ==[測驗 `3`](https://docs.google.com/forms/d/e/1FAIpQLSdeAgdyNfMwtPt0aITs3YoJ94IfKjqw1LtHbBWxn1G7rpfbfQ/viewform)== (Linux 核心實作)

### 測驗 `1`

考慮一個運用 [Linux 核心記憶體管理](https://hackmd.io/@sysprog/linux-memory) 和 [CS:APP 第 9 章](https://hackmd.io/@sysprog/CSAPP-ch9) 提到的 [mmap](https://man7.org/linux/man-pages/man2/mmap.2.html) 系統呼叫，來實作類似 C++ [std::vector](https://www.cplusplus.com/reference/vector/vector/) 的機制，並自動管理記憶體，程式碼列表如下:

#include <asm-generic/param.h>
#define PAGESIZE EXEC_PAGESIZE

#include <err.h>
#include <errno.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/mman.h>

/* how many directories per (preallocated) page
 * -> (PAGESIZE/16) = 256 for 4KiB pages.
 * each path can be in the medium (PAGESIZE - 4 * 256 - 20) / 256 Bytes.
 * The notify dirlist ist dynamically grown.
 */
#define N_VM_ELEMENTS (PAGESIZE / 16)

/* the macro OPTFENCE(...) can be invoked with any parameter.
 * The parameters will get calculated, even if gcc doesn't recognize
 * the use of the parameters, e.g. cause they are needed for an inlined asm
 * syscall.
 *
 * The macro translates to an asm jmp and a function call to the function
 * opt_fence, which is defined with the attribute "noipa" -
 * (the compiler "forgets" the function body, so gcc is forced to generate
 * all arguments for the function.)
 */
void __attribute__((noipa, cold, naked)) opt_fence(void *p, ...) {}
#define _optjmp(a, b) asm(a "OPTFENCE_" #b)
#define _optlabel(a) asm("OPTFENCE_" #a ":")
#define __optfence(a, ...)  \
    _optjmp("jmp ", a);     \
    opt_fence(__VA_ARGS__); \
    _optlabel(a)
#define OPTFENCE(...) __optfence(__COUNTER__, __VA_ARGS__)

/* Avoids with uint32 the penalty of unaligned memory access */
typedef unsigned int p_rel;

static inline char *_getaddr(p_rel *i, p_rel addr)
{
    return ((char *) i + addr);
}
/* translate a relative pointer to an absolute address */
#define getaddr(addr) _getaddr(&addr, addr)

static inline p_rel _setaddr(p_rel *i, char *p)
{
    return (*i = (p - (char *) i));
}
/* store the absolute pointer as relative address in relative_p */
#define setaddr(relative_p, pointer) _setaddr(&relative_p, pointer)

typedef struct __vm {
    p_rel array[N_VM_ELEMENTS];
    struct __vm *next;
    int max, subtract;
    /* dynamic string section starts here */
    char str[0];
} vm_t;

vm_t *vm_new()
{
    vm_t *node = mmap(0, PAGESIZE, PROT_READ | PROT_WRITE,
                      MAP_ANONYMOUS | MAP_PRIVATE, -1, 0);
    if (node == MAP_FAILED)
        err(ENOMEM, "Failed to map memory");

    node->max = N_VM_ELEMENTS;
    node->next = NULL; /* for clarity */
    setaddr(node->array[0], node->str);

    /* prevent compilers from optimizing assignments out */
    OPTFENCE(node);
    return node;
}

const char *vm_get(int num, vm_t *nod)
{
    num -= nod->subtract;
    if (num < 0)
        return NULL;

    while (num >= (nod->max - 1)) { /* otherwise, addr > map */
        num -= nod->max - 1;
        if (!nod->next)
            return 0;
        nod = nod->next;
    }

    return getaddr(nod->array[num]);
}

void vm_destroy(vm_t *nod, void *(callback)(const char *e))
{
    const char *ee;
    for (int a = nod->subtract; (ee = vm_get(a, nod)); a++)
        callback(ee);

    do {
        char *tmp = (char *) nod;
        nod = nod->next;
        munmap(tmp, PAGESIZE);
    } while (nod);
}

static vm_t *vm_extend_map(vm_t *nod)
{
    nod->next = mmap(0, PAGESIZE, PROT_READ | PROT_WRITE,
                     MAP_ANONYMOUS | MAP_PRIVATE, -1, 0);
    nod = nod->next;
    nod->max = N_VM_ELEMENTS;
    setaddr(nod->array[0], nod->str);
    return nod;
}

/* append a path. num MUST be sequential */
void vm_add(int num, const char *path, vm_t *nod)
{
    if (!nod->subtract)
        nod->subtract = num;
    num -= nod->subtract;

    while (num >= (nod->max - 1)) {
        num -= MMMM;
        if (!nod->next) {
            nod = vm_extend_map(nod);
            break;
        }
        nod = nod->next;
    }

    if (nod->array[num + 1])
        err(0, "Num %d already used!\n", num);

    if ((int) ((nod->array[num] + (sizeof(p_rel) * (N_VM_ELEMENTS - num)) +
                strlen(path))) >= PAGESIZE) {
        nod->max = num + 1; /* addr > map */
        NNNN;
        nod = vm_extend_map(nod);
    }

    char *p = stpcpy(getaddr(nod->array[num]), path);
    p++;
    setaddr(nod->array[num + 1], p);
}

static void *dealloc(const char *e)
{
    /* FIXME: implement real deallocation */
    return NULL;
}

int main(int argc, char **argv)
{
    vm_t *vm = vm_new();

    vm_add(1, "First element\n", vm);
    vm_add(2, "Second element\n", vm);

    char buf[64];
    strcpy(buf, "Element    #  \n");

    for (int i = 3; i < 10; i++) {
        buf[12] = i + '0';
        vm_add(i, buf, vm);
    }

    printf("fetch, 5: %s", vm_get(5, vm));

    for (int i = 10; i < 400; i++) {
        sprintf(buf, "Element (extending the medium size): %d\n", i);
        vm_add(i, buf, vm);
    }

    printf("fetch: %s", vm_get(15, vm));
    printf("fetch: %s", vm_get(155, vm));
    printf("fetch: %s", vm_get(355, vm));
    printf("fetch: %s", vm_get(100, vm));
    printf("fetch: %s", vm_get(224, vm));

    vm_destroy(vm, dealloc);
    return (0);
}

在 GNU/Linux 參考執行輸出:

fetch, 5: Element    #5 
fetch: Element (extending the medium size): 15
fetch: Element (extending the medium size): 155
fetch: Element (extending the medium size): 355
fetch: Element (extending the medium size): 100
fetch: Element (extending the medium size): 224

請補完程式碼，使其執行符合預期。作答規範:
* `MMMM` 和 `NNNN` 均為 C 表示式，以符合 C99 規範撰寫最精簡的形式

:::success
延伸問題:
1. 解釋上述程式碼運作原理，指出其缺失並改進
2. 擴充上述程式碼為通用的 malloc 和 free 實作
3. 參照 [mmap-benchmark](https://github.com/exabytes18/mmap-benchmark)，佐以 [madvise](https://man7.org/linux/man-pages/man2/madvise.2.html) 系統呼叫，調整特定樣式 (pattern) 的記憶體存取，從而達到更高效的表現
> 參照 [microsoft/mimalloc](https://github.com/microsoft/mimalloc)
:::

---

### 測驗 `2`

考慮使用 mmap 和 [memfd](https://man7.org/linux/man-pages/man2/memfd_create.2.html) 系統呼叫的 circular buffer 實作: [cbuf](https://gist.github.com/jserv/d9270b533af07461fac5b1e04b9f2f98) (部分程式碼遮蔽)。參考執行結果:

Test #0: PASSED (57698)
Test #1: PASSED (64222)
Test #2: PASSED (59112)
...
Test #98: PASSED (59448)
Test #99: PASSED (55487)
Average for 100 tests: 57340

請補完程式碼，使其執行符合預期。作答規範:
* `CCCC` 為 C 表示式，以符合 C99 規範撰寫最精簡的形式

---

### 測驗 `3`

在 [你所不知道的 C 語言：連結器和執行檔資訊](https://hackmd.io/@sysprog/c-linker-loader) 提過 ELF 執行檔格式，更多資訊可見 [Executable and Linkable Format](https://en.wikipedia.org/wiki/Executable_and_Linkable_Format)，以 64 位元 ELF 來說，開頭的幾個位元組的意義:
| offset | size | Purpose |
|:------:|:----:|:-------:|
| 0x00 | 4 | 0x7F followed by ELF(`45` `4c` `46`) in ASCII; these four bytes constitute the magic number. |
| 0x04 | 1 | This byte is set to either 1 or 2 to signify 32- or 64-bit format, respectively. |
| 0x05 | 1 | This byte is set to either 1 or 2 to signify little or big endianness, respectively. This affects interpretation of multi-byte fields starting with offset `0x10`. |
| x06 | 1 | Set to 1 for the original and current version of ELF. |
| ... | ... | ...待續... |

以下是相關的函式及系統呼叫:
* [memfd_create](http://man7.org/linux/man-pages/man2/memfd_create.2.html): 詳見 [解析 Linux 共享記憶體機制](https://hackmd.io/@sysprog/linux-shared-memory) 一文
* [memmem](http://man7.org/linux/man-pages/man3/memmem.3.html): GNU extension，在給定的記憶體範圍找到「非」C-style 字串 (仍為連續記憶體)
* [fexecve](http://man7.org/linux/man-pages/man3/fexecve.3.html): 類似 execve 系統呼叫，但由給定的 file descriptor 載入程式並執行

給定要載入的程式碼: (檔名 `hello.c`)

#include <stdio.h>
int main() { return puts("Hello!"); }

以下程式碼可載入並動態修改程式行為:

#define _GNU_SOURCE /* See feature_test_macros(7) */
#include <fcntl.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/mman.h>
#include <sys/stat.h>
#include <unistd.h>

static void file_execution(size_t size, char *elf, char **f_file, char **envp)                       
{
    char e_elf[256];
    int des = memfd_create("targ_file", FD_CLOEXEC);
    write(des, elf, size);
    sprintf(e_elf, "/proc/self/fd/%u", des);
    execve(e_elf, f_file, envp);
}

int main(int argc, char **argv, char **envp)
{
    if (argc != 2) {
        fprintf(stderr, "Usage: %s <elf_file>\n", argv[0]);
        exit(EXIT_FAILURE);
    }
    int des = open(argv[1], O_RDONLY);
    struct stat l_stat;
    fstat(des, &l_stat);
    char *elf = malloc(l_stat.st_size);
    read(des, elf, l_stat.st_size);
    char *str = memmem(elf, l_stat.st_size, "Hello!", 6);
    str[0] = 'Y', str[5] = 'w';
    file_execution(l_stat.st_size, elf, &argv[1], envp);
    return EXIT_SUCCESS;
}

編譯和執行:

gcc -Wall -o execelf execelf.c
./execelf hello

預期會得到 "Yellow" 輸出

接下來的程式碼嘗試在既有的 ELF 檔案內嵌另一個 ELF 檔案 (可預先加密)，目的是隱匿特定的程式，避免被掃毒程式或防火牆偵測出來，或將高價值的程式嵌入到文件、圖片，甚至是影音檔案中，透過特定的載入器自檔案提取出執行檔並執行，這手法在 [Digital rights management (DRM)](https://en.wikipedia.org/wiki/Digital_rights_management) 和 [Digital watermarking](https://en.wikipedia.org/wiki/Digital_watermarking) 領域不算少見。

假設即將被嵌入的程式碼名為 `payload.c`:

#include <stdio.h>                          
int main() { puts("Hello world!"); return 0; }

編譯並移去除錯用的符號:

$ gcc -Os payload.c -o payload
$ strip -s payload

接著我們要開發得以載入 ELF 的程式，在這之前，

假定程式載入器檔名為 `loader.c`，內容如下:

/* A program that executes a second (embedded) ELF */

#define _GNU_SOURCE
#include <errno.h>
#include <fcntl.h>
#include <sys/mman.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/stat.h>
#include <unistd.h>

/* ELF format
 * https://en.wikipedia.org/wiki/Executable_and_Linkable_Format
 */
static bool valid_elf(char *ptr)
{
    return (ptr[4] == 1 || ptr[4] == 2) /* offset 0x4: 32/64-bit format */ &&
           (ptr[5] == 1 || ptr[5] == 2) /* offset 0x5: endianness */ &&
           (ptr[6] == 1); /* offset 0x6: current version */
}

int main(int argc, char *argv[], char **envp)
{
    int pid = getpid();
    int ret = 0;

    char proc_path[32];
    sprintf(proc_path, "/proc/%d/exe", pid);
    int filedesc = open(proc_path, O_RDONLY);
    if (filedesc < 0) {
        printf("Invalid file descriptor for /proc: %d\n", filedesc);
        return -1;
    }

    /* Find the size of this executable */
    struct stat st;
    stat(proc_path, &st);
    size_t size = st.st_size;

    char *entirefile = malloc(size);
    if (!entirefile) {
        printf("Insufficient memory.\n");
        return -2;
    }

    read(filedesc, entirefile, size);
    close(filedesc);

    /* find the second ELF header, which 52 or 64 bytes long for 32-bit and
     * 64-bit binaries respectively.
     */
    const char elf_magic[] = {0x7F, 'E', 'L', 'F'};
    char *newelf = memmem(entirefile + 52, size - 52, elf_magic, 4);
    if (newelf && !valid_elf(newelf)) /* forcely find again for real ELF */
        newelf = memmem(newelf + 6, size - (intptr_t) newelf - 6, elf_magic, 4);
    if (!newelf || !valid_elf(newelf)) {
        printf("No second ELF header found.\n");
        ret = -3;
        goto cleanup;
    }

    int newsize = AAA;
    int memfd = memfd_create("hidden", 0);
    if (memfd < 0) {
        printf("Invalid memfd.\n");
        ret = -4;
        goto cleanup;
    }

    /* Write ELF to temporary memory file */
    write(memfd, newelf, newsize);

    // Deploy the payload as a different process
    fork();
    if (BBB) {
        ret = fexecve(memfd, argv, envp); /* Execute the in-memory ELF */
        /* The above will only return if there is an error. */
        printf("Fail to execute payload. ret=%d (%s)\n", ret, strerror(errno));
    }

cleanup:
    free(entirefile);
    return ret;
}

編譯、嵌入上述 `payload` 執行檔，然後再執行: (你沒看錯，真的用 `cat` 命令)

$ gcc -Wall loader.c -o loader
$ cat payload >> loader
$ ./loader

在 x86_64 GNU/Linux (核心版本: 5.4) 預期輸出為:

Hello world!

> 注意：只有一行 "Hello world!" 字串

請補完程式碼，只要考慮 x86_64 硬體架構即可。

==作答區== (注意: 複選題，儘量選取有效的答案)

AAA = ?
* `(a)` `newelf - entirefile`
* `(b)` `size - newelf`
* `(c)` `entirefile - newelf`
* `(d)` `size - newelf - entirefile`
* `(e)` `size - newelf + entirefile`
* `(f)` `newelf - entirefile + size`
* `(g)` `entirefile - newelf - size`

BBB = ?
* `(a)` `getpid()`
* `(b)` `getpid() != pid`
* `(c)` `getpid() == pid`
* `(d)` `0`
* `(e)` `1`

:::success
延伸問題:
1. 解釋上述程式碼運作原理，指出其中不足處並改進;
2. 參照 [Embedding binary data in executables](https://csl.name/post/embedding-binary-data/) 和 [incbin](https://github.com/graphitemaster/incbin)，將 payload 加密並嵌入到給定的 C 程式中，允許在執行時期解密再載入 payload 並執行
:::