处理JIT代码调用(潜在地)远距离编译的函数

17

这个问题被认为是过于宽泛,可能是因为我在尝试“展示我的工作”而不是提出低成本问题时包含了研究。为了解决这个问题,让我用一句话总结整个问题(感谢@PeterCordes提供的短语):

  

如何从JIT生成的代码(我正在生成的)高效地调用(x86-64)预先编译的函数(我控制,可能超过2GB)?

仅凭这一点,我怀疑也会被认为是“过于宽泛”的。特别是缺少“您尝试过什么”。因此,我感到需要添加附加信息来显示我的研究/思考以及我所尝试的内容。以下是这种有点意识流的东西。

请注意,下面没有一个问题是我希望得到答案的问题;它们更多是修辞性的。它们的目的是说明为什么我无法回答上述问题(尽管我进行了研究,但在这个领域缺乏经验,无法像@PeterCordes那样做出确定性陈述,例如“分支预测隐藏了从内存中提取和检查函数指针的延迟,假设它预测良好。”)。还要注意,这里的Rust组件在很大程度上与此无关,因为这是一个汇编问题。我包含它的原因是预先编译的函数是用Rust编写的,所以我不确定是否有什么Rust可以做的(或者指示LLVM做的)可以在这种情况下具有优势。完全可以回答不考虑Rust的答案;实际上,我期望情况就是这样。

把以下内容视为数学考试后面的草稿:


注意:我在这里混淆了内部函数的术语。正如评论中指出的那样,“预先编译的函数”是一个更好的描述。以下我将缩写为AOTC函数。

