Try   HackMD

2021q1 第 5 週測驗題

tags: linux2021

目的: 檢驗學員對 bitwise operation, bit-field, C 語言：記憶體管理, small string/buffer optimization, coroutine 的認知

作答表單

測驗 1

考慮到一個針對空間處理最佳化的 vector 實作

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

支援以下操作:

  • vec_push_back : 新增元素至 vector 的尾端，必要時會進行記憶體配置;
  • vec_pop_back() : 刪除 vector 最尾端的元素;

每個 vector 都有兩個重要的屬性:

  • 容量 (capacity) : 是這個 vector 擁有的空間。
  • 長度 (size): 實際儲存了元素的空間大小。capacity 永遠不小於 size

使用示範:

int main()
{
    v(float, 3, vec1);
    v(int, 2, vec2, 13, 42);

    printf("pos(vec2,0)=%d, pos(vec2,1)=%d\n", vec_pos(vec2, 0),
           vec_pos(vec2, 1));
    vec_push_back(vec2, 88);
    vec_reserve(vec2, 100);
    printf("capacity(vec1)=%zu, capacity(vec2)=%zu\n", vec_capacity(vec1),
           vec_capacity(vec2));
    printf("pos(vec2,2)=%d\n", vec_pos(vec2, 2));

#define display(v)                               \
    do {                                         \
        for (size_t i = 0; i < vec_size(v); i++) \
            printf("%.2f ", vec_pos(v, i));      \
        puts(v.on_heap ? "heap" : "stack");      \
    } while (0)

    display(vec1);
    vec_push_back(vec1, 0.0);
    display(vec1);
    vec_push_back(vec1, 1.1);
    display(vec1);
    vec_push_back(vec1, 2.2);
    display(vec1);
    vec_push_back(vec1, 3.3);
    display(vec1);
    vec_push_back(vec1, 4.4);
    display(vec1);
    vec_push_back(vec1, 5.5);
    display(vec1);
    vec_pop_back(vec1);
    display(vec1);
    vec_pop_back(vec1);
    display(vec1);
    vec_pop_back(vec1);
    display(vec1);
    vec_pop_back(vec1);
    display(vec1);
    vec_pop_back(vec1);
    display(vec1);
    vec_pop_back(vec1);
    display(vec1);

    return 0;
}

預期輸出:

pos(vec2,0)=13, pos(vec2,1)=42
capacity(vec1)=4, capacity(vec2)=128
pos(vec2,2)=88
stack
0.00 stack
0.00 1.10 stack
0.00 1.10 2.20 stack
0.00 1.10 2.20 3.30 stack
0.00 1.10 2.20 3.30 4.40 heap
0.00 1.10 2.20 3.30 4.40 5.50 heap
0.00 1.10 2.20 3.30 4.40 heap
0.00 1.10 2.20 3.30 heap
0.00 1.10 2.20 heap
0.00 1.10 heap
0.00 heap
heap

STRUCT_BODY 與 v 巨集實作 C++ vector (STL) 雛形。

  • STRUCT_BODY: 紀錄 metadata 與存放資料的起始位址。
    • size: 紀錄 vector 已存放的資料個數。
    • on_heap: vector 的資料是否存放在 heap。
    • capacity: vector 可容納資料的總個數。
    • ptr: 資料若存放在 heap，ptr 用以紀錄起始位址。若存放在 stack，其起始位址為 buf 成員。
  • v: 此巨集宣告一個新 vector 變數。由於，vector 存放的資料有可能會在 heap，因此需要一個機制將分配到的記憶體空間釋放，進而避免 memory leak。所以當 vector 變數不在宣告此變數的作用範圍 (scope) 內 (譬如: 在某一函式宣告 vector 變數，當此函式程式執行完畢準備返回時)，可使用 GNU extension cleanup 屬性自行定義 cleanup function 用以釋放記憶體空間。
    • 使用 v 宣告新的 vector 變數，其資料預設存放空間位於 stack 。當使用 vec_push_back 或 vec_reserve，如有需要擴充 vector capacity大小，則使用 malloc 配置記憶體空間 (也就是存放空間改為 heap)。

