ceph/src/os/bluestore/BitAllocator.h

   1 // -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*-
   2 // vim: ts=8 sw=2 smarttab
   3 /*
   4  * Bitmap based in memory allocator.
   5  * Author: Ramesh Chander, Ramesh.Chander@sandisk.com
   6  */
   7
   8 #ifndef  CEPH_OS_BLUESTORE_BITALLOCATOR_H
   9 #define CEPH_OS_BLUESTORE_BITALLOCATOR_H
  10
  11
  12 #include <assert.h>
  13 #include <stdint.h>
  14 #include <pthread.h>
  15 #include <mutex>
  16 #include <atomic>
  17 #include <vector>
  18 #include "include/intarith.h"
  19 #include "os/bluestore/bluestore_types.h"
  20
  21 #define alloc_assert assert
  22
  23 #ifdef BIT_ALLOCATOR_DEBUG
  24 #define alloc_dbg_assert(x) assert(x)
  25 #else
  26 #define alloc_dbg_assert(x) (static_cast<void> (0))
  27 #endif
  28
  29
  30 class BitAllocatorStats {
  31 public:
  32   std::atomic<int64_t> m_total_alloc_calls;
  33   std::atomic<int64_t> m_total_free_calls;
  34   std::atomic<int64_t> m_total_allocated;
  35   std::atomic<int64_t> m_total_freed;
  36   std::atomic<int64_t> m_total_serial_scans;
  37   std::atomic<int64_t> m_total_concurrent_scans;
  38   std::atomic<int64_t> m_total_node_scanned;
  39
  40   BitAllocatorStats() {
  41     m_total_alloc_calls = 0;
  42     m_total_free_calls = 0;
  43     m_total_allocated = 0;
  44     m_total_freed = 0;
  45     m_total_serial_scans = 0;
  46     m_total_concurrent_scans = 0;
  47     m_total_node_scanned = 0;
  48   }
  49
  50   void add_alloc_calls(int64_t val) {
  51     std::atomic_fetch_add(&m_total_alloc_calls, val);
  52   }
  53   void add_free_calls(int64_t val) {
  54     std::atomic_fetch_add(&m_total_free_calls, val);
  55   }
  56   void add_allocated(int64_t val) {
  57     std::atomic_fetch_add(&m_total_allocated, val);
  58   }
  59   void add_freed(int64_t val) {
  60     std::atomic_fetch_add(&m_total_freed, val);
  61   }
  62   void add_serial_scans(int64_t val) {
  63     std::atomic_fetch_add(&m_total_serial_scans, val);
  64   }
  65   void add_concurrent_scans(int64_t val) {
  66     std::atomic_fetch_add(&m_total_concurrent_scans, val);
  67   }
  68   void add_node_scanned(int64_t val) {
  69     std::atomic_fetch_add(&m_total_node_scanned, val);
  70   }
  71 };
  72
  73 template <class BitMapEntity>
  74 class BitMapEntityIter {
  75   typedef mempool::bluestore_alloc::vector<BitMapEntity> BitMapEntityVector;
  76   BitMapEntityVector *m_list;
  77   int64_t m_start_idx;
  78   int64_t m_cur_idx;
  79   bool m_wrap;
  80   bool m_wrapped;
  81   bool m_end;
  82 public:
  83
  84   void init(BitMapEntityVector *list, bool wrap, int64_t start_idx) {
  85     m_list = list;
  86     m_wrap = wrap;
  87     m_start_idx = start_idx;
  88     m_cur_idx = m_start_idx;
  89     m_wrapped = false;
  90     m_end = false;
  91   }
  92
  93   BitMapEntityIter(BitMapEntityVector *list, int64_t start_idx) {
  94     init(list, false, start_idx);
  95   }
  96   BitMapEntityIter(BitMapEntityVector *list, int64_t start_idx, bool wrap) {
  97     init(list, wrap, start_idx);
  98   }
  99
 100   BitMapEntity *next() {
 101     int64_t cur_idx = m_cur_idx;
 102
 103     if (m_wrapped &&
 104       cur_idx == m_start_idx) {
 105       /*
 106        * End of wrap cycle + 1
 107        */
 108       if (!m_end) {
 109         m_end = true;
 110         return &(*m_list)[cur_idx];
 111       }
 112       return NULL;
 113     }
 114     m_cur_idx++;
 115
 116     if (m_cur_idx == (int64_t)m_list->size() &&
 117         m_wrap) {
 118       m_cur_idx = 0;
 119       m_wrapped = true;
 120     }
 121
 122     if (cur_idx == (int64_t)m_list->size()) {
 123       /*
 124        * End of list
 125        */
 126       return NULL;
 127     }
 128
 129     alloc_assert(cur_idx < (int64_t)m_list->size());
 130     return &(*m_list)[cur_idx];
 131   }
 132
 133   int64_t index() {
 134     return m_cur_idx;
 135   }
 136 };
 137
 138 typedef unsigned long bmap_t;
 139 typedef mempool::bluestore_alloc::vector<bmap_t> bmap_mask_vec_t;
 140
 141 class BmapEntry {
 142 private:
 143   bmap_t m_bits;
 144
 145 public:
 146   MEMPOOL_CLASS_HELPERS();
 147   static bmap_t full_bmask() {
 148     return (bmap_t) -1;
 149   }
 150   static int64_t size() {
 151     return (sizeof(bmap_t) * 8);
 152   }
 153   static bmap_t empty_bmask() {
 154     return (bmap_t) 0;
 155   }
 156   static bmap_t align_mask(int x) {
 157     return ((x) >= BmapEntry::size()? (bmap_t) -1 : (~(((bmap_t) -1) >> (x))));
 158   }
 159   static bmap_t bit_mask(int bit_num) {
 160     return (bmap_t) 0x1 << ((BmapEntry::size() - 1) - bit_num);
 161   }
 162   bmap_t atomic_fetch() {
 163     return m_bits;
 164   }
 165   BmapEntry(CephContext*, bool val);
 166   BmapEntry(CephContext*) {
 167     m_bits = 0;
 168   }
 169   BmapEntry(const BmapEntry& bmap) {
 170     m_bits = bmap.m_bits;
 171   }
 172
 173   void clear_bit(int bit);
 174   void clear_bits(int offset, int num_bits);
 175   void set_bits(int offset, int num_bits);
 176   bool check_n_set_bit(int bit);
 177   bool check_bit(int bit);
 178   bool is_allocated(int64_t start_bit, int64_t num_bits);
 179
 180   int find_n_cont_bits(int start_offset, int64_t num_bits);
 181   int find_n_free_bits(int start_idx, int64_t max_bits,
 182            int *free_bit, int *end_idx);
 183   int find_first_set_bits(int64_t required_blocks, int bit_offset,
 184           int *start_offset, int64_t *scanned);
 185
 186   void dump_state(CephContext* cct, const int& count);
 187   ~BmapEntry();
 188
 189 };
 190
 191 class BitMapArea {
 192 protected:
 193   int16_t m_area_index;
 194
 195 public:
 196   MEMPOOL_CLASS_HELPERS();
 197   static int64_t get_zone_size(CephContext* cct);
 198   static int64_t get_span_size(CephContext* cct);
 199   static int get_level(CephContext* cct, int64_t total_blocks);
 200   static int64_t get_level_factor(CephContext* cct, int level);
 201   virtual bool is_allocated(int64_t start_block, int64_t num_blocks) = 0;
 202   virtual bool is_exhausted() = 0;
 203   virtual bool child_check_n_lock(BitMapArea *child, int64_t required) {
 204       ceph_abort();
 205       return true;
 206   }
 207   virtual bool child_check_n_lock(BitMapArea *child, int64_t required, bool lock) {
 208       ceph_abort();
 209       return true;
 210   }
 211   virtual void child_unlock(BitMapArea *child) {
 212     ceph_abort();
 213   }
 214
 215   virtual void lock_excl() = 0;
 216   virtual bool lock_excl_try() {
 217     ceph_abort();
 218     return false;
 219   }
 220   virtual void lock_shared() {
 221     ceph_abort();
 222     return;
 223   }
 224   virtual void unlock() = 0;
 225
 226   virtual int64_t sub_used_blocks(int64_t num_blocks) = 0;
 227   virtual int64_t add_used_blocks(int64_t num_blocks) = 0;
 228   virtual bool reserve_blocks(int64_t num_blocks) = 0;
 229   virtual void unreserve(int64_t num_blocks, int64_t allocated) = 0;
 230   virtual int64_t get_reserved_blocks() = 0;
 231   virtual int64_t get_used_blocks() = 0;
 232
 233   virtual void shutdown() = 0;
 234
 235   virtual int64_t alloc_blocks_dis(int64_t num_blocks, int64_t min_alloc,
 236              int64_t hint, int64_t blk_off, ExtentList *block_list) {
 237     ceph_abort();
 238     return 0;
 239   }
 240
 241   virtual void set_blocks_used(int64_t start_block, int64_t num_blocks) = 0;
 242   virtual void free_blocks(int64_t start_block, int64_t num_blocks) = 0;
 243   virtual int64_t size() = 0;
 244
 245   int64_t child_count();
 246   int64_t get_index();
 247   int64_t get_level();
 248   virtual void dump_state(CephContext* cct, int& count) = 0;
 249   BitMapArea(CephContext*) { }
 250   virtual ~BitMapArea() { }
 251 };
 252
 253 class BitMapAreaList {
 254
 255 private:
 256   std::vector<BitMapArea*> m_items;
 257
 258 public:
 259   /* Must be DefaultConstructible as BitMapAreaIN and derivates employ
 260    * a deferred init, sorry. */
 261   BitMapAreaList() = default;
 262
 263   BitMapAreaList(std::vector<BitMapArea*>&& m_items)
 264     : m_items(std::move(m_items)) {
 265   }
 266
 267   BitMapArea *get_nth_item(const int64_t idx) {
 268     return m_items[idx];
 269   }
 270
 271   /* FIXME: we really should use size_t. */
 272   int64_t size() const {
 273     return m_items.size();
 274   }
 275 };
 276
 277 /* Intensionally inlined for the sake of BitMapAreaLeaf::alloc_blocks_dis_int. */
 278 class BmapEntityListIter {
 279   BitMapAreaList* m_list;
 280   int64_t m_start_idx;
 281   int64_t m_cur_idx;
 282   bool m_wrap;
 283   bool m_wrapped;
 284   bool m_end;
 285
 286 public:
 287   BmapEntityListIter(BitMapAreaList* const list,
 288                      const int64_t start_idx,
 289                      const bool wrap = false)
 290     : m_list(list),
 291       m_start_idx(start_idx),
 292       m_cur_idx(start_idx),
 293       m_wrap(wrap),
 294       m_wrapped(false),
 295       m_end(false) {
 296   }
 297
 298   BitMapArea* next() {
 299     int64_t cur_idx = m_cur_idx;
 300
 301     if (m_wrapped &&
 302       cur_idx == m_start_idx) {
 303       /*
 304        * End of wrap cycle + 1
 305        */
 306       if (!m_end) {
 307         m_end = true;
 308         return m_list->get_nth_item(cur_idx);
 309       }
 310       return NULL;
 311     }
 312     m_cur_idx++;
 313
 314     if (m_cur_idx == m_list->size() &&
 315         m_wrap) {
 316       m_cur_idx = 0;
 317       m_wrapped = true;
 318     }
 319     if (cur_idx == m_list->size()) {
 320       /*
 321        * End of list
 322        */
 323       return NULL;
 324     }
 325
 326     /* This method should be *really* fast as it's being executed over
 327      * and over during traversal of allocators indexes. */
 328     alloc_dbg_assert(cur_idx < m_list->size());
 329     return m_list->get_nth_item(cur_idx);
 330   }
 331
 332   int64_t index();
 333 };
 334
 335 typedef mempool::bluestore_alloc::vector<BmapEntry> BmapEntryVector;
 336
 337 class BitMapZone: public BitMapArea {
 338
 339 private:
 340   std::atomic<int32_t> m_used_blocks;
 341   BmapEntryVector m_bmap_vec;
 342   std::mutex m_lock;
 343
 344 public:
 345   MEMPOOL_CLASS_HELPERS();
 346   static int64_t count;
 347   static int64_t total_blocks;
 348   static void incr_count() { count++;}
 349   static int64_t get_total_blocks() {return total_blocks;}
 350   bool is_allocated(int64_t start_block, int64_t num_blocks) override;
 351   bool is_exhausted() override final;
 352   void reset_marker();
 353
 354   int64_t sub_used_blocks(int64_t num_blocks) override;
 355   int64_t add_used_blocks(int64_t num_blocks) override;
 356   bool reserve_blocks(int64_t num_blocks) override;
 357   void unreserve(int64_t num_blocks, int64_t allocated) override;
 358   int64_t get_reserved_blocks() override;
 359   int64_t get_used_blocks() override final;
 360   int64_t size() override final {
 361     return get_total_blocks();
 362   }
 363
 364   void lock_excl() override;
 365   bool lock_excl_try() override;
 366   void unlock() override;
 367   bool check_locked();
 368
 369   void free_blocks_int(int64_t start_block, int64_t num_blocks);
 370   void init(CephContext* cct, int64_t zone_num, int64_t total_blocks, bool def);
 371
 372   BitMapZone(CephContext* cct, int64_t total_blocks, int64_t zone_num);
 373   BitMapZone(CephContext* cct, int64_t total_blocks, int64_t zone_num, bool def);
 374
 375   ~BitMapZone() override;
 376   void shutdown() override;
 377   int64_t alloc_blocks_dis(int64_t num_blocks, int64_t min_alloc, int64_t hint,
 378         int64_t blk_off, ExtentList *block_list) override;
 379   void set_blocks_used(int64_t start_block, int64_t num_blocks) override;
 380
 381   void free_blocks(int64_t start_block, int64_t num_blocks) override;
 382   void dump_state(CephContext* cct, int& count) override;
 383 };
 384
 385 class BitMapAreaIN: public BitMapArea{
 386
 387 protected:
 388   int64_t m_child_size_blocks;
 389   int64_t m_total_blocks;
 390   int16_t m_level;
 391
 392   int64_t m_used_blocks;
 393   int64_t m_reserved_blocks;
 394   std::mutex m_blocks_lock;
 395   BitMapAreaList m_child_list;
 396
 397   bool is_allocated(int64_t start_block, int64_t num_blocks) override;
 398   bool is_exhausted() override;
 399
 400   bool child_check_n_lock(BitMapArea *child, int64_t required, bool lock) override {
 401     ceph_abort();
 402     return false;
 403   }
 404
 405   bool child_check_n_lock(BitMapArea *child, int64_t required) override;
 406   void child_unlock(BitMapArea *child) override;
 407
 408   void lock_excl() override {
 409     return;
 410   }
 411   void lock_shared() override {
 412     return;
 413   }
 414   void unlock() override {
 415     return;
 416   }
 417
 418   void init(CephContext* cct, int64_t total_blocks, int64_t zone_size_block, bool def);
 419   void init_common(CephContext* cct,
 420                    int64_t total_blocks,
 421                    int64_t zone_size_block,
 422                    bool def);
 423   int64_t alloc_blocks_dis_int_work(bool wrap, int64_t num_blocks, int64_t min_alloc, int64_t hint,
 424         int64_t blk_off, ExtentList *block_list);
 425
 426   int64_t alloc_blocks_int_work(bool wait, bool wrap,
 427                          int64_t num_blocks, int64_t hint, int64_t *start_block);
 428
 429 public:
 430   MEMPOOL_CLASS_HELPERS();
 431   BitMapAreaIN(CephContext* cct);
 432   BitMapAreaIN(CephContext* cct, int64_t zone_num, int64_t total_blocks);
 433   BitMapAreaIN(CephContext* cct, int64_t zone_num, int64_t total_blocks,
 434                bool def);
 435
 436   ~BitMapAreaIN() override;
 437   void shutdown() override;
 438   int64_t sub_used_blocks(int64_t num_blocks) override;
 439   int64_t add_used_blocks(int64_t num_blocks) override;
 440   bool reserve_blocks(int64_t num_blocks) override;
 441   void unreserve(int64_t num_blocks, int64_t allocated) override;
 442   int64_t get_reserved_blocks() override;
 443   int64_t get_used_blocks() override;
 444   virtual int64_t get_used_blocks_adj();
 445   int64_t size() override {
 446     return m_total_blocks;
 447   }
 448   using BitMapArea::alloc_blocks_dis; //non-wait version
 449
 450   virtual int64_t alloc_blocks_dis_int(int64_t num_blocks, int64_t min_alloc, int64_t hint,
 451                                        int64_t blk_off, ExtentList *block_list);
 452   int64_t alloc_blocks_dis(int64_t num_blocks, int64_t min_alloc, int64_t hint,
 453                            int64_t blk_off, ExtentList *block_list) override;
 454   virtual void set_blocks_used_int(int64_t start_block, int64_t num_blocks);
 455   void set_blocks_used(int64_t start_block, int64_t num_blocks) override;
 456
 457   virtual void free_blocks_int(int64_t start_block, int64_t num_blocks);
 458   void free_blocks(int64_t start_block, int64_t num_blocks) override;
 459   void dump_state(CephContext* cct, int& count) override;
 460 };
 461
 462 class BitMapAreaLeaf: public BitMapAreaIN{
 463
 464 private:
 465   void init(CephContext* cct, int64_t total_blocks, int64_t zone_size_block,
 466             bool def);
 467
 468 public:
 469   MEMPOOL_CLASS_HELPERS();
 470   static int64_t count;
 471   static void incr_count() { count++;}
 472   BitMapAreaLeaf(CephContext* cct) : BitMapAreaIN(cct) { }
 473   BitMapAreaLeaf(CephContext* cct, int64_t zone_num, int64_t total_blocks);
 474   BitMapAreaLeaf(CephContext* cct, int64_t zone_num, int64_t total_blocks,
 475                  bool def);
 476
 477   using BitMapAreaIN::child_check_n_lock;
 478   bool child_check_n_lock(BitMapArea *child, int64_t required) override {
 479     ceph_abort();
 480     return false;
 481   }
 482
 483   bool child_check_n_lock(BitMapZone* child, int64_t required, bool lock);
 484
 485   int64_t alloc_blocks_int(int64_t num_blocks, int64_t hint, int64_t *start_block);
 486   int64_t alloc_blocks_dis_int(int64_t num_blocks, int64_t min_alloc, int64_t hint,
 487         int64_t blk_off, ExtentList *block_list) override;
 488   void free_blocks_int(int64_t start_block, int64_t num_blocks) override;
 489
 490   ~BitMapAreaLeaf() override;
 491 };
 492
 493
 494 typedef enum bmap_alloc_mode {
 495   SERIAL = 1,
 496   CONCURRENT = 2,
 497 } bmap_alloc_mode_t;
 498
 499 class BitAllocator:public BitMapAreaIN{
 500 private:
 501   CephContext* const cct;
 502   bmap_alloc_mode_t m_alloc_mode;
 503   std::mutex m_serial_mutex;
 504   pthread_rwlock_t m_rw_lock;
 505   BitAllocatorStats *m_stats;
 506   bool m_is_stats_on;
 507   int64_t m_extra_blocks;
 508
 509   bool is_stats_on() {
 510     return m_is_stats_on;
 511   }
 512
 513   using BitMapArea::child_check_n_lock;
 514   bool child_check_n_lock(BitMapArea *child, int64_t required) override;
 515   void child_unlock(BitMapArea *child) override;
 516
 517   void serial_lock();
 518   bool try_serial_lock();
 519   void serial_unlock();
 520   void lock_excl() override;
 521   void lock_shared() override;
 522   bool try_lock();
 523   void unlock() override;
 524
 525   bool check_input(int64_t num_blocks);
 526   bool check_input_dis(int64_t num_blocks);
 527   void init_check(int64_t total_blocks, int64_t zone_size_block,
 528                  bmap_alloc_mode_t mode, bool def, bool stats_on);
 529   int64_t alloc_blocks_dis_work(int64_t num_blocks, int64_t min_alloc, int64_t hint, ExtentList *block_list, bool reserved);
 530
 531   int64_t alloc_blocks_dis_int(int64_t num_blocks, int64_t min_alloc,
 532            int64_t hint, int64_t area_blk_off, ExtentList *block_list) override;
 533
 534 public:
 535   MEMPOOL_CLASS_HELPERS();
 536
 537   BitAllocator(CephContext* cct, int64_t total_blocks,
 538                int64_t zone_size_block, bmap_alloc_mode_t mode);
 539   BitAllocator(CephContext* cct, int64_t total_blocks, int64_t zone_size_block,
 540                bmap_alloc_mode_t mode, bool def);
 541   BitAllocator(CephContext* cct, int64_t total_blocks, int64_t zone_size_block,
 542                bmap_alloc_mode_t mode, bool def, bool stats_on);
 543   ~BitAllocator() override;
 544   void shutdown() override;
 545   using BitMapAreaIN::alloc_blocks_dis; //Wait version
 546
 547   void free_blocks(int64_t start_block, int64_t num_blocks) override;
 548   void set_blocks_used(int64_t start_block, int64_t num_blocks) override;
 549   void unreserve_blocks(int64_t blocks);
 550
 551   int64_t alloc_blocks_dis_res(int64_t num_blocks, int64_t min_alloc, int64_t hint, ExtentList *block_list);
 552
 553   void free_blocks_dis(int64_t num_blocks, ExtentList *block_list);
 554   bool is_allocated_dis(ExtentList *blocks, int64_t num_blocks);
 555
 556   int64_t total_blocks() const {
 557     return m_total_blocks - m_extra_blocks;
 558   }
 559   int64_t get_used_blocks() override {
 560     return (BitMapAreaIN::get_used_blocks_adj() - m_extra_blocks);
 561   }
 562
 563   BitAllocatorStats *get_stats() {
 564       return m_stats;
 565   }
 566   void dump();
 567 };
 568
 569 #endif //End of file