Index: libcfa/src/bits/algorithm.hfa =================================================================== --- libcfa/src/bits/algorithm.hfa (revision f7066971a8d399395addd0fa9ee744a61ac3555b) +++ libcfa/src/bits/algorithm.hfa (revision c08c3cfa1e4a6930d362550049713d2d3fd7ed43) @@ -17,12 +17,12 @@ #ifdef SAFE_SORT -forall( otype T | { int ??( T, T ); } ) static inline void __libcfa_small_sort2( T * arr ); -forall( otype T | { int ??( T, T ); } ) static inline void __libcfa_small_sort3( T * arr ); -forall( otype T | { int ??( T, T ); } ) static inline void __libcfa_small_sort4( T * arr ); -forall( otype T | { int ??( T, T ); } ) static inline void __libcfa_small_sort5( T * arr ); -forall( otype T | { int ??( T, T ); } ) static inline void __libcfa_small_sort6( T * arr ); -forall( otype T | { int ??( T, T ); } ) static inline void __libcfa_small_sortN( T * arr, size_t dim ); +forall( T | { int ??( T, T ); } ) static inline void __libcfa_small_sort2( T * arr ); +forall( T | { int ??( T, T ); } ) static inline void __libcfa_small_sort3( T * arr ); +forall( T | { int ??( T, T ); } ) static inline void __libcfa_small_sort4( T * arr ); +forall( T | { int ??( T, T ); } ) static inline void __libcfa_small_sort5( T * arr ); +forall( T | { int ??( T, T ); } ) static inline void __libcfa_small_sort6( T * arr ); +forall( T | { int ??( T, T ); } ) static inline void __libcfa_small_sortN( T * arr, size_t dim ); -forall( otype T | { int ??( T, T ); } ) +forall( T | { int ??( T, T ); } ) static inline void __libcfa_small_sort( T * arr, size_t dim ) { switch( dim ) { @@ -41,10 +41,10 @@ #define SWAP(x,y) { T a = min(arr[x], arr[y]); T b = max(arr[x], arr[y]); arr[x] = a; arr[y] = b;} -forall( otype T | { int ??( T, T ); } ) +forall( T | { int ??( T, T ); } ) static inline void __libcfa_small_sort2( T * arr ) { SWAP(0, 1); } -forall( otype T | { int ??( T, T ); } ) +forall( T | { int ??( T, T ); } ) static inline void __libcfa_small_sort3( T * arr ) { SWAP(1, 2); @@ -53,5 +53,5 @@ } -forall( otype T | { int ??( T, T ); } ) +forall( T | { int ??( T, T ); } ) static inline void __libcfa_small_sort4( T * arr ) { SWAP(0, 1); @@ -62,5 +62,5 @@ } -forall( otype T | { int ??( T, T ); } ) +forall( T | { int ??( T, T ); } ) static inline void __libcfa_small_sort5( T * arr ) { SWAP(0, 1); @@ -75,5 +75,5 @@ } -forall( otype T | { int ??( T, T ); } ) +forall( T | { int ??( T, T ); } ) static inline void __libcfa_small_sort6( T * arr ) { SWAP(1, 2); @@ -91,5 +91,5 @@ } -forall( otype T | { int ??( T, T ); } ) +forall( T | { int ??( T, T ); } ) static inline void __libcfa_small_sortN( T * arr, size_t dim ) { int i, j; @@ -112,5 +112,5 @@ static inline void __libcfa_small_sortN( void* * arr, size_t dim ); -forall( dtype T ) +forall( T & ) static inline void __libcfa_small_sort( T* * arr, size_t dim ) { switch( dim ) { Index: libcfa/src/bits/collection.hfa =================================================================== --- libcfa/src/bits/collection.hfa (revision f7066971a8d399395addd0fa9ee744a61ac3555b) +++ libcfa/src/bits/collection.hfa (revision c08c3cfa1e4a6930d362550049713d2d3fd7ed43) @@ -31,5 +31,5 @@ // // wrappers to make Collection have T - // forall( dtype T ) { + // forall( T & ) { // T *& Next( T * n ) { // return (T *)Next( (Colable *)n ); @@ -76,5 +76,5 @@ } // post: elts = null - forall( dtype T ) { + forall( T & ) { T * Curr( ColIter & ci ) with( ci ) { return (T *)curr; Index: libcfa/src/bits/containers.hfa =================================================================== --- libcfa/src/bits/containers.hfa (revision f7066971a8d399395addd0fa9ee744a61ac3555b) +++ libcfa/src/bits/containers.hfa (revision c08c3cfa1e4a6930d362550049713d2d3fd7ed43) @@ -23,5 +23,5 @@ #ifdef __cforall - forall(dtype T) + forall(T &) #else #define T void @@ -40,23 +40,23 @@ #ifdef __cforall - // forall(otype T | sized(T)) + // forall(T | sized(T)) // static inline void ?{}(__small_array(T) & this) {} - forall(dtype T | sized(T)) + forall(T & | sized(T)) static inline T & ?[?]( __small_array(T) & this, __lock_size_t idx ) { return ((typeof(this.data))this.data)[idx]; } - forall(dtype T | sized(T)) + forall(T & | sized(T)) static inline T & ?[?]( const __small_array(T) & this, __lock_size_t idx ) { return ((typeof(this.data))this.data)[idx]; } - forall(dtype T) + forall(T &) static inline T * begin( const __small_array(T) & this ) { return ((typeof(this.data))this.data); } - forall(dtype T | sized(T)) + forall(T & | sized(T)) static inline T * end( const __small_array(T) & this ) { return ((typeof(this.data))this.data) + this.size; @@ -69,5 +69,5 @@ #ifdef __cforall - trait is_node(dtype T) { + trait is_node(T &) { T *& get_next( T & ); }; @@ -78,5 +78,5 @@ //----------------------------------------------------------------------------- #ifdef __cforall - forall(dtype TYPE) + forall(TYPE &) #define T TYPE #else @@ -95,10 +95,10 @@ #ifdef __cforall - forall(dtype T) + forall(T &) static inline void ?{}( __stack(T) & this ) { (this.top){ 0p }; } - static inline forall( dtype T | is_node(T) ) { + static inline forall( T & | is_node(T) ) { void push( __stack(T) & this, T * val ) { verify( !get_next( *val ) ); @@ -126,5 +126,5 @@ //----------------------------------------------------------------------------- #ifdef __cforall - forall(dtype TYPE) + forall(TYPE &) #define T TYPE #else @@ -144,5 +144,5 @@ #ifdef __cforall - static inline forall( dtype T | is_node(T) ) { + static inline forall( T & | is_node(T) ) { void ?{}( __queue(T) & this ) with( this ) { (this.head){ 1p }; @@ -215,5 +215,5 @@ //----------------------------------------------------------------------------- #ifdef __cforall - forall(dtype TYPE) + forall(TYPE &) #define T TYPE #define __getter_t * [T * & next, T * & prev] ( T & ) @@ -237,5 +237,5 @@ #ifdef __cforall - forall(dtype T ) + forall(T & ) static inline [void] ?{}( __dllist(T) & this, * [T * & next, T * & prev] ( T & ) __get ) { (this.head){ 0p }; @@ -245,5 +245,5 @@ #define next 0 #define prev 1 - static inline forall(dtype T) { + static inline forall(T &) { void push_front( __dllist(T) & this, T & node ) with( this ) { verify(__get); Index: libcfa/src/bits/defs.hfa =================================================================== --- libcfa/src/bits/defs.hfa (revision f7066971a8d399395addd0fa9ee744a61ac3555b) +++ libcfa/src/bits/defs.hfa (revision c08c3cfa1e4a6930d362550049713d2d3fd7ed43) @@ -5,5 +5,8 @@ // file "LICENCE" distributed with Cforall. // -// defs.hfa -- +// defs.hfa -- Commen macros, functions and typedefs +// Most files depend on them and they are always useful to have. +// +// *** Must not contain code specific to libcfathread *** // // Author : Thierry Delisle @@ -62,2 +65,11 @@ #endif } + +// pause to prevent excess processor bus usage +#if defined( __i386 ) || defined( __x86_64 ) + #define Pause() __asm__ __volatile__ ( "pause" : : : ) +#elif defined( __ARM_ARCH ) + #define Pause() __asm__ __volatile__ ( "YIELD" : : : ) +#else + #error unsupported architecture +#endif Index: libcfa/src/bits/locks.hfa =================================================================== --- libcfa/src/bits/locks.hfa (revision f7066971a8d399395addd0fa9ee744a61ac3555b) +++ libcfa/src/bits/locks.hfa (revision c08c3cfa1e4a6930d362550049713d2d3fd7ed43) @@ -5,5 +5,8 @@ // file "LICENCE" distributed with Cforall. // -// bits/locks.hfa -- Fast internal locks. +// bits/locks.hfa -- Basic spinlocks that are reused in the system. +// Used for locks that aren't specific to cforall threads and can be used anywhere +// +// *** Must not contain code specific to libcfathread *** // // Author : Thierry Delisle @@ -19,19 +22,4 @@ #include "bits/defs.hfa" #include - -#ifdef __cforall - extern "C" { - #include - } -#endif - -// pause to prevent excess processor bus usage -#if defined( __i386 ) || defined( __x86_64 ) - #define Pause() __asm__ __volatile__ ( "pause" : : : ) -#elif defined( __ARM_ARCH ) - #define Pause() __asm__ __volatile__ ( "YIELD" : : : ) -#else - #error unsupported architecture -#endif struct __spinlock_t { @@ -104,320 +92,3 @@ enable_interrupts_noPoll(); } - - - #ifdef __CFA_WITH_VERIFY__ - extern bool __cfaabi_dbg_in_kernel(); - #endif - - extern "C" { - char * strerror(int); - } - #define CHECKED(x) { int err = x; if( err != 0 ) abort("KERNEL ERROR: Operation \"" #x "\" return error %d - %s\n", err, strerror(err)); } - - struct __bin_sem_t { - pthread_mutex_t lock; - pthread_cond_t cond; - int val; - }; - - static inline void ?{}(__bin_sem_t & this) with( this ) { - // Create the mutex with error checking - pthread_mutexattr_t mattr; - pthread_mutexattr_init( &mattr ); - pthread_mutexattr_settype( &mattr, PTHREAD_MUTEX_ERRORCHECK_NP); - pthread_mutex_init(&lock, &mattr); - - pthread_cond_init (&cond, (const pthread_condattr_t *)0p); // workaround trac#208: cast should not be required - val = 0; - } - - static inline void ^?{}(__bin_sem_t & this) with( this ) { - CHECKED( pthread_mutex_destroy(&lock) ); - CHECKED( pthread_cond_destroy (&cond) ); - } - - static inline void wait(__bin_sem_t & this) with( this ) { - verify(__cfaabi_dbg_in_kernel()); - CHECKED( pthread_mutex_lock(&lock) ); - while(val < 1) { - pthread_cond_wait(&cond, &lock); - } - val -= 1; - CHECKED( pthread_mutex_unlock(&lock) ); - } - - static inline bool post(__bin_sem_t & this) with( this ) { - bool needs_signal = false; - - CHECKED( pthread_mutex_lock(&lock) ); - if(val < 1) { - val += 1; - pthread_cond_signal(&cond); - needs_signal = true; - } - CHECKED( pthread_mutex_unlock(&lock) ); - - return needs_signal; - } - - #undef CHECKED - - struct $thread; - extern void park( void ); - extern void unpark( struct $thread * this ); - static inline struct $thread * active_thread (); - - // Semaphore which only supports a single thread - struct single_sem { - struct $thread * volatile ptr; - }; - - static inline { - void ?{}(single_sem & this) { - this.ptr = 0p; - } - - void ^?{}(single_sem &) {} - - bool wait(single_sem & this) { - for() { - struct $thread * expected = this.ptr; - if(expected == 1p) { - if(__atomic_compare_exchange_n(&this.ptr, &expected, 0p, false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)) { - return false; - } - } - else { - /* paranoid */ verify( expected == 0p ); - if(__atomic_compare_exchange_n(&this.ptr, &expected, active_thread(), false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)) { - park(); - return true; - } - } - - } - } - - bool post(single_sem & this) { - for() { - struct $thread * expected = this.ptr; - if(expected == 1p) return false; - if(expected == 0p) { - if(__atomic_compare_exchange_n(&this.ptr, &expected, 1p, false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)) { - return false; - } - } - else { - if(__atomic_compare_exchange_n(&this.ptr, &expected, 0p, false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)) { - unpark( expected ); - return true; - } - } - } - } - } - - // Synchronozation primitive which only supports a single thread and one post - // Similar to a binary semaphore with a 'one shot' semantic - // is expected to be discarded after each party call their side - struct oneshot { - // Internal state : - // 0p : is initial state (wait will block) - // 1p : fulfilled (wait won't block) - // any thread : a thread is currently waiting - struct $thread * volatile ptr; - }; - - static inline { - void ?{}(oneshot & this) { - this.ptr = 0p; - } - - void ^?{}(oneshot &) {} - - // Wait for the post, return immidiately if it already happened. - // return true if the thread was parked - bool wait(oneshot & this) { - for() { - struct $thread * expected = this.ptr; - if(expected == 1p) return false; - /* paranoid */ verify( expected == 0p ); - if(__atomic_compare_exchange_n(&this.ptr, &expected, active_thread(), false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)) { - park(); - /* paranoid */ verify( this.ptr == 1p ); - return true; - } - } - } - - // Mark as fulfilled, wake thread if needed - // return true if a thread was unparked - bool post(oneshot & this) { - struct $thread * got = __atomic_exchange_n( &this.ptr, 1p, __ATOMIC_SEQ_CST); - if( got == 0p ) return false; - unpark( got ); - return true; - } - } - - // base types for future to build upon - // It is based on the 'oneshot' type to allow multiple futures - // to block on the same instance, permitting users to block a single - // thread on "any of" [a given set of] futures. - // does not support multiple threads waiting on the same future - struct future_t { - // Internal state : - // 0p : is initial state (wait will block) - // 1p : fulfilled (wait won't block) - // 2p : in progress () - // 3p : abandoned, server should delete - // any oneshot : a context has been setup to wait, a thread could wait on it - struct oneshot * volatile ptr; - }; - - static inline { - void ?{}(future_t & this) { - this.ptr = 0p; - } - - void ^?{}(future_t &) {} - - void reset(future_t & this) { - // needs to be in 0p or 1p - __atomic_exchange_n( &this.ptr, 0p, __ATOMIC_SEQ_CST); - } - - // check if the future is available - bool available( future_t & this ) { - return this.ptr == 1p; - } - - // Prepare the future to be waited on - // intented to be use by wait, wait_any, waitfor, etc. rather than used directly - bool setup( future_t & this, oneshot & wait_ctx ) { - /* paranoid */ verify( wait_ctx.ptr == 0p ); - // The future needs to set the wait context - for() { - struct oneshot * expected = this.ptr; - // Is the future already fulfilled? - if(expected == 1p) return false; // Yes, just return false (didn't block) - - // The future is not fulfilled, try to setup the wait context - /* paranoid */ verify( expected == 0p ); - if(__atomic_compare_exchange_n(&this.ptr, &expected, &wait_ctx, false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)) { - return true; - } - } - } - - // Stop waiting on a future - // When multiple futures are waited for together in "any of" pattern - // futures that weren't fulfilled before the thread woke up - // should retract the wait ctx - // intented to be use by wait, wait_any, waitfor, etc. rather than used directly - void retract( future_t & this, oneshot & wait_ctx ) { - // Remove the wait context - struct oneshot * got = __atomic_exchange_n( &this.ptr, 0p, __ATOMIC_SEQ_CST); - - // got == 0p: future was never actually setup, just return - if( got == 0p ) return; - - // got == wait_ctx: since fulfil does an atomic_swap, - // if we got back the original then no one else saw context - // It is safe to delete (which could happen after the return) - if( got == &wait_ctx ) return; - - // got == 1p: the future is ready and the context was fully consumed - // the server won't use the pointer again - // It is safe to delete (which could happen after the return) - if( got == 1p ) return; - - // got == 2p: the future is ready but the context hasn't fully been consumed - // spin until it is safe to move on - if( got == 2p ) { - while( this.ptr != 1p ) Pause(); - return; - } - - // got == any thing else, something wen't wrong here, abort - abort("Future in unexpected state"); - } - - // Mark the future as abandoned, meaning it will be deleted by the server - bool abandon( future_t & this ) { - /* paranoid */ verify( this.ptr != 3p ); - - // Mark the future as abandonned - struct oneshot * got = __atomic_exchange_n( &this.ptr, 3p, __ATOMIC_SEQ_CST); - - // If the future isn't already fulfilled, let the server delete it - if( got == 0p ) return false; - - // got == 2p: the future is ready but the context hasn't fully been consumed - // spin until it is safe to move on - if( got == 2p ) { - while( this.ptr != 1p ) Pause(); - got = 1p; - } - - // The future is completed delete it now - /* paranoid */ verify( this.ptr != 1p ); - free( &this ); - return true; - } - - // from the server side, mark the future as fulfilled - // delete it if needed - bool fulfil( future_t & this ) { - for() { - struct oneshot * expected = this.ptr; - // was this abandoned? - #if defined(__GNUC__) && __GNUC__ >= 7 - #pragma GCC diagnostic push - #pragma GCC diagnostic ignored "-Wfree-nonheap-object" - #endif - if( expected == 3p ) { free( &this ); return false; } - #if defined(__GNUC__) && __GNUC__ >= 7 - #pragma GCC diagnostic pop - #endif - - /* paranoid */ verify( expected != 1p ); // Future is already fulfilled, should not happen - /* paranoid */ verify( expected != 2p ); // Future is bein fulfilled by someone else, this is even less supported then the previous case. - - // If there is a wait context, we need to consume it and mark it as consumed after - // If there is no context then we can skip the in progress phase - struct oneshot * want = expected == 0p ? 1p : 2p; - if(__atomic_compare_exchange_n(&this.ptr, &expected, want, false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)) { - if( expected == 0p ) { /* paranoid */ verify( this.ptr == 1p); return false; } - bool ret = post( *expected ); - __atomic_store_n( &this.ptr, 1p, __ATOMIC_SEQ_CST); - return ret; - } - } - - } - - // Wait for the future to be fulfilled - bool wait( future_t & this ) { - oneshot temp; - if( !setup(this, temp) ) return false; - - // Wait context is setup, just wait on it - bool ret = wait( temp ); - - // Wait for the future to tru - while( this.ptr == 2p ) Pause(); - // Make sure the state makes sense - // Should be fulfilled, could be in progress but it's out of date if so - // since if that is the case, the oneshot was fulfilled (unparking this thread) - // and the oneshot should not be needed any more - __attribute__((unused)) struct oneshot * was = this.ptr; - /* paranoid */ verifyf( was == 1p, "Expected this.ptr to be 1p, was %p\n", was ); - - // Mark the future as fulfilled, to be consistent - // with potential calls to avail - // this.ptr = 1p; - return ret; - } - } #endif Index: libcfa/src/bits/queue.hfa =================================================================== --- libcfa/src/bits/queue.hfa (revision f7066971a8d399395addd0fa9ee744a61ac3555b) +++ libcfa/src/bits/queue.hfa (revision c08c3cfa1e4a6930d362550049713d2d3fd7ed43) @@ -9,5 +9,5 @@ // instead of being null. -forall( dtype T | { T *& Next ( T * ); } ) { +forall( T & | { T *& Next ( T * ); } ) { struct Queue { inline Collection; // Plan 9 inheritance @@ -151,5 +151,5 @@ } // distribution -forall( dtype T | { T *& Next ( T * ); } ) { +forall( T & | { T *& Next ( T * ); } ) { struct QueueIter { inline ColIter; // Plan 9 inheritance Index: libcfa/src/bits/sequence.hfa =================================================================== --- libcfa/src/bits/sequence.hfa (revision f7066971a8d399395addd0fa9ee744a61ac3555b) +++ libcfa/src/bits/sequence.hfa (revision c08c3cfa1e4a6930d362550049713d2d3fd7ed43) @@ -29,5 +29,5 @@ // // wrappers to make Collection have T - // forall( dtype T ) { + // forall( T & ) { // T *& Back( T * n ) { // return (T *)Back( (Seqable *)n ); @@ -43,5 +43,5 @@ // and the back field of the last node points at the first node (circular). -forall( dtype T | { T *& Back ( T * ); T *& Next ( T * ); } ) { +forall( T & | { T *& Back ( T * ); T *& Next ( T * ); } ) { struct Sequence { inline Collection; // Plan 9 inheritance @@ -231,5 +231,5 @@ } // distribution -forall( dtype T | { T *& Back ( T * ); T *& Next ( T * ); } ) { +forall( T & | { T *& Back ( T * ); T *& Next ( T * ); } ) { // SeqIter(T) is used to iterate over a Sequence(T) in head-to-tail order. struct SeqIter { Index: libcfa/src/bits/stack.hfa =================================================================== --- libcfa/src/bits/stack.hfa (revision f7066971a8d399395addd0fa9ee744a61ac3555b) +++ libcfa/src/bits/stack.hfa (revision c08c3cfa1e4a6930d362550049713d2d3fd7ed43) @@ -9,5 +9,5 @@ // instead of being null. -forall( dtype T | { T *& Next ( T * ); } ) { +forall( T & | { T *& Next ( T * ); } ) { struct Stack { inline Collection; // Plan 9 inheritance @@ -67,5 +67,5 @@ // order returned by drop(). -forall( dtype T | { T *& Next ( T * ); } ) { +forall( T & | { T *& Next ( T * ); } ) { struct StackIter { inline ColIter; // Plan 9 inheritance