2022q1 Homework3 (quiz3)

contributed by < leewei05 >

tags: linux2022

測驗 1

• 解釋上述程式碼運作原理
• 比較 Linux 核心 GENMASK 巨集的實作，闡述其額外的考量
• 舉出 Linux 核心原始程式碼中二處 GENMASK 巨集和 include/linux/bitfield.h 的應用案例

• GENMASK(6, 4) 產生
  ${01110000}_2$ (2 進制)
• GENMASK(39, 21) 產生 0x000000ffffe00000 (64 位元)

已知我們使用的微處理器架構為 64 位元，且 unsigned long 為 8 位元組寬度 (符合 LP64 資料模型)，以下是可能的 GENMASK 巨集的定義:

#define GENMASK(h, l) \
    (((~0UL) >> (LEFT)) & ((~0UL) >> (l) << (RIGHT)))

首先 GENMASK 代入(6, 4) 先右移 57 再左移 4

result = 0x000000000000007f(01110000)
(~0UL) >> (4) = 00001111
    
(~0UL) >> (LEFT) = 11111111 or 01111111
LEFT  = 56 or 57
(~0UL) >> (4) << (RIGHT) = 01111000 or 11110000
RIGHT = 3 or 4
    
// Cannot be LEFT = 56, RIGHT = 4

接著 GENMASK 代入(39, 21) 先右移 24 再左移 21

result = 0x000000ffffe00000(24*0 19*1 21*0)
(~0UL) >> (21) = 0x000007ffffffffff (21*0 43*1)
    
(~0UL) >> (LEFT) = 0x000000ffffffffff (24*0 40*1)
LEFT = 24
(~0UL) >> (21) << (RIGHT) = 0xffffffffffe00000(43*1 21*0)
RIGHT = 21

LEFT = 63 - h
RIGHT = l

以下取自 Linux Kernl 程式碼

/*
 * Create a contiguous bitmask starting at bit position @l and ending at
 * position @h. For example
 * GENMASK_ULL(39, 21) gives us the 64bit vector 0x000000ffffe00000.
 */
#if !defined(__ASSEMBLY__)
#include <linux/build_bug.h>
#define GENMASK_INPUT_CHECK(h, l) \
	(BUILD_BUG_ON_ZERO(__builtin_choose_expr( \
		__is_constexpr((l) > (h)), (l) > (h), 0)))
#else
/*
 * BUILD_BUG_ON_ZERO is not available in h files included from asm files,
 * disable the input check if that is the case.
 */
#define GENMASK_INPUT_CHECK(h, l) 0
#endif

#define __GENMASK(h, l) \
	(((~UL(0)) - (UL(1) << (l)) + 1) & \
	 (~UL(0) >> (BITS_PER_LONG - 1 - (h))))
#define GENMASK(h, l) \
	(GENMASK_INPUT_CHECK(h, l) + __GENMASK(h, l))

#define __GENMASK_ULL(h, l) \
	(((~ULL(0)) - (ULL(1) << (l)) + 1) & \
	 (~ULL(0) >> (BITS_PER_LONG_LONG - 1 - (h))))
#define GENMASK_ULL(h, l) \
	(GENMASK_INPUT_CHECK(h, l) + __GENMASK_ULL(h, l))

測驗 2

• 解釋上述程式碼運作原理
• 在 Linux 核心原始程式碼找出類似技巧的實作 (例如檔案系統) 並解說

考慮以下程式碼:

struct foo;
  
struct fd {
    struct foo *foo;
    unsigned int flags;
};

enum {
    FOO_DEFAULT = 0,
    FOO_ACTION,                           
    FOO_UNLOCK,
} FOO_FLAGS;

static inline struct fd to_fd(unsigned long v)
{
    return (struct fd){EXP1, v & 3};
}

測驗 3

• 解釋上述程式碼運作原理
• 在 Linux 核心原始程式碼找出類似技巧的實作並解說其應用場景

考慮以下程式碼，能將輸入的 8 位元無號整數逐一位元反轉，如同 LeetCode 190. Reverse Bits 的描述。

前後四位元進行互換 x = (x >> 4) | (x << 4);。0xCC 的二進制為 11001100，0xAA 的二進制為 10101010。推斷 EXP2 = (x & 0x33) << 2)， EXP3 = (x & 0x55) << 1) 因為依序是左右互換 4, 2, 1 的位元。

#include <stdint.h>
uint8_t rev8(uint8_t x)
{
    x = (x >> 4) | (x << 4);               
    x = ((x & 0xCC) >> 2) | (EXP2);
    x = ((x & 0xAA) >> 1) | (EXP3);
    return x;
}

測驗 7

• 解釋上述程式碼運作原理
• 在 Linux 核心原始程式碼找出類似實作並解說其應用場景
• 研讀論文《Using de Bruijn Sequences to Index a 1 in a Computer Word》，探討缺乏硬體 ctz/clz 指令的微處理器上，如何實作 branchless 的 ilog
• 運用〈你所不知道的 C 語言：前置處理器應用篇〉和〈你所不知道的 C 語言：數值系統篇〉提及的技巧，實作編譯時期 (compile-time) 的 ilog2 實作

考慮 ilog32 函式可針對給定的 32 位元無號數，計算扣除開頭的 0，最少需要多少位元才可儲存 (the minimum number of bits required to store an unsigned 32-bit value without any leading zero bits)，以下是一個可能的實作:

int ilog32(uint32_t v)
{
    int ret = v > 0;
    int m = (v > 0xFFFFU) << 4;
    v >>= m;
    ret |= m;
    m = (v > 0xFFU) << 3;
    v >>= m;
    ret |= m;
    m = (v > 0xFU) << 2;
    v >>= m;
    ret |= m;
    m = EXP10;
    v >>= m;
    ret |= m;
    EXP11;
    return ret;
}

6.5.8 Relational operators
Each of the operators < (less than), > (greater than), <= (less than or equal to), and >=
(greater than or equal to) shall yield 1 if the specified relation is true and 0 if it is false.92)
The result has type int.

如果 v > 0 則 ret 為 1; v <= 0 則 ret 為 0。

0xFFFFU 全為 1 的 16 位元數