This is an archive of the discontinued LLVM Phabricator instance.

[scudo] secondary allocator cache optimal-fit retrieval
ClosedPublic

Authored by frs513 on Aug 4 2023, 4:13 PM.

Details

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

Diff Detail

Event Timeline

frs513 created this revision.Aug 4 2023, 4:13 PM
Herald added a project: Restricted Project. · View Herald TranscriptAug 4 2023, 4:13 PM
Herald added subscribers: yaneury, Enna1. · View Herald Transcript
frs513 requested review of this revision.Aug 4 2023, 4:13 PM
Herald added a project: Restricted Project. · View Herald TranscriptAug 4 2023, 4:13 PM
Herald added a subscriber: Restricted Project. · View Herald Transcript
cferris requested changes to this revision.Aug 4 2023, 4:49 PM

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.

This revision now requires changes to proceed.Aug 4 2023, 4:49 PM
frs513 updated this revision to Diff 547408.Aug 4 2023, 4:54 PM

ran git clang-format

frs513 updated this revision to Diff 547411.Aug 4 2023, 5:06 PM

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

frs513 marked an inline comment as done.Aug 4 2023, 5:06 PM
frs513 updated this revision to Diff 547418.Aug 4 2023, 5:21 PM

changed MaxAllowedWastedBytes

cferris accepted this revision.Aug 4 2023, 5:36 PM

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

This revision is now accepted and ready to land.Aug 4 2023, 5:36 PM
frs513 updated this revision to Diff 547438.Aug 4 2023, 7:07 PM

remade commit

frs513 updated this revision to Diff 547439.Aug 4 2023, 7:38 PM

added type to TempHeaderPos

frs513 updated this revision to Diff 548007.Aug 7 2023, 5:29 PM

updating this change to avoid merge conflicts with dependant cl

Chia-hungDuan added inline comments.Aug 7 2023, 9:05 PM
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 marked 2 inline comments as done.Aug 8 2023, 11:09 AM
frs513 added inline comments.
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?

frs513 marked 2 inline comments as not done.Aug 8 2023, 11:10 AM
Chia-hungDuan added inline comments.Aug 8 2023, 1:44 PM
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 marked 2 inline comments as done.Aug 8 2023, 1:55 PM
frs513 added inline comments.
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 marked an inline comment as not done.Aug 8 2023, 1:55 PM
frs513 updated this revision to Diff 548370.Aug 8 2023, 3:09 PM

fixed comments and improved style and variable names

Chia-hungDuan added inline comments.Aug 8 2023, 3:13 PM
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 marked 3 inline comments as done.Aug 8 2023, 4:26 PM
frs513 added inline comments.
compiler-rt/lib/scudo/standalone/secondary.h
306

will deal with this in later cl

frs513 updated this revision to Diff 548396.Aug 8 2023, 4:27 PM

Moved comments for the FragmentedBytesDivisor

Chia-hungDuan accepted this revision.Aug 8 2023, 4:35 PM

I'm submitting this CL