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

arm-ehjacob/cs343-translationnew-ast-unique-expr
Last change on this file since c993b15 was c993b15, checked in by Thierry Delisle <tdelisle@…>, 7 months ago

Changed RW lock to avoid hitting the global array on schedule.

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