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

:::info
目的: 檢驗學員對遞迴呼叫和記憶體管理的認知
:::

==[作答表單](https://docs.google.com/forms/d/e/1FAIpQLSdmIWkQrL5ograFNkfudiDuXQ8Iyt-E4nmaWM6PE87czwGt9Q/viewform)==

---

### 測驗 `1`

LeetCode [1239. Maximum Length of a Concatenated String with Unique Characters](https://leetcode.com/problems/maximum-length-of-a-concatenated-string-with-unique-characters/) 題意：給定一個由 C 風格字串構成的陣列 `arr`，字串 `s` 是將 `arr` 某個字串連接所得的字串，若 `s` 中的每個字元都只出現一次，於是這會是個可能解。請提供所有可能解 `s` 中最大的長度。

範例 1
* 輸入
> arr = `["un", "iq", "ue"]`
* 輸出
> 4
* 解讀: 所有可能的字元串接組合是 `"", "un", "iq", "ue", "uniq", "ique"`，最大長度為 `4`

範例 2
* 輸入
> arr = `["cha", "r", "act", "ers"]`
* 輸出
> 6
* 解讀: 可能的解答有 "chaers" 和 "acters"，於是最大長度為 `6`

範例 3
* 輸入
> arr = `["abcdefghijklmnopqrstuvwxyz"]`
* 輸出: 26

提示：
* $1 \le arr.length \le 16$
* $1 \le arr[i].length \le 26$
* arr[i] 不算 null terminator (`\0`)，僅有小寫英文字母

本題用遞迴來思考：依序走訪每個單詞，對於目前的字串，若與之前連接的字串沒有相同的字串，那我們就可選擇將其串接或不串接。反之，若目前字串與之前串接的字串存在相同字元，那我們就無法串接。

針對 LeetCode [1239. Maximum Length of a Concatenated String with Unique Characters](https://leetcode.com/problems/maximum-length-of-a-concatenated-string-with-unique-characters/)，以下 C 程式是對應的解法：

#include <string.h>
#define MAX(x, y) ((x) > (y) ? (x) : (y))

static void dfs(int *arr, int arr_size, int i, int temp, int *maxm)
{
    if (i > arr_size - 1)
        return;
    int c = temp;
    if ((c & arr[i]) == 0) {
        ASSIGN;
        ACT2;
        dfs(arr, arr_size, i + 1, c, maxm);
    }
    dfs(arr, arr_size, i + 1, temp, maxm);
}

int maxLength(char **arr, int arr_size)
{
    int a[arr_size];
    memset(a, 0, arr_size * sizeof(int));
    for (int i = 0; i < arr_size; i++) {
        int k = 0;
        int len = strlen(arr[i]);
        for (int j = 0; j < len; j++)
            k |= 1 << (arr[i][j] - 'a');
        ACT1;
        a[i] = k;
    }
    int maxm = 0;
    dfs(a, arr_size, 0, 0, &maxm);
    return maxm;
}

請補完程式碼，使得符合預期。

==作答區==

ACT1 = ?
* `(a)` `if (k != len) continue`
* `(b)` `if (__builtin_popcount(k) != len) continue`
* `(c)` `if (k != len) break`
* `(d)` `if (__builtin_popcount(k) != len) break`

ACT2 = ?
* `(a)` `*maxm = MAX(c, *maxm)`
* `(b)` `*maxm = c`
* `(c)` `*maxm |= c`
* `(d)` `*maxm &= c`
* `(e)` `*maxm ^= c`
* `(f)` `*maxm = MAX(__builtin_popcount(c), *maxm)`

ASSIGN = ?
* `(a)` `c |= arr[i]`
* `(b)` `c &= arr[i]`
* `(c)` `c ^= arr[i]`
* `(d)` `c = arr[i]`

:::success
延伸問題:
1. 解釋上述程式碼運作原理
2. 改寫程式碼，避免使用遞迴並尋求效率更高的實作
:::

---

### 測驗 `2`

考慮以下透過 mmap 實作快速檔案複製的程式碼: `mmap-filecopy.c`

/* copy modified blocks of source file to destination file efficiently
 * using mmap.
 */

#include <assert.h>
#include <fcntl.h>
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/mman.h>
#include <sys/stat.h>
#include <sys/types.h>
#include <sysexits.h>
#include <unistd.h>

int main(int argc, char *argv[])
{
    if (argc != 3) {
        printf("Usage: %s <source> <destination>\n", argv[0]);
        return EX_USAGE;
    }

    const char *src_name = argv[1];
    const char *dst_name = argv[2];
    int src_fd, dst_fd;
    struct stat dst_stat = {0};
    off_t src_len, dst_len;

    src_fd = open(src_name, O_RDONLY);
    if (src_fd == -1) {
        perror(src_name);
        return EX_DATAERR;
    }

    dst_fd = open(dst_name, O_RDWR | O_CREAT,
                  S_IRUSR | S_IWUSR | S_IRGRP | S_IWGRP | S_IROTH | S_IWOTH);
    if (dst_fd == -1 || fstat(dst_fd, &dst_stat) != 0) {
        perror(dst_name);
        return EX_DATAERR;
    }

    src_len = lseek(src_fd, 0, SEEK_END);
    if (src_len < 0) {
        perror(src_name);
        return EX_DATAERR;
    }

    dst_len = lseek(dst_fd, 0, SEEK_END);
    if (dst_len < 0) {
        perror(dst_name);
        return EX_DATAERR;
    }

    if (dst_len > src_len) {
        printf("Destination file is larger (%zd) than input file (%zd)\n",
               dst_len, src_len);
        return EX_DATAERR;
    }

    const size_t page_size =
        dst_stat.st_blksize > 0 ? dst_stat.st_blksize : BUFSIZ;
    const size_t len = src_len;

    if (ftruncate(dst_fd, len) != 0) {
        perror(dst_name);
        return EX_DATAERR;
    }

    size_t read_count = 0;
    size_t write_count = 0;

    if (len > 0) {
        const uint8_t *src;
        uint8_t *dst;

        src = mmap(NULL, len, PROT_READ, MAP_SHARED, src_fd, 0);
        if (src == NULL ||
            posix_madvise((void *) src, len, POSIX_MADV_SEQUENTIAL) != 0) {
            perror(src_name);
            return EX_UNAVAILABLE;
        }

        dst = mmap(NULL, len, PROP, MAP_SHARED, dst_fd, 0);
        if (dst == NULL ||
            posix_madvise(dst, len, POSIX_MADV_SEQUENTIAL) != 0) {
            perror(dst_name);
            return EX_UNAVAILABLE;
        }

        for (size_t i = 0; i < len; i += page_size) {
            size_t block_size = (len - i) >= page_size ? page_size : (len - i);

            if (memcmp(src + i, dst + i, block_size)) {
                memcpy(dst + i, src + i, block_size);
                write_count += block_size;
            }

            read_count += block_size;
        }

        if (munmap((void *) src, len) != 0) {
            perror(src_name);
            return EX_UNAVAILABLE;
        }

        if (msync(dst, len, MS_SYNC) != 0 || munmap(dst, len) != 0) {
            perror(dst_name);
            return EX_UNAVAILABLE;
        }
    }

    if (close(src_fd) != 0) {
        perror(src_name);
        return EX_UNAVAILABLE;
    }

    if (close(dst_fd) != 0) {
        perror(dst_name);
        return EX_UNAVAILABLE;
    }

    printf("%zu bytes read\n", read_count);
    printf("%zu bytes written\n", write_count);
    return EXIT_SUCCESS;
}

編譯方式:

$ gcc -std=c11 -D_POSIX_C_SOURCE=200809L -o mmap-filecopy mmap-filecopy.c

假設原本已有檔名為 `in` 的檔案，且 `out` 不存在目前的路徑，可執行以下命令:

$ ./mmap-filecopy in out

這樣即可達成快速的檔案複製。

請補完程式碼，使得符合預期。

==作答區==

PROP = ?
* `(a)` `PROT_READ | PROT_WRITE`
* `(b)` `PROT_READ`

:::success
延伸問題:
1. 解釋上述程式碼運作原理，並指出其缺失
2. 探討 sendfile 和 splice 等系統系統在上述程式的應用
* 參見 [以 sendfile 和 splice 系統呼叫達到 Zero-Copy](https://hackmd.io/@sysprog/linux2020-zerocopy)
:::