Subversion Repositories HelenOS-historic

Rev

Rev 1114 | Rev 1152 | Go to most recent revision | Show entire file | Ignore whitespace | Details | Blame | Last modification | View Log | RSS feed

Rev 1114 Rev 1116
Line 28... Line 28...
28 
 
 28 
 
29 
#include <futex.h>
 29 
#include <futex.h>
30 
#include <atomic.h>
 30 
#include <atomic.h>
31 
#include <libc.h>
 31 
#include <libc.h>
32 
#include <stdio.h>
 32 
#include <stdio.h>
- 
 
 33 
#include <types.h>
- 
 
 34 
#include <kernel/synch/synch.h>
33 
 
 35 
 
- 
 
 36 
/*
- 
 
 37 
 * Note about race conditions.
- 
 
 38 
 * Because of non-atomic nature of operations performed sequentially on the futex
- 
 
 39 
 * counter and the futex wait queue, there is a race condition:
- 
 
 40 
 *
- 
 
 41 
 * wq->missed_wakeups == 1 && futex->count = 1
- 
 
 42 
 *
- 
 
 43 
 * Scenario 1 (wait queue timeout vs. futex_up()):
- 
 
 44 
 * 1. assume wq->missed_wakeups == 0 && futex->count == -1
- 
 
 45 
 *    (ie. thread A sleeping, thread B in the critical section)
- 
 
 46 
 * 2. A receives timeout and gets removed from the wait queue
- 
 
 47 
 * 3. B wants to leave the critical section and calls futex_up()
- 
 
 48 
 * 4. B thus changes futex->count from -1 to 0
- 
 
 49 
 * 5. B has to call SYS_FUTEX_WAKEUP syscall to wake up the sleeping thread
- 
 
 50 
 * 6. B finds the wait queue empty and changes wq->missed_wakeups from 0 to 1
- 
 
 51 
 * 7. A fixes futex->count (i.e. the number of waiting threads) by changing it from 0 to 1
- 
 
 52 
 *
- 
 
 53 
 * Scenario 2 (conditional down operation vs. futex_up)
- 
 
 54 
 * 1. assume wq->missed_wakeups == 0 && futex->count == 0
- 
 
 55 
 *    (i.e. thread A is in the critical section)
- 
 
 56 
 * 2. thread B performs futex_trydown() operation and changes futex->count from 0 to -1
- 
 
 57 
 *    B is now obliged to call SYS_FUTEX_SLEEP syscall
- 
 
 58 
 * 3. A wants to leave the critical section and does futex_up()
- 
 
 59 
 * 4. A thus changes futex->count from -1 to 0 and must call SYS_FUTEX_WAKEUP syscall
- 
 
 60 
 * 5. B finds the wait queue empty and immediatelly aborts the conditional sleep
- 
 
 61 
 * 6. No thread is queueing in the wait queue so wq->missed_wakeups changes from 0 to 1
- 
 
 62 
 * 6. B fixes futex->count (i.e. the number of waiting threads) by changing it from 0 to 1
- 
 
 63 
 *
- 
 
 64 
 * Both scenarios allow two threads to be in the critical section simultaneously.
- 
 
 65 
 * One without kernel intervention and the other through wq->missed_wakeups being 1.
- 
 
 66 
 *
- 
 
 67 
 * To mitigate this problem, futex_down_timeout() detects that the syscall didn't sleep
- 
 
 68 
 * in the wait queue, fixes the futex counter and RETRIES the whole operation again.
- 
 
 69 
 *
- 
 
 70 
 */
- 
 
 71 
 
- 
 
 72 
/** Initialize futex counter.
- 
 
 73 
 *
- 
 
 74 
 * @param futex Futex.
- 
 
 75 
 * @param val Initialization value.
- 
 
 76 
 */
34 
void futex_initialize(atomic_t *futex, int val)
 77 
void futex_initialize(atomic_t *futex, int val)
35 
{
 78 
{
36 
    atomic_set(futex, val);
 79 
    atomic_set(futex, val);
37 
}
 80 
}
38 
 
 81 
 
39 
int futex_down(atomic_t *futex)
 82 
