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