Refactor PerfElfMap to make it easier to change its internals

Instead of leaking the implementation details such as the QMap
iterators in the API, always return an ElfInfo struct. This
requires us to add the address to the ElfInfo, essentially duplicating
the data that is already used for the QMap key. But this only
marginally increases memory consumption, and does not decrease
performance significantly. Also, future commits to improve the
performance will probably require this anyways.

The code in the symbol table that so far relied on accessing the
mapping internals directly via the iterators is moved into the elfmap
directly. This also allows us to test this part of the code, and
enables us to hide the internals. One exception is the iteration
over all elf infos, which is required to guess the target
architecture. This is still possible, but now uses a simpler foreach
loop over all elf infos, which also makes it possible to change the
underlying data type seamlessly in the future.

To simplify the testing process, ElfInfo also gets a proper
QDebug streaming operator as well as a QTest::toString overload.
The test is updated accordingly, to leverage this new API.

Furthermore, the testing code is simplified by removing the
boolean found parameter in the ElfInfo ctor. Instead, it is now
initialized by calling `file.isFile()` internally.

To show that the performance impact of this change is negleglible,
please compare the following benchmark results to those of the
previous two commits:

PASS   : TestElfMap::benchRegisterElfDisjunct(10)
RESULT : TestElfMap::benchRegisterElfDisjunct():"10":
     0.0017 msecs per iteration (total: 58, iterations: 32768)
PASS   : TestElfMap::benchRegisterElfDisjunct(100)
RESULT : TestElfMap::benchRegisterElfDisjunct():"100":
     0.037 msecs per iteration (total: 77, iterations: 2048)
PASS   : TestElfMap::benchRegisterElfDisjunct(1000)
RESULT : TestElfMap::benchRegisterElfDisjunct():"1000":
     3.8 msecs per iteration (total: 61, iterations: 16)
PASS   : TestElfMap::benchRegisterElfDisjunct(2000)
RESULT : TestElfMap::benchRegisterElfDisjunct():"2000":
     21 msecs per iteration (total: 85, iterations: 4)
PASS   : TestElfMap::benchRegisterElfOverlapping(10)
RESULT : TestElfMap::benchRegisterElfOverlapping():"10":
     0.0040 msecs per iteration (total: 66, iterations: 16384)
PASS   : TestElfMap::benchRegisterElfOverlapping(100)
RESULT : TestElfMap::benchRegisterElfOverlapping():"100":
     0.086 msecs per iteration (total: 89, iterations: 1024)
PASS   : TestElfMap::benchRegisterElfOverlapping(1000)
RESULT : TestElfMap::benchRegisterElfOverlapping():"1000":
     9.7 msecs per iteration (total: 78, iterations: 8)
PASS   : TestElfMap::benchRegisterElfOverlapping(2000)
RESULT : TestElfMap::benchRegisterElfOverlapping():"2000":
     35.2 msecs per iteration (total: 141, iterations: 4)
PASS   : TestElfMap::benchRegisterElfExpanding(10)
RESULT : TestElfMap::benchRegisterElfExpanding():"10":
     0.0019 msecs per iteration (total: 63, iterations: 32768)
PASS   : TestElfMap::benchRegisterElfExpanding(100)
RESULT : TestElfMap::benchRegisterElfExpanding():"100":
     0.043 msecs per iteration (total: 90, iterations: 2048)
PASS   : TestElfMap::benchRegisterElfExpanding(1000)
RESULT : TestElfMap::benchRegisterElfExpanding():"1000":
     4.6 msecs per iteration (total: 74, iterations: 16)
PASS   : TestElfMap::benchRegisterElfExpanding(2000)
RESULT : TestElfMap::benchRegisterElfExpanding():"2000":
     22 msecs per iteration (total: 91, iterations: 4)
PASS   : TestElfMap::benchFindElfDisjunct(10)
RESULT : TestElfMap::benchFindElfDisjunct():"10":
     0.0029 msecs per iteration (total: 98, iterations: 32768)
PASS   : TestElfMap::benchFindElfDisjunct(100)
RESULT : TestElfMap::benchFindElfDisjunct():"100":
     0.031 msecs per iteration (total: 65, iterations: 2048)
PASS   : TestElfMap::benchFindElfDisjunct(1000)
RESULT : TestElfMap::benchFindElfDisjunct():"1000":
     0.40 msecs per iteration (total: 52, iterations: 128)
