PDB parsing produces overlapping inlinees
mstange opened this issue · 8 comments
The Function produced for a procedure in a pdb file can contain inlinees whose (start, size) ranges overlap among sibling inlinees.
I am unsure if this should be considered a bug or if it is the expected behavior.
The information is still correct, it is just making my life a little harder than necessary.
Here's an example from symbolic-testutils/fixtures/windows/crash.pdb:
public: __thiscall std::basic_string<wchar_t,struct std::char_traits<wchar_t>,class std::allocator<wchar_t> >::~basic_string<wchar_t,struct std::char_traits<wchar_t>,class std::allocator<wchar_t> >(void)
0x1120 push esi
0x1121 mov esi, ecx
0x1123 mov ecx, dword [esi+0x14]
0x1126 cmp ecx, 0x8
0x1129 jb loc_401158
0x112b mov eax, dword [esi]
0x112d lea ecx, dword [0x2+ecx*2]
0x1134 cmp ecx, 0x1000
0x113a jb loc_40114e
0x113c mov edx, dword [eax-4]
0x113f add ecx, 0x23
0x1142 sub eax, edx
0x1144 add eax, 0xfffffffc
0x1147 cmp eax, 0x1f
0x114a ja loc_40116d
0x114c mov eax, edx
0x114e push ecx
0x114f push eax
0x1150 call ??3@YAXPAXI@Z
0x1155 add esp, 0x8
0x1158 mov dword [esi+0x10], 0x0
0x115f xor eax, eax
0x1161 mov dword [esi+0x14], 0x7
0x1168 mov word [esi], ax
0x116b pop esi
0x116c ret
0x116d call dword [__imp___invalid_parameter_noinfo_noreturn]
0x1173 int3> 0x1120: std::basic_string<wchar_t,std::char_traits<wchar_t>,std::allocator<wchar_t> >::~basic_string<wchar_t,std::char_traits<wchar_t>,std::allocator<wchar_t> > (0x54)
0x1120: xstring:2424 (c:\program files (x86)\microsoft visual studio\2017\community\vc\tools\msvc\14.13.26128\include)
0x1123: xstring:2425 (c:\program files (x86)\microsoft visual studio\2017\community\vc\tools\msvc\14.13.26128\include)
0x116c: xstring:2426 (c:\program files (x86)\microsoft visual studio\2017\community\vc\tools\msvc\14.13.26128\include)
0x116d: xstring:2425 (c:\program files (x86)\microsoft visual studio\2017\community\vc\tools\msvc\14.13.26128\include)
> 0x1123: std::basic_string<wchar_t,std::char_traits<wchar_t>,std::allocator<wchar_t> >::_Tidy_deallocate (0x50)
0x1123: xstring:3902 (c:\program files (x86)\microsoft visual studio\2017\community\vc\tools\msvc\14.13.26128\include)
0x112b: xstring:3907 (c:\program files (x86)\microsoft visual studio\2017\community\vc\tools\msvc\14.13.26128\include)
0x1158: xstring:3910 (c:\program files (x86)\microsoft visual studio\2017\community\vc\tools\msvc\14.13.26128\include)
0x115f: xstring:3914 (c:\program files (x86)\microsoft visual studio\2017\community\vc\tools\msvc\14.13.26128\include)
0x1161: xstring:3911 (c:\program files (x86)\microsoft visual studio\2017\community\vc\tools\msvc\14.13.26128\include)
0x1168: xstring:3914 (c:\program files (x86)\microsoft visual studio\2017\community\vc\tools\msvc\14.13.26128\include)
0x116d: xstring:3907 (c:\program files (x86)\microsoft visual studio\2017\community\vc\tools\msvc\14.13.26128\include)
> 0x1123: std::_String_val<std::_Simple_types<wchar_t> >::_Large_string_engaged (0x6)
0x1123: xstring:1802 (c:\program files (x86)\microsoft visual studio\2017\community\vc\tools\msvc\14.13.26128\include)
> 0x115f: std::_WChar_traits<wchar_t>::assign (0xc)
0x115f: iosfwd:341 (c:\program files (x86)\microsoft visual studio\2017\community\vc\tools\msvc\14.13.26128\include)
0x1168: iosfwd:341 (c:\program files (x86)\microsoft visual studio\2017\community\vc\tools\msvc\14.13.26128\include)
> 0x112b: std::allocator<wchar_t>::deallocate (0x48)
0x112b: xmemory0:1030 (c:\program files (x86)\microsoft visual studio\2017\community\vc\tools\msvc\14.13.26128\include)
0x116d: xmemory0:1030 (c:\program files (x86)\microsoft visual studio\2017\community\vc\tools\msvc\14.13.26128\include)
[...] v 0x1120 v 0x1123 v 0x112b v 0x1158 v 0x115f v 0x1161 v 0x1168 v 0x116b v 0x116c v 0x116d v 0x1174
|------------------------------------------------------------------------------------------------------------| outer function (~basic_string)
|---------||---------------------------------------------------------------------------||---------||---------| lines
2424 2425 2426 2425
inline level 0:
|-------------------------------------------------------------------------------------------------| inline (_Tidy_deallocate)
|---------||---------||---------||---------||---------||---------| |---------| lines
3902 3907 3910 3914 3911 3914 3907
inline level 1:
|----------| inline (_Large_string_engaged)
|----------| lines
1802
|-------------------------------| inline (assign)
|---------| |---------| lines
341 341
|-------------------------------------------------------------------------------------| inline (deallocate)
|--------| |---------| lines
1030 1030
inline level 2:
[...]
It is these two inlinees which are overlapping:
|-------------------------------| inline (assign)
|---------| |---------| lines
341 341
|-------------------------------------------------------------------------------------| inline (deallocate)
|--------| |---------| lines
1030 1030
But their line ranges are not overlapping, so it is still possible to get the right information, and all consumers within symbolic seem to be able to deal with this representation just fine.
As of #607, the DWARF parsing no longer produces overlapping sibling inlinees, and the inlinees are sorted by start address.
We could make the same change for PDBs. Or we could say "overlaps and non-sortedness are fine, it's really the lines within each inlinee which determine the true address ranges of that inlinee". If we choose the latter, we may also be able to simplify the DWARF parsing by a small amount.
Whichever option we choose, I think we should update the documentation for Function inlinees to set the right expectations.
I'm running into this in the context of mozilla/dump_syms#280: I need to convert a Function into the breakpad-with-inlines representation. In the breakpad-with-inlines representation, each function only emits "lines" for address ranges which are not covered by any of this functions inlinees. For address ranges which are covered by inlinees, the file+line information is stored in that inlinee's "call file" and "call line".
For example, let's look at the outer function in the example above:
v 0x1120 v 0x1123 v 0x112b v 0x1158 v 0x115f v 0x1161 v 0x1168 v 0x116b v 0x116c v 0x116d v 0x1174
|------------------------------------------------------------------------------------------------------------| outer function (~basic_string)
|---------||---------------------------------------------------------------------------||---------||---------| lines
2424 2425 2426 2425
inline level 0:
|-------------------------------------------------------------------------------------------------| inline (_Tidy_deallocate)
|---------||---------||---------||---------||---------||---------| |---------| lines
3902 3907 3910 3914 3911 3914 3907
For the outer function, I need to emit two line records: 0x1120 at line 2424, and 0x116c at line 2426. Additionally, there is one inlinee at level 0, with call line 2425 and the two address ranges 0x1123..0x116b and 0x116d..0x1174.
(Edit: Actually, there's a third line record I need to output: 0x116b at line 2425. The inlinee doesn't cover the trailing bit of that 2425 line record. Ugh.)
How do I filter [(0x1120, 2424), (0x1123, 2425), (0x116c, 2426), (0x116d, 2425)] down to [(0x1120, 2424), (0x116c, 2426)]? I suppose I could put the lines of each function into a BTreeMap<address, line info>, and then recurse into the inlinees, and for each inlinee's line record, erase any line records at that address in all ancestor functions. And I'd need to determine each inlinee's call file / call line first, by looking up the inlinee's address in the caller function's line BTreeMap.
The part about erasing all line records in all ancestor functions for each address that is covered by a descendant line record is what concerns me.
Or I compute a RangeSet of addresses for each function based on the function's lines. Then I subtract the rangesets from all inlinees out, and whatever's left is the list of ranges for which I need to emit lines from this function. And then I iterate over my function's lines, and check if the line's address range has overlap with that difference. If it does, I compute the intersection, and emit one or more line ranges for each range in the intersection.
In contrast, let's say our representation was the following: No holes, no overlap, no out-of-order.
v 0x1120 v 0x1123 v 0x112b v 0x1158 v 0x115f v 0x1161 v 0x1168 v 0x116b v 0x116c v 0x116d v 0x1174
|------------------------------------------------------------------------------------------------------------| outer function (~basic_string)
|---------||---------------------------------------------------------------------------||---------||---------| lines
2424 2425 2426 2425
inline level 0:
|----------------------------------------------------------------| inline (_Tidy_deallocate)
|---------||---------||---------||---------||---------||---------|
3902 3907 3910 3914 3911 3914
|---------| inline (_Tidy_deallocate)
|---------| lines
3907
inline level 1:
|----------| inline (_Large_string_engaged)
|----------| lines
1802
|--------| inline (deallocate)
|--------| lines
1030
|---------| inline (assign)
|---------| lines
341
|---------| inline (assign)
|---------| lines
341
|---------| inline (deallocate)
|---------| lines
1030
inline level 2:
[...]
With this representation, I can iterate over all lines and inlinees in order, at the same time (by using two manually-advanced iterators). If the next element is an inlinee, then the current line is the inlinee's call line. If the next element is a line, then I emit a line record. And sometimes I may need to emit another line record if an inlinee ends before the end of the current line's address range.
And I can trust that each inlinee covers exactly the address range which it says it covers. I don't need to look at the inlinee's lines to find out the actual address ranges.
Just to clarify, is the difference between the two diagrams that in the second one, the _Tidy_deallocate inlinee is split into two inlinees, which fixes the problem of inlinees not being contiguous?
That's right. With the split, each of the inlinees now represents a contiguous address range. This makes it easier to to exclude those ranges from the caller's line ranges.
After thinking about this some more, I'm less convinced now that this change is worth making. The transformation from "unsorted inlinees with holes" into "sorted list of inlinee address ranges" is fairly straightforward and is something I could do in dump_syms. I'll give that a go, maybe it'll look fine.
Doing the de-gappification and sorting inside dump_syms turned out to be fine. I'll close this.
I think we run into a variant of this issue ourselves (internal ref https://github.com/getsentry/team-stacktrace-private/issues/8)
The symcache writer was built with the assumption that a line record of an inlinee also exists as a line record in all of its parents, see this logic:
symbolic/symbolic-symcache/src/writer.rs
Lines 221 to 229 in ab8e248
Essentially the symcache writer works like this:
- The parent fills in all its line infos into the "ranges" structure
- The inlined child fills in its own line infos and assumes that the parent has already written a line info for this "range".
- with this assumption, the child can then just say "I was inlined into this source location of the parent"
Now I think we hit a case where the parent has, for example:
- 0x10 - 0x40: file X.cpp, line 10
And the child has: - 0x10 - 0x20: file Y.cpp, line 3
- 0x20 - 0x30: file Y.cpp, line 4
For the first line record, we can correctly link these up, and end up with:
- 0x10: file Y.cpp, line 3; inlined into X.cpp, line 10
But the second record does not find an existing entry in "ranges" and thus does the wrong thing:
- 0x20: file Y.cpp, line 4
Even worse, the inlinee line record only goes to 0x30, but we don’t work with ranges when writing the symcache, in particular, we don’t split the "parent" range, thus we lose the info that 0x30 - 0x40 should actually be X.cpp, line 10.
So I believe we need to process and sort all these things in the symbolic-debuginfo abstraction. @mstange do you have a suggestion of how to best do this?
That's actually a different issue than what I filed this issue about. The example I gave does not violate the assumption that you describe. So I think it would be better to track this in a new issue, so that we don't get confused.
That said, I've run into the same thing as you describe in pdb-addr2line. Here's the workaround I use there: https://github.com/mstange/pdb-addr2line/blob/0812a738d1315994497752f200974ec61bdd59ea/src/lib.rs#L1307-L1327
I think we were really able to work around this issue in the symcache conversion now, closing this again ;-)