// 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>
#include <google/protobuf/stubs/port.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_PROTOBUF_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__
