// Protocol Buffers - Google's data interchange format

// Copyright 2022 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 the internal class SerialArena

#ifndef GOOGLE_PROTOBUF_SERIAL_ARENA_H__

#define GOOGLE_PROTOBUF_SERIAL_ARENA_H__

#include <algorithm>

#include <atomic>

#include <string>

#include <type_traits>

#include <typeinfo>

#include <utility>

#include "google/protobuf/stubs/common.h"

#include "absl/base/attributes.h"

#include "absl/log/absl_check.h"

#include "absl/numeric/bits.h"

#include "google/protobuf/arena_align.h"

#include "google/protobuf/arena_cleanup.h"

#include "google/protobuf/arena_config.h"

#include "google/protobuf/arenaz_sampler.h"

#include "google/protobuf/port.h"

#include "google/protobuf/string_block.h"

// Must be included last.

#include "google/protobuf/port_def.inc"

namespace google {

namespace protobuf {

namespace internal {

// Arena blocks are variable length malloc-ed objects.  The following structure

// describes the common header for all blocks.

struct ArenaBlock {

  // For the sentry block with zero-size where ptr_, limit_, cleanup_nodes all

  // point to "this".

  constexpr ArenaBlock()

      : next(nullptr), cleanup_nodes(this), size(0) {}

  ArenaBlock(ArenaBlock* next, size_t size)

      : next(next), cleanup_nodes(nullptr), size(size) {

    ABSL_DCHECK_GT(size, sizeof(ArenaBlock));

  }

  char* Pointer(size_t n) {

    ABSL_DCHECK_LE(n, size);

    return reinterpret_cast<char*>(this) + n;

  }

  char* Limit() { return Pointer(size & static_cast<size_t>(-8)); }

  bool IsSentry() const { return size == 0; }

  ArenaBlock* const next;

  void* cleanup_nodes;

  const size_t size;

  // data follows

};

enum class AllocationClient { kDefault, kArray };

class ThreadSafeArena;

// Tag type used to invoke the constructor of the first SerialArena.

struct FirstSerialArena {

  explicit FirstSerialArena() = default;

};

// A simple arena allocator. Calls to allocate functions must be properly

// serialized by the caller, hence this class cannot be used as a general

// purpose allocator in a multi-threaded program. It serves as a building block

// for ThreadSafeArena, which provides a thread-safe arena allocator.

//

// This class manages

// 1) Arena bump allocation + owning memory blocks.

// 2) Maintaining a cleanup list.

// It delegates the actual memory allocation back to ThreadSafeArena, which

// contains the information on block growth policy and backing memory allocation

// used.

class PROTOBUF_EXPORT SerialArena {

 public:

  void CleanupList();

  size_t FreeStringBlocks() {

    // On the active block delete all strings skipping the unused instances.

    size_t unused_bytes = string_block_unused_.load(std::memory_order_relaxed);

    if (string_block_ != nullptr) {

      return FreeStringBlocks(string_block_, unused_bytes);

    }

    return 0;

  }

  uint64_t SpaceAllocated() const {

    return space_allocated_.load(std::memory_order_relaxed);

  }

  uint64_t SpaceUsed() const;

  bool HasSpace(size_t n) const {

    return n <= static_cast<size_t>(limit_ - ptr());

  }

  // See comments on `cached_blocks_` member for details.

  PROTOBUF_ALWAYS_INLINE void* TryAllocateFromCachedBlock(size_t size) {

    if (PROTOBUF_PREDICT_FALSE(size < 16)) return nullptr;

    // We round up to the next larger block in case the memory doesn't match

    // the pattern we are looking for.

    const size_t index = absl::bit_width(size - 1) - 4;

    if (index >= cached_block_length_) return nullptr;

    auto& cached_head = cached_blocks_[index];

    if (cached_head == nullptr) return nullptr;

    void* ret = cached_head;

    PROTOBUF_UNPOISON_MEMORY_REGION(ret, size);

    cached_head = cached_head->next;

    return ret;

  }

  // In kArray mode we look through cached blocks.

  // We do not do this by default because most non-array allocations will not

