# 2020q1 Homework3 (quiz4)
contributed by < `eecheng87` >
###### tags: `linux2020`
> [第 4 週測驗題](https://hackmd.io/@sysprog/linux2020-quiz4)
## 題目 `1`
### 解釋程式運作原理
首先，觀察如何呼叫 `bitcpy`，從參數著手：
* src : 代表欲被複製的起始位址
* read : 為 src 的偏移量 ( 真正開始複製的位址 )
* dest : 代表欲被貼上的起始位址
* write : 為 dest 的偏移量 ( 真正開始貼上的位址 )
* count : 代表要複製的位元數
舉例如何呼叫 `bitcpy` :
```cpp
memset(&input[0], 0xFF, sizeof(input));
memset(&output[0], 0x00, sizeof(output));
bitcpy(&output[0], 1, &input[0], 1, 3);
dump_binary(&output[0], 1);
```
```shell
01100000
```
解釋 : 要複製 `input[0]` 的第 1 個位元往後數 3 個 ( $111_b$ ) 到 `output[0]` 的第 1 個位元 ( 左邊表示資料最高位 )。
再來，我們開始看 `bitcpy` 是如何實作的
```cpp
..
data = *source++;
bitsize = (_count > 8) ? 8 : _count;
if (read_lhs > 0) {
data <<= read_lhs;
if (bitsize > read_rhs)
data |= (*source >> read_rhs);
}
..
```
進入 while 迴圈作的第一件事，把 8 個 bit 的資料複製到 `data`。但是又分成兩種情況，第一種是最簡單的，若我們的 `_read` 是 0 ( 不位移 )，那我們可以直接把 `source` 的 8 個 bit 給 data。另外一種情況是，並非從 `source` 的第一個位元開始複製。
用實際例子說明狀況二：
假設 `_read = 3` ( 從第三個位元開始複製 )，則我們會得到 `read_lhs = 3; read_rhs = 5`。目前我們得到的 `data` 是從 `source` 第 0 位元開始的資料，所以我們要把 `data` 往左移 3 格 ( 即 `read_lhs` )。所以目前 `data` 由左數過來 5 個 bits 都是我們要的，但是因為上一個步驟往左移，最右邊 3 個 bit 變成 $000_b$，這不是我們要的。我們要的是，下一個 `source` 的左邊三個 bit 。因為我們在上面已經移動 `source` 了 ( `source++` )，所以我們不需要再動，直接取左三 bit 然後再透過 `|` 寫到 `data` 右邊三個 bit。這樣我們就得到我們想要的前 8 個 bit 了 。
```cpp
..
if (bitsize < 8)
data &= read_mask[bitsize];
..
```
接著如果 目前還需要再讀的 bit 小於 8 的話，我們透過 mask 把多餘的部分變成 0。
```cpp
original = *dest;
if (write_lhs > 0) {
..
} else {
if (bitsize < 8)
data = data | (original & write_mask[bitsize]);
*dest++ = data;
}
```
再來是處理寫到 `dest` 的部分，分成兩種情境，寫的位址是否有位移值，若沒有則是比較單純的狀況 ( `else` ) ，我們先來看看若不用位移的話怎麼處理。
目前我們的 `data` 是經過前面**讀的位移**處理後拿到的資料，這裡面全部都是我們要的，所以可以直接給 `dest`。但是如果我們剩下需要複製的位元小於 8 的話，我們需要透過 `mask` 把 `data` 右邊不要的位元清掉。
```cpp
mask = read_mask[write_lhs];
if (bitsize > write_rhs) {
..
} else {
..
}
```
再來，我們來觀察若寫需位移要怎麼處理。這裡的 `mask` 是用來保留左邊的 bit 和清除右邊的 bit ( 因為若有位移，我們不能汙染到左邊的 bit )。
這次我們同樣用舉例的方式來了解程式原理 :
假設`_write = 3` ( 從第三個位元開始貼上 )，則我們會得到 `write_lhs = 3; write_rhs = 5`。若該次需要寫的位元超過 `write_rhs`，代表接下來要貼上的 8 位元會跨一個單位 ( 8 位元 )。所以我們要做以下處理 :
```cpp
*dest++ = (original & mask) | (data >> write_lhs);
original = *dest & write_mask[bitsize - write_rhs];
*dest = original | (data << write_rhs);
```
分別是 :
* 把前五個 bit 寫到 `dest` ( 注意不能污染前三個 bit，然後把 `dest` 往下一格移動 )
* 把下一格 `dest` 的右邊 5 個 bit 保留好存到 `original` ( 左邊 3 個清成 0 )
* 把 `original` 往左移 5 bit，所以目前的前三 bit 就是上次 `data` 還沒複製到 `dest` 的資料。透過 `|` 把第二步驟留下的左三 bit 填滿
接著第二種情況就比較單純了，不用考慮跨單位的貼上，所以我們只需：
```cpp
*dest++ = (original & mask) | (data >> write_lhs);
```
`(original & mask)` 讓左邊保持原本的狀態，右邊清成 0，接著透過 `|` 把右邊清掉的位元填上 `data`。
```cpp
_count -= bitsize;
```
最後，要更新還需要寫幾個 bit。
## 延伸問題
### 改善 bit copy 的效能
原本的版本讓人詬病的地方是做了太多的檢查。當讀 `source` 時，為了能讓 `data` 存滿 8 bit ，會判斷一次，處理跨位址的位元。此外，複製到 `dest` 也會透過判斷來處理跨位址的貼上。而最糟糕的部份是，迭代的每一次都會做上述的判斷。
若我們要提高複製位元的效能，在原版本的基礎上，我們要做的是儘量降低判斷 (branch) 的次數。我想到一個方法是，一開始先處理最前頭小於 8 bit 的資料，接著而來的是一堆連續需要改動的 8 bit 資料，我們可以透過迴圈解決，最後處理最後一段小於 8 bit 的資料。以下為優化後的 `my_bitcpy` 片段程式碼：
```cpp
const char MASK[8] = { 1, 3, 7, 15, 31, 63, 127, 255 };
uint8_t *src = (uint8_t *)_src + (_read / 8);
uint8_t *dest = (uint8_t *)_dest + (_write / 8);
uint8_t src_off = _read & 7;
uint8_t dest_off = _write & 7;
size_t offset = src_off - dest_off;
int iter_time;
uint8_t data;
uint8_t mask = MASK[offset - 1];
int count = (int)_count;
data = (*src++ << offset) | ((*src >> (8 - offset)) & mask);
data &= MASK[8 - dest_off - 1];
*dest++ |= data;
count -= 8 - dest_off;
iter_time = count >> 3;
while (--iter_time >= 0){
*dest++ = (*src++ << offset) | ((*src >> (8 - offset)) & mask);
}
int append = (count & 7);
if (append > 0) {
*dest |= ((*src++ << offset) | (*src >> (8 - offset))) & (~MASK[8 - append - 1]);
}
```
誠如前面的說明，一開始透過 bit operation，取出最前頭小於 8 bit 的資料存到 `data`，再貼上到 `dest`。接著是迴圈處理連續的 8 bit 貼上，這是也讓效能提昇最關鍵的地方，我們只需要判斷迭代次數就好，準備要貼上的東西有固定的模式，不須再額外判斷，而次數由 `count` 決定 ( 除以 8 ，因為一次 8 bit )。最後記得貼上剩下少於 8 bit 的尾巴。
以上的程式碼是建立在 `source_offset > dest_offset` 的情況寫的演算法。大於和等於的情況也是比照辦理，大概照著以下架構：
```cpp
if (_read == _write) {
..
} else if (_read > _write) {
..
} else {
..
}
```
而我的演算法純粹以跨位址的複製為考量點，並未考量在同一個位址內的複製，因為在小範圍的複製，演算法對效能的影響有限。如同在 N 很小的條件下，複雜度 $O(N^2)$ 的 insertion sort 不會表現的比 $O(NlogN)$ 的 merge sort 還差。
### 實驗
設計實驗，同樣以跨位址複製為出發點。評估當複製的位元數從 8 ~ 7900 兩種演算法 (優化前後) 的速度。
```cpp
static uint8_t output[1000], input[1000];
for (int size = 8; size < 7900; size++) {
memset(&output[0], 0x00, sizeof(output));
clock_gettime(CLOCK_REALTIME, &t1);
bitcpy(&output[0], 2, &input[0], 4, size);
clock_gettime(CLOCK_REALTIME, &t2);
printf("%d %ld",size,elapse(t1, t2));
memset(&output[0], 0x00, sizeof(output));
clock_gettime(CLOCK_REALTIME, &t1);
my_bitcpy(&output[0], 2, &input[0], 4, size);
clock_gettime(CLOCK_REALTIME, &t2);
printf(" %ld\n",elapse(t1, t2));
printf("\n");
}
```
以下為實驗結果 (已排除干擾)：
由上面的結果可以觀察到，如同我一開始的說法，當複製的位元數很小，其實演算法對效能的影響有限。反之，當 N 上升到一定的程度，便可看出速度的差異，當 N = 7900 時，我的演算法比原本的快 3 倍。
另外還可以透過 `perf` 來觀察是否有達到一開始的目標， branch 數量的減少。
```shell
$ sudo perf record \
-e branch-misses:u,branch-instructions:u \
-F 11000 ./cpybit
$ sudo perf report
```
可以觀察到當執行 `bitcpy` 時：
```shell
Available samples
-------------------------------
293 branch-misses:u
489 branch-instructions:u
```
當執行 `my_bitcpy` 時：
```shell
Available samples
-------------------------------
320 branch-misses:u
427 branch-instructions:u
```
的確，修改後的版本 branch 指令有減少。
:::warning
可對照 Linux 核心的 [bitmap](https://www.kernel.org/doc/htmldocs/kernel-api/kernel-lib.html) 實作，做了進一步的包裝，注意到 `IS_ALIGNED` 和 `__builtin_constant_p` 的使用
> 原始程式碼: [include/linux/bitmap.h](https://github.com/torvalds/linux/blob/master/include/linux/bitmap.h)
:notes: jserv
:::
### 補充
透過老師的提示，我找到 bitmap.h 中的 `bitmap_set`，觀察 linux 專案如何實作未對齊字元的操作。
```cpp
static __always_inline void bitmap_set(unsigned long *map, unsigned int start,
unsigned int nbits)
{
if (__builtin_constant_p(nbits) && nbits == 1)
__set_bit(start, map);
else if (__builtin_constant_p(start & BITMAP_MEM_MASK) &&
IS_ALIGNED(start, BITMAP_MEM_ALIGNMENT) &&
__builtin_constant_p(nbits & BITMAP_MEM_MASK) &&
IS_ALIGNED(nbits, BITMAP_MEM_ALIGNMENT))
memset((char *)map + start / 8, 0xff, nbits / 8);
else
__bitmap_set(map, start, nbits);
}
```
`bitmap_set` 主要分成三個功能:
* 若需要 set 的 bit 數只有 1 個，則直接呼叫 `__set_bit`
* 若需要 set 的 bits 的起始位置和終了位置都有對齊，則可直接用 `memset` 來完成
* 若需要處理沒對齊的位元操作則呼叫 `__bitmap_set`。
很明顯地，我們在乎的是最後一個功能，看看原始碼如何處理非對齊的位元操作，於是我們往 `__bitmap_set` 裡面看:
```cpp
void __bitmap_set(unsigned long *map, unsigned int start, int len)
{
unsigned long *p = map + BIT_WORD(start);
const unsigned int size = start + len;
int bits_to_set = BITS_PER_LONG - (start % BITS_PER_LONG);
unsigned long mask_to_set = BITMAP_FIRST_WORD_MASK(start);
while (len - bits_to_set >= 0) {
*p |= mask_to_set;
len -= bits_to_set;
bits_to_set = BITS_PER_LONG;
mask_to_set = ~0UL;
p++;
}
if (len) {
mask_to_set &= BITMAP_LAST_WORD_MASK(size);
*p |= mask_to_set;
}
}
```
其實以上的實作和我提供的方法很像，都是只處理前後兩段非對齊的記憶體 + 用迭代處理中間連續的記憶體。簡單說明一下 `__bitmap_set`，運作原理。`bits_to_set` 是紀錄從 `start` 到下一個 unsigned long 前還需要設幾個 bit。然後 `mask_to_set` 就是等等要用來 set 第一段 ( 非對齊 ) 的遮罩。接著進入迴圈就是一次 set 整個 unsigned long，直到需要 set 的 bit 數量小於一個 unsigned long 的長度。跳出迴圈之後，做和一開始類似的事情，但只是這次是從 unsigned long 的頭開始 set。
:::info
提問:
還是不太理解為甚麼除了需要 IS_ALIGNED 之外 還需要 __builtin_constant_p 來判斷變數是否在編譯時期是常量
:8ball: eecheng87
:::
---
## 題目 `2`
### 解釋程式運作原理
#### 巨集 ( 挑幾個特別的說明 )
* `NEXT_POWER_OF_2`
如同名字所指，巨集的功能是在找大於傳入參數的最小的 $2^k$。將舉 2 個例子來解釋運作原理 :
* 若 k 為 $2^n$，透過巨集得到 $2^n$，因為 $(2^k - 1)\ \& \ 2^k$ 一定會得到 0，所以回傳自己。
* 若 k 非 $2^n$，則表示為 $2^{64-builtin\_clzl(k)}$。
* `v(t, s, name, ...)`
...表示可以傳入多個參數，再由 `__VA_ARGS__` 取得值，詳細用法可以參考[這裡](https://ithelp.ithome.com.tw/articles/10160393)。另外，`__attribute__((cleanup(vec_free)))`的用法表示當被形容的變數離開 block 時，會呼叫 `vec_free`，而參數是該變數的指標型態。
* `NON_NULL __attribute__((nonnull))`
確保被此特性描述的指標型態參數不為 NULL。
> [GCC Manual: Declaring Attributes of Functions](https://gcc.gnu.org/onlinedocs/gcc/Function-Attributes.html) )
:::warning
GCC 的 nonnull 屬性對於編譯器施加最佳化有益，可見 [The GCC nonnull attribute and compiler optimizations](http://rachid.koucha.free.fr/tech_corner/nonnull_gcc_attribute.html)
:notes: jserv
:::
:::danger
給定的 vector 實作存在若干嚴重疏失，例如:
1. `vec_pop_back` 沒進行例外處理;
2. 巨集 `v` 並未對給定的型態進行檢查，至少需要排除 `void` 和 `void *`
3. 記憶體配置策略不可靠;
你應該指出並討論改進方案。
:notes: jserv
:::
## 延伸問題
### 參照 `fbvector`
#### 記憶體配置策略
研讀 [folly/FBVector 文件](https://github.com/facebook/folly/blob/master/folly/docs/FBVector.md)，發現要優化 vector 的第一個步驟是替換掉原本 realloc 的大小，原版本 vector 一次會給現在大小的兩倍 (即 factor 為 `2`)。但是這樣的壞處是，每次 realloc 新的一塊總是會比以前 alloc 的總和還小，因為目前所有 alloc 的大小 $c\sum_{i = 0}^{n} 2^{i} = c\ (2^{n+1}-1)$ ，一定會小於接著要 realloc 的大小 $c \times 2^{n+1}$。
fbvector 選的 factor 是 1.5，他可以在第五次 realloc 時，重複利用之前 alloc 的記憶體。
```=
k = 1.5, c = 4
0123
012345
012345678
0123456789ABCD
0123456789ABCDEF0123
0123456789ABCDEF0123456789ABCD
0123456789ABCDEF0123456789ABCDEF
```
可以注意到第 6 行可以被前幾次已經拿到的記憶體容納下。
#### The jemalloc Connection
fbvector 會透過演算法判斷當下應該新配置多少記憶體
:::warning
可對照 [Deterministic Memory Allocation for Mission-Critical Linux](https://static.sched.com/hosted_files/ossna2017/cf/Deterministic%20Memory%20Allocation%20for%20Mission-Critical%20Linux.pdf)，在 2017 年我們進行一些實驗，記憶體配置的情境和對應策略組合，有著巨大的差異。
:notes: jserv
:::
### 新增 vector 經典操作
#### insert
```cpp
#define vec_insert(v, e, pos) \
__vec_insert(&v, &(__typeof__(v.buf[0])[]){e}, pos, vec_elemsize(v),\
vec_capacity(v))
static NON_NULL void __vec_insert(void *restrict vec,
void *restrict e,
size_t pos,
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, elemsize * (size_t)1 << ++v->capacity);
memcpy(&v->ptr[(pos + 1) * elemsize],
&v->ptr[pos * elemsize],
elemsize * ((v->size++) - pos));
memcpy(&v->ptr[pos * 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);
memcpy(tmp, v->buf, elemsize * pos);
memcpy(tmp + (pos + 1) * elemsize,
&v->buf[pos + 1], elemsize * ((v->size++) - pos));
v->ptr = tmp;
v->on_heap = 1;
memcpy(&v->ptr[pos * elemsize], e, elemsize);
} else{
memcpy(&v->buf[pos * elemsize], e, elemsize);
v->size++;
}
}
}
```
其實 insert 需要考慮的事和 `push_back` 幾乎一樣，我們需要先判斷出目前的 vector 在 heap 或是 stack，接著在判斷是否有足夠的空間塞入新元素。但是 insert 需要額外處理新元素的位置。我採用的方式是用 `memcpy` 直接把要插入的點以後的所有成員往後移一格，這種方式的優點是不用像最直覺的方式，一個成員一個一個移。不過這種方式會帶來的壞處就是隨著插入的位置越前面，你所需 copy 的成員將會越多，意味著越慢。
##### 實驗
簡單做個實驗，將新成員插入 0~9999 的位置，分別紀錄時間。嘗試應證上方所言，插入的點越前面，速度越慢：
```cpp
// experiment
v(char, 3, v1);
for (int i = 0; i < 10000; i++)
vec_push_back(v1, 98);
for(int i = 0; i < 10000; i++){
clock_gettime(CLOCK_REALTIME, &t1);
vec_insert(v1,'a',i);
clock_gettime(CLOCK_REALTIME, &t2);
printf("%d %ld\n",i,elapse(t1,t2));
vec_erase(v1,i);
}
```
透過 gnuplot 作圖：
整體來說符合預期，速度和位置大小成反比。
#### erase
這個操作同樣也需要位移一堆連續的成員，已達到刪除的效果，最後記得更新變數 `size`。
```cpp
if (v->on_heap) {
memcpy(&v->ptr[pos * elemsize],
&v->ptr[(pos + 1) * elemsize],
(v->size - pos - 1) * elemsize);
} else {
memcpy(&v->buf[pos * elemsize],
&v->buf[(pos + 1) * elemsize],
(v->size - pos - 1) * elemsize);
}
v->size--;
```
同樣也可觀測到，刪除的位置和時間有關係。
另外，我們再來觀察看看若用 C++ 標準函式庫提供的 [std::vector](https://en.cppreference.com/w/cpp/container/vector) 來刪除成員，是否也會和我們實做的產生類似的結果。
#### 實驗
```cpp
vector <char> v1;
struct timespec t1, t2;
for(int i = 0; i < 10000; i++)
v1.push_back('b');
for(int i = 0; i < 10000; i++){
v1.insert(v1.begin(),'a');
clock_gettime(CLOCK_REALTIME, &t1);
v1.erase(v1.begin()+i);
clock_gettime(CLOCK_REALTIME, &t2);
cout<<i<<" "<<elapse(t1,t2)<<"\n";
}
```
看來 c++ 刪除元素的速度也是會受到位置的影響。不過我在這裡偶然注意到一件事，似乎 c++ 在同樣操作的速度下和 c 相比，慢蠻多的。於是，我進一步的來驗證看看。
接著我們再設計一個實驗，分別用 C 和 C++ 來執行四種操作一千次，分別是 `push_back`, `insert`, `erase` 和 `pop_back`。然後紀錄每次操作的時間，程式碼如下：
```cpp
for (int i = 0; i < 1000; i++){
clock_gettime(CLOCK_REALTIME, &t1);
v1.push_back('b');
clock_gettime(CLOCK_REALTIME, &t2);
cout << i << " " << elapse(t1, t2) << "\n";
}
..
for(int i = 3000; i < 4000; i++){
clock_gettime(CLOCK_REALTIME, &t1);
v1.pop_back();
clock_gettime(CLOCK_REALTIME, &t2);
cout << i << " " << elapse(t1, t2) << "\n";
}
```
將結果用 gnuplot 展示：
很明顯的可以看出，C 版本 (我改進的實做) 的 insert 和 erase 速度比 C++ 標準函式庫提供的 [std::vector](https://en.cppreference.com/w/cpp/container/vector) 還快。接著把另外兩個操作放大來看。
也可以發現 C 版本的操作會比較快。
:::warning
TODO: 研讀 Linux 核心原始程式碼 [flexible arrays](https://www.kernel.org/doc/Documentation/flexible-arrays.txt) 的設計和實作
:notes: jserv
:::
### 補充
因老師要求，開始研讀 [flexible arrays](https://www.kernel.org/doc/Documentation/flexible-arrays.txt) 的設計和實作。
首先在 `flex_array.h` 中觀察結構 `flex_array`:
```cpp
struct flex_array {
union {
struct {
int element_size;
int total_nr_elements;
int elems_per_part;
u32 reciprocal_elems;
struct flex_array_part *parts[];
};
char padding[FLEX_ARRAY_BASE_SIZE];
};
};
```
除了一些功能很明顯的變數外，`padding` 主要的功能是結合 union 特性，來限制這個結構大小在 1 個 page。
而因為 `flex_array` 中的 flex，所以我猜這個陣列應該有類似 vector 能自動伸縮的功能，接著打開 .c 檔案來看各種操作的實作。
首先看到函數 `flex_array_alloc`:
```cpp
struct flex_array *ret;
int max_size = FLEX_ARRAY_NR_BASE_PTRS *
FLEX_ARRAY_ELEMENTS_PER_PART(element_size);
/* max_size will end up 0 if element_size > PAGE_SIZE */
if (total > max_size)
return NULL;
ret = kzalloc(sizeof(struct flex_array), flags);
if (!ret)
return NULL;
ret->element_size = element_size;
ret->total_nr_elements = total;
if (elements_fit_in_base(ret) && !(flags & __GFP_ZERO))
memset(&ret->parts[0], FLEX_ARRAY_FREE,
FLEX_ARRAY_BASE_BYTES_LEFT);
return ret;
```
這個函數在做的事基本上就是重新拿一塊新的 `flex_array` 然後把成員變數填一填。這裡面值得注意的是 `kzalloc`，這是在 kernel mode 下請求記憶體需要呼叫的函數。和 `vmalloc` 的差異是在前者只能拿 1 個 page 以內的記憶體，超過就要用後者。
接著來看 `flex_array_put`:
```cpp
int part_nr = fa_element_to_part_nr(fa, element_nr);
struct flex_array_part *part;
void *dst;
if (element_nr >= fa->total_nr_elements)
return -ENOSPC;
if (elements_fit_in_base(fa))
part = (struct flex_array_part *)&fa->parts[0];
else {
part = __fa_get_part(fa, part_nr, flags);
if (!part)
return -ENOMEM;
}
dst = &part->elements[index_inside_part(fa, element_nr)];
memcpy(dst, src, fa->element_size);
return 0;
```
這個函數的功能有點像 vector 的 push。把你需要加入的資料 ( src ) 插入 flex_array 中。如果 src 的大小沒有超過 array ( 第 2 個 if statement )，理所當然可以塞入，但是我真正關心的是另外一種狀況，我想知道所謂的 **flex** array 當塞入超過原本範圍限制的資料會做甚麼應對。
首先解釋第 1 個 if statement，可以發現 `if (element_nr >= fa->total_nr_elements)` 就是當 src 大小超過 array 的邊界 ( 無法 append )，條件為真，會回傳一個 error code。把問題丟回去給上層使用者 ( 呼叫 put 的人 )，因為這是一個不合理的呼叫。
但反觀最後的 else block，這個是當要插入到目前最後一個資料的後面，會呼叫 `__fa_get_part`:
```cpp
if (!part) {
part = kmalloc(sizeof(struct flex_array_part), flags);
if (!part)
return NULL;
if (!(flags & __GFP_ZERO))
memset(part, FLEX_ARRAY_FREE,
sizeof(struct flex_array_part));
fa->parts[part_nr] = part;
}
```
而 `__fa_get_part` 中果然幫我們新拿了一塊記憶體 (kmalloc)，做了伸長的動作 (flexible)。
提問:
1. 除了可以 shrink 和可以做類似 push_back() 功能之外，這樣和一般的 array 對比之下還有其他能稱得上 flex 的地方嗎 ?
2. 我搜尋過 linux 專案底下，沒找到有呼叫過這個函數的檔案，在 google 上也沒找到使用的實例。flex_array 真的有存在的必要?那會是怎麼樣的情境?
:::info
[Open vSwitch](https://www.openvswitch.org/) 用到 flex_array，見 [datapath: remove flex_array](https://mail.openvswitch.org/pipermail/ovs-dev/2016-July/319379.html) (2016):
> "flex_array is already present on Linux 3.10, so there is no need for its backport anymore."
但之後就移除了，見 [datapath: convert to kvmalloc](https://lists.linuxfoundation.org/pipermail/ovs-dev/2019-March/357628.html) (2019)
> "There was no real need for this code to be using flexarrays, it's just implementing a hash table - ideally it would be using rhashtables, but that conversion would be significantly more complicated."
這個案例說明 Linux 核心 (及生態系統，如上述的 Open vSwitch) 一直反思專案內部設計，不合時宜的設計會被取代。
也可嘗試對 LKML 提交改寫 flex_array 的修改。
:notes: jserv
:::
Sign in with Wallet
Connect another wallet