# 2019q1 Homework7 (ringbuffer)
contributed by < `grant7163` >

###### tags: `sysprog2019_q1`

## 作業要求
依據 [F11: ringbuffer](https://hackmd.io/s/SkYLI9CiN)
* 完成 [第 11 週測驗題 (上)](https://hackmd.io/s/HypUB7HjV) 和所有延伸題目
* 在 Linux 核心原始程式碼指出類似的 ring buffer 實作，設計 Linux 核心模組的實驗，需要探討對應的原理
* 需要涵蓋 kernel API 同步機制的運用
* 執行時期的分析 (提示: 可善用 eBPF)

## 測驗 1
首先判斷 cirbuf 是否已滿，若還沒滿則將 data 複製到 cirbuf tail 中並更新 tail 的位置，最後在檢查 tail 是否有超出 cirbuf 的記憶體區段，若超出 cirbuf 的記憶體區段則將 tail 取餘數(tail % cirbuf size)。

static inline int cirbuf_offer(cirbuf_t *cb,
                               const unsigned char *data,
                               const int size)
{
    /* prevent buffer from getting completely full or over commited */
    if (cirbuf_unusedspace(cb) <= size)
        return 0;

    int written = cirbuf_unusedspace(cb);
    written = size < written ? size : written;
    memcpy(cb->data + cb->tail, data, written);
    cb->tail += written;
    MM1 = if (cb->size < cb->tail) cb->tail %= cb->size;
    return written;
}

首先判斷 cirbuf 是否為空，若不為空則將 cirbuf head 中的資料取出並更新 head 的位置。

static inline unsigned char *cirbuf_peek(const cirbuf_t *cb)
{
    if (cirbuf_is_empty(cb))
        return NULL;
    MM2 = return cb->data + cb->head;
}

ps : 藍色圈圈為 head, 橘色圈圈為 tail

查閱 linux man page 了解相關說明。

`$ man mkstemp`
> The function generates a unique temporary filename from template, creates and opens the file, and returns an open file descriptor for the file.
> ==The last six characters of template must be "XXXXXX" and these are replaced with a string that makes the filename unique.== Since it will be modified, ==template must not be a string constant, but should be declared as a character array.==

`$ man 2 unlink`
> unlink() deletes a name from the filesystem. If that name was the last link to a file and no processes have the file open, the file is deleted and the space it was using is made available for reuse.
> If the name was the last link to a file but any processes still have the file open, the file will remain in existence until the last file descriptor referring to it is closed.
> If the name referred to a symbolic link, the link is removed.

`$ man 2 ftruncate`
> If the file previously was larger than this size, the extra data is lost. If the file previously was shorter, it is extended, and the extended part reads as null bytes ('\0').
> If the size changed, then the st_ctime and st_mtime fields (respectively, time of last status change and time of last modification; see inode(7)) for the file are updated, and the set-user-ID and set-group-ID mode bits may be cleared.

static void create_buffer_mirror(cirbuf_t *cb)
{
    char path[] = "/tmp/cirbuf-XXXXXX";
    int fd = mkstemp(path);
    unlink(path);
    ftruncate(fd, cb->size);
    /* FIXME: validate if mkstemp, unlink, ftruncate failed */

    /* create the array of data */
    cb->data = mmap(NULL, cb->size << 1, PROT_NONE, MAP_ANONYMOUS | MAP_PRIVATE,
                    -1, 0);
    /* FIXME: validate if cb->data != MAP_FAILED */

    void *address = mmap(cb->data, cb->size, PROT_READ | PROT_WRITE,
                         MAP_FIXED | MAP_SHARED, fd, 0);
    /* FIXME: validate if address == cb->data */

    address = mmap(cb->data + cb->size, cb->size, PROT_READ | PROT_WRITE,
                   MAP_FIXED | MAP_SHARED, fd, 0);
    /* FIXME: validate if address == cb->data + cb->size */

    close(fd);
}

## 延伸問題
- [ ] 解析 test suite 運作原理，嘗試強化現有 cirbuf 的例外處理機制，並且實作於 unit test 內部

#### test suite 運作原理
在 cirbuf 目錄下輸入 make 後會自動執行測試程式並將訊息顯示在終端機上，可以看到會額外產生一個 main.c，不難發現這就是剛剛在執行的測試程式。

$ make
...
./driver
 running TestCirbuf_set_size_with_init
 running TestCirbuf_is_empty_after_init
 running TestCirbuf_is_not_empty_after_offer
 running TestCirbuf_is_empty_after_poll_release
 running TestCirbuf_spaceused_is_zero_after_poll_release
 running TestCirbuf_cant_offer_if_not_enough_space
 running TestCirbuf_cant_offer_if_buffer_will_be_completely_full
 running TestCirbuf_offer_and_poll
 running TestCirbuf_cant_poll_nonexistant
 running TestCirbuf_cant_poll_twice_when_released
 running TestCirbuf_independant_of_each_other
 running TestCirbuf_independant_of_each_other_with_no_polling
OK (12 tests)

從 makefile 中觀察 main.c 是透過一個 shell script 的腳本(`gentest.sh`) 產生的。

main.c:
        bash tests/gentest.sh tests/test-*.c > $@
        
driver: main.c tests/test-cirbuf.c tests/unit-test.c main.c
        $(CC) $(CFLAGS) -o $@ $^
        ./$@

將檔案指定為 command line 的第一個 arguments(在此為 test-cirbuf.c)，接著使用 sed 命令編輯文字。

先將　test-cirbuf.c　中所有開頭為　void Test　的字串列出來，接著將　(　之後的字串替換為　`(CuTest*);` 並將字串開頭替換為　extern。

* `sed -e 's/^void //'` : 將 void 取代為 空白
參考 [3.3 The s Command](http://www.gnu.org/software/sed/manual/sed.html#The-_0022s_0022-Command)

* `*` : 匹配前面的（左鄰）字元有 0 個以上
* `.` : 匹配任何字元
* `^` : 表達式的開頭
* `$` : 表達式的結尾
參考 [5.3 Overview of basic regular expression syntax](http://www.gnu.org/software/sed/manual/sed.html#BRE-syntax)

FILES=$1
...
cat $FILES | grep '^void Test' |
    sed -e 's/(.*$//' \
        -e 's/$/(CuTest*);/' \
        -e 's/^/extern /'
...
cat $FILES | grep '^void Test' |
    sed -e 's/^void //' \
        -e 's/(.*$//' \
        -e 's/^/    SUITE_ADD_TEST(suite, /' \
        -e 's/$/);/'
...

在 main.c 中，建立一個 suite 來管理整個測試資料，透過 SUITE_ADD_TEST 這樣的 macro 將要測試的函式加入到 suite 中的 list。

#define SUITE_ADD_TEST(SUITE, TEST) CuSuiteAdd(SUITE, CuTestNew(#TEST, TEST))

typedef struct {
    int count;
    CuTest *list[MAX_TEST_CASES];
    int failCount;
} CuSuite;

...
void RunAllTests(void) {
    CuString *output = CuStringNew();
    CuSuite *suite = CuSuiteNew();

    SUITE_ADD_TEST(suite, TestCirbuf_set_size_with_init);
    SUITE_ADD_TEST(suite, TestCirbuf_is_empty_after_init);
    SUITE_ADD_TEST(suite, TestCirbuf_is_not_empty_after_offer);
    ...

    CuSuiteRun(suite);
    CuSuiteDetails(suite, output);
    printf("%s\n", CuStringC(output));
}

int main() {
    RunAllTests();
    return 0;
}

以 TestCirbuf_set_size_with_init() 函式為例 ：
建立一個 CuTest 的變數並將 TestCirbuf_set_size_with_init 指派給該變數，後續就可以透過這個變數來呼叫該函式(callback function)。

struct CuTestInternal {
    const char *name;
    TestFunction function;
    int failed;
    int ran;
    const char *message;
    jmp_buf *jumpBuf;
};

typedef struct CuTestInternal CuTest;

void CuTestInit(CuTest *t, const char *name, TestFunction function)
{
    t->name = CuStrCopy(name);
    t->failed = 0;
    t->ran = 0;
    t->message = NULL;
    t->function = function;
    t->jumpBuf = NULL;
}

CuTest *CuTestNew(const char *name, TestFunction function)
{
    CuTest *tc = CU_ALLOC(CuTest);
    CuTestInit(tc, name, function);
    return tc;
}

接著從 testSuite 中一一執行先前所加入的 testCase。

void CuSuiteRun(CuSuite *testSuite)
{
    for (int i = 0; i < testSuite->count; ++i) {
        CuTest *testCase = testSuite->list[i];
        CuTestRun(testCase);
        if (testCase->failed) {
            testSuite->failCount += 1;
        }
    }
}

在第 16 行的 `tc->function` 實際是執行先前指派的`TestCirbuf_set_size_with_init` 。

void TestCirbuf_set_size_with_init(CuTest *tc)
{
    cirbuf_t cb;
    cirbuf_new(&cb, 65536u);
    CuAssertTrue(tc, 65536u == cirbuf_size(&cb));
}

void CuTestRun(CuTest *tc)
{
    printf(" running %s\n", tc->name);

    jmp_buf buf;
    tc->jumpBuf = &buf;
    if (setjmp(buf) == 0) {
        tc->ran = 1;
        (tc->function)(tc);
    }
    tc->jumpBuf = 0;
}

故意先將 `CuAssertTrue(tc, 65536u == cirbuf_size(&cb));` 的大小改為不相等，使其方便觀察 CuAssertTrue 函式的整個作用。

$ make 
...
 running TestCirbuf_cant_poll_twice_when_released
 running TestCirbuf_independant_of_each_other
 running TestCirbuf_independant_of_each_other_with_no_polling
There was 1 failure:
1) TestCirbuf_set_size_with_init: tests/test-cirbuf.c:13: assert failed

!!!FAILURES!!!
Runs: 12 Passes: 11 Fails: 1

當 cond 為 1 時就直接 return 結束一個測試項目，否的話則紀錄錯誤資訊。

#define CuAssertTrue(tc, cond) \
    CuAssert_Line((tc), __FILE__, __LINE__, "assert failed", (cond))
    
void CuAssert_Line(CuTest *tc, const char *file, int line,
                   const char *message, int condition)
{
    if (condition)
        return;
    CuFail_Line(tc, file, line, NULL, message);
}    

將 `assert failed`, `__FILE__`, `__LINE__` 加入到該測試項目的 tc->message ，接著使用 longjmp 回到當初呼叫 setjmp() 的地方。

`$ man memmove`
> The memmove() function copies n bytes from memory area src to memory area dest. ==The memory areas may overlap==: copying takes place as though the bytes in src are first copied into a temporary array that does not overlap src or dest, and the bytes are then copied from the temporary array to dest.

void CuFail_Line(CuTest *tc, const char *file, int line,
                 const char *message2, const char *message)
{
    CuString string;

    CuStringInit(&string);
    if (message2) {
        CuStringAppend(&string, message2);
        CuStringAppend(&string, ": ");
    }
    CuStringAppend(&string, message);
    CuFailInternal(tc, file, line, &string);
}

static void CuFailInternal(CuTest *tc, const char *file,
                           int line, CuString *string)
{
    char buf[HUGE_STRING_LEN];

    sprintf(buf, "%s:%d: ", file, line);
    CuStringInsert(string, buf, 0);

    tc->failed = 1;
    tc->message = string->buffer;
    if (tc->jumpBuf != 0)
        longjmp(*(tc->jumpBuf), 0);
}

最後藉由 CuStringAppendFormat() 函式顯示統計的結果。

void CuSuiteDetails(CuSuite *testSuite, CuString *details)
{
...
    for (int i = 0, failCount = 0; i < testSuite->count; ++i) {
        CuTest *testCase = testSuite->list[i];
        if (testCase->failed) {
            failCount++;
            CuStringAppendFormat(details, "%d) %s: %s\n", failCount,
                                 testCase->name, testCase->message);
        }
    }
    CuStringAppend(details, "\n!!!FAILURES!!!\n");

    CuStringAppendFormat(details, "Runs: %d ", testSuite->count);
    CuStringAppendFormat(details, "Passes: %d ",
                         testSuite->count - testSuite->failCount);
    CuStringAppendFormat(details, "Fails: %d\n", testSuite->failCount);
}

#### 強化 cirbuf 程式碼
在 unit-test.c 中針對當有配置記憶體空間失敗時直接回傳 NULL 並印出錯誤訊息，接著不要讓該測試項目加入到測試 list 中。

void CuSuiteAdd(CuSuite *testSuite, CuTest *testCase)
{
    assert(testSuite->count < MAX_TEST_CASES);
    if(testCase == NULL)
        return;
        
    testSuite->list[testSuite->count] = testCase;
    testSuite->count++;
}

CuTest *CuTestNew(const char *name, TestFunction function)
{
    int ret = 0;

    CuTest *tc = CU_ALLOC(CuTest);
    if(tc == NULL)
    {
        printf("CuTestNew malloc fail \n");
        return tc;
    }

    ret = CuTestInit(tc, name, function);
    if(ret < 0)
    {
        free(tc);
        tc = NULL;
        printf("CuTestInit malloc fail \n");
    }

    return tc;
}

- [ ] 儘管已有 12 個 test case，但涵蓋層面仍不夠廣泛，請指出現有實作的缺陷並著手改善; （提示: 數值範圍及多個 PAGE_SIZE 的空間)

- [ ] 學習 [Using black magic to make a fast circular buffer](https://lo.calho.st/quick-hacks/employing-black-magic-in-the-linux-page-table/)，指出 fast circular buffer 實作的技巧，並分析 cirbuf 的效能，並逐步量化及改善效率;

### mmap

void *mmap(void *addr, size_t length, int prot, int flags, int fd, off_t offset);

`$ man 2 mmap`
>mmap() creates a new mapping in the virtual address space of the calling process.

* addr : The starting address for the new mapping is specified in addr
* length : 設定 mapping 的記憶體空間大小(必須大於 0)
* prot : 設定 mapping 的操作權限(不能與 open 函式設定的權現有衝突)
* PROT_EXEC : Pages may be executed
* PROT_READ : Pages may be read
* PROT_WRITE : Pages may be written
* PROT_NONE : Pages may not be accessed
* flags : 設定 mapping 到記憶體空間的功能
* MAP_SHARED : Share this mapping
* MAP_PRIVATE : Create a private copy-on-write mapping. Updates to the mapping are not visible to other processes mapping the same file, and are not carried through to the underlying file.
* fd :
* offset : mapping 開始的位置(原先 mapping 啟始的位置加偏移量)

- [ ] 向 OP-TEE 的 [Benchmark framework](https://optee.readthedocs.io/debug/benchmark.html) 取鏡，學習效能評比框架的開發;