Add a value barrier to constant-time selects.

Clang recognizes the (mask & a) | (~mask & b) pattern as a select. While
it often optimizes this into a cmov, it sometimes inserts branches
instead, particularly when it detects a string of cmovs with the same
condition.

In the long term, we need language-level support for expressing our
constraints. In the short term, introduce value barriers to prevent the
compiler from reasoning about our bit tricks. Thanks to Chandler Carruth
for suggesting this pattern. It should be reasonably robust, short of
value-based PGO or the compiler learning to reason about empty inline
assembly blocks.

Apply barriers to our various constant-time selects. We should invest
more in the valgrind-based tooling to figure out if there are other
instances.

Change-Id: Icc24ce36a61f7fec021a762c27197b9c5bd28c5d
Reviewed-on: https://boringssl-review.googlesource.com/c/boringssl/+/36484
Reviewed-by: Chandler Carruth <chandlerc@google.com>
Reviewed-by: Adam Langley <agl@google.com>

4 files changed, 28 insertions, 4 deletions

diff --git a/third_party/fiat/curve25519_32.h b/third_party/fiat/curve25519_32.h
index 820a5c9..5377242 100644
--- a/third_party/fiat/curve25519_32.h
+++ b/third_party/fiat/curve25519_32.h
@@ -90,7 +90,13 @@ static void fiat_25519_subborrowx_u25(uint32_t* out1, fiat_25519_uint1* out2, fi
 static void fiat_25519_cmovznz_u32(uint32_t* out1, fiat_25519_uint1 arg1, uint32_t arg2, uint32_t arg3) {
   fiat_25519_uint1 x1 = (!(!arg1));
   uint32_t x2 = ((fiat_25519_int1)(0x0 - x1) & UINT32_C(0xffffffff));
-  uint32_t x3 = ((x2 & arg3) | ((~x2) & arg2));
+  // Note this line has been patched from the synthesized code to add value
+  // barriers.
+  //
+  // Clang recognizes this pattern as a select. While it usually transforms it
+  // to a cmov, it sometimes further transforms it into a branch, which we do
+  // not want.
+  uint32_t x3 = ((value_barrier_u32(x2) & arg3) | (value_barrier_u32(~x2) & arg2));
   *out1 = x3;
 }
 
diff --git a/third_party/fiat/curve25519_64.h b/third_party/fiat/curve25519_64.h
index 23bf361..7c31ff9 100644
--- a/third_party/fiat/curve25519_64.h
+++ b/third_party/fiat/curve25519_64.h
@@ -58,7 +58,13 @@ static void fiat_25519_subborrowx_u51(uint64_t* out1, fiat_25519_uint1* out2, fi
 static void fiat_25519_cmovznz_u64(uint64_t* out1, fiat_25519_uint1 arg1, uint64_t arg2, uint64_t arg3) {
   fiat_25519_uint1 x1 = (!(!arg1));
   uint64_t x2 = ((fiat_25519_int1)(0x0 - x1) & UINT64_C(0xffffffffffffffff));
-  uint64_t x3 = ((x2 & arg3) | ((~x2) & arg2));
+  // Note this line has been patched from the synthesized code to add value
+  // barriers.
+  //
+  // Clang recognizes this pattern as a select. While it usually transforms it
+  // to a cmov, it sometimes further transforms it into a branch, which we do
+  // not want.
+  uint64_t x3 = ((value_barrier_u64(x2) & arg3) | (value_barrier_u64(~x2) & arg2));
   *out1 = x3;
 }
 
diff --git a/third_party/fiat/p256_32.h b/third_party/fiat/p256_32.h
index faaa0b0..638eb5d 100644
--- a/third_party/fiat/p256_32.h
+++ b/third_party/fiat/p256_32.h
@@ -77,7 +77,13 @@ static void fiat_p256_mulx_u32(uint32_t* out1, uint32_t* out2, uint32_t arg1, ui
 static void fiat_p256_cmovznz_u32(uint32_t* out1, fiat_p256_uint1 arg1, uint32_t arg2, uint32_t arg3) {
   fiat_p256_uint1 x1 = (!(!arg1));
   uint32_t x2 = ((fiat_p256_int1)(0x0 - x1) & UINT32_C(0xffffffff));
-  uint32_t x3 = ((x2 & arg3) | ((~x2) & arg2));
+  // Note this line has been patched from the synthesized code to add value
+  // barriers.
+  //
+  // Clang recognizes this pattern as a select. While it usually transforms it
+  // to a cmov, it sometimes further transforms it into a branch, which we do
+  // not want.
+  uint32_t x3 = ((value_barrier_u32(x2) & arg3) | (value_barrier_u32(~x2) & arg2));
   *out1 = x3;
 }
 
diff --git a/third_party/fiat/p256_64.h b/third_party/fiat/p256_64.h
index 8e449c6..7d97e0a 100644
--- a/third_party/fiat/p256_64.h
+++ b/third_party/fiat/p256_64.h
@@ -79,7 +79,13 @@ static void fiat_p256_mulx_u64(uint64_t* out1, uint64_t* out2, uint64_t arg1, ui
 static void fiat_p256_cmovznz_u64(uint64_t* out1, fiat_p256_uint1 arg1, uint64_t arg2, uint64_t arg3) {
   fiat_p256_uint1 x1 = (!(!arg1));
   uint64_t x2 = ((fiat_p256_int1)(0x0 - x1) & UINT64_C(0xffffffffffffffff));
-  uint64_t x3 = ((x2 & arg3) | ((~x2) & arg2));
+  // Note this line has been patched from the synthesized code to add value
+  // barriers.
+  //
+  // Clang recognizes this pattern as a select. While it usually transforms it
+  // to a cmov, it sometimes further transforms it into a branch, which we do
+  // not want.
+  uint64_t x3 = ((value_barrier_u64(x2) & arg3) | (value_barrier_u64(~x2) & arg2));
   *out1 = x3;
 }