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

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 d23c0b2 was 454f478, checked in by Thierry Delisle <tdelisle@…>, 5 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.