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

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

blocking_lock & multiple_acquisition_lock can now be used without libcfa-thread.
Doing so will have all functions be no-ops for these locks.
If libcfa-thread is linked in, these locks will behave as proper user-level locking.

  • Property mode set to 100644
File size: 11.6 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
138        // if recursion count is zero release lock and set new owner if one is waiting
139        recursion_count--;
140        if ( recursion_count == 0 ) {
141                pop_and_set_new_owner( this );
142        }
143        unlock( lock );
144}
145
146size_t wait_count( blocking_lock & this ) with( this ) {
147        return wait_count;
148}
149
150void set_recursion_count( blocking_lock & this, size_t recursion ) with( this ) {
151        recursion_count = recursion;
152}
153
154size_t get_recursion_count( blocking_lock & this ) with( this ) {
155        return recursion_count;
156}
157
158void on_notify( blocking_lock & this, $thread * t ) with( this ) {
159        lock( lock __cfaabi_dbg_ctx2 );
160        // lock held
161        if ( owner != 0p ) {
162                addTail( blocked_threads, *t );
163                wait_count++;
164                unlock( lock );
165        }
166        // lock not held
167        else {
168                owner = t;
169                recursion_count = 1;
170                unpark( t );
171                unlock( lock );
172        }
173}
174
175void on_wait( blocking_lock & this ) with( this ) {
176        lock( lock __cfaabi_dbg_ctx2 );
177        /* paranoid */ verifyf( owner != 0p, "Attempt to release lock %p that isn't held", &this );
178        /* paranoid */ verifyf( owner == active_thread() || !strict_owner, "Thread %p other than the owner %p attempted to release owner lock %p", owner, active_thread(), &this );
179
180        pop_and_set_new_owner( this );
181        unlock( lock );
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) { return empty(blocked_threads); }
277
278        int counter( condition_variable(L) & this ) with(this) { return count; }
279
280        size_t queue_and_get_recursion( condition_variable(L) & this, info_thread(L) * i ) with(this) {
281                // add info_thread to waiting queue
282                addTail( blocked_threads, *i );
283                count++;
284                size_t recursion_count = 0;
285                if (i->lock) {
286                        // if lock was passed get recursion count to reset to after waking thread
287                        recursion_count = get_recursion_count(*i->lock);
288                        on_wait( *i->lock );
289                }
290                return recursion_count;
291        }
292
293        // helper for wait()'s' with no timeout
294        void queue_info_thread( condition_variable(L) & this, info_thread(L) & i ) with(this) {
295                lock( lock __cfaabi_dbg_ctx2 );
296                size_t recursion_count = queue_and_get_recursion(this, &i);
297                unlock( lock );
298
299                // blocks here
300                park( );
301
302                // resets recursion count here after waking
303                if (i.lock) set_recursion_count(*i.lock, recursion_count);
304        }
305
306        #define WAIT( u, l ) \
307                info_thread( L ) i = { active_thread(), u, l }; \
308                queue_info_thread( this, i );
309
310        // helper for wait()'s' with a timeout
311        void queue_info_thread_timeout( condition_variable(L) & this, info_thread(L) & info, Time t ) with(this) {
312                lock( lock __cfaabi_dbg_ctx2 );
313                size_t recursion_count = queue_and_get_recursion(this, &info);
314                alarm_node_wrap(L) node_wrap = { t, 0`s, alarm_node_wrap_cast, &this, &info };
315                register_self( &node_wrap.alarm_node );
316                unlock( lock );
317
318                // blocks here
319                park();
320
321                // unregisters alarm so it doesn't go off if this happens first
322                unregister_self( &node_wrap.alarm_node );
323
324                // resets recursion count here after waking
325                if (info.lock) set_recursion_count(*info.lock, recursion_count);
326        }
327
328        #define WAIT_TIME( u, l, t ) \
329                info_thread( L ) i = { active_thread(), u, l }; \
330                queue_info_thread_timeout(this, i, t ); \
331                return i.signalled;
332
333        void wait( condition_variable(L) & this                        ) with(this) { WAIT( 0, 0p    ) }
334        void wait( condition_variable(L) & this, uintptr_t info        ) with(this) { WAIT( info, 0p ) }
335        void wait( condition_variable(L) & this, L & l                 ) with(this) { WAIT( 0, &l    ) }
336        void wait( condition_variable(L) & this, L & l, uintptr_t info ) with(this) { WAIT( info, &l ) }
337
338        bool wait( condition_variable(L) & this, Duration duration                        ) with(this) { WAIT_TIME( 0   , 0p , __kernel_get_time() + duration ) }
339        bool wait( condition_variable(L) & this, uintptr_t info, Duration duration        ) with(this) { WAIT_TIME( info, 0p , __kernel_get_time() + duration ) }
340        bool wait( condition_variable(L) & this, Time time                                ) with(this) { WAIT_TIME( 0   , 0p , time ) }
341        bool wait( condition_variable(L) & this, uintptr_t info, Time time                ) with(this) { WAIT_TIME( info, 0p , time ) }
342        bool wait( condition_variable(L) & this, L & l, Duration duration                 ) with(this) { WAIT_TIME( 0   , &l , __kernel_get_time() + duration ) }
343        bool wait( condition_variable(L) & this, L & l, uintptr_t info, Duration duration ) with(this) { WAIT_TIME( info, &l , __kernel_get_time() + duration ) }
344        bool wait( condition_variable(L) & this, L & l, Time time                         ) with(this) { WAIT_TIME( 0   , &l , time ) }
345        bool wait( condition_variable(L) & this, L & l, uintptr_t info, Time time         ) with(this) { WAIT_TIME( info, &l , time ) }
346}
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
375bool V(semaphore & this) with( this ) {
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
387        unpark( thrd );
388
389        return thrd != 0p;
390}
391
392bool V(semaphore & this, unsigned diff) with( this ) {
393        $thread * thrd = 0p;
394        lock( lock __cfaabi_dbg_ctx2 );
395        int release = max(-count, (int)diff);
396        count += diff;
397        for(release) {
398                unpark( pop_head( waiting ) );
399        }
400
401        unlock( lock );
402
403        return thrd != 0p;
404}
Note: See TracBrowser for help on using the repository browser.