Debian Codegraph @

extra/protobuf/protobuf-24.4/src/google/protobuf/arena.cc

raw
1 // Protocol Buffers - Google's data interchange format
2 // Copyright 2008 Google Inc. All rights reserved.
3 // https://developers.google.com/protocol-buffers/
4 //
5 // Redistribution and use in source and binary forms, with or without
6 // modification, are permitted provided that the following conditions are
7 // met:
8 //
9 // * Redistributions of source code must retain the above copyright
10 // notice, this list of conditions and the following disclaimer.
11 // * Redistributions in binary form must reproduce the above
12 // copyright notice, this list of conditions and the following disclaimer
13 // in the documentation and/or other materials provided with the
14 // distribution.
15 // * Neither the name of Google Inc. nor the names of its
16 // contributors may be used to endorse or promote products derived from
17 // this software without specific prior written permission.
18 //
19 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
20 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
21 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
22 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
23 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
24 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
25 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
26 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
27 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
28 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
29 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
30
31 #include "google/protobuf/arena.h"
32
33 #include <algorithm>
34 #include <atomic>
35 #include <cstddef>
36 #include <cstdint>
37 #include <limits>
38 #include <string>
39 #include <typeinfo>
40 #include <vector>
41
42 #include "absl/base/attributes.h"
43 #include "absl/container/internal/layout.h"
44 #include "absl/synchronization/mutex.h"
45 #include "google/protobuf/arena_allocation_policy.h"
46 #include "google/protobuf/arenaz_sampler.h"
47 #include "google/protobuf/port.h"
48 #include "google/protobuf/serial_arena.h"
49 #include "google/protobuf/thread_safe_arena.h"
50
51
52 #ifdef ADDRESS_SANITIZER
53 #include <sanitizer/asan_interface.h>
54 #endif // ADDRESS_SANITIZER
55
56 // Must be included last.
57 #include "google/protobuf/port_def.inc"
58
59 namespace google {
60 namespace protobuf {
61 namespace internal {
62 namespace {
63
64 #if defined(__GNUC__) && __GNUC__ >= 5
65 // kSentryArenaBlock is used for arenas which can be referenced pre-main. So,
66 // constexpr is required.
67 constexpr ArenaBlock kSentryArenaBlock;
68
69 ArenaBlock* SentryArenaBlock() {
70 // const_cast<> is okay as kSentryArenaBlock will never be mutated.
71 return const_cast<ArenaBlock*>(&kSentryArenaBlock);
72 }
73 #else
74 // TODO(b/248322260) Remove this once we're not using GCC 4.9 for tests.
75 // There is a compiler bug in this version that causes the above constexpr to
76 // fail. This version is no longer in our support window, but we use it in
77 // some of our aarch64 docker images.
78 ArenaBlock* SentryArenaBlock() {
79 static const ArenaBlock kSentryArenaBlock;
80 // const_cast<> is okay as kSentryArenaBlock will never be mutated.
81 return const_cast<ArenaBlock*>(&kSentryArenaBlock);
82 }
83 #endif
84
85 } // namespace
86
87 static SizedPtr AllocateMemory(const AllocationPolicy* policy_ptr,
88 size_t last_size, size_t min_bytes) {
89 AllocationPolicy policy; // default policy
90 if (policy_ptr) policy = *policy_ptr;
91 size_t size;
92 if (last_size != 0) {
93 // Double the current block size, up to a limit.
94 auto max_size = policy.max_block_size;
95 size = std::min(2 * last_size, max_size);
96 } else {
97 size = policy.start_block_size;
98 }
99 // Verify that min_bytes + kBlockHeaderSize won't overflow.
100 ABSL_CHECK_LE(min_bytes, std::numeric_limits<size_t>::max() -
101 SerialArena::kBlockHeaderSize);
102 size = std::max(size, SerialArena::kBlockHeaderSize + min_bytes);
103
104 if (policy.block_alloc == nullptr) {
105 return AllocateAtLeast(size);
106 }
107 return {policy.block_alloc(size), size};
108 }
109
110 class GetDeallocator {
111 public:
112 GetDeallocator(const AllocationPolicy* policy, size_t* space_allocated)
113 : dealloc_(policy ? policy->block_dealloc : nullptr),
114 space_allocated_(space_allocated) {}
115
116 void operator()(SizedPtr mem) const {
117 #ifdef ADDRESS_SANITIZER
118 // This memory was provided by the underlying allocator as unpoisoned,
119 // so return it in an unpoisoned state.
120 ASAN_UNPOISON_MEMORY_REGION(mem.p, mem.n);
121 #endif // ADDRESS_SANITIZER
122 if (dealloc_) {
123 dealloc_(mem.p, mem.n);
124 } else {
125 internal::SizedDelete(mem.p, mem.n);
126 }
127 *space_allocated_ += mem.n;
128 }
129
130 private:
131 void (*dealloc_)(void*, size_t);
132 size_t* space_allocated_;
133 };
134
135 // It is guaranteed that this is constructed in `b`. IOW, this is not the first
136 // arena and `b` cannot be sentry.
137 SerialArena::SerialArena(ArenaBlock* b, ThreadSafeArena& parent)
138 : ptr_{b->Pointer(kBlockHeaderSize + ThreadSafeArena::kSerialArenaSize)},
139 limit_{b->Limit()},
140 head_{b},
141 space_allocated_{b->size},
142 parent_{parent} {
143 ABSL_DCHECK(!b->IsSentry());
144 }
145
146 // It is guaranteed that this is the first SerialArena. Use sentry block.
147 SerialArena::SerialArena(ThreadSafeArena& parent)
148 : head_{SentryArenaBlock()}, parent_{parent} {}
149
150 // It is guaranteed that this is the first SerialArena but `b` may be user
151 // provided or newly allocated to store AllocationPolicy.
152 SerialArena::SerialArena(FirstSerialArena, ArenaBlock* b,
153 ThreadSafeArena& parent)
154 : head_{b}, space_allocated_{b->size}, parent_{parent} {
155 if (b->IsSentry()) return;
156
157 set_ptr(b->Pointer(kBlockHeaderSize));
158 limit_ = b->Limit();
159 }
160
161 std::vector<void*> SerialArena::PeekCleanupListForTesting() {
162 std::vector<void*> res;
163
164 ArenaBlock* b = head();
165 if (b->IsSentry()) return res;
166
167 const auto peek_list = [&](const char* pos, const char* end) {
168 while (pos != end) {
169 pos += cleanup::PeekNode(pos, res);
170 }
171 };
172
173 peek_list(limit_, b->Limit());
174 for (b = b->next; b; b = b->next) {
175 peek_list(reinterpret_cast<char*>(b->cleanup_nodes), b->Limit());
176 }
177 return res;
178 }
179
180 std::vector<void*> ThreadSafeArena::PeekCleanupListForTesting() {
181 return GetSerialArena()->PeekCleanupListForTesting();
182 }
183
184 void SerialArena::Init(ArenaBlock* b, size_t offset) {
185 set_ptr(b->Pointer(offset));
186 limit_ = b->Limit();
187 head_.store(b, std::memory_order_relaxed);
188 space_used_.store(0, std::memory_order_relaxed);
189 space_allocated_.store(b->size, std::memory_order_relaxed);
190 cached_block_length_ = 0;
191 cached_blocks_ = nullptr;
192 string_block_ = nullptr;
193 string_block_unused_.store(0, std::memory_order_relaxed);
194 }
195
196 SerialArena* SerialArena::New(SizedPtr mem, ThreadSafeArena& parent) {
197 ABSL_DCHECK_LE(kBlockHeaderSize + ThreadSafeArena::kSerialArenaSize, mem.n);
198 ThreadSafeArenaStats::RecordAllocateStats(parent.arena_stats_.MutableStats(),
199 /*used=*/0, /*allocated=*/mem.n,
200 /*wasted=*/0);
201 auto b = new (mem.p) ArenaBlock{nullptr, mem.n};
202 return new (b->Pointer(kBlockHeaderSize)) SerialArena(b, parent);
203 }
204
205 template <typename Deallocator>
206 SizedPtr SerialArena::Free(Deallocator deallocator) {
207 ArenaBlock* b = head();
208 SizedPtr mem = {b, b->size};
209 while (b->next) {
210 b = b->next; // We must first advance before deleting this block
211 deallocator(mem);
212 mem = {b, b->size};
213 }
214 return mem;
215 }
216
217 PROTOBUF_NOINLINE
218 void* SerialArena::AllocateAlignedFallback(size_t n) {
219 AllocateNewBlock(n);
220 return AllocateFromExisting(n);
221 }
222
223 PROTOBUF_NOINLINE
224 void* SerialArena::AllocateFromStringBlockFallback() {
225 ABSL_DCHECK_EQ(string_block_unused_.load(std::memory_order_relaxed), 0U);
226 if (string_block_) {
227 AddSpaceUsed(string_block_->effective_size());
228 }
229
230 void* ptr;
231 size_t size = StringBlock::NextSize(string_block_);
232 if (MaybeAllocateAligned(size, &ptr)) {
233 // Correct space_used_ to avoid double counting
234 AddSpaceUsed(-size);
235 string_block_ = StringBlock::Emplace(ptr, size, string_block_);
236 } else {
237 string_block_ = StringBlock::New(string_block_);
238 AddSpaceAllocated(string_block_->allocated_size());
239 }
240 size_t unused = string_block_->effective_size() - sizeof(std::string);
241 string_block_unused_.store(unused, std::memory_order_relaxed);
242 return string_block_->AtOffset(unused);
243 }
244
245 PROTOBUF_NOINLINE
246 void* SerialArena::AllocateAlignedWithCleanupFallback(
247 size_t n, size_t align, void (*destructor)(void*)) {
248 size_t required = AlignUpTo(n, align) + cleanup::Size(destructor);
249 AllocateNewBlock(required);
250 return AllocateFromExistingWithCleanupFallback(n, align, destructor);
251 }
252
253 PROTOBUF_NOINLINE
254 void SerialArena::AddCleanupFallback(void* elem, void (*destructor)(void*)) {
255 size_t required = cleanup::Size(destructor);
256 AllocateNewBlock(required);
257 AddCleanupFromExisting(elem, destructor);
258 }
259
260 void SerialArena::AllocateNewBlock(size_t n) {
261 size_t used = 0;
262 size_t wasted = 0;
263 ArenaBlock* old_head = head();
264 if (!old_head->IsSentry()) {
265 // Sync limit to block
266 old_head->cleanup_nodes = limit_;
267
268 // Record how much used in this block.
269 used = static_cast<size_t>(ptr() - old_head->Pointer(kBlockHeaderSize));
270 wasted = old_head->size - used;
271 AddSpaceUsed(used);
272 }
273
274 // TODO(sbenza): Evaluate if pushing unused space into the cached blocks is a
275 // win. In preliminary testing showed increased memory savings as expected,
276 // but with a CPU regression. The regression might have been an artifact of
277 // the microbenchmark.
278
279 auto mem = AllocateMemory(parent_.AllocPolicy(), old_head->size, n);
280 // We don't want to emit an expensive RMW instruction that requires
281 // exclusive access to a cacheline. Hence we write it in terms of a
282 // regular add.
283 AddSpaceAllocated(mem.n);
284 ThreadSafeArenaStats::RecordAllocateStats(parent_.arena_stats_.MutableStats(),
285 /*used=*/used,
286 /*allocated=*/mem.n, wasted);
287 auto* new_head = new (mem.p) ArenaBlock{old_head, mem.n};
288 set_ptr(new_head->Pointer(kBlockHeaderSize));
289 limit_ = new_head->Limit();
290 // Previous writes must take effect before writing new head.
291 head_.store(new_head, std::memory_order_release);
292
293 #ifdef ADDRESS_SANITIZER
294 ASAN_POISON_MEMORY_REGION(ptr(), limit_ - ptr());
295 #endif // ADDRESS_SANITIZER
296 }
297
298 uint64_t SerialArena::SpaceUsed() const {
299 // Note: the calculation below technically causes a race with
300 // AllocateNewBlock when called from another thread (which happens in
301 // ThreadSafeArena::SpaceUsed). However, worst-case space_used_ will have
302 // stale data and the calculation will incorrectly assume 100%
303 // usage of the *current* block.
304 // TODO(mkruskal) Consider eliminating this race in exchange for a possible
305 // performance hit on ARM (see cl/455186837).
306
307 uint64_t space_used = 0;
308 if (string_block_) {
309 size_t unused = string_block_unused_.load(std::memory_order_relaxed);
310 space_used += string_block_->effective_size() - unused;
311 }
312 const ArenaBlock* h = head_.load(std::memory_order_acquire);
313 if (h->IsSentry()) return space_used;
314
315 const uint64_t current_block_size = h->size;
316 space_used += std::min(
317 static_cast<uint64_t>(
318 ptr() - const_cast<ArenaBlock*>(h)->Pointer(kBlockHeaderSize)),
319 current_block_size);
320 return space_used + space_used_.load(std::memory_order_relaxed);
321 }
322
323 size_t SerialArena::FreeStringBlocks(StringBlock* string_block,
324 size_t unused_bytes) {
325 ABSL_DCHECK(string_block != nullptr);
326 StringBlock* next = string_block->next();
327 std::string* end = string_block->end();
328 for (std::string* s = string_block->AtOffset(unused_bytes); s != end; ++s) {
329 s->~basic_string();
330 }
331 size_t deallocated = StringBlock::Delete(string_block);
332
333 while ((string_block = next) != nullptr) {
334 next = string_block->next();
335 for (std::string& s : *string_block) {
336 s.~basic_string();
337 }
338 deallocated += StringBlock::Delete(string_block);
339 }
340 return deallocated;
341 }
342
343 void SerialArena::CleanupList() {
344 ArenaBlock* b = head();
345 if (b->IsSentry()) return;
346
347 b->cleanup_nodes = limit_;
348 do {
349 char* limit = b->Limit();
350 char* it = reinterpret_cast<char*>(b->cleanup_nodes);
351 ABSL_DCHECK(!b->IsSentry() || it == limit);
352 while (it < limit) {
353 it += cleanup::DestroyNode(it);
354 }
355 b = b->next;
356 } while (b);
357 }
358
359 // Stores arrays of void* and SerialArena* instead of linked list of
360 // SerialArena* to speed up traversing all SerialArena. The cost of walk is non
361 // trivial when there are many nodes. Separately storing "ids" minimizes cache
362 // footprints and more efficient when looking for matching arena.
363 //
364 // Uses absl::container_internal::Layout to emulate the following:
365 //
366 // struct SerialArenaChunk {
367 // struct SerialArenaChunkHeader {
368 // SerialArenaChunk* next_chunk;
369 // uint32_t capacity;
370 // std::atomic<uint32_t> size;
371 // } header;
372 // std::atomic<void*> ids[];
373 // std::atomic<SerialArena*> arenas[];
374 // };
375 //
376 // where the size of "ids" and "arenas" is determined at runtime; hence the use
377 // of Layout.
378 struct SerialArenaChunkHeader {
379 constexpr SerialArenaChunkHeader(uint32_t capacity, uint32_t size)
380 : next_chunk(nullptr), capacity(capacity), size(size) {}
381
382 ThreadSafeArena::SerialArenaChunk* next_chunk;
383 uint32_t capacity;
384 std::atomic<uint32_t> size;
385 };
386
387 class ThreadSafeArena::SerialArenaChunk {
388 public:
389 SerialArenaChunk(uint32_t capacity, void* me, SerialArena* serial) {
390 new (&header()) SerialArenaChunkHeader{capacity, 1};
391
392 new (&id(0)) std::atomic<void*>{me};
393 for (uint32_t i = 1; i < capacity; ++i) {
394 new (&id(i)) std::atomic<void*>{nullptr};
395 }
396
397 new (&arena(0)) std::atomic<SerialArena*>{serial};
398 for (uint32_t i = 1; i < capacity; ++i) {
399 new (&arena(i)) std::atomic<void*>{nullptr};
400 }
401 }
402
403 bool IsSentry() const { return capacity() == 0; }
404
405 // next_chunk
406 const SerialArenaChunk* next_chunk() const { return header().next_chunk; }
407 SerialArenaChunk* next_chunk() { return header().next_chunk; }
408 void set_next(SerialArenaChunk* next_chunk) {
409 header().next_chunk = next_chunk;
410 }
411
412 // capacity
413 uint32_t capacity() const { return header().capacity; }
414 void set_capacity(uint32_t capacity) { header().capacity = capacity; }
415
416 // ids: returns up to size().
417 absl::Span<const std::atomic<void*>> ids() const {
418 return Layout(capacity()).Slice<kIds>(ptr()).first(safe_size());
419 }
420 absl::Span<std::atomic<void*>> ids() {
421 return Layout(capacity()).Slice<kIds>(ptr()).first(safe_size());
422 }
423 std::atomic<void*>& id(uint32_t i) {
424 ABSL_DCHECK_LT(i, capacity());
425 return Layout(capacity()).Pointer<kIds>(ptr())[i];
426 }
427
428 // arenas: returns up to size().
429 absl::Span<const std::atomic<SerialArena*>> arenas() const {
430 return Layout(capacity()).Slice<kArenas>(ptr()).first(safe_size());
431 }
432 absl::Span<std::atomic<SerialArena*>> arenas() {
433 return Layout(capacity()).Slice<kArenas>(ptr()).first(safe_size());
434 }
435 const std::atomic<SerialArena*>& arena(uint32_t i) const {
436 ABSL_DCHECK_LT(i, capacity());
437 return Layout(capacity()).Pointer<kArenas>(ptr())[i];
438 }
439 std::atomic<SerialArena*>& arena(uint32_t i) {
440 ABSL_DCHECK_LT(i, capacity());
441 return Layout(capacity()).Pointer<kArenas>(ptr())[i];
442 }
443
444 // Tries to insert {id, serial} to head chunk. Returns false if the head is
445 // already full.
446 //
447 // Note that the updating "size", "id", "arena" is individually atomic but
448 // those are not protected by a mutex. This is acceptable because concurrent
449 // lookups from SpaceUsed or SpaceAllocated accept inaccuracy due to race. On
450 // other paths, either race is not possible (GetSerialArenaFallback) or must
451 // be prevented by users (CleanupList, Free).
452 bool insert(void* me, SerialArena* serial) {
453 uint32_t idx = size().fetch_add(1, std::memory_order_relaxed);
454 // Bail out if this chunk is full.
455 if (idx >= capacity()) {
456 // Write old value back to avoid potential overflow.
457 size().store(capacity(), std::memory_order_relaxed);
458 return false;
459 }
460
461 id(idx).store(me, std::memory_order_relaxed);
462 arena(idx).store(serial, std::memory_order_release);
463 return true;
464 }
465
466 constexpr static size_t AllocSize(size_t n) { return Layout(n).AllocSize(); }
467
468 private:
469 constexpr static int kHeader = 0;
470 constexpr static int kIds = 1;
471 constexpr static int kArenas = 2;
472
473 using layout_type = absl::container_internal::Layout<
474 SerialArenaChunkHeader, std::atomic<void*>, std::atomic<SerialArena*>>;
475
476 const char* ptr() const { return reinterpret_cast<const char*>(this); }
477 char* ptr() { return reinterpret_cast<char*>(this); }
478
479 SerialArenaChunkHeader& header() {
480 return *layout_type::Partial().Pointer<kHeader>(ptr());
481 }
482 const SerialArenaChunkHeader& header() const {
483 return *layout_type::Partial().Pointer<kHeader>(ptr());
484 }
485
486 std::atomic<uint32_t>& size() { return header().size; }
487 const std::atomic<uint32_t>& size() const { return header().size; }
488
489 // Returns the size capped by the capacity as fetch_add may result in a size
490 // greater than capacity.
491 uint32_t safe_size() const {
492 return std::min(capacity(), size().load(std::memory_order_relaxed));
493 }
494
495 constexpr static layout_type Layout(size_t n) {
496 return layout_type(
497 /*header*/ 1,
498 /*ids*/ n,
499 /*arenas*/ n);
500 }
501 };
502
503 constexpr SerialArenaChunkHeader kSentryArenaChunk = {0, 0};
504
505 ThreadSafeArena::SerialArenaChunk* ThreadSafeArena::SentrySerialArenaChunk() {
506 // const_cast is okay because the sentry chunk is never mutated. Also,
507 // reinterpret_cast is acceptable here as it should be identical to
508 // SerialArenaChunk with zero payload. This is a necessary trick to
509 // constexpr initialize kSentryArenaChunk.
510 return reinterpret_cast<SerialArenaChunk*>(
511 const_cast<SerialArenaChunkHeader*>(&kSentryArenaChunk));
512 }
513
514
515 alignas(kCacheAlignment) ABSL_CONST_INIT
516 std::atomic<ThreadSafeArena::LifecycleId> ThreadSafeArena::lifecycle_id_{0};
517 #if defined(PROTOBUF_NO_THREADLOCAL)
518 ThreadSafeArena::ThreadCache& ThreadSafeArena::thread_cache() {
519 static internal::ThreadLocalStorage<ThreadCache>* thread_cache_ =
520 new internal::ThreadLocalStorage<ThreadCache>();
521 return *thread_cache_->Get();
522 }
523 #elif defined(PROTOBUF_USE_DLLS) && defined(_WIN32)
524 ThreadSafeArena::ThreadCache& ThreadSafeArena::thread_cache() {
525 static PROTOBUF_THREAD_LOCAL ThreadCache thread_cache;
526 return thread_cache;
527 }
528 #else
529 PROTOBUF_CONSTINIT PROTOBUF_THREAD_LOCAL
530 ThreadSafeArena::ThreadCache ThreadSafeArena::thread_cache_;
531 #endif
532
533 ThreadSafeArena::ThreadSafeArena() : first_arena_(*this) { Init(); }
534
535 ThreadSafeArena::ThreadSafeArena(char* mem, size_t size)
536 : first_arena_(FirstSerialArena{}, FirstBlock(mem, size), *this) {
537 Init();
538 }
539
540 ThreadSafeArena::ThreadSafeArena(void* mem, size_t size,
541 const AllocationPolicy& policy)
542 : first_arena_(FirstSerialArena{}, FirstBlock(mem, size, policy), *this) {
543 InitializeWithPolicy(policy);
544 }
545
546 ArenaBlock* ThreadSafeArena::FirstBlock(void* buf, size_t size) {
547 ABSL_DCHECK_EQ(reinterpret_cast<uintptr_t>(buf) & 7, 0u);
548 if (buf == nullptr || size <= kBlockHeaderSize) {
549 return SentryArenaBlock();
550 }
551 // Record user-owned block.
552 alloc_policy_.set_is_user_owned_initial_block(true);
553 return new (buf) ArenaBlock{nullptr, size};
554 }
555
556 ArenaBlock* ThreadSafeArena::FirstBlock(void* buf, size_t size,
557 const AllocationPolicy& policy) {
558 if (policy.IsDefault()) return FirstBlock(buf, size);
559
560 ABSL_DCHECK_EQ(reinterpret_cast<uintptr_t>(buf) & 7, 0u);
561
562 SizedPtr mem;
563 if (buf == nullptr || size < kBlockHeaderSize + kAllocPolicySize) {
564 mem = AllocateMemory(&policy, 0, kAllocPolicySize);
565 } else {
566 mem = {buf, size};
567 // Record user-owned block.
568 alloc_policy_.set_is_user_owned_initial_block(true);
569 }
570
571 return new (mem.p) ArenaBlock{nullptr, mem.n};
572 }
573
574 void ThreadSafeArena::InitializeWithPolicy(const AllocationPolicy& policy) {
575 Init();
576
577 if (policy.IsDefault()) return;
578
579 #ifndef NDEBUG
580 const uint64_t old_alloc_policy = alloc_policy_.get_raw();
581 // If there was a policy (e.g., in Reset()), make sure flags were preserved.
582 #define ABSL_DCHECK_POLICY_FLAGS_() \
583 if (old_alloc_policy > 3) \
584 ABSL_CHECK_EQ(old_alloc_policy & 3, alloc_policy_.get_raw() & 3)
585 #else
586 #define ABSL_DCHECK_POLICY_FLAGS_()
587 #endif // NDEBUG
588
589 // We ensured enough space so this cannot fail.
590 void* p;
591 if (!first_arena_.MaybeAllocateAligned(kAllocPolicySize, &p)) {
592 ABSL_LOG(FATAL) << "MaybeAllocateAligned cannot fail here.";
593 return;
594 }
595 new (p) AllocationPolicy{policy};
596 // Low bits store flags, so they mustn't be overwritten.
597 ABSL_DCHECK_EQ(0u, reinterpret_cast<uintptr_t>(p) & 3);
598 alloc_policy_.set_policy(reinterpret_cast<AllocationPolicy*>(p));
599 ABSL_DCHECK_POLICY_FLAGS_();
600
601 #undef ABSL_DCHECK_POLICY_FLAGS_
602 }
603
604 uint64_t ThreadSafeArena::GetNextLifeCycleId() {
605 ThreadCache& tc = thread_cache();
606 uint64_t id = tc.next_lifecycle_id;
607 constexpr uint64_t kInc = ThreadCache::kPerThreadIds;
608 if (PROTOBUF_PREDICT_FALSE((id & (kInc - 1)) == 0)) {
609 // On platforms that don't support uint64_t atomics we can certainly not
610 // afford to increment by large intervals and expect uniqueness due to
611 // wrapping, hence we only add by 1.
612 id = lifecycle_id_.fetch_add(1, std::memory_order_relaxed) * kInc;
613 }
614 tc.next_lifecycle_id = id + 1;
615 return id;
616 }
617
618 // We assume that #threads / arena is bimodal; i.e. majority small ones are
619 // single threaded but some big ones are highly concurrent. To balance between
620 // memory overhead and minimum pointer chasing, we start with few entries and
621 // exponentially (4x) grow with a limit (255 entries). Note that parameters are
622 // picked for x64 architectures as hint and the actual size is calculated by
623 // Layout.
624 ThreadSafeArena::SerialArenaChunk* ThreadSafeArena::NewSerialArenaChunk(
625 uint32_t prev_capacity, void* id, SerialArena* serial) {
626 constexpr size_t kMaxBytes = 4096; // Can hold up to 255 entries.
627 constexpr size_t kGrowthFactor = 4;
628 constexpr size_t kHeaderSize = SerialArenaChunk::AllocSize(0);
629 constexpr size_t kEntrySize = SerialArenaChunk::AllocSize(1) - kHeaderSize;
630
631 // On x64 arch: {4, 16, 64, 256, 256, ...} * 16.
632 size_t prev_bytes = SerialArenaChunk::AllocSize(prev_capacity);
633 size_t next_bytes = std::min(kMaxBytes, prev_bytes * kGrowthFactor);
634 uint32_t next_capacity =
635 static_cast<uint32_t>(next_bytes - kHeaderSize) / kEntrySize;
636 // Growth based on bytes needs to be adjusted by AllocSize.
637 next_bytes = SerialArenaChunk::AllocSize(next_capacity);
638
639 // If we allocate bigger memory than requested, we should expand
640 // size to use that extra space, and add extra entries permitted
641 // by the extra space.
642 SizedPtr mem = AllocateAtLeast(next_bytes);
643 next_capacity = static_cast<uint32_t>(mem.n - kHeaderSize) / kEntrySize;
644 ABSL_DCHECK_LE(SerialArenaChunk::AllocSize(next_capacity), mem.n);
645 return new (mem.p) SerialArenaChunk{next_capacity, id, serial};
646 }
647
648 // Tries to reserve an entry by atomic fetch_add. If the head chunk is already
649 // full (size >= capacity), acquires the mutex and adds a new head.
650 void ThreadSafeArena::AddSerialArena(void* id, SerialArena* serial) {
651 SerialArenaChunk* head = head_.load(std::memory_order_acquire);
652 // Fast path without acquiring mutex.
653 if (!head->IsSentry() && head->insert(id, serial)) {
654 return;
655 }
656
657 // Slow path with acquiring mutex.
658 absl::MutexLock lock(&mutex_);
659
660 // Refetch and if someone else installed a new head, try allocating on that!
661 SerialArenaChunk* new_head = head_.load(std::memory_order_acquire);
662 if (new_head != head) {
663 if (new_head->insert(id, serial)) return;
664 // Update head to link to the latest one.
665 head = new_head;
666 }
667
668 new_head = NewSerialArenaChunk(head->capacity(), id, serial);
669 new_head->set_next(head);
670
671 // Use "std::memory_order_release" to make sure prior stores are visible after
672 // this one.
673 head_.store(new_head, std::memory_order_release);
674 }
675
676 void ThreadSafeArena::Init() {
677 tag_and_id_ = GetNextLifeCycleId();
678 arena_stats_ = Sample();
679 head_.store(SentrySerialArenaChunk(), std::memory_order_relaxed);
680 first_owner_ = &thread_cache();
681
682 // Record allocation for the first block that was either user-provided or
683 // newly allocated.
684 ThreadSafeArenaStats::RecordAllocateStats(
685 arena_stats_.MutableStats(),
686 /*used=*/0,
687 /*allocated=*/first_arena_.SpaceAllocated(),
688 /*wasted=*/0);
689
690 CacheSerialArena(&first_arena_);
691 }
692
693 ThreadSafeArena::~ThreadSafeArena() {
694 // Have to do this in a first pass, because some of the destructors might
695 // refer to memory in other blocks.
696 CleanupList();
697
698 size_t space_allocated = 0;
699 auto mem = Free(&space_allocated);
700 if (alloc_policy_.is_user_owned_initial_block()) {
701 #ifdef ADDRESS_SANITIZER
702 // Unpoison the initial block, now that it's going back to the user.
703 ASAN_UNPOISON_MEMORY_REGION(mem.p, mem.n);
704 #endif // ADDRESS_SANITIZER
705 space_allocated += mem.n;
706 } else if (mem.n > 0) {
707 GetDeallocator(alloc_policy_.get(), &space_allocated)(mem);
708 }
709 }
710
711 SizedPtr ThreadSafeArena::Free(size_t* space_allocated) {
712 auto deallocator = GetDeallocator(alloc_policy_.get(), space_allocated);
713
714 WalkSerialArenaChunk([&](SerialArenaChunk* chunk) {
715 absl::Span<std::atomic<SerialArena*>> span = chunk->arenas();
716 // Walks arenas backward to handle the first serial arena the last. Freeing
717 // in reverse-order to the order in which objects were created may not be
718 // necessary to Free and we should revisit this. (b/247560530)
719 for (auto it = span.rbegin(); it != span.rend(); ++it) {
720 SerialArena* serial = it->load(std::memory_order_relaxed);
721 ABSL_DCHECK_NE(serial, nullptr);
722 // Free string blocks
723 *space_allocated += serial->FreeStringBlocks();
724 // Always frees the first block of "serial" as it cannot be user-provided.
725 SizedPtr mem = serial->Free(deallocator);
726 ABSL_DCHECK_NE(mem.p, nullptr);
727 deallocator(mem);
728 }
729
730 // Delete the chunk as we're done with it.
731 internal::SizedDelete(chunk,
732 SerialArenaChunk::AllocSize(chunk->capacity()));
733 });
734
735 // The first block of the first arena is special and let the caller handle it.
736 *space_allocated += first_arena_.FreeStringBlocks();
737 return first_arena_.Free(deallocator);
738 }
739
740 uint64_t ThreadSafeArena::Reset() {
741 // Have to do this in a first pass, because some of the destructors might
742 // refer to memory in other blocks.
743 CleanupList();
744
745 // Discard all blocks except the first one. Whether it is user-provided or
746 // allocated, always reuse the first block for the first arena.
747 size_t space_allocated = 0;
748 auto mem = Free(&space_allocated);
749 space_allocated += mem.n;
750
751 // Reset the first arena with the first block. This avoids redundant
752 // free / allocation and re-allocating for AllocationPolicy. Adjust offset if
753 // we need to preserve alloc_policy_.
754 if (alloc_policy_.is_user_owned_initial_block() ||
755 alloc_policy_.get() != nullptr) {
756 size_t offset = alloc_policy_.get() == nullptr
757 ? kBlockHeaderSize
758 : kBlockHeaderSize + kAllocPolicySize;
759 first_arena_.Init(new (mem.p) ArenaBlock{nullptr, mem.n}, offset);
760 } else {
761 first_arena_.Init(SentryArenaBlock(), 0);
762 }
763
764 // Since the first block and potential alloc_policy on the first block is
765 // preserved, this can be initialized by Init().
766 Init();
767
768 return space_allocated;
769 }
770
771 void* ThreadSafeArena::AllocateAlignedWithCleanup(size_t n, size_t align,
772 void (*destructor)(void*)) {
773 SerialArena* arena;
774 if (PROTOBUF_PREDICT_TRUE(GetSerialArenaFast(&arena))) {
775 return arena->AllocateAlignedWithCleanup(n, align, destructor);
776 } else {
777 return AllocateAlignedWithCleanupFallback(n, align, destructor);
778 }
779 }
780
781 void ThreadSafeArena::AddCleanup(void* elem, void (*cleanup)(void*)) {
782 GetSerialArena()->AddCleanup(elem, cleanup);
783 }
784
785 SerialArena* ThreadSafeArena::GetSerialArena() {
786 SerialArena* arena;
787 if (PROTOBUF_PREDICT_FALSE(!GetSerialArenaFast(&arena))) {
788 arena = GetSerialArenaFallback(kMaxCleanupNodeSize);
789 }
790 return arena;
791 }
792
793 PROTOBUF_NOINLINE
794 void* ThreadSafeArena::AllocateAlignedWithCleanupFallback(
795 size_t n, size_t align, void (*destructor)(void*)) {
796 return GetSerialArenaFallback(n + kMaxCleanupNodeSize)
797 ->AllocateAlignedWithCleanup(n, align, destructor);
798 }
799
800 PROTOBUF_NOINLINE
801 void* ThreadSafeArena::AllocateFromStringBlock() {
802 return GetSerialArena()->AllocateFromStringBlock();
803 }
804
805 template <typename Functor>
806 void ThreadSafeArena::WalkConstSerialArenaChunk(Functor fn) const {
807 const SerialArenaChunk* chunk = head_.load(std::memory_order_acquire);
808
809 for (; !chunk->IsSentry(); chunk = chunk->next_chunk()) {
810 fn(chunk);
811 }
812 }
813
814 template <typename Functor>
815 void ThreadSafeArena::WalkSerialArenaChunk(Functor fn) {
816 // By omitting an Acquire barrier we help the sanitizer that any user code
817 // that doesn't properly synchronize Reset() or the destructor will throw a
818 // TSAN warning.
819 SerialArenaChunk* chunk = head_.load(std::memory_order_relaxed);
820
821 while (!chunk->IsSentry()) {
822 // Cache next chunk in case this chunk is destroyed.
823 SerialArenaChunk* next_chunk = chunk->next_chunk();
824 fn(chunk);
825 chunk = next_chunk;
826 }
827 }
828
829 template <typename Functor>
830 void ThreadSafeArena::PerConstSerialArenaInChunk(Functor fn) const {
831 WalkConstSerialArenaChunk([&fn](const SerialArenaChunk* chunk) {
832 for (const auto& each : chunk->arenas()) {
833 const SerialArena* serial = each.load(std::memory_order_acquire);
834 // It is possible that newly added SerialArena is not updated although
835 // size was. This is acceptable for SpaceAllocated and SpaceUsed.
836 if (serial == nullptr) continue;
837 fn(serial);
838 }
839 });
840 }
841
842 uint64_t ThreadSafeArena::SpaceAllocated() const {
843 uint64_t space_allocated = first_arena_.SpaceAllocated();
844 PerConstSerialArenaInChunk([&space_allocated](const SerialArena* serial) {
845 space_allocated += serial->SpaceAllocated();
846 });
847 return space_allocated;
848 }
849
850 uint64_t ThreadSafeArena::SpaceUsed() const {
851 // First arena is inlined to ThreadSafeArena and the first block's overhead is
852 // smaller than others that contain SerialArena.
853 uint64_t space_used = first_arena_.SpaceUsed();
854 PerConstSerialArenaInChunk([&space_used](const SerialArena* serial) {
855 // SerialArena on chunks directly allocated from the block and needs to be
856 // subtracted from SpaceUsed.
857 space_used += serial->SpaceUsed() - kSerialArenaSize;
858 });
859 return space_used - (alloc_policy_.get() ? sizeof(AllocationPolicy) : 0);
860 }
861
862 template <AllocationClient alloc_client>
863 PROTOBUF_NOINLINE void* ThreadSafeArena::AllocateAlignedFallback(size_t n) {
864 return GetSerialArenaFallback(n)->AllocateAligned<alloc_client>(n);
865 }
866
867 template void* ThreadSafeArena::AllocateAlignedFallback<
868 AllocationClient::kDefault>(size_t);
869 template void*
870 ThreadSafeArena::AllocateAlignedFallback<AllocationClient::kArray>(size_t);
871
872 void ThreadSafeArena::CleanupList() {
873 WalkSerialArenaChunk([](SerialArenaChunk* chunk) {
874 absl::Span<std::atomic<SerialArena*>> span = chunk->arenas();
875 // Walks arenas backward to handle the first serial arena the last.
876 // Destroying in reverse-order to the construction is often assumed by users
877 // and required not to break inter-object dependencies. (b/247560530)
878 for (auto it = span.rbegin(); it != span.rend(); ++it) {
879 SerialArena* serial = it->load(std::memory_order_relaxed);
880 ABSL_DCHECK_NE(serial, nullptr);
881 serial->CleanupList();
882 }
883 });
884 // First arena must be cleaned up last. (b/247560530)
885 first_arena_.CleanupList();
886 }
887
888 PROTOBUF_NOINLINE
889 SerialArena* ThreadSafeArena::GetSerialArenaFallback(size_t n) {
890 void* const id = &thread_cache();
891 if (id == first_owner_) {
892 CacheSerialArena(&first_arena_);
893 return &first_arena_;
894 }
895
896 // Search matching SerialArena.
897 SerialArena* serial = nullptr;
898 WalkConstSerialArenaChunk([&serial, id](const SerialArenaChunk* chunk) {
899 absl::Span<const std::atomic<void*>> ids = chunk->ids();
900 for (uint32_t i = 0; i < ids.size(); ++i) {
901 if (ids[i].load(std::memory_order_relaxed) == id) {
902 serial = chunk->arena(i).load(std::memory_order_relaxed);
903 ABSL_DCHECK_NE(serial, nullptr);
904 break;
905 }
906 }
907 });
908
909 if (!serial) {
910 // This thread doesn't have any SerialArena, which also means it doesn't
911 // have any blocks yet. So we'll allocate its first block now. It must be
912 // big enough to host SerialArena and the pending request.
913 serial = SerialArena::New(
914 AllocateMemory(alloc_policy_.get(), 0, n + kSerialArenaSize), *this);
915
916 AddSerialArena(id, serial);
917 }
918
919 CacheSerialArena(serial);
920 return serial;
921 }
922
923 } // namespace internal
924
925 void* Arena::Allocate(size_t n) { return impl_.AllocateAligned(n); }
926
927 void* Arena::AllocateForArray(size_t n) {
928 return impl_.AllocateAligned<internal::AllocationClient::kArray>(n);
929 }
930
931 void* Arena::AllocateAlignedWithCleanup(size_t n, size_t align,
932 void (*destructor)(void*)) {
933 return impl_.AllocateAlignedWithCleanup(n, align, destructor);
934 }
935
936 std::vector<void*> Arena::PeekCleanupListForTesting() {
937 return impl_.PeekCleanupListForTesting();
938 }
939
940 } // namespace protobuf
941 } // namespace google
942
943 #include "google/protobuf/port_undef.inc"