Try   HackMD

2022q1 Homework3 (quiz3)

contributed by < yyyyuwen >

測驗 1 : GENMASK

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

題目

在 Linux 核心原始程式碼，include/linux/bitfield.h 提及一個巨集 GENMASK，其作用是依據給定的範圍，產生連續的 bitmask，例如:

  • GENMASK(6, 4) 產生 011100002
  • GENMASK(39, 21) 產生 0x000000ffffe00000 (64 位元)

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

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

請補完，使其行為符合預期。作答規範:

  1. LEFT 和 RIGHT 應以最簡潔的形式撰寫，且符合作業一排版規範 (近似 Linux 核心程式碼排版風格)
  2. LEFT 和 RIGHT 皆為表示式，可能包含常數
  3. LEFT 和 RIGHT 皆不該包含小括號 (即 ( 和 ))

作答區

Common bitmask function

maskng bit to 1 -> OR

  • To make sure the bit is on, OR can be set with 1.
  • To leave the bit unchanged, OR can be set with 0.

Example:
Masking on the higher nibble (bits 4, 5, 6, 7) while leaving the lower nibble (bits 0, 1, 2, 3) unchanged.

    10010101   10100101
 OR 11110000   11110000
 -----------------------
  = 11110101   11110101

Masking bits to 0 -> AND

More often in practice, bits are "masked off" (or masked to 0) than "masked on" (or masked to 1)

  • To make the result always be 0, AND can be set with 0.
  • To leave other bits as they are originally, AND can be set with 1.

Example
Masking off the higher nibble (bits 4, 5, 6, 7) while leaving the lower nibble (bits 0, 1, 2, 3) unchanged.

    10010101   10100101
AND 00001111   00001111
 -----------------------
  = 00000101   00000101

Querying the status of a bit -> AND

To use bitmask to check the state of individual bits regardless of the other bits.
-> 將要檢查的設定成1，其餘的設0。

Example
Querying the status of the 4th bit

    10011101   10010101
AND 00001000   00001000
 -----------------------
  = 00001000   00000000

Toggling bit values -> XOR

更多的應用是關於 XOR
XOR 又可以解釋成 "A or B, but not, A and B"

首先透過 GENMASK(6, 4) 所產生的 011100002 來討論。

  • (((~0UL) >> (LEFT)) ：是將 ~0(all 1) 的 unsigned long 往右移，所以推測位移後高位都會是0，低位都會是1。
  • ((~0UL) >> (l) << (RIGHT)) ：會先把 ~0 往右位移 l 個bits，再往左移 RIGHT 個bits，推測位移後應該是 高位與低位都是0而中間是1的型態

利用 GENMASK(6, 4) 來代入得知

//先右移57格再左移4格
GENMASK(6, 4) = 01110000 (0x0000000000000070)
(~0UL) >> (4) = 00001111

// 推測該式子應該是將 h 往右移到 l 為止，前面0的個數應該要為 63-h
(~0UL) >> (LEFT) = 0x000000000000007f

// 因為最後是 AND 的操作，因此要確保的是 l 的右邊都要為0 
((~0UL) >> (4) << (RIGHT)) = 0x0fffffffffffffff << (RIGHT)
                           = 0xfffffffffffffff0
    
(~0UL) >> (LEFT) & ((~0UL) >> (4) << (RIGHT))
=     0x000000000000007f
      0xfffffffffffffff0
    &
--------------------------
      0x0000000000000070
  • LEFT = 63 - h
  • RIGHT = l

提問：是否可將 ((~0UL) >> (4) << (RIGHT)) 更改為 ((~0UL) << (l))?

列出你的推測和實驗
:notes: jserv

測驗 2 : Align down

延伸問題:

  • 解釋上述程式碼運作原理
  • 在 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};
}

函式 to_fd 接受指定的地址 v，填入一個 fd 結構體，並確保第一個成員的地址得以依據〈你所不知道的 C 語言：記憶體管理、對齊及硬體特性〉描述，對 4 個位元組進行向下對齊 (即 C++ Boost 描述的 align_down)。其中 struct foo; 運用〈你所不知道的 C 語言：指標篇〉提及的 forward declaration 技巧，可在實作階段才提供具體 struct foo 的定義。

請補完，使其行為符合預期。作答規範:

  1. EXP1 應以最簡潔的 C99 形式撰寫，符合作業一排版規範，且不該觸發編譯器警告訊息
  2. EXP1 不得使用 % (modulo) 運算子
  3. 當變數和常數進行運算時，變數應該出現前於常數，例如 v | 1

作答區

  • EXP1 = ?

作答區

先去了解 data alignment ，可以知道其作用就是讓記憶體內的資料落在 4 個 bytes 或是 8 個 btyes 的倍數位置(看電腦規格，主要為

2n)。
而 data alignment 又可分為 align down 以及 align up。

Align up

include/uapi/linux/const.h

#define __ALIGN_KERNEL(x, a)		__ALIGN_KERNEL_MASK(x, (typeof(x))(a) - 1)
#define __ALIGN_KERNEL_MASK(x, mask)	(((x) + (mask)) & ~(mask))
  • __ALIGN_KERNEL : 指的是使 x 以 a 為邊界來對齊






G



address

Memory address

0x04

0x05

0x06

0x07

0x08

0x09

0x0a

0x0b



before

before align

 

 

data

data

data

data

 

 



address->before





after

after align

 

 

 

 

