内存依赖性推测会阻止BN_consttime_swap成为恒定时间吗？

Question

上下文

OpenSSL中的功能 BN_consttime_swap是一件美丽的事情.在此片段中,condition已计算为0或(BN_ULONG)-1:

#define BN_CONSTTIME_SWAP(ind) \
    do { \
            t = (a->d[ind] ^ b->d[ind]) & condition; \
            a->d[ind] ^= t; \
            b->d[ind] ^= t; \
    } while (0)
…
    BN_CONSTTIME_SWAP(9);
…
    BN_CONSTTIME_SWAP(8);
…
    BN_CONSTTIME_SWAP(7);

目的是为了确保更高级别的bignum操作需要恒定的时间,这个功能要么交换两个bignum,要么在恒定时间内将它们留在原位.当它离开它们时,它实际上读取每个bignum的每个单词,计算一个与旧单词相同的新单词,并将该结果写回原始位置.

目的是这将花费相同的时间,好像有效地交换了bignums.

在这个问题中,我假设一个现代的,广泛的架构,如Agner Fog在他的优化手册中描述的那些.还假设C代码直接转换为汇编(没有C编译器撤消程序员的努力).

题

我试图理解上面的构造是否表征为"尽力而为"的恒定时间执行,或者是完美的恒定时间执行.

特别是,我担心a在BN_consttime_swap调用函数时bignum 已经在L1数据缓存中的情况,并且函数返回后的代码立即开始在bignum上工作a.在现代处理器上,足够的指令可以同时在飞行中,以便在a使用bignum时技术上不会完成复制.在调用之后允许指令BN_consttime_swap工作的机制a是存储器依赖性推测.让我们假设为了论证而进行天真的记忆依赖性推测.

这个问题似乎归结为:

当处理器最终检测到BN_consttime_swap从内存读取后的代码,与推测相反,已经写入函数内部时,一旦检测到地址已被写入,它是否取消推测执行,或者它是否允许自己当它检测到已写入的值与已存在的值相同时保留它？

在第一种情况下,BN_consttime_swap看起来它实现了完美的恒定时间.在第二种情况下,它只是尽力而为的恒定时间:如果没有交换bignums,那么在调用之后执行的代码BN_consttime_swap将比它们被交换时快得多.

即使在第二种情况下,这看起来似乎可以在可预见的未来固定(只要处理器保持足够天真),对于两个bignums中的每一个的每个单词,写出不同于两个可能的最终值的值.在再次写入旧值或新值之前的值.该volatile类型修饰符可能需要在某一时刻参与,以防止一个普通的编译器过度优化的序列,但它仍然听起来可能.

注意:我知道商店转发,但商店转发只是一种捷径.它不会阻止在执行写操作之前执行读操作.在某些情况下它会失败,尽管在这种情况下人们不会指望它.

Answer 1

还假设C代码直接转换为汇编(没有C编译器撤消程序员的努力).

我知道这不是你问题的主旨,我知道你知道这一点,但我需要咆哮一分钟.这甚至没有资格作为提供恒定时间执行的"尽力而为"尝试.许可编译器检查其值condition,如果condition为零则跳过整个事件.模糊设置condition使得这种情况不太可能发生,但不能保证.

据称,"恒定时间"代码不应该用C语言写成,完全停止.即使它是今天的恒定时间,在您测试的编译器上,一个更聪明的编译器也会出现并击败您.您的其中一个用户将在使用此编译器之前使用此编译器,并且他们不会意识到您将其暴露给它们的风险.我知道有三种实现恒定时间的方法:专用硬件,汇编或生成机器代码的DSL以及恒定时间执行的证明.

暂且不谈,关于手头的实际架构问题:假设一个愚蠢的天真的编译器,这段代码是我熟悉的μ问题的常量时间来评估这个问题,并且我认为它大致是真的,原因很简单:功率.我希望检查存储队列或缓存,如果存储的值与已存在的值匹配并有条件地使存储短路或避免弄脏每个商店的缓存行消耗的能量比在极少数情况下节省的能量消耗更多避免一些工作.但是,我不是CPU设计师,并且不假设代表他们发言,所以请用几汤匙盐,并在假设这是真的之前请咨询一下.

Answer 2

这篇博文以及作者 Henry 就该问题发表的评论应被视为具有任何人所期望的权威性。我将在这里复制后者以供存档：

\n

\n

我不认为用相同值覆盖内存位置的情况有实际用途。我认为答案是，在当前的处理器中，存储的值是无关紧要的，只有地址很重要。

\n

在学术界，我听说过两种消除内存歧义的方法：基于地址或基于值。据我所知，当前的处理器都进行基于地址的消歧。

\n

我认为当前的微基准测试有一些证据表明该值与 \xe2\x80\x99t 相关。许多情况涉及将相同的值重复存储到相同的位置（特别是那些偏移量 = 0 的位置）。这些速度并不算异常快。

\n

基于地址的方案使用存储队列和加载队列来跟踪未完成的内存操作。加载检查存储队列以获取地址匹配（此加载是否应该执行存储到加载转发而不是从缓存读取？），而存储则检查加载队列（此存储是否破坏了我允许执行的后续加载的位置）早期的？）。这些检查完全基于地址（存储和加载发生冲突的位置）。该方案的一个优点是，它是存储到加载转发之上的一个相当简单的扩展，因为那里也使用了存储队列搜索。

\n

基于值的方案摆脱了关联搜索（即更快、功耗更低等），但需要更好的预测器来进行存储到加载的转发（现在你必须猜测是否转发以及转发到哪里，而不是搜索SQ）。这些方案通过在提交时重新执行加载并检查它们的值是否正确来检查顺序违规（和不正确的转发）。在这些方案中，如果您有一个冲突的存储（或犯了一些其他错误）但仍然产生正确的结果值，则不会将其检测为排序违规。

\n

未来的处理器可以转向基于价值的方案吗？我怀疑他们可能会。它们是在 2000 年代中期提出的，旨在降低内存执行硬件的复杂性。

\n

\n