[scudo] Dump MapAllocatorCache::retrieve() data

[frs513]

Summary

Keeps track of CallsToRetrieve, how many SuccessfulRetrieves, and
total WastedBytes from cached block allocations. Dumps this data in the
MapAllocatorCache::getStats() function

[cferris]

Small question.

compiler-rt/lib/scudo/standalone/secondary.h

437

Looks like an extra line snuck in here.

Did you run clang format on this? I don't know if it would have removed this line.

[frs513]

ran git clang-format

[cferris]

LGTM, but give Chia-hung a chance to comment too.

[frs513]

compiler-rt/lib/scudo/standalone/secondary.h

437

I just re-uploaded after running clang format

[frs513]

added check for dividing by zero case

[cferris]

Yeah, I should have checked for a divide by zero. Unfortunately, on arm that doesn't actually crash.

[Chia-hungDuan]

compiler-rt/lib/scudo/standalone/secondary.h

170

How about adding Cache before this? To make the info down below more clear

172

As discussed, I think the occurrence is useful as well, how about let's do it like

64 / 128 (50%)

172

I'm wondering what the value will hint us. It seems to me the accumulated value may give limited information and may be misleading. For example, does higher wasted bytes indicate bad cache strategy? Not exactly, if it always maintains good SuccessfulRetrieves, then that may have less impact.

Don't get me wrong, we still want to review that value when we are tuning the cache algorithm but in terms of general stats, we may want to provide some information which are less ambiguous.

Therefore, I may suggest removing the WastedBytes

[frs513]

compiler-rt/lib/scudo/standalone/secondary.h

172

I am currently outputting the fractional and percent values for the Success Rate.

172

For WastedBytes would it be a good idea to update that value when we store a cached block as well? or just remove it for now since it is ambiuous?

[Chia-hungDuan]

compiler-rt/lib/scudo/standalone/secondary.h

172

Oops, my bad! You're doing what I was suggesting. Ignore this comment :)

172

I may just remove it or let's discuss what you have in mind offline before making the decision

[frs513]

got rid of WastedBytes tracking, will add in a seperate cl

[Chia-hungDuan]

Per discussion, the *WastedBytes* will be presented in a different way which tells how many bytes are unused in secondary blocks. @frs513 will do it in a separate CL

I will merge this change

compiler-rt/lib/scudo/standalone/secondary.h

 };
 
 template <typename Config> class MapAllocatorCache {
 public:
   using CacheConfig = typename Config::Secondary::Cache;
 
   void getStats(ScopedString *Str) {
     ScopedLock L(Mutex);
+    u32 Integral = 0;
+    u32 Fractional = 0;
+    if (CallsToRetrieve != 0) {
+      Integral = SuccessfulRetrieves * 100 / CallsToRetrieve;
+      Fractional = (((SuccessfulRetrieves * 100) % CallsToRetrieve) * 100 +
+                    CallsToRetrieve / 2) /
+                   CallsToRetrieve;
+    }
     Str->append("Stats: MapAllocatorCache: EntriesCount: %d, "
                 "MaxEntriesCount: %u, MaxEntrySize: %zu\n",
                 EntriesCount, atomic_load_relaxed(&MaxEntriesCount),
                 atomic_load_relaxed(&MaxEntrySize));
+    Str->append("Stats: CacheRetrievalStats: SuccessRate: %u/%u "
+                "(%u.%02u%%)\n",
+                SuccessfulRetrieves, CallsToRetrieve,
+                Integral, Fractional);
     for (CachedBlock Entry : Entries) {
       if (!Entry.isValid())
         continue;
       Str->append("StartBlockAddress: 0x%zx, EndBlockAddress: 0x%zx, "
                   "BlockSize: %zu\n",
                   Entry.CommitBase, Entry.CommitBase + Entry.CommitSize,
                   Entry.CommitSize);
     }
bool retrieve(Options Options, uptr Size, uptr Alignment, uptr HeadersSize,
                 LargeBlock::Header **H, bool *Zeroed) EXCLUDES(Mutex) {
     const uptr PageSize = getPageSizeCached();
     const u32 MaxCount = atomic_load_relaxed(&MaxEntriesCount);
     bool Found = false;
     CachedBlock Entry;
     uptr HeaderPos = 0;
     {
       ScopedLock L(Mutex);
+      CallsToRetrieve++;
       if (EntriesCount == 0)
         return false;
       for (u32 I = 0; I < MaxCount; I++) {
         if (!Entries[I].isValid())
           continue;
         const uptr CommitBase = Entries[I].CommitBase;
         const uptr CommitSize = Entries[I].CommitSize;
         const uptr AllocPos =
             roundDown(CommitBase + CommitSize - Size, Alignment);
         HeaderPos = AllocPos - HeadersSize;
         if (HeaderPos > CommitBase + CommitSize)
           continue;
         if (HeaderPos < CommitBase ||
             AllocPos > CommitBase + PageSize * MaxUnusedCachePages) {
           continue;
         }
         Found = true;
         Entry = Entries[I];
         Entries[I].invalidate();
         EntriesCount--;
+        SuccessfulRetrieves++;
         break;
       }
     }
     if (!Found)
       return false;
 
     *H = reinterpret_cast<LargeBlock::Header *>(
         LargeBlock::addHeaderTag<Config>(HeaderPos));
if (!EntriesCount || OldestTime == 0 || OldestTime > Time)
       return;
     OldestTime = 0;
     for (uptr I = 0; I < CacheConfig::QuarantineSize; I++)
       releaseIfOlderThan(Quarantine[I], Time);
     for (uptr I = 0; I < CacheConfig::EntriesArraySize; I++)
       releaseIfOlderThan(Entries[I], Time);
   }
 
   HybridMutex Mutex;
   u32 EntriesCount GUARDED_BY(Mutex) = 0;
   u32 QuarantinePos GUARDED_BY(Mutex) = 0;
   atomic_u32 MaxEntriesCount = {};
   atomic_uptr MaxEntrySize = {};
   u64 OldestTime GUARDED_BY(Mutex) = 0;
   u32 IsFullEvents GUARDED_BY(Mutex) = 0;
   atomic_s32 ReleaseToOsIntervalMs = {};
+  u32 CallsToRetrieve GUARDED_BY(Mutex) = 0;
+  u32 SuccessfulRetrieves GUARDED_BY(Mutex) = 0;
 
   CachedBlock Entries[CacheConfig::EntriesArraySize] GUARDED_BY(Mutex) = {};
   NonZeroLengthArray<CachedBlock, CacheConfig::QuarantineSize>
       Quarantine GUARDED_BY(Mutex) = {};
 };
 
 template <typename Config> class MapAllocator {
 public: