From 40188718f232423c6e28922e39ea6e9c10eb444b Mon Sep 17 00:00:00 2001 From: Sebastian Huber Date: Mon, 13 Jul 2015 10:00:28 +0200 Subject: score: Add self-contained futex implementation --- cpukit/libmisc/monitor/mon-prmisc.c | 1 + cpukit/score/Makefile.am | 1 + cpukit/score/include/rtems/score/statesimpl.h | 3 + cpukit/score/src/futex.c | 199 +++++++++++++++++++++++++ testsuites/sptests/spsyslock01/init.c | 74 +++++++++ testsuites/sptests/spsyslock01/spsyslock01.doc | 5 + 6 files changed, 283 insertions(+) create mode 100644 cpukit/score/src/futex.c diff --git a/cpukit/libmisc/monitor/mon-prmisc.c b/cpukit/libmisc/monitor/mon-prmisc.c index 4656ed297a..14ba173256 100644 --- a/cpukit/libmisc/monitor/mon-prmisc.c +++ b/cpukit/libmisc/monitor/mon-prmisc.c @@ -134,6 +134,7 @@ static const rtems_assoc_t rtems_monitor_state_assoc[] = { { "Wseg", STATES_WAITING_FOR_SEGMENT, 0 }, { "Wsem", STATES_WAITING_FOR_SEMAPHORE, 0 }, { "Wsig", STATES_WAITING_FOR_SIGNAL, 0 }, + { "Wslftx", STATES_WAITING_FOR_SYS_LOCK_FUTEX, 0 }, { "Wslmtx", STATES_WAITING_FOR_SYS_LOCK_MUTEX, 0 }, { "Wslsem", STATES_WAITING_FOR_SYS_LOCK_SEMAPHORE, 0 }, { "Wsysev", STATES_WAITING_FOR_SYSTEM_EVENT, 0 }, diff --git a/cpukit/score/Makefile.am b/cpukit/score/Makefile.am index 4b4c1f5fce..460076c6a9 100644 --- a/cpukit/score/Makefile.am +++ b/cpukit/score/Makefile.am @@ -345,6 +345,7 @@ libscore_a_SOURCES += src/apiext.c src/chain.c src/chainappend.c \ src/interr.c src/isr.c src/wkspace.c src/wkstringduplicate.c libscore_a_SOURCES += src/isrisinprogress.c libscore_a_SOURCES += src/debugisownerofallocator.c +libscore_a_SOURCES += src/futex.c libscore_a_SOURCES += src/profilingisrentryexit.c libscore_a_SOURCES += src/mutex.c libscore_a_SOURCES += src/once.c diff --git a/cpukit/score/include/rtems/score/statesimpl.h b/cpukit/score/include/rtems/score/statesimpl.h index 7805ca4c9b..82d222c490 100644 --- a/cpukit/score/include/rtems/score/statesimpl.h +++ b/cpukit/score/include/rtems/score/statesimpl.h @@ -90,6 +90,8 @@ extern "C" { #define STATES_WAITING_FOR_SYS_LOCK_MUTEX 0x2000000 /** This macro corresponds to a task waiting for a semaphore. */ #define STATES_WAITING_FOR_SYS_LOCK_SEMAPHORE 0x4000000 +/** This macro corresponds to a task waiting for a futex. */ +#define STATES_WAITING_FOR_SYS_LOCK_FUTEX 0x8000000 /** This macro corresponds to a task which is in an interruptible * blocking state. @@ -109,6 +111,7 @@ extern "C" { STATES_WAITING_FOR_BSD_WAKEUP | \ STATES_WAITING_FOR_SYS_LOCK_MUTEX | \ STATES_WAITING_FOR_SYS_LOCK_SEMAPHORE | \ + STATES_WAITING_FOR_SYS_LOCK_FUTEX | \ STATES_WAITING_FOR_RWLOCK ) /** This macro corresponds to a task waiting which is blocked. */ diff --git a/cpukit/score/src/futex.c b/cpukit/score/src/futex.c new file mode 100644 index 0000000000..2ec38a3747 --- /dev/null +++ b/cpukit/score/src/futex.c @@ -0,0 +1,199 @@ +/* + * Copyright (c) 2015 embedded brains GmbH. All rights reserved. + * + * embedded brains GmbH + * Dornierstr. 4 + * 82178 Puchheim + * Germany + * + * + * The license and distribution terms for this file may be + * found in the file LICENSE in this distribution or at + * http://www.rtems.org/license/LICENSE. + */ + +#if HAVE_CONFIG_H + #include "config.h" +#endif + +#if HAVE_STRUCT__THREAD_QUEUE_QUEUE + +#include +#include + +#include +#include +#include +#include + +#define FUTEX_TQ_OPERATIONS &_Thread_queue_Operations_FIFO + +typedef struct { + Thread_queue_Syslock_queue Queue; +} Futex_Control; + +RTEMS_STATIC_ASSERT( + offsetof( Futex_Control, Queue ) + == offsetof( struct _Futex_Control, _Queue ), + FUTEX_CONTROL_QUEUE +); + +RTEMS_STATIC_ASSERT( + sizeof( Futex_Control ) == sizeof( struct _Futex_Control ), + FUTEX_CONTROL_SIZE +); + +static Futex_Control *_Futex_Get( struct _Futex_Control *_futex ) +{ + return (Futex_Control *) _futex; +} + +static Thread_Control *_Futex_Queue_acquire( + Futex_Control *futex, + ISR_lock_Context *lock_context +) +{ + Thread_Control *executing; + + _ISR_lock_ISR_disable( lock_context ); + executing = _Thread_Executing; + _Thread_queue_Queue_acquire_critical( + &futex->Queue.Queue, + &executing->Potpourri_stats, + lock_context + ); + + return executing; +} + +static void _Futex_Queue_release( + Futex_Control *futex, + ISR_lock_Context *lock_context +) +{ + _Thread_queue_Queue_release( &futex->Queue.Queue, lock_context ); +} + +int _Futex_Wait( struct _Futex_Control *_futex, int *uaddr, int val ) +{ + Futex_Control *futex; + ISR_lock_Context lock_context; + Thread_Control *executing; + int eno; + + futex = _Futex_Get( _futex ); + executing = _Futex_Queue_acquire( futex, &lock_context ); + + if ( *uaddr == val ) { + _Thread_queue_Enqueue_critical( + &futex->Queue.Queue, + FUTEX_TQ_OPERATIONS, + executing, + STATES_WAITING_FOR_SYS_LOCK_FUTEX, + 0, + 0, + &lock_context + ); + eno = 0; + } else { + _Futex_Queue_release( futex, &lock_context ); + eno = EWOULDBLOCK; + } + + return eno; +} + +/* + * Use a noinline function to force the compiler to set up and tear down the + * large stack frame only in the slow case. + */ +static __attribute__((noinline)) int _Futex_Wake_slow( + Futex_Control *futex, + int count, + Thread_queue_Heads *heads, + ISR_lock_Context *lock_context +) +{ + Chain_Control unblock; + Chain_Node *node; + Chain_Node *tail; + int woken; + + woken = 0; + _Chain_Initialize_empty( &unblock ); + + while ( count > 0 && heads != NULL ) { + const Thread_queue_Operations *operations; + Thread_Control *first; + bool do_unblock; + + operations = FUTEX_TQ_OPERATIONS; + first = ( *operations->first )( heads ); + + do_unblock = _Thread_queue_Extract_locked( + &futex->Queue.Queue, + operations, + first + ); + if (do_unblock) { + _Chain_Append_unprotected( &unblock, &first->Wait.Node.Chain ); + } + + ++woken; + --count; + heads = futex->Queue.Queue.heads; + } + + node = _Chain_First( &unblock ); + tail = _Chain_Tail( &unblock ); + + if ( node != tail ) { + Per_CPU_Control *cpu_self; + + cpu_self = _Thread_Dispatch_disable_critical( lock_context ); + _Futex_Queue_release( futex, lock_context ); + + do { + Thread_Control *thread; + Chain_Node *next; + + next = _Chain_Next( node ); + thread = THREAD_CHAIN_NODE_TO_THREAD( node ); + _Thread_Unblock( thread ); + + node = next; + } while ( node != tail ); + + _Thread_Dispatch_enable( cpu_self ); + } else { + _Futex_Queue_release( futex, lock_context ); + } + + return woken; +} + +int _Futex_Wake( struct _Futex_Control *_futex, int count ) +{ + Futex_Control *futex; + ISR_lock_Context lock_context; + Thread_queue_Heads *heads; + + futex = _Futex_Get( _futex ); + _Futex_Queue_acquire( futex, &lock_context ); + + /* + * For some synchronization objects like barriers the _Futex_Wake() must be + * called in the fast path. Normally there are no threads on the queue, so + * check this condition early. + */ + heads = futex->Queue.Queue.heads; + if ( __predict_true( heads == NULL ) ) { + _Futex_Queue_release( futex, &lock_context ); + + return 0; + } + + return _Futex_Wake_slow( futex, count, heads, &lock_context ); +} + +#endif /* HAVE_STRUCT__THREAD_QUEUE_QUEUE */ diff --git a/testsuites/sptests/spsyslock01/init.c b/testsuites/sptests/spsyslock01/init.c index ece5943492..72e2ad28e7 100644 --- a/testsuites/sptests/spsyslock01/init.c +++ b/testsuites/sptests/spsyslock01/init.c @@ -19,6 +19,8 @@ #include "tmacros.h" #include +#include +#include #include #include @@ -42,6 +44,8 @@ const char rtems_test_name[] = "SPSYSLOCK 1"; #define EVENT_SEM_WAIT RTEMS_EVENT_7 +#define EVENT_FUTEX_WAIT RTEMS_EVENT_8 + typedef struct { rtems_id high[2]; rtems_id mid; @@ -49,6 +53,9 @@ typedef struct { struct _Mutex_Control mtx; struct _Mutex_recursive_Control rec_mtx; struct _Semaphore_Control sem; + struct _Futex_Control futex; + int val; + int eno[2]; int generation[2]; int current_generation[2]; } test_context; @@ -87,18 +94,22 @@ static void test_initialization(test_context *ctx) struct _Mutex_Control mtx = _MUTEX_INITIALIZER; struct _Mutex_recursive_Control rec_mtx = _MUTEX_RECURSIVE_INITIALIZER; struct _Semaphore_Control sem = _SEMAPHORE_INITIALIZER(1); + struct _Futex_Control futex = _FUTEX_INITIALIZER; _Mutex_Initialize(&ctx->mtx); _Mutex_recursive_Initialize(&ctx->rec_mtx); _Semaphore_Initialize(&ctx->sem, 1); + _Futex_Initialize(&ctx->futex); rtems_test_assert(memcmp(&mtx, &ctx->mtx, sizeof(mtx)) == 0); rtems_test_assert(memcmp(&rec_mtx, &ctx->rec_mtx, sizeof(rec_mtx)) == 0); rtems_test_assert(memcmp(&sem, &ctx->sem, sizeof(sem)) == 0); + rtems_test_assert(memcmp(&futex, &ctx->futex, sizeof(futex)) == 0); _Mutex_Destroy(&mtx); _Mutex_recursive_Destroy(&rec_mtx); _Semaphore_Destroy(&sem); + _Futex_Destroy(&futex); } static void test_recursive_acquire_normal(test_context *ctx) @@ -321,6 +332,63 @@ static void test_sem_prio_wait_order(test_context *ctx) rtems_test_assert(ctx->generation[b] == gen_b + 1); } +static void test_futex(test_context *ctx) +{ + struct _Futex_Control *futex = &ctx->futex; + size_t a = 0; + size_t b = 1; + int eno; + int woken; + + eno = _Futex_Wait(futex, &ctx->val, 1); + rtems_test_assert(eno == EWOULDBLOCK); + + woken = _Futex_Wake(futex, 0); + rtems_test_assert(woken == 0); + + woken = _Futex_Wake(futex, 1); + rtems_test_assert(woken == 0); + + ctx->val = 1; + + ctx->eno[a] = -1; + send_event(ctx, a, EVENT_FUTEX_WAIT); + rtems_test_assert(ctx->eno[a] == -1); + + woken = _Futex_Wake(futex, INT_MAX); + rtems_test_assert(woken == 1); + rtems_test_assert(ctx->eno[a] == 0); + + ctx->eno[a] = -1; + ctx->eno[b] = -1; + send_event(ctx, a, EVENT_FUTEX_WAIT); + send_event(ctx, b, EVENT_FUTEX_WAIT); + rtems_test_assert(ctx->eno[a] == -1); + rtems_test_assert(ctx->eno[b] == -1); + + woken = _Futex_Wake(futex, 1); + rtems_test_assert(woken == 1); + rtems_test_assert(ctx->eno[a] == 0); + rtems_test_assert(ctx->eno[b] == -1); + + woken = _Futex_Wake(futex, 1); + rtems_test_assert(woken == 1); + rtems_test_assert(ctx->eno[a] == 0); + rtems_test_assert(ctx->eno[b] == 0); + + ctx->eno[a] = -1; + ctx->eno[b] = -1; + send_event(ctx, a, EVENT_FUTEX_WAIT); + send_event(ctx, b, EVENT_FUTEX_WAIT); + rtems_test_assert(ctx->eno[a] == -1); + rtems_test_assert(ctx->eno[b] == -1); + + woken = _Futex_Wake(futex, 2); + rtems_test_assert(woken == 2); + rtems_test_assert(ctx->eno[a] == 0); + rtems_test_assert(ctx->eno[b] == 0); +} + static void mid_task(rtems_task_argument arg) { rtems_test_assert(0); @@ -402,6 +470,10 @@ static void high_task(rtems_task_argument idx) _Semaphore_Wait(&ctx->sem); ctx->generation[idx] = generation(ctx, idx); } + + if ((events & EVENT_FUTEX_WAIT) != 0) { + ctx->eno[idx] = _Futex_Wait(&ctx->futex, &ctx->val, 1); + } } } @@ -459,12 +531,14 @@ static void test(void) test_mtx_timeout_recursive(ctx); test_sem(ctx); test_sem_prio_wait_order(ctx); + test_futex(ctx); send_event(ctx, 0, EVENT_MTX_DEADLOCK); _Mutex_Destroy(&ctx->mtx); _Mutex_recursive_Destroy(&ctx->rec_mtx); _Semaphore_Destroy(&ctx->sem); + _Futex_Destroy(&ctx->futex); } static void Init(rtems_task_argument arg) diff --git a/testsuites/sptests/spsyslock01/spsyslock01.doc b/testsuites/sptests/spsyslock01/spsyslock01.doc index 1a7384ce7e..bf59cebeff 100644 --- a/testsuites/sptests/spsyslock01/spsyslock01.doc +++ b/testsuites/sptests/spsyslock01/spsyslock01.doc @@ -18,8 +18,13 @@ directives: - _Semaphore_Wait() - _Semaphore_Post() - _Semaphore_Destroy() + - _Futex_Initialize() + - _Futex_Wait() + - _Futex_Wake() + - _Futex_Destroy() concepts: - Ensure that self-contained mutexes and recursive mutexes work. - Ensure that self-contained semaphores work. + - Ensure that self-contained futexes work. -- cgit v1.2.3