source: libcfa/src/concurrency/locks.cfa @ 22b7579

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

Changed is_blocking_lock trait to use on_wakeup.
Fixed fast_lock to work with conditions.

  • Property mode set to 100644
File size: 11.9 KB
Line 
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
19#include "locks.hfa"
20#include "kernel_private.hfa"
21
22#include <kernel.hfa>
23#include <stdlib.hfa>
24
25//-----------------------------------------------------------------------------
26// info_thread
27forall(L & | is_blocking_lock(L)) {
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        };
44
45        void ?{}( info_thread(L) & this, $thread * t, uintptr_t info, L * l ) {
46                ((Seqable &) this){};
47                this.t = t;
48                this.info = info;
49                this.lock = l;
50        }
51
52        void ^?{}( info_thread(L) & this ) {}
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        }
61}
62
63//-----------------------------------------------------------------------------
64// Blocking Locks
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
75void ^?{}( blocking_lock & this ) {}
76
77
78void lock( blocking_lock & this ) with( this ) {
79        lock( lock __cfaabi_dbg_ctx2 );
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 );
88                wait_count++;
89                unlock( lock );
90                park( );
91        }
92        // multi acquisition lock is held by current thread
93        else if ( owner == thrd && multi_acquisition ) {
94                recursion_count++;
95                unlock( lock );
96        }
97        // lock isn't held
98        else {
99                owner = thrd;
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 );
108
109        // lock isn't held
110        if ( owner == 0p ) {
111                owner = active_thread();
112                recursion_count = 1;
113                ret = true;
114        }
115        // multi acquisition lock is held by current thread
116        else if ( owner == active_thread() && multi_acquisition ) {
117                recursion_count++;
118                ret = true;
119        }
120
121        unlock( lock );
122        return ret;
123}
124
125void pop_and_set_new_owner( blocking_lock & this ) with( this ) {
126        $thread * t = &dropHead( blocked_threads );
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 );
135        /* paranoid */ verifyf( owner != 0p, "Attempt to release lock %p that isn't held", &this );
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 );
138
139        // if recursion count is zero release lock and set new owner if one is waiting
140        recursion_count--;
141        if ( recursion_count == 0 ) {
142                pop_and_set_new_owner( this );
143        }
144        unlock( lock );
145}
146
147size_t wait_count( blocking_lock & this ) with( this ) {
148        return wait_count;
149}
150
151void on_notify( blocking_lock & this, $thread * t ) with( this ) {
152        lock( lock __cfaabi_dbg_ctx2 );
153        // lock held
154        if ( owner != 0p ) {
155                addTail( blocked_threads, *t );
156                wait_count++;
157                unlock( lock );
158        }
159        // lock not held
160        else {
161                owner = t;
162                recursion_count = 1;
163                unpark( t );
164                unlock( lock );
165        }
166}
167
168size_t on_wait( blocking_lock & this ) with( this ) {
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
173        size_t ret = recursion_count;
174
175        pop_and_set_new_owner( this );
176        unlock( lock );
177        return ret;
178}
179
180void on_wakeup( blocking_lock & this, size_t recursion ) with( this ) {
181        recursion_count = recursion;
182}
183
184//-----------------------------------------------------------------------------
185// alarm node wrapper
186forall(L & | is_blocking_lock(L)) {
187        struct alarm_node_wrap {
188                alarm_node_t alarm_node;
189                condition_variable(L) * cond;
190                info_thread(L) * i;
191        };
192
193        void ?{}( alarm_node_wrap(L) & this, Time alarm, Duration period, Alarm_Callback callback, condition_variable(L) * c, info_thread(L) * i ) {
194                this.alarm_node{ callback, alarm, period };
195                this.cond = c;
196                this.i = i;
197        }
198
199        void ^?{}( alarm_node_wrap(L) & this ) { }
200
201        void timeout_handler ( alarm_node_wrap(L) & this ) with( this ) {
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
208                if ( listed(i) ) {      // is thread on queue
209                        i->signalled = false;
210                        // remove this thread O(1)
211                        remove( cond->blocked_threads, *i );
212                        cond->count--;
213                        if( i->lock ) {
214                                // call lock's on_notify if a lock was passed
215                                on_notify(*i->lock, i->t);
216                        } else {
217                                // otherwise wake thread
218                                unpark( i->t );
219                        }
220                }
221                unlock( cond->lock );
222        }
223
224        // this casts the alarm node to our wrapped type since we used type erasure
225        void alarm_node_wrap_cast( alarm_node_t & a ) { timeout_handler( (alarm_node_wrap(L) &)a ); }
226}
227
228//-----------------------------------------------------------------------------
229// condition variable
230forall(L & | is_blocking_lock(L)) {
231
232        void ?{}( condition_variable(L) & this ){
233                this.lock{};
234                this.blocked_threads{};
235                this.count = 0;
236        }
237
238        void ^?{}( condition_variable(L) & this ){ }
239
240        void process_popped( condition_variable(L) & this, info_thread(L) & popped ) with( this ) {
241                if(&popped != 0p) {
242                        popped.signalled = true;
243                        count--;
244                        if (popped.lock) {
245                                // if lock passed call on_notify
246                                on_notify(*popped.lock, popped.t);
247                        } else {
248                                // otherwise wake thread
249                                unpark(popped.t);
250                        }
251                }
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 ));
258                unlock( lock );
259                return ret;
260        }
261
262        bool notify_all( condition_variable(L) & this ) with(this) {
263                lock( lock __cfaabi_dbg_ctx2 );
264                bool ret = !empty(blocked_threads);
265                while( !empty(blocked_threads) ) {
266                        process_popped(this, dropHead( blocked_threads ));
267                }
268                unlock( lock );
269                return ret;
270        }
271
272        uintptr_t front( condition_variable(L) & this ) with(this) {
273                return empty(blocked_threads) ? NULL : head(blocked_threads).info;
274        }
275
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        }
282
283        int counter( condition_variable(L) & this ) with(this) { return count; }
284
285        size_t queue_and_get_recursion( condition_variable(L) & this, info_thread(L) * i ) with(this) {
286                // add info_thread to waiting queue
287                addTail( blocked_threads, *i );
288                count++;
289                size_t recursion_count = 0;
290                if (i->lock) {
291                        // if lock was passed get recursion count to reset to after waking thread
292                        recursion_count = on_wait( *i->lock );
293                }
294                return recursion_count;
295        }
296
297        // helper for wait()'s' with no timeout
298        void queue_info_thread( condition_variable(L) & this, info_thread(L) & i ) with(this) {
299                lock( lock __cfaabi_dbg_ctx2 );
300                size_t recursion_count = queue_and_get_recursion(this, &i);
301                unlock( lock );
302
303                // blocks here
304                park( );
305
306                // resets recursion count here after waking
307                if (i.lock) on_wakeup(*i.lock, recursion_count);
308        }
309
310        #define WAIT( u, l ) \
311                info_thread( L ) i = { active_thread(), u, l }; \
312                queue_info_thread( this, i );
313
314        // helper for wait()'s' with a timeout
315        void queue_info_thread_timeout( condition_variable(L) & this, info_thread(L) & info, Time t ) with(this) {
316                lock( lock __cfaabi_dbg_ctx2 );
317                size_t recursion_count = queue_and_get_recursion(this, &info);
318                alarm_node_wrap(L) node_wrap = { t, 0`s, alarm_node_wrap_cast, &this, &info };
319                register_self( &node_wrap.alarm_node );
320                unlock( lock );
321
322                // blocks here
323                park();
324
325                // unregisters alarm so it doesn't go off if this happens first
326                unregister_self( &node_wrap.alarm_node );
327
328                // resets recursion count here after waking
329                if (info.lock) on_wakeup(*info.lock, recursion_count);
330        }
331
332        #define WAIT_TIME( u, l, t ) \
333                info_thread( L ) i = { active_thread(), u, l }; \
334                queue_info_thread_timeout(this, i, t ); \
335                return i.signalled;
336
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
342        bool wait( condition_variable(L) & this, Duration duration                        ) with(this) { WAIT_TIME( 0   , 0p , __kernel_get_time() + duration ) }
343        bool wait( condition_variable(L) & this, uintptr_t info, Duration duration        ) with(this) { WAIT_TIME( info, 0p , __kernel_get_time() + duration ) }
344        bool wait( condition_variable(L) & this, Time time                                ) with(this) { WAIT_TIME( 0   , 0p , time ) }
345        bool wait( condition_variable(L) & this, uintptr_t info, Time time                ) with(this) { WAIT_TIME( info, 0p , time ) }
346        bool wait( condition_variable(L) & this, L & l, Duration duration                 ) with(this) { WAIT_TIME( 0   , &l , __kernel_get_time() + duration ) }
347        bool wait( condition_variable(L) & this, L & l, uintptr_t info, Duration duration ) with(this) { WAIT_TIME( info, &l , __kernel_get_time() + duration ) }
348        bool wait( condition_variable(L) & this, L & l, Time time                         ) with(this) { WAIT_TIME( 0   , &l , time ) }
349        bool wait( condition_variable(L) & this, L & l, uintptr_t info, Time time         ) with(this) { WAIT_TIME( info, &l , time ) }
350}
351
352//-----------------------------------------------------------------------------
353// Semaphore
354void  ?{}( semaphore & this, int count = 1 ) {
355        (this.lock){};
356        this.count = count;
357        (this.waiting){};
358}
359void ^?{}(semaphore & this) {}
360
361bool P(semaphore & this) with( this ){
362        lock( lock __cfaabi_dbg_ctx2 );
363        count -= 1;
364        if ( count < 0 ) {
365                // queue current task
366                append( waiting, active_thread() );
367
368                // atomically release spin lock and block
369                unlock( lock );
370                park();
371                return true;
372        }
373        else {
374            unlock( lock );
375            return false;
376        }
377}
378
379$thread * V (semaphore & this, const bool doUnpark ) with( this ) {
380        $thread * thrd = 0p;
381        lock( lock __cfaabi_dbg_ctx2 );
382        count += 1;
383        if ( count <= 0 ) {
384                // remove task at head of waiting list
385                thrd = pop_head( waiting );
386        }
387
388        unlock( lock );
389
390        // make new owner
391        if( doUnpark ) unpark( thrd );
392
393        return thrd;
394}
395
396bool V(semaphore & this) with( this ) {
397        $thread * thrd = V(this, true);
398        return thrd != 0p;
399}
400
401bool V(semaphore & this, unsigned diff) with( this ) {
402        $thread * thrd = 0p;
403        lock( lock __cfaabi_dbg_ctx2 );
404        int release = max(-count, (int)diff);
405        count += diff;
406        for(release) {
407                unpark( pop_head( waiting ) );
408        }
409
410        unlock( lock );
411
412        return thrd != 0p;
413}
Note: See TracBrowser for help on using the repository browser.