1 /* SPDX-License-Identifier: GPL-2.0 */ 2 3 #ifndef _LINUX_SIX_H 4 #define _LINUX_SIX_H 5 6 /** 7 * DOC: SIX locks overview 8 * 9 * Shared/intent/exclusive locks: sleepable read/write locks, like rw semaphores 10 * but with an additional state: read/shared, intent, exclusive/write 11 * 12 * The purpose of the intent state is to allow for greater concurrency on tree 13 * structures without deadlocking. In general, a read can't be upgraded to a 14 * write lock without deadlocking, so an operation that updates multiple nodes 15 * will have to take write locks for the full duration of the operation. 16 * 17 * But by adding an intent state, which is exclusive with other intent locks but 18 * not with readers, we can take intent locks at thte start of the operation, 19 * and then take write locks only for the actual update to each individual 20 * nodes, without deadlocking. 21 * 22 * Example usage: 23 * six_lock_read(&foo->lock); 24 * six_unlock_read(&foo->lock); 25 * 26 * An intent lock must be held before taking a write lock: 27 * six_lock_intent(&foo->lock); 28 * six_lock_write(&foo->lock); 29 * six_unlock_write(&foo->lock); 30 * six_unlock_intent(&foo->lock); 31 * 32 * Other operations: 33 * six_trylock_read() 34 * six_trylock_intent() 35 * six_trylock_write() 36 * 37 * six_lock_downgrade() convert from intent to read 38 * six_lock_tryupgrade() attempt to convert from read to intent, may fail 39 * 40 * There are also interfaces that take the lock type as an enum: 41 * 42 * six_lock_type(&foo->lock, SIX_LOCK_read); 43 * six_trylock_convert(&foo->lock, SIX_LOCK_read, SIX_LOCK_intent) 44 * six_lock_type(&foo->lock, SIX_LOCK_write); 45 * six_unlock_type(&foo->lock, SIX_LOCK_write); 46 * six_unlock_type(&foo->lock, SIX_LOCK_intent); 47 * 48 * Lock sequence numbers - unlock(), relock(): 49 * 50 * Locks embed sequences numbers, which are incremented on write lock/unlock. 51 * This allows locks to be dropped and the retaken iff the state they protect 52 * hasn't changed; this makes it much easier to avoid holding locks while e.g. 53 * doing IO or allocating memory. 54 * 55 * Example usage: 56 * six_lock_read(&foo->lock); 57 * u32 seq = six_lock_seq(&foo->lock); 58 * six_unlock_read(&foo->lock); 59 * 60 * some_operation_that_may_block(); 61 * 62 * if (six_relock_read(&foo->lock, seq)) { ... } 63 * 64 * If the relock operation succeeds, it is as if the lock was never unlocked. 65 * 66 * Reentrancy: 67 * 68 * Six locks are not by themselves reentrent, but have counters for both the 69 * read and intent states that can be used to provide reentrency by an upper 70 * layer that tracks held locks. If a lock is known to already be held in the 71 * read or intent state, six_lock_increment() can be used to bump the "lock 72 * held in this state" counter, increasing the number of unlock calls that 73 * will be required to fully unlock it. 74 * 75 * Example usage: 76 * six_lock_read(&foo->lock); 77 * six_lock_increment(&foo->lock, SIX_LOCK_read); 78 * six_unlock_read(&foo->lock); 79 * six_unlock_read(&foo->lock); 80 * foo->lock is now fully unlocked. 81 * 82 * Since the intent state supercedes read, it's legal to increment the read 83 * counter when holding an intent lock, but not the reverse. 84 * 85 * A lock may only be held once for write: six_lock_increment(.., SIX_LOCK_write) 86 * is not legal. 87 * 88 * should_sleep_fn: 89 * 90 * There is a six_lock() variant that takes a function pointer that is called 91 * immediately prior to schedule() when blocking, and may return an error to 92 * abort. 93 * 94 * One possible use for this feature is when objects being locked are part of 95 * a cache and may reused, and lock ordering is based on a property of the 96 * object that will change when the object is reused - i.e. logical key order. 97 * 98 * If looking up an object in the cache may race with object reuse, and lock 99 * ordering is required to prevent deadlock, object reuse may change the 100 * correct lock order for that object and cause a deadlock. should_sleep_fn 101 * can be used to check if the object is still the object we want and avoid 102 * this deadlock. 103 * 104 * Wait list entry interface: 105 * 106 * There is a six_lock() variant, six_lock_waiter(), that takes a pointer to a 107 * wait list entry. By embedding six_lock_waiter into another object, and by 108 * traversing lock waitlists, it is then possible for an upper layer to 109 * implement full cycle detection for deadlock avoidance. 110 * 111 * should_sleep_fn should be used for invoking the cycle detector, walking the 112 * graph of held locks to check for a deadlock. The upper layer must track 113 * held locks for each thread, and each thread's held locks must be reachable 114 * from its six_lock_waiter object. 115 * 116 * six_lock_waiter() will add the wait object to the waitlist re-trying taking 117 * the lock, and before calling should_sleep_fn, and the wait object will not 118 * be removed from the waitlist until either the lock has been successfully 119 * acquired, or we aborted because should_sleep_fn returned an error. 120 * 121 * Also, six_lock_waiter contains a timestamp, and waiters on a waitlist will 122 * have timestamps in strictly ascending order - this is so the timestamp can 123 * be used as a cursor for lock graph traverse. 124 */ 125 126 #include <linux/lockdep.h> 127 #include <linux/sched.h> 128 #include <linux/types.h> 129 130 #ifdef CONFIG_SIX_LOCK_SPIN_ON_OWNER 131 #include <linux/osq_lock.h> 132 #endif 133 134 enum six_lock_type { 135 SIX_LOCK_read, 136 SIX_LOCK_intent, 137 SIX_LOCK_write, 138 }; 139 140 struct six_lock { 141 atomic_t state; 142 u32 seq; 143 unsigned intent_lock_recurse; 144 struct task_struct *owner; 145 unsigned __percpu *readers; 146 #ifdef CONFIG_SIX_LOCK_SPIN_ON_OWNER 147 struct optimistic_spin_queue osq; 148 #endif 149 raw_spinlock_t wait_lock; 150 struct list_head wait_list; 151 #ifdef CONFIG_DEBUG_LOCK_ALLOC 152 struct lockdep_map dep_map; 153 #endif 154 }; 155 156 struct six_lock_waiter { 157 struct list_head list; 158 struct task_struct *task; 159 enum six_lock_type lock_want; 160 bool lock_acquired; 161 u64 start_time; 162 }; 163 164 typedef int (*six_lock_should_sleep_fn)(struct six_lock *lock, void *); 165 166 void six_lock_exit(struct six_lock *lock); 167 168 enum six_lock_init_flags { 169 SIX_LOCK_INIT_PCPU = 1U << 0, 170 }; 171 172 void __six_lock_init(struct six_lock *lock, const char *name, 173 struct lock_class_key *key, enum six_lock_init_flags flags); 174 175 /** 176 * six_lock_init - initialize a six lock 177 * @lock: lock to initialize 178 * @flags: optional flags, i.e. SIX_LOCK_INIT_PCPU 179 */ 180 #define six_lock_init(lock, flags) \ 181 do { \ 182 static struct lock_class_key __key; \ 183 \ 184 __six_lock_init((lock), #lock, &__key, flags); \ 185 } while (0) 186 187 /** 188 * six_lock_seq - obtain current lock sequence number 189 * @lock: six_lock to obtain sequence number for 190 * 191 * @lock should be held for read or intent, and not write 192 * 193 * By saving the lock sequence number, we can unlock @lock and then (typically 194 * after some blocking operation) attempt to relock it: the relock will succeed 195 * if the sequence number hasn't changed, meaning no write locks have been taken 196 * and state corresponding to what @lock protects is still valid. 197 */ 198 static inline u32 six_lock_seq(const struct six_lock *lock) 199 { 200 return lock->seq; 201 } 202 203 bool six_trylock_ip(struct six_lock *lock, enum six_lock_type type, unsigned long ip); 204 205 /** 206 * six_trylock_type - attempt to take a six lock without blocking 207 * @lock: lock to take 208 * @type: SIX_LOCK_read, SIX_LOCK_intent, or SIX_LOCK_write 209 * 210 * Return: true on success, false on failure. 211 */ 212 static inline bool six_trylock_type(struct six_lock *lock, enum six_lock_type type) 213 { 214 return six_trylock_ip(lock, type, _THIS_IP_); 215 } 216 217 int six_lock_ip_waiter(struct six_lock *lock, enum six_lock_type type, 218 struct six_lock_waiter *wait, 219 six_lock_should_sleep_fn should_sleep_fn, void *p, 220 unsigned long ip); 221 222 /** 223 * six_lock_waiter - take a lock, with full waitlist interface 224 * @lock: lock to take 225 * @type: SIX_LOCK_read, SIX_LOCK_intent, or SIX_LOCK_write 226 * @wait: pointer to wait object, which will be added to lock's waitlist 227 * @should_sleep_fn: callback run after adding to waitlist, immediately prior 228 * to scheduling 229 * @p: passed through to @should_sleep_fn 230 * 231 * This is a convenience wrapper around six_lock_ip_waiter(), see that function 232 * for full documentation. 233 * 234 * Return: 0 on success, or the return code from @should_sleep_fn on failure. 235 */ 236 static inline int six_lock_waiter(struct six_lock *lock, enum six_lock_type type, 237 struct six_lock_waiter *wait, 238 six_lock_should_sleep_fn should_sleep_fn, void *p) 239 { 240 return six_lock_ip_waiter(lock, type, wait, should_sleep_fn, p, _THIS_IP_); 241 } 242 243 /** 244 * six_lock_ip - take a six lock lock 245 * @lock: lock to take 246 * @type: SIX_LOCK_read, SIX_LOCK_intent, or SIX_LOCK_write 247 * @should_sleep_fn: callback run after adding to waitlist, immediately prior 248 * to scheduling 249 * @p: passed through to @should_sleep_fn 250 * @ip: ip parameter for lockdep/lockstat, i.e. _THIS_IP_ 251 * 252 * Return: 0 on success, or the return code from @should_sleep_fn on failure. 253 */ 254 static inline int six_lock_ip(struct six_lock *lock, enum six_lock_type type, 255 six_lock_should_sleep_fn should_sleep_fn, void *p, 256 unsigned long ip) 257 { 258 struct six_lock_waiter wait; 259 260 return six_lock_ip_waiter(lock, type, &wait, should_sleep_fn, p, ip); 261 } 262 263 /** 264 * six_lock_type - take a six lock lock 265 * @lock: lock to take 266 * @type: SIX_LOCK_read, SIX_LOCK_intent, or SIX_LOCK_write 267 * @should_sleep_fn: callback run after adding to waitlist, immediately prior 268 * to scheduling 269 * @p: passed through to @should_sleep_fn 270 * 271 * Return: 0 on success, or the return code from @should_sleep_fn on failure. 272 */ 273 static inline int six_lock_type(struct six_lock *lock, enum six_lock_type type, 274 six_lock_should_sleep_fn should_sleep_fn, void *p) 275 { 276 struct six_lock_waiter wait; 277 278 return six_lock_ip_waiter(lock, type, &wait, should_sleep_fn, p, _THIS_IP_); 279 } 280 281 bool six_relock_ip(struct six_lock *lock, enum six_lock_type type, 282 unsigned seq, unsigned long ip); 283 284 /** 285 * six_relock_type - attempt to re-take a lock that was held previously 286 * @lock: lock to take 287 * @type: SIX_LOCK_read, SIX_LOCK_intent, or SIX_LOCK_write 288 * @seq: lock sequence number obtained from six_lock_seq() while lock was 289 * held previously 290 * 291 * Return: true on success, false on failure. 292 */ 293 static inline bool six_relock_type(struct six_lock *lock, enum six_lock_type type, 294 unsigned seq) 295 { 296 return six_relock_ip(lock, type, seq, _THIS_IP_); 297 } 298 299 void six_unlock_ip(struct six_lock *lock, enum six_lock_type type, unsigned long ip); 300 301 /** 302 * six_unlock_type - drop a six lock 303 * @lock: lock to unlock 304 * @type: SIX_LOCK_read, SIX_LOCK_intent, or SIX_LOCK_write 305 * 306 * When a lock is held multiple times (because six_lock_incement()) was used), 307 * this decrements the 'lock held' counter by one. 308 * 309 * For example: 310 * six_lock_read(&foo->lock); read count 1 311 * six_lock_increment(&foo->lock, SIX_LOCK_read); read count 2 312 * six_lock_unlock(&foo->lock, SIX_LOCK_read); read count 1 313 * six_lock_unlock(&foo->lock, SIX_LOCK_read); read count 0 314 */ 315 static inline void six_unlock_type(struct six_lock *lock, enum six_lock_type type) 316 { 317 six_unlock_ip(lock, type, _THIS_IP_); 318 } 319 320 #define __SIX_LOCK(type) \ 321 static inline bool six_trylock_ip_##type(struct six_lock *lock, unsigned long ip)\ 322 { \ 323 return six_trylock_ip(lock, SIX_LOCK_##type, ip); \ 324 } \ 325 \ 326 static inline bool six_trylock_##type(struct six_lock *lock) \ 327 { \ 328 return six_trylock_ip(lock, SIX_LOCK_##type, _THIS_IP_); \ 329 } \ 330 \ 331 static inline int six_lock_ip_waiter_##type(struct six_lock *lock, \ 332 struct six_lock_waiter *wait, \ 333 six_lock_should_sleep_fn should_sleep_fn, void *p,\ 334 unsigned long ip) \ 335 { \ 336 return six_lock_ip_waiter(lock, SIX_LOCK_##type, wait, should_sleep_fn, p, ip);\ 337 } \ 338 \ 339 static inline int six_lock_ip_##type(struct six_lock *lock, \ 340 six_lock_should_sleep_fn should_sleep_fn, void *p, \ 341 unsigned long ip) \ 342 { \ 343 return six_lock_ip(lock, SIX_LOCK_##type, should_sleep_fn, p, ip);\ 344 } \ 345 \ 346 static inline bool six_relock_ip_##type(struct six_lock *lock, u32 seq, unsigned long ip)\ 347 { \ 348 return six_relock_ip(lock, SIX_LOCK_##type, seq, ip); \ 349 } \ 350 \ 351 static inline bool six_relock_##type(struct six_lock *lock, u32 seq) \ 352 { \ 353 return six_relock_ip(lock, SIX_LOCK_##type, seq, _THIS_IP_); \ 354 } \ 355 \ 356 static inline int six_lock_##type(struct six_lock *lock, \ 357 six_lock_should_sleep_fn fn, void *p)\ 358 { \ 359 return six_lock_ip_##type(lock, fn, p, _THIS_IP_); \ 360 } \ 361 \ 362 static inline void six_unlock_ip_##type(struct six_lock *lock, unsigned long ip) \ 363 { \ 364 six_unlock_ip(lock, SIX_LOCK_##type, ip); \ 365 } \ 366 \ 367 static inline void six_unlock_##type(struct six_lock *lock) \ 368 { \ 369 six_unlock_ip(lock, SIX_LOCK_##type, _THIS_IP_); \ 370 } 371 372 __SIX_LOCK(read) 373 __SIX_LOCK(intent) 374 __SIX_LOCK(write) 375 #undef __SIX_LOCK 376 377 void six_lock_downgrade(struct six_lock *); 378 bool six_lock_tryupgrade(struct six_lock *); 379 bool six_trylock_convert(struct six_lock *, enum six_lock_type, 380 enum six_lock_type); 381 382 void six_lock_increment(struct six_lock *, enum six_lock_type); 383 384 void six_lock_wakeup_all(struct six_lock *); 385 386 struct six_lock_count { 387 unsigned n[3]; 388 }; 389 390 struct six_lock_count six_lock_counts(struct six_lock *); 391 void six_lock_readers_add(struct six_lock *, int); 392 393 #endif /* _LINUX_SIX_H */ 394