Changeset 4774a32 in mainline for uspace/lib/libc/generic/futex.c


Ignore:
Timestamp:
2009-12-01T21:27:37Z (15 years ago)
Author:
Jakub Jermar <jakub@…>
Branches:
lfn, master, serial, ticket/834-toolchain-update, topic/msim-upgrade, topic/simplify-dev-export
Children:
eae4e8f
Parents:
4af185f
Message:

Greatly simplify futexes.
Drop timeout support.

File:
1 edited

Legend:

Unmodified
Added
Removed

  • uspace/lib/libc/generic/futex.c

    r4af185f r4774a32  
    3636#include <atomic.h>
    3737#include <libc.h>
    38 #include <stdio.h>
    3938#include <sys/types.h>
    40 #include <kernel/synch/synch.h>
    41 
    42 /*
    43  * Note about race conditions.
    44  * Because of non-atomic nature of operations performed sequentially on the
    45  * futex counter and the futex wait queue, there is a race condition:
    46  *
    47  * (wq->missed_wakeups == 1) && (futex->count = 1)
    48  *
    49  * Scenario 1 (wait queue timeout vs. futex_up()):
    50  * 1. assume wq->missed_wakeups == 0 && futex->count == -1
    51  *    (ie. thread A sleeping, thread B in the critical section)
    52  * 2. A receives timeout and gets removed from the wait queue
    53  * 3. B wants to leave the critical section and calls futex_up()
    54  * 4. B thus changes futex->count from -1 to 0
    55  * 5. B has to call SYS_FUTEX_WAKEUP syscall to wake up the sleeping thread
    56  * 6. B finds the wait queue empty and changes wq->missed_wakeups from 0 to 1
    57  * 7. A fixes futex->count (i.e. the number of waiting threads) by changing it
    58  *    from 0 to 1
    59  *
    60  * Scenario 2 (conditional down operation vs. futex_up)
    61  * 1. assume wq->missed_wakeups == 0 && futex->count == 0
    62  *    (i.e. thread A is in the critical section)
    63  * 2. thread B performs futex_trydown() operation and changes futex->count from
    64  *    0 to -1
    65  *    B is now obliged to call SYS_FUTEX_SLEEP syscall
    66  * 3. A wants to leave the critical section and does futex_up()
    67  * 4. A thus changes futex->count from -1 to 0 and must call SYS_FUTEX_WAKEUP
    68  *    syscall
    69  * 5. B finds the wait queue empty and immediatelly aborts the conditional sleep
    70  * 6. No thread is queueing in the wait queue so wq->missed_wakeups changes from
    71  *    0 to 1
    72  * 6. B fixes futex->count (i.e. the number of waiting threads) by changing it
    73  *    from 0 to 1
    74  *
    75  * Both scenarios allow two threads to be in the critical section
    76  * simultaneously. One without kernel intervention and the other through
    77  * wq->missed_wakeups being 1.
    78  *
    79  * To mitigate this problem, futex_down_timeout() detects that the syscall
    80  * didn't sleep in the wait queue, fixes the futex counter and RETRIES the
    81  * whole operation again.
    82  */
    8339
    8440/** Initialize futex counter.
    … …  
    9248}
    9349
    94 int futex_down(futex_t *futex)
    95 {
    96         return futex_down_timeout(futex, SYNCH_NO_TIMEOUT, SYNCH_FLAGS_NONE);
    97 }
    98 
    99 int futex_trydown(futex_t *futex)
    100 {
    101         return futex_down_timeout(futex, SYNCH_NO_TIMEOUT,
    102             SYNCH_FLAGS_NON_BLOCKING);
    103 }
    104 
    10550/** Try to down the futex.
    10651 *
    10752 * @param futex         Futex.
    108  * @param usec          Microseconds to wait. Zero value means sleep without
    109  *                      timeout.
    110  * @param flags         Select mode of operation. See comment for
    111  *                      waitq_sleep_timeout().
     53 * @return              Non-zero if the futex was acquired.
     54 * @return              Zero if the futex was not acquired.
     55 */
     56int futex_trydown(futex_t *futex)
     57{
     58        return cas(futex, 1, 0);
     59}
     60
     61/** Down the futex.
    11262 *
    113  * @return              ENOENT if there is no such virtual address. One of
    114  *                      ESYNCH_OK_ATOMIC and ESYNCH_OK_BLOCKED on success or
    115  *                      ESYNCH_TIMEOUT if the lock was not acquired because of
    116  *                      a timeout or ESYNCH_WOULD_BLOCK if the operation could
    117  *                      not be carried out atomically (if requested so).
     63 * @param futex         Futex.
     64 * @return              ENOENT if there is no such virtual address.
     65 * @return              Zero in the uncontended case.
     66 * @return              Otherwise one of ESYNCH_OK_ATOMIC or ESYNCH_OK_BLOCKED.
    11867 */
    119 int futex_down_timeout(futex_t *futex, uint32_t usec, int flags)
     68int futex_down(futex_t *futex)
    12069{
    121         int rc;
    122        
    123         while (atomic_predec(futex) < 0) {
    124                 rc = __SYSCALL3(SYS_FUTEX_SLEEP, (sysarg_t) &futex->count,
    125                     (sysarg_t) usec, (sysarg_t) flags);
    126                
    127                 switch (rc) {
    128                 case ESYNCH_OK_ATOMIC:
    129                         /*
    130                          * Because of a race condition between timeout and
    131                          * futex_up() and between conditional
    132                          * futex_down_timeout() and futex_up(), we have to give
    133                          * up and try again in this special case.
    134                          */
    135                         atomic_inc(futex);
    136                         break;
     70        if (atomic_predec(futex) < 0)
     71                return __SYSCALL1(SYS_FUTEX_SLEEP, (sysarg_t) &futex->count);
    13772
    138                 case ESYNCH_TIMEOUT:
    139                         atomic_inc(futex);
    140                         return ESYNCH_TIMEOUT;
    141                         break;
    142 
    143                 case ESYNCH_WOULD_BLOCK:
    144                         /*
    145                          * The conditional down operation should be implemented
    146                          * this way. The userspace-only variant tends to
    147                          * accumulate missed wakeups in the kernel futex wait
    148                          * queue.
    149                          */
    150                         atomic_inc(futex);
    151                         return ESYNCH_WOULD_BLOCK;
    152                         break;
    153 
    154                 case ESYNCH_OK_BLOCKED:
    155                         /*
    156                          * Enter the critical section.
    157                          * The futex counter has already been incremented for
    158                          * us.
    159                          */
    160                         return ESYNCH_OK_BLOCKED;
    161                         break;
    162                 default:
    163                         return rc;
    164                 }
    165         }
    166 
    167         /*
    168          * Enter the critical section.
    169          */
    170         return ESYNCH_OK_ATOMIC;
     73        return 0;
    17174}
    17275
    … …  
    17477 *
    17578 * @param futex         Futex.
    176  *
    177  * @return              ENOENT if there is no such virtual address. Otherwise
    178  *                      zero.
     79 * @return              ENOENT if there is no such virtual address.
     80 * @return              Zero in the uncontended case.
    17981 */
    18082int futex_up(futex_t *futex)
    18183{
    182         long val;
    183        
    184         val = atomic_postinc(futex);
    185         if (val < 0)
     84        if (atomic_postinc(futex) < 0)
    18685                return __SYSCALL1(SYS_FUTEX_WAKEUP, (sysarg_t) &futex->count);
    18786               
Note: See TracChangeset for help on using the changeset viewer.