2022q1 Homework3 (quiz3)

contributed by < cy023 >

測驗題

測驗 1

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

#define GENMASK(h, l) \
    (((~0UL) >> (63 - h)) & ((~0UL) >> (l) << (l)))

延伸問題:

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

測驗 2

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};
}

延伸問題:

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

測驗 3

uint8_t rev8(uint8_t x)
{
    x = (x >> 4) | (x << 4);               
    x = ((x & 0xCC) >> 2) | ((x & 0x33) << 2);
    x = ((x & 0xAA) >> 1) | ((x & 0x55) << 1);
    return x;
}

延伸問題:

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

測驗 4

#include <assert.h>
#define _foreach_no_nullval(i, p, arr) \
    assert((i) >= sizeof(arr) / sizeof(arr[0]) || (p))

#define foreach_int(i, ...)                                            \
    for (unsigned _foreach_i = (((i) = ((int[]){__VA_ARGS__})[0]), 0); \
         _foreach_i < sizeof((int[]){__VA_ARGS__}) / sizeof(int);      \
         (i) = ((int[]){__VA_ARGS__, 0})[EXP4])

#define foreach_ptr(i, ...)                                                 \
    for (unsigned _foreach_i =                                              \
             (((i) = (void *) ((typeof(i)[]){__VA_ARGS__})[0]), 0); \
         (i); (i) = (void *) ((typeof(i)[]){__VA_ARGS__,            \
                                                    NULL})[EXP5],   \
                  _foreach_no_nullval(_foreach_i, i,                        \
                                      ((const void *[]){__VA_ARGS__})))

參考 C99 規格書

6.10.3 Macro replacement
Constraints
…
5 The identifier __VA_ARGS__ shall occur only in the replacement-list of a function-like macro that uses the ellipsis notation in the parameters.

6.10.3.1 Argument substitution
…
2 An identifier __VA_ARGS__ that occurs in the replacement list shall be treated as if it were a parameter, and the variable arguments shall form the preprocessing tokens used to replace it.

測驗 5

dvs << shift
dvd -= dvs << shift

測驗 6

測驗 7

測驗 8

測驗 9

/* maximum alignment needed for any type on this platform, rounded up to a
   power of two */
#define MAX_ALIGNMENT 16

/* Given a size, round up to the next multiple of sizeof(void *) */
#define ROUND_UP_TO_ALIGNMENT_SIZE(x) \
    (((x) + MAX_ALIGNMENT - 1) & ~(-MAX_ALIGNMENT))

/* Given a size, round down to the next multiple of sizeof(void *) */
#define ROUND_DOWN_TO_ALIGNMENT_SIZE(x) \
    ((x) & ~(-MAX_ALIGNMENT))

測驗 10

#define DIVIDE_ROUND_CLOSEST(x, divisor)                       \
    ({                                                         \
        typeof(x) __x = x;                                     \
        typeof(divisor) __d = divisor;                         \
        (((typeof(x)) -1) > 0 || ((typeof(divisor)) -1) > 0 || \
         (((__x) > 0) == ((__d) > 0)))                         \
            ? ((RRR) / (__d))                  \
            : ((SSS) / (__d));                 \
    })

測驗 11

fls() 函式用來找 64 bits 變數中最靠近

// find left set
static inline unsigned long fls(unsigned long word)
{
    int num = 64 - 1;
        
    if (!(word & (~0ul << 32))) { // focus on bit63 ~ bit32
        num -= 32;
        word <<= 32;
    }
    if (!(word & (~0ul << (64 - 16)))) { // focus on bit63 ~ bit48
        num -= 16;
        word <<= 16;
    }
    if (!(word & (~0ul << (64 - 8)))) {  // focus on bit63 ~ bit56
        num -= 8;
        word <<= 8;
    }
    if (!(word & (~0ul << (64 - 4)))) {  // focus on bit63 ~ bit60
        num -= 4;
        word <<= 4;
    }   
    if (!(word & (~0ul << (64 - 2)))) {  // focus on bit63 ~ bit62
        num -= 2;
        word <<= 2;
    }   
    if (!(word & (~0ul << (64 - 1))))  // focus on bit63
        num -= 1;
    return num;
}

unsigned long i_sqrt(unsigned long x)
{
    unsigned long b, m, y = 0;

    if (x <= 1)
        return x;

    m = 1UL << (fls(x) & ~1UL);
    while (m) {
        b = y + m;
        y >>= 1;

        if (x >= b) {
            x -= b;
            y += m;
        }
        m >>= 2;
    }

    return y;
}

• lib/math/int_sqrt.c

延伸問題:

• 解釋上述程式碼運作原理，嘗試利用硬體的 clz/ctz 指令改寫
• 在 Linux 核心找出類似的巨集和程式碼，說明其應用場景