PASS   : TestElfMap::benchFindElfDisjunct(2000)
RESULT : TestElfMap::benchFindElfDisjunct():"2000":
     0.85 msecs per iteration (total: 55, iterations: 64)
PASS   : TestElfMap::benchFindElfOverlapping(10)
RESULT : TestElfMap::benchFindElfOverlapping():"10":
     0.0032 msecs per iteration (total: 53, iterations: 16384)
PASS   : TestElfMap::benchFindElfOverlapping(100)
RESULT : TestElfMap::benchFindElfOverlapping():"100":
     0.041 msecs per iteration (total: 85, iterations: 2048)
PASS   : TestElfMap::benchFindElfOverlapping(1000)
RESULT : TestElfMap::benchFindElfOverlapping():"1000":
     0.48 msecs per iteration (total: 62, iterations: 128)
PASS   : TestElfMap::benchFindElfOverlapping(2000)
RESULT : TestElfMap::benchFindElfOverlapping():"2000":
     1.0 msecs per iteration (total: 65, iterations: 64)
PASS   : TestElfMap::benchFindElfExpanding(10)
RESULT : TestElfMap::benchFindElfExpanding():"10":
     0.0060 msecs per iteration (total: 99, iterations: 16384)
PASS   : TestElfMap::benchFindElfExpanding(100)
RESULT : TestElfMap::benchFindElfExpanding():"100":
     0.67 msecs per iteration (total: 87, iterations: 128)
PASS   : TestElfMap::benchFindElfExpanding(1000)
RESULT : TestElfMap::benchFindElfExpanding():"1000":
     120 msecs per iteration (total: 120, iterations: 1)
PASS   : TestElfMap::benchFindElfExpanding(2000)
RESULT : TestElfMap::benchFindElfExpanding():"2000":
     696 msecs per iteration (total: 696, iterations: 1)

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

1 files changed, 99 insertions, 84 deletions

diff --git a/tests/auto/elfmap/tst_elfmap.cpp b/tests/auto/elfmap/tst_elfmap.cpp
index f92b303..68e0c5a 100644
--- a/tests/auto/elfmap/tst_elfmap.cpp
+++ b/tests/auto/elfmap/tst_elfmap.cpp
@@ -24,49 +24,69 @@
 
 #include "perfelfmap.h"
 
