fs/bcachefs/six.c

   1 // SPDX-License-Identifier: GPL-2.0
   2
   3 #include <linux/export.h>
   4 #include <linux/log2.h>
   5 #include <linux/percpu.h>
   6 #include <linux/preempt.h>
   7 #include <linux/rcupdate.h>
   8 #include <linux/sched.h>
   9 #include <linux/sched/clock.h>
  10 #include <linux/sched/rt.h>
  11 #include <linux/sched/task.h>
  12 #include <linux/slab.h>
  13
  14 #include <trace/events/lock.h>
  15
  16 #include "six.h"
  17
  18 #ifdef DEBUG
  19 #define EBUG_ON(cond)                   BUG_ON(cond)
  20 #else
  21 #define EBUG_ON(cond)                   do {} while (0)
  22 #endif
  23
  24 #define six_acquire(l, t, r, ip)        lock_acquire(l, 0, t, r, 1, NULL, ip)
  25 #define six_release(l, ip)              lock_release(l, ip)
  26
  27 static void do_six_unlock_type(struct six_lock *lock, enum six_lock_type type);
  28
  29 #define SIX_LOCK_HELD_read_OFFSET       0
  30 #define SIX_LOCK_HELD_read              ~(~0U << 26)
  31 #define SIX_LOCK_HELD_intent            (1U << 26)
  32 #define SIX_LOCK_HELD_write             (1U << 27)
  33 #define SIX_LOCK_WAITING_read           (1U << (28 + SIX_LOCK_read))
  34 #define SIX_LOCK_WAITING_write          (1U << (28 + SIX_LOCK_write))
  35 #define SIX_LOCK_NOSPIN                 (1U << 31)
  36
  37 struct six_lock_vals {
  38         /* Value we add to the lock in order to take the lock: */
  39         u32                     lock_val;
  40
  41         /* If the lock has this value (used as a mask), taking the lock fails: */
  42         u32                     lock_fail;
  43
  44         /* Mask that indicates lock is held for this type: */
  45         u32                     held_mask;
  46
  47         /* Waitlist we wakeup when releasing the lock: */
  48         enum six_lock_type      unlock_wakeup;
  49 };
  50
  51 static const struct six_lock_vals l[] = {
  52         [SIX_LOCK_read] = {
  53                 .lock_val       = 1U << SIX_LOCK_HELD_read_OFFSET,
  54                 .lock_fail      = SIX_LOCK_HELD_write,
  55                 .held_mask      = SIX_LOCK_HELD_read,
  56                 .unlock_wakeup  = SIX_LOCK_write,
  57         },
  58         [SIX_LOCK_intent] = {
  59                 .lock_val       = SIX_LOCK_HELD_intent,
  60                 .lock_fail      = SIX_LOCK_HELD_intent,
  61                 .held_mask      = SIX_LOCK_HELD_intent,
  62                 .unlock_wakeup  = SIX_LOCK_intent,
  63         },
  64         [SIX_LOCK_write] = {
  65                 .lock_val       = SIX_LOCK_HELD_write,
  66                 .lock_fail      = SIX_LOCK_HELD_read,
  67                 .held_mask      = SIX_LOCK_HELD_write,
  68                 .unlock_wakeup  = SIX_LOCK_read,
  69         },
  70 };
  71
  72 static inline void six_set_bitmask(struct six_lock *lock, u32 mask)
  73 {
  74         if ((atomic_read(&lock->state) & mask) != mask)
  75                 atomic_or(mask, &lock->state);
  76 }
  77
  78 static inline void six_clear_bitmask(struct six_lock *lock, u32 mask)
  79 {
  80         if (atomic_read(&lock->state) & mask)
  81                 atomic_and(~mask, &lock->state);
  82 }
  83
  84 static inline void six_set_owner(struct six_lock *lock, enum six_lock_type type,
  85                                  u32 old, struct task_struct *owner)
  86 {
  87         if (type != SIX_LOCK_intent)
  88                 return;
  89
  90         if (!(old & SIX_LOCK_HELD_intent)) {
  91                 EBUG_ON(lock->owner);
  92                 lock->owner = owner;
  93         } else {
  94                 EBUG_ON(lock->owner != current);
  95         }
  96 }
  97
  98 static inline unsigned pcpu_read_count(struct six_lock *lock)
  99 {
 100         unsigned read_count = 0;
 101         int cpu;
 102
 103         for_each_possible_cpu(cpu)
 104                 read_count += *per_cpu_ptr(lock->readers, cpu);
 105         return read_count;
 106 }
 107
 108 /*
 109  * __do_six_trylock() - main trylock routine
 110  *
 111  * Returns 1 on success, 0 on failure
 112  *
 113  * In percpu reader mode, a failed trylock may cause a spurious trylock failure
 114  * for anoter thread taking the competing lock type, and we may havve to do a
 115  * wakeup: when a wakeup is required, we return -1 - wakeup_type.
 116  */
 117 static int __do_six_trylock(struct six_lock *lock, enum six_lock_type type,
 118                             struct task_struct *task, bool try)
 119 {
 120         int ret;
 121         u32 old;
 122
 123         EBUG_ON(type == SIX_LOCK_write && lock->owner != task);
 124         EBUG_ON(type == SIX_LOCK_write &&
 125                 (try != !(atomic_read(&lock->state) & SIX_LOCK_HELD_write)));
 126
 127         /*
 128          * Percpu reader mode:
 129          *
 130          * The basic idea behind this algorithm is that you can implement a lock
 131          * between two threads without any atomics, just memory barriers:
 132          *
 133          * For two threads you'll need two variables, one variable for "thread a
 134          * has the lock" and another for "thread b has the lock".
 135          *
 136          * To take the lock, a thread sets its variable indicating that it holds
 137          * the lock, then issues a full memory barrier, then reads from the
 138          * other thread's variable to check if the other thread thinks it has
 139          * the lock. If we raced, we backoff and retry/sleep.
 140          *
 141          * Failure to take the lock may cause a spurious trylock failure in
 142          * another thread, because we temporarily set the lock to indicate that
 143          * we held it. This would be a problem for a thread in six_lock(), when
 144          * they are calling trylock after adding themself to the waitlist and
 145          * prior to sleeping.
 146          *
 147          * Therefore, if we fail to get the lock, and there were waiters of the
 148          * type we conflict with, we will have to issue a wakeup.
 149          *
 150          * Since we may be called under wait_lock (and by the wakeup code
 151          * itself), we return that the wakeup has to be done instead of doing it
 152          * here.
 153          */
 154         if (type == SIX_LOCK_read && lock->readers) {
 155                 preempt_disable();
 156                 this_cpu_inc(*lock->readers); /* signal that we own lock */
 157
 158                 smp_mb();
 159
 160                 old = atomic_read(&lock->state);
 161                 ret = !(old & l[type].lock_fail);
 162
 163                 this_cpu_sub(*lock->readers, !ret);
 164                 preempt_enable();
 165
 166                 if (!ret && (old & SIX_LOCK_WAITING_write))
 167                         ret = -1 - SIX_LOCK_write;
 168         } else if (type == SIX_LOCK_write && lock->readers) {
 169                 if (try) {
 170                         atomic_add(SIX_LOCK_HELD_write, &lock->state);
 171                         smp_mb__after_atomic();
 172                 }
 173
 174                 ret = !pcpu_read_count(lock);
 175
 176                 if (try && !ret) {
 177                         old = atomic_sub_return(SIX_LOCK_HELD_write, &lock->state);
 178                         if (old & SIX_LOCK_WAITING_read)
 179                                 ret = -1 - SIX_LOCK_read;
 180                 }
 181         } else {
 182                 old = atomic_read(&lock->state);
 183                 do {
 184                         ret = !(old & l[type].lock_fail);
 185                         if (!ret || (type == SIX_LOCK_write && !try)) {
 186                                 smp_mb();
 187                                 break;
 188                         }
 189                 } while (!atomic_try_cmpxchg_acquire(&lock->state, &old, old + l[type].lock_val));
 190
 191                 EBUG_ON(ret && !(atomic_read(&lock->state) & l[type].held_mask));
 192         }
 193
 194         if (ret > 0)
 195                 six_set_owner(lock, type, old, task);
 196
 197         EBUG_ON(type == SIX_LOCK_write && try && ret <= 0 &&
 198                 (atomic_read(&lock->state) & SIX_LOCK_HELD_write));
 199
 200         return ret;
 201 }
 202
 203 static void __six_lock_wakeup(struct six_lock *lock, enum six_lock_type lock_type)
 204 {
 205         struct six_lock_waiter *w, *next;
 206         struct task_struct *task;
 207         bool saw_one;
 208         int ret;
 209 again:
 210         ret = 0;
 211         saw_one = false;
 212         raw_spin_lock(&lock->wait_lock);
 213
 214         list_for_each_entry_safe(w, next, &lock->wait_list, list) {
 215                 if (w->lock_want != lock_type)
 216                         continue;
 217
 218                 if (saw_one && lock_type != SIX_LOCK_read)
 219                         goto unlock;
 220                 saw_one = true;
 221
 222                 ret = __do_six_trylock(lock, lock_type, w->task, false);
 223                 if (ret <= 0)
 224                         goto unlock;
 225
 226                 /*
 227                  * Similar to percpu_rwsem_wake_function(), we need to guard
 228                  * against the wakee noticing w->lock_acquired, returning, and
 229                  * then exiting before we do the wakeup:
 230                  */
 231                 task = get_task_struct(w->task);
 232                 __list_del(w->list.prev, w->list.next);
 233                 /*
 234                  * The release barrier here ensures the ordering of the
 235                  * __list_del before setting w->lock_acquired; @w is on the
 236                  * stack of the thread doing the waiting and will be reused
 237                  * after it sees w->lock_acquired with no other locking:
 238                  * pairs with smp_load_acquire() in six_lock_slowpath()
 239                  */
 240                 smp_store_release(&w->lock_acquired, true);
 241                 wake_up_process(task);
 242                 put_task_struct(task);
 243         }
 244
 245         six_clear_bitmask(lock, SIX_LOCK_WAITING_read << lock_type);
 246 unlock:
 247         raw_spin_unlock(&lock->wait_lock);
 248
 249         if (ret < 0) {
 250                 lock_type = -ret - 1;
 251                 goto again;
 252         }
 253 }
 254
 255 __always_inline
 256 static void six_lock_wakeup(struct six_lock *lock, u32 state,
 257                             enum six_lock_type lock_type)
 258 {
 259         if (lock_type == SIX_LOCK_write && (state & SIX_LOCK_HELD_read))
 260                 return;
 261
 262         if (!(state & (SIX_LOCK_WAITING_read << lock_type)))
 263                 return;
 264
 265         __six_lock_wakeup(lock, lock_type);
 266 }
 267
 268 __always_inline
 269 static bool do_six_trylock(struct six_lock *lock, enum six_lock_type type, bool try)
 270 {
 271         int ret;
 272
 273         ret = __do_six_trylock(lock, type, current, try);
 274         if (ret < 0)
 275                 __six_lock_wakeup(lock, -ret - 1);
 276
 277         return ret > 0;
 278 }
 279
 280 /**
 281  * six_trylock_ip - attempt to take a six lock without blocking
 282  * @lock:       lock to take
 283  * @type:       SIX_LOCK_read, SIX_LOCK_intent, or SIX_LOCK_write
 284  * @ip:         ip parameter for lockdep/lockstat, i.e. _THIS_IP_
 285  *
 286  * Return: true on success, false on failure.
 287  */
 288 bool six_trylock_ip(struct six_lock *lock, enum six_lock_type type, unsigned long ip)
 289 {
 290         if (!do_six_trylock(lock, type, true))
 291                 return false;
 292
 293         if (type != SIX_LOCK_write)
 294                 six_acquire(&lock->dep_map, 1, type == SIX_LOCK_read, ip);
 295         return true;
 296 }
 297 EXPORT_SYMBOL_GPL(six_trylock_ip);
 298
 299 /**
 300  * six_relock_ip - attempt to re-take a lock that was held previously
 301  * @lock:       lock to take
 302  * @type:       SIX_LOCK_read, SIX_LOCK_intent, or SIX_LOCK_write
 303  * @seq:        lock sequence number obtained from six_lock_seq() while lock was
 304  *              held previously
 305  * @ip:         ip parameter for lockdep/lockstat, i.e. _THIS_IP_
 306  *
 307  * Return: true on success, false on failure.
 308  */
 309 bool six_relock_ip(struct six_lock *lock, enum six_lock_type type,
 310                    unsigned seq, unsigned long ip)
 311 {
 312         if (six_lock_seq(lock) != seq || !six_trylock_ip(lock, type, ip))
 313                 return false;
 314
 315         if (six_lock_seq(lock) != seq) {
 316                 six_unlock_ip(lock, type, ip);
 317                 return false;
 318         }
 319
 320         return true;
 321 }
 322 EXPORT_SYMBOL_GPL(six_relock_ip);
 323
 324 #ifdef CONFIG_SIX_LOCK_SPIN_ON_OWNER
 325
 326 static inline bool six_can_spin_on_owner(struct six_lock *lock)
 327 {
 328         struct task_struct *owner;
 329         bool ret;
 330
 331         if (need_resched())
 332                 return false;
 333
 334         rcu_read_lock();
 335         owner = READ_ONCE(lock->owner);
 336         ret = !owner || owner_on_cpu(owner);
 337         rcu_read_unlock();
 338
 339         return ret;
 340 }
 341
 342 static inline bool six_spin_on_owner(struct six_lock *lock,
 343                                      struct task_struct *owner,
 344                                      u64 end_time)
 345 {
 346         bool ret = true;
 347         unsigned loop = 0;
 348
 349         rcu_read_lock();
 350         while (lock->owner == owner) {
 351                 /*
 352                  * Ensure we emit the owner->on_cpu, dereference _after_
 353                  * checking lock->owner still matches owner. If that fails,
 354                  * owner might point to freed memory. If it still matches,
 355                  * the rcu_read_lock() ensures the memory stays valid.
 356                  */
 357                 barrier();
 358
 359                 if (!owner_on_cpu(owner) || need_resched()) {
 360                         ret = false;
 361                         break;
 362                 }
 363
 364                 if (!(++loop & 0xf) && (time_after64(sched_clock(), end_time))) {
 365                         six_set_bitmask(lock, SIX_LOCK_NOSPIN);
 366                         ret = false;
 367                         break;
 368                 }
 369
 370                 cpu_relax();
 371         }
 372         rcu_read_unlock();
 373
 374         return ret;
 375 }
 376
 377 static inline bool six_optimistic_spin(struct six_lock *lock, enum six_lock_type type)
 378 {
 379         struct task_struct *task = current;
 380         u64 end_time;
 381
 382         if (type == SIX_LOCK_write)
 383                 return false;
 384
 385         preempt_disable();
 386         if (!six_can_spin_on_owner(lock))
 387                 goto fail;
 388
 389         if (!osq_lock(&lock->osq))
 390                 goto fail;
 391
 392         end_time = sched_clock() + 10 * NSEC_PER_USEC;
 393
 394         while (1) {
 395                 struct task_struct *owner;
 396
 397                 /*
 398                  * If there's an owner, wait for it to either
 399                  * release the lock or go to sleep.
 400                  */
 401                 owner = READ_ONCE(lock->owner);
 402                 if (owner && !six_spin_on_owner(lock, owner, end_time))
 403                         break;
 404
 405                 if (do_six_trylock(lock, type, false)) {
 406                         osq_unlock(&lock->osq);
 407                         preempt_enable();
 408                         return true;
 409                 }
 410
 411                 /*
 412                  * When there's no owner, we might have preempted between the
 413                  * owner acquiring the lock and setting the owner field. If
 414                  * we're an RT task that will live-lock because we won't let
 415                  * the owner complete.
 416                  */
 417                 if (!owner && (need_resched() || rt_task(task)))
 418                         break;
 419
 420                 /*
 421                  * The cpu_relax() call is a compiler barrier which forces
 422                  * everything in this loop to be re-loaded. We don't need
 423                  * memory barriers as we'll eventually observe the right
 424                  * values at the cost of a few extra spins.
 425                  */
 426                 cpu_relax();
 427         }
 428
 429         osq_unlock(&lock->osq);
 430 fail:
 431         preempt_enable();
 432
 433         /*
 434          * If we fell out of the spin path because of need_resched(),
 435          * reschedule now, before we try-lock again. This avoids getting
 436          * scheduled out right after we obtained the lock.
 437          */
 438         if (need_resched())
 439                 schedule();
 440
 441         return false;
 442 }
 443
 444 #else /* CONFIG_SIX_LOCK_SPIN_ON_OWNER */
 445
 446 static inline bool six_optimistic_spin(struct six_lock *lock, enum six_lock_type type)
 447 {
 448         return false;
 449 }
 450
 451 #endif
 452
 453 noinline
 454 static int six_lock_slowpath(struct six_lock *lock, enum six_lock_type type,
 455                              struct six_lock_waiter *wait,
 456                              six_lock_should_sleep_fn should_sleep_fn, void *p,
 457                              unsigned long ip)
 458 {
 459         int ret = 0;
 460
 461         if (type == SIX_LOCK_write) {
 462                 EBUG_ON(atomic_read(&lock->state) & SIX_LOCK_HELD_write);
 463                 atomic_add(SIX_LOCK_HELD_write, &lock->state);
 464                 smp_mb__after_atomic();
 465         }
 466
 467         trace_contention_begin(lock, 0);
 468         lock_contended(&lock->dep_map, ip);
 469
 470         if (six_optimistic_spin(lock, type))
 471                 goto out;
 472
 473         wait->task              = current;
 474         wait->lock_want         = type;
 475         wait->lock_acquired     = false;
 476
 477         raw_spin_lock(&lock->wait_lock);
 478         six_set_bitmask(lock, SIX_LOCK_WAITING_read << type);
 479         /*
 480          * Retry taking the lock after taking waitlist lock, in case we raced
 481          * with an unlock:
 482          */
 483         ret = __do_six_trylock(lock, type, current, false);
 484         if (ret <= 0) {
 485                 wait->start_time = local_clock();
 486
 487                 if (!list_empty(&lock->wait_list)) {
 488                         struct six_lock_waiter *last =
 489                                 list_last_entry(&lock->wait_list,
 490                                         struct six_lock_waiter, list);
 491
 492                         if (time_before_eq64(wait->start_time, last->start_time))
 493                                 wait->start_time = last->start_time + 1;
 494                 }
 495
 496                 list_add_tail(&wait->list, &lock->wait_list);
 497         }
 498         raw_spin_unlock(&lock->wait_lock);
 499
 500         if (unlikely(ret > 0)) {
 501                 ret = 0;
 502                 goto out;
 503         }
 504
 505         if (unlikely(ret < 0)) {
 506                 __six_lock_wakeup(lock, -ret - 1);
 507                 ret = 0;
 508         }
 509
 510         while (1) {
 511                 set_current_state(TASK_UNINTERRUPTIBLE);
 512
 513                 /*
 514                  * Ensures that writes to the waitlist entry happen after we see
 515                  * wait->lock_acquired: pairs with the smp_store_release in
 516                  * __six_lock_wakeup
 517                  */
 518                 if (smp_load_acquire(&wait->lock_acquired))
 519                         break;
 520
 521                 ret = should_sleep_fn ? should_sleep_fn(lock, p) : 0;
 522                 if (unlikely(ret)) {
 523                         bool acquired;
 524
 525                         /*
 526                          * If should_sleep_fn() returns an error, we are
 527                          * required to return that error even if we already
 528                          * acquired the lock - should_sleep_fn() might have
 529                          * modified external state (e.g. when the deadlock cycle
 530                          * detector in bcachefs issued a transaction restart)
 531                          */
 532                         raw_spin_lock(&lock->wait_lock);
 533                         acquired = wait->lock_acquired;
 534                         if (!acquired)
 535                                 list_del(&wait->list);
 536                         raw_spin_unlock(&lock->wait_lock);
 537
 538                         if (unlikely(acquired))
 539                                 do_six_unlock_type(lock, type);
 540                         break;
 541                 }
 542
 543                 schedule();
 544         }
 545
 546         __set_current_state(TASK_RUNNING);
 547 out:
 548         if (ret && type == SIX_LOCK_write) {
 549                 six_clear_bitmask(lock, SIX_LOCK_HELD_write);
 550                 six_lock_wakeup(lock, atomic_read(&lock->state), SIX_LOCK_read);
 551         }
 552         trace_contention_end(lock, 0);
 553
 554         return ret;
 555 }
 556
 557 /**
 558  * six_lock_ip_waiter - take a lock, with full waitlist interface
 559  * @lock:       lock to take
 560  * @type:       SIX_LOCK_read, SIX_LOCK_intent, or SIX_LOCK_write
 561  * @wait:       pointer to wait object, which will be added to lock's waitlist
 562  * @should_sleep_fn: callback run after adding to waitlist, immediately prior
 563  *              to scheduling
 564  * @p:          passed through to @should_sleep_fn
 565  * @ip:         ip parameter for lockdep/lockstat, i.e. _THIS_IP_
 566  *
 567  * This is the most general six_lock() variant, with parameters to support full
 568  * cycle detection for deadlock avoidance.
 569  *
 570  * The code calling this function must implement tracking of held locks, and the
 571  * @wait object should be embedded into the struct that tracks held locks -
 572  * which must also be accessible in a thread-safe way.
 573  *
 574  * @should_sleep_fn should invoke the cycle detector; it should walk each
 575  * lock's waiters, and for each waiter recursively walk their held locks.
 576  *
 577  * When this function must block, @wait will be added to @lock's waitlist before
 578  * calling trylock, and before calling @should_sleep_fn, and @wait will not be
 579  * removed from the lock waitlist until the lock has been successfully acquired,
 580  * or we abort.
 581  *
 582  * @wait.start_time will be monotonically increasing for any given waitlist, and
 583  * thus may be used as a loop cursor.
 584  *
 585  * Return: 0 on success, or the return code from @should_sleep_fn on failure.
 586  */
 587 int six_lock_ip_waiter(struct six_lock *lock, enum six_lock_type type,
 588                        struct six_lock_waiter *wait,
 589                        six_lock_should_sleep_fn should_sleep_fn, void *p,
 590                        unsigned long ip)
 591 {
 592         int ret;
 593
 594         wait->start_time = 0;
 595
 596         if (type != SIX_LOCK_write)
 597                 six_acquire(&lock->dep_map, 0, type == SIX_LOCK_read, ip);
 598
 599         ret = do_six_trylock(lock, type, true) ? 0
 600                 : six_lock_slowpath(lock, type, wait, should_sleep_fn, p, ip);
 601
 602         if (ret && type != SIX_LOCK_write)
 603                 six_release(&lock->dep_map, ip);
 604         if (!ret)
 605                 lock_acquired(&lock->dep_map, ip);
 606
 607         return ret;
 608 }
 609 EXPORT_SYMBOL_GPL(six_lock_ip_waiter);
 610
 611 __always_inline
 612 static void do_six_unlock_type(struct six_lock *lock, enum six_lock_type type)
 613 {
 614         u32 state;
 615
 616         if (type == SIX_LOCK_intent)
 617                 lock->owner = NULL;
 618
 619         if (type == SIX_LOCK_read &&
 620             lock->readers) {
 621                 smp_mb(); /* unlock barrier */
 622                 this_cpu_dec(*lock->readers);
 623                 smp_mb(); /* between unlocking and checking for waiters */
 624                 state = atomic_read(&lock->state);
 625         } else {
 626                 u32 v = l[type].lock_val;
 627
 628                 if (type != SIX_LOCK_read)
 629                         v += atomic_read(&lock->state) & SIX_LOCK_NOSPIN;
 630
 631                 EBUG_ON(!(atomic_read(&lock->state) & l[type].held_mask));
 632                 state = atomic_sub_return_release(v, &lock->state);
 633         }
 634
 635         six_lock_wakeup(lock, state, l[type].unlock_wakeup);
 636 }
 637
 638 /**
 639  * six_unlock_ip - drop a six lock
 640  * @lock:       lock to unlock
 641  * @type:       SIX_LOCK_read, SIX_LOCK_intent, or SIX_LOCK_write
 642  * @ip:         ip parameter for lockdep/lockstat, i.e. _THIS_IP_
 643  *
 644  * When a lock is held multiple times (because six_lock_incement()) was used),
 645  * this decrements the 'lock held' counter by one.
 646  *
 647  * For example:
 648  * six_lock_read(&foo->lock);                           read count 1
 649  * six_lock_increment(&foo->lock, SIX_LOCK_read);       read count 2
 650  * six_lock_unlock(&foo->lock, SIX_LOCK_read);          read count 1
 651  * six_lock_unlock(&foo->lock, SIX_LOCK_read);          read count 0
 652  */
 653 void six_unlock_ip(struct six_lock *lock, enum six_lock_type type, unsigned long ip)
 654 {
 655         EBUG_ON(type == SIX_LOCK_write &&
 656                 !(atomic_read(&lock->state) & SIX_LOCK_HELD_intent));
 657         EBUG_ON((type == SIX_LOCK_write ||
 658                  type == SIX_LOCK_intent) &&
 659                 lock->owner != current);
 660
 661         if (type != SIX_LOCK_write)
 662                 six_release(&lock->dep_map, ip);
 663         else
 664                 lock->seq++;
 665
 666         if (type == SIX_LOCK_intent &&
 667             lock->intent_lock_recurse) {
 668                 --lock->intent_lock_recurse;
 669                 return;
 670         }
 671
 672         do_six_unlock_type(lock, type);
 673 }
 674 EXPORT_SYMBOL_GPL(six_unlock_ip);
 675
 676 /**
 677  * six_lock_downgrade - convert an intent lock to a read lock
 678  * @lock:       lock to dowgrade
 679  *
 680  * @lock will have read count incremented and intent count decremented
 681  */
 682 void six_lock_downgrade(struct six_lock *lock)
 683 {
 684         six_lock_increment(lock, SIX_LOCK_read);
 685         six_unlock_intent(lock);
 686 }
 687 EXPORT_SYMBOL_GPL(six_lock_downgrade);
 688
 689 /**
 690  * six_lock_tryupgrade - attempt to convert read lock to an intent lock
 691  * @lock:       lock to upgrade
 692  *
 693  * On success, @lock will have intent count incremented and read count
 694  * decremented
 695  *
 696  * Return: true on success, false on failure
 697  */
 698 bool six_lock_tryupgrade(struct six_lock *lock)
 699 {
 700         u32 old = atomic_read(&lock->state), new;
 701
 702         do {
 703                 new = old;
 704
 705                 if (new & SIX_LOCK_HELD_intent)
 706                         return false;
 707
 708                 if (!lock->readers) {
 709                         EBUG_ON(!(new & SIX_LOCK_HELD_read));
 710                         new -= l[SIX_LOCK_read].lock_val;
 711                 }
 712
 713                 new |= SIX_LOCK_HELD_intent;
 714         } while (!atomic_try_cmpxchg_acquire(&lock->state, &old, new));
 715
 716         if (lock->readers)
 717                 this_cpu_dec(*lock->readers);
 718
 719         six_set_owner(lock, SIX_LOCK_intent, old, current);
 720
 721         return true;
 722 }
 723 EXPORT_SYMBOL_GPL(six_lock_tryupgrade);
 724
 725 /**
 726  * six_trylock_convert - attempt to convert a held lock from one type to another
 727  * @lock:       lock to upgrade
 728  * @from:       SIX_LOCK_read or SIX_LOCK_intent
 729  * @to:         SIX_LOCK_read or SIX_LOCK_intent
 730  *
 731  * On success, @lock will have intent count incremented and read count
 732  * decremented
 733  *
 734  * Return: true on success, false on failure
 735  */
 736 bool six_trylock_convert(struct six_lock *lock,
 737                          enum six_lock_type from,
 738                          enum six_lock_type to)
 739 {
 740         EBUG_ON(to == SIX_LOCK_write || from == SIX_LOCK_write);
 741
 742         if (to == from)
 743                 return true;
 744
 745         if (to == SIX_LOCK_read) {
 746                 six_lock_downgrade(lock);
 747                 return true;
 748         } else {
 749                 return six_lock_tryupgrade(lock);
 750         }
 751 }
 752 EXPORT_SYMBOL_GPL(six_trylock_convert);
 753
 754 /**
 755  * six_lock_increment - increase held lock count on a lock that is already held
 756  * @lock:       lock to increment
 757  * @type:       SIX_LOCK_read or SIX_LOCK_intent
 758  *
 759  * @lock must already be held, with a lock type that is greater than or equal to
 760  * @type
 761  *
 762  * A corresponding six_unlock_type() call will be required for @lock to be fully
 763  * unlocked.
 764  */
 765 void six_lock_increment(struct six_lock *lock, enum six_lock_type type)
 766 {
 767         six_acquire(&lock->dep_map, 0, type == SIX_LOCK_read, _RET_IP_);
 768
 769         /* XXX: assert already locked, and that we don't overflow: */
 770
 771         switch (type) {
 772         case SIX_LOCK_read:
 773                 if (lock->readers) {
 774                         this_cpu_inc(*lock->readers);
 775                 } else {
 776                         EBUG_ON(!(atomic_read(&lock->state) &
 777                                   (SIX_LOCK_HELD_read|
 778                                    SIX_LOCK_HELD_intent)));
 779                         atomic_add(l[type].lock_val, &lock->state);
 780                 }
 781                 break;
 782         case SIX_LOCK_intent:
 783                 EBUG_ON(!(atomic_read(&lock->state) & SIX_LOCK_HELD_intent));
 784                 lock->intent_lock_recurse++;
 785                 break;
 786         case SIX_LOCK_write:
 787                 BUG();
 788                 break;
 789         }
 790 }
 791 EXPORT_SYMBOL_GPL(six_lock_increment);
 792
 793 /**
 794  * six_lock_wakeup_all - wake up all waiters on @lock
 795  * @lock:       lock to wake up waiters for
 796  *
 797  * Wakeing up waiters will cause them to re-run should_sleep_fn, which may then
 798  * abort the lock operation.
 799  *
 800  * This function is never needed in a bug-free program; it's only useful in
 801  * debug code, e.g. to determine if a cycle detector is at fault.
 802  */
 803 void six_lock_wakeup_all(struct six_lock *lock)
 804 {
 805         u32 state = atomic_read(&lock->state);
 806         struct six_lock_waiter *w;
 807
 808         six_lock_wakeup(lock, state, SIX_LOCK_read);
 809         six_lock_wakeup(lock, state, SIX_LOCK_intent);
 810         six_lock_wakeup(lock, state, SIX_LOCK_write);
 811
 812         raw_spin_lock(&lock->wait_lock);
 813         list_for_each_entry(w, &lock->wait_list, list)
 814                 wake_up_process(w->task);
 815         raw_spin_unlock(&lock->wait_lock);
 816 }
 817 EXPORT_SYMBOL_GPL(six_lock_wakeup_all);
 818
 819 /**
 820  * six_lock_counts - return held lock counts, for each lock type
 821  * @lock:       lock to return counters for
 822  *
 823  * Return: the number of times a lock is held for read, intent and write.
 824  */
 825 struct six_lock_count six_lock_counts(struct six_lock *lock)
 826 {
 827         struct six_lock_count ret;
 828
 829         ret.n[SIX_LOCK_read]    = !lock->readers
 830                 ? atomic_read(&lock->state) & SIX_LOCK_HELD_read
 831                 : pcpu_read_count(lock);
 832         ret.n[SIX_LOCK_intent]  = !!(atomic_read(&lock->state) & SIX_LOCK_HELD_intent) +
 833                 lock->intent_lock_recurse;
 834         ret.n[SIX_LOCK_write]   = !!(atomic_read(&lock->state) & SIX_LOCK_HELD_write);
 835
 836         return ret;
 837 }
 838 EXPORT_SYMBOL_GPL(six_lock_counts);
 839
 840 /**
 841  * six_lock_readers_add - directly manipulate reader count of a lock
 842  * @lock:       lock to add/subtract readers for
 843  * @nr:         reader count to add/subtract
 844  *
 845  * When an upper layer is implementing lock reentrency, we may have both read
 846  * and intent locks on the same lock.
 847  *
 848  * When we need to take a write lock, the read locks will cause self-deadlock,
 849  * because six locks themselves do not track which read locks are held by the
 850  * current thread and which are held by a different thread - it does no
 851  * per-thread tracking of held locks.
 852  *
 853  * The upper layer that is tracking held locks may however, if trylock() has
 854  * failed, count up its own read locks, subtract them, take the write lock, and
 855  * then re-add them.
 856  *
 857  * As in any other situation when taking a write lock, @lock must be held for
 858  * intent one (or more) times, so @lock will never be left unlocked.
 859  */
 860 void six_lock_readers_add(struct six_lock *lock, int nr)
 861 {
 862         if (lock->readers) {
 863                 this_cpu_add(*lock->readers, nr);
 864         } else {
 865                 EBUG_ON((int) (atomic_read(&lock->state) & SIX_LOCK_HELD_read) + nr < 0);
 866                 /* reader count starts at bit 0 */
 867                 atomic_add(nr, &lock->state);
 868         }
 869 }
 870 EXPORT_SYMBOL_GPL(six_lock_readers_add);
 871
 872 /**
 873  * six_lock_exit - release resources held by a lock prior to freeing
 874  * @lock:       lock to exit
 875  *
 876  * When a lock was initialized in percpu mode (SIX_OLCK_INIT_PCPU), this is
 877  * required to free the percpu read counts.
 878  */
 879 void six_lock_exit(struct six_lock *lock)
 880 {
 881         WARN_ON(lock->readers && pcpu_read_count(lock));
 882         WARN_ON(atomic_read(&lock->state) & SIX_LOCK_HELD_read);
 883
 884         free_percpu(lock->readers);
 885         lock->readers = NULL;
 886 }
 887 EXPORT_SYMBOL_GPL(six_lock_exit);
 888
 889 void __six_lock_init(struct six_lock *lock, const char *name,
 890                      struct lock_class_key *key, enum six_lock_init_flags flags)
 891 {
 892         atomic_set(&lock->state, 0);
 893         raw_spin_lock_init(&lock->wait_lock);
 894         INIT_LIST_HEAD(&lock->wait_list);
 895 #ifdef CONFIG_DEBUG_LOCK_ALLOC
 896         debug_check_no_locks_freed((void *) lock, sizeof(*lock));
 897         lockdep_init_map(&lock->dep_map, name, key, 0);
 898 #endif
 899
 900         /*
 901          * Don't assume that we have real percpu variables available in
 902          * userspace:
 903          */
 904 #ifdef __KERNEL__
 905         if (flags & SIX_LOCK_INIT_PCPU) {
 906                 /*
 907                  * We don't return an error here on memory allocation failure
 908                  * since percpu is an optimization, and locks will work with the
 909                  * same semantics in non-percpu mode: callers can check for
 910                  * failure if they wish by checking lock->readers, but generally
 911                  * will not want to treat it as an error.
 912                  */
 913                 lock->readers = alloc_percpu(unsigned);
 914         }
 915 #endif
 916 }
 917 EXPORT_SYMBOL_GPL(__six_lock_init);