source: libcfa/src/concurrency/locks.cfa @ 02a43ff

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

Merge branch 'master' of plg.uwaterloo.ca:software/cfa/cfa-cc

  • Property mode set to 100644
File size: 11.5 KB
RevLine 
[ab1b971]1//
2// Cforall Version 1.0.0 Copyright (C) 2021 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// locks.hfa -- LIBCFATHREAD
8// Runtime locks that used with the runtime thread system.
9//
10// Author           : Colby Alexander Parsons
11// Created On       : Thu Jan 21 19:46:50 2021
12// Last Modified By :
13// Last Modified On :
14// Update Count     :
15//
16
17#define __cforall_thread__
18
[848439f]19#include "locks.hfa"
20#include "kernel_private.hfa"
21
22#include <kernel.hfa>
23#include <stdlib.hfa>
24
[ac5816d]25//-----------------------------------------------------------------------------
26// info_thread
[fd54fef]27forall(L & | is_blocking_lock(L)) {
[ac5816d]28        struct info_thread {
29                // used to put info_thread on a dl queue (aka sequence)
30                inline Seqable;
31
32                // waiting thread
33                struct $thread * t;
34
35                // shadow field
36                uintptr_t info;
37
38                // lock that is passed to wait() (if one is passed)
39                L * lock;
40
41                // true when signalled and false when timeout wakes thread
42                bool signalled;
43        };
[848439f]44
[ac5816d]45        void ?{}( info_thread(L) & this, $thread * t, uintptr_t info, L * l ) {
[cad1df1]46                ((Seqable &) this){};
[848439f]47                this.t = t;
48                this.info = info;
[ac5816d]49                this.lock = l;
[848439f]50        }
51
[ac5816d]52        void ^?{}( info_thread(L) & this ) {}
[c131a02]53
54        info_thread(L) *& Back( info_thread(L) * this ) {
55                return (info_thread(L) *)Back( (Seqable *)this );
56        }
57
58        info_thread(L) *& Next( info_thread(L) * this ) {
59                return (info_thread(L) *)Next( (Colable *)this );
60        }
[848439f]61}
[cad1df1]62
[ac5816d]63//-----------------------------------------------------------------------------
64// Blocking Locks
[848439f]65void ?{}( blocking_lock & this, bool multi_acquisition, bool strict_owner ) {
66        this.lock{};
67        this.blocked_threads{};
68        this.wait_count = 0;
69        this.multi_acquisition = multi_acquisition;
70        this.strict_owner = strict_owner;
71        this.owner = 0p;
72        this.recursion_count = 0;
73}
74
[cad1df1]75void ^?{}( blocking_lock & this ) {}
[ab1b971]76
[848439f]77
78void lock( blocking_lock & this ) with( this ) {
79        lock( lock __cfaabi_dbg_ctx2 );
[ac5816d]80        $thread * thrd = active_thread();
81
82        // single acquisition lock is held by current thread
83        /* paranoid */ verifyf( owner != thrd || multi_acquisition, "Single acquisition lock holder (%p) attempted to reacquire the lock %p resulting in a deadlock.", owner, &this );
84
85        // lock is held by some other thread
86        if ( owner != 0p && owner != thrd ) {
87                addTail( blocked_threads, *thrd );
[848439f]88                wait_count++;
89                unlock( lock );
[eeb5023]90                park( );
[ac5816d]91        }
92        // multi acquisition lock is held by current thread
93        else if ( owner == thrd && multi_acquisition ) {
[848439f]94                recursion_count++;
95                unlock( lock );
[ac5816d]96        }
97        // lock isn't held
98        else {
99                owner = thrd;
[848439f]100                recursion_count = 1;
101                unlock( lock );
102        }
103}
104
105bool try_lock( blocking_lock & this ) with( this ) {
106        bool ret = false;
107        lock( lock __cfaabi_dbg_ctx2 );
[ac5816d]108
109        // lock isn't held
110        if ( owner == 0p ) {
[6a8882c]111                owner = active_thread();
112                recursion_count = 1;
[848439f]113                ret = true;
[ac5816d]114        }
115        // multi acquisition lock is held by current thread
116        else if ( owner == active_thread() && multi_acquisition ) {
[848439f]117                recursion_count++;
118                ret = true;
119        }
[ac5816d]120
[848439f]121        unlock( lock );
122        return ret;
123}
124
[cad1df1]125void pop_and_set_new_owner( blocking_lock & this ) with( this ) {
[c131a02]126        $thread * t = &dropHead( blocked_threads );
[cad1df1]127        owner = t;
128        recursion_count = ( t ? 1 : 0 );
129        wait_count--;
130        unpark( t );
131}
132
133void unlock( blocking_lock & this ) with( this ) {
134        lock( lock __cfaabi_dbg_ctx2 );
[ac5816d]135        /* paranoid */ verifyf( owner != 0p, "Attempt to release lock %p that isn't held", &this );
[22b7579]136        /* paranoid */ verifyf( owner == active_thread() || !strict_owner , "Thread %p other than the owner %p attempted to release owner lock %p", owner, active_thread(), &this );
137        /* paranoid */ verifyf( recursion_count == 1 || multi_acquisition, "Thread %p attempted to release owner lock %p which is not recursive but has a recursive count of %zu", active_thread(), &this, recursion_count );
[ac5816d]138
139        // if recursion count is zero release lock and set new owner if one is waiting
[848439f]140        recursion_count--;
[ac5816d]141        if ( recursion_count == 0 ) {
[cad1df1]142                pop_and_set_new_owner( this );
[848439f]143        }
144        unlock( lock );
145}
146
147size_t wait_count( blocking_lock & this ) with( this ) {
148        return wait_count;
149}
150
[797a193]151void on_notify( blocking_lock & this, $thread * t ) with( this ) {
[ac5816d]152        lock( lock __cfaabi_dbg_ctx2 );
153        // lock held
154        if ( owner != 0p ) {
[c131a02]155                addTail( blocked_threads, *t );
[848439f]156                wait_count++;
157                unlock( lock );
[ac5816d]158        }
159        // lock not held
160        else {
[848439f]161                owner = t;
[6a8882c]162                recursion_count = 1;
[eeb5023]163                unpark( t );
[848439f]164                unlock( lock );
165        }
166}
167
[22b7579]168size_t on_wait( blocking_lock & this ) with( this ) {
[ac5816d]169        lock( lock __cfaabi_dbg_ctx2 );
170        /* paranoid */ verifyf( owner != 0p, "Attempt to release lock %p that isn't held", &this );
171        /* paranoid */ verifyf( owner == active_thread() || !strict_owner, "Thread %p other than the owner %p attempted to release owner lock %p", owner, active_thread(), &this );
172
[22b7579]173        size_t ret = recursion_count;
174
[cad1df1]175        pop_and_set_new_owner( this );
[848439f]176        unlock( lock );
[22b7579]177        return ret;
178}
179
180void on_wakeup( blocking_lock & this, size_t recursion ) with( this ) {
181        recursion_count = recursion;
[848439f]182}
183
[ac5816d]184//-----------------------------------------------------------------------------
185// alarm node wrapper
[fd54fef]186forall(L & | is_blocking_lock(L)) {
[c20533ea]187        struct alarm_node_wrap {
188                alarm_node_t alarm_node;
189                condition_variable(L) * cond;
[90a10e8]190                info_thread(L) * info_thd;
[c20533ea]191        };
192
[c457dc4]193        void ?{}( alarm_node_wrap(L) & this, Duration alarm, Duration period, Alarm_Callback callback, condition_variable(L) * c, info_thread(L) * i ) {
[c20533ea]194                this.alarm_node{ callback, alarm, period };
[ac5816d]195                this.cond = c;
[90a10e8]196                this.info_thd = i;
[c20533ea]197        }
198
199        void ^?{}( alarm_node_wrap(L) & this ) { }
[848439f]200
[c5bbb9b]201        void timeout_handler ( alarm_node_wrap(L) & this ) with( this ) {
[ac5816d]202                // This condition_variable member is called from the kernel, and therefore, cannot block, but it can spin.
203                lock( cond->lock __cfaabi_dbg_ctx2 );
204
205                // this check is necessary to avoid a race condition since this timeout handler
206                //      may still be called after a thread has been removed from the queue but
207                //      before the alarm is unregistered
[90a10e8]208                if ( listed(info_thd) ) {       // is thread on queue
209                        info_thd->signalled = false;
[ac5816d]210                        // remove this thread O(1)
[90a10e8]211                        remove( cond->blocked_threads, *info_thd );
[6a8882c]212                        cond->count--;
[90a10e8]213                        if( info_thd->lock ) {
[ac5816d]214                                // call lock's on_notify if a lock was passed
[90a10e8]215                                on_notify(*info_thd->lock, info_thd->t);
[ac5816d]216                        } else {
217                                // otherwise wake thread
[90a10e8]218                                unpark( info_thd->t );
[ac5816d]219                        }
220                }
221                unlock( cond->lock );
[848439f]222        }
223
[797a193]224        // this casts the alarm node to our wrapped type since we used type erasure
[cad1df1]225        void alarm_node_wrap_cast( alarm_node_t & a ) { timeout_handler( (alarm_node_wrap(L) &)a ); }
[c20533ea]226}
227
[ac5816d]228//-----------------------------------------------------------------------------
229// condition variable
[fd54fef]230forall(L & | is_blocking_lock(L)) {
[c20533ea]231
[848439f]232        void ?{}( condition_variable(L) & this ){
[eeb5023]233                this.lock{};
234                this.blocked_threads{};
235                this.count = 0;
[848439f]236        }
237
[cad1df1]238        void ^?{}( condition_variable(L) & this ){ }
[848439f]239
[cad1df1]240        void process_popped( condition_variable(L) & this, info_thread(L) & popped ) with( this ) {
241                if(&popped != 0p) {
[dff1fd1]242                        popped.signalled = true;
[eeb5023]243                        count--;
[cad1df1]244                        if (popped.lock) {
[ac5816d]245                                // if lock passed call on_notify
246                                on_notify(*popped.lock, popped.t);
[848439f]247                        } else {
[ac5816d]248                                // otherwise wake thread
249                                unpark(popped.t);
[848439f]250                        }
251                }
[cad1df1]252        }
253
254        bool notify_one( condition_variable(L) & this ) with( this ) {
255                lock( lock __cfaabi_dbg_ctx2 );
256                bool ret = !empty(blocked_threads);
257                process_popped(this, dropHead( blocked_threads ));
[848439f]258                unlock( lock );
259                return ret;
260        }
261
[eeb5023]262        bool notify_all( condition_variable(L) & this ) with(this) {
[848439f]263                lock( lock __cfaabi_dbg_ctx2 );
[cad1df1]264                bool ret = !empty(blocked_threads);
265                while( !empty(blocked_threads) ) {
266                        process_popped(this, dropHead( blocked_threads ));
[848439f]267                }
268                unlock( lock );
269                return ret;
270        }
271
[eeb5023]272        uintptr_t front( condition_variable(L) & this ) with(this) {
[cad1df1]273                return empty(blocked_threads) ? NULL : head(blocked_threads).info;
[848439f]274        }
275
[22b7579]276        bool empty( condition_variable(L) & this ) with(this) {
277                lock( lock __cfaabi_dbg_ctx2 );
278                bool ret = empty(blocked_threads);
279                unlock( lock );
280                return ret;
281        }
[cad1df1]282
283        int counter( condition_variable(L) & this ) with(this) { return count; }
[848439f]284
[cad1df1]285        size_t queue_and_get_recursion( condition_variable(L) & this, info_thread(L) * i ) with(this) {
[ac5816d]286                // add info_thread to waiting queue
287                addTail( blocked_threads, *i );
[cad1df1]288                count++;
289                size_t recursion_count = 0;
[ac5816d]290                if (i->lock) {
291                        // if lock was passed get recursion count to reset to after waking thread
[22b7579]292                        recursion_count = on_wait( *i->lock );
[cad1df1]293                }
294                return recursion_count;
[848439f]295        }
296
[cad1df1]297        // helper for wait()'s' with no timeout
[eeb5023]298        void queue_info_thread( condition_variable(L) & this, info_thread(L) & i ) with(this) {
[848439f]299                lock( lock __cfaabi_dbg_ctx2 );
[cad1df1]300                size_t recursion_count = queue_and_get_recursion(this, &i);
[848439f]301                unlock( lock );
[ac5816d]302
303                // blocks here
304                park( );
305
306                // resets recursion count here after waking
[22b7579]307                if (i.lock) on_wakeup(*i.lock, recursion_count);
[848439f]308        }
309
[ac5816d]310        #define WAIT( u, l ) \
311                info_thread( L ) i = { active_thread(), u, l }; \
312                queue_info_thread( this, i );
313
[eeb5023]314        // helper for wait()'s' with a timeout
[afd7faf]315        void queue_info_thread_timeout( condition_variable(L) & this, info_thread(L) & info, Duration t, Alarm_Callback callback ) with(this) {
[eeb5023]316                lock( lock __cfaabi_dbg_ctx2 );
[cad1df1]317                size_t recursion_count = queue_and_get_recursion(this, &info);
[afd7faf]318                alarm_node_wrap(L) node_wrap = { t, 0`s, callback, &this, &info };
[eeb5023]319                register_self( &node_wrap.alarm_node );
[848439f]320                unlock( lock );
321
[ac5816d]322                // blocks here
323                park();
[848439f]324
[ac5816d]325                // unregisters alarm so it doesn't go off if this happens first
326                unregister_self( &node_wrap.alarm_node );
[848439f]327
[ac5816d]328                // resets recursion count here after waking
[22b7579]329                if (info.lock) on_wakeup(*info.lock, recursion_count);
[848439f]330        }
331
[ac5816d]332        #define WAIT_TIME( u, l, t ) \
333                info_thread( L ) i = { active_thread(), u, l }; \
[afd7faf]334                queue_info_thread_timeout(this, i, t, alarm_node_wrap_cast ); \
[dff1fd1]335                return i.signalled;
[848439f]336
[ac5816d]337        void wait( condition_variable(L) & this                        ) with(this) { WAIT( 0, 0p    ) }
338        void wait( condition_variable(L) & this, uintptr_t info        ) with(this) { WAIT( info, 0p ) }
339        void wait( condition_variable(L) & this, L & l                 ) with(this) { WAIT( 0, &l    ) }
340        void wait( condition_variable(L) & this, L & l, uintptr_t info ) with(this) { WAIT( info, &l ) }
341
[c457dc4]342        bool wait( condition_variable(L) & this, Duration duration                        ) with(this) { WAIT_TIME( 0   , 0p , duration ) }
343        bool wait( condition_variable(L) & this, uintptr_t info, Duration duration        ) with(this) { WAIT_TIME( info, 0p , duration ) }
344        bool wait( condition_variable(L) & this, L & l, Duration duration                 ) with(this) { WAIT_TIME( 0   , &l , duration ) }
345        bool wait( condition_variable(L) & this, L & l, uintptr_t info, Duration duration ) with(this) { WAIT_TIME( info, &l , duration ) }
[848439f]346}
[454f478]347
348//-----------------------------------------------------------------------------
349// Semaphore
350void  ?{}( semaphore & this, int count = 1 ) {
351        (this.lock){};
352        this.count = count;
353        (this.waiting){};
354}
355void ^?{}(semaphore & this) {}
356
357bool P(semaphore & this) with( this ){
358        lock( lock __cfaabi_dbg_ctx2 );
359        count -= 1;
360        if ( count < 0 ) {
361                // queue current task
362                append( waiting, active_thread() );
363
364                // atomically release spin lock and block
365                unlock( lock );
366                park();
367                return true;
368        }
369        else {
370            unlock( lock );
371            return false;
372        }
373}
374
[22b7579]375$thread * V (semaphore & this, const bool doUnpark ) with( this ) {
[454f478]376        $thread * thrd = 0p;
377        lock( lock __cfaabi_dbg_ctx2 );
378        count += 1;
379        if ( count <= 0 ) {
380                // remove task at head of waiting list
381                thrd = pop_head( waiting );
382        }
383
384        unlock( lock );
385
386        // make new owner
[22b7579]387        if( doUnpark ) unpark( thrd );
388
389        return thrd;
390}
[454f478]391
[22b7579]392bool V(semaphore & this) with( this ) {
393        $thread * thrd = V(this, true);
[454f478]394        return thrd != 0p;
395}
396
397bool V(semaphore & this, unsigned diff) with( this ) {
398        $thread * thrd = 0p;
399        lock( lock __cfaabi_dbg_ctx2 );
400        int release = max(-count, (int)diff);
401        count += diff;
402        for(release) {
403                unpark( pop_head( waiting ) );
404        }
405
406        unlock( lock );
407
408        return thrd != 0p;
409}
Note: See TracBrowser for help on using the repository browser.