int futex_down(atomic_t *futex)
40 
{
 83 
{
- 
 
 84 
    return futex_down_timeout(futex, SYNCH_NO_TIMEOUT, SYNCH_BLOCKING);
- 
 
 85 
}
- 
 
 86 
 
- 
 
 87 
int futex_trydown(atomic_t *futex)
- 
 
 88 
{
- 
 
 89 
    return futex_down_timeout(futex, SYNCH_NO_TIMEOUT, SYNCH_NON_BLOCKING);
- 
 
 90 
}
- 
 
 91 
 
- 
 
 92 
/** Try to down the futex.
- 
 
 93 
 *
- 
 
 94 
 * @param futex Futex.
- 
 
 95 
 * @param usec Microseconds to wait. Zero value means sleep without timeout.
- 
 
 96 
 * @param trydown If usec is zero and trydown is non-zero, only conditional
- 
 
 97 
 *
- 
 
 98 
 * @return ENOENT if there is no such virtual address. One of ESYNCH_OK_ATOMIC
- 
 
 99 
 *     and ESYNCH_OK_BLOCKED on success or ESYNCH_TIMEOUT if the lock was
- 
 
 100 
 *     not acquired because of a timeout or ESYNCH_WOULD_BLOCK if the
- 
 
 101 
 *     operation could not be carried out atomically (if requested so).
- 
 
 102 
 */
- 
 
 103 
int futex_down_timeout(atomic_t *futex, uint32_t usec, int trydown)
- 
 
 104 
{
41 
    long val;
 105 
    int rc;
42 
   
 106 
   
43 
    val = atomic_predec(futex);
 107 
    while (atomic_predec(futex) < 0) {
44 
    if (val < 0)
 - 
 
45 
        return __SYSCALL1(SYS_FUTEX_SLEEP, (sysarg_t) &futex->count);
 108 
        rc = __SYSCALL3(SYS_FUTEX_SLEEP, (sysarg_t) &futex->count, (sysarg_t) usec, (sysarg_t) trydown);
46 
       
 109 
       
- 
 
 110 
        switch (rc) {
- 
 
 111 
        case ESYNCH_OK_ATOMIC:
- 
 
 112 
            /*
- 
 
 113 
             * Because of a race condition between timeout and futex_up()
- 
 
 114 
             * and between conditional futex_down_timeout() and futex_up(),
- 
 
 115 
             * we have to give up and try again in this special case.
- 
 
 116 
             */
- 
 
 117 
            atomic_inc(futex);
- 
 
 118 
            break;
- 
 
 119 
 
- 
 
 120 
        case ESYNCH_TIMEOUT:
- 
 
 121 
            atomic_inc(futex);
- 
 
 122 
            return ESYNCH_TIMEOUT;
- 
 
 123 
            break;
- 
 
 124 
 
- 
 
 125 
        case ESYNCH_WOULD_BLOCK:
- 
 
 126 
            /*
- 
 
 127 
             * The conditional down operation should be implemented this way.
- 
 
 128 
             * The userspace-only variant tends to accumulate missed wakeups
- 
 
 129 
             * in the kernel futex wait queue.
- 
 
 130 
             */
- 
 
 131 
            atomic_inc(futex);
- 
 
 132 
            return ESYNCH_WOULD_BLOCK;
- 
 
 133 
            break;
- 
 
 134 
 
- 
 
 135 
        case ESYNCH_OK_BLOCKED:
- 
 
 136 
            /*
- 
 
 137 
             * Enter the critical section.
- 
 
 138 
             * The futex counter has already been incremented for us.
- 
 
 139 
             */
- 
 
 140 
            return ESYNCH_OK_BLOCKED;
- 
 
 141 
            break;
- 
 
 142 
        default:
47 
    return 0;
 143 
            return rc;
- 
 
 144 
        }
- 
 
 145 
    }
- 
 
 146 
 
- 
 
 147 
    /*
- 
 
 148 
     * Enter the critical section.
- 
 
 149 
     */
- 
 
 150 
    return ESYNCH_OK_ATOMIC;
48 
}
 151 
}
49 
 
 152 
 
- 
 
 153 
/** Up the futex.
- 
 
 154 
 *
- 
 
 155 
 * @param futex Futex.
- 
 
 156 
 *
- 
 
 157 
 * @return ENOENT if there is no such virtual address or futex. Otherwise zero.
- 
 
 158 
 */
50 
int futex_up(atomic_t *futex)
 159 
int futex_up(atomic_t *futex)
51 
{
 160 
{
52 
    long val;
 161 
    long val;
53 
   
 162 
   
54 
    val = atomic_postinc(futex);
 163 
    val = atomic_postinc(futex);