google / syzygy

Syzygy Transformation Toolchain
Apache License 2.0
355 stars 59 forks source link

Invert how relative stack IDs are calculated and stored. #12

Closed chhamilton closed 8 years ago

chhamilton commented 9 years ago

Relative stack IDs are expensive to compute, but allow a stack ID to be computed that is persistent across runs of an instrumented binary (abstracts away base addresses).

Currently, we compute the relative stack ID and explicitly store it in the registry. During the next run we need to explicitly calculate relative stack IDs for each stack in order to see if this matches.

A better way would be to store sufficient information in the registry to directly calculate a corresponding absolute stack ID using current module load addresses. Since modules can load/unload at runtime, and some modules used in some stacks may not always be in memory, this will require a persistent module load observer mechanism that updates an in-memory set of stack IDs that can be matched against.

chhamilton commented 9 years ago

Turns out that this isn't going to work either. The problem is with generated frames that don't lie within any module. They will always make a random contribution to a stack-trace ID, which can only be filtered out by actually checking which frames are in modules (expensive to do, and the reason why relative stack IDs are expensive to calculate).

We have decided to stick with storing relative stack IDs in the registry, and to make a class that observes both the StackCaptureCache and the modules, computing relative stack IDs of stacks at most once each as they enter a stack-capture cache, and only when pending relative stack IDs haven't been matched.

In the usual case the overhead will be nil. While actively matching a non-empty list of relative stack IDs the cost will be to calculate a single relative stack ID per stack ID committed to the stack cache.

chhamilton commented 8 years ago

This was addressed indirectly in the following CLs:

https://github.com/google/syzygy/commit/72cf729374d6f746de31d1a5d404ff1c82d00b10 https://github.com/google/syzygy/commit/84fc538f381d9f02aeadbd75fe582050b63222f7 https://github.com/google/syzygy/commit/b16783c81c2c38bc61c9fe309b0a9e32fc7af398

Closing.