Reduce drsyms address lookups by storing suppression-matched callstack prefixes or lazy symbolization

_From [rnk@google.com](https://code.google.com/u/rnk@google.com/) on May 07, 2012 10:31:45_

Address to symbol+line lookups can take a long time, and they seem to be cached forever by dbghelp ( issue #792 ), leading to increased memory usage over time.

Currently, when generating a report, we take the full callstack and look it up in our error table, which is a plain hashtable and does not do any prefix matching. Then we add it to the table, regardless of whether the error is reported or suppressed. If we did not find the callstack, then we symbolize it and compare it against our suppressions.

For errors that occur in frequently called leaf functions, such as in issue #337 , there can be many unique callstacks that reach the same error report, such as every call to malloc. However, there are only ~4 PCs that will actually generate the report, and we only need to match symbolize two frames before we decide to suppress the error.

There are two ways I can think of to address this problem:
1. Lazy symbolization. The major catch here is that we match each stack against many suppressions, and it would be inefficient to attempt matching each stack prefix against all the suppressions and stop on the first match. We could attempt to perform some kind of breadth first matching against all the suppressions in lock step, but that would be a big change. Alternatively we could try some hacks like sorting the suppressions in order of ascending length and matching the module before looking at the function. This would probably work for our issue #337 suppression.
2. Prefix matching. In this solution, we'd save the prefix of the stack that ultimately matched a suppression, and store it in some kind of prefix-matching data structure. One nice thing here is that, if we're using a trie, we can do the lookup as we unwind the stack, and stop once we hit the end of a suppressed stack prefix. Tries are also slightly more memory efficient if we have multiple stacks with the same prefix.

If malloc replacement comes along quickly, then we might not need this for the low fragmentation heap suppression ( issue #337 ), because we won't hit that uninit anymore.

_Original issue: http://code.google.com/p/drmemory/issues/detail?id=884_