1 /** 2 * Copyright (c) 2021-2024 Huawei Device Co., Ltd. 3 * Licensed under the Apache License, Version 2.0 (the "License"); 4 * you may not use this file except in compliance with the License. 5 * You may obtain a copy of the License at 6 * 7 * http://www.apache.org/licenses/LICENSE-2.0 8 * 9 * Unless required by applicable law or agreed to in writing, software 10 * distributed under the License is distributed on an "AS IS" BASIS, 11 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12 * See the License for the specific language governing permissions and 13 * limitations under the License. 14 */ 15 16 #ifndef PANDA_VERIFIER_ADDR_MAP_HPP_ 17 #define PANDA_VERIFIER_ADDR_MAP_HPP_ 18 19 #include "macros.h" 20 #include "range.h" 21 #include "bit_vector.h" 22 23 #include <cstdint> 24 25 namespace ark::verifier { 26 class AddrMap { 27 public: 28 AddrMap() = delete; AddrMap(const void * startPtr,const void * endPtr)29 AddrMap(const void *startPtr, const void *endPtr) 30 : AddrMap(reinterpret_cast<uintptr_t>(startPtr), reinterpret_cast<uintptr_t>(endPtr)) 31 { 32 } 33 AddrMap(const void * startPtr,size_t size)34 AddrMap(const void *startPtr, size_t size) 35 : AddrMap(reinterpret_cast<uintptr_t>(startPtr), reinterpret_cast<uintptr_t>(startPtr) + size - 1) 36 { 37 } 38 39 ~AddrMap() = default; 40 41 DEFAULT_MOVE_SEMANTIC(AddrMap); 42 DEFAULT_COPY_SEMANTIC(AddrMap); 43 IsInAddressSpace(const void * ptr)44 bool IsInAddressSpace(const void *ptr) const 45 { 46 return IsInAddressSpace(reinterpret_cast<uintptr_t>(ptr)); 47 } 48 49 template <typename PtrType> AddrStart()50 PtrType AddrStart() const 51 { 52 return reinterpret_cast<PtrType>(addrRange_.Start()); 53 } 54 55 template <typename PtrType> AddrEnd()56 PtrType AddrEnd() const 57 { 58 return reinterpret_cast<PtrType>(addrRange_.Finish()); 59 } 60 Mark(const void * addrPtr)61 bool Mark(const void *addrPtr) 62 { 63 return Mark(addrPtr, addrPtr); 64 } 65 Mark(const void * addrStartPtr,const void * addrEndPtr)66 bool Mark(const void *addrStartPtr, const void *addrEndPtr) 67 { 68 return Mark(reinterpret_cast<uintptr_t>(addrStartPtr), reinterpret_cast<uintptr_t>(addrEndPtr)); 69 } 70 Clear()71 void Clear() 72 { 73 Clear(addrRange_.Start(), addrRange_.Finish()); 74 } 75 Clear(const void * addrPtr)76 bool Clear(const void *addrPtr) 77 { 78 return Clear(addrPtr, addrPtr); 79 } 80 Clear(const void * addrStartPtr,const void * addrEndPtr)81 bool Clear(const void *addrStartPtr, const void *addrEndPtr) 82 { 83 return Clear(reinterpret_cast<uintptr_t>(addrStartPtr), reinterpret_cast<uintptr_t>(addrEndPtr)); 84 } 85 HasMark(const void * addrPtr)86 bool HasMark(const void *addrPtr) const 87 { 88 return HasMarks(addrPtr, addrPtr); 89 } 90 HasMarks(const void * addrStartPtr,const void * addrEndPtr)91 bool HasMarks(const void *addrStartPtr, const void *addrEndPtr) const 92 { 93 return HasMarks(reinterpret_cast<uintptr_t>(addrStartPtr), reinterpret_cast<uintptr_t>(addrEndPtr)); 94 } 95 HasCommonMarks(const AddrMap & rhs)96 bool HasCommonMarks(const AddrMap &rhs) const 97 { 98 // NOTE: work with different addr spaces 99 ASSERT(addrRange_ == rhs.addrRange_); 100 return BitVector::LazyAndThenIndicesOf<true>(bitMap_, rhs.bitMap_)().IsValid(); 101 } 102 103 template <typename PtrType> GetFirstCommonMark(const AddrMap & rhs,PtrType * ptr)104 bool GetFirstCommonMark(const AddrMap &rhs, PtrType *ptr) const 105 { 106 // NOTE: work with different addr spaces 107 ASSERT(addrRange_ == rhs.addrRange_); 108 Index<size_t> idx = BitVector::LazyAndThenIndicesOf<true>(bitMap_, rhs.bitMap_)(); 109 if (idx.IsValid()) { 110 size_t offset = idx; 111 *ptr = reinterpret_cast<PtrType>(addrRange_.IndexOf(offset)); 112 return true; 113 } 114 return false; 115 } 116 117 // NOTE(vdyadov): optimize this function, push blocks enumeration to bit vector level 118 // and refactor it to work with words and ctlz like intrinsics 119 template <typename PtrType, typename Callback> EnumerateMarkedBlocks(Callback cb)120 void EnumerateMarkedBlocks(Callback cb) const 121 { 122 PtrType start = nullptr; 123 PtrType end = nullptr; 124 for (auto addr : addrRange_) { 125 uintptr_t bitOffset = addrRange_.OffsetOf(addr); 126 if (start == nullptr) { 127 if (bitMap_[bitOffset]) { 128 start = reinterpret_cast<PtrType>(addr); 129 } 130 } else { 131 if (bitMap_[bitOffset]) { 132 continue; 133 } 134 end = reinterpret_cast<PtrType>(addr - 1); 135 if (!cb(start, end)) { 136 return; 137 } 138 start = nullptr; 139 } 140 } 141 if (start != nullptr) { 142 end = reinterpret_cast<PtrType>(addrRange_.Finish()); 143 cb(start, end); 144 } 145 } 146 InvertMarks()147 void InvertMarks() 148 { 149 bitMap_.Invert(); 150 } 151 152 template <typename PtrType, typename Handler> EnumerateMarksInScope(const void * addrStartPtr,const void * addrEndPtr,Handler handler)153 void EnumerateMarksInScope(const void *addrStartPtr, const void *addrEndPtr, Handler handler) const 154 { 155 EnumerateMarksInScope<PtrType>(reinterpret_cast<uintptr_t>(addrStartPtr), 156 reinterpret_cast<uintptr_t>(addrEndPtr), std::move(handler)); 157 } 158 159 private: AddrMap(uintptr_t addrFrom,uintptr_t addrTo)160 AddrMap(uintptr_t addrFrom, uintptr_t addrTo) : addrRange_ {addrFrom, addrTo}, bitMap_ {addrRange_.Length()} {} 161 IsInAddressSpace(uintptr_t addr)162 bool IsInAddressSpace(uintptr_t addr) const 163 { 164 return addrRange_.Contains(addr); 165 } 166 Mark(uintptr_t addrFrom,uintptr_t addrTo)167 bool Mark(uintptr_t addrFrom, uintptr_t addrTo) 168 { 169 if (!addrRange_.Contains(addrFrom) || !addrRange_.Contains(addrTo)) { 170 return false; 171 } 172 ASSERT(addrFrom <= addrTo); 173 bitMap_.Set(addrRange_.OffsetOf(addrFrom), addrRange_.OffsetOf(addrTo)); 174 return true; 175 } 176 Clear(uintptr_t addrFrom,uintptr_t addrTo)177 bool Clear(uintptr_t addrFrom, uintptr_t addrTo) 178 { 179 if (!addrRange_.Contains(addrFrom) || !addrRange_.Contains(addrTo)) { 180 return false; 181 } 182 ASSERT(addrFrom <= addrTo); 183 bitMap_.Clr(addrRange_.OffsetOf(addrFrom), addrRange_.OffsetOf(addrTo)); 184 return true; 185 } 186 HasMarks(uintptr_t addrFrom,uintptr_t addrTo)187 bool HasMarks(uintptr_t addrFrom, uintptr_t addrTo) const 188 { 189 if (!addrRange_.Contains(addrFrom) || !addrRange_.Contains(addrTo)) { 190 return false; 191 } 192 ASSERT(addrFrom <= addrTo); 193 Index<size_t> firstMarkIdx = 194 bitMap_.LazyIndicesOf<1>(addrRange_.OffsetOf(addrFrom), addrRange_.OffsetOf(addrTo))(); 195 return firstMarkIdx.IsValid(); 196 } 197 198 template <typename PtrType, typename Handler> EnumerateMarksInScope(uintptr_t addrFrom,uintptr_t addrTo,Handler handler)199 void EnumerateMarksInScope(uintptr_t addrFrom, uintptr_t addrTo, Handler handler) const 200 { 201 ASSERT(addrFrom <= addrTo); 202 auto from = addrRange_.OffsetOf(addrRange_.PutInBounds(addrFrom)); 203 auto to = addrRange_.OffsetOf(addrRange_.PutInBounds(addrTo)); 204 // upper range point is excluded 205 for (uintptr_t idx = from; idx < to; idx++) { 206 if (bitMap_[idx]) { 207 if (!handler(reinterpret_cast<PtrType>(addrRange_.IndexOf(idx)))) { 208 return; 209 } 210 } 211 } 212 } 213 214 private: 215 Range<uintptr_t> addrRange_; 216 BitVector bitMap_; 217 }; 218 } // namespace ark::verifier 219 220 #endif // !PANDA_VERIFIER_ADDR_MAP_HPP_ 221