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_TRACE_PROCESSOR_UTIL_BUMP_ALLOCATOR_H_ 18 #define SRC_TRACE_PROCESSOR_UTIL_BUMP_ALLOCATOR_H_ 19 20 #include <cmath> 21 #include <cstdint> 22 #include <cstring> 23 #include <limits> 24 #include <memory> 25 #include <optional> 26 #include <tuple> 27 28 #include "perfetto/ext/base/circular_queue.h" 29 #include "perfetto/ext/base/utils.h" 30 31 namespace perfetto { 32 namespace trace_processor { 33 34 // A simple memory allocator which "bumps" a pointer to service allocations. 35 // See [1] for more details for an overview of bump allocators. 36 // 37 // This implementation works by obtaining a large chunk of memory from the 38 // system allocator (i.e. from malloc). Every allocation uses that chunk as long 39 // as there is free space inside. Once an allocation is requested which does not 40 // fit in that chunk, a new chunk is requested from the system. 41 // 42 // IMPORTANT: all allocations returned from this allocator are 8-aligned and 43 // all allocation sizes must be a multiple of 8. 44 // 45 // IMPORTANT: this allocator can allocate a total of 4GB of memory (2^32). Once 46 // this is exhausted, any further allocation will cause a CHECK. 47 // 48 // IMPORTANT: all allocations *must* be explicitly freed before destroying this 49 // object. The destructor will CHECK if it detects any allocation which is 50 // unfreed. 51 // 52 // [1] https://rust-hosted-langs.github.io/book/chapter-simple-bump.html 53 class BumpAllocator { 54 public: 55 // The limit on the total number of bits which can be used to represent 56 // the chunk id. 57 static constexpr uint64_t kMaxIdBits = 58; 58 59 // The limit on the total amount of memory which can be allocated. 60 static constexpr uint64_t kAllocLimit = 1ull << kMaxIdBits; 61 62 // The size of the "large chunk" requested from the system allocator. 63 // The size of this value trades-off between unused memory use vs CPU cost 64 // of going to the system allocator. 64KB feels a good trade-off there. 65 static constexpr uint64_t kChunkSize = 64ull * 1024; // 64KB 66 67 // The maximum number of chunks which this allocator can have. 68 static constexpr uint64_t kMaxChunkCount = kAllocLimit / kChunkSize; 69 70 // The number of bits used to represent the offset the chunk in AllocId. 71 // 72 // This is simply log2(kChunkSize): we have a separate constant as log2 is 73 // not a constexpr function: the static assets below verify this stays in 74 // sync. 75 static constexpr uint64_t kChunkOffsetAllocIdBits = 16u; 76 77 // The number of bits used to represent the chunk index in AllocId. 78 static constexpr uint64_t kChunkIndexAllocIdBits = 79 kMaxIdBits - kChunkOffsetAllocIdBits; 80 81 // Represents an allocation returned from the allocator. We return this 82 // instead of just returning a pointer to allow looking up a chunk an 83 // allocation belongs to without needing having to scan chunks. 84 struct AllocId { 85 uint64_t chunk_index : kChunkIndexAllocIdBits; 86 uint64_t chunk_offset : kChunkOffsetAllocIdBits; 87 88 // Comparision operators mainly for sorting. 89 bool operator<(const AllocId& other) const { 90 return std::tie(chunk_index, chunk_offset) < 91 std::tie(other.chunk_index, other.chunk_offset); 92 } 93 bool operator>=(const AllocId& other) const { return !(*this < other); } 94 bool operator>(const AllocId& other) const { return other < *this; } 95 }; 96 static_assert(sizeof(AllocId) == sizeof(uint64_t), 97 "AllocId should be 64-bit in size to allow serialization"); 98 static_assert( 99 kMaxChunkCount == (1ull << kChunkIndexAllocIdBits), 100 "Max chunk count must match the number of bits used for chunk indices"); 101 static_assert( 102 kChunkSize == (1 << kChunkOffsetAllocIdBits), 103 "Chunk size must match the number of bits used for offset within chunk"); 104 105 BumpAllocator(); 106 107 // Verifies that all calls to |Alloc| were paired with matching calls to 108 // |Free|. 109 ~BumpAllocator(); 110 111 BumpAllocator(BumpAllocator&&) noexcept = default; 112 BumpAllocator& operator=(BumpAllocator&&) noexcept = default; 113 114 // Allocates |size| bytes of memory. |size| must be a multiple of 8 and less 115 // than or equal to |kChunkSize|. 116 // 117 // Returns an |AllocId| which can be converted to a pointer using 118 // |GetPointer|. 119 AllocId Alloc(uint32_t size); 120 121 // Frees an allocation previously allocated by |Alloc|. This function is *not* 122 // idempotent. 123 // 124 // Once this function returns, |id| is no longer valid for any use. Trying 125 // to use it further (e.g. to passing to other methods including Free itself) 126 // will cause undefined behaviour. 127 void Free(AllocId id); 128 129 // Given an AllocId, returns a pointer which can be read from/written to. 130 // 131 // The caller is only allowed to access up to |size| bytes, where |size| == 132 // the |size| argument to Alloc. 133 void* GetPointer(AllocId); 134 135 // Removes chunks from the start of this allocator where all the allocations 136 // in the chunks have been freed. This releases the memory back to the system. 137 // 138 // Returns the number of chunks freed. 139 uint64_t EraseFrontFreeChunks(); 140 141 // Returns a "past the end" serialized AllocId i.e. a serialized value 142 // greater than all previously returned AllocIds. 143 AllocId PastTheEndId(); 144 145 // Returns the number of erased chunks from the start of this allocator. 146 // 147 // This value may change any time |EraseFrontFreeChunks| is called but is 148 // constant otherwise. erased_front_chunks_count()149 uint64_t erased_front_chunks_count() const { 150 return erased_front_chunks_count_; 151 } 152 153 private: 154 struct Chunk { 155 // The allocation from the system for this chunk. Because all allocations 156 // need to be 8 byte aligned, the chunk also needs to be 8-byte aligned. 157 // base::AlignedUniquePtr ensures this is the case. 158 base::AlignedUniquePtr<uint8_t[]> allocation; 159 160 // The bump offset relative to |allocation.data|. Incremented to service 161 // Alloc requests. 162 uint32_t bump_offset = 0; 163 164 // The number of unfreed allocations in this chunk. 165 uint32_t unfreed_allocations = 0; 166 }; 167 168 // Tries to allocate |size| bytes in the final chunk in |chunks_|. Returns 169 // an AllocId if this was successful or std::nullopt otherwise. 170 std::optional<AllocId> TryAllocInLastChunk(uint32_t size); 171 ChunkIndexToQueueIndex(uint64_t chunk_index)172 uint64_t ChunkIndexToQueueIndex(uint64_t chunk_index) const { 173 return chunk_index - erased_front_chunks_count_; 174 } QueueIndexToChunkIndex(uint64_t index_in_chunks_vec)175 uint64_t QueueIndexToChunkIndex(uint64_t index_in_chunks_vec) const { 176 return erased_front_chunks_count_ + index_in_chunks_vec; 177 } LastChunkIndex()178 uint64_t LastChunkIndex() const { 179 PERFETTO_DCHECK(!chunks_.empty()); 180 return QueueIndexToChunkIndex(static_cast<uint64_t>(chunks_.size() - 1)); 181 } 182 183 base::CircularQueue<Chunk> chunks_; 184 uint64_t erased_front_chunks_count_ = 0; 185 }; 186 187 } // namespace trace_processor 188 } // namespace perfetto 189 190 #endif // SRC_TRACE_PROCESSOR_UTIL_BUMP_ALLOCATOR_H_ 191