1 /* 2 * Copyright (C) 2023 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_SHARED_LIB_INTERN_MAP_H_ 18 #define SRC_SHARED_LIB_INTERN_MAP_H_ 19 20 #include "perfetto/ext/base/flat_hash_map.h" 21 #include "perfetto/public/fnv1a.h" 22 23 namespace perfetto { 24 25 // Assigns and maintains the mapping between "interned" data and iids (small 26 // integers that can be used to refer to the same data without repeating it) 27 // for different types. 28 class InternMap { 29 public: 30 // Zero will never be assigned as a valid iid: it is used as the return value 31 // of Find() to signal failure. 32 using Iid = uint64_t; 33 34 InternMap(); 35 ~InternMap(); 36 37 // Given a value (identified by the memory buffer starting at `value`, 38 // `value_size` bytes long) of a specific `type`, finds if there was an 39 // existing iid associated with it, or assigns a new iid to it. Assigned iids 40 // are unique for a specific type, but are reused across different types. 41 struct FindOrAssignRes { 42 // Iid associated with the passed value. 43 Iid iid; 44 // Whether the iid was newly assigned in this call (i.e. true if the value 45 // was not seen before). 46 bool newly_assigned; 47 }; 48 FindOrAssignRes FindOrAssign(int32_t type, 49 const void* value, 50 size_t value_size); 51 52 private: 53 // Stores a value of a specific type. If the value is small, it is stored 54 // inline, otherwise it is stored in an external buffer. The Key can own the 55 // external buffer (when the key is stored in the map) or not (when the key is 56 // just used for lookup). 57 class Key { 58 public: NonOwning(int32_t type,const void * value,size_t value_size)59 static Key NonOwning(int32_t type, const void* value, size_t value_size) { 60 Key key; 61 key.type_ = type; 62 key.val_type_ = ValueStorage::kNonOwnedPtr; 63 key.ptr_ = value; 64 key.value_size_ = value_size; 65 return key; 66 } Owning(int32_t type,const void * value,size_t value_size)67 static Key Owning(int32_t type, const void* value, size_t value_size) { 68 Key key; 69 key.type_ = type; 70 key.value_size_ = value_size; 71 if (value_size < sizeof(value_buf_)) { 72 key.val_type_ = ValueStorage::kInline; 73 memcpy(key.value_buf_, value, value_size); 74 } else { 75 key.val_type_ = ValueStorage::kOwnedPtr; 76 char* newvalue = new char[value_size]; 77 memcpy(newvalue, value, value_size); 78 key.owned_ptr_ = newvalue; 79 } 80 return key; 81 } ~Key()82 ~Key() { 83 if (val_type_ == ValueStorage::kOwnedPtr) { 84 delete[] owned_ptr_; 85 } 86 } 87 Key(const Key&) = delete; Key(Key && other)88 Key(Key&& other) noexcept { 89 type_ = other.type_; 90 value_size_ = other.value_size_; 91 switch (other.val_type_) { 92 case ValueStorage::kNonOwnedPtr: 93 val_type_ = ValueStorage::kNonOwnedPtr; 94 ptr_ = other.ptr_; 95 return; 96 case ValueStorage::kOwnedPtr: 97 val_type_ = ValueStorage::kOwnedPtr; 98 owned_ptr_ = other.owned_ptr_; 99 other.val_type_ = ValueStorage::kInline; 100 other.value_size_ = 0; 101 return; 102 case ValueStorage::kInline: 103 val_type_ = ValueStorage::kInline; 104 memcpy(value_buf_, other.value_buf_, value_size_); 105 return; 106 } 107 } 108 bool operator==(const Key& other) const { 109 if (type_ != other.type_) { 110 return false; 111 } 112 if (value_size_ != other.value_size_) { 113 return false; 114 } 115 return memcmp(value(), other.value(), value_size_) == 0; 116 } value()117 const void* value() const { 118 switch (val_type_) { 119 case ValueStorage::kNonOwnedPtr: 120 return ptr_; 121 case ValueStorage::kOwnedPtr: 122 return owned_ptr_; 123 case ValueStorage::kInline: 124 break; 125 } 126 return &value_buf_; 127 } 128 struct Hash { operatorHash129 size_t operator()(const Key& obj) const { 130 return std::hash<int32_t>()(obj.type_) ^ 131 static_cast<size_t>(PerfettoFnv1a(obj.value(), obj.value_size_)); 132 } 133 }; 134 135 private: 136 enum class ValueStorage { 137 kInline, // `value_buf_` is used directly to store the value. 138 kNonOwnedPtr, // `ptr_` points to an external buffer that stores the 139 // value. Not owned by this Key. 140 kOwnedPtr, // `owned_ptr_` points to an external buffer that stores 141 // the value. Owned by this Key. 142 }; 143 Key() = default; 144 int32_t type_; 145 ValueStorage val_type_; 146 size_t value_size_; 147 union { 148 char value_buf_[sizeof(uint64_t)]; 149 const void* ptr_; 150 char* owned_ptr_; 151 }; 152 }; 153 154 base::FlatHashMap<Key, uint64_t, Key::Hash> map_; 155 base::FlatHashMap<int32_t, uint64_t> last_iid_by_type_; 156 }; 157 158 } // namespace perfetto 159 160 #endif // SRC_SHARED_LIB_INTERN_MAP_H_ 161