本體的實作程式如下:

#include <stddef.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/* vector with small buffer optimization */

#define STRUCT_BODY(type)                                                  \
    struct {                                                               \
        size_t size : 54, on_heap : 1, capacity : 6, flag1 : 1, flag2 : 1, \
            flag3 : 1;                                                     \
        type *ptr;                                                         \
    }

#define NEXT_POWER_OF_2(s) \
    VV1 ? s : (size_t) 1 << (64 - __builtin_clzl(s))

#define v(t, s, name, ...)                                              \
    (void) ((struct {                                                   \
        _Static_assert(s <= 8, "it is too big");                        \
        int dummy;                                                      \
    }){1});                                                             \
    union {                                                             \
        STRUCT_BODY(t);                                                 \
        struct {                                                        \
            size_t filler;                                              \
            t buf[NEXT_POWER_OF_2(s)];                                  \
        };                                                              \
    } name __attribute__((cleanup(vec_free))) = {.buf = {__VA_ARGS__}}; \
    name.size = sizeof((__typeof__(name.buf[0])[]){0, __VA_ARGS__}) /   \
                    sizeof(name.buf[0]) -                               \
                1;                                                      \
    name.capacity = sizeof(name.buf) / sizeof(name.buf[0])

#define vec_size(v) v.size
#define vec_capacity(v) \
    (v.on_heap ? (size_t) 1 << v.capacity : sizeof(v.buf) / sizeof(v.buf[0]))

#define vec_data(v) (v.on_heap ? v.ptr : v.buf) /* always contiguous buffer */

#define vec_elemsize(v) sizeof(v.buf[0])
#define vec_pos(v, n) vec_data(v)[n] /* lvalue */

#define vec_reserve(v, n) __vec_reserve(&v, n, vec_elemsize(v), vec_capacity(v))
#define vec_push_back(v, e)                                            \
    __vec_push_back(&v, &(__typeof__(v.buf[0])[]){e}, vec_elemsize(v), \
                    vec_capacity(v))

#define vec_pop_back(v) (void) (VV2)

/* This function attribute specifies function parameters that are not supposed
 * to be null pointers. This enables the compiler to generate a warning on
 * encountering such a parameter.
 */
#define NON_NULL __attribute__((nonnull))

static NON_NULL void vec_free(void *p)
{
    STRUCT_BODY(void) *s = p;
    if (s->on_heap)
        free(s->ptr);
}

static inline int ilog2(size_t n)
{
    return 64 - __builtin_clzl(n) - ((n & (n - 1)) == 0);
}

static NON_NULL void __vec_reserve(void *vec,
                                   size_t n,
                                   size_t elemsize,
                                   size_t capacity)
{
    union {
        STRUCT_BODY(void);
        struct {
            size_t filler;
            char buf[];
        };
    } *v = vec;

    if (n > capacity) {
        if (v->on_heap) {
            v->ptr = realloc(v->ptr,
                             elemsize * (size_t) 1 << (v->capacity = ilog2(n)));
        } else {
            void *tmp =
                malloc(elemsize * (size_t) 1 << (v->capacity = ilog2(n)));
            memcpy(tmp, v->buf, elemsize * v->size);
            v->ptr = tmp;
            v->on_heap = 1;
        }
    }
}

static NON_NULL void __vec_push_back(void *restrict vec,
                                     void *restrict e,
                                     size_t elemsize,
                                     size_t capacity)
{
    union {
        STRUCT_BODY(char);
        struct {
            size_t filler;
            char buf[];
        };
    } *v = vec;

    if (v->on_heap) {
        if (v->size == capacity)
            v->ptr = realloc(v->ptr, VV3);
        memcpy(&v->ptr[v->size++ * elemsize], e, elemsize);
    } else {
        if (v->size == capacity) {
            void *tmp =
                malloc(elemsize * (size_t) 1 << (v->capacity = capacity + 1));
            memcpy(tmp, v->buf, elemsize * v->size);
            v->ptr = tmp;
            v->on_heap = 1;
            memcpy(&v->ptr[v->size++ * elemsize], e, elemsize);
        } else
            memcpy(&v->buf[v->size++ * elemsize], e, elemsize);
    }
}

