source: libcfa/src/concurrency/locks.cfa @ c131a02

ADTarm-ehast-experimentalenumforall-pointer-decayjacob/cs343-translationnew-ast-unique-exprpthread-emulationqualifiedEnum
Last change on this file since c131a02 was c131a02, checked in by Colby Alexander Parsons <caparsons@…>, 3 years ago

added support for threads in sequence
  • Property mode set to 100644
File size: 17.4 KB
Line 
1#include "locks.hfa"
2#include "kernel_private.hfa"
3#include <stdlib.h>
4#include <stdio.h>
5
6#include <kernel.hfa>
7#include <stdlib.hfa>
8#include <thread.hfa>
9
10///////////////////////////////////////////////////////////////////
11//// info_thread
12///////////////////////////////////////////////////////////////////
13
14forall(dtype L | is_blocking_lock(L)) {
15        void ?{}( info_thread(L) & this, $thread * t ) {
16                ((Seqable &) this){};
17                this.t = t;
18                this.lock = 0p;
19                this.listed = false;
20        }
21
22        void ?{}( info_thread(L) & this, $thread * t, uintptr_t info ) {
23                ((Seqable &) this){};
24                this.t = t;
25                this.info = info;
26                this.lock = 0p;
27                this.listed = false;
28        }
29
30        void ^?{}( info_thread(L) & this ){ }
31
32        info_thread(L) *& Back( info_thread(L) * this ) {
33                return (info_thread(L) *)Back( (Seqable *)this );
34        }
35
36        info_thread(L) *& Next( info_thread(L) * this ) {
37                return (info_thread(L) *)Next( (Colable *)this );
38        }
39
40        bool listed( info_thread(L) * this ) {
41                return Next( (Colable *)this ) != 0p;
42        }
43}
44
45///////////////////////////////////////////////////////////////////
46//// Blocking Locks
47///////////////////////////////////////////////////////////////////
48
49void ?{}( blocking_lock & this, bool multi_acquisition, bool strict_owner ) {
50        this.lock{};
51        this.blocked_threads{};
52        this.wait_count = 0;
53        this.multi_acquisition = multi_acquisition;
54        this.strict_owner = strict_owner;
55        this.owner = 0p;
56        this.recursion_count = 0;
57}
58
59void ^?{}( blocking_lock & this ) {}
60void ?{}( single_acquisition_lock & this ) {((blocking_lock &)this){ false, false };}
61void ^?{}( single_acquisition_lock & this ) {}
62void ?{}( owner_lock & this ) {((blocking_lock &)this){ true, true };}
63void ^?{}( owner_lock & this ) {}
64void ?{}( multiple_acquisition_lock & this ) {((blocking_lock &)this){ true, false };}
65void ^?{}( multiple_acquisition_lock & this ) {}
66
67void lock( blocking_lock & this ) with( this ) {
68        lock( lock __cfaabi_dbg_ctx2 );
69        if ( owner == active_thread() && !multi_acquisition) {
70                abort("A single acquisition lock holder attempted to reacquire the lock resulting in a deadlock.");
71        } else if ( owner != 0p && owner != active_thread() ) {
72                addTail( blocked_threads, *active_thread() );
73                wait_count++;
74                unlock( lock );
75                park( );
76        } else if ( owner == active_thread() && multi_acquisition ) {
77                recursion_count++;
78                unlock( lock );
79        } else {
80                owner = active_thread();
81                recursion_count = 1;
82                unlock( lock );
83        }
84}
85
86bool try_lock( blocking_lock & this ) with( this ) {
87        bool ret = false;
88        lock( lock __cfaabi_dbg_ctx2 );
89        if ( owner == 0p ) {
90                owner = active_thread();
91                recursion_count = 1;
92                ret = true;
93        } else if ( owner == active_thread() && multi_acquisition ) {
94                recursion_count++;
95                ret = true;
96        }
97        unlock( lock );
98        return ret;
99}
100
101void unlock_error_check( blocking_lock & this ) with( this ) {
102        if ( owner == 0p ){ // no owner implies lock isn't held
103                abort( "There was an attempt to release a lock that isn't held" );
104        } else if ( strict_owner && owner != active_thread() ) {
105                abort( "A thread other than the owner attempted to release an owner lock" );
106        }
107}
108
109void pop_and_set_new_owner( blocking_lock & this ) with( this ) {
110        $thread * t = &dropHead( blocked_threads );
111        owner = t;
112        recursion_count = ( t ? 1 : 0 );
113        wait_count--;
114        unpark( t );
115}
116
117void unlock( blocking_lock & this ) with( this ) {
118        lock( lock __cfaabi_dbg_ctx2 );
119        unlock_error_check( this );
120        recursion_count--;
121        if ( recursion_count == 0 ) {
122                pop_and_set_new_owner( this );
123        }
124        unlock( lock );
125}
126
127size_t wait_count( blocking_lock & this ) with( this ) {
128        return wait_count;
129}
130
131void set_recursion_count( blocking_lock & this, size_t recursion ) with( this ) {
132        recursion_count = recursion;
133}
134
135size_t get_recursion_count( blocking_lock & this ) with( this ) {
136        return recursion_count;
137}
138
139void add_( blocking_lock & this, $thread * t ) with( this ) {
140    lock( lock __cfaabi_dbg_ctx2 );
141        if ( owner != 0p ) {
142                addTail( blocked_threads, *t );
143                wait_count++;
144                unlock( lock );
145        } else {
146                owner = t;
147                recursion_count = 1;
148                unpark( t );
149                unlock( lock );
150        }
151}
152
153void remove_( blocking_lock & this ) with( this ) {
154    lock( lock __cfaabi_dbg_ctx2 );
155        unlock_error_check( this );
156        pop_and_set_new_owner( this );
157        unlock( lock );
158}
159
160///////////////////////////////////////////////////////////////////
161//// Overloaded routines for traits
162///////////////////////////////////////////////////////////////////
163
164// This is temporary until an inheritance bug is fixed
165
166void lock( single_acquisition_lock & this ){ lock( (blocking_lock &)this ); }
167void unlock( single_acquisition_lock & this ){ unlock( (blocking_lock &)this ); }
168void add_( single_acquisition_lock & this, struct $thread * t ){ add_( (blocking_lock &)this, t ); }
169void remove_( single_acquisition_lock & this ){ remove_( (blocking_lock &)this ); }
170void set_recursion_count( single_acquisition_lock & this, size_t recursion ){ set_recursion_count( (blocking_lock &)this, recursion ); }
171size_t get_recursion_count( single_acquisition_lock & this ){ return get_recursion_count( (blocking_lock &)this ); }
172
173void lock( owner_lock & this ){ lock( (blocking_lock &)this ); }
174void unlock( owner_lock & this ){ unlock( (blocking_lock &)this ); }
175void add_( owner_lock & this, struct $thread * t ){ add_( (blocking_lock &)this, t ); }
176void remove_( owner_lock & this ){ remove_( (blocking_lock &)this ); }
177void set_recursion_count( owner_lock & this, size_t recursion ){ set_recursion_count( (blocking_lock &)this, recursion ); }
178size_t get_recursion_count( owner_lock & this ){ return get_recursion_count( (blocking_lock &)this ); }
179
180void lock( multiple_acquisition_lock & this ){ lock( (blocking_lock &)this ); }
181void unlock( multiple_acquisition_lock & this ){ unlock( (blocking_lock &)this ); }
182void add_( multiple_acquisition_lock & this, struct $thread * t ){ add_( (blocking_lock &)this, t ); }
183void remove_( multiple_acquisition_lock & this ){ remove_( (blocking_lock &)this ); }
184void set_recursion_count( multiple_acquisition_lock & this, size_t recursion ){ set_recursion_count( (blocking_lock &)this, recursion ); }
185size_t get_recursion_count( multiple_acquisition_lock & this ){ return get_recursion_count( (blocking_lock &)this ); }
186
187///////////////////////////////////////////////////////////////////
188//// condition variable
189///////////////////////////////////////////////////////////////////
190
191forall(dtype L | is_blocking_lock(L)) {
192
193        void timeout_handler ( alarm_node_wrap(L) & this ) with( this ) {
194        // This condition_variable member is called from the kernel, and therefore, cannot block, but it can spin.
195            lock( cond->lock __cfaabi_dbg_ctx2 );
196           
197            if ( i->listed ) {                  // is thread on queue
198                cond->last_thread = i;          // REMOVE THIS AFTER DEBUG
199                        remove( cond->blocked_threads, *i );             //remove this thread O(1)
200                        cond->count--;
201                        if( !i->lock ) {
202                                unpark( i->t );
203                } else {
204                        add_(*i->lock, i->t);                   // call lock's add_
205                }
206            }
207            unlock( cond->lock );
208        }
209
210        void alarm_node_wrap_cast( alarm_node_t & a ) { timeout_handler( (alarm_node_wrap(L) &)a ); }
211
212        void ?{}( condition_variable(L) & this ){
213                this.lock{};
214                this.blocked_threads{};
215                this.count = 0;
216                this.last_thread = 0p; // REMOVE AFTER DEBUG
217        }
218
219        void ^?{}( condition_variable(L) & this ){ }
220
221        void ?{}( alarm_node_wrap(L) & this, Time alarm, Duration period, Alarm_Callback callback ) {
222                this.alarm_node{ callback, alarm, period };
223        }
224
225        void ^?{}( alarm_node_wrap(L) & this ) { }
226
227        void process_popped( condition_variable(L) & this, info_thread(L) & popped ) with( this ) {
228                if(&popped != 0p) {
229                        popped.listed = false;
230                        count--;
231                        if (popped.lock) {
232                                add_(*popped.lock, popped.t);
233                        } else {
234                                unpark(popped.t);
235                        }
236                }
237        }
238
239        bool notify_one( condition_variable(L) & this ) with( this ) {
240                lock( lock __cfaabi_dbg_ctx2 );
241                bool ret = !empty(blocked_threads);
242                process_popped(this, dropHead( blocked_threads ));
243                unlock( lock );
244                return ret;
245        }
246
247        bool notify_all( condition_variable(L) & this ) with(this) {
248                lock( lock __cfaabi_dbg_ctx2 );
249                bool ret = !empty(blocked_threads);
250                while( !empty(blocked_threads) ) {
251                        process_popped(this, dropHead( blocked_threads ));
252                }
253                unlock( lock );
254                return ret;
255        }
256
257        uintptr_t front( condition_variable(L) & this ) with(this) {
258                return empty(blocked_threads) ? NULL : head(blocked_threads).info;
259        }
260
261        bool empty( condition_variable(L) & this ) with(this) { return empty(blocked_threads); }
262
263        int counter( condition_variable(L) & this ) with(this) { return count; }
264
265        size_t queue_and_get_recursion( condition_variable(L) & this, info_thread(L) * i ) with(this) {
266                addTail( blocked_threads, *i );
267                count++;
268                i->listed = true;
269                size_t recursion_count = 0;
270                if (i->lock) {
271                        recursion_count = get_recursion_count(*i->lock);
272                        remove_( *i->lock );
273                }
274                return recursion_count;
275        }
276
277        // helper for wait()'s' with no timeout
278        void queue_info_thread( condition_variable(L) & this, info_thread(L) & i ) with(this) {
279                lock( lock __cfaabi_dbg_ctx2 );
280                size_t recursion_count = queue_and_get_recursion(this, &i);
281                unlock( lock );
282                park( ); // blocks here
283                if (i.lock) set_recursion_count(*i.lock, recursion_count); // resets recursion count here after waking
284        }
285
286        // helper for wait()'s' with a timeout
287        void queue_info_thread_timeout( condition_variable(L) & this, info_thread(L) & info, Time t ) with(this) {
288                lock( lock __cfaabi_dbg_ctx2 );
289                size_t recursion_count = queue_and_get_recursion(this, &info);
290                alarm_node_wrap(L) node_wrap = { t, 0`s, alarm_node_wrap_cast };
291                node_wrap.cond = &this;
292                node_wrap.i = &info;
293                register_self( &node_wrap.alarm_node );
294                unlock( lock );
295                park();
296                unregister_self( &node_wrap.alarm_node );
297                if (info.lock) set_recursion_count(*info.lock, recursion_count);
298        }
299
300        void wait( condition_variable(L) & this ) with(this) {
301                info_thread( L ) i = { active_thread() };
302                queue_info_thread( this, i );
303        }
304
305        void wait( condition_variable(L) & this, uintptr_t info ) with(this) {
306                info_thread( L ) i = { active_thread(), info };
307                queue_info_thread( this, i );
308        }
309       
310        void wait( condition_variable(L) & this, Duration duration ) with(this) {
311                info_thread( L ) i = { active_thread() };
312                queue_info_thread_timeout(this, i, __kernel_get_time() + duration );
313        }
314
315        void wait( condition_variable(L) & this, uintptr_t info, Duration duration ) with(this) {
316                info_thread( L ) i = { active_thread(), info };
317                queue_info_thread_timeout(this, i, __kernel_get_time() + duration );
318        }
319
320        void wait( condition_variable(L) & this, Time time ) with(this) {
321                info_thread( L ) i = { active_thread() };
322                queue_info_thread_timeout(this, i, time);
323        }
324
325        void wait( condition_variable(L) & this, uintptr_t info, Time time ) with(this) {
326                info_thread( L ) i = { active_thread(), info };
327                queue_info_thread_timeout(this, i, time);
328        }
329
330        void wait( condition_variable(L) & this, L & l ) with(this) {
331                info_thread(L) i = { active_thread() };
332                i.lock = &l;
333                queue_info_thread( this, i );
334        }
335
336        void wait( condition_variable(L) & this, L & l, uintptr_t info ) with(this) {
337                info_thread(L) i = { active_thread(), info };
338                i.lock = &l;
339                queue_info_thread( this, i );
340        }
341       
342        void wait( condition_variable(L) & this, L & l, Duration duration ) with(this) {
343                info_thread(L) i = { active_thread() };
344                i.lock = &l;
345                queue_info_thread_timeout(this, i, __kernel_get_time() + duration );
346        }
347       
348        void wait( condition_variable(L) & this, L & l, uintptr_t info, Duration duration ) with(this) {
349                info_thread(L) i = { active_thread(), info };
350                i.lock = &l;
351                queue_info_thread_timeout(this, i, __kernel_get_time() + duration );
352        }
353       
354        void wait( condition_variable(L) & this, L & l, Time time ) with(this) {
355                info_thread(L) i = { active_thread() };
356                i.lock = &l;
357                queue_info_thread_timeout(this, i, time );
358        }
359       
360        void wait( condition_variable(L) & this, L & l, uintptr_t info, Time time ) with(this) {
361                info_thread(L) i = { active_thread(), info };
362                i.lock = &l;
363                queue_info_thread_timeout(this, i, time );
364        }
365}
366
367// const unsigned int num_times = 50000;
368
369// multiple_acquisition_lock m;
370// condition_variable( multiple_acquisition_lock ) c_m;
371
372// single_acquisition_lock s;
373// condition_variable( single_acquisition_lock ) c_s;
374
375// owner_lock o;
376// condition_variable( owner_lock ) c_o;
377
378// thread T_C_M_WS1 {};
379
380// void main( T_C_M_WS1 & this ) {
381//      fprintf(stderr, "start of thd main listed: %d\n", listed(active_thread()) );
382//      fprintf(stderr, "thread colable next ptr in start of thd main %p\n", Next( (Colable *)active_thread() ) );
383//      for (unsigned int i = 0; i < num_times; i++) {
384//              lock(m);
385//              if(empty(c_m) && i != num_times - 1) {
386//                      wait(c_m,m);
387//              }else{
388//                      notify_one(c_m);
389//              }
390//              unlock(m);
391//      }
392// }
393
394// thread T_C_M_WB1 {};
395
396// void main( T_C_M_WB1 & this ) {
397//      for (unsigned int i = 0; i < num_times; i++) {
398//              lock(m);
399//              if(counter(c_m) == 3 || i == num_times - 1) {
400//                      notify_all(c_m);
401//              }else{
402//                      wait(c_m,m);
403//              }
404//              unlock(m);
405//      }
406// }
407
408// thread T_C_S_WS1 {};
409
410// void main( T_C_S_WS1 & this ) {
411//      for (unsigned int i = 0; i < num_times; i++) {
412//              lock(s);
413//              if(empty(c_s) && i != num_times - 1) {
414//                      wait(c_s,s);
415//              }else{
416//                      notify_one(c_s);
417//              }
418//              unlock(s);
419//      }
420// }
421
422// thread T_C_S_WB1 {};
423
424// void main( T_C_S_WB1 & this ) {
425//      for (unsigned int i = 0; i < num_times; i++) {
426//              lock(s);
427//              if(counter(c_s) == 3 || i == num_times - 1) {
428//                      notify_all(c_s);
429//              }else{
430//                      wait(c_s,s);
431//              }
432//              unlock(s);
433//      }
434// }
435
436// thread T_C_O_WS1 {};
437
438// void main( T_C_O_WS1 & this ) {
439//      for (unsigned int i = 0; i < num_times; i++) {
440//              lock(o);
441//              if(empty(c_o) && i != num_times - 1) {
442//                      wait(c_o,o);
443//              }else{
444//                      notify_one(c_o);
445//              }
446//              unlock(o);
447//      }
448// }
449
450// thread T_C_O_WB1 {};
451
452// void main( T_C_O_WB1 & this ) {
453//      for (unsigned int i = 0; i < num_times; i++) {
454//              lock(o);
455//              if(counter(c_o) == 3 || i == num_times - 1) {
456//                      notify_all(c_o);
457//              }else{
458//                      wait(c_o,o);
459//              }
460//              unlock(o);
461//      }
462// }
463
464// thread T_C_M_WS2 {};
465
466// void main( T_C_M_WS2 & this ) {
467//      for (unsigned int i = 0; i < num_times; i++) {
468//              lock(m);
469//              lock(m);
470//              lock(m);
471//              if(empty(c_m) && i != num_times - 1) {
472//                      wait(c_m,m);
473//              }else{
474//                      notify_one(c_m);
475//              }
476//              unlock(m);
477//              unlock(m);
478//              unlock(m);
479//      }
480// }
481
482// thread T_C_O_WS2 {};
483
484// void main( T_C_O_WS2 & this ) {
485//      for (unsigned int i = 0; i < num_times; i++) {
486//              lock(o);
487//              lock(o);
488//              lock(o);
489//              if(empty(c_o) && i != num_times - 1) {
490//                      wait(c_o,o);
491//              }else{
492//                      notify_one(c_o);
493//              }
494//              unlock(o);
495//              unlock(o);
496//              unlock(o);
497//      }
498// }
499
500// thread T_C_NLW {};
501
502// void main( T_C_NLW & this ) {
503//      for (unsigned int i = 0; i < num_times; i++) {
504//              wait(c_o);
505//      }
506// }
507
508// thread T_C_NLS {};
509
510// void main( T_C_NLS & this ) {
511//      for (unsigned int i = 0; i < num_times; i++) {
512//              while (empty(c_o)) { }
513//              notify_one(c_o);
514//      }
515// }
516
517// thread T_C_S_WNF {};
518
519// void main( T_C_S_WNF & this ) {
520//      for (unsigned int i = 0; i < num_times; i++) {
521//              lock(s);
522//              if(empty(c_s) && i != num_times - 1) {
523//                      wait(c_s, s, 10);
524//              }else{
525//                      if(!empty(c_s)) assert(front(c_s) == 10);
526//                      notify_one(c_s);
527//              }
528//              unlock(s);
529//      }
530// }
531
532// bool done = false;
533
534// thread T_C_NLWD {};
535
536// void main( T_C_NLWD & this ) {
537//      done = false;
538//      for (unsigned int i = 0; i < num_times; i++) {
539//              wait(c_s, 1`ns);
540//      }
541//      done = true;
542// }
543
544// thread T_C_WDS {};
545
546// void main( T_C_WDS & this ) {
547//      for (unsigned int i = 0; i < num_times; i++) {
548//              while (empty(c_s) && !done) { }
549//              notify_one(c_s);
550//              sleep(1`ns);
551//              if(done) break;
552//      }
553// }
554
555// thread T_C_LWD {};
556
557// void main( T_C_LWD & this ) {
558//      done = false;
559//      for (unsigned int i = 0; i < num_times; i++) {
560//              if (i % 500 == 0) printf("!! %d\n", i);
561//              lock(s);
562//              wait(c_s, s, 1`ns);
563//              unlock(s);
564//      }
565//      done = true;
566// }
567
568// int main() {
569//      processor p[2];
570//      printf("Start Test 1: multi acquisition lock and condition variable single wait/notify\n");
571//      {
572//              T_C_M_WS1 t1;
573//      }
574//      printf("Done Test 1\n");
575
576//      printf("Start Test 2: multi acquisition lock and condition variable 3 wait/notify all\n");
577//      {
578//              T_C_M_WB1 t1[4];
579//      }
580//      printf("Done Test 2\n");
581
582//      printf("Start Test 3: single acquisition lock and condition variable single wait/notify\n");
583//      {
584//              T_C_S_WS1 t1[2];
585//      }
586//      printf("Done Test 3\n");
587
588//      printf("Start Test 4: single acquisition lock and condition variable 3 wait/notify all\n");
589//      {
590//              T_C_S_WB1 t1[4];
591//      }
592//      printf("Done Test 4\n");
593
594//      printf("Start Test 5: owner lock and condition variable single wait/notify\n");
595//      {
596//              T_C_O_WS1 t1[2];
597//      }
598//      printf("Done Test 5\n");
599
600//      printf("Start Test 6: owner lock and condition variable 3 wait/notify all\n");
601//      {
602//              T_C_O_WB1 t1[4];
603//      }
604//      printf("Done Test 6\n");
605
606//      printf("Start Test 7: multi acquisiton lock and condition variable multiple acquire and wait/notify\n");
607//      {
608//              T_C_M_WS2 t1[2];
609//      }
610//      printf("Done Test 7\n");
611
612//      printf("Start Test 8: owner lock and condition variable multiple acquire and wait/notify\n");
613//      {
614//              T_C_O_WS2 t1[2];
615//      }
616//      printf("Done Test 8\n");
617
618//      printf("Start Test 9: no lock condition variable wait/notify\n");
619//      {
620//              T_C_NLW t1;
621//              T_C_NLS t2;
622//      }
623//      printf("Done Test 9\n");
624
625//      printf("Start Test 10: locked condition variable wait/notify with front()\n");
626//      {
627//              T_C_S_WNF t1[2];
628//      }
629//      printf("Done Test 10\n");
630
631//      printf("Start Test 11: unlocked condition variable delay wait\n");
632//      {
633//              T_C_NLWD t1;
634//              T_C_WDS t2;
635//      }
636//      printf("Done Test 11\n");
637
638//      // printf("Start Test 12: locked condition variable delay wait\n");
639//      // {
640//      //      T_C_LWD t1;
641//      //      T_C_WDS t2;
642//      // }
643//      // printf("Done Test 12\n");
644// }
Note: See TracBrowser for help on using the repository browser.