lib/rwsem.c

   1 /* rwsem.c: R/W semaphores: contention handling functions
   2  *
   3  * Written by David Howells (dhowells@redhat.com).
   4  * Derived from arch/i386/kernel/semaphore.c
   5  */
   6 #include <linux/rwsem.h>
   7 #include <linux/sched.h>
   8 #include <linux/init.h>
   9 #include <linux/module.h>
  10
  11 struct rwsem_waiter {
  12         struct list_head list;
  13         struct task_struct *task;
  14         unsigned int flags;
  15 #define RWSEM_WAITING_FOR_READ  0x00000001
  16 #define RWSEM_WAITING_FOR_WRITE 0x00000002
  17 };
  18
  19 #if RWSEM_DEBUG
  20 #undef rwsemtrace
  21 void rwsemtrace(struct rw_semaphore *sem, const char *str)
  22 {
  23         printk("sem=%p\n", sem);
  24         printk("(sem)=%08lx\n", sem->count);
  25         if (sem->debug)
  26                 printk("[%d] %s({%08lx})\n", current->pid, str, sem->count);
  27 }
  28 #endif
  29
  30 /*
  31  * handle the lock release when processes blocked on it that can now run
  32  * - if we come here from up_xxxx(), then:
  33  *   - the 'active part' of count (&0x0000ffff) reached 0 (but may have changed)
  34  *   - the 'waiting part' of count (&0xffff0000) is -ve (and will still be so)
  35  *   - there must be someone on the queue
  36  * - the spinlock must be held by the caller
  37  * - woken process blocks are discarded from the list after having task zeroed
  38  * - writers are only woken if downgrading is false
  39  */
  40 static inline struct rw_semaphore *
  41 __rwsem_do_wake(struct rw_semaphore *sem, int downgrading)
  42 {
  43         struct rwsem_waiter *waiter;
  44         struct task_struct *tsk;
  45         struct list_head *next;
  46         signed long oldcount, woken, loop;
  47
  48         rwsemtrace(sem, "Entering __rwsem_do_wake");
  49
  50         if (downgrading)
  51                 goto dont_wake_writers;
  52
  53         /* if we came through an up_xxxx() call, we only only wake someone up
  54          * if we can transition the active part of the count from 0 -> 1
  55          */
  56  try_again:
  57         oldcount = rwsem_atomic_update(RWSEM_ACTIVE_BIAS, sem)
  58                                                 - RWSEM_ACTIVE_BIAS;
  59         if (oldcount & RWSEM_ACTIVE_MASK)
  60                 goto undo;
  61
  62         waiter = list_entry(sem->wait_list.next, struct rwsem_waiter, list);
  63
  64         /* try to grant a single write lock if there's a writer at the front
  65          * of the queue - note we leave the 'active part' of the count
  66          * incremented by 1 and the waiting part incremented by 0x00010000
  67          */
  68         if (!(waiter->flags & RWSEM_WAITING_FOR_WRITE))
  69                 goto readers_only;
  70
  71         /* We must be careful not to touch 'waiter' after we set ->task = NULL.
  72          * It is an allocated on the waiter's stack and may become invalid at
  73          * any time after that point (due to a wakeup from another source).
  74          */
  75         list_del(&waiter->list);
  76         tsk = waiter->task;
  77         mb();
  78         waiter->task = NULL;
  79         wake_up_process(tsk);
  80         put_task_struct(tsk);
  81         goto out;
  82
  83         /* don't want to wake any writers */
  84  dont_wake_writers:
  85         waiter = list_entry(sem->wait_list.next, struct rwsem_waiter, list);
  86         if (waiter->flags & RWSEM_WAITING_FOR_WRITE)
  87                 goto out;
  88
  89         /* grant an infinite number of read locks to the readers at the front
  90          * of the queue
  91          * - note we increment the 'active part' of the count by the number of
  92          *   readers before waking any processes up
  93          */
  94  readers_only:
  95         woken = 0;
  96         do {
  97                 woken++;
  98
  99                 if (waiter->list.next == &sem->wait_list)
 100                         break;
 101
 102                 waiter = list_entry(waiter->list.next,
 103                                         struct rwsem_waiter, list);
 104
 105         } while (waiter->flags & RWSEM_WAITING_FOR_READ);
 106
 107         loop = woken;
 108         woken *= RWSEM_ACTIVE_BIAS - RWSEM_WAITING_BIAS;
 109         if (!downgrading)
 110                 /* we'd already done one increment earlier */
 111                 woken -= RWSEM_ACTIVE_BIAS;
 112
 113         rwsem_atomic_add(woken, sem);
 114
 115         next = sem->wait_list.next;
 116         for (; loop > 0; loop--) {
 117                 waiter = list_entry(next, struct rwsem_waiter, list);
 118                 next = waiter->list.next;
 119                 tsk = waiter->task;
 120                 mb();
 121                 waiter->task = NULL;
 122                 wake_up_process(tsk);
 123                 put_task_struct(tsk);
 124         }
 125
 126         sem->wait_list.next = next;
 127         next->prev = &sem->wait_list;
 128
 129  out:
 130         rwsemtrace(sem, "Leaving __rwsem_do_wake");
 131         return sem;
 132
 133         /* undo the change to count, but check for a transition 1->0 */
 134  undo:
 135         if (rwsem_atomic_update(-RWSEM_ACTIVE_BIAS, sem) != 0)
 136                 goto out;
 137         goto try_again;
 138 }
 139
 140 /*
 141  * wait for a lock to be granted
 142  */
 143 static inline struct rw_semaphore *
 144 rwsem_down_failed_common(struct rw_semaphore *sem,
 145                         struct rwsem_waiter *waiter, signed long adjustment)
 146 {
 147         struct task_struct *tsk = current;
 148         signed long count;
 149
 150         set_task_state(tsk, TASK_UNINTERRUPTIBLE);
 151
 152         /* set up my own style of waitqueue */
 153         spin_lock(&sem->wait_lock);
 154         waiter->task = tsk;
 155         get_task_struct(tsk);
 156
 157         list_add_tail(&waiter->list, &sem->wait_list);
 158
 159         /* we're now waiting on the lock, but no longer actively read-locking */
 160         count = rwsem_atomic_update(adjustment, sem);
 161
 162         /* if there are no active locks, wake the front queued process(es) up */
 163         if (!(count & RWSEM_ACTIVE_MASK))
 164                 sem = __rwsem_do_wake(sem, 0);
 165
 166         spin_unlock(&sem->wait_lock);
 167
 168         /* wait to be given the lock */
 169         for (;;) {
 170                 if (!waiter->task)
 171                         break;
 172                 schedule();
 173                 set_task_state(tsk, TASK_UNINTERRUPTIBLE);
 174         }
 175
 176         tsk->state = TASK_RUNNING;
 177
 178         return sem;
 179 }
 180
 181 /*
 182  * wait for the read lock to be granted
 183  */
 184 struct rw_semaphore fastcall __sched *
 185 rwsem_down_read_failed(struct rw_semaphore *sem)
 186 {
 187         struct rwsem_waiter waiter;
 188
 189         rwsemtrace(sem, "Entering rwsem_down_read_failed");
 190
 191         waiter.flags = RWSEM_WAITING_FOR_READ;
 192         rwsem_down_failed_common(sem, &waiter,
 193                                 RWSEM_WAITING_BIAS - RWSEM_ACTIVE_BIAS);
 194
 195         rwsemtrace(sem, "Leaving rwsem_down_read_failed");
 196         return sem;
 197 }
 198
 199 /*
 200  * wait for the write lock to be granted
 201  */
 202 struct rw_semaphore fastcall __sched *
 203 rwsem_down_write_failed(struct rw_semaphore *sem)
 204 {
 205         struct rwsem_waiter waiter;
 206
 207         rwsemtrace(sem, "Entering rwsem_down_write_failed");
 208
 209         waiter.flags = RWSEM_WAITING_FOR_WRITE;
 210         rwsem_down_failed_common(sem, &waiter, -RWSEM_ACTIVE_BIAS);
 211
 212         rwsemtrace(sem, "Leaving rwsem_down_write_failed");
 213         return sem;
 214 }
 215
 216 /*
 217  * handle waking up a waiter on the semaphore
 218  * - up_read/up_write has decremented the active part of count if we come here
 219  */
 220 struct rw_semaphore fastcall *rwsem_wake(struct rw_semaphore *sem)
 221 {
 222         rwsemtrace(sem, "Entering rwsem_wake");
 223
 224         spin_lock(&sem->wait_lock);
 225
 226         /* do nothing if list empty */
 227         if (!list_empty(&sem->wait_list))
 228                 sem = __rwsem_do_wake(sem, 0);
 229
 230         spin_unlock(&sem->wait_lock);
 231
 232         rwsemtrace(sem, "Leaving rwsem_wake");
 233
 234         return sem;
 235 }
 236
 237 /*
 238  * downgrade a write lock into a read lock
 239  * - caller incremented waiting part of count and discovered it still negative
 240  * - just wake up any readers at the front of the queue
 241  */
 242 struct rw_semaphore fastcall *rwsem_downgrade_wake(struct rw_semaphore *sem)
 243 {
 244         rwsemtrace(sem, "Entering rwsem_downgrade_wake");
 245
 246         spin_lock(&sem->wait_lock);
 247
 248         /* do nothing if list empty */
 249         if (!list_empty(&sem->wait_list))
 250                 sem = __rwsem_do_wake(sem, 1);
 251
 252         spin_unlock(&sem->wait_lock);
 253
 254         rwsemtrace(sem, "Leaving rwsem_downgrade_wake");
 255         return sem;
 256 }
 257
 258 EXPORT_SYMBOL(rwsem_down_read_failed);
 259 EXPORT_SYMBOL(rwsem_down_write_failed);
 260 EXPORT_SYMBOL(rwsem_wake);
 261 EXPORT_SYMBOL(rwsem_downgrade_wake);
 262 #if RWSEM_DEBUG
 263 EXPORT_SYMBOL(rwsemtrace);
 264 #endif