ceph/src/rocksdb/utilities/transactions/lock/range/range_tree/lib/locktree/lock_request.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 "../db.h"
  57 #include "../ft/comparator.h"
  58 #include "../portability/toku_pthread.h"
  59 #include "locktree.h"
  60 #include "txnid_set.h"
  61 #include "wfg.h"
  62
  63 namespace toku {
  64
  65 // Information about a lock wait
  66 struct lock_wait_info {
  67   locktree *ltree;  // the tree where wait happens
  68   TXNID waiter;     // the waiting transaction
  69   void *m_extra;    // lock_request's m_extra
  70
  71   // The transactions that are waited for.
  72   std::vector<TXNID> waitees;
  73 };
  74
  75 typedef std::vector<lock_wait_info> lock_wait_infos;
  76
  77 // A lock request contains the db, the key range, the lock type, and
  78 // the transaction id that describes a potential row range lock.
  79 //
  80 // the typical use case is:
  81 // - initialize a lock request
  82 // - start to try to acquire the lock
  83 // - do something else
  84 // - wait for the lock request to be resolved on a timed condition
  85 // - destroy the lock request
  86 // a lock request is resolved when its state is no longer pending, or
  87 // when it becomes granted, or timedout, or deadlocked. when resolved, the
  88 // state of the lock request is changed and any waiting threads are awakened.
  89
  90 class lock_request {
  91  public:
  92   enum type { UNKNOWN, READ, WRITE };
  93
  94   // effect: Initializes a lock request.
  95   void create(toku_external_mutex_factory_t mutex_factory);
  96
  97   // effect: Destroys a lock request.
  98   void destroy(void);
  99
 100   // effect: Resets the lock request parameters, allowing it to be reused.
 101   // requires: Lock request was already created at some point
 102   void set(locktree *lt, TXNID txnid, const DBT *left_key, const DBT *right_key,
 103            type lock_type, bool big_txn, void *extra = nullptr);
 104
 105   // effect: Tries to acquire a lock described by this lock request.
 106   // returns: The return code of locktree::acquire_[write,read]_lock()
 107   //          or DB_LOCK_DEADLOCK if this request would end up deadlocked.
 108   int start(void);
 109
 110   // effect: Sleeps until either the request is granted or the wait time
 111   // expires. returns: The return code of locktree::acquire_[write,read]_lock()
 112   //          or simply DB_LOCK_NOTGRANTED if the wait time expired.
 113   int wait(uint64_t wait_time_ms);
 114   int wait(uint64_t wait_time_ms, uint64_t killed_time_ms,
 115            int (*killed_callback)(void),
 116            void (*lock_wait_callback)(void *, lock_wait_infos *) = nullptr,
 117            void *callback_arg = nullptr);
 118
 119   // return: left end-point of the lock range
 120   const DBT *get_left_key(void) const;
 121
 122   // return: right end-point of the lock range
 123   const DBT *get_right_key(void) const;
 124
 125   // return: the txnid waiting for a lock
 126   TXNID get_txnid(void) const;
 127
 128   // return: when this lock request started, as milliseconds from epoch
 129   uint64_t get_start_time(void) const;
 130
 131   // return: which txnid is blocking this request (there may be more, though)
 132   TXNID get_conflicting_txnid(void) const;
 133
 134   // effect: Retries all of the lock requests for the given locktree.
 135   //         Any lock requests successfully restarted is completed and woken
 136   //         up.
 137   //         The rest remain pending.
 138   static void retry_all_lock_requests(
 139       locktree *lt,
 140       void (*lock_wait_callback)(void *, lock_wait_infos *) = nullptr,
 141       void *callback_arg = nullptr,
 142       void (*after_retry_test_callback)(void) = nullptr);
 143   static void retry_all_lock_requests_info(
 144       lt_lock_request_info *info,
 145       void (*lock_wait_callback)(void *, lock_wait_infos *),
 146       void *callback_arg);
 147
 148   void set_start_test_callback(void (*f)(void));
 149   void set_start_before_pending_test_callback(void (*f)(void));
 150   void set_retry_test_callback(void (*f)(void));
 151
 152   void *get_extra(void) const;
 153
 154   void kill_waiter(void);
 155   static void kill_waiter(locktree *lt, void *extra);
 156
 157  private:
 158   enum state {
 159     UNINITIALIZED,
 160     INITIALIZED,
 161     PENDING,
 162     COMPLETE,
 163     DESTROYED,
 164   };
 165
 166   // The keys for a lock request are stored "unowned" in m_left_key
 167   // and m_right_key. When the request is about to go to sleep, it
 168   // copies these keys and stores them in m_left_key_copy etc and
 169   // sets the temporary pointers to null.
 170   TXNID m_txnid;
 171   TXNID m_conflicting_txnid;
 172   uint64_t m_start_time;
 173   const DBT *m_left_key;
 174   const DBT *m_right_key;
 175   DBT m_left_key_copy;
 176   DBT m_right_key_copy;
 177
 178   // The lock request type and associated locktree
 179   type m_type;
 180   locktree *m_lt;
 181
 182   // If the lock request is in the completed state, then its
 183   // final return value is stored in m_complete_r
 184   int m_complete_r;
 185   state m_state;
 186
 187   toku_external_cond_t m_wait_cond;
 188
 189   bool m_big_txn;
 190
 191   // the lock request info state stored in the
 192   // locktree that this lock request is for.
 193   struct lt_lock_request_info *m_info;
 194
 195   void *m_extra;
 196
 197   // effect: tries again to acquire the lock described by this lock request
 198   // returns: 0 if retrying the request succeeded and is now complete
 199   int retry(lock_wait_infos *collector);
 200
 201   void complete(int complete_r);
 202
 203   // effect: Finds another lock request by txnid.
 204   // requires: The lock request info mutex is held
 205   lock_request *find_lock_request(const TXNID &txnid);
 206
 207   // effect: Insert this lock request into the locktree's set.
 208   // requires: the locktree's mutex is held
 209   void insert_into_lock_requests(void);
 210
 211   // effect: Removes this lock request from the locktree's set.
 212   // requires: The lock request info mutex is held
 213   void remove_from_lock_requests(void);
 214
 215   // effect: Asks this request's locktree which txnids are preventing
 216   //         us from getting the lock described by this request.
 217   // returns: conflicts is populated with the txnid's that this request
 218   //          is blocked on
 219   void get_conflicts(txnid_set *conflicts);
 220
 221   // effect: Builds a wait-for-graph for this lock request and the given
 222   // conflict set
 223   void build_wait_graph(wfg *wait_graph, const txnid_set &conflicts);
 224
 225   // returns: True if this lock request is in deadlock with the given conflicts
 226   // set
 227   bool deadlock_exists(const txnid_set &conflicts);
 228
 229   void copy_keys(void);
 230
 231   static int find_by_txnid(lock_request *const &request, const TXNID &txnid);
 232
 233   // Report list of conflicts to lock wait callback.
 234   static void report_waits(lock_wait_infos *wait_conflicts,
 235                            void (*lock_wait_callback)(void *,
 236                                                       lock_wait_infos *),
 237                            void *callback_arg);
 238   void add_conflicts_to_waits(txnid_set *conflicts,
 239                               lock_wait_infos *wait_conflicts);
 240
 241   void (*m_start_test_callback)(void);
 242   void (*m_start_before_pending_test_callback)(void);
 243   void (*m_retry_test_callback)(void);
 244
 245  public:
 246   std::function<void(TXNID, bool, const DBT *, const DBT *)> m_deadlock_cb;
 247
 248   friend class lock_request_unit_test;
 249 };
 250 // PORT: lock_request is not a POD anymore due to use of toku_external_cond_t
 251 //  This is ok as the PODness is not really required: lock_request objects are
 252 //  not moved in memory or anything.
 253 // ENSURE_POD(lock_request);
 254
 255 } /* namespace toku */