1 // Copyright (c) 2011-present, Facebook, Inc. All rights reserved. 2 // This source code is licensed under both the GPLv2 (found in the 3 // COPYING file in the root directory) and Apache 2.0 License 4 // (found in the LICENSE.Apache file in the root directory). 5 6 #pragma once 7 #ifndef ROCKSDB_LITE 8 9 #include <memory> 10 #include <string> 11 #include <unordered_map> 12 #include <utility> 13 #include <vector> 14 15 #include "monitoring/instrumented_mutex.h" 16 #include "rocksdb/utilities/transaction.h" 17 #include "util/autovector.h" 18 #include "util/hash_map.h" 19 #include "util/thread_local.h" 20 #include "utilities/transactions/lock/lock_manager.h" 21 #include "utilities/transactions/lock/point/point_lock_tracker.h" 22 23 namespace ROCKSDB_NAMESPACE { 24 25 class ColumnFamilyHandle; 26 struct LockInfo; 27 struct LockMap; 28 struct LockMapStripe; 29 30 template <class Path> 31 class DeadlockInfoBufferTempl { 32 private: 33 std::vector<Path> paths_buffer_; 34 uint32_t buffer_idx_; 35 std::mutex paths_buffer_mutex_; 36 Normalize()37 std::vector<Path> Normalize() { 38 auto working = paths_buffer_; 39 40 if (working.empty()) { 41 return working; 42 } 43 44 // Next write occurs at a nonexistent path's slot 45 if (paths_buffer_[buffer_idx_].empty()) { 46 working.resize(buffer_idx_); 47 } else { 48 std::rotate(working.begin(), working.begin() + buffer_idx_, 49 working.end()); 50 } 51 52 return working; 53 } 54 55 public: DeadlockInfoBufferTempl(uint32_t n_latest_dlocks)56 explicit DeadlockInfoBufferTempl(uint32_t n_latest_dlocks) 57 : paths_buffer_(n_latest_dlocks), buffer_idx_(0) {} 58 AddNewPath(Path path)59 void AddNewPath(Path path) { 60 std::lock_guard<std::mutex> lock(paths_buffer_mutex_); 61 62 if (paths_buffer_.empty()) { 63 return; 64 } 65 66 paths_buffer_[buffer_idx_] = std::move(path); 67 buffer_idx_ = (buffer_idx_ + 1) % paths_buffer_.size(); 68 } 69 Resize(uint32_t target_size)70 void Resize(uint32_t target_size) { 71 std::lock_guard<std::mutex> lock(paths_buffer_mutex_); 72 73 paths_buffer_ = Normalize(); 74 75 // Drop the deadlocks that will no longer be needed ater the normalize 76 if (target_size < paths_buffer_.size()) { 77 paths_buffer_.erase( 78 paths_buffer_.begin(), 79 paths_buffer_.begin() + (paths_buffer_.size() - target_size)); 80 buffer_idx_ = 0; 81 } 82 // Resize the buffer to the target size and restore the buffer's idx 83 else { 84 auto prev_size = paths_buffer_.size(); 85 paths_buffer_.resize(target_size); 86 buffer_idx_ = (uint32_t)prev_size; 87 } 88 } 89 PrepareBuffer()90 std::vector<Path> PrepareBuffer() { 91 std::lock_guard<std::mutex> lock(paths_buffer_mutex_); 92 93 // Reversing the normalized vector returns the latest deadlocks first 94 auto working = Normalize(); 95 std::reverse(working.begin(), working.end()); 96 97 return working; 98 } 99 }; 100 101 typedef DeadlockInfoBufferTempl<DeadlockPath> DeadlockInfoBuffer; 102 103 struct TrackedTrxInfo { 104 autovector<TransactionID> m_neighbors; 105 uint32_t m_cf_id; 106 bool m_exclusive; 107 std::string m_waiting_key; 108 }; 109 110 class PointLockManager : public LockManager { 111 public: 112 PointLockManager(PessimisticTransactionDB* db, 113 const TransactionDBOptions& opt); 114 // No copying allowed 115 PointLockManager(const PointLockManager&) = delete; 116 PointLockManager& operator=(const PointLockManager&) = delete; 117 118 ~PointLockManager() override; 119 IsPointLockSupported()120 bool IsPointLockSupported() const override { return true; } 121 IsRangeLockSupported()122 bool IsRangeLockSupported() const override { return false; } 123 GetLockTrackerFactory()124 const LockTrackerFactory& GetLockTrackerFactory() const override { 125 return PointLockTrackerFactory::Get(); 126 } 127 128 // Creates a new LockMap for this column family. Caller should guarantee 129 // that this column family does not already exist. 130 void AddColumnFamily(const ColumnFamilyHandle* cf) override; 131 // Deletes the LockMap for this column family. Caller should guarantee that 132 // this column family is no longer in use. 133 void RemoveColumnFamily(const ColumnFamilyHandle* cf) override; 134 135 Status TryLock(PessimisticTransaction* txn, ColumnFamilyId column_family_id, 136 const std::string& key, Env* env, bool exclusive) override; 137 Status TryLock(PessimisticTransaction* txn, ColumnFamilyId column_family_id, 138 const Endpoint& start, const Endpoint& end, Env* env, 139 bool exclusive) override; 140 141 void UnLock(PessimisticTransaction* txn, const LockTracker& tracker, 142 Env* env) override; 143 void UnLock(PessimisticTransaction* txn, ColumnFamilyId column_family_id, 144 const std::string& key, Env* env) override; 145 void UnLock(PessimisticTransaction* txn, ColumnFamilyId column_family_id, 146 const Endpoint& start, const Endpoint& end, Env* env) override; 147 148 PointLockStatus GetPointLockStatus() override; 149 150 RangeLockStatus GetRangeLockStatus() override; 151 152 std::vector<DeadlockPath> GetDeadlockInfoBuffer() override; 153 154 void Resize(uint32_t new_size) override; 155 156 private: 157 PessimisticTransactionDB* txn_db_impl_; 158 159 // Default number of lock map stripes per column family 160 const size_t default_num_stripes_; 161 162 // Limit on number of keys locked per column family 163 const int64_t max_num_locks_; 164 165 // The following lock order must be satisfied in order to avoid deadlocking 166 // ourselves. 167 // - lock_map_mutex_ 168 // - stripe mutexes in ascending cf id, ascending stripe order 169 // - wait_txn_map_mutex_ 170 // 171 // Must be held when accessing/modifying lock_maps_. 172 InstrumentedMutex lock_map_mutex_; 173 174 // Map of ColumnFamilyId to locked key info 175 using LockMaps = std::unordered_map<uint32_t, std::shared_ptr<LockMap>>; 176 LockMaps lock_maps_; 177 178 // Thread-local cache of entries in lock_maps_. This is an optimization 179 // to avoid acquiring a mutex in order to look up a LockMap 180 std::unique_ptr<ThreadLocalPtr> lock_maps_cache_; 181 182 // Must be held when modifying wait_txn_map_ and rev_wait_txn_map_. 183 std::mutex wait_txn_map_mutex_; 184 185 // Maps from waitee -> number of waiters. 186 HashMap<TransactionID, int> rev_wait_txn_map_; 187 // Maps from waiter -> waitee. 188 HashMap<TransactionID, TrackedTrxInfo> wait_txn_map_; 189 DeadlockInfoBuffer dlock_buffer_; 190 191 // Used to allocate mutexes/condvars to use when locking keys 192 std::shared_ptr<TransactionDBMutexFactory> mutex_factory_; 193 194 bool IsLockExpired(TransactionID txn_id, const LockInfo& lock_info, Env* env, 195 uint64_t* wait_time); 196 197 std::shared_ptr<LockMap> GetLockMap(uint32_t column_family_id); 198 199 Status AcquireWithTimeout(PessimisticTransaction* txn, LockMap* lock_map, 200 LockMapStripe* stripe, uint32_t column_family_id, 201 const std::string& key, Env* env, int64_t timeout, 202 LockInfo&& lock_info); 203 204 Status AcquireLocked(LockMap* lock_map, LockMapStripe* stripe, 205 const std::string& key, Env* env, 206 LockInfo&& lock_info, uint64_t* wait_time, 207 autovector<TransactionID>* txn_ids); 208 209 void UnLockKey(PessimisticTransaction* txn, const std::string& key, 210 LockMapStripe* stripe, LockMap* lock_map, Env* env); 211 212 bool IncrementWaiters(const PessimisticTransaction* txn, 213 const autovector<TransactionID>& wait_ids, 214 const std::string& key, const uint32_t& cf_id, 215 const bool& exclusive, Env* const env); 216 void DecrementWaiters(const PessimisticTransaction* txn, 217 const autovector<TransactionID>& wait_ids); 218 void DecrementWaitersImpl(const PessimisticTransaction* txn, 219 const autovector<TransactionID>& wait_ids); 220 }; 221 222 } // namespace ROCKSDB_NAMESPACE 223 #endif // ROCKSDB_LITE 224