[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

309

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

299–300

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

303

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?

312

Per discussion, how about fragmented?

313

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

[frs513]

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

303

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

313

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

[Chia-hungDuan]

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

303

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

313

Just the magic number

[frs513]

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

303

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

310

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

303

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

bool retrieve(Options Options, uptr Size, uptr Alignment, uptr HeadersSize,
     bool Found = false;
     CachedBlock Entry;
     uptr HeaderPos = 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;
-        if (HeaderPos > CommitBase + CommitSize)
+        const TempHeaderPos = AllocPos - HeadersSize;
+        if (TempHeaderPos > CommitBase + CommitSize)
           continue;
-        if (HeaderPos < CommitBase ||
+        if (TempHeaderPos < CommitBase ||
             AllocPos > CommitBase + PageSize * MaxUnusedCachePages) {
           continue;
         }
         Found = true;
-        Entry = Entries[I];
-        Entries[I].invalidate();
+        const uptr Diff = TempHeaderPos - CommitBase;
+        // immediately use a cached block if it's size is close enough to the
+        // requested size.
+        // 10% of the requested size proved to be the optimal choice for
+        // retrieving cached blocks after testing several options.
+        const uptr MaxAllowedWastedBytes =
+            (CommitBase + CommitSize - TempHeaderPos) / 10;
+        if (Diff <= MaxAllowedWastedBytes) {
+          OptimalFitIndex = I;
+          HeaderPos = TempHeaderPos;
+          break;
+        }
+        // keep track of the smallest cached block
+        // that is greater than (AllocSize + HeaderSize)
+        if (Diff > MinDiff)
+          continue;
+        OptimalFitIndex = I;
+        MinDiff = Diff;
+        HeaderPos = TempHeaderPos;
+      }
+      if (Found) {
+        Entry = Entries[OptimalFitIndex];
+        Entries[OptimalFitIndex].invalidate();
         EntriesCount--;
         SuccessfulRetrieves++;
         WastedBytes += HeaderPos - Entry.CommitBase;
-        break;
       }
     }
     if (!Found)
       return false;
 
     *H = reinterpret_cast<LargeBlock::Header *>(
         LargeBlock::addHeaderTag<Config>(HeaderPos));
     *Zeroed = Entry.Time == 0;