memory/allocators/concurrent_slab_memory_pool.h
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #pragma once | ||
| 2 | |||
| 3 | #include <atomic> | ||
| 4 | #include <deque> | ||
| 5 | #include <memory> | ||
| 6 | #include <set> | ||
| 7 | #include <string> | ||
| 8 | #include <unordered_map> | ||
| 9 | #include <utility> | ||
| 10 | #include <vector> | ||
| 11 | |||
| 12 | #include "base/async_time.h" | ||
| 13 | #include "base/base.h" | ||
| 14 | #include "base/bitmap.h" | ||
| 15 | #include "base/factory.h" | ||
| 16 | #include "base/log.h" | ||
| 17 | #include "base/string.h" | ||
| 18 | #include <fmt/format.h> | ||
| 19 | #include "memory/malloc.h" | ||
| 20 | #include "memory/shm_file.h" | ||
| 21 | |||
| 22 | namespace base { | ||
| 23 | |||
| 24 | namespace concurrent_slab_detail { | ||
| 25 | |||
| 26 | 308960 | inline uint64_t* BitmapWords(base::BitMap* bitmap) { | |
| 27 | return reinterpret_cast<uint64_t*>( | ||
| 28 | 308960 | reinterpret_cast<char*>(bitmap) + sizeof(base::BitMap)); | |
| 29 | } | ||
| 30 | |||
| 31 | 184340 | inline int BitmapNumWords(int nr_entries) { return nr_entries / 64; } | |
| 32 | |||
| 33 | 184340 | inline int& AllocWordHintTls() { | |
| 34 | thread_local int hint = 0; | ||
| 35 | 184340 | return hint; | |
| 36 | } | ||
| 37 | |||
| 38 | inline int | ||
| 39 | 184340 | TryAllocFromBitmap(uint64_t* words, int n_words, int start_word = 0) { | |
| 40 |
1/2✓ Branch 0 taken 184340 times.
✗ Branch 1 not taken.
|
184340 | for (int w = 0; w < n_words; ++w) { |
| 41 | 184340 | const int i = (start_word + w) % n_words; | |
| 42 | 184340 | uint64_t old = words[i]; | |
| 43 | while (true) { | ||
| 44 | 184340 | const uint64_t inv = ~old; | |
| 45 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 184340 times.
|
184340 | if (!inv) { |
| 46 | ✗ | break; | |
| 47 | } | ||
| 48 | 184340 | const uint64_t pos = static_cast<uint64_t>(__builtin_ctzll(inv)); | |
| 49 | 184340 | const uint64_t desired = old | (1ull << pos); | |
| 50 |
1/2✓ Branch 0 taken 184340 times.
✗ Branch 1 not taken.
|
184340 | if (__sync_bool_compare_and_swap(&words[i], old, desired)) { |
| 51 | 184340 | return i * 64 + static_cast<int>(pos); | |
| 52 | } | ||
| 53 | ✗ | old = words[i]; | |
| 54 | ✗ | } | |
| 55 | } | ||
| 56 | ✗ | return -1; | |
| 57 | } | ||
| 58 | |||
| 59 | 124620 | inline bool TryFreeBitmapBit(uint64_t* words, int bit) { | |
| 60 | 124620 | const int i = bit / 64; | |
| 61 | 124620 | const int pos = bit % 64; | |
| 62 | 124620 | const uint64_t clear_mask = ~(1ull << pos); | |
| 63 | 124620 | uint64_t old = words[i]; | |
| 64 | while (true) { | ||
| 65 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 124620 times.
|
124620 | if ((old & (1ull << pos)) == 0) { |
| 66 | ✗ | return false; | |
| 67 | } | ||
| 68 | 124620 | const uint64_t desired = old & clear_mask; | |
| 69 |
1/2✓ Branch 0 taken 124620 times.
✗ Branch 1 not taken.
|
124620 | if (__sync_bool_compare_and_swap(&words[i], old, desired)) { |
| 70 | 124620 | return true; | |
| 71 | } | ||
| 72 | ✗ | old = words[i]; | |
| 73 | ✗ | } | |
| 74 | } | ||
| 75 | |||
| 76 | } // namespace concurrent_slab_detail | ||
| 77 | |||
| 78 | template <bool PERFECT_FIT_MOD = true> | ||
| 79 | class ConcurrentSlabMemoryPool : public MallocApi { | ||
| 80 | static constexpr uint64_t kChunkSize = 1 * 1024 * 1024ULL; | ||
| 81 | static constexpr int kMetaDataSize = 8; | ||
| 82 | |||
| 83 | class SlabChunk { | ||
| 84 | public: | ||
| 85 | 26268 | SlabChunk(char* chunk_start, uint64_t chunk_id) | |
| 86 | 26268 | : header_(reinterpret_cast<ChunkHeader*>(chunk_start)), | |
| 87 | 26268 | data_(nullptr), | |
| 88 | 26268 | chunk_id_(chunk_id), | |
| 89 | 26268 | allocated_entries_(0), | |
| 90 | 26268 | listed_in_partial_(false) {} | |
| 91 | |||
| 92 | 49448 | void Initialize() { | |
| 93 | 49448 | header_->slab_size_ = 0; | |
| 94 | 49448 | header_->nr_entries_ = 0; | |
| 95 | 49448 | data_ = nullptr; | |
| 96 | 49448 | allocated_entries_.store(0, std::memory_order_relaxed); | |
| 97 | 49448 | listed_in_partial_.store(false, std::memory_order_relaxed); | |
| 98 | 49448 | } | |
| 99 | |||
| 100 | 964 | void Use(int slab_size) { | |
| 101 |
1/6✗ Branch 3 not taken.
✓ Branch 4 taken 964 times.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
✗ Branch 10 not taken.
✗ Branch 11 not taken.
|
964 | CHECK_EQ(header_->slab_size_, 0) |
| 102 | ✗ | << "chunk " << chunk_id_ << " already bound to slab " | |
| 103 | ✗ | << header_->slab_size_; | |
| 104 | |||
| 105 | 964 | int nr_entries = static_cast<int>(kChunkSize / slab_size); | |
| 106 | 964 | nr_entries -= (nr_entries % 64); | |
| 107 | |||
| 108 |
2/2✓ Branch 1 taken 90 times.
✓ Branch 2 taken 964 times.
|
1054 | while (ChunkHeader::HeaderSize(nr_entries) + nr_entries * slab_size > |
| 109 | kChunkSize) { | ||
| 110 | 90 | nr_entries -= 64; | |
| 111 | } | ||
| 112 |
1/6✗ Branch 3 not taken.
✓ Branch 4 taken 964 times.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
✗ Branch 10 not taken.
✗ Branch 11 not taken.
|
964 | CHECK_GT(nr_entries, 0); |
| 113 | |||
| 114 | 964 | header_->slab_size_ = slab_size; | |
| 115 | 964 | header_->nr_entries_ = nr_entries; | |
| 116 |
1/2✓ Branch 2 taken 964 times.
✗ Branch 3 not taken.
|
964 | new (header_->bitmap_) base::BitMap(nr_entries); |
| 117 | 964 | header_->bitmap_->Clear(); | |
| 118 | 964 | data_ = reinterpret_cast<char*>(header_) + header_->HeaderSize(); | |
| 119 | 964 | allocated_entries_.store(0, std::memory_order_relaxed); | |
| 120 | 964 | listed_in_partial_.store(false, std::memory_order_relaxed); | |
| 121 | 964 | } | |
| 122 | |||
| 123 | 308960 | bool IsActivated() const { return header_->slab_size_ != 0; } | |
| 124 | |||
| 125 | 183384 | bool Full() const { | |
| 126 | 183384 | return allocated_entries_.load(std::memory_order_relaxed) >= | |
| 127 | 183384 | header_->nr_entries_; | |
| 128 | } | ||
| 129 | |||
| 130 | 184340 | char* Malloc() { | |
| 131 |
2/12✗ Branch 1 not taken.
✓ Branch 2 taken 184340 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
✗ Branch 10 not taken.
✗ Branch 11 not taken.
✗ Branch 14 not taken.
✓ Branch 15 taken 184340 times.
✗ Branch 17 not taken.
✗ Branch 18 not taken.
|
184340 | CHECK(IsActivated()); |
| 132 | 184340 | const int nr_entries = header_->nr_entries_; | |
| 133 | 184340 | uint64_t* words = concurrent_slab_detail::BitmapWords(header_->bitmap_); | |
| 134 | 184340 | const int n_words = concurrent_slab_detail::BitmapNumWords(nr_entries); | |
| 135 | 184340 | int& word_hint = concurrent_slab_detail::AllocWordHintTls(); | |
| 136 |
1/2✓ Branch 0 taken 184340 times.
✗ Branch 1 not taken.
|
368680 | const int entry_id = concurrent_slab_detail::TryAllocFromBitmap( |
| 137 | 184340 | words, n_words, n_words > 0 ? word_hint % n_words : 0); | |
| 138 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 184340 times.
|
184340 | if (entry_id < 0) { |
| 139 | ✗ | return nullptr; | |
| 140 | } | ||
| 141 | 184340 | word_hint = (entry_id / 64 + 1) % n_words; | |
| 142 | 184340 | allocated_entries_.fetch_add(1, std::memory_order_relaxed); | |
| 143 | 184340 | return Entry(entry_id); | |
| 144 | } | ||
| 145 | |||
| 146 | // Returns true if the chunk was full before this free (now has free slots). | ||
| 147 | 124620 | bool Free(void* memory_data) { | |
| 148 |
2/12✗ Branch 1 not taken.
✓ Branch 2 taken 124620 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
✗ Branch 10 not taken.
✗ Branch 11 not taken.
✗ Branch 14 not taken.
✓ Branch 15 taken 124620 times.
✗ Branch 17 not taken.
✗ Branch 18 not taken.
|
124620 | CHECK(IsActivated()); |
| 149 | 124620 | const int nr_entries = header_->nr_entries_; | |
| 150 | 124620 | const bool was_full = | |
| 151 | 124620 | allocated_entries_.load(std::memory_order_relaxed) >= nr_entries; | |
| 152 | 124620 | const int entry_id = EntryId(memory_data); | |
| 153 | 124620 | uint64_t* words = concurrent_slab_detail::BitmapWords(header_->bitmap_); | |
| 154 |
2/10✗ Branch 1 not taken.
✓ Branch 2 taken 124620 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
✗ Branch 10 not taken.
✓ Branch 11 taken 124620 times.
✗ Branch 13 not taken.
✗ Branch 14 not taken.
|
124620 | CHECK(concurrent_slab_detail::TryFreeBitmapBit(words, entry_id)) |
| 155 | ✗ | << "double free or corrupt pointer in chunk " << chunk_id_; | |
| 156 | 124620 | allocated_entries_.fetch_sub(1, std::memory_order_relaxed); | |
| 157 | 124620 | return was_full; | |
| 158 | } | ||
| 159 | |||
| 160 | 2 | bool TryMarkListedInPartial() { | |
| 161 | 2 | bool expected = false; | |
| 162 | 2 | return listed_in_partial_.compare_exchange_strong( | |
| 163 | 2 | expected, true, std::memory_order_relaxed); | |
| 164 | } | ||
| 165 | |||
| 166 | 964 | void ClearListedInPartial() { | |
| 167 | 964 | listed_in_partial_.store(false, std::memory_order_relaxed); | |
| 168 | 964 | } | |
| 169 | |||
| 170 | 433580 | int SlabSize() const { return header_->slab_size_; } | |
| 171 | |||
| 172 | ✗ | int AllocatedEntryNumber() const { | |
| 173 | ✗ | return allocated_entries_.load(std::memory_order_relaxed); | |
| 174 | } | ||
| 175 | |||
| 176 | ✗ | std::vector<char*> GetMallocedData() const { | |
| 177 | ✗ | std::vector<char*> return_data; | |
| 178 | ✗ | if (!IsActivated()) { | |
| 179 | ✗ | return return_data; | |
| 180 | } | ||
| 181 | ✗ | for (int i = 0; i < header_->nr_entries_; ++i) { | |
| 182 | ✗ | if (header_->bitmap_->Get(i)) { | |
| 183 | ✗ | return_data.push_back(Entry(i)); | |
| 184 | } | ||
| 185 | } | ||
| 186 | ✗ | return return_data; | |
| 187 | ✗ | } | |
| 188 | |||
| 189 | uint64_t chunk_id() const { return chunk_id_; } | ||
| 190 | |||
| 191 | private: | ||
| 192 | 124620 | int EntryId(void* memory_data) const { | |
| 193 | return static_cast<int>( | ||
| 194 | 124620 | (reinterpret_cast<char*>(memory_data) - data_) / SlabSize()); | |
| 195 | } | ||
| 196 | |||
| 197 | 184340 | char* Entry(int entry_id) const { return data_ + entry_id * SlabSize(); } | |
| 198 | |||
| 199 | struct ChunkHeader { | ||
| 200 | int slab_size_ = 0; | ||
| 201 | int nr_entries_ = 0; | ||
| 202 | base::BitMap bitmap_[0]; | ||
| 203 | |||
| 204 | 964 | size_t HeaderSize() const { | |
| 205 | 964 | return sizeof(ChunkHeader) + base::BitMap::MemorySize(nr_entries_); | |
| 206 | } | ||
| 207 | |||
| 208 | 1054 | static size_t HeaderSize(int nr_entries) { | |
| 209 | 1054 | return sizeof(ChunkHeader) + base::BitMap::MemorySize(nr_entries); | |
| 210 | } | ||
| 211 | |||
| 212 | DISALLOW_COPY_AND_ASSIGN(ChunkHeader); | ||
| 213 | }; | ||
| 214 | |||
| 215 | ChunkHeader* header_; | ||
| 216 | char* data_; | ||
| 217 | uint64_t chunk_id_; | ||
| 218 | std::atomic<int> allocated_entries_; | ||
| 219 | std::atomic<bool> listed_in_partial_; | ||
| 220 | DISALLOW_COPY_AND_ASSIGN(SlabChunk); | ||
| 221 | }; | ||
| 222 | |||
| 223 | struct SlabState { | ||
| 224 | base::Lock lock; | ||
| 225 | std::deque<SlabChunk*> partial; | ||
| 226 | std::deque<SlabChunk*> active; | ||
| 227 | }; | ||
| 228 | |||
| 229 | struct ThreadLocalPool { | ||
| 230 | std::unordered_map<int, SlabChunk*> hot_by_slab; | ||
| 231 | }; | ||
| 232 | |||
| 233 | 309208 | static ThreadLocalPool& PoolTls() { | |
| 234 |
2/2✓ Branch 0 taken 500 times.
✓ Branch 1 taken 308708 times.
|
309208 | thread_local ThreadLocalPool tls; |
| 235 | 309208 | return tls; | |
| 236 | } | ||
| 237 | |||
| 238 | public: | ||
| 239 | 262 | ConcurrentSlabMemoryPool(const std::string& filename, | |
| 240 | int64 memory_size, | ||
| 241 | const std::vector<int>& slab_sizes) | ||
| 242 |
2/4✓ Branch 4 taken 262 times.
✗ Branch 5 not taken.
✓ Branch 11 taken 262 times.
✗ Branch 12 not taken.
|
262 | : allocated_slab_sizes_(slab_sizes.begin(), slab_sizes.end()) { |
| 243 |
2/4✓ Branch 1 taken 262 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 262 times.
|
262 | if (base::file_util::PathExists(filename)) { |
| 244 | ✗ | CHECK(base::file_util::Delete(filename, false)); | |
| 245 | } | ||
| 246 |
3/6✓ Branch 2 taken 262 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 262 times.
✗ Branch 6 not taken.
✓ Branch 8 taken 262 times.
✗ Branch 9 not taken.
|
262 | shm_file_ = |
| 247 | ShmFile::New(ShmFile::ConfigForMedium("DRAM", filename, memory_size)); | ||
| 248 |
2/18✗ Branch 1 not taken.
✓ Branch 2 taken 262 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
✗ Branch 10 not taken.
✗ Branch 11 not taken.
✗ Branch 13 not taken.
✗ Branch 14 not taken.
✗ Branch 16 not taken.
✗ Branch 17 not taken.
✗ Branch 19 not taken.
✗ Branch 20 not taken.
✗ Branch 23 not taken.
✓ Branch 24 taken 262 times.
✗ Branch 26 not taken.
✗ Branch 27 not taken.
|
262 | CHECK(shm_file_) << filename << " " << memory_size; |
| 249 | |||
| 250 | 262 | const int64 aligned_size = | |
| 251 | 262 | memory_size - (memory_size % static_cast<int64>(kChunkSize)); | |
| 252 | 262 | nr_chunks_ = aligned_size / static_cast<int64>(kChunkSize); | |
| 253 |
2/8✓ Branch 3 taken 262 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✓ Branch 6 taken 262 times.
✗ Branch 9 not taken.
✗ Branch 10 not taken.
✗ Branch 12 not taken.
✗ Branch 13 not taken.
|
262 | CHECK_GT(nr_chunks_, 0); |
| 254 | |||
| 255 |
1/2✓ Branch 1 taken 262 times.
✗ Branch 2 not taken.
|
262 | chunks_.reserve(static_cast<size_t>(nr_chunks_)); |
| 256 |
2/2✓ Branch 0 taken 26268 times.
✓ Branch 1 taken 262 times.
|
26530 | for (int64 i = 0; i < nr_chunks_; ++i) { |
| 257 | 26268 | auto* chunk = new SlabChunk( | |
| 258 |
1/2✓ Branch 3 taken 26268 times.
✗ Branch 4 not taken.
|
26268 | shm_file_->Data() + i * kChunkSize, static_cast<uint64_t>(i)); |
| 259 | 26268 | chunk->Initialize(); | |
| 260 |
1/2✓ Branch 1 taken 26268 times.
✗ Branch 2 not taken.
|
26268 | chunks_.push_back(chunk); |
| 261 |
1/2✓ Branch 1 taken 26268 times.
✗ Branch 2 not taken.
|
26268 | free_chunks_.push_back(chunk); |
| 262 | } | ||
| 263 | |||
| 264 |
2/2✓ Branch 5 taken 1310 times.
✓ Branch 6 taken 262 times.
|
1572 | for (int slab : slab_sizes) { |
| 265 |
1/2✓ Branch 1 taken 1310 times.
✗ Branch 2 not taken.
|
1310 | (void)slab_states_[slab]; |
| 266 | } | ||
| 267 | |||
| 268 |
4/8✓ Branch 1 taken 262 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 262 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 262 times.
✗ Branch 8 not taken.
✓ Branch 10 taken 262 times.
✗ Branch 11 not taken.
|
524 | LOG(INFO) << "ConcurrentSlabMemoryPool: initialized " << nr_chunks_ |
| 269 |
3/6✓ Branch 1 taken 262 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 262 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 262 times.
✗ Branch 8 not taken.
|
262 | << " chunks of " << kChunkSize << " bytes."; |
| 270 | 262 | } | |
| 271 | |||
| 272 | 262 | ~ConcurrentSlabMemoryPool() override { | |
| 273 |
2/2✓ Branch 4 taken 26268 times.
✓ Branch 5 taken 262 times.
|
26530 | for (auto* chunk : chunks_) { |
| 274 |
1/2✓ Branch 0 taken 26268 times.
✗ Branch 1 not taken.
|
26268 | delete chunk; |
| 275 | } | ||
| 276 | 524 | } | |
| 277 | |||
| 278 | 184340 | char* New(int memory_size) override { | |
| 279 | if (PERFECT_FIT_MOD) { | ||
| 280 | return NewInternal(memory_size); | ||
| 281 | } | ||
| 282 |
1/2✓ Branch 1 taken 184340 times.
✗ Branch 2 not taken.
|
184340 | auto iter = allocated_slab_sizes_.lower_bound(kMetaDataSize + memory_size); |
| 283 |
2/12✗ Branch 2 not taken.
✓ Branch 3 taken 184340 times.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✗ Branch 8 not taken.
✗ Branch 9 not taken.
✗ Branch 11 not taken.
✗ Branch 12 not taken.
✗ Branch 15 not taken.
✓ Branch 16 taken 184340 times.
✗ Branch 18 not taken.
✗ Branch 19 not taken.
|
184340 | CHECK(iter != allocated_slab_sizes_.end()); |
| 284 |
1/2✓ Branch 2 taken 184340 times.
✗ Branch 3 not taken.
|
184340 | char* ptr = NewInternal(*iter); |
| 285 | 184340 | *reinterpret_cast<int*>(ptr) = memory_size; | |
| 286 | 184340 | return ptr + kMetaDataSize; | |
| 287 | } | ||
| 288 | |||
| 289 | 124620 | bool Free(void* memory_data) override { | |
| 290 | if (!PERFECT_FIT_MOD) { | ||
| 291 | 124620 | memory_data = static_cast<char*>(memory_data) - kMetaDataSize; | |
| 292 | } | ||
| 293 | |||
| 294 |
1/2✓ Branch 1 taken 124620 times.
✗ Branch 2 not taken.
|
124620 | const int64 chunk_id = GetChunkID(memory_data); |
| 295 |
2/4✓ Branch 0 taken 124620 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 124620 times.
|
124620 | if (chunk_id < 0 || chunk_id >= nr_chunks_) { |
| 296 | ✗ | return false; | |
| 297 | } | ||
| 298 | 124620 | SlabChunk* chunk = chunks_[static_cast<size_t>(chunk_id)]; | |
| 299 |
1/2✓ Branch 1 taken 124620 times.
✗ Branch 2 not taken.
|
124620 | const bool was_full = chunk->Free(memory_data); |
| 300 | 124620 | const int slab_size = chunk->SlabSize(); | |
| 301 | 124620 | ThreadLocalPool& tls = PoolTls(); | |
| 302 |
1/2✓ Branch 1 taken 124620 times.
✗ Branch 2 not taken.
|
124620 | SlabChunk*& hot = tls.hot_by_slab[slab_size]; |
| 303 |
2/6✗ Branch 0 not taken.
✓ Branch 1 taken 124620 times.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✓ Branch 6 taken 124620 times.
|
124620 | if (hot == nullptr && !chunk->Full()) { |
| 304 | ✗ | chunk->ClearListedInPartial(); | |
| 305 | ✗ | hot = chunk; | |
| 306 |
2/2✓ Branch 0 taken 2 times.
✓ Branch 1 taken 124618 times.
|
124620 | } else if (was_full) { |
| 307 |
1/2✓ Branch 1 taken 2 times.
✗ Branch 2 not taken.
|
2 | TryEnqueuePartial(slab_size, chunk); |
| 308 | } | ||
| 309 | 124620 | total_malloc_.fetch_sub(1, std::memory_order_relaxed); | |
| 310 | 124620 | return true; | |
| 311 | } | ||
| 312 | |||
| 313 | ✗ | void GetMallocsAppend(std::vector<char*>* mallocs_data) const override { | |
| 314 | ✗ | for (auto* chunk : chunks_) { | |
| 315 | ✗ | for (char* each : chunk->GetMallocedData()) { | |
| 316 | if (PERFECT_FIT_MOD) { | ||
| 317 | mallocs_data->push_back(each); | ||
| 318 | } else { | ||
| 319 | ✗ | mallocs_data->push_back(each + kMetaDataSize); | |
| 320 | } | ||
| 321 | } | ||
| 322 | } | ||
| 323 | ✗ | } | |
| 324 | |||
| 325 | ✗ | void GetMallocsAppend(std::vector<int64>* mallocs_offset) const override { | |
| 326 | ✗ | std::vector<char*> mallocs_data; | |
| 327 | ✗ | GetMallocsAppend(&mallocs_data); | |
| 328 | ✗ | for (char* each : mallocs_data) { | |
| 329 | ✗ | mallocs_offset->push_back(each - shm_file_->Data()); | |
| 330 | } | ||
| 331 | ✗ | } | |
| 332 | |||
| 333 | 248 | void Initialize() override { | |
| 334 |
2/2✓ Branch 5 taken 23180 times.
✓ Branch 6 taken 248 times.
|
23428 | for (auto* chunk : chunks_) { |
| 335 | 23180 | chunk->Initialize(); | |
| 336 | } | ||
| 337 | 248 | free_chunks_.clear(); | |
| 338 |
2/2✓ Branch 5 taken 23180 times.
✓ Branch 6 taken 248 times.
|
23428 | for (auto* chunk : chunks_) { |
| 339 |
1/2✓ Branch 1 taken 23180 times.
✗ Branch 2 not taken.
|
23180 | free_chunks_.push_back(chunk); |
| 340 | } | ||
| 341 |
2/2✓ Branch 7 taken 1240 times.
✓ Branch 8 taken 248 times.
|
1488 | for (auto& [slab, state] : slab_states_) { |
| 342 | (void)slab; | ||
| 343 | 1240 | state.partial.clear(); | |
| 344 | 1240 | state.active.clear(); | |
| 345 | } | ||
| 346 | 248 | PoolTls().hot_by_slab.clear(); | |
| 347 | 248 | total_malloc_.store(0, std::memory_order_relaxed); | |
| 348 | 248 | } | |
| 349 | |||
| 350 | ✗ | char* BackingData() const override { return shm_file_->Data(); } | |
| 351 | ✗ | int64 BackingSize() const override { | |
| 352 | ✗ | return nr_chunks_ * static_cast<int64>(kChunkSize); | |
| 353 | } | ||
| 354 | |||
| 355 | ✗ | std::string GetInfo() const override { | |
| 356 | ✗ | uint64_t malloced_bytes = 0; | |
| 357 | ✗ | uint64_t malloced_chunk = 0; | |
| 358 | ✗ | for (auto* each : chunks_) { | |
| 359 | ✗ | if (each->IsActivated()) { | |
| 360 | ✗ | malloced_bytes += static_cast<uint64_t>(each->AllocatedEntryNumber()) * | |
| 361 | ✗ | each->SlabSize(); | |
| 362 | ✗ | malloced_chunk++; | |
| 363 | } | ||
| 364 | } | ||
| 365 | return base::SFormat( | ||
| 366 | "[ConcurrentSlabMemoryPool] " | ||
| 367 | "Use {} of {} chunks, Util {} %", | ||
| 368 | malloced_chunk, | ||
| 369 | ✗ | chunks_.size(), | |
| 370 | ✗ | chunks_.empty() ? 0 | |
| 371 | ✗ | : 100 * malloced_bytes / (kChunkSize * chunks_.size())); | |
| 372 | } | ||
| 373 | |||
| 374 | 392856 | char* GetMallocData(int64 offset) const override { | |
| 375 | 392856 | return shm_file_->Data() + offset; | |
| 376 | } | ||
| 377 | |||
| 378 | 147804 | int GetMallocSize(int64 offset) const override { | |
| 379 | 147804 | return GetMallocSize(GetMallocData(offset)); | |
| 380 | } | ||
| 381 | |||
| 382 | 111938 | int64 GetMallocOffset(const char* data) const override { | |
| 383 | 111938 | const auto ret = data - shm_file_->Data(); | |
| 384 |
2/8✓ Branch 3 taken 111938 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✓ Branch 6 taken 111938 times.
✗ Branch 9 not taken.
✗ Branch 10 not taken.
✗ Branch 12 not taken.
✗ Branch 13 not taken.
|
111938 | CHECK_EQ((ret >> 3) << 3, ret); |
| 385 | 111938 | return ret; | |
| 386 | } | ||
| 387 | |||
| 388 | 217006 | int GetMallocSize(const char* data) const override { | |
| 389 | if (PERFECT_FIT_MOD) { | ||
| 390 | return chunks_[static_cast<size_t>(GetChunkID(data))]->SlabSize(); | ||
| 391 | } | ||
| 392 | 217006 | return *reinterpret_cast<const int*>(data - kMetaDataSize); | |
| 393 | } | ||
| 394 | |||
| 395 | 8 | uint64_t total_malloc() const override { | |
| 396 | 16 | return static_cast<uint64_t>(total_malloc_.load(std::memory_order_relaxed)); | |
| 397 | } | ||
| 398 | |||
| 399 | ✗ | bool Healthy() const override { return true; } | |
| 400 | |||
| 401 | ✗ | void AddMallocs4Recovery(int64_t /*shm_offset*/) override { | |
| 402 | ✗ | RECSTORE_LOG_EVERY_MS(ERROR, 1000) << "AddMallocs4Recovery not implement"; | |
| 403 | ✗ | } | |
| 404 | |||
| 405 | private: | ||
| 406 | ✗ | void AbandonHotChunk(int slab_size, SlabChunk*& hot) { | |
| 407 | ✗ | SlabChunk* abandoned = hot; | |
| 408 | ✗ | hot = nullptr; | |
| 409 | ✗ | if (abandoned != nullptr && !abandoned->Full()) { | |
| 410 | ✗ | TryEnqueuePartial(slab_size, abandoned); | |
| 411 | } | ||
| 412 | ✗ | } | |
| 413 | |||
| 414 | 2 | void TryEnqueuePartial(int slab_size, SlabChunk* chunk) { | |
| 415 |
4/8✓ Branch 0 taken 2 times.
✗ Branch 1 not taken.
✓ Branch 3 taken 2 times.
✗ Branch 4 not taken.
✗ Branch 6 not taken.
✓ Branch 7 taken 2 times.
✗ Branch 8 not taken.
✓ Branch 9 taken 2 times.
|
2 | if (chunk == nullptr || chunk->Full() || !chunk->TryMarkListedInPartial()) { |
| 416 | ✗ | return; | |
| 417 | } | ||
| 418 |
1/2✓ Branch 1 taken 2 times.
✗ Branch 2 not taken.
|
2 | auto state_it = slab_states_.find(slab_size); |
| 419 |
2/12✗ Branch 2 not taken.
✓ Branch 3 taken 2 times.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✗ Branch 8 not taken.
✗ Branch 9 not taken.
✗ Branch 11 not taken.
✗ Branch 12 not taken.
✗ Branch 15 not taken.
✓ Branch 16 taken 2 times.
✗ Branch 18 not taken.
✗ Branch 19 not taken.
|
2 | CHECK(state_it != slab_states_.end()); |
| 420 |
1/2✓ Branch 2 taken 2 times.
✗ Branch 3 not taken.
|
2 | base::AutoLock slab_lock(state_it->second.lock); |
| 421 |
1/2✗ Branch 1 not taken.
✓ Branch 2 taken 2 times.
|
2 | if (chunk->Full()) { |
| 422 | ✗ | chunk->ClearListedInPartial(); | |
| 423 | ✗ | return; | |
| 424 | } | ||
| 425 |
1/2✓ Branch 2 taken 2 times.
✗ Branch 3 not taken.
|
2 | state_it->second.partial.push_back(chunk); |
| 426 |
1/2✓ Branch 1 taken 2 times.
✗ Branch 2 not taken.
|
2 | } |
| 427 | |||
| 428 | 184340 | char* NewInternal(int slab_size) { | |
| 429 | 184340 | ThreadLocalPool& tls = PoolTls(); | |
| 430 | 184340 | SlabChunk*& hot = tls.hot_by_slab[slab_size]; | |
| 431 | |||
| 432 | ✗ | while (true) { | |
| 433 |
6/6✓ Branch 0 taken 183378 times.
✓ Branch 1 taken 962 times.
✓ Branch 3 taken 183376 times.
✓ Branch 4 taken 2 times.
✓ Branch 5 taken 183376 times.
✓ Branch 6 taken 964 times.
|
184340 | if (hot != nullptr && !hot->Full()) { |
| 434 | 183376 | char* ptr = hot->Malloc(); | |
| 435 |
1/2✓ Branch 0 taken 183376 times.
✗ Branch 1 not taken.
|
183376 | if (ptr != nullptr) { |
| 436 | 183376 | total_malloc_.fetch_add(1, std::memory_order_relaxed); | |
| 437 | 183376 | return ptr; | |
| 438 | } | ||
| 439 | // Another thread filled the chunk after the Full() check. | ||
| 440 | ✗ | AbandonHotChunk(slab_size, hot); | |
| 441 | } | ||
| 442 | |||
| 443 | 964 | SlabChunk* chunk = AcquireChunk(slab_size, &hot); | |
| 444 | 964 | char* ptr = chunk->Malloc(); | |
| 445 |
1/2✓ Branch 0 taken 964 times.
✗ Branch 1 not taken.
|
964 | if (ptr != nullptr) { |
| 446 | 964 | total_malloc_.fetch_add(1, std::memory_order_relaxed); | |
| 447 | 964 | return ptr; | |
| 448 | } | ||
| 449 | // The selected chunk became full after AcquireChunk() released the slab | ||
| 450 | // lock, or Full() briefly lagged behind the bitmap state. | ||
| 451 | ✗ | if (hot == chunk) { | |
| 452 | ✗ | AbandonHotChunk(slab_size, hot); | |
| 453 | } | ||
| 454 | } | ||
| 455 | } | ||
| 456 | |||
| 457 | 964 | SlabChunk* AcquireChunk(int slab_size, SlabChunk** hot_slot) { | |
| 458 |
1/2✓ Branch 1 taken 964 times.
✗ Branch 2 not taken.
|
964 | auto state_it = slab_states_.find(slab_size); |
| 459 |
2/12✗ Branch 2 not taken.
✓ Branch 3 taken 964 times.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✗ Branch 8 not taken.
✗ Branch 9 not taken.
✗ Branch 11 not taken.
✗ Branch 12 not taken.
✗ Branch 15 not taken.
✓ Branch 16 taken 964 times.
✗ Branch 18 not taken.
✗ Branch 19 not taken.
|
964 | CHECK(state_it != slab_states_.end()); |
| 460 | 964 | SlabState& state = state_it->second; | |
| 461 | |||
| 462 |
1/2✓ Branch 1 taken 964 times.
✗ Branch 2 not taken.
|
964 | base::AutoLock slab_lock(state.lock); |
| 463 | |||
| 464 | 964 | SlabChunk*& hot = *hot_slot; | |
| 465 |
5/6✓ Branch 0 taken 2 times.
✓ Branch 1 taken 962 times.
✓ Branch 3 taken 2 times.
✗ Branch 4 not taken.
✓ Branch 5 taken 2 times.
✓ Branch 6 taken 962 times.
|
964 | if (hot != nullptr && hot->Full()) { |
| 466 | 2 | hot = nullptr; | |
| 467 | } | ||
| 468 | |||
| 469 |
1/2✗ Branch 1 not taken.
✓ Branch 2 taken 964 times.
|
964 | while (!state.partial.empty()) { |
| 470 | ✗ | SlabChunk* chunk = state.partial.front(); | |
| 471 | ✗ | state.partial.pop_front(); | |
| 472 | ✗ | chunk->ClearListedInPartial(); | |
| 473 | ✗ | if (chunk->Full()) { | |
| 474 | ✗ | continue; | |
| 475 | } | ||
| 476 | ✗ | chunk->ClearListedInPartial(); | |
| 477 | ✗ | hot = chunk; | |
| 478 | ✗ | return chunk; | |
| 479 | } | ||
| 480 | |||
| 481 | { | ||
| 482 |
1/2✓ Branch 1 taken 964 times.
✗ Branch 2 not taken.
|
964 | base::AutoLock free_lock(free_chunks_lock_); |
| 483 |
1/2✓ Branch 1 taken 964 times.
✗ Branch 2 not taken.
|
964 | if (!free_chunks_.empty()) { |
| 484 | 964 | SlabChunk* chunk = free_chunks_.front(); | |
| 485 | 964 | free_chunks_.pop_front(); | |
| 486 |
1/2✓ Branch 1 taken 964 times.
✗ Branch 2 not taken.
|
964 | chunk->Use(slab_size); |
| 487 |
1/2✓ Branch 1 taken 964 times.
✗ Branch 2 not taken.
|
964 | state.active.push_back(chunk); |
| 488 | 964 | chunk->ClearListedInPartial(); | |
| 489 | 964 | hot = chunk; | |
| 490 | 964 | return chunk; | |
| 491 | } | ||
| 492 |
1/2✗ Branch 1 not taken.
✓ Branch 2 taken 964 times.
|
964 | } |
| 493 | |||
| 494 | ✗ | for (SlabChunk* chunk : state.active) { | |
| 495 | ✗ | if (!chunk->Full()) { | |
| 496 | ✗ | chunk->ClearListedInPartial(); | |
| 497 | ✗ | hot = chunk; | |
| 498 | ✗ | return chunk; | |
| 499 | } | ||
| 500 | } | ||
| 501 | |||
| 502 | ✗ | LOG(FATAL) << fmt::format( | |
| 503 | "ConcurrentSlabMemoryPool OOM, slab_size={}, total_malloc={}", | ||
| 504 | slab_size, | ||
| 505 | ✗ | total_malloc_.load(std::memory_order_relaxed)); | |
| 506 | return nullptr; | ||
| 507 | 964 | } | |
| 508 | |||
| 509 | 124620 | int64 GetChunkID(const void* data) const { | |
| 510 | 124620 | return GetChunkID(static_cast<const char*>(data) - shm_file_->Data()); | |
| 511 | } | ||
| 512 | |||
| 513 | 124620 | int64 GetChunkID(int64 offset) const { | |
| 514 | 124620 | return offset / static_cast<int64>(kChunkSize); | |
| 515 | } | ||
| 516 | |||
| 517 | std::unique_ptr<ShmFile> shm_file_; | ||
| 518 | int64 nr_chunks_ = 0; | ||
| 519 | std::vector<SlabChunk*> chunks_; | ||
| 520 | std::deque<SlabChunk*> free_chunks_; | ||
| 521 | base::Lock free_chunks_lock_; | ||
| 522 | std::unordered_map<int, SlabState> slab_states_; | ||
| 523 | std::set<int> allocated_slab_sizes_; | ||
| 524 | std::atomic<int64> total_malloc_{0}; | ||
| 525 | DISALLOW_COPY_AND_ASSIGN(ConcurrentSlabMemoryPool); | ||
| 526 | }; | ||
| 527 | |||
| 528 | class ConcurrentSlabMemoryPoolMalloc : public ConcurrentSlabMemoryPool<false> { | ||
| 529 | public: | ||
| 530 | 262 | ConcurrentSlabMemoryPoolMalloc(const std::string& filename, | |
| 531 | int64 memory_size, | ||
| 532 | const std::string& /*medium*/) | ||
| 533 | 262 | : ConcurrentSlabMemoryPool<false>( | |
| 534 | filename, | ||
| 535 | memory_size, | ||
| 536 |
2/4✓ Branch 2 taken 262 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 262 times.
✗ Branch 6 not taken.
|
262 | {8 + 32, 8 + 64, 8 + 128, 8 + 512, 8 + 1024}) {} |
| 537 | }; | ||
| 538 | |||
| 539 | FACTORY_REGISTER(MallocApi, | ||
| 540 | CONCURRENT_SLAB_MEMORY_POOL, | ||
| 541 | ConcurrentSlabMemoryPoolMalloc, | ||
| 542 | const std::string&, | ||
| 543 | int64, | ||
| 544 | const std::string&); | ||
| 545 | |||
| 546 | } // namespace base | ||
| 547 |