+namespace {
+bool registerElf(PerfElfMap *map, const PerfElfMap::ElfInfo &info)
+{
+    return map->registerElf(info.addr, info.length, info.pgoff, info.timeAdded,
+                            info.file);
+}
+}
+
+namespace QTest {
+template<>
+char *toString(const PerfElfMap::ElfInfo &info)
+{
+    QString string;
+    QDebug stream(&string);
+    stream << info;
+    return qstrdup(qPrintable(string));
+}
+}
+
 class TestElfMap : public QObject
 {
     Q_OBJECT
 private slots:
     void testNoOverlap()
     {
+        const PerfElfMap::ElfInfo invalid;
+
         PerfElfMap map;
         QVERIFY(map.isEmpty());
 
-        QVERIFY(!map.registerElf(100, 10, 0, 0, {}));
+        const PerfElfMap::ElfInfo first({}, 100, 10, 0, 0);
+
+        QVERIFY(!registerElf(&map, first));
         QVERIFY(!map.isEmpty());
 
-        QCOMPARE(map.constBegin().key(), 100ull);
-        QCOMPARE(map.constBegin()->length, 10ull);
-        QCOMPARE(map.constBegin()->timeAdded, 0ull);
-
-        QCOMPARE(map.findElf(99, 0), map.constEnd());
-        QCOMPARE(map.findElf(100, 0), map.constBegin());
-        QCOMPARE(map.findElf(109, 0), map.constBegin());
-        QCOMPARE(map.findElf(110, 0), map.constEnd());
-        QCOMPARE(map.findElf(105, 1), map.constBegin());
-
-        QVERIFY(!map.registerElf(0, 10, 0, 1, {}));
-
-        QCOMPARE(map.constBegin().key(), 0ull);
-        QCOMPARE(map.constBegin()->length, 10ull);
-        QCOMPARE(map.constBegin()->timeAdded, 1ull);
-
-        auto first = map.constBegin();
-        auto second = first + 1;
-
-        QCOMPARE(map.findElf(0, 0), map.constEnd());
-        QCOMPARE(map.findElf(0, 1), first);
-        QCOMPARE(map.findElf(5, 1), first);
-        QCOMPARE(map.findElf(9, 1), first);
-        QCOMPARE(map.findElf(10, 0), map.constEnd());
-        QCOMPARE(map.findElf(5, 2), first);
-
-        QCOMPARE(map.findElf(99, 0), map.constEnd());
-        QCOMPARE(map.findElf(100, 0), second);
-        QCOMPARE(map.findElf(109, 0), second);
-        QCOMPARE(map.findElf(110, 0), map.constEnd());
-        QCOMPARE(map.findElf(105, 1), second);
+        QCOMPARE(std::distance(map.begin(), map.end()), 1);
+        QCOMPARE(*map.begin(), first);
+
+        QCOMPARE(map.findElf(99, 0), invalid);
+        QCOMPARE(map.findElf(100, 0), first);
+        QCOMPARE(map.findElf(109, 0), first);
+        QCOMPARE(map.findElf(110, 0), invalid);
+        QCOMPARE(map.findElf(105, 1), first);
+
+        const PerfElfMap::ElfInfo second({}, 0, 10, 0, 1);
+        QVERIFY(!registerElf(&map, second));
+
+        QCOMPARE(std::distance(map.begin(), map.end()), 2);
+        QCOMPARE(*map.begin(), second);
+        QCOMPARE(*(map.begin()+1), first);
+
+        QCOMPARE(map.findElf(0, 0), invalid);
+        QCOMPARE(map.findElf(0, 1), second);
+        QCOMPARE(map.findElf(5, 1), second);
+        QCOMPARE(map.findElf(9, 1), second);
+        QCOMPARE(map.findElf(10, 0), invalid);
+        QCOMPARE(map.findElf(5, 2), second);
+
+        QCOMPARE(map.findElf(99, 0), invalid);
+        QCOMPARE(map.findElf(100, 0), first);
+        QCOMPARE(map.findElf(109, 0), first);
+        QCOMPARE(map.findElf(110, 0), invalid);
+        QCOMPARE(map.findElf(105, 1), first);
     }
 
     void testOverwrite()
@@ -89,66 +109,36 @@ private slots:
         QFileInfo file2(tmpFile2.fileName());
         QCOMPARE(file2.isFile(), secondIsFile);
 
+        const PerfElfMap::ElfInfo first(file1, 95, 20, 0, 0, 1);
+        const PerfElfMap::ElfInfo second(file1, 105, 20, 0, 1, 2);
+        const PerfElfMap::ElfInfo third(file2, 100, 20, 0, 2);
+
         PerfElfMap map;
         if (!reversed) {
-            QVERIFY(!map.registerElf(95, 20, 0, 0, file1));
-            QCOMPARE(map.registerElf(105, 20, 0, 1, file1), firstIsFile);
-            QCOMPARE(map.registerElf(100, 20, 0, 2, file2), firstIsFile || secondIsFile);
+            QCOMPARE(registerElf(&map, first), false);
+            QCOMPARE(registerElf(&map, second), firstIsFile);
+            QCOMPARE(registerElf(&map, third), firstIsFile || secondIsFile);
         } else {
-            QVERIFY(!map.registerElf(100, 20, 0, 2, file2));
-            QCOMPARE(map.registerElf(105, 20, 0, 1, file1), firstIsFile || secondIsFile);
-            QCOMPARE(map.registerElf(95, 20, 0, 0, file1), firstIsFile || secondIsFile);
+            QCOMPARE(registerElf(&map, third), false);
+            QCOMPARE(registerElf(&map, second), firstIsFile || secondIsFile);
+            QCOMPARE(registerElf(&map, first), firstIsFile || secondIsFile);
         }
 
-        auto first = map.findElf(110, 0);
-        QCOMPARE(first.key(), 95ull);
-        QCOMPARE(first->length, 20ull);
-        QCOMPARE(first->pgoff, 0ull);
-        QCOMPARE(first->timeAdded, 0ull);
-        QCOMPARE(first->timeOverwritten, 1ull);
-        QCOMPARE(first->file, file1);
-
-        auto second = map.findElf(110, 1);
-        QCOMPARE(second.key(), 105ull);
-        QCOMPARE(second->length, 20ull);
-        QCOMPARE(second->pgoff, 0ull);
-        QCOMPARE(second->timeAdded, 1ull);
-        QCOMPARE(second->timeOverwritten, 2ull);
-        QCOMPARE(second->file, file1);
-
-        auto third = map.findElf(110, 2);
-        QCOMPARE(third.key(), 100ull);
-        QCOMPARE(third->length, 20ull);
-        QCOMPARE(third->pgoff, 0ull);
-        QCOMPARE(third->timeAdded, 2ull);
-        QCOMPARE(third->timeOverwritten, std::numeric_limits<quint64>::max());
-        QCOMPARE(third->file, file2);
+        QCOMPARE(map.findElf(110, 0), first);
+
+        QCOMPARE(map.findElf(110, 1), second);
 
+        QCOMPARE(map.findElf(110, 2), third);
         QCOMPARE(map.findElf(110, 3), third);
 
-        auto fragment1 = map.findElf(97, 1);
-        QCOMPARE(fragment1.key(), 95ull);
-        QCOMPARE(fragment1->length, 10ull);
-        QCOMPARE(fragment1->pgoff, 0ull);
-        QCOMPARE(fragment1->timeAdded, 1ull);
-        QCOMPARE(fragment1->timeOverwritten, 2ull);
-        QCOMPARE(fragment1->file, file1);
-
-        auto fragment2 = map.findElf(122, 2);
-        QCOMPARE(fragment2.key(), 120ull);
-        QCOMPARE(fragment2->length, 5ull);
-        QCOMPARE(fragment2->pgoff, 15ull);
-        QCOMPARE(fragment2->timeAdded, 2ull);
-        QCOMPARE(fragment2->timeOverwritten, std::numeric_limits<quint64>::max());
-        QCOMPARE(fragment2->file, file1);
-
-        auto fragment3 = map.findElf(97, 2);
-        QCOMPARE(fragment3.key(), 95ull);
-        QCOMPARE(fragment3->length, 5ull);
-        QCOMPARE(fragment3->pgoff, 0ull);
-        QCOMPARE(fragment3->timeAdded, 2ull);
-        QCOMPARE(fragment3->timeOverwritten, std::numeric_limits<quint64>::max());
-        QCOMPARE(fragment3->file, file1);
+        const PerfElfMap::ElfInfo fragment1(file1, 95, 10, 0, 1, 2);
+        QCOMPARE(map.findElf(97, 1), fragment1);
+
+        const PerfElfMap::ElfInfo fragment2(file1, 120, 5, 15, 2);
+        QCOMPARE(map.findElf(122, 2), fragment2);
+
+        const PerfElfMap::ElfInfo fragment3(file1, 95, 5, 0, 2);
+        QCOMPARE(map.findElf(97, 2), fragment3);
     }
 
     void testOverwrite_data()
