Linux 内核列表实现是否导致 UB？

Question

先决条件：

根据 C standard，会产生无效指针的指针算法会导致未定义的行为。
Linux 源代码 seems to conform 符合 C 标准，希望与大多数体系结构兼容。
Linux's list implementation 包含以下代码（保留格式，另一个问题的想法可能是如何使用 Whosebug 语法设置适当的制表宽度）：

#define list_entry(ptr, type, member) \
    container_of(ptr, type, member)

#define list_next_entry(pos, member) \
    list_entry((pos)->member.next, typeof(*(pos)), member)

#define list_first_entry(ptr, type, member) \
    list_entry((ptr)->next, type, member)

#define list_entry_is_head(pos, head, member)               \
    (&pos->member == (head))

#define list_for_each_entry(pos, head, member)              \
    for (pos = list_first_entry(head, typeof(*pos), member);    \
         !list_entry_is_head(pos, head, member);            \
         pos = list_next_entry(pos, member))

上述列表实现的典型用例具有struct A类型的结构，包含struct B.

Q：假设 offsetof(struct B, entry_in_list) > offsetof(struct A, list_head) 并实现了以下循环：

struct A* A_ptr = something_meaningful;
struct B* pos = NULL;
list_for_each_entry(pos, &A_ptr->list_head, entry_in_list) {
  do_something();
}

然后 list_next_entry(pos, member) 的最后（在循环退出之前）评估将扩展为：

container_of(A_ptr->list_head, struct B, entry_in_list) = 
 = (char*)A_ptr->list_head - offsetof(struct B, entry_in_list) =
 = (char*)A_ptr + offsetof(struct A, list_head) - offsetof(struct B, entry_in_list)

，根据我们的假设，它会指向 A 结构之前的区域。假设这个区域不包含分配的内存，container_of() 宏的结果将是一个无效指针，从而导致 Linux 中的 UB（通常情况下是 OFC）。这个推理是合理的还是我弄错了？

或者标准中是否有某些部分被普遍认为不值得遵循？

Answer 1

正如OP所怀疑的那样，list_for_each_entry(pos, head, member)宏的实现依赖于C语言中的未定义行为，以便循环终止条件!list_entry_is_head(pos, head, member)变成假的。

假设列表是非空的，那么在最后一次迭代之后，for 循环的第三个“推进”表达式在地址 [=14] 处产生一个指向无效 typeof(*pos) 的指针=] 在 head 指向的 struct list_head 之前的字节。它依赖于 &pos->member 但比较等于 head.

虽然它依赖于未定义的行为，但编译器很难确定 pos 在技术上是一个无效指针。只要 pos 和 head 都指向同一个平面地址 space，Linux 内核就设法摆脱了这种规则的扭曲。

另一种方法是 #include <linux/list.h> 根本不提供 list_for_each_entry(pos, head, member) 宏，代码使用 list_for_each(pos, head) 和 list_entry(ptr, type, member) 宏（其中 pos 是 struct list_head * 而 ptr 是 type *)，但这通常需要代码中的额外变量。

Answer 2

编译内核时进行的额外断言。这些实际上到处都在使用。

指针可能加载了未分配的地址。您会在每个系统调用条目上看到它。处理此类指针时必须特别小心，因为取消引用它们比崩溃更糟糕。
取消引用 NULL 指针不一定会崩溃；并且不允许编译器假定取消引用 NULL 的路径是不可访问的。（这个是在 NULL 指针优化删除了安全检查之后才添加的。）在某些体系结构上实际上有一些东西；在其他架构上，它只是另一个用户模式指针。

编译器选项告诉编译器这些都是真的。（事实上，第一个在平面模型中通常被认为是正确的，内核就是。）

传递给 gcc 的标志是 -fno-delete-null-pointer-checks。空指针优化改动参考：https://lwn.net/Articles/342420/

Answer 3

你是对的，这是未定义的行为。根据 Richard Biener 的说法，this kind of undefined behavior is not supported/made defined by -fno-strict-aliasing。（Clang 也将其视为未定义。）

这种特殊的错误编译是在 Open vSwitch 中观察到的，但它的列表宏显然是从内核中建模的 after/copied。为什么内核能逃脱它？

它是用 -fno-strict-aliasing 构建的（尽管这对这种特殊情况没有帮助）。
内核很少使用 LTO 构建。
内核不使用堆栈上的列表头。
编译器无法识别内核分配函数。

因此，编译器不会观察 invalid/impossible 对象引用，也不会基于此进行优化。

Linux 内核列表实现是否导致 UB？

Does Linux kernel list implementation cause UB?

c

linked-list

list

linux-kernel