1/* 2 * i386 semaphore implementation. 3 * 4 * (C) Copyright 1999 Linus Torvalds 5 * 6 * Portions Copyright 1999 Red Hat, Inc. 7 * 8 * This program is free software; you can redistribute it and/or 9 * modify it under the terms of the GNU General Public License 10 * as published by the Free Software Foundation; either version 11 * 2 of the License, or (at your option) any later version. 12 * 13 * rw semaphores implemented November 1999 by Benjamin LaHaise <bcrl@redhat.com> 14 */ 15#include <linux/config.h> 16#include <linux/sched.h> 17#include <asm/semaphore.h> 18#include <asm/kernprof.h> 19 20/* 21 * Semaphores are implemented using a two-way counter: 22 * The "count" variable is decremented for each process 23 * that tries to acquire the semaphore, while the "sleeping" 24 * variable is a count of such acquires. 25 * 26 * Notably, the inline "up()" and "down()" functions can 27 * efficiently test if they need to do any extra work (up 28 * needs to do something only if count was negative before 29 * the increment operation. 30 * 31 * "sleeping" and the contention routine ordering is 32 * protected by the semaphore spinlock. 33 * 34 * Note that these functions are only called when there is 35 * contention on the lock, and as such all this is the 36 * "non-critical" part of the whole semaphore business. The 37 * critical part is the inline stuff in <asm/semaphore.h> 38 * where we want to avoid any extra jumps and calls. 39 */ 40 41/* 42 * Logic: 43 * - only on a boundary condition do we need to care. When we go 44 * from a negative count to a non-negative, we wake people up. 45 * - when we go from a non-negative count to a negative do we 46 * (a) synchronize with the "sleeper" count and (b) make sure 47 * that we're on the wakeup list before we synchronize so that 48 * we cannot lose wakeup events. 49 */ 50 51void __up(struct semaphore *sem) 52{ 53 wake_up(&sem->wait); 54} 55 56static spinlock_t semaphore_lock = SPIN_LOCK_UNLOCKED; 57 58void __down(struct semaphore * sem) 59{ 60 struct task_struct *tsk = current; 61 DECLARE_WAITQUEUE(wait, tsk); 62 tsk->state = TASK_UNINTERRUPTIBLE; 63 add_wait_queue_exclusive(&sem->wait, &wait); 64 65 spin_lock_irq(&semaphore_lock); 66 sem->sleepers++; 67 for (;;) { 68 int sleepers = sem->sleepers; 69 70 /* 71 * Add "everybody else" into it. They aren't 72 * playing, because we own the spinlock. 73 */ 74 if (!atomic_add_negative(sleepers - 1, &sem->count)) { 75 sem->sleepers = 0; 76 break; 77 } 78 sem->sleepers = 1; /* us - see -1 above */ 79 spin_unlock_irq(&semaphore_lock); 80 81 schedule(); 82 tsk->state = TASK_UNINTERRUPTIBLE; 83 spin_lock_irq(&semaphore_lock); 84 } 85 spin_unlock_irq(&semaphore_lock); 86 remove_wait_queue(&sem->wait, &wait); 87 tsk->state = TASK_RUNNING; 88 wake_up(&sem->wait); 89} 90 91int __down_interruptible(struct semaphore * sem) 92{ 93 int retval = 0; 94 struct task_struct *tsk = current; 95 DECLARE_WAITQUEUE(wait, tsk); 96 tsk->state = TASK_INTERRUPTIBLE; 97 add_wait_queue_exclusive(&sem->wait, &wait); 98 99 spin_lock_irq(&semaphore_lock); 100 sem->sleepers ++; 101 for (;;) { 102 int sleepers = sem->sleepers; 103 104 /* 105 * With signals pending, this turns into 106 * the trylock failure case - we won't be 107 * sleeping, and we* can't get the lock as 108 * it has contention. Just correct the count 109 * and exit. 110 */ 111 if (signal_pending(current)) { 112 retval = -EINTR; 113 sem->sleepers = 0; 114 atomic_add(sleepers, &sem->count); 115 break; 116 } 117 118 /* 119 * Add "everybody else" into it. They aren't 120 * playing, because we own the spinlock. The 121 * "-1" is because we're still hoping to get 122 * the lock. 123 */ 124 if (!atomic_add_negative(sleepers - 1, &sem->count)) { 125 sem->sleepers = 0; 126 break; 127 } 128 sem->sleepers = 1; /* us - see -1 above */ 129 spin_unlock_irq(&semaphore_lock); 130 131 schedule(); 132 tsk->state = TASK_INTERRUPTIBLE; 133 spin_lock_irq(&semaphore_lock); 134 } 135 spin_unlock_irq(&semaphore_lock); 136 tsk->state = TASK_RUNNING; 137 remove_wait_queue(&sem->wait, &wait); 138 wake_up(&sem->wait); 139 return retval; 140} 141 142/* 143 * Trylock failed - make sure we correct for 144 * having decremented the count. 145 * 146 * We could have done the trylock with a 147 * single "cmpxchg" without failure cases, 148 * but then it wouldn't work on a 386. 149 */ 150int __down_trylock(struct semaphore * sem) 151{ 152 int sleepers; 153 unsigned long flags; 154 155 spin_lock_irqsave(&semaphore_lock, flags); 156 sleepers = sem->sleepers + 1; 157 sem->sleepers = 0; 158 159 /* 160 * Add "everybody else" and us into it. They aren't 161 * playing, because we own the spinlock. 162 */ 163 if (!atomic_add_negative(sleepers, &sem->count)) 164 wake_up(&sem->wait); 165 166 spin_unlock_irqrestore(&semaphore_lock, flags); 167 return 1; 168} 169 170 171/* 172 * The semaphore operations have a special calling sequence that 173 * allow us to do a simpler in-line version of them. These routines 174 * need to convert that sequence back into the C sequence when 175 * there is contention on the semaphore. 176 * 177 * %ecx contains the semaphore pointer on entry. Save the C-clobbered 178 * registers (%eax, %edx and %ecx) except %eax when used as a return 179 * value.. 180 */ 181asm( 182".text\n" 183".align 4\n" 184".globl __down_failed\n" 185"__down_failed:\n\t" 186 MCOUNT_STEXT_LOCK"\n\t" 187#if defined(CONFIG_FRAME_POINTER) 188 "pushl %ebp\n\t" 189 "movl %esp,%ebp\n\t" 190#endif 191 "pushl %eax\n\t" 192 "pushl %edx\n\t" 193 "pushl %ecx\n\t" 194 "call __down\n\t" 195 "popl %ecx\n\t" 196 "popl %edx\n\t" 197 "popl %eax\n\t" 198#if defined(CONFIG_FRAME_POINTER) 199 "movl %ebp,%esp\n\t" 200 "popl %ebp\n\t" 201#endif 202 "ret" 203); 204 205asm( 206".text\n" 207".align 4\n" 208".globl __down_failed_interruptible\n" 209"__down_failed_interruptible:\n\t" 210 MCOUNT_STEXT_LOCK"\n\t" 211#if defined(CONFIG_FRAME_POINTER) 212 "pushl %ebp\n\t" 213 "movl %esp,%ebp\n\t" 214#endif 215 "pushl %edx\n\t" 216 "pushl %ecx\n\t" 217 "call __down_interruptible\n\t" 218 "popl %ecx\n\t" 219 "popl %edx\n\t" 220#if defined(CONFIG_FRAME_POINTER) 221 "movl %ebp,%esp\n\t" 222 "popl %ebp\n\t" 223#endif 224 "ret" 225); 226 227asm( 228".text\n" 229".align 4\n" 230".globl __down_failed_trylock\n" 231"__down_failed_trylock:\n\t" 232 MCOUNT_STEXT_LOCK"\n\t" 233#if defined(CONFIG_FRAME_POINTER) 234 "pushl %ebp\n\t" 235 "movl %esp,%ebp\n\t" 236#endif 237 "pushl %edx\n\t" 238 "pushl %ecx\n\t" 239 "call __down_trylock\n\t" 240 "popl %ecx\n\t" 241 "popl %edx\n\t" 242#if defined(CONFIG_FRAME_POINTER) 243 "movl %ebp,%esp\n\t" 244 "popl %ebp\n\t" 245#endif 246 "ret" 247); 248 249asm( 250".text\n" 251".align 4\n" 252".globl __up_wakeup\n" 253"__up_wakeup:\n\t" 254 MCOUNT_STEXT_LOCK"\n\t" 255 "pushl %eax\n\t" 256 "pushl %edx\n\t" 257 "pushl %ecx\n\t" 258 "call __up\n\t" 259 "popl %ecx\n\t" 260 "popl %edx\n\t" 261 "popl %eax\n\t" 262 "ret" 263); 264 265/* 266 * rw spinlock fallbacks 267 */ 268#if defined(CONFIG_SMP) 269asm( 270".text\n" 271".align 4\n" 272".globl __write_lock_failed\n" 273"__write_lock_failed:\n\t" 274 LOCK "addl $" RW_LOCK_BIAS_STR ",(%eax)\n" 275"1: rep; nop\n\t" 276 "cmpl $" RW_LOCK_BIAS_STR ",(%eax)\n\t" 277 "jne 1b\n\t" 278 LOCK "subl $" RW_LOCK_BIAS_STR ",(%eax)\n\t" 279 "jnz __write_lock_failed\n\t" 280 "ret" 281); 282 283asm( 284".text\n" 285".align 4\n" 286".globl __read_lock_failed\n" 287"__read_lock_failed:\n\t" 288 LOCK "incl (%eax)\n" 289"1: rep; nop\n\t" 290 "cmpl $1,(%eax)\n\t" 291 "js 1b\n\t" 292 LOCK "decl (%eax)\n\t" 293 "js __read_lock_failed\n\t" 294 "ret" 295); 296#endif 297