Line data Source code
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 : // This file defines an Arena allocator for better allocation performance.
32 :
33 : #ifndef GOOGLE_PROTOBUF_ARENA_IMPL_H__
34 : #define GOOGLE_PROTOBUF_ARENA_IMPL_H__
35 :
36 : #include <atomic>
37 : #include <limits>
38 :
39 : #include <google/protobuf/stubs/common.h>
40 : #include <google/protobuf/stubs/logging.h>
41 :
42 : #include <google/protobuf/stubs/port.h>
43 :
44 : #ifdef ADDRESS_SANITIZER
45 : #include <sanitizer/asan_interface.h>
46 : #endif // ADDRESS_SANITIZER
47 :
48 : namespace google {
49 :
50 : namespace protobuf {
51 : namespace internal {
52 :
53 0 : inline size_t AlignUpTo8(size_t n) {
54 : // Align n to next multiple of 8 (from Hacker's Delight, Chapter 3.)
55 0 : return (n + 7) & -8;
56 : }
57 :
58 : // This class provides the core Arena memory allocation library. Different
59 : // implementations only need to implement the public interface below.
60 : // Arena is not a template type as that would only be useful if all protos
61 : // in turn would be templates, which will/cannot happen. However separating
62 : // the memory allocation part from the cruft of the API users expect we can
63 : // use #ifdef the select the best implementation based on hardware / OS.
64 : class LIBPROTOBUF_EXPORT ArenaImpl {
65 : public:
66 : struct Options {
67 : size_t start_block_size;
68 : size_t max_block_size;
69 : char* initial_block;
70 : size_t initial_block_size;
71 : void* (*block_alloc)(size_t);
72 : void (*block_dealloc)(void*, size_t);
73 :
74 : template <typename O>
75 : explicit Options(const O& options)
76 : : start_block_size(options.start_block_size),
77 : max_block_size(options.max_block_size),
78 : initial_block(options.initial_block),
79 : initial_block_size(options.initial_block_size),
80 : block_alloc(options.block_alloc),
81 : block_dealloc(options.block_dealloc) {}
82 : };
83 :
84 : template <typename O>
85 : explicit ArenaImpl(const O& options) : options_(options) {
86 : if (options_.initial_block != NULL && options_.initial_block_size > 0) {
87 : GOOGLE_CHECK_GE(options_.initial_block_size, sizeof(Block))
88 : << ": Initial block size too small for header.";
89 : initial_block_ = reinterpret_cast<Block*>(options_.initial_block);
90 : } else {
91 : initial_block_ = NULL;
92 : }
93 :
94 : Init();
95 : }
96 :
97 : // Destructor deletes all owned heap allocated objects, and destructs objects
98 : // that have non-trivial destructors, except for proto2 message objects whose
99 : // destructors can be skipped. Also, frees all blocks except the initial block
100 : // if it was passed in.
101 : ~ArenaImpl();
102 :
103 : uint64 Reset();
104 :
105 : uint64 SpaceAllocated() const;
106 : uint64 SpaceUsed() const;
107 :
108 : void* AllocateAligned(size_t n);
109 :
110 : void* AllocateAlignedAndAddCleanup(size_t n, void (*cleanup)(void*));
111 :
112 : // Add object pointer and cleanup function pointer to the list.
113 : void AddCleanup(void* elem, void (*cleanup)(void*));
114 :
115 : private:
116 : void* AllocateAlignedFallback(size_t n);
117 : void* AllocateAlignedAndAddCleanupFallback(size_t n, void (*cleanup)(void*));
118 : void AddCleanupFallback(void* elem, void (*cleanup)(void*));
119 :
120 : // Node contains the ptr of the object to be cleaned up and the associated
121 : // cleanup function ptr.
122 : struct CleanupNode {
123 : void* elem; // Pointer to the object to be cleaned up.
124 : void (*cleanup)(void*); // Function pointer to the destructor or deleter.
125 : };
126 :
127 : // Cleanup uses a chunked linked list, to reduce pointer chasing.
128 : struct CleanupChunk {
129 : static size_t SizeOf(size_t i) {
130 : return sizeof(CleanupChunk) + (sizeof(CleanupNode) * (i - 1));
131 : }
132 : size_t size; // Total elements in the list.
133 : CleanupChunk* next; // Next node in the list.
134 : CleanupNode nodes[1]; // True length is |size|.
135 : };
136 :
137 : class Block;
138 :
139 : // A thread-unsafe Arena that can only be used within its owning thread.
140 : class LIBPROTOBUF_EXPORT SerialArena {
141 : public:
142 : // The allocate/free methods here are a little strange, since SerialArena is
143 : // allocated inside a Block which it also manages. This is to avoid doing
144 : // an extra allocation for the SerialArena itself.
145 :
146 : // Creates a new SerialArena inside Block* and returns it.
147 : static SerialArena* New(Block* b, void* owner, ArenaImpl* arena);
148 :
149 : // Destroys this SerialArena, freeing all blocks with the given dealloc
150 : // function, except any block equal to |initial_block|.
151 : static uint64 Free(SerialArena* serial, Block* initial_block,
152 : void (*block_dealloc)(void*, size_t));
153 :
154 : void CleanupList();
155 : uint64 SpaceUsed() const;
156 :
157 : void* AllocateAligned(size_t n) {
158 : GOOGLE_DCHECK_EQ(internal::AlignUpTo8(n), n); // Must be already aligned.
159 : GOOGLE_DCHECK_GE(limit_, ptr_);
160 : if (GOOGLE_PREDICT_FALSE(static_cast<size_t>(limit_ - ptr_) < n)) {
161 : return AllocateAlignedFallback(n);
162 : }
163 : void* ret = ptr_;
164 : ptr_ += n;
165 : #ifdef ADDRESS_SANITIZER
166 : ASAN_UNPOISON_MEMORY_REGION(ret, n);
167 : #endif // ADDRESS_SANITIZER
168 : return ret;
169 : }
170 :
171 : void AddCleanup(void* elem, void (*cleanup)(void*)) {
172 : if (GOOGLE_PREDICT_FALSE(cleanup_ptr_ == cleanup_limit_)) {
173 : AddCleanupFallback(elem, cleanup);
174 : return;
175 : }
176 : cleanup_ptr_->elem = elem;
177 : cleanup_ptr_->cleanup = cleanup;
178 : cleanup_ptr_++;
179 : }
180 :
181 : void* AllocateAlignedAndAddCleanup(size_t n, void (*cleanup)(void*)) {
182 : void* ret = AllocateAligned(n);
183 : AddCleanup(ret, cleanup);
184 : return ret;
185 : }
186 :
187 : void* owner() const { return owner_; }
188 : SerialArena* next() const { return next_; }
189 : void set_next(SerialArena* next) { next_ = next; }
190 :
191 : private:
192 : void* AllocateAlignedFallback(size_t n);
193 : void AddCleanupFallback(void* elem, void (*cleanup)(void*));
194 : void CleanupListFallback();
195 :
196 : ArenaImpl* arena_; // Containing arena.
197 : void* owner_; // &ThreadCache of this thread;
198 : Block* head_; // Head of linked list of blocks.
199 : CleanupChunk* cleanup_; // Head of cleanup list.
200 : SerialArena* next_; // Next SerialArena in this linked list.
201 :
202 : // Next pointer to allocate from. Always 8-byte aligned. Points inside
203 : // head_ (and head_->pos will always be non-canonical). We keep these
204 : // here to reduce indirection.
205 : char* ptr_;
206 : char* limit_;
207 :
208 : // Next CleanupList members to append to. These point inside cleanup_.
209 : CleanupNode* cleanup_ptr_;
210 : CleanupNode* cleanup_limit_;
211 : };
212 :
213 : // Blocks are variable length malloc-ed objects. The following structure
214 : // describes the common header for all blocks.
215 : class LIBPROTOBUF_EXPORT Block {
216 : public:
217 : Block(size_t size, Block* next);
218 :
219 : char* Pointer(size_t n) {
220 : GOOGLE_DCHECK(n <= size_);
221 : return reinterpret_cast<char*>(this) + n;
222 : }
223 :
224 : Block* next() const { return next_; }
225 : size_t pos() const { return pos_; }
226 : size_t size() const { return size_; }
227 : void set_pos(size_t pos) { pos_ = pos; }
228 :
229 : private:
230 : Block* next_; // Next block for this thread.
231 : size_t pos_;
232 : size_t size_;
233 : // data follows
234 : };
235 :
236 : struct ThreadCache {
237 : #if defined(GOOGLE_PROTOBUF_NO_THREADLOCAL)
238 : // If we are using the ThreadLocalStorage class to store the ThreadCache,
239 : // then the ThreadCache's default constructor has to be responsible for
240 : // initializing it.
241 : ThreadCache() : last_lifecycle_id_seen(-1), last_serial_arena(NULL) {}
242 : #endif
243 :
244 : // The ThreadCache is considered valid as long as this matches the
245 : // lifecycle_id of the arena being used.
246 : int64 last_lifecycle_id_seen;
247 : SerialArena* last_serial_arena;
248 : };
249 : static std::atomic<int64> lifecycle_id_generator_;
250 : #if defined(GOOGLE_PROTOBUF_NO_THREADLOCAL)
251 : // Android ndk does not support GOOGLE_THREAD_LOCAL keyword so we use a custom thread
252 : // local storage class we implemented.
253 : // iOS also does not support the GOOGLE_THREAD_LOCAL keyword.
254 : static ThreadCache& thread_cache();
255 : #elif defined(PROTOBUF_USE_DLLS)
256 : // Thread local variables cannot be exposed through DLL interface but we can
257 : // wrap them in static functions.
258 : static ThreadCache& thread_cache();
259 : #else
260 : static GOOGLE_THREAD_LOCAL ThreadCache thread_cache_;
261 : static ThreadCache& thread_cache() { return thread_cache_; }
262 : #endif
263 :
264 : void Init();
265 :
266 : // Free all blocks and return the total space used which is the sums of sizes
267 : // of the all the allocated blocks.
268 : uint64 FreeBlocks();
269 : // Delete or Destruct all objects owned by the arena.
270 : void CleanupList();
271 :
272 : inline void CacheSerialArena(SerialArena* serial) {
273 : thread_cache().last_serial_arena = serial;
274 : thread_cache().last_lifecycle_id_seen = lifecycle_id_;
275 : // TODO(haberman): evaluate whether we would gain efficiency by getting rid
276 : // of hint_. It's the only write we do to ArenaImpl in the allocation path,
277 : // which will dirty the cache line.
278 :
279 : hint_.store(serial, std::memory_order_release);
280 : }
281 :
282 :
283 : std::atomic<SerialArena*>
284 : threads_; // Pointer to a linked list of SerialArena.
285 : std::atomic<SerialArena*> hint_; // Fast thread-local block access
286 : std::atomic<size_t> space_allocated_; // Total size of all allocated blocks.
287 :
288 : Block *initial_block_; // If non-NULL, points to the block that came from
289 : // user data.
290 :
291 : Block* NewBlock(Block* last_block, size_t min_bytes);
292 :
293 : SerialArena* GetSerialArena();
294 : bool GetSerialArenaFast(SerialArena** arena);
295 : SerialArena* GetSerialArenaFallback(void* me);
296 : int64 lifecycle_id_; // Unique for each arena. Changes on Reset().
297 :
298 : Options options_;
299 :
300 : GOOGLE_DISALLOW_EVIL_CONSTRUCTORS(ArenaImpl);
301 : // All protos have pointers back to the arena hence Arena must have
302 : // pointer stability.
303 : ArenaImpl(ArenaImpl&&) = delete;
304 : ArenaImpl& operator=(ArenaImpl&&) = delete;
305 :
306 : public:
307 : // kBlockHeaderSize is sizeof(Block), aligned up to the nearest multiple of 8
308 : // to protect the invariant that pos is always at a multiple of 8.
309 : static const size_t kBlockHeaderSize = (sizeof(Block) + 7) & -8;
310 : static const size_t kSerialArenaSize = (sizeof(SerialArena) + 7) & -8;
311 : static_assert(kBlockHeaderSize % 8 == 0,
312 : "kBlockHeaderSize must be a multiple of 8.");
313 : static_assert(kSerialArenaSize % 8 == 0,
314 : "kSerialArenaSize must be a multiple of 8.");
315 : };
316 :
317 : } // namespace internal
318 : } // namespace protobuf
319 :
320 : } // namespace google
321 : #endif // GOOGLE_PROTOBUF_ARENA_IMPL_H__
|
