[scudo] Fragmentation info secondary cache

[frs513]

Summary

Added a variable that tracks the FragmentedBytes in the secondary cache.
Updates this information after successful retrieves and stores. Dumps
info in getStats().

[Chia-hungDuan]

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

262

I think we may want to track all secondary allocations because we don't know if a returned block is cached before. Then we add the fragmented bytes at every allocation and subtract it at every deallocation

[frs513]

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

262

So I should be doing these calculations in the allocate & deallocate methods instead of retrieve and store?

[Chia-hungDuan]

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

262

Right, so that we won't miss some of them like if the cache is full, you can't store it

[frs513]

moved FragmentedBytes calculation to allocate/deallocate methods

[frs513]

added a "\n" to stats dump for clarity

[frs513]

Stats: MapAllocator: allocated 34 times (2404K), freed 34 times (2404K), remains 0 (0K) max 0M, Fragmented 18014398509481850K
.
.
.
Stats: MapAllocator: allocated 7683 times (1066772K), freed 7683 times (1066772K), remains 0 (0K) max 1M, Fragmented 4081387162245704K

.
.
.
Stats: MapAllocator: allocated 32 times (1180K), freed 32 times (1180K), remains 0 (0K) max 0M, Fragmented 15762598695796610K
.
.
.
These are the values I am getting, which do not make sense, I assume my arithmetic is leading to overflow

[Chia-hungDuan]

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

670–671

I think you also want to account the Fragmented bytes here

[frs513]

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

670–671

I added the calculation here and now I am getting 0K fragmented

[frs513]

added Fragmentation calculation to another place that I had not concidered before

[frs513]

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

702

I was dumping this in the CacheRetrieveStats, but now since I am doing the calculations in the MapAllocator, it is getting dumped here. I am wondering if I should also move the SuccessRate to this getStats()?

[frs513]

LGTM

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

if (CallsToRetrieve != 0) {
                    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);
+                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);
     }
do {
       } else {
         for (u32 I = 0; I < MaxCount; I++) {
           if (Entries[I].isValid())
             continue;
           if (I != 0)
             Entries[I] = Entries[0];
           Entries[0] = Entry;
           EntriesCount++;
           if (OldestTime == 0)
             OldestTime = Entry.Time;
           EntryCached = true;
           break;
         }
       }
     } while (0);
     if (EmptyCache)
       empty();

 
 private:
   typename Config::Secondary::template CacheT<Config> Cache;
 
   mutable HybridMutex Mutex;
   DoublyLinkedList<LargeBlock::Header> InUseBlocks GUARDED_BY(Mutex);
   uptr AllocatedBytes GUARDED_BY(Mutex) = 0;
   uptr FreedBytes GUARDED_BY(Mutex) = 0;
+  uptr FragmentedBytes GUARDED_BY(Mutex) = 0;
   uptr LargestSize GUARDED_BY(Mutex) = 0;
   u32 NumberOfAllocs GUARDED_BY(Mutex) = 0;
   u32 NumberOfFrees GUARDED_BY(Mutex) = 0;
   LocalStats Stats GUARDED_BY(Mutex);
 };
 
 // As with the Primary, the size passed to this function includes any desired
 // alignment, so that the frontend can align the user allocation. The hint
if (Cache.retrieve(Options, Size, Alignment, getHeadersSize(), &H,
       void *Ptr = reinterpret_cast<void *>(PtrInt);
       if (FillContents && !Zeroed)
         memset(Ptr, FillContents == ZeroFill ? 0 : PatternFillByte,
                BlockEnd - PtrInt);
       {
         ScopedLock L(Mutex);
         InUseBlocks.push_back(H);
         AllocatedBytes += H->CommitSize;
+        FragmentedBytes += reinterpret_cast<uptr>(H) - H->CommitBase;
         NumberOfAllocs++;
         Stats.add(StatAllocated, H->CommitSize);
         Stats.add(StatMapped, H->MemMap.getCapacity());
       }
       return Ptr;
     }
   }
 
void *MapAllocator<Config>::allocate(const Options &Options, uptr Size,
   H->CommitBase = CommitBase;
   H->CommitSize = CommitSize;
   H->MemMap = MemMap;
   if (BlockEndPtr)
     *BlockEndPtr = CommitBase + CommitSize;
   {
     ScopedLock L(Mutex);
     InUseBlocks.push_back(H);
     AllocatedBytes += CommitSize;
+    FragmentedBytes += reinterpret_cast<uptr>(H) - H->CommitBase;
     if (LargestSize < CommitSize)
       LargestSize = CommitSize;
     NumberOfAllocs++;
     Stats.add(StatAllocated, CommitSize);
     Stats.add(StatMapped, H->MemMap.getCapacity());
   }
   return reinterpret_cast<void *>(HeaderPos + LargeBlock::getHeaderSize());
 }
 
 template <typename Config>
 void MapAllocator<Config>::deallocate(const Options &Options, void *Ptr)
     EXCLUDES(Mutex) {
   LargeBlock::Header *H = LargeBlock::getHeader<Config>(Ptr);
   const uptr CommitSize = H->CommitSize;
   {
     ScopedLock L(Mutex);
     InUseBlocks.remove(H);
     FreedBytes += CommitSize;
+    FragmentedBytes -= reinterpret_cast<uptr>(H) - H->CommitBase;
     NumberOfFrees++;
     Stats.sub(StatAllocated, CommitSize);
     Stats.sub(StatMapped, H->MemMap.getCapacity());
   }
   Cache.store(Options, H);
 }
 
 template <typename Config>
 void MapAllocator<Config>::getStats(ScopedString *Str) EXCLUDES(Mutex) {
   ScopedLock L(Mutex);
   Str->append("Stats: MapAllocator: allocated %u times (%zuK), freed %u times "
-              "(%zuK), remains %u (%zuK) max %zuM\n",
+              "(%zuK), remains %u (%zuK) max %zuM, Fragmented %zuK\n",
               NumberOfAllocs, AllocatedBytes >> 10, NumberOfFrees,
               FreedBytes >> 10, NumberOfAllocs - NumberOfFrees,
-              (AllocatedBytes - FreedBytes) >> 10, LargestSize >> 20);
+              (AllocatedBytes - FreedBytes) >> 10, LargestSize >> 20,
+              FragmentedBytes >> 10);
   Cache.getStats(Str);
 }
 
 } // namespace scudo
 
 #endif // SCUDO_SECONDARY_H_