# 先決測驗
###### tags: `2021 Summer - Linux kernel`
:::warning
依據指定格式，標注 GitHub 帳號名稱
:notes: jserv
:::
Github account: [demonsome](https://github.com/demonsome/linux2021_projects.git)

[先決測驗題目連結](https://hackmd.io/@sysprog/linux2021-summer/https%3A%2F%2Fhackmd.io%2F%40sysprog%2Flinux2021-summer-quiz)

## 測驗 $\alpha$
延伸問題:

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

**ANS:**
在Linux核心之中的[bitops.h](https://github.com/torvalds/linux/blob/master/tools/include/linux/bitops.h)之中，我們可以找到bit rotation的程式碼如下:

/**
 * rol32 - rotate a 32-bit value left
 * @word: value to rotate
 * @shift: bits to roll
 */
static inline __u32 rol32(__u32 word, unsigned int shift)
{
	return (word << shift) | (word >> ((-shift) & 31));
}

此函式為巨集定義，故`__u32`會在編譯後被取代為32bits的資料型態，變數**word**為32bits。這是實作32bits的向左位元旋轉，位移量為變數**shift**。舉例來說，當**word** = 0xABCDEF12, **shift** = 4 時，此函式應回傳 0xBCDEF12A 。

因此，實作上只要將word向左位移**shift**個bits，以此例來說是0xABCDEF12向左位移4個bits成為0xBCDEF120，並和word向右位移(32-**shift**)個bits，即0x0000000A，兩者再進行AND bitwise操作即可得到結果。

但為確保(32-**shift**)在大於31以及小於0時，仍可以正確運作。故寫成((-**shift**) & 31)，此操作類似mod 32，使數值可以落在0到31之間。

**2. x86_64 指令集具備 rotr 和 rotl 指令，下述(測驗 $\alpha$ ) C 程式碼經過編譯器最佳化 (例如使用 gcc) 後，能否運用到這二個指令呢？**

#include <stdint.h>
  
#define __DECLARE_ROTATE(bits, type)                   \
    static inline type rotl##bits(const type v, int c) \
    {                                                  \
        const int mask = (bits) - (1);                 \
        c &= mask;                                     \
                                                       \
        return (v << c) | (LLL);                      \
    }                                                  \
                                                       \
    static inline type rotr##bits(const type v, int c) \
    {                                                  \
        const int mask = (bits) - (1);                 \
        c &= mask;                                     \
                                                       \
        return (v >> c) | (RRR);                      \
    }

#define DECLARE_ROTATE(bits) __DECLARE_ROTATE(bits, uint##bits##_t)

**ANS:**

一般來說，若gcc可認得pattern: `(x << n) | (x >> (bits - n))`，則在最佳化時可直接將上述程式碼編譯成rotr 和 rotl指令，以減少指令數，增加處理器執行效能。

但是前提需滿足`0<n<bits`，否則編譯時，編譯器對於這些未定義的行為，會直接轉成 negl, shrl, sall, orl...等多個指令，而非rotr 和 rotl指令。詳細資訊可參考:
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=57157
## 測驗 $\beta$

延伸問題:

**1. 說明下述程式碼的運作原理**

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

此函式是將參數**sz**向上進位至參數**alignment**的倍數後回傳，若**alignment**是2的冪次方，則套用一個比較快速的方式(bitwise operation)回傳，否則使用除法的方式向上進位。

由於數位邏輯的基本運算中，邏輯運算如: AND, OR, NOT, shift 等bitwise operation操作是遠比除法快很多的。故將2的冪次方的情況獨立出來處理。

**2. 在 Linux 核心原始程式碼找出類似 align_up 的程式碼，並舉例說明其用法**

在linux的header file [align.h](https://github.com/torvalds/linux/blob/master/include/linux/align.h)中定義了向上對齊至2的冪次方的巨集，如下:

/* SPDX-License-Identifier: GPL-2.0 */
#ifndef _LINUX_ALIGN_H
#define _LINUX_ALIGN_H

#include <linux/const.h>

/* @a is a power of 2 value */
#define ALIGN(x, a)		__ALIGN_KERNEL((x), (a))
#define ALIGN_DOWN(x, a)	__ALIGN_KERNEL((x) - ((a) - 1), (a))
#define __ALIGN_MASK(x, mask)	__ALIGN_KERNEL_MASK((x), (mask))
#define PTR_ALIGN(p, a)		((typeof(p))ALIGN((unsigned long)(p), (a)))
#define PTR_ALIGN_DOWN(p, a)	((typeof(p))ALIGN_DOWN((unsigned long)(p), (a)))
#define IS_ALIGNED(x, a)		(((x) & ((typeof(x))(a) - 1)) == 0)

#endif	/* _LINUX_ALIGN_H */

而我們又可以在`/include/linux/netfilter/x_tables.h`中發現`__ALIGN_KERNEL`的蹤跡，巨集如下:

/* this is a dummy structure to find out the alignment requirement for a struct
 * containing all the fundamental data types that are used in ipt_entry,
 * ip6t_entry and arpt_entry.  This sucks, and it is a hack.  It will be my
 * personal pleasure to remove it -HW
 */
struct _xt_align {
	__u8 u8;
	__u16 u16;
	__u32 u32;
	__u64 u64;
};

#define COMPAT_XT_ALIGN(s) __ALIGN_KERNEL((s), __alignof__(struct _compat_xt_align))

由於在gcc及XL C/C++中，`__alignof__`讓你可以了解一個物件是如何被對齊的，在此應用中，假設結構`_compat_xt_align`需對齊到a個bytes的邊界，`COMPAT_XT_ALIGN(s)`將回傳一個讓參數s可以向上對齊的一個a的倍數，且a是2的冪次方。如此，可以確保物件在記憶體位置中被正確的擺放，而沒有被錯誤覆寫的狀況發生。