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