Changeset 4774a32 in mainline


Ignore:
Timestamp:
2009-12-01T21:27:37Z (14 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.

Files:
5 edited

Legend:

Unmodified
Added
Removed

  • kernel/generic/include/synch/futex.h

    r4af185f r4774a32  
    5252
    5353extern void futex_init(void);
    54 extern unative_t sys_futex_sleep_timeout(uintptr_t, uint32_t, int);
     54extern unative_t sys_futex_sleep(uintptr_t);
    5555extern unative_t sys_futex_wakeup(uintptr_t);
    5656

  • kernel/generic/src/synch/futex.c

    r4af185f r4774a32  
    9090/** Initialize kernel futex structure.
    9191 *
    92  * @param futex Kernel futex structure.
     92 * @param futex         Kernel futex structure.
    9393 */
    9494void futex_initialize(futex_t *futex)
    … …  
    102102/** Sleep in futex wait queue.
    103103 *
    104  * @param uaddr Userspace address of the futex counter.
    105  * @param usec If non-zero, number of microseconds this thread is willing to
    106  *     sleep.
    107  * @param flags Select mode of operation.
    108  *
    109  * @return One of ESYNCH_TIMEOUT, ESYNCH_OK_ATOMIC and ESYNCH_OK_BLOCKED. See
    110  *     synch.h. If there is no physical mapping for uaddr ENOENT is returned.
    111  */
    112 unative_t sys_futex_sleep_timeout(uintptr_t uaddr, uint32_t usec, int flags)
     104 * @param uaddr         Userspace address of the futex counter.
     105 *
     106 * @return              If there is no physical mapping for uaddr ENOENT is
     107 *                      returned. Otherwise returns a wait result as defined in
     108 *                      synch.h.
     109 */
     110unative_t sys_futex_sleep(uintptr_t uaddr)
    113111{
    114112        futex_t *futex;
    … …  
    140138        udebug_stoppable_begin();
    141139#endif
    142         rc = waitq_sleep_timeout(&futex->wq, usec, flags |
    143             SYNCH_FLAGS_INTERRUPTIBLE);
    144 
     140        rc = waitq_sleep_timeout(&futex->wq, 0, SYNCH_FLAGS_INTERRUPTIBLE);
    145141#ifdef CONFIG_UDEBUG
    146142        udebug_stoppable_end();
    … …  
    151147/** Wakeup one thread waiting in futex wait queue.
    152148 *
    153  * @param uaddr Userspace address of the futex counter.
    154  *
    155  * @return ENOENT if there is no physical mapping for uaddr.
     149 * @param uaddr         Userspace address of the futex counter.
     150 *
     151 * @return              ENOENT if there is no physical mapping for uaddr.
    156152 */
    157153unative_t sys_futex_wakeup(uintptr_t uaddr)
    … …  
    190186 * If the structure does not exist already, a new one is created.
    191187 *
    192  * @param paddr Physical address of the userspace futex counter.
    193  *
    194  * @return Address of the kernel futex structure.
     188 * @param paddr         Physical address of the userspace futex counter.
     189 *
     190 * @return              Address of the kernel futex structure.
    195191 */
    196192futex_t *futex_find(uintptr_t paddr)
    … …  
    284280/** Compute hash index into futex hash table.
    285281 *
    286  * @param key Address where the key (i.e. physical address of futex counter) is
    287  *    stored.
    288  *
    289  * @return Index into futex hash table.
     282 * @param key           Address where the key (i.e. physical address of futex
     283 *                      counter) is stored.
     284 *
     285 * @return              Index into futex hash table.
    290286 */
    291287size_t futex_ht_hash(unative_t *key)
    … …  
    296292/** Compare futex hash table item with a key.
    297293 *
    298  * @param key Address where the key (i.e. physical address of futex counter) is
    299  *    stored.
    300  *
    301  * @return True if the item matches the key. False otherwise.
     294 * @param key           Address where the key (i.e. physical address of futex
     295 *                      counter) is stored.
     296 *
     297 * @return              True if the item matches the key. False otherwise.
    302298 */
    303299bool futex_ht_compare(unative_t *key, size_t keys, link_t *item)
    … …  
    313309/** Callback for removal items from futex hash table.
    314310 *
    315  * @param item Item removed from the hash table.
     311 * @param item          Item removed from the hash table.
    316312 */
    317313void futex_ht_remove_callback(link_t *item)

  • kernel/generic/src/syscall/syscall.c

    r4af185f r4774a32  
    118118       
    119119        /* Synchronization related syscalls. */
    120         (syshandler_t) sys_futex_sleep_timeout,
     120        (syshandler_t) sys_futex_sleep,
    121121        (syshandler_t) sys_futex_wakeup,
    122122        (syshandler_t) sys_smc_coherence,

  • 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               

  • uspace/lib/libc/include/futex.h

    r4af185f r4774a32  
    4646extern int futex_down(futex_t *futex);
    4747extern int futex_trydown(futex_t *futex);
    48 extern int futex_down_timeout(futex_t *futex, uint32_t usec, int flags);
    4948extern int futex_up(futex_t *futex);
    5049
Note: See TracChangeset for help on using the changeset viewer.