[MemProf] Avoid global lock when updating MIB cache

[tejohnson]

Summary

Previously we used a global Allocator-scope mutex to lock when adding a
deallocation to the MIB cache. This resulted in a lot of contention.
Instead add and use per-set mutexes.

Along with this, we now need to remove the global miss and access count
variables and instead utilize the per-set statistics to report the
overall miss rate.

[snehasish]

LGTM with one minor comment.

compiler-rt/lib/memprof/memprof_allocator.cpp

347

Since you are touching these lines, can you update the format specifiers to match the data types?
Same for the loop below.

It would clean up some of the errors I am seeing with -Wformat - e.g.
warning: format ‘%d’ expects argument of type ‘int’, but argument 3 has type ‘__sanitizer::u64’

[tejohnson]

compiler-rt/lib/memprof/memprof_allocator.cpp

347

Ah, I build with -Wno-format, so was missing these. If it is ok with you, since there are quite a few from various lines when I remove that option, I will commit those fixes as a separate change.

[snehasish]

compiler-rt/lib/memprof/memprof_allocator.cpp

347

A separate cleanup patch with the option removed sounds better. Thanks!

[tejohnson]

compiler-rt/lib/memprof/memprof_allocator.cpp

347

Fix committed in 242524741f3582d93e4fac8052d0bfc40f4c1ac4.

compiler-rt/lib/memprof/memprof_allocator.cpp

void Merge(MemInfoBlock &newMIB) {
 
     num_same_alloc_cpu += alloc_cpu_id == newMIB.alloc_cpu_id;
     num_same_dealloc_cpu += dealloc_cpu_id == newMIB.dealloc_cpu_id;
     alloc_cpu_id = newMIB.alloc_cpu_id;
     dealloc_cpu_id = newMIB.dealloc_cpu_id;
   }
 };
 
-static u32 AccessCount = 0;
-static u32 MissCount = 0;
-
 struct SetEntry {
   SetEntry() : id(0), MIB() {}
   bool Empty() { return id == 0; }
   void Print() {
     CHECK(!Empty());
     MIB.Print(id);
   }
   // The stack id
   u64 id;
   MemInfoBlock MIB;
 };
 
 struct CacheSet {
   enum { kSetSize = 4 };
 
   void PrintAll() {
     for (int i = 0; i < kSetSize; i++) {
       if (Entries[i].Empty())
         continue;
       Entries[i].Print();
     }
   }
   void insertOrMerge(u64 new_id, MemInfoBlock &newMIB) {
+    SpinMutexLock l(&SetMutex);
     AccessCount++;
-    SetAccessCount++;
 
     for (int i = 0; i < kSetSize; i++) {
       auto id = Entries[i].id;
       // Check if this is a hit or an empty entry. Since we always move any
       // filled locations to the front of the array (see below), we don't need
       // to look after finding the first empty entry.
       if (id == new_id || !id) {
         if (id == 0) {
for (int i = 0; i < kSetSize; i++) {
           Entries[i] = tmp;
         }
         return;
       }
     }
 
     // Miss
     MissCount++;
-    SetMissCount++;
 
     // We try to find the entries with the lowest alloc count to be evicted:
     int min_idx = 0;
     u64 min_count = Entries[0].MIB.alloc_count;
     for (int i = 1; i < kSetSize; i++) {
       CHECK(!Entries[i].Empty());
       if (Entries[i].MIB.alloc_count < min_count) {
         min_idx = i;
void insertOrMerge(u64 new_id, MemInfoBlock &newMIB) {
     // Similar to the hit case, put new MIB in first set position.
     if (min_idx != 0)
       Entries[min_idx] = Entries[0];
     Entries[0].id = new_id;
     Entries[0].MIB = newMIB;
   }
 
   void PrintMissRate(int i) {
-    u64 p = SetAccessCount ? SetMissCount * 10000ULL / SetAccessCount : 0;
-    Printf("Set %d miss rate: %d / %d = %5d.%02d%%\n", i, SetMissCount,
-           SetAccessCount, p / 100, p % 100);
+    u64 p = AccessCount ? MissCount * 10000ULL / AccessCount : 0;
+    Printf("Set %d miss rate: %d / %d = %5d.%02d%%\n", i, MissCount,
+           AccessCount, p / 100, p % 100);
   }
 
   SetEntry Entries[kSetSize];
-  u32 SetAccessCount = 0;
-  u32 SetMissCount = 0;
+  u32 AccessCount = 0;
+  u32 MissCount = 0;
+  SpinMutex SetMutex;
 };
 
 struct MemInfoBlockCache {
   MemInfoBlockCache() {
     if (common_flags()->print_module_map)
       DumpProcessMap();
     if (flags()->print_terse)
       MemInfoBlock::printHeader();
void PrintAll() {
     for (int i = 0; i < flags()->mem_info_cache_entries; i++) {
       Sets[i].PrintAll();
     }
   }
 
   void PrintMissRate() {
     if (!flags()->print_mem_info_cache_miss_rate)
       return;
-    u64 p = AccessCount ? MissCount * 10000ULL / AccessCount : 0;
-    Printf("Overall miss rate: %d / %d = %5d.%02d%%\n", MissCount, AccessCount,
-           p / 100, p % 100);
+    u64 MissCountSum = 0;
+    u64 AccessCountSum = 0;
+    for (int i = 0; i < flags()->mem_info_cache_entries; i++) {
+      MissCountSum += Sets[i].MissCount;
+      AccessCountSum += Sets[i].AccessCount;
+    }
+    u64 p = AccessCountSum ? MissCountSum * 10000ULL / AccessCountSum : 0;
+    Printf("Overall miss rate: %d / %d = %5d.%02d%%\n", MissCountSum,
+           AccessCountSum, p / 100, p % 100);
     if (flags()->print_mem_info_cache_miss_rate_details)
       for (int i = 0; i < flags()->mem_info_cache_entries; i++)
         Sets[i].PrintMissRate(i);
   }
 
   CacheSet *Sets;
   // Flag when the Sets have been allocated, in case a deallocation is called
   // very early before the static init of the Allocator and therefore this table
u64 user_requested_size =
         atomic_exchange(&m->user_requested_size, 0, memory_order_acquire);
     if (memprof_inited && memprof_init_done && !destructing &&
         MemInfoBlockTable.Constructed) {
       u64 c = GetShadowCount(p, user_requested_size);
       long curtime = GetTimestamp();
 
       MemInfoBlock newMIB(user_requested_size, c, m->timestamp_ms, curtime,
                           m->cpu_id, GetCpuId());
-      {
-        SpinMutexLock l(&fallback_mutex);
         MemInfoBlockTable.insertOrMerge(m->alloc_context_id, newMIB);
-      }
-    }
 
     MemprofStats &thread_stats = GetCurrentThreadStats();
     thread_stats.frees++;
     thread_stats.freed += user_requested_size;
 
     void *alloc_beg = m->AllocBeg();
     if (alloc_beg != m) {
       // Clear the magic value, as allocator internals may overwrite the