Контекст
Функция BN_consttime_swap
в OpenSSL - вещь прекрасная. В этом фрагменте 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 более высокого уровня занимают постоянное время, эта функция либо заменяет два бонуса, либо оставляет их на месте в постоянное время. Когда он оставляет их на месте, он на самом деле читает каждое слово каждого бонуса, вычисляет новое слово, которое идентично старому слову, и записывает этот результат обратно в исходное местоположение.
Цель состоит в том, что это займет то же самое время, как если бы бонусы были эффективно заменены.
В этом вопросе я предполагаю современную, широко распространенную архитектуру, такую как те, которые описаны Agner Fog в его руководствах по оптимизации. Предполагается также простой перевод кода C на сборку (без компилятора C, отменяющего усилия программиста).
Вопрос
Я пытаюсь понять, характеризует ли описанная выше конструкция как "наилучшее усилие" выполнения постоянной работы или как идеальное выполнение постоянной времени.
В частности, меня беспокоит сценарий, когда bignum a
уже находится в кэше данных L1 при вызове функции BN_consttime_swap
, а код сразу после возвращения функции начинает работать с правами bignum a
далеко. На современном процессоре достаточно инструкций может быть одновременно в полете, чтобы копия не была технически закончена, когда используется bignum a
. Механизм, позволяющий инструкциям после вызова BN_consttime_swap
работать на a
, - это спекуляция о зависимости от памяти. Предположим наивные предположения о зависимости от памяти для аргумента.
Кажется, что этот вопрос сводится к следующему:
Когда процессор, наконец, обнаруживает, что код после BN_consttime_swap
читается из памяти, который, вопреки спекуляции, был написан внутри функции, отменяет ли он спекулятивное исполнение, как только он обнаруживает, что адрес написано или позволяет сохранить его, когда обнаруживает, что значение, которое было написано, совпадает с значением, которое уже было там?
В первом случае BN_consttime_swap
выглядит так, будто он реализует идеальное постоянное время. Во втором случае это только наилучшее усилие: постоянное время: если бингомы не были заменены, выполнение кода, следующего после вызова BN_consttime_swap
, будет значительно быстрее, чем если бы они были заменены.
Даже во втором случае это похоже на то, что он может быть исправлен в обозримом будущем (пока процессоры остаются наивными) за каждое слово каждого из двух бонусов, записывая значение, отличное от два возможных окончательных значения перед записью либо старого значения, либо нового значения. Квалификатор типа volatile
, возможно, должен быть задействован в какой-то момент, чтобы не позволить обычным компиляторам чрезмерно оптимизировать последовательность, но это все еще кажется возможным.
ПРИМЕЧАНИЕ. Я знаю о сохранении пересылки, но сохранение пересылки - это только ярлык. Это не мешает чтению, выполняемому до, писать, которое оно должно последовать. И в некоторых случаях это терпит неудачу, хотя в этом случае этого не ожидалось.