Better support for inlined frames in backtraces

Use the same approach as eu-addr2line to find inline frames.
I.e. use dwarf_getscopes_die instead of manually parsing the
dwarf tree. This allows us to get full inline backtraces for
both, gcc 9 and clang 8. Previously, we only got partial inline
backtraces for gcc, and no inline traces for clang at all.
similar to how eu-addr2line

Before:
        560b37713a54    /usr/include/c++/9.1.0/bits/random.h:139:6
        560b37713a3b    /usr/include/c++/9.1.0/bits/random.h:135:2      std::__detail::_Mod<unsigned long, 2147483647ul, 16807ul, 0ul, true, true>::__calc(unsigned long) cpp-inlining /home/milian/projects/kdab/rnd/hotspot/build-debug/tests/test-clients/cpp-inlining/cpp-inlining
        560b37713a3b    /usr/include/c++/9.1.0/bits/random.h:147:48
        560b37713a3b    /usr/include/c++/9.1.0/bits/random.h:146:7      unsigned long std::__detail::__mod<unsigned long, 2147483647ul, 16807ul, 0ul>(unsigned long) cpp-inlining /home/milian/projects/kdab/rnd/hotspot/build-debug/tests/test-clients/cpp-inlining/cpp-inlining
        560b37713a3b    /usr/include/c++/9.1.0/bits/random.h:349:50
        560b37713a3b    /usr/include/c++/9.1.0/bits/random.h:347:7      std::linear_congruential_engine<unsigned long, 16807ul, 0ul, 2147483647ul>::operator()() cpp-inlining /home/milian/projects/kdab/rnd/hotspot/build-debug/tests/test-clients/cpp-inlining/cpp-inlining
        560b37713a3b    /usr/include/c++/9.1.0/bits/random.tcc:3336:29
        560b37713b80    /usr/include/c++/9.1.0/bits/random.h:1852:2     double std::uniform_real_distribution<double>::operator()<std::linear_congruential_engine<unsigned long, 16807ul, 0ul, 2147483647ul> >(std::linear_congruential_engine<unsigned long, 16807ul, 0ul, 2147483647ul>&) cpp-inlining /home/milian/projects/kdab/rnd/hotspot/build-debug/tests/test-clients/cpp-inlining/cpp-inlining
        560b37713b80    /home/milian/projects/kdab/rnd/hotspot/tests/test-clients/cpp-inlining/main.cpp:39:19
        560b377139a0    /home/milian/projects/kdab/rnd/hotspot/tests/test-clients/cpp-inlining/main.cpp:33:5    main cpp-inlining /home/milian/projects/kdab/rnd/hotspot/build-debug/tests/test-clients/cpp-inlining/cpp-inlining
        7f7a30bb7ee2
        7f7a30bb7df0    __libc_start_main libc-2.29.so /usr/lib/libc-2.29.so
        560b37713cdd
        560b37713cb0    _start cpp-inlining /home/milian/projects/kdab/rnd/hotspot/build-debug/tests/test-clients/cpp-inlining/cpp-inlining

