2021q1 Homework2 (quiz2)

contributed by < bakudr18 >

tags: linux2021

第 2 週測驗題

測驗 1

解釋 list_merge_sort 運作原理

void list_merge_sort(queue_t *q) {
  if (list_is_singular(&q->list))
    return;

  queue_t left;
  struct list_head sorted;
  INIT_LIST_HEAD(&left.list);
  list_cut_position(&left.list, &q->list, &get_middle(&q->list)->list);
  list_merge_sort(&left);
  list_merge_sort(q);
  list_merge(&left.list, &q->list, &sorted);
  INIT_LIST_HEAD(&q->list);
  list_splice_tail(&sorted, &q->list);
}

以下逐步解說 list_merge_sort 過程。

static inline int list_is_singular(const struct list_head *head)
{
    return (!list_empty(head) && head->prev == head->next);
}

list_is_singular ，是用來判斷 list 是否為空或是只有 head node。

static inline void INIT_LIST_HEAD(struct list_head *head)
{
    head->next = head; head->prev = head;
}

INIT_LIST_HEAD 建立一個新的 list 並把 prev 和 next 都指向 head ， list_merge_sort 創建一個 left list 準備做 divide 後的 list 容器

static inline void list_cut_position(struct list_head *head_to,
                                     struct list_head *head_from,
                                     struct list_head *node)
{
    struct list_head *head_from_first = head_from->next;

    if (list_empty(head_from))
        return;

    if (head_from == node) {
        INIT_LIST_HEAD(head_to);
        return;
    }

    head_from->next = node->next;
    head_from->next->prev = head_from;

    head_to->prev = node;
    node->next = head_to;
    head_to->next = head_from_first;
    head_to->next->prev = head_to;
}

list_cut_position ，把head_from list 從 node 差解給 head_to ，如下圖所示:

拆解後分別對 left 與 q->list 遞迴排序，然後進行 merge 。

static void list_merge(struct list_head *lhs, struct list_head *rhs,
                       struct list_head *head) {
  INIT_LIST_HEAD(head);
  if (list_empty(lhs)) {
    list_splice_tail(lhs, head);
    return;
  }
  if (list_empty(rhs)) {
    list_splice_tail(rhs, head);
    return;
  }

  while (!list_empty(lhs) && !list_empty(rhs)) {
    char *lv = list_entry(lhs->next, list_ele_t, list)->value;
    char *rv = list_entry(rhs->next, list_ele_t, list)->value;
    struct list_head *tmp = strcmp(lv, rv) <= 0 ? lhs->next : rhs->next;
    list_del(tmp);
    list_add_tail(tmp, head);
  }
  list_splice_tail(list_empty(lhs) ? rhs : lhs, head);
}

list_splice_tail 是把 list 串接到 head 的尾端。

static inline void list_splice_tail(struct list_head *list,
                                    struct list_head *head)
{
    struct list_head *head_last = head->prev;
    struct list_head *list_first = list->next, *list_last = list->prev;

    if (list_empty(list))
        return;

    head->prev = list_last;
    list_last->next = head;

    list_first->prev = head_last;
    head_last->next = list_first;
}

指出上述程式碼改善空間

struct list_head 已經有 prev 和 next 能拿來記錄 head 和 tail 位置，也能夠直接走訪 list，因此 queue_t 和 next 都是不必要的。

typedef struct __element {
    char *value;
-    struct __element *next;
    struct list_head list;
} list_ele_t;

-typedef struct {
-    list_ele_t *head; /* Linked list of elements */
-    list_ele_t *tail;
-    size_t size;
-    struct list_head list;
-} queue_t;

而 list_ele_t 同樣可以使用 lab0 用到的 Flexible array member 技巧對記憶體配置方式做改善。

typedef struct __element {
-   char *value;
    struct list_head list;
+   char value[]; 
} list_ele_t;

另外在釋放記憶體部分(函式 list_free )，如果使用 list_for_each 來走訪 list 並在過程中移除 node 的話，node->next 就會遺失。因此這裡參考 linux/list.h 中的 list_for_each_safe 用法，新增一個 n 作為暫存 node->next 的位置，因此在走訪過程才可以安全刪除 node。