請補完程式碼，使其執行符合預期。

參閱 你所不知道的C語言：技巧篇 以得知 GCC extension: attribute cleanup 使用技巧。

folly::fbvector 提到配置動態記憶體大小使用的 growth factor 會影響效能，其中 2 是一個不建議的數值，因為任何新配置的記憶體大小一定會大於之前配置過的記憶體的總和，造成 vector 無法重新利用曾經配置的空間。這點可以由下式驗證，例如欲配置的空間大小是

24 時，過去已配置的空間總和是
25−1
20+21+22+23+...2n=2n+1−1

以下嘗試設定 1.5 作為 growth factor，以資料筆數做為計算的依據，而非使用實際配置的記憶體空間，考量點：

  • 不是每個數字都適合成為記憶體大小，例如說 91 bytes
  • 可以用一套一樣的邏輯管理不同資料型態的 vector
  • 程式碼的更動比較少

在實做更動以前，須先完成相關的輔助函式

#define FACTOR 1.5
#define CHUNK_SIZE 4
static inline float ilog_factor(float n) /* log1.5(n) = log2(n)/log2(1.5)*/
{
    return ceilf(log2f(n)/log2f(FACTOR));
}

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →
這份實作程式碼的執行成本相當高，應予以改進

  • 根據容量計算最接近的 capacity 比較麻煩，無法像以 2 為底進行計算時單純使用 bitwise shift
  • 根據
    log1.5(n)=log2(n)log2(1.5)     進行計算，並嘗試全部都用標準函式庫來實作
  • 最大可用資料數量為
    chunk size×1.5capacity     (我選定的初始 chunk size 為 4 筆資料)
#define vec_capacity(v) __vec_capacity(&v)
static size_t inline __vec_capacity(void *vec)
{
    union {
        STRUCT_BODY(char);
        struct {
            size_t filler;
            char buf[];
        };
    } *v = vec;

    if (v->on_heap)
        return (size_t) (pow(1.5, v->capacity) * CHUNK_SIZE);
    return CHUNK_SIZE;
}

以 CHUNK_SIZE = 4 FACTOR = 1.5 為例，修改後的資料筆數會以如下方式成長

4 6 9 13 20 30 45 ...

作答區

VV1 = ?

  • (a) s
  • (b) s - 1
  • (c) s & (s - 1)
  • (d) (s & (s - 1))
  • (e) !(s & (s - 1))

VV2 = ?

  • (a) v.size -= 1
  • (b) v.capacity--

VV3 = ?

  • (a) (size_t) 1 << ++v->capacity
  • (b) elemsize * (size_t) 1 << ++v->capacity
  • (c) elemsize
  • (d) elemsize + (size_t) 1 << ++v->capacity

延伸問題:

  1. 解釋上述程式運作的原理，比照 第 3 週測驗題 進行效率分析;
  2. 指出上述實作的限制並提出改進方案，務必參照 folly::fbvector 文件和對應原始程式碼
  3. 以上述程式為基礎，實作 vector 經典操作，如 insert 和 erase

測驗 2

Donald E. Knuth 的經典著作《The Art of Computer Programming》提到 coroutine 這個自 1960 年代即現身的程式交錯執行技巧。nc 是個泛 UNIX 系統的工具程式，可用來檢測網路連線，詳見 nc: 網路管理者工具實用範例。我們嘗試透過 coroutine 來實作精簡的 nc 命令。GCC 針對 C 語言進行擴充，提供 Labels as Values，因此我們能取得 label 的地址並透過 goto 敘述跳躍到指定的 label，從而落實 coroutine。

搭配閱讀 你所不知道的C語言: goto 和流程控制篇

以下是實作程式碼: (檔名: tinync.c)

#include <stddef.h>

/* coroutine status values */
enum {
    CR_BLOCKED = 0,
    CR_FINISHED = 1,
};

