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