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 93 class VirtualAddressSpace { 94 public: VirtualAddressSpace()95 VirtualAddressSpace() {} 96 class Builder { 97 public: Builder(TraceProcessorContext * context)98 explicit Builder(TraceProcessorContext* context) : context_(context) {} 99 void AddMapping(tables::MmapRecordTable::ConstRowReference mmap); 100 VirtualAddressSpace Build() &&; 101 102 private: 103 // Mappings ordered by ascending address and descending creation time. We 104 // resolve collisions by additionally ordering by mapping_id. Note that if 105 // two mappings overlap, and they are created at the same time, only the one 106 // with the higher mapping_id will be used. (Although iun practice this 107 // should never happen, TM) 108 struct FullSort { operatorFullSort109 bool operator()(const MappingVersion& lhs, 110 const MappingVersion& rhs) const { 111 if (lhs.start() < rhs.start()) { 112 return true; 113 } 114 if (rhs.start() < lhs.start()) { 115 return false; 116 } 117 if (lhs.create_ts() > rhs.create_ts()) { 118 return true; 119 } 120 if (rhs.create_ts() > lhs.create_ts()) { 121 return false; 122 } 123 return lhs.id() < rhs.id(); 124 } 125 }; 126 127 using SortedMappingsWithOverlaps = std::set<MappingVersion, FullSort>; 128 using Vertices = std::set<uint64_t>; 129 130 TraceProcessorContext* context_; 131 SortedMappingsWithOverlaps mappings_; 132 Vertices vertices_; 133 }; 134 const MappingVersion* FindMapping(int64_t ts, uint64_t address) const; 135 136 template <typename Callback> ForEach(Callback cb)137 void ForEach(Callback cb) const { 138 for (const auto& m : mappings_) { 139 cb(m); 140 } 141 } 142 143 private: 144 struct LookupKey { 145 uint64_t address; 146 int64_t ts; 147 }; 148 149 // Mappings ordered by ascending address and descending creation time. So 150 // point lookups can be answered with one lower_bound lookup. 151 struct Lookup { operatorLookup152 bool operator()(const MappingVersion& lhs, const LookupKey& rhs) const { 153 if (lhs.end() <= rhs.address) { 154 return true; 155 } 156 if (rhs.address < lhs.start()) { 157 return false; 158 } 159 return lhs.create_ts() > rhs.ts; 160 } 161 }; 162 163 private: VirtualAddressSpace(std::vector<MappingVersion> mappings)164 explicit VirtualAddressSpace(std::vector<MappingVersion> mappings) 165 : mappings_(std::move(mappings)) {} 166 std::vector<MappingVersion> mappings_; 167 }; 168 169 } // namespace etm 170 } // namespace perfetto::trace_processor 171 172 #endif // SRC_TRACE_PROCESSOR_IMPORTERS_ETM_VIRTUAL_ADDRESS_SPACE_H_ 173