lib/rwsem-spinlock.c

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