@@ -170,6 +160,31 @@ private slots:
         QTest::newRow("reversed-no-files") << true << false << false;
     }
 
+    void testIsAddressInRange()
+    {
+        PerfElfMap map;
+        QVERIFY(!map.isAddressInRange(10));
+
+        const PerfElfMap::ElfInfo first({}, 10, 10, 0, 0);
+        QVERIFY(!registerElf(&map, first));
+        QVERIFY(!map.isAddressInRange(9));
+        QVERIFY(map.isAddressInRange(10));
+        QVERIFY(map.isAddressInRange(19));
+        QVERIFY(!map.isAddressInRange(20));
+
+        const PerfElfMap::ElfInfo second({}, 30, 10, 0, 1);
+        QVERIFY(!registerElf(&map, second));
+        QVERIFY(!map.isAddressInRange(9));
+        QVERIFY(map.isAddressInRange(10));
+        QVERIFY(map.isAddressInRange(19));
+        QVERIFY(map.isAddressInRange(30));
+        QVERIFY(map.isAddressInRange(39));
+        QVERIFY(!map.isAddressInRange(40));
+        // gaps are also within range
+        QVERIFY(map.isAddressInRange(20));
+        QVERIFY(map.isAddressInRange(29));
+    }
+
     void benchRegisterElfDisjunct()
     {
         QFETCH(int, numElfMaps);