由于从越界内存跳过cmov,很难调试SEGV

Question

我正在尝试将一些高性能的汇编函数编写为练习,并且遇到了在运行程序时发生的奇怪的段错误,但在valgrind或nemiver中却没有.

基本上一个不应该运行的cmov,带有一个越界的地址,即使条件总是假的,也会让我发生段错误

我有一个快速和慢速的版本.缓慢的一直在工作.快速的一个工作,除非它收到一个非ascii字符,此时它崩溃可怕,除非我在adb或nemiver上运行.

ascii_flags只是一个128字节的数组(最后有一点空间),包含所有ASCII字符(alpha,numeric,printable等)的标志

这工作:

ft_isprint:
    xor EAX, EAX                ; empty EAX
    test EDI, ~127              ; check for non-ascii (>127) input
    jnz .error
    mov EAX, [rel ascii_flags + EDI]    ; load ascii table if input fits
    and EAX, 0b00001000         ; get specific bit
.error:
    ret

但这不是:

ft_isprint:
    xor EAX, EAX                ; empty EAX
    test EDI, ~127              ; check for non-ascii (>127) input
    cmovz EAX, [rel ascii_flags + EDI]  ; load ascii table if input fits
    and EAX, flag_print         ; get specific bit
    ret

Valgrind确实崩溃了,但没有其他信息而不是内存地址,因为我没有设法获得更多的调试信息.

编辑:

我写了三个版本的函数来考虑到很好的答案:

ft_isprint:
    mov RAX, 128                            ; load default index
    test RDI, ~127                          ; check for non-ascii (>127) input
    cmovz RAX, RDI                          ; if none are found, load correct index
    mov AL, byte [ascii_flags + RAX]        ; dereference index into least sig. byte
    and RAX, flag_print                     ; get specific bit (and zeros rest of RAX)
    ret

ft_isprint_branch:
    test RDI, ~127                          ; check for non-ascii (>127) input
    jnz .out_of_bounds                      ; if non-ascii, jump to error handling
    mov AL, byte [ascii_flags + RDI]        ; dereference index into least sig. byte
    and RAX, flag_print                     ; get specific bit (and zeros rest of RAX)
    ret
.out_of_bounds:
    xor RAX, RAX                            ; zeros return value
    ret

ft_isprint_compact:
    xor RAX, RAX                            ; zeros return value preemptively
    test RDI, ~127                          ; check for non-ascii (>127) input
    jnz .out_of_bounds                      ; if non-ascii was found, skip dereferenciation
    mov AL, byte [ascii_flags + RDI]        ; dereference index into least sig. byte
    and RAX, flag_print                     ; get specific bit
.out_of_bounds:
    ret

经过大量测试后,分支函数肯定比cmov函数在所有类型的数据上快约5-15%.紧凑型和非紧凑型之间的差异正如预期的那样最小.Compact在可预测的数据集上稍微快一些,而non compact在不可预测的数据上稍微快一点.

我尝试了各种不同的方法来跳过'xor EAX,EAX'指令,但找不到任何有效的方法.

编辑:经过更多测试,我已将代码更新为三个新版本:

ft_isprint_compact:
    sub EDI, 32                             ; substract 32 from input, to overflow any value < ' '
    xor EAX, EAX                            ; set return value to 0
    cmp EDI, 94                             ; check if input <= '~' - 32
    setbe AL                                ; if so, set return value to 1
    ret

ft_isprint_branch:
    xor EAX, EAX                            ; set return value to 0
    cmp EDI, 127                            ; check for non-ascii (>127) input
    ja .out_of_bounds                       ; if non-ascii was found, skip dereferenciation
    mov AL, byte [rel ascii_flags + EDI]    ; dereference index into least sig. byte
.out_of_bounds:
    ret

ft_isprint:
    mov EAX, 128                            ; load default index
    cmp EDI, EAX                            ; check if ascii
    cmovae EDI, EAX                         ; replace with 128 if outside 0..127
                                            ; cmov also zero-extends EDI into RDI
;   movzx EAX, byte [ascii_flags + RDI]     ; alternative to two following instruction if masking is removed
    mov AL, byte [ascii_flags + RDI]        ; load table entry
    and EAX, flag_print                     ; apply mask to get correct bit and zero rest of EAX
    ret

表演如下,以微秒为单位.1-2-3显示执行顺序,以避免缓存优势:

