source: libcfa/src/concurrency/kernel/fwd.hfa @ c25338d

ADTast-experimentalpthread-emulationqualifiedEnum
Last change on this file since c25338d was f3da205, checked in by Thierry Delisle <tdelisle@…>, 22 months ago

Fixed wait_any to be polymorphic on future type.

  • Property mode set to 100644
File size: 13.1 KB
RevLine 
[e660761]1//
2// Cforall Version 1.0.0 Copyright (C) 2020 University of Waterloo
3//
4// The contents of this file are covered under the licence agreement in the
5// file "LICENCE" distributed with Cforall.
6//
[454f478]7// kernel/fwd.hfa -- PUBLIC
8// Fundamental code needed to implement threading M.E.S. algorithms.
[e660761]9//
10// Author           : Thierry Delisle
11// Created On       : Thu Jul 30 16:46:41 2020
12// Last Modified By :
13// Last Modified On :
14// Update Count     :
15//
16
[3e2b9c9]17#pragma once
18
[e660761]19#include "bits/defs.hfa"
20#include "bits/debug.hfa"
21
[3e2b9c9]22#ifdef __cforall
23#include "bits/random.hfa"
[e660761]24#endif
25
[e84ab3d]26struct thread$;
[e660761]27struct processor;
28struct cluster;
29
[3e2b9c9]30enum __Preemption_Reason { __NO_PREEMPTION, __ALARM_PREEMPTION, __POLL_PREEMPTION, __MANUAL_PREEMPTION };
31
32#define KERNEL_STORAGE(T,X) __attribute((aligned(__alignof__(T)))) static char storage_##X[sizeof(T)]
33
[e660761]34#ifdef __cforall
35extern "C" {
[3e2b9c9]36        extern "Cforall" {
[e660761]37                extern __attribute__((aligned(128))) thread_local struct KernelThreadData {
[e84ab3d]38                        struct thread$          * volatile this_thread;
[e873838]39                        struct processor        * volatile this_processor;
[c993b15]40                        volatile bool sched_lock;
[e660761]41
42                        struct {
43                                volatile unsigned short disable_count;
44                                volatile bool enabled;
45                                volatile bool in_progress;
46                        } preemption_state;
47
48                        #if defined(__SIZEOF_INT128__)
49                                __uint128_t rand_seed;
50                        #else
51                                uint64_t rand_seed;
52                        #endif
[f2384c9a]53                        struct {
54                                uint64_t fwd_seed;
55                                uint64_t bck_seed;
56                        } ready_rng;
[c993b15]57
58                        struct __stats_t        * volatile this_stats;
59
60
61                        #ifdef __CFA_WITH_VERIFY__
62                                // Debug, check if the rwlock is owned for reading
63                                bool in_sched_lock;
64                                unsigned sched_id;
65                        #endif
[8fc652e0]66                } __cfaabi_tls __attribute__ ((tls_model ( "initial-exec" )));
[3e2b9c9]67
[8fc652e0]68                extern bool __preemption_enabled();
[f2384c9a]69
[8fc652e0]70                static inline KernelThreadData & kernelTLS( void ) {
71                        /* paranoid */ verify( ! __preemption_enabled() );
72                        return __cfaabi_tls;
73                }
74
75                extern uintptr_t __cfatls_get( unsigned long int member );
[82a2fed]76                #define publicTLS_get( member ) ((typeof(__cfaabi_tls.member))__cfatls_get( __builtin_offsetof(KernelThreadData, member) ))
[f2384c9a]77
[3e2b9c9]78                static inline uint64_t __tls_rand() {
[c52f033]79                        return
[3e2b9c9]80                        #if defined(__SIZEOF_INT128__)
[5d1ebb9]81                                lehmer64( kernelTLS().rand_seed );
[3e2b9c9]82                        #else
[5d1ebb9]83                                xorshift_13_7_17( kernelTLS().rand_seed );
[3e2b9c9]84                        #endif
85                }
[f2384c9a]86
87                static inline unsigned __tls_rand_fwd() {
[5d1ebb9]88                        return LCGBI_fwd( kernelTLS().ready_rng.fwd_seed );
[f2384c9a]89                }
90
91                static inline unsigned __tls_rand_bck() {
[5d1ebb9]92                        return LCGBI_bck( kernelTLS().ready_rng.bck_seed );
[f2384c9a]93                }
94
95                static inline void __tls_rand_advance_bck(void) {
[8fc652e0]96                        kernelTLS().ready_rng.bck_seed = kernelTLS().ready_rng.fwd_seed;
[f2384c9a]97                }
[e660761]98        }
99
[3e2b9c9]100        extern void disable_interrupts();
[a3821fa]101        extern void enable_interrupts( bool poll = false );
[e660761]102
[3e2b9c9]103        extern "Cforall" {
[24e321c]104                enum unpark_hint { UNPARK_LOCAL, UNPARK_REMOTE };
105
[e235429]106                extern void park( void );
[24e321c]107                extern void unpark( struct thread$ *, unpark_hint );
108                static inline void unpark( struct thread$ * thrd ) { unpark(thrd, UNPARK_LOCAL); }
[e84ab3d]109                static inline struct thread$ * active_thread () {
110                        struct thread$ * t = publicTLS_get( this_thread );
[8fc652e0]111                        /* paranoid */ verify( t );
112                        return t;
113                }
[3e2b9c9]114
115                extern bool force_yield( enum __Preemption_Reason );
[e660761]116
[3e2b9c9]117                static inline void yield() {
118                        force_yield(__MANUAL_PREEMPTION);
119                }
[e660761]120
[3e2b9c9]121                // Yield: yield N times
122                static inline void yield( unsigned times ) {
123                        for( times ) {
124                                yield();
125                        }
126                }
127
[454f478]128                // Semaphore which only supports a single thread
129                struct single_sem {
[e84ab3d]130                        struct thread$ * volatile ptr;
[454f478]131                };
132
133                static inline {
134                        void  ?{}(single_sem & this) {
135                                this.ptr = 0p;
136                        }
137
138                        void ^?{}(single_sem &) {}
139
140                        bool wait(single_sem & this) {
141                                for() {
[e84ab3d]142                                        struct thread$ * expected = this.ptr;
[454f478]143                                        if(expected == 1p) {
144                                                if(__atomic_compare_exchange_n(&this.ptr, &expected, 0p, false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)) {
145                                                        return false;
146                                                }
147                                        }
148                                        else {
149                                                /* paranoid */ verify( expected == 0p );
150                                                if(__atomic_compare_exchange_n(&this.ptr, &expected, active_thread(), false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)) {
151                                                        park();
152                                                        return true;
153                                                }
154                                        }
155
156                                }
157                        }
158
159                        bool post(single_sem & this) {
160                                for() {
[e84ab3d]161                                        struct thread$ * expected = this.ptr;
[454f478]162                                        if(expected == 1p) return false;
163                                        if(expected == 0p) {
164                                                if(__atomic_compare_exchange_n(&this.ptr, &expected, 1p, false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)) {
165                                                        return false;
166                                                }
167                                        }
168                                        else {
169                                                if(__atomic_compare_exchange_n(&this.ptr, &expected, 0p, false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)) {
170                                                        unpark( expected );
171                                                        return true;
172                                                }
173                                        }
174                                }
175                        }
176                }
177
178                // Synchronozation primitive which only supports a single thread and one post
179                // Similar to a binary semaphore with a 'one shot' semantic
180                // is expected to be discarded after each party call their side
181                struct oneshot {
182                        // Internal state :
183                        //     0p     : is initial state (wait will block)
184                        //     1p     : fulfilled (wait won't block)
185                        // any thread : a thread is currently waiting
[e84ab3d]186                        struct thread$ * volatile ptr;
[454f478]187                };
188
189                static inline {
190                        void  ?{}(oneshot & this) {
191                                this.ptr = 0p;
192                        }
193
194                        void ^?{}(oneshot &) {}
195
196                        // Wait for the post, return immidiately if it already happened.
197                        // return true if the thread was parked
198                        bool wait(oneshot & this) {
199                                for() {
[e84ab3d]200                                        struct thread$ * expected = this.ptr;
[454f478]201                                        if(expected == 1p) return false;
202                                        if(__atomic_compare_exchange_n(&this.ptr, &expected, active_thread(), false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)) {
203                                                park();
204                                                /* paranoid */ verify( this.ptr == 1p );
205                                                return true;
206                                        }
207                                }
208                        }
209
210                        // Mark as fulfilled, wake thread if needed
211                        // return true if a thread was unparked
[e84ab3d]212                        thread$ * post(oneshot & this, bool do_unpark = true) {
213                                struct thread$ * got = __atomic_exchange_n( &this.ptr, 1p, __ATOMIC_SEQ_CST);
[c06551b]214                                if( got == 0p || got == 1p ) return 0p;
[a76efc8]215                                if(do_unpark) unpark( got );
216                                return got;
[454f478]217                        }
218                }
219
220                // base types for future to build upon
221                // It is based on the 'oneshot' type to allow multiple futures
222                // to block on the same instance, permitting users to block a single
223                // thread on "any of" [a given set of] futures.
224                // does not support multiple threads waiting on the same future
225                struct future_t {
226                        // Internal state :
227                        //     0p      : is initial state (wait will block)
228                        //     1p      : fulfilled (wait won't block)
229                        //     2p      : in progress ()
230                        //     3p      : abandoned, server should delete
231                        // any oneshot : a context has been setup to wait, a thread could wait on it
232                        struct oneshot * volatile ptr;
233                };
234
235                static inline {
236                        void  ?{}(future_t & this) {
237                                this.ptr = 0p;
238                        }
239
240                        void ^?{}(future_t &) {}
241
242                        void reset(future_t & this) {
243                                // needs to be in 0p or 1p
244                                __atomic_exchange_n( &this.ptr, 0p, __ATOMIC_SEQ_CST);
245                        }
246
247                        // check if the future is available
248                        bool available( future_t & this ) {
[64bdacc]249                                while( this.ptr == 2p ) Pause();
[454f478]250                                return this.ptr == 1p;
251                        }
252
253                        // Prepare the future to be waited on
254                        // intented to be use by wait, wait_any, waitfor, etc. rather than used directly
255                        bool setup( future_t & this, oneshot & wait_ctx ) {
256                                /* paranoid */ verify( wait_ctx.ptr == 0p );
257                                // The future needs to set the wait context
258                                for() {
259                                        struct oneshot * expected = this.ptr;
260                                        // Is the future already fulfilled?
261                                        if(expected == 1p) return false; // Yes, just return false (didn't block)
262
263                                        // The future is not fulfilled, try to setup the wait context
264                                        if(__atomic_compare_exchange_n(&this.ptr, &expected, &wait_ctx, false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)) {
265                                                return true;
266                                        }
267                                }
268                        }
269
270                        // Stop waiting on a future
271                        // When multiple futures are waited for together in "any of" pattern
272                        // futures that weren't fulfilled before the thread woke up
273                        // should retract the wait ctx
274                        // intented to be use by wait, wait_any, waitfor, etc. rather than used directly
[c06551b]275                        bool retract( future_t & this, oneshot & wait_ctx ) {
[1c56bf7]276                                for() {
277                                        struct oneshot * expected = this.ptr;
[454f478]278
[1c56bf7]279                                        // expected == 0p: future was never actually setup, just return
280                                        if( expected == 0p ) return false;
281
282                                        // expected == 1p: the future is ready and the context was fully consumed
283                                        // the server won't use the pointer again
284                                        // It is safe to delete (which could happen after the return)
285                                        if( expected == 1p ) return true;
286
287                                        // expected == 2p: the future is ready but the context hasn't fully been consumed
288                                        // spin until it is safe to move on
289                                        if( expected == 2p ) {
290                                                while( this.ptr != 1p ) Pause();
291                                                /* paranoid */ verify( this.ptr != 1p );
292                                                return true;
293                                        }
294
295                                        // expected != wait_ctx: the future was setup with a different context ?!?!
296                                        // something went wrong here, abort
297                                        if( expected != &wait_ctx ) abort("Future in unexpected state");
298
299                                        // we still have the original context, then no one else saw it
300                                        // attempt to remove the context so it doesn't get consumed.
301                                        if(__atomic_compare_exchange_n( &this.ptr, &expected, 0p, false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)) {
302                                                return false;
303                                        }
304                                }
[454f478]305                        }
306
307                        // Mark the future as abandoned, meaning it will be deleted by the server
308                        bool abandon( future_t & this ) {
309                                /* paranoid */ verify( this.ptr != 3p );
310
311                                // Mark the future as abandonned
312                                struct oneshot * got = __atomic_exchange_n( &this.ptr, 3p, __ATOMIC_SEQ_CST);
313
314                                // If the future isn't already fulfilled, let the server delete it
315                                if( got == 0p ) return false;
316
317                                // got == 2p: the future is ready but the context hasn't fully been consumed
318                                // spin until it is safe to move on
319                                if( got == 2p ) {
320                                        while( this.ptr != 1p ) Pause();
321                                        got = 1p;
322                                }
323
324                                // The future is completed delete it now
325                                /* paranoid */ verify( this.ptr != 1p );
326                                free( &this );
327                                return true;
328                        }
329
330                        // from the server side, mark the future as fulfilled
331                        // delete it if needed
[e84ab3d]332                        thread$ * fulfil( future_t & this, bool do_unpark = true  ) {
[454f478]333                                for() {
334                                        struct oneshot * expected = this.ptr;
335                                        // was this abandoned?
336                                        #if defined(__GNUC__) && __GNUC__ >= 7
337                                                #pragma GCC diagnostic push
338                                                #pragma GCC diagnostic ignored "-Wfree-nonheap-object"
339                                        #endif
[a76efc8]340                                                if( expected == 3p ) { free( &this ); return 0p; }
[454f478]341                                        #if defined(__GNUC__) && __GNUC__ >= 7
342                                                #pragma GCC diagnostic pop
343                                        #endif
344
345                                        /* paranoid */ verify( expected != 1p ); // Future is already fulfilled, should not happen
346                                        /* paranoid */ verify( expected != 2p ); // Future is bein fulfilled by someone else, this is even less supported then the previous case.
347
348                                        // If there is a wait context, we need to consume it and mark it as consumed after
349                                        // If there is no context then we can skip the in progress phase
350                                        struct oneshot * want = expected == 0p ? 1p : 2p;
351                                        if(__atomic_compare_exchange_n(&this.ptr, &expected, want, false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)) {
[13fdf86]352                                                if( expected == 0p ) { return 0p; }
[e84ab3d]353                                                thread$ * ret = post( *expected, do_unpark );
[454f478]354                                                __atomic_store_n( &this.ptr, 1p, __ATOMIC_SEQ_CST);
355                                                return ret;
356                                        }
357                                }
358
359                        }
360
361                        // Wait for the future to be fulfilled
362                        bool wait( future_t & this ) {
363                                oneshot temp;
364                                if( !setup(this, temp) ) return false;
365
366                                // Wait context is setup, just wait on it
367                                bool ret = wait( temp );
368
369                                // Wait for the future to tru
370                                while( this.ptr == 2p ) Pause();
371                                // Make sure the state makes sense
372                                // Should be fulfilled, could be in progress but it's out of date if so
373                                // since if that is the case, the oneshot was fulfilled (unparking this thread)
374                                // and the oneshot should not be needed any more
375                                __attribute__((unused)) struct oneshot * was = this.ptr;
376                                /* paranoid */ verifyf( was == 1p, "Expected this.ptr to be 1p, was %p\n", was );
377
378                                // Mark the future as fulfilled, to be consistent
379                                // with potential calls to avail
380                                // this.ptr = 1p;
381                                return ret;
382                        }
[c06551b]383
384                        // Wait for any future to be fulfilled
[f3da205]385                        forall(T& | sized(T) | { bool setup( T&, oneshot & ); bool retract( T&, oneshot & ); })
386                        T & wait_any( T * futures, size_t num_futures ) {
[c06551b]387                                oneshot temp;
388
389                                // setup all futures
390                                // if any are already satisfied return
391                                for ( i; num_futures ) {
392                                        if( !setup(futures[i], temp) ) return futures[i];
393                                }
[f3da205]394
[c06551b]395                                // Wait context is setup, just wait on it
396                                wait( temp );
[f3da205]397
[c06551b]398                                size_t ret;
399                                // attempt to retract all futures
400                                for ( i; num_futures ) {
401                                        if ( retract( futures[i], temp ) ) ret = i;
402                                }
[f3da205]403
[c06551b]404                                return futures[ret];
405                        }
[454f478]406                }
407
[3e2b9c9]408                //-----------------------------------------------------------------------
409                // Statics call at the end of each thread to register statistics
410                #if !defined(__CFA_NO_STATISTICS__)
411                        static inline struct __stats_t * __tls_stats() {
[8fc652e0]412                                /* paranoid */ verify( ! __preemption_enabled() );
413                                /* paranoid */ verify( kernelTLS().this_stats );
414                                return kernelTLS().this_stats;
[3e2b9c9]415                        }
416
417                        #define __STATS__(in_kernel, ...) { \
418                                if( !(in_kernel) ) disable_interrupts(); \
419                                with( *__tls_stats() ) { \
420                                        __VA_ARGS__ \
421                                } \
[a3821fa]422                                if( !(in_kernel) ) enable_interrupts(); \
[3e2b9c9]423                        }
[c9c1c1c]424                        #if defined(CFA_HAVE_LINUX_IO_URING_H)
425                                #define __IO_STATS__(in_kernel, ...) { \
426                                        if( !(in_kernel) ) disable_interrupts(); \
427                                        with( *__tls_stats() ) { \
428                                                __VA_ARGS__ \
429                                        } \
430                                        if( !(in_kernel) ) enable_interrupts(); \
431                                }
432                        #else
433                                #define __IO_STATS__(in_kernel, ...)
434                        #endif
[3e2b9c9]435                #else
436                        #define __STATS__(in_kernel, ...)
[c9c1c1c]437                        #define __IO_STATS__(in_kernel, ...)
[3e2b9c9]438                #endif
439        }
[e660761]440}
[442b624]441#endif
Note: See TracBrowser for help on using the repository browser.