git.sesse.net Git - bcachefs-tools-debian/blob - linux/six.c

   1 // SPDX-License-Identifier: GPL-2.0
   2
   3 #include <linux/export.h>
   4 #include <linux/log2.h>
   5 #include <linux/preempt.h>
   6 #include <linux/rcupdate.h>
   7 #include <linux/sched.h>
   8 #include <linux/sched/rt.h>
   9 #include <linux/six.h>
  10
  11 #ifdef DEBUG
  12 #define EBUG_ON(cond)           BUG_ON(cond)
  13 #else
  14 #define EBUG_ON(cond)           do {} while (0)
  15 #endif
  16
  17 #define six_acquire(l, t)       lock_acquire(l, 0, t, 0, 0, NULL, _RET_IP_)
  18 #define six_release(l)          lock_release(l, _RET_IP_)
  19
  20 struct six_lock_vals {
  21         /* Value we add to the lock in order to take the lock: */
  22         u64                     lock_val;
  23
  24         /* If the lock has this value (used as a mask), taking the lock fails: */
  25         u64                     lock_fail;
  26
  27         /* Value we add to the lock in order to release the lock: */
  28         u64                     unlock_val;
  29
  30         /* Mask that indicates lock is held for this type: */
  31         u64                     held_mask;
  32
  33         /* Waitlist we wakeup when releasing the lock: */
  34         enum six_lock_type      unlock_wakeup;
  35 };
  36
  37 #define __SIX_LOCK_HELD_read    __SIX_VAL(read_lock, ~0)
  38 #define __SIX_LOCK_HELD_intent  __SIX_VAL(intent_lock, ~0)
  39 #define __SIX_LOCK_HELD_write   __SIX_VAL(seq, 1)
  40
  41 #define LOCK_VALS {                                                     \
  42         [SIX_LOCK_read] = {                                             \
  43                 .lock_val       = __SIX_VAL(read_lock, 1),              \
  44                 .lock_fail      = __SIX_LOCK_HELD_write,                \
  45                 .unlock_val     = -__SIX_VAL(read_lock, 1),             \
  46                 .held_mask      = __SIX_LOCK_HELD_read,                 \
  47                 .unlock_wakeup  = SIX_LOCK_write,                       \
  48         },                                                              \
  49         [SIX_LOCK_intent] = {                                           \
  50                 .lock_val       = __SIX_VAL(intent_lock, 1),            \
  51                 .lock_fail      = __SIX_LOCK_HELD_intent,               \
  52                 .unlock_val     = -__SIX_VAL(intent_lock, 1),           \
  53                 .held_mask      = __SIX_LOCK_HELD_intent,               \
  54                 .unlock_wakeup  = SIX_LOCK_intent,                      \
  55         },                                                              \
  56         [SIX_LOCK_write] = {                                            \
  57                 .lock_val       = __SIX_VAL(seq, 1),                    \
  58                 .lock_fail      = __SIX_LOCK_HELD_read,                 \
  59                 .unlock_val     = __SIX_VAL(seq, 1),                    \
  60                 .held_mask      = __SIX_LOCK_HELD_write,                \
  61                 .unlock_wakeup  = SIX_LOCK_read,                        \
  62         },                                                              \
  63 }
  64
  65 static inline void six_set_owner(struct six_lock *lock, enum six_lock_type type,
  66                                  union six_lock_state old)
  67 {
  68         if (type != SIX_LOCK_intent)
  69                 return;
  70
  71         if (!old.intent_lock) {
  72                 EBUG_ON(lock->owner);
  73                 lock->owner = current;
  74         } else {
  75                 EBUG_ON(lock->owner != current);
  76         }
  77 }
  78
  79 static __always_inline bool do_six_trylock_type(struct six_lock *lock,
  80                                                 enum six_lock_type type)
  81 {
  82         const struct six_lock_vals l[] = LOCK_VALS;
  83         union six_lock_state old;
  84         u64 v = READ_ONCE(lock->state.v);
  85
  86         EBUG_ON(type == SIX_LOCK_write && lock->owner != current);
  87
  88         do {
  89                 old.v = v;
  90
  91                 EBUG_ON(type == SIX_LOCK_write &&
  92                         ((old.v & __SIX_LOCK_HELD_write) ||
  93                          !(old.v & __SIX_LOCK_HELD_intent)));
  94
  95                 if (old.v & l[type].lock_fail)
  96                         return false;
  97         } while ((v = atomic64_cmpxchg_acquire(&lock->state.counter,
  98                                 old.v,
  99                                 old.v + l[type].lock_val)) != old.v);
 100
 101         six_set_owner(lock, type, old);
 102         return true;
 103 }
 104
 105 __always_inline __flatten
 106 static bool __six_trylock_type(struct six_lock *lock, enum six_lock_type type)
 107 {
 108         if (!do_six_trylock_type(lock, type))
 109                 return false;
 110
 111         if (type != SIX_LOCK_write)
 112                 six_acquire(&lock->dep_map, 1);
 113         return true;
 114 }
 115
 116 __always_inline __flatten
 117 static bool __six_relock_type(struct six_lock *lock, enum six_lock_type type,
 118                               unsigned seq)
 119 {
 120         const struct six_lock_vals l[] = LOCK_VALS;
 121         union six_lock_state old;
 122         u64 v = READ_ONCE(lock->state.v);
 123
 124         do {
 125                 old.v = v;
 126
 127                 if (old.seq != seq || old.v & l[type].lock_fail)
 128                         return false;
 129         } while ((v = atomic64_cmpxchg_acquire(&lock->state.counter,
 130                                 old.v,
 131                                 old.v + l[type].lock_val)) != old.v);
 132
 133         six_set_owner(lock, type, old);
 134         if (type != SIX_LOCK_write)
 135                 six_acquire(&lock->dep_map, 1);
 136         return true;
 137 }
 138
 139 struct six_lock_waiter {
 140         struct list_head        list;
 141         struct task_struct      *task;
 142 };
 143
 144 /* This is probably up there with the more evil things I've done */
 145 #define waitlist_bitnr(id) ilog2((((union six_lock_state) { .waiters = 1 << (id) }).l))
 146
 147 #ifdef CONFIG_LOCK_SPIN_ON_OWNER
 148
 149 static inline int six_can_spin_on_owner(struct six_lock *lock)
 150 {
 151         struct task_struct *owner;
 152         int retval = 1;
 153
 154         if (need_resched())
 155                 return 0;
 156
 157         rcu_read_lock();
 158         owner = READ_ONCE(lock->owner);
 159         if (owner)
 160                 retval = owner->on_cpu;
 161         rcu_read_unlock();
 162         /*
 163          * if lock->owner is not set, the mutex owner may have just acquired
 164          * it and not set the owner yet or the mutex has been released.
 165          */
 166         return retval;
 167 }
 168
 169 static inline bool six_spin_on_owner(struct six_lock *lock,
 170                                      struct task_struct *owner)
 171 {
 172         bool ret = true;
 173
 174         rcu_read_lock();
 175         while (lock->owner == owner) {
 176                 /*
 177                  * Ensure we emit the owner->on_cpu, dereference _after_
 178                  * checking lock->owner still matches owner. If that fails,
 179                  * owner might point to freed memory. If it still matches,
 180                  * the rcu_read_lock() ensures the memory stays valid.
 181                  */
 182                 barrier();
 183
 184                 if (!owner->on_cpu || need_resched()) {
 185                         ret = false;
 186                         break;
 187                 }
 188
 189                 cpu_relax();
 190         }
 191         rcu_read_unlock();
 192
 193         return ret;
 194 }
 195
 196 static inline bool six_optimistic_spin(struct six_lock *lock, enum six_lock_type type)
 197 {
 198         struct task_struct *task = current;
 199
 200         if (type == SIX_LOCK_write)
 201                 return false;
 202
 203         preempt_disable();
 204         if (!six_can_spin_on_owner(lock))
 205                 goto fail;
 206
 207         if (!osq_lock(&lock->osq))
 208                 goto fail;
 209
 210         while (1) {
 211                 struct task_struct *owner;
 212
 213                 /*
 214                  * If there's an owner, wait for it to either
 215                  * release the lock or go to sleep.
 216                  */
 217                 owner = READ_ONCE(lock->owner);
 218                 if (owner && !six_spin_on_owner(lock, owner))
 219                         break;
 220
 221                 if (do_six_trylock_type(lock, type)) {
 222                         osq_unlock(&lock->osq);
 223                         preempt_enable();
 224                         return true;
 225                 }
 226
 227                 /*
 228                  * When there's no owner, we might have preempted between the
 229                  * owner acquiring the lock and setting the owner field. If
 230                  * we're an RT task that will live-lock because we won't let
 231                  * the owner complete.
 232                  */
 233                 if (!owner && (need_resched() || rt_task(task)))
 234                         break;
 235
 236                 /*
 237                  * The cpu_relax() call is a compiler barrier which forces
 238                  * everything in this loop to be re-loaded. We don't need
 239                  * memory barriers as we'll eventually observe the right
 240                  * values at the cost of a few extra spins.
 241                  */
 242                 cpu_relax();
 243         }
 244
 245         osq_unlock(&lock->osq);
 246 fail:
 247         preempt_enable();
 248
 249         /*
 250          * If we fell out of the spin path because of need_resched(),
 251          * reschedule now, before we try-lock again. This avoids getting
 252          * scheduled out right after we obtained the lock.
 253          */
 254         if (need_resched())
 255                 schedule();
 256
 257         return false;
 258 }
 259
 260 #else /* CONFIG_LOCK_SPIN_ON_OWNER */
 261
 262 static inline bool six_optimistic_spin(struct six_lock *lock, enum six_lock_type type)
 263 {
 264         return false;
 265 }
 266
 267 #endif
 268
 269 noinline
 270 static void __six_lock_type_slowpath(struct six_lock *lock, enum six_lock_type type)
 271 {
 272         const struct six_lock_vals l[] = LOCK_VALS;
 273         union six_lock_state old, new;
 274         struct six_lock_waiter wait;
 275         u64 v;
 276
 277         if (six_optimistic_spin(lock, type))
 278                 return;
 279
 280         lock_contended(&lock->dep_map, _RET_IP_);
 281
 282         INIT_LIST_HEAD(&wait.list);
 283         wait.task = current;
 284
 285         while (1) {
 286                 set_current_state(TASK_UNINTERRUPTIBLE);
 287                 if (type == SIX_LOCK_write)
 288                         EBUG_ON(lock->owner != current);
 289                 else if (list_empty_careful(&wait.list)) {
 290                         raw_spin_lock(&lock->wait_lock);
 291                         list_add_tail(&wait.list, &lock->wait_list[type]);
 292                         raw_spin_unlock(&lock->wait_lock);
 293                 }
 294
 295                 v = READ_ONCE(lock->state.v);
 296                 do {
 297                         new.v = old.v = v;
 298
 299                         if (!(old.v & l[type].lock_fail))
 300                                 new.v += l[type].lock_val;
 301                         else if (!(new.waiters & (1 << type)))
 302                                 new.waiters |= 1 << type;
 303                         else
 304                                 break; /* waiting bit already set */
 305                 } while ((v = atomic64_cmpxchg_acquire(&lock->state.counter,
 306                                         old.v, new.v)) != old.v);
 307
 308                 if (!(old.v & l[type].lock_fail))
 309                         break;
 310
 311                 schedule();
 312         }
 313
 314         six_set_owner(lock, type, old);
 315
 316         __set_current_state(TASK_RUNNING);
 317
 318         if (!list_empty_careful(&wait.list)) {
 319                 raw_spin_lock(&lock->wait_lock);
 320                 list_del_init(&wait.list);
 321                 raw_spin_unlock(&lock->wait_lock);
 322         }
 323 }
 324
 325 __always_inline
 326 static void __six_lock_type(struct six_lock *lock, enum six_lock_type type)
 327 {
 328         if (type != SIX_LOCK_write)
 329                 six_acquire(&lock->dep_map, 0);
 330
 331         if (!do_six_trylock_type(lock, type))
 332                 __six_lock_type_slowpath(lock, type);
 333
 334         lock_acquired(&lock->dep_map, _RET_IP_);
 335 }
 336
 337 static inline void six_lock_wakeup(struct six_lock *lock,
 338                                    union six_lock_state state,
 339                                    unsigned waitlist_id)
 340 {
 341         struct list_head *wait_list = &lock->wait_list[waitlist_id];
 342         struct six_lock_waiter *w, *next;
 343
 344         if (waitlist_id == SIX_LOCK_write && state.read_lock)
 345                 return;
 346
 347         if (!(state.waiters & (1 << waitlist_id)))
 348                 return;
 349
 350         clear_bit(waitlist_bitnr(waitlist_id),
 351                   (unsigned long *) &lock->state.v);
 352
 353         if (waitlist_id == SIX_LOCK_write) {
 354                 struct task_struct *p = READ_ONCE(lock->owner);
 355
 356                 if (p)
 357                         wake_up_process(p);
 358                 return;
 359         }
 360
 361         raw_spin_lock(&lock->wait_lock);
 362
 363         list_for_each_entry_safe(w, next, wait_list, list) {
 364                 list_del_init(&w->list);
 365
 366                 if (wake_up_process(w->task) &&
 367                     waitlist_id != SIX_LOCK_read) {
 368                         if (!list_empty(wait_list))
 369                                 set_bit(waitlist_bitnr(waitlist_id),
 370                                         (unsigned long *) &lock->state.v);
 371                         break;
 372                 }
 373         }
 374
 375         raw_spin_unlock(&lock->wait_lock);
 376 }
 377
 378 __always_inline __flatten
 379 static void __six_unlock_type(struct six_lock *lock, enum six_lock_type type)
 380 {
 381         const struct six_lock_vals l[] = LOCK_VALS;
 382         union six_lock_state state;
 383
 384         EBUG_ON(!(lock->state.v & l[type].held_mask));
 385         EBUG_ON(type == SIX_LOCK_write &&
 386                 !(lock->state.v & __SIX_LOCK_HELD_intent));
 387
 388         if (type != SIX_LOCK_write)
 389                 six_release(&lock->dep_map);
 390
 391         if (type == SIX_LOCK_intent) {
 392                 EBUG_ON(lock->owner != current);
 393
 394                 if (lock->intent_lock_recurse) {
 395                         --lock->intent_lock_recurse;
 396                         return;
 397                 }
 398
 399                 lock->owner = NULL;
 400         }
 401
 402         state.v = atomic64_add_return_release(l[type].unlock_val,
 403                                               &lock->state.counter);
 404         six_lock_wakeup(lock, state, l[type].unlock_wakeup);
 405 }
 406
 407 #define __SIX_LOCK(type)                                                \
 408 bool six_trylock_##type(struct six_lock *lock)                          \
 409 {                                                                       \
 410         return __six_trylock_type(lock, SIX_LOCK_##type);               \
 411 }                                                                       \
 412 EXPORT_SYMBOL_GPL(six_trylock_##type);                                  \
 413                                                                         \
 414 bool six_relock_##type(struct six_lock *lock, u32 seq)                  \
 415 {                                                                       \
 416         return __six_relock_type(lock, SIX_LOCK_##type, seq);           \
 417 }                                                                       \
 418 EXPORT_SYMBOL_GPL(six_relock_##type);                                   \
 419                                                                         \
 420 void six_lock_##type(struct six_lock *lock)                             \
 421 {                                                                       \
 422         __six_lock_type(lock, SIX_LOCK_##type);                         \
 423 }                                                                       \
 424 EXPORT_SYMBOL_GPL(six_lock_##type);                                     \
 425                                                                         \
 426 void six_unlock_##type(struct six_lock *lock)                           \
 427 {                                                                       \
 428         __six_unlock_type(lock, SIX_LOCK_##type);                       \
 429 }                                                                       \
 430 EXPORT_SYMBOL_GPL(six_unlock_##type);
 431
 432 __SIX_LOCK(read)
 433 __SIX_LOCK(intent)
 434 __SIX_LOCK(write)
 435
 436 #undef __SIX_LOCK
 437
 438 /* Convert from intent to read: */
 439 void six_lock_downgrade(struct six_lock *lock)
 440 {
 441         six_lock_increment(lock, SIX_LOCK_read);
 442         six_unlock_intent(lock);
 443 }
 444 EXPORT_SYMBOL_GPL(six_lock_downgrade);
 445
 446 bool six_lock_tryupgrade(struct six_lock *lock)
 447 {
 448         const struct six_lock_vals l[] = LOCK_VALS;
 449         union six_lock_state old, new;
 450         u64 v = READ_ONCE(lock->state.v);
 451
 452         do {
 453                 new.v = old.v = v;
 454
 455                 EBUG_ON(!(old.v & l[SIX_LOCK_read].held_mask));
 456
 457                 new.v += l[SIX_LOCK_read].unlock_val;
 458
 459                 if (new.v & l[SIX_LOCK_intent].lock_fail)
 460                         return false;
 461
 462                 new.v += l[SIX_LOCK_intent].lock_val;
 463         } while ((v = atomic64_cmpxchg_acquire(&lock->state.counter,
 464                                 old.v, new.v)) != old.v);
 465
 466         six_set_owner(lock, SIX_LOCK_intent, old);
 467         six_lock_wakeup(lock, new, l[SIX_LOCK_read].unlock_wakeup);
 468
 469         return true;
 470 }
 471 EXPORT_SYMBOL_GPL(six_lock_tryupgrade);
 472
 473 bool six_trylock_convert(struct six_lock *lock,
 474                          enum six_lock_type from,
 475                          enum six_lock_type to)
 476 {
 477         EBUG_ON(to == SIX_LOCK_write || from == SIX_LOCK_write);
 478
 479         if (to == from)
 480                 return true;
 481
 482         if (to == SIX_LOCK_read) {
 483                 six_lock_downgrade(lock);
 484                 return true;
 485         } else {
 486                 return six_lock_tryupgrade(lock);
 487         }
 488 }
 489 EXPORT_SYMBOL_GPL(six_trylock_convert);
 490
 491 /*
 492  * Increment read/intent lock count, assuming we already have it read or intent
 493  * locked:
 494  */
 495 void six_lock_increment(struct six_lock *lock, enum six_lock_type type)
 496 {
 497         const struct six_lock_vals l[] = LOCK_VALS;
 498
 499         EBUG_ON(type == SIX_LOCK_write);
 500         six_acquire(&lock->dep_map, 0);
 501
 502         /* XXX: assert already locked, and that we don't overflow: */
 503
 504         switch (type) {
 505         case SIX_LOCK_read:
 506                 atomic64_add(l[type].lock_val, &lock->state.counter);
 507                 break;
 508         case SIX_LOCK_intent:
 509                 lock->intent_lock_recurse++;
 510                 break;
 511         case SIX_LOCK_write:
 512                 BUG();
 513                 break;
 514         }
 515 }
 516 EXPORT_SYMBOL_GPL(six_lock_increment);