After:
        560b37713a54    /usr/include/c++/9.1.0/bits/random.h:139:6
        560b37713a3b    /usr/include/c++/9.1.0/bits/random.h:135:2      std::__detail::_Mod<unsigned long, 2147483647ul, 16807ul, 0ul, true, true>::__calc(unsigned long) cpp-inlining /home/milian/projects/kdab/rnd/hotspot/build-debug/tests/test-clients/cpp-inlining/cpp-inlining
        560b37713a3b    /usr/include/c++/9.1.0/bits/random.h:147:48
        560b37713a3b    /usr/include/c++/9.1.0/bits/random.h:146:7      unsigned long std::__detail::__mod<unsigned long, 2147483647ul, 16807ul, 0ul>(unsigned long) cpp-inlining /home/milian/projects/kdab/rnd/hotspot/build-debug/tests/test-clients/cpp-inlining/cpp-inlining
        560b37713a3b    /usr/include/c++/9.1.0/bits/random.h:349:50
        560b37713a3b    /usr/include/c++/9.1.0/bits/random.h:347:7      std::linear_congruential_engine<unsigned long, 16807ul, 0ul, 2147483647ul>::operator()() cpp-inlining /home/milian/projects/kdab/rnd/hotspot/build-debug/tests/test-clients/cpp-inlining/cpp-inlining
        560b37713a3b    /usr/include/c++/9.1.0/bits/random.tcc:3336:29
        560b37713000    /usr/include/c++/9.1.0/bits/random.tcc:3318:5   double std::generate_canonical<double, 53ul, std::linear_congruential_engine<unsigned long, 16807ul, 0ul, 2147483647ul> >(std::linear_congruential_engine<unsigned long, 16807ul, 0ul, 2147483647ul>&) cpp-inlining /home/milian/projects/kdab/rnd/hotspot/build-debug/tests/test-clients/cpp-inlining/cpp-inlining
        560b37713000    /usr/include/c++/9.1.0/bits/random.h:181:38
        560b37713000    /usr/include/c++/9.1.0/bits/random.h:177:2      std::__detail::_Adaptor<std::linear_congruential_engine<unsigned long, 16807ul, 0ul, 2147483647ul>, double>::operator()() cpp-inlining /home/milian/projects/kdab/rnd/hotspot/build-debug/tests/test-clients/cpp-inlining/cpp-inlining
        560b37713000    /usr/include/c++/9.1.0/bits/random.h:1862:19
        560b37713000    /usr/include/c++/9.1.0/bits/random.h:1857:2     double std::uniform_real_distribution<double>::operator()<std::linear_congruential_engine<unsigned long, 16807ul, 0ul, 2147483647ul> >(std::linear_congruential_engine<unsigned long, 16807ul, 0ul, 2147483647ul>&, std::uniform_real_distribution<double>::param_type const&) cpp-inlining /home/milian/projects/kdab/rnd/hotspot/build-debug/tests/test-clients/cpp-inlining/cpp-inlining
        560b37713000    /usr/include/c++/9.1.0/bits/random.h:1853:51
        560b37713b80    /usr/include/c++/9.1.0/bits/random.h:1852:2     double std::uniform_real_distribution<double>::operator()<std::linear_congruential_engine<unsigned long, 16807ul, 0ul, 2147483647ul> >(std::linear_congruential_engine<unsigned long, 16807ul, 0ul, 2147483647ul>&) cpp-inlining /home/milian/projects/kdab/rnd/hotspot/build-debug/tests/test-clients/cpp-inlining/cpp-inlining
        560b37713b80    /home/milian/projects/kdab/rnd/hotspot/tests/test-clients/cpp-inlining/main.cpp:39:19
        560b377139a0    /home/milian/projects/kdab/rnd/hotspot/tests/test-clients/cpp-inlining/main.cpp:33:5    main cpp-inlining /home/milian/projects/kdab/rnd/hotspot/build-debug/tests/test-clients/cpp-inlining/cpp-inlining
        7f7a30bb7ee2
        7f7a30bb7df0    __libc_start_main libc-2.29.so /usr/lib/libc-2.29.so
        560b37713cdd
        560b37713cb0    _start cpp-inlining /home/milian/projects/kdab/rnd/hotspot/build-debug/tests/test-clients/cpp-inlining/cpp-inlining

Change-Id: I5d8d5d3f29f659e092c2270c105ef48eae3d99c4
Reviewed-by: Ulf Hermann <ulf.hermann@qt.io>

2 files changed, 32 insertions, 49 deletions

