# 2020q3 Homework13 (quiz 13)

contributed by < `JimmyLiu0530` >

###### tags: `進階電腦系統理論與實作`

## 測驗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 \leq arr.length \leq 16$
- $1 \leq arr[i].length \leq 16$
- arr[i] 不算 null terminator (`\0`)，僅有小寫英文字母

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

以下 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;
}

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

### 程式說明
首先，我們看 `maxLength` 這個函式。一開始宣告一個大小為 `arr_size` 的整數陣列 `a`，而這個 `a` 用來表示每個字串所使用到的英文字母的位元表示，簡單來說就是狀態壓縮。比如說假設第 `i` 個字串為 `"abc"`，則 `a[i]=7(=00...00111)`。

接下來，line 21 的 `for` 迴圈會根據每個字串 `arr[i]` 去更新 `a`。我們設想一種情況:
假設某個字串中存在重複的字母，則此字串沒必要被選來與其他字串串接，因為不管怎麼串接，一定會有重複的字母出現，因此，`ACT1` 就在排除掉這種情況，所以 `ACT1 為 if (__builtin_popcount(k) != len) continue`。

建立完 `a` 後，呼叫 `dfs`，透過遞迴走訪每個字串，來決定不重複字母的最長字串長度。
想法如下:
就目前的字串 `arr[i]` 而言，考慮與之前串接的字串 `c` 是否存在相同字母，
- 如果沒有，即 (c & arr[i] == 0)，則可以選擇串接或是不串接，
- 選擇串接的話，需要更新 `c`，並且檢查串接後是否加長字串，因此 `ASSIGN 為 c |= arr[i]`，`ACT2 為 *maxm = MAX(__builtin_popcount(c), *maxm)`
- 選擇不串接的話，就直接忽略目前的字串，繼續走訪下一個字串。
- 相反地，如果有相同字母，則就如同上面選擇不串接的情況，直接忽略此字串，繼續走訪下一個字串。

最終，走訪完所有字串後，就會得到最長字串長度 `maxm`。

### 延伸問題
#### 1. 改寫程式碼，避免使用遞迴並尋求效率更高的實作

--------------------------------------------------

## 測驗2: mmap 實作快速檔案複製
考慮以下透過 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

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

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

### 程式說明
根據 [Linux manual page -- mmap(2)](https://man7.org/linux/man-pages/man2/mmap.2.html)，首先我們能了解 mmap 的作用為在呼叫者的虛擬記憶體上建立一個檔案的映射，通過對這段記憶體的讀取和修改，實現對檔案的讀取和修改。

void *mmap(void *addr, size_t length, int prot, int flags,
                  int fd, off_t offset) // prototype
                  
dst = mmap(NULL, len, PROP, MAP_SHARED, dst_fd, 0); // example

mmap 有上面這些參數，我們將一一的解釋其用途:
- `addr`: "希望"映射記憶體的初始位置，實際的初始位置為此呼叫的回傳值，不一定等於 `addr`。
- 若為 `NULL`，則由 Linux 核心決定其初始位置
- `length`: 映射空間的大小
- `prot`: 描述想要對該映射空間作什麼記憶體保護措施，但注意不能與檔案的開啟模式有衝突 (例如檔案為唯讀 (raed-only)，但卻有 `PROT_WRITE` flag)
- `PROT_EXEC`: 可能會被執行
- `PROT_READ`: 可能會被讀取
- `PROT_WRITE`: 可能會被寫入
- `PROT_NONE`: 可能不會被存取

因此，就可以回答 `PROP = PROT_READ | PROT_WRITE`。

- `flags`: 決定對該映射空間的更新是否可讓其他一樣映射到此空間的行程 (process) 所看見 (映射空間的共享性)
- `MAP_SHARED`: 允許其他映射到此空間的行程共享，並且對映射空間的寫入會複製回文件。
- `MAP_PRIVAT`: 不允許其他映射到此空間的行程共享，對映射空間的寫入會產生一個映射的複製 (copy-on-write)，對此空間所做的修改不會寫回原文件。
- 還有很多 `flags` 可以使用，請參考 [Linux manual page -- mmap(2)](https://man7.org/linux/man-pages/man2/mmap.2.html)

- `fd`: 由 `open` 返回的文件描述符 (file descriptor)，代表要映射到核心中的文件。
- `offset`: 映射空間初始位置的偏移量，通常為0。此外，`offset` 必須是分頁大小的整數倍

跟 mmap 搭配的 `munmap`，用來關閉記憶體映射

int munmap(void *addr, size_t length); //prototype

if (munmap((void *) src, len) != 0) {
...
} //example

munmap 刪除特定記憶體區段的映射，使原先合法參照此記憶體區段變為不合法。當行程終止時，該記憶體區段也會自動刪除。然而，關閉文件描述符並不會刪除映射。

如果成功，回傳 `0`；否則，回傳 `-1`，並設定 `errno` 指出錯誤的原因。

最後，mmap 帶來什麼好處呢?
- 加速檔案存取
- 一般的I/O機制通常需要將資料先到緩區中。記憶體對映免去了中間這一層
- 可把檔案當成記憶體來用，直接使用指標來操作 (e.g. line 95-96)
- 可執行檔可對映到記憶體空間中，使程式動態載入
- Linux Dynamic Loading便是如此實作出來的

### 延伸問題
#### 1. 指出上述程式碼的缺失

#### 2. 探討 sendfile 和 splice 等系統系統在上述程式的應用
- > 參見 [以 sendfile 和 splice 系統呼叫達到 Zero-Copy](https://hackmd.io/@sysprog/linux2020-zerocopy)