[sanitizer/coverage] Add AFL-style coverage counters (search heuristic for fuzzing).

Introduce -mllvm -sanitizer-coverage-8bit-counters=1
which adds imprecise thread-unfriendly 8-bit coverage counters.

The run-time library maps these 8-bit counters to 8-bit bitsets in the same way
AFL (http://lcamtuf.coredump.cx/afl/technical_details.txt) does:
counter values are divided into 8 ranges and based on the counter
value one of the bits in the bitset is set.
The AFL ranges are used here: 1, 2, 3, 4-7, 8-15, 16-31, 32-127, 128+.

These counters provide a search heuristic for single-threaded
coverage-guided fuzzers, we do not expect them to be useful for other purposes.

Depending on the value of -fsanitize-coverage=[123] flag,
these counters will be added to the function entry blocks (=1),
every basic block (=2), or every edge (=3).

Use these counters as an optional search heuristic in the Fuzzer library.
Add a test where this heuristic is critical.


git-svn-id: https://llvm.org/svn/llvm-project/compiler-rt/trunk@231166 91177308-0d34-0410-b5e6-96231b3b80d8

1 files changed, 93 insertions, 1 deletions

diff --git a/lib/sanitizer_common/sanitizer_coverage_libcdep.cc b/lib/sanitizer_common/sanitizer_coverage_libcdep.cc
index 49887b1e9..7197b4c6a 100644
--- a/lib/sanitizer_common/sanitizer_coverage_libcdep.cc
+++ b/lib/sanitizer_common/sanitizer_coverage_libcdep.cc
@@ -83,7 +83,10 @@ class CoverageData {
 
   void InitializeGuardArray(s32 *guards);
   void InitializeGuards(s32 *guards, uptr n, const char *module_name);
+  void InitializeCounters(u8 *counters, uptr n);
   void ReinitializeGuards();
+  uptr GetNumberOf8bitCounters();
+  uptr Update8bitCounterBitsetAndClearCounters(u8 *bitset);
 
   uptr *data();
   uptr size();
@@ -113,6 +116,14 @@ class CoverageData {
   // Vector of module (compilation unit) names.
   InternalMmapVectorNoCtor<const char*> comp_unit_name_vec;
 
+  struct CounterAndSize {
+    u8 *counters;
+    uptr n;
+  };
+
+  InternalMmapVectorNoCtor<CounterAndSize> counters_vec;
+  uptr num_8bit_counters;
+
   // Caller-Callee (cc) array, size and current index.
   static const uptr kCcArrayMaxSize = FIRST_32_SECOND_64(1 << 18, 1 << 24);
   uptr **cc_array;
@@ -184,6 +195,8 @@ void CoverageData::Enable() {
            GetMmapGranularity());
   tr_event_array_size = kTrEventArrayMaxSize;
   tr_event_pointer = tr_event_array;
+
+  num_8bit_counters = 0;
 }
 
 void CoverageData::InitializeGuardArray(s32 *guards) {
@@ -289,6 +302,15 @@ void CoverageData::Extend(uptr npcs) {
   atomic_store(&pc_array_size, size, memory_order_release);
 }
 
+void CoverageData::InitializeCounters(u8 *counters, uptr n) {
+  if (!counters) return;
+  CHECK_EQ(reinterpret_cast<uptr>(counters) % 16, 0);
+  n = RoundUpTo(n, 16); // The compiler must ensure that counters is 16-aligned.
+  SpinMutexLock l(&mu);
+  counters_vec.push_back({counters, n});
+  num_8bit_counters += n;
+}
+
 void CoverageData::InitializeGuards(s32 *guards, uptr n,
                                     const char *module_name) {
   // The array 'guards' has n+1 elements, we use the element zero
@@ -354,6 +376,64 @@ void CoverageData::IndirCall(uptr caller, uptr callee, uptr callee_cache[],
   }
 }
 
+uptr CoverageData::GetNumberOf8bitCounters() {
+  return num_8bit_counters;
+}
+
+// Map every 8bit counter to a 8-bit bitset and clear the counter.
+uptr CoverageData::Update8bitCounterBitsetAndClearCounters(u8 *bitset) {
+  uptr num_new_bits = 0;
+  uptr cur = 0;
+  // For better speed we map 8 counters to 8 bytes of bitset at once.
+  static const uptr kBatchSize = 8;
+  CHECK_EQ(reinterpret_cast<uptr>(bitset) % kBatchSize, 0);
+  for (uptr i = 0, len = counters_vec.size(); i < len; i++) {
+    u8 *c = counters_vec[i].counters;
+    uptr n = counters_vec[i].n;
+    CHECK_EQ(n % 16, 0);
+    CHECK_EQ(cur % kBatchSize, 0);
+    CHECK_EQ(reinterpret_cast<uptr>(c) % kBatchSize, 0);
+    if (!bitset) {
+      internal_bzero_aligned16(c, n);
+      cur += n;
+      continue;
+    }
+    for (uptr j = 0; j < n; j += kBatchSize, cur += kBatchSize) {
+      CHECK_LT(cur, num_8bit_counters);
+      u64 *pc64 = reinterpret_cast<u64*>(c + j);
+      u64 *pb64 = reinterpret_cast<u64*>(bitset + cur);
+      u64 c64 = *pc64;
+      u64 old_bits_64 = *pb64;
+      u64 new_bits_64 = old_bits_64;
+      if (c64) {
+        *pc64 = 0;
+        for (uptr k = 0; k < kBatchSize; k++) {
+          u64 x = (c64 >> (8 * k)) & 0xff;
+          if (x) {
+            u64 bit = 0;
+            /**/ if (x >= 128) bit = 128;
+            else if (x >= 32) bit = 64;
+            else if (x >= 16) bit = 32;
+            else if (x >= 8) bit = 16;
+            else if (x >= 4) bit = 8;
+            else if (x >= 3) bit = 4;
+            else if (x >= 2) bit = 2;
+            else if (x >= 1) bit = 1;
+            u64 mask = bit << (8 * k);
+            if (!(new_bits_64 & mask)) {
+              num_new_bits++;
+              new_bits_64 |= mask;
+            }
+          }
+        }
+        *pb64 = new_bits_64;
+      }
+    }
+  }
+  CHECK_EQ(cur, num_8bit_counters);
+  return num_new_bits;
+}
+
 uptr *CoverageData::data() {
   return pc_array;
 }
@@ -689,8 +769,10 @@ SANITIZER_INTERFACE_ATTRIBUTE void __sanitizer_cov_init() {
 }
 SANITIZER_INTERFACE_ATTRIBUTE void __sanitizer_cov_dump() { CovDump(); }
 SANITIZER_INTERFACE_ATTRIBUTE void
-__sanitizer_cov_module_init(s32 *guards, uptr npcs, const char *module_name) {
+__sanitizer_cov_module_init(s32 *guards, uptr npcs, u8 *counters,
+                            const char *module_name) {
   coverage_data.InitializeGuards(guards, npcs, module_name);
+  coverage_data.InitializeCounters(counters, npcs);
   if (!common_flags()->coverage_direct) return;
   if (SANITIZER_ANDROID && coverage_enabled) {
     // dlopen/dlclose interceptors do not work on Android, so we rely on
@@ -728,4 +810,14 @@ uptr __sanitizer_get_coverage_guards(uptr **data) {
   *data = coverage_data.data();
   return coverage_data.size();
 }
+
+SANITIZER_INTERFACE_ATTRIBUTE
+uptr __sanitizer_get_number_of_counters() {
+  return coverage_data.GetNumberOf8bitCounters();
+}
+
+SANITIZER_INTERFACE_ATTRIBUTE
+uptr __sanitizer_update_counter_bitset_and_clear_counters(u8 *bitset) {
+  return coverage_data.Update8bitCounterBitsetAndClearCounters(bitset);
+}
 }  // extern "C"