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

ADT arm-eh ast-experimental enum forall-pointer-decay jacob/cs343-translation new-ast-unique-expr pthread-emulation qualifiedEnum
Last change on this file since eeb9f9f was c993b15, checked in by Thierry Delisle <tdelisle@…>, 4 years 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.