ceph/src/include/mempool.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) 2016 Allen Samuels <allen.samuels@sandisk.com>
   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
  15 #ifndef _CEPH_INCLUDE_MEMPOOL_H
  16 #define _CEPH_INCLUDE_MEMPOOL_H
  17
  18 #include <cstddef>
  19 #include <map>
  20 #include <unordered_map>
  21 #include <set>
  22 #include <vector>
  23 #include <list>
  24 #include <mutex>
  25 #include <atomic>
  26 #include <typeinfo>
  27
  28 #include <common/Formatter.h>
  29 #include "include/assert.h"
  30
  31
  32 /*
  33
  34 Memory Pools
  35 ============
  36
  37 A memory pool is a method for accounting the consumption of memory of
  38 a set of containers.
  39
  40 Memory pools are statically declared (see pool_index_t).
  41
  42 Each memory pool tracks the number of bytes and items it contains.
  43
  44 Allocators can be declared and associated with a type so that they are
  45 tracked independently of the pool total.  This additional accounting
  46 is optional and only incurs an overhead if the debugging is enabled at
  47 runtime.  This allows developers to see what types are consuming the
  48 pool resources.
  49
  50
  51 Declaring
  52 ---------
  53
  54 Using memory pools is very easy.
  55
  56 To create a new memory pool, simply add a new name into the list of
  57 memory pools that's defined in "DEFINE_MEMORY_POOLS_HELPER".  That's
  58 it.  :)
  59
  60 For each memory pool that's created a C++ namespace is also
  61 automatically created (name is same as in DEFINE_MEMORY_POOLS_HELPER).
  62 That namespace contains a set of common STL containers that are predefined
  63 with the appropriate allocators.
  64
  65 Thus for mempool "unittest_1" we have automatically available to us:
  66
  67    mempool::unittest_1::map
  68    mempool::unittest_1::multimap
  69    mempool::unittest_1::set
  70    mempool::unittest_1::multiset
  71    mempool::unittest_1::list
  72    mempool::unittest_1::vector
  73    mempool::unittest_1::unordered_map
  74
  75
  76 Putting objects in a mempool
  77 ----------------------------
  78
  79 In order to use a memory pool with a particular type, a few additional
  80 declarations are needed.
  81
  82 For a class:
  83
  84   struct Foo {
  85     MEMPOOL_CLASS_HELPERS();
  86     ...
  87   };
  88
  89 Then, in an appropriate .cc file,
  90
  91   MEMPOOL_DEFINE_OBJECT_FACTORY(Foo, foo, unittest_1);
  92
  93 The second argument can generally be identical to the first, except
  94 when the type contains a nested scope.  For example, for
  95 BlueStore::Onode, we need to do
  96
  97   MEMPOOL_DEFINE_OBJECT_FACTORY(BlueStore::Onode, bluestore_onode,
  98                                 bluestore_meta);
  99
 100 (This is just because we need to name some static variables and we
 101 can't use :: in a variable name.)
 102
 103 In order to use the STL containers, simply use the namespaced variant
 104 of the container type.  For example,
 105
 106   mempool::unittest_1::map<int> myvec;
 107
 108 Introspection
 109 -------------
 110
 111 The simplest way to interrogate the process is with
 112
 113   Formater *f = ...
 114   mempool::dump(f);
 115
 116 This will dump information about *all* memory pools.  When debug mode
 117 is enabled, the runtime complexity of dump is O(num_shards *
 118 num_types).  When debug name is disabled it is O(num_shards).
 119
 120 You can also interrogate a specific pool programmatically with
 121
 122   size_t bytes = mempool::unittest_2::allocated_bytes();
 123   size_t items = mempool::unittest_2::allocated_items();
 124
 125 The runtime complexity is O(num_shards).
 126
 127 Note that you cannot easily query per-type, primarily because debug
 128 mode is optional and you should not rely on that information being
 129 available.
 130
 131 */
 132
 133 namespace mempool {
 134
 135 // --------------------------------------------------------------
 136 // define memory pools
 137
 138 #define DEFINE_MEMORY_POOLS_HELPER(f) \
 139   f(bloom_filter)                     \
 140   f(bluestore_meta_onode)             \
 141   f(bluestore_meta_other)             \
 142   f(bluestore_alloc)                  \
 143   f(bluestore_fsck)                   \
 144   f(bluefs)                           \
 145   f(buffer_meta)                      \
 146   f(buffer_data)                      \
 147   f(osd)                              \
 148   f(osdmap)                           \
 149   f(osdmap_mapping)                   \
 150   f(unittest_1)                       \
 151   f(unittest_2)
 152
 153
 154 // give them integer ids
 155 #define P(x) mempool_##x,
 156 enum pool_index_t {
 157   DEFINE_MEMORY_POOLS_HELPER(P)
 158   num_pools        // Must be last.
 159 };
 160 #undef P
 161
 162 extern bool debug_mode;
 163 extern void set_debug_mode(bool d);
 164
 165 // --------------------------------------------------------------
 166 class pool_t;
 167
 168 // we shard pool stats across many shard_t's to reduce the amount
 169 // of cacheline ping pong.
 170 enum {
 171   num_shard_bits = 5
 172 };
 173 enum {
 174   num_shards = 1 << num_shard_bits
 175 };
 176
 177 // align shard to a cacheline
 178 struct shard_t {
 179   std::atomic<size_t> bytes = {0};
 180   std::atomic<size_t> items = {0};
 181   char __padding[128 - sizeof(std::atomic<size_t>)*2];
 182 } __attribute__ ((aligned (128)));
 183
 184 static_assert(sizeof(shard_t) == 128, "shard_t should be cacheline-sized");
 185
 186 struct stats_t {
 187   ssize_t items = 0;
 188   ssize_t bytes = 0;
 189   void dump(ceph::Formatter *f) const {
 190     f->dump_int("items", items);
 191     f->dump_int("bytes", bytes);
 192   }
 193 };
 194
 195 pool_t& get_pool(pool_index_t ix);
 196 const char *get_pool_name(pool_index_t ix);
 197
 198 struct type_t {
 199   const char *type_name;
 200   size_t item_size;
 201   std::atomic<ssize_t> items = {0};  // signed
 202 };
 203
 204 struct type_info_hash {
 205   std::size_t operator()(const std::type_info& k) const {
 206     return k.hash_code();
 207   }
 208 };
 209
 210 class pool_t {
 211   shard_t shard[num_shards];
 212
 213   mutable std::mutex lock;  // only used for types list
 214   std::unordered_map<const char *, type_t> type_map;
 215
 216 public:
 217   //
 218   // How much this pool consumes. O(<num_shards>)
 219   //
 220   size_t allocated_bytes() const;
 221   size_t allocated_items() const;
 222
 223   shard_t* pick_a_shard() {
 224     // Dirt cheap, see:
 225     //   http://fossies.org/dox/glibc-2.24/pthread__self_8c_source.html
 226     size_t me = (size_t)pthread_self();
 227     size_t i = (me >> 3) & ((1 << num_shard_bits) - 1);
 228     return &shard[i];
 229   }
 230
 231   type_t *get_type(const std::type_info& ti, size_t size) {
 232     std::lock_guard<std::mutex> l(lock);
 233     auto p = type_map.find(ti.name());
 234     if (p != type_map.end()) {
 235       return &p->second;
 236     }
 237     type_t &t = type_map[ti.name()];
 238     t.type_name = ti.name();
 239     t.item_size = size;
 240     return &t;
 241   }
 242
 243   // get pool stats.  by_type is not populated if !debug
 244   void get_stats(stats_t *total,
 245                  std::map<std::string, stats_t> *by_type) const;
 246
 247   void dump(ceph::Formatter *f) const;
 248 };
 249
 250 void dump(ceph::Formatter *f);
 251
 252
 253 // STL allocator for use with containers.  All actual state
 254 // is stored in the static pool_allocator_base_t, which saves us from
 255 // passing the allocator to container constructors.
 256
 257 template<pool_index_t pool_ix, typename T>
 258 class pool_allocator {
 259   pool_t *pool;
 260   type_t *type = nullptr;
 261
 262 public:
 263   typedef pool_allocator<pool_ix, T> allocator_type;
 264   typedef T value_type;
 265   typedef value_type *pointer;
 266   typedef const value_type * const_pointer;
 267   typedef value_type& reference;
 268   typedef const value_type& const_reference;
 269   typedef std::size_t size_type;
 270   typedef std::ptrdiff_t difference_type;
 271
 272   template<typename U> struct rebind {
 273     typedef pool_allocator<pool_ix,U> other;
 274   };
 275
 276   void init(bool force_register) {
 277     pool = &get_pool(pool_ix);
 278     if (debug_mode || force_register) {
 279       type = pool->get_type(typeid(T), sizeof(T));
 280     }
 281   }
 282
 283   pool_allocator(bool force_register=false) {
 284     init(force_register);
 285   }
 286   template<typename U>
 287   pool_allocator(const pool_allocator<pool_ix,U>&) {
 288     init(false);
 289   }
 290
 291   T* allocate(size_t n, void *p = nullptr) {
 292     size_t total = sizeof(T) * n;
 293     shard_t *shard = pool->pick_a_shard();
 294     shard->bytes += total;
 295     shard->items += n;
 296     if (type) {
 297       type->items += n;
 298     }
 299     T* r = reinterpret_cast<T*>(new char[total]);
 300     return r;
 301   }
 302
 303   void deallocate(T* p, size_t n) {
 304     size_t total = sizeof(T) * n;
 305     shard_t *shard = pool->pick_a_shard();
 306     shard->bytes -= total;
 307     shard->items -= n;
 308     if (type) {
 309       type->items -= n;
 310     }
 311     delete[] reinterpret_cast<char*>(p);
 312   }
 313
 314   T* allocate_aligned(size_t n, size_t align, void *p = nullptr) {
 315     size_t total = sizeof(T) * n;
 316     shard_t *shard = pool->pick_a_shard();
 317     shard->bytes += total;
 318     shard->items += n;
 319     if (type) {
 320       type->items += n;
 321     }
 322     char *ptr;
 323     int rc = ::posix_memalign((void**)(void*)&ptr, align, total);
 324     if (rc)
 325       throw std::bad_alloc();
 326     T* r = reinterpret_cast<T*>(ptr);
 327     return r;
 328   }
 329
 330   void deallocate_aligned(T* p, size_t n) {
 331     size_t total = sizeof(T) * n;
 332     shard_t *shard = pool->pick_a_shard();
 333     shard->bytes -= total;
 334     shard->items -= n;
 335     if (type) {
 336       type->items -= n;
 337     }
 338     ::free(p);
 339   }
 340
 341   void destroy(T* p) {
 342     p->~T();
 343   }
 344
 345   template<class U>
 346   void destroy(U *p) {
 347     p->~U();
 348   }
 349
 350   void construct(T* p, const T& val) {
 351     ::new ((void *)p) T(val);
 352   }
 353
 354   template<class U, class... Args> void construct(U* p,Args&&... args) {
 355     ::new((void *)p) U(std::forward<Args>(args)...);
 356   }
 357
 358   bool operator==(const pool_allocator&) const { return true; }
 359   bool operator!=(const pool_allocator&) const { return false; }
 360 };
 361
 362
 363 // Namespace mempool
 364
 365 #define P(x)                                                            \
 366   namespace x {                                                         \
 367     static const mempool::pool_index_t id = mempool::mempool_##x;       \
 368     template<typename v>                                                \
 369     using pool_allocator = mempool::pool_allocator<id,v>;               \
 370                                                                         \
 371     using string = std::basic_string<char,std::char_traits<char>,       \
 372                                      pool_allocator<char>>;             \
 373                                                                         \
 374     template<typename k,typename v, typename cmp = std::less<k> >       \
 375     using map = std::map<k, v, cmp,                                     \
 376                          pool_allocator<std::pair<const k,v>>>;         \
 377                                                                         \
 378     template<typename k,typename v, typename cmp = std::less<k> >       \
 379     using multimap = std::multimap<k,v,cmp,                             \
 380                                    pool_allocator<std::pair<const k,    \
 381                                                             v>>>;       \
 382                                                                         \
 383     template<typename k, typename cmp = std::less<k> >                  \
 384     using set = std::set<k,cmp,pool_allocator<k>>;                      \
 385                                                                         \
 386     template<typename v>                                                \
 387     using list = std::list<v,pool_allocator<v>>;                        \
 388                                                                         \
 389     template<typename v>                                                \
 390     using vector = std::vector<v,pool_allocator<v>>;                    \
 391                                                                         \
 392     template<typename k, typename v,                                    \
 393              typename h=std::hash<k>,                                   \
 394              typename eq = std::equal_to<k>>                            \
 395     using unordered_map =                                               \
 396       std::unordered_map<k,v,h,eq,pool_allocator<std::pair<const k,v>>>;\
 397                                                                         \
 398     inline size_t allocated_bytes() {                                   \
 399       return mempool::get_pool(id).allocated_bytes();                   \
 400     }                                                                   \
 401     inline size_t allocated_items() {                                   \
 402       return mempool::get_pool(id).allocated_items();                   \
 403     }                                                                   \
 404   };
 405
 406 DEFINE_MEMORY_POOLS_HELPER(P)
 407
 408 #undef P
 409
 410 };
 411
 412
 413
 414 // Use this for any type that is contained by a container (unless it
 415 // is a class you defined; see below).
 416 #define MEMPOOL_DECLARE_FACTORY(obj, factoryname, pool)                 \
 417   namespace mempool {                                                   \
 418     namespace pool {                                                    \
 419       extern pool_allocator<obj> alloc_##factoryname;                   \
 420     }                                                                   \
 421   }
 422
 423 #define MEMPOOL_DEFINE_FACTORY(obj, factoryname, pool)                  \
 424   namespace mempool {                                                   \
 425     namespace pool {                                                    \
 426       pool_allocator<obj> alloc_##factoryname = {true};                 \
 427     }                                                                   \
 428   }
 429
 430 // Use this for each class that belongs to a mempool.  For example,
 431 //
 432 //   class T {
 433 //     MEMPOOL_CLASS_HELPERS();
 434 //     ...
 435 //   };
 436 //
 437 #define MEMPOOL_CLASS_HELPERS()                                         \
 438   void *operator new(size_t size);                                      \
 439   void *operator new[](size_t size) noexcept {                          \
 440     assert(0 == "no array new");                                        \
 441     return nullptr; }                                                   \
 442   void  operator delete(void *);                                        \
 443   void  operator delete[](void *) { assert(0 == "no array delete"); }
 444
 445
 446 // Use this in some particular .cc file to match each class with a
 447 // MEMPOOL_CLASS_HELPERS().
 448 #define MEMPOOL_DEFINE_OBJECT_FACTORY(obj,factoryname,pool)             \
 449   MEMPOOL_DEFINE_FACTORY(obj, factoryname, pool)                        \
 450   void *obj::operator new(size_t size) {                                \
 451     return mempool::pool::alloc_##factoryname.allocate(1); \
 452   }                                                                     \
 453   void obj::operator delete(void *p)  {                                 \
 454     return mempool::pool::alloc_##factoryname.deallocate((obj*)p, 1);   \
 455   }
 456
 457 #endif