# 2022q1 Homework3 (quiz3)
contributed by < `shawn5141` >
## [測驗 `1`](https://hackmd.io/@sysprog/linux2022-quiz3#%E6%B8%AC%E9%A9%97-1)
:::success
在 Linux 核心原始程式碼，[include/linux/bitfield.h](https://github.com/torvalds/linux/blob/master/include/linux/bitfield.h) 提及一個巨集 `GENMASK`，其作用是依據給定的範圍，產生連續的 [bitmask](https://en.wikipedia.org/wiki/Mask_(computing))，例如:
* `GENMASK(6, 4)` 產生 01110000<sub>2</sub>
* `GENMASK(39, 21)` 產生 0x000000ffffe00000 (64 位元)
已知我們使用的微處理器架構為 64 位元，且 `unsigned long` 為 8 位元組寬度 (符合 [LP64](https://en.wikipedia.org/wiki/64-bit_computing#64-bit_data_models) 資料模型)，以下是可能的 `GENMASK` 巨集的定義:
```cpp
#define GENMASK(h, l) \
(((~0UL) >> (LEFT)) & ((~0UL) >> (l) << (RIGHT)))
```
請補完，使其行為符合預期。作答規範:
1. `LEFT` 和 `RIGHT` 應以最簡潔的形式撰寫，且符合[作業一](https://hackmd.io/@sysprog/linux2022-lab0)排版規範 (近似 Linux 核心程式碼排版風格)
2. `LEFT` 和 `RIGHT` 皆為表示式，可能包含常數
3. `LEFT` 和 `RIGHT` 皆不該包含小括號 (即 `(` 和 `)`)
作答區
LEFT = ?
RIGHT = ?
:::
### 1. 解釋上述程式碼運作原理
我們可以從`GENMASK(6, 4)`產生 01110000<sub>2</sub>來分析。
- `(((~0UL) >> (LEFT)) & ((~0UL) >> (l) << (RIGHT)))`可以當成
`(A) & (B))`，在只有一個`&`且只有左移跟右移的情況，可以合理的懷疑A和B是由`11110000`跟`01111111`組成。
>因為是unsigned long，所以Left shift 和 right shift 都會補上0。
>`~0UL` 是`0xffffffffffffffff`
```cpp=
11110000
& 01111111
------------
01110000
```
- A因為只有右移，所以其LSB是會有0。這邊發現A只有右移1個。考慮這個例子只有8bits，所以可以假設A=(8-(h+1))= (8-6-1) = 1。
同理，我們可發現B左移了4，但這邊我們看到B先右移了`l`，然後才左移Right。
在我們的例子中，l=4，所以變成00001111，然後再右移4變成11110000。
按照上面的假設，我們可以得到公式
```cpp=
(((~0UL) >> (63-h)) & ((~0UL) >> (l) << (l)))
```
我們把這個公式帶到第二個範例中可以得到`0x000000ffffe00000`
### 2. 比較 Linux 核心 GENMASK 巨集的實作，闡述其額外的考量
有三個地方皆有定義 GENMASK。這邊就以[include/linux/bits.h](https://elixir.bootlin.com/linux/latest/source/include/linux/bits.h#:~:text=%23define%20GENMASK(h%2C%20l)%20%5C%0A%09(GENMASK_INPUT_CHECK(h%2C%20l)%20%2B%20__GENMASK(h%2C%20l)))來討論。
```cpp=
#define GENMASK(h, l) \
(GENMASK_INPUT_CHECK(h, l) + __GENMASK(h, l))
```
呼叫 `GENMASK_INPUT_CHECK` 跟 `__GENMASK`，我們先探討前者。
```cpp=
#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
```
從comments中發現如果`BUILD_BUG_ON_ZERO`的話，就把GENMASK_INPUT_CHECK設為0。否則的話，就判斷
```cpp=
(BUILD_BUG_ON_ZERO(__builtin_choose_expr( \
__is_constexpr((l) > (h)), (l) > (h), 0)))
```
<details>
<summary>__is_constexpr判斷(l) > (h)是不是integer const expression，如果是的話就用回傳1 </summary>
- [__is_constexpr](https://stackoverflow.com/questions/49481217/linux-kernels-is-constexpr-macro#:~:text=24-,Linux%20Kernel%27s%20__is_constexpr%20macro,Introduction,-The%20__is_constexpr(x))不錯的文章
:::success
The `__is_constexpr(x)` macro can be found in Linux Kernel's [include/kernel/kernel.h](https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/include/linux/kernel.h?id=3c8ba0d61d04ced9f8d9ff93977995a9e4e96e91#n814):
The macro is notable for taking advantage of subtle details of the C standard: the conditional operator's rules for determining its returned type (6.5.15.6) and the definition of a null pointer constant (6.3.2.3.3). In summary, the __is_constexpr(x) macro returns an integer constant expression of value 1 if the argument is an integer constant expression. Otherwise, it returns an integer constant expression of value 0.
:::
```cpp=
/*
* This returns a constant expression while determining if an argument is
* a constant expression, most importantly without evaluating the argument.
* Glory to Martin Uecker <Martin.Uecker@med.uni-goettingen.de>
*/
#define __is_constexpr(x) \
(sizeof(int) == sizeof(*(8 ? ((void *)((long)(x) * 0l)) : (int *)8)))
```
`8 ? ((void *)((long)(x) * 0l)) : (int *)8)`基本上就是去考慮
```
sizeof(int) == sizeof(*((int *) (NULL))) // if `x` was an integer constant expression
sizeof(int) == sizeof(*((void *)(....))) // otherwise
```
>According to the GNU C extension, sizeof(void) == 1. Therefore, if x was an integer constant expression, the result of the macro is 1; otherwise, 0.
(圖擷取自[Linux內核中max()宏的奧妙何在？](https://www.twblogs.net/a/5d8c9b15bd9eee5327001eb0))
</details>
<details>
<summary>__builtin_choose_expr在編譯的時候做ternary operator 判斷，如果__is_constexpr((l) > (h))回傳1就用(l)>(h)，不然就回傳0</summary>
TYPE __builtin_choose_expr(CONST_EXP, EXP1, EXP2)：同CONST_EXP?EXP1:EXP2的概念，但是這個寫法會在編譯時就決定結果。
</details>
<details>
<summary>BUILD_BUG_ON_ZERO 如果回傳是0就沒事，但如果(l)>(h)是true的話，就沒辦法編譯通過。因為H必須要大於L</summary>
```cpp=
#define BUILD_BUG_ON_ZERO(e) (sizeof(struct { int:-!!(e); }))
```
[參照此篇文章](https://www.programminghunter.com/article/68671244579/)
1. (e): 表达式e的声明
2. !!(e): 对e的结果进行两次求非。即如果e开始是0的话，结果就是0；如果e不为0，则结果为1。
3. –!!(e): 再乘以-1。如果第2步结果为0，则仍为0；否则结果为-1。
4. struct { int : –!!(0); } --> struct { int : 0; } : 如果e的结果为0，则我们声明一个结构体拥有一个int型的数据域，并且规定它所占的位的个数为0。这没有任何问题，我们认为一切正常。
5. struct { int : –!!(1); } --> struct { int : –1; } : 如果e的结果非0，结构体的int型数据域的位域将变为一个负数，将位域声明为负数这是一个语法的错误。
6. 现在要么结果为声明了一个位域为0的结构体，要么出现位域为负数编译出错；如果能正确编译，然后我们对该结构体进行sizeof操作，得到一个类型为size_t的结果，值为0。
</details>
:::info
所以這邊就是在檢查`h`和`l`的大小合不合規定
:::
#### __GENMASK
```cpp=
#define __GENMASK(h, l) \
(((~UL(0)) - (UL(1) << (l)) + 1) & \
(~UL(0) >> (BITS_PER_LONG - 1 - (h))))
```
<details>
<summary>BITS_PER_LONG 在64bit machine下是64，不然就是32</summary>
```cpp
#ifdef CONFIG_64BIT
#define BITS_PER_LONG 64
#else
#define BITS_PER_LONG 32
#endif /* CONFIG_64BIT */
```
</details>
[隔壁同學不錯的例子](https://hackmd.io/@jim12312321/linux2022-quiz3#:~:text=%E6%88%91%E5%80%91%E4%B8%80%E6%A8%A3%E4%BE%86%E8%88%89%E5%80%8B%E4%BE%8B%E5%AD%90%E8%AA%AA%E6%98%8E%EF%BC%88%E4%B8%8D%E8%88%89%E4%BE%8B%E7%B5%A6%E8%87%AA%E5%B7%B1%E7%9C%8B%E6%88%91%E7%9C%9F%E7%9A%84%E8%85%A6%E8%A2%8B%E5%8D%A1%E4%BD%8F%EF%BC%89)
### 3. 舉出 Linux 核心原始程式碼中二處 GENMASK 巨集和 include/linux/bitfield.h 的應用案例
1. [include/asm-generic/bitops/find.h](https://elixir.bootlin.com/linux/latest/source/include/asm-generic/bitops/find.h#L23)
```cpp=
#ifndef find_last_bit
/**
* find_last_bit - find the last set bit in a memory region
* @addr: The address to start the search at
* @size: The number of bits to search
*
* Returns the bit number of the last set bit, or size.
*/
static inline
unsigned long find_last_bit(const unsigned long *addr, unsigned long size)
{
if (small_const_nbits(size)) {
unsigned long val = *addr & GENMASK(size - 1, 0);
return val ? __fls(val) : size;
}
return _find_last_bit(addr, size);
}
#endif
```
然後`find_last_bit`有被用在[/mm/percpu.c](https://elixir.bootlin.com/linux/latest/source/mm/percpu.c#:~:text=l_bit%20%3D%20find_last_bit(pcpu_index_alloc_map(chunk%2C%20s_index)%2C%20s_off)%3B)
```cpp=
/*
* pcpu_block_update_scan - update a block given a free area from a scan
* @chunk: chunk of interest
* @bit_off: chunk offset
* @bits: size of free area
*
* Finding the final allocation spot first goes through pcpu_find_block_fit()
* to find a block that can hold the allocation and then pcpu_alloc_area()
* where a scan is used. When allocations require specific alignments,
* we can inadvertently create holes which will not be seen in the alloc
* or free paths.
*
* This takes a given free area hole and updates a block as it may change the
* scan_hint. We need to scan backwards to ensure we don't miss free bits
* from alignment.
*/
static void pcpu_block_update_scan(struct pcpu_chunk *chunk, int bit_off,
int bits)
{
int s_off = pcpu_off_to_block_off(bit_off);
int e_off = s_off + bits;
int s_index, l_bit;
struct pcpu_block_md *block;
if (e_off > PCPU_BITMAP_BLOCK_BITS)
return;
s_index = pcpu_off_to_block_index(bit_off);
block = chunk->md_blocks + s_index;
/* scan backwards in case of alignment skipping free bits */
l_bit = find_last_bit(pcpu_index_alloc_map(chunk, s_index), s_off);
s_off = (s_off == l_bit) ? 0 : l_bit + 1;
pcpu_block_update(block, s_off, e_off);
}
```
---
# [測驗 2](https://hackmd.io/@sysprog/linux2022-quiz3#%E6%B8%AC%E9%A9%97-2)
:::success
考慮以下程式碼:
```cpp
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};
}
```
函式 `fo_fd` 接受指定的地址 `v`，填入一個 `fd` 結構體，並確保第一個成員的地址得以依據〈[你所不知道的 C 語言：記憶體管理、對齊及硬體特性](https://hackmd.io/@sysprog/c-memory)〉描述，對 4 個位元組進行向下對齊 (即 C++ Boost 描述的 [align_down](https://www.boost.org/doc/libs/1_78_0/doc/html/align/reference.html#align.reference.functions.align_down))。其中 `struct foo;` 運用〈[你所不知道的 C 語言：指標篇](https://hackmd.io/@sysprog/c-pointer)〉提及的 forward declaration 技巧，可在實作階段才提供具體 `struct foo` 的定義。
請補完，使其行為符合預期。作答規範:
1. `EXP1` 應以最簡潔的 C99 形式撰寫，符合[作業一](https://hackmd.io/@sysprog/linux2022-lab0)排版規範，且不該觸發編譯器警告訊息
2. `EXP1` 不得使用 `%` (modulo) 運算子
3. 當變數和常數進行運算時，變數應該出現前於常數，例如 `v | 1`
<mark>作答區</mark>
* `EXP1` = ?
:::
延伸問題:
### 1. 解釋上述程式碼運作原理
在linux kernel 中已經有定義了`#define ALIGN_DOWN(addr, size) (addr)&(~((size)-1))` 當中size 是4，`(addr)&(~((size)-1))`變成`(addr)&(~(3))`= `(addr)&(0xFFFFFFFFFFFFFFFC)`。最後的C代表1100<sub>2</sub>，也就是說會強制把最後的兩位變成零，造成align_down 的效果。
這邊因為是使用Compound Literals來初始化fd，所以EPX1會把第一個元素變成struct foo。EXP1 = `(struct foo)(v & ~3)`
### 2. 在 Linux 核心原始程式碼找出類似技巧的實作 (例如檔案系統) 並解說
在[arch/arm/mm/init.c](https://elixir.bootlin.com/linux/latest/source/arch/arm/mm/init.c#:~:text=ALIGN_DOWN(addr%2C%20pageblock_size)%2C)有使用`ALIGN_DOWN`的技巧。
```cpp=
#ifdef CONFIG_HAVE_ARCH_PFN_VALID
int pfn_valid(unsigned long pfn)
{
phys_addr_t addr = __pfn_to_phys(pfn);
unsigned long pageblock_size = PAGE_SIZE * pageblock_nr_pages;
if (__phys_to_pfn(addr) != pfn)
return 0;
/*
* If address less than pageblock_size bytes away from a present
* memory chunk there still will be a memory map entry for it
* because we round freed memory map to the pageblock boundaries.
*/
if (memblock_overlaps_region(&memblock.memory,
ALIGN_DOWN(addr, pageblock_size),
pageblock_size))
return 1;
return 0;
}
EXPORT_SYMBOL(pfn_valid);
#endif
```
- pfn stands for page-frame number.
<details>
<summary>從這個commit我們得知 pfn_valid 是用來判斷memblock中有沒有hole的</summary>
Platforms like arm and arm64 have redefined pfn_valid() because their early memory sections might have contained memmap holes caused by memblock areas tagged with MEMBLOCK_NOMAP, which should be skipped while validating a pfn for struct page backing. This scenario could be captured with a new option CONFIG_HAVE_EARLY_SECTION_MEMMAP_HOLES and then generic pfn_valid() can be improved to accommodate such platforms. This reduces overall code footprint and also improves maintainability.
[link](https://lore.kernel.org/linux-arm-kernel/2541b182-1f1c-c1ed-c15c-9d71160eb6fe@redhat.com/T/)
</details>，而memblock_overlaps_region則是在這個commit:
[[PATCH 3/3] arm: extend pfn_valid to take into accound freed memory map alignment](https://www.spinics.net/lists/arm-kernel/msg906173.html) 被引入
## [測驗3](https://hackmd.io/@sysprog/linux2022-quiz3#%E6%B8%AC%E9%A9%97-3)
:::success
考慮以下程式碼，能將輸入的 8 位元無號整數逐一位元反轉，如同 [LeetCode 190. Reverse Bits](https://leetcode.com/problems/reverse-bits/) 的描述。
```cpp=
#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 = ?
:::
### 延伸問題:
#### 1. 解釋上述程式碼運作原理
不懂就用例子來解，假設`x = 0b01101100`，翻轉後應該變成`reverse_x = 0b00110110`。放進rev8中，
##### Step 1. x = x>>4 | x<<4
```cpp=
0b00000110
| 0b11000000
---------------
x= 0b11000110 （翻轉前後4bits）
```
##### Step 2. ((x & 0xCC) >> 2) | (EXP2);
```cpp=
0b11000110 (x)
& 0b11001100 (0xCC)
----------------------
0b11000100 (x')
>> 2
----------------------
0b00110001 (x'')
```
> 這邊先跟0xCC 做AND Op，再右移2可以想像成保留4bits的前兩個bits。然後移位到後兩個bits。
因為無法從step3 `x = ((x & 0xAA) >> 1) | (EXP3)`回推，所以我們先猜想step2跟step1的目的是類似的，也就是翻轉前後2bits，看得到的答案最後能不能演化成reverse bit要的結果。所以經過| (EXP2)後應該會變成 0x00111001。
```cpp=
0b00110001 (x'')
| EXP2
----------------------
0b00111001 (x''')
所以可以知道 EXP2 = 0b00??100? (?可是1或0)就先當作0吧
```
所以要想辦法把 `x''(0b11000110)`變成`EXP2(0b00001000)`，主要思考的點是要讓`EXP2(0x00001000)`從右邊數來第四個bit是1的話，要怎麼使用左移或右移的情形產生。所以我們這邊先假設使用0x33對x''進行mask。
> 會使用0x33，是因為想要保留4bits中的後兩位。之後在left shift 2。模仿(x & 0xCC) >> 2
```cpp=
0b11000110 (x)
& 0b00110011 (0x33)
---------------------
0b00000010 (y')
<< 2 (在left shift 2)
---------------------
0b00001000 (EXP2)
```
這樣我們就可以得到`EXP2= (x & 0x33) << 2`
#### step3 ((x & 0xAA) >> 1) | (EXP3)
接著我們來思考`step3`。跟上面的情況類似，x在這邊是`0b00111001 (x''')`，兩個兩個bits交換後會得到0b00110110，ˊˋˊ就是我們想要得到的最終答案。也就是說前面step2的推理有可能是正確的。這邊先推理左半邊 `((x & 0xAA) >> 1)`。
```cpp=
0b00111001 (x''')
& 0b10101010 (0xAA)
---------------------
0b00101000
>>1
---------------------
0b00010100 (x'''')
```
再來思考右半邊，如果也是做類似的動作(masking掉其中一個bit，然後shift)
我們可以用`0b01010101`(0x55)，然後在left shift 1。
> 所以得知EXP3 = `(x & 0x55) << 1`
```cpp=
0b00111001 (x''')
& 0b01010101 (0x55)
---------------------
0b00010001
<<1
---------------------
0b00100010 (y)
```
把 `0b00010100 (x'''')`跟 `0b00100010 (y)`做 OR Operation。
```cpp=
0b00010100 (x'''')
| 0b00100010 (y)
---------------------
0b00110110 (final)
```
如果還是看不懂的話，可以參照此[文章](https://hackmd.io/@sysprog/bitwise-reverse#%E8%AA%B2%E5%89%8D%E6%B8%AC%E9%A9%97%E5%8F%83%E8%80%83%E8%A7%A3%E7%AD%94-Q1)，有精美圖片
#### 2. 在 Linux 核心原始程式碼找出類似技巧的實作並解說其應用場景
參見[linux/lib/packing.c](https://github.com/torvalds/linux/blob/9bc62afe03afdf33904f5e784e1ad68c50ff00bb/lib/packing.c#L32)
```cpp=
static u64 bit_reverse(u64 val, unsigned int width)
{
u64 new_val = 0;
unsigned int bit;
unsigned int i;
for (i = 0; i < width; i++) {
bit = (val & (1 << i)) != 0;
new_val |= (bit << (width - i - 1));
}
return new_val;
}
```
使用場景，同個[linux/lib/packing.c](https://github.com/torvalds/linux/blob/9bc62afe03afdf33904f5e784e1ad68c50ff00bb/lib/packing.c#L52)文件下。
```cpp=
static void adjust_for_msb_right_quirk(u64 *to_write, int *box_start_bit,
int *box_end_bit, u8 *box_mask)
{
int box_bit_width = *box_start_bit - *box_end_bit + 1;
int new_box_start_bit, new_box_end_bit;
*to_write >>= *box_end_bit;
*to_write = bit_reverse(*to_write, box_bit_width);
*to_write <<= *box_end_bit;
new_box_end_bit = box_bit_width - *box_start_bit - 1;
new_box_start_bit = box_bit_width - *box_end_bit - 1;
*box_mask = GENMASK_ULL(new_box_start_bit, new_box_end_bit);
*box_start_bit = new_box_start_bit;
*box_end_bit = new_box_end_bit;
}
```
## [測驗4](https://hackmd.io/@sysprog/linux2022-quiz3#%E6%B8%AC%E9%A9%97-4)
:::success
延伸〈[你所不知道的 C 語言：前置處理器應用篇](https://hackmd.io/@sysprog/c-preprocessor)〉，我們嘗試將 [foreach 巨集](https://en.wikipedia.org/wiki/Foreach_loop) 予以擴充，使得支援以下寫法:
```cpp
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
```
對應的巨集定義:
```cpp
#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 形式撰寫，符合[作業一](https://hackmd.io/@sysprog/linux2022-lab0)排版規範，且不該觸發編譯器警告訊息
2. 不該出現小括號 (即 `(` 和 `)`)
<mark>作答區</mark>
* `EXP4` = ?
* `EXP5` = ?
:::
### 1. 解釋上述程式碼運作原理
```cpp=
#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])
```
#### foreach_int
for loop 可以分為
##### 1. 起始條件: `unsigned _foreach_i = (((i) = ((int[]){__VA_ARGS__})[0]), 0)`
- `(int[]){__VA_ARGS__})`: 轉成integer array
- `(int[]){__VA_ARGS__})[0]`:拿到第一個integer
- `((i) = ((int[]){__VA_ARGS__})[0])`: 把第一個integer assign給 i
- 把第二個`0`，指派給`_foreach_i`
##### 2. 終止條件: `_foreach_i < sizeof((int[]){__VA_ARGS__}) / sizeof(int)`
- 當_foreach_i < `sizeof(integer array) / sizeof(int)`，就是一般的找integer array的長度。
##### 3. 更新條件: `(i) = ((int[]){__VA_ARGS__, 0})[EXP4]`
- 已知_foreach_i 作為index，所以要透過先做increment再取值來更新i。
> 所以`EXP4 = ++_foreach_i`
#### foreach_ptr
##### 1. 起始條件: `unsigned _foreach_i = (((i) = (void *) ((typeof(i)[]){__VA_ARGS__})[0]), 0)`
- 跟上面的分析一樣，只是這邊變成先把variable array變成(void*) (typeof(i)[])，然後在assign給i。而_foreach_i 也還是從0開始。
##### 2. 終止條件: `(i)`
- 判斷是不是null pointer
##### 3. 更新條件:
```cpp=
(i) = (void *) ((typeof(i)[]){__VA_ARGS__, NULL})[EXP5], \
_foreach_no_nullval(_foreach_i, i,((const void *[]) {__VA_ARGS__})))
```
我們先來看第二個function: _foreach_no_nullval
```cpp=
#define _foreach_no_nullval(i, p, arr) \
assert((i) >= sizeof(arr) / sizeof(arr[0]) || (p))
```
- 這邊是要判斷傳進去的index(_foreach_i)在小於array 的memory boundary的時候pointer 的值存不存在。（在大於等於memory boundary的時候assert值會自動唯一）否則的話就會assert fail。
>EXP5跟上面一樣，都是使用++當_foreach_i
### 2. 在 Linux 核心原始程式碼找出類似技巧的實作並解說其應用場景
在[linux/tools/perf/util/debug.h](https://github.com/torvalds/linux/blob/27151f177827d478508e756c7657273261aaf8a9/tools/perf/util/debug.h#L21)蠻多使用`__VA_ARGS__`的macro function，提供不同的debug print。
<details>
<summary> 看更多 </summary>
```cpp=
/* SPDX-License-Identifier: GPL-2.0 */
/* For debugging general purposes */
#ifndef __PERF_DEBUG_H
#define __PERF_DEBUG_H
#include <stdarg.h>
#include <stdbool.h>
#include <stdio.h>
#include <linux/compiler.h>
extern int verbose;
extern int debug_peo_args;
extern bool quiet, dump_trace;
extern int debug_ordered_events;
extern int debug_data_convert;
#ifndef pr_fmt
#define pr_fmt(fmt) fmt
#endif
#define pr_err(fmt, ...) \
eprintf(0, verbose, pr_fmt(fmt), ##__VA_ARGS__)
#define pr_warning(fmt, ...) \
eprintf(0, verbose, pr_fmt(fmt), ##__VA_ARGS__)
#define pr_warning_once(fmt, ...) ({ \
static int __warned; \
if (unlikely(!__warned)) { \
pr_warning(fmt, ##__VA_ARGS__); \
__warned = 1; \
} \
})
#define pr_info(fmt, ...) \
eprintf(0, verbose, pr_fmt(fmt), ##__VA_ARGS__)
#define pr_debug(fmt, ...) \
eprintf(1, verbose, pr_fmt(fmt), ##__VA_ARGS__)
#define pr_debugN(n, fmt, ...) \
eprintf(n, verbose, pr_fmt(fmt), ##__VA_ARGS__)
#define pr_debug2(fmt, ...) pr_debugN(2, pr_fmt(fmt), ##__VA_ARGS__)
#define pr_debug3(fmt, ...) pr_debugN(3, pr_fmt(fmt), ##__VA_ARGS__)
#define pr_debug4(fmt, ...) pr_debugN(4, pr_fmt(fmt), ##__VA_ARGS__)
/* Special macro to print perf_event_open arguments/return value. */
#define pr_debug2_peo(fmt, ...) { \
if (debug_peo_args) \
pr_debugN(0, pr_fmt(fmt), ##__VA_ARGS__); \
else \
pr_debugN(2, pr_fmt(fmt), ##__VA_ARGS__); \
}
#define pr_time_N(n, var, t, fmt, ...) \
eprintf_time(n, var, t, fmt, ##__VA_ARGS__)
#define pr_oe_time(t, fmt, ...) pr_time_N(1, debug_ordered_events, t, pr_fmt(fmt), ##__VA_ARGS__)
#define pr_oe_time2(t, fmt, ...) pr_time_N(2, debug_ordered_events, t, pr_fmt(fmt), ##__VA_ARGS__)
#define STRERR_BUFSIZE 128 /* For the buffer size of str_error_r */
union perf_event;
int dump_printf(const char *fmt, ...) __printf(1, 2);
void trace_event(union perf_event *event);
int ui__error(const char *format, ...) __printf(1, 2);
int ui__warning(const char *format, ...) __printf(1, 2);
#define ui__warning_once(format, ...) ({ \
static int __warned; \
if (unlikely(!__warned)) { \
ui__warning(format, ##__VA_ARGS__); \
__warned = 1; \
} \
})
void pr_stat(const char *fmt, ...);
int eprintf(int level, int var, const char *fmt, ...) __printf(3, 4);
int eprintf_time(int level, int var, u64 t, const char *fmt, ...) __printf(4, 5);
int veprintf(int level, int var, const char *fmt, va_list args);
int perf_debug_option(const char *str);
void debug_set_file(FILE *file);
void debug_set_display_time(bool set);
void perf_debug_setup(void);
int perf_quiet_option(void);
void dump_stack(void);
void sighandler_dump_stack(int sig);
#endif /* __PERF_DEBUG_H */
```
</details>
## [測驗 5](https://hackmd.io/@sysprog/linux2022-quiz3#%E6%B8%AC%E9%A9%97-5)
:::success
針對 LeetCode [29\. Divide Two Integers](https://leetcode.com/problems/divide-two-integers/)，以下是可能的實作:
```cpp=
#include <limits.h>
int divide(int dividend, int divisor)
{
int signal = 1;
unsigned int dvd = dividend;
if (dividend < 0) {
signal *= -1;
dvd = ~dvd + 1;
}
unsigned int dvs = divisor;
if (divisor < 0) {
signal *= -1;
dvs = ~dvs + 1;
}
int shift = 0;
while (dvd > (EXP6))
shift++;
unsigned int res = 0;
while (dvd >= dvs) {
while (dvd < (dvs << shift))
shift--;
res |= (unsigned int) 1 << shift;
EXP7;
}
if (signal == 1 && res >= INT_MAX)
return INT_MAX;
return res * signal;
}
```
請補完，使其行為符合預期。作答規範:
1. `EXP6` 和 `EXP7` 應以最簡潔的 C99 形式撰寫，符合[作業一](https://hackmd.io/@sysprog/linux2022-lab0)排版規範，且不該觸發編譯器警告訊息
2. 不該出現小括號 (即 `(` 和 `)`)
作答區
- `EXP6` = ?
- `EXP7` = ?
:::
### 1. 解釋上述程式碼運作原理，指出可改進之處，並予以實作
我們依然使用例子丟進去判斷。`dividend = 10 (0b1010)` 與 `divisor = 3 (0b0011)`。答案應該是3.33 (0b11.0101 0101 0101 0011 0010 0110)
- 因為本題類似於二進位的除法。`EXP6 = dvs << shift`
- 可以發現 res 很像是除法得商數。 (在例子中是0b11)，所以EXP7就像是餘數，dvd -= dvs << shift
優化的話可以使用`uint64_t shift = __builtin_clzll(dvs) - __builtin_clzll(dvd) + 1;`，效果比單使用while loop的情況好一些。
```cpp=
uint64_t divide_clzll(uint64_t dividend, uint64_t divisor)
{
uint64_t signal = 1;
unsigned int dvd = dividend;
if (dividend < 0) {
signal *= -1;
dvd = ~dvd + 1;
}
uint64_t dvs = divisor;
if (divisor < 0) {
signal *= -1;
dvs = ~dvs + 1;
}
uint64_t shift = __builtin_clzll(dvs) - __builtin_clzll(dvd) + 1;
uint64_t res = 0;
while (dvd >= dvs) {
while (dvd < (dvs << shift)){
shift--;
}
res |= (uint64_t) 1 << shift;
dvd -= dvs << shift;
}
if (signal == 1 && res >= INT_MAX)
return INT_MAX;
return res * signal;
}
```
### 2. 在 Linux 核心原始程式碼中找出針對整數/浮點數/定點數除法特別撰寫的程式碼，並予以討論
## [測驗6](https://hackmd.io/@sysprog/linux2022-quiz3#%E6%B8%AC%E9%A9%97-6)
:::success
針對 LeetCode [149. Max Points on a Line](https://leetcode.com/problems/max-points-on-a-line/)，以下是可能的實作:
```cpp=
#include <stdbool.h>
#include "list.h"
struct Point {
int x, y;
};
struct point_node {
int p1, p2;
struct list_head link;
};
static bool can_insert(struct list_head *head, int p1, int p2)
{
struct point_node *pn;
list_for_each_entry (pn, head, link)
return EXP8;
return true;
}
static int gcd(int x, int y)
{
while (y) {
int tmp = y;
y = x % y;
x = tmp;
}
return x;
}
static int maxPoints(struct Point *points, int pointsSize)
{
if (pointsSize <= 2)
return pointsSize;
int i, j, slope_size = pointsSize * pointsSize / 2 + 133;
int *dup_cnts = malloc(pointsSize * sizeof(int));
int *hori_cnts = malloc(pointsSize * sizeof(int));
int *vert_cnts = malloc(pointsSize * sizeof(int));
int *slope_cnts = malloc(slope_size * sizeof(int));
memset(hori_cnts, 0, pointsSize * sizeof(int));
memset(vert_cnts, 0, pointsSize * sizeof(int));
memset(slope_cnts, 0, slope_size * sizeof(int));
for (i = 0; i < pointsSize; i++)
dup_cnts[i] = 1;
struct list_head *heads = malloc(slope_size * sizeof(*heads));
for (i = 0; i < slope_size; i++)
INIT_LIST_HEAD(&heads[i]);
for (i = 0; i < pointsSize; i++) {
for (j = i + 1; j < pointsSize; j++) {
if (points[i].x == points[j].x)
hori_cnts[i]++, hori_cnts[j]++;
if (points[i].y == points[j].y)
vert_cnts[i]++, vert_cnts[j]++;
if (points[i].x == points[j].x && points[i].y == points[j].y)
dup_cnts[i]++, dup_cnts[j]++;
if (points[i].x != points[j].x && points[i].y != points[j].y) {
int dx = points[j].x - points[i].x;
int dy = points[j].y - points[i].y;
int tmp = gcd(dx, dy);
dx /= tmp;
dy /= tmp;
int hash = dx * dy - 1333 * (dx + dy);
if (hash < 0)
hash = -hash;
hash %= slope_size;
if (can_insert(&heads[hash], i, j)) {
struct point_node *pn = malloc(sizeof(*pn));
pn->p1 = i;
pn->p2 = j;
EXP9;
}
}
}
}
for (i = 0; i < slope_size; i++) {
int index = -1;
struct point_node *pn;
list_for_each_entry (pn, &heads[i], link) {
index = pn->p1;
slope_cnts[i]++;
}
if (index >= 0)
slope_cnts[i] += dup_cnts[index];
}
int max_num = 0;
for (i = 0; i < pointsSize; i++) {
if (hori_cnts[i] + 1 > max_num)
max_num = hori_cnts[i] + 1;
if (vert_cnts[i] + 1 > max_num)
max_num = vert_cnts[i] + 1;
}
for (i = 0; i < slope_size; i++) {
if (slope_cnts[i] > max_num)
max_num = slope_cnts[i];
}
return max_num;
}
```
請補完，使其行為符合預期。作答規範:
1. `EXP8` 和 `EXP9` 應以最簡潔的 C99 形式撰寫，符合[作業一](https://hackmd.io/@sysprog/linux2022-lab0)排版規範，且不該觸發編譯器警告訊息
2. `EXP8` 不該出現小括號 (即 `(` 和 `)`)
3. `EXP9` 為包含 `list_` 開頭巨集的單一敘述
<mark>作答區</mark>
* `EXP8` = ?
* `EXP9` = ?
:::
### 解釋上述程式碼運作原理，指出可改進之處，並予以實作
- #37-#43 Initialization of dup_cnts, hori_cnts, vert_cnts.
- #48-#50 Initialization of heads。heads是長度為slope_size的array。之後會用作hash table，他的index是由 `hash = dx * dy - 1333 * (dx + dy)`組成。
- #54-#61 把垂直, 平行跟重複的點都存起來。
- #63-#72 算出剩下的兩點的hash number
- #73 can_insert function
- 需要確定放進來的兩點跟之前的點有重複？所以設計`EXP8=pn->p1 == p1`
- #77 `EXP9`應該會跟linux list_head api有關。list_add_tail(pn->link,&heads[hash])
- #85-90 把重複的點也計算到slope_cnt中。
- #94-104 去比較說是平行的點多，垂直的多，還是有斜率的點多。把最大值記錄下來。
[隔壁同學很不錯的解析](https://hackmd.io/@at0mCe11/linux2022-quiz3#%E6%B8%AC%E9%A9%97-6)
### 擴充 LeetCode 題目，考慮更多座標點的輸入 (例如超過 10 萬個) 時，設計有效的資料結構以降低記憶體開銷，並確保快速的執行
## [測驗7](https://hackmd.io/@sysprog/linux2022-quiz3#%E6%B8%AC%E9%A9%97-7)
:::success
考慮 `ilog32` 函式可針對給定的 32 位元無號數，計算扣除開頭的 `0`，最少需要多少位元才可儲存 (the minimum number of bits required to store an unsigned 32-bit value without any leading zero bits)，以下是一個可能的實作:
```cpp=
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;
}
```
請補完，使其行為符合預期。作答規範:
1. `EXP10` 和 `EXP11` 應以最簡潔的 C99 形式撰寫，符合[作業一](https://hackmd.io/@sysprog/linux2022-lab0)排版規範，且不該觸發編譯器警告訊息
2. `EXP11` 不該出現小括號 (即 `(` 和 `)`)
3. `EXP10` 和 `EXP11` 皆包含 `>` 運算子
作答區
- `EXP10` = ?
- `EXP11` = ?
:::
### 解釋上述程式碼運作原理
####
可以把程式分成#3-6, #7-9, #10-12, #13-15。
#3-6 `0xFFFFU` 是 `0b1111 1111 1111 1111`，所以比`0xFFFFU`大就代表MSB是介於16-31。也就是說當 m= (v > 0xFFFFU) << 4。也就說要 m=0x10，v>>m 就會變成右移16 bits。然後ret|=m是把ret變成'm=0x10'假設`v`>`0xFFFFU`的情況。在右移16bits後，v 的 MSB變成位於 0-15bits間。
#7-9 因為目前v的MSB位置是 `0 <= MSB <= 15`，跟`0xFFU`是 `0b1111 1111`比較是要找出v是不是介於9-15bit，如果是的話則右移8(`m = (v > 0xFFU)<<3`)。讓MSB介於0-7。然後再把`m`的值存到ret。
#10-12 目前 MSB位於： `0 <= MSB <= 7`，跟`0xFU`比較是要看v是介於0-3 還是4-7。如果是後者的話，就右移4 (`m = (v>0xFU)<<2`)。再把m記錄下來。
#13-15 同理，目前 MSB位於： `0 <= MSB <= 3`。要判斷是不是介於0-1還是2-3。所以EXP10是
`m = (v>0x3U)<<1`。位移完會把MSB的範圍變成0<=MSB<=1。
#16 最後利用 `ret |= v > 0x1`去判斷是否大於1，如果是的話，則直接存起來。
### 在 Linux 核心原始程式碼找出類似實作並解說其應用場景
### 研讀論文《[Using de Bruijn Sequences to Index a 1 in a Computer Word](http://supertech.csail.mit.edu/papers/debruijn.pdf)》，探討缺乏硬體 ctz/clz 指令的微處理器上，如何實作 branchless 的 `ilog`
### 運用〈[你所不知道的 C 語言：前置處理器應用篇](https://hackmd.io/@sysprog/c-preprocessor)〉和〈[你所不知道的 C 語言：數值系統篇](https://hackmd.io/@sysprog/c-numerics)〉提及的技巧，實作編譯時期 (compile-time) 的 `ilog2` 實作
```
```
## [測驗8](https://hackmd.io/@sysprog/linux2022-quiz3#%E6%B8%AC%E9%A9%97-8)
:::success
考慮以下 C++ 二元搜尋樹的程式:
```
typedef struct tnode *tree;
struct tnode {
int data;
tnode *left;
tnode *right;
tnode(int d)
{
data = d;
left = right = 0;
}
};
void remove_data(tree &t, int d)
{
tnode *p = t;
tnode *q;
while (p != 0 && p->data != d) {
if (d < p->data) {
q = p;
p = p->left;
} else {
q = p;
p = p->right;
}
}
if (p != 0) {
if (p->left == 0)
if (p == t)
t = p->right;
else if (p == q->left)
q->left = p->right;
else
q->right = p->right;
else if (p->right == 0)
if (p == t)
t = p->left;
else if (p == q->left)
q->left = p->left;
else
q->right = p->left;
else {
tnode *r = p->right;
while (r->left) {
q = r;
r = r->left;
}
p->data = r->data;
if (r == p->right)
p->right = r->right;
else
q->left = r->right;
p = r;
}
delete p;
}
}
```
函式 `remove_data` 嘗試將指定的資料，自給定的二元搜尋樹移除，但原本的 `remove_data` 過於冗長，於是我們可善用 indirect pointer 改寫為以下:
```
void remove_data(tree &t, int d)
{
tnode **p = &t;
while (*p != 0 && (*p)->data != d) {
if (d < (*p)->data)
EXP12;
else
EXP13;
}
tnode *q = *p;
if (!q)
return;
if (!q->left)
*p = q->right;
else if (!q->right)
*p = q->left;
else {
tnode **r = &q->right;
while ((*r)->left)
r = EXP14;
q->data = (*r)->data;
q = *r;
*r = q->right;
}
delete q;
}
```
請補完，使其行為符合預期。作答規範:
1. `EXP12`, `EXP13` 和 `EXP14` 應以最簡潔的 C99 形式撰寫，符合[作業一](https://hackmd.io/@sysprog/linux2022-lab0)排版規範，且不該觸發編譯器警告訊息，並善用 indirect pointer 的技巧來撰寫
2. `EXP12`, `EXP13` 和 `EXP14` 皆不該出現 `;`
作答區
- `EXP12` = ?
- `EXP13` = ?
- `EXP14` = ?
:::
```cpp=
if (d < p->data) {
q = p;
p = p->left;
} else {
q = p;
p = p->right;
}
```
應該跟
```cpp=
if (d < (*p)->data)
p = &(*p)->left;
else
p = &(*p)->right;
```
等價
Sign in with Wallet
Connect another wallet