  // have the right size and will fail to find an appropriate cached block.

  //

  // TODO(sbenza): Evaluate if we should use cached blocks for message types of

  // the right size. We can statically know if the allocation size can benefit

  // from it.

  template <AllocationClient alloc_client = AllocationClient::kDefault>

  void* AllocateAligned(size_t n) {

    ABSL_DCHECK(internal::ArenaAlignDefault::IsAligned(n));

    ABSL_DCHECK_GE(limit_, ptr());

    if (alloc_client == AllocationClient::kArray) {

      if (void* res = TryAllocateFromCachedBlock(n)) {

        return res;

      }

    }

    if (PROTOBUF_PREDICT_FALSE(!HasSpace(n))) {

      return AllocateAlignedFallback(n);

    }

    return AllocateFromExisting(n);

  }

 private:

  static inline PROTOBUF_ALWAYS_INLINE constexpr size_t AlignUpTo(size_t n,

                                                                  size_t a) {

    // We are wasting space by over allocating align - 8 bytes. Compared to a

    // dedicated function that takes current alignment in consideration.  Such a

    // scheme would only waste (align - 8)/2 bytes on average, but requires a

    // dedicated function in the outline arena allocation functions. Possibly

    // re-evaluate tradeoffs later.

    return a <= 8 ? ArenaAlignDefault::Ceil(n) : ArenaAlignAs(a).Padded(n);

  }

  static inline PROTOBUF_ALWAYS_INLINE void* AlignTo(void* p, size_t a) {

    return (a <= ArenaAlignDefault::align)

               ? ArenaAlignDefault::CeilDefaultAligned(p)

               : ArenaAlignAs(a).CeilDefaultAligned(p);

  }

  void* AllocateFromExisting(size_t n) {

    PROTOBUF_UNPOISON_MEMORY_REGION(ptr(), n);

    void* ret = ptr();

    set_ptr(static_cast<char*>(ret) + n);

    return ret;

  }

  // See comments on `cached_blocks_` member for details.

  void ReturnArrayMemory(void* p, size_t size) {

    // We only need to check for 32-bit platforms.

    // In 64-bit platforms the minimum allocation size from Repeated*Field will

    // be 16 guaranteed.

    if (sizeof(void*) < 8) {

      if (PROTOBUF_PREDICT_FALSE(size < 16)) return;

    } else {

      PROTOBUF_ASSUME(size >= 16);

    }

    // We round down to the next smaller block in case the memory doesn't match

    // the pattern we are looking for. eg, someone might have called Reserve()

    // on the repeated field.

    const size_t index = absl::bit_width(size) - 5;

    if (PROTOBUF_PREDICT_FALSE(index >= cached_block_length_)) {

      // We can't put this object on the freelist so make this object the

      // freelist. It is guaranteed it is larger than the one we have, and

      // large enough to hold another allocation of `size`.

      CachedBlock** new_list = static_cast<CachedBlock**>(p);

      size_t new_size = size / sizeof(CachedBlock*);

      std::copy(cached_blocks_, cached_blocks_ + cached_block_length_,

                new_list);

      // We need to unpoison this memory before filling it in case it has been

      // poisoned by another santizer client.

      PROTOBUF_UNPOISON_MEMORY_REGION(

          new_list + cached_block_length_,

          (new_size - cached_block_length_) * sizeof(CachedBlock*));

      std::fill(new_list + cached_block_length_, new_list + new_size, nullptr);

      cached_blocks_ = new_list;

      // Make the size fit in uint8_t. This is the power of two, so we don't

      // need anything larger.

      cached_block_length_ =

          static_cast<uint8_t>(std::min(size_t{64}, new_size));

      return;

    }

    auto& cached_head = cached_blocks_[index];

    auto* new_node = static_cast<CachedBlock*>(p);

    new_node->next = cached_head;

    cached_head = new_node;

    PROTOBUF_POISON_MEMORY_REGION(p, size);

  }

 public:

  // Allocate space if the current region provides enough space.