/**
 * list_for_each_safe - iterate over a list safe against removal of list entry
 * @pos:	the &struct list_head to use as a loop cursor.
 * @n:		another &struct list_head to use as temporary storage
 * @head:	the head for your list.
 */
#define list_for_each_safe(pos, n, head) \
	for (pos = (head)->next, n = pos->next; pos != (head); \
		pos = n, n = pos->next)

static void list_free(struct list_head *list)
{
    if (list_empty(list))
        return;
    struct list_head *node, *tmp;
    list_for_each_safe(node, tmp, list)
    {
        list_del(node);
        free(list_entry(node, list_ele_t, list));
    }
}

---

測驗 2

解釋 func 運作原理

考慮函式 func 接受一個 16 位元無號整數

$N$ ，並回傳小於或等於

$N$ 的 power-of-2

uint16_t func(uint16_t N) {
    /* change all right side bits to 1 */
    N |= N >> 1;
    N |= N >> 2;
    N |= N >> 4;
    N |= N >> 8;

    return (N + 1) >> 1;
}

從 return (N + 1) >> 1; 可以看出，需要先把初始 N 的 MSB (most significant bit) 右邊的所有 bits 都設為 1 才能得到正確的

$N$ ，而 N |= N >> 1 能夠將 MSB 的右邊一個 bit 設為 1。因此剩餘要做的就是繼續把右邊的 bits 都設為 1。
考慮到 input 為 16 bits 無號整數，假設輸入為 func(1 << 15) ， N 依序執行結果應為

1000 0000 0000 0000    // N 
1100 0000 0000 0000    // N |= N >> 1
1111 0000 0000 0000    // N |= N >> 2
1111 1111 0000 0000    // N |= N >> 4
1111 1111 1111 1111    // N |= N >> 8

注意到這裡最後一行 N 為0xFFFF ， 如果加一會發生 overflow，因此 func 最後一行應改為 return (N >> 1) + 1; ，以保證結果正確。

Linux kernel 中的 power of two 實作

首先分析 linux/log2.h 與 power of two 相關的實作

• is_power_of_2

/**
 * is_power_of_2() - check if a value is a power of two
 * @n: the value to check
 *
 * Determine whether some value is a power of two, where zero is
 * *not* considered a power of two.
 * Return: true if @n is a power of 2, otherwise false.
 */
static inline __attribute__((const))
bool is_power_of_2(unsigned long n)
{
	return (n != 0 && ((n & (n - 1)) == 0));
}

用來判斷輸入是否為 power of two (輸入為 0 定義為 false)，直接看以下例子

1000 0000    // n
0111 1111    // n - 1
0000 0000    // n & (n - 1)

如果 n 是 power of two ，代表 n 除了 MSB 以外的 bit 都是 0，而 n - 1 會將 MSB 設為 0 而右側所有 bit 設為 1， 因此做 & 運算後可得結果。

• roundup_pow_of_two & rounddown_pow_of_two

/**
 * roundup_pow_of_two - round the given value up to nearest power of two
 * @n: parameter
 *
 * round the given value up to the nearest power of two
 * - the result is undefined when n == 0
 * - this can be used to initialise global variables from constant data
 */
#define roundup_pow_of_two(n)			\
(						\
	__builtin_constant_p(n) ? (		\
		((n) == 1) ? 1 :		\
		(1UL << (ilog2((n) - 1) + 1))	\
				   ) :		\
	__roundup_pow_of_two(n)			\
 )
 
/**
 * rounddown_pow_of_two - round the given value down to nearest power of two
 * @n: parameter
 *
 * round the given value down to the nearest power of two
 * - the result is undefined when n == 0
 * - this can be used to initialise global variables from constant data
 */
#define rounddown_pow_of_two(n)			\
(						\
	__builtin_constant_p(n) ? (		\
		(1UL << ilog2(n))) :		\
	__rounddown_pow_of_two(n)		\
 )

roundup_pow_of_two 是向上找最接近的 power of two ， rounddown_pow_of_two 是向下捨去找到最接近的 power of two ， __builtin_constant_p 是 GNU extension 用來判斷輸入是否為常數，若後續的計算不會修改到記憶體，就可以在編譯時期先計算後續的結果，而 ilog2 會回傳以 log2 為底的次方數，定義如下

