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                         goto out_nolock;
 218
 219                 set_current_state(state);
 220                 raw_spin_unlock_irqrestore(&sem->wait_lock, flags);
 221                 schedule();
 222                 raw_spin_lock_irqsave(&sem->wait_lock, flags);
 223         }
 224         /* got the lock */
 225         sem->count = -1;
 226         list_del(&waiter.list);
 227
 228         raw_spin_unlock_irqrestore(&sem->wait_lock, flags);
 229
 230         return ret;
 231
 232 out_nolock:
 233         list_del(&waiter.list);
 234         if (!list_empty(&sem->wait_list))
 235                 __rwsem_do_wake(sem, 1);
 236         raw_spin_unlock_irqrestore(&sem->wait_lock, flags);
 237
 238         return -EINTR;
 239 }
 240
 241 void __sched __down_write(struct rw_semaphore *sem)
 242 {
 243         __down_write_common(sem, TASK_UNINTERRUPTIBLE);
 244 }
 245
 246 int __sched __down_write_killable(struct rw_semaphore *sem)
 247 {
 248         return __down_write_common(sem, TASK_KILLABLE);
 249 }
 250
 251 /*
 252  * trylock for writing -- returns 1 if successful, 0 if contention
 253  */
 254 int __down_write_trylock(struct rw_semaphore *sem)
 255 {
 256         unsigned long flags;
 257         int ret = 0;
 258
 259         raw_spin_lock_irqsave(&sem->wait_lock, flags);
 260
 261         if (sem->count == 0) {
 262                 /* got the lock */
 263                 sem->count = -1;
 264                 ret = 1;
 265         }
 266
 267         raw_spin_unlock_irqrestore(&sem->wait_lock, flags);
 268
 269         return ret;
 270 }
 271
 272 /*
 273  * release a read lock on the semaphore
 274  */
 275 void __up_read(struct rw_semaphore *sem)
 276 {
 277         unsigned long flags;
 278
 279         raw_spin_lock_irqsave(&sem->wait_lock, flags);
 280
 281         if (--sem->count == 0 && !list_empty(&sem->wait_list))
 282                 sem = __rwsem_wake_one_writer(sem);
 283
 284         raw_spin_unlock_irqrestore(&sem->wait_lock, flags);
 285 }
 286
 287 /*
 288  * release a write lock on the semaphore
 289  */
 290 void __up_write(struct rw_semaphore *sem)
 291 {
 292         unsigned long flags;
 293
 294         raw_spin_lock_irqsave(&sem->wait_lock, flags);
 295
 296         sem->count = 0;
 297         if (!list_empty(&sem->wait_list))
 298                 sem = __rwsem_do_wake(sem, 1);
 299
 300         raw_spin_unlock_irqrestore(&sem->wait_lock, flags);
 301 }
 302
 303 /*
 304  * downgrade a write lock into a read lock
 305  * - just wake up any readers at the front of the queue
 306  */
 307 void __downgrade_write(struct rw_semaphore *sem)
 308 {
 309         unsigned long flags;
 310
 311         raw_spin_lock_irqsave(&sem->wait_lock, flags);
 312
 313         sem->count = 1;
 314         if (!list_empty(&sem->wait_list))
 315                 sem = __rwsem_do_wake(sem, 0);
 316
 317         raw_spin_unlock_irqrestore(&sem->wait_lock, flags);
 318 }
 319