1 /* 2 * Copyright (C) 2024 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 #ifndef SRC_TRACE_PROCESSOR_IMPORTERS_ETM_VIRTUAL_ADDRESS_SPACE_H_ 18 #define SRC_TRACE_PROCESSOR_IMPORTERS_ETM_VIRTUAL_ADDRESS_SPACE_H_ 19 20 #include <cstdint> 21 #include <optional> 22 #include <vector> 23 24 #include "src/trace_processor/importers/etm/mapping_version.h" 25 #include "src/trace_processor/storage/trace_storage.h" 26 #include "src/trace_processor/tables/perf_tables_py.h" 27 28 namespace perfetto::trace_processor { 29 class TraceProcessorContext; 30 namespace etm { 31 32 // Represents the virtual address space for a process. 33 // This class is used to answer queries in the form: At timestamp t, what was 34 // the mapping at address x for the thread tid. We want these lookups to be as 35 // fast as possible, as we will be doing a lot of these during ETM parsing. 36 // 37 // Basically this boils down to the "point location" problem in a 2D rectilinear 38 // space where one dimension is time and the other is the address space. 39 // 40 // Eg: 41 // T ↑ 42 // i │ 43 // m │ ↑ ↑ ↑ ↑ 44 // e │ │ │ │ Mapping 4 │ 45 // │ │ Mapping 3 │ └──────┬─────┘ 46 // │ │ │ │ 47 // │ └──┬───┬────┘ │ 48 // │ │ │ Mapping 2 │ 49 // │ │ └────────────┬────────┘ 50 // │ │ Mapping 1 │ 51 // │ └────────────────┘ 52 // └──────────────────────────────────────────────────────→ address 53 // 54 // There are many studied solutions to this problem or increased complexity and 55 // better performance. This class implements a "slab decomposition" approach as 56 // described by "Dobkin and Lipton" 57 // (https://en.wikipedia.org/wiki/Point_location). 58 // 59 // This is a very simple approach that just partitions the space using vertical 60 // lines that pass through each vertex, creating so called slabs. This 61 // partitions the address space in on overlapping regions, and for each region 62 // you can see that mappings will be ordered by time. This gives us O(log N) 63 // lookup but O(N^2) space, which is fine in our case as the ^2 comes from 64 // mapping overlaps, which we expect to rarely happen, so in practice space 65 // usage will be more like O(N). 66 // 67 // So the above example would look like: 68 // 69 // T ↑ 70 // i │ 71 // m │ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ 72 // e │ │ │ │ │ │ │ 4 │ 4 │ 73 // │ │ │ │ │ │ ├──────┼─────┘ 74 // │ │3 │ 3 │ 3 │ 2 │2│ 2 │ ┊ 75 // │ └──┼───┼────┤ │ │ │ ┊ 76 // │ ┊ │ │ 2 │ │ │ │ ┊ 77 // │ ┊ │ ├────┼───────┼─┴──────┘ ┊ 78 // │ ┊ │ 1 │ 1 │ 1 │ ┊ ┊ ┊ 79 // │ ┊ └───┴────┴───────┘ ┊ ┊ ┊ 80 // │ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 81 // └─┴──┴───┴────┴───────┴─┴──────┴─────┴──────────────→ address 82 // Slabs A B C D E F G 83 // 84 // Instead of keeping two separate structures (one to store the non overlapping 85 // ranges and one to store the mappings timestamp order), we have one array of 86 // `MappingVersion` objects (one for each of the boxes above) ordered by 87 // increasing address range and decreasing creation time. This allows us to do 88 // one lower_bound search to find the desired mapping. So the ordering keep in 89 // this class would look like: 90 // 91 // A3, B3, B1, C3, C2, C1, D2, D1, E2, F4, F2, G4 92 class VirtualAddressSpace { 93 public: VirtualAddressSpace()94 VirtualAddressSpace() {} 95 class Builder { 96 public: Builder(TraceProcessorContext * context)97 explicit Builder(TraceProcessorContext* context) : context_(context) {} 98 void AddMapping(tables::MmapRecordTable::ConstRowReference mmap); 99 VirtualAddressSpace Build() &&; 100 101 private: 102 // Mappings ordered by ascending address and descending creation time. We 103 // resolve collisions by additionally ordering by mapping_id. Note that if 104 // two mappings overlap, and they are created at the same time, only the one 105 // with the higher mapping_id will be used. (Although iun practice this 106 // should never happen, TM) 107 struct FullSort { operatorFullSort108 bool operator()(const MappingVersion& lhs, 109 const MappingVersion& rhs) const { 110 if (lhs.start() < rhs.start()) { 111 return true; 112 } 113 if (rhs.start() < lhs.start()) { 114 return false; 115 } 116 if (lhs.create_ts() > rhs.create_ts()) { 117 return true; 118 } 119 if (rhs.create_ts() > lhs.create_ts()) { 120 return false; 121 } 122 return lhs.id() < rhs.id(); 123 } 124 }; 125 126 using SortedMappingsWithOverlaps = std::set<MappingVersion, FullSort>; 127 using Vertices = std::set<uint64_t>; 128 129 TraceProcessorContext* context_; 130 SortedMappingsWithOverlaps mappings_; 131 Vertices vertices_; 132 }; 133 const MappingVersion* FindMapping(int64_t ts, uint64_t address) const; 134 135 template <typename Callback> ForEach(Callback cb)136 void ForEach(Callback cb) const { 137 for (const auto& m : mappings_) { 138 cb(m); 139 } 140 } 141 142 private: 143 struct LookupKey { 144 uint64_t address; 145 int64_t ts; 146 }; 147 148 // Mappings ordered by ascending address and descending creation time. So 149 // point lookups can be answered with one lower_bound lookup. 150 struct Lookup { operatorLookup151 bool operator()(const MappingVersion& lhs, const LookupKey& rhs) const { 152 if (lhs.end() <= rhs.address) { 153 return true; 154 } 155 if (rhs.address < lhs.start()) { 156 return false; 157 } 158 return lhs.create_ts() > rhs.ts; 159 } 160 }; 161 162 private: VirtualAddressSpace(std::vector<MappingVersion> mappings)163 explicit VirtualAddressSpace(std::vector<MappingVersion> mappings) 164 : mappings_(std::move(mappings)) {} 165 std::vector<MappingVersion> mappings_; 166 }; 167 168 } // namespace etm 169 } // namespace perfetto::trace_processor 170 171 #endif // SRC_TRACE_PROCESSOR_IMPORTERS_ETM_VIRTUAL_ADDRESS_SPACE_H_ 172