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/module.h>
  11
  12 struct rwsem_waiter {
  13         struct list_head list;
  14         struct task_struct *task;
  15         unsigned int flags;
  16 #define RWSEM_WAITING_FOR_READ  0x00000001
  17 #define RWSEM_WAITING_FOR_WRITE 0x00000002
  18 };
  19
  20 /*
  21  * initialise the semaphore
  22  */
  23 void __init_rwsem(struct rw_semaphore *sem, const char *name,
  24                   struct lock_class_key *key)
  25 {
  26 #ifdef CONFIG_DEBUG_LOCK_ALLOC
  27         /*
  28          * Make sure we are not reinitializing a held semaphore:
  29          */
  30         debug_check_no_locks_freed((void *)sem, sizeof(*sem));
  31         lockdep_init_map(&sem->dep_map, name, key, 0);
  32 #endif
  33         sem->activity = 0;
  34         spin_lock_init(&sem->wait_lock);
  35         INIT_LIST_HEAD(&sem->wait_list);
  36 }
  37
  38 /*
  39  * handle the lock release when processes blocked on it that can now run
  40  * - if we come here, then:
  41  *   - the 'active count' _reached_ zero
  42  *   - the 'waiting count' is non-zero
  43  * - the spinlock must be held by the caller
  44  * - woken process blocks are discarded from the list after having task zeroed
  45  * - writers are only woken if wakewrite is non-zero
  46  */
  47 static inline struct rw_semaphore *
  48 __rwsem_do_wake(struct rw_semaphore *sem, int wakewrite)
  49 {
  50         struct rwsem_waiter *waiter;
  51         struct task_struct *tsk;
  52         int woken;
  53
  54         waiter = list_entry(sem->wait_list.next, struct rwsem_waiter, list);
  55
  56         if (!wakewrite) {
  57                 if (waiter->flags & RWSEM_WAITING_FOR_WRITE)
  58                         goto out;
  59                 goto dont_wake_writers;
  60         }
  61
  62         /* if we are allowed to wake writers try to grant a single write lock
  63          * if there's a writer at the front of the queue
  64          * - we leave the 'waiting count' incremented to signify potential
  65          *   contention
  66          */
  67         if (waiter->flags & RWSEM_WAITING_FOR_WRITE) {
  68                 sem->activity = -1;
  69                 list_del(&waiter->list);
  70                 tsk = waiter->task;
  71                 /* Don't touch waiter after ->task has been NULLed */
  72                 smp_mb();
  73                 waiter->task = NULL;
  74                 wake_up_process(tsk);
  75                 put_task_struct(tsk);
  76                 goto out;
  77         }
  78
  79         /* grant an infinite number of read locks to the front of the queue */
  80  dont_wake_writers:
  81         woken = 0;
  82         while (waiter->flags & RWSEM_WAITING_FOR_READ) {
  83                 struct list_head *next = waiter->list.next;
  84
  85                 list_del(&waiter->list);
  86                 tsk = waiter->task;
  87                 smp_mb();
  88                 waiter->task = NULL;
  89                 wake_up_process(tsk);
  90                 put_task_struct(tsk);
  91                 woken++;
  92                 if (list_empty(&sem->wait_list))
  93                         break;
  94                 waiter = list_entry(next, struct rwsem_waiter, list);
  95         }
  96
  97         sem->activity += woken;
  98
  99  out:
 100         return sem;
 101 }
 102
 103 /*
 104  * wake a single writer
 105  */
 106 static inline struct rw_semaphore *
 107 __rwsem_wake_one_writer(struct rw_semaphore *sem)
 108 {
 109         struct rwsem_waiter *waiter;
 110         struct task_struct *tsk;
 111
 112         sem->activity = -1;
 113
 114         waiter = list_entry(sem->wait_list.next, struct rwsem_waiter, list);
 115         list_del(&waiter->list);
 116
 117         tsk = waiter->task;
 118         smp_mb();
 119         waiter->task = NULL;
 120         wake_up_process(tsk);
 121         put_task_struct(tsk);
 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
 133         spin_lock_irq(&sem->wait_lock);
 134
 135         if (sem->activity >= 0 && list_empty(&sem->wait_list)) {
 136                 /* granted */
 137                 sem->activity++;
 138                 spin_unlock_irq(&sem->wait_lock);
 139                 goto out;
 140         }
 141
 142         tsk = current;
 143         set_task_state(tsk, TASK_UNINTERRUPTIBLE);
 144
 145         /* set up my own style of waitqueue */
 146         waiter.task = tsk;
 147         waiter.flags = RWSEM_WAITING_FOR_READ;
 148         get_task_struct(tsk);
 149
 150         list_add_tail(&waiter.list, &sem->wait_list);
 151
 152         /* we don't need to touch the semaphore struct anymore */
 153         spin_unlock_irq(&sem->wait_lock);
 154
 155         /* wait to be given the lock */
 156         for (;;) {
 157                 if (!waiter.task)
 158                         break;
 159                 schedule();
 160                 set_task_state(tsk, TASK_UNINTERRUPTIBLE);
 161         }
 162
 163         tsk->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         spin_lock_irqsave(&sem->wait_lock, flags);
 178
 179         if (sem->activity >= 0 && list_empty(&sem->wait_list)) {
 180                 /* granted */
 181                 sem->activity++;
 182                 ret = 1;
 183         }
 184
 185         spin_unlock_irqrestore(&sem->wait_lock, flags);
 186
 187         return ret;
 188 }
 189
 190 /*
 191  * get a write lock on the semaphore
 192  * - we increment the waiting count anyway to indicate an exclusive lock
 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
 199         spin_lock_irq(&sem->wait_lock);
 200
 201         if (sem->activity == 0 && list_empty(&sem->wait_list)) {
 202                 /* granted */
 203                 sem->activity = -1;
 204                 spin_unlock_irq(&sem->wait_lock);
 205                 goto out;
 206         }
 207
 208         tsk = current;
 209         set_task_state(tsk, TASK_UNINTERRUPTIBLE);
 210
 211         /* set up my own style of waitqueue */
 212         waiter.task = tsk;
 213         waiter.flags = RWSEM_WAITING_FOR_WRITE;
 214         get_task_struct(tsk);
 215
 216         list_add_tail(&waiter.list, &sem->wait_list);
 217
 218         /* we don't need to touch the semaphore struct anymore */
 219         spin_unlock_irq(&sem->wait_lock);
 220
 221         /* wait to be given the lock */
 222         for (;;) {
 223                 if (!waiter.task)
 224                         break;
 225                 schedule();
 226                 set_task_state(tsk, TASK_UNINTERRUPTIBLE);
 227         }
 228
 229         tsk->state = TASK_RUNNING;
 230  out:
 231         ;
 232 }
 233
 234 void __sched __down_write(struct rw_semaphore *sem)
 235 {
 236         __down_write_nested(sem, 0);
 237 }
 238
 239 /*
 240  * trylock for writing -- returns 1 if successful, 0 if contention
 241  */
 242 int __down_write_trylock(struct rw_semaphore *sem)
 243 {
 244         unsigned long flags;
 245         int ret = 0;
 246
 247         spin_lock_irqsave(&sem->wait_lock, flags);
 248
 249         if (sem->activity == 0 && list_empty(&sem->wait_list)) {
 250                 /* granted */
 251                 sem->activity = -1;
 252                 ret = 1;
 253         }
 254
 255         spin_unlock_irqrestore(&sem->wait_lock, flags);
 256
 257         return ret;
 258 }
 259
 260 /*
 261  * release a read lock on the semaphore
 262  */
 263 void __up_read(struct rw_semaphore *sem)
 264 {
 265         unsigned long flags;
 266
 267         spin_lock_irqsave(&sem->wait_lock, flags);
 268
 269         if (--sem->activity == 0 && !list_empty(&sem->wait_list))
 270                 sem = __rwsem_wake_one_writer(sem);
 271
 272         spin_unlock_irqrestore(&sem->wait_lock, flags);
 273 }
 274
 275 /*
 276  * release a write lock on the semaphore
 277  */
 278 void __up_write(struct rw_semaphore *sem)
 279 {
 280         unsigned long flags;
 281
 282         spin_lock_irqsave(&sem->wait_lock, flags);
 283
 284         sem->activity = 0;
 285         if (!list_empty(&sem->wait_list))
 286                 sem = __rwsem_do_wake(sem, 1);
 287
 288         spin_unlock_irqrestore(&sem->wait_lock, flags);
 289 }
 290
 291 /*
 292  * downgrade a write lock into a read lock
 293  * - just wake up any readers at the front of the queue
 294  */
 295 void __downgrade_write(struct rw_semaphore *sem)
 296 {
 297         unsigned long flags;
 298
 299         spin_lock_irqsave(&sem->wait_lock, flags);
 300
 301         sem->activity = 1;
 302         if (!list_empty(&sem->wait_list))
 303                 sem = __rwsem_do_wake(sem, 0);
 304
 305         spin_unlock_irqrestore(&sem->wait_lock, flags);
 306 }
 307
 308 EXPORT_SYMBOL(__init_rwsem);
 309 EXPORT_SYMBOL(__down_read);
 310 EXPORT_SYMBOL(__down_read_trylock);
 311 EXPORT_SYMBOL(__down_write_nested);
 312 EXPORT_SYMBOL(__down_write);
 313 EXPORT_SYMBOL(__down_write_trylock);
 314 EXPORT_SYMBOL(__up_read);
 315 EXPORT_SYMBOL(__up_write);
 316 EXPORT_SYMBOL(__downgrade_write);