Extremely slow demangling of malformed symbol using excessive memory

[5225225]

Test case:

fn main() {
    symbolic::demangle::demangle("_ZUlzjjlZZL1zStUlSt7j_Z3kjIIjIjL1vfIIEEEjzjjfjzSt7j_Z3kjIIjfjzL4t3kjIIjfjtUlSt7j_Z3kjIIjIjL1vfIIEEEjzjjfjzSt7j_Z3kjIIjfjzL4t3kjIIjfjzL4t7IjIjjzjjzSt7j_Z3kjIIjfjzStfjzSt7j_ZA3kjIIjIjL1vfIIEEEjzjjfjzSt7j_Z3kjIIjIjL1vfIIEEEjzjjfjzSt7j_Z3kjIIjfjzL4t3kjIIjzL4t7IjIjjzjjzSt7j_Z3kjIIjfjzStfjzSt7j_ZA3kjIIjIjL1vfIIEEEjzjjfjzSt7j_Z3kjIIjIjL1vfIIEEEjzjjfjzSt7j_Z3kjIIjfjzL4t3kjIIjfjzL4t7IjIjL1vfIIEEEjzjjSI");
}

This is probably a cpp_demangle issue, but I can't reproduce this there. At least, that's where the stack trace led.

When fuzzing, this hits a memory limit and then stops. When running normally, it does complete successfully, but uses a few gigabytes of RAM on the way, and I assume it can be easily crafted to OOM any normal system, though I haven't tried it.

[Swatinem]

Indeed, this is not an issue upstream. I suspect because upstream has some tighter limits around recursion (both parsing as well as pretty printing). We had to increase those limits to support more complex (but still valid) mangled symbols.

As you say that it blows up memory usage, I suspect its rather a matter of either adding a potentially huge amount of substitutions, or blowing past some limit when pretty printing.
Probably the latter, which I think we can work around by just bounding the output string.

[Swatinem]

Interesting. The problem does not seem to be the pretty printing, but rather some part of the parsing. Even when I reset the recursion depth back to the default of cpp_demangle, the tests runs for ~15 seconds on my system and uses a ton of memory, whereas the upstream test I added in gimli-rs/cpp_demangle#236 runs essentially instantly.

So this does need some more investigation. While #481 does not fix this particular issue, IMO it is still worth merging and bounding the length of demangled symbols.

[Swatinem]

Looking at this again after a while and running this in a profiler…
It eventually finishes after ~18s on my hardware. Not sure about peak memory usage though.
I filed gimli-rs/cpp_demangle#277 as the profile revealed that 14% of the runtime is spent freeing the SubstitutionTable. We should definitely bound that somehow to bail earlier in that case.

In general, I recently added an LRU cache for the demangling that we do in symbolicator: getsentry/symbolicator#1124
This should hopefully reduce time and memory spent in average on demangling.

[khuey]

cpp_demangle 0.4.1 has been released and contains a fix for this.