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 the 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 reentrant, but have counters for both the 69 * read and intent states that can be used to provide reentrancy 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 enum six_lock_type { 131 SIX_LOCK_read, 132 SIX_LOCK_intent, 133 SIX_LOCK_write, 134 }; 135 136 struct six_lock { 137 atomic_t state; 138 u32 seq; 139 unsigned intent_lock_recurse; 140 unsigned write_lock_recurse; 141 struct task_struct *owner; 142 unsigned __percpu *readers; 143 raw_spinlock_t wait_lock; 144 struct list_head wait_list; 145 #ifdef CONFIG_DEBUG_LOCK_ALLOC 146 struct lockdep_map dep_map; 147 #endif 148 }; 149 150 struct six_lock_waiter { 151 struct list_head list; 152 struct task_struct *task; 153 enum six_lock_type lock_want; 154 bool lock_acquired; 155 u64 start_time; 156 }; 157 158 typedef int (*six_lock_should_sleep_fn)(struct six_lock *lock, void *); 159 160 void six_lock_exit(struct six_lock *lock); 161 162 enum six_lock_init_flags { 163 SIX_LOCK_INIT_PCPU = 1U << 0, 164 }; 165 166 void __six_lock_init(struct six_lock *lock, const char *name, 167 struct lock_class_key *key, enum six_lock_init_flags flags); 168 169 /** 170 * six_lock_init - initialize a six lock 171 * @lock: lock to initialize 172 * @flags: optional flags, i.e. SIX_LOCK_INIT_PCPU 173 */ 174 #define six_lock_init(lock, flags) \ 175 do { \ 176 static struct lock_class_key __key; \ 177 \ 178 __six_lock_init((lock), #lock, &__key, flags); \ 179 } while (0) 180 181 /** 182 * six_lock_seq - obtain current lock sequence number 183 * @lock: six_lock to obtain sequence number for 184 * 185 * @lock should be held for read or intent, and not write 186 * 187 * By saving the lock sequence number, we can unlock @lock and then (typically 188 * after some blocking operation) attempt to relock it: the relock will succeed 189 * if the sequence number hasn't changed, meaning no write locks have been taken 190 * and state corresponding to what @lock protects is still valid. 191 */ 192 static inline u32 six_lock_seq(const struct six_lock *lock) 193 { 194 return lock->seq; 195 } 196 197 bool six_trylock_ip(struct six_lock *lock, enum six_lock_type type, unsigned long ip); 198 199 /** 200 * six_trylock_type - attempt to take a six lock without blocking 201 * @lock: lock to take 202 * @type: SIX_LOCK_read, SIX_LOCK_intent, or SIX_LOCK_write 203 * 204 * Return: true on success, false on failure. 205 */ 206 static inline bool six_trylock_type(struct six_lock *lock, enum six_lock_type type) 207 { 208 return six_trylock_ip(lock, type, _THIS_IP_); 209 } 210 211 int six_lock_ip_waiter(struct six_lock *lock, enum six_lock_type type, 212 struct six_lock_waiter *wait, 213 six_lock_should_sleep_fn should_sleep_fn, void *p, 214 unsigned long ip); 215 216 /** 217 * six_lock_waiter - take a lock, with full waitlist interface 218 * @lock: lock to take 219 * @type: SIX_LOCK_read, SIX_LOCK_intent, or SIX_LOCK_write 220 * @wait: pointer to wait object, which will be added to lock's waitlist 221 * @should_sleep_fn: callback run after adding to waitlist, immediately prior 222 * to scheduling 223 * @p: passed through to @should_sleep_fn 224 * 225 * This is a convenience wrapper around six_lock_ip_waiter(), see that function 226 * for full documentation. 227 * 228 * Return: 0 on success, or the return code from @should_sleep_fn on failure. 229 */ 230 static inline int six_lock_waiter(struct six_lock *lock, enum six_lock_type type, 231 struct six_lock_waiter *wait, 232 six_lock_should_sleep_fn should_sleep_fn, void *p) 233 { 234 return six_lock_ip_waiter(lock, type, wait, should_sleep_fn, p, _THIS_IP_); 235 } 236 237 /** 238 * six_lock_ip - take a six lock lock 239 * @lock: lock to take 240 * @type: SIX_LOCK_read, SIX_LOCK_intent, or SIX_LOCK_write 241 * @should_sleep_fn: callback run after adding to waitlist, immediately prior 242 * to scheduling 243 * @p: passed through to @should_sleep_fn 244 * @ip: ip parameter for lockdep/lockstat, i.e. _THIS_IP_ 245 * 246 * Return: 0 on success, or the return code from @should_sleep_fn on failure. 247 */ 248 static inline int six_lock_ip(struct six_lock *lock, enum six_lock_type type, 249 six_lock_should_sleep_fn should_sleep_fn, void *p, 250 unsigned long ip) 251 { 252 struct six_lock_waiter wait; 253 254 return six_lock_ip_waiter(lock, type, &wait, should_sleep_fn, p, ip); 255 } 256 257 /** 258 * six_lock_type - take a six lock lock 259 * @lock: lock to take 260 * @type: SIX_LOCK_read, SIX_LOCK_intent, or SIX_LOCK_write 261 * @should_sleep_fn: callback run after adding to waitlist, immediately prior 262 * to scheduling 263 * @p: passed through to @should_sleep_fn 264 * 265 * Return: 0 on success, or the return code from @should_sleep_fn on failure. 266 */ 267 static inline int six_lock_type(struct six_lock *lock, enum six_lock_type type, 268 six_lock_should_sleep_fn should_sleep_fn, void *p) 269 { 270 struct six_lock_waiter wait; 271 272 return six_lock_ip_waiter(lock, type, &wait, should_sleep_fn, p, _THIS_IP_); 273 } 274 275 bool six_relock_ip(struct six_lock *lock, enum six_lock_type type, 276 unsigned seq, unsigned long ip); 277 278 /** 279 * six_relock_type - attempt to re-take a lock that was held previously 280 * @lock: lock to take 281 * @type: SIX_LOCK_read, SIX_LOCK_intent, or SIX_LOCK_write 282 * @seq: lock sequence number obtained from six_lock_seq() while lock was 283 * held previously 284 * 285 * Return: true on success, false on failure. 286 */ 287 static inline bool six_relock_type(struct six_lock *lock, enum six_lock_type type, 288 unsigned seq) 289 { 290 return six_relock_ip(lock, type, seq, _THIS_IP_); 291 } 292 293 void six_unlock_ip(struct six_lock *lock, enum six_lock_type type, unsigned long ip); 294 295 /** 296 * six_unlock_type - drop a six lock 297 * @lock: lock to unlock 298 * @type: SIX_LOCK_read, SIX_LOCK_intent, or SIX_LOCK_write 299 * 300 * When a lock is held multiple times (because six_lock_incement()) was used), 301 * this decrements the 'lock held' counter by one. 302 * 303 * For example: 304 * six_lock_read(&foo->lock); read count 1 305 * six_lock_increment(&foo->lock, SIX_LOCK_read); read count 2 306 * six_lock_unlock(&foo->lock, SIX_LOCK_read); read count 1 307 * six_lock_unlock(&foo->lock, SIX_LOCK_read); read count 0 308 */ 309 static inline void six_unlock_type(struct six_lock *lock, enum six_lock_type type) 310 { 311 six_unlock_ip(lock, type, _THIS_IP_); 312 } 313 314 #define __SIX_LOCK(type) \ 315 static inline bool six_trylock_ip_##type(struct six_lock *lock, unsigned long ip)\ 316 { \ 317 return six_trylock_ip(lock, SIX_LOCK_##type, ip); \ 318 } \ 319 \ 320 static inline bool six_trylock_##type(struct six_lock *lock) \ 321 { \ 322 return six_trylock_ip(lock, SIX_LOCK_##type, _THIS_IP_); \ 323 } \ 324 \ 325 static inline int six_lock_ip_waiter_##type(struct six_lock *lock, \ 326 struct six_lock_waiter *wait, \ 327 six_lock_should_sleep_fn should_sleep_fn, void *p,\ 328 unsigned long ip) \ 329 { \ 330 return six_lock_ip_waiter(lock, SIX_LOCK_##type, wait, should_sleep_fn, p, ip);\ 331 } \ 332 \ 333 static inline int six_lock_ip_##type(struct six_lock *lock, \ 334 six_lock_should_sleep_fn should_sleep_fn, void *p, \ 335 unsigned long ip) \ 336 { \ 337 return six_lock_ip(lock, SIX_LOCK_##type, should_sleep_fn, p, ip);\ 338 } \ 339 \ 340 static inline bool six_relock_ip_##type(struct six_lock *lock, u32 seq, unsigned long ip)\ 341 { \ 342 return six_relock_ip(lock, SIX_LOCK_##type, seq, ip); \ 343 } \ 344 \ 345 static inline bool six_relock_##type(struct six_lock *lock, u32 seq) \ 346 { \ 347 return six_relock_ip(lock, SIX_LOCK_##type, seq, _THIS_IP_); \ 348 } \ 349 \ 350 static inline int six_lock_##type(struct six_lock *lock, \ 351 six_lock_should_sleep_fn fn, void *p)\ 352 { \ 353 return six_lock_ip_##type(lock, fn, p, _THIS_IP_); \ 354 } \ 355 \ 356 static inline void six_unlock_ip_##type(struct six_lock *lock, unsigned long ip) \ 357 { \ 358 six_unlock_ip(lock, SIX_LOCK_##type, ip); \ 359 } \ 360 \ 361 static inline void six_unlock_##type(struct six_lock *lock) \ 362 { \ 363 six_unlock_ip(lock, SIX_LOCK_##type, _THIS_IP_); \ 364 } 365 366 __SIX_LOCK(read) 367 __SIX_LOCK(intent) 368 __SIX_LOCK(write) 369 #undef __SIX_LOCK 370 371 void six_lock_downgrade(struct six_lock *); 372 bool six_lock_tryupgrade(struct six_lock *); 373 bool six_trylock_convert(struct six_lock *, enum six_lock_type, 374 enum six_lock_type); 375 376 void six_lock_increment(struct six_lock *, enum six_lock_type); 377 378 void six_lock_wakeup_all(struct six_lock *); 379 380 struct six_lock_count { 381 unsigned n[3]; 382 }; 383 384 struct six_lock_count six_lock_counts(struct six_lock *); 385 void six_lock_readers_add(struct six_lock *, int); 386 387 #endif /* _LINUX_SIX_H */ 388