c - 内存依赖推测是否会阻止 BN_consttime_swap 成为恒定时间？

Question

上下文

function 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 在他的 optimization manuals 中描述的架构。 .还假定将 C 代码直接转换为汇编代码(无需 C 编译器取消程序员的工作)。

问题

我试图了解上述结构是“尽力而为”的恒定时间执行，还是完美的恒定时间执行。

我特别关心调用函数BN_consttime_swap时bignum a已经在L1数据缓存中的场景，以及函数之后的代码返回立即开始处理 bignum a。在现代处理器上，可以同时运行足够多的指令，以便在使用 bignum a 时从技术上讲不会完成复制。允许调用 BN_consttime_swap 后的指令在 a 上工作的机制是内存依赖推测。让我们假设 naive memory dependence speculation为了论证。

问题似乎归结为:

当处理器最终检测到 BN_consttime_swap 之后的代码从内存中读取时，与猜测相反，它被写入了函数内部，它是否会立即取消推测执行检测到地址已被写入，还是在检测到已写入的值与已经存在的值相同时允许自己保留该地址？

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

即使在第二种情况下，这看起来也可以在可预见的 future (只要处理器保持足够天真)通过为两个 bignums 中的每一个的每个单词写入一个不同于在再次写入旧值或新值之前，两个可能的最终值。 volatile 类型限定符可能需要在某些时候参与，以防止普通编译器过度优化序列，但这听起来仍然可行。

注意:我知道 store forwarding ，但存储转发只是一个捷径。它不会阻止读取在它应该在其之后执行的之前执行。在某些情况下它会失败，尽管在这种情况下人们不会期望它会失败。

Answer 1

Straightforward translation of the C code to assembly (without the C compiler undoing the efforts of the programmer) is also assumed.

我知道这不是您问题的重点，而且我知道您 知道这一点，但我需要吐槽一下。这甚至不符合提供恒定时间执行的“最大努力”尝试。编译器被授权检查 condition 的值，如果 condition 为零，则跳过整个过程。混淆 condition 的设置可以降低这种情况发生的可能性，但不能保证。

据称“恒定时间”代码不应该用 C 语言编写，句号。即使今天是恒定时间，在你测试的编译器上，一个更聪明的编译器也会出现并打败你。您的一位用户会在您之前使用此编译器，他们不会意识到您让他们面临的风险。我知道只有三种方法可以实现恒定时间:专用硬件、程序集或生成机器代码的 DSL 以及恒定时间执行的证明。

---

抛开咆哮，关于手头的实际架构问题:假设一个愚蠢天真的编译器，这段代码是 µarches 上的恒定时间，我已经足够熟悉来评估这个问题，我希望它对一个人来说是广泛适用的原因很简单:权力。我希望如果存储的值与已经存在的值匹配并有条件地使存储短路或避免弄脏每个存储上的缓存行，那么检查存储队列或缓存会消耗比在极少数情况下保存的能量更多的能量避免一些工作。但是，我不是 CPU 设计者，也不敢代表他们发言，因此请多加怀疑，在假设这是真的之前请咨询其中一位。