kernel/locking/rwsem-spinlock.c

   1 /* rwsem-spinlock.c: R/W semaphores: contention handling functions for
   2  * generic spinlock implementation
   3  *
   4  * Copyright (c) 2001   David Howells (dhowells@redhat.com).
   5  * - Derived partially from idea by Andrea Arcangeli <andrea@suse.de>
   6  * - Derived also from comments by Linus
   7  */
   8 #include <linux/rwsem.h>
   9 #include <linux/sched/signal.h>
  10 #include <linux/sched/debug.h>
  11 #include <linux/export.h>
  12
  13 enum rwsem_waiter_type {
  14         RWSEM_WAITING_FOR_WRITE,
  15         RWSEM_WAITING_FOR_READ
  16 };
  17
  18 struct rwsem_waiter {
  19         struct list_head list;
  20         struct task_struct *task;
  21         enum rwsem_waiter_type type;
  22 };
  23
  24 int rwsem_is_locked(struct rw_semaphore *sem)
  25 {
  26         int ret = 1;
  27         unsigned long flags;
  28
  29         if (raw_spin_trylock_irqsave(&sem->wait_lock, flags)) {
  30                 ret = (sem->count != 0);
  31                 raw_spin_unlock_irqrestore(&sem->wait_lock, flags);
  32         }
  33         return ret;
  34 }
  35 EXPORT_SYMBOL(rwsem_is_locked);
  36
  37 /*
  38  * initialise the semaphore
  39  */
  40 void __init_rwsem(struct rw_semaphore *sem, const char *name,
  41                   struct lock_class_key *key)
  42 {
  43 #ifdef CONFIG_DEBUG_LOCK_ALLOC
  44         /*
  45          * Make sure we are not reinitializing a held semaphore:
  46          */
  47         debug_check_no_locks_freed((void *)sem, sizeof(*sem));
  48         lockdep_init_map(&sem->dep_map, name, key, 0);
  49 #endif
  50         sem->count = 0;
  51         raw_spin_lock_init(&sem->wait_lock);
  52         INIT_LIST_HEAD(&sem->wait_list);
  53 }
  54 EXPORT_SYMBOL(__init_rwsem);
  55
  56 /*
  57  * handle the lock release when processes blocked on it that can now run
  58  * - if we come here, then:
  59  *   - the 'active count' _reached_ zero
  60  *   - the 'waiting count' is non-zero
  61  * - the spinlock must be held by the caller
  62  * - woken process blocks are discarded from the list after having task zeroed
  63  * - writers are only woken if wakewrite is non-zero
  64  */
  65 static inline struct rw_semaphore *
  66 __rwsem_do_wake(struct rw_semaphore *sem, int wakewrite)
  67 {
  68         struct rwsem_waiter *waiter;
  69         struct task_struct *tsk;
  70         int woken;
  71
  72         waiter = list_entry(sem->wait_list.next, struct rwsem_waiter, list);
  73
  74         if (waiter->type == RWSEM_WAITING_FOR_WRITE) {
  75                 if (wakewrite)
  76                         /* Wake up a writer. Note that we do not grant it the
  77                          * lock - it will have to acquire it when it runs. */
  78                         wake_up_process(waiter->task);
  79                 goto out;
  80         }
  81
  82         /* grant an infinite number of read locks to the front of the queue */
  83         woken = 0;
  84         do {
  85                 struct list_head *next = waiter->list.next;
  86
  87                 list_del(&waiter->list);
  88                 tsk = waiter->task;
  89                 /*
  90                  * Make sure we do not wakeup the next reader before
  91                  * setting the nil condition to grant the next reader;
  92                  * otherwise we could miss the wakeup on the other
  93                  * side and end up sleeping again. See the pairing
  94                  * in rwsem_down_read_failed().
  95                  */
  96                 smp_mb();
  97                 waiter->task = NULL;
  98                 wake_up_process(tsk);
  99                 put_task_struct(tsk);
 100                 woken++;
 101                 if (next == &sem->wait_list)
 102                         break;
 103                 waiter = list_entry(next, struct rwsem_waiter, list);
 104         } while (waiter->type != RWSEM_WAITING_FOR_WRITE);
 105
 106         sem->count += woken;
 107
 108  out:
 109         return sem;
 110 }
 111
 112 /*
 113  * wake a single writer
 114  */
 115 static inline struct rw_semaphore *
 116 __rwsem_wake_one_writer(struct rw_semaphore *sem)
 117 {
 118         struct rwsem_waiter *waiter;
 119
 120         waiter = list_entry(sem->wait_list.next, struct rwsem_waiter, list);
 121         wake_up_process(waiter->task);
 122
 123         return sem;
 124 }
 125
 126 /*
 127  * get a read lock on the semaphore
 128  */
 129 void __sched __down_read(struct rw_semaphore *sem)
 130 {
 131         struct rwsem_waiter waiter;
 132         unsigned long flags;
 133
 134         raw_spin_lock_irqsave(&sem->wait_lock, flags);
 135
 136         if (sem->count >= 0 && list_empty(&sem->wait_list)) {
 137                 /* granted */
 138                 sem->count++;
 139                 raw_spin_unlock_irqrestore(&sem->wait_lock, flags);
 140                 goto out;
 141         }
 142
 143         set_current_state(TASK_UNINTERRUPTIBLE);
 144
 145         /* set up my own style of waitqueue */
 146         waiter.task = current;
 147         waiter.type = RWSEM_WAITING_FOR_READ;
 148         get_task_struct(current);
 149
 150         list_add_tail(&waiter.list, &sem->wait_list);
 151
 152         /* we don't need to touch the semaphore struct anymore */
 153         raw_spin_unlock_irqrestore(&sem->wait_lock, flags);
 154
 155         /* wait to be given the lock */
 156         for (;;) {
 157                 if (!waiter.task)
 158                         break;
 159                 schedule();
 160                 set_current_state(TASK_UNINTERRUPTIBLE);
 161         }
 162
 163         __set_current_state(TASK_RUNNING);
 164  out:
 165         ;
 166 }
 167
 168 /*
 169  * trylock for reading -- returns 1 if successful, 0 if contention
 170  */
 171 int __down_read_trylock(struct rw_semaphore *sem)
 172 {
 173         unsigned long flags;
 174         int ret = 0;
 175
 176
 177         raw_spin_lock_irqsave(&sem->wait_lock, flags);
 178
 179         if (sem->count >= 0 && list_empty(&sem->wait_list)) {
 180                 /* granted */
 181                 sem->count++;
 182                 ret = 1;
 183         }
 184
 185         raw_spin_unlock_irqrestore(&sem->wait_lock, flags);
 186
 187         return ret;
 188 }
 189
 190 /*
 191  * get a write lock on the semaphore
 192  */
 193 int __sched __down_write_common(struct rw_semaphore *sem, int state)
 194 {
 195         struct rwsem_waiter waiter;
 196         unsigned long flags;
 197         int ret = 0;
 198
 199         raw_spin_lock_irqsave(&sem->wait_lock, flags);
 200
 201         /* set up my own style of waitqueue */
 202         waiter.task = current;
 203         waiter.type = RWSEM_WAITING_FOR_WRITE;
 204         list_add_tail(&waiter.list, &sem->wait_list);
 205
 206         /* wait for someone to release the lock */
 207         for (;;) {
 208                 /*
 209                  * That is the key to support write lock stealing: allows the
 210                  * task already on CPU to get the lock soon rather than put
 211                  * itself into sleep and waiting for system woke it or someone
 212                  * else in the head of the wait list up.
 213                  */
 214                 if (sem->count == 0)
 215                         break;
 216                 if (signal_pending_state(state, current)) {
 217                         ret = -EINTR;
 218                         goto out;
 219                 }
 220                 set_current_state(state);
 221                 raw_spin_unlock_irqrestore(&sem->wait_lock, flags);
 222                 schedule();
 223                 raw_spin_lock_irqsave(&sem->wait_lock, flags);
 224         }
 225         /* got the lock */
 226         sem->count = -1;
 227 out:
 228         list_del(&waiter.list);
 229
 230         raw_spin_unlock_irqrestore(&sem->wait_lock, flags);
 231
 232         return ret;
 233 }
 234
 235 void __sched __down_write(struct rw_semaphore *sem)
 236 {
 237         __down_write_common(sem, TASK_UNINTERRUPTIBLE);
 238 }
 239
 240 int __sched __down_write_killable(struct rw_semaphore *sem)
 241 {
 242         return __down_write_common(sem, TASK_KILLABLE);
 243 }
 244
 245 /*
 246  * trylock for writing -- returns 1 if successful, 0 if contention
 247  */
 248 int __down_write_trylock(struct rw_semaphore *sem)
 249 {
 250         unsigned long flags;
 251         int ret = 0;
 252
 253         raw_spin_lock_irqsave(&sem->wait_lock, flags);
 254
 255         if (sem->count == 0) {
 256                 /* got the lock */
 257                 sem->count = -1;
 258                 ret = 1;
 259         }
 260
 261         raw_spin_unlock_irqrestore(&sem->wait_lock, flags);
 262
 263         return ret;
 264 }
 265
 266 /*
 267  * release a read lock on the semaphore
 268  */
 269 void __up_read(struct rw_semaphore *sem)
 270 {
 271         unsigned long flags;
 272
 273         raw_spin_lock_irqsave(&sem->wait_lock, flags);
 274
 275         if (--sem->count == 0 && !list_empty(&sem->wait_list))
 276                 sem = __rwsem_wake_one_writer(sem);
 277
 278         raw_spin_unlock_irqrestore(&sem->wait_lock, flags);
 279 }
 280
 281 /*
 282  * release a write lock on the semaphore
 283  */
 284 void __up_write(struct rw_semaphore *sem)
 285 {
 286         unsigned long flags;
 287
 288         raw_spin_lock_irqsave(&sem->wait_lock, flags);
 289
 290         sem->count = 0;
 291         if (!list_empty(&sem->wait_list))
 292                 sem = __rwsem_do_wake(sem, 1);
 293
 294         raw_spin_unlock_irqrestore(&sem->wait_lock, flags);
 295 }
 296
 297 /*
 298  * downgrade a write lock into a read lock
 299  * - just wake up any readers at the front of the queue
 300  */
 301 void __downgrade_write(struct rw_semaphore *sem)
 302 {
 303         unsigned long flags;
 304
 305         raw_spin_lock_irqsave(&sem->wait_lock, flags);
 306
 307         sem->count = 1;
 308         if (!list_empty(&sem->wait_list))
 309                 sem = __rwsem_do_wake(sem, 0);
 310
 311         raw_spin_unlock_irqrestore(&sem->wait_lock, flags);
 312 }
 313