  bool MaybeAllocateAligned(size_t n, void** out) {

    ABSL_DCHECK(internal::ArenaAlignDefault::IsAligned(n));

    ABSL_DCHECK_GE(limit_, ptr());

    if (PROTOBUF_PREDICT_FALSE(!HasSpace(n))) return false;

    *out = AllocateFromExisting(n);

    return true;

  }

  // If there is enough space in the current block, allocate space for one `T`

  // object and register for destruction. The object has not been constructed

  // and the memory returned is uninitialized.

  template <typename T>

  PROTOBUF_ALWAYS_INLINE void* MaybeAllocateWithCleanup() {

    ABSL_DCHECK_GE(limit_, ptr());

    static_assert(!std::is_trivially_destructible<T>::value,

                  "This function is only for non-trivial types.");

    constexpr int aligned_size = ArenaAlignDefault::Ceil(sizeof(T));

    constexpr auto destructor = cleanup::arena_destruct_object<T>;

    size_t required = aligned_size + cleanup::Size(destructor);

    if (PROTOBUF_PREDICT_FALSE(!HasSpace(required))) {

      return nullptr;

    }

    void* ptr = AllocateFromExistingWithCleanupFallback(aligned_size,

                                                        alignof(T), destructor);

    PROTOBUF_ASSUME(ptr != nullptr);

    return ptr;

  }

  PROTOBUF_ALWAYS_INLINE

  void* AllocateAlignedWithCleanup(size_t n, size_t align,

                                   void (*destructor)(void*)) {

    size_t required = AlignUpTo(n, align) + cleanup::Size(destructor);

    if (PROTOBUF_PREDICT_FALSE(!HasSpace(required))) {

      return AllocateAlignedWithCleanupFallback(n, align, destructor);

    }

    return AllocateFromExistingWithCleanupFallback(n, align, destructor);

  }

  PROTOBUF_ALWAYS_INLINE

  void AddCleanup(void* elem, void (*destructor)(void*)) {

    size_t required = cleanup::Size(destructor);

    if (PROTOBUF_PREDICT_FALSE(!HasSpace(required))) {

      return AddCleanupFallback(elem, destructor);

    }

    AddCleanupFromExisting(elem, destructor);

  }

  ABSL_ATTRIBUTE_RETURNS_NONNULL void* AllocateFromStringBlock();

 private:

  bool MaybeAllocateString(void*& p);

  ABSL_ATTRIBUTE_RETURNS_NONNULL void* AllocateFromStringBlockFallback();

  void* AllocateFromExistingWithCleanupFallback(size_t n, size_t align,

                                                void (*destructor)(void*)) {

    n = AlignUpTo(n, align);

    PROTOBUF_UNPOISON_MEMORY_REGION(ptr(), n);

    void* ret = ArenaAlignAs(align).CeilDefaultAligned(ptr());

    set_ptr(ptr() + n);

    ABSL_DCHECK_GE(limit_, ptr());

    AddCleanupFromExisting(ret, destructor);

    return ret;

  }

  PROTOBUF_ALWAYS_INLINE

  void AddCleanupFromExisting(void* elem, void (*destructor)(void*)) {

    cleanup::Tag tag = cleanup::Type(destructor);

    size_t n = cleanup::Size(tag);

    PROTOBUF_UNPOISON_MEMORY_REGION(limit_ - n, n);

    limit_ -= n;

    ABSL_DCHECK_GE(limit_, ptr());

    cleanup::CreateNode(tag, limit_, elem, destructor);

  }

 private:

  friend class ThreadSafeArena;

  // Creates a new SerialArena inside mem using the remaining memory as for

  // future allocations.

  // The `parent` arena must outlive the serial arena, which is guaranteed

  // because the parent manages the lifetime of the serial arenas.

  static SerialArena* New(SizedPtr mem, ThreadSafeArena& parent);

  // Free SerialArena returning the memory passed in to New

  template <typename Deallocator>

  SizedPtr Free(Deallocator deallocator);

  static size_t FreeStringBlocks(StringBlock* string_block, size_t unused);

  // Members are declared here to track sizeof(SerialArena) and hotness

