Runtime flags for malloc bisection.
Reviewers: kcc, pcc
Subscribers: kubamracek, mgorny, jdoerfert, llvm-commits
Tags: #llvm
Differential Revision: https://reviews.llvm.org/D58162
git-svn-id: https://llvm.org/svn/llvm-project/compiler-rt/trunk@354156 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/lib/hwasan/CMakeLists.txt b/lib/hwasan/CMakeLists.txt
index 20ab94d..71db2d5 100644
--- a/lib/hwasan/CMakeLists.txt
+++ b/lib/hwasan/CMakeLists.txt
@@ -24,6 +24,7 @@
hwasan_flags.h
hwasan_flags.inc
hwasan_interface_internal.h
+ hwasan_malloc_bisect.h
hwasan_mapping.h
hwasan_poisoning.h
hwasan_report.h
diff --git a/lib/hwasan/hwasan_allocator.cc b/lib/hwasan/hwasan_allocator.cc
index 4a4de3e..09f1ab9 100644
--- a/lib/hwasan/hwasan_allocator.cc
+++ b/lib/hwasan/hwasan_allocator.cc
@@ -17,6 +17,7 @@
#include "hwasan.h"
#include "hwasan_allocator.h"
#include "hwasan_mapping.h"
+#include "hwasan_malloc_bisect.h"
#include "hwasan_thread.h"
#include "hwasan_report.h"
@@ -181,7 +182,7 @@
// retag to 0.
if ((flags()->tag_in_malloc || flags()->tag_in_free) &&
atomic_load_relaxed(&hwasan_allocator_tagging_enabled)) {
- tag_t tag = flags()->tag_in_malloc
+ tag_t tag = flags()->tag_in_malloc && malloc_bisect(stack, orig_size)
? (t ? t->GenerateRandomTag() : kFallbackAllocTag)
: 0;
user_ptr = (void *)TagMemoryAligned((uptr)user_ptr, size, tag);
@@ -247,7 +248,7 @@
Min(TaggedSize(orig_size), (uptr)flags()->max_free_fill_size);
internal_memset(aligned_ptr, flags()->free_fill_byte, fill_size);
}
- if (flags()->tag_in_free &&
+ if (flags()->tag_in_free && malloc_bisect(stack, 0) &&
atomic_load_relaxed(&hwasan_allocator_tagging_enabled))
TagMemoryAligned(reinterpret_cast<uptr>(aligned_ptr), TaggedSize(orig_size),
t ? t->GenerateRandomTag() : kFallbackFreeTag);
diff --git a/lib/hwasan/hwasan_flags.inc b/lib/hwasan/hwasan_flags.inc
index f0cf151..01fdad8 100644
--- a/lib/hwasan/hwasan_flags.inc
+++ b/lib/hwasan/hwasan_flags.inc
@@ -85,3 +85,16 @@
"The number of stack frames remembered per thread. "
"Affects the quality of stack-related reports, but not the ability "
"to find bugs.")
+
+// Malloc / free bisection. Only tag malloc and free calls when a hash of
+// allocation size and stack trace is between malloc_bisect_left and
+// malloc_bisect_right (both inclusive). [0, 0] range is special and disables
+// bisection (i.e. everything is tagged). Once the range is narrowed down
+// enough, use malloc_bisect_dump to see interesting allocations.
+HWASAN_FLAG(uptr, malloc_bisect_left, 0,
+ "Left bound of malloc bisection, inclusive.")
+HWASAN_FLAG(uptr, malloc_bisect_right, 0,
+ "Right bound of malloc bisection, inclusive.")
+HWASAN_FLAG(bool, malloc_bisect_dump, false,
+ "Print all allocations within [malloc_bisect_left, "
+ "malloc_bisect_right] range ")
diff --git a/lib/hwasan/hwasan_malloc_bisect.h b/lib/hwasan/hwasan_malloc_bisect.h
new file mode 100644
index 0000000..eaf124a
--- /dev/null
+++ b/lib/hwasan/hwasan_malloc_bisect.h
@@ -0,0 +1,50 @@
+//===-- hwasan_malloc_bisect.h ----------------------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// This file is a part of HWAddressSanitizer.
+//
+//===----------------------------------------------------------------------===//
+
+#include "sanitizer_common/sanitizer_hash.h"
+#include "hwasan.h"
+
+namespace __hwasan {
+
+static u32 malloc_hash(StackTrace *stack, uptr orig_size) {
+ uptr len = Min(stack->size, (unsigned)7);
+ MurMur2HashBuilder H(len);
+ H.add(orig_size);
+ // Start with frame #1 to skip __sanitizer_malloc frame, which is
+ // (a) almost always the same (well, could be operator new or new[])
+ // (b) can change hashes when compiler-rt is rebuilt, invalidating previous
+ // bisection results.
+ // Because of ASLR, use only offset inside the page.
+ for (uptr i = 1; i < len; ++i) H.add(((u32)stack->trace[i]) & 0xFFF);
+ return H.get();
+}
+
+static INLINE bool malloc_bisect(StackTrace *stack, uptr orig_size) {
+ uptr left = flags()->malloc_bisect_left;
+ uptr right = flags()->malloc_bisect_right;
+ if (LIKELY(left == 0 && right == 0))
+ return true;
+ if (!stack)
+ return true;
+ // Allow malloc_bisect_right > (u32)(-1) to avoid spelling the latter in
+ // decimal.
+ uptr h = (uptr)malloc_hash(stack, orig_size);
+ if (h < left || h > right)
+ return false;
+ if (flags()->malloc_bisect_dump) {
+ Printf("[alloc] %u %zu\n", h, orig_size);
+ stack->Print();
+ }
+ return true;
+}
+
+} // namespace __hwasan
diff --git a/lib/sanitizer_common/CMakeLists.txt b/lib/sanitizer_common/CMakeLists.txt
index 470ef20..4d331ec 100644
--- a/lib/sanitizer_common/CMakeLists.txt
+++ b/lib/sanitizer_common/CMakeLists.txt
@@ -142,6 +142,7 @@
sanitizer_freebsd.h
sanitizer_fuchsia.h
sanitizer_getauxval.h
+ sanitizer_hash.h
sanitizer_interceptors_ioctl_netbsd.inc
sanitizer_interface_internal.h
sanitizer_internal_defs.h
diff --git a/lib/sanitizer_common/sanitizer_hash.h b/lib/sanitizer_common/sanitizer_hash.h
new file mode 100644
index 0000000..3d97dcc
--- /dev/null
+++ b/lib/sanitizer_common/sanitizer_hash.h
@@ -0,0 +1,43 @@
+//===-- sanitizer_common.h --------------------------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements a simple hash function.
+//===----------------------------------------------------------------------===//
+
+#ifndef SANITIZER_HASH_H
+#define SANITIZER_HASH_H
+
+#include "sanitizer_internal_defs.h"
+
+namespace __sanitizer {
+class MurMur2HashBuilder {
+ static const u32 m = 0x5bd1e995;
+ static const u32 seed = 0x9747b28c;
+ static const u32 r = 24;
+ u32 h;
+
+ public:
+ explicit MurMur2HashBuilder(u32 init = 0) { h = seed ^ init; }
+ void add(u32 k) {
+ k *= m;
+ k ^= k >> r;
+ k *= m;
+ h *= m;
+ h ^= k;
+ }
+ u32 get() {
+ u32 x = h;
+ x ^= x >> 13;
+ x *= m;
+ x ^= x >> 15;
+ return x;
+ }
+};
+} //namespace __sanitizer
+
+#endif // SANITIZER_HASH_H
diff --git a/lib/sanitizer_common/sanitizer_stackdepot.cc b/lib/sanitizer_common/sanitizer_stackdepot.cc
index a38cb9d..1cdedfa 100644
--- a/lib/sanitizer_common/sanitizer_stackdepot.cc
+++ b/lib/sanitizer_common/sanitizer_stackdepot.cc
@@ -13,6 +13,7 @@
#include "sanitizer_stackdepot.h"
#include "sanitizer_common.h"
+#include "sanitizer_hash.h"
#include "sanitizer_stackdepotbase.h"
namespace __sanitizer {
@@ -49,23 +50,9 @@
return sizeof(StackDepotNode) + (args.size - 1) * sizeof(uptr);
}
static u32 hash(const args_type &args) {
- // murmur2
- const u32 m = 0x5bd1e995;
- const u32 seed = 0x9747b28c;
- const u32 r = 24;
- u32 h = seed ^ (args.size * sizeof(uptr));
- for (uptr i = 0; i < args.size; i++) {
- u32 k = args.trace[i];
- k *= m;
- k ^= k >> r;
- k *= m;
- h *= m;
- h ^= k;
- }
- h ^= h >> 13;
- h *= m;
- h ^= h >> 15;
- return h;
+ MurMur2HashBuilder H(args.size * sizeof(uptr));
+ for (uptr i = 0; i < args.size; i++) H.add(args.trace[i]);
+ return H.get();
}
static bool is_valid(const args_type &args) {
return args.size > 0 && args.trace;
diff --git a/test/hwasan/TestCases/malloc_bisect.c b/test/hwasan/TestCases/malloc_bisect.c
new file mode 100644
index 0000000..51cbbfe
--- /dev/null
+++ b/test/hwasan/TestCases/malloc_bisect.c
@@ -0,0 +1,26 @@
+// RUN: %clang_hwasan -O0 %s -o %t
+// RUN: %env_hwasan_opts=malloc_bisect_left=0,malloc_bisect_right=0 not %run %t 2>&1 | \
+// RUN: FileCheck %s --check-prefix=CRASH
+// RUN: %env_hwasan_opts=malloc_bisect_left=1000,malloc_bisect_right=999 %run %t 2>&1
+// RUN: %env_hwasan_opts=malloc_bisect_left=0,malloc_bisect_right=4294967295 not %run %t 2>&1 | \
+// RUN: FileCheck %s --check-prefix=CRASH
+// RUN: %env_hwasan_opts=malloc_bisect_left=0,malloc_bisect_right=4294967295,malloc_bisect_dump=1 not %run %t 2>&1 | \
+// RUN: FileCheck %s --check-prefixes=CRASH,DUMP
+
+#include <stdlib.h>
+#include <stdio.h>
+#include <sanitizer/hwasan_interface.h>
+
+int main() {
+ __hwasan_enable_allocator_tagging();
+ // DUMP: [alloc] {{.*}} 10{{$}}
+ // DUMP: in main{{.*}}malloc_bisect.c
+ char * volatile p = (char*)malloc(10);
+ // CRASH: HWAddressSanitizer: tag-mismatch on address
+ // CRASH: in main{{.*}}malloc_bisect.c
+ char volatile x = p[16];
+ free(p);
+ __hwasan_disable_allocator_tagging();
+
+ return 0;
+}
