# 2022q1 Homework4 (quiz4)
contributed by < `ccs100203` >
###### tags: `linux2022`
> [第 4 週測驗題](https://hackmd.io/@sysprog/linux2022-quiz4)
<!-- ## 測驗 1 -->
<!--
偷懶 ><
太多進度要趕Q
```cpp
int ceil_log2(uint32_t x)
{
uint32_t r, shift;
x--;
r = (x > 0xFFFF) << 4;
x >>= r;
shift = (x > 0xFF) << 3;
x >>= shift;
r |= shift;
shift = (x > 0xF) << 2;
x >>= shift;
r |= shift;
shift = (x > 0x3) << 1;
x >>= shift;
return (EXP1) + 1;
}
```
EXP1: r | shift | x >> 1
-->
<!-- ---
## 測驗 2 -->
<!--
```cpp
#define BITS_PER_BYTE 8
#define BITS_PER_LONG (sizeof(unsigned long) * BITS_PER_BYTE)
#include <stddef.h>
static inline size_t ffs(unsigned long x)
{
if (x == 0)
return 0;
size_t o = 1;
unsigned long t = ~0UL;
size_t shift = BITS_PER_LONG;
shift >>= 1;
t >>= shift;
while (shift) {
if ((EXP2) == 0) {
x >>= shift;
EXP3;
}
shift >>= 1;
t >>= shift;
}
return o;
}
```
EXP2: x & t
EXP3: o += shift
-->
<!-- ---
## 測驗 3
---
## 測驗 4 -->
---
## 測驗 5
`READ_ONCE`為防止編譯器做相關最佳化工作的 macro，以下程式碼是 `READ_ONCE` 可能的實作
```cpp
#include <stdint.h>
#include <string.h>
#include <stdlib.h>
#define __READ_ONCE_SIZE \
({ \
switch (size) { \
case 1: \
*(uint8_t *) res = *(volatile uint8_t *) p; \
break; \
case 2: \
*(uint16_t *) res = *(volatile uint16_t *) p; \
break; \
case 4: \
*(uint32_t *) res = *(volatile uint32_t *) p; \
break; \
case 8: \
*(uint64_t *) res = *(volatile uint64_t *) p; \
break; \
default: \
memcpy((void *) res, (const void *) p, size); \
} \
})
static inline void __read_once_size(const volatile void *p, void *res, int size)
{
__READ_ONCE_SIZE;
}
#define READ_ONCE(x) \
({ \
union { \
typeof(x) __val; \
char __c[1]; \
} __u; \
__read_once_size(&(x), __u.__c, sizeof(x)); \
__u.__val; \
})
```
### 解釋程式碼原理
`READ_ONCE` 巨集先在傳入 `__read_once_size` 時將參數轉型成 `void *`，限制傳入的參數是 scalar type，然後在存取前轉換為 `volatile uint64_t *` 等等包含 `volatile` 的型態，就可以避免編譯器對其進行優化。
可以看到 `void *res` 就是將 `__c` 轉型後傳入的變數，因為 union 內的記憶體位置相同，所以在 `__read_once_size` 內改動 `res` 的值，就會相對應的改到 `__val` 上，所以程式就是借此將 `x` 的值複製到 `__val` 中，並作為回傳值。
### 如果 `sizeof(__c)` > `sizeof(__val)`
這裡是用 `char` 也就是 `uint8_t` 作為 `__c` 的型態，使用 `uint8_t` 到 `uint64_t` 中最小的型態可以避免 union 佔用多餘的空間，也可以避免 array 的範圍超過傳入的 `__val` 的大小。
假設 union 是下列情況:
```cpp
union {
uint8_t __val;
uint16_t __c[1];
} __u;
```
此時的 `sizeof(__c)` > `sizeof(__val)`，在之後對 `res` 操作會有一定的風險，因為 `__val` 只佔 `__c` 的 1 byte 而已，有可能在對 `__c` 存取後卻沒更新到 `__val` 上。
不過其實在 little endian 的情況下是不會有問題的，因為 `__val` 對齊在 `__c` 從 LSB 開始的 1 byte，所以更新 `__c` 時還是可以同時改到 `__val` 上，但如果是在 big endian 上的機器上，我想就會發生沒有更新到 `__val` 的情況。
- 0x01234567 會如下圖所示
### 如果把 `char __c[1]` 改成 `char *__c`
如果把 `char __c[1]` 改成 `char *__c`，程式的執行結果會是錯誤的。
因為 `*__c` 會把它記憶體位置上所放的值當作 address 使用 (也就是指向該 address)，所以在對 `res` 操作時，改到的會是該指標所指向的位置，而不是 union 的記憶體位置，所以 `__val` 不會得到正確的結果。
#### 在 gdb 中的測試結果
- 使用 `char __c[1]`
- original value `x`: 0xf3f
- return value of `READ_ONCE(x)`: 0xf3f
| | addr. of union | __val |__c|dereference on __c|
| -------- | -------- | -------- | -|-|
| before `__read_once_size` | 0x7fffffffdc10 | 0x7fffffffdd10 |0x7fffffffdc10|0x10|
| after `__read_once_size` | 0x7fffffffdc10 | 0xf3f |0x7fffffffdc10|0x3f|
<!--  -->
:::warning
文字訊息不要用圖片來展現！
:notes: jserv
:::
:::info
2022/03/19 已修改
:::
union 的位置是 0x7fffffffdc10，在進入 `__read_once_size` 之前，union 上放著一個 uninitialized value 0x7fffffffdd10，此時印出 `*__c`，會是印出 0x7fffffffdd10 的最後一個 byte 0x10。(因為 `__c` 是 1 byte)
在做完 `__read_once_size` 後，已經將 `x` 的值 0xf3f 放到 `__val` 上，此時印出 `*__c`，會是印出 0xf3f 的最後一個 byte 0x3f，再來程式就會將 `__val` 回傳回去並得到 0xf3f。
- 使用 `char *__c`
- original value `x`: 0xf3f
- return value of `READ_ONCE(x)`: 0xffffdd10
| | addr. of union | __val |__c|dereference on __c|
| -------- | -------- | -------- | -|-|
| before `__read_once_size` | 0x7fffffffdc10 | 0x7fffffffdd10 |0x7fffffffdd10|0x1|
| after `__read_once_size` | 0x7fffffffdc10 | 0x7fffffffdd10 |0x7fffffffdd10|0x3f|
<!--  -->
union 的位置與一開始放在 union 內的值和上面相同，但可以發現在 `*__c` 會得到不同的結果。
`*__c` 會指向內容尚未初始化的地址 `0x7fffffffdd10`，所以在印出 dereference 的結果時會是印出 0x7fffffffdd10 上目前的值 0x1。
而在做完 `__read_once_size` 後，因為 `*res` 內含值存於記憶體地址 0x7fffffffdd10，所以可以看到 `__val` 上的值仍然沒變，變的是記憶體位置 0x7fffffffdd10 上的值，這樣在最後回傳 `__val` 時就會得到錯誤的結果。
### 用 `memcpy` 避免編譯器做了非預期的最佳化
好奇為什麼用 `memcpy` 可以避免編譯器進行優化，雖然還沒找到相關說明，不過有找到在 linux 的 [xdp_sample.bpf.h](https://elixir.bootlin.com/linux/latest/source/samples/bpf/xdp_sample.bpf.h#L89) 中某一種實作 `__read_once_size` 的方式，他是用
`asm volatile ("" : : : "memory")` 去設置 compiler barrier，避免其進行優化。
- 節錄 switch default 中的部份 code
```cpp
default:
asm volatile ("" : : : "memory");
__builtin_memcpy((void *)res, (const void *)p, size);
asm volatile ("" : : : "memory");
}
```
### [Why the “volatile” type class should not be used](https://docs.kernel.org/process/volatile-considered-harmful.html)
在使用 `volatile` 的情況下，該變數也必須要有 atomic 的性質，所以就必須透過一些 lock 去進行保護，既然已經需要使用 lock，那麼在適當使用 spinlocks, mutexes, memory barriers 等保護 critical section 的機制下，其實就可以捨去 `volatile`。
> In properly-written kernel code, `volatile` can only serve to slow things down.
在正確撰寫的 kernel code 中，`volatile` 只會有負面效果，像是導致執行速度變慢。
#### `volatile` on spin_lock
- 參考以下的 code:
```cpp
spin_lock(&the_lock);
do_something_on(&shared_data);
do_something_else_with(&shared_data);
spin_unlock(&the_lock);
```
假設現在有一個 `share_data`，雖然 compiler 認為他知道 `share_data` 的值並想要進行優化，但他可以透過 `share_data` 被 `spin_lock` 保護這件事得知這個變數可能會被其他程式修改，所以 compiler 就會跳過對 `share_data` 的優化。那既然已經需要使用 lock，compiler 也會在看到 lock 時就避免優化，那自然可以省去使用 `volatile`。
#### `volatile` on memory-mapped I/O registers
`volatile` 一開始設計的目的是為了 memory-mapped I/O registers，在 kernel 中， register accesses 同樣是需要被 lock 保護的。但因為並不是所有架構都能直接透過 pointer 直接存取 I/O memory，所以 I/O memory accesses 總是會透過呼叫 accessor functions 來進行，那麼就可以用 lock 對其保護，而不需要 `volatile`。
#### `volatile` on busy-waiting
- 參考以下的 code:
```cpp
while (my_variable != what_i_want)
cpu_relax();
```
或許程式撰寫者會想要在等待 `busy-waiting` 時加上 `volatile`，但因為 `cpu_relax()` 會做 lower CPU power 或 yield 等動作，這其實就等同於做了 compiler barrier，所以不需要使用 `volatile`。
#### 仍然可以使用 `volatile` 的情況
- The above-mentioned accessor functions might use `volatile` on architectures where direct I/O memory access does work
> 前面提到的 access function，在可以直接存取 I/O memory 的情況下可能需要使用 `volatile`，因為每次的 accessor call 都是一個小小的 critical section。
- Inline assembly code which changes memory, but which has no other visible side effects, risks being deleted by GCC. Adding the `volatile` keyword to asm statements will prevent this removal.
> 一段會改變 memory 的 Inline assembly code，當他沒有任何 side effects 時，GCC 可能會直接將其刪除，所以需要透過加入 `volatile` 去保護他。
- The jiffies variable is special in that it can have a different value every time it is referenced, but it can be read without any special locking. So jiffies can be `volatile`.
> 每次存取的值都會改變的變數稱為 jiffies，因為這不需要 lock 就可以直接存取，所以要用 `volatile` 進行保護，但 Linus 說這是 Linux 中的 "stupid legacy"。
- Pointers to data structures in coherent memory which might be modified by I/O devices can, sometimes, legitimately be `volatile`.
> 如果一個指向 coherent memory 內的資料結構的 pointer，可能被 I/O devices 更改的話，可以合法的加入 `volatile`。像是網路卡中的 ring buffer，網卡會改變裡頭的 pointer 去紀錄存取的位置。
#### Side effects
根據 C11 5.1.2.3/2 中定義 side effects
> Accessing a volatile object, modifying an object, modifying a file, or calling a function that does any of those operations are all side effects, which are changes in the state of the execution environment.
可以簡單將 side effects 分類為:
- accessing a `volatile` variable
- modifying any variable
- writing to a file
而前面提到的 inline assembly code 可能被優化，可以參考 C11 5.1.2.3/4
> In the abstract machine, all expressions are evaluated as specified by the semantics. An actual implementation need not evaluate part of an expression if it can deduce that its value is not used and that no needed side effects are produced (including any caused by calling a function or accessing a volatile object).
若是一個 implementation 沒有 side effects，那麼就不用被視為一個 expression，也可以直接推斷出他的值。
> 參考 [What is side effect in C?](https://stackoverflow.com/questions/62148339/what-is-side-effect-in-c)
#### 結尾
文章最後提到，現在繳交的 patch 若有使用 `volatile` 的話，容易被當成 bug，且會受到額外的審查。
現在非常歡迎協助刪除 `volatile` 的 patch，但要確保有仔細思考過裡頭的 concurrency issues。
### [ACCESS_ONCE() and compiler bugs](https://lwn.net/Articles/624126/)
TODO
Sign in with Wallet
Connect another wallet