[scudo] secondary allocator cache optimal-fit retrieval

[frs513]

Summary

changed cache retrieve algorithm to an "optimal-fit" which immediate
returns blocks that are less than 110% of the requested size. This
reduces memory waste while still allowing for an early return without
traversing the entire array of cached blocks

[cferris]

A minor comment nit.

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

312

I think you lost the small description about how you did experiments to figure out the max allowed waste.

[frs513]

ran git clang-format

[frs513]

added reasoning behind MaxAllowedWastedBytes variable and how I came up with that number

[frs513]

changed MaxAllowedWastedBytes

[cferris]

LGTM, but as with the other, good to wait for Chia-hung to take a look.

[frs513]

remade commit

[frs513]

added type to TempHeaderPos

[frs513]

updating this change to avoid merge conflicts with dependant cl

[Chia-hungDuan]

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

303

I may name this as HeaderPos and rename another as EntryHeaderPos or CachedBlockHeaderPos

306

It seems to me that this value may impact the optimal-parameter as well. Do you know what the range of Diff from your experiments is?

315

Per discussion, how about fragmented?

316

Declare this as constexpr at the prologue of this function and move the above comment there.

[frs513]

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

306

I did not really keep track of that value. Could you explain to me more later how this could affect things?

316

Do you want the entire equation to be a constexpr or just the magic number?

[Chia-hungDuan]

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

306

This puts a limit on the wasted bytes. For example, if the block size is 16K greater than requested size, it'll be skipped.

316

Just the magic number

[frs513]

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

306

Should I get rid of this check? I'm pretty sure all of my 'Diff' calculations will be less than 16K right now because of the check

[frs513]

fixed comments and improved style and variable names

[Chia-hungDuan]

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

313

Maybe you want to update the comment here (not just the 10%) and attach some comment to FragmentedBytesDivisor

[frs513]

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

306

will deal with this in later cl

[frs513]

Moved comments for the FragmentedBytesDivisor

[Chia-hungDuan]

I'm submitting this CL

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

void store(const Options &Options, LargeBlock::Header *H) EXCLUDES(Mutex) {
     if (!EntryCached)
       Entry.MemMap.unmap(Entry.MemMap.getBase(), Entry.MemMap.getCapacity());
   }
 
   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);
+    // 10% of the requested size proved to be the optimal choice for
+    // retrieving cached blocks after testing several options.
+    constexpr u32 FragmentedBytesDivisor = 10;
     bool Found = false;
     CachedBlock Entry;
-    uptr HeaderPos = 0;
+    uptr EntryHeaderPos = 0;
     {
       ScopedLock L(Mutex);
       CallsToRetrieve++;
       if (EntriesCount == 0)
         return false;
+      u32 OptimalFitIndex = 0;
+      uptr MinDiff = UINTPTR_MAX;
       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;
+        const uptr HeaderPos = AllocPos - HeadersSize;
         if (HeaderPos > CommitBase + CommitSize)
           continue;
         if (HeaderPos < CommitBase ||
             AllocPos > CommitBase + PageSize * MaxUnusedCachePages) {
           continue;
         }
         Found = true;
-        Entry = Entries[I];
-        Entries[I].invalidate();
+        const uptr Diff = HeaderPos - CommitBase;
+        // immediately use a cached block if it's size is close enough to the
+        // requested size.
+        const uptr MaxAllowedFragmentedBytes =
+            (CommitBase + CommitSize - HeaderPos) / FragmentedBytesDivisor;
+        if (Diff <= MaxAllowedFragmentedBytes) {
+          OptimalFitIndex = I;
+          EntryHeaderPos = HeaderPos;
+          break;
+        }
+        // keep track of the smallest cached block
+        // that is greater than (AllocSize + HeaderSize)
+        if (Diff > MinDiff)
+          continue;
+        OptimalFitIndex = I;
+        MinDiff = Diff;
+        EntryHeaderPos = HeaderPos;
+      }
+      if (Found) {
+        Entry = Entries[OptimalFitIndex];
+        Entries[OptimalFitIndex].invalidate();
         EntriesCount--;
         SuccessfulRetrieves++;
-        break;
       }
     }
     if (!Found)
       return false;
 
     *H = reinterpret_cast<LargeBlock::Header *>(
-        LargeBlock::addHeaderTag<Config>(HeaderPos));
+        LargeBlock::addHeaderTag<Config>(EntryHeaderPos));
     *Zeroed = Entry.Time == 0;
     if (useMemoryTagging<Config>(Options))
       Entry.MemMap.setMemoryPermission(Entry.CommitBase, Entry.CommitSize, 0);
     uptr NewBlockBegin = reinterpret_cast<uptr>(*H + 1);
     if (useMemoryTagging<Config>(Options)) {
       if (*Zeroed) {
         storeTags(LargeBlock::addHeaderTag<Config>(Entry.CommitBase),
                   NewBlockBegin);