未定义大小为0的c-qsort



我有一份报告,未经我确认,但来源可靠,代码

qsort(a, n, sizeof *a, cmpfunc);

由现代版本的gcc编译,就好像是编写的一样

if(n == 0)
__builtin_trap();
qsort(a, n, sizeof *a, cmpfunc);

显然,认为用n == 0调用qsort是未定义的行为。

[编辑:这里的整个前提被发现是错误的;请参阅下面的"更新2"。]

有人指出,Posix明确支持n == 0的情况,,但显然没有现存版本的C标准这样做

所以显而易见的问题是:

  1. n = 0调用qsort实际上是C中未定义的行为吗
  2. 是否每个用任意n调用qsort的程序都必须检查n == 0,而在这种情况下不调用qsort
  3. 为什么gcc会执行这个";优化";?即使您认为用n == 0调用qsort是未定义的,这似乎会稍微减慢每个未定义程序的速度

快速排序的教科书实现(我知道qsort不是必需的)几乎不能正确处理n = 0。我想知道,如果初始调用有n == 0,那么gcc在这里的行为是否是为了防止qsort实现在某种程度上比__builtin_trap做得更糟糕?


更新:感谢迄今为止的回复听起来gcc错了正如我所说,我自己还没有确认这个结果,但我正在努力找出哪个版本的gcc以及用哪个优化标志观察到了这个问题。


更新2:我提到的原始报告有错误。两个关键澄清:

  1. gcc实际上是在检查a == 0,而不是n == 0。这显然是一个完全不同的问题:正如这个线程(和其他线程)已经证实的那样,在空指针上调用qsort的问题要大得多,而且几乎可以肯定是形式上未定义的
  2. 有问题的编译包括-fsanitize=undefined-fsanitize-undefined-trap-on-error标志,因此当然gcc在检查无意的空指针方面非常严格(甚至以效率为代价)

很抱歉收到错误信息和跑题。恐怕这个问题现在是";不能再现或是由打字错误引起的";,在此基础上,我投了一票。

值得一提的是,gcc的版本是12.2.1。

正如其他人所提到的,最新版本的C标准以及POSIX明确允许nmemb参数为0。但是,C89标准中缺少这种语言。

C89第4.10.5节(相当于C90第7.10.5节)不包含bsearchqsort规范之前允许的额外段落。因此,在严格的C89模式下编译可能会生成问题中的有效代码。

C89模式下的最新gcc没有显示违规行为:

https://godbolt.org/z/YhKoGEre7

但其他版本可以想象。我还没有全部检查。

更新:

根据这篇帖子,这引发了最初的问题:

https://mm.icann.org/pipermail/tz/2022-October/032096.html

这是对它的回应:

https://mm.icann.org/pipermail/tz/2022-October/032107.html

在带有-fsanitize=undefined选项的gcc 12.2上观察到有问题的行为,并且报告该行为的人员在读取程序集时出现错误。上面的godbolt链接显示了以下使用给定编译器和选项的反汇编:

mov     eax, DWORD PTR [rbp-20]
movsx   rbx, eax
mov     edi, OFFSET FLAT:.Lubsan_data0
call    __ubsan_handle_nonnull_arg
mov     ecx, OFFSET FLAT:cmpfunc
mov     edx, 4
mov     rsi, rbx
mov     edi, 0
call    qsort
mov     eax, 0

检查实际上是查看base是否为NULL,而不是nmemb是否为0。在这种情况下,未定义的行为。

  1. 在C中调用n=0的qsort实际上是未定义的行为吗

它是每种语言版本中定义良好的行为。

  1. 是否每个调用任意n的qsort的程序都必须检查n==0,而在这种情况下不调用qsort

应用程序程序员的源代码不需要执行任何此类检查。至于生成程序的行为,qsort库函数不应该在内部调用比较函数,所以它本质上与根本不调用qsort是一样的,相当于no-op。

为什么gcc会执行这个"优化";?即使您认为调用n=0的qsort是未定义的,这似乎会稍微减慢每个未定义程序的速度。

因为n=0是一种特殊的、定义良好的情况,它允许编译器优化(不调用函数)。当然,一个额外的分支并不一定是一个优化。


来源:

C17 7.22.5.2

void qsort(void *base, size_t nmemb, size_t size,
int (*compar)(const void *, const void *));

C17 7.22.5重点矿井:

这些实用程序使用比较函数来搜索或排序未指定的数组类型如果声明为size_t nmemb的参数指定了函数的数组长度,则nmemb在调用该函数时可以为零;比较函数未被调用,搜索未找到匹配的元素,排序不执行重排如前所述,此类调用上的指针参数仍应具有有效值7.1.4。

来自POSIX标准(强调是我的):

[CX]本参考页中描述的功能符合ISO C标准。此处描述的要求和ISO C标准是无意的。本卷IEEE Std 1003.1-2001遵循ISO C标准。

CCD_ 32函数将对CCD_,其初始元素由CCD_ 34指向。每个的大小对象,以字节为单位,由width参数指定如果nel参数的值为零不应调用compar,也不应进行重新排列

正如其他人所提到的,qsort的C标准库函数需要正确处理零大小。

但这是从程序员的角度来看的。C标准对生成的机器代码没有任何规定,只是它应该按照它应该的方式行事。

对于C编译器来说,生成一个二进制文件是完全有效的,该文件调用的排序函数不能正确处理0的大小,只要它在它之前添加了一个零检查。但如果大小为零,我在C89标准中找不到任何允许UB的东西。

在实践中,规范中的附加文本并没有增加太多内容。相关部分是:

nmemb在调用该函数时可以具有值零;比较函数不称为

这意味着这个片段:

#include <stdio.h>
#include <stdlib.h>
int cmpfunc (const void * a, const void * b) {
puts("foobar"); // To see if this function is executed
return ( *(int*)a - *(int*)b );
}
int main (void) {
int values[1] = {42};
qsort(values, 0, sizeof *values, cmpfunc);
}

保证不打印";foobar";如果使用C99或更高版本进行编译。但如果使用C89进行编译,则可能会发生这种情况。或者不是。但这段代码在C89或更高版本中都不会调用未定义的行为。

John Bollinger在的评论部分提出了一个有趣的观点

如果没有第二个参数可能是0的明确说明,我可以为UB做一个参数。它将围绕这样一个事实展开,即第二个参数需要是指向第一个参数的数组的长度,而C不具有零长度的数组。但我仍然希望每个C实现都能以规范的后续版本所描述的自然方式来处理这种情况

在没有明确要求允许大小为零的情况下,有一点回旋余地来解释它是UB。然而,C标准明确地将许多内容声明为UB,但不是这样。

我个人的观点(我很想知道是否有任何官方共识)是,如果规范是模糊的,但没有明确表示为UB,那么编译器不应该使用模糊性进行优化。这样做将是恶意的合规

最新更新