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 int __sched __down_read_common(struct rw_semaphore *sem, int state)
 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 up my own style of waitqueue */
 144         waiter.task = current;
 145         waiter.type = RWSEM_WAITING_FOR_READ;
 146         get_task_struct(current);
 147
 148         list_add_tail(&waiter.list, &sem->wait_list);
 149
 150         /* wait to be given the lock */
 151         for (;;) {
 152                 if (!waiter.task)
 153                         break;
 154                 if (signal_pending_state(state, current))
 155                         goto out_nolock;
 156                 set_current_state(state);
 157                 raw_spin_unlock_irqrestore(&sem->wait_lock, flags);
 158                 schedule();
 159                 raw_spin_lock_irqsave(&sem->wait_lock, flags);
 160         }
 161
 162         raw_spin_unlock_irqrestore(&sem->wait_lock, flags);
 163  out:
 164         return 0;
 165
 166 out_nolock:
 167         /*
 168          * We didn't take the lock, so that there is a writer, which
 169          * is owner or the first waiter of the sem. If it's a waiter,
 170          * it will be woken by current owner. Not need to wake anybody.
 171          */
 172         list_del(&waiter.list);
 173         raw_spin_unlock_irqrestore(&sem->wait_lock, flags);
 174         return -EINTR;
 175 }
 176
 177 void __sched __down_read(struct rw_semaphore *sem)
 178 {
 179         __down_read_common(sem, TASK_UNINTERRUPTIBLE);
 180 }
 181
 182 int __sched __down_read_killable(struct rw_semaphore *sem)
 183 {
 184         return __down_read_common(sem, TASK_KILLABLE);
 185 }
 186
 187 /*
 188  * trylock for reading -- returns 1 if successful, 0 if contention
 189  */
 190 int __down_read_trylock(struct rw_semaphore *sem)
 191 {
 192         unsigned long flags;
 193         int ret = 0;
 194
 195
 196         raw_spin_lock_irqsave(&sem->wait_lock, flags);
 197
 198         if (sem->count >= 0 && list_empty(&sem->wait_list)) {
 199                 /* granted */
 200                 sem->count++;
 201                 ret = 1;
 202         }
 203
 204         raw_spin_unlock_irqrestore(&sem->wait_lock, flags);
 205
 206         return ret;
 207 }
 208
 209 /*
 210  * get a write lock on the semaphore
 211  */
 212 int __sched __down_write_common(struct rw_semaphore *sem, int state)
 213 {
 214         struct rwsem_waiter waiter;
 215         unsigned long flags;
 216         int ret = 0;
 217
 218         raw_spin_lock_irqsave(&sem->wait_lock, flags);
 219
 220         /* set up my own style of waitqueue */
 221         waiter.task = current;
 222         waiter.type = RWSEM_WAITING_FOR_WRITE;
 223         list_add_tail(&waiter.list, &sem->wait_list);
 224
 225         /* wait for someone to release the lock */
 226         for (;;) {
 227                 /*
 228                  * That is the key to support write lock stealing: allows the
 229                  * task already on CPU to get the lock soon rather than put
 230                  * itself into sleep and waiting for system woke it or someone
 231                  * else in the head of the wait list up.
 232                  */
 233                 if (sem->count == 0)
 234                         break;
 235                 if (signal_pending_state(state, current))
 236                         goto out_nolock;
 237
 238                 set_current_state(state);
 239                 raw_spin_unlock_irqrestore(&sem->wait_lock, flags);
 240                 schedule();
 241                 raw_spin_lock_irqsave(&sem->wait_lock, flags);
 242         }
 243         /* got the lock */
 244         sem->count = -1;
 245         list_del(&waiter.list);
 246
 247         raw_spin_unlock_irqrestore(&sem->wait_lock, flags);
 248
 249         return ret;
 250
 251 out_nolock:
 252         list_del(&waiter.list);
 253         if (!list_empty(&sem->wait_list) && sem->count >= 0)
 254                 __rwsem_do_wake(sem, 0);
 255         raw_spin_unlock_irqrestore(&sem->wait_lock, flags);
 256
 257         return -EINTR;
 258 }
 259
 260 void __sched __down_write(struct rw_semaphore *sem)
 261 {
 262         __down_write_common(sem, TASK_UNINTERRUPTIBLE);
 263 }
 264
 265 int __sched __down_write_killable(struct rw_semaphore *sem)
 266 {
 267         return __down_write_common(sem, TASK_KILLABLE);
 268 }
 269
 270 /*
 271  * trylock for writing -- returns 1 if successful, 0 if contention
 272  */
 273 int __down_write_trylock(struct rw_semaphore *sem)
 274 {
 275         unsigned long flags;
 276         int ret = 0;
 277
 278         raw_spin_lock_irqsave(&sem->wait_lock, flags);
 279
 280         if (sem->count == 0) {
 281                 /* got the lock */
 282                 sem->count = -1;
 283                 ret = 1;
 284         }
 285
 286         raw_spin_unlock_irqrestore(&sem->wait_lock, flags);
 287
 288         return ret;
 289 }
 290
 291 /*
 292  * release a read lock on the semaphore
 293  */
 294 void __up_read(struct rw_semaphore *sem)
 295 {
 296         unsigned long flags;
 297
 298         raw_spin_lock_irqsave(&sem->wait_lock, flags);
 299
 300         if (--sem->count == 0 && !list_empty(&sem->wait_list))
 301                 sem = __rwsem_wake_one_writer(sem);
 302
 303         raw_spin_unlock_irqrestore(&sem->wait_lock, flags);
 304 }
 305
 306 /*
 307  * release a write lock on the semaphore
 308  */
 309 void __up_write(struct rw_semaphore *sem)
 310 {
 311         unsigned long flags;
 312
 313         raw_spin_lock_irqsave(&sem->wait_lock, flags);
 314
 315         sem->count = 0;
 316         if (!list_empty(&sem->wait_list))
 317                 sem = __rwsem_do_wake(sem, 1);
 318
 319         raw_spin_unlock_irqrestore(&sem->wait_lock, flags);
 320 }
 321
 322 /*
 323  * downgrade a write lock into a read lock
 324  * - just wake up any readers at the front of the queue
 325  */
 326 void __downgrade_write(struct rw_semaphore *sem)
 327 {
 328         unsigned long flags;
 329
 330         raw_spin_lock_irqsave(&sem->wait_lock, flags);
 331
 332         sem->count = 1;
 333         if (!list_empty(&sem->wait_list))
 334                 sem = __rwsem_do_wake(sem, 0);
 335
 336         raw_spin_unlock_irqrestore(&sem->wait_lock, flags);
 337 }
 338