Changeset c0c940a


Ignore:
Timestamp:
May 4, 2021, 12:25:36 PM (3 years ago)
Author:
Peter A. Buhr <pabuhr@…>
Branches:
ADT, arm-eh, ast-experimental, enum, forall-pointer-decay, jacob/cs343-translation, master, new-ast-unique-expr, pthread-emulation, qualifiedEnum
Children:
1716e1c, 58c671ba, 78a6b9c
Parents:
692f0c8 (diff), 9fa538c (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.
Message:

fix conflicit

Files:
9 edited
2 moved

Legend:

Unmodified
Added
Removed

  • doc/theses/andrew_beach_MMath/cfalab.sty

    r692f0c8 rc0c940a  
    11% Package for CFA Research Lab.
    22%
    3 % Made by combining and updating various macro files people had made.
     3% This is a collection of commands everyone working on CFA related documents
     4% should find useful. So mostly programming language related tools.
    45%
    56% Internal commands are prefixed with "\cfalab@".
    … …  
    1718% Automatically adds spaces.
    1819\RequirePackage{xspace}
    19 % Improved reference tools.
    20 \RequirePackage[nospace]{varioref}
    2120
    22 % Symbols: All symbols are zero argument robust commands with special rules
    23 % about the space following the c.s. token. Normally the space might be
    24 % re-added according to the rules of the xspace package. They may be followed
    25 % by a star (which the command will consume) to disable this behaviour.
    26 
    27 % \newsymbolcmd{<command>}{<replacement text>}
    28 % Defines <command> to be a symbol that has the given <replacement text>.
    29 \newrobustcmd*\newsymbolcmd[2]{\newrobustcmd{#1}{\cfalab@symbol{#2}}}
    30 \def\cfalab@symbol#1{\@ifnextchar*{#1\cfalab@eatstar}{#1\xspace}}
    31 \def\cfalab@eatstar*{}
    32 
     21% Tip for commands that end with \xspace: if the default is not correct then
     22% follow the command with {} to disable \xspace, use '{} ' to force add a
     23% space and '{}<whatever-follows>' to force remove one.
     24%
    3325% Cforall with the forall symbol.
    34 \newsymbolcmd\CFA{\textsf{C}\raisebox{\depth}{\rotatebox{180}{\textsf{A}}}}
    35 % C++ with kerning. (No standard number support.)
    36 \newsymbolcmd\Cpp{\textrm{C}\kern-.1em\hbox{+\kern-.25em+}}
     26\newrobustcmd\CFA{\textsf{C\raisebox{\depth}{\rotatebox{180}{A}}}\xspace}
     27% C++ with kerning. You may optionally append a standard number.
     28\newrobustcmd\Cpp[1][\xspace]{C++#1}
    3729
    3830% This is executed very early in the \begin{document} code, before the

  • doc/theses/andrew_beach_MMath/uw-ethesis.tex

    r692f0c8 rc0c940a  
    9999% allow global and individual modification of spacing
    100100\usepackage{enumitem}
     101% Improved reference tools.
     102\usepackage[nospace]{varioref}
    101103
    102104% Hyperlinks make it very easy to navigate an electronic document.

  • libcfa/src/concurrency/invoke.h

    r692f0c8 rc0c940a  
    146146        struct __thread_desc_link {
    147147                struct $thread * next;
    148                 struct $thread * prev;
    149148                volatile unsigned long long ts;
    150                 unsigned preferred;
    151149        };
    152150
    … …  
    155153                // context that is switch during a __cfactx_switch
    156154                struct __stack_context_t context;
     155
     156                // Link lists fields
     157                // instrusive link field for threads
     158                struct __thread_desc_link link;
    157159
    158160                // current execution status for coroutine
    … …  
    170172                struct cluster * curr_cluster;
    171173
    172                 // Link lists fields
    173                 // instrusive link field for threads
    174                 struct __thread_desc_link link;
     174                // preferred ready-queue
     175                unsigned preferred;
    175176
    176177                // coroutine body used to store context

  • libcfa/src/concurrency/kernel.cfa

    r692f0c8 rc0c940a  
    184184                MAIN_LOOP:
    185185                for() {
     186                        #if 1
    186187                        // Check if there is pending io
    187188                        __maybe_io_drain( this );
    … …  
    270271                        }
    271272
    272                 //      SEARCH: {
    273                 //              /* paranoid */ verify( ! __preemption_enabled() );
    274                 //              /* paranoid */ verify( kernelTLS().this_proc_id );
    275 
    276                 //              // First, lock the scheduler since we are searching for a thread
    277 
    278                 //              // Try to get the next thread
    279                 //              ready_schedule_lock();
    280                 //              readyThread = pop_fast( this->cltr );
    281                 //              ready_schedule_unlock();
    282                 //              if(readyThread) {  break SEARCH; }
    283 
    284                 //              // If we can't find a thread, might as well flush any outstanding I/O
    285                 //              if(this->io.pending) { __cfa_io_flush( this ); }
    286 
    287                 //              // Spin a little on I/O, just in case
    288                 //              for(25) {
    289                 //                      __maybe_io_drain( this );
    290                 //                      ready_schedule_lock();
    291                 //                      readyThread = pop_fast( this->cltr );
    292                 //                      ready_schedule_unlock();
    293                 //                      if(readyThread) {  break SEARCH; }
    294                 //              }
    295 
    296                 //              // no luck, try stealing a few times
    297                 //              for(25) {
    298                 //                      if( __maybe_io_drain( this ) ) {
    299                 //                              ready_schedule_lock();
    300                 //                              readyThread = pop_fast( this->cltr );
    301                 //                      } else {
    302                 //                              ready_schedule_lock();
    303                 //                              readyThread = pop_slow( this->cltr );
    304                 //                      }
    305                 //                      ready_schedule_unlock();
    306                 //                      if(readyThread) {  break SEARCH; }
    307                 //              }
    308 
    309                 //              // still no luck, search for a thread
    310                 //              ready_schedule_lock();
    311                 //              readyThread = pop_search( this->cltr );
    312                 //              ready_schedule_unlock();
    313                 //              if(readyThread) { break SEARCH; }
    314 
    315                 //              // Don't block if we are done
    316                 //              if( __atomic_load_n(&this->do_terminate, __ATOMIC_SEQ_CST) ) break MAIN_LOOP;
    317 
    318                 //              __STATS( __tls_stats()->ready.sleep.halts++; )
    319 
    320                 //              // Push self to idle stack
    321                 //              mark_idle(this->cltr->procs, * this);
    322 
    323                 //              // Confirm the ready-queue is empty
    324                 //              __maybe_io_drain( this );
    325                 //              ready_schedule_lock();
    326                 //              readyThread = pop_search( this->cltr );
    327                 //              ready_schedule_unlock();
    328 
    329                 //              if( readyThread ) {
    330                 //                      // A thread was found, cancel the halt
    331                 //                      mark_awake(this->cltr->procs, * this);
    332 
    333                 //                      __STATS( __tls_stats()->ready.sleep.cancels++; )
    334 
    335                 //                      // continue the main loop
    336                 //                      break SEARCH;
    337                 //              }
    338 
    339                 //              __STATS( if(this->print_halts) __cfaabi_bits_print_safe( STDOUT_FILENO, "PH:%d - %lld 0\n", this->id, rdtscl()); )
    340                 //              __cfadbg_print_safe(runtime_core, "Kernel : core %p waiting on eventfd %d\n", this, this->idle);
    341 
    342                 //              // __disable_interrupts_hard();
    343                 //              eventfd_t val;
    344                 //              eventfd_read( this->idle, &val );
    345                 //              // __enable_interrupts_hard();
    346 
    347                 //              __STATS( if(this->print_halts) __cfaabi_bits_print_safe( STDOUT_FILENO, "PH:%d - %lld 1\n", this->id, rdtscl()); )
    348 
    349                 //              // We were woken up, remove self from idle
    350                 //              mark_awake(this->cltr->procs, * this);
    351 
    352                 //              // DON'T just proceed, start looking again
    353                 //              continue MAIN_LOOP;
    354                 //      }
    355 
    356                 // RUN_THREAD:
    357                 //      /* paranoid */ verify( kernelTLS().this_proc_id );
    358                 //      /* paranoid */ verify( ! __preemption_enabled() );
    359                 //      /* paranoid */ verify( readyThread );
    360 
    361                 //      // Reset io dirty bit
    362                 //      this->io.dirty = false;
    363 
    364                 //      // We found a thread run it
    365                 //      __run_thread(this, readyThread);
    366 
    367                 //      // Are we done?
    368                 //      if( __atomic_load_n(&this->do_terminate, __ATOMIC_SEQ_CST) ) break MAIN_LOOP;
    369 
    370                 //      #if !defined(__CFA_NO_STATISTICS__)
    371                 //              unsigned long long curr = rdtscl();
    372                 //              if(curr > (last_tally + 500000000)) {
    373                 //                      __tally_stats(this->cltr->stats, __cfaabi_tls.this_stats);
    374                 //                      last_tally = curr;
    375                 //              }
    376                 //      #endif
    377 
    378                 //      if(this->io.pending && !this->io.dirty) {
    379                 //              __cfa_io_flush( this );
    380                 //      }
    381 
    382                 //      // Check if there is pending io
    383                 //      __maybe_io_drain( this );
     273                        #else
     274
     275                        SEARCH: {
     276                                /* paranoid */ verify( ! __preemption_enabled() );
     277                                /* paranoid */ verify( kernelTLS().this_proc_id );
     278
     279                                // First, lock the scheduler since we are searching for a thread
     280                                ready_schedule_lock();
     281
     282                                // Try to get the next thread
     283                                readyThread = pop_fast( this->cltr );
     284                                if(readyThread) { ready_schedule_unlock(); break SEARCH; }
     285
     286                                // If we can't find a thread, might as well flush any outstanding I/O
     287                                if(this->io.pending) { __cfa_io_flush( this ); }
     288
     289                                // Spin a little on I/O, just in case
     290                                for(25) {
     291                                        __maybe_io_drain( this );
     292                                        readyThread = pop_fast( this->cltr );
     293                                        if(readyThread) { ready_schedule_unlock(); break SEARCH; }
     294                                }
     295
     296                                // no luck, try stealing a few times
     297                                for(25) {
     298                                        if( __maybe_io_drain( this ) ) {
     299                                                readyThread = pop_fast( this->cltr );
     300                                        } else {
     301                                                readyThread = pop_slow( this->cltr );
     302                                        }
     303                                        if(readyThread) { ready_schedule_unlock(); break SEARCH; }
     304                                }
     305
     306                                // still no luck, search for a thread
     307                                readyThread = pop_search( this->cltr );
     308                                if(readyThread) { ready_schedule_unlock(); break SEARCH; }
     309
     310                                // Don't block if we are done
     311                                if( __atomic_load_n(&this->do_terminate, __ATOMIC_SEQ_CST) ) break MAIN_LOOP;
     312
     313                                __STATS( __tls_stats()->ready.sleep.halts++; )
     314
     315                                // Push self to idle stack
     316                                ready_schedule_unlock();
     317                                mark_idle(this->cltr->procs, * this);
     318                                ready_schedule_lock();
     319
     320                                // Confirm the ready-queue is empty
     321                                __maybe_io_drain( this );
     322                                readyThread = pop_search( this->cltr );
     323                                ready_schedule_unlock();
     324
     325                                if( readyThread ) {
     326                                        // A thread was found, cancel the halt
     327                                        mark_awake(this->cltr->procs, * this);
     328
     329                                        __STATS( __tls_stats()->ready.sleep.cancels++; )
     330
     331                                        // continue the main loop
     332                                        break SEARCH;
     333                                }
     334
     335                                __STATS( if(this->print_halts) __cfaabi_bits_print_safe( STDOUT_FILENO, "PH:%d - %lld 0\n", this->id, rdtscl()); )
     336                                __cfadbg_print_safe(runtime_core, "Kernel : core %p waiting on eventfd %d\n", this, this->idle);
     337
     338                                // __disable_interrupts_hard();
     339                                eventfd_t val;
     340                                eventfd_read( this->idle, &val );
     341                                // __enable_interrupts_hard();
     342
     343                                __STATS( if(this->print_halts) __cfaabi_bits_print_safe( STDOUT_FILENO, "PH:%d - %lld 1\n", this->id, rdtscl()); )
     344
     345                                // We were woken up, remove self from idle
     346                                mark_awake(this->cltr->procs, * this);
     347
     348                                // DON'T just proceed, start looking again
     349                                continue MAIN_LOOP;
     350                        }
     351
     352                RUN_THREAD:
     353                        /* paranoid */ verify( kernelTLS().this_proc_id );
     354                        /* paranoid */ verify( ! __preemption_enabled() );
     355                        /* paranoid */ verify( readyThread );
     356
     357                        // Reset io dirty bit
     358                        this->io.dirty = false;
     359
     360                        // We found a thread run it
     361                        __run_thread(this, readyThread);
     362
     363                        // Are we done?
     364                        if( __atomic_load_n(&this->do_terminate, __ATOMIC_SEQ_CST) ) break MAIN_LOOP;
     365
     366                        #if !defined(__CFA_NO_STATISTICS__)
     367                                unsigned long long curr = rdtscl();
     368                                if(curr > (last_tally + 500000000)) {
     369                                        __tally_stats(this->cltr->stats, __cfaabi_tls.this_stats);
     370                                        last_tally = curr;
     371                                }
     372                        #endif
     373
     374                        if(this->io.pending && !this->io.dirty) {
     375                                __cfa_io_flush( this );
     376                        }
     377
     378                        ready_schedule_lock();
     379                        __maybe_io_drain( this );
     380                        ready_schedule_unlock();
     381                        #endif
    384382                }
    385383

  • libcfa/src/concurrency/kernel/startup.cfa

    r692f0c8 rc0c940a  
    461461        self_mon_p = &self_mon;
    462462        link.next = 0p;
    463         link.prev = 0p;
    464         link.preferred = -1u;
     463        link.ts   = 0;
     464        preferred = -1u;
    465465        last_proc = 0p;
    466466        #if defined( __CFA_WITH_VERIFY__ )

  • libcfa/src/concurrency/ready_queue.cfa

    r692f0c8 rc0c940a  
    1717// #define __CFA_DEBUG_PRINT_READY_QUEUE__
    1818
    19 // #define USE_MPSC
    2019
    2120#define USE_RELAXED_FIFO
    … …  
    256255                /* paranoid */ verify(external || kernelTLS().this_processor->rdq.id < lanes.count );
    257256
    258                 // write timestamp
    259                 thrd->link.ts = rdtscl();
    260 
    261257                bool local;
    262258                int preferred = external ? -1 : kernelTLS().this_processor->rdq.id;
    … …  
    277273                        #endif
    278274
    279                 #if defined(USE_MPSC)
    280                         // mpsc always succeeds
    281                 } while( false );
    282                 #else
    283275                        // If we can't lock it retry
    284276                } while( !__atomic_try_acquire( &lanes.data[i].lock ) );
    285                 #endif
    286277
    287278                // Actually push it
    288279                push(lanes.data[i], thrd);
    289280
    290                 #if !defined(USE_MPSC)
    291281                        // Unlock and return
    292282                        __atomic_unlock( &lanes.data[i].lock );
    293                 #endif
    294283
    295284                // Mark the current index in the tls rng instance as having an item
    … …  
    350339                __cfadbg_print_safe(ready_queue, "Kernel : Pushing %p on cluster %p\n", thrd, cltr);
    351340
     341                // #define USE_PREFERRED
     342                #if !defined(USE_PREFERRED)
    352343                const bool external = (!kernelTLS().this_processor) || (cltr != kernelTLS().this_processor->cltr);
    353344                /* paranoid */ verify(external || kernelTLS().this_processor->rdq.id < lanes.count );
    354 
    355                 // write timestamp
    356                 thrd->link.ts = rdtscl();
     345                #else
     346                        unsigned preferred = thrd->preferred;
     347                        const bool external = (!kernelTLS().this_processor) || preferred == -1u || thrd->curr_cluster != cltr;
     348                        /* paranoid */ verifyf(external || preferred < lanes.count, "Invalid preferred queue %u for %u lanes", preferred, lanes.count );
     349
     350                        unsigned r = preferred % READYQ_SHARD_FACTOR;
     351                        const unsigned start = preferred - r;
     352                #endif
    357353
    358354                // Try to pick a lane and lock it
    … …  
    368364                        }
    369365                        else {
     366                                #if !defined(USE_PREFERRED)
    370367                                processor * proc = kernelTLS().this_processor;
    371368                                unsigned r = proc->rdq.its++;
    372369                                i =  proc->rdq.id + (r % READYQ_SHARD_FACTOR);
     370                #else
     371                                        i = start + (r++ % READYQ_SHARD_FACTOR);
     372                                #endif
    373373                        }
    374 
    375 
    376                 #if defined(USE_MPSC)
    377                         // mpsc always succeeds
    378                 } while( false );
    379                 #else
    380374                        // If we can't lock it retry
    381375                } while( !__atomic_try_acquire( &lanes.data[i].lock ) );
    382                 #endif
    383376
    384377                // Actually push it
    385378                push(lanes.data[i], thrd);
    386379
    387                 #if !defined(USE_MPSC)
    388380                        // Unlock and return
    389381                        __atomic_unlock( &lanes.data[i].lock );
    390                 #endif
    391382
    392383                #if !defined(__CFA_NO_STATISTICS__)
    … …  
    492483                lanes.tscs[w].tv = thrd->link.ts;
    493484        #endif
     485
     486        thrd->preferred = w;
    494487
    495488        // return the popped thread
    … …  
    519512// Check that all the intrusive queues in the data structure are still consistent
    520513static void check( __ready_queue_t & q ) with (q) {
    521         #if defined(__CFA_WITH_VERIFY__) && !defined(USE_MPSC)
     514        #if defined(__CFA_WITH_VERIFY__)
    522515                {
    523516                        for( idx ; lanes.count ) {
    … …  
    525518                                assert(!lanes.data[idx].lock);
    526519
    527                                 assert(head(sl)->link.prev == 0p );
    528                                 assert(head(sl)->link.next->link.prev == head(sl) );
    529                                 assert(tail(sl)->link.next == 0p );
    530                                 assert(tail(sl)->link.prev->link.next == tail(sl) );
    531 
    532                                 if(is_empty(sl)) {
    533                                         assert(tail(sl)->link.prev == head(sl));
    534                                         assert(head(sl)->link.next == tail(sl));
    535                                 } else {
    536                                         assert(tail(sl)->link.prev != head(sl));
    537                                         assert(head(sl)->link.next != tail(sl));
    538                                 }
     520                                        if(is_empty(sl)) {
     521                                                assert( sl.anchor.next == 0p );
     522                                                assert( sl.anchor.ts   == 0  );
     523                                                assert( mock_head(sl)  == sl.prev );
     524                                        } else {
     525                                                assert( sl.anchor.next != 0p );
     526                                                assert( sl.anchor.ts   != 0  );
     527                                                assert( mock_head(sl)  != sl.prev );
     528                                        }
    539529                        }
    540530                }
    … …  
    557547// fixes the list so that the pointers back to anchors aren't left dangling
    558548static inline void fix(__intrusive_lane_t & ll) {
    559         #if !defined(USE_MPSC)
    560                 // if the list is not empty then follow he pointer and fix its reverse
    561                 if(!is_empty(ll)) {
    562                         head(ll)->link.next->link.prev = head(ll);
    563                         tail(ll)->link.prev->link.next = tail(ll);
    564                 }
    565                 // Otherwise just reset the list
    566                 else {
    567                         verify(tail(ll)->link.next == 0p);
    568                         tail(ll)->link.prev = head(ll);
    569                         head(ll)->link.next = tail(ll);
    570                         verify(head(ll)->link.prev == 0p);
    571                 }
    572         #endif
     549                        if(is_empty(ll)) {
     550                                verify(ll.anchor.next == 0p);
     551                                ll.prev = mock_head(ll);
     552                        }
    573553}
    574554

  • libcfa/src/concurrency/ready_subqueue.hfa

    r692f0c8 rc0c940a  
    77// Intrusives lanes which are used by the relaxed ready queue
    88struct __attribute__((aligned(128))) __intrusive_lane_t {
    9 
    10         #if defined(USE_MPSC)
    11                 mpsc_queue($thread) queue;
    12                 __attribute__((aligned(128)))
    13         #else
    14                 // anchor for the head and the tail of the queue
    15                 __attribute__((aligned(128))) struct __sentinel_t {
    16                         // Link lists fields
    17                         // instrusive link field for threads
    18                         // must be exactly as in $thread
    19                         __thread_desc_link link;
    20                 } before, after;
    21         #endif
     9        struct $thread * prev;
    2210
    2311        // spin lock protecting the queue
    2412        volatile bool lock;
    2513
    26         // Optional statistic counters
    27         #if !defined(__CFA_NO_SCHED_STATS__)
    28                 struct __attribute__((aligned(64))) {
    29                         // difference between number of push and pops
    30                         ssize_t diff;
    31 
    32                         // total number of pushes and pops
    33                         size_t  push;
    34                         size_t  pop ;
    35                 } stat;
    36         #endif
     14        __thread_desc_link anchor;
    3715};
    3816
    39 void  ?{}(__intrusive_lane_t & this);
    40 void ^?{}(__intrusive_lane_t & this);
    41 
    4217// Get the head pointer (one before the first element) from the anchor
    43 static inline $thread * head(const __intrusive_lane_t & this) {
    44         #if defined(USE_MPSC)
    45                 return this.queue.head;
    46         #else
    47                 $thread * rhead = ($thread *)(
    48                         (uintptr_t)( &this.before ) - offsetof( $thread, link )
    49                 );
    50                 /* paranoid */ verify(rhead);
    51                 return rhead;
    52         #endif
    53 }
    54 
    55 // Get the tail pointer (one after the last element) from the anchor
    56 static inline $thread * tail(const __intrusive_lane_t & this) {
    57         #if defined(USE_MPSC)
    58                 return this.queue.tail;
    59         #else
    60                 $thread * rtail = ($thread *)(
    61                         (uintptr_t)( &this.after ) - offsetof( $thread, link )
    62                 );
    63                 /* paranoid */ verify(rtail);
    64                 return rtail;
    65         #endif
     18static inline $thread * mock_head(const __intrusive_lane_t & this) {
     19        $thread * rhead = ($thread *)(
     20                (uintptr_t)( &this.anchor ) - __builtin_offsetof( $thread, link )
     21        );
     22        return rhead;
    6623}
    6724
    … …  
    6926void ?{}( __intrusive_lane_t & this ) {
    7027        this.lock = false;
     28        this.prev = mock_head(this);
     29        this.anchor.next = 0p;
     30        this.anchor.ts   = 0;
    7131
    72         #if !defined(USE_MPSC)
    73                 this.before.link.prev = 0p;
    74                 this.before.link.next = tail(this);
    75                 this.before.link.ts   = 0;
    76 
    77                 this.after .link.prev = head(this);
    78                 this.after .link.next = 0p;
    79                 this.after .link.ts   = 0;
    80 
    81                 #if !defined(__CFA_NO_SCHED_STATS__)
    82                         this.stat.diff = 0;
    83                         this.stat.push = 0;
    84                         this.stat.pop  = 0;
    85                 #endif
    86 
    87                 // We add a boat-load of assertions here because the anchor code is very fragile
    88                 /* paranoid */ verify(((uintptr_t)( head(this) ) + offsetof( $thread, link )) == (uintptr_t)(&this.before));
    89                 /* paranoid */ verify(((uintptr_t)( tail(this) ) + offsetof( $thread, link )) == (uintptr_t)(&this.after ));
    90                 /* paranoid */ verify(head(this)->link.prev == 0p );
    91                 /* paranoid */ verify(head(this)->link.next == tail(this) );
    92                 /* paranoid */ verify(tail(this)->link.next == 0p );
    93                 /* paranoid */ verify(tail(this)->link.prev == head(this) );
    94                 /* paranoid */ verify(&head(this)->link.prev == &this.before.link.prev );
    95                 /* paranoid */ verify(&head(this)->link.next == &this.before.link.next );
    96                 /* paranoid */ verify(&tail(this)->link.prev == &this.after .link.prev );
    97                 /* paranoid */ verify(&tail(this)->link.next == &this.after .link.next );
    98                 /* paranoid */ verify(__alignof__(__intrusive_lane_t) == 128);
    99                 /* paranoid */ verify(__alignof__(this) == 128);
    100                 /* paranoid */ verifyf(((intptr_t)(&this) % 128) == 0, "Expected address to be aligned %p %% 128 == %zd", &this, ((intptr_t)(&this) % 128));
    101         #endif
     32        // We add a boat-load of assertions here because the anchor code is very fragile
     33        /* paranoid */ verify( offsetof( $thread, link ) == offsetof(__intrusive_lane_t, anchor) );
     34        /* paranoid */ verify( ((uintptr_t)( mock_head(this) ) + offsetof( $thread, link )) == (uintptr_t)(&this.anchor) );
     35        /* paranoid */ verify( &mock_head(this)->link.next == &this.anchor.next );
     36        /* paranoid */ verify( &mock_head(this)->link.ts   == &this.anchor.ts   );
     37        /* paranoid */ verify( mock_head(this)->link.next == 0p );
     38        /* paranoid */ verify( mock_head(this)->link.ts   == 0  );
     39        /* paranoid */ verify( mock_head(this) == this.prev );
     40        /* paranoid */ verify( __alignof__(__intrusive_lane_t) == 128 );
     41        /* paranoid */ verify( __alignof__(this) == 128 );
     42        /* paranoid */ verifyf( ((intptr_t)(&this) % 128) == 0, "Expected address to be aligned %p %% 128 == %zd", &this, ((intptr_t)(&this) % 128) );
    10243}
    10344
    10445// Dtor is trivial
    10546void ^?{}( __intrusive_lane_t & this ) {
    106         #if !defined(USE_MPSC)
    107                 // Make sure the list is empty
    108                 /* paranoid */ verify(head(this)->link.prev == 0p );
    109                 /* paranoid */ verify(head(this)->link.next == tail(this) );
    110                 /* paranoid */ verify(tail(this)->link.next == 0p );
    111                 /* paranoid */ verify(tail(this)->link.prev == head(this) );
    112         #endif
     47        // Make sure the list is empty
     48        /* paranoid */ verify( this.anchor.next == 0p );
     49        /* paranoid */ verify( this.anchor.ts   == 0  );
     50        /* paranoid */ verify( mock_head(this)  == this.prev );
    11351}
    11452
    11553// Push a thread onto this lane
    11654// returns true of lane was empty before push, false otherwise
    117 bool push(__intrusive_lane_t & this, $thread * node) {
    118         #if defined(USE_MPSC)
    119                 inline $thread * volatile & ?`next ( $thread * this )  __attribute__((const)) {
    120                         return this->link.next;
    121                 }
    122                 push(this.queue, node);
    123         #else
    124                 #if defined(__CFA_WITH_VERIFY__)
    125                         /* paranoid */ verify(this.lock);
    126                         /* paranoid */ verify(node->link.ts != 0);
    127                         /* paranoid */ verify(node->link.next == 0p);
    128                         /* paranoid */ verify(node->link.prev == 0p);
    129                         /* paranoid */ verify(tail(this)->link.next == 0p);
    130                         /* paranoid */ verify(head(this)->link.prev == 0p);
     55void push( __intrusive_lane_t & this, $thread * node ) {
     56        /* paranoid */ verify( node->link.next == 0p );
     57        /* paranoid */ verify( node->link.ts   == 0  );
     58        /* paranoid */ verify( this.prev->link.next == 0p );
     59        /* paranoid */ verify( this.prev->link.ts   == 0  );
     60        if( this.anchor.next == 0p ) {
     61                /* paranoid */ verify( this.anchor.next == 0p );
     62                /* paranoid */ verify( this.anchor.ts   == 0  );
     63                /* paranoid */ verify( this.prev == mock_head( this ) );
     64        } else {
     65                /* paranoid */ verify( this.anchor.next != 0p );
     66                /* paranoid */ verify( this.anchor.ts   != 0  );
     67                /* paranoid */ verify( this.prev != mock_head( this ) );
     68        }
    13169
    132                         if(this.before.link.ts == 0l) {
    133                                 /* paranoid */ verify(tail(this)->link.prev == head(this));
    134                                 /* paranoid */ verify(head(this)->link.next == tail(this));
    135                         } else {
    136                                 /* paranoid */ verify(tail(this)->link.prev != head(this));
    137                                 /* paranoid */ verify(head(this)->link.next != tail(this));
    138                         }
    139                 #endif
    140 
    141                 // Get the relevant nodes locally
    142                 $thread * tail = tail(this);
    143                 $thread * prev = tail->link.prev;
    144 
    145                 // Do the push
    146                 node->link.next = tail;
    147                 node->link.prev = prev;
    148                 prev->link.next = node;
    149                 tail->link.prev = node;
    150 
    151                 // Update stats
    152                 #if !defined(__CFA_NO_SCHED_STATS__)
    153                         this.stat.diff++;
    154                         this.stat.push++;
    155                 #endif
    156 
    157                 verify(node->link.next == tail(this));
    158 
    159                 // Check if the queue used to be empty
    160                 if(this.before.link.ts == 0l) {
    161                         this.before.link.ts = node->link.ts;
    162                         /* paranoid */ verify(node->link.prev == head(this));
    163                         return true;
    164                 }
    165                 return false;
    166         #endif
     70        // Get the relevant nodes locally
     71        this.prev->link.next = node;
     72        this.prev->link.ts   = rdtscl();
     73        this.prev = node;
    16774}
    16875
    … …  
    17077// returns popped
    17178// returns true of lane was empty before push, false otherwise
    172 $thread * pop(__intrusive_lane_t & this) {
    173         /* paranoid */ verify(this.lock);
    174         #if defined(USE_MPSC)
    175                 inline $thread * volatile & ?`next ( $thread * this )  __attribute__((const)) {
    176                         return this->link.next;
    177                 }
    178                 return pop(this.queue);
    179         #else
    180                 /* paranoid */ verify(this.before.link.ts != 0ul);
     79$thread * pop( __intrusive_lane_t & this ) {
     80        /* paranoid */ verify( this.anchor.next != 0p );
     81        /* paranoid */ verify( this.anchor.ts   != 0  );
    18182
    182                 // Get anchors locally
    183                 $thread * head = head(this);
    184                 $thread * tail = tail(this);
     83        // Get the relevant nodes locally
     84        $thread * node = this.anchor.next;
     85        this.anchor.next = node->link.next;
     86        this.anchor.ts   = node->link.ts;
     87        bool is_empty = this.anchor.ts == 0;
     88        node->link.next = 0p;
     89        node->link.ts   = 0;
    18590
    186                 // Get the relevant nodes locally
    187                 $thread * node = head->link.next;
    188                 $thread * next = node->link.next;
     91        // Update head time stamp
     92        if(is_empty) this.prev = mock_head( this );
    18993
    190                 /* paranoid */ verify(node != tail);
    191                 /* paranoid */ verify(node);
    192 
    193                 // Do the pop
    194                 head->link.next = next;
    195                 next->link.prev = head;
    196                 node->link.next = 0p;
    197                 node->link.prev = 0p;
    198 
    199                 // Update head time stamp
    200                 this.before.link.ts = next->link.ts;
    201 
    202                 // Update stats
    203                 #ifndef __CFA_NO_SCHED_STATS__
    204                         this.stat.diff--;
    205                         this.stat.pop ++;
    206                 #endif
    207 
    208                 // Check if we emptied list and return accordingly
    209                 /* paranoid */ verify(tail(this)->link.next == 0p);
    210                 /* paranoid */ verify(head(this)->link.prev == 0p);
    211                 if(next == tail) {
    212                         /* paranoid */ verify(this.before.link.ts == 0);
    213                         /* paranoid */ verify(tail(this)->link.prev == head(this));
    214                         /* paranoid */ verify(head(this)->link.next == tail(this));
    215                         return node;
    216                 }
    217                 else {
    218                         /* paranoid */ verify(next->link.ts != 0);
    219                         /* paranoid */ verify(tail(this)->link.prev != head(this));
    220                         /* paranoid */ verify(head(this)->link.next != tail(this));
    221                         /* paranoid */ verify(this.before.link.ts != 0);
    222                         return node;
    223                 }
    224         #endif
     94        /* paranoid */ verify( node->link.next == 0p );
     95        /* paranoid */ verify( node->link.ts   == 0  );
     96        return node;
    22597}
    22698
    22799// Check whether or not list is empty
    228100static inline bool is_empty(__intrusive_lane_t & this) {
    229         #if defined(USE_MPSC)
    230                 return this.queue.head == 0p;
    231         #else
    232                 // Cannot verify here since it may not be locked
    233                 return this.before.link.ts == 0;
    234         #endif
     101        return this.anchor.ts == 0;
    235102}
    236103
    237104// Return the timestamp
    238105static inline unsigned long long ts(__intrusive_lane_t & this) {
    239         #if defined(USE_MPSC)
    240                 $thread * tl = this.queue.head;
    241                 if(!tl) return -1ull;
    242                 return tl->link.ts;
    243         #else
    244                 // Cannot verify here since it may not be locked
    245                 return this.before.link.ts;
    246         #endif
     106        // Cannot verify here since it may not be locked
     107        return this.anchor.ts;
    247108}
    248109

  • libcfa/src/concurrency/thread.cfa

    r692f0c8 rc0c940a  
    3838        curr_cluster = &cl;
    3939        link.next = 0p;
    40         link.prev = 0p;
    41         link.preferred = -1u;
     40        link.ts   = 0;
     41        preferred = -1u;
    4242        last_proc = 0p;
    4343        #if defined( __CFA_WITH_VERIFY__ )

  • libcfa/src/containers/array.hfa

    r692f0c8 rc0c940a  
    2121    };
    2222
    23     Timmed & ?[?]( arpk(N, S, Timmed, Tbase) & a, ptrdiff_t i ) {
     23    // About the choice of integral types offered as subscript overloads:
     24    // Intent is to cover these use cases:
     25    //    float foo( ptrdiff_t i ) { return a[i]; }           // i : ptrdiff_t
     26    //    forall( [N] ) ... for( i; N ) { total += a[i]; }    // i : typeof( sizeof(42) )
     27    //    for( i; 5 ) { total += a[i]; }                      // i : int
     28    // It gets complicated by:
     29    // -  CFA does overloading on concrete types, like int and unsigned int, not on typedefed
     30    //    types like size_t.  So trying to overload on ptrdiff_t vs int works in 64-bit mode
     31    //    but not in 32-bit mode.
     32    // -  Given bug of Trac #247, CFA gives sizeof expressions type unsigned long int, when it
     33    //    should give them type size_t.
     34    //   
     35    //                          gcc -m32         cfa -m32 given bug         gcc -m64
     36    // ptrdiff_t                int              int                        long int
     37    // size_t                   unsigned int     unsigned int               unsigned long int
     38    // typeof( sizeof(42) )     unsigned int     unsigned long int          unsigned long int
     39    // int                      int              int                        int
     40
     41    static inline Timmed & ?[?]( arpk(N, S, Timmed, Tbase) & a, int i ) {
    2442        return (Timmed &) a.strides[i];
    2543    }
    2644
    27     Timmed & ?[?]( arpk(N, S, Timmed, Tbase) & a, int i ) {
     45    static inline Timmed & ?[?]( arpk(N, S, Timmed, Tbase) & a, unsigned int i ) {
    2846        return (Timmed &) a.strides[i];
    2947    }
    3048
    31     Timmed & ?[?]( arpk(N, S, Timmed, Tbase) & a, size_t i ) {
     49    static inline Timmed & ?[?]( arpk(N, S, Timmed, Tbase) & a, long int i ) {
    3250        return (Timmed &) a.strides[i];
    3351    }
    3452
    35     size_t ?`len( arpk(N, S, Timmed, Tbase) & a ) {
     53    static inline Timmed & ?[?]( arpk(N, S, Timmed, Tbase) & a, unsigned long int i ) {
     54        return (Timmed &) a.strides[i];
     55    }
     56
     57    static inline size_t ?`len( arpk(N, S, Timmed, Tbase) & a ) {
    3658        return z(N);
    3759    }
    3860
    3961    // workaround #226 (and array relevance thereof demonstrated in mike102/otype-slow-ndims.cfa)
    40     void ?{}( arpk(N, S, Timmed, Tbase) & this ) {
     62    static inline void ?{}( arpk(N, S, Timmed, Tbase) & this ) {
    4163        void ?{}( S (&inner)[z(N)] ) {}
    4264        ?{}(this.strides);
    4365    }
    44     void ^?{}( arpk(N, S, Timmed, Tbase) & this ) {
     66    static inline void ^?{}( arpk(N, S, Timmed, Tbase) & this ) {
    4567        void ^?{}( S (&inner)[z(N)] ) {}
    4668        ^?{}(this.strides);
    … …  
    5375
    5476forall( Te )
    55 Te mkar_( tag(Te) ) {}
     77static inline Te mkar_( tag(Te) ) {}
    5678
    5779forall( [N], ZTags ... , Trslt &, Tatom & | { Trslt mkar_( tag(Tatom), ZTags ); } )
    58 arpk(N, Trslt, Trslt, Tatom) mkar_( tag(Tatom), tag(N), ZTags ) {}
     80static inline arpk(N, Trslt, Trslt, Tatom) mkar_( tag(Tatom), tag(N), ZTags ) {}
    5981
    6082// based on https://stackoverflow.com/questions/1872220/is-it-possible-to-iterate-over-arguments-in-variadic-macros
    … …  
    90112
    91113forall( TA &, TB &, TC &, IxAB, IxBC ... | { TB & ?[?]( TA &, IxAB ); TC & ?[?]( TB &, IxBC ); } )
    92 TC & ?[?]( TA & this, IxAB ab, IxBC bc ) {
     114static inline TC & ?[?]( TA & this, IxAB ab, IxBC bc ) {
    93115    return this[ab][bc];
    94116}
    … …  
    99121
    100122forall( TA &, TB &, TC &, IxAB_0, IxBC | { TB & ?[?]( TA &, IxAB_0 ); TC & ?[?]( TB &, IxBC ); } )
    101 TC & ?[?]( TA & this, IxAB_0 ab, IxBC bc ) {
     123static inline TC & ?[?]( TA & this, IxAB_0 ab, IxBC bc ) {
    102124    return this[ab][bc];
    103125}
    104126
    105127forall( TA &, TB &, TC &, IxAB_0, IxAB_1, IxBC | { TB & ?[?]( TA &, IxAB_0, IxAB_1 ); TC & ?[?]( TB &, IxBC ); } )
    106 TC & ?[?]( TA & this, IxAB_0 ab0, IxAB_1 ab1, IxBC bc ) {
     128static inline TC & ?[?]( TA & this, IxAB_0 ab0, IxAB_1 ab1, IxBC bc ) {
    107129    return this[[ab0,ab1]][bc];
    108130}
    109131
    110132forall( TA &, TB &, TC &, IxAB_0, IxAB_1, IxAB_2, IxBC | { TB & ?[?]( TA &, IxAB_0, IxAB_1, IxAB_2 ); TC & ?[?]( TB &, IxBC ); } )
    111 TC & ?[?]( TA & this, IxAB_0 ab0, IxAB_1 ab1, IxAB_2 ab2, IxBC bc ) {
     133static inline TC & ?[?]( TA & this, IxAB_0 ab0, IxAB_1 ab1, IxAB_2 ab2, IxBC bc ) {
    112134    return this[[ab0,ab1,ab2]][bc];
    113135}
    … …  
    121143// Base
    122144forall( [Nq], [Sq], Tbase & )
    123 tag(arpk(Nq, Sq, Tbase, Tbase)) enq_( tag(Tbase), tag(Nq), tag(Sq), tag(Tbase) ) {}
     145static inline tag(arpk(Nq, Sq, Tbase, Tbase)) enq_( tag(Tbase), tag(Nq), tag(Sq), tag(Tbase) ) {}
    124146
    125147// Rec
    126148forall( [Nq], [Sq], [N], [S], recq &, recr &, Tbase & | { tag(recr) enq_( tag(Tbase), tag(Nq), tag(Sq), tag(recq) ); } )
    127 tag(arpk(N, S, recr, Tbase)) enq_( tag(Tbase), tag(Nq), tag(Sq), tag(arpk(N, S, recq, Tbase)) ) {}
     149static inline tag(arpk(N, S, recr, Tbase)) enq_( tag(Tbase), tag(Nq), tag(Sq), tag(arpk(N, S, recq, Tbase)) ) {}
    128150
    129151// Wrapper
    130152struct all_t {} all;
    131153forall( [N], [S], Te &, result &, Tbase & | { tag(result) enq_( tag(Tbase), tag(N), tag(S), tag(Te) ); } )
    132 result & ?[?]( arpk(N, S, Te, Tbase) & this, all_t ) {
     154static inline result & ?[?]( arpk(N, S, Te, Tbase) & this, all_t ) {
    133155    return (result&) this;
    134156}
Note: See TracChangeset for help on using the changeset viewer.