# 2019q1 Homework7 (ringbuffer)
contributed by < `rebvivi` >
###### tags: `linux2019`
* [F11: ringbuffer](https://hackmd.io/s/SkYLI9CiN)
## 作業要求
- 完成 第 11 週測驗題 (上) 和所有延伸題目
- 在 Linux 核心原始程式碼指出類似的 ring buffer 實作，設計 Linux 核心模組的實驗，需要探討對應的原理
- 需要涵蓋 kernel API 同步機制的運用
- 執行時期的分析 (提示: 可善用 eBPF)
## 測驗 `1`
- 在 `cirbuf.h` 中的 `create_buffer_mirror()` 函式中有用到 mmap
>在 [mmap 的 Linux Man Page](http://man7.org/linux/man-pages/man2/mmap.2.html) 中有提到：
>
>mmap() creates a new mapping in the virtual address space of the calling process.
>
>將檔案內容 mapping 到一段 virtual memory 上，透過對這段 memory 的讀取和修改，實現對檔案的讀取和修改
>
>>#include <sys/mman.h>
void *mmap(void *addr, size_t length, int prot, int flags, int fd, off_t offset);
>
>- `void *addr`：指向 new mapping 的 starting address ，通常設為 NULL，代表讓 kernel 自動選定 address
>
>- `size_t length`： mapping 的長度
>
>- `int prot`： mapping 區域所想要的 memory protection 方式
>`PROT_EXEC`：pages 可被 execute
`PROT_READ`：pages 可被 read
`PROT_WRITE`：pages 可被 write
`PROT_NONE`：pages 不能被 access
>
>- `int flags`：影響 mapping 區域的各種特性
>`MAP_ANONYMOUS`：建立匿名 mapping ，會忽略參數 fd，不涉及檔案，而且 mapping 區域無法和其他 process 共享
>`MAP_PRIVATE`：不允許其他 mapping 該檔案的 process 共享，對 mapping 區域的寫入操作會產生一個 copy-on-write 的 mapping ，對此區域所做的修改不會寫回原檔案
>
>- `int fd`：由 open 返回的 file descriptor ，代表要 mapping 到 kernel 的檔案，如果 `flags` 中設置了`MAP_ANONYMOUS`， `fd` 設為 -1
>
>- `off_t offset`：從檔案 mapping 開始處的 offset ，通常為 0 ，代表從檔案最前方開始 mapping
>
>如果 mapping 成功則 return mapping 區域的 kernel starting address，否則 return MAP_FAILED(-1)
```cpp=
static int create_buffer_mirror(cirbuf_t *cb)
{
char path[] = "/tmp/cirbuf-XXXXXX";
int fd = mkstemp(path);
int vu = unlink(path);
int vf = ftruncate(fd, cb->size);
/* FIXME: validate if mkstemp, unlink, ftruncate failed */
if (fd < 0)
return -1;
if (vu)
return -1;
if (vf)
return -1;
/* 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 */
if (cb->data == MAP_FAILED)
return -1;
void *address = mmap(cb->data, cb->size, PROT_READ | PROT_WRITE,
MAP_FIXED | MAP_SHARED, fd, 0);
/* FIXME: validate if address == cb->data */
if (address != cb->data)
return -1;
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 */
if (address != cb->data + cb->size)
return -1;
close(fd);
return 0;
}
```
- 第 4 行中，根據 path 建立檔名不重複的暫存檔
```cpp
int fd = mkstemp(path);
```
>在 [mkstemp 的 Linux Man Page](http://man7.org/linux/man-pages/man3/mkstemp.3.html) 中有提到：
>
>The mkstemp() function generates a unique temporary filename from template, creates and opens the file, and returns an open file descriptor for the file.
>
>>#include <stdlib.h>
int mkstemp(char *template);
>
- 第 5 行中，刪除參數 path 所指定的檔案
如果該檔名為最後連接點，但有其他 process 打開了此檔案，則在所有關於此檔案的 file descriptor 皆關閉後才會刪除
```cpp
int vu = unlink(path);
```
>在 [unlink 的 Linux Man Page](https://linux.die.net/man/2/unlink) 中有提到：
>
>unlink() deletes a name from the file system. 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.
>
>>#include <unistd.h>
int unlink(const char *pathname);
- 第 6 行中，將檔案的大小指定為 cb->size
```cpp
int vf = ftruncate(fd, cb->size);
```
>在 [ftruncate 的 Linux Man Page](https://linux.die.net/man/2/ftruncate) 中有提到：
>
>The truncate() and ftruncate() functions cause the regular file named by path or referenced by fd to be truncated to a size of precisely length bytes.
>
>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').
>
>>#include <unistd.h>
#include <sys/types.h>
int ftruncate(int fd, off_t length);
>
>ftruncate() 會將參數 fd 指定的檔案大小改為參數 length 指定的大小。參數 fd 為已打開的 file descriptor ，而且必須是以寫入模式打開的檔案。如果原來的檔案容量比參數 length 大，則超過的部分會被刪去
- 第 18 行中，使用 `MAP_ANONYMOUS` 和 ` MAP_PRIVATE` 的方式分配了一塊為指定緩衝區大小 2 倍的 memory space
```cpp
cb->data = mmap(NULL, cb->size << 1, PROT_NONE, MAP_ANONYMOUS | MAP_PRIVATE,-1, 0);
```
- 第 25 行中，將 mkstemp 所建立的暫存檔 mapping 到 address `data ~ data + size`
```cpp
void *address = mmap(cb->data, cb->size, PROT_READ | PROT_WRITE,MAP_FIXED | MAP_SHARED, fd, 0);
```
- 第 32 行中，將 mkstemp 所建立的暫存檔 mapping 到 address `data + size ~ data + (2 * size)`
```cpp
address = mmap(cb->data + cb->size, cb->size, PROT_READ | PROT_WRITE, MAP_FIXED | MAP_SHARED, fd, 0);
```
這樣對 `data[i]` 的讀寫操作就等同於對 `data [i+size]` 的讀寫操作，達到了 ring buffer 這樣形同環狀資料的處理
---
```cpp=
/** 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;
int written = cirbuf_unusedspace(cb);
written = size < written ? size : written;
memcpy(cb->data + cb->tail, data, written);
cb->tail += written;
if (cb->size < cb->tail) cb->tail %= cb->size;
return written;
}
```
- 第 21 行中，將 `data` copy 長度 `written` 到 `data[tail]`
```cpp
memcpy(cb->data + cb->tail, data, written);
```
- 第 22 ~ 23 行中，改變 cb->tail 所在的 index，也就是
```
data[tail]=data[tail + written]
if(size < tail) data[tail]=data[tail % size]
```
```cpp
cb->tail += written;
if (cb->size < cb->tail) cb->tail %= cb->size;
```
---
```cpp=
/** 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 行中， return `data[head]`
```cpp
return cb->data + cb->head;
```
## 延伸問題 1
### 解析 test suite 運作原理
- 在 `unit-test.c` 中的 `CuStringAppendFormat()` 函式：
```cpp=
void CuStringAppendFormat(CuString *str, const char *format, ...)
{
va_list argp;
char buf[HUGE_STRING_LEN];
va_start(argp, format);
vsprintf(buf, format, argp);
va_end(argp);
CuStringAppend(str, buf);
}
```
>定義一個 function prototype 時，若是將 argument list 以"..."代入，就代表了這個 function 使用 variant argument：
>`void func(...);`
>
>這樣子可以讓 compiler 不檢驗傳入 function 裡的 argument 的型態和數量， compile 出來的程式碼在呼叫端就能夠把各式各樣 argument 傳入：
>`void func(0, 1, 2, 3, 0.4, 0.5 "6789");`
>
>但是要存取 variant argument 不可能像一般程式一樣直接存取它們，因為缺少 argument variable ，所以我們改用 <stdarg.h> 裡面所提供的 macro 與 type
>
>在 [stdarg 的 Linux Man Page](http://man7.org/linux/man-pages/man3/stdarg.3.html) 中有提到：
>
>A function may be called with a varying number of arguments of varying types. The include file <stdarg.h> declares a type va_list and defines three macros for stepping through a list of arguments whose number and types are not known to the called function.
>
>The called function must declare an object of type va_list which is used by the macros va_start(), va_arg(), and va_end().
>
>
>>#include <stdarg.h>
void va_start(va_list ap, last);
type va_arg(va_list ap, type);
void va_end(va_list ap);
>
>- `va_list`：宣告一個指向 variable argument list 的 pointer `ap`
>
>- `va_start`：初始化 `ap` ，讓它指向正確的 variable argument list 開頭
> `last`：variable argument list 中，",..." 之前的那個 argument
>
>- `va_end`：清除 pointer `ap`，把它設為NULL
>
>在 [vsprintf 的 Linux Man Page](https://linux.die.net/man/3/vsprintf) 中有提到：
>
>The functions vprintf(), vfprintf(), vsprintf(), vsnprintf() are equivalent to the functions printf(), fprintf(), sprintf(), snprintf(), respectively, except that they are called with a va_list instead of a variable number of arguments. These functions do not call the va_end macro. Because they invoke the va_arg macro, the value of ap is undefined after the call.
>
>
>>#include <stdarg.h>
int vsprintf(char *str, const char *format, va_list ap);
>
>vsprintf() 會根據 `format` 來轉換並格式化數據，然後將結果 copy 到 `str`，直到出現 `'\0'`為止
>
- 第 6 行中，根據 `format` 來轉換並格式化數據，然後將結果 copy 到 `buf`
```cpp
vsprintf(buf, format, argp);
```
- 第 8 行中，將根據 `format` 轉換完成並格式的化數據，利用 `CuStringAppend()` 函式，加到 `str` 的後面
```cpp
CuStringAppend(str, buf);
```
---
- 在 `unit-test.c` 中的 `CuTestRun()` 函式：
```cpp=
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;
}
```
>[C99 的規格書](http://www.dii.uchile.cl/~daespino/files/Iso_C_1999_definition.pdf) 的 254 頁中有提到：
>
>The setjmp macro saves its calling environment in its jmp_buf argument for later use by the longjmp function.
>
>>#include <setjmp.h>
int setjmp(jmp_buf env);
>
>- `env`：保存現有執行環境資訊，型態為 jmp_buf
>
>
>If the return is from a direct invocation, the setjmp macro returns the value zero. If the return is from a call to the longjmp function, the setjmp macro returns a nonzero value.
>
>如果 return 0 表示第一次呼叫 setjmp() ， return nonzero 表示它是從 longjmp() 返回的
>
---
- 在 `test-cirbuf.c` 中，多次用到 `CuAssertTrue()`，例如：
```cpp=
void TestCirbuf_set_size_with_init(CuTest *tc)
{
cirbuf_t cb;
cirbuf_new(&cb, 65536u);
CuAssertTrue(tc, 65536u == cirbuf_size(&cb));
}
```
- `CuAssertTrue()` 的 macro 定義在 `unit-test.h` 中
```cpp
#define CuAssertTrue(tc, cond) \
CuAssert_Line((tc), __FILE__, __LINE__, "assert failed", (cond))
```
>[C99 的規格書](http://www.dii.uchile.cl/~daespino/files/Iso_C_1999_definition.pdf) 的 172 頁中有提到：
>
>- `__FILE__` ：The presumed name of the current source file (a character string literal).
>- `__LINE__` ： The presumed line number (within the current source file) of the current source line (an integer constant).
>
- 如果 `TestCirbuf_set_size_with_init()` 的第 5 行 `65536u == cirbuf_size(&cb)` 有成立，代表第 4 行 `cirbuf_new(&cb, 65536u)`有成功：
```cpp=
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);
}
```
- `CuAssert_Line()`的第 7 行就會成立，return 回這個 function
- 之後 `main.c` 就會繼續進行下一個測試
- 如果 `TestCirbuf_set_size_with_init()` 的第 5 行 `65536u == cirbuf_size(&cb)` 不成立，代表第 4 行 `cirbuf_new(&cb, 65536u)` 沒有成功：
- `CuAssert_Line()` 的第 7 行就不會成立
- 執行 `CuAssert_Line()` 的第 9 行，也就是 `CuFail_Line()` 函式：
```cpp
CuFail_Line(tc, __FILE__, __LINE__, NULL, "assert failed");
```
```cpp=
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);
}
```
- 之後 `CuFail_Line()` 的第 14 行，將錯誤訊息 `"assert failed"` 附加到 `string`
- `CuFail_Line()` 的第 15 行，將`string` 傳給 `CuFailInternal()` 函式：
```cpp
CuFailInternal(tc, __FILE__, __LINE__, &string);
```
```cpp=
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);
}
```
- `CuFailInternal()` 函式的第 9 行，利用 `CuStringInsert()` 將 function name 和 line number，追加到錯誤消息 `"assert failed"` 的後面
- 第 12 行中，將完整的錯誤消息給 `tc->message`
- 第 14 行中，由 `longjmp` 返回
---
- 在 `main.c` 中，多次用到 `SUITE_ADD_TEST`：
```cpp
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);
SUITE_ADD_TEST(suite, TestCirbuf_is_empty_after_poll_release);
SUITE_ADD_TEST(suite, TestCirbuf_spaceused_is_zero_after_poll_release);
SUITE_ADD_TEST(suite, TestCirbuf_cant_offer_if_not_enough_space);
SUITE_ADD_TEST(suite, TestCirbuf_cant_offer_if_buffer_will_be_completely_full);
SUITE_ADD_TEST(suite, TestCirbuf_offer_and_poll);
SUITE_ADD_TEST(suite, TestCirbuf_cant_poll_nonexistant);
SUITE_ADD_TEST(suite, TestCirbuf_cant_poll_twice_when_released);
SUITE_ADD_TEST(suite, TestCirbuf_independant_of_each_other);
SUITE_ADD_TEST(suite, TestCirbuf_independant_of_each_other_with_no_polling);
```
- `SUITE_ADD_TEST` 的 macro 定義在 `unit-test.h` 中：
```cpp
CuTest *CuTestNew(const char *name, TestFunction function);
#define SUITE_ADD_TEST(SUITE, TEST) CuSuiteAdd(SUITE, CuTestNew(#TEST, TEST))
```
- `#TEST` 等於將 `TEST` 内容轉為 `const char *`
```cpp=
void CuSuiteAdd(CuSuite *testSuite, CuTest *testCase)
{
assert(testSuite->count < MAX_TEST_CASES);
testSuite->list[testSuite->count] = testCase;
testSuite->count++;
}
```
- 利用 `CuSuiteAdd()` ，將多個 `testCase` 合併成 `testSuite`
---
- 在 `main.c` 中，測試的執行是靠 `CuSuiteRun()` 函式：
```cpp
CuSuiteRun(suite);
```
```cpp=
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;
}
}
}
```
- `CuSuiteRun()` 的第 3 行中，for 迴圈是依序測試 `testSuite` 裡頭的各個 `testCase`
- `CuSuiteRun()` 的第 5 行中，對各個 `testCase` 進行 `CuTestRun()`
```cpp=
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;
}
```
- `CuTestRun()` 的第 7 行的 `setjmp(buf) == 0` ，設下跳轉點
- 之後第 8 ~ 9 行開始測試 `testCase`，如果測試失敗就紀錄錯誤訊息，使用 `longjmp` 回到第 7 行的 `setjmp(buf) == 0`
- `CuSuiteRun()` 的第 6 ~ 7 行中，會對 `testCase` fail 的次數進行 count，以便全部 `testCase` 運行完後，進而運行 `CuSuiteDetails()`
Sign in with Wallet
Connect another wallet