source: libcfa/src/concurrency/kernel/fwd.hfa @ 9b71679

ADTarm-ehast-experimentalenumforall-pointer-decayjacob/cs343-translationnew-ast-unique-exprpthread-emulationqualifiedEnum
Last change on this file since 9b71679 was 454f478, checked in by Thierry Delisle <tdelisle@…>, 4 years ago

Re-arranged and commented low-level headers.
Main goal was for better support of weakso locks that are comming.

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