近期在閱讀由Jserv撰寫的[Linux 核心原始程式碼巨集: max, min](https://hackmd.io/@sysprog/linux-macro-minmax)時發現最新版本的`max`, `min`已經改變了實作方式，所以本篇記錄了在閱讀前人筆記時遇到的問題以及新的實作方式我注意到的細節。

# 舊版本的`min`和`max`

#define __is_constexpr(x) \                   
    (sizeof(int) == sizeof(*(8 ? ((void *)((long)(x) * 0l)) : (int *)8)))

#define __typecheck(x, y) \
    (!!(sizeof((typeof(x) *)1 == (typeof(y) *)1)))

#define __no_side_effects(x, y) \             
    (__is_constexpr(x) && __is_constexpr(y))

#define __safe_cmp(x, y) \
    (__typecheck(x, y) && __no_side_effects(x, y))
                
#define __cmp(x, y, op) ((x) op (y) ? (x) : (y))
                
#define __cmp_once(x, y, unique_x, unique_y, op) ({ \
    typeof(x) unique_x = (x); \
    typeof(y) unique_y = (y); \
    __cmp(unique_x, unique_y, op); })

#define __careful_cmp(x, y, op) \
    __builtin_choose_expr(__safe_cmp(x, y), \
        __cmp(x, y, op), \
        __cmp_once(x, y, __UNIQUE_ID(__x), __UNIQUE_ID(__y), op))
#define max(x, y)       __careful_cmp(x, y, >)

## What does the macro `__typecheck` do?

#define __typecheck(x, y) \
    (!!(sizeof((typeof(x) *)1 == (typeof(y) *)1)))
#define __safe_cmp(x, y) \
    (__typecheck(x, y) && __no_side_effects(x, y))

`__typecheck`的[第一次](https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/commit/include/linux/kernel.h?id=3c8ba0d61d04ced9f8d9ff93977995a9e4e96e91)出現是在`kernel.h`中，後來把`min`跟`max`[移動到`minmax.h`](https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/commit/include/linux/kernel.h?id=b296a6d53339a79082c1d2c1761e948e8b3def69)時，也跟著一起搬到`minmax.h`。

乍看之下以為`__safe_cmp(x, y)`會先檢查兩者的型態是否相同，若不同則判斷為`false`。但是仔細解讀`__typecheck(x, y)`會發現根本不是這麼回事!

先把整個巨集拆開來看

(
    !!(
        sizeof(
            (typeof(x) *)1 == (typeof(y) *)1
        )
    )
)

1. `==`的兩邊是`(typeof(x or y) *) 1`這只是把`int 1`轉換成指向`x`或`y`型態的指標。
2. `==`本身會去比較兩邊是否相等，相等的定義在C11的§6.5.9，最後我們會得到一個`==`的回傳值。
> — both operands have arithmetic type;
— both operands are pointers to qualified or unqualified versions of compatible types;
— one operand is a pointer to an object type and the other is a pointer to a qualified or unqualified version of void; or
— one operand is a pointer and the other is a null pointer constant.
3. `sizeof(X)`會拿到`X`的型態，C11的§6.5.9第3點提到，不管結果是否相等，型態都是`int`，所以不管`x`跟`y`的型態是否相同，都是呼叫`sizeof(int)`
> The == (equal to) and != (not equal to) operators are analogous to the relational operators except for their lower precedence.108) Each of the operators yields 1 if the specified relation is true and 0 if it is false. The result has type int. For any pair of operands, exactly one of the relations is true
4. 最後，`!!`代表的是將數值改變成0或1，由於永遠都是`sizeof(int)`，因此最終的結果永遠都是1


`__typecheck(x, y)` 的功能是在編譯階段檢測比較操作中的型態差異。透過 `-Wcompare-distinct-pointer-types` 選項，它會生成相應的警告，而此警告默認情況下是啟用的。然而，值得注意的是，這不會對 `cmp` 函數的執行造成任何影響。

# 新版本的`min`和`max`([commit](https://github.com/torvalds/linux/commit/867046cc7027703f60a46339ffde91a1970f2901))

/* True for a non-negative signed int constant */
#define __is_noneg_int(x)	\
	(__builtin_choose_expr(__is_constexpr(x) && __is_signed(x), x, -1) >= 0)
/* is_signed_type() isn't a constexpr for pointer types */
#define __is_signed(x) 								\
	__builtin_choose_expr(__is_constexpr(is_signed_type(typeof(x))),	\
		is_signed_type(typeof(x)), 0)

/* True for a non-negative signed int constant */
#define __is_noneg_int(x)	\
	(__builtin_choose_expr(__is_constexpr(x) && __is_signed(x), x, -1) >= 0)

#define __types_ok(x, y) 					\
	(__is_signed(x) == __is_signed(y) ||			\
		__is_signed((x) + 0) == __is_signed((y) + 0) ||	\
		__is_noneg_int(x) || __is_noneg_int(y))

#define __cmp_op_min <
#define __cmp_op_max >

#define __cmp(op, x, y)	((x) __cmp_op_##op (y) ? (x) : (y))

