# linux2021: fwfly
> [題目描述](https://hackmd.io/@sysprog/linux2021-summer-quiz)
> [作答 github](https://github.com/fwfly/2021_summer)
## 測驗 $\alpha$
透過 gcc 展開 macro 會得到以下結果
```cpp=
static inline uint8_t rotl8(const uint8_t v, int c) {
const int mask = (8) - (1);
c &= mask;
return (v << c) | LLL;
};
```
mask 是避免使用者輸入 > bits 數的數字，同時可以省掉一個 if
如果沒有 mask ，就需要用 if 寫成這樣
```cpp
// 假設是 8 bits;
// 數字7 是因為如果位移 8 bits 就等於沒有做 rotate
if (c > 7)
c = 7
```
### LLL 跟 RRR
```cpp=
LLL = (v >> (bits-c))
RRR = (v << (bits-c))
```
以 184 (隨機選的 8bits 數字)為例
184 的 bits 是 : 10111000
假設向左 rotate 2 個 bits
(v << c) 會變成 111000
那最前面的 10 會移到最後面變成 000000 10
假設向左 rotate 4 個 bits
最前面的 1011 會移到最後面變成 0000 1011
假設向左 rotate 6 個 bits
最前面的 101110 會移到最後面變成 00 101110
透過觀察可以看到， overflow 的部分其實是等同於做反向的 shift
而這個 bits 數會是最大 bits 減去使用者輸入的數字
所以答案是 (v <反向> (bits-c))
#### 處理 c 等於 0
根據[文章](https://blog.regehr.org/archives/1063)表示，這樣的寫法需要去處理額外 0 的部分，因為當 rotate 為 0 時，bits 會全部 rotate 一輪，這樣會有額外運算．所以用個 if 去判斷是否為 0，不過這樣在 assembly 就會產生 branch
#### no branch 解法
答案
```cpp
LLL = (v >> (-c&mask))
RRR = (v << (-c&mask))
```
要理解這樣的方式，需要先理解補數: [解讀計算機編碼-計算機為何如此編碼](https://hackmd.io/@sysprog/binary-representation?type=view#%E8%A8%88%E7%AE%97%E6%A9%9F%E7%82%BA%E4%BD%95%E5%A6%82%E6%AD%A4%E7%B7%A8%E7%A2%BC)
### reference
* https://blog.regehr.org/archives/1063
## 測驗 β
```cpp
static inline uintptr_t align_up(uintptr_t sz, size_t alignment)
{
uintptr_t mask = alignment - 1;
if ((alignment & mask) == 0) { /* power of two? */
return MMM;
}
return (((sz + mask) / alignment) * alignment);
}
```
uintptr_t : 任意數字
alignment : 要對齊的數字
假設要對齊的數字是 4
那輸入的數字跟相對應的結果就會如以下
```
1 -> 4
2 -> 4
3 -> 4
4 -> 4
5 -> 8 (需要用兩個 4 來做對齊)
6 -> 8
..
...
```
關於 memory alignment 可以參考以下文章
[memory alignment](http://opass.logdown.com/posts/743054-about-memory-alignment)
### MMM
```cpp
(sz + mask) & ~mask;
```
### 解說
參考來自 boost source code 1.68.0 : https://www.boost.org/doc/libs/1_68_0/boost/align/align_up.hpp
如果是 power of 2 , 假設 alignment 為 8
可以把
```cpp
(((sz + mask) / alignment) * alignment)
```
看成
```cpp
// 因為 8 是 2 的 3 次方
(((sz + mask) >> 3) << 3)
```
簡單來說就會是對後面 3 個 bits 直接清 0
如果是後面 3 個 bits 清成 0 則可以產生類似這樣的 mask (假設為 mask0)
```
111111....1111000
```
mask0 則會等於 alignment 減一 再取個 not
```
aliment -1 = ...00001000 - 1 = ...0000 0111
```
再取個 not
```
~(aliment -1) = ~(...0000 0111) = ...1111 1000
```
這樣就可以完成新的 mask0 然後去做 alignment.
## 測驗 γ
```cpp
#include <stdio.h>
#include <unistd.h>
int main(void)
{
for (int i = 0; i < NNN; i++) {
fork();
printf("-");
}
fflush(stdout);
return 0;
}
```
先要理解 fork 跟 fflush 怎麼運作
### NNN
透過測試的結果是 12
### 解說
依照這篇 [stackoverflow](https://unix.stackexchange.com/questions/447898/why-does-a-program-with-fork-sometimes-print-its-output-multiple-times) 上面說的，兩個情形照成多印出來的狀況
1. printf 是先被 buffer 住的，等到碰到 `\n` 再印出 或 flush(清空)
2. fork 是會把 buffer 的狀態也一併作 copy, 所以如果在 fork 前 print, print 的內容也會一併的被 copy
不過以上的說法還需要實際驗證，但跟目前輸出的情形雷同
```
To do : 輸出結果
```
### To do-實驗
### reference
* https://code.woboq.org/userspace/glibc/stdio-common/vfprintf-internal.c.html#1244
# 測驗 δ
### AAA
```cpp
queue->last->next = node;
```
AAA 是在 con_push 裡面．
這個 function 是把新的值加到 queue 裡面，
AAA 的部分則是把 node 加到 queue 的後面
### BBB 跟 CCC
BBB 跟 CCC 是在 con_pop 裡面
這個 function 主要是從 queue 中 pop 一個數字
BBB 是把值給 return_value
CCC 則是做移動 first 的部分
```cpp
/* Queue not empty: retrieve data and rewire */
void *return_value = node->value; // BBB
queue->first = new_header; // CCC
```
## 測驗 ϵ
### XXX
```cpp
x = x + 1;
```
iceil2 這個 function 主要是在找最高位的 bit
策略就是把高位的 bits 1 複製到低位的 bit 讓數字變成全部都是1
最後再 + 1 進行進位，來找到 ceil
所以以下的過程是在進行一個 bits 複製的動作
```
x = x - 1;
x = x | (x >> 1);
x = x | (x >> 2);
x = x | (x >> 4);
x = x | (x >> 8);
x = x | (x >> 16);
```
以 4097 為例
首先先減 1 變為 4096, 然後進行最前面第一個 bit 複製
先 shit 1 得到要複製的 bit
```
x = 4096
1 0000 0000 0000
0 1000 0000 0000 // x >> 1
---------------- // use or
1 1000 0000 0000
```
因為已經有兩個 bits 了所以直接複製兩個
```
1 1000 0000 0000
0 0110 0000 0000 // x >> 2
---------------- // use or
1 1110 0000 0000
```
現在有 4 個 bits 所以可以直接複製 4 個
```
1 1110 0000 0000
0 0001 1110 0000 // x >> 4
---------------- // use or
1 1111 1110 0000
```
因為有 8 個 bits 為 1 了，所以可以一次複製 8 個
```
1 1111 1110 0000
0 0000 0001 1111 // x >> 8
---------------- // use or
1 1111 1111 1111
```
16個的結果是一樣的，所以不變，最後再做 +1 來取得 ceil (天花板)
```
01 1111 1111 1111
00 0000 0000 0001 // 1
---------------- // use +
10 0000 0000 0000
```
所以就會得到 8192
### YYY
```cpp
*ip = mp->hs[i];
```
答案來自這個 [github repo](https://github.com/silentbicycle/mpool/blob/master/mpool.c#L240)
透過 gdb 可以知道 mp->hs[i] 會被換成 p 的 address
然後新的 address 的 value 會是原本的 address
```cpp
Breakpoint 1, mpool_repool (mp=0x55555555a6b0, p=0x7ffff7ffb6c0, sz=60) at mpool.c:217
217 *ip = mp->hs[i]; //YYY
(gdb) p mp->hs[i]
$2 = (void *) 0x7ffff7fc8070
(gdb) n
218 assert(ip);
(gdb) n
219 mp->hs[i] = ip;
(gdb) n
220 }
(gdb) p mp->hs[i]
$3 = (void *) 0x7ffff7ffb6c0 //換成 0x7ffff7ffb6c0
(gdb) x 0x7ffff7ffb6c0
0x7ffff7ffb6c0: 0xf7fc8070 // 原本的 address
```
經過幾輪的 repool 再透過 x 去 dump memory
可以發現前幾輪的 memory address 裡面的值是之前的 address
```cpp
Breakpoint 1, mpool_repool (mp=0x55555555a6b0, p=0x7ffff7ffb700, sz=33) at mpool.c:217
217 *ip = mp->hs[i]; //YYY
(gdb) p mp->hs[i]
$4 = (void *) 0x7ffff7ffb6c0
(gdb) x 0x7ffff7ffb6c0
0x7ffff7ffb6c0: 0xf7fc8070
(gdb) n
218 assert(ip);
(gdb) n
219 mp->hs[i] = ip;
(gdb) n
220 }
(gdb) p mp->hs[i]
$5 = (void *) 0x7ffff7ffb700
(gdb) x 0x7ffff7ffb700
0x7ffff7ffb700: 0xf7ffb6c0
(gdb) x 0x7ffff7ffb6c0
0x7ffff7ffb6c0: 0xf7fc8070
```
但是再多做幾輪就會發現前幾次 address 中的直變成 9 (這邊我把程式的 p 從 7 改成 9)
```cpp
Breakpoint 1, mpool_repool (mp=0x55555555a6b0, p=0x7ffff7ffbb00, sz=46) at mpool.c:217
217 *ip = mp->hs[i]; //YYY
(gdb) p mp->hs[i]
$6 = (void *) 0x7ffff7fc80c0
(gdb) x 0x7ffff7fc80c0
0x7ffff7fc80c0: 0xf7fc80d0
(gdb) n
218 assert(ip);
(gdb) n
219 mp->hs[i] = ip;
(gdb) n
220 }
(gdb) x 0x7ffff7ffbb00
0x7ffff7ffbb00: 0xf7fc80c0
(gdb) x 0x7ffff7fc8070
0x7ffff7fc8070: 0x00000009 // 9
(gdb) x 0x7ffff7ffb6c0
0x7ffff7ffb6c0: 0x00000009 // 9
```
### Reference
* http://graphics.stanford.edu/~seander/bithacks.html#RoundUpPowerOf2
## 測驗 ζ
LLL 跟 JJJ 是設定 poll 的 fd 跟要觸發的 events
以題目為例是只設定 POLLIN
然後從這段程式碼可以知道 pollsp[0] 是放 cl_fd
```cpp
int from_client = polls[0].revents & POLLIN;
if (from_client)
move(cl_fd, target_fd, fds);
else
move(target_fd, cl_fd, fds);
```
所以答案如下
```cpp
struct pollfd polls[2] = {
[1] = {.fd = target_fd, .events = POLLIN}, // lll
[0] = {.fd = cl_fd, .events = POLLIN}, // JJJ
};
```
Sign in with Wallet
Connect another wallet