Index: compiler-rt/trunk/lib/hwasan/hwasan_allocator.cc
===================================================================
--- compiler-rt/trunk/lib/hwasan/hwasan_allocator.cc
+++ compiler-rt/trunk/lib/hwasan/hwasan_allocator.cc
@@ -100,6 +100,9 @@
 static SpinMutex fallback_mutex;
 static atomic_uint8_t hwasan_allocator_tagging_enabled;
 
+static const tag_t kFallbackAllocTag = 0xBB;
+static const tag_t kFallbackFreeTag = 0xBC;
+
 void HwasanAllocatorInit() {
   atomic_store_relaxed(&hwasan_allocator_tagging_enabled,
                        !flags()->disable_allocator_tagging);
@@ -145,10 +148,11 @@
   if (zeroise)
     internal_memset(allocated, 0, size);
 
-  void *user_ptr = (flags()->tag_in_malloc &&
-                    atomic_load_relaxed(&hwasan_allocator_tagging_enabled))
-                       ? (void *)TagMemoryAligned((uptr)allocated, size, 0xBB)
-                       : allocated;
+  void *user_ptr = allocated;
+  if (flags()->tag_in_malloc &&
+      atomic_load_relaxed(&hwasan_allocator_tagging_enabled))
+    user_ptr = (void *)TagMemoryAligned(
+        (uptr)user_ptr, size, t ? t->GenerateRandomTag() : kFallbackAllocTag);
 
   HWASAN_MALLOC_HOOK(user_ptr, size);
   return user_ptr;
@@ -166,10 +170,11 @@
   meta->free_context_id = StackDepotPut(*stack);
   // This memory will not be reused by anyone else, so we are free to keep it
   // poisoned.
+  HwasanThread *t = GetCurrentThread();
   if (flags()->tag_in_free &&
       atomic_load_relaxed(&hwasan_allocator_tagging_enabled))
-    TagMemoryAligned((uptr)p, size, 0xBC);
-  HwasanThread *t = GetCurrentThread();
+    TagMemoryAligned((uptr)p, size,
+                     t ? t->GenerateRandomTag() : kFallbackFreeTag);
   if (t) {
     AllocatorCache *cache = GetAllocatorCache(&t->malloc_storage());
     allocator.Deallocate(cache, p);
@@ -195,8 +200,12 @@
     meta->requested_size = new_size;
     if (!atomic_load_relaxed(&hwasan_allocator_tagging_enabled))
       return user_old_p;
-    if (flags()->retag_in_realloc)
-      return (void *)TagMemoryAligned((uptr)old_p, new_size, 0xCC);
+    if (flags()->retag_in_realloc) {
+      HwasanThread *t = GetCurrentThread();
+      return (void *)TagMemoryAligned(
+          (uptr)old_p, new_size,
+          t ? t->GenerateRandomTag() : kFallbackAllocTag);
+    }
     if (new_size > old_size) {
       tag_t tag = GetTagFromPointer((uptr)user_old_p);
       TagMemoryAligned((uptr)old_p + old_size, new_size - old_size, tag);
Index: compiler-rt/trunk/lib/hwasan/hwasan_thread.h
===================================================================
--- compiler-rt/trunk/lib/hwasan/hwasan_thread.h
+++ compiler-rt/trunk/lib/hwasan/hwasan_thread.h
@@ -52,6 +52,8 @@
 
   HwasanThreadLocalMallocStorage &malloc_storage() { return malloc_storage_; }
 
+  tag_t GenerateRandomTag();
+
   int destructor_iterations_;
 
  private:
@@ -70,6 +72,9 @@
   unsigned in_symbolizer_;
   unsigned in_interceptor_scope_;
 
+  u32 random_state_;
+  u32 random_buffer_;
+
   HwasanThreadLocalMallocStorage malloc_storage_;
 };
 
Index: compiler-rt/trunk/lib/hwasan/hwasan_thread.cc
===================================================================
--- compiler-rt/trunk/lib/hwasan/hwasan_thread.cc
+++ compiler-rt/trunk/lib/hwasan/hwasan_thread.cc
@@ -8,6 +8,19 @@
 
 namespace __hwasan {
 
+static u32 RandomSeed() {
+  u32 seed;
+  do {
+    if (UNLIKELY(!GetRandom(reinterpret_cast<void *>(&seed), sizeof(seed),
+                            /*blocking=*/false))) {
+      seed = static_cast<u32>(
+          (NanoTime() >> 12) ^
+          (reinterpret_cast<uptr>(__builtin_frame_address(0)) >> 4));
+    }
+  } while (!seed);
+  return seed;
+}
+
 HwasanThread *HwasanThread::Create(thread_callback_t start_routine,
                                void *arg) {
   uptr PageSize = GetPageSizeCached();
@@ -16,6 +29,7 @@
   thread->start_routine_ = start_routine;
   thread->arg_ = arg;
   thread->destructor_iterations_ = GetPthreadDestructorIterations();
+  thread->random_state_ = RandomSeed();
 
   return thread;
 }
@@ -72,4 +86,24 @@
   return res;
 }
 
+static u32 xorshift(u32 state) {
+  state ^= state << 13;
+  state ^= state >> 17;
+  state ^= state << 5;
+  return state;
+}
+
+// Generate a (pseudo-)random non-zero tag.
+tag_t HwasanThread::GenerateRandomTag() {
+  tag_t tag;
+  do {
+    if (!random_buffer_)
+      random_buffer_ = random_state_ = xorshift(random_state_);
+    CHECK(random_buffer_);
+    tag = random_buffer_ & 0xFF;
+    random_buffer_ >>= 8;
+  } while (!tag);
+  return tag;
+}
+
 } // namespace __hwasan