为什么/如何在此签名溢出测试中编译未定义的行为,以便它可以在x86上工作但不能在ARM64上工作？

Question

当我在断言测试运行期间遇到一个奇怪的问题时,我正在自学CSAPP并得到一个奇怪的结果.

我不知道该怎么开始这个问题,所以让我先得到代码(文件名在评论中可见):

// File: 2.30.c
// Author: iBug

int tadd_ok(int x, int y) {
    if ((x ^ y) >> 31)
        return 1;  // A positive number and a negative integer always add without problem
    if (x < 0)
        return (x + y) < y;
    if (x > 0)
        return (x + y) > y;
    // x == 0
    return 1;
}

// File: 2.30-test.c
// Author: iBug

#include <assert.h>

int tadd_ok(int x, int y);

int main() {
    assert(sizeof(int) == 4);

    assert(tadd_ok(0x7FFFFFFF, 0x80000000) == 1);
    assert(tadd_ok(0x7FFFFFFF, 0x7FFFFFFF) == 0);
    assert(tadd_ok(0x80000000, 0x80000000) == 0);
    return 0;
}

和命令:

gcc -o test -O0 -g3 -Wall -std=c11 2.30.c 2.30-test.c
./test

(旁注:-O命令行中没有任何选项,但由于它默认为0级,因此显式添加-O0不应该有太大变化.)

上面两个命令在我的Ubuntu VM(amd64,GCC 7.3.0)上运行得很好,但其中一个断言在我的Android手机上失败了(AArch64或armv8-a,GCC 8.2.0).

2.30-test.c:13: main: assertion "tadd_ok(0x7FFFFFFF, 0x7FFFFFFF) == 0" failed

请注意,第一个断言已通过,因此int在平台上保证为4个字节.

所以我gdb试着通过手机试图获得一些见解:

(gdb) l 2.30.c:1
1       // File: 2.30.c
2       // Author: iBug
3
4       int tadd_ok(int x, int y) {
5           if ((x ^ y) >> 31)
6               return 1;  // A positive number and a negative integer always add without problem
7           if (x < 0)
8               return (x + y) < y;
9           if (x > 0)
10              return (x + y) > y;
(gdb) b 2.30.c:10
Breakpoint 1 at 0x728: file 2.30.c, line 10.
(gdb) r
Starting program: /data/data/com.termux/files/home/CSAPP-2019/ch2/test
warning: Unable to determine the number of hardware watchpoints available.
warning: Unable to determine the number of hardware breakpoints available.

Breakpoint 1, tadd_ok (x=2147483647, y=2147483647)
    at 2.30.c:10
10              return (x + y) > y;
(gdb) p x
$1 = 2147483647
(gdb) p y
$2 = 2147483647
(gdb) p (x + y) > y
$3 = 0
(gdb) c
Continuing.
2.30-test.c:13: main: assertion "tadd_ok(0x7FFFFFFF, 0x7FFFFFFF) == 0" failed

Program received signal SIGABRT, Aborted.
0x0000007fb7ca5928 in abort ()
   from /system/lib64/libc.so
(gdb) d 1
(gdb) p tadd_ok(0x7FFFFFFF, 0x7FFFFFFF)
$4 = 1
(gdb)

正如您在GDB输出中看到的那样,结果非常不一致,因为已达到return语句2.30.c:10,返回值应为0,但函数仍返回1,使断言失败.

请提供一个想法,我在这里错了.

---

请尊重我所呈现的内容.只是说UB没有关联平台,特别是GDB输出,没有任何帮助.

Answer 1

签名溢出是ISO C中的未定义行为.您无法可靠地导致它,然后检查它是否发生.

在表达式中(x + y) > y;,允许编译器假定x+y不溢出(因为那将是UB).因此,它优化到检查x > 0. (是的,真的,gcc甚至这样做-O0).

此优化是gcc8中的新增功能.它在x86和AArch64上是一样的; 您必须在AArch64和x86上使用不同的GCC版本.(即使在-O3,gcc7.x和早期(故意？)错过这个优化.clang7.0没有做它的.实际上他们做的一个32位的添加和比较,他们也将错过优化tadd_ok来return 1,或者add和检查溢出标志(V在ARM上,OF在x86上).Clang的优化asm是一个有趣的混合>>31,OR和一个XOR操作,但-fwrapv实际上改变了asm所以它可能没有进行完全溢出检查.)

你可以说gcc8"打破"你的代码,但实际上它已经被打破了,因为合法/可移植的ISO C. gcc8刚刚揭示了这个事实.

为了更清楚地看到它,让我们将该表达式分离为一个函数. gcc -O0无论如何编译每个语句,所以只在x<0不影响函数中-O0此语句的代码生成时才运行的信息tadd_ok.

// compiles to add and checking the carry flag, or equivalent
int unsigned_overflow_test(unsigned x, unsigned y) {
    return (x+y) >= y;    // unsigned overflow is well-defined as wrapping.
}

// doesn't work because of UB.
int signed_overflow_expression(int x, int y) {
    return (x+y) > y;
}

在使用AArch64 GCC8.2的Godbolt编译器资源管理器上-O0 -fverbose-asm:

signed_overflow_expression:
    sub     sp, sp, #16       //,,      // make a stack fram
    str     w0, [sp, 12]      // x, x   // spill the args
    str     w1, [sp, 8]       // y, y
   // end of prologue

   // instructions that implement return (x+y) > y; as return  x > 0
    ldr     w0, [sp, 12]      // tmp94, x
    cmp     w0, 0     // tmp94,
    cset    w0, gt  // tmp95,                  // w0 = (x>0) ? 1 : 0
    and     w0, w0, 255       // _1, tmp93     // redundant

  // epilogue
    add     sp, sp, 16        //,,
    ret     

GCC -ftree-dump-original或者-optimized甚至会通过这种优化(来自Godbolt链接)将其GIMPLE变回类似C的代码:

;; Function signed_overflow_expression (null)
;; enabled by -tree-original

{
  return x > 0;
}

不幸的是,即便如此-Wall -Wextra -Wpedantic,也没有关于比较的警告.这不平凡真实的; 它仍然取决于x.

优化的asm不足为奇cmp w0, 0/ cset w0, gt/ ret.AND与0xff多余. cset是csinc使用零寄存器作为两个源的别名.因此它将产生0/1.对于其他寄存器,一般情况csinc是任何2个寄存器的条件选择和增量.

无论如何,csetAArch64相当于x86 setcc,用于将标志条件转换bool为寄存器中的a.

如果您希望代码按照编写的方式工作,则需要进行编译,-fwrapv以便在-fwrapv使CCC实现的C变体中使其具有良好定义的行为.默认值-fstrict-overflow与ISO C标准类似.

如果要在现代C中检查签名溢出,则需要编写检测溢出而不实际导致溢出的检查. 这更难,更烦人,并且是编译器编写者和(某些)开发人员之间争论的焦点.他们争辩说,围绕未定义行为的语言规则并不意味着在编译目标机器时"无偿破解"代码的借口,因为它在asm中是有意义的.但现代编译器大多只实现ISO C(带有一些扩展和额外定义的行为),即使在编译目标体系结构时,如x86和ARM,其中有符号整数没有填充(因此包裹很好),并且不会在溢出时陷阱.

所以你可以说在那场战争中"开枪",随着gcc8.x的变化实际上"打破"这样的不安全代码.:P

请参阅检测C/C++中的带符号溢出和如何在没有未定义行为的情况下检查C中的有符号整数溢出？

由于有符号和无符号加法在2的补码中是相同的二进制运算,你可能只是转换unsigned为加法,并转换为有符号的比较.这将使你的函数版本在"正常"实现上是安全的:2的补码,并且在它们之间进行转换,unsigned并且int只是对相同位的重新解释.

这不能有UB,它只是不能给出一个补码或符号/幅度C实现的正确答案.

return  (int)((unsigned)x + (unsigned)y) > y;

这编译(与AArch64的gcc8.2 -O3)

    add     w0, w0, w1            // x+y
    cmp     w0, w1                // x+y  cmp  y
    cset    w0, gt
    ret

如果您已将其int sum = x+y作为单独的C语句编写,则return sum < y禁用优化的gcc将无法看到此UB. 但作为同一表达式的一部分,即使gcc默认-O0也可以看到它.

编译时可见的UB是各种不好的.在这种情况下,只有某些输入范围会产生UB,因此编译器认为它不会发生.如果在执行路径上看到无条件UB,则优化编译器可以假定路径永远不会发生.(在没有分支的函数中,它可以假设函数永远不会被调用,并将其编译为单个非法指令.)请参阅C++标准是否允许未初始化的bool使程序崩溃？有关编译时可见UB的更多信息.

(-O0并不意味着"无优化",这意味着没有额外的除了什么已经必须通过gcc的内部表示的方式转换到ASM存储任何目标平台的优化.@Basile Starynkevitch在解释 禁止在GCC的所有优化选项)

其他一些编译器可能会在禁用优化的情况下"关闭大脑",并且更接近将C音译成asm,但gcc 不是那样的.例如,gcc仍然使用乘法逆对整数除以常数at -O0.(为什么GCC在实现整数除法时使用乘以一个奇数？)所有其他3个主要的x86编译器(clang/ICC/MSVC)都使用div.

Answer 2

有符号整数的溢出会调用未定义的行为.您无法通过添加两个数字并检查它们是否以某种方式回绕来检查溢出情况.虽然您可能在x86/x64系统上侥幸逃脱,但无法保证其他人的行为相同.

你可以不过做的是沿着一些算术INT_MAX或INT_MIN做检查.

int tadd_ok(int x, int y) {
    if ((x ^ y) >> 31)
        return 1;  // A positive number and a negative integer always add without problem
    if (x < 0)
        return INT_MIN - x < y;
    if (x > 0)
        return INT_MAX - x > y;
    // x == 0
    return 1;
}

该表达式INT_MAX - x > y与算术等价,INT_MAX > x + y但可防止发生溢出.类似地,INT_MIN - x < y算术等价INT_MIN < x + y但防止溢出.

编辑:

如果要强制定义有符号整数溢出,可以使用-fwrapvgcc选项.但是,你最好完全避免溢出.