futex.c

Go to the documentation of this file.
00001 /*
00002  * Copyright (C) 2006 Jakub Jermar
00003  * All rights reserved.
00004  *
00005  * Redistribution and use in source and binary forms, with or without
00006  * modification, are permitted provided that the following conditions
00007  * are met:
00008  *
00009  * - Redistributions of source code must retain the above copyright
00010  *   notice, this list of conditions and the following disclaimer.
00011  * - Redistributions in binary form must reproduce the above copyright
00012  *   notice, this list of conditions and the following disclaimer in the
00013  *   documentation and/or other materials provided with the distribution.
00014  * - The name of the author may not be used to endorse or promote products
00015  *   derived from this software without specific prior written permission.
00016  *
00017  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
00018  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
00019  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
00020  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
00021  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
00022  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
00023  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
00024  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
00025  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
00026  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
00027  */
00028 
00035 #include <futex.h>
00036 #include <atomic.h>
00037 #include <libc.h>
00038 #include <stdio.h>
00039 #include <types.h>
00040 #include <kernel/synch/synch.h>
00041 
00042 /*
00043  * Note about race conditions.
00044  * Because of non-atomic nature of operations performed sequentially on the futex
00045  * counter and the futex wait queue, there is a race condition:
00046  *
00047  * (wq->missed_wakeups == 1) && (futex->count = 1)
00048  *
00049  * Scenario 1 (wait queue timeout vs. futex_up()):
00050  * 1. assume wq->missed_wakeups == 0 && futex->count == -1
00051  *    (ie. thread A sleeping, thread B in the critical section)
00052  * 2. A receives timeout and gets removed from the wait queue
00053  * 3. B wants to leave the critical section and calls futex_up()
00054  * 4. B thus changes futex->count from -1 to 0
00055  * 5. B has to call SYS_FUTEX_WAKEUP syscall to wake up the sleeping thread
00056  * 6. B finds the wait queue empty and changes wq->missed_wakeups from 0 to 1
00057  * 7. A fixes futex->count (i.e. the number of waiting threads) by changing it from 0 to 1
00058  *
00059  * Scenario 2 (conditional down operation vs. futex_up)
00060  * 1. assume wq->missed_wakeups == 0 && futex->count == 0
00061  *    (i.e. thread A is in the critical section)
00062  * 2. thread B performs futex_trydown() operation and changes futex->count from 0 to -1
00063  *    B is now obliged to call SYS_FUTEX_SLEEP syscall
00064  * 3. A wants to leave the critical section and does futex_up()
00065  * 4. A thus changes futex->count from -1 to 0 and must call SYS_FUTEX_WAKEUP syscall
00066  * 5. B finds the wait queue empty and immediatelly aborts the conditional sleep
00067  * 6. No thread is queueing in the wait queue so wq->missed_wakeups changes from 0 to 1
00068  * 6. B fixes futex->count (i.e. the number of waiting threads) by changing it from 0 to 1
00069  *
00070  * Both scenarios allow two threads to be in the critical section simultaneously.
00071  * One without kernel intervention and the other through wq->missed_wakeups being 1.
00072  *
00073  * To mitigate this problem, futex_down_timeout() detects that the syscall didn't sleep
00074  * in the wait queue, fixes the futex counter and RETRIES the whole operation again.
00075  *
00076  */
00077 
00083 void futex_initialize(atomic_t *futex, int val)
00084 {
00085         atomic_set(futex, val);
00086 }
00087 
00088 int futex_down(atomic_t *futex)
00089 {
00090         return futex_down_timeout(futex, SYNCH_NO_TIMEOUT, SYNCH_FLAGS_NONE);
00091 }
00092 
00093 int futex_trydown(atomic_t *futex)
00094 {
00095         return futex_down_timeout(futex, SYNCH_NO_TIMEOUT, SYNCH_FLAGS_NON_BLOCKING);
00096 }
00097 
00109 int futex_down_timeout(atomic_t *futex, uint32_t usec, int flags)
00110 {
00111         int rc;
00112         
00113         while (atomic_predec(futex) < 0) {
00114                 rc = __SYSCALL3(SYS_FUTEX_SLEEP, (sysarg_t) &futex->count, (sysarg_t) usec, (sysarg_t) flags);
00115                 
00116                 switch (rc) {
00117                 case ESYNCH_OK_ATOMIC:
00118                         /*
00119                          * Because of a race condition between timeout and futex_up()
00120                          * and between conditional futex_down_timeout() and futex_up(),
00121                          * we have to give up and try again in this special case.
00122                          */
00123                         atomic_inc(futex);
00124                         break;
00125 
00126                 case ESYNCH_TIMEOUT:
00127                         atomic_inc(futex);
00128                         return ESYNCH_TIMEOUT;
00129                         break;
00130 
00131                 case ESYNCH_WOULD_BLOCK:
00132                         /*
00133                          * The conditional down operation should be implemented this way.
00134                          * The userspace-only variant tends to accumulate missed wakeups
00135                          * in the kernel futex wait queue.
00136                          */
00137                         atomic_inc(futex);
00138                         return ESYNCH_WOULD_BLOCK;
00139                         break;
00140 
00141                 case ESYNCH_OK_BLOCKED:
00142                         /*
00143                          * Enter the critical section.
00144                          * The futex counter has already been incremented for us.
00145                          */
00146                         return ESYNCH_OK_BLOCKED;
00147                         break;
00148                 default:
00149                         return rc;
00150                 }
00151         }
00152 
00153         /*
00154          * Enter the critical section.
00155          */
00156         return ESYNCH_OK_ATOMIC;
00157 }
00158 
00165 int futex_up(atomic_t *futex)
00166 {
00167         long val;
00168         
00169         val = atomic_postinc(futex);
00170         if (val < 0)
00171                 return __SYSCALL1(SYS_FUTEX_WAKEUP, (sysarg_t) &futex->count);
00172                 
00173         return 0;
00174 }
00175 
00176 

Generated on Sun Jun 18 18:00:18 2006 for HelenOS Userspace (ia64) by  doxygen 1.4.6