ceph/src/crimson/common/fixed_kv_node_layout.h

   1 // -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*-
   2 // vim: ts=8 sw=2 smarttab
   3
   4 #pragma once
   5
   6 #include <algorithm>
   7 #include <iostream>
   8
   9 #include <boost/iterator/counting_iterator.hpp>
  10
  11 #include "include/byteorder.h"
  12
  13 #include "crimson/common/layout.h"
  14
  15 namespace crimson::common {
  16
  17 template <typename T, bool is_const>
  18 struct maybe_const_t {
  19 };
  20 template<typename T>
  21 struct maybe_const_t<T, true> {
  22   using type = const T*;
  23 };
  24 template<typename T>
  25 struct maybe_const_t<T, false> {
  26   using type = T*;
  27 };
  28
  29
  30 /**
  31  * FixedKVNodeLayout
  32  *
  33  * Reusable implementation of a fixed size block mapping
  34  * K -> V with internal representations KINT and VINT.
  35  *
  36  * Uses absl::container_internal::Layout for the actual memory layout.
  37  *
  38  * The primary interface exposed is centered on the iterator
  39  * and related methods.
  40  *
  41  * Also included are helpers for doing splits and merges as for a btree.
  42  */
  43 template <
  44   size_t CAPACITY,
  45   typename Meta,
  46   typename MetaInt,
  47   typename K,
  48   typename KINT,
  49   typename V,
  50   typename VINT,
  51   bool VALIDATE_INVARIANTS=true>
  52 class FixedKVNodeLayout {
  53   char *buf = nullptr;
  54
  55   using L = absl::container_internal::Layout<ceph_le32, MetaInt, KINT, VINT>;
  56   static constexpr L layout{1, 1, CAPACITY, CAPACITY};
  57
  58 public:
  59   template <bool is_const>
  60   struct iter_t {
  61     friend class FixedKVNodeLayout;
  62     using parent_t = typename maybe_const_t<FixedKVNodeLayout, is_const>::type;
  63
  64     parent_t node;
  65     uint16_t offset = 0;
  66
  67     iter_t() = default;
  68     iter_t(
  69       parent_t parent,
  70       uint16_t offset) : node(parent), offset(offset) {}
  71
  72     iter_t(const iter_t &) noexcept = default;
  73     iter_t(iter_t &&) noexcept = default;
  74     template<bool is_const_ = is_const>
  75     iter_t(const iter_t<false>& it, std::enable_if_t<is_const_, int> = 0)
  76       : iter_t{it.node, it.offset}
  77     {}
  78     iter_t &operator=(const iter_t &) = default;
  79     iter_t &operator=(iter_t &&) = default;
  80
  81     // Work nicely with for loops without requiring a nested type.
  82     using reference = iter_t&;
  83     iter_t &operator*() { return *this; }
  84     iter_t *operator->() { return this; }
  85
  86     iter_t operator++(int) {
  87       auto ret = *this;
  88       ++offset;
  89       return ret;
  90     }
  91
  92     iter_t &operator++() {
  93       ++offset;
  94       return *this;
  95     }
  96
  97     iter_t operator--(int) {
  98       assert(offset > 0);
  99       auto ret = *this;
 100       --offset;
 101       return ret;
 102     }
 103
 104     iter_t &operator--() {
 105       assert(offset > 0);
 106       --offset;
 107       return *this;
 108     }
 109
 110     uint16_t operator-(const iter_t &rhs) const {
 111       assert(rhs.node == node);
 112       return offset - rhs.offset;
 113     }
 114
 115     iter_t operator+(uint16_t off) const {
 116       return iter_t(
 117         node,
 118         offset + off);
 119     }
 120     iter_t operator-(uint16_t off) const {
 121       return iter_t(
 122         node,
 123         offset - off);
 124     }
 125
 126     friend bool operator==(const iter_t &lhs, const iter_t &rhs) {
 127       assert(lhs.node == rhs.node);
 128       return lhs.offset == rhs.offset;
 129     }
 130
 131     friend bool operator!=(const iter_t &lhs, const iter_t &rhs) {
 132       return !(lhs == rhs);
 133     }
 134
 135     friend bool operator==(const iter_t<is_const> &lhs, const iter_t<!is_const> &rhs) {
 136       assert(lhs.node == rhs.node);
 137       return lhs.offset == rhs.offset;
 138     }
 139     friend bool operator!=(const iter_t<is_const> &lhs, const iter_t<!is_const> &rhs) {
 140       return !(lhs == rhs);
 141     }
 142     K get_key() const {
 143       return K(node->get_key_ptr()[offset]);
 144     }
 145
 146     K get_next_key_or_max() const {
 147       auto next = *this + 1;
 148       if (next == node->end())
 149         return std::numeric_limits<K>::max();
 150       else
 151         return next->get_key();
 152     }
 153
 154     void set_val(V val) const {
 155       static_assert(!is_const);
 156       node->get_val_ptr()[offset] = VINT(val);
 157     }
 158
 159     V get_val() const {
 160       return V(node->get_val_ptr()[offset]);
 161     };
 162
 163     bool contains(K addr) const {
 164       return (get_key() <= addr) && (get_next_key_or_max() > addr);
 165     }
 166
 167     uint16_t get_offset() const {
 168       return offset;
 169     }
 170
 171   private:
 172     void set_key(K _lb) const {
 173       static_assert(!is_const);
 174       KINT lb;
 175       lb = _lb;
 176       node->get_key_ptr()[offset] = lb;
 177     }
 178
 179     typename maybe_const_t<char, is_const>::type get_key_ptr() const {
 180       return reinterpret_cast<
 181         typename maybe_const_t<char, is_const>::type>(
 182           node->get_key_ptr() + offset);
 183     }
 184
 185     typename maybe_const_t<char, is_const>::type get_val_ptr() const {
 186       return reinterpret_cast<
 187         typename maybe_const_t<char, is_const>::type>(
 188           node->get_val_ptr() + offset);
 189     }
 190   };
 191   using const_iterator = iter_t<true>;
 192   using iterator = iter_t<false>;
 193
 194   struct delta_t {
 195     enum class op_t : uint8_t {
 196       INSERT,
 197       REMOVE,
 198       UPDATE,
 199     } op;
 200     KINT key;
 201     VINT val;
 202
 203     void replay(FixedKVNodeLayout &l) {
 204       switch (op) {
 205       case op_t::INSERT: {
 206         l.insert(l.lower_bound(key), key, val);
 207         break;
 208       }
 209       case op_t::REMOVE: {
 210         auto iter = l.find(key);
 211         assert(iter != l.end());
 212         l.remove(iter);
 213         break;
 214       }
 215       case op_t::UPDATE: {
 216         auto iter = l.find(key);
 217         assert(iter != l.end());
 218         l.update(iter, val);
 219         break;
 220       }
 221       default:
 222         assert(0 == "Impossible");
 223       }
 224     }
 225
 226     bool operator==(const delta_t &rhs) const {
 227       return op == rhs.op &&
 228         key == rhs.key &&
 229         val == rhs.val;
 230     }
 231   };
 232
 233 public:
 234   class delta_buffer_t {
 235     std::vector<delta_t> buffer;
 236   public:
 237     bool empty() const {
 238       return buffer.empty();
 239     }
 240     void insert(
 241       const K &key,
 242       const V &val) {
 243       KINT k;
 244       k = key;
 245       buffer.push_back(
 246         delta_t{
 247           delta_t::op_t::INSERT,
 248           k,
 249           VINT(val)
 250         });
 251     }
 252     void update(
 253       const K &key,
 254       const V &val) {
 255       KINT k;
 256       k = key;
 257       buffer.push_back(
 258         delta_t{
 259           delta_t::op_t::UPDATE,
 260           k,
 261           VINT(val)
 262         });
 263     }
 264     void remove(const K &key) {
 265       KINT k;
 266       k = key;
 267       buffer.push_back(
 268         delta_t{
 269           delta_t::op_t::REMOVE,
 270           k,
 271           VINT()
 272         });
 273     }
 274     void replay(FixedKVNodeLayout &node) {
 275       for (auto &i: buffer) {
 276         i.replay(node);
 277       }
 278     }
 279     size_t get_bytes() const {
 280       return buffer.size() * sizeof(delta_t);
 281     }
 282     void copy_out(char *out, size_t len) {
 283       assert(len == get_bytes());
 284       ::memcpy(out, reinterpret_cast<const void *>(buffer.data()), get_bytes());
 285       buffer.clear();
 286     }
 287     void copy_in(const char *out, size_t len) {
 288       assert(empty());
 289       assert(len % sizeof(delta_t) == 0);
 290       buffer = std::vector(
 291         reinterpret_cast<const delta_t*>(out),
 292         reinterpret_cast<const delta_t*>(out + len));
 293     }
 294     bool operator==(const delta_buffer_t &rhs) const {
 295       return buffer == rhs.buffer;
 296     }
 297   };
 298
 299   void journal_insert(
 300     const_iterator _iter,
 301     const K &key,
 302     const V &val,
 303     delta_buffer_t *recorder) {
 304     auto iter = iterator(this, _iter.offset);
 305     if (recorder) {
 306       recorder->insert(
 307         key,
 308         val);
 309     }
 310     insert(iter, key, val);
 311   }
 312
 313   void journal_update(
 314     const_iterator _iter,
 315     const V &val,
 316     delta_buffer_t *recorder) {
 317     auto iter = iterator(this, _iter.offset);
 318     if (recorder) {
 319       recorder->update(iter->get_key(), val);
 320     }
 321     update(iter, val);
 322   }
 323
 324   void journal_replace(
 325     const_iterator _iter,
 326     const K &key,
 327     const V &val,
 328     delta_buffer_t *recorder) {
 329     auto iter = iterator(this, _iter.offset);
 330     if (recorder) {
 331       recorder->remove(iter->get_key());
 332       recorder->insert(key, val);
 333     }
 334     replace(iter, key, val);
 335   }
 336
 337
 338   void journal_remove(
 339     const_iterator _iter,
 340     delta_buffer_t *recorder) {
 341     auto iter = iterator(this, _iter.offset);
 342     if (recorder) {
 343       recorder->remove(iter->get_key());
 344     }
 345     remove(iter);
 346   }
 347
 348
 349   FixedKVNodeLayout(char *buf) :
 350     buf(buf) {}
 351
 352   virtual ~FixedKVNodeLayout() = default;
 353
 354   const_iterator begin() const {
 355     return const_iterator(
 356       this,
 357       0);
 358   }
 359
 360   const_iterator end() const {
 361     return const_iterator(
 362       this,
 363       get_size());
 364   }
 365
 366   iterator begin() {
 367     return iterator(
 368       this,
 369       0);
 370   }
 371
 372   iterator end() {
 373     return iterator(
 374       this,
 375       get_size());
 376   }
 377
 378   const_iterator iter_idx(uint16_t off) const {
 379     return const_iterator(
 380       this,
 381       off);
 382   }
 383
 384   const_iterator find(K l) const {
 385     auto ret = begin();
 386     for (; ret != end(); ++ret) {
 387       if (ret->get_key() == l)
 388         break;
 389     }
 390     return ret;
 391   }
 392   iterator find(K l) {
 393     const auto &tref = *this;
 394     return iterator(this, tref.find(l).offset);
 395   }
 396
 397   const_iterator lower_bound(K l) const {
 398     auto it = std::lower_bound(boost::make_counting_iterator<uint16_t>(0),
 399                                boost::make_counting_iterator<uint16_t>(get_size()),
 400                                l,
 401                                [this](uint16_t i, K key) {
 402                                  const_iterator iter(this, i);
 403                                  return iter->get_key() < key;
 404                                });
 405     return const_iterator(this, *it);
 406   }
 407
 408   iterator lower_bound(K l) {
 409     const auto &tref = *this;
 410     return iterator(this, tref.lower_bound(l).offset);
 411   }
 412
 413   const_iterator upper_bound(K l) const {
 414     auto it = std::upper_bound(boost::make_counting_iterator<uint16_t>(0),
 415                                boost::make_counting_iterator<uint16_t>(get_size()),
 416                                l,
 417                                [this](K key, uint16_t i) {
 418                                  const_iterator iter(this, i);
 419                                  return key < iter->get_key();
 420                                });
 421     return const_iterator(this, *it);
 422   }
 423
 424   iterator upper_bound(K l) {
 425     const auto &tref = *this;
 426     return iterator(this, tref.upper_bound(l).offset);
 427   }
 428
 429   const_iterator get_split_pivot() const {
 430     return iter_idx(get_size() / 2);
 431   }
 432
 433   uint16_t get_size() const {
 434     return *layout.template Pointer<0>(buf);
 435   }
 436
 437   /**
 438    * set_size
 439    *
 440    * Set size representation to match size
 441    */
 442   void set_size(uint16_t size) {
 443     *layout.template Pointer<0>(buf) = size;
 444   }
 445
 446   /**
 447    * get_meta/set_meta
 448    *
 449    * Enables stashing a templated type within the layout.
 450    * Cannot be modified after initial write as it is not represented
 451    * in delta_t
 452    */
 453   Meta get_meta() const {
 454     MetaInt &metaint = *layout.template Pointer<1>(buf);
 455     return Meta(metaint);
 456   }
 457   void set_meta(const Meta &meta) {
 458     *layout.template Pointer<1>(buf) = MetaInt(meta);
 459   }
 460
 461   constexpr static size_t get_capacity() {
 462     return CAPACITY;
 463   }
 464
 465   bool operator==(const FixedKVNodeLayout &rhs) const {
 466     if (get_size() != rhs.get_size()) {
 467       return false;
 468     }
 469
 470     auto iter = begin();
 471     auto iter2 = rhs.begin();
 472     while (iter != end()) {
 473       if (iter->get_key() != iter2->get_key() ||
 474           iter->get_val() != iter2->get_val()) {
 475         return false;
 476       }
 477       iter++;
 478       iter2++;
 479     }
 480     return true;
 481   }
 482
 483   /**
 484    * split_into
 485    *
 486    * Takes *this and splits its contents into left and right.
 487    */
 488   K split_into(
 489     FixedKVNodeLayout &left,
 490     FixedKVNodeLayout &right) const {
 491     auto piviter = get_split_pivot();
 492
 493     left.copy_from_foreign(left.begin(), begin(), piviter);
 494     left.set_size(piviter - begin());
 495
 496     right.copy_from_foreign(right.begin(), piviter, end());
 497     right.set_size(end() - piviter);
 498
 499     auto [lmeta, rmeta] = get_meta().split_into(piviter->get_key());
 500     left.set_meta(lmeta);
 501     right.set_meta(rmeta);
 502
 503     return piviter->get_key();
 504   }
 505
 506   /**
 507    * merge_from
 508    *
 509    * Takes two nodes and copies their contents into *this.
 510    *
 511    * precondition: left.size() + right.size() < CAPACITY
 512    */
 513   void merge_from(
 514     const FixedKVNodeLayout &left,
 515     const FixedKVNodeLayout &right)
 516   {
 517     copy_from_foreign(
 518       end(),
 519       left.begin(),
 520       left.end());
 521     set_size(left.get_size());
 522     copy_from_foreign(
 523       end(),
 524       right.begin(),
 525       right.end());
 526     set_size(left.get_size() + right.get_size());
 527     set_meta(Meta::merge_from(left.get_meta(), right.get_meta()));
 528   }
 529
 530   /**
 531    * balance_into_new_nodes
 532    *
 533    * Takes the contents of left and right and copies them into
 534    * replacement_left and replacement_right such that in the
 535    * event that the number of elements is odd the extra goes to
 536    * the left side iff prefer_left.
 537    */
 538   static K balance_into_new_nodes(
 539     const FixedKVNodeLayout &left,
 540     const FixedKVNodeLayout &right,
 541     bool prefer_left,
 542     FixedKVNodeLayout &replacement_left,
 543     FixedKVNodeLayout &replacement_right)
 544   {
 545     auto total = left.get_size() + right.get_size();
 546     auto pivot_idx = (left.get_size() + right.get_size()) / 2;
 547     if (total % 2 && prefer_left) {
 548       pivot_idx++;
 549     }
 550     auto replacement_pivot = pivot_idx >= left.get_size() ?
 551       right.iter_idx(pivot_idx - left.get_size())->get_key() :
 552       left.iter_idx(pivot_idx)->get_key();
 553
 554     if (pivot_idx < left.get_size()) {
 555       replacement_left.copy_from_foreign(
 556         replacement_left.end(),
 557         left.begin(),
 558         left.iter_idx(pivot_idx));
 559       replacement_left.set_size(pivot_idx);
 560
 561       replacement_right.copy_from_foreign(
 562         replacement_right.end(),
 563         left.iter_idx(pivot_idx),
 564         left.end());
 565
 566       replacement_right.set_size(left.get_size() - pivot_idx);
 567       replacement_right.copy_from_foreign(
 568         replacement_right.end(),
 569         right.begin(),
 570         right.end());
 571       replacement_right.set_size(total - pivot_idx);
 572     } else {
 573       replacement_left.copy_from_foreign(
 574         replacement_left.end(),
 575         left.begin(),
 576         left.end());
 577       replacement_left.set_size(left.get_size());
 578
 579       replacement_left.copy_from_foreign(
 580         replacement_left.end(),
 581         right.begin(),
 582         right.iter_idx(pivot_idx - left.get_size()));
 583       replacement_left.set_size(pivot_idx);
 584
 585       replacement_right.copy_from_foreign(
 586         replacement_right.end(),
 587         right.iter_idx(pivot_idx - left.get_size()),
 588         right.end());
 589       replacement_right.set_size(total - pivot_idx);
 590     }
 591
 592     auto [lmeta, rmeta] = Meta::rebalance(
 593       left.get_meta(), right.get_meta(), replacement_pivot);
 594     replacement_left.set_meta(lmeta);
 595     replacement_right.set_meta(rmeta);
 596     return replacement_pivot;
 597   }
 598
 599 private:
 600   void insert(
 601     iterator iter,
 602     const K &key,
 603     const V &val) {
 604     if (VALIDATE_INVARIANTS) {
 605       if (iter != begin()) {
 606         assert((iter - 1)->get_key() < key);
 607       }
 608       if (iter != end()) {
 609         assert(iter->get_key() > key);
 610       }
 611       assert(get_size() < CAPACITY);
 612     }
 613     copy_from_local(iter + 1, iter, end());
 614     iter->set_key(key);
 615     iter->set_val(val);
 616     set_size(get_size() + 1);
 617   }
 618
 619   void update(
 620     iterator iter,
 621     V val) {
 622     assert(iter != end());
 623     iter->set_val(val);
 624   }
 625
 626   void replace(
 627     iterator iter,
 628     const K &key,
 629     const V &val) {
 630     assert(iter != end());
 631     if (VALIDATE_INVARIANTS) {
 632       if (iter != begin()) {
 633         assert((iter - 1)->get_key() < key);
 634       }
 635       if ((iter + 1) != end()) {
 636         assert((iter + 1)->get_key() > key);
 637       }
 638     }
 639     iter->set_key(key);
 640     iter->set_val(val);
 641   }
 642
 643   void remove(iterator iter) {
 644     assert(iter != end());
 645     copy_from_local(iter, iter + 1, end());
 646     set_size(get_size() - 1);
 647   }
 648
 649   /**
 650    * get_key_ptr
 651    *
 652    * Get pointer to start of key array
 653    */
 654   KINT *get_key_ptr() {
 655     return layout.template Pointer<2>(buf);
 656   }
 657   const KINT *get_key_ptr() const {
 658     return layout.template Pointer<2>(buf);
 659   }
 660
 661   /**
 662    * get_val_ptr
 663    *
 664    * Get pointer to start of val array
 665    */
 666   VINT *get_val_ptr() {
 667     return layout.template Pointer<3>(buf);
 668   }
 669   const VINT *get_val_ptr() const {
 670     return layout.template Pointer<3>(buf);
 671   }
 672
 673   /**
 674    * node_resolve/unresolve_vals
 675    *
 676    * If the representation for values depends in some way on the
 677    * node in which they are located, users may implement
 678    * resolve/unresolve to enable copy_from_foreign to handle that
 679    * transition.
 680    */
 681   virtual void node_resolve_vals(iterator from, iterator to) const {}
 682   virtual void node_unresolve_vals(iterator from, iterator to) const {}
 683
 684   /**
 685    * copy_from_foreign
 686    *
 687    * Copies entries from [from_src, to_src) to tgt.
 688    *
 689    * tgt and from_src must be from different nodes.
 690    * from_src and to_src must be from the same node.
 691    */
 692   static void copy_from_foreign(
 693     iterator tgt,
 694     const_iterator from_src,
 695     const_iterator to_src) {
 696     assert(tgt->node != from_src->node);
 697     assert(to_src->node == from_src->node);
 698     memcpy(
 699       tgt->get_val_ptr(), from_src->get_val_ptr(),
 700       to_src->get_val_ptr() - from_src->get_val_ptr());
 701     memcpy(
 702       tgt->get_key_ptr(), from_src->get_key_ptr(),
 703       to_src->get_key_ptr() - from_src->get_key_ptr());
 704     from_src->node->node_resolve_vals(tgt, tgt + (to_src - from_src));
 705     tgt->node->node_unresolve_vals(tgt, tgt + (to_src - from_src));
 706   }
 707
 708   /**
 709    * copy_from_local
 710    *
 711    * Copies entries from [from_src, to_src) to tgt.
 712    *
 713    * tgt, from_src, and to_src must be from the same node.
 714    */
 715   static void copy_from_local(
 716     iterator tgt,
 717     iterator from_src,
 718     iterator to_src) {
 719     assert(tgt->node == from_src->node);
 720     assert(to_src->node == from_src->node);
 721     memmove(
 722       tgt->get_val_ptr(), from_src->get_val_ptr(),
 723       to_src->get_val_ptr() - from_src->get_val_ptr());
 724     memmove(
 725       tgt->get_key_ptr(), from_src->get_key_ptr(),
 726       to_src->get_key_ptr() - from_src->get_key_ptr());
 727   }
 728 };
 729
 730 }