/* Helper macros to generate unique labels */
#define __cr_line3(name, line) _cr_##name##line
#define __cr_line2(name, line) __cr_line3(name, line)
#define __cr_line(name) __cr_line2(name, __LINE__)

struct cr {
    void *label;
    int status;
    void *local; /* private local storage */
};

#define cr_init()                           \
    {                                       \
        .label = NULL, .status = CR_BLOCKED \
    }
#define cr_begin(o)                     \
    do {                                \
        if ((o)->status == CR_FINISHED) \
            return;                     \
        if ((o)->label)                 \
            goto *(o)->label;           \
    } while (0)
#define cr_label(o, stat)                                   \
    do {                                                    \
        (o)->status = (stat);                               \
        __cr_line(label) : (o)->label = &&__cr_line(label); \
    } while (0)
#define cr_end(o) cr_label(o, CR_FINISHED)

#define cr_status(o) (o)->status

#define cr_wait(o, cond)         \
    do {                         \
        cr_label(o, CR_BLOCKED); \
        if (!(cond))             \
            return;              \
    } while (0)

#define cr_exit(o, stat)   \
    do {                   \
        cr_label(o, stat); \
        return;            \
    } while (0)

#define cr_queue(T, size) \
    struct {              \
        T buf[size];      \
        size_t r, w;      \
    }
#define cr_queue_init() \
    {                   \
        .r = 0, .w = 0  \
    }
#define cr_queue_len(q) (sizeof((q)->buf) / sizeof((q)->buf[0]))
#define cr_queue_cap(q) ((q)->w - (q)->r)
#define cr_queue_empty(q) ((q)->w == (q)->r)
#define cr_queue_full(q) (cr_queue_cap(q) == cr_queue_len(q))

#define cr_queue_push(q, el) \
    (!cr_queue_full(q) && ((q)->buf[(q)->w++ % cr_queue_len(q)] = (el), 1))
#define cr_queue_pop(q) \
    (cr_queue_empty(q) ? NULL : &(q)->buf[(q)->r++ % cr_queue_len(q)])

/* Wrap system calls and other functions that return -1 and set errno */
#define cr_sys(o, call)                                                     \
    cr_wait(o, (errno = 0) || !(((call) == -1) &&                           \
                                (errno == EAGAIN || errno == EWOULDBLOCK || \
                                 errno == EINPROGRESS || errno == EINTR)))

#include <arpa/inet.h>
#include <errno.h>
#include <fcntl.h>
#include <netinet/in.h>
#include <stdio.h>
#include <stdlib.h>
#include <sys/select.h>
#include <sys/socket.h>
#include <unistd.h>

typedef cr_queue(uint8_t, 4096) byte_queue_t;

static void stdin_loop(struct cr *o, byte_queue_t *out)
{
    static uint8_t b;
    static int r;
    cr_begin(o);
    for (;;) {
        cr_sys(o, r = read(STDIN_FILENO, &b, 1));
        if (r == 0) {
            cr_wait(o, cr_queue_empty(out));
            cr_exit(o, 1);
        }
        cr_wait(o, LLL);
        cr_queue_push(out, b);
    }
    cr_end(o);
}

static void socket_write_loop(struct cr *o, int fd, byte_queue_t *in)
{
    static uint8_t *b;
    cr_begin(o);
    for (;;) {
        cr_wait(o, WWW);
        b = cr_queue_pop(in);
        cr_sys(o, send(fd, b, 1, 0));
    }
    cr_end(o);
}

static void socket_read_loop(struct cr *o, int fd)
{
    static uint8_t b;
    static int r;
    cr_begin(o);
    for (;;) {
        cr_sys(o, r = recv(fd, &b, 1, 0));
        if (r == 0)
            cr_exit(o, 1);
        cr_sys(o, write(STDOUT_FILENO, &b, 1));
    }
    cr_end(o);
}

static int nonblock(int fd)
{
    int flags = fcntl(fd, F_GETFL, 0);
    if (flags == -1)
        return -1;
    return fcntl(fd, F_SETFL, flags | O_NONBLOCK);
}

