387 lines · c
1/* SPDX-License-Identifier: GPL-2.0 */2 3#ifndef _LINUX_SIX_H4#define _LINUX_SIX_H5 6/**7 * DOC: SIX locks overview8 *9 * Shared/intent/exclusive locks: sleepable read/write locks, like rw semaphores10 * but with an additional state: read/shared, intent, exclusive/write11 *12 * The purpose of the intent state is to allow for greater concurrency on tree13 * structures without deadlocking. In general, a read can't be upgraded to a14 * write lock without deadlocking, so an operation that updates multiple nodes15 * 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 but18 * 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 individual20 * 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 read38 * six_lock_tryupgrade() attempt to convert from read to intent, may fail39 *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 protect52 * 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 the69 * read and intent states that can be used to provide reentrancy by an upper70 * layer that tracks held locks. If a lock is known to already be held in the71 * read or intent state, six_lock_increment() can be used to bump the "lock72 * held in this state" counter, increasing the number of unlock calls that73 * 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 read83 * 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 called91 * immediately prior to schedule() when blocking, and may return an error to92 * abort.93 *94 * One possible use for this feature is when objects being locked are part of95 * a cache and may reused, and lock ordering is based on a property of the96 * 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 lock99 * ordering is required to prevent deadlock, object reuse may change the100 * correct lock order for that object and cause a deadlock. should_sleep_fn101 * can be used to check if the object is still the object we want and avoid102 * this deadlock.103 *104 * Wait list entry interface:105 *106 * There is a six_lock() variant, six_lock_waiter(), that takes a pointer to a107 * wait list entry. By embedding six_lock_waiter into another object, and by108 * traversing lock waitlists, it is then possible for an upper layer to109 * implement full cycle detection for deadlock avoidance.110 *111 * should_sleep_fn should be used for invoking the cycle detector, walking the112 * graph of held locks to check for a deadlock. The upper layer must track113 * held locks for each thread, and each thread's held locks must be reachable114 * from its six_lock_waiter object.115 *116 * six_lock_waiter() will add the wait object to the waitlist re-trying taking117 * the lock, and before calling should_sleep_fn, and the wait object will not118 * be removed from the waitlist until either the lock has been successfully119 * 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 will122 * have timestamps in strictly ascending order - this is so the timestamp can123 * 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 130enum six_lock_type {131 SIX_LOCK_read,132 SIX_LOCK_intent,133 SIX_LOCK_write,134};135 136struct six_lock {137 atomic_t state;138 u32 seq;139 unsigned intent_lock_recurse;140 struct task_struct *owner;141 unsigned __percpu *readers;142 raw_spinlock_t wait_lock;143 struct list_head wait_list;144#ifdef CONFIG_DEBUG_LOCK_ALLOC145 struct lockdep_map dep_map;146#endif147};148 149struct six_lock_waiter {150 struct list_head list;151 struct task_struct *task;152 enum six_lock_type lock_want;153 bool lock_acquired;154 u64 start_time;155};156 157typedef int (*six_lock_should_sleep_fn)(struct six_lock *lock, void *);158 159void six_lock_exit(struct six_lock *lock);160 161enum six_lock_init_flags {162 SIX_LOCK_INIT_PCPU = 1U << 0,163};164 165void __six_lock_init(struct six_lock *lock, const char *name,166 struct lock_class_key *key, enum six_lock_init_flags flags);167 168/**169 * six_lock_init - initialize a six lock170 * @lock: lock to initialize171 * @flags: optional flags, i.e. SIX_LOCK_INIT_PCPU172 */173#define six_lock_init(lock, flags) \174do { \175 static struct lock_class_key __key; \176 \177 __six_lock_init((lock), #lock, &__key, flags); \178} while (0)179 180/**181 * six_lock_seq - obtain current lock sequence number182 * @lock: six_lock to obtain sequence number for183 *184 * @lock should be held for read or intent, and not write185 *186 * By saving the lock sequence number, we can unlock @lock and then (typically187 * after some blocking operation) attempt to relock it: the relock will succeed188 * if the sequence number hasn't changed, meaning no write locks have been taken189 * and state corresponding to what @lock protects is still valid.190 */191static inline u32 six_lock_seq(const struct six_lock *lock)192{193 return lock->seq;194}195 196bool six_trylock_ip(struct six_lock *lock, enum six_lock_type type, unsigned long ip);197 198/**199 * six_trylock_type - attempt to take a six lock without blocking200 * @lock: lock to take201 * @type: SIX_LOCK_read, SIX_LOCK_intent, or SIX_LOCK_write202 *203 * Return: true on success, false on failure.204 */205static inline bool six_trylock_type(struct six_lock *lock, enum six_lock_type type)206{207 return six_trylock_ip(lock, type, _THIS_IP_);208}209 210int six_lock_ip_waiter(struct six_lock *lock, enum six_lock_type type,211 struct six_lock_waiter *wait,212 six_lock_should_sleep_fn should_sleep_fn, void *p,213 unsigned long ip);214 215/**216 * six_lock_waiter - take a lock, with full waitlist interface217 * @lock: lock to take218 * @type: SIX_LOCK_read, SIX_LOCK_intent, or SIX_LOCK_write219 * @wait: pointer to wait object, which will be added to lock's waitlist220 * @should_sleep_fn: callback run after adding to waitlist, immediately prior221 * to scheduling222 * @p: passed through to @should_sleep_fn223 *224 * This is a convenience wrapper around six_lock_ip_waiter(), see that function225 * for full documentation.226 *227 * Return: 0 on success, or the return code from @should_sleep_fn on failure.228 */229static inline int six_lock_waiter(struct six_lock *lock, enum six_lock_type type,230 struct six_lock_waiter *wait,231 six_lock_should_sleep_fn should_sleep_fn, void *p)232{233 return six_lock_ip_waiter(lock, type, wait, should_sleep_fn, p, _THIS_IP_);234}235 236/**237 * six_lock_ip - take a six lock lock238 * @lock: lock to take239 * @type: SIX_LOCK_read, SIX_LOCK_intent, or SIX_LOCK_write240 * @should_sleep_fn: callback run after adding to waitlist, immediately prior241 * to scheduling242 * @p: passed through to @should_sleep_fn243 * @ip: ip parameter for lockdep/lockstat, i.e. _THIS_IP_244 *245 * Return: 0 on success, or the return code from @should_sleep_fn on failure.246 */247static inline int six_lock_ip(struct six_lock *lock, enum six_lock_type type,248 six_lock_should_sleep_fn should_sleep_fn, void *p,249 unsigned long ip)250{251 struct six_lock_waiter wait;252 253 return six_lock_ip_waiter(lock, type, &wait, should_sleep_fn, p, ip);254}255 256/**257 * six_lock_type - take a six lock lock258 * @lock: lock to take259 * @type: SIX_LOCK_read, SIX_LOCK_intent, or SIX_LOCK_write260 * @should_sleep_fn: callback run after adding to waitlist, immediately prior261 * to scheduling262 * @p: passed through to @should_sleep_fn263 *264 * Return: 0 on success, or the return code from @should_sleep_fn on failure.265 */266static inline int six_lock_type(struct six_lock *lock, enum six_lock_type type,267 six_lock_should_sleep_fn should_sleep_fn, void *p)268{269 struct six_lock_waiter wait;270 271 return six_lock_ip_waiter(lock, type, &wait, should_sleep_fn, p, _THIS_IP_);272}273 274bool six_relock_ip(struct six_lock *lock, enum six_lock_type type,275 unsigned seq, unsigned long ip);276 277/**278 * six_relock_type - attempt to re-take a lock that was held previously279 * @lock: lock to take280 * @type: SIX_LOCK_read, SIX_LOCK_intent, or SIX_LOCK_write281 * @seq: lock sequence number obtained from six_lock_seq() while lock was282 * held previously283 *284 * Return: true on success, false on failure.285 */286static inline bool six_relock_type(struct six_lock *lock, enum six_lock_type type,287 unsigned seq)288{289 return six_relock_ip(lock, type, seq, _THIS_IP_);290}291 292void six_unlock_ip(struct six_lock *lock, enum six_lock_type type, unsigned long ip);293 294/**295 * six_unlock_type - drop a six lock296 * @lock: lock to unlock297 * @type: SIX_LOCK_read, SIX_LOCK_intent, or SIX_LOCK_write298 *299 * When a lock is held multiple times (because six_lock_incement()) was used),300 * this decrements the 'lock held' counter by one.301 *302 * For example:303 * six_lock_read(&foo->lock); read count 1304 * six_lock_increment(&foo->lock, SIX_LOCK_read); read count 2305 * six_lock_unlock(&foo->lock, SIX_LOCK_read); read count 1306 * six_lock_unlock(&foo->lock, SIX_LOCK_read); read count 0307 */308static inline void six_unlock_type(struct six_lock *lock, enum six_lock_type type)309{310 six_unlock_ip(lock, type, _THIS_IP_);311}312 313#define __SIX_LOCK(type) \314static inline bool six_trylock_ip_##type(struct six_lock *lock, unsigned long ip)\315{ \316 return six_trylock_ip(lock, SIX_LOCK_##type, ip); \317} \318 \319static inline bool six_trylock_##type(struct six_lock *lock) \320{ \321 return six_trylock_ip(lock, SIX_LOCK_##type, _THIS_IP_); \322} \323 \324static inline int six_lock_ip_waiter_##type(struct six_lock *lock, \325 struct six_lock_waiter *wait, \326 six_lock_should_sleep_fn should_sleep_fn, void *p,\327 unsigned long ip) \328{ \329 return six_lock_ip_waiter(lock, SIX_LOCK_##type, wait, should_sleep_fn, p, ip);\330} \331 \332static inline int six_lock_ip_##type(struct six_lock *lock, \333 six_lock_should_sleep_fn should_sleep_fn, void *p, \334 unsigned long ip) \335{ \336 return six_lock_ip(lock, SIX_LOCK_##type, should_sleep_fn, p, ip);\337} \338 \339static inline bool six_relock_ip_##type(struct six_lock *lock, u32 seq, unsigned long ip)\340{ \341 return six_relock_ip(lock, SIX_LOCK_##type, seq, ip); \342} \343 \344static inline bool six_relock_##type(struct six_lock *lock, u32 seq) \345{ \346 return six_relock_ip(lock, SIX_LOCK_##type, seq, _THIS_IP_); \347} \348 \349static inline int six_lock_##type(struct six_lock *lock, \350 six_lock_should_sleep_fn fn, void *p)\351{ \352 return six_lock_ip_##type(lock, fn, p, _THIS_IP_); \353} \354 \355static inline void six_unlock_ip_##type(struct six_lock *lock, unsigned long ip) \356{ \357 six_unlock_ip(lock, SIX_LOCK_##type, ip); \358} \359 \360static inline void six_unlock_##type(struct six_lock *lock) \361{ \362 six_unlock_ip(lock, SIX_LOCK_##type, _THIS_IP_); \363}364 365__SIX_LOCK(read)366__SIX_LOCK(intent)367__SIX_LOCK(write)368#undef __SIX_LOCK369 370void six_lock_downgrade(struct six_lock *);371bool six_lock_tryupgrade(struct six_lock *);372bool six_trylock_convert(struct six_lock *, enum six_lock_type,373 enum six_lock_type);374 375void six_lock_increment(struct six_lock *, enum six_lock_type);376 377void six_lock_wakeup_all(struct six_lock *);378 379struct six_lock_count {380 unsigned n[3];381};382 383struct six_lock_count six_lock_counts(struct six_lock *);384void six_lock_readers_add(struct six_lock *, int);385 386#endif /* _LINUX_SIX_H */387