source: src/libcfa/concurrency/monitor.c @ fe97a7d8

ADTaaron-thesisarm-ehast-experimentalcleanup-dtorsdeferred_resndemanglerenumforall-pointer-decayjacob/cs343-translationjenkins-sandboxnew-astnew-ast-unique-exprnew-envno_listpersistent-indexerpthread-emulationqualifiedEnumresolv-newwith_gc
Last change on this file since fe97a7d8 was 6b0b624, checked in by Peter A. Buhr <pabuhr@…>, 7 years ago

change #ifndef to #pragma once

  • Property mode set to 100644
File size: 15.3 KB
Line 
1//
2// Cforall Version 1.0.0 Copyright (C) 2016 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// monitor_desc.c --
8//
9// Author           : Thierry Delisle
10// Created On       : Thd Feb 23 12:27:26 2017
11// Last Modified By : Peter A. Buhr
12// Last Modified On : Fri Jul 21 22:37:11 2017
13// Update Count     : 1
14//
15
16#include "monitor"
17
18#include <stdlib>
19
20#include "libhdr.h"
21#include "kernel_private.h"
22
23//-----------------------------------------------------------------------------
24// Forward declarations
25static inline void set_owner( monitor_desc * this, thread_desc * owner );
26static inline thread_desc * next_thread( monitor_desc * this );
27
28static inline void lock_all( spinlock ** locks, unsigned short count );
29static inline void lock_all( monitor_desc ** source, spinlock ** /*out*/ locks, unsigned short count );
30static inline void unlock_all( spinlock ** locks, unsigned short count );
31static inline void unlock_all( monitor_desc ** locks, unsigned short count );
32
33static inline void save_recursion   ( monitor_desc ** ctx, unsigned int * /*out*/ recursions, unsigned short count );
34static inline void restore_recursion( monitor_desc ** ctx, unsigned int * /*in */ recursions, unsigned short count );
35
36static inline thread_desc * check_condition( __condition_criterion_t * );
37static inline void brand_condition( condition * );
38static inline unsigned short insert_unique( thread_desc ** thrds, unsigned short end, thread_desc * val );
39
40//-----------------------------------------------------------------------------
41// Enter/Leave routines
42
43
44extern "C" {
45        void __enter_monitor_desc( monitor_desc * this ) {
46                lock_yield( &this->lock DEBUG_CTX2 );
47                thread_desc * thrd = this_thread;
48
49                // LIB_DEBUG_PRINT_SAFE("%p Entering %p (o: %p, r: %i)\n", thrd, this, this->owner, this->recursion);
50
51                if( !this->owner ) {
52                        //No one has the monitor, just take it
53                        set_owner( this, thrd );
54                }
55                else if( this->owner == thrd) {
56                        //We already have the monitor, just not how many times we took it
57                        verify( this->recursion > 0 );
58                        this->recursion += 1;
59                }
60                else {
61                        //Some one else has the monitor, wait in line for it
62                        append( &this->entry_queue, thrd );
63                        // LIB_DEBUG_PRINT_SAFE("%p Blocking on entry\n", thrd);
64                        BlockInternal( &this->lock );
65
66                        //BlockInternal will unlock spinlock, no need to unlock ourselves
67                        return;
68                }
69
70                unlock( &this->lock );
71                return;
72        }
73
74        // leave pseudo code :
75        //      TODO
76        void __leave_monitor_desc( monitor_desc * this ) {
77                lock_yield( &this->lock DEBUG_CTX2 );
78
79                // LIB_DEBUG_PRINT_SAFE("%p Leaving %p (o: %p, r: %i). ", this_thread, this, this->owner, this->recursion);
80                verifyf( this_thread == this->owner, "Expected owner to be %p, got %p (r: %i)", this_thread, this->owner, this->recursion );
81
82                //Leaving a recursion level, decrement the counter
83                this->recursion -= 1;
84
85                //If we haven't left the last level of recursion
86                //it means we don't need to do anything
87                if( this->recursion != 0) {
88                        unlock( &this->lock );
89                        return;
90                }
91
92                thread_desc * new_owner = next_thread( this );
93
94                //We can now let other threads in safely
95                unlock( &this->lock );
96
97                // LIB_DEBUG_PRINT_SAFE("Next owner is %p\n", new_owner);
98
99                //We need to wake-up the thread
100                WakeThread( new_owner );
101        }
102
103        void __leave_thread_monitor( thread_desc * thrd ) {
104                monitor_desc * this = &thrd->mon;
105                lock_yield( &this->lock DEBUG_CTX2 );
106
107                disable_interrupts();
108
109                thrd->cor.state = Halted;
110
111                verifyf( thrd == this->owner, "Expected owner to be %p, got %p (r: %i)", thrd, this->owner, this->recursion );
112
113                //Leaving a recursion level, decrement the counter
114                this->recursion -= 1;
115
116                //If we haven't left the last level of recursion
117                //it means we don't need to do anything
118                if( this->recursion != 0) {
119                        unlock( &this->lock );
120                        return;
121                }
122
123                thread_desc * new_owner = next_thread( this );
124
125                LeaveThread( &this->lock, new_owner );
126        }
127}
128
129static inline void enter(monitor_desc ** monitors, int count) {
130        for(int i = 0; i < count; i++) {
131                __enter_monitor_desc( monitors[i] );
132        }
133}
134
135static inline void leave(monitor_desc ** monitors, int count) {
136        for(int i = count - 1; i >= 0; i--) {
137                __leave_monitor_desc( monitors[i] );
138        }
139}
140
141void ?{}( monitor_guard_t * this, monitor_desc ** m, int count ) {
142        this->m = m;
143        this->count = count;
144        qsort(this->m, count);
145        enter( this->m, this->count );
146
147        this->prev_mntrs = this_thread->current_monitors;
148        this->prev_count = this_thread->current_monitor_count;
149
150        this_thread->current_monitors      = m;
151        this_thread->current_monitor_count = count;
152}
153
154void ^?{}( monitor_guard_t * this ) {
155        leave( this->m, this->count );
156
157        this_thread->current_monitors      = this->prev_mntrs;
158        this_thread->current_monitor_count = this->prev_count;
159}
160
161void ?{}(__condition_node_t * this, thread_desc * waiting_thread, unsigned short count, uintptr_t user_info ) {
162        this->waiting_thread = waiting_thread;
163        this->count = count;
164        this->next = NULL;
165        this->user_info = user_info;
166}
167
168void ?{}(__condition_criterion_t * this ) {
169        this->ready  = false;
170        this->target = NULL;
171        this->owner  = NULL;
172        this->next   = NULL;
173}
174
175void ?{}(__condition_criterion_t * this, monitor_desc * target, __condition_node_t * owner ) {
176        this->ready  = false;
177        this->target = target;
178        this->owner  = owner;
179        this->next   = NULL;
180}
181
182//-----------------------------------------------------------------------------
183// Internal scheduling
184void wait( condition * this, uintptr_t user_info = 0 ) {
185        // LIB_DEBUG_PRINT_SAFE("Waiting\n");
186
187        brand_condition( this );
188
189        //Check that everything is as expected
190        assertf( this->monitors != NULL, "Waiting with no monitors (%p)", this->monitors );
191        verifyf( this->monitor_count != 0, "Waiting with 0 monitors (%i)", this->monitor_count );
192        verifyf( this->monitor_count < 32u, "Excessive monitor count (%i)", this->monitor_count );
193
194        unsigned short count = this->monitor_count;
195        unsigned int recursions[ count ];               //Save the current recursion levels to restore them later
196        spinlock *   locks     [ count ];               //We need to pass-in an array of locks to BlockInternal
197
198        // LIB_DEBUG_PRINT_SAFE("count %i\n", count);
199
200        __condition_node_t waiter = { (thread_desc*)this_thread, count, user_info };
201
202        __condition_criterion_t criteria[count];
203        for(int i = 0; i < count; i++) {
204                (&criteria[i]){ this->monitors[i], &waiter };
205                // LIB_DEBUG_PRINT_SAFE( "Criterion %p\n", &criteria[i] );
206        }
207
208        waiter.criteria = criteria;
209        append( &this->blocked, &waiter );
210
211        lock_all( this->monitors, locks, count );
212        save_recursion( this->monitors, recursions, count );
213        //DON'T unlock, ask the kernel to do it
214
215        //Find the next thread(s) to run
216        unsigned short thread_count = 0;
217        thread_desc * threads[ count ];
218        for(int i = 0; i < count; i++) {
219                threads[i] = 0;
220        }
221
222        for( int i = 0; i < count; i++) {
223                thread_desc * new_owner = next_thread( this->monitors[i] );
224                thread_count = insert_unique( threads, thread_count, new_owner );
225        }
226
227        // LIB_DEBUG_PRINT_SAFE("Will unblock: ");
228        for(int i = 0; i < thread_count; i++) {
229                // LIB_DEBUG_PRINT_SAFE("%p ", threads[i]);
230        }
231        // LIB_DEBUG_PRINT_SAFE("\n");
232
233        // Everything is ready to go to sleep
234        BlockInternal( locks, count, threads, thread_count );
235
236
237        //WE WOKE UP
238
239
240        //We are back, restore the owners and recursions
241        lock_all( locks, count );
242        restore_recursion( this->monitors, recursions, count );
243        unlock_all( locks, count );
244}
245
246bool signal( condition * this ) {
247        if( is_empty( this ) ) {
248                // LIB_DEBUG_PRINT_SAFE("Nothing to signal\n");
249                return false;
250        }
251
252        //Check that everything is as expected
253        verify( this->monitors );
254        verify( this->monitor_count != 0 );
255
256        unsigned short count = this->monitor_count;
257
258        //Some more checking in debug
259        LIB_DEBUG_DO(
260                thread_desc * this_thrd = this_thread;
261                if ( this->monitor_count != this_thrd->current_monitor_count ) {
262                        abortf( "Signal on condition %p made with different number of monitor(s), expected %i got %i", this, this->monitor_count, this_thrd->current_monitor_count );
263                } // if
264
265                for(int i = 0; i < this->monitor_count; i++) {
266                        if ( this->monitors[i] != this_thrd->current_monitors[i] ) {
267                                abortf( "Signal on condition %p made with different monitor, expected %p got %i", this, this->monitors[i], this_thrd->current_monitors[i] );
268                        } // if
269                }
270        );
271
272        //Lock all the monitors
273        lock_all( this->monitors, NULL, count );
274        // LIB_DEBUG_PRINT_SAFE("Signalling");
275
276        //Pop the head of the waiting queue
277        __condition_node_t * node = pop_head( &this->blocked );
278
279        //Add the thread to the proper AS stack
280        for(int i = 0; i < count; i++) {
281                __condition_criterion_t * crit = &node->criteria[i];
282                // LIB_DEBUG_PRINT_SAFE(" %p", crit->target);
283                assert( !crit->ready );
284                push( &crit->target->signal_stack, crit );
285        }
286
287        // LIB_DEBUG_PRINT_SAFE("\n");
288
289        //Release
290        unlock_all( this->monitors, count );
291
292        return true;
293}
294
295bool signal_block( condition * this ) {
296        if( !this->blocked.head ) {
297                LIB_DEBUG_PRINT_SAFE("Nothing to signal\n");
298                return false;
299        }
300
301        //Check that everything is as expected
302        verifyf( this->monitors != NULL, "Waiting with no monitors (%p)", this->monitors );
303        verifyf( this->monitor_count != 0, "Waiting with 0 monitors (%i)", this->monitor_count );
304
305        unsigned short count = this->monitor_count;
306        unsigned int recursions[ count ];               //Save the current recursion levels to restore them later
307        spinlock *   locks     [ count ];               //We need to pass-in an array of locks to BlockInternal
308
309        lock_all( this->monitors, locks, count );
310
311        //create creteria
312        __condition_node_t waiter = { (thread_desc*)this_thread, count, 0 };
313
314        __condition_criterion_t criteria[count];
315        for(int i = 0; i < count; i++) {
316                (&criteria[i]){ this->monitors[i], &waiter };
317                // LIB_DEBUG_PRINT_SAFE( "Criterion %p\n", &criteria[i] );
318                push( &criteria[i].target->signal_stack, &criteria[i] );
319        }
320
321        waiter.criteria = criteria;
322
323        //save contexts
324        save_recursion( this->monitors, recursions, count );
325
326        //Find the thread to run
327        thread_desc * signallee = pop_head( &this->blocked )->waiting_thread;
328        for(int i = 0; i < count; i++) {
329                set_owner( this->monitors[i], signallee );
330        }
331
332        LIB_DEBUG_PRINT_SAFE( "Waiting on signal block\n" );
333
334        //Everything is ready to go to sleep
335        BlockInternal( locks, count, &signallee, 1 );
336
337
338
339
340        LIB_DEBUG_PRINT_SAFE( "Back from signal block\n" );
341
342        //We are back, restore the owners and recursions
343        lock_all( locks, count );
344        restore_recursion( this->monitors, recursions, count );
345        unlock_all( locks, count );
346
347        return true;
348}
349
350uintptr_t front( condition * this ) {
351        verifyf( !is_empty(this),
352                "Attempt to access user data on an empty condition.\n"
353                "Possible cause is not checking if the condition is empty before reading stored data."
354        );
355        return this->blocked.head->user_info;
356}
357
358//-----------------------------------------------------------------------------
359// Internal scheduling
360void __accept_internal( unsigned short count, __acceptable_t * acceptables, void (*func)(void) ) {
361        // thread_desc * this = this_thread;
362
363        // unsigned short count = this->current_monitor_count;
364        // unsigned int recursions[ count ];            //Save the current recursion levels to restore them later
365        // spinlock *   locks     [ count ];            //We need to pass-in an array of locks to BlockInternal
366
367        // lock_all( this->current_monitors, locks, count );
368
369
370
371
372
373        // // // Everything is ready to go to sleep
374        // // BlockInternal( locks, count, threads, thread_count );
375
376
377        // //WE WOKE UP
378
379
380        // //We are back, restore the owners and recursions
381        // lock_all( locks, count );
382        // restore_recursion( this->monitors, recursions, count );
383        // unlock_all( locks, count );
384}
385
386//-----------------------------------------------------------------------------
387// Utilities
388
389static inline void set_owner( monitor_desc * this, thread_desc * owner ) {
390        //Pass the monitor appropriately
391        this->owner = owner;
392
393        //We are passing the monitor to someone else, which means recursion level is not 0
394        this->recursion = owner ? 1 : 0;
395}
396
397static inline thread_desc * next_thread( monitor_desc * this ) {
398        //Check the signaller stack
399        __condition_criterion_t * urgent = pop( &this->signal_stack );
400        if( urgent ) {
401                //The signaller stack is not empty,
402                //regardless of if we are ready to baton pass,
403                //we need to set the monitor as in use
404                set_owner( this,  urgent->owner->waiting_thread );
405
406                return check_condition( urgent );
407        }
408
409        // No signaller thread
410        // Get the next thread in the entry_queue
411        thread_desc * new_owner = pop_head( &this->entry_queue );
412        set_owner( this, new_owner );
413
414        return new_owner;
415}
416
417static inline void lock_all( spinlock ** locks, unsigned short count ) {
418        for( int i = 0; i < count; i++ ) {
419                lock_yield( locks[i] DEBUG_CTX2 );
420        }
421}
422
423static inline void lock_all( monitor_desc ** source, spinlock ** /*out*/ locks, unsigned short count ) {
424        for( int i = 0; i < count; i++ ) {
425                spinlock * l = &source[i]->lock;
426                lock_yield( l DEBUG_CTX2 );
427                if(locks) locks[i] = l;
428        }
429}
430
431static inline void unlock_all( spinlock ** locks, unsigned short count ) {
432        for( int i = 0; i < count; i++ ) {
433                unlock( locks[i] );
434        }
435}
436
437static inline void unlock_all( monitor_desc ** locks, unsigned short count ) {
438        for( int i = 0; i < count; i++ ) {
439                unlock( &locks[i]->lock );
440        }
441}
442
443
444static inline void save_recursion   ( monitor_desc ** ctx, unsigned int * /*out*/ recursions, unsigned short count ) {
445        for( int i = 0; i < count; i++ ) {
446                recursions[i] = ctx[i]->recursion;
447        }
448}
449
450static inline void restore_recursion( monitor_desc ** ctx, unsigned int * /*in */ recursions, unsigned short count ) {
451        for( int i = 0; i < count; i++ ) {
452                ctx[i]->recursion = recursions[i];
453        }
454}
455
456// Function has 2 different behavior
457// 1 - Marks a monitors as being ready to run
458// 2 - Checks if all the monitors are ready to run
459//     if so return the thread to run
460static inline thread_desc * check_condition( __condition_criterion_t * target ) {
461        __condition_node_t * node = target->owner;
462        unsigned short count = node->count;
463        __condition_criterion_t * criteria = node->criteria;
464
465        bool ready2run = true;
466
467        for(    int i = 0; i < count; i++ ) {
468
469                // LIB_DEBUG_PRINT_SAFE( "Checking %p for %p\n", &criteria[i], target );
470                if( &criteria[i] == target ) {
471                        criteria[i].ready = true;
472                        // LIB_DEBUG_PRINT_SAFE( "True\n" );
473                }
474
475                ready2run = criteria[i].ready && ready2run;
476        }
477
478        // LIB_DEBUG_PRINT_SAFE( "Runing %i\n", ready2run );
479        return ready2run ? node->waiting_thread : NULL;
480}
481
482static inline void brand_condition( condition * this ) {
483        thread_desc * thrd = this_thread;
484        if( !this->monitors ) {
485                // LIB_DEBUG_PRINT_SAFE("Branding\n");
486                assertf( thrd->current_monitors != NULL, "No current monitor to brand condition", thrd->current_monitors );
487                this->monitor_count = thrd->current_monitor_count;
488
489                this->monitors = malloc( this->monitor_count * sizeof( *this->monitors ) );
490                for( int i = 0; i < this->monitor_count; i++ ) {
491                        this->monitors[i] = thrd->current_monitors[i];
492                }
493        }
494}
495
496static inline unsigned short insert_unique( thread_desc ** thrds, unsigned short end, thread_desc * val ) {
497        if( !val ) return end;
498
499        for(int i = 0; i <= end; i++) {
500                if( thrds[i] == val ) return end;
501        }
502
503        thrds[end] = val;
504        return end + 1;
505}
506
507void ?{}( __condition_blocked_queue_t * this ) {
508        this->head = NULL;
509        this->tail = &this->head;
510}
511
512void append( __condition_blocked_queue_t * this, __condition_node_t * c ) {
513        verify(this->tail != NULL);
514        *this->tail = c;
515        this->tail = &c->next;
516}
517
518__condition_node_t * pop_head( __condition_blocked_queue_t * this ) {
519        __condition_node_t * head = this->head;
520        if( head ) {
521                this->head = head->next;
522                if( !head->next ) {
523                        this->tail = &this->head;
524                }
525                head->next = NULL;
526        }
527        return head;
528}
529
530// Local Variables: //
531// mode: c //
532// tab-width: 4 //
533// End: //
Note: See TracBrowser for help on using the repository browser.