This is an archive of the discontinued LLVM Phabricator instance.

[sanitizer] Switch to StackDepotNode to 64bit hash
ClosedPublic

Authored by vitalybuka on Oct 5 2021, 1:56 PM.

Details

Summary

Now we can avoid scanning the stack on fast path.
The price is the false stack trace with probability of the hash collision.
This increase performance of lsan by 6% and pre-requirement for stack compression.

Depends on D111182.

Diff Detail

Event Timeline

vitalybuka requested review of this revision.Oct 5 2021, 1:56 PM
vitalybuka created this revision.
Herald added a project: Restricted Project. · View Herald TranscriptOct 5 2021, 1:56 PM
Herald added a subscriber: Restricted Project. · View Herald Transcript
vitalybuka edited the summary of this revision. (Show Details)Oct 5 2021, 1:57 PM
vitalybuka added reviewers: morehouse, dvyukov, eugenis.
vitalybuka updated this revision to Diff 377351.Oct 5 2021, 2:02 PM

include tag into hash

vitalybuka updated this revision to Diff 377352.Oct 5 2021, 2:03 PM

fix compilation

This revision is now accepted and ready to land.Oct 5 2021, 2:13 PM
vitalybuka updated this revision to Diff 377419.Oct 5 2021, 8:41 PM

move 64bit field front, for better alignment

dvyukov added inline comments.Oct 5 2021, 11:23 PM
compiler-rt/lib/sanitizer_common/sanitizer_stackdepot.cpp
23

wonder if the header can be compressed back to 3 words
size is pretty small and maybe can be combined with something else

but we could remove id entirely (and simplify code along the way)
the algorithm used by kernel is better in this regard, we make the id an index in a dense allocator:
https://elixir.bootlin.com/linux/v5.15-rc4/source/lib/stackdepot.c#L136
then id does not need to be stored explicitly and can be easily mapped back to the stack in O(1):
https://elixir.bootlin.com/linux/v5.15-rc4/source/lib/stackdepot.c#L231

this would also remove all of StackDepotReverseMap machinery

36

args are now unused and can be removed

vitalybuka added inline comments.Oct 5 2021, 11:55 PM
compiler-rt/lib/sanitizer_common/sanitizer_stackdepot.cpp
23

I am planing to move out size completely and put it with compressed data in "compression" patches.

Thanks, I was thinking about switching to single sequential id and remove map, but didn't realized that we can reuse some info from allocator. I will check these links. Still it's going to be done in separate patches.

36

This interface is used by "origin" depots, which is actually needs just a hash table part. There is some opportunity for refactoring.

dvyukov accepted this revision.Oct 6 2021, 12:02 AM
dvyukov added inline comments.
compiler-rt/lib/sanitizer_common/sanitizer_stackdepot.cpp
23

tsan_dense_alloc.h is almost the allocator we need (maps allocated objects to u32 and back), but it only supports objects of fixed size; while in the kernel stackdepot we allocate variable size objects (due to variable size stack traces)
maybe tsan_dense_alloc.h can be extended to handle such case as well, not sure

This revision was landed with ongoing or failed builds.Oct 6 2021, 10:45 AM
This revision was automatically updated to reflect the committed changes.