data

data

data

data



before->after

假設今天的 data 在

0x06 ，要將它對 align 於每4個bytes當中，即
0x04,
0x08,
0x0c,
0x10。
此時的 Align value = 4 (byte)
若今天採取的方法為 Align up ，則
0x06 將會對齊於
0x08 的位置。
這時候 mask 為 (typeof(x))(a) - 1 意思就是
2n−1，以 4 byte 為例， mask 此時是
0x03

  • ((x) + (mask)) 是為了讓數字不小於 x 並且不大於下一個倍數。
  • ((x) + (mask)) & ~(mask) 是為了將低位的 bit 清成零。

以此題來說

// 以二進位表示
((x) + (mask)) = 00000110 + 00000011 = 00001001
(((x) + (mask)) & ~(mask)) = 00001001 & 00001100 = 00001000

而若是 alignment 不為

2n 時，需改寫成乘除運算的形式
即

  (x + mask) & ~mask
= (x + (mask - 1)) - ((x + (mask - 1)) % (mask))
= ((x + (mask - 1))/(mask)) * (mask)

Align down

Align down 指的是向下對齊記憶體位址

include/linux/align.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)

與 Align up 不同的是在 __ALIGN_KERNEL 中所傳的值為 ((x) - ((a) - 1), (a)) 其作用是要讓值往上移到上4 byte 後再進行 mask 的操作。







G



address

Memory address

0x04

0x05

0x06

0x07

0x08

0x09

0x0a

0x0b



before

before align

 

 

data

data

data

data

 

 



address->before





after

after align

data

data

data

data

 

 

 

 



before->after

題目程式為










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

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

由於 ALIGN_DOWN(v, mask) = (v) & ~mask (mask = size - 1)， 而題目要求是要做 4 byte 的 align ，因此 mask = 3。
最後根據 forward declaration 的定義，我們要將回傳格式轉成 (struct foo *)

  • EXP = (struct foo *) (v & ~3)

測驗 3 : Reverse Bits

延伸問題:

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

題目

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









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

請補完，使其行為符合預期。作答規範:

EXP2 和 EXP3 應以最簡潔的 C99 形式撰寫，符合作業一排版規範，且不該觸發編譯器警告訊息
當變數和常數進行運算時，變數應該出現前於常數，例如 v | 1
作答區

EXP2 = ?
EXP3 = ?

作答區

此行代表的是 4 位元的前後反轉。 x 先分別往右以及往左 4 位元，最後再做 OR 的動作，而因為是uint，所以都是補 0。

x = (x >> 4) | (x << 4);

e.g.

x = 10000111
(x >> 4) = 00001000
(x << 4) = 01110000
(x >> 4) | (x << 4) = 01111000

再來是做兩兩位移，

0xCC 代表是
11001100b。

  • ((x & 0xCC) >> 2) 是將每 4 bits 高位元的 2 bits 做兩兩置換，這邊是先留下前面兩個 bits 將後面的捨去掉。
  • EXP2 推測應該是要置換每 4 bits 中低位元的部分，即
    00110011b     ，最後再做 OR 合併。
x = ((x & 0xCC) >> 2) | (EXP2);

e.g.

x = 01111000
(x & 0xCC) = 01001000
((x & 0xCC) >> 2) = 00010010
EXP2 = ((x & 0x33) << 2) = 00110000 << 2 = 11000000
((x & 0xCC) >> 2) | ((x & 0x33) << 2) = 11010010

最後是做每一個 bit 的置換，

0xAA 代表的是
10101010

  • ((x & 0xAA) >> 1) 對於每兩個 bits 中，將前一個留下而後一個拿掉，同時將式子往右移一個 bit ，是為了後許將值變成是低位的 bit。
  • EXP3 因此對於這邊則是相反，留下後面的並拿掉前面的一個 bit ，並往左移一個 bit ，轉換每兩個 bit 的高低位元，推測應該是要用
    01010101b     也就是
    0x55     。
x = ((x & 0xAA) >> 1) | (EXP3);

x = 11010010
(x & 0xAA) = 10000010
((x & 0xAA) >> 1) = 01000001
EXP3 = ((x & 0x55) << 1) = 01010000 << 1 = 10100000
((x & 0xAA) >> 1) | ((x & 0x55) << 1) = 11100001
  • EXP2 = ((x & 0x33) << 2)
  • EXP3 = ((x & 0x55) << 1)

測驗4 : foreach 巨集

延伸問題:

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

題目

延伸〈你所不知道的 C 語言：前置處理器應用篇〉，我們嘗試將 foreach 巨集 予以擴充，使得支援以下寫法:

int i;
    foreach_int(i, 0, -1, 100, 0, -99) {
        printf("i is %i\n", i);
    }
    const char *p;
    foreach_ptr(p, "Hello", "world") {
        printf("p is %s\n", p);
    }

預期輸出如下:

i is 0
i is -1
i is 100
i is 0
i is -99
p is Hello
p is world

對應的巨集定義:

#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__})))

請補完，使其行為符合預期。作答規範:

  1. EXP4 和 EXP5 應以最簡潔的 C99 形式撰寫，符合作業一排版規範，且不該觸發編譯器警告訊息
  2. 不該出現小括號 (即 ( 和 ))

作答區

  • EXP4 = ?
  • EXP5 = ?

作答區





#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])
Last changed by 
 
Dodo
0
105
Published on HackMD