#define ilog2(n) \
( \
	__builtin_constant_p(n) ?	\
	((n) < 2 ? 0 :			\
	 63 - __builtin_clzll(n)) :	\
	(sizeof(n) <= 4) ?		\
	__ilog2_u32(n) :		\
	__ilog2_u64(n)			\
 )

這裡會執行到 63 - __builtin_clzll(n) 這行， __builtin_clzll 同樣是 GNU extension ，input type 為 unsigned long long ，會回傳 MSB 左邊 leading 0 bit 的個數，與 63 相減就是所求。

接著繼續看到 __roundup_pow_of_two 和 __rounddown_pow_of_two ，定義如下

static inline __attribute__((const))
unsigned long __roundup_pow_of_two(unsigned long n)
{
	return 1UL << fls_long(n - 1);
}

static inline __attribute__((const))
unsigned long __rounddown_pow_of_two(unsigned long n)
{
	return 1UL << (fls_long(n) - 1);
}

fls_long 同樣是用來計算 MSB 的位置，舉例來說 fsl_long(0b100) 會回傳 3。繼續追蹤程式碼會發現根據不同 CPU 會有不同的透過指令集實作的方式，這我選擇先討論與 CPU 指令集無關的實作

/* 我的 CPU 是 64-bit x86， 在 UNIX 系統下 unsigned long 為 64 bit */
#elif BITS_PER_LONG == 64
static __always_inline int fls64(__u64 x)
{
	if (x == 0)
		return 0;
	return __fls(x) + 1;
}
#else

static __always_inline unsigned long __fls(unsigned long word)
{
	int num = BITS_PER_LONG - 1;

#if BITS_PER_LONG == 64
	if (!(word & (~0ul << 32))) {    // 靠左側 32 bit 皆為 0
		num -= 32;
		word <<= 32;
	}
#endif
	if (!(word & (~0ul << (BITS_PER_LONG-16)))) {    // 靠左側 16 bit 皆為 0
		num -= 16;
		word <<= 16;
	}
	if (!(word & (~0ul << (BITS_PER_LONG-8)))) {    // 靠左側 8 bit 皆為 0
		num -= 8;
		word <<= 8;
	}
	if (!(word & (~0ul << (BITS_PER_LONG-4)))) {    // 靠左側 4 bit 皆為 0
		num -= 4;
		word <<= 4;
	}
	if (!(word & (~0ul << (BITS_PER_LONG-2)))) {    // 靠左側 2 bit 皆為 0
		num -= 2;
		word <<= 2;
	}
	if (!(word & (~0ul << (BITS_PER_LONG-1))))    // 最左側 1 bit 為 0
		num -= 1;
	return num;
}

if (!(word & (~0ul << 32))) 代表 word 左側 32 bit 都是 0 (即 word < (1 << 32) ) ，因此 num 只可能為 0~31 ，然後把 word 左移 32 bits 後繼續做類似操作，這樣做的目的是把 MSB 推到最左邊，就可以根據 left shift 多少次計算出 MSB 位置。

fls64 與 __fls 的註解分別為:

• fls64 - find last set bit in a 64-bit word
• __fls - find last (most-significant) set bit in a long word
  同樣都是 find last set bit ，但 fls64(0b100) == 3 ，而 __fls(0b100) == 2 ，兩者結果不同，註解容易混淆須注意!

補充:
在追蹤 fsl64 實作時看到有趣的註解，在此做個紀錄，在 x86_64 CPU 架構下 fsl64 如下

static __always_inline int fls64(__u64 x)
{
	int bitpos = -1;
	/*
	 * AMD64 says BSRQ won't clobber the dest reg if x==0; Intel64 says the
	 * dest reg is undefined if x==0, but their CPU architect says its
	 * value is written to set it to the same as before.
	 */
	asm("bsrq %1,%q0"
	    : "+r" (bitpos)
	    : "rm" (x));
	return bitpos + 1;
}

