linux2021: OscarShiang

測驗

$\alpha -1$

舉出 Linux 核心原始程式碼裡頭 bit rotation 的案例並說明

首先在 Linux source code include/linux/bitops.h 可以看到關於 bitops 的實作

這邊以 8 bit 的實作舉例：

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 的 __jhash_mix() 可以看到使用 rol32 將 a, b, c 三組數字進行混合，進而減少算出的 hash 值碰撞的機率。

#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 指令。

不能只有「認為有機會」，證明！

jserv

我在 Intel-based Mac 上面使用 gcc 搭配 -O1 編譯以下的程式碼：

#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;
}

這邊不將 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$

說明上述程式碼的運作原理

這段程式碼共可以分為兩個部分

power of 2 的翻譯是「2 的冪」，而非「冪次」

jserv

• 給定 alignment 的數值不是 2 的冪

  如果不是 2 的冪，只要數值換成 alignment 的倍數即可，所以當 sz 是 alignment 的倍數時， (sz + mask) / alignment == (sz + mask) / alignment 所以得到的即是本身；但是如果 sz 不是 alignment 的倍數時，就會算成大於 sz 且最接近的 alignment 的倍數。

• 給定 alignment 的數值是 2 的冪

  這邊的做法其實與上述的作法類似，但是因為 2 的冪可以利用 mask 直接去除 sz % alignment 的部分，因此寫法就會變成

  ​​​​(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