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

# circbuf 程式碼解析

## cirbuf_usedspace()

/** Tell how much data has been written in bytes to the circular buffer.
 * @param cb The circular buffer.
 * @return number of bytes of how data has been written
 */
static inline int cirbuf_usedspace(const cirbuf_t *cb)
{
    if (cb->head <= cb->tail)
        return cb->tail - cb->head;
    return cb->size - (cb->head - cb->tail);
}

此函數功用為取得 cirbuf 中已使用之空間。其運作方式分成兩種，第一種為 `head <= tail`，表示 `tail` 尚未走訪回 cirbuf 的起點(以時鐘想像即尚未到達12點的位置)，此時我們可以直接以 `tail - head` 得知已使用的空間(尚未處理的資料)的大小。第二種方式則用於 `tail` 回到起點後(可想像成 `起點--tail--head`，`tail` 被包在中間)，這時候我們只要以 cirbuf 的大小去減掉未使用的空間(`head - tail`)即可得到已使用的空間的大小。

# 第 11 週測驗題 (上)

/** Write data to the tail of the circular buffer.
 * Increases the position of the tail.
 * This copies data to the circular buffer using memcpy.
 * After calling you should free the data if you don't need it anymore.
 *
 * @param cb The circular buffer.
 * @param data Buffer to be written to the circular buffer.
 * @param size Size of the buffer to be added to the circular buffer in bytes.
 * @return number of bytes offered
 */
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;

    memcpy(cb->data + cb->tail, data, size);
    cb->tail += size;
    
    if (cb->tail >= cb->size)
        cb->tail %= cb->size;

    return size;
}

第12~13行為補上的程式碼，其用途為檢查目前 `tail` 是否超過 cirbuf 的邊界，若是的話則以 cirbuf 的大小去對 `tail` 取餘數，以使得 `tail` 永遠只會在 cirbuf 的合法區域內走訪。

/** Look at data at the circular buffer's head.
 * Use cirbuf_usedspace to determine how much data in bytes can be read.
 * @param cb The circular buffer.
 * @return pointer to the head of the circular buffer
 */
static inline unsigned char *cirbuf_peek(const cirbuf_t *cb)
{
    if (cirbuf_is_empty(cb))
        return NULL;

    return cb->data + cb->head;
}

第11行為補上的程式碼，其用途為回傳 cirbuf 中 `head` 所處位置之記憶體位置。

## 延伸問題

### Test suite
#### 運作原理
使用的框架為 `unit-test.[ch]`，再搭配開發者為自己程式所設計的測試程式(`test-cirubf.c`)，最後使用 `gentest.sh` 生成 unit test 程式碼。

若需新增 test case ，則將其函數加入 `test-cirbuf.c` 中(測試函數命名的開頭需要與其他測試函數一致，因為測試程式生成腳本在生成過程中會以過濾函數名稱開頭的方式來擷取函數)。另，新增時也須注意到目前 test case 的數量是否超過設定上限(位於 `unit-test.h` 中)。

#### [強化測試框架對 signal 的處理](https://github.com/flawless0714/cirbuf/commit/4c30e40486dfe388b41f2b55e96e627553cc25dc)
初版測試框架沒有對 signal 做處理，導致遇到 SIGSEGV 等 signal 時測試程式被直接關閉。有鑑於強化 unit test 的完整性，我將搭配測試框架的 API 的 signal handler 加入測試框架中，使其可以在測試過程中接收到已註冊的 signal 時繼續完成整輪測試。

以下為測試過程中接收到 signal 的測試結果:

./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
There was 1 failure:
1) TestCirbuf_independant_of_each_other_with_no_polling: Segmentation fault occured!

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

> 題外話，在 `create_buffer_mirror` (或其他 API) 中遇到映射失敗等問題時不應該直接使用 exit() 離開程式，應該回傳 false 等結果，以使得 unit test 能接到所有錯誤。

#### fast circular buffer
讀完這篇給定的文章後才理解為什麼 circular buffer 在做初始化時要呼叫三次 mmap:
- 第一次呼叫:
向 OS 要一塊放的下兩倍 circular buffer 大小兩倍的記憶體。
- 第二次呼叫:
將稍早用 mkstemp 建立的暫存檔映射到第一次呼叫拿到的記憶體中，映射大小為 buffer 的大小。
- 第三次呼叫:
以第二次要求映射的記憶體位置(即第一次得到的位置)加上 buffer 大小的記憶體位置作為要求配置的位置，映射大小同樣為 buffer 的大小，並且也是映射到同樣的 fd 上(注意，兩次呼叫傳入的 offset 均為0)。如此一來，**第二次與第三次映射的記憶體位置即指向同一塊記憶體**。

有了這個特性後，當我們使用 memcpy 在寫入/讀取 buffer 時就可以不用考慮到邊界問題(當然，memcpy 前後要有對應的 handler 去處理 index (head/tail))去做存取。這種手法的考量點是存取效率，當使用一般方法時，我們必須考慮到目前 index 是否會超出邊界等等，這將對效能造成衝擊。文章中作者實測兩種方法的效率差距為三倍左右。

# Linux 核心原始程式碼中類似的 ring buffer 實作 (v4.15.18)
[此為 ring buffer 的實做](https://elixir.bootlin.com/linux/v4.15.18/source/include/linux/circ_buf.h)。Linux kernel 中用到 ring buffer 的程式碼大部分都是驅動程式。

開發人員會依照需求加入額外 ring buffer 相關的巨集到自己驅動程式的程式碼中。E.g. [Chrome OS EC](https://elixir.bootlin.com/linux/v4.15.18/source/drivers/platform/chrome/cros_ec_debugfs.c#L39) 自行實做了用於更新 ring buffer 的 index (head/tail) 的巨集(`CIRC_ADD`)，其中值得注意的是為了確保 index 不會超過 buffer 大小，他們在更新完 index 後將其與 `size - 1` (-1 為確保 head 與 tail 不會重疊(`head == tail`)，因為重疊也表示著 buffer 目前是空的，會產生矛盾)做 AND 運算，由此可知，除了使用 `head - size` (當發現 head 超過 size 後) 與 `head % size` 之外，我們還可以使用上述方法。

# 筆記
- mkstemp syscall
此系統呼叫用於建立暫存檔。需注意傳入參數 `template` 不可為 `char*` 形式的字串，必須為 `char []`，因為 mkstemp 會修改傳入參數(檔名)，所以我們必須傳入非唯讀的記憶體。

暫存檔建立成功後，我們即可呼叫 unlink 刪除檔案。雖然形式上是呼叫後檔案即被刪除，但如果還有 process 在使用這個檔案的資源則會等到 process 結束才被釋放。

- mmap syscall
此系統呼叫其中一種用法為增加存取效率。記得老師說過新酷音輸入法在使用 mmap 載入字典後效能提昇不少，因為少了 I/O 的瓶頸。

###### tags: `linux2019`