lib/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->activity != 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->activity = 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 (!wakewrite) {
  74                 if (waiter->type == RWSEM_WAITING_FOR_WRITE)
  75                         goto out;
  76                 goto dont_wake_writers;
  77         }
  78
  79         /*
  80          * as we support write lock stealing, we can't set sem->activity
  81          * to -1 here to indicate we get the lock. Instead, we wake it up
  82          * to let it go get it again.
  83          */
  84         if (waiter->type == RWSEM_WAITING_FOR_WRITE) {
  85                 wake_up_process(waiter->task);
  86                 goto out;
  87         }
  88
  89         /* grant an infinite number of read locks to the front of the queue */
  90  dont_wake_writers:
  91         woken = 0;
  92         while (waiter->type == RWSEM_WAITING_FOR_READ) {
  93                 struct list_head *next = waiter->list.next;
  94
  95                 list_del(&waiter->list);
  96                 tsk = waiter->task;
  97                 smp_mb();
  98                 waiter->task = NULL;
  99                 wake_up_process(tsk);
 100                 put_task_struct(tsk);
 101                 woken++;
 102                 if (list_empty(&sem->wait_list))
 103                         break;
 104                 waiter = list_entry(next, struct rwsem_waiter, list);
 105         }
 106
 107         sem->activity += woken;
 108
 109  out:
 110         return sem;
 111 }
 112
 113 /*
 114  * wake a single writer
 115  */
 116 static inline struct rw_semaphore *
 117 __rwsem_wake_one_writer(struct rw_semaphore *sem)
 118 {
 119         struct rwsem_waiter *waiter;
 120
 121         waiter = list_entry(sem->wait_list.next, struct rwsem_waiter, list);
 122         wake_up_process(waiter->task);
 123
 124         return sem;
 125 }
 126
 127 /*
 128  * get a read lock on the semaphore
 129  */
 130 void __sched __down_read(struct rw_semaphore *sem)
 131 {
 132         struct rwsem_waiter waiter;
 133         struct task_struct *tsk;
 134         unsigned long flags;
 135
 136         raw_spin_lock_irqsave(&sem->wait_lock, flags);
 137
 138         if (sem->activity >= 0 && list_empty(&sem->wait_list)) {
 139                 /* granted */
 140                 sem->activity++;
 141                 raw_spin_unlock_irqrestore(&sem->wait_lock, flags);
 142                 goto out;
 143         }
 144
 145         tsk = current;
 146         set_task_state(tsk, TASK_UNINTERRUPTIBLE);
 147
 148         /* set up my own style of waitqueue */
 149         waiter.task = tsk;
 150         waiter.type = RWSEM_WAITING_FOR_READ;
 151         get_task_struct(tsk);
 152
 153         list_add_tail(&waiter.list, &sem->wait_list);
 154
 155         /* we don't need to touch the semaphore struct anymore */
 156         raw_spin_unlock_irqrestore(&sem->wait_lock, flags);
 157
 158         /* wait to be given the lock */
 159         for (;;) {
 160                 if (!waiter.task)
 161                         break;
 162                 schedule();
 163                 set_task_state(tsk, TASK_UNINTERRUPTIBLE);
 164         }
 165
 166         tsk->state = TASK_RUNNING;
 167  out:
 168         ;
 169 }
 170
 171 /*
 172  * trylock for reading -- returns 1 if successful, 0 if contention
 173  */
 174 int __down_read_trylock(struct rw_semaphore *sem)
 175 {
 176         unsigned long flags;
 177         int ret = 0;
 178
 179
 180         raw_spin_lock_irqsave(&sem->wait_lock, flags);
 181
 182         if (sem->activity >= 0 && list_empty(&sem->wait_list)) {
 183                 /* granted */
 184                 sem->activity++;
 185                 ret = 1;
 186         }
 187
 188         raw_spin_unlock_irqrestore(&sem->wait_lock, flags);
 189
 190         return ret;
 191 }
 192
 193 /*
 194  * get a write lock on the semaphore
 195  */
 196 void __sched __down_write_nested(struct rw_semaphore *sem, int subclass)
 197 {
 198         struct rwsem_waiter waiter;
 199         struct task_struct *tsk;
 200         unsigned long flags;
 201
 202         raw_spin_lock_irqsave(&sem->wait_lock, flags);
 203
 204         /* set up my own style of waitqueue */
 205         tsk = current;
 206         waiter.task = tsk;
 207         waiter.type = RWSEM_WAITING_FOR_WRITE;
 208         list_add_tail(&waiter.list, &sem->wait_list);
 209
 210         /* wait for someone to release the lock */
 211         for (;;) {
 212                 /*
 213                  * That is the key to support write lock stealing: allows the
 214                  * task already on CPU to get the lock soon rather than put
 215                  * itself into sleep and waiting for system woke it or someone
 216                  * else in the head of the wait list up.
 217                  */
 218                 if (sem->activity == 0)
 219                         break;
 220                 set_task_state(tsk, TASK_UNINTERRUPTIBLE);
 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->activity = -1;
 227         list_del(&waiter.list);
 228
 229         raw_spin_unlock_irqrestore(&sem->wait_lock, flags);
 230 }
 231
 232 void __sched __down_write(struct rw_semaphore *sem)
 233 {
 234         __down_write_nested(sem, 0);
 235 }
 236
 237 /*
 238  * trylock for writing -- returns 1 if successful, 0 if contention
 239  */
 240 int __down_write_trylock(struct rw_semaphore *sem)
 241 {
 242         unsigned long flags;
 243         int ret = 0;
 244
 245         raw_spin_lock_irqsave(&sem->wait_lock, flags);
 246
 247         if (sem->activity == 0) {
 248                 /* got the lock */
 249                 sem->activity = -1;
 250                 ret = 1;
 251         }
 252
 253         raw_spin_unlock_irqrestore(&sem->wait_lock, flags);
 254
 255         return ret;
 256 }
 257
 258 /*
 259  * release a read lock on the semaphore
 260  */
 261 void __up_read(struct rw_semaphore *sem)
 262 {
 263         unsigned long flags;
 264
 265         raw_spin_lock_irqsave(&sem->wait_lock, flags);
 266
 267         if (--sem->activity == 0 && !list_empty(&sem->wait_list))
 268                 sem = __rwsem_wake_one_writer(sem);
 269
 270         raw_spin_unlock_irqrestore(&sem->wait_lock, flags);
 271 }
 272
 273 /*
 274  * release a write lock on the semaphore
 275  */
 276 void __up_write(struct rw_semaphore *sem)
 277 {
 278         unsigned long flags;
 279
 280         raw_spin_lock_irqsave(&sem->wait_lock, flags);
 281
 282         sem->activity = 0;
 283         if (!list_empty(&sem->wait_list))
 284                 sem = __rwsem_do_wake(sem, 1);
 285
 286         raw_spin_unlock_irqrestore(&sem->wait_lock, flags);
 287 }
 288
 289 /*
 290  * downgrade a write lock into a read lock
 291  * - just wake up any readers at the front of the queue
 292  */
 293 void __downgrade_write(struct rw_semaphore *sem)
 294 {
 295         unsigned long flags;
 296
 297         raw_spin_lock_irqsave(&sem->wait_lock, flags);
 298
 299         sem->activity = 1;
 300         if (!list_empty(&sem->wait_list))
 301                 sem = __rwsem_do_wake(sem, 0);
 302
 303         raw_spin_unlock_irqrestore(&sem->wait_lock, flags);
 304 }
 305