SAFE public projects git trees. - safe/jmp/linux-2.6/blob - kernel/semaphore.c

   1 /*
   2  * Copyright (c) 2008 Intel Corporation
   3  * Author: Matthew Wilcox <willy@linux.intel.com>
   4  *
   5  * Distributed under the terms of the GNU GPL, version 2
   6  */
   7
   8 #include <linux/compiler.h>
   9 #include <linux/kernel.h>
  10 #include <linux/module.h>
  11 #include <linux/sched.h>
  12 #include <linux/semaphore.h>
  13 #include <linux/spinlock.h>
  14
  15 /*
  16  * Some notes on the implementation:
  17  *
  18  * down_trylock() and up() can be called from interrupt context.
  19  * So we have to disable interrupts when taking the lock.
  20  *
  21  * The ->count variable, if positive, defines how many more tasks can
  22  * acquire the semaphore.  If negative, it represents how many tasks are
  23  * waiting on the semaphore (*).  If zero, no tasks are waiting, and no more
  24  * tasks can acquire the semaphore.
  25  *
  26  * (*) Except for the window between one task calling up() and the task
  27  * sleeping in a __down_common() waking up.  In order to avoid a third task
  28  * coming in and stealing the second task's wakeup, we leave the ->count
  29  * negative.  If we have a more complex situation, the ->count may become
  30  * zero or negative (eg a semaphore with count = 2, three tasks attempt to
  31  * acquire it, one sleeps, two finish and call up(), the second task to call
  32  * up() notices that the list is empty and just increments count).
  33  */
  34
  35 static noinline void __down(struct semaphore *sem);
  36 static noinline int __down_interruptible(struct semaphore *sem);
  37 static noinline int __down_killable(struct semaphore *sem);
  38 static noinline void __up(struct semaphore *sem);
  39
  40 void down(struct semaphore *sem)
  41 {
  42         unsigned long flags;
  43
  44         spin_lock_irqsave(&sem->lock, flags);
  45         if (unlikely(sem->count-- <= 0))
  46                 __down(sem);
  47         spin_unlock_irqrestore(&sem->lock, flags);
  48 }
  49 EXPORT_SYMBOL(down);
  50
  51 int down_interruptible(struct semaphore *sem)
  52 {
  53         unsigned long flags;
  54         int result = 0;
  55
  56         spin_lock_irqsave(&sem->lock, flags);
  57         if (unlikely(sem->count-- <= 0))
  58                 result = __down_interruptible(sem);
  59         spin_unlock_irqrestore(&sem->lock, flags);
  60
  61         return result;
  62 }
  63 EXPORT_SYMBOL(down_interruptible);
  64
  65 int down_killable(struct semaphore *sem)
  66 {
  67         unsigned long flags;
  68         int result = 0;
  69
  70         spin_lock_irqsave(&sem->lock, flags);
  71         if (unlikely(sem->count-- <= 0))
  72                 result = __down_killable(sem);
  73         spin_unlock_irqrestore(&sem->lock, flags);
  74
  75         return result;
  76 }
  77 EXPORT_SYMBOL(down_killable);
  78
  79 /**
  80  * down_trylock - try to acquire the semaphore, without waiting
  81  * @sem: the semaphore to be acquired
  82  *
  83  * Try to acquire the semaphore atomically.  Returns 0 if the mutex has
  84  * been acquired successfully and 1 if it is contended.
  85  *
  86  * NOTE: This return value is inverted from both spin_trylock and
  87  * mutex_trylock!  Be careful about this when converting code.
  88  *
  89  * Unlike mutex_trylock, this function can be used from interrupt context,
  90  * and the semaphore can be released by any task or interrupt.
  91  */
  92 int down_trylock(struct semaphore *sem)
  93 {
  94         unsigned long flags;
  95         int count;
  96
  97         spin_lock_irqsave(&sem->lock, flags);
  98         count = sem->count - 1;
  99         if (likely(count >= 0))
 100                 sem->count = count;
 101         spin_unlock_irqrestore(&sem->lock, flags);
 102
 103         return (count < 0);
 104 }
 105 EXPORT_SYMBOL(down_trylock);
 106
 107 void up(struct semaphore *sem)
 108 {
 109         unsigned long flags;
 110
 111         spin_lock_irqsave(&sem->lock, flags);
 112         if (likely(sem->count >= 0))
 113                 sem->count++;
 114         else
 115                 __up(sem);
 116         spin_unlock_irqrestore(&sem->lock, flags);
 117 }
 118 EXPORT_SYMBOL(up);
 119
 120 /* Functions for the contended case */
 121
 122 struct semaphore_waiter {
 123         struct list_head list;
 124         struct task_struct *task;
 125         int up;
 126 };
 127
 128 /*
 129  * Wake up a process waiting on a semaphore.  We need to call this from both
 130  * __up and __down_common as it's possible to race a task into the semaphore
 131  * if it comes in at just the right time between two tasks calling up() and
 132  * a third task waking up.  This function assumes the wait_list is already
 133  * checked for being non-empty.
 134  */
 135 static noinline void __sched __up_down_common(struct semaphore *sem)
 136 {
 137         struct semaphore_waiter *waiter = list_first_entry(&sem->wait_list,
 138                                                 struct semaphore_waiter, list);
 139         list_del(&waiter->list);
 140         waiter->up = 1;
 141         wake_up_process(waiter->task);
 142 }
 143
 144 /*
 145  * Because this function is inlined, the 'state' parameter will be constant,
 146  * and thus optimised away by the compiler.
 147  */
 148 static inline int __sched __down_common(struct semaphore *sem, long state)
 149 {
 150         int result = 0;
 151         struct task_struct *task = current;
 152         struct semaphore_waiter waiter;
 153
 154         list_add_tail(&waiter.list, &sem->wait_list);
 155         waiter.task = task;
 156         waiter.up = 0;
 157
 158         for (;;) {
 159                 if (state == TASK_INTERRUPTIBLE && signal_pending(task))
 160                         goto interrupted;
 161                 if (state == TASK_KILLABLE && fatal_signal_pending(task))
 162                         goto interrupted;
 163                 __set_task_state(task, state);
 164                 spin_unlock_irq(&sem->lock);
 165                 schedule();
 166                 spin_lock_irq(&sem->lock);
 167                 if (waiter.up)
 168                         goto woken;
 169         }
 170
 171  interrupted:
 172         list_del(&waiter.list);
 173         result = -EINTR;
 174  woken:
 175         /*
 176          * Account for the process which woke us up.  For the case where
 177          * we're interrupted, we need to increment the count on our own
 178          * behalf.  I don't believe we can hit the case where the
 179          * sem->count hits zero, *and* there's a second task sleeping,
 180          * but it doesn't hurt, that's not a commonly exercised path and
 181          * it's not a performance path either.
 182          */
 183         if (unlikely((++sem->count >= 0) && !list_empty(&sem->wait_list)))
 184                 __up_down_common(sem);
 185         return result;
 186 }
 187
 188 static noinline void __sched __down(struct semaphore *sem)
 189 {
 190         __down_common(sem, TASK_UNINTERRUPTIBLE);
 191 }
 192
 193 static noinline int __sched __down_interruptible(struct semaphore *sem)
 194 {
 195         return __down_common(sem, TASK_INTERRUPTIBLE);
 196 }
 197
 198 static noinline int __sched __down_killable(struct semaphore *sem)
 199 {
 200         return __down_common(sem, TASK_KILLABLE);
 201 }
 202
 203 static noinline void __sched __up(struct semaphore *sem)
 204 {
 205         if (unlikely(list_empty(&sem->wait_list)))
 206                 sem->count++;
 207         else
 208                 __up_down_common(sem);
 209 }