int main(int argc, char *argv[])
{
    if (argc != 3) {
        fprintf(stderr, "USAGE: %s <ip> <port>\n", argv[0]);
        return 1;
    }

    char *host = argv[1];
    int port = atoi(argv[2]);

    int fd = socket(AF_INET, SOCK_STREAM, 0);
    if (fd < 0) {
        perror("socket()");
        return 1;
    }
    if (nonblock(fd) < 0) {
        perror("nonblock() socket");
        return 1;
    }
    if (nonblock(STDIN_FILENO) < 0) {
        perror("nonblock() stdin");
        return 1;
    }
    if (nonblock(STDOUT_FILENO) < 0) {
        perror("nonblock() stdout");
        return 1;
    }

    struct sockaddr_in addr = {
        .sin_family = AF_INET,
        .sin_addr =
            {
                .s_addr = inet_addr(host),
            },
        .sin_port = htons(port),
    };
    connect(fd, (struct sockaddr *) &addr, sizeof(struct sockaddr_in));

    struct cr cr_stdin = cr_init();
    struct cr cr_socket_read = cr_init();
    struct cr cr_socket_write = cr_init();
    byte_queue_t queue = cr_queue_init();

    while (cr_status(&cr_stdin) == CR_BLOCKED &&
           cr_status(&cr_socket_read) == CR_BLOCKED) {
        if (cr_queue_empty(&queue)) {
            fd_set fds;
            FD_ZERO(&fds);
            FD_SET(STDIN_FILENO, &fds);
            FD_SET(fd, &fds);
            select(fd + 1, &fds, NULL, NULL, NULL);
        }
        socket_read_loop(&cr_socket_read, fd);
        socket_write_loop(&cr_socket_write, fd, &queue);
        stdin_loop(&cr_stdin, &queue);
    }

    close(fd);
    return 0;
}

測試方式為，建立兩個終端機視窗，為了方便後面描述，我們分別稱為 T1 和 T2。首先在 T1 終端機執行以下命令: (在 GNU/Linux 作業系統中)

nc -l 127.0.0.1 1234 < /etc/lsb-release

在 T2 終端機執行:

./tinync 127.0.0.1 1234 < tinync.c

這時會在 T1 終端機看到 tinync.c 檔案內容，而在 T2 終端機看到 /etc/lsb-release 檔案內容。

請補完程式碼，使其符合預期地運作。

作答區

WWW = ?

  • (a) cr_queue_empty(in)
  • (b) !cr_queue_empty(in)
  • (c) cr_queue_full(in)
  • (d) !cr_queue_full(in)

LLL = ?

  • (a) cr_queue_empty(out)
  • (b) !cr_queue_empty(out)
  • (c) cr_queue_full(out)
  • (d) !cr_queue_full(out)

延伸問題:

  1. 解釋上述程式運作的原理，可搭配 Simon Tatham 的文章 Coroutines in C 來解讀
  2. 指出上述實作的限制並提出改進方案
  3. 學習 EV3 子計畫 Coroutines in C，在上述程式碼的基礎上，實作 yield 和 restart 一類經典 coroutine 操作
Last changed by 
 
sysprog
System Software Programming
1566

Read more

Linux 核心的 /dev/mem 裝置

改寫自 Linux /dev/mem 的新玩法 一文，採用 CC BY-SA 授權

Jun 19, 2025
Linux 核心設計: Timer 及其管理機制

Copyright (慣C) 2019 宅色夫

Jun 16, 2025
現代處理器設計：原理和關鍵特徵

現代處理器設計：原理和關鍵特徵 ==直播錄影(上)== ==直播錄影(下)== 導讀短片 How A CPU Works | A Basic Guide On Processor Stages & Functionality 多核處理器有前途嗎？ [ ] 〈The Evolution Of CPU Processing Power〉系列 ==^必看^==

Jun 15, 2025
Linux 核心設計: Scheduler(8): Energy Aware Scheduling

系統的 throughput 是評斷排程器優劣的重要效能

Jun 14, 2025
Read more from sysprog
Published on HackMD