| // 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 <limits> |
| |
| #include <google/protobuf/stubs/atomic_sequence_num.h> |
| #include <google/protobuf/stubs/atomicops.h> |
| #include <google/protobuf/stubs/common.h> |
| #include <google/protobuf/stubs/logging.h> |
| #include <google/protobuf/stubs/mutex.h> |
| #include <google/protobuf/stubs/type_traits.h> |
| |
| 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) { |
| 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: |
| // 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 len; // Number of elements currently present. |
| size_t size; // Total elements in the list. |
| CleanupChunk* next; // Next node in the list. |
| CleanupNode nodes[1]; // True length is |size|. |
| }; |
| |
| // Blocks are variable length malloc-ed objects. The following structure |
| // describes the common header for all blocks. |
| struct Block { |
| void* owner; // &ThreadCache of thread that owns this block. |
| Block* next; // Next block in arena (may have different owner) |
| CleanupChunk* cleanup; // Head of cleanup list (may point to another block, |
| // but it must have the same owner). |
| // ((char*) &block) + pos is next available byte. It is always |
| // aligned at a multiple of 8 bytes. |
| size_t pos; |
| size_t size; // total size of the block. |
| GOOGLE_ATTRIBUTE_ALWAYS_INLINE size_t avail() const { return size - pos; } |
| // data follows |
| }; |
| |
| struct ThreadCache { |
| // The ThreadCache is considered valid as long as this matches the |
| // lifecycle_id of the arena being used. |
| int64 last_lifecycle_id_seen; |
| Block* last_block_used_; |
| }; |
| |
| // kHeaderSize 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 kHeaderSize = (sizeof(Block) + 7) & -8; |
| #if LANG_CXX11 |
| static_assert(kHeaderSize % 8 == 0, "kHeaderSize must be a multiple of 8."); |
| #endif |
| static google::protobuf::internal::SequenceNumber 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(Block* head); |
| |
| void AddCleanupInBlock(Block* b, void* elem, void (*cleanup)(void*)); |
| Block* ExpandCleanupList(Block* b); |
| // Delete or Destruct all objects owned by the arena. |
| void CleanupList(Block* head); |
| uint64 ResetInternal(); |
| |
| inline void CacheBlock(Block* block) { |
| thread_cache().last_block_used_ = block; |
| thread_cache().last_lifecycle_id_seen = lifecycle_id_; |
| google::protobuf::internal::Release_Store(&hint_, reinterpret_cast<google::protobuf::internal::AtomicWord>(block)); |
| } |
| |
| google::protobuf::internal::AtomicWord blocks_; // Head of linked list of all allocated blocks |
| google::protobuf::internal::AtomicWord hint_; // Fast thread-local block access |
| uint64 space_allocated_; // Sum of sizes of all allocated blocks. |
| |
| bool owns_first_block_; // Indicates that arena owns the first block |
| mutable Mutex blocks_lock_; |
| |
| void AddBlock(Block* b); |
| // Access must be synchronized, either by blocks_lock_ or by being called from |
| // Init()/Reset(). |
| void AddBlockInternal(Block* b); |
| // Returns a block owned by this thread. |
| Block* GetBlock(size_t n); |
| Block* GetBlockSlow(void* me, Block* my_full_block, size_t n); |
| Block* FindBlock(void* me); |
| Block* NewBlock(void* me, Block* my_last_block, size_t min_bytes, |
| size_t start_block_size, size_t max_block_size); |
| static void* AllocFromBlock(Block* b, size_t n); |
| |
| int64 lifecycle_id_; // Unique for each arena. Changes on Reset(). |
| |
| Options options_; |
| |
| GOOGLE_DISALLOW_EVIL_CONSTRUCTORS(ArenaImpl); |
| }; |
| |
| } // namespace internal |
| } // namespace protobuf |
| |
| } // namespace google |
| #endif // GOOGLE_PROTOBUF_ARENA_IMPL_H__ |