source: libcfa/src/concurrency/ready_queue.cfa @ 13c5e19

arm-ehenumforall-pointer-decayjacob/cs343-translationnew-astnew-ast-unique-exprpthread-emulationqualifiedEnum
Last change on this file since 13c5e19 was 13c5e19, checked in by Thierry Delisle <tdelisle@…>, 3 years ago
  • Moved snzi and subqueues outside of ready_queue.cfa.
  • Added random.hfa with multiple prng.
  • Minor optimizations to ready-queue
  • Stats now track number of local pops( bias pops )
  • Fixed stats for io
  • Fixed calculaton of nprocessors
  • Fixed IO to work with new ready-queue
  • Property mode set to 100644
File size: 16.6 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        // Try to pick a lane and lock it
222        unsigned i;
223        do {
224                // Pick the index of a lane
225                #if defined(BIAS)
226                        unsigned r = __tls_rand();
227                        unsigned rlow  = r % BIAS;
228                        unsigned rhigh = r / BIAS;
229                        if((0 != rlow) && kernelTLS.this_processor) {
230                                // (BIAS - 1) out of BIAS chances
231                                // Use perferred queues
232                                unsigned pid = kernelTLS.this_processor->id * 4;
233                                i = pid + (rhigh % 4);
234
235                                #if !defined(__CFA_NO_STATISTICS__)
236                                        __tls_stats()->ready.pick.push.local++;
237                                #endif
238                        }
239                        else {
240                                // 1 out of BIAS chances
241                                // Use all queues
242                                i = rhigh;
243                        }
244                #else
245                        i = __tls_rand();
246                #endif
247
248                i %= __atomic_load_n( &lanes.count, __ATOMIC_RELAXED );
249
250                #if !defined(__CFA_NO_STATISTICS__)
251                        __tls_stats()->ready.pick.push.attempt++;
252                #endif
253
254                // If we can't lock it retry
255        } while( !__atomic_try_acquire( &lanes.data[i].lock ) );
256
257        bool first = false;
258
259        // Actually push it
260        bool lane_first = push(lanes.data[i], thrd);
261
262        // If this lane used to be empty we need to do more
263        if(lane_first) {
264                // Check if the entire queue used to be empty
265                first = !query(snzi);
266
267                // Update the snzi
268                arrive( snzi, i );
269        }
270
271        // Unlock and return
272        __atomic_unlock( &lanes.data[i].lock );
273
274        __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);
275
276        // Update statistics
277        #if !defined(__CFA_NO_STATISTICS__)
278                __tls_stats()->ready.pick.push.success++;
279        #endif
280
281        // return whether or not the list was empty before this push
282        return first;
283}
284
285static struct $thread * try_pop(struct cluster * cltr, unsigned i, unsigned j);
286static struct $thread * try_pop(struct cluster * cltr, unsigned i);
287
288// Pop from the ready queue from a given cluster
289__attribute__((hot)) $thread * pop(struct cluster * cltr) with (cltr->ready_queue) {
290        /* paranoid */ verify( lanes.count > 0 );
291        #if defined(BIAS)
292                // Don't bother trying locally too much
293                int local_tries = 8;
294        #endif
295
296        // As long as the list is not empty, try finding a lane that isn't empty and pop from it
297        while( query(snzi) ) {
298                // Pick two lists at random
299                unsigned i,j;
300                #if defined(BIAS)
301                        uint64_t r = __tls_rand();
302                        unsigned rlow  = r % BIAS;
303                        uint64_t rhigh = r / BIAS;
304                        if(local_tries && 0 != rlow) {
305                                // (BIAS - 1) out of BIAS chances
306                                // Use perferred queues
307                                unsigned pid = kernelTLS.this_processor->id * 4;
308                                i = pid + (rhigh % 4);
309                                j = pid + ((rhigh >> 32ull) % 4);
310
311                                // count the tries
312                                local_tries--;
313
314                                #if !defined(__CFA_NO_STATISTICS__)
315                                        __tls_stats()->ready.pick.pop.local++;
316                                #endif
317                        }
318                        else {
319                                // 1 out of BIAS chances
320                                // Use all queues
321                                i = rhigh;
322                                j = rhigh >> 32ull;
323                        }
324                #else
325                        i = __tls_rand();
326                        j = __tls_rand();
327                #endif
328
329                i %= __atomic_load_n( &lanes.count, __ATOMIC_RELAXED );
330                j %= __atomic_load_n( &lanes.count, __ATOMIC_RELAXED );
331
332                // try popping from the 2 picked lists
333                struct $thread * thrd = try_pop(cltr, i, j);
334                if(thrd) return thrd;
335        }
336
337        // All lanes where empty return 0p
338        return 0p;
339}
340
341//-----------------------------------------------------------------------
342// Given 2 indexes, pick the list with the oldest push an try to pop from it
343static inline struct $thread * try_pop(struct cluster * cltr, unsigned i, unsigned j) with (cltr->ready_queue) {
344        #if !defined(__CFA_NO_STATISTICS__)
345                __tls_stats()->ready.pick.pop.attempt++;
346        #endif
347
348        // Pick the bet list
349        int w = i;
350        if( __builtin_expect(!is_empty(lanes.data[j]), true) ) {
351                w = (ts(lanes.data[i]) < ts(lanes.data[j])) ? i : j;
352        }
353
354        return try_pop(cltr, w);
355}
356
357static inline struct $thread * try_pop(struct cluster * cltr, unsigned w) with (cltr->ready_queue) {
358        // Get relevant elements locally
359        __intrusive_lane_t & lane = lanes.data[w];
360
361        // If list looks empty retry
362        if( is_empty(lane) ) return 0p;
363
364        // If we can't get the lock retry
365        if( !__atomic_try_acquire(&lane.lock) ) return 0p;
366
367
368        // If list is empty, unlock and retry
369        if( is_empty(lane) ) {
370                __atomic_unlock(&lane.lock);
371                return 0p;
372        }
373
374        // Actually pop the list
375        struct $thread * thrd;
376        bool emptied;
377        [thrd, emptied] = pop(lane);
378
379        /* paranoid */ verify(thrd);
380        /* paranoid */ verify(lane.lock);
381
382        // If this was the last element in the lane
383        if(emptied) {
384                depart( snzi, w );
385        }
386
387        // Unlock and return
388        __atomic_unlock(&lane.lock);
389
390        // Update statistics
391        #if !defined(__CFA_NO_STATISTICS__)
392                __tls_stats()->ready.pick.pop.success++;
393        #endif
394
395        // return the popped thread
396        return thrd;
397}
398//-----------------------------------------------------------------------
399
400bool remove_head(struct cluster * cltr, struct $thread * thrd) with (cltr->ready_queue) {
401        for(i; lanes.count) {
402                __intrusive_lane_t & lane = lanes.data[i];
403
404                bool removed = false;
405
406                __atomic_acquire(&lane.lock);
407                        if(head(lane)->link.next == thrd) {
408                                $thread * pthrd;
409                                bool emptied;
410                                [pthrd, emptied] = pop(lane);
411
412                                /* paranoid */ verify( pthrd == thrd );
413
414                                removed = true;
415                                if(emptied) {
416                                        depart( snzi, i );
417                                }
418                        }
419                __atomic_unlock(&lane.lock);
420
421                if( removed ) return true;
422        }
423        return false;
424}
425
426//-----------------------------------------------------------------------
427
428static void check( __ready_queue_t & q ) with (q) {
429        #if defined(__CFA_WITH_VERIFY__)
430                {
431                        for( idx ; lanes.count ) {
432                                __intrusive_lane_t & sl = lanes.data[idx];
433                                assert(!lanes.data[idx].lock);
434
435                                assert(head(sl)->link.prev == 0p );
436                                assert(head(sl)->link.next->link.prev == head(sl) );
437                                assert(tail(sl)->link.next == 0p );
438                                assert(tail(sl)->link.prev->link.next == tail(sl) );
439
440                                if(sl.before.link.ts == 0l) {
441                                        assert(tail(sl)->link.prev == head(sl));
442                                        assert(head(sl)->link.next == tail(sl));
443                                } else {
444                                        assert(tail(sl)->link.prev != head(sl));
445                                        assert(head(sl)->link.next != tail(sl));
446                                }
447                        }
448                }
449        #endif
450}
451
452// Call this function of the intrusive list was moved using memcpy
453// fixes the list so that the pointers back to anchors aren't left dangling
454static inline void fix(__intrusive_lane_t & ll) {
455        // if the list is not empty then follow he pointer and fix its reverse
456        if(!is_empty(ll)) {
457                head(ll)->link.next->link.prev = head(ll);
458                tail(ll)->link.prev->link.next = tail(ll);
459        }
460        // Otherwise just reset the list
461        else {
462                verify(tail(ll)->link.next == 0p);
463                tail(ll)->link.prev = head(ll);
464                head(ll)->link.next = tail(ll);
465                verify(head(ll)->link.prev == 0p);
466        }
467}
468
469// Grow the ready queue
470void ready_queue_grow  (struct cluster * cltr) {
471        /* paranoid */ verify( ready_mutate_islocked() );
472        __cfadbg_print_safe(ready_queue, "Kernel : Growing ready queue\n");
473
474        // Make sure that everything is consistent
475        /* paranoid */ check( cltr->ready_queue );
476
477        // grow the ready queue
478        with( cltr->ready_queue ) {
479                ^(snzi){};
480
481                size_t ncount = lanes.count;
482
483                // increase count
484                ncount += 4;
485
486                // Allocate new array (uses realloc and memcpies the data)
487                lanes.data = alloc(lanes.data, ncount);
488
489                // Fix the moved data
490                for( idx; (size_t)lanes.count ) {
491                        fix(lanes.data[idx]);
492                }
493
494                // Construct new data
495                for( idx; (size_t)lanes.count ~ ncount) {
496                        (lanes.data[idx]){};
497                }
498
499                // Update original
500                lanes.count = ncount;
501
502                // Re-create the snzi
503                snzi{ log2( lanes.count / 8 ) };
504                for( idx; (size_t)lanes.count ) {
505                        if( !is_empty(lanes.data[idx]) ) {
506                                arrive(snzi, idx);
507                        }
508                }
509        }
510
511        // Make sure that everything is consistent
512        /* paranoid */ check( cltr->ready_queue );
513
514        __cfadbg_print_safe(ready_queue, "Kernel : Growing ready queue done\n");
515
516        /* paranoid */ verify( ready_mutate_islocked() );
517}
518
519// Shrink the ready queue
520void ready_queue_shrink(struct cluster * cltr) {
521        /* paranoid */ verify( ready_mutate_islocked() );
522        __cfadbg_print_safe(ready_queue, "Kernel : Shrinking ready queue\n");
523
524        // Make sure that everything is consistent
525        /* paranoid */ check( cltr->ready_queue );
526
527        with( cltr->ready_queue ) {
528                ^(snzi){};
529
530                size_t ocount = lanes.count;
531                // Check that we have some space left
532                if(ocount < 8) abort("Program attempted to destroy more Ready Queues than were created");
533
534                // reduce the actual count so push doesn't use the old queues
535                lanes.count -= 4;
536                verify(ocount > lanes.count);
537
538                // for printing count the number of displaced threads
539                #if defined(__CFA_DEBUG_PRINT__) || defined(__CFA_DEBUG_PRINT_READY_QUEUE__)
540                        __attribute__((unused)) size_t displaced = 0;
541                #endif
542
543                // redistribute old data
544                for( idx; (size_t)lanes.count ~ ocount) {
545                        // Lock is not strictly needed but makes checking invariants much easier
546                        __attribute__((unused)) bool locked = __atomic_try_acquire(&lanes.data[idx].lock);
547                        verify(locked);
548
549                        // As long as we can pop from this lane to push the threads somewhere else in the queue
550                        while(!is_empty(lanes.data[idx])) {
551                                struct $thread * thrd;
552                                __attribute__((unused)) bool _;
553                                [thrd, _] = pop(lanes.data[idx]);
554
555                                push(cltr, thrd);
556
557                                // for printing count the number of displaced threads
558                                #if defined(__CFA_DEBUG_PRINT__) || defined(__CFA_DEBUG_PRINT_READY_QUEUE__)
559                                        displaced++;
560                                #endif
561                        }
562
563                        // Unlock the lane
564                        __atomic_unlock(&lanes.data[idx].lock);
565
566                        // TODO print the queue statistics here
567
568                        ^(lanes.data[idx]){};
569                }
570
571                __cfadbg_print_safe(ready_queue, "Kernel : Shrinking ready queue displaced %zu threads\n", displaced);
572
573                // Allocate new array (uses realloc and memcpies the data)
574                lanes.data = alloc(lanes.data, lanes.count);
575
576                // Fix the moved data
577                for( idx; (size_t)lanes.count ) {
578                        fix(lanes.data[idx]);
579                }
580
581                // Re-create the snzi
582                snzi{ log2( lanes.count / 8 ) };
583                for( idx; (size_t)lanes.count ) {
584                        if( !is_empty(lanes.data[idx]) ) {
585                                arrive(snzi, idx);
586                        }
587                }
588        }
589
590        // Make sure that everything is consistent
591        /* paranoid */ check( cltr->ready_queue );
592
593        __cfadbg_print_safe(ready_queue, "Kernel : Shrinking ready queue done\n");
594        /* paranoid */ verify( ready_mutate_islocked() );
595}
Note: See TracBrowser for help on using the repository browser.