#define __cmp_once(op, x, y, unique_x, unique_y) ({	\
	typeof(x) unique_x = (x);			\
	typeof(y) unique_y = (y);			\
	static_assert(__types_ok(x, y),			\
		#op "(" #x ", " #y ") signedness error, fix types or consider u" #op "() before " #op "_t()"); \
	__cmp(op, unique_x, unique_y); })

#define __careful_cmp(op, x, y)					\
	__builtin_choose_expr(__is_constexpr((x) - (y)),	\
		__cmp(op, x, y),				\
		__cmp_once(op, x, y, __UNIQUE_ID(__x), __UNIQUE_ID(__y)))

## What's new?
- `__is_signed(x)`
- `__is_noneg_int(x)`
- `__types_ok(x, y)`

以及在`__cmp_once`中使用`static_assert`，可以在編譯階段判斷`x`跟`y`的型態是否會在比較時造成問題，如果會造成問題就會產生compile-time error。

### `__is_signed`

__builtin_choose_expr(
    __is_constexpr(
        is_signed_type(typeof(x))
    ),
    is_signed_type(typeof(x)),
    0
)

如果[`is_signed_type`](####is_signed_type)的結果是常量值，則會返回`is_signed_type`的結果；否則代表詢問一個指標是否為有號數，因此結果為0。

#### `is_signed_type`
這個巨集定義在[`linux/compiler.h`](https://github.com/torvalds/linux/blob/master/include/linux/compiler.h#L242C1-L242C1)中

#define is_signed_type(type) (((type)(-1)) < (__force type)1)

其中的`__force`代表可以強制轉型的attribute: `__attribute__((force))`
所以簡單來說，這個巨集用於檢查$-1 < 1$是否成立，因為我們知道在無號數型態時，等式是不成立的。

另外，如果傳入的型別是指標，依據C11的§6.5.8第5點所述，`>` 比較兩個指標時是判斷兩者是否指向相同的 `object`。由於在編譯時無法確定指向的具體物件，因此`is_signed_type` 的結果在這種情況下不是一個constant value。

> When two pointers are compared, the result depends on the relative locations in the address space of the objects pointed to.

## `__is_noneg_int(x)`

#define __is_noneg_int(x)	\
	(__builtin_choose_expr(__is_constexpr(x) && __is_signed(x), x, -1) >= 0)

如果`x`是constant value並且為有號數，則回傳`x`是否大於等於0，否則回傳`false`

## `__types_ok(x, y)`

#define __types_ok(x, y) 					\
	(__is_signed(x) == __is_signed(y) ||			\
		__is_signed((x) + 0) == __is_signed((y) + 0) ||	\
		__is_noneg_int(x) || __is_noneg_int(y))

四個判斷式，只要任意一個為真，就是可以拿來比較的兩個數值
- `__is_signed(x) == __is_signed(y)`: 判斷是否同為有號數或無號數，因為相同型態的比較不會發生問題
- `__is_noneg_int(x)`: 若`x`是非負有號數，代表`y`是無號數，而無號數跟非負有號數的比較並不會造成問題
- `__is_noneg_int(y)`: 走到這一步代表`x`是無號數，所以確認`y`是否為非負有號數
- `__is_signed((x) + 0) == __is_signed((y) + 0)`

C11標準中的第6.5.9節中第2項規定，當使用`+`、`-`、`>>`、`<<`或`~`運算子時，如果結果可以用`int`表示，則回傳型態將為`int`；反之，若結果不能用`int`表示，則回傳型態為`unsigned int`。這種轉換被稱為**integer promotions**。

簡單來說，根據這個條件，只要無號數的變數數值不超過有號數的最大值，我們就可以將其視為有號數進行比較。在[這次提交](https://lkml.kernel.org/r/[e-mail])中提供了這個例外的情境，當比較`unsigned short/char`與`signed int`時，由於`unsigned short/char`會被轉換成`signed int`，而且所有`unsigned short/char`表示的數值都在`signed int`的範圍內，因此這樣的轉換不會影響比較的結果。
> If an int can represent all values of the original type (as restricted by the width, for a bit-field), the value is converted to an int; otherwise, it is converted to an unsigned int. These are called the integer promotions. 58) All other types are unchanged by the integer promotions.
>
> 58) The integer promotions are applied only: as part of the usual arithmetic conversions, to certain argument expressions, to the operands of the unary +, -, and ~ operators, and to both operands of the shift operators, as specified by their respective subclauses.

# Reference
- [Linux 核心原始程式碼巨集: max, min](https://hackmd.io/@sysprog/linux-macro-minmax)
- [ISO/IEC 9899:201x](https://www.open-std.org/jtc1/sc22/wg14/www/docs/n1570.pdf)
- [linux/include/linux/compiler.h](https://github.com/torvalds/linux/blob/master/include/linux/compiler.h)
- [linux/include/linux/minmax.h](https://github.com/torvalds/linux/blob/master/include/linux/minmax.h)
- [linux内核：__user,__kernel,__safe,__force,__iomem
](https://blog.csdn.net/Rong_Toa/article/details/86585086)