ceph/src/rocksdb/utilities/transactions/lock/range/range_tree/lib/locktree/treenode.h

   1 /* -*- mode: C++; c-basic-offset: 4; indent-tabs-mode: nil -*- */
   2 // vim: ft=cpp:expandtab:ts=8:sw=2:softtabstop=2:
   3 #ident "$Id$"
   4 /*======
   5 This file is part of PerconaFT.
   6
   7
   8 Copyright (c) 2006, 2015, Percona and/or its affiliates. All rights reserved.
   9
  10     PerconaFT is free software: you can redistribute it and/or modify
  11     it under the terms of the GNU General Public License, version 2,
  12     as published by the Free Software Foundation.
  13
  14     PerconaFT is distributed in the hope that it will be useful,
  15     but WITHOUT ANY WARRANTY; without even the implied warranty of
  16     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  17     GNU General Public License for more details.
  18
  19     You should have received a copy of the GNU General Public License
  20     along with PerconaFT.  If not, see <http://www.gnu.org/licenses/>.
  21
  22 ----------------------------------------
  23
  24     PerconaFT is free software: you can redistribute it and/or modify
  25     it under the terms of the GNU Affero General Public License, version 3,
  26     as published by the Free Software Foundation.
  27
  28     PerconaFT is distributed in the hope that it will be useful,
  29     but WITHOUT ANY WARRANTY; without even the implied warranty of
  30     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  31     GNU Affero General Public License for more details.
  32
  33     You should have received a copy of the GNU Affero General Public License
  34     along with PerconaFT.  If not, see <http://www.gnu.org/licenses/>.
  35
  36 ----------------------------------------
  37
  38    Licensed under the Apache License, Version 2.0 (the "License");
  39    you may not use this file except in compliance with the License.
  40    You may obtain a copy of the License at
  41
  42        http://www.apache.org/licenses/LICENSE-2.0
  43
  44    Unless required by applicable law or agreed to in writing, software
  45    distributed under the License is distributed on an "AS IS" BASIS,
  46    WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  47    See the License for the specific language governing permissions and
  48    limitations under the License.
  49 ======= */
  50
  51 #ident \
  52     "Copyright (c) 2006, 2015, Percona and/or its affiliates. All rights reserved."
  53
  54 #pragma once
  55
  56 #include <string.h>
  57
  58 #include "../ft/comparator.h"
  59 #include "../portability/memory.h"
  60 #include "../portability/toku_pthread.h"
  61 // PORT: we need LTM_STATUS
  62 #include "../ft/ft-status.h"
  63 #include "../portability/txn_subst.h"
  64 #include "keyrange.h"
  65
  66 namespace toku {
  67
  68 // a node in a tree with its own mutex
  69 // - range is the "key" of this node
  70 // - txnid is the single txnid associated with this node
  71 // - left and right children may be null
  72 //
  73 // to build a tree on top of this abstraction, the user:
  74 // - provides memory for a root node, initializes it via create_root()
  75 // - performs tree operations on the root node. memory management
  76 //   below the root node is handled by the abstraction, not the user.
  77 // this pattern:
  78 // - guaruntees a root node always exists.
  79 // - does not allow for rebalances on the root node
  80
  81 class treenode {
  82  public:
  83   // every treenode function has some common requirements:
  84   // - node is locked and children are never locked
  85   // - node may be unlocked if no other thread has visibility
  86
  87   // effect: create the root node
  88   void create_root(const comparator *cmp);
  89
  90   // effect: destroys the root node
  91   void destroy_root(void);
  92
  93   // effect: sets the txnid and copies the given range for this node
  94   void set_range_and_txnid(const keyrange &range, TXNID txnid, bool is_shared);
  95
  96   // returns: true iff this node is marked as empty
  97   bool is_empty(void);
  98
  99   // returns: true if this is the root node, denoted by a null parent
 100   bool is_root(void);
 101
 102   // returns: true if the given range overlaps with this node's range
 103   bool range_overlaps(const keyrange &range);
 104
 105   // effect: locks the node
 106   void mutex_lock(void);
 107
 108   // effect: unlocks the node
 109   void mutex_unlock(void);
 110
 111   // return: node whose child overlaps, or a child that is empty
 112   //         and would contain range if it existed
 113   // given: if cmp_hint is non-null, then it is a precomputed
 114   //        comparison of this node's range to the given range.
 115   treenode *find_node_with_overlapping_child(
 116       const keyrange &range, const keyrange::comparison *cmp_hint);
 117
 118   // effect: performs an in-order traversal of the ranges that overlap the
 119   //         given range, calling function->fn() on each node that does
 120   // requires: function signature is: bool fn(const keyrange &range, TXNID
 121   // txnid) requires: fn returns true to keep iterating, false to stop iterating
 122   // requires: fn does not attempt to use any ranges read out by value
 123   //           after removing a node with an overlapping range from the tree.
 124   template <class F>
 125   void traverse_overlaps(const keyrange &range, F *function) {
 126     keyrange::comparison c = range.compare(*m_cmp, m_range);
 127     if (c == keyrange::comparison::EQUALS) {
 128       // Doesn't matter if fn wants to keep going, there
 129       // is nothing left, so return.
 130       function->fn(m_range, m_txnid, m_is_shared, m_owners);
 131       return;
 132     }
 133
 134     treenode *left = m_left_child.get_locked();
 135     if (left) {
 136       if (c != keyrange::comparison::GREATER_THAN) {
 137         // Target range is less than this node, or it overlaps this
 138         // node.  There may be something on the left.
 139         left->traverse_overlaps(range, function);
 140       }
 141       left->mutex_unlock();
 142     }
 143
 144     if (c == keyrange::comparison::OVERLAPS) {
 145       bool keep_going = function->fn(m_range, m_txnid, m_is_shared, m_owners);
 146       if (!keep_going) {
 147         return;
 148       }
 149     }
 150
 151     treenode *right = m_right_child.get_locked();
 152     if (right) {
 153       if (c != keyrange::comparison::LESS_THAN) {
 154         // Target range is greater than this node, or it overlaps this
 155         // node.  There may be something on the right.
 156         right->traverse_overlaps(range, function);
 157       }
 158       right->mutex_unlock();
 159     }
 160   }
 161
 162   // effect: inserts the given range and txnid into a subtree, recursively
 163   // requires: range does not overlap with any node below the subtree
 164   bool insert(const keyrange &range, TXNID txnid, bool is_shared);
 165
 166   // effect: removes the given range from the subtree
 167   // requires: range exists in the subtree
 168   // returns: the root of the resulting subtree
 169   treenode *remove(const keyrange &range, TXNID txnid);
 170
 171   // effect: removes this node and all of its children, recursively
 172   // requires: every node at and below this node is unlocked
 173   void recursive_remove(void);
 174
 175  private:
 176   // the child_ptr is a light abstraction for the locking of
 177   // a child and the maintenence of its depth estimate.
 178
 179   struct child_ptr {
 180     // set the child pointer
 181     void set(treenode *node);
 182
 183     // get and lock this child if it exists
 184     treenode *get_locked(void);
 185
 186     treenode *ptr;
 187     uint32_t depth_est;
 188   };
 189
 190   // the balance factor at which a node is considered imbalanced
 191   static const int32_t IMBALANCE_THRESHOLD = 2;
 192
 193   // node-level mutex
 194   toku_mutex_t m_mutex;
 195
 196   // the range and txnid for this node. the range contains a copy
 197   // of the keys originally inserted into the tree. nodes may
 198   // swap ranges. but at the end of the day, when a node is
 199   // destroyed, it frees the memory associated with whatever range
 200   // it has at the time of destruction.
 201   keyrange m_range;
 202
 203   void remove_shared_owner(TXNID txnid);
 204
 205   bool has_multiple_owners() { return (m_txnid == TXNID_SHARED); }
 206
 207  private:
 208   // Owner transaction id.
 209   // A value of TXNID_SHARED means this node has multiple owners
 210   TXNID m_txnid;
 211
 212   // If true, this lock is a non-exclusive lock, and it can have either
 213   // one or several owners.
 214   bool m_is_shared;
 215
 216   // List of the owners, or nullptr if there's just one owner.
 217   TxnidVector *m_owners;
 218
 219   // two child pointers
 220   child_ptr m_left_child;
 221   child_ptr m_right_child;
 222
 223   // comparator for ranges
 224   // psergey-todo: Is there any sense to store the comparator in each tree
 225   // node?
 226   const comparator *m_cmp;
 227
 228   // marked for the root node. the root node is never free()'d
 229   // when removed, but instead marked as empty.
 230   bool m_is_root;
 231
 232   // marked for an empty node. only valid for the root.
 233   bool m_is_empty;
 234
 235   // effect: initializes an empty node with the given comparator
 236   void init(const comparator *cmp);
 237
 238   // requires: this is a shared node (m_is_shared==true)
 239   // effect: another transaction is added as an owner.
 240   // returns: true <=> added another owner
 241   //          false <=> this transaction is already an owner
 242   bool add_shared_owner(TXNID txnid);
 243
 244   // requires: *parent is initialized to something meaningful.
 245   // requires: subtree is non-empty
 246   // returns: the leftmost child of the given subtree
 247   // returns: a pointer to the parent of said child in *parent, only
 248   //          if this function recurred, otherwise it is untouched.
 249   treenode *find_leftmost_child(treenode **parent);
 250
 251   // requires: *parent is initialized to something meaningful.
 252   // requires: subtree is non-empty
 253   // returns: the rightmost child of the given subtree
 254   // returns: a pointer to the parent of said child in *parent, only
 255   //          if this function recurred, otherwise it is untouched.
 256   treenode *find_rightmost_child(treenode **parent);
 257
 258   // effect: remove the root of this subtree, destroying the old root
 259   // returns: the new root of the subtree
 260   treenode *remove_root_of_subtree(void);
 261
 262   // requires: subtree is non-empty, direction is not 0
 263   // returns: the child of the subtree at either the left or rightmost extreme
 264   treenode *find_child_at_extreme(int direction, treenode **parent);
 265
 266   // effect: retrieves and possibly rebalances the left child
 267   // returns: a locked left child, if it exists
 268   treenode *lock_and_rebalance_left(void);
 269
 270   // effect: retrieves and possibly rebalances the right child
 271   // returns: a locked right child, if it exists
 272   treenode *lock_and_rebalance_right(void);
 273
 274   // returns: the estimated depth of this subtree
 275   uint32_t get_depth_estimate(void) const;
 276
 277   // returns: true iff left subtree depth is sufficiently less than the right
 278   bool left_imbalanced(int threshold) const;
 279
 280   // returns: true iff right subtree depth is sufficiently greater than the left
 281   bool right_imbalanced(int threshold) const;
 282
 283   // effect: performs an O(1) rebalance, which will "heal" an imbalance by at
 284   // most 1. effect: if the new root is not this node, then this node is
 285   // unlocked. returns: locked node representing the new root of the rebalanced
 286   // subtree
 287   treenode *maybe_rebalance(void);
 288
 289   // returns: allocated treenode populated with a copy of the range and txnid
 290   static treenode *alloc(const comparator *cmp, const keyrange &range,
 291                          TXNID txnid, bool is_shared);
 292
 293   // requires: node is a locked root node, or an unlocked non-root node
 294   static void free(treenode *node);
 295
 296   // effect: swaps the range/txnid pairs for node1 and node2.
 297   static void swap_in_place(treenode *node1, treenode *node2);
 298
 299   friend class concurrent_tree_unit_test;
 300 };
 301
 302 } /* namespace toku */