---
tags: linux2021-summer
---

# 2021 年暑期「Linux 核心」課程先決測驗題 回答
> [先決測驗](https://hackmd.io/@sysprog/linux2021-summer-quiz)
>
## alpha
AAA = v >> (bits - c)
BBB= v << (bits - c)

我智商一開始只想到這樣的做法，後來看分析文沒想到有 UDB 要顧

## beta
MMM = (sz + mask) & (~mask)

## gamma
NNN = 12

## delta
AAA = queue->last->next = node
BBB = node
CCC = queue->first = new_header

## epsiloon
XXX = x

## eta
### 1. 探討 gamma 中迴圈 fork 並 print 至數量 49152 個 -

總共會產生 $2^{12} - 1 = 4095$ 個 child process
本身 parent 也是一個 process ，因此共有 4096 個 process 會進行
而原本應該每個 process 輸出都應該從 i 開始遞減輸出。
但是 buffered io 在遇到 fflush 或 newline 時才會被輸出至螢幕上。並參考以下 fork 之說明，會共享 parent 的 file descriptor 。因此每個 process 裏面都含有 i 個 "-" 於 buffer 中。

因此共會印出 4096 process * 12 = 49152 個

[man 2 fork](https://man7.org/linux/man-pages/man2/fork.2.html)

> The child inherits copies of the parent's set of open file
> descriptors. Each file descriptor in the child refers to the
> same open file description (see open(2)) as the corresponding
> file descriptor in the parent. This means that the two file
> descriptors share open file status flags, file offset, and
> signal-driven I/O attributes (see the description of F_SETOWN
> and F_SETSIG in fcntl(2)).

### 2. Beta 中 Bitwise 進行記憶體位置向上對齊

題目中的數字，是希望用來做記憶體位置的表示。CPU 取資料不會是一個 byte 一個 byte 抓，而是以 word 為單位。如果將資料擺放位置都剛好符合 CPU 一次抓取的大小，拿到資料後就不用額外花時間喬正資料。

因此假設記憶體位置對齊 aligment 位，表示位置的數值需剛好為 aligment 的倍數。

如果剛好就是 aligment 的倍數，則表示本身就已經對齊，無需對該數值操作。

以題目中的例子，希望對齊 4 ，因此 120 ~ 123 中， 120 剛好為 4 的倍數，表示已經對其無需改動，121~123 按題目需求向上對齊至下一個倍數。

作答如下，如果剛好 alignment 為 2 的冪，可以用簡單的 bitwise 特性，直接用 bitwise 運算取值

#include <stdint.h>

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 (sz + mask) & (~mask);       
    }
    return (((sz + mask) / alignment) * alignment);
}

以下分為 2 的冪和非 2 的冪進行討論

#### alignment 為 2 的冪

如果剛好為 2 的冪，一個對齊的位置其右半邊皆剛好是 bit 0。
舉例如下

* align_up(4, 4) => 0b0100
* align_up(8, 4) => 0b1000

多少個最右邊 bit 需要變成零，剛好是最大還不會二位元進位的 bit，例如 aligiment 為 4 = 0b0100 ，右邊兩個 bit 只要剛好是 0，皆是對齊的數字。

因此 aligment - 1 可以拿來作為 mask，其特性剛好是右邊位數皆為 1。

以對齊 4 為例，alignment - 1 = 3 = 0b0011

核心想法為:

1. 想辦法辨識右邊非 0 為未對齊
2. 右半邊最終都必須剛好是 0

##### 後半部 右半邊清零

上述作法單獨將 `& (~mask)` 拿出來看。bitwise and 的特性是

* 任何數字 and 1 = 原數字
* 任何數字 and 0 = 0

剛好 mask 最右邊的數字皆為 1 ，只要全部翻轉再做 & 運算就能保留右半邊。

##### 前半部 利用進位特性加法

除了右半邊清 0 之外，還必須辨別是剛好對齊的數字還是非對齊的數字。

剛好所有非對齊的數字 + mask 皆能造成二位元進位。只有對齊的數字 00 不會進位，最終被後半部清零

eg.

* 4 (0b0100) + 3 (mask 0b0011) = 7 (0b0111)
* 6 (0b0101) + 3 (mask 0b0011) = 9 (0b1001)

:::warning
TODO: 列出其他可能的實作
:::

其他思路，以核心想法找出非對齊的作法，只要快速 !!(sz & mask) 便能得知是否非 0。只要再 + mask 也能觸發進位和不進位

#### alignment 非 2 的冪

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

上述則是改為利用 int 的除法為捨去小數點之後的整數，加上 mask 則是為了讓數值向上對齊，而非相下。

eg.

##### align_up(9, 7)

1. 9 + mask = 15
2. 15 / 7 = 2
3. 2 * 7 = 14

若改為向下對齊則不用加 mask

##### align_down(9, 7)

1. 9 / 7 = 1
2. 1 * 7 = 7

### linux 用於 sign_up 的做法

linux 的紅黑樹的 parent pointer 同時也用做顏色的判斷，
其方法為沒對齊多出來的部分作為紅黑判斷。因此每次取得 parent 的位置時都透過 macro，將位置對齊

#define rb_parent(r)   ((struct rb_node *)((r)->__rb_parent_color & ~3))

參考如下
[rbtree.h](https://github.com/torvalds/linux/blob/master/include/linux/rbtree.h#L35)