  // centrally. They are (roughly) laid out in descending order of hotness.

  // 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.

  std::atomic<char*> ptr_{nullptr};

  // Limiting address up to which memory can be allocated from the head block.

  char* limit_ = nullptr;

  // The active string block.

  StringBlock* string_block_ = nullptr;

  // The number of unused bytes in string_block_.

  // We allocate from `effective_size()` down to 0 inside `string_block_`.

  // `unused  == 0` means that `string_block_` is exhausted. (or null).

  std::atomic<size_t> string_block_unused_{0};

  std::atomic<ArenaBlock*> head_{nullptr};  // Head of linked list of blocks.

  std::atomic<size_t> space_used_{0};       // Necessary for metrics.

  std::atomic<size_t> space_allocated_{0};

  ThreadSafeArena& parent_;

  // Repeated*Field and Arena play together to reduce memory consumption by

  // reusing blocks. Currently, natural growth of the repeated field types makes

  // them allocate blocks of size `8 + 2^N, N>=3`.

  // When the repeated field grows returns the previous block and we put it in

  // this free list.

  // `cached_blocks_[i]` points to the free list for blocks of size `8+2^(i+3)`.

  // The array of freelists is grown when needed in `ReturnArrayMemory()`.

  struct CachedBlock {

    // Simple linked list.

    CachedBlock* next;

  };

  uint8_t cached_block_length_ = 0;

  CachedBlock** cached_blocks_ = nullptr;

  // Helper getters/setters to handle relaxed operations on atomic variables.

  ArenaBlock* head() { return head_.load(std::memory_order_relaxed); }

  const ArenaBlock* head() const {

    return head_.load(std::memory_order_relaxed);

  }

  char* ptr() { return ptr_.load(std::memory_order_relaxed); }

  const char* ptr() const { return ptr_.load(std::memory_order_relaxed); }

  void set_ptr(char* ptr) { return ptr_.store(ptr, std::memory_order_relaxed); }

  // Constructor is private as only New() should be used.

  inline SerialArena(ArenaBlock* b, ThreadSafeArena& parent);

  // Constructors to handle the first SerialArena.

  inline explicit SerialArena(ThreadSafeArena& parent);

  inline SerialArena(FirstSerialArena, ArenaBlock* b, ThreadSafeArena& parent);

  void* AllocateAlignedFallback(size_t n);

  void* AllocateAlignedWithCleanupFallback(size_t n, size_t align,

                                           void (*destructor)(void*));

  void AddCleanupFallback(void* elem, void (*destructor)(void*));

  inline void AllocateNewBlock(size_t n);

  inline void Init(ArenaBlock* b, size_t offset);

 public:

  static constexpr size_t kBlockHeaderSize =

      ArenaAlignDefault::Ceil(sizeof(ArenaBlock));

};

inline PROTOBUF_ALWAYS_INLINE bool SerialArena::MaybeAllocateString(void*& p) {

  // Check how many unused instances are in the current block.

  size_t unused_bytes = string_block_unused_.load(std::memory_order_relaxed);

  if (PROTOBUF_PREDICT_TRUE(unused_bytes != 0)) {

    unused_bytes -= sizeof(std::string);

    string_block_unused_.store(unused_bytes, std::memory_order_relaxed);

    p = string_block_->AtOffset(unused_bytes);

    return true;

  }

  return false;

}

template <>

inline PROTOBUF_ALWAYS_INLINE void*

SerialArena::MaybeAllocateWithCleanup<std::string>() {

  void* p;

  return MaybeAllocateString(p) ? p : nullptr;

}

ABSL_ATTRIBUTE_RETURNS_NONNULL inline PROTOBUF_ALWAYS_INLINE void*

SerialArena::AllocateFromStringBlock() {

  void* p;

  if (ABSL_PREDICT_TRUE(MaybeAllocateString(p))) return p;

  return AllocateFromStringBlockFallback();

}

}  // namespace internal

}  // namespace protobuf

}  // namespace google

#include "google/protobuf/port_undef.inc"

#endif  // GOOGLE_PROTOBUF_SERIAL_ARENA_H__