arch/arm/kernel/semaphore.c

   1 /*
   2  *  ARM semaphore implementation, taken from
   3  *
   4  *  i386 semaphore implementation.
   5  *
   6  *  (C) Copyright 1999 Linus Torvalds
   7  *
   8  *  Modified for ARM by Russell King
   9  *
  10  * This program is free software; you can redistribute it and/or modify
  11  * it under the terms of the GNU General Public License version 2 as
  12  * published by the Free Software Foundation.
  13  */
  14 #include <linux/config.h>
  15 #include <linux/sched.h>
  16
  17 #include <asm/semaphore.h>
  18
  19 /*
  20  * Semaphores are implemented using a two-way counter:
  21  * The "count" variable is decremented for each process
  22  * that tries to acquire the semaphore, while the "sleeping"
  23  * variable is a count of such acquires.
  24  *
  25  * Notably, the inline "up()" and "down()" functions can
  26  * efficiently test if they need to do any extra work (up
  27  * needs to do something only if count was negative before
  28  * the increment operation.
  29  *
  30  * "sleeping" and the contention routine ordering is
  31  * protected by the semaphore spinlock.
  32  *
  33  * Note that these functions are only called when there is
  34  * contention on the lock, and as such all this is the
  35  * "non-critical" part of the whole semaphore business. The
  36  * critical part is the inline stuff in <asm/semaphore.h>
  37  * where we want to avoid any extra jumps and calls.
  38  */
  39
  40 /*
  41  * Logic:
  42  *  - only on a boundary condition do we need to care. When we go
  43  *    from a negative count to a non-negative, we wake people up.
  44  *  - when we go from a non-negative count to a negative do we
  45  *    (a) synchronize with the "sleeper" count and (b) make sure
  46  *    that we're on the wakeup list before we synchronize so that
  47  *    we cannot lose wakeup events.
  48  */
  49
  50 void __up(struct semaphore *sem)
  51 {
  52         wake_up(&sem->wait);
  53 }
  54
  55 static spinlock_t semaphore_lock = SPIN_LOCK_UNLOCKED;
  56
  57 void __down(struct semaphore * sem)
  58 {
  59         struct task_struct *tsk = current;
  60         DECLARE_WAITQUEUE(wait, tsk);
  61         tsk->state = TASK_UNINTERRUPTIBLE;
  62         add_wait_queue_exclusive(&sem->wait, &wait);
  63
  64         spin_lock_irq(&semaphore_lock);
  65         sem->sleepers++;
  66         for (;;) {
  67                 int sleepers = sem->sleepers;
  68
  69                 /*
  70                  * Add "everybody else" into it. They aren't
  71                  * playing, because we own the spinlock.
  72                  */
  73                 if (!atomic_add_negative(sleepers - 1, &sem->count)) {
  74                         sem->sleepers = 0;
  75                         break;
  76                 }
  77                 sem->sleepers = 1;      /* us - see -1 above */
  78                 spin_unlock_irq(&semaphore_lock);
  79
  80                 schedule();
  81                 tsk->state = TASK_UNINTERRUPTIBLE;
  82                 spin_lock_irq(&semaphore_lock);
  83         }
  84         spin_unlock_irq(&semaphore_lock);
  85         remove_wait_queue(&sem->wait, &wait);
  86         tsk->state = TASK_RUNNING;
  87         wake_up(&sem->wait);
  88 }
  89
  90 int __down_interruptible(struct semaphore * sem)
  91 {
  92         int retval = 0;
  93         struct task_struct *tsk = current;
  94         DECLARE_WAITQUEUE(wait, tsk);
  95         tsk->state = TASK_INTERRUPTIBLE;
  96         add_wait_queue_exclusive(&sem->wait, &wait);
  97
  98         spin_lock_irq(&semaphore_lock);
  99         sem->sleepers ++;
 100         for (;;) {
 101                 int sleepers = sem->sleepers;
 102
 103                 /*
 104                  * With signals pending, this turns into
 105                  * the trylock failure case - we won't be
 106                  * sleeping, and we* can't get the lock as
 107                  * it has contention. Just correct the count
 108                  * and exit.
 109                  */
 110                 if (signal_pending(current)) {
 111                         retval = -EINTR;
 112                         sem->sleepers = 0;
 113                         atomic_add(sleepers, &sem->count);
 114                         break;
 115                 }
 116
 117                 /*
 118                  * Add "everybody else" into it. They aren't
 119                  * playing, because we own the spinlock. The
 120                  * "-1" is because we're still hoping to get
 121                  * the lock.
 122                  */
 123                 if (!atomic_add_negative(sleepers - 1, &sem->count)) {
 124                         sem->sleepers = 0;
 125                         break;
 126                 }
 127                 sem->sleepers = 1;      /* us - see -1 above */
 128                 spin_unlock_irq(&semaphore_lock);
 129
 130                 schedule();
 131                 tsk->state = TASK_INTERRUPTIBLE;
 132                 spin_lock_irq(&semaphore_lock);
 133         }
 134         spin_unlock_irq(&semaphore_lock);
 135         tsk->state = TASK_RUNNING;
 136         remove_wait_queue(&sem->wait, &wait);
 137         wake_up(&sem->wait);
 138         return retval;
 139 }
 140
 141 /*
 142  * Trylock failed - make sure we correct for
 143  * having decremented the count.
 144  *
 145  * We could have done the trylock with a
 146  * single "cmpxchg" without failure cases,
 147  * but then it wouldn't work on a 386.
 148  */
 149 int __down_trylock(struct semaphore * sem)
 150 {
 151         int sleepers;
 152         unsigned long flags;
 153
 154         spin_lock_irqsave(&semaphore_lock, flags);
 155         sleepers = sem->sleepers + 1;
 156         sem->sleepers = 0;
 157
 158         /*
 159          * Add "everybody else" and us into it. They aren't
 160          * playing, because we own the spinlock.
 161          */
 162         if (!atomic_add_negative(sleepers, &sem->count))
 163                 wake_up(&sem->wait);
 164
 165         spin_unlock_irqrestore(&semaphore_lock, flags);
 166         return 1;
 167 }
 168
 169 struct rw_semaphore *down_read_failed_biased(struct rw_semaphore *sem)
 170 {
 171         struct task_struct *tsk = current;
 172         DECLARE_WAITQUEUE(wait, tsk);
 173
 174         add_wait_queue(&sem->wait, &wait);      /* put ourselves at the head of the list */
 175
 176         for (;;) {
 177                 if (sem->read_bias_granted && xchg(&sem->read_bias_granted, 0))
 178                         break;
 179                 set_task_state(tsk, TASK_UNINTERRUPTIBLE);
 180                 if (!sem->read_bias_granted)
 181                         schedule();
 182         }
 183
 184         remove_wait_queue(&sem->wait, &wait);
 185         tsk->state = TASK_RUNNING;
 186
 187         return sem;
 188 }
 189
 190 struct rw_semaphore *down_write_failed_biased(struct rw_semaphore *sem)
 191 {
 192         struct task_struct *tsk = current;
 193         DECLARE_WAITQUEUE(wait, tsk);
 194
 195         add_wait_queue_exclusive(&sem->write_bias_wait, &wait); /* put ourselves at the end of the list */
 196
 197         for (;;) {
 198                 if (sem->write_bias_granted && xchg(&sem->write_bias_granted, 0))
 199                         break;
 200                 set_task_state(tsk, TASK_UNINTERRUPTIBLE);
 201                 if (!sem->write_bias_granted)
 202                         schedule();
 203         }
 204
 205         remove_wait_queue(&sem->write_bias_wait, &wait);
 206         tsk->state = TASK_RUNNING;
 207
 208         /* if the lock is currently unbiased, awaken the sleepers
 209          * FIXME: this wakes up the readers early in a bit of a
 210          * stampede -> bad!
 211          */
 212         if (atomic_read(&sem->count) >= 0)
 213                 wake_up(&sem->wait);
 214
 215         return sem;
 216 }
 217
 218 /* Wait for the lock to become unbiased.  Readers
 219  * are non-exclusive. =)
 220  */
 221 struct rw_semaphore *down_read_failed(struct rw_semaphore *sem)
 222 {
 223         struct task_struct *tsk = current;
 224         DECLARE_WAITQUEUE(wait, tsk);
 225
 226         /* this takes care of granting the lock */
 227         __up_op_read(sem, __rwsem_wake);
 228
 229         add_wait_queue(&sem->wait, &wait);
 230
 231         while (atomic_read(&sem->count) < 0) {
 232                 set_task_state(tsk, TASK_UNINTERRUPTIBLE);
 233                 if (atomic_read(&sem->count) >= 0)
 234                         break;
 235                 schedule();
 236         }
 237
 238         remove_wait_queue(&sem->wait, &wait);
 239         tsk->state = TASK_RUNNING;
 240
 241         return sem;
 242 }
 243
 244 /* Wait for the lock to become unbiased. Since we're
 245  * a writer, we'll make ourselves exclusive.
 246  */
 247 struct rw_semaphore *down_write_failed(struct rw_semaphore *sem)
 248 {
 249         struct task_struct *tsk = current;
 250         DECLARE_WAITQUEUE(wait, tsk);
 251
 252         /* this takes care of granting the lock */
 253         __up_op_write(sem, __rwsem_wake);
 254
 255         add_wait_queue_exclusive(&sem->wait, &wait);
 256
 257         while (atomic_read(&sem->count) < 0) {
 258                 set_task_state(tsk, TASK_UNINTERRUPTIBLE);
 259                 if (atomic_read(&sem->count) >= 0)
 260                         break;  /* we must attempt to acquire or bias the lock */
 261                 schedule();
 262         }
 263
 264         remove_wait_queue(&sem->wait, &wait);
 265         tsk->state = TASK_RUNNING;
 266
 267         return sem;
 268 }
 269
 270 /* Called when someone has done an up that transitioned from
 271  * negative to non-negative, meaning that the lock has been
 272  * granted to whomever owned the bias.
 273  */
 274 struct rw_semaphore *rwsem_wake_readers(struct rw_semaphore *sem)
 275 {
 276         if (xchg(&sem->read_bias_granted, 1))
 277                 BUG();
 278         wake_up(&sem->wait);
 279         return sem;
 280 }
 281
 282 struct rw_semaphore *rwsem_wake_writer(struct rw_semaphore *sem)
 283 {
 284         if (xchg(&sem->write_bias_granted, 1))
 285                 BUG();
 286         wake_up(&sem->write_bias_wait);
 287         return sem;
 288 }
 289
 290 /*
 291  * The semaphore operations have a special calling sequence that
 292  * allow us to do a simpler in-line version of them. These routines
 293  * need to convert that sequence back into the C sequence when
 294  * there is contention on the semaphore.
 295  *
 296  * ip contains the semaphore pointer on entry. Save the C-clobbered
 297  * registers (r0 to r3 and lr), but not ip, as we use it as a return
 298  * value in some cases..
 299  */
 300 #ifdef CONFIG_CPU_26
 301 asm("   .section        .text.lock, \"ax\"
 302         .align  5
 303         .globl  __down_failed
 304 __down_failed:
 305         stmfd   sp!, {r0 - r3, lr}
 306         mov     r0, ip
 307         bl      __down
 308         ldmfd   sp!, {r0 - r3, pc}^
 309
 310         .align  5
 311         .globl  __down_interruptible_failed
 312 __down_interruptible_failed:
 313         stmfd   sp!, {r0 - r3, lr}
 314         mov     r0, ip
 315         bl      __down_interruptible
 316         mov     ip, r0
 317         ldmfd   sp!, {r0 - r3, pc}^
 318
 319         .align  5
 320         .globl  __down_trylock_failed
 321 __down_trylock_failed:
 322         stmfd   sp!, {r0 - r3, lr}
 323         mov     r0, ip
 324         bl      __down_trylock
 325         mov     ip, r0
 326         ldmfd   sp!, {r0 - r3, pc}^
 327
 328         .align  5
 329         .globl  __up_wakeup
 330 __up_wakeup:
 331         stmfd   sp!, {r0 - r3, lr}
 332         mov     r0, ip
 333         bl      __up
 334         ldmfd   sp!, {r0 - r3, pc}^
 335
 336         .align  5
 337         .globl  __down_read_failed
 338 __down_read_failed:
 339         stmfd   sp!, {r0 - r3, lr}
 340         mov     r0, ip
 341         bcc     1f
 342 1:      bl      down_read_failed_biased
 343         ldmfd   sp!, {r0 - r3, pc}^
 344 2:      bl      down_read_failed
 345         mov     r1, pc
 346         orr     r2, r1, #
 347         teqp r2, #0
 348
 349         ldr     r3, [r0]
 350         subs    r3, r3, #1
 351         str     r3, [r0]
 352         ldmplfd sp!, {r0 - r3, pc}^
 353   orrcs r1, r1, #0x20000000   @ Set carry
 354   teqp r1, #0
 355         bcc     2b
 356         b       1b
 357
 358         .align  5
 359         .globl  __down_write_failed
 360 __down_write_failed:
 361         stmfd   sp!, {r0 - r3, lr}
 362         mov     r0, ip
 363         bcc     1f
 364 1:      bl      down_write_failed_biased
 365         ldmfd   sp!, {r0 - r3, pc}^
 366 2:      bl      down_write_failed
 367         mov r1, pc
 368         orr     r2, r1, #128
 369         teqp r2, #0
 370
 371         ldr     r3, [r0]
 372         subs    r3, r3, #"RW_LOCK_BIAS_STR"
 373         str     r3, [r0]
 374         ldmeqfd sp!, {r0 - r3, pc}^
 375   orrcs r1, r1, #0x20000000   @ Set carry
 376         teqp r1, #0
 377         bcc     2b
 378         b       1b
 379
 380         .align  5
 381         .globl  __rwsem_wake
 382 __rwsem_wake:
 383         stmfd   sp!, {r0 - r3, lr}
 384         mov     r0, ip
 385         beq     1f
 386         bl      rwsem_wake_readers
 387         ldmfd   sp!, {r0 - r3, pc}^
 388 1:      bl      rwsem_wake_writer
 389         ldmfd   sp!, {r0 - r3, pc}^
 390
 391         .previous
 392         ");
 393
 394 #else
 395 /* 32 bit version */
 396 asm("   .section        .text.lock, \"ax\"
 397         .align  5
 398         .globl  __down_failed
 399 __down_failed:
 400         stmfd   sp!, {r0 - r3, lr}
 401         mov     r0, ip
 402         bl      __down
 403         ldmfd   sp!, {r0 - r3, pc}
 404
 405         .align  5
 406         .globl  __down_interruptible_failed
 407 __down_interruptible_failed:
 408         stmfd   sp!, {r0 - r3, lr}
 409         mov     r0, ip
 410         bl      __down_interruptible
 411         mov     ip, r0
 412         ldmfd   sp!, {r0 - r3, pc}
 413
 414         .align  5
 415         .globl  __down_trylock_failed
 416 __down_trylock_failed:
 417         stmfd   sp!, {r0 - r3, lr}
 418         mov     r0, ip
 419         bl      __down_trylock
 420         mov     ip, r0
 421         ldmfd   sp!, {r0 - r3, pc}
 422
 423         .align  5
 424         .globl  __up_wakeup
 425 __up_wakeup:
 426         stmfd   sp!, {r0 - r3, lr}
 427         mov     r0, ip
 428         bl      __up
 429         ldmfd   sp!, {r0 - r3, pc}
 430
 431         .align  5
 432         .globl  __down_read_failed
 433 __down_read_failed:
 434         stmfd   sp!, {r0 - r3, lr}
 435         mov     r0, ip
 436         bcc     1f
 437 1:      bl      down_read_failed_biased
 438         ldmfd   sp!, {r0 - r3, pc}
 439 2:      bl      down_read_failed
 440         mrs     r1, cpsr
 441         orr     r2, r1, #128
 442         msr     cpsr_c, r2
 443         ldr     r3, [r0]
 444         subs    r3, r3, #1
 445         str     r3, [r0]
 446         msr     cpsr_c, r1
 447         ldmplfd sp!, {r0 - r3, pc}
 448         bcc     2b
 449         b       1b
 450
 451         .align  5
 452         .globl  __down_write_failed
 453 __down_write_failed:
 454         stmfd   sp!, {r0 - r3, lr}
 455         mov     r0, ip
 456         bcc     1f
 457 1:      bl      down_write_failed_biased
 458         ldmfd   sp!, {r0 - r3, pc}
 459 2:      bl      down_write_failed
 460         mrs     r1, cpsr
 461         orr     r2, r1, #128
 462         msr     cpsr_c, r2
 463         ldr     r3, [r0]
 464         subs    r3, r3, #"RW_LOCK_BIAS_STR"
 465         str     r3, [r0]
 466         msr     cpsr_c, r1
 467         ldmeqfd sp!, {r0 - r3, pc}
 468         bcc     2b
 469         b       1b
 470
 471         .align  5
 472         .globl  __rwsem_wake
 473 __rwsem_wake:
 474         stmfd   sp!, {r0 - r3, lr}
 475         mov     r0, ip
 476         beq     1f
 477         bl      rwsem_wake_readers
 478         ldmfd   sp!, {r0 - r3, pc}
 479 1:      bl      rwsem_wake_writer
 480         ldmfd   sp!, {r0 - r3, pc}
 481
 482         .previous
 483         ");
 484
 485 #endif