[msan] Instrument x86 BMI intrinsics.

[eugenis]

Summary

They simply shuffle bits. MSan needs to do the same with shadow bits,
after making sure that the shuffle mask is fully initialized.

[Hahnfeld]

The added test is failing for me because I'm building (and testing) compiler-rt with Clang 7 which doesn't instrument BMI, and I'd assume the same with Clang 8 once released. Is that an oversight or is this configuration expected to break?

lib/msan/tests/msan_test.cc

4653

Shouldn't this be return b & kBmi12Mask? The current expression should always cast to true...

[eugenis]

This is expected to break. I'm surprised it did not break earlier - we often do a compiler change and corresponding integration tests in compiler-rt as a single commit, or two consecutive commits.

lib/msan/tests/msan_test.cc

4653

Of course! Will fix.

[Hahnfeld]

In D58858#1425505, @eugenis wrote:

This is expected to break. I'm surprised it did not break earlier - we often do a compiler change and corresponding integration tests in compiler-rt as a single commit, or two consecutive commits.

I'm running that configuration for years and it always worked. Do you have a change at hand that did such compiler change?

[eugenis]

In D58858#1425740, @Hahnfeld wrote:

I'm running that configuration for years and it always worked. Do you have a change at hand that did such compiler change?

Do you run msan lit tests? This is an example where new compiler behavior is tested the same change list, less than a year ago:
https://reviews.llvm.org/rL332761

[Hahnfeld]

In D58858#1426718, @eugenis wrote:

In D58858#1425740, @Hahnfeld wrote:

I'm running that configuration for years and it always worked. Do you have a change at hand that did such compiler change?

Do you run msan lit tests? This is an example where new compiler behavior is tested the same change list, less than a year ago:
https://reviews.llvm.org/rL332761

Yes, I'm running check-all which includes the lit tests. However they are different in that they use the just-built clang executable which will include the fixes to the instrumentation passes. The unit tests are built with the host compiler (Clang 7 in my case) which obviously doesn't work.

Is there a reason the added test needs to be a unit test instead of a new lit test?

[eugenis]

As far as I can see, "unit" tests in lib/msan/tests also use the freshly built compiler through msan_compile / clang_compile cmake macros. Otherwise this CL would break everyone's builds.

Both standalone and in-tree use cases seem to be handled, as long as you pass correct COMPILER_RT_TEST_COMPILER to cmake.
What are you doing differently?

[Hahnfeld]

