allocator_with_stats.hpp

//
// Copyright 2014 Felix Petriconi
//
// License: http://boost.org/LICENSE_1_0.txt, Boost License 1.0
//
// Authors:
//          http://erdani.com, Andrei Alexandrescu
//          Implementation in D from
//          https://github.com/andralex/phobos/blob/allocator/std/allocator.d
//          http://petriconi.net, Felix Petriconi
//
#pragma once

#include "allocator_base.hpp"
#include "affix_allocator.hpp"
#include "internal/traits.hpp"
#include "internal/noatomic.hpp"
#include <atomic>
#include <chrono>

namespace alb {

#define ALLOCATE(A, N) A.allocate(N, __FILE__, __FUNCTION__, __LINE__)

#define MEMBER_ACCESSOR(X)                                                     \
private:                                                                       \
  statistic_type X##_;                                                         \
public:                                                                        \
  size_t X() const noexcept { return X##_.load(); }                            \


inline namespace v_100 {
enum StatsOptions : unsigned {
  NumOwns = 1u << 0,
  NumAllocate = 1u << 1,
  NumAllocateOK = 1u << 2,
  NumExpand = 1u << 3,
  NumExpandOK = 1u << 4,
  NumReallocate = 1u << 5,
  NumReallocateOK = 1u << 6,
  NumReallocateInPlace = 1u << 7,
  NumDeallocate = 1u << 8,
  NumDeallocateAll = 1u << 9,
  NumAll = (1u << 10) - 1,
  BytesAllocated = 1u << 10,
  BytesDeallocated = 1u << 11,
  BytesExpanded = 1u << 12,
  BytesContracted = 1u << 13,
  BytesMoved = 1u << 14,
  BytesSlack = 1u << 15,
  BytesHighTide = 1u << 16,
  BytesAll = ((1u << 17) - 1) & ~NumAll,
  CallerSize = 1u << 17,
  CallerFile = 1u << 18,
  CallerFunction = 1u << 19,
  CallerLine = 1u << 20,
  CallerTime = 1u << 21,
  CallerAll = ((1u << 22) - 1) & ~NumAll & ~BytesAll,
  All = (1u << 22) - 1
};

template <bool Shared, class Allocator, unsigned Flags = alb::StatsOptions::All>
class allocator_with_stats_base {
public:
  struct AllocationInfo {
    size_t callerSize;
    const char *callerFile;
    const char *callerFunction;
    int callerLine;

    /* The comparison does not take the allocation time into account
    * It is a template to be able to compare the AllocationInfo from different
    * allocators
    */
    template <typename RHS> 
    bool operator==(const RHS &rhs) const {
      return callerSize == rhs.callerSize &&
             (callerFile == rhs.callerFile ||
              ::strcmp(callerFile, rhs.callerFile) == 0) &&
             (callerFunction == rhs.callerFunction ||
              ::strcmp(callerFunction, rhs.callerFunction) == 0);
    }

    std::chrono::time_point<std::chrono::system_clock> callerTime;
    AllocationInfo *previous, *next;
  };

  class Allocations {
  public:
    class iterator {
    public:
      using iterator_category = std::bidirectional_iterator_tag;
      using value_type = AllocationInfo *;
      using difference_type = ptrdiff_t;
      using pointer = value_type;
      using const_pointer = const pointer;
      using reference = value_type;
      using const_reference = const reference;

      iterator() : _node{nullptr} {}

      explicit iterator(AllocationInfo *data) : _node{data} {}

      reference operator*() const { return _node; }

      pointer operator->() const { return &(operator*()); }

      iterator &operator++() {
        _node = _node->next;
        return *this;
      }

      iterator operator++(int) {
        iterator tmp = *this;
        ++*this;
        return tmp;
      }

      iterator &operator--() {
        _node = _node->previous();
        return *this;
      }

      iterator operator--(int) {
        iterator tmp = *this;
        --*this;
        return tmp;
      }

      friend bool operator==(const iterator &x, const iterator &y) {
        return x._node == y._node;
      }

      friend bool operator!=(const iterator &x, const iterator &y) {
        return !(x == y);
      }

    private:
      AllocationInfo *_node;
    };

  public:
    using const_iterator = const iterator;

    explicit Allocations(AllocationInfo *root) : _begin(root), _end(nullptr) {}

    const_iterator cbegin() const { return _begin; }

    const_iterator cend() const { return _end; }

    bool empty() const { return _begin == _end; }

  private:
    const const_iterator _begin;
    const const_iterator _end;
  };

  static const bool HasPerAllocationState =
      (Flags & (StatsOptions::CallerTime | StatsOptions::CallerFile |
                StatsOptions::CallerLine)) != 0;
  
  static_assert(HasPerAllocationState && !Shared,
    "Currently it is not supported to collect per file/line/time stats in shared mode!");

  using statistic_type = typename traits::type_switch<std::atomic<size_t>, internal::no_atomic<size_t>, Shared>::type;

// Simplification for defining all members and accessors.
#define MEMBER_ACCESSORS                                                       \
  MEMBER_ACCESSOR(num_owns)                                                    \
  MEMBER_ACCESSOR(num_allocate)                                                \
  MEMBER_ACCESSOR(num_allocate_ok)                                             \
  MEMBER_ACCESSOR(num_expand)                                                  \
  MEMBER_ACCESSOR(num_expand_ok)                                               \
  MEMBER_ACCESSOR(num_reallocate)                                              \
  MEMBER_ACCESSOR(num_reallocate_ok)                                           \
  MEMBER_ACCESSOR(num_reallocate_in_place)                                     \
  MEMBER_ACCESSOR(num_deallocate)                                              \
  MEMBER_ACCESSOR(num_deallocate_all)                                          \
  MEMBER_ACCESSOR(bytes_allocated)                                             \
  MEMBER_ACCESSOR(bytes_deallocated)                                           \
  MEMBER_ACCESSOR(bytes_expanded)                                              \
  MEMBER_ACCESSOR(bytes_contracted)                                            \
  MEMBER_ACCESSOR(bytes_moved)                                                 \
  MEMBER_ACCESSOR(bytes_slack)                                                 \
  MEMBER_ACCESSOR(bytes_high_tide)

  MEMBER_ACCESSORS

#undef MEMBER_ACCESSOR
#undef MEMBER_ACCESSORS

  static constexpr bool supports_truncated_deallocation =
      Allocator::supports_truncated_deallocation;
  static constexpr bool has_per_allocation_state = HasPerAllocationState;
  static constexpr unsigned alignment = Allocator::alignment;

  allocator_with_stats_base() noexcept : num_owns_(0),
                                         num_allocate_(0),
                                         num_allocate_ok_(0),
                                         num_expand_(0),
                                         num_expand_ok_(0),
                                         num_reallocate_(0),
                                         num_reallocate_ok_(0),
                                         num_reallocate_in_place_(0),
                                         num_deallocate_(0),
                                         num_deallocate_all_(0),
                                         bytes_allocated_(0),
                                         bytes_deallocated_(0),
                                         bytes_expanded_(0),
                                         bytes_contracted_(0),
                                         bytes_moved_(0),
                                         bytes_slack_(0),
                                         bytes_high_tide_(0),
                                         root_(nullptr) {}

  block allocate(size_t n, const char *file = nullptr,
                 const char *function = nullptr, int line = 0) noexcept {

    auto result = allocator_.allocate(n);
    up(StatsOptions::NumAllocate, num_allocate_);
    upOK(StatsOptions::NumAllocateOK, num_allocate_ok_, n > 0 && result);
    add(StatsOptions::BytesAllocated, bytes_allocated_, result.length);
    update_high_tide();

    if (has_per_allocation_state) {
      if (result) {
        AllocationInfo *stat =
            traits::affix_extractor<decltype(allocator_),
                                    AllocationInfo>::prefix(allocator_, result);

        set(StatsOptions::CallerSize, stat->callerSize, n);
        set(StatsOptions::CallerFile, stat->callerFile, file);
        set(StatsOptions::CallerFunction, stat->callerFunction, function);
        set(StatsOptions::CallerLine, stat->callerLine, line);
        set(StatsOptions::CallerTime, stat->callerTime,
            std::chrono::system_clock::now());

        // push into caller info stack
        if (root_) {
          root_->previous = stat;
          stat->next = root_;
          stat->previous = nullptr;
          root_ = stat;
        } else { // create the new stack
          stat->previous = nullptr;
          stat->next = nullptr;
          root_ = stat;
        }
      }
    }
    return result;
  }

  void deallocate(block &b) noexcept {
    up(StatsOptions::NumDeallocate, num_deallocate_);
    add(StatsOptions::BytesDeallocated, bytes_deallocated_, b.length);

    if (has_per_allocation_state) {
      if (b) {
        auto stat =
            traits::affix_extractor<decltype(allocator_),
                                    AllocationInfo>::prefix(allocator_, b);
        if (stat->previous) {
          stat->previous->next = stat->next;
        }
        if (stat->next) {
          stat->next->previous = stat->previous;
        }
        if (stat == root_) {
          root_ = stat->previous;
        }
      }
    }
    allocator_.deallocate(b);
  }

  bool reallocate(block &b, size_t n) noexcept {
    auto originalBlock = b;
    auto wasRootBlock(false);
    if (has_per_allocation_state) {
      if (b) {
        wasRootBlock =
            root_ ==
            traits::affix_extractor<decltype(allocator_),
                                    AllocationInfo>::prefix(allocator_, b);
      }
    }
    up(StatsOptions::NumReallocate, num_reallocate_);

    if (!allocator_.reallocate(b, n)) {
      return false;
    }
    up(StatsOptions::NumReallocateOK, num_reallocate_ok_);
    std::make_signed<size_t>::type delta = b.length - originalBlock.length;
    if (b.ptr == originalBlock.ptr) {
      up(StatsOptions::NumReallocateInPlace, num_reallocate_in_place_);
      if (delta > 0) {
        add(StatsOptions::BytesAllocated, bytes_allocated_, delta);
        add(StatsOptions::BytesExpanded, bytes_expanded_, delta);
      } else {
        add(StatsOptions::BytesDeallocated, bytes_deallocated_, -delta);
        add(StatsOptions::BytesContracted, bytes_contracted_, -delta);
      }
    } // was moved to a new location
    else {
      add(StatsOptions::BytesAllocated, bytes_allocated_, b.length);
      add(StatsOptions::BytesMoved, bytes_moved_, originalBlock.length);
      add(StatsOptions::BytesDeallocated, bytes_deallocated_,
          originalBlock.length);

      if (has_per_allocation_state) {
        if (b) {
          auto stat =
              traits::affix_extractor<decltype(allocator_),
                                      AllocationInfo>::prefix(allocator_, b);
          if (stat->next) {
            stat->next->previous = stat;
          }
          if (stat->previous) {
            stat->previous->next = stat;
          }
          if (wasRootBlock) {
            root_ = stat;
          }
        }
      }
    }
    update_high_tide();
    return true;
  }

  template <typename U = Allocator>
  typename std::enable_if<traits::has_owns<U>::value, bool>::type
  owns(const block &b) const noexcept {
    up(StatsOptions::NumOwns, num_owns_);
    return allocator_.owns(b);
  }

  template <typename U = Allocator>
  typename std::enable_if<traits::has_expand<U>::value, bool>::type
  expand(block &b, size_t delta) noexcept {
    up(StatsOptions::NumExpand, num_expand_);
    auto oldLength = b.length;
    auto result = allocator_.expand(b, delta);
    if (result) {
      up(StatsOptions::NumExpandOK, num_expand_ok_);
      add(StatsOptions::BytesExpanded, bytes_expanded_, b.length - oldLength);
      add(StatsOptions::BytesAllocated, bytes_allocated_, b.length - oldLength);
      update_high_tide();
      // if (b && has_per_allocation_state) {
      //   auto stat = traits::AffixExtractor<
      //       decltype(allocator_), AllocationInfo>::prefix(allocator_, b);
      // }
    }
    return result;
  }

  Allocations allocations() const noexcept { return Allocations(root_); }

private:
  template <typename T> 
  inline void up(StatsOptions option, T &value) const noexcept {
    if (Flags & option)
      ++value;
  }

  template <typename T>
  inline void upOK(StatsOptions option, T &value, bool ok) const noexcept {
    if (Flags & option && ok)
      ++value;
  }

  template <typename T>
  void inline add(StatsOptions option, T &value,
                  typename std::make_signed<typename T::type>::type delta) const noexcept {
    if (Flags & option)
      value += delta;
  }

  template <typename T> 
  inline void set(StatsOptions option, T &value, T t) const noexcept {
    if (Flags & option)
      value = std::move(t);
  }

  void update_high_tide() noexcept {
    if (Flags & StatsOptions::BytesHighTide) {
      const size_t currentlyAllocated = bytes_allocated_ - bytes_deallocated_;
      if (bytes_high_tide_ < currentlyAllocated) {
        bytes_high_tide_ = currentlyAllocated;
      }
    }
  }

  typename traits::type_switch<affix_allocator<Allocator, AllocationInfo>,
                               Allocator,
                               HasPerAllocationState>::type allocator_;

  AllocationInfo *root_;
};


template <class Allocator, unsigned Flags = alb::StatsOptions::All>
class allocator_with_stats : public allocator_with_stats_base<false, Allocator, Flags>
{
public:
  allocator_with_stats() noexcept {}
};

// template <class Allocator, unsigned Flags = alb::StatsOptions::All>
// class shared_allocator_with_stats : public allocator_with_stats_base<true, Allocator, Flags>
// {
// public:
//  shared_allocator_with_stats() noexcept {}
//};

}
using namespace v_100;
}