我正在使用Rust编写JIT(尽管Rust仅涉及我的问题的一部分,但大部分与JIT约定相关)。我有在Rust中实现的AOTC函数,我需要能够从我的JIT生成的代码中call这些函数。我的JITmmap(_,_,PROT_EXEC,MAP_ANONYMOUS | MAP_SHARED)一些页面用于jitted代码。我有我的AOTC函数的地址,但不幸的是它们比32位偏移大得多。我现在正在尝试决定如何发出对这些AOTC函数的调用。我考虑了以下选项(这些不是要回答的问题,只是演示为什么我无法自己回答此SO线程的核心问题):

  1. (Rust具体)以某种方式使Rust将AOTC函数放置在堆栈附近(也许在堆栈上?),以便call将在32位偏移内。不清楚是否可能使用Rust实现这一点(有一种方法可以指定自定义链接器参数,但我无法确定这些参数应用

    mov rax, {ABSOLUTE_AOTC_FUNCTION_ADDRESS}
    jmp rax
    
    1. 将上述方法内联到 JIT 代码中的每个内部调用位置,从而得到 (3) 的反向处理方式。此方法解决了间接引用问题,但会使 JIT 代码变得更大(可能会影响指令缓存和解码效果)。它仍然存在着跳转是间接的并且取决于 mov 操作的问题。

    2. 在 JIT 页附近的 PROT_READ(只读)页面上放置 AOTC 函数的地址。使所有附近的调用站点成为绝对间接调用(请参见以下代码)。这种方式消除了 (2) 中的第二层间接引用。但是,这条指令的编码非常大(6 个字节),因此其与 (4) 具有相同的问题。此外,现在跳转不再依赖寄存器,而是不必要地依赖内存(只要 JIT 时已知地址),这肯定会影响性能(尽管这个页面可能被缓存?)。

    aotc_function_address:
        .quad 0xDEADBEEF
    
    # Then at the call site
    call qword ptr [rip+aotc_function_address]
    
    1. 调整段寄存器以使其接近AOTC函数,从而可以相对于该段寄存器进行调用。这种调用的编码很长(所以可能有解码管道问题),但除此之外,基本上避免了所有前面的棘手问题。但是,可能相对于非cs段进行调用会表现不佳。或者说这样的 futzing 不明智(例如会干扰 Rust 运行时)。(正如 @prl 所指出的,这需要远程调用,这对性能来说非常糟糕。)

    2. 并不是一个解决方案,但我可以使编译器成为32位,完全没有这个问题。这并不是一个好的解决方案,它也将阻止我使用扩展通用寄存器(我利用了全部)。

    所有提出的选项都有缺点。简要地说,1和2似乎是没有性能影响的唯一选项,但不清楚是否有非hack的方法实现它们(或者根本没有办法)。3到5与Rust无关,但显然有性能缺陷。

    在这个意识流中,我得出了以下修辞问题(不需要明确回答),以证明我缺乏回答这个 SO 线程核心问题的知识。 我将它们打了出来,以便清楚地表明我不是把它们都作为我的问题提出。

    1. 对于方法(1),是否可能强制Rust在特定地址(靠近堆)链接某些extern "C"函数?我应该如何选择这样的地址(在编译时)?可以安全地假设mmap返回的任何地址(或由Rust分配的地址)都在与此位置为32位偏移之内吗?

    2. 对于方法(2),如何找到一个合适的地方放置JIT页面(以便它不会破坏现有的Rust代码)?

    还有一些针对 JIT(非 Rust)的具体问题:

    1. 对于方法(3),存根会影响性能到足以值得关注吗?间接的 jmp 呢?我知道这有点像链接器存根,只不过我理解的链接器存根至少只在解析一次(因此它们不需要是间接的?)。任何 JIT 是否采用此技术?

    2. 对于方法(4),如果(3)中的间接调用可以,那么内联调用是否值得?如果JIT通常采用方法(3/4),那么这个选项更好吗?

    3. 对于方法(5),跳转对内存的依赖性(考虑到地址在编译时已知)是否不好?这会使其比(3)或(4)更不耐用吗?任何 JIT 是否采用此技术?

    4. 对于方法(6),这种 futzing 是否不明智?(针对 Rust)是否有可用的段寄存器(未被运行时或ABI使用)用于此目的?相对于非cs段的调用是否与相对于cs的调用一样有效?

    5. 最后(也是最重要的),是否有更好的方法(也许JIT常用的方法),我错过了这些方法吗?

      我的Rust问题没有答案,所以我无法实现(1)或(2)。当然,我可以实现和基准测试3-5(也许6,尽管事先知道段寄存器 futzing 会很好),但是考虑到这些方法差异巨大,我希望有现有的文献介绍这一点,而我找不到它,因为我不知道正确的术语来搜索(我也正在进行这些基准测试)。或者,也许深入研究JIT内部的人可以分享他们的经验或他们经常看到的东西?

      我知道这个问题:Jumps for a JIT (x86_64)。它与我的不同,因为它在谈论连接基本块(接受的解决方案对于频繁调用的内部函数来说指令太多了)。我还知道Call an absolute pointer in x86 machine code,虽然它讨论了与我的类似的主题,但是不同之处在于,我不假设绝对跳转是必要的(例如方法1-2将避免它们)。


1
我喜欢这个问题,但它似乎非常广泛。你可能会在r/compilers和r/programminglanguages这两个子论坛中获得更好的反馈,因为那里有志同道合的人分享着这些领域的兴趣。 - Matthieu M.
1
下面的 Rust 代码是否小于4G?如果是,您可以使用 MAP_32BIT 标志。 - prl
3
@BaileyParker 不要因为一次接近的投票而感到气馁。像这样的问题非常棒! - Theodoros Chatzigiannakis
3
我必须同意这是一组有趣的问题,但它们完全不适合在Stack Overflow上发布 :( Rust特定的编号问题可能每个都可以成为自己的问答帖子(我认为它们会很有价值)。关于某些事情是否“值得”或是否存在“更好的方法”的问题可能不容易成为论题。除了Reddit之外,也许您应该考虑users.rust-lang.org。如果经过编辑,您问题的某些部分也适合软件工程SE(请阅读规则以了解该网站的期望)。 - trent
2
@PeterCordes:我要注意的是,我没有投票关闭这个问题,实际上我还点赞了这个问题。我现在看到它已经关闭了(30分钟),这意味着我可以投票重新开放...虽然我认为这个问题应该重新表述一下。结尾的问题列表可能是导致关闭的原因 => 太多的问号 = 太广泛。一个单一的问题:“如何在JIT代码中高效地发出对内置函数的调用?”,列出已知的方法及其缺点/未知之处而不带有“问题”,将达到相同的目标,但更不容易引起反对票。 - Matthieu M.
显示剩余14条评论
1个回答

7
摘要: 尝试在静态代码附近分配内存。但对于无法使用rel32到达的调用,回退到call qword [rel pointer]或内联mov r64,imm64 / call r64
如果无法使2.工作,则机制5.可能是性能最佳的选择,但4.很容易并且应该可以胜任。直接的call rel32也需要一些分支预测,但肯定仍然更好。
术语:“intrinsic functions” 可能应该是 “helper” 函数。 "Intrinsic" 通常意味着语言内置(例如Fortran含义)或者 “不是真正的函数,只是一些可以内联到机器指令的东西” (C/C++/Rust 的含义,例如对于SIMD或类似_mm_popcnt_u32()_pdep_u32()_mm_mfence()的内容)。您的Rust函数将编译为实际存在于机器代码中的真实函数,您将使用call指令调用它们。

是的,将JIT缓冲区分配在目标函数的+-2GiB范围内是最理想的,可以直接使用rel32调用。

最简单的方法是在BSS中使用一个大的静态数组(链接器将其放置在距离代码不到2GiB的位置),然后从中划分出你的分配空间。(使用mprotect(POSIX)或VirtualProtect(Windows)使其可执行)。

大多数操作系统(包括Linux)都会对BSS进行延迟分配(COW映射到零页,只有在写入时才分配物理页面框来支持该分配,就像没有MAP_POPULATE的mmap一样),因此,在BSS中拥有一个512MiB的数组,你仅仅使用了底部的10kB,这只浪费了虚拟地址空间。

不要让它变得比2GiB更大或更接近,因为这会将BSS中的其他内容推得太远。默认的“小”代码模型(如x86-64 System V ABI中所述)将所有静态地址放在彼此相距不到2GiB的位置上,以进行RIP相对数据寻址和rel32调用/ jmp。

缺点:你需要自己编写至少一个简单的内存分配器,而不是使用mmap / munmap的整个页面。但是如果您不需要释放任何内容,则这很容易。也许只需从地址开始生成代码,并在到达结尾并发现代码块有多长时更新指针。(但这不是多线程的...) 为了安全起见,请记住在到达此缓冲区的末尾时进行检查并中止,或者退回到 mmap 。
如果您的绝对目标地址在虚拟地址空间的前2GiB,建议在Linux上使用mmap(MAP_32BIT)。(例如,如果您的Rust代码编译成非PIE可执行文件用于x86-64 Linux。但这不适用于PIE可执行文件(现在),也不适用于共享库的目标。您可以通过检查其中一个辅助函数的地址来在运行时检测此问题。)
一般而言(如果MAP_32BIT无效/不可用),您最好使用mmap 没有 MAP_FIXED,但是使用一个非NULL的提示地址,您认为该地址是空闲的。

Linux 4.17引入了MAP_FIXED_NOREPLACE,可以让你轻松地搜索附近未使用的区域(例如按64MB逐步尝试并重试EEXIST,然后记住该地址以避免下次搜索)。否则,在启动时可以解析/ proc / self / maps以查找包含其中一个辅助函数地址的映射附近的一些未映射空间。 它们将靠得很近。

请注意,不认识MAP_FIXED_NOREPLACE标志的旧内核通常会(在检测到与预先存在的映射冲突时)回退到“non-MAP_FIXED”类型的行为:它们将返回与请求的地址不同的地址。

在更高或更低的空闲页面中,最好有一个非稀疏内存映射,这样页面表就不需要太多不同的顶级页面目录。(硬件页面表是基数树。)一旦找到一个有效位置,将来的分配应与之相邻。如果您在那里使用了很多空间,内核可以机会地使用2MB巨大页面,而且您的页面再次连续意味着它们在硬件页面表中共享相同的父页面目录,因此iTLB错过触发页面行走可能会稍微便宜一些(如果这些更高级别在数据缓存中保持活动,甚至缓存在页行走硬件本身内)。对于内核以一个更大的映射方式进行高效跟踪也很重要。当然,如果有空间,更好地利用已经分配的页面会更好。页面级别上的更好代码密度有助于指令TLB,可能也有助于DRAM页面内的代码密度(但不一定与虚拟内存页面大小相同)。
当为每个调用生成代码时,只需检查目标是否适合使用call rel32off == (off as i32) as i64,否则回退到10字节的mov r64,imm64 / call r64。(rustcc会将其编译为movsxd/cmp,因此每次检查对于JIT编译时间来说仅有微不足道的成本。)
(如果可能的话,则使用5字节的mov r32,imm32。不支持MAP_32BIT的操作系统可能仍然在那里具有目标地址。通过target == (target as u32) as u64进行检查。第三个mov -立即编码,7字节的mov r / m64,sign_extended_imm32可能没有太多意义,除非您正在为映射在虚拟地址空间的高2GiB中的内核代码 JIT。)
检查并尽可能使用直接调用的优点在于它将代码生成与分配相邻页面或地址来源的任何知识解耦,并且只是机会主义地生成良好的代码。(您可以记录计数器或日志,以便您/您的用户至少注意到附近的分配机制是否失败,因为性能差异通常不容易测量。)

mov-imm / call reg的替代方案

mov r64,imm64是一个10字节的指令,它的获取/解码有点大,并且对于uop缓存来说也很大。根据Agner Fog的微体系结构pdf(https://agner.org/optimize),在SnB家族上可能需要额外的周期从uop缓存中读取。但现代CPU对于代码获取有相当好的带宽和强大的前端。

如果分析发现前端瓶颈是你的代码中的一个大问题,或者大代码大小导致其他有价值的代码被逐出L1 I-cache,我会选择选项5。

顺便说一下,如果你的任何函数是可变参数的,x86-64 System V要求你传递AL = XMM参数数量,你可以使用r11作为函数指针。它被调用并且不用于参数传递。但RAX(或其他“遗留”寄存器)将在call上节省一个REX前缀。


  1. mmap分配附近分配Rust函数

不,我认为没有机制可以使您的静态编译函数靠近mmap可能放置新页面的位置。

mmap有超过4GB的可用虚拟地址空间可供选择。您无法预先知道它将分配在哪里。(尽管我认为Linux至少保留了一定程度的局部性以优化硬件页表。)

您理论上可以复制 Rust函数的机器代码,但它们可能会引用具有RIP相对寻址模式的其他静态代码/数据。


  1. call rel32用于使用mov/jmp reg的存根

这似乎会对性能产生负面影响(可能会干扰RAS /跳转地址预测)。

性能下降只是因为在前端获取有用指令之前,需要通过2个总的call/jump指令。这不是很好;5.要好得多。

这基本上就是Unix/Linux共享库函数调用时PLT的工作原理,并且将执行相同操作。通过PLT(过程链接表)存根函数进行调用几乎与此类似。因此,性能影响已经得到了充分研究并与其他方法进行了比较。我们知道动态库调用不会导致性能灾难。

地址前的星号和push指令,它被推到哪里了?展示了AT&T对其中一个的反汇编,或者如果你好奇的话,可以单步执行像main(){puts("hello"); puts("world");}这样的C程序。(在第一次调用时,它会将参数推入堆栈并跳转到一个惰性动态链接器函数;在后续调用中,间接跳转目标是共享库中函数的地址。)

为什么除了GOT之外还需要PLT存在?提供了更多解释。被延迟链接更新地址的jmpjmp qword [xxx@GOTPLT]。(即使在i386上,使用会被重写的jmp rel32也能正常工作,但PLT确实在这里使用了内存间接jmp。我不知道GNU / Linux是否曾经在jmp rel32中重写偏移量。)

jmp只是标准的尾调用,并且不会破坏返回地址预测器堆栈。目标函数中最终的ret将返回到原始call之后的指令,即返回到call推送到调用堆栈和微架构RAS的地址。只有当您使用push / ret(例如Spectre缓解的“retpoline”)时,才会破坏RAS。

但是您提供的Jumps for a JIT (x86_64)代码非常糟糕(请看我的评论)。它将会破坏未来返回地址栈。您可能认为它只会破坏调用时的返回地址栈,因为调用(获取要调整的返回地址)应该平衡推/弹出,但实际上call +0是一个特殊情况,在大多数CPU中不会进入返回地址栈:http://blog.stuffedcow.net/2018/04/ras-microbenchmarks。(通过nop进行调用可能会改变这一点,但整个过程与call rax相比完全疯狂,除非它试图防御Spectre漏洞。)通常在x86-64上,您使用RIP相对LEA将附近的地址加载到寄存器中,而不是使用call/pop
  1. 内联 mov r64, imm64 / call reg

这可能比3更好;较大代码大小的前端成本可能低于通过使用jmp的存根进行调用的成本。

但这也可能已经足够好了,特别是如果您的在2GiB内分配的方法在大多数情况下在您关心的大多数目标上运行良好。

虽然有时它可能比5慢。分支预测隐藏了从内存获取和检查函数指针的延迟,假设它预测得很好。(通常如此,否则它运行得如此不频繁,以至于它不影响性能。)


  1. call qword [rel nearby_func_ptr]

这是在Linux上使用gcc -fno-plt编译共享库函数调用的方式(call [rip + symbol@GOTPCREL]),也是Windows DLL函数调用的常规方式。(这类似于http://www.macieira.org/blog/2012/01/sorry-state-of-dynamic-libraries-on-linux/中的建议之一)

call [RIP-relative]指令占用6个字节,比call rel32指令只多1个字节,因此对代码大小几乎没有影响,与调用存根相比。有趣的是:有时在机器码中会看到addr32 call rel32(地址大小前缀除了填充外没有任何效果)。这来自于链接器将call [RIP + symbol@GOTPCREL]转换为call rel32,如果非隐藏ELF可见性符号在链接期间在另一个.o中找到,而不是在另一个共享对象中找到。

对于共享库调用,这通常优于PLT存根,唯一的缺点是程序启动较慢,因为它需要早期绑定(非惰性动态链接)。但这对您来说不是问题;目标地址在代码生成时已知。

The patch author tested its performance在一些未知的x86-64硬件上与传统PLT进行了比较。Clang可能是共享库调用的最坏情况,因为它对小型LLVM函数进行了许多调用,而这些函数花费的时间不多,并且它长时间运行,因此早期绑定启动开销可以忽略不计。使用gccgcc -fno-plt编译clang后,clang -O2 -g编译tramp3d的时间从41.6秒(PLT)降至36.8秒(-fno-plt)。clang --help则稍微变慢。

(x86-64 PLT stubs使用jmp qword [symbol@GOTPLT],而不是mov r64,imm64/jmp。现代Intel CPU上的内存间接jmp只有一个uop,因此在正确预测时更便宜,但如果GOTPLT条目未命中缓存,则可能较慢。如果经常使用,通常会正确预测。但无论如何,一个10字节的movabs和一个2字节的jmp可以作为一个块获取(如果它适合于16字节对齐的获取块),并且在单个周期中解码,所以3.不是完全不合理的。但这样做更好。)
当分配指针空间时,请记住它们作为数据提取,进入 L1d 缓存,并使用 dTLB 条目而非 iTLB。不要与代码交错,这会浪费 I-cache 上该数据的空间,并且会在包含一个指针和大多数代码的行中浪费 D-cache 上的空间。将您的指针分组放在一个单独的 64 字节块中,使得该行不需要同时存在于 L1I 和 L1D 中。 如果它们与某些代码位于同一页中,也没问题;它们是只读的,因此不会导致自修改代码流水线故障。

3
哇!非常感谢你,彼得!这太棒了!你回答了我甚至不知道自己有的问题!如果我还能悬赏这个问题,我一定会这样做并把奖励给你!我会回去多读几遍并重新查阅你的资料。感谢你的所有努力 :) - Bailey Parker

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接