fs/bcachefs/six.h

   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 */