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 34#ifdef ADDRESS_SANITIZER 35#include <sanitizer/asan_interface.h> 36#endif 37 38namespace google { 39namespace protobuf { 40 41 42google::protobuf::internal::SequenceNumber Arena::lifecycle_id_generator_; 43#if defined(GOOGLE_PROTOBUF_NO_THREADLOCAL) 44Arena::ThreadCache& Arena::thread_cache() { 45 static internal::ThreadLocalStorage<ThreadCache>* thread_cache_ = 46 new internal::ThreadLocalStorage<ThreadCache>(); 47 return *thread_cache_->Get(); 48} 49#elif defined(PROTOBUF_USE_DLLS) 50Arena::ThreadCache& Arena::thread_cache() { 51 static GOOGLE_THREAD_LOCAL ThreadCache thread_cache_ = { -1, NULL }; 52 return thread_cache_; 53} 54#else 55GOOGLE_THREAD_LOCAL Arena::ThreadCache Arena::thread_cache_ = { -1, NULL }; 56#endif 57 58void Arena::Init() { 59 lifecycle_id_ = lifecycle_id_generator_.GetNext(); 60 blocks_ = 0; 61 hint_ = 0; 62 owns_first_block_ = true; 63 cleanup_list_ = 0; 64 65 if (options_.initial_block != NULL && options_.initial_block_size > 0) { 66 GOOGLE_CHECK_GE(options_.initial_block_size, sizeof(Block)) 67 << ": Initial block size too small for header."; 68 69 // Add first unowned block to list. 70 Block* first_block = reinterpret_cast<Block*>(options_.initial_block); 71 first_block->size = options_.initial_block_size; 72 first_block->pos = kHeaderSize; 73 first_block->next = NULL; 74 // Thread which calls Init() owns the first block. This allows the 75 // single-threaded case to allocate on the first block without taking any 76 // locks. 77 first_block->owner = &thread_cache(); 78 SetThreadCacheBlock(first_block); 79 AddBlockInternal(first_block); 80 owns_first_block_ = false; 81 } 82 83 // Call the initialization hook 84 if (options_.on_arena_init != NULL) { 85 hooks_cookie_ = options_.on_arena_init(this); 86 } else { 87 hooks_cookie_ = NULL; 88 } 89} 90 91Arena::~Arena() { 92 uint64 space_allocated = ResetInternal(); 93 94 // Call the destruction hook 95 if (options_.on_arena_destruction != NULL) { 96 options_.on_arena_destruction(this, hooks_cookie_, space_allocated); 97 } 98} 99 100uint64 Arena::Reset() { 101 // Invalidate any ThreadCaches pointing to any blocks we just destroyed. 102 lifecycle_id_ = lifecycle_id_generator_.GetNext(); 103 return ResetInternal(); 104} 105 106uint64 Arena::ResetInternal() { 107 CleanupList(); 108 uint64 space_allocated = FreeBlocks(); 109 110 // Call the reset hook 111 if (options_.on_arena_reset != NULL) { 112 options_.on_arena_reset(this, hooks_cookie_, space_allocated); 113 } 114 115 return space_allocated; 116} 117 118Arena::Block* Arena::NewBlock(void* me, Block* my_last_block, size_t n, 119 size_t start_block_size, size_t max_block_size) { 120 size_t size; 121 if (my_last_block != NULL) { 122 // Double the current block size, up to a limit. 123 size = 2 * (my_last_block->size); 124 if (size > max_block_size) size = max_block_size; 125 } else { 126 size = start_block_size; 127 } 128 if (n > size - kHeaderSize) { 129 // TODO(sanjay): Check if n + kHeaderSize would overflow 130 size = kHeaderSize + n; 131 } 132 133 Block* b = reinterpret_cast<Block*>(options_.block_alloc(size)); 134 b->pos = kHeaderSize + n; 135 b->size = size; 136 if (b->avail() == 0) { 137 // Do not attempt to reuse this block. 138 b->owner = NULL; 139 } else { 140 b->owner = me; 141 } 142#ifdef ADDRESS_SANITIZER 143 // Poison the rest of the block for ASAN. It was unpoisoned by the underlying 144 // malloc but it's not yet usable until we return it as part of an allocation. 145 ASAN_POISON_MEMORY_REGION( 146 reinterpret_cast<char*>(b) + b->pos, b->size - b->pos); 147#endif 148 return b; 149} 150 151void Arena::AddBlock(Block* b) { 152 MutexLock l(&blocks_lock_); 153 AddBlockInternal(b); 154} 155 156void Arena::AddBlockInternal(Block* b) { 157 b->next = reinterpret_cast<Block*>(google::protobuf::internal::NoBarrier_Load(&blocks_)); 158 google::protobuf::internal::Release_Store(&blocks_, reinterpret_cast<google::protobuf::internal::AtomicWord>(b)); 159 if (b->avail() != 0) { 160 // Direct future allocations to this block. 161 google::protobuf::internal::Release_Store(&hint_, reinterpret_cast<google::protobuf::internal::AtomicWord>(b)); 162 } 163} 164 165void Arena::AddListNode(void* elem, void (*cleanup)(void*)) { 166 Node* node = reinterpret_cast<Node*>(AllocateAligned(sizeof(Node))); 167 node->elem = elem; 168 node->cleanup = cleanup; 169 node->next = reinterpret_cast<Node*>( 170 google::protobuf::internal::NoBarrier_AtomicExchange(&cleanup_list_, 171 reinterpret_cast<google::protobuf::internal::AtomicWord>(node))); 172} 173 174void* Arena::AllocateAligned(const std::type_info* allocated, size_t n) { 175 // Align n to next multiple of 8 (from Hacker's Delight, Chapter 3.) 176 n = (n + 7) & -8; 177 178 // Monitor allocation if needed. 179 if (GOOGLE_PREDICT_FALSE(hooks_cookie_ != NULL) && 180 options_.on_arena_allocation != NULL) { 181 options_.on_arena_allocation(allocated, n, hooks_cookie_); 182 } 183 184 // If this thread already owns a block in this arena then try to use that. 185 // This fast path optimizes the case where multiple threads allocate from the 186 // same arena. 187 if (thread_cache().last_lifecycle_id_seen == lifecycle_id_ && 188 thread_cache().last_block_used_ != NULL) { 189 if (thread_cache().last_block_used_->avail() < n) { 190 return SlowAlloc(n); 191 } 192 return AllocFromBlock(thread_cache().last_block_used_, n); 193 } 194 195 // Check whether we own the last accessed block on this arena. 196 // This fast path optimizes the case where a single thread uses multiple 197 // arenas. 198 void* me = &thread_cache(); 199 Block* b = reinterpret_cast<Block*>(google::protobuf::internal::Acquire_Load(&hint_)); 200 if (!b || b->owner != me || b->avail() < n) { 201 return SlowAlloc(n); 202 } 203 return AllocFromBlock(b, n); 204} 205 206void* Arena::AllocFromBlock(Block* b, size_t n) { 207 size_t p = b->pos; 208 b->pos = p + n; 209#ifdef ADDRESS_SANITIZER 210 ASAN_UNPOISON_MEMORY_REGION(reinterpret_cast<char*>(b) + p, n); 211#endif 212 return reinterpret_cast<char*>(b) + p; 213} 214 215void* Arena::SlowAlloc(size_t n) { 216 void* me = &thread_cache(); 217 Block* b = FindBlock(me); // Find block owned by me. 218 // See if allocation fits in my latest block. 219 if (b != NULL && b->avail() >= n) { 220 SetThreadCacheBlock(b); 221 google::protobuf::internal::NoBarrier_Store(&hint_, reinterpret_cast<google::protobuf::internal::AtomicWord>(b)); 222 return AllocFromBlock(b, n); 223 } 224 b = NewBlock(me, b, n, options_.start_block_size, options_.max_block_size); 225 AddBlock(b); 226 if (b->owner == me) { // If this block can be reused (see NewBlock()). 227 SetThreadCacheBlock(b); 228 } 229 return reinterpret_cast<char*>(b) + kHeaderSize; 230} 231 232uint64 Arena::SpaceAllocated() const { 233 uint64 space_allocated = 0; 234 Block* b = reinterpret_cast<Block*>(google::protobuf::internal::NoBarrier_Load(&blocks_)); 235 while (b != NULL) { 236 space_allocated += (b->size); 237 b = b->next; 238 } 239 return space_allocated; 240} 241 242uint64 Arena::SpaceUsed() const { 243 uint64 space_used = 0; 244 Block* b = reinterpret_cast<Block*>(google::protobuf::internal::NoBarrier_Load(&blocks_)); 245 while (b != NULL) { 246 space_used += (b->pos - kHeaderSize); 247 b = b->next; 248 } 249 return space_used; 250} 251 252pair<uint64, uint64> Arena::SpaceAllocatedAndUsed() const { 253 uint64 allocated = 0; 254 uint64 used = 0; 255 256 Block* b = reinterpret_cast<Block*>(google::protobuf::internal::NoBarrier_Load(&blocks_)); 257 while (b != NULL) { 258 allocated += b->size; 259 used += (b->pos - kHeaderSize); 260 b = b->next; 261 } 262 return std::make_pair(allocated, used); 263} 264 265uint64 Arena::FreeBlocks() { 266 uint64 space_allocated = 0; 267 Block* b = reinterpret_cast<Block*>(google::protobuf::internal::NoBarrier_Load(&blocks_)); 268 Block* first_block = NULL; 269 while (b != NULL) { 270 space_allocated += (b->size); 271 Block* next = b->next; 272 if (next != NULL) { 273 options_.block_dealloc(b, b->size); 274 } else { 275 if (owns_first_block_) { 276 options_.block_dealloc(b, b->size); 277 } else { 278 // User passed in the first block, skip free'ing the memory. 279 first_block = b; 280 } 281 } 282 b = next; 283 } 284 blocks_ = 0; 285 hint_ = 0; 286 if (!owns_first_block_) { 287 // Make the first block that was passed in through ArenaOptions 288 // available for reuse. 289 first_block->pos = kHeaderSize; 290 // Thread which calls Reset() owns the first block. This allows the 291 // single-threaded case to allocate on the first block without taking any 292 // locks. 293 first_block->owner = &thread_cache(); 294 SetThreadCacheBlock(first_block); 295 AddBlockInternal(first_block); 296 } 297 return space_allocated; 298} 299 300void Arena::CleanupList() { 301 Node* head = 302 reinterpret_cast<Node*>(google::protobuf::internal::NoBarrier_Load(&cleanup_list_)); 303 while (head != NULL) { 304 head->cleanup(head->elem); 305 head = head->next; 306 } 307 cleanup_list_ = 0; 308} 309 310Arena::Block* Arena::FindBlock(void* me) { 311 // TODO(sanjay): We might want to keep a separate list with one 312 // entry per thread. 313 Block* b = reinterpret_cast<Block*>(google::protobuf::internal::Acquire_Load(&blocks_)); 314 while (b != NULL && b->owner != me) { 315 b = b->next; 316 } 317 return b; 318} 319 320} // namespace protobuf 321} // namespace google 322