source: libcfa/src/concurrency/ready_queue.cfa @ 52769ba

arm-ehenumforall-pointer-decayjacob/cs343-translationnew-astnew-ast-unique-exprpthread-emulationqualifiedEnum
Last change on this file since 52769ba was 52769ba, checked in by Thierry Delisle <tdelisle@…>, 3 years ago

Added statistics for local success when biased

  • Property mode set to 100644
File size: 17.0 KB
Line 
1//
2// Cforall Version 1.0.0 Copyright (C) 2019 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// ready_queue.cfa --
8//
9// Author           : Thierry Delisle
10// Created On       : Mon Nov dd 16:29:18 2019
11// Last Modified By :
12// Last Modified On :
13// Update Count     :
14//
15
16#define __cforall_thread__
17// #define __CFA_DEBUG_PRINT_READY_QUEUE__
18
19#include "bits/defs.hfa"
20#include "kernel_private.hfa"
21
22#define _GNU_SOURCE
23#include "stdlib.hfa"
24#include "math.hfa"
25
26#include <unistd.h>
27
28#include "snzi.hfa"
29#include "ready_subqueue.hfa"
30
31static const size_t cache_line_size = 64;
32
33// No overriden function, no environment variable, no define
34// fall back to a magic number
35#ifndef __CFA_MAX_PROCESSORS__
36        #define __CFA_MAX_PROCESSORS__ 1024
37#endif
38
39#define BIAS 8
40
41// returns the maximum number of processors the RWLock support
42__attribute__((weak)) unsigned __max_processors() {
43        const char * max_cores_s = getenv("CFA_MAX_PROCESSORS");
44        if(!max_cores_s) {
45                __cfadbg_print_nolock(ready_queue, "No CFA_MAX_PROCESSORS in ENV\n");
46                return __CFA_MAX_PROCESSORS__;
47        }
48
49        char * endptr = 0p;
50        long int max_cores_l = strtol(max_cores_s, &endptr, 10);
51        if(max_cores_l < 1 || max_cores_l > 65535) {
52                __cfadbg_print_nolock(ready_queue, "CFA_MAX_PROCESSORS out of range : %ld\n", max_cores_l);
53                return __CFA_MAX_PROCESSORS__;
54        }
55        if('\0' != *endptr) {
56                __cfadbg_print_nolock(ready_queue, "CFA_MAX_PROCESSORS not a decimal number : %s\n", max_cores_s);
57                return __CFA_MAX_PROCESSORS__;
58        }
59
60        return max_cores_l;
61}
62
63//=======================================================================
64// Cluster wide reader-writer lock
65//=======================================================================
66void  ?{}(__scheduler_RWLock_t & this) {
67        this.max   = __max_processors();
68        this.alloc = 0;
69        this.ready = 0;
70        this.lock  = false;
71        this.data  = alloc(this.max);
72
73        /*paranoid*/ verify( 0 == (((uintptr_t)(this.data    )) % 64) );
74        /*paranoid*/ verify( 0 == (((uintptr_t)(this.data + 1)) % 64) );
75        /*paranoid*/ verify(__atomic_is_lock_free(sizeof(this.alloc), &this.alloc));
76        /*paranoid*/ verify(__atomic_is_lock_free(sizeof(this.ready), &this.ready));
77
78}
79void ^?{}(__scheduler_RWLock_t & this) {
80        free(this.data);
81}
82
83void ?{}( __scheduler_lock_id_t & this, __processor_id_t * proc ) {
84        this.handle = proc;
85        this.lock   = false;
86        #ifdef __CFA_WITH_VERIFY__
87                this.owned  = false;
88        #endif
89}
90
91//=======================================================================
92// Lock-Free registering/unregistering of threads
93unsigned doregister( struct __processor_id_t * proc ) with(*__scheduler_lock) {
94        __cfadbg_print_safe(ready_queue, "Kernel : Registering proc %p for RW-Lock\n", proc);
95
96        // Step - 1 : check if there is already space in the data
97        uint_fast32_t s = ready;
98
99        // Check among all the ready
100        for(uint_fast32_t i = 0; i < s; i++) {
101                __processor_id_t * null = 0p; // Re-write every loop since compare thrashes it
102                if( __atomic_load_n(&data[i].handle, (int)__ATOMIC_RELAXED) == null
103                        && __atomic_compare_exchange_n( &data[i].handle, &null, proc, false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)) {
104                        /*paranoid*/ verify(i < ready);
105                        /*paranoid*/ verify(0 == (__alignof__(data[i]) % cache_line_size));
106                        /*paranoid*/ verify((((uintptr_t)&data[i]) % cache_line_size) == 0);
107                        return i;
108                }
109        }
110
111        if(max <= alloc) abort("Trying to create more than %ud processors", __scheduler_lock->max);
112
113        // Step - 2 : F&A to get a new spot in the array.
114        uint_fast32_t n = __atomic_fetch_add(&alloc, 1, __ATOMIC_SEQ_CST);
115        if(max <= n) abort("Trying to create more than %ud processors", __scheduler_lock->max);
116
117        // Step - 3 : Mark space as used and then publish it.
118        __scheduler_lock_id_t * storage = (__scheduler_lock_id_t *)&data[n];
119        (*storage){ proc };
120        while(true) {
121                unsigned copy = n;
122                if( __atomic_load_n(&ready, __ATOMIC_RELAXED) == n
123                        && __atomic_compare_exchange_n(&ready, &copy, n + 1, true, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST))
124                        break;
125                asm volatile("pause");
126        }
127
128        __cfadbg_print_safe(ready_queue, "Kernel : Registering proc %p done, id %lu\n", proc, n);
129
130        // Return new spot.
131        /*paranoid*/ verify(n < ready);
132        /*paranoid*/ verify(__alignof__(data[n]) == (2 * cache_line_size));
133        /*paranoid*/ verify((((uintptr_t)&data[n]) % cache_line_size) == 0);
134        return n;
135}
136
137void unregister( struct __processor_id_t * proc ) with(*__scheduler_lock) {
138        unsigned id = proc->id;
139        /*paranoid*/ verify(id < ready);
140        /*paranoid*/ verify(proc == __atomic_load_n(&data[id].handle, __ATOMIC_RELAXED));
141        __atomic_store_n(&data[id].handle, 0p, __ATOMIC_RELEASE);
142
143        __cfadbg_print_safe(ready_queue, "Kernel : Unregister proc %p\n", proc);
144}
145
146//-----------------------------------------------------------------------
147// Writer side : acquire when changing the ready queue, e.g. adding more
148//  queues or removing them.
149uint_fast32_t ready_mutate_lock( void ) with(*__scheduler_lock) {
150        // Step 1 : lock global lock
151        // It is needed to avoid processors that register mid Critical-Section
152        //   to simply lock their own lock and enter.
153        __atomic_acquire( &lock );
154
155        // Step 2 : lock per-proc lock
156        // Processors that are currently being registered aren't counted
157        //   but can't be in read_lock or in the critical section.
158        // All other processors are counted
159        uint_fast32_t s = ready;
160        for(uint_fast32_t i = 0; i < s; i++) {
161                __atomic_acquire( &data[i].lock );
162        }
163
164        return s;
165}
166
167void ready_mutate_unlock( uint_fast32_t last_s ) with(*__scheduler_lock) {
168        // Step 1 : release local locks
169        // This must be done while the global lock is held to avoid
170        //   threads that where created mid critical section
171        //   to race to lock their local locks and have the writer
172        //   immidiately unlock them
173        // Alternative solution : return s in write_lock and pass it to write_unlock
174        for(uint_fast32_t i = 0; i < last_s; i++) {
175                verify(data[i].lock);
176                __atomic_store_n(&data[i].lock, (bool)false, __ATOMIC_RELEASE);
177        }
178
179        // Step 2 : release global lock
180        /*paranoid*/ assert(true == lock);
181        __atomic_store_n(&lock, (bool)false, __ATOMIC_RELEASE);
182}
183
184//=======================================================================
185// Cforall Reqdy Queue used for scheduling
186//=======================================================================
187void ?{}(__ready_queue_t & this) with (this) {
188
189        lanes.data = alloc(4);
190        for( i; 4 ) {
191                (lanes.data[i]){};
192        }
193        lanes.count = 4;
194        snzi{ log2( lanes.count / 8 ) };
195}
196
197void ^?{}(__ready_queue_t & this) with (this) {
198        verify( 4  == lanes.count );
199        verify( !query( snzi ) );
200
201        ^(snzi){};
202
203        for( i; 4 ) {
204                ^(lanes.data[i]){};
205        }
206        free(lanes.data);
207}
208
209//-----------------------------------------------------------------------
210__attribute__((hot)) bool query(struct cluster * cltr) {
211        return query(cltr->ready_queue.snzi);
212}
213
214//-----------------------------------------------------------------------
215__attribute__((hot)) bool push(struct cluster * cltr, struct $thread * thrd) with (cltr->ready_queue) {
216        __cfadbg_print_safe(ready_queue, "Kernel : Pushing %p on cluster %p\n", thrd, cltr);
217
218        // write timestamp
219        thrd->link.ts = rdtscl();
220
221        #if defined(BIAS) && !defined(__CFA_NO_STATISTICS__)
222                bool local = false;
223        #endif
224
225        // Try to pick a lane and lock it
226        unsigned i;
227        do {
228                // Pick the index of a lane
229                #if defined(BIAS)
230                        unsigned r = __tls_rand();
231                        unsigned rlow  = r % BIAS;
232                        unsigned rhigh = r / BIAS;
233                        if((0 != rlow) && kernelTLS.this_processor) {
234                                // (BIAS - 1) out of BIAS chances
235                                // Use perferred queues
236                                unsigned pid = kernelTLS.this_processor->id * 4;
237                                i = pid + (rhigh % 4);
238
239                                #if !defined(__CFA_NO_STATISTICS__)
240                                        local = true;
241                                        __tls_stats()->ready.pick.push.local++;
242                                #endif
243                        }
244                        else {
245                                // 1 out of BIAS chances
246                                // Use all queues
247                                i = rhigh;
248                                local = false;
249                        }
250                #else
251                        i = __tls_rand();
252                #endif
253
254                i %= __atomic_load_n( &lanes.count, __ATOMIC_RELAXED );
255
256                #if !defined(__CFA_NO_STATISTICS__)
257                        __tls_stats()->ready.pick.push.attempt++;
258                #endif
259
260                // If we can't lock it retry
261        } while( !__atomic_try_acquire( &lanes.data[i].lock ) );
262
263        bool first = false;
264
265        // Actually push it
266        bool lane_first = push(lanes.data[i], thrd);
267
268        // If this lane used to be empty we need to do more
269        if(lane_first) {
270                // Check if the entire queue used to be empty
271                first = !query(snzi);
272
273                // Update the snzi
274                arrive( snzi, i );
275        }
276
277        // Unlock and return
278        __atomic_unlock( &lanes.data[i].lock );
279
280        __cfadbg_print_safe(ready_queue, "Kernel : Pushed %p on cluster %p (idx: %u, mask %llu, first %d)\n", thrd, cltr, i, used.mask[0], lane_first);
281
282        // Update statistics
283        #if !defined(__CFA_NO_STATISTICS__)
284                #if defined(BIAS)
285                        if( local ) __tls_stats()->ready.pick.push.lsuccess++;
286                #endif
287                __tls_stats()->ready.pick.push.success++;
288        #endif
289
290        // return whether or not the list was empty before this push
291        return first;
292}
293
294static struct $thread * try_pop(struct cluster * cltr, unsigned i, unsigned j);
295static struct $thread * try_pop(struct cluster * cltr, unsigned i);
296
297// Pop from the ready queue from a given cluster
298__attribute__((hot)) $thread * pop(struct cluster * cltr) with (cltr->ready_queue) {
299        /* paranoid */ verify( lanes.count > 0 );
300        #if defined(BIAS)
301                // Don't bother trying locally too much
302                int local_tries = 8;
303        #endif
304
305        // As long as the list is not empty, try finding a lane that isn't empty and pop from it
306        while( query(snzi) ) {
307                // Pick two lists at random
308                unsigned i,j;
309                #if defined(BIAS)
310                        #if !defined(__CFA_NO_STATISTICS__)
311                                bool local = false;
312                        #endif
313                        uint64_t r = __tls_rand();
314                        unsigned rlow  = r % BIAS;
315                        uint64_t rhigh = r / BIAS;
316                        if(local_tries && 0 != rlow) {
317                                // (BIAS - 1) out of BIAS chances
318                                // Use perferred queues
319                                unsigned pid = kernelTLS.this_processor->id * 4;
320                                i = pid + (rhigh % 4);
321                                j = pid + ((rhigh >> 32ull) % 4);
322
323                                // count the tries
324                                local_tries--;
325
326                                #if !defined(__CFA_NO_STATISTICS__)
327                                        local = true;
328                                        __tls_stats()->ready.pick.pop.local++;
329                                #endif
330                        }
331                        else {
332                                // 1 out of BIAS chances
333                                // Use all queues
334                                i = rhigh;
335                                j = rhigh >> 32ull;
336                        }
337                #else
338                        i = __tls_rand();
339                        j = __tls_rand();
340                #endif
341
342                i %= __atomic_load_n( &lanes.count, __ATOMIC_RELAXED );
343                j %= __atomic_load_n( &lanes.count, __ATOMIC_RELAXED );
344
345                // try popping from the 2 picked lists
346                struct $thread * thrd = try_pop(cltr, i, j);
347                if(thrd) {
348                        #if defined(BIAS) && !defined(__CFA_NO_STATISTICS__)
349                                if( local ) __tls_stats()->ready.pick.pop.lsuccess++;
350                        #endif
351                        return thrd;
352                }
353        }
354
355        // All lanes where empty return 0p
356        return 0p;
357}
358
359//-----------------------------------------------------------------------
360// Given 2 indexes, pick the list with the oldest push an try to pop from it
361static inline struct $thread * try_pop(struct cluster * cltr, unsigned i, unsigned j) with (cltr->ready_queue) {
362        #if !defined(__CFA_NO_STATISTICS__)
363                __tls_stats()->ready.pick.pop.attempt++;
364        #endif
365
366        // Pick the bet list
367        int w = i;
368        if( __builtin_expect(!is_empty(lanes.data[j]), true) ) {
369                w = (ts(lanes.data[i]) < ts(lanes.data[j])) ? i : j;
370        }
371
372        return try_pop(cltr, w);
373}
374
375static inline struct $thread * try_pop(struct cluster * cltr, unsigned w) with (cltr->ready_queue) {
376        // Get relevant elements locally
377        __intrusive_lane_t & lane = lanes.data[w];
378
379        // If list looks empty retry
380        if( is_empty(lane) ) return 0p;
381
382        // If we can't get the lock retry
383        if( !__atomic_try_acquire(&lane.lock) ) return 0p;
384
385
386        // If list is empty, unlock and retry
387        if( is_empty(lane) ) {
388                __atomic_unlock(&lane.lock);
389                return 0p;
390        }
391
392        // Actually pop the list
393        struct $thread * thrd;
394        bool emptied;
395        [thrd, emptied] = pop(lane);
396
397        /* paranoid */ verify(thrd);
398        /* paranoid */ verify(lane.lock);
399
400        // If this was the last element in the lane
401        if(emptied) {
402                depart( snzi, w );
403        }
404
405        // Unlock and return
406        __atomic_unlock(&lane.lock);
407
408        // Update statistics
409        #if !defined(__CFA_NO_STATISTICS__)
410                __tls_stats()->ready.pick.pop.success++;
411        #endif
412
413        // return the popped thread
414        return thrd;
415}
416//-----------------------------------------------------------------------
417
418bool remove_head(struct cluster * cltr, struct $thread * thrd) with (cltr->ready_queue) {
419        for(i; lanes.count) {
420                __intrusive_lane_t & lane = lanes.data[i];
421
422                bool removed = false;
423
424                __atomic_acquire(&lane.lock);
425                        if(head(lane)->link.next == thrd) {
426                                $thread * pthrd;
427                                bool emptied;
428                                [pthrd, emptied] = pop(lane);
429
430                                /* paranoid */ verify( pthrd == thrd );
431
432                                removed = true;
433                                if(emptied) {
434                                        depart( snzi, i );
435                                }
436                        }
437                __atomic_unlock(&lane.lock);
438
439                if( removed ) return true;
440        }
441        return false;
442}
443
444//-----------------------------------------------------------------------
445
446static void check( __ready_queue_t & q ) with (q) {
447        #if defined(__CFA_WITH_VERIFY__)
448                {
449                        for( idx ; lanes.count ) {
450                                __intrusive_lane_t & sl = lanes.data[idx];
451                                assert(!lanes.data[idx].lock);
452
453                                assert(head(sl)->link.prev == 0p );
454                                assert(head(sl)->link.next->link.prev == head(sl) );
455                                assert(tail(sl)->link.next == 0p );
456                                assert(tail(sl)->link.prev->link.next == tail(sl) );
457
458                                if(sl.before.link.ts == 0l) {
459                                        assert(tail(sl)->link.prev == head(sl));
460                                        assert(head(sl)->link.next == tail(sl));
461                                } else {
462                                        assert(tail(sl)->link.prev != head(sl));
463                                        assert(head(sl)->link.next != tail(sl));
464                                }
465                        }
466                }
467        #endif
468}
469
470// Call this function of the intrusive list was moved using memcpy
471// fixes the list so that the pointers back to anchors aren't left dangling
472static inline void fix(__intrusive_lane_t & ll) {
473        // if the list is not empty then follow he pointer and fix its reverse
474        if(!is_empty(ll)) {
475                head(ll)->link.next->link.prev = head(ll);
476                tail(ll)->link.prev->link.next = tail(ll);
477        }
478        // Otherwise just reset the list
479        else {
480                verify(tail(ll)->link.next == 0p);
481                tail(ll)->link.prev = head(ll);
482                head(ll)->link.next = tail(ll);
483                verify(head(ll)->link.prev == 0p);
484        }
485}
486
487// Grow the ready queue
488void ready_queue_grow  (struct cluster * cltr) {
489        /* paranoid */ verify( ready_mutate_islocked() );
490        __cfadbg_print_safe(ready_queue, "Kernel : Growing ready queue\n");
491
492        // Make sure that everything is consistent
493        /* paranoid */ check( cltr->ready_queue );
494
495        // grow the ready queue
496        with( cltr->ready_queue ) {
497                ^(snzi){};
498
499                size_t ncount = lanes.count;
500
501                // increase count
502                ncount += 4;
503
504                // Allocate new array (uses realloc and memcpies the data)
505                lanes.data = alloc(lanes.data, ncount);
506
507                // Fix the moved data
508                for( idx; (size_t)lanes.count ) {
509                        fix(lanes.data[idx]);
510                }
511
512                // Construct new data
513                for( idx; (size_t)lanes.count ~ ncount) {
514                        (lanes.data[idx]){};
515                }
516
517                // Update original
518                lanes.count = ncount;
519
520                // Re-create the snzi
521                snzi{ log2( lanes.count / 8 ) };
522                for( idx; (size_t)lanes.count ) {
523                        if( !is_empty(lanes.data[idx]) ) {
524                                arrive(snzi, idx);
525                        }
526                }
527        }
528
529        // Make sure that everything is consistent
530        /* paranoid */ check( cltr->ready_queue );
531
532        __cfadbg_print_safe(ready_queue, "Kernel : Growing ready queue done\n");
533
534        /* paranoid */ verify( ready_mutate_islocked() );
535}
536
537// Shrink the ready queue
538void ready_queue_shrink(struct cluster * cltr) {
539        /* paranoid */ verify( ready_mutate_islocked() );
540        __cfadbg_print_safe(ready_queue, "Kernel : Shrinking ready queue\n");
541
542        // Make sure that everything is consistent
543        /* paranoid */ check( cltr->ready_queue );
544
545        with( cltr->ready_queue ) {
546                ^(snzi){};
547
548                size_t ocount = lanes.count;
549                // Check that we have some space left
550                if(ocount < 8) abort("Program attempted to destroy more Ready Queues than were created");
551
552                // reduce the actual count so push doesn't use the old queues
553                lanes.count -= 4;
554                verify(ocount > lanes.count);
555
556                // for printing count the number of displaced threads
557                #if defined(__CFA_DEBUG_PRINT__) || defined(__CFA_DEBUG_PRINT_READY_QUEUE__)
558                        __attribute__((unused)) size_t displaced = 0;
559                #endif
560
561                // redistribute old data
562                for( idx; (size_t)lanes.count ~ ocount) {
563                        // Lock is not strictly needed but makes checking invariants much easier
564                        __attribute__((unused)) bool locked = __atomic_try_acquire(&lanes.data[idx].lock);
565                        verify(locked);
566
567                        // As long as we can pop from this lane to push the threads somewhere else in the queue
568                        while(!is_empty(lanes.data[idx])) {
569                                struct $thread * thrd;
570                                __attribute__((unused)) bool _;
571                                [thrd, _] = pop(lanes.data[idx]);
572
573                                push(cltr, thrd);
574
575                                // for printing count the number of displaced threads
576                                #if defined(__CFA_DEBUG_PRINT__) || defined(__CFA_DEBUG_PRINT_READY_QUEUE__)
577                                        displaced++;
578                                #endif
579                        }
580
581                        // Unlock the lane
582                        __atomic_unlock(&lanes.data[idx].lock);
583
584                        // TODO print the queue statistics here
585
586                        ^(lanes.data[idx]){};
587                }
588
589                __cfadbg_print_safe(ready_queue, "Kernel : Shrinking ready queue displaced %zu threads\n", displaced);
590
591                // Allocate new array (uses realloc and memcpies the data)
592                lanes.data = alloc(lanes.data, lanes.count);
593
594                // Fix the moved data
595                for( idx; (size_t)lanes.count ) {
596                        fix(lanes.data[idx]);
597                }
598
599                // Re-create the snzi
600                snzi{ log2( lanes.count / 8 ) };
601                for( idx; (size_t)lanes.count ) {
602                        if( !is_empty(lanes.data[idx]) ) {
603                                arrive(snzi, idx);
604                        }
605                }
606        }
607
608        // Make sure that everything is consistent
609        /* paranoid */ check( cltr->ready_queue );
610
611        __cfadbg_print_safe(ready_queue, "Kernel : Shrinking ready queue done\n");
612        /* paranoid */ verify( ready_mutate_islocked() );
613}
Note: See TracBrowser for help on using the repository browser.