GCC Code Coverage Report

src/
Coverage:
low: ≥ 0%
medium: ≥ 75.0%
high: ≥ 90.0%
Lines:
242 / 317
76.3%
Branches:
129 / 374
34.5%
Functions:
42 / 50
84.0%
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 339542 inline uint64_t* BitmapWords(base::BitMap* bitmap) {
27 return reinterpret_cast<uint64_t*>(
28 339542 reinterpret_cast<char*>(bitmap) + sizeof(base::BitMap));
29 }
30
31 199656 inline int BitmapNumWords(int nr_entries) { return nr_entries / 64; }
32
33 199656 inline int& AllocWordHintTls() {
34 thread_local int hint = 0;
35 199656 return hint;
36 }
37
38 inline int
39 199656 TryAllocFromBitmap(uint64_t* words, int n_words, int start_word = 0) {
40
1/2
✓ Branch 0 taken 199656 times.
✗ Branch 1 not taken.
 199656 for (int w = 0; w < n_words; ++w) {
41 199656 const int i = (start_word + w) % n_words;
42 199656 uint64_t old = words[i];
43 while (true) {
44 199656 const uint64_t inv = ~old;
45
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 199656 times.
 199656 if (!inv) {
46 ✗ break;
47 }
48 199656 const uint64_t pos = static_cast<uint64_t>(__builtin_ctzll(inv));
49 199656 const uint64_t desired = old | (1ull << pos);
50
1/2
✓ Branch 0 taken 199656 times.
✗ Branch 1 not taken.
 199656 if (__sync_bool_compare_and_swap(&words[i], old, desired)) {
51 199656 return i * 64 + static_cast<int>(pos);
52 }
53 ✗ old = words[i];
54 ✗ }
55 }
56 ✗ return -1;
57 }
58
59 139886 inline bool TryFreeBitmapBit(uint64_t* words, int bit) {
60 139886 const int i = bit / 64;
61 139886 const int pos = bit % 64;
62 139886 const uint64_t clear_mask = ~(1ull << pos);
63 139886 uint64_t old = words[i];
64 while (true) {
65
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 139886 times.
 139886 if ((old & (1ull << pos)) == 0) {
66 ✗ return false;
67 }
68 139886 const uint64_t desired = old & clear_mask;
69
1/2
✓ Branch 0 taken 139886 times.
✗ Branch 1 not taken.
 139886 if (__sync_bool_compare_and_swap(&words[i], old, desired)) {
70 139886 return true;
71 }
72 ✗ old = words[i];
73 ✗ }
74 }
75
76 // Size classes for the legacy (8-byte metadata + payload) layout. The
77 // `8 + dim * 4` widths cover embedding rows: 8+80 serves a dim-20 row and
78 // 8+272 serves a dim-68 row, which would otherwise round up to 136 / 520.
79 302 inline const std::vector<int>& DefaultSlabSizeClasses() {
80 static const std::vector<int> kClasses = {
81
4/8
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 298 times.
✓ Branch 3 taken 4 times.
✗ Branch 4 not taken.
✓ Branch 7 taken 4 times.
✗ Branch 8 not taken.
✗ Branch 13 not taken.
✗ Branch 14 not taken.
 302 8 + 32, 8 + 64, 8 + 80, 8 + 128, 8 + 272, 8 + 512, 8 + 1024};
82 302 return kClasses;
83 }
84
85 } // namespace concurrent_slab_detail
86
87 template <bool PERFECT_FIT_MOD = true>
88 class ConcurrentSlabMemoryPool : public MallocApi {
89 static constexpr uint64_t kChunkSize = 1 * 1024 * 1024ULL;
90 static constexpr int kMetaDataSize = 8;
91
92 class SlabChunk {
93 public:
94 29346 SlabChunk(char* chunk_start, uint64_t chunk_id)
95 29346 : header_(reinterpret_cast<ChunkHeader*>(chunk_start)),
96 29346 data_(nullptr),
97 29346 chunk_id_(chunk_id),
98 29346 allocated_entries_(0),
99 29346 listed_in_partial_(false) {}
100
101 53884 void Initialize() {
102 53884 header_->slab_size_ = 0;
103 53884 header_->nr_entries_ = 0;
104 53884 data_ = nullptr;
105 53884 allocated_entries_.store(0, std::memory_order_relaxed);
106 53884 listed_in_partial_.store(false, std::memory_order_relaxed);
107 53884 }
108
109 1010 void Use(int slab_size) {
110
1/6
✗ Branch 3 not taken.
✓ Branch 4 taken 1010 times.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
✗ Branch 10 not taken.
✗ Branch 11 not taken.
 1010 CHECK_EQ(header_->slab_size_, 0)
111
0/6
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
 ✗ << "chunk " << chunk_id_ << " already bound to slab "
112
0/2
✗ Branch 1 not taken.
✗ Branch 2 not taken.
 ✗ << header_->slab_size_;
113
114 1010 int nr_entries = static_cast<int>(kChunkSize / slab_size);
115 1010 nr_entries -= (nr_entries % 64);
116
117
2/2
✓ Branch 1 taken 94 times.
✓ Branch 2 taken 1010 times.
 1104 while (ChunkHeader::HeaderSize(nr_entries) + nr_entries * slab_size >
118 kChunkSize) {
119 94 nr_entries -= 64;
120 }
121
1/6
✗ Branch 3 not taken.
✓ Branch 4 taken 1010 times.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
✗ Branch 10 not taken.
✗ Branch 11 not taken.
 1010 CHECK_GT(nr_entries, 0);
122
123 1010 header_->slab_size_ = slab_size;
124 1010 header_->nr_entries_ = nr_entries;
125
1/2
✓ Branch 2 taken 1010 times.
✗ Branch 3 not taken.
 1010 new (header_->bitmap_) base::BitMap(nr_entries);
126 1010 header_->bitmap_->Clear();
127 1010 data_ = reinterpret_cast<char*>(header_) + header_->HeaderSize();
128 1010 allocated_entries_.store(0, std::memory_order_relaxed);
129 1010 listed_in_partial_.store(false, std::memory_order_relaxed);
130 1010 }
131
132 339542 bool IsActivated() const { return header_->slab_size_ != 0; }
133
134 213866 bool Full() const {
135 213866 return allocated_entries_.load(std::memory_order_relaxed) >=
136 213866 header_->nr_entries_;
137 }
138
139 199656 char* Malloc() {
140
2/12
✗ Branch 1 not taken.
✓ Branch 2 taken 199656 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 199656 times.
✗ Branch 17 not taken.
✗ Branch 18 not taken.
 199656 CHECK(IsActivated());
141 199656 const int nr_entries = header_->nr_entries_;
142 199656 uint64_t* words = concurrent_slab_detail::BitmapWords(header_->bitmap_);
143 199656 const int n_words = concurrent_slab_detail::BitmapNumWords(nr_entries);
144 199656 int& word_hint = concurrent_slab_detail::AllocWordHintTls();
145
1/2
✓ Branch 0 taken 199656 times.
✗ Branch 1 not taken.
 399312 const int entry_id = concurrent_slab_detail::TryAllocFromBitmap(
146 199656 words, n_words, n_words > 0 ? word_hint % n_words : 0);
147
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 199656 times.
 199656 if (entry_id < 0) {
148 ✗ return nullptr;
149 }
150 199656 word_hint = (entry_id / 64 + 1) % n_words;
151 199656 allocated_entries_.fetch_add(1, std::memory_order_relaxed);
152 199656 return Entry(entry_id);
153 }
154
155 // Returns true if the chunk was full before this free (now has free slots).
156 139886 bool Free(void* memory_data) {
157
2/12
✗ Branch 1 not taken.
✓ Branch 2 taken 139886 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 139886 times.
✗ Branch 17 not taken.
✗ Branch 18 not taken.
 139886 CHECK(IsActivated());
158 139886 const int nr_entries = header_->nr_entries_;
159 139886 const bool was_full =
160 139886 allocated_entries_.load(std::memory_order_relaxed) >= nr_entries;
161 139886 const int entry_id = EntryId(memory_data);
162 139886 uint64_t* words = concurrent_slab_detail::BitmapWords(header_->bitmap_);
163
2/10
✗ Branch 1 not taken.
✓ Branch 2 taken 139886 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
✗ Branch 10 not taken.
✓ Branch 11 taken 139886 times.
✗ Branch 13 not taken.
✗ Branch 14 not taken.
 139886 CHECK(concurrent_slab_detail::TryFreeBitmapBit(words, entry_id))
164
0/6
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
 ✗ << "double free or corrupt pointer in chunk " << chunk_id_;
165 139886 allocated_entries_.fetch_sub(1, std::memory_order_relaxed);
166 139886 return was_full;
167 }
168
169 2 bool TryMarkListedInPartial() {
170 2 bool expected = false;
171 2 return listed_in_partial_.compare_exchange_strong(
172 2 expected, true, std::memory_order_relaxed);
173 }
174
175 31420 void ClearListedInPartial() {
176 31420 listed_in_partial_.store(false, std::memory_order_relaxed);
177 31420 }
178
179 479428 int SlabSize() const { return header_->slab_size_; }
180
181 ✗ int AllocatedEntryNumber() const {
182 ✗ return allocated_entries_.load(std::memory_order_relaxed);
183 }
184
185 ✗ std::vector<char*> GetMallocedData() const {
186 ✗ std::vector<char*> return_data;
187
0/2
✗ Branch 1 not taken.
✗ Branch 2 not taken.
 ✗ if (!IsActivated()) {
188 ✗ return return_data;
189 }
190
0/2
✗ Branch 0 not taken.
✗ Branch 1 not taken.
 ✗ for (int i = 0; i < header_->nr_entries_; ++i) {
191
0/2
✗ Branch 1 not taken.
✗ Branch 2 not taken.
 ✗ if (header_->bitmap_->Get(i)) {
192
0/2
✗ Branch 2 not taken.
✗ Branch 3 not taken.
 ✗ return_data.push_back(Entry(i));
193 }
194 }
195 ✗ return return_data;
196 ✗ }
197
198 uint64_t chunk_id() const { return chunk_id_; }
199
200 private:
201 139886 int EntryId(void* memory_data) const {
202 return static_cast<int>(
203 139886 (reinterpret_cast<char*>(memory_data) - data_) / SlabSize());
204 }
205
206 199656 char* Entry(int entry_id) const { return data_ + entry_id * SlabSize(); }
207
208 struct ChunkHeader {
209 int slab_size_ = 0;
210 int nr_entries_ = 0;
211 base::BitMap bitmap_[0];
212
213 1010 size_t HeaderSize() const {
214 1010 return sizeof(ChunkHeader) + base::BitMap::MemorySize(nr_entries_);
215 }
216
217 1104 static size_t HeaderSize(int nr_entries) {
218 1104 return sizeof(ChunkHeader) + base::BitMap::MemorySize(nr_entries);
219 }
220
221 DISALLOW_COPY_AND_ASSIGN(ChunkHeader);
222 };
223
224 ChunkHeader* header_;
225 char* data_;
226 uint64_t chunk_id_;
227 std::atomic<int> allocated_entries_;
228 std::atomic<bool> listed_in_partial_;
229 DISALLOW_COPY_AND_ASSIGN(SlabChunk);
230 };
231
232 struct SlabState {
233 base::Lock lock;
234 std::deque<SlabChunk*> partial;
235 std::deque<SlabChunk*> active;
236 };
237
238 struct ThreadLocalPool {
239 uint64_t generation = 0;
240 bool recover_active = false;
241 std::unordered_map<int, SlabChunk*> hot_by_slab;
242 };
243
244 572 static uint64_t NextGeneration() {
245 static std::atomic<uint64_t> next{1};
246 572 return next.fetch_add(1, std::memory_order_relaxed);
247 }
248
249 339542 ThreadLocalPool& PoolTls() {
250
2/2
✓ Branch 0 taken 508 times.
✓ Branch 1 taken 339034 times.
 339542 thread_local ThreadLocalPool tls;
251
2/2
✓ Branch 0 taken 31144 times.
✓ Branch 1 taken 308398 times.
 339542 if (tls.generation != generation_) {
252 // Cached chunks may belong to a destroyed or reinitialized pool.
253 31144 tls.recover_active = tls.generation != 0;
254 31144 tls.hot_by_slab.clear();
255 31144 tls.generation = generation_;
256 }
257 339542 return tls;
258 }
259
260 public:
261 306 ConcurrentSlabMemoryPool(const std::string& filename,
262 int64 memory_size,
263 const std::vector<int>& slab_sizes)
264
2/4
✓ Branch 5 taken 306 times.
✗ Branch 6 not taken.
✓ Branch 12 taken 306 times.
✗ Branch 13 not taken.
 306 : allocated_slab_sizes_(slab_sizes.begin(), slab_sizes.end()) {
265
3/4
✓ Branch 1 taken 306 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 4 times.
✓ Branch 4 taken 302 times.
 306 if (base::file_util::PathExists(filename)) {
266
3/14
✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 4 times.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
✗ Branch 9 not taken.
✗ Branch 10 not taken.
✗ Branch 12 not taken.
✗ Branch 13 not taken.
✗ Branch 16 not taken.
✓ Branch 17 taken 4 times.
✗ Branch 19 not taken.
✗ Branch 20 not taken.
 4 CHECK(base::file_util::Delete(filename, false));
267 }
268
3/6
✓ Branch 2 taken 306 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 306 times.
✗ Branch 6 not taken.
✓ Branch 8 taken 306 times.
✗ Branch 9 not taken.
 306 shm_file_ =
269 ShmFile::New(ShmFile::ConfigForMedium("DRAM", filename, memory_size));
270
2/18
✗ Branch 1 not taken.
✓ Branch 2 taken 306 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 306 times.
✗ Branch 26 not taken.
✗ Branch 27 not taken.
 306 CHECK(shm_file_) << filename << " " << memory_size;
271
272 306 const int64 aligned_size =
273 306 memory_size - (memory_size % static_cast<int64>(kChunkSize));
274 306 nr_chunks_ = aligned_size / static_cast<int64>(kChunkSize);
275
2/8
✓ Branch 3 taken 306 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✓ Branch 6 taken 306 times.
✗ Branch 9 not taken.
✗ Branch 10 not taken.
✗ Branch 12 not taken.
✗ Branch 13 not taken.
 306 CHECK_GT(nr_chunks_, 0);
276
277
1/2
✓ Branch 1 taken 306 times.
✗ Branch 2 not taken.
 306 chunks_.reserve(static_cast<size_t>(nr_chunks_));
278
2/2
✓ Branch 0 taken 29346 times.
✓ Branch 1 taken 306 times.
 29652 for (int64 i = 0; i < nr_chunks_; ++i) {
279 29346 auto* chunk = new SlabChunk(
280
1/2
✓ Branch 3 taken 29346 times.
✗ Branch 4 not taken.
 29346 shm_file_->Data() + i * kChunkSize, static_cast<uint64_t>(i));
281 29346 chunk->Initialize();
282
1/2
✓ Branch 1 taken 29346 times.
✗ Branch 2 not taken.
 29346 chunks_.push_back(chunk);
283
1/2
✓ Branch 1 taken 29346 times.
✗ Branch 2 not taken.
 29346 free_chunks_.push_back(chunk);
284 }
285
286
2/2
✓ Branch 5 taken 2120 times.
✓ Branch 6 taken 306 times.
 2426 for (int slab : slab_sizes) {
287
1/2
✓ Branch 1 taken 2120 times.
✗ Branch 2 not taken.
 2120 (void)slab_states_[slab];
288 }
289
290
4/8
✓ Branch 1 taken 306 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 306 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 306 times.
✗ Branch 8 not taken.
✓ Branch 10 taken 306 times.
✗ Branch 11 not taken.
 612 LOG(INFO) << "ConcurrentSlabMemoryPool: initialized " << nr_chunks_
291
3/6
✓ Branch 1 taken 306 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 306 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 306 times.
✗ Branch 8 not taken.
 306 << " chunks of " << kChunkSize << " bytes.";
292 306 }
293
294 306 ~ConcurrentSlabMemoryPool() override {
295
2/2
✓ Branch 4 taken 29346 times.
✓ Branch 5 taken 306 times.
 29652 for (auto* chunk : chunks_) {
296
1/2
✓ Branch 0 taken 29346 times.
✗ Branch 1 not taken.
 29346 delete chunk;
297 }
298 612 }
299
300 199656 char* New(int memory_size) override {
301 if (PERFECT_FIT_MOD) {
302 return NewInternal(memory_size);
303 }
304
1/2
✓ Branch 1 taken 199656 times.
✗ Branch 2 not taken.
 199656 auto iter = allocated_slab_sizes_.lower_bound(kMetaDataSize + memory_size);
305
2/12
✗ Branch 2 not taken.
✓ Branch 3 taken 199656 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 199656 times.
✗ Branch 18 not taken.
✗ Branch 19 not taken.
 199656 CHECK(iter != allocated_slab_sizes_.end());
306
1/2
✓ Branch 2 taken 199656 times.
✗ Branch 3 not taken.
 199656 char* ptr = NewInternal(*iter);
307 199656 *reinterpret_cast<int*>(ptr) = memory_size;
308 199656 return ptr + kMetaDataSize;
309 }
310
311 139886 bool Free(void* memory_data) override {
312 if (!PERFECT_FIT_MOD) {
313 139886 memory_data = static_cast<char*>(memory_data) - kMetaDataSize;
314 }
315
316
1/2
✓ Branch 1 taken 139886 times.
✗ Branch 2 not taken.
 139886 const int64 chunk_id = GetChunkID(memory_data);
317
2/4
✓ Branch 0 taken 139886 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 139886 times.
 139886 if (chunk_id < 0 || chunk_id >= nr_chunks_) {
318 ✗ return false;
319 }
320 139886 SlabChunk* chunk = chunks_[static_cast<size_t>(chunk_id)];
321
1/2
✓ Branch 1 taken 139886 times.
✗ Branch 2 not taken.
 139886 const bool was_full = chunk->Free(memory_data);
322 139886 const int slab_size = chunk->SlabSize();
323 139886 ThreadLocalPool& tls = PoolTls();
324
1/2
✓ Branch 1 taken 139886 times.
✗ Branch 2 not taken.
 139886 SlabChunk*& hot = tls.hot_by_slab[slab_size];
325
5/6
✓ Branch 0 taken 15210 times.
✓ Branch 1 taken 124676 times.
✓ Branch 3 taken 15210 times.
✗ Branch 4 not taken.
✓ Branch 5 taken 15210 times.
✓ Branch 6 taken 124676 times.
 139886 if (hot == nullptr && !chunk->Full()) {
326 15210 chunk->ClearListedInPartial();
327 15210 hot = chunk;
328
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 124674 times.
 124676 } else if (was_full) {
329
1/2
✓ Branch 1 taken 2 times.
✗ Branch 2 not taken.
 2 TryEnqueuePartial(slab_size, chunk);
330 }
331 139886 total_malloc_.fetch_sub(1, std::memory_order_relaxed);
332 139886 return true;
333 }
334
335 ✗ void GetMallocsAppend(std::vector<char*>* mallocs_data) const override {
336
0/2
✗ Branch 5 not taken.
✗ Branch 6 not taken.
 ✗ for (auto* chunk : chunks_) {
337
0/4
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
 ✗ for (char* each : chunk->GetMallocedData()) {
338 if (PERFECT_FIT_MOD) {
339 mallocs_data->push_back(each);
340 } else {
341
0/2
✗ Branch 1 not taken.
✗ Branch 2 not taken.
 ✗ mallocs_data->push_back(each + kMetaDataSize);
342 }
343 }
344 }
345 ✗ }
346
347 ✗ void GetMallocsAppend(std::vector<int64>* mallocs_offset) const override {
348 ✗ std::vector<char*> mallocs_data;
349
0/2
✗ Branch 1 not taken.
✗ Branch 2 not taken.
 ✗ GetMallocsAppend(&mallocs_data);
350
0/2
✗ Branch 4 not taken.
✗ Branch 5 not taken.
 ✗ for (char* each : mallocs_data) {
351
0/2
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 ✗ mallocs_offset->push_back(each - shm_file_->Data());
352 }
353 ✗ }
354
355 266 void Initialize() override {
356 // As with chunk reset, callers must exclude concurrent allocator access.
357
2/2
✓ Branch 5 taken 24538 times.
✓ Branch 6 taken 266 times.
 24804 for (auto* chunk : chunks_) {
358 24538 chunk->Initialize();
359 }
360 266 free_chunks_.clear();
361
2/2
✓ Branch 5 taken 24538 times.
✓ Branch 6 taken 266 times.
 24804 for (auto* chunk : chunks_) {
362
1/2
✓ Branch 1 taken 24538 times.
✗ Branch 2 not taken.
 24538 free_chunks_.push_back(chunk);
363 }
364
2/2
✓ Branch 7 taken 1862 times.
✓ Branch 8 taken 266 times.
 2128 for (auto& [slab, state] : slab_states_) {
365 (void)slab;
366 1862 state.partial.clear();
367 1862 state.active.clear();
368 }
369 266 generation_ = NextGeneration();
370 266 total_malloc_.store(0, std::memory_order_relaxed);
371 266 }
372
373 15220 char* BackingData() const override { return shm_file_->Data(); }
374 15220 int64 BackingSize() const override {
375 15220 return nr_chunks_ * static_cast<int64>(kChunkSize);
376 }
377
378 ✗ std::string GetInfo() const override {
379 ✗ uint64_t malloced_bytes = 0;
380 ✗ uint64_t malloced_chunk = 0;
381
0/2
✗ Branch 5 not taken.
✗ Branch 6 not taken.
 ✗ for (auto* each : chunks_) {
382
0/2
✗ Branch 1 not taken.
✗ Branch 2 not taken.
 ✗ if (each->IsActivated()) {
383 ✗ malloced_bytes += static_cast<uint64_t>(each->AllocatedEntryNumber()) *
384 ✗ each->SlabSize();
385 ✗ malloced_chunk++;
386 }
387 }
388 return base::SFormat(
389 "[ConcurrentSlabMemoryPool] "
390 "Use {} of {} chunks, Util {} %",
391 malloced_chunk,
392
0/2
✗ Branch 1 not taken.
✗ Branch 2 not taken.
 ✗ chunks_.size(),
393
0/2
✗ Branch 1 not taken.
✗ Branch 2 not taken.
 ✗ chunks_.empty() ? 0
394
0/2
✗ Branch 2 not taken.
✗ Branch 3 not taken.
 ✗ : 100 * malloced_bytes / (kChunkSize * chunks_.size()));
395 }
396
397 393300 char* GetMallocData(int64 offset) const override {
398 393300 return shm_file_->Data() + offset;
399 }
400
401 147978 int GetMallocSize(int64 offset) const override {
402 147978 return GetMallocSize(GetMallocData(offset));
403 }
404
405 112038 int64 GetMallocOffset(const char* data) const override {
406 112038 const auto ret = data - shm_file_->Data();
407
2/8
✓ Branch 3 taken 112038 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✓ Branch 6 taken 112038 times.
✗ Branch 9 not taken.
✗ Branch 10 not taken.
✗ Branch 12 not taken.
✗ Branch 13 not taken.
 112038 CHECK_EQ((ret >> 3) << 3, ret);
408 112038 return ret;
409 }
410
411 217188 int GetMallocSize(const char* data) const override {
412 if (PERFECT_FIT_MOD) {
413 return chunks_[static_cast<size_t>(GetChunkID(data))]->SlabSize();
414 }
415 217188 return *reinterpret_cast<const int*>(data - kMetaDataSize);
416 }
417
418 28 uint64_t total_malloc() const override {
419 56 return static_cast<uint64_t>(total_malloc_.load(std::memory_order_relaxed));
420 }
421
422 ✗ bool Healthy() const override { return true; }
423
424 ✗ void AddMallocs4Recovery(int64_t /*shm_offset*/) override {
425
0/10
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✗ 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 13 not taken.
✗ Branch 14 not taken.
 ✗ RECSTORE_LOG_EVERY_MS(ERROR, 1000) << "AddMallocs4Recovery not implement";
426 ✗ }
427
428 private:
429 ✗ void AbandonHotChunk(int slab_size, SlabChunk*& hot) {
430 ✗ SlabChunk* abandoned = hot;
431 ✗ hot = nullptr;
432
0/6
✗ Branch 0 not taken.
✗ Branch 1 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
 ✗ if (abandoned != nullptr && !abandoned->Full()) {
433 ✗ TryEnqueuePartial(slab_size, abandoned);
434 }
435 ✗ }
436
437 2 void TryEnqueuePartial(int slab_size, SlabChunk* chunk) {
438
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()) {
439 ✗ return;
440 }
441
1/2
✓ Branch 1 taken 2 times.
✗ Branch 2 not taken.
 2 auto state_it = slab_states_.find(slab_size);
442
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());
443
1/2
✓ Branch 2 taken 2 times.
✗ Branch 3 not taken.
 2 base::AutoLock slab_lock(state_it->second.lock);
