在 MASM x64 中跳转 table 实现？
Jump table implementation in MASM x64?
我正在尝试使用跳转 tables 在汇编（MASM64、Windows、x64）中实现一个算法。基本思想是：我需要对数据进行 3 种不同类型的操作。这些操作取决于一些变量，但我发现实现大量切换和许多长实现很乏味。
PUBLIC superFunc@@40 ;__vectorcall decoration
.DATA
ALIGN 16
jumpTable1 qword func_11, func_12, func_13, func_14
jumpTable2 qword func_21, func_22, func_23, func_24
jumpTable3 qword func_31, func_32, func_33, func_34
.CODE
superFunc@@40 PROC
;no stack actions, as we should do our stuff as a leaf function
;assume the first parameter (rcx) is our jumpTable index, and it's
;the same index for all functions
mov rax, qword ptr [rcx*8 + offset jumpTable1]
mov r10, qword ptr [rcx*8 + offset jumpTable2]
mov r11, qword ptr [rcx*8 + offset jumpTable3]
jmp qword ptr [rax]
superFunc@@40 ENDP
func_11:
[...] do something with data
jmp qword ptr [r10]
func_12: ; shorted, simply does something else to the data and jumps thru r10
[...]
func_21:
[...] do something with data
jmp qword ptr [r11]
func_22: ; shorted, simply does something else to the data and jumps thru r11
[...]
func_31:
[...] do something with data
ret
func_32: ; shorted, simply does something else to the data and returns
END
现在可以很好地编译了，但是 link 我的主要 C++ 插件（一个 DLL）没有，给我以下 linker 错误：
LINK : warning LNK4075: ignoring '/LARGEADDRESSAWARE:NO' due to '/DLL' specification
error LNK2017: 'ADDR32' relocation to 'jumpTable1' invalid without /LARGEADDRESSAWARE:NO
我怎样才能正确地实现这样的东西？也许措辞更好：How do I implement jump tables and jumping/calling to addresses from those tables correctly in MASM64?
P.S.: 我可以在 C++ 中设置一个函数 table 并通过参数告诉 superFunc。如果找不到更好的解决方案，我将这样做。
RIP 相对寻址仅在寻址模式下没有其他寄存器时有效。
[table + rcx*8] 只能在 x86-64 机器代码中编码为 [disp32 + rcx*8]，因此 仅适用于非大型适合 32 位带符号绝对地址的地址 。 Windows 显然可以用 LARGEADDRESSAWARE:NO 来支持这一点，就像 Linux compiling with -no-pie 一样可以解决同样的问题。
MacOS 没有解决方法，您根本不能在那里使用 64 位绝对寻址。 Mach-O 64-bit format does not support 32-bit absolute addresses. NASM Accessing Array 展示了 如何使用相对于 RIP lea 索引静态数组以将 table 地址放入寄存器 同时避免 32 位绝对地址。
你的跳转 tables 本身很好：它们使用 64 位 绝对地址，可以在虚拟地址 space 中的任何位置重定位。 （在 ASLR 之后使用加载时修正。）
我认为你的间接层级太多了。由于您已经将函数指针加载到寄存器中，因此您应该使用 jmp r10 而不是 jmp [r10]。在任何可能的分支预测错误之前，预先将所有负载加载到寄存器中可以使它们更快地进入管道，因此如果您有很多寄存器可以使用，可能 是个好主意。
更好的方法是内联一些后面的块，如果它们很小，因为任何给定 RCX 值可到达的块无法通过任何其他方式到达。因此，将所有 func_21 和 func_31 内联到 func_11 中会好得多，对于 func_12 依此类推。您可以使用汇编程序宏来简化此过程。
实际上重要的是 func_11 总是 末尾的跳转到 func_21。有其他方法可以到达那个街区很好，例如来自其他跳过 table 的间接分支 1. func_11 没有理由不陷入其中；如果 func_21 仍然必须是未从 func_11.
落空的执行路径的有效入口点，它只会限制您可以在这两个块之间进行的优化
但无论如何，您可以像这样实现您的代码。如果做优化的话，可以去掉后面的调度步骤和对应的负载。
我认为这是有效的 MASM 语法。如果不是，应该仍然清楚所需的机器代码是什么。
lea rax, [jumpTable1] ; RIP-relative by default in MASM, like GAS [RIP + jumpTable1] or NASM [rel jumpTable1]
; The other tables are at assemble-time-constant small offsets from RAX
mov r10, [rax + rcx*8 + jumpTable3 - jumpTable1]
mov r11, [rax + rcx*8 + jumpTable2 - jumpTable1]
jmp [rax + rcx*8]
func_11:
...
jmp r10 ; TODO: inline func_21 or at least use jmp func_21
; you can use macros to help with either of those
或者，如果您只想为一个 table 绑定一个寄存器，可以使用：
lea r10, [jumpTable1] ; RIP-relative LEA
lea r10, [r10 + rcx*8] ; address of the function pointer we want
jmp [r10]
align 8
func_11:
...
jmp [r10 + jumpTable2 - jumpTable1] ; same index in another table
align 8
func_12:
...
jmp [r10 + jumpTable3 - jumpTable1] ; same index in *another* table
这充分利用了 tables 之间的已知静态偏移。
跳转目标的缓存位置
在您的跳跃目标矩阵中，任何一次使用都会跨过 "column" 以跟随一些跳跃链。显然，转置您的布局会更好，这样一连串的跳转会沿着 "row" 进行，因此所有目标都来自同一缓存行。
即安排你的table，这样func_11和21可以以jmp [r10+8]结尾，然后是jmp [r10+16]，而不是+一些tables 之间的偏移量，以改善空间局部性。 L1d 加载延迟只有几个周期，因此 CPU 在检查分支预测的正确性时没有太多额外延迟，如果您在第一个间接分支之前加载到寄存器中。 （我正在考虑第一个分支预测错误的情况，所以 OoO exec 不能 "see" 内存间接跳转，直到它的正确路径开始发出。）
避免使用 64 位绝对地址：
您还可以存储 32 位（或 16 位或 8 位）相对于跳转目标附近的某个参考地址或相对于 table 本身的偏移量。
例如，看看 GCC 在编译 switch 跳转 table 位置无关代码时所做的事情，即使对于允许运行时绝对地址修正的目标也是如此。
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=84011 includes a testcase; see it on Godbolt with GCC's MASM-style .intel_syntax。它使用来自 table 的 movsxd 加载，然后是 add rax, rdx / jmp rax。 table 条目类似于 dd L27 - L4 和 dd L25 - L4（其中这些是标签名称，给出了从跳跃目标到 "anchor" L4 的距离）。
（也与那个案例相关https://gcc.gnu.org/bugzilla/show_bug.cgi?id=85585）。
我正在尝试使用跳转 tables 在汇编（MASM64、Windows、x64）中实现一个算法。基本思想是：我需要对数据进行 3 种不同类型的操作。这些操作取决于一些变量，但我发现实现大量切换和许多长实现很乏味。
PUBLIC superFunc@@40 ;__vectorcall decoration
.DATA
ALIGN 16
jumpTable1 qword func_11, func_12, func_13, func_14
jumpTable2 qword func_21, func_22, func_23, func_24
jumpTable3 qword func_31, func_32, func_33, func_34
.CODE
superFunc@@40 PROC
;no stack actions, as we should do our stuff as a leaf function
;assume the first parameter (rcx) is our jumpTable index, and it's
;the same index for all functions
mov rax, qword ptr [rcx*8 + offset jumpTable1]
mov r10, qword ptr [rcx*8 + offset jumpTable2]
mov r11, qword ptr [rcx*8 + offset jumpTable3]
jmp qword ptr [rax]
superFunc@@40 ENDP
func_11:
[...] do something with data
jmp qword ptr [r10]
func_12: ; shorted, simply does something else to the data and jumps thru r10
[...]
func_21:
[...] do something with data
jmp qword ptr [r11]
func_22: ; shorted, simply does something else to the data and jumps thru r11
[...]
func_31:
[...] do something with data
ret
func_32: ; shorted, simply does something else to the data and returns
END
现在可以很好地编译了，但是 link 我的主要 C++ 插件（一个 DLL）没有，给我以下 linker 错误：
LINK : warning LNK4075: ignoring '/LARGEADDRESSAWARE:NO' due to '/DLL' specification
error LNK2017: 'ADDR32' relocation to 'jumpTable1' invalid without /LARGEADDRESSAWARE:NO
我怎样才能正确地实现这样的东西？也许措辞更好：How do I implement jump tables and jumping/calling to addresses from those tables correctly in MASM64?
P.S.: 我可以在 C++ 中设置一个函数 table 并通过参数告诉 superFunc。如果找不到更好的解决方案，我将这样做。
RIP 相对寻址仅在寻址模式下没有其他寄存器时有效。
[table + rcx*8] 只能在 x86-64 机器代码中编码为 [disp32 + rcx*8]，因此 仅适用于非大型适合 32 位带符号绝对地址的地址 。 Windows 显然可以用 LARGEADDRESSAWARE:NO 来支持这一点，就像 Linux compiling with -no-pie 一样可以解决同样的问题。
MacOS 没有解决方法，您根本不能在那里使用 64 位绝对寻址。 Mach-O 64-bit format does not support 32-bit absolute addresses. NASM Accessing Array 展示了 如何使用相对于 RIP lea 索引静态数组以将 table 地址放入寄存器 同时避免 32 位绝对地址。
你的跳转 tables 本身很好：它们使用 64 位 绝对地址，可以在虚拟地址 space 中的任何位置重定位。 （在 ASLR 之后使用加载时修正。）
我认为你的间接层级太多了。由于您已经将函数指针加载到寄存器中，因此您应该使用 jmp r10 而不是 jmp [r10]。在任何可能的分支预测错误之前，预先将所有负载加载到寄存器中可以使它们更快地进入管道，因此如果您有很多寄存器可以使用，可能 是个好主意。
更好的方法是内联一些后面的块，如果它们很小，因为任何给定 RCX 值可到达的块无法通过任何其他方式到达。因此，将所有 func_21 和 func_31 内联到 func_11 中会好得多，对于 func_12 依此类推。您可以使用汇编程序宏来简化此过程。
实际上重要的是 func_11 总是 末尾的跳转到 func_21。有其他方法可以到达那个街区很好，例如来自其他跳过 table 的间接分支 1. func_11 没有理由不陷入其中；如果 func_21 仍然必须是未从 func_11.
但无论如何，您可以像这样实现您的代码。如果做优化的话，可以去掉后面的调度步骤和对应的负载。
我认为这是有效的 MASM 语法。如果不是，应该仍然清楚所需的机器代码是什么。
lea rax, [jumpTable1] ; RIP-relative by default in MASM, like GAS [RIP + jumpTable1] or NASM [rel jumpTable1]
; The other tables are at assemble-time-constant small offsets from RAX
mov r10, [rax + rcx*8 + jumpTable3 - jumpTable1]
mov r11, [rax + rcx*8 + jumpTable2 - jumpTable1]
jmp [rax + rcx*8]
func_11:
...
jmp r10 ; TODO: inline func_21 or at least use jmp func_21
; you can use macros to help with either of those
或者，如果您只想为一个 table 绑定一个寄存器，可以使用：
lea r10, [jumpTable1] ; RIP-relative LEA
lea r10, [r10 + rcx*8] ; address of the function pointer we want
jmp [r10]
align 8
func_11:
...
jmp [r10 + jumpTable2 - jumpTable1] ; same index in another table
align 8
func_12:
...
jmp [r10 + jumpTable3 - jumpTable1] ; same index in *another* table
这充分利用了 tables 之间的已知静态偏移。
跳转目标的缓存位置
在您的跳跃目标矩阵中，任何一次使用都会跨过 "column" 以跟随一些跳跃链。显然，转置您的布局会更好，这样一连串的跳转会沿着 "row" 进行，因此所有目标都来自同一缓存行。
即安排你的table，这样func_11和21可以以jmp [r10+8]结尾，然后是jmp [r10+16]，而不是+一些tables 之间的偏移量，以改善空间局部性。 L1d 加载延迟只有几个周期，因此 CPU 在检查分支预测的正确性时没有太多额外延迟，如果您在第一个间接分支之前加载到寄存器中。 （我正在考虑第一个分支预测错误的情况，所以 OoO exec 不能 "see" 内存间接跳转，直到它的正确路径开始发出。）
避免使用 64 位绝对地址：
您还可以存储 32 位（或 16 位或 8 位）相对于跳转目标附近的某个参考地址或相对于 table 本身的偏移量。
例如，看看 GCC 在编译 switch 跳转 table 位置无关代码时所做的事情，即使对于允许运行时绝对地址修正的目标也是如此。
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=84011 includes a testcase; see it on Godbolt with GCC's MASM-style .intel_syntax。它使用来自 table 的 movsxd 加载，然后是 add rax, rdx / jmp rax。 table 条目类似于 dd L27 - L4 和 dd L25 - L4（其中这些是标签名称，给出了从跳跃目标到 "anchor" L4 的距离）。
（也与那个案例相关https://gcc.gnu.org/bugzilla/show_bug.cgi?id=85585）。