Okay, the test failure is related to my Intel Westmere system (yeah, that's old, I know) where I see:

b = 0x13c0
kBmi12Mask = 0x108

Even the "corrected" code only checked that at least one bit is set :-(

Apologies for running into the wrong direction!

lib/msan/tests/msan_test.cc

4653

Actually the code was still wrong: I've changed this to return (b & kBmi12Mask) == kBmi12Mask in rL356242 which fixes my test failures.

lib/msan/tests/msan_test.cc

do {                                                                     \
     __msan_set_expect_umr(1);                                              \
     action;                                                                \
     __msan_set_expect_umr(0);                                              \
     if (TrackingOrigins()) EXPECT_ORIGIN(origin, __msan_get_umr_origin()); \
   } while (0)
 
 #define EXPECT_POISONED(x) ExpectPoisoned(x)
 
-template<typename T>
+template <typename T>
 void ExpectPoisoned(const T& t) {
   EXPECT_NE(-1, __msan_test_shadow((void*)&t, sizeof(t)));
 }
 
 #define EXPECT_POISONED_O(x, origin) \
   ExpectPoisonedWithOrigin(x, origin)
 
 template<typename T>
TEST(MemorySanitizer, MallocUsableSizeTest) {
   int *int_ptr = Ident(new int);
   EXPECT_EQ(0U, malloc_usable_size(NULL));
   EXPECT_EQ(kArraySize, malloc_usable_size(array));
   EXPECT_EQ(sizeof(int), malloc_usable_size(int_ptr));
   free(array);
   delete int_ptr;
 }
 #endif  // SANITIZER_TEST_HAS_MALLOC_USABLE_SIZE
+
+static bool HaveBmi() {
+#ifdef __x86_64__
+  U4 a = 0, b = 0, c = 0, d = 0;
+  asm("cpuid\n\t" : "=a"(a), "=D"(b), "=c"(c), "=d"(d) : "a"(7));
+  const U4 kBmi12Mask = (1U<<3) | (1U<<8);
+  return b | kBmi12Mask;
+#else
+  return false;
+#endif
+}
+
+__attribute__((target("bmi,bmi2")))
+static void TestBZHI() {
+  EXPECT_NOT_POISONED(
+      __builtin_ia32_bzhi_si(Poisoned<U4>(0xABCDABCD, 0xFF000000), 24));
+  EXPECT_POISONED(
+      __builtin_ia32_bzhi_si(Poisoned<U4>(0xABCDABCD, 0xFF800000), 24));
+  // Second operand saturates.
+  EXPECT_POISONED(
+      __builtin_ia32_bzhi_si(Poisoned<U4>(0xABCDABCD, 0x80000000), 240));
+  // Any poison in the second operand poisons output.
+  EXPECT_POISONED(
+      __builtin_ia32_bzhi_si(0xABCDABCD, Poisoned<U4>(1, 1)));
+  EXPECT_POISONED(
+      __builtin_ia32_bzhi_si(0xABCDABCD, Poisoned<U4>(1, 0x80000000)));
+  EXPECT_POISONED(
+      __builtin_ia32_bzhi_si(0xABCDABCD, Poisoned<U4>(1, 0xFFFFFFFF)));
+
+  EXPECT_NOT_POISONED(
+      __builtin_ia32_bzhi_di(Poisoned<U8>(0xABCDABCDABCDABCD, 0xFF00000000000000ULL), 56));
+  EXPECT_POISONED(
+      __builtin_ia32_bzhi_di(Poisoned<U8>(0xABCDABCDABCDABCD, 0xFF80000000000000ULL), 56));
+  // Second operand saturates.
+  EXPECT_POISONED(
+      __builtin_ia32_bzhi_di(Poisoned<U8>(0xABCDABCDABCDABCD, 0x8000000000000000ULL), 240));
+  // Any poison in the second operand poisons output.
+  EXPECT_POISONED(
+      __builtin_ia32_bzhi_di(0xABCDABCDABCDABCD, Poisoned<U8>(1, 1)));
+  EXPECT_POISONED(
+      __builtin_ia32_bzhi_di(0xABCDABCDABCDABCD, Poisoned<U8>(1, 0x8000000000000000ULL)));
+  EXPECT_POISONED(
+      __builtin_ia32_bzhi_di(0xABCDABCDABCDABCD, Poisoned<U8>(1, 0xFFFFFFFF00000000ULL)));
+}
+
+inline U4 bextr_imm(U4 start, U4 len) {
+  start &= 0xFF;
+  len &= 0xFF;
+  return (len << 8) | start;
+}
+
+__attribute__((target("bmi,bmi2")))
+static void TestBEXTR() {
+  EXPECT_POISONED(
+      __builtin_ia32_bextr_u32(Poisoned<U4>(0xABCDABCD, 0xFF), bextr_imm(0, 8)));
+  EXPECT_POISONED(
+      __builtin_ia32_bextr_u32(Poisoned<U4>(0xABCDABCD, 0xFF), bextr_imm(7, 8)));
+  EXPECT_NOT_POISONED(
+      __builtin_ia32_bextr_u32(Poisoned<U4>(0xABCDABCD, 0xFF), bextr_imm(8, 8)));
+  EXPECT_NOT_POISONED(
+      __builtin_ia32_bextr_u32(Poisoned<U4>(0xABCDABCD, 0xFF), bextr_imm(8, 800)));
+  EXPECT_POISONED(
+      __builtin_ia32_bextr_u32(Poisoned<U4>(0xABCDABCD, 0xFF), bextr_imm(7, 800)));
+  EXPECT_NOT_POISONED(
+      __builtin_ia32_bextr_u32(Poisoned<U4>(0xABCDABCD, 0xFF), bextr_imm(5, 0)));
+
+  EXPECT_POISONED(
+      __builtin_ia32_bextr_u32(0xABCDABCD, Poisoned<U4>(bextr_imm(7, 800), 1)));
+  EXPECT_POISONED(__builtin_ia32_bextr_u32(
+      0xABCDABCD, Poisoned<U4>(bextr_imm(7, 800), 0x80000000)));
+
+  EXPECT_POISONED(
+      __builtin_ia32_bextr_u64(Poisoned<U8>(0xABCDABCD, 0xFF), bextr_imm(0, 8)));
+  EXPECT_POISONED(
+      __builtin_ia32_bextr_u64(Poisoned<U8>(0xABCDABCD, 0xFF), bextr_imm(7, 8)));
+  EXPECT_NOT_POISONED(
+      __builtin_ia32_bextr_u64(Poisoned<U8>(0xABCDABCD, 0xFF), bextr_imm(8, 8)));
+  EXPECT_NOT_POISONED(
+      __builtin_ia32_bextr_u64(Poisoned<U8>(0xABCDABCD, 0xFF), bextr_imm(8, 800)));
+  EXPECT_POISONED(
+      __builtin_ia32_bextr_u64(Poisoned<U8>(0xABCDABCD, 0xFF), bextr_imm(7, 800)));
+  EXPECT_NOT_POISONED(
+      __builtin_ia32_bextr_u64(Poisoned<U8>(0xABCDABCD, 0xFF), bextr_imm(5, 0)));
+
+  // Poison in the top half.
+  EXPECT_NOT_POISONED(__builtin_ia32_bextr_u64(
+      Poisoned<U8>(0xABCDABCD, 0xFF0000000000), bextr_imm(32, 8)));
+  EXPECT_POISONED(__builtin_ia32_bextr_u64(
+      Poisoned<U8>(0xABCDABCD, 0xFF0000000000), bextr_imm(32, 9)));
+
+  EXPECT_POISONED(
+      __builtin_ia32_bextr_u64(0xABCDABCD, Poisoned<U8>(bextr_imm(7, 800), 1)));
+  EXPECT_POISONED(__builtin_ia32_bextr_u64(
+      0xABCDABCD, Poisoned<U8>(bextr_imm(7, 800), 0x80000000)));
+}
+
+__attribute__((target("bmi,bmi2")))
+static void TestPDEP() {
+  U4 x = Poisoned<U4>(0, 0xFF00);
+  EXPECT_NOT_POISONED(__builtin_ia32_pdep_si(x, 0xFF));
+  EXPECT_POISONED(__builtin_ia32_pdep_si(x, 0x1FF));
+  EXPECT_NOT_POISONED(__builtin_ia32_pdep_si(x, 0xFF00));
+  EXPECT_POISONED(__builtin_ia32_pdep_si(x, 0x1FF00));
+
+  EXPECT_NOT_POISONED(__builtin_ia32_pdep_si(x, 0x1FF00) & 0xFF);
+  EXPECT_POISONED(__builtin_ia32_pdep_si(0, Poisoned<U4>(0xF, 1)));
+
+  U8 y = Poisoned<U8>(0, 0xFF00);
+  EXPECT_NOT_POISONED(__builtin_ia32_pdep_di(y, 0xFF));
+  EXPECT_POISONED(__builtin_ia32_pdep_di(y, 0x1FF));
+  EXPECT_NOT_POISONED(__builtin_ia32_pdep_di(y, 0xFF0000000000));
+  EXPECT_POISONED(__builtin_ia32_pdep_di(y, 0x1FF000000000000));
+
+  EXPECT_NOT_POISONED(__builtin_ia32_pdep_di(y, 0x1FF00) & 0xFF);
+  EXPECT_POISONED(__builtin_ia32_pdep_di(0, Poisoned<U4>(0xF, 1)));
+}
+
+__attribute__((target("bmi,bmi2")))
+static void TestPEXT() {
+  U4 x = Poisoned<U4>(0, 0xFF00);
+  EXPECT_NOT_POISONED(__builtin_ia32_pext_si(x, 0xFF));
+  EXPECT_POISONED(__builtin_ia32_pext_si(x, 0x1FF));
+  EXPECT_POISONED(__builtin_ia32_pext_si(x, 0x100));
+  EXPECT_POISONED(__builtin_ia32_pext_si(x, 0x1000));
+  EXPECT_NOT_POISONED(__builtin_ia32_pext_si(x, 0x10000));
+
+  EXPECT_POISONED(__builtin_ia32_pext_si(0xFF00, Poisoned<U4>(0xFF, 1)));
+
+  U8 y = Poisoned<U8>(0, 0xFF0000000000);
+  EXPECT_NOT_POISONED(__builtin_ia32_pext_di(y, 0xFF00000000));
+  EXPECT_POISONED(__builtin_ia32_pext_di(y, 0x1FF00000000));
+  EXPECT_POISONED(__builtin_ia32_pext_di(y, 0x10000000000));
+  EXPECT_POISONED(__builtin_ia32_pext_di(y, 0x100000000000));
+  EXPECT_NOT_POISONED(__builtin_ia32_pext_di(y, 0x1000000000000));
+
+  EXPECT_POISONED(__builtin_ia32_pext_di(0xFF00, Poisoned<U8>(0xFF, 1)));
+}
+
+TEST(MemorySanitizer, Bmi) {
+  if (HaveBmi()) {
+    TestBZHI();
+    TestBEXTR();
+    TestPDEP();
+    TestPEXT();
+  }
+}