| // Protocol Buffers - Google's data interchange format |
| // Copyright 2008 Google Inc. All rights reserved. |
| // https://developers.google.com/protocol-buffers/ |
| // |
| // Redistribution and use in source and binary forms, with or without |
| // modification, are permitted provided that the following conditions are |
| // met: |
| // |
| // * Redistributions of source code must retain the above copyright |
| // notice, this list of conditions and the following disclaimer. |
| // * Redistributions in binary form must reproduce the above |
| // copyright notice, this list of conditions and the following disclaimer |
| // in the documentation and/or other materials provided with the |
| // distribution. |
| // * Neither the name of Google Inc. nor the names of its |
| // contributors may be used to endorse or promote products derived from |
| // this software without specific prior written permission. |
| // |
| // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS |
| // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT |
| // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR |
| // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT |
| // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, |
| // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT |
| // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, |
| // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY |
| // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
| // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE |
| // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
| |
| // This file defines an Arena allocator for better allocation performance. |
| |
| #ifndef GOOGLE_PROTOBUF_ARENA_IMPL_H__ |
| #define GOOGLE_PROTOBUF_ARENA_IMPL_H__ |
| |
| #include <atomic> |
| #include <limits> |
| |
| #include <google/protobuf/stubs/common.h> |
| #include <google/protobuf/stubs/logging.h> |
| |
| #include <google/protobuf/stubs/port.h> |
| |
| #ifdef ADDRESS_SANITIZER |
| #include <sanitizer/asan_interface.h> |
| #endif // ADDRESS_SANITIZER |
| |
| namespace google { |
| |
| namespace protobuf { |
| namespace internal { |
| |
| inline size_t AlignUpTo8(size_t n) { |
| // Align n to next multiple of 8 (from Hacker's Delight, Chapter 3.) |
| return (n + 7) & -8; |
| } |
| |
| // This class provides the core Arena memory allocation library. Different |
| // implementations only need to implement the public interface below. |
| // Arena is not a template type as that would only be useful if all protos |
| // in turn would be templates, which will/cannot happen. However separating |
| // the memory allocation part from the cruft of the API users expect we can |
| // use #ifdef the select the best implementation based on hardware / OS. |
| class LIBPROTOBUF_EXPORT ArenaImpl { |
| public: |
| struct Options { |
| size_t start_block_size; |
| size_t max_block_size; |
| char* initial_block; |
| size_t initial_block_size; |
| void* (*block_alloc)(size_t); |
| void (*block_dealloc)(void*, size_t); |
| |
| template <typename O> |
| explicit Options(const O& options) |
| : start_block_size(options.start_block_size), |
| max_block_size(options.max_block_size), |
| initial_block(options.initial_block), |
| initial_block_size(options.initial_block_size), |
| block_alloc(options.block_alloc), |
| block_dealloc(options.block_dealloc) {} |
| }; |
| |
| template <typename O> |
| explicit ArenaImpl(const O& options) : options_(options) { |
| if (options_.initial_block != NULL && options_.initial_block_size > 0) { |
| GOOGLE_CHECK_GE(options_.initial_block_size, sizeof(Block)) |
| << ": Initial block size too small for header."; |
| initial_block_ = reinterpret_cast<Block*>(options_.initial_block); |
| } else { |
| initial_block_ = NULL; |
| } |
| |
| Init(); |
| } |
| |
| // Destructor deletes all owned heap allocated objects, and destructs objects |
| // that have non-trivial destructors, except for proto2 message objects whose |
| // destructors can be skipped. Also, frees all blocks except the initial block |
| // if it was passed in. |
| ~ArenaImpl(); |
| |
| uint64 Reset(); |
| |
| uint64 SpaceAllocated() const; |
| uint64 SpaceUsed() const; |
| |
| void* AllocateAligned(size_t n); |
| |
| void* AllocateAlignedAndAddCleanup(size_t n, void (*cleanup)(void*)); |
| |
| // Add object pointer and cleanup function pointer to the list. |
| void AddCleanup(void* elem, void (*cleanup)(void*)); |
| |
| private: |
| void* AllocateAlignedFallback(size_t n); |
| void* AllocateAlignedAndAddCleanupFallback(size_t n, void (*cleanup)(void*)); |
| void AddCleanupFallback(void* elem, void (*cleanup)(void*)); |
| |
| // Node contains the ptr of the object to be cleaned up and the associated |
| // cleanup function ptr. |
| struct CleanupNode { |
| void* elem; // Pointer to the object to be cleaned up. |
| void (*cleanup)(void*); // Function pointer to the destructor or deleter. |
| }; |
| |
| // Cleanup uses a chunked linked list, to reduce pointer chasing. |
| struct CleanupChunk { |
| static size_t SizeOf(size_t i) { |
| return sizeof(CleanupChunk) + (sizeof(CleanupNode) * (i - 1)); |
| } |
| size_t size; // Total elements in the list. |
| CleanupChunk* next; // Next node in the list. |
| CleanupNode nodes[1]; // True length is |size|. |
| }; |
| |
| class Block; |
| |
| // A thread-unsafe Arena that can only be used within its owning thread. |
| class LIBPROTOBUF_EXPORT SerialArena { |
| public: |
| // The allocate/free methods here are a little strange, since SerialArena is |
| // allocated inside a Block which it also manages. This is to avoid doing |
| // an extra allocation for the SerialArena itself. |
| |
| // Creates a new SerialArena inside Block* and returns it. |
| static SerialArena* New(Block* b, void* owner, ArenaImpl* arena); |
| |
| // Destroys this SerialArena, freeing all blocks with the given dealloc |
| // function, except any block equal to |initial_block|. |
| static uint64 Free(SerialArena* serial, Block* initial_block, |
| void (*block_dealloc)(void*, size_t)); |
| |
| void CleanupList(); |
| uint64 SpaceUsed() const; |
| |
| void* AllocateAligned(size_t n) { |
| GOOGLE_DCHECK_EQ(internal::AlignUpTo8(n), n); // Must be already aligned. |
| GOOGLE_DCHECK_GE(limit_, ptr_); |
| if (GOOGLE_PREDICT_FALSE(static_cast<size_t>(limit_ - ptr_) < n)) { |
| return AllocateAlignedFallback(n); |
| } |
| void* ret = ptr_; |
| ptr_ += n; |
| #ifdef ADDRESS_SANITIZER |
| ASAN_UNPOISON_MEMORY_REGION(ret, n); |
| #endif // ADDRESS_SANITIZER |
| return ret; |
| } |
| |
| void AddCleanup(void* elem, void (*cleanup)(void*)) { |
| if (GOOGLE_PREDICT_FALSE(cleanup_ptr_ == cleanup_limit_)) { |
| AddCleanupFallback(elem, cleanup); |
| return; |
| } |
| cleanup_ptr_->elem = elem; |
| cleanup_ptr_->cleanup = cleanup; |
| cleanup_ptr_++; |
| } |
| |
| void* AllocateAlignedAndAddCleanup(size_t n, void (*cleanup)(void*)) { |
| void* ret = AllocateAligned(n); |
| AddCleanup(ret, cleanup); |
| return ret; |
| } |
| |
| void* owner() const { return owner_; } |
| SerialArena* next() const { return next_; } |
| void set_next(SerialArena* next) { next_ = next; } |
| |
| private: |
| void* AllocateAlignedFallback(size_t n); |
| void AddCleanupFallback(void* elem, void (*cleanup)(void*)); |
| void CleanupListFallback(); |
| |
| ArenaImpl* arena_; // Containing arena. |
| void* owner_; // &ThreadCache of this thread; |
| Block* head_; // Head of linked list of blocks. |
| CleanupChunk* cleanup_; // Head of cleanup list. |
| SerialArena* next_; // Next SerialArena in this linked list. |
| |
| // Next pointer to allocate from. Always 8-byte aligned. Points inside |
| // head_ (and head_->pos will always be non-canonical). We keep these |
| // here to reduce indirection. |
| char* ptr_; |
| char* limit_; |
| |
| // Next CleanupList members to append to. These point inside cleanup_. |
| CleanupNode* cleanup_ptr_; |
| CleanupNode* cleanup_limit_; |
| }; |
| |
| // Blocks are variable length malloc-ed objects. The following structure |
| // describes the common header for all blocks. |
| class LIBPROTOBUF_EXPORT Block { |
| public: |
| Block(size_t size, Block* next); |
| |
| char* Pointer(size_t n) { |
| GOOGLE_DCHECK(n <= size_); |
| return reinterpret_cast<char*>(this) + n; |
| } |
| |
| Block* next() const { return next_; } |
| size_t pos() const { return pos_; } |
| size_t size() const { return size_; } |
| void set_pos(size_t pos) { pos_ = pos; } |
| |
| private: |
| Block* next_; // Next block for this thread. |
| size_t pos_; |
| size_t size_; |
| // data follows |
| }; |
| |
| struct ThreadCache { |
| #if defined(GOOGLE_PROTOBUF_NO_THREADLOCAL) |
| // If we are using the ThreadLocalStorage class to store the ThreadCache, |
| // then the ThreadCache's default constructor has to be responsible for |
| // initializing it. |
| ThreadCache() : last_lifecycle_id_seen(-1), last_serial_arena(NULL) {} |
| #endif |
| |
| // The ThreadCache is considered valid as long as this matches the |
| // lifecycle_id of the arena being used. |
| int64 last_lifecycle_id_seen; |
| SerialArena* last_serial_arena; |
| }; |
| static std::atomic<int64> lifecycle_id_generator_; |
| #if defined(GOOGLE_PROTOBUF_NO_THREADLOCAL) |
| // Android ndk does not support GOOGLE_THREAD_LOCAL keyword so we use a custom thread |
| // local storage class we implemented. |
| // iOS also does not support the GOOGLE_THREAD_LOCAL keyword. |
| static ThreadCache& thread_cache(); |
| #elif defined(PROTOBUF_USE_DLLS) |
| // Thread local variables cannot be exposed through DLL interface but we can |
| // wrap them in static functions. |
| static ThreadCache& thread_cache(); |
| #else |
| static GOOGLE_THREAD_LOCAL ThreadCache thread_cache_; |
| static ThreadCache& thread_cache() { return thread_cache_; } |
| #endif |
| |
| void Init(); |
| |
| // Free all blocks and return the total space used which is the sums of sizes |
| // of the all the allocated blocks. |
| uint64 FreeBlocks(); |
| // Delete or Destruct all objects owned by the arena. |
| void CleanupList(); |
| |
| inline void CacheSerialArena(SerialArena* serial) { |
| thread_cache().last_serial_arena = serial; |
| thread_cache().last_lifecycle_id_seen = lifecycle_id_; |
| // TODO(haberman): evaluate whether we would gain efficiency by getting rid |
| // of hint_. It's the only write we do to ArenaImpl in the allocation path, |
| // which will dirty the cache line. |
| |
| hint_.store(serial, std::memory_order_release); |
| } |
| |
| |
| std::atomic<SerialArena*> |
| threads_; // Pointer to a linked list of SerialArena. |
| std::atomic<SerialArena*> hint_; // Fast thread-local block access |
| std::atomic<size_t> space_allocated_; // Total size of all allocated blocks. |
| |
| Block *initial_block_; // If non-NULL, points to the block that came from |
| // user data. |
| |
| Block* NewBlock(Block* last_block, size_t min_bytes); |
| |
| SerialArena* GetSerialArena(); |
| bool GetSerialArenaFast(SerialArena** arena); |
| SerialArena* GetSerialArenaFallback(void* me); |
| int64 lifecycle_id_; // Unique for each arena. Changes on Reset(). |
| |
| Options options_; |
| |
| GOOGLE_DISALLOW_EVIL_CONSTRUCTORS(ArenaImpl); |
| // All protos have pointers back to the arena hence Arena must have |
| // pointer stability. |
| ArenaImpl(ArenaImpl&&) = delete; |
| ArenaImpl& operator=(ArenaImpl&&) = delete; |
| |
| public: |
| // kBlockHeaderSize is sizeof(Block), aligned up to the nearest multiple of 8 |
| // to protect the invariant that pos is always at a multiple of 8. |
| static const size_t kBlockHeaderSize = (sizeof(Block) + 7) & -8; |
| static const size_t kSerialArenaSize = (sizeof(SerialArena) + 7) & -8; |
| static_assert(kBlockHeaderSize % 8 == 0, |
| "kBlockHeaderSize must be a multiple of 8."); |
| static_assert(kSerialArenaSize % 8 == 0, |
| "kSerialArenaSize must be a multiple of 8."); |
| }; |
| |
| } // namespace internal |
| } // namespace protobuf |
| |
| } // namespace google |
| #endif // GOOGLE_PROTOBUF_ARENA_IMPL_H__ |