# linux2021: new-type

## 測驗 $\alpha - 1$
在
./include/linux/bitops.h

static inline __u64 rol64(__u64 word, unsigned int shift)
{
	return (word << (shift & 63)) | (word >> ((-shift) & 63));
}
static inline __u64 ror64(__u64 word, unsigned int shift)
{
	return (word >> (shift & 63)) | (word << ((-shift) & 63));
}
static inline __u32 rol32(__u32 word, unsigned int shift)
{
	return (word << (shift & 31)) | (word >> ((-shift) & 31));
}
static inline __u32 ror32(__u32 word, unsigned int shift)
{
	return (word >> (shift & 31)) | (word << ((-shift) & 31));
}
...

在 ./arch/ia64/include/asm/processor.h 中有使用到這類運算。

static inline __u64
ia64_rotr (__u64 w, __u64 n)
{
	return (w >> n) | (w << (64 - n));
}

#define ia64_rotl(w,n)	ia64_rotr((w), (64) - (n))

## 測驗 α−2
感覺是要看語法樹那邊是不是能轉換，以及有沒有未定義行為的狀況
:::warning
工程人員說話要精準，避免用「感覺」一詞，你有推論，就該去驗證和查核。
:notes: jserv
:::

## 測驗 β−1
2 的 x 次冪以二進位表示時會在位置 x (位置從最右方為 0 算起)為 1 ，其餘都是 0。
而 2^x - 1 會造成位置 x 為 0，而在位置 0 到 x - 1 全部是 1。
也就能推導出 2^x & 2^x - 1 = 0
所以對於 alignment 是 2 的 x 次冪的對齊，可以直接將原數 sz 加上 mask ，若是沒對齊就會進位到位置 x 的 bit。之後再用 ~mask 將 0 至 x - 1 的 bits 全清為零。
而不是 2 的某次冪的，則是利用 sz + mask 也會產生進位的問題，而後面使用 / alignment 再 * alignment 則是用來對齊，也就是將比 alignment 小的 bits 清為零。

## 測驗 β−2
定義在 ./include/uapi/linux/const.h中的 __ALIGN_KERNEL_MASK 的作法與題目相類似

#define __ALIGN_KERNEL(x, a)		__ALIGN_KERNEL_MASK(x, (typeof(x))(a) - 1)
#define __ALIGN_KERNEL_MASK(x, mask)	(((x) + (mask)) & ~(mask))

應用如記憶體分頁的對齊(./include/linux/mm.h)

/* to align the pointer to the (next) page boundary */
#define PAGE_ALIGN(addr) ALIGN(addr, PAGE_SIZE)

## 測驗 γ
可以先將原本的程式先去掉 fork() 來看

for (int i = 0; i < N; ++ i) {
    printf("-");
}

上面可以知道一個 process 可以產生 N 個 "-"。

再來看 process 數量的變化

for (int i = 0; i < N; ++ i) {
    fork();
}

可以看出隨著 i 的變化會產生的 child process 數量為：
i = 0 時: 1 = 2¹ - 1
i = 1 時: 3 = 2² - 1
i = 2 時: 7 = 2³ - 1
...
i = N - 1 時: 2^{(N - 1) + 1} - 1
所以包含一開始的 process，總共有 1 + (2^N - 1) = 2^N 個 process。

因此 2^N 個 process，每個可以輸出 N 個字元，總共就是 N * 2^N 個字元輸出。

## 測驗 δ−1
運作原理是利用 mutex 來保證 queue 的操作正確。實作上可以利用 lock_guard 來減少忘了手動解鎖產生的 deadlock。