Changeset c08c3cf for libcfa/src/bits
- Timestamp:
- Jan 20, 2021, 8:46:31 PM (4 years ago)
- Branches:
- ADT, arm-eh, ast-experimental, enum, forall-pointer-decay, jacob/cs343-translation, master, new-ast-unique-expr, pthread-emulation, qualifiedEnum
- Children:
- 481cf3a
- Parents:
- 467c8b7 (diff), 9db2c92 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the(diff)links above to see all the changes relative to each parent. - Location:
- libcfa/src/bits
- Files:
-
- 8 edited
-
algorithm.hfa (modified) (7 diffs)
-
collection.hfa (modified) (2 diffs)
-
containers.hfa (modified) (10 diffs)
-
defs.hfa (modified) (2 diffs)
-
locks.hfa (modified) (3 diffs)
-
queue.hfa (modified) (2 diffs)
-
sequence.hfa (modified) (3 diffs)
-
stack.hfa (modified) (2 diffs)
Legend:
- Unmodified
- Added
- Removed
-
TabularUnified libcfa/src/bits/algorithm.hfa ¶
r467c8b7 rc08c3cf 17 17 18 18 #ifdef SAFE_SORT 19 forall( otypeT | { int ?<?( T, T ); int ?>?( T, T ); } ) static inline void __libcfa_small_sort2( T * arr );20 forall( otypeT | { int ?<?( T, T ); int ?>?( T, T ); } ) static inline void __libcfa_small_sort3( T * arr );21 forall( otypeT | { int ?<?( T, T ); int ?>?( T, T ); } ) static inline void __libcfa_small_sort4( T * arr );22 forall( otypeT | { int ?<?( T, T ); int ?>?( T, T ); } ) static inline void __libcfa_small_sort5( T * arr );23 forall( otypeT | { int ?<?( T, T ); int ?>?( T, T ); } ) static inline void __libcfa_small_sort6( T * arr );24 forall( otypeT | { int ?<?( T, T ); int ?>?( T, T ); } ) static inline void __libcfa_small_sortN( T * arr, size_t dim );19 forall( T | { int ?<?( T, T ); int ?>?( T, T ); } ) static inline void __libcfa_small_sort2( T * arr ); 20 forall( T | { int ?<?( T, T ); int ?>?( T, T ); } ) static inline void __libcfa_small_sort3( T * arr ); 21 forall( T | { int ?<?( T, T ); int ?>?( T, T ); } ) static inline void __libcfa_small_sort4( T * arr ); 22 forall( T | { int ?<?( T, T ); int ?>?( T, T ); } ) static inline void __libcfa_small_sort5( T * arr ); 23 forall( T | { int ?<?( T, T ); int ?>?( T, T ); } ) static inline void __libcfa_small_sort6( T * arr ); 24 forall( T | { int ?<?( T, T ); int ?>?( T, T ); } ) static inline void __libcfa_small_sortN( T * arr, size_t dim ); 25 25 26 forall( otypeT | { int ?<?( T, T ); int ?>?( T, T ); } )26 forall( T | { int ?<?( T, T ); int ?>?( T, T ); } ) 27 27 static inline void __libcfa_small_sort( T * arr, size_t dim ) { 28 28 switch( dim ) { … … 41 41 #define SWAP(x,y) { T a = min(arr[x], arr[y]); T b = max(arr[x], arr[y]); arr[x] = a; arr[y] = b;} 42 42 43 forall( otypeT | { int ?<?( T, T ); int ?>?( T, T ); } )43 forall( T | { int ?<?( T, T ); int ?>?( T, T ); } ) 44 44 static inline void __libcfa_small_sort2( T * arr ) { 45 45 SWAP(0, 1); 46 46 } 47 47 48 forall( otypeT | { int ?<?( T, T ); int ?>?( T, T ); } )48 forall( T | { int ?<?( T, T ); int ?>?( T, T ); } ) 49 49 static inline void __libcfa_small_sort3( T * arr ) { 50 50 SWAP(1, 2); … … 53 53 } 54 54 55 forall( otypeT | { int ?<?( T, T ); int ?>?( T, T ); } )55 forall( T | { int ?<?( T, T ); int ?>?( T, T ); } ) 56 56 static inline void __libcfa_small_sort4( T * arr ) { 57 57 SWAP(0, 1); … … 62 62 } 63 63 64 forall( otypeT | { int ?<?( T, T ); int ?>?( T, T ); } )64 forall( T | { int ?<?( T, T ); int ?>?( T, T ); } ) 65 65 static inline void __libcfa_small_sort5( T * arr ) { 66 66 SWAP(0, 1); … … 75 75 } 76 76 77 forall( otypeT | { int ?<?( T, T ); int ?>?( T, T ); } )77 forall( T | { int ?<?( T, T ); int ?>?( T, T ); } ) 78 78 static inline void __libcfa_small_sort6( T * arr ) { 79 79 SWAP(1, 2); … … 91 91 } 92 92 93 forall( otypeT | { int ?<?( T, T ); int ?>?( T, T ); } )93 forall( T | { int ?<?( T, T ); int ?>?( T, T ); } ) 94 94 static inline void __libcfa_small_sortN( T * arr, size_t dim ) { 95 95 int i, j; … … 112 112 static inline void __libcfa_small_sortN( void* * arr, size_t dim ); 113 113 114 forall( dtype T)114 forall( T & ) 115 115 static inline void __libcfa_small_sort( T* * arr, size_t dim ) { 116 116 switch( dim ) { -
TabularUnified libcfa/src/bits/collection.hfa ¶
r467c8b7 rc08c3cf 31 31 32 32 // // wrappers to make Collection have T 33 // forall( dtype T) {33 // forall( T & ) { 34 34 // T *& Next( T * n ) { 35 35 // return (T *)Next( (Colable *)n ); … … 76 76 } // post: elts = null 77 77 78 forall( dtype T) {78 forall( T & ) { 79 79 T * Curr( ColIter & ci ) with( ci ) { 80 80 return (T *)curr; -
TabularUnified libcfa/src/bits/containers.hfa ¶
r467c8b7 rc08c3cf 23 23 24 24 #ifdef __cforall 25 forall( dtype T)25 forall(T &) 26 26 #else 27 27 #define T void … … 40 40 41 41 #ifdef __cforall 42 // forall( otypeT | sized(T))42 // forall(T | sized(T)) 43 43 // static inline void ?{}(__small_array(T) & this) {} 44 44 45 forall( dtype T| sized(T))45 forall(T & | sized(T)) 46 46 static inline T & ?[?]( __small_array(T) & this, __lock_size_t idx ) { 47 47 return ((typeof(this.data))this.data)[idx]; 48 48 } 49 49 50 forall( dtype T| sized(T))50 forall(T & | sized(T)) 51 51 static inline T & ?[?]( const __small_array(T) & this, __lock_size_t idx ) { 52 52 return ((typeof(this.data))this.data)[idx]; 53 53 } 54 54 55 forall( dtype T)55 forall(T &) 56 56 static inline T * begin( const __small_array(T) & this ) { 57 57 return ((typeof(this.data))this.data); 58 58 } 59 59 60 forall( dtype T| sized(T))60 forall(T & | sized(T)) 61 61 static inline T * end( const __small_array(T) & this ) { 62 62 return ((typeof(this.data))this.data) + this.size; … … 69 69 70 70 #ifdef __cforall 71 trait is_node( dtype T) {71 trait is_node(T &) { 72 72 T *& get_next( T & ); 73 73 }; … … 78 78 //----------------------------------------------------------------------------- 79 79 #ifdef __cforall 80 forall( dtype TYPE)80 forall(TYPE &) 81 81 #define T TYPE 82 82 #else … … 95 95 96 96 #ifdef __cforall 97 forall( dtype T)97 forall(T &) 98 98 static inline void ?{}( __stack(T) & this ) { 99 99 (this.top){ 0p }; 100 100 } 101 101 102 static inline forall( dtype T| is_node(T) ) {102 static inline forall( T & | is_node(T) ) { 103 103 void push( __stack(T) & this, T * val ) { 104 104 verify( !get_next( *val ) ); … … 126 126 //----------------------------------------------------------------------------- 127 127 #ifdef __cforall 128 forall( dtype TYPE)128 forall(TYPE &) 129 129 #define T TYPE 130 130 #else … … 144 144 145 145 #ifdef __cforall 146 static inline forall( dtype T| is_node(T) ) {146 static inline forall( T & | is_node(T) ) { 147 147 void ?{}( __queue(T) & this ) with( this ) { 148 148 (this.head){ 1p }; … … 215 215 //----------------------------------------------------------------------------- 216 216 #ifdef __cforall 217 forall( dtype TYPE)217 forall(TYPE &) 218 218 #define T TYPE 219 219 #define __getter_t * [T * & next, T * & prev] ( T & ) … … 237 237 238 238 #ifdef __cforall 239 forall( dtype T)239 forall(T & ) 240 240 static inline [void] ?{}( __dllist(T) & this, * [T * & next, T * & prev] ( T & ) __get ) { 241 241 (this.head){ 0p }; … … 245 245 #define next 0 246 246 #define prev 1 247 static inline forall( dtype T) {247 static inline forall(T &) { 248 248 void push_front( __dllist(T) & this, T & node ) with( this ) { 249 249 verify(__get); -
TabularUnified libcfa/src/bits/defs.hfa ¶
r467c8b7 rc08c3cf 5 5 // file "LICENCE" distributed with Cforall. 6 6 // 7 // defs.hfa -- 7 // defs.hfa -- Commen macros, functions and typedefs 8 // Most files depend on them and they are always useful to have. 9 // 10 // *** Must not contain code specific to libcfathread *** 8 11 // 9 12 // Author : Thierry Delisle … … 62 65 #endif 63 66 } 67 68 // pause to prevent excess processor bus usage 69 #if defined( __i386 ) || defined( __x86_64 ) 70 #define Pause() __asm__ __volatile__ ( "pause" : : : ) 71 #elif defined( __ARM_ARCH ) 72 #define Pause() __asm__ __volatile__ ( "YIELD" : : : ) 73 #else 74 #error unsupported architecture 75 #endif -
TabularUnified libcfa/src/bits/locks.hfa ¶
r467c8b7 rc08c3cf 5 5 // file "LICENCE" distributed with Cforall. 6 6 // 7 // bits/locks.hfa -- Fast internal locks. 7 // bits/locks.hfa -- Basic spinlocks that are reused in the system. 8 // Used for locks that aren't specific to cforall threads and can be used anywhere 9 // 10 // *** Must not contain code specific to libcfathread *** 8 11 // 9 12 // Author : Thierry Delisle … … 19 22 #include "bits/defs.hfa" 20 23 #include <assert.h> 21 22 #ifdef __cforall23 extern "C" {24 #include <pthread.h>25 }26 #endif27 28 // pause to prevent excess processor bus usage29 #if defined( __i386 ) || defined( __x86_64 )30 #define Pause() __asm__ __volatile__ ( "pause" : : : )31 #elif defined( __ARM_ARCH )32 #define Pause() __asm__ __volatile__ ( "YIELD" : : : )33 #else34 #error unsupported architecture35 #endif36 24 37 25 struct __spinlock_t { … … 104 92 enable_interrupts_noPoll(); 105 93 } 106 107 108 #ifdef __CFA_WITH_VERIFY__109 extern bool __cfaabi_dbg_in_kernel();110 #endif111 112 extern "C" {113 char * strerror(int);114 }115 #define CHECKED(x) { int err = x; if( err != 0 ) abort("KERNEL ERROR: Operation \"" #x "\" return error %d - %s\n", err, strerror(err)); }116 117 struct __bin_sem_t {118 pthread_mutex_t lock;119 pthread_cond_t cond;120 int val;121 };122 123 static inline void ?{}(__bin_sem_t & this) with( this ) {124 // Create the mutex with error checking125 pthread_mutexattr_t mattr;126 pthread_mutexattr_init( &mattr );127 pthread_mutexattr_settype( &mattr, PTHREAD_MUTEX_ERRORCHECK_NP);128 pthread_mutex_init(&lock, &mattr);129 130 pthread_cond_init (&cond, (const pthread_condattr_t *)0p); // workaround trac#208: cast should not be required131 val = 0;132 }133 134 static inline void ^?{}(__bin_sem_t & this) with( this ) {135 CHECKED( pthread_mutex_destroy(&lock) );136 CHECKED( pthread_cond_destroy (&cond) );137 }138 139 static inline void wait(__bin_sem_t & this) with( this ) {140 verify(__cfaabi_dbg_in_kernel());141 CHECKED( pthread_mutex_lock(&lock) );142 while(val < 1) {143 pthread_cond_wait(&cond, &lock);144 }145 val -= 1;146 CHECKED( pthread_mutex_unlock(&lock) );147 }148 149 static inline bool post(__bin_sem_t & this) with( this ) {150 bool needs_signal = false;151 152 CHECKED( pthread_mutex_lock(&lock) );153 if(val < 1) {154 val += 1;155 pthread_cond_signal(&cond);156 needs_signal = true;157 }158 CHECKED( pthread_mutex_unlock(&lock) );159 160 return needs_signal;161 }162 163 #undef CHECKED164 165 struct $thread;166 extern void park( void );167 extern void unpark( struct $thread * this );168 static inline struct $thread * active_thread ();169 170 // Semaphore which only supports a single thread171 struct single_sem {172 struct $thread * volatile ptr;173 };174 175 static inline {176 void ?{}(single_sem & this) {177 this.ptr = 0p;178 }179 180 void ^?{}(single_sem &) {}181 182 bool wait(single_sem & this) {183 for() {184 struct $thread * expected = this.ptr;185 if(expected == 1p) {186 if(__atomic_compare_exchange_n(&this.ptr, &expected, 0p, false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)) {187 return false;188 }189 }190 else {191 /* paranoid */ verify( expected == 0p );192 if(__atomic_compare_exchange_n(&this.ptr, &expected, active_thread(), false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)) {193 park();194 return true;195 }196 }197 198 }199 }200 201 bool post(single_sem & this) {202 for() {203 struct $thread * expected = this.ptr;204 if(expected == 1p) return false;205 if(expected == 0p) {206 if(__atomic_compare_exchange_n(&this.ptr, &expected, 1p, false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)) {207 return false;208 }209 }210 else {211 if(__atomic_compare_exchange_n(&this.ptr, &expected, 0p, false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)) {212 unpark( expected );213 return true;214 }215 }216 }217 }218 }219 220 // Synchronozation primitive which only supports a single thread and one post221 // Similar to a binary semaphore with a 'one shot' semantic222 // is expected to be discarded after each party call their side223 struct oneshot {224 // Internal state :225 // 0p : is initial state (wait will block)226 // 1p : fulfilled (wait won't block)227 // any thread : a thread is currently waiting228 struct $thread * volatile ptr;229 };230 231 static inline {232 void ?{}(oneshot & this) {233 this.ptr = 0p;234 }235 236 void ^?{}(oneshot &) {}237 238 // Wait for the post, return immidiately if it already happened.239 // return true if the thread was parked240 bool wait(oneshot & this) {241 for() {242 struct $thread * expected = this.ptr;243 if(expected == 1p) return false;244 /* paranoid */ verify( expected == 0p );245 if(__atomic_compare_exchange_n(&this.ptr, &expected, active_thread(), false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)) {246 park();247 /* paranoid */ verify( this.ptr == 1p );248 return true;249 }250 }251 }252 253 // Mark as fulfilled, wake thread if needed254 // return true if a thread was unparked255 bool post(oneshot & this) {256 struct $thread * got = __atomic_exchange_n( &this.ptr, 1p, __ATOMIC_SEQ_CST);257 if( got == 0p ) return false;258 unpark( got );259 return true;260 }261 }262 263 // base types for future to build upon264 // It is based on the 'oneshot' type to allow multiple futures265 // to block on the same instance, permitting users to block a single266 // thread on "any of" [a given set of] futures.267 // does not support multiple threads waiting on the same future268 struct future_t {269 // Internal state :270 // 0p : is initial state (wait will block)271 // 1p : fulfilled (wait won't block)272 // 2p : in progress ()273 // 3p : abandoned, server should delete274 // any oneshot : a context has been setup to wait, a thread could wait on it275 struct oneshot * volatile ptr;276 };277 278 static inline {279 void ?{}(future_t & this) {280 this.ptr = 0p;281 }282 283 void ^?{}(future_t &) {}284 285 void reset(future_t & this) {286 // needs to be in 0p or 1p287 __atomic_exchange_n( &this.ptr, 0p, __ATOMIC_SEQ_CST);288 }289 290 // check if the future is available291 bool available( future_t & this ) {292 return this.ptr == 1p;293 }294 295 // Prepare the future to be waited on296 // intented to be use by wait, wait_any, waitfor, etc. rather than used directly297 bool setup( future_t & this, oneshot & wait_ctx ) {298 /* paranoid */ verify( wait_ctx.ptr == 0p );299 // The future needs to set the wait context300 for() {301 struct oneshot * expected = this.ptr;302 // Is the future already fulfilled?303 if(expected == 1p) return false; // Yes, just return false (didn't block)304 305 // The future is not fulfilled, try to setup the wait context306 /* paranoid */ verify( expected == 0p );307 if(__atomic_compare_exchange_n(&this.ptr, &expected, &wait_ctx, false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)) {308 return true;309 }310 }311 }312 313 // Stop waiting on a future314 // When multiple futures are waited for together in "any of" pattern315 // futures that weren't fulfilled before the thread woke up316 // should retract the wait ctx317 // intented to be use by wait, wait_any, waitfor, etc. rather than used directly318 void retract( future_t & this, oneshot & wait_ctx ) {319 // Remove the wait context320 struct oneshot * got = __atomic_exchange_n( &this.ptr, 0p, __ATOMIC_SEQ_CST);321 322 // got == 0p: future was never actually setup, just return323 if( got == 0p ) return;324 325 // got == wait_ctx: since fulfil does an atomic_swap,326 // if we got back the original then no one else saw context327 // It is safe to delete (which could happen after the return)328 if( got == &wait_ctx ) return;329 330 // got == 1p: the future is ready and the context was fully consumed331 // the server won't use the pointer again332 // It is safe to delete (which could happen after the return)333 if( got == 1p ) return;334 335 // got == 2p: the future is ready but the context hasn't fully been consumed336 // spin until it is safe to move on337 if( got == 2p ) {338 while( this.ptr != 1p ) Pause();339 return;340 }341 342 // got == any thing else, something wen't wrong here, abort343 abort("Future in unexpected state");344 }345 346 // Mark the future as abandoned, meaning it will be deleted by the server347 bool abandon( future_t & this ) {348 /* paranoid */ verify( this.ptr != 3p );349 350 // Mark the future as abandonned351 struct oneshot * got = __atomic_exchange_n( &this.ptr, 3p, __ATOMIC_SEQ_CST);352 353 // If the future isn't already fulfilled, let the server delete it354 if( got == 0p ) return false;355 356 // got == 2p: the future is ready but the context hasn't fully been consumed357 // spin until it is safe to move on358 if( got == 2p ) {359 while( this.ptr != 1p ) Pause();360 got = 1p;361 }362 363 // The future is completed delete it now364 /* paranoid */ verify( this.ptr != 1p );365 free( &this );366 return true;367 }368 369 // from the server side, mark the future as fulfilled370 // delete it if needed371 bool fulfil( future_t & this ) {372 for() {373 struct oneshot * expected = this.ptr;374 // was this abandoned?375 #if defined(__GNUC__) && __GNUC__ >= 7376 #pragma GCC diagnostic push377 #pragma GCC diagnostic ignored "-Wfree-nonheap-object"378 #endif379 if( expected == 3p ) { free( &this ); return false; }380 #if defined(__GNUC__) && __GNUC__ >= 7381 #pragma GCC diagnostic pop382 #endif383 384 /* paranoid */ verify( expected != 1p ); // Future is already fulfilled, should not happen385 /* paranoid */ verify( expected != 2p ); // Future is bein fulfilled by someone else, this is even less supported then the previous case.386 387 // If there is a wait context, we need to consume it and mark it as consumed after388 // If there is no context then we can skip the in progress phase389 struct oneshot * want = expected == 0p ? 1p : 2p;390 if(__atomic_compare_exchange_n(&this.ptr, &expected, want, false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)) {391 if( expected == 0p ) { /* paranoid */ verify( this.ptr == 1p); return false; }392 bool ret = post( *expected );393 __atomic_store_n( &this.ptr, 1p, __ATOMIC_SEQ_CST);394 return ret;395 }396 }397 398 }399 400 // Wait for the future to be fulfilled401 bool wait( future_t & this ) {402 oneshot temp;403 if( !setup(this, temp) ) return false;404 405 // Wait context is setup, just wait on it406 bool ret = wait( temp );407 408 // Wait for the future to tru409 while( this.ptr == 2p ) Pause();410 // Make sure the state makes sense411 // Should be fulfilled, could be in progress but it's out of date if so412 // since if that is the case, the oneshot was fulfilled (unparking this thread)413 // and the oneshot should not be needed any more414 __attribute__((unused)) struct oneshot * was = this.ptr;415 /* paranoid */ verifyf( was == 1p, "Expected this.ptr to be 1p, was %p\n", was );416 417 // Mark the future as fulfilled, to be consistent418 // with potential calls to avail419 // this.ptr = 1p;420 return ret;421 }422 }423 94 #endif -
TabularUnified libcfa/src/bits/queue.hfa ¶
r467c8b7 rc08c3cf 9 9 // instead of being null. 10 10 11 forall( dtype T| { T *& Next ( T * ); } ) {11 forall( T & | { T *& Next ( T * ); } ) { 12 12 struct Queue { 13 13 inline Collection; // Plan 9 inheritance … … 151 151 } // distribution 152 152 153 forall( dtype T| { T *& Next ( T * ); } ) {153 forall( T & | { T *& Next ( T * ); } ) { 154 154 struct QueueIter { 155 155 inline ColIter; // Plan 9 inheritance -
TabularUnified libcfa/src/bits/sequence.hfa ¶
r467c8b7 rc08c3cf 29 29 30 30 // // wrappers to make Collection have T 31 // forall( dtype T) {31 // forall( T & ) { 32 32 // T *& Back( T * n ) { 33 33 // return (T *)Back( (Seqable *)n ); … … 43 43 // and the back field of the last node points at the first node (circular). 44 44 45 forall( dtype T| { T *& Back ( T * ); T *& Next ( T * ); } ) {45 forall( T & | { T *& Back ( T * ); T *& Next ( T * ); } ) { 46 46 struct Sequence { 47 47 inline Collection; // Plan 9 inheritance … … 231 231 } // distribution 232 232 233 forall( dtype T| { T *& Back ( T * ); T *& Next ( T * ); } ) {233 forall( T & | { T *& Back ( T * ); T *& Next ( T * ); } ) { 234 234 // SeqIter(T) is used to iterate over a Sequence(T) in head-to-tail order. 235 235 struct SeqIter { -
TabularUnified libcfa/src/bits/stack.hfa ¶
r467c8b7 rc08c3cf 9 9 // instead of being null. 10 10 11 forall( dtype T| { T *& Next ( T * ); } ) {11 forall( T & | { T *& Next ( T * ); } ) { 12 12 struct Stack { 13 13 inline Collection; // Plan 9 inheritance … … 67 67 // order returned by drop(). 68 68 69 forall( dtype T| { T *& Next ( T * ); } ) {69 forall( T & | { T *& Next ( T * ); } ) { 70 70 struct StackIter { 71 71 inline ColIter; // Plan 9 inheritance
Note: See TracChangeset
for help on using the changeset viewer.
