kernel/locking/ww_mutex.h

   1 /* SPDX-License-Identifier: GPL-2.0-only */
   2
   3 #define MUTEX           mutex
   4 #define MUTEX_WAITER    mutex_waiter
   5
   6 static inline struct mutex_waiter *
   7 __ww_waiter_first(struct mutex *lock)
   8 {
   9         struct mutex_waiter *w;
  10
  11         w = list_first_entry(&lock->wait_list, struct mutex_waiter, list);
  12         if (list_entry_is_head(w, &lock->wait_list, list))
  13                 return NULL;
  14
  15         return w;
  16 }
  17
  18 static inline struct mutex_waiter *
  19 __ww_waiter_next(struct mutex *lock, struct mutex_waiter *w)
  20 {
  21         w = list_next_entry(w, list);
  22         if (list_entry_is_head(w, &lock->wait_list, list))
  23                 return NULL;
  24
  25         return w;
  26 }
  27
  28 static inline struct mutex_waiter *
  29 __ww_waiter_prev(struct mutex *lock, struct mutex_waiter *w)
  30 {
  31         w = list_prev_entry(w, list);
  32         if (list_entry_is_head(w, &lock->wait_list, list))
  33                 return NULL;
  34
  35         return w;
  36 }
  37
  38 static inline struct mutex_waiter *
  39 __ww_waiter_last(struct mutex *lock)
  40 {
  41         struct mutex_waiter *w;
  42
  43         w = list_last_entry(&lock->wait_list, struct mutex_waiter, list);
  44         if (list_entry_is_head(w, &lock->wait_list, list))
  45                 return NULL;
  46
  47         return w;
  48 }
  49
  50 static inline void
  51 __ww_waiter_add(struct mutex *lock, struct mutex_waiter *waiter, struct mutex_waiter *pos)
  52 {
  53         struct list_head *p = &lock->wait_list;
  54         if (pos)
  55                 p = &pos->list;
  56         __mutex_add_waiter(lock, waiter, p);
  57 }
  58
  59 static inline struct task_struct *
  60 __ww_mutex_owner(struct mutex *lock)
  61 {
  62         return __mutex_owner(lock);
  63 }
  64
  65 static inline bool
  66 __ww_mutex_has_waiters(struct mutex *lock)
  67 {
  68         return atomic_long_read(&lock->owner) & MUTEX_FLAG_WAITERS;
  69 }
  70
  71 /*
  72  * Wait-Die:
  73  *   The newer transactions are killed when:
  74  *     It (the new transaction) makes a request for a lock being held
  75  *     by an older transaction.
  76  *
  77  * Wound-Wait:
  78  *   The newer transactions are wounded when:
  79  *     An older transaction makes a request for a lock being held by
  80  *     the newer transaction.
  81  */
  82
  83 /*
  84  * Associate the ww_mutex @ww with the context @ww_ctx under which we acquired
  85  * it.
  86  */
  87 static __always_inline void
  88 ww_mutex_lock_acquired(struct ww_mutex *ww, struct ww_acquire_ctx *ww_ctx)
  89 {
  90 #ifdef CONFIG_DEBUG_MUTEXES
  91         /*
  92          * If this WARN_ON triggers, you used ww_mutex_lock to acquire,
  93          * but released with a normal mutex_unlock in this call.
  94          *
  95          * This should never happen, always use ww_mutex_unlock.
  96          */
  97         DEBUG_LOCKS_WARN_ON(ww->ctx);
  98
  99         /*
 100          * Not quite done after calling ww_acquire_done() ?
 101          */
 102         DEBUG_LOCKS_WARN_ON(ww_ctx->done_acquire);
 103
 104         if (ww_ctx->contending_lock) {
 105                 /*
 106                  * After -EDEADLK you tried to
 107                  * acquire a different ww_mutex? Bad!
 108                  */
 109                 DEBUG_LOCKS_WARN_ON(ww_ctx->contending_lock != ww);
 110
 111                 /*
 112                  * You called ww_mutex_lock after receiving -EDEADLK,
 113                  * but 'forgot' to unlock everything else first?
 114                  */
 115                 DEBUG_LOCKS_WARN_ON(ww_ctx->acquired > 0);
 116                 ww_ctx->contending_lock = NULL;
 117         }
 118
 119         /*
 120          * Naughty, using a different class will lead to undefined behavior!
 121          */
 122         DEBUG_LOCKS_WARN_ON(ww_ctx->ww_class != ww->ww_class);
 123 #endif
 124         ww_ctx->acquired++;
 125         ww->ctx = ww_ctx;
 126 }
 127
 128 /*
 129  * Determine if context @a is 'after' context @b. IOW, @a is a younger
 130  * transaction than @b and depending on algorithm either needs to wait for
 131  * @b or die.
 132  */
 133 static inline bool
 134 __ww_ctx_stamp_after(struct ww_acquire_ctx *a, struct ww_acquire_ctx *b)
 135 {
 136
 137         return (signed long)(a->stamp - b->stamp) > 0;
 138 }
 139
 140 /*
 141  * Wait-Die; wake a younger waiter context (when locks held) such that it can
 142  * die.
 143  *
 144  * Among waiters with context, only the first one can have other locks acquired
 145  * already (ctx->acquired > 0), because __ww_mutex_add_waiter() and
 146  * __ww_mutex_check_kill() wake any but the earliest context.
 147  */
 148 static bool
 149 __ww_mutex_die(struct MUTEX *lock, struct MUTEX_WAITER *waiter,
 150                struct ww_acquire_ctx *ww_ctx)
 151 {
 152         if (!ww_ctx->is_wait_die)
 153                 return false;
 154
 155         if (waiter->ww_ctx->acquired > 0 &&
 156                         __ww_ctx_stamp_after(waiter->ww_ctx, ww_ctx)) {
 157                 debug_mutex_wake_waiter(lock, waiter);
 158                 wake_up_process(waiter->task);
 159         }
 160
 161         return true;
 162 }
 163
 164 /*
 165  * Wound-Wait; wound a younger @hold_ctx if it holds the lock.
 166  *
 167  * Wound the lock holder if there are waiters with older transactions than
 168  * the lock holders. Even if multiple waiters may wound the lock holder,
 169  * it's sufficient that only one does.
 170  */
 171 static bool __ww_mutex_wound(struct MUTEX *lock,
 172                              struct ww_acquire_ctx *ww_ctx,
 173                              struct ww_acquire_ctx *hold_ctx)
 174 {
 175         struct task_struct *owner = __ww_mutex_owner(lock);
 176
 177         lockdep_assert_held(&lock->wait_lock);
 178
 179         /*
 180          * Possible through __ww_mutex_add_waiter() when we race with
 181          * ww_mutex_set_context_fastpath(). In that case we'll get here again
 182          * through __ww_mutex_check_waiters().
 183          */
 184         if (!hold_ctx)
 185                 return false;
 186
 187         /*
 188          * Can have !owner because of __mutex_unlock_slowpath(), but if owner,
 189          * it cannot go away because we'll have FLAG_WAITERS set and hold
 190          * wait_lock.
 191          */
 192         if (!owner)
 193                 return false;
 194
 195         if (ww_ctx->acquired > 0 && __ww_ctx_stamp_after(hold_ctx, ww_ctx)) {
 196                 hold_ctx->wounded = 1;
 197
 198                 /*
 199                  * wake_up_process() paired with set_current_state()
 200                  * inserts sufficient barriers to make sure @owner either sees
 201                  * it's wounded in __ww_mutex_check_kill() or has a
 202                  * wakeup pending to re-read the wounded state.
 203                  */
 204                 if (owner != current)
 205                         wake_up_process(owner);
 206
 207                 return true;
 208         }
 209
 210         return false;
 211 }
 212
 213 /*
 214  * We just acquired @lock under @ww_ctx, if there are later contexts waiting
 215  * behind us on the wait-list, check if they need to die, or wound us.
 216  *
 217  * See __ww_mutex_add_waiter() for the list-order construction; basically the
 218  * list is ordered by stamp, smallest (oldest) first.
 219  *
 220  * This relies on never mixing wait-die/wound-wait on the same wait-list;
 221  * which is currently ensured by that being a ww_class property.
 222  *
 223  * The current task must not be on the wait list.
 224  */
 225 static void
 226 __ww_mutex_check_waiters(struct MUTEX *lock, struct ww_acquire_ctx *ww_ctx)
 227 {
 228         struct MUTEX_WAITER *cur;
 229
 230         lockdep_assert_held(&lock->wait_lock);
 231
 232         for (cur = __ww_waiter_first(lock); cur;
 233              cur = __ww_waiter_next(lock, cur)) {
 234
 235                 if (!cur->ww_ctx)
 236                         continue;
 237
 238                 if (__ww_mutex_die(lock, cur, ww_ctx) ||
 239                     __ww_mutex_wound(lock, cur->ww_ctx, ww_ctx))
 240                         break;
 241         }
 242 }
 243
 244 /*
 245  * After acquiring lock with fastpath, where we do not hold wait_lock, set ctx
 246  * and wake up any waiters so they can recheck.
 247  */
 248 static __always_inline void
 249 ww_mutex_set_context_fastpath(struct ww_mutex *lock, struct ww_acquire_ctx *ctx)
 250 {
 251         ww_mutex_lock_acquired(lock, ctx);
 252
 253         /*
 254          * The lock->ctx update should be visible on all cores before
 255          * the WAITERS check is done, otherwise contended waiters might be
 256          * missed. The contended waiters will either see ww_ctx == NULL
 257          * and keep spinning, or it will acquire wait_lock, add itself
 258          * to waiter list and sleep.
 259          */
 260         smp_mb(); /* See comments above and below. */
 261
 262         /*
 263          * [W] ww->ctx = ctx        [W] MUTEX_FLAG_WAITERS
 264          *     MB                       MB
 265          * [R] MUTEX_FLAG_WAITERS   [R] ww->ctx
 266          *
 267          * The memory barrier above pairs with the memory barrier in
 268          * __ww_mutex_add_waiter() and makes sure we either observe ww->ctx
 269          * and/or !empty list.
 270          */
 271         if (likely(!__ww_mutex_has_waiters(&lock->base)))
 272                 return;
 273
 274         /*
 275          * Uh oh, we raced in fastpath, check if any of the waiters need to
 276          * die or wound us.
 277          */
 278         raw_spin_lock(&lock->base.wait_lock);
 279         __ww_mutex_check_waiters(&lock->base, ctx);
 280         raw_spin_unlock(&lock->base.wait_lock);
 281 }
 282
 283 static __always_inline int
 284 __ww_mutex_kill(struct MUTEX *lock, struct ww_acquire_ctx *ww_ctx)
 285 {
 286         if (ww_ctx->acquired > 0) {
 287 #ifdef CONFIG_DEBUG_MUTEXES
 288                 struct ww_mutex *ww;
 289
 290                 ww = container_of(lock, struct ww_mutex, base);
 291                 DEBUG_LOCKS_WARN_ON(ww_ctx->contending_lock);
 292                 ww_ctx->contending_lock = ww;
 293 #endif
 294                 return -EDEADLK;
 295         }
 296
 297         return 0;
 298 }
 299
 300 /*
 301  * Check the wound condition for the current lock acquire.
 302  *
 303  * Wound-Wait: If we're wounded, kill ourself.
 304  *
 305  * Wait-Die: If we're trying to acquire a lock already held by an older
 306  *           context, kill ourselves.
 307  *
 308  * Since __ww_mutex_add_waiter() orders the wait-list on stamp, we only have to
 309  * look at waiters before us in the wait-list.
 310  */
 311 static inline int
 312 __ww_mutex_check_kill(struct MUTEX *lock, struct MUTEX_WAITER *waiter,
 313                       struct ww_acquire_ctx *ctx)
 314 {
 315         struct ww_mutex *ww = container_of(lock, struct ww_mutex, base);
 316         struct ww_acquire_ctx *hold_ctx = READ_ONCE(ww->ctx);
 317         struct MUTEX_WAITER *cur;
 318
 319         if (ctx->acquired == 0)
 320                 return 0;
 321
 322         if (!ctx->is_wait_die) {
 323                 if (ctx->wounded)
 324                         return __ww_mutex_kill(lock, ctx);
 325
 326                 return 0;
 327         }
 328
 329         if (hold_ctx && __ww_ctx_stamp_after(ctx, hold_ctx))
 330                 return __ww_mutex_kill(lock, ctx);
 331
 332         /*
 333          * If there is a waiter in front of us that has a context, then its
 334          * stamp is earlier than ours and we must kill ourself.
 335          */
 336         for (cur = __ww_waiter_prev(lock, waiter); cur;
 337              cur = __ww_waiter_prev(lock, cur)) {
 338
 339                 if (!cur->ww_ctx)
 340                         continue;
 341
 342                 return __ww_mutex_kill(lock, ctx);
 343         }
 344
 345         return 0;
 346 }
 347
 348 /*
 349  * Add @waiter to the wait-list, keep the wait-list ordered by stamp, smallest
 350  * first. Such that older contexts are preferred to acquire the lock over
 351  * younger contexts.
 352  *
 353  * Waiters without context are interspersed in FIFO order.
 354  *
 355  * Furthermore, for Wait-Die kill ourself immediately when possible (there are
 356  * older contexts already waiting) to avoid unnecessary waiting and for
 357  * Wound-Wait ensure we wound the owning context when it is younger.
 358  */
 359 static inline int
 360 __ww_mutex_add_waiter(struct MUTEX_WAITER *waiter,
 361                       struct MUTEX *lock,
 362                       struct ww_acquire_ctx *ww_ctx)
 363 {
 364         struct MUTEX_WAITER *cur, *pos = NULL;
 365         bool is_wait_die;
 366
 367         if (!ww_ctx) {
 368                 __ww_waiter_add(lock, waiter, NULL);
 369                 return 0;
 370         }
 371
 372         is_wait_die = ww_ctx->is_wait_die;
 373
 374         /*
 375          * Add the waiter before the first waiter with a higher stamp.
 376          * Waiters without a context are skipped to avoid starving
 377          * them. Wait-Die waiters may die here. Wound-Wait waiters
 378          * never die here, but they are sorted in stamp order and
 379          * may wound the lock holder.
 380          */
 381         for (cur = __ww_waiter_last(lock); cur;
 382              cur = __ww_waiter_prev(lock, cur)) {
 383
 384                 if (!cur->ww_ctx)
 385                         continue;
 386
 387                 if (__ww_ctx_stamp_after(ww_ctx, cur->ww_ctx)) {
 388                         /*
 389                          * Wait-Die: if we find an older context waiting, there
 390                          * is no point in queueing behind it, as we'd have to
 391                          * die the moment it would acquire the lock.
 392                          */
 393                         if (is_wait_die) {
 394                                 int ret = __ww_mutex_kill(lock, ww_ctx);
 395
 396                                 if (ret)
 397                                         return ret;
 398                         }
 399
 400                         break;
 401                 }
 402
 403                 pos = cur;
 404
 405                 /* Wait-Die: ensure younger waiters die. */
 406                 __ww_mutex_die(lock, cur, ww_ctx);
 407         }
 408
 409         __ww_waiter_add(lock, waiter, pos);
 410
 411         /*
 412          * Wound-Wait: if we're blocking on a mutex owned by a younger context,
 413          * wound that such that we might proceed.
 414          */
 415         if (!is_wait_die) {
 416                 struct ww_mutex *ww = container_of(lock, struct ww_mutex, base);
 417
 418                 /*
 419                  * See ww_mutex_set_context_fastpath(). Orders setting
 420                  * MUTEX_FLAG_WAITERS vs the ww->ctx load,
 421                  * such that either we or the fastpath will wound @ww->ctx.
 422                  */
 423                 smp_mb();
 424                 __ww_mutex_wound(lock, ww_ctx, ww->ctx);
 425         }
 426
 427         return 0;
 428 }
 429
 430 static inline void __ww_mutex_unlock(struct ww_mutex *lock)
 431 {
 432         if (lock->ctx) {
 433 #ifdef CONFIG_DEBUG_MUTEXES
 434                 DEBUG_LOCKS_WARN_ON(!lock->ctx->acquired);
 435 #endif
 436                 if (lock->ctx->acquired > 0)
 437                         lock->ctx->acquired--;
 438                 lock->ctx = NULL;
 439         }
 440 }