# linux2021: OscarShiang ## 測驗 $\alpha-1$ > 舉出 Linux 核心原始程式碼裡頭 bit rotation 的案例並說明 首先在 Linux source code [`include/linux/bitops.h`](https://elixir.bootlin.com/linux/latest/source/include/linux/bitops.h#L86) 可以看到關於 bitops 的實作 這邊以 8 bit 的實作舉例： ```c static inline __u8 rol8(__u8 word, unsigned int shift) { return (word << (shift & 7)) | (word >> ((-shift) & 7)); } static inline __u8 ror8(__u8 word, unsigned int shift) { return (word >> (shift & 7)) | (word << ((-shift) & 7)); } ``` 而在 [`/tools/testing/selftests/bpf/progs/test_jhash.h`](https://elixir.bootlin.com/linux/latest/source/tools/testing/selftests/bpf/progs/test_jhash.h#L14) 的 `__jhash_mix()` 可以看到使用 `rol32` 將 `a`, `b`, `c` 三組數字進行混合，進而減少算出的 hash 值碰撞的機率。 ```c #define __jhash_mix(a, b, c) \ { \ a -= c; a ^= rol32(c, 4); c += b; \ b -= a; b ^= rol32(a, 6); a += c; \ c -= b; c ^= rol32(b, 8); b += a; \ a -= c; a ^= rol32(c, 16); c += b; \ b -= a; b ^= rol32(a, 19); a += c; \ c -= b; c ^= rol32(b, 4); b += a; \ } ``` ## $\alpha-2$ > x86_64 指令集具備 rotr 和 rotl 指令，上述 C 程式碼經過編譯器最佳化 (例如使用 gcc) 後，能否運用到這二個指令呢？ 我認為有機會。但是應該只會發生在使用操作 32 位元或是 64 位元的資料時，因為指令集並不支援小於 32 位元以下數值的 rotate 指令。 :::warning 不能只有「認為有機會」，證明！ :notes: jserv ::: 我在 Intel-based Mac 上面使用 gcc 搭配 `-O1` 編譯以下的程式碼： ```c #include <stdio.h> #include <stdint.h> int main(int argc, char *argv[]) { uint32_t a = 0x1; uint32_t b; scanf("%d\n", &b); a = (a >> b) | (a << (32 - b)); printf("%d\n", a); return 0; } ``` :::info 這邊不將 `b` 設定為常數是因為 gcc 會直接計算出最後 a 的數值而不會產生 rotate 的指令 ::: 經過反組譯可以發現在 `0x100003f63` 的位址有 `rorl` 指令的存在： ``` test`main: test[0x100003f40] <+0>: pushq %rbp test[0x100003f41] <+1>: movq %rsp, %rbp test[0x100003f44] <+4>: pushq %rbx test[0x100003f45] <+5>: pushq %rax test[0x100003f46] <+6>: leaq 0x5b(%rip), %rbx ; "%d\n" test[0x100003f4d] <+13>: leaq -0xc(%rbp), %rsi test[0x100003f51] <+17>: movq %rbx, %rdi test[0x100003f54] <+20>: xorl %eax, %eax test[0x100003f56] <+22>: callq 0x100003f7e ; symbol stub for: scanf test[0x100003f5b] <+27>: movb -0xc(%rbp), %cl test[0x100003f5e] <+30>: movl $0x1, %esi test[0x100003f63] <+35>: rorl %cl, %esi <= rotate intruction test[0x100003f65] <+37>: movq %rbx, %rdi test[0x100003f68] <+40>: xorl %eax, %eax test[0x100003f6a] <+42>: callq 0x100003f78 ; symbol stub for: printf test[0x100003f6f] <+47>: xorl %eax, %eax test[0x100003f71] <+49>: addq $0x8, %rsp test[0x100003f75] <+53>: popq %rbx test[0x100003f76] <+54>: popq %rbp test[0x100003f77] <+55>: retq ``` ## $\beta-1$ > 說明上述程式碼的運作原理 這段程式碼共可以分為兩個部分 :::warning power of 2 的翻譯是「2 的冪」，而非「冪次」 :notes: jserv ::: - 給定 `alignment` 的數值**不是** 2 的冪 如果不是 2 的冪，只要數值換成 `alignment` 的倍數即可，所以當 `sz` 是 `alignment` 的倍數時， `(sz + mask) / alignment` == `(sz + mask) / alignment` 所以得到的即是本身；但是如果 `sz` 不是 `alignment` 的倍數時，就會算成大於 `sz` 且最接近的 `alignment` 的倍數。 - 給定 `alignment` 的數值是 2 的冪 這邊的做法其實與上述的作法類似，但是因為 2 的冪可以利用 mask 直接去除 `sz % alignment` 的部分，因此寫法就會變成 ```c (sz + mask) & (~mask) ``` ## $\gamma$ > 解釋上述程式碼輸出 `-` 字元數量的原理 因為 for 迴圈所使用的變數是區域變數，所以對於每個新 `fork()` 產生的執行緒而言，他們都需要印出 `NNN` 個 `-`，而在執行過程中總共會產生出的執行緒共是 $2^{NNN}$ 個 因此若假設迴圈總共執行 $n$ 次的話， `-` 的個數就會是 $2^n \times n$ 而題目給定的 `49152` 根據上述的推論可以轉換成下列的形式 $$ 49152 = 2 ^ {12} \times 12 $$ 所以可知 `NNN` 即是 `12` ## $\zeta-1$ > 解釋上述程式碼運作原理 這段程式碼的作用就是以 proxy 作為兩個伺服器的中介人並進行資料互傳。 因此 `proxy()` 在做的就是利用 `poll` 監聽 `target_fd` 與 `cl_fd` 兩者，當其中一方要傳送資料的時候，就使用 splice 進行對傳。 ###### tags: `linux2021`