Index: libcfa/src/bits/locks.hfa =================================================================== --- libcfa/src/bits/locks.hfa (revision 3bb1292129f5be158f2a3192bf864d1ab2191cb9) +++ libcfa/src/bits/locks.hfa (revision 42daeb4e7403d43cd525897dd510b83f331ddae4) @@ -31,4 +31,6 @@ // previous thread to acquire the lock void* prev_thrd; + // keep track of number of times we had to spin, just in case the number is unexpectedly huge + size_t spin_count; #endif }; @@ -48,4 +50,7 @@ static inline void ?{}( __spinlock_t & this ) { this.lock = 0; + #ifdef __CFA_DEBUG__ + this.spin_count = 0; + #endif } @@ -72,4 +77,7 @@ for ( unsigned int i = 1;; i += 1 ) { if ( (this.lock == 0) && (__atomic_test_and_set( &this.lock, __ATOMIC_ACQUIRE ) == 0) ) break; + #ifdef __CFA_DEBUG__ + this.spin_count++; + #endif #ifndef NOEXPBACK // exponential spin Index: libcfa/src/bits/random.hfa =================================================================== --- libcfa/src/bits/random.hfa (revision 3bb1292129f5be158f2a3192bf864d1ab2191cb9) +++ libcfa/src/bits/random.hfa (revision 42daeb4e7403d43cd525897dd510b83f331ddae4) Index: libcfa/src/concurrency/invoke.h =================================================================== --- libcfa/src/concurrency/invoke.h (revision 3bb1292129f5be158f2a3192bf864d1ab2191cb9) +++ libcfa/src/concurrency/invoke.h (revision 42daeb4e7403d43cd525897dd510b83f331ddae4) @@ -10,6 +10,6 @@ // Created On : Tue Jan 17 12:27:26 2016 // Last Modified By : Peter A. Buhr -// Last Modified On : Thu Jan 6 16:37:40 2022 -// Update Count : 47 +// Last Modified On : Sun Jan 9 19:06:45 2022 +// Update Count : 48 // @@ -211,4 +211,6 @@ struct processor * last_proc; + uint32_t random_state; // fast random numbers + #if defined( __CFA_WITH_VERIFY__ ) void * canary; Index: libcfa/src/concurrency/io.cfa =================================================================== --- libcfa/src/concurrency/io.cfa (revision 3bb1292129f5be158f2a3192bf864d1ab2191cb9) +++ libcfa/src/concurrency/io.cfa (revision 42daeb4e7403d43cd525897dd510b83f331ddae4) @@ -548,4 +548,6 @@ /* paranoid */ verify( proc == __cfaabi_tls.this_processor ); /* paranoid */ verify( ! __preemption_enabled() ); + + return true; } #endif Index: libcfa/src/concurrency/kernel.cfa =================================================================== --- libcfa/src/concurrency/kernel.cfa (revision 3bb1292129f5be158f2a3192bf864d1ab2191cb9) +++ libcfa/src/concurrency/kernel.cfa (revision 42daeb4e7403d43cd525897dd510b83f331ddae4) @@ -554,5 +554,4 @@ /* paranoid */ verify( 0x0D15EA5E0D15EA5Ep == thrd->canary ); - const bool local = thrd->state != Start; if (thrd->preempted == __NO_PREEMPTION) thrd->state = Ready; @@ -737,5 +736,9 @@ // Check if there is a sleeping processor - int fd = __atomic_load_n(&this->procs.fd, __ATOMIC_SEQ_CST); + // int fd = __atomic_load_n(&this->procs.fd, __ATOMIC_SEQ_CST); + int fd = 0; + if( __atomic_load_n(&this->procs.fd, __ATOMIC_SEQ_CST) != 0 ) { + fd = __atomic_exchange_n(&this->procs.fd, 0, __ATOMIC_RELAXED); + } // If no one is sleeping, we are done Index: libcfa/src/concurrency/kernel/fwd.hfa =================================================================== --- libcfa/src/concurrency/kernel/fwd.hfa (revision 3bb1292129f5be158f2a3192bf864d1ab2191cb9) +++ libcfa/src/concurrency/kernel/fwd.hfa (revision 42daeb4e7403d43cd525897dd510b83f331ddae4) @@ -77,8 +77,9 @@ static inline uint64_t __tls_rand() { + return #if defined(__SIZEOF_INT128__) - return __lehmer64( kernelTLS().rand_seed ); + __lehmer64( kernelTLS().rand_seed ); #else - return __xorshift64( kernelTLS().rand_seed ); + __xorshift64( kernelTLS().rand_seed ); #endif } @@ -91,5 +92,4 @@ static inline unsigned __tls_rand_fwd() { - kernelTLS().ready_rng.fwd_seed = (A * kernelTLS().ready_rng.fwd_seed + C) & (M - 1); return kernelTLS().ready_rng.fwd_seed >> D; @@ -112,6 +112,4 @@ } } - - extern void disable_interrupts(); Index: libcfa/src/concurrency/kernel/startup.cfa =================================================================== --- libcfa/src/concurrency/kernel/startup.cfa (revision 3bb1292129f5be158f2a3192bf864d1ab2191cb9) +++ libcfa/src/concurrency/kernel/startup.cfa (revision 42daeb4e7403d43cd525897dd510b83f331ddae4) @@ -101,4 +101,5 @@ extern void __wake_proc(processor *); extern int cfa_main_returned; // from interpose.cfa +extern uint32_t __global_random_seed; //----------------------------------------------------------------------------- @@ -489,4 +490,5 @@ preferred = ready_queue_new_preferred(); last_proc = 0p; + random_state = __global_random_seed; #if defined( __CFA_WITH_VERIFY__ ) canary = 0x0D15EA5E0D15EA5Ep; Index: libcfa/src/concurrency/ready_queue.cfa =================================================================== --- libcfa/src/concurrency/ready_queue.cfa (revision 3bb1292129f5be158f2a3192bf864d1ab2191cb9) +++ libcfa/src/concurrency/ready_queue.cfa (revision 42daeb4e7403d43cd525897dd510b83f331ddae4) @@ -681,5 +681,7 @@ // Actually pop the list struct thread$ * thrd; - unsigned long long tsc_before = ts(lane); + #if defined(USE_WORK_STEALING) || defined(USE_CPU_WORK_STEALING) + unsigned long long tsc_before = ts(lane); + #endif unsigned long long tsv; [thrd, tsv] = pop(lane); Index: libcfa/src/concurrency/thread.cfa =================================================================== --- libcfa/src/concurrency/thread.cfa (revision 3bb1292129f5be158f2a3192bf864d1ab2191cb9) +++ libcfa/src/concurrency/thread.cfa (revision 42daeb4e7403d43cd525897dd510b83f331ddae4) @@ -10,6 +10,6 @@ // Created On : Tue Jan 17 12:27:26 2017 // Last Modified By : Peter A. Buhr -// Last Modified On : Wed Dec 4 09:17:49 2019 -// Update Count : 9 +// Last Modified On : Wed Jan 12 18:46:48 2022 +// Update Count : 36 // @@ -27,7 +27,9 @@ uint64_t thread_rand(); +extern uint32_t __global_random_seed; + //----------------------------------------------------------------------------- // Thread ctors and dtors -void ?{}(thread$ & this, const char * const name, cluster & cl, void * storage, size_t storageSize ) with( this ) { +void ?{}( thread$ & this, const char * const name, cluster & cl, void * storage, size_t storageSize ) with( this ) { context{ 0p, 0p }; self_cor{ name, storage, storageSize }; @@ -45,4 +47,5 @@ preferred = ready_queue_new_preferred(); last_proc = 0p; + random_state = __global_random_seed; #if defined( __CFA_WITH_VERIFY__ ) canary = 0x0D15EA5E0D15EA5Ep; @@ -177,4 +180,26 @@ return ret; } + +#define GENERATOR LCG + +static inline uint32_t MarsagliaXor( uint32_t & state ) { + uint32_t ret = state; + state ^= state << 6; + state ^= state >> 21; + state ^= state << 7; + return ret; +} // MarsagliaXor + +static inline uint32_t LCG( uint32_t & state ) { // linear congruential generator + uint32_t ret = state; + state = 36969 * (state & 65535) + (state >> 16); // 36969 is NOT prime! No not change it! + return ret; +} // LCG + +void set_seed( uint32_t seed ) { + active_thread()->random_state = __global_random_seed = seed; + GENERATOR( active_thread()->random_state ); +} // set_seed +uint32_t prng( void ) { return GENERATOR( active_thread()->random_state ); } // [0,UINT_MAX] // Local Variables: // Index: libcfa/src/device/cpu.cfa =================================================================== --- libcfa/src/device/cpu.cfa (revision 3bb1292129f5be158f2a3192bf864d1ab2191cb9) +++ libcfa/src/device/cpu.cfa (revision 42daeb4e7403d43cd525897dd510b83f331ddae4) @@ -427,10 +427,9 @@ unsigned c = pairings[i].cpu; unsigned llc_id = pairings[i].id; - unsigned width = maps[llc_id].raw->width; unsigned start = maps[llc_id].start; - unsigned self = start + (maps[llc_id].count++); - entries[c].count = width; + entries[c].count = maps[llc_id].raw->width; entries[c].start = start; - entries[c].self = self; + entries[c].self = start + (maps[llc_id].count++); + entries[c].cache = llc_id; } Index: libcfa/src/device/cpu.hfa =================================================================== --- libcfa/src/device/cpu.hfa (revision 3bb1292129f5be158f2a3192bf864d1ab2191cb9) +++ libcfa/src/device/cpu.hfa (revision 42daeb4e7403d43cd525897dd510b83f331ddae4) @@ -16,8 +16,19 @@ #include +// Map from cpu entry to a structure detailling cpus with common topologies +// Note that the cpu-groups are contiguous so the indexing is different from +// the cpu indexing struct cpu_map_entry_t { + // Where this particular cpu is in the group unsigned self; + + // Starting index of the cpus with the same topology unsigned start; + + // Number of cpus with the same topology unsigned count; + + // Index of the cache this entry describes + unsigned cache; }; Index: libcfa/src/fstream.cfa =================================================================== --- libcfa/src/fstream.cfa (revision 3bb1292129f5be158f2a3192bf864d1ab2191cb9) +++ libcfa/src/fstream.cfa (revision 42daeb4e7403d43cd525897dd510b83f331ddae4) @@ -10,6 +10,6 @@ // Created On : Wed May 27 17:56:53 2015 // Last Modified By : Peter A. Buhr -// Last Modified On : Sun Oct 10 11:23:05 2021 -// Update Count : 512 +// Last Modified On : Mon Jan 10 08:45:05 2022 +// Update Count : 513 // @@ -52,5 +52,5 @@ inline void setPrt$( ofstream & os, bool state ) { os.prt$ = state; } -inline void lock( ofstream & os ) with( os ) { lock( os.lock$ ); } +inline void lock( ofstream & os ) with( os ) { lock( os.lock$ ); } inline void unlock( ofstream & os ) { unlock( os.lock$ ); } Index: libcfa/src/startup.cfa =================================================================== --- libcfa/src/startup.cfa (revision 3bb1292129f5be158f2a3192bf864d1ab2191cb9) +++ libcfa/src/startup.cfa (revision 42daeb4e7403d43cd525897dd510b83f331ddae4) @@ -10,6 +10,6 @@ // Created On : Tue Jul 24 16:21:57 2018 // Last Modified By : Peter A. Buhr -// Last Modified On : Sat Jan 9 23:18:23 2021 -// Update Count : 34 +// Last Modified On : Wed Jan 12 18:51:24 2022 +// Update Count : 51 // @@ -18,4 +18,7 @@ #include // getenv #include "startup.hfa" +#include "bits/defs.hfa" + +extern uint32_t __global_random_seed, __global_random_state; extern "C" { @@ -48,4 +51,5 @@ void __cfaabi_core_startup( void ) __attribute__(( constructor( STARTUP_PRIORITY_CORE ) )); void __cfaabi_core_startup( void ) { + __global_random_state = __global_random_seed = rdtscl(); __cfaabi_interpose_startup(); __cfaabi_device_startup(); Index: libcfa/src/stdlib.cfa =================================================================== --- libcfa/src/stdlib.cfa (revision 3bb1292129f5be158f2a3192bf864d1ab2191cb9) +++ libcfa/src/stdlib.cfa (revision 42daeb4e7403d43cd525897dd510b83f331ddae4) @@ -10,9 +10,11 @@ // Created On : Thu Jan 28 17:10:29 2016 // Last Modified By : Peter A. Buhr -// Last Modified On : Mon Jan 3 09:36:27 2022 -// Update Count : 519 +// Last Modified On : Wed Jan 12 18:52:41 2022 +// Update Count : 582 // #include "stdlib.hfa" +//#include "concurrency/kernel/fwd.hfa" +#include "concurrency/invoke.h" // random_state //--------------------------------------- @@ -221,30 +223,32 @@ //--------------------------------------- -static uint32_t seed = 0; // current seed -static thread_local uint32_t state; // random state - -void set_seed( uint32_t seed_ ) { state = seed = seed_; } -uint32_t get_seed() { return seed; } +// Pipelined to allow OoO overlap with reduced dependencies. Critically, return the current value, and compute and store +// the next value. #define GENERATOR LCG -inline uint32_t MarsagliaXor( uint32_t & state ) { - if ( unlikely( seed == 0 ) ) set_seed( rdtscl() ); - else if ( unlikely( state == 0 ) ) state = seed; +static inline uint32_t MarsagliaXor( uint32_t & state ) { + uint32_t ret = state; state ^= state << 6; state ^= state >> 21; state ^= state << 7; - return state; + return ret; } // MarsagliaXor -inline uint32_t LCG( uint32_t & state ) { // linear congruential generator - if ( unlikely( seed == 0 ) ) set_seed( rdtscl() ); - else if ( unlikely( state == 0 ) ) state = seed; - return state = 36969 * (state & 65535) + (state >> 16); // 36969 is NOT prime! +static inline uint32_t LCG( uint32_t & state ) { // linear congruential generator + uint32_t ret = state; + state = 36969 * (state & 65535) + (state >> 16); // 36969 is NOT prime! No not change it! + return ret; } // LCG +uint32_t __global_random_seed; // sequential/concurrent +uint32_t __global_random_state; // sequential only + +void set_seed( PRNG & prng, uint32_t seed_ ) with( prng ) { state = seed = seed_; GENERATOR( state ); } // set seed uint32_t prng( PRNG & prng ) with( prng ) { callcnt += 1; return GENERATOR( state ); } -uint32_t prng( void ) { return GENERATOR( state ); } +void set_seed( uint32_t seed ) { __global_random_seed = seed; GENERATOR( __global_random_state ); } +uint32_t get_seed() { return __global_random_seed; } +uint32_t prng( void ) { return GENERATOR( __global_random_state ); } // [0,UINT_MAX] //--------------------------------------- Index: libcfa/src/stdlib.hfa =================================================================== --- libcfa/src/stdlib.hfa (revision 3bb1292129f5be158f2a3192bf864d1ab2191cb9) +++ libcfa/src/stdlib.hfa (revision 42daeb4e7403d43cd525897dd510b83f331ddae4) @@ -10,6 +10,6 @@ // Created On : Thu Jan 28 17:12:35 2016 // Last Modified By : Peter A. Buhr -// Last Modified On : Sun Jan 2 22:53:57 2022 -// Update Count : 594 +// Last Modified On : Wed Jan 12 18:56:13 2022 +// Update Count : 621 // @@ -21,4 +21,5 @@ #include // *alloc, strto*, ato* #include + // Reduce includes by explicitly defining these routines. @@ -385,4 +386,23 @@ //--------------------------------------- +// Sequential Pseudo Random-Number Generator : generate repeatable sequence of values that appear random. +// +// Declaration : +// PRNG sprng = { 1009 } - set starting seed versus random seed +// +// Interface : +// set_seed( sprng, 1009 ) - set starting seed for ALL kernel threads versus random seed +// get_seed( sprng ) - read seed +// prng( sprng ) - generate random value in range [0,UINT_MAX] +// prng( sprng, u ) - generate random value in range [0,u) +// prng( sprng, l, u ) - generate random value in range [l,u] +// calls( sprng ) - number of generated random value so far +// +// Examples : generate random number between 5-21 +// prng( sprng ) % 17 + 5; values 0-16 + 5 = 5-21 +// prng( sprng, 16 + 1 ) + 5; +// prng( sprng, 5, 21 ); +// calls( sprng ); + struct PRNG { uint32_t callcnt; // call count @@ -391,7 +411,7 @@ }; // PRNG -extern uint32_t prng( PRNG & prng ) __attribute__(( warn_unused_result )); // [0,UINT_MAX] +void set_seed( PRNG & prng, uint32_t seed_ ); +uint32_t prng( PRNG & prng ) __attribute__(( warn_unused_result )); // [0,UINT_MAX] static inline { - void set_seed( PRNG & prng, uint32_t seed_ ) with( prng ) { state = seed = seed_; } // set seed void ?{}( PRNG & prng ) { set_seed( prng, rdtscl() ); } // random seed void ?{}( PRNG & prng, uint32_t seed ) { set_seed( prng, seed ); } // fixed seed @@ -402,12 +422,24 @@ } // distribution -extern void set_seed( uint32_t seed ); // set per thread seed -extern uint32_t get_seed(); // get seed -extern uint32_t prng( void ) __attribute__(( warn_unused_result )); // [0,UINT_MAX] +// Concurrent Pseudo Random-Number Generator : generate repeatable sequence of values that appear random. +// +// Interface : +// set_seed( 1009 ) - fixed seed for all kernel threads versus random seed +// get_seed() - read seed +// prng() - generate random value in range [0,UINT_MAX] +// prng( u ) - generate random value in range [0,u) +// prng( l, u ) - generate random value in range [l,u] +// +// Examples : generate random number between 5-21 +// prng() % 17 + 5; values 0-16 + 5 = 5-21 +// prng( 16 + 1 ) + 5; +// prng( 5, 21 ); + +void set_seed( uint32_t seed_ ) OPTIONAL_THREAD; +uint32_t get_seed() __attribute__(( warn_unused_result )); +uint32_t prng( void ) __attribute__(( warn_unused_result )) OPTIONAL_THREAD; // [0,UINT_MAX] static inline { - uint32_t prng( uint32_t u ) __attribute__(( warn_unused_result )); - uint32_t prng( uint32_t u ) { return prng() % u; } // [0,u) - uint32_t prng( uint32_t l, uint32_t u ) __attribute__(( warn_unused_result )); - uint32_t prng( uint32_t l, uint32_t u ) { return prng( u - l + 1 ) + l; } // [l,u] + uint32_t prng( uint32_t u ) __attribute__(( warn_unused_result )) { return prng() % u; } // [0,u) + uint32_t prng( uint32_t l, uint32_t u ) __attribute__(( warn_unused_result )) { return prng( u - l + 1 ) + l; } // [l,u] } // distribution Index: tests/io/io-acquire.cfa =================================================================== --- tests/io/io-acquire.cfa (revision 3bb1292129f5be158f2a3192bf864d1ab2191cb9) +++ tests/io/io-acquire.cfa (revision 42daeb4e7403d43cd525897dd510b83f331ddae4) @@ -10,6 +10,6 @@ // Created On : Mon Mar 1 18:40:09 2021 // Last Modified By : Peter A. Buhr -// Last Modified On : Wed Oct 6 18:04:58 2021 -// Update Count : 72 +// Last Modified On : Mon Jan 10 07:57:12 2022 +// Update Count : 73 // @@ -23,5 +23,5 @@ for ( 100 ) { // expression protection - mutex(sout) sout | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9; + mutex( sout ) sout | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9; } mutex( sout ) { // statement protection @@ -51,5 +51,5 @@ int a, b, c, d, e, f, g, h, i; for ( 100 ) { // expression protection - mutex(sin) sin | a | b | c | d | e | f | g | h | i; + mutex( sin ) sin | a | b | c | d | e | f | g | h | i; } mutex( sin ) { // statement protection Index: tests/io/io-acquire2.cfa =================================================================== --- tests/io/io-acquire2.cfa (revision 42daeb4e7403d43cd525897dd510b83f331ddae4) +++ tests/io/io-acquire2.cfa (revision 42daeb4e7403d43cd525897dd510b83f331ddae4) @@ -0,0 +1,87 @@ +// +// Cforall Version 1.0.0 Copyright (C) 2015 University of Waterloo +// +// The contents of this file are covered under the licence agreement in the +// file "LICENCE" distributed with Cforall. +// +// io-acquire.cfa -- +// +// Author : Peter A. Buhr +// Created On : Mon Mar 1 18:40:09 2021 +// Last Modified By : Peter A. Buhr +// Last Modified On : Mon Jan 10 16:10:20 2022 +// Update Count : 74 +// + +#include +#include +#include + +Duration default_preemption() { return 0; } + +thread T {}; +void main( T & ) { + // output from parallel threads should not be scrambled + + for ( 100 ) { // expression protection + mutex( sout ) sout | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9; + } + mutex( sout ) { // statement protection + for ( 100 ) { + sout | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9; + } + } + { // duplicate protection demonstrating recursive lock + ofstream & h1( ofstream & os ) { // helper + mutex( os ) return os | 1 | 2 | 3 | 4; // unnecessary mutex + } + ofstream & h2( ofstream & os ) { // helper + mutex( os ) return os | 6 | 7 | 8 | 9; // unnecessary mutex + } + mutex( sout ) { // unnecessary mutex + for ( 100 ) { + mutex( sout ) { + sout | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9; + sout | h1 | 5 | h2; // refactored code + } + } + } + } + + // above output used as input to parallel threads + + int a, b, c, d, e, f, g, h, i; + for ( 100 ) { // expression protection + mutex( sin ) sin | a | b | c | d | e | f | g | h | i; + } + mutex( sin ) { // statement protection + for ( 100 ) { + sin | a | b | c | d | e | f | g | h | i; + } + } + { // duplicate protection demonstrating recursive lock + ifstream & h1( ifstream & is ) { // helper + mutex( is ) return is | a | b | c | d; // unnecessary mutex + } + ifstream & h2( ifstream & is ) { // helper + mutex( is ) return is | f | g | h | i; // unnecessary mutex + } + mutex( sin ) { // unnecessary mutex + for ( 5 ) { + mutex( sin ) { + sin | a | b | c | d | e | f | g | h | i; + sin | h1 | e | h2; // refactored code + } + } + } + } +} +int main() { + processor p; + T t[5]; +} + +// Local Variables: // +// tab-width: 4 // +// compile-command: "cfa io-acquire2.cfa" // +// End: // Index: tools/jenkins/setup.sh.in =================================================================== --- tools/jenkins/setup.sh.in (revision 3bb1292129f5be158f2a3192bf864d1ab2191cb9) +++ tools/jenkins/setup.sh.in (revision 42daeb4e7403d43cd525897dd510b83f331ddae4) @@ -48,5 +48,5 @@ regex1='/([[:alpha:][:digit:]@/_.-]+)' regex2='(libcfa[[:alpha:][:digit:].]+) => not found' - regex3='linux-vdso.so.1' + regex3='linux-vdso.so.1|linux-gate.so.1' if [[ $line =~ $regex1 ]]; then retsysdeps+=(${BASH_REMATCH[1]})