444
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 2 times.
 2 if (chunk->Full()) {
445 ✗ chunk->ClearListedInPartial();
446 ✗ return;
447 }
448
1/2
✓ Branch 2 taken 2 times.
✗ Branch 3 not taken.
 2 state_it->second.partial.push_back(chunk);
449
1/2
✓ Branch 1 taken 2 times.
✗ Branch 2 not taken.
 2 }
450
451 199656 char* NewInternal(int slab_size) {
452 199656 ThreadLocalPool& tls = PoolTls();
453 199656 SlabChunk*& hot = tls.hot_by_slab[slab_size];
454
455 ✗ while (true) {
456
6/6
✓ Branch 0 taken 183448 times.
✓ Branch 1 taken 16208 times.
✓ Branch 3 taken 183446 times.
✓ Branch 4 taken 2 times.
✓ Branch 5 taken 183446 times.
✓ Branch 6 taken 16210 times.
 199656 if (hot != nullptr && !hot->Full()) {
457 183446 char* ptr = hot->Malloc();
458
1/2
✓ Branch 0 taken 183446 times.
✗ Branch 1 not taken.
 183446 if (ptr != nullptr) {
459 183446 total_malloc_.fetch_add(1, std::memory_order_relaxed);
460 183446 return ptr;
461 }
462 // Another thread filled the chunk after the Full() check.
463 ✗ AbandonHotChunk(slab_size, hot);
464 }
465
466 16210 SlabChunk* chunk = AcquireChunk(slab_size, &hot, tls.recover_active);
467 16210 char* ptr = chunk->Malloc();
468
1/2
✓ Branch 0 taken 16210 times.
✗ Branch 1 not taken.
 16210 if (ptr != nullptr) {
469 16210 total_malloc_.fetch_add(1, std::memory_order_relaxed);
470 16210 return ptr;
471 }
472 // The selected chunk became full after AcquireChunk() released the slab
473 // lock, or Full() briefly lagged behind the bitmap state.
474
0/2
✗ Branch 0 not taken.
✗ Branch 1 not taken.
 ✗ if (hot == chunk) {
475 ✗ AbandonHotChunk(slab_size, hot);
476 }
477 }
478 }
479
480 SlabChunk*
481 16210 AcquireChunk(int slab_size, SlabChunk** hot_slot, bool recover_active) {
482
1/2
✓ Branch 1 taken 16210 times.
✗ Branch 2 not taken.
 16210 auto state_it = slab_states_.find(slab_size);
483
2/12
✗ Branch 2 not taken.
✓ Branch 3 taken 16210 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 16210 times.
✗ Branch 18 not taken.
✗ Branch 19 not taken.
 16210 CHECK(state_it != slab_states_.end());
484 16210 SlabState& state = state_it->second;
485
486
1/2
✓ Branch 1 taken 16210 times.
✗ Branch 2 not taken.
 16210 base::AutoLock slab_lock(state.lock);
487
488 16210 SlabChunk*& hot = *hot_slot;
489
5/6
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 16208 times.
✓ Branch 3 taken 2 times.
✗ Branch 4 not taken.
✓ Branch 5 taken 2 times.
✓ Branch 6 taken 16208 times.
 16210 if (hot != nullptr && hot->Full()) {
490 2 hot = nullptr;
491 }
492
493
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 16210 times.
 16210 while (!state.partial.empty()) {
494 ✗ SlabChunk* chunk = state.partial.front();
495 ✗ state.partial.pop_front();
496 ✗ chunk->ClearListedInPartial();
497
0/2
✗ Branch 1 not taken.
✗ Branch 2 not taken.
 ✗ if (chunk->Full()) {
498 ✗ continue;
499 }
500 ✗ chunk->ClearListedInPartial();
501 ✗ hot = chunk;
502 ✗ return chunk;
503 }
504
505 46856 const auto reuse_active = [&]() -> SlabChunk* {
506
2/2
✓ Branch 5 taken 15202 times.
✓ Branch 6 taken 246 times.
 15448 for (SlabChunk* chunk : state.active) {
507
2/2
✓ Branch 1 taken 15200 times.
✓ Branch 2 taken 2 times.
 15202 if (!chunk->Full()) {
508 15200 chunk->ClearListedInPartial();
509 15200 hot = chunk;
510 15200 return chunk;
511 }
512 }
513 246 return nullptr;
514 };
515 // Recover discarded TLS capacity without changing fresh-thread spreading.
516
2/2
✓ Branch 0 taken 15446 times.
✓ Branch 1 taken 764 times.
 16210 if (recover_active) {
517
2/2
✓ Branch 1 taken 15200 times.
✓ Branch 2 taken 246 times.
 15446 if (SlabChunk* chunk = reuse_active()) {
518 15200 return chunk;
519 }
520 }
521
522 {
523
1/2
✓ Branch 1 taken 1010 times.
✗ Branch 2 not taken.
 1010 base::AutoLock free_lock(free_chunks_lock_);
524
1/2
✓ Branch 1 taken 1010 times.
✗ Branch 2 not taken.
 1010 if (!free_chunks_.empty()) {
525 1010 SlabChunk* chunk = free_chunks_.front();
526 1010 free_chunks_.pop_front();
527
1/2
✓ Branch 1 taken 1010 times.
✗ Branch 2 not taken.
 1010 chunk->Use(slab_size);
528
1/2
✓ Branch 1 taken 1010 times.
✗ Branch 2 not taken.
 1010 state.active.push_back(chunk);
529 1010 chunk->ClearListedInPartial();
530 1010 hot = chunk;
531 1010 return chunk;
532 }
533
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 1010 times.
 1010 }
534
535
0/2
✗ Branch 1 not taken.
✗ Branch 2 not taken.
 ✗ if (SlabChunk* chunk = reuse_active()) {
536 ✗ return chunk;
537 }
538
539
0/6
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
 ✗ LOG(FATAL) << fmt::format(
540 "ConcurrentSlabMemoryPool OOM, slab_size={}, total_malloc={}",
541 slab_size,
542
0/2
✗ Branch 2 not taken.
✗ Branch 3 not taken.
 ✗ total_malloc_.load(std::memory_order_relaxed));
543 return nullptr;
544 16210 }
545
546 139886 int64 GetChunkID(const void* data) const {
547 139886 return GetChunkID(static_cast<const char*>(data) - shm_file_->Data());
548 }
549
550 139886 int64 GetChunkID(int64 offset) const {
551 139886 return offset / static_cast<int64>(kChunkSize);
552 }
553
554 uint64_t generation_ = NextGeneration();
555 std::unique_ptr<ShmFile> shm_file_;
556 int64 nr_chunks_ = 0;
557 std::vector<SlabChunk*> chunks_;
558 std::deque<SlabChunk*> free_chunks_;
559 base::Lock free_chunks_lock_;
560 std::unordered_map<int, SlabState> slab_states_;
561 std::set<int> allocated_slab_sizes_;
562 std::atomic<int64> total_malloc_{0};
563 DISALLOW_COPY_AND_ASSIGN(ConcurrentSlabMemoryPool);
564 };
565
566 class ConcurrentSlabMemoryPoolMalloc : public ConcurrentSlabMemoryPool<false> {
567 public:
568 302 ConcurrentSlabMemoryPoolMalloc(const std::string& filename,
569 int64 memory_size,
570 const std::string& /*medium*/)
571 302 : ConcurrentSlabMemoryPool<false>(
572 filename,
573 memory_size,
574 302 concurrent_slab_detail::DefaultSlabSizeClasses()) {}
575 };
576
577 // Same pool, but the caller supplies the size-class list
578 // (value.dram_allocator.size_classes). The classes are exact minimum sizes:
579 // a request is served by the first class >= kMetaDataSize + request.
580 class ConcurrentSlabMemoryPoolSized : public ConcurrentSlabMemoryPool<false> {
581 public:
582 4 ConcurrentSlabMemoryPoolSized(const std::string& filename,
583 int64 memory_size,
584 const std::string& /*medium*/,
585 const std::vector<int>& size_classes)
586 4 : ConcurrentSlabMemoryPool<false>(
587 filename,
588 memory_size,
589 4 size_classes.empty()
590 ✗ ? concurrent_slab_detail::DefaultSlabSizeClasses()
591
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 4 times.
 4 : size_classes) {}
592 };
593
594 FACTORY_REGISTER(MallocApi,
595 CONCURRENT_SLAB_MEMORY_POOL,
596 ConcurrentSlabMemoryPoolMalloc,
597 const std::string&,
598 int64,
599 const std::string&);
600
601 // The sized variant answers the same factory key but takes an explicit
602 // size-class list; DramValueStore picks it when
603 // value.dram_allocator.size_classes is set. The registration lives in its own
604 // namespace only because FACTORY_REGISTER names its static by key.
605 namespace {
606
607 FACTORY_REGISTER(MallocApi,
608 CONCURRENT_SLAB_MEMORY_POOL,
609 ConcurrentSlabMemoryPoolSized,
610 const std::string&,
611 int64,
612 const std::string&,
613 const std::vector<int>&);
614
615 } // namespace
616
617 } // namespace base
618