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

###### tags: `sysprog2019`

## 測驗 `1`

考慮到 [cirbuf](https://github.com/sysprog21/cirbuf) 這個 [circular buffer](https://en.wikipedia.org/wiki/Circular_buffer) 實作，嘗試透過 mmap 系統來化簡緩衝區邊界處理的議題。對照 [cirbuf.h](https://github.com/sysprog21/cirbuf/blob/master/cirbuf.h) 和 [test-cirbuf.c](https://github.com/sysprog21/cirbuf/blob/master/tests/test-cirbuf.c) 以得知具體用法，請補完以下程式碼:

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
    return written;
}

static inline unsigned char *cirbuf_peek(const cirbuf_t *cb)
{
    if (cirbuf_is_empty(cb))
        return NULL;
    MM2
}

==作答區==

MM1 = ?
* `(d)` if (cb->size < cb->tail) cb->tail %= cb->size;

MM2 = ?
* `(c)` returb cb->data + cb->head;

## 閱讀程式碼並著手改善
### cirbuf.h
- [int mkstemp(char *template);](https://linux.die.net/man/3/mkstemp)
> The mkstemp() 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.
>
> On success, these functions return the file descriptor of the temporary file. <font color ="red">On error, -1 is returned, and errno is set appropriately.</font>
1. template 的最後六個字必須要是 "XXXXXX" ，以便被替換成獨特的檔案名稱
2. "XXXXXX" 必須要透過 character array 來宣告
3. Return -1 when function creates and opens temporary file and errno is set appropriately.

- unlink
> Upon successful completion, 0 shall be returned. <font color ="red">Otherwise, -1 shall be returned and errno set to indicate the error.</font> If -1 is returned, the named file shall not be changed.

- ftruncate
> Upon successful completion, ftruncate() shall return 0; <font color ="red">otherwise, -1 shall be returned and errno set to indicate the error.</font>

- mmap
> On success, mmap() returns a pointer to the mapped area. <font color ="red">On error, the value MAP_FAILED (that is, (void *) -1) is returned, and errno is set to indicate the cause of the error.</font>

因此
1. 可以透過這些 function 的回傳值來判斷此次的呼叫是否成功
2. 若此次 <font color ="red">function 呼叫若是失敗，`errno` 的值會被設定，並可查詢 `errno` 的值得知呼叫失敗的原因 </font>
3. 一旦
`cb->data = mmap(NULL, cb->size << 1, PROT_NONE, MAP_ANONYMOUS | MAP_PRIVATE, -1, 0);` 成功要到記憶體空間，接下來
`address_start = mmap(cb->data, cb->size, PROT_READ | PROT_WRITE, MAP_FIXED | MAP_SHARED, fd, 0);` 或是 `void *address_half = mmap(cb->data + cb->size, cb->size, PROT_READ | PROT_WRITE, MAP_FIXED | MAP_SHARED, fd, 0); ` 若回傳值不對，則要記得 `munmap(cb->data, cb->size << 1);`

因此程式碼可改善為：

static void create_buffer_mirror(cirbuf_t *cb)
{
    char path[] = "/tmp/cirbuf-XXXXXX";
    int fd = mkstemp(path);
    if (fd == -1 || unlink(path) || ftruncate(fd, cb->size)) {
        if (-1 != fd) {
            close(fd);
        }   
        return;
    }   

    /* create the array of data */
    cb->data = mmap(NULL, cb->size << 1, PROT_NONE, MAP_ANONYMOUS | MAP_PRIVATE,
                    -1, 0); 
    if (cb->data == MAP_FAILED) {
        close(fd);
        return;
    }   

    void *address_start = mmap(cb->data, cb->size, PROT_READ | PROT_WRITE,
                               MAP_FIXED | MAP_SHARED, fd, 0); 
    if (cb->data != address_start) {
        munmap(cb->data, cb->size << 1); 
        close(fd);
        return;
    }   

    void *address_half =
        mmap(cb->data + cb->size, cb->size, PROT_READ | PROT_WRITE,
             MAP_FIXED | MAP_SHARED, fd, 0); 
    if (address_half != cb->data + cb->size) {
        munmap(cb->data, cb->size << 1); 
        close(fd);
        return;
    }   

    close(fd);
    return;
}

`create_buffer_mirror` 後若 errno 的值不為 0 則代表在 create buffer mirror 的過程中有出錯。

/** Create new circular buffer.
 * @param size Size of the circular buffer.
 * @return pointer to new circular buffer
 */
static inline void cirbuf_new(cirbuf_t *dst, const unsigned long int size)
{
    dst->size = size;
    dst->head = dst->tail = 0;
    assert(!errno);
    create_buffer_mirror(dst);
    if (errno) {
        printf("Fail to create buffer mirror\n");
        errno = 0;
    }
}

## 延伸問題:
1. 解析 test suite 運作原理，嘗試強化現有 cirbuf 的例外處理機制，並且實作於 unit test 內部;
2. 儘管已有 12 個 test case，但涵蓋層面仍不夠廣泛，請指出現有實作的缺陷並著手改善; （提示: 數值範圍及多個 PAGE_SIZE 的空間)
3. 學習 [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 的效能，並逐步量化及改善效率;
4. 向 OP-TEE 的 [Benchmark framework](https://optee.readthedocs.io/debug/benchmark.html) 取鏡，學習效能評比框架的開發;