This is an archive of the discontinued LLVM Phabricator instance.

[GWP-ASan] Implement stack frame compression.
ClosedPublic

Authored by hctim on Aug 13 2019, 5:14 PM.

Details

Summary

This patch introduces stack frame compression to GWP-ASan. Each stack frame is
variable-length integer encoded as the difference between frame[i] and
frame[i - 1]. Furthermore, we use zig-zag encoding on the difference to ensure
that negative differences are also encoded into a relatively small number of
bytes.

Examples of what the compression looks like can be seen in
gwp_asan/tests/compression.cpp.

This compression can reduce the memory consumption cost of stack traces by
~50%.

Diff Detail

Repository
rL LLVM

Event Timeline

hctim created this revision.Aug 13 2019, 5:14 PM
Herald added projects: Restricted Project, Restricted Project. · View Herald TranscriptAug 13 2019, 5:14 PM
Herald added subscribers: llvm-commits, Restricted Project, mgorny. · View Herald Transcript
compiler-rt/lib/gwp_asan/guarded_pool_allocator.cpp
78 ↗(On Diff #214990)

Use a VLA instead of allocas, here and below.

compiler-rt/lib/gwp_asan/options.inc
28 ↗(On Diff #214990)

Why make this an option? I don't see why users would need to tune it, I'd set it to something reasonable (64?) and just leave it as a constant.

compiler-rt/lib/gwp_asan/stack_trace_compressor.cpp
10 ↗(On Diff #214990)

Most of these implementations vary from the ones in Chrome, I'd consider just using the same ones (modulo style differences) for consistency.

compiler-rt/lib/gwp_asan/stack_trace_compressor.h
9 ↗(On Diff #214990)

COMPRESSION -> COMPRESSOR

hctim updated this revision to Diff 215445.Aug 15 2019, 11:05 AM
hctim marked 6 inline comments as done.
  • Updated with Vlad's comments.
compiler-rt/lib/gwp_asan/guarded_pool_allocator.cpp
78 ↗(On Diff #214990)

Unfortunately VLA with non-constexpr size is C++14 only, and IMHO adding explicit C++14 requirements in the CMake file is more ugly than just using alloca here. LMK if you're really keen on a different strategy.

compiler-rt/lib/gwp_asan/options.inc
28 ↗(On Diff #214990)

Agreed that runtime users shouldn't generally need to tune this, but this is more for the supporting allocator to tune. I'd expect that bionic on Android has vastly different requirements for scudo on fuchsia for example, and this allows them to tune it in the supporting allocator. Scudo currently exposes this to the user (as they use optional/options_parser.cpp from sanitizer-common to enumaret the options), but allocators don't have to expose this option to the user.

compiler-rt/lib/gwp_asan/stack_trace_compressor.cpp
10 ↗(On Diff #214990)

I've done this and updated the tests. Original code didn't zigzag encode the first pointer, only the subsequent diffs.

compiler-rt/lib/gwp_asan/options.inc
28 ↗(On Diff #214990)

I don't understand how the bionic/scudo examples have different requirements. Why would an embedding allocator need to tune this? The actual amount of space (and hence the approximate number of frames) is already constant, all they can adjust is collecting fewer frames.

hctim marked an inline comment as done.Aug 15 2019, 12:38 PM
hctim added inline comments.
compiler-rt/lib/gwp_asan/options.inc
28 ↗(On Diff #214990)

That's a good point.

Maybe they should also be able to control the number of storage bytes as well?

compiler-rt/lib/gwp_asan/options.inc
28 ↗(On Diff #214990)

Maybe in the future if we implement MESH and allocations pages don't dominate memory consumption, as it stands now the stack traces are a small part of the memory consumption so I would just leave it constant until a need arises. (This also has the side benefit of being able to replace the allocas with fixed-size arrays.)

hctim updated this revision to Diff 215461.Aug 15 2019, 1:20 PM
hctim marked 2 inline comments as done.
  • Removed ability to set trace length.
compiler-rt/lib/gwp_asan/options.inc
28 ↗(On Diff #214990)

Ack. Have gone ahead and done this.

vlad.tsyrklevich accepted this revision.Aug 15 2019, 1:27 PM
This revision is now accepted and ready to land.Aug 15 2019, 1:27 PM
This revision was automatically updated to reflect the committed changes.

Hi. We believe this patch is causing a CMake error for out toolchian build:

-- Compiler-RT supported architectures: i386
CMake Error at /b/s/w/ir/k/llvm-project/compiler-rt/lib/gwp_asan/CMakeLists.txt:111 (target_link_options):
  Unknown CMake command "target_link_options".

Could you look into this? Thanks.

hctim added a comment.Aug 15 2019, 4:03 PM

Hi. We believe this patch is causing a CMake error for out toolchian build:

-- Compiler-RT supported architectures: i386
CMake Error at /b/s/w/ir/k/llvm-project/compiler-rt/lib/gwp_asan/CMakeLists.txt:111 (target_link_options):
  Unknown CMake command "target_link_options".

Could you look into this? Thanks.

Hey Leonard, that should have been fixed in rL369051. Can you apply that patch and let me know?

Hi. We believe this patch is causing a CMake error for out toolchian build:

-- Compiler-RT supported architectures: i386
CMake Error at /b/s/w/ir/k/llvm-project/compiler-rt/lib/gwp_asan/CMakeLists.txt:111 (target_link_options):
  Unknown CMake command "target_link_options".

Could you look into this? Thanks.

Hey Leonard, that should have been fixed in rL369051. Can you apply that patch and let me know?

Looks like it was applied for us, but we're still seeing the same error.

Let me know if there's anything that you need from me to help diagnose this.

hctim added a comment.Aug 15 2019, 4:28 PM

Looks like rL369051 was accidentally reverted by rL369055. Have fixed it in rL369067.

This build is on r369069 and still has the problem:
http://lab.llvm.org:8011/builders/sanitizer-x86_64-linux-android/builds/23577

[2195/2261] Performing build step for 'compiler-rt'
[0/1] Re-running CMake...

  • Compiler-RT supported architectures: x86_64
  • Builtin supported architectures: x86_64

CMake Error at lib/gwp_asan/CMakeLists.txt:104 (add_llvm_executable):

Unknown CMake command "add_llvm_executable".
hctim added a comment.Aug 15 2019, 6:35 PM

Commit is still causing some build issues. I'll take a look shortly and rollback if necessary.

This comment was removed by aheejin.

I posted a bug report but it turned out to be a bug with -D_GLIBCXX_DEBUG. Sorry, please ignore my previous comment.