-O3 a.out
1 cond 153185, 2 branch 238341 3 no_table 145436
1 cond 148928, 3 branch 248954 2 no_table 116629
2 cond 149599, 1 branch 226222 3 no_table 117428
2 cond 117258, 3 branch 241118 1 no_table 147053
3 cond 117635, 1 branch 228209 2 no_table 147263
3 cond 146212, 2 branch 220900 1 no_table 147377
-O3 main.c
1 cond 132964, 2 branch 157963 3 no_table 131826
1 cond 133697, 3 branch 159629 2 no_table 105961
2 cond 133825, 1 branch 139360 3 no_table 108185
2 cond 113039, 3 branch 162261 1 no_table 142454
3 cond 106407, 1 branch 133979 2 no_table 137602
3 cond 134306, 2 branch 148205 1 no_table 141934
-O0 a.out
1 cond 255904, 2 branch 320505 3 no_table 257241
1 cond 262288, 3 branch 325310 2 no_table 249576
2 cond 247948, 1 branch 340220 3 no_table 250163
2 cond 256020, 3 branch 415632 1 no_table 256492
3 cond 250690, 1 branch 316983 2 no_table 257726
3 cond 249331, 2 branch 325226 1 no_table 250227
-O0 main.c
1 cond 225019, 2 branch 224297 3 no_table 229554
1 cond 235607, 3 branch 199806 2 no_table 226286
2 cond 226739, 1 branch 210179 3 no_table 238690
2 cond 237532, 3 branch 223877 1 no_table 234103
3 cond 225485, 1 branch 201246 2 no_table 230591
3 cond 228824, 2 branch 202015 1 no_table 226788

无表版本与cmov一样快,但不允许轻松实现的本地版本.除非零优化中的可预测数据,否则分支算法更糟糕？那里我没有解释.

我将保留cmov版本,这是最优雅和易于更新的.谢谢你的帮助.

Answer 1

cmov是ALU选择操作,在检查条件之前始终读取两个源.使用内存源不会改变这一点.如果条件为假,它就不像ARM预测的指令那样充当NOP. cmovz eax, [mem]也无条件地写 EAX,无论条件如何都将零扩展到RAX.

就大多数CPU而言(无序调度程序等),cmovcc reg, [mem]其处理方式与adc reg, [mem]:3输入1输出ALU指令完全相同.(adc写入标记,不像cmov,但从来没有说过.)微融合内存源操作数是一个单独的uop,恰好是同一个x86指令的一部分.这也是ISA规则的工作方式.

所以真的,一个更合适的助记 cmovz为selectz

x86唯一的条件加载(在坏地址上没有错误,可能运行缓慢)是:

• 正常负载受条件分支保护.分支错误预测或导致运行故障负载的其他错误推测被相当有效地处理(可能开始页面遍历,但是一旦识别出错误推测,执行正确的指令流就不必等待任何内存操作由推测执行启动).

  如果在页面上有一个TLB命中,你无法读取,那么在故障负载达到退役之前不会发生更多事情(已知是非推测性的,因此实际上会出现#PF页面错误异常,这种情况不可避免地会变慢) .在某些CPU上,这种快速处理会导致Meltdown攻击.>.<见http://blog.stuffedcow.net/2018/05/meltdown-microarchitecture/.

• rep lodsdRCX = 0或1.(不是快速或高效,但微码分支是特殊的,不能从英特尔CPU上的分支预测中受益.请参阅REP做什么设置？ .Andy Glew提到微码分支错误预测,但我认为那些与正常的分支未命中不同,因为似乎有固定的成本.)

• AVX2 vpmaskmovd/q/ AVX1vmaskmovps/pd.故障被抑制的元件,其中该掩模为0的掩模载甚至从法律地址为全0掩模需要〜200微码循环辅助用碱+索引寻址模式.)见节12.9有条件SIMD PACKED荷载和英特尔优化手册中的STORES和表C-8.(在Skylake上,商店到一个全零掩码的非法地址也需要帮助.)

  较早的MMX/SSE2 maskmovdqu是仅存储(并且具有NT提示).只有带有dword/qword(而不是byte)元素的类似AVX指令才有加载形式.

• AVX512屏蔽了负载
• AVX2收集了部分/全部掩码元素被清除.

......也许是其他我忘记了.TSX/RTM事务中的正常负载:故障中止事务而不是引发#PF.但你不能指望一个糟糕的索引故障,而不是只是从附近的某个地方读取虚假数据,所以它不是真正的条件负载.它也不是超级快.

另一种方法可能是cmov您无条件使用的地址,选择要加载的地址.例如,如果您0从其他地方加载,那就可以了.但是你必须在寄存器中计算表索引,而不是使用寻址模式,所以你可以cmov得到最终地址.

或者只是CMOV索引并在最后用一些零字节填充表,这样你就可以从中加载table + 128.

或者使用分支,它可能会很好地预测很多情况.但也许不是像法语这样的语言,你可以在普通文本中找到低128和更高Unicode代码点的混合.

代码审查

请注意,[rel]仅当寻址模式中没有寄存器(RIP除外)时才有效.RIP相对寻址替换2种冗余方式之一(在32位代码中)来编码a [disp32].它使用较短的非SIB编码,而ModRM + SIB仍然可以编码绝对[disp32]没有寄存器.(对于[fs: 16]相对于具有段基的线程局部存储的小偏移的地址很有用.)

如果您只想在可能的情况下使用RIP相对寻址,请使用default rel文件顶部. [symbol]将是RIP相对的,但[symbol + rax]不会.不幸的是,NASM和YASM默认为default abs.