diff --git a/app/perfsymboltable.cpp b/app/perfsymboltable.cpp
index 794bcc7..01f698b 100644
--- a/app/perfsymboltable.cpp
+++ b/app/perfsymboltable.cpp
@@ -381,7 +381,7 @@ int PerfSymbolTable::insertSubprogram(Dwarf_Die *top, Dwarf_Addr entry, qint32 b
 }
 
 int PerfSymbolTable::parseDie(Dwarf_Die *top, qint32 binaryId, qint32 binaryPathId, bool isKernel,
-                              Dwarf_Files *files, Dwarf_Addr entry, const QStack<DieAndLocation> &stack)
+                              Dwarf_Files *files, Dwarf_Addr entry, qint32 parentLocationId)
 {
     int tag = dwarf_tag(top);
     switch (tag) {
@@ -401,13 +401,7 @@ int PerfSymbolTable::parseDie(Dwarf_Die *top, qint32 binaryId, qint32 binaryPath
                 ? static_cast<qint32>(val) : -1;
         location.pid = m_pid;
 
-        auto it = stack.end();
-        --it;
-        while (it != stack.begin()) {
-            location.parentLocationId = (--it)->locationId;
-            if (location.parentLocationId != -1)
-                break;
-        }
+        location.parentLocationId = parentLocationId;
 
         int callLocationId = m_unwind->resolveLocation(location);
         return insertSubprogram(top, entry, binaryId, binaryPathId, callLocationId, isKernel);
@@ -419,42 +413,30 @@ int PerfSymbolTable::parseDie(Dwarf_Die *top, qint32 binaryId, qint32 binaryPath
     }
 }
 
-void PerfSymbolTable::parseDwarf(Dwarf_Die *cudie, Dwarf_Addr bias, qint32 binaryId, qint32 binaryPathId,
-                                 bool isKernel)
+qint32 PerfSymbolTable::parseDwarf(Dwarf_Die *cudie, Dwarf_Die *subroutine, Dwarf_Addr bias, qint32 binaryId,
+                                   qint32 binaryPathId, bool isKernel)
 {
-    // Iterate through all dwarf sections and establish parent/child relations for inline
-    // subroutines. Add all symbols to m_symbols and special frames for start points of inline
-    // instances to m_addresses.
-
-    QStack<DieAndLocation> stack;
-    stack.push_back({*cudie, -1});
+    Dwarf_Die *scopes = nullptr;
+    const auto nscopes = dwarf_getscopes_die(subroutine, &scopes);
 
     Dwarf_Files *files = nullptr;
     dwarf_getsrcfiles(cudie, &files, nullptr);
 
-    while (!stack.isEmpty()) {
-        Dwarf_Die *top = &(stack.last().die);
+    qint32 parentLocationId = -1;
+    for (int i = nscopes - 1; i >= 0; --i) {
+        const auto scope = &scopes[i];
+        Dwarf_Addr scopeAddr = bias;
         Dwarf_Addr entry = 0;
-        if (dwarf_entrypc(top, &entry) == 0 && entry != 0)
-            stack.last().locationId = parseDie(top, binaryId, binaryPathId, isKernel,
-                                               files, entry + bias, stack);
+        if (dwarf_entrypc(scope, &entry) == 0 && entry != 0)
+            scopeAddr += entry;
 
-        Dwarf_Die child;
-        if (dwarf_child(top, &child) == 0) {
-            stack.push_back({child, -1});
-        } else {
-            do {
-                Dwarf_Die sibling;
-                // Mind that stack.last() can change during this loop. So don't use "top" below.
-                const bool hasSibling = (dwarf_siblingof(&(stack.last().die), &sibling) == 0);
-                stack.pop_back();
-                if (hasSibling) {
-                    stack.push_back({sibling, -1});
-                    break;
-                }
-            } while (!stack.isEmpty());
-        }
+        auto locationId = parseDie(scope, binaryId, binaryPathId, isKernel, files, scopeAddr, parentLocationId);
+        if (locationId != -1)
+            parentLocationId = locationId;
     }
+
+    eu_compat_free(scopes);
+    return parentLocationId;
 }
 
 static void reportError(qint32 pid, const PerfElfMap::ElfInfo& info, const char *message)
@@ -864,29 +846,36 @@ int PerfSymbolTable::lookupFrame(Dwarf_Addr ip, bool isKernel,
             functionLocation.address -= off; // in case we don't find anything better
             Dwarf_Die *die = dwfl_module_addrdie(mod, addressLocation.address, &bias);
 
+            Dwarf_Die *subroutine = nullptr;
             Dwarf_Die *scopes = nullptr;
             int nscopes = dwarf_getscopes(die, addressLocation.address - bias, &scopes);
-
             for (int i = 0; i < nscopes; ++i) {
                 Dwarf_Die *scope = &scopes[i];
                 const int tag = dwarf_tag(scope);
                 if (tag == DW_TAG_subprogram || tag == DW_TAG_inlined_subroutine) {
                     Dwarf_Addr entry = 0;
                     dwarf_entrypc(scope, &entry);
+                    symname = dieName(scope); // use name of inlined function as symbol
                     functionLocation.address = entry + bias;
                     functionLocation.file = m_unwind->resolveString(dwarf_decl_file(scope));
                     dwarf_decl_line(scope, &functionLocation.line);
                     dwarf_decl_column(scope, &functionLocation.column);
+
+                    subroutine = scope;
                     break;
                 }
             }
-            eu_compat_free(scopes);
 
+            // check if the inline chain was cached already
             addressLocation.parentLocationId = m_unwind->lookupLocation(functionLocation);
-            if (die && !m_unwind->hasSymbol(addressLocation.parentLocationId))
-                parseDwarf(die, bias, binaryId, binaryPathId, isKernel);
+            // otherwise resolve the inline chain if possible
+            if (subroutine && !m_unwind->hasSymbol(addressLocation.parentLocationId))
+                functionLocation.parentLocationId = parseDwarf(die, subroutine, bias, binaryId, binaryPathId, isKernel);
+            // then resolve and cache the inline chain
             if (addressLocation.parentLocationId == -1)
                 addressLocation.parentLocationId = m_unwind->resolveLocation(functionLocation);
+
+            eu_compat_free(scopes);
         }
         if (!m_unwind->hasSymbol(addressLocation.parentLocationId)) {
             // no sufficient debug information. Use what we already know
diff --git a/app/perfsymboltable.h b/app/perfsymboltable.h
index 0070a16..3fcd155 100644
--- a/app/perfsymboltable.h
+++ b/app/perfsymboltable.h
@@ -48,11 +48,6 @@ public:
         QByteArray name;
     };
 
-    struct DieAndLocation {
-        Dwarf_Die die;
-        qint32 locationId;
-    };
-
     // Announce an mmap. Invalidate the symbol and address cache and clear the dwfl if it overlaps
     // with an existing one.
     void registerElf(const PerfRecordMmap &mmap, const QByteArray &buildId);
@@ -119,14 +114,13 @@ private:
 
     QByteArray symbolFromPerfMap(quint64 ip, GElf_Off *offset) const;
     int parseDie(Dwarf_Die *top, qint32 binaryId, qint32 binaryPathId, bool isKernel,
-                 Dwarf_Files *files, Dwarf_Addr entry, const QStack<DieAndLocation> &stack);
+                 Dwarf_Files *files, Dwarf_Addr entry, qint32 parentLocationId);
     int insertSubprogram(Dwarf_Die *top, Dwarf_Addr entry, qint32 binaryId, qint32 binaryPathId,
                          qint32 inlineParent, bool isKernel);
-    void parseDwarf(Dwarf_Die *cudie, Dwarf_Addr bias, qint32 binaryId, qint32 binaryPathId,
-                    bool isKernel);
+    qint32 parseDwarf(Dwarf_Die *cudie, Dwarf_Die *subroutine, Dwarf_Addr bias, qint32 binaryId,
+                      qint32 binaryPathId, bool isKernel);
 };
 
 QT_BEGIN_NAMESPACE
 Q_DECLARE_TYPEINFO(PerfSymbolTable::PerfMapSymbol, Q_MOVABLE_TYPE);
-Q_DECLARE_TYPEINFO(PerfSymbolTable::DieAndLocation, Q_MOVABLE_TYPE);
 QT_END_NAMESPACE