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 #if RWSEM_DEBUG
  21 void rwsemtrace(struct rw_semaphore *sem, const char *str)
  22 {
  23         if (sem->debug)
  24                 printk("[%d] %s({%d,%d})\n",
  25                        current->pid, str, sem->activity,
  26                        list_empty(&sem->wait_list) ? 0 : 1);
  27 }
  28 #endif
  29
  30 /*
  31  * initialise the semaphore
  32  */
  33 void fastcall init_rwsem(struct rw_semaphore *sem)
  34 {
  35         sem->activity = 0;
  36         spin_lock_init(&sem->wait_lock);
  37         INIT_LIST_HEAD(&sem->wait_list);
  38 #if RWSEM_DEBUG
  39         sem->debug = 0;
  40 #endif
  41 }
  42
  43 /*
  44  * handle the lock release when processes blocked on it that can now run
  45  * - if we come here, then:
  46  *   - the 'active count' _reached_ zero
  47  *   - the 'waiting count' is non-zero
  48  * - the spinlock must be held by the caller
  49  * - woken process blocks are discarded from the list after having task zeroed
  50  * - writers are only woken if wakewrite is non-zero
  51  */
  52 static inline struct rw_semaphore *
  53 __rwsem_do_wake(struct rw_semaphore *sem, int wakewrite)
  54 {
  55         struct rwsem_waiter *waiter;
  56         struct task_struct *tsk;
  57         int woken;
  58
  59         rwsemtrace(sem, "Entering __rwsem_do_wake");
  60
  61         waiter = list_entry(sem->wait_list.next, struct rwsem_waiter, list);
  62
  63         if (!wakewrite) {
  64                 if (waiter->flags & RWSEM_WAITING_FOR_WRITE)
  65                         goto out;
  66                 goto dont_wake_writers;
  67         }
  68
  69         /* if we are allowed to wake writers try to grant a single write lock
  70          * if there's a writer at the front of the queue
  71          * - we leave the 'waiting count' incremented to signify potential
  72          *   contention
  73          */
  74         if (waiter->flags & RWSEM_WAITING_FOR_WRITE) {
  75                 sem->activity = -1;
  76                 list_del(&waiter->list);
  77                 tsk = waiter->task;
  78                 /* Don't touch waiter after ->task has been NULLed */
  79                 mb();
  80                 waiter->task = NULL;
  81                 wake_up_process(tsk);
  82                 put_task_struct(tsk);
  83                 goto out;
  84         }
  85
  86         /* grant an infinite number of read locks to the front of the queue */
  87  dont_wake_writers:
  88         woken = 0;
  89         while (waiter->flags & RWSEM_WAITING_FOR_READ) {
  90                 struct list_head *next = waiter->list.next;
  91
  92                 list_del(&waiter->list);
  93                 tsk = waiter->task;
  94                 mb();
  95                 waiter->task = NULL;
  96                 wake_up_process(tsk);
  97                 put_task_struct(tsk);
  98                 woken++;
  99                 if (list_empty(&sem->wait_list))
 100                         break;
 101                 waiter = list_entry(next, struct rwsem_waiter, list);
 102         }
 103
 104         sem->activity += woken;
 105
 106  out:
 107         rwsemtrace(sem, "Leaving __rwsem_do_wake");
 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         struct task_struct *tsk;
 119
 120         sem->activity = -1;
 121
 122         waiter = list_entry(sem->wait_list.next, struct rwsem_waiter, list);
 123         list_del(&waiter->list);
 124
 125         tsk = waiter->task;
 126         mb();
 127         waiter->task = NULL;
 128         wake_up_process(tsk);
 129         put_task_struct(tsk);
 130         return sem;
 131 }
 132
 133 /*
 134  * get a read lock on the semaphore
 135  */
 136 void fastcall __sched __down_read(struct rw_semaphore *sem)
 137 {
 138         struct rwsem_waiter waiter;
 139         struct task_struct *tsk;
 140
 141         rwsemtrace(sem, "Entering __down_read");
 142
 143         spin_lock(&sem->wait_lock);
 144
 145         if (sem->activity >= 0 && list_empty(&sem->wait_list)) {
 146                 /* granted */
 147                 sem->activity++;
 148                 spin_unlock(&sem->wait_lock);
 149                 goto out;
 150         }
 151
 152         tsk = current;
 153         set_task_state(tsk, TASK_UNINTERRUPTIBLE);
 154
 155         /* set up my own style of waitqueue */
 156         waiter.task = tsk;
 157         waiter.flags = RWSEM_WAITING_FOR_READ;
 158         get_task_struct(tsk);
 159
 160         list_add_tail(&waiter.list, &sem->wait_list);
 161
 162         /* we don't need to touch the semaphore struct anymore */
 163         spin_unlock(&sem->wait_lock);
 164
 165         /* wait to be given the lock */
 166         for (;;) {
 167                 if (!waiter.task)
 168                         break;
 169                 schedule();
 170                 set_task_state(tsk, TASK_UNINTERRUPTIBLE);
 171         }
 172
 173         tsk->state = TASK_RUNNING;
 174
 175  out:
 176         rwsemtrace(sem, "Leaving __down_read");
 177 }
 178
 179 /*
 180  * trylock for reading -- returns 1 if successful, 0 if contention
 181  */
 182 int fastcall __down_read_trylock(struct rw_semaphore *sem)
 183 {
 184         int ret = 0;
 185         rwsemtrace(sem, "Entering __down_read_trylock");
 186
 187         spin_lock(&sem->wait_lock);
 188
 189         if (sem->activity >= 0 && list_empty(&sem->wait_list)) {
 190                 /* granted */
 191                 sem->activity++;
 192                 ret = 1;
 193         }
 194
 195         spin_unlock(&sem->wait_lock);
 196
 197         rwsemtrace(sem, "Leaving __down_read_trylock");
 198         return ret;
 199 }
 200
 201 /*
 202  * get a write lock on the semaphore
 203  * - we increment the waiting count anyway to indicate an exclusive lock
 204  */
 205 void fastcall __sched __down_write(struct rw_semaphore *sem)
 206 {
 207         struct rwsem_waiter waiter;
 208         struct task_struct *tsk;
 209
 210         rwsemtrace(sem, "Entering __down_write");
 211
 212         spin_lock(&sem->wait_lock);
 213
 214         if (sem->activity == 0 && list_empty(&sem->wait_list)) {
 215                 /* granted */
 216                 sem->activity = -1;
 217                 spin_unlock(&sem->wait_lock);
 218                 goto out;
 219         }
 220
 221         tsk = current;
 222         set_task_state(tsk, TASK_UNINTERRUPTIBLE);
 223
 224         /* set up my own style of waitqueue */
 225         waiter.task = tsk;
 226         waiter.flags = RWSEM_WAITING_FOR_WRITE;
 227         get_task_struct(tsk);
 228
 229         list_add_tail(&waiter.list, &sem->wait_list);
 230
 231         /* we don't need to touch the semaphore struct anymore */
 232         spin_unlock(&sem->wait_lock);
 233
 234         /* wait to be given the lock */
 235         for (;;) {
 236                 if (!waiter.task)
 237                         break;
 238                 schedule();
 239                 set_task_state(tsk, TASK_UNINTERRUPTIBLE);
 240         }
 241
 242         tsk->state = TASK_RUNNING;
 243
 244  out:
 245         rwsemtrace(sem, "Leaving __down_write");
 246 }
 247
 248 /*
 249  * trylock for writing -- returns 1 if successful, 0 if contention
 250  */
 251 int fastcall __down_write_trylock(struct rw_semaphore *sem)
 252 {
 253         int ret = 0;
 254         rwsemtrace(sem, "Entering __down_write_trylock");
 255
 256         spin_lock(&sem->wait_lock);
 257
 258         if (sem->activity == 0 && list_empty(&sem->wait_list)) {
 259                 /* granted */
 260                 sem->activity = -1;
 261                 ret = 1;
 262         }
 263
 264         spin_unlock(&sem->wait_lock);
 265
 266         rwsemtrace(sem, "Leaving __down_write_trylock");
 267         return ret;
 268 }
 269
 270 /*
 271  * release a read lock on the semaphore
 272  */
 273 void fastcall __up_read(struct rw_semaphore *sem)
 274 {
 275         rwsemtrace(sem, "Entering __up_read");
 276
 277         spin_lock(&sem->wait_lock);
 278
 279         if (--sem->activity == 0 && !list_empty(&sem->wait_list))
 280                 sem = __rwsem_wake_one_writer(sem);
 281
 282         spin_unlock(&sem->wait_lock);
 283
 284         rwsemtrace(sem, "Leaving __up_read");
 285 }
 286
 287 /*
 288  * release a write lock on the semaphore
 289  */
 290 void fastcall __up_write(struct rw_semaphore *sem)
 291 {
 292         rwsemtrace(sem, "Entering __up_write");
 293
 294         spin_lock(&sem->wait_lock);
 295
 296         sem->activity = 0;
 297         if (!list_empty(&sem->wait_list))
 298                 sem = __rwsem_do_wake(sem, 1);
 299
 300         spin_unlock(&sem->wait_lock);
 301
 302         rwsemtrace(sem, "Leaving __up_write");
 303 }
 304
 305 /*
 306  * downgrade a write lock into a read lock
 307  * - just wake up any readers at the front of the queue
 308  */
 309 void fastcall __downgrade_write(struct rw_semaphore *sem)
 310 {
 311         rwsemtrace(sem, "Entering __downgrade_write");
 312
 313         spin_lock(&sem->wait_lock);
 314
 315         sem->activity = 1;
 316         if (!list_empty(&sem->wait_list))
 317                 sem = __rwsem_do_wake(sem, 0);
 318
 319         spin_unlock(&sem->wait_lock);
 320
 321         rwsemtrace(sem, "Leaving __downgrade_write");
 322 }
 323
 324 EXPORT_SYMBOL(init_rwsem);
 325 EXPORT_SYMBOL(__down_read);
 326 EXPORT_SYMBOL(__down_read_trylock);
 327 EXPORT_SYMBOL(__down_write);
 328 EXPORT_SYMBOL(__down_write_trylock);
 329 EXPORT_SYMBOL(__up_read);
 330 EXPORT_SYMBOL(__up_write);
 331 EXPORT_SYMBOL(__downgrade_write);
 332 #if RWSEM_DEBUG
 333 EXPORT_SYMBOL(rwsemtrace);
 334 #endif