[reg + disp32]是一种非常有效的方法来索引位置相关代码中的静态数据,只是不要愚弄自己认为它可以是RIP相关的.请参阅x86-64 Linux中不再允许的32位绝对地址？.

[rel ascii_flags + EDI]也很奇怪,因为你在x86-64代码中使用寻址模式的32位寄存器.通常没有理由花费地址大小的前缀来将地址截断为32位.

但是,在这种情况下,如果您的表位于低32位的虚拟地址空间中,并且您的函数arg仅指定为32位(因此允许调用者在RDI的上部32中留下垃圾),它实际上是赢得使用[disp32 + edi]而不是一个mov esi,edi或一些零延伸.如果您是故意这样做,请明确说明您使用32位寻址模式的原因.

但在这种情况下,使用cmov索引将零扩展到64位.

从字节表中使用DWORD加载也很奇怪.您偶尔会跨越缓存行边界并遭受额外延迟.

@fuz显示了一个使用RIP相对LEA 和索引上的CMOV 的版本.

在位置相关的代码中,32位绝对地址是可以的,一定要用它来保存指令. [disp32]寻址模式比RIP相对更差(长1个字节),[reg + disp32]但当位置相关的代码和32位绝对地址正常时,寻址模式非常好.(例如x86-64 Linux,但不是OS X,其中可执行文件总是映射到低32位之外.)请注意,它不是rel.

; position-dependent version taking advantage of 32-bit absolute [reg + disp32] addressing
; not usable in shared libraries, only non-PIE executables.
ft_isprint:
    mov     eax, 128               ; offset of dummy entry for "not ASCII"
    cmp     edi, eax               ; check if ascii
    cmovae  edi, eax               ; replace with 128 if outside 0..127
              ; cmov also zero-extends EDI into RDI
    movzx   eax, byte [ascii_flags + rdi] ; load table entry
    and     al, flag_print         ; mask the desired flag
      ; if the caller is only going to read / test AL anyway, might as well save bytes here
    ret

如果表中的任何现有条目具有相同的高输入标记,例如0,您可能永远不会在隐式长度字符串中看到的条目,您仍然可以将EAX归零并将表保持在128字节而不是129.

test r32, imm32需要更多的代码字节. ~127 = 0xFFFFFF80将适合符号扩展字节,但不是TEST r/m32, sign-extended-imm8编码.cmp但是,存在这样的编码,就像基本上所有其他直接指令一样.

您可以使用cmp edi, 127/ cmovbe eax, edi或检查127以上的未签名cmova edi, eax.这节省了3个字节的代码大小.或者我们可以cmp reg,reg使用128我们用于表索引的方法来节省4个字节.

对于大多数人来说,在进行数组索引之前的范围检查比检查高位更直观.

and al, imm8只有2个字节,而3个字节and r/m32, sign-extended-imm8.只要呼叫者只读AL,它在任何CPU上都不会慢.在Sandybridge之前的Intel CPU上,在AND运行到AL之后读取EAX可能会导致部分寄存器停止/减速.如果我没记错的话,Sandybridge不会重命名部分寄存器进行读 - 修改 - 写操作,而IvB和以后根本不重命名low8部分寄存器.

您也可以使用mov al, [table]而不是movzx保存另一个代码字节.早先mov eax, 128已经打破了对EAX旧值的任何错误依赖,因此它不应该有性能下降.但这movzx不是一个坏主意.

当其他条件相同时,较小的代码大小几乎总是更好(对于指令缓存占用空间,有时用于打包到uop缓存中).如果它花费任何额外的uops或引入任何错误的依赖性,那么在优化速度时它是不值得的.

Answer 2

正如Peter Cordes解释的那样，cmovCC无条件地从内存加载。要缓解此问题，您可以做的一件事是首先进行有条件的移动，edi以清除edi角色是否超出范围，从而导致有条件的移动加载ascii_flags[0]并避免了您的问题。方便地，eax当您这样做时已经很清楚了。

还要注意，您可能希望避免将32位寄存器用作基址寄存器和索引寄存器，因为它们需要额外的前缀来表示，并且在某些体系结构上可能较慢。只需使用其64位对应物即可。

ft_isprint:
    xor EAX, EAX                ; empty EAX
    test EDI, ~127              ; check for non-ascii (>127) input
    cmovnz EDI, EAX             ; clear EDI if not ascii
    cmovz EAX, [ascii_flags + RDI]  ; load ascii table if input fits
    and EAX, flag_print         ; get specific bit
    ret

为了解决Peter Cordes的其他问题，我实际上将使用如下代码：

; PIC/PIE safe version, doing only a byte load
ft_isprint:
    lea   rsi, [rel ascii_flags] ; load address of ascii_flags
    mov   eax, 128               ; load offset of dummy entry for "not ASCII"
    test   edi, ~127             ; check if ascii
    cmovz  eax, edi              ; load proper entry if ascii
    movzx  eax, byte [rsi + rax] ; load table entry
    and    eax, flag_print       ; mask the desired flag
    ret