linux2021: fwfly

題目描述
作答 github

測驗

$\alpha$

透過 gcc 展開 macro 會得到以下結果

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 寫成這樣

  // 假設是 8 bits; 
  // 數字7 是因為如果位移 8 bits 就等於沒有做 rotate
  if (c > 7) 
    c = 7

LLL 跟 RRR

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

根據文章表示，這樣的寫法需要去處理額外 0 的部分，因為當 rotate 為 0 時，bits 會全部 rotate 一輪，這樣會有額外運算．所以用個 if 去判斷是否為 0，不過這樣在 assembly 就會產生 branch

no branch 解法

答案

LLL = (v >> (-c&mask))
RRR = (v << (-c&mask))

要理解這樣的方式，需要先理解補數: 解讀計算機編碼-計算機為何如此編碼

reference

• https://blog.regehr.org/archives/1063

測驗 β

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

MMM

(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
可以把

(((sz + mask) / alignment) * alignment)

看成

// 因為 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.

測驗 γ

#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 上面說的，兩個情形照成多印出來的狀況

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

 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 的部分

    /* Queue not empty: retrieve data and rewire */
    void *return_value = node->value; // BBB
    queue->first = new_header;        // CCC

測驗 ϵ

XXX

 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

*ip = mp->hs[i];

答案來自這個 github repo
透過 gdb 可以知道 mp->hs[i] 會被換成 p 的 address
然後新的 address 的 value 會是原本的 address

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

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)

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

        int from_client = polls[0].revents & POLLIN;
        if (from_client)
            move(cl_fd, target_fd, fds);
        else
            move(target_fd, cl_fd, fds);

所以答案如下

    struct pollfd polls[2] = {
        [1] = {.fd = target_fd, .events = POLLIN}, // lll
        [0] = {.fd = cl_fd, .events = POLLIN},     // JJJ
    };