MemArena.h

Go to the documentation of this file.

// SPDX-License-Identifier: Apache-2.0
// Copyright Verizon Media 2020
 
#pragma once
 
#include <mutex>
#include <memory>
#include <stdexcept>
#include <type_traits>
#include <utility>
#include <new>
#if __has_include(<memory_resource>)
#include <memory_resource>
#endif
 
#include "swoc/MemSpan.h"
#include "swoc/Scalar.h"
#include "swoc/IntrusiveDList.h"
#include "swoc/TextView.h"
 
namespace swoc { inline namespace SWOC_VERSION_NS {

class MemArena
#if __has_include(<memory_resource>)
  : public std::pmr::memory_resource
#endif
{
  using self_type = MemArena; 
 
public:
  static constexpr size_t DEFAULT_ALIGNMENT{1}; 

  static void (*destroyer)(self_type *);

  using unique_ptr = std::unique_ptr<self_type, void (*)(self_type *)>;

  struct Block {
    static constexpr size_t MIN_FREE_SPACE = 16;

    char *data();

    const char *data() const;

    char *allocated_data_end();

    const char *allocated_data_end() const;

    size_t remaining() const;

    static size_t align_padding(void const *ptr, size_t align);

    bool satisfies(size_t n, size_t align) const;

    MemSpan<void> remnant();

    MemSpan<void> alloc(size_t n, size_t = DEFAULT_ALIGNMENT);

    Block &discard();

    bool contains(const void *ptr) const;

    bool is_full() const;
 
  protected:
    friend MemArena; 

    static void* operator new(size_t block_size, size_t n);

    static void* operator new([[maybe_unused]] size_t block_size, void* place) noexcept;

    static void operator delete(void *ptr) noexcept;

    static void operator delete([[maybe_unused]] void *ptr, void *place) noexcept;

    explicit Block(size_t n) noexcept;
 
    size_t size;         
    size_t allocated{0}; 
 
    struct Linkage {
      Block *_next{nullptr};
      Block *_prev{nullptr};
 
      static Block *&next_ptr(Block *);
 
      static Block *&prev_ptr(Block *);
    } _link; 
  };

  using BlockList = IntrusiveDList<Block::Linkage>;

  explicit MemArena(size_t n = DEFAULT_BLOCK_SIZE);

  explicit MemArena(MemSpan<void> static_block);

  MemArena(self_type const &that) = delete;

  MemArena(self_type &&that) noexcept;

  ~MemArena();

  self_type &operator=(self_type const &that) = delete;

  self_type &operator=(self_type &&that) noexcept;

  static self_type *construct_self_contained(size_t n = DEFAULT_BLOCK_SIZE);

  MemSpan<void> alloc(size_t n, size_t align = DEFAULT_ALIGNMENT);

  template <typename T> MemSpan<T> alloc_span(size_t n);

  template <typename T, typename... Args> T *make(Args &&...args);

  MemSpan<char> localize(MemSpan<char const> s);

  MemSpan<char> localize(char const * s);

  MemSpan<char> localize_c(MemSpan<char const> s);

  MemSpan<char> localize_c(char const * s);

  MemArena &freeze(size_t n = 0);

  self_type &thaw();

  MemArena &clear(size_t hint = 0);

  MemArena &discard(MemSpan<void const> span);

  MemArena &discard(size_t hint = 0);

  size_t size() const;

  size_t remaining() const;

  template <typename T> MemSpan<T> remnant_span(size_t n);

  MemSpan<void> remnant();

  MemSpan<void> remnant(size_t n, size_t align = DEFAULT_ALIGNMENT);

  self_type &require(size_t n, size_t align = DEFAULT_ALIGNMENT);

  size_t allocated_size() const;

  bool contains(const void *ptr) const;

  size_t reserved_size() const;
 
  using const_iterator = BlockList::const_iterator; 
  using iterator       = const_iterator;            

  const_iterator begin() const;

  const_iterator end() const;

  const_iterator frozen_begin() const;

  const_iterator frozen_end() const;
 
protected:
  Block *make_block(size_t n);

  void destroy_frozen();

  void destroy_active();
 
  using Page        = Scalar<4096>;            
  using QuarterPage = Scalar<Page::SCALE / 4>; 
  using Paragraph   = Scalar<16>;              
 
  static constexpr size_t ALLOC_HEADER_SIZE = 16; 
  static constexpr size_t DEFAULT_BLOCK_SIZE = Page::SCALE - Paragraph{round_up(ALLOC_HEADER_SIZE + sizeof(Block))};
 
  size_t _active_allocated = 0; 
  size_t _active_reserved  = 0; 
  size_t _frozen_allocated = 0;
  size_t _frozen_reserved = 0; 

  size_t _reserve_hint = 0;
 
  BlockList _frozen; 
  BlockList _active; 

  Block *_static_block = nullptr;
 
  // Note on _active block list - blocks that become full are moved to the end of the list.
  // This means that when searching for a block with space, the first full block encountered
  // marks the last block to check. This keeps the set of blocks to check short.
 
private:
#if __has_include(<memory_resource>)
  // PMR support methods.

  void *do_allocate(std::size_t bytes, std::size_t align) override;

  void do_deallocate(void *, size_t, size_t) override;

  bool do_is_equal(std::pmr::memory_resource const &that) const noexcept override;
#endif
};

template <typename T> class FixedArena {
  using self_type = FixedArena; 
protected:
  struct Item {
    Item *_next; 
  };
 
  Item _list{nullptr}; 
  MemArena &_arena;    
 
public:
  explicit FixedArena(MemArena &arena);

  template <typename... Args> T *make(Args... args);

  void destroy(T *t);

  void clear();

  MemArena &arena();
};
 
// --- Implementation ---
 
inline auto
MemArena::Block::Linkage::next_ptr(Block *b) -> Block *& {
  return b->_link._next;
}
 
inline auto
MemArena::Block::Linkage::prev_ptr(Block *b) -> Block *& {
  return b->_link._prev;
}
 
inline MemArena::Block::Block(size_t n) noexcept : size(n) {}
 
inline char *
MemArena::Block::data() {
  return reinterpret_cast<char *>(this + 1);
}
 
inline const char *
MemArena::Block::data() const {
  return reinterpret_cast<const char *>(this + 1);
}
 
inline char *
MemArena::Block::allocated_data_end() {
  return this->data() + allocated;
}
 
inline const char *
MemArena::Block::allocated_data_end() const {
  return this->data() + allocated;
}
 
inline bool
MemArena::Block::contains(const void *ptr) const {
  const char *base = this->data();
  return base <= ptr && ptr < base + size;
}
 
inline size_t
MemArena::Block::remaining() const {
  return size - allocated;
}
 
inline bool
MemArena::Block::is_full() const {
  return this->remaining() < MIN_FREE_SPACE;
}
 
inline MemSpan<void>
MemArena::Block::alloc(size_t n, size_t align) {
  auto base = this->data() + allocated;
  auto pad  = align_padding(base, align);
  if ((n + pad) > this->remaining()) {
    throw(std::invalid_argument{"MemArena::Block::alloc size is more than remaining."});
  }
  MemSpan<void> zret = this->remnant().prefix(n + pad);
  zret.remove_prefix(pad);
  allocated += n + pad;
  return zret;
}
 
inline MemSpan<void>
MemArena::Block::remnant() {
  return {this->data() + allocated, this->remaining()};
}
 
inline MemArena::Block &
MemArena::Block::discard() {
  allocated = 0;
  return *this;
}
 
inline void*
MemArena::Block::operator new(size_t block_size, size_t n)
{
  if (n < block_size) {
    throw std::invalid_argument("MemArena::Block::operator new size is less than object size.");
  }
  // In theory we could use ::operator new(n) but this causes a size mismatch during ::operator delete.
  // Easier to use malloc here and also override @c delete.
  auto b = static_cast<Block *>(::malloc(n));
  if (b == nullptr) {
    throw std::bad_alloc();
  }
  return b;
}
 
inline void*
MemArena::Block::operator new([[maybe_unused]] size_t block_size, void* place) noexcept {
  return place;
}
 
inline void
MemArena::Block::operator delete(void *ptr) noexcept {
  ::free(ptr);
}
inline void
MemArena::Block::operator delete([[maybe_unused]] void *ptr, void *place) noexcept {
  ::free(place);
}
 
inline size_t
MemArena::Block::align_padding(void const *ptr, size_t align) {
  if (auto delta = uintptr_t(ptr) & (align - 1); delta > 0) {
    return align - delta;
  }
  return 0;
}
 
inline MemArena::MemArena(size_t n) : _reserve_hint(n) {}
 
template <typename T>
MemSpan<T>
MemArena::alloc_span(size_t n) {
  return this->alloc(sizeof(T) * n, alignof(T)).rebind<T>();
}
 
template <typename T, typename... Args>
T *
MemArena::make(Args &&...args) {
  return new (this->alloc(sizeof(T), alignof(T)).data()) T(std::forward<Args>(args)...);
}
 
inline MemSpan<char> MemArena::localize(MemSpan<char const> s) {
  auto span = this->alloc(s.size()).rebind<char>();
  memcpy(span.data(), s.data(), span.size());
  return { span.data(), span.size() };
}
 
inline MemSpan<char> MemArena::localize(char const * s) {
  return this->localize(MemSpan<char const>(s, strlen(s)));
}
 
inline MemSpan<char> MemArena::localize_c(MemSpan<char const> s) {
  auto span = this->alloc(s.size() + 1).rebind<char>();
  memcpy(span.data(), s.data(), span.size());
  span[s.size()] = '\0';
  return { span.data(), span.size() };
}
 
inline MemSpan<char> MemArena::localize_c(char const * s) {
  return this->localize_c(MemSpan<char const>(s, strlen(s)));
}
 
template <typename T>
MemSpan<T>
MemArena::remnant_span(size_t n) {
  auto span = this->require(sizeof(T) * n, alignof(T)).remnant();
  return span.remove_prefix(Block::align_padding(span.data(), alignof(T))).rebind<T>();
}
 
template <>
inline MemSpan<void>
MemArena::remnant_span<void>(size_t n) {
  return this->require(n).remnant().prefix(n);
}
 
inline MemSpan<void>
MemArena::remnant(size_t n, size_t align) {
  return this->require(n, align).remnant().prefix(n);
}
 
inline size_t
MemArena::size() const {
  return _active_allocated;
}
 
inline size_t
MemArena::allocated_size() const {
  return _frozen_allocated + _active_allocated;
}
 
inline size_t
MemArena::remaining() const {
  return _active.empty() ? 0 : _active.head()->remaining();
}
 
inline MemSpan<void>
MemArena::remnant() {
  return _active.empty() ? MemSpan<void>() : _active.head()->remnant();
}
 
inline size_t
MemArena::reserved_size() const {
  return _active_reserved + _frozen_reserved;
}
 
inline auto
MemArena::begin() const -> const_iterator {
  return _active.begin();
}
 
inline auto
MemArena::end() const -> const_iterator {
  return _active.end();
}
 
inline auto
MemArena::frozen_begin() const -> const_iterator {
  return _frozen.begin();
}
 
inline auto
MemArena::frozen_end() const -> const_iterator {
  return _frozen.end();
}
 
template <typename T> FixedArena<T>::FixedArena(MemArena &arena) : _arena(arena) {
  static_assert(sizeof(T) >= sizeof(T *));
}
 
template <typename T>
template <typename... Args>
T *
FixedArena<T>::make(Args... args) {
  if (_list._next) {
    void *t     = _list._next;
    _list._next = _list._next->_next;
    return new (t) T(std::forward<Args>(args)...);
  }
  return _arena.template make<T>(std::forward<Args>(args)...);
}
 
template <typename T>
void
FixedArena<T>::destroy(T *t) {
  if (t) {
    t->~T(); // destructor.
    auto item   = reinterpret_cast<Item *>(t);
    item->_next = _list._next;
    _list._next = item;
  }
}
 
template <typename T>
void
FixedArena<T>::clear() {
  _list._next = nullptr;
}
 
template <typename T>
MemArena &
FixedArena<T>::arena() {
  return _arena;
}

 
}} // namespace swoc::SWOC_VERSION_NS