ceph/src/common/containers.h

   1 // -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*-
   2 // vim: ts=8 sw=2 smarttab
   3 //
   4 // Ceph - scalable distributed file system
   5 //
   6 // Copyright (C) 2018 Red Hat, Inc.
   7 //
   8 // This is free software; you can redistribute it and/or
   9 // modify it under the terms of the GNU Lesser General Public
  10 // License version 2.1, as published by the Free Software
  11 // Foundation.  See file COPYING.
  12 //
  13
  14 #ifndef CEPH_COMMON_CONTAINERS_H
  15 #define CEPH_COMMON_CONTAINERS_H
  16
  17 #include <cstdint>
  18 #include <type_traits>
  19
  20 namespace ceph::containers {
  21
  22 // tiny_vector – CPU friendly, small_vector-like container for mutexes,
  23 // atomics and other non-movable things.
  24 //
  25 // The purpose of the container is to store arbitrary number of objects
  26 // with absolutely minimal requirements regarding constructibility
  27 // and assignability while minimizing memory indirection.
  28 // There is no obligation for MoveConstructibility, CopyConstructibility,
  29 // MoveAssignability, CopyAssignability nor even DefaultConstructibility
  30 // which allows to handle std::mutexes, std::atomics or any type embedding
  31 // them.
  32 //
  33 // Few requirements translate into tiny interface. The container isn't
  34 // Copy- nor MoveConstructible. Although it does offer random access
  35 // iterator, insertion in the middle is not allowed. The maximum number
  36 // of elements must be known at run-time. This shouldn't be an issue in
  37 // the intended use case: sharding.
  38 //
  39 // For the special case of no internal slots (InternalCapacity eq 0),
  40 // tiny_vector doesn't require moving any elements (changing pointers
  41 // is enough), and thus should be MoveConstructibile.
  42 //
  43 // Alternatives:
  44 //  1. std::vector<boost::optional<ValueT>> initialized with the known
  45 //     size and emplace_backed(). boost::optional inside provides
  46 //     the DefaultConstructibility. Imposes extra memory indirection.
  47 //  2. boost::container::small_vector + boost::optional always
  48 //     requires MoveConstructibility.
  49 //  3. boost::container::static_vector feed via emplace_back().
  50 //     Good for performance but enforces upper limit on elements count.
  51 //     For sharding this means we can't handle arbitrary number of
  52 //     shards (weird configs).
  53 //  4. std::unique_ptr<ValueT>: extra indirection together with memory
  54 //     fragmentation.
  55
  56 template<typename Value, std::size_t InternalCapacity = 0>
  57 class tiny_vector {
  58   // NOTE: to avoid false sharing consider aligning to cache line
  59   using storage_unit_t = \
  60     std::aligned_storage_t<sizeof(Value), alignof(Value)>;
  61
  62   std::size_t _size = 0;
  63   storage_unit_t* const data = nullptr;
  64   storage_unit_t internal[InternalCapacity];
  65
  66 public:
  67   typedef std::size_t size_type;
  68   typedef std::add_lvalue_reference_t<Value> reference;
  69   typedef std::add_const_t<reference> const_reference;
  70   typedef std::add_pointer_t<Value> pointer;
  71
  72   // emplacer is the piece of weirdness that comes from handling
  73   // unmovable-and-uncopyable things. The only way to instantiate
  74   // such types I know is to create instances in-place perfectly
  75   // forwarding necessary data to constructor.
  76   // Abstracting that is the exact purpose of emplacer.
  77   //
  78   // The usage scenario is:
  79   //   1. The tiny_vector's ctor is provided with a) maximum number
  80   //      of instances and b) a callable taking emplacer.
  81   //   2. The callable can (but isn't obliged to!) use emplacer to
  82   //      construct an instance without knowing at which address
  83   //      in memory it will be put. Callable is also supplied with
  84   //      an unique integer from the range <0, maximum number of
  85   //      instances).
  86   //   3. If callable decides to instantiate, it calls ::emplace
  87   //      of emplacer passing all arguments required by the type
  88   //      hold in tiny_vector.
  89   //
  90   // Example:
  91   // ```
  92   //   static constexpr const num_internally_allocated_slots = 32;
  93   //   tiny_vector<T, num_internally_allocated_slots> mytinyvec {
  94   //     num_of_instances,
  95   //     [](const size_t i, auto emplacer) {
  96   //       emplacer.emplace(argument_for_T_ctor);
  97   //     }
  98   //   }
  99   // ```
 100   //
 101   // For the sake of supporting the ceph::make_mutex() family of
 102   // factories, which relies on C++17's guaranteed copy elision,
 103   // the emplacer provides `data()` to retrieve the location for
 104   // constructing the instance with placement-new. This is handy
 105   // as the `emplace()` depends on perfect forwarding, and thus
 106   // interfere with the elision for cases like:
 107   // ```
 108   //   emplacer.emplace(ceph::make_mutex("mtx-name"));
 109   // ```
 110   // See: https://stackoverflow.com/a/52498826
 111
 112   class emplacer {
 113     friend class tiny_vector;
 114
 115     tiny_vector* parent;
 116     emplacer(tiny_vector* const parent)
 117       : parent(parent) {
 118     }
 119
 120   public:
 121     void* data() {
 122       void* const ret = &parent->data[parent->_size++];
 123       parent = nullptr;
 124       return ret;
 125     }
 126
 127     template<class... Args>
 128     void emplace(Args&&... args) {
 129       if (parent) {
 130         new (data()) Value(std::forward<Args>(args)...);
 131       }
 132     }
 133   };
 134
 135   template<typename F>
 136   tiny_vector(const std::size_t count, F&& f)
 137     : data(count <= InternalCapacity ? internal
 138                                      : new storage_unit_t[count]) {
 139     for (std::size_t i = 0; i < count; ++i) {
 140       // caller MAY emplace up to `count` elements but it IS NOT
 141       // obliged to do so. The emplacer guarantees that the limit
 142       // will never be exceeded.
 143       f(i, emplacer(this));
 144     }
 145   }
 146
 147   ~tiny_vector() {
 148     for (auto& elem : *this) {
 149       elem.~Value();
 150     }
 151
 152     const auto data_addr = reinterpret_cast<std::uintptr_t>(data);
 153     const auto this_addr = reinterpret_cast<std::uintptr_t>(this);
 154     if (data_addr < this_addr ||
 155         data_addr >= this_addr + sizeof(*this)) {
 156       delete[] data;
 157     }
 158   }
 159
 160   reference       operator[](size_type pos) {
 161     return reinterpret_cast<reference>(data[pos]);
 162   }
 163   const_reference operator[](size_type pos) const {
 164     return reinterpret_cast<const_reference>(data[pos]);
 165   }
 166
 167   size_type size() const {
 168     return _size;
 169   }
 170
 171   pointer begin() {
 172     return reinterpret_cast<pointer>(&data[0]);
 173   }
 174   pointer end() {
 175     return reinterpret_cast<pointer>(&data[_size]);
 176   }
 177
 178   const pointer begin() const {
 179     return reinterpret_cast<pointer>(&data[0]);
 180   }
 181   const pointer end() const {
 182     return reinterpret_cast<pointer>(&data[_size]);
 183   }
 184
 185   const pointer cbegin() const {
 186     return reinterpret_cast<pointer>(&data[0]);
 187   }
 188   const pointer cend() const {
 189     return reinterpret_cast<pointer>(&data[_size]);
 190   }
 191 };
 192
 193 } // namespace ceph::containers
 194
 195 #endif // CEPH_COMMON_CONTAINERS_H