2020q3 Homework13 (quiz 13)

contributed by < JimmyLiu0530 >

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

測驗1: LeetCode 1239. 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 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)，首先我們能了解 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)

• 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