bsr 是 x86 計算 most significant bit 的指令， q 在 AT&T assembly synax 定義為 quad (64 bit)。
這裡註解表示當 input 為 0 時，在 AMD64 下 bsr 不會修改 destination 的值 ，因此 bitpos 會維持為 -1，但在 Intel64 下是 undefined ，不過註解表示根據 CPU 架構師說法其值也不會變 (也就是 Undocumented 的用法)。

---

測驗 3

解釋 bitcpy 運作原理

void bitcpy(void *_dest,      /* Address of the buffer to write to */
            size_t _write,    /* Bit offset to start writing to */
            const void *_src, /* Address of the buffer to read from */
            size_t _read,     /* Bit offset to start reading from */
            size_t count)
{
    size_t read_lhs = _read & 7;
    size_t read_rhs = 8 - read_lhs;
    const uint8_t *source = (const uint8_t *) _src + (_read / 8);
    size_t write_lhs = _write & 7;
    size_t write_rhs = 8 - write_lhs;
    uint8_t *dest = (uint8_t *) _dest + (_write / 8);

開頭部分根據 _read , _write offset 來拆分成 left hand side 和 right hand side ，以作為後續分段 copy 的判斷依據。

size_t bitsize = (count > 8) ? 8 : count;

每次回圈最多只處理 8 bits。

uint8_t data = *source++;
if (read_lhs > 0) {
    data <<= read_lhs;
    if (bitsize > read_rhs)
        data |= (*source >> read_rhs);
}

這裡直接帶數字解說，假設

read_lhs = 5;
read_rhs = 3;
bitsize = 7;

data <<= read_lhs 會將 data 左移 5 bits ， 代表複製 src[0] 中低位的 3 bit 到 data 高位的 3 bit 中。再來看到 if (bitsize > read_rhs) 這裡若 bitsize <= 3 就代表 data 複製完了，這裡設 bitsize = 7 則會將 src[1] 右移 3 bits ，代表要複製 src[1] 高位的 5 bits 到 data 低位的 5 bits 中。

if (bitsize < 8)
    data &= read_mask[bitsize];

與 11111110b 做 & 運算，表示捨棄掉最低位的 bit，因為 bitsize = 7 只需複製 7 bits。到這裡 read 操作就結束了。

接下來是 write部分 ，一樣直接帶數字，假設

write_lhs = 5;
write_rhs = 3;

則 uint8_t mask = read_mask[write_lhs] 中的 mask = 11111000b

if (bitsize > write_rhs) {
    /* Cross multiple bytes */
    *dest++ = (original & mask) | (data >> write_lhs);
    original = *dest & write_mask[bitsize - write_rhs];
    *dest = original | (data << write_rhs);
}

假設 bitsize = 7 ，表示要分兩段寫入， *dest++ = (original & mask) | (data >> write_lhs) 會保留 original 的高位 5 bits 到 dest[0] 高位的 5 bits ，然後將 data 的高位 3 bits 寫入 dest[0] 低位的 3 bits 中。
接著 original = *dest & write_mask[bitsize - write_rhs] 則是 dest[1] & 00001111b ，表示先保留 dest[1] 低位 4 bits ，接著 *dest = original | (data << write_rhs) 這裡做 OR 運算，表示先複製了 data 低位的 5 bits 後，只寫入左側 4 bits 到 dest[1] 高位 4 bits 中，這樣寫入的 bitsize 才會等於 7。

else {
    // Since write_lhs + bitsize is never >= 8, no out-of-bound access.
    mask |= write_mask[write_lhs + bitsize];
    *dest++ = (original & mask) | (data >> write_lhs);
}

最後 else 表示可以一次寫入，假設 bitsize = 3 ，則 mask = 11111000b | 00000000b ， *dest++ = (original & mask) | (data >> write_lhs) 表示保留 original 高位 5 bits ，只需寫入 data 高位 3 bits 到的 dest[0] 低位的 3 bits 即可。

改善 bitcpy 效能

Bitmask

原始程式碼使用兩個 array 來存放 bitmask ，這兩個 array 完全可用 bitwise operation 取代。

#define READMASK(x) ((uint8_t)(~0U) << (8 - (x)))
#define WRITEMASK(x) ((uint8_t)(~0U) >> (x))

注意到這裡需先將 (~0U) 轉型成 uint8_t 再做 shift 才能保證正確。

根據 C11 standard 6.5.7 Bitwise shift operators 中第 3 點提到，

The integer promotions are performed on each of the operands. The type of the result is that of the promoted left operand. If the value of the right operand is negative or is greater than or equal to the width of the promoted left operand, the behavior is undefined.

這邊對 uint8_t 位移 8 位元是未定義行為，是否需要特別處理。

DDerveialm

感謝 DDerveialm 的提醒，修正後的結果如下，改為先對 unsigned int 位移後再轉型成 uint8_t

#define READMASK(x) (uint8_t)((~0U) << (8 - (x)))
#define WRITEMASK(x) (~READMASK(x))

BakudYao

由於陸續對 bitcpy 進行激進 (aggressive) 的最佳化，為了確保程式行為一致，需要有更好的測試案例，可參照 glibc/string/test-memcpy.c

jserv

Branch prediction

現代處理器大多都有 branch predictor ，會對執行程式做預測並先做計算，來改善處理器的效能，考慮到原始程式碼使用太多 if 判斷可能讓程式碼產生過多分支，進而造成過多 branch misses，因此首先試圖減少使用 if 判斷，盡可能都用 bitwise operation。

void bitcpy_branch_predict(
    void *_dest,      /* Address of the buffer to write to */
    size_t _write,    /* Bit offset to start writing to */
    const void *_src, /* Address of the buffer to read from */
    size_t _read,     /* Bit offset to start reading from */
    size_t count)
{
...

    uint8_t data, original;
    /* copy until count < 8 bits */
    for (size_t bytecount = count >> 3; bytecount > 0; bytecount--) {
        data = *source++;
        data = data << read_lhs | (*source >> read_rhs);
        original = *dest & READMASK(write_lhs);
        *dest++ = original | (data >> write_lhs);
        *dest = (*dest >> write_lhs) | (data << write_rhs);
    }
    count &= 7;

    /* copy the remaining count */
    data = *source++;
    data = ((data << read_lhs) | (*source >> read_rhs)) & READMASK(count);
    original = (*dest & READMASK(write_lhs));
    *dest++ = original | ((data & READMASK(count)) >> write_lhs);
    if (count > write_rhs)
        *dest = (*dest & WRITEMASK(count - write_rhs)) | (data << write_rhs);
}

首先對於 count > 8 的 input ， 不需要像原實作方法拆成三段，可以使用一個迴圈和一個 data 暫存就可解決。然後再對於剩餘的 bit 做複製即可，最後一個 if 判斷是用來確認剩餘 bit 是否跨越兩個 byte 之間而須做另外的複製。

接著進行實驗複製 1 ~ 8000 bits ， 比較優化前後的結果如下，可以發現優化後程式碼速度明顯較快。

memcpy

考慮到 C 語言函式庫提供的 memcpy 已經針對各電腦硬體做不同的優化，在 _read 與 _write offset 相差為 8 bits (或 8 的倍數) 時，可以直接使用 memcpy ，以下為實作

if (read_lhs == write_lhs) {
        uint8_t mask;
        uint8_t data = *source++;
        uint8_t original = *dest;
        size_t bitsize = count > read_rhs ? read_rhs : count;
        data = (data << read_lhs) & READMASK(bitsize);
        mask = WRITEMASK(bitsize);
        *dest++ = (original & mask) | (data >> read_lhs);
        count -= bitsize;

        size_t bytecount = count / 8;
        if (bytecount > 0) {
            memcpy(dest, source, bytecount);
            source += bytecount;
            dest += bytecount;
        }

        data = *source;
        original = *dest;
        count %= 8;
        if (count > 0) {
            mask = READMASK(count);
            *dest = (original & (~mask)) | (data & mask);
        }
    }

首先處理開頭沒有對齊記憶體的 offset ，然後對於中間的 byte 使用 memcpy 直接複製，就可以避免使用迴圈，最後一樣針對剩餘的 bit 做最後處理。
使用 offset 相差 8 bit 的值作為 input 進行效能測試，可以發現使用 memcpy 效能明顯快上不少。

Linux 核心原始程式碼中，提供若干 unaligned/aligned 記憶體存取的巨集/API，你可對照閱讀 Unaligned Memory Accesses

jserv