Changes in / [d02e547:660665f]


Ignore:
Files:
7 edited

Legend:

Unmodified
Added
Removed

  • libcfa/src/bits/defs.hfa

    rd02e547 r660665f  
    3131#ifdef __cforall
    3232#define __cfa_anonymous_object(x) inline struct x
     33#define __cfa_dlink(x) inline dlink(x)
    3334#else
    3435#define __cfa_anonymous_object(x) struct x __cfa_anonymous_object
     36#define __cfa_dlink(x) struct { struct x * next; struct x * back; } __dlink_substitute
    3537#endif
    3638

  • libcfa/src/bits/weakso_locks.hfa

    rd02e547 r660665f  
    2121#include "bits/sequence.hfa"
    2222#include "bits/containers.hfa"
     23#include "containers/list.hfa"
    2324
    2425struct $thread;
    … …  
    3132
    3233        // List of blocked threads
    33         Sequence( $thread ) blocked_threads;
     34        dlist( $thread ) blocked_threads;
    3435
    3536        // Count of current blocked threads

  • libcfa/src/concurrency/invoke.h

    rd02e547 r660665f  
    2020
    2121#ifdef __cforall
     22#include "containers/list.hfa"
    2223extern "C" {
    2324#endif
    … …  
    198199                } seqable;
    199200
     201                // used to put threads on dlist data structure
     202                __cfa_dlink($thread);
     203
    200204                struct {
    201205                        struct $thread * next;
    … …  
    209213                #endif
    210214        };
     215        #ifdef __cforall
     216                P9_EMBEDDED( $thread, dlink($thread) )
     217        #endif
    211218        // Wrapper for gdb
    212219        struct cfathread_thread_t { struct $thread debug; };
    … …  
    238245
    239246                static inline $thread *& Next( $thread * this ) __attribute__((const)) {
    240                         return this->seqable.next;
     247                                return this->seqable.next;
    241248                }
    242249

  • libcfa/src/concurrency/locks.cfa

    rd02e547 r660665f  
    2828forall(L & | is_blocking_lock(L)) {
    2929        struct info_thread {
    30                 // used to put info_thread on a dl queue (aka sequence)
    31                 inline Seqable;
     30                // used to put info_thread on a dl queue
     31                inline dlink(info_thread(L));
    3232
    3333                // waiting thread
    … …  
    4343                bool signalled;
    4444        };
     45        P9_EMBEDDED( info_thread(L), dlink(info_thread(L)) )
    4546
    4647        void ?{}( info_thread(L) & this, $thread * t, uintptr_t info, L * l ) {
    47                 ((Seqable &) this){};
    4848                this.t = t;
    4949                this.info = info;
    … …  
    5252
    5353        void ^?{}( info_thread(L) & this ) {}
    54 
    55         info_thread(L) *& Back( info_thread(L) * this ) {
    56                 return (info_thread(L) *)Back( (Seqable *)this );
    57         }
    58 
    59         info_thread(L) *& Next( info_thread(L) * this ) {
    60                 return (info_thread(L) *)Next( (Colable *)this );
    61         }
    6254}
    6355
    … …  
    8678        // lock is held by some other thread
    8779        if ( owner != 0p && owner != thrd ) {
    88                 addTail( blocked_threads, *thrd );
     80                insert_last( blocked_threads, *thrd );
    8981                wait_count++;
    9082                unlock( lock );
    … …  
    125117
    126118void pop_and_set_new_owner( blocking_lock & this ) with( this ) {
    127         $thread * t = &dropHead( blocked_threads );
     119        $thread * t = &try_pop_front( blocked_threads );
    128120        owner = t;
    129121        recursion_count = ( t ? 1 : 0 );
    … …  
    154146        // lock held
    155147        if ( owner != 0p ) {
    156                 addTail( blocked_threads, *t );
     148                insert_last( blocked_threads, *t );
    157149                wait_count++;
    158150                unlock( lock );
    … …  
    207199                //      may still be called after a thread has been removed from the queue but
    208200                //      before the alarm is unregistered
    209                 if ( listed(info_thd) ) {       // is thread on queue
     201                if ( (*info_thd)`isListed ) {   // is thread on queue
    210202                        info_thd->signalled = false;
    211203                        // remove this thread O(1)
    212                         remove( cond->blocked_threads, *info_thd );
     204                        remove( *info_thd );
    213205                        cond->count--;
    214206                        if( info_thd->lock ) {
    … …  
    255247        bool notify_one( condition_variable(L) & this ) with( this ) {
    256248                lock( lock __cfaabi_dbg_ctx2 );
    257                 bool ret = !empty(blocked_threads);
    258                 process_popped(this, dropHead( blocked_threads ));
     249                bool ret = ! blocked_threads`isEmpty;
     250                process_popped(this, try_pop_front( blocked_threads ));
    259251                unlock( lock );
    260252                return ret;
    … …  
    263255        bool notify_all( condition_variable(L) & this ) with(this) {
    264256                lock( lock __cfaabi_dbg_ctx2 );
    265                 bool ret = !empty(blocked_threads);
    266                 while( !empty(blocked_threads) ) {
    267                         process_popped(this, dropHead( blocked_threads ));
     257                bool ret = ! blocked_threads`isEmpty;
     258                while( ! blocked_threads`isEmpty ) {
     259                        process_popped(this, try_pop_front( blocked_threads ));
    268260                }
    269261                unlock( lock );
    … …  
    272264
    273265        uintptr_t front( condition_variable(L) & this ) with(this) {
    274                 return empty(blocked_threads) ? NULL : head(blocked_threads).info;
     266                return blocked_threads`isEmpty ? NULL : blocked_threads`first.info;
    275267        }
    276268
    277269        bool empty( condition_variable(L) & this ) with(this) {
    278270                lock( lock __cfaabi_dbg_ctx2 );
    279                 bool ret = empty(blocked_threads);
     271                bool ret = blocked_threads`isEmpty;
    280272                unlock( lock );
    281273                return ret;
    … …  
    286278        size_t queue_and_get_recursion( condition_variable(L) & this, info_thread(L) * i ) with(this) {
    287279                // add info_thread to waiting queue
    288                 addTail( blocked_threads, *i );
     280                insert_last( blocked_threads, *i );
    289281                count++;
    290282                size_t recursion_count = 0;

  • libcfa/src/concurrency/locks.hfa

    rd02e547 r660665f  
    1818
    1919#include <stdbool.h>
     20#include <stdio.h>
    2021
    2122#include "bits/weakso_locks.hfa"
    2223#include "containers/queueLockFree.hfa"
     24#include "containers/list.hfa"
     25
    2326#include "limits.hfa"
    2427#include "thread.hfa"
    … …  
    4043
    4144static inline bool P(Semaphore0nary & this, $thread * thrd) {
    42         /* paranoid */ verify(!(thrd->seqable.next));
    43         /* paranoid */ verify(!(thrd`next));
     45        /* paranoid */ verify(!thrd`next);
     46        /* paranoid */ verify(!(&(*thrd)`next));
    4447
    4548        push(this.queue, thrd);
    … …  
    240243}
    241244
     245struct linear_backoff_then_block_lock {
     246        // Spin lock used for mutual exclusion
     247        __spinlock_t spinlock;
     248
     249        // Current thread owning the lock
     250        struct $thread * owner;
     251
     252        // List of blocked threads
     253        dlist( $thread ) blocked_threads;
     254
     255        // Used for comparing and exchanging
     256        volatile size_t lock_value;
     257
     258        // used for linear backoff spinning
     259        int spin_start;
     260        int spin_end;
     261        int spin_count;
     262
     263        // after unsuccessful linear backoff yield this many times
     264        int yield_count;
     265};
     266
     267static inline void  ?{}( linear_backoff_then_block_lock & this, int spin_start, int spin_end, int spin_count, int yield_count ) {
     268        this.spinlock{};
     269        this.blocked_threads{};
     270        this.lock_value = 0;
     271        this.spin_start = spin_start;
     272        this.spin_end = spin_end;
     273        this.spin_count = spin_count;
     274        this.yield_count = yield_count;
     275}
     276static inline void  ?{}( linear_backoff_then_block_lock & this ) { this{4, 1024, 16, 0}; }
     277static inline void ^?{}( linear_backoff_then_block_lock & this ) {}
     278
     279static inline bool internal_try_lock(linear_backoff_then_block_lock & this, size_t & compare_val) with(this) {
     280        if (__atomic_compare_exchange_n(&lock_value, &compare_val, 1, false, __ATOMIC_ACQUIRE, __ATOMIC_RELAXED)) {
     281                owner = active_thread();
     282                return true;
     283        }
     284        return false;
     285}
     286
     287static inline bool try_lock(linear_backoff_then_block_lock & this) { size_t compare_val = 0; return internal_try_lock(this, compare_val); }
     288
     289static inline bool try_lock_contention(linear_backoff_then_block_lock & this) with(this) {
     290        if (__atomic_exchange_n(&lock_value, 2, __ATOMIC_ACQUIRE) == 0) {
     291                owner = active_thread();
     292                return true;
     293        }
     294        return false;
     295}
     296
     297static inline bool block(linear_backoff_then_block_lock & this) with(this) {
     298        lock( spinlock __cfaabi_dbg_ctx2 );
     299        if (lock_value != 2) {
     300                unlock( spinlock );
     301                return true;
     302        }
     303        insert_last( blocked_threads, *active_thread() );
     304        unlock( spinlock );
     305        park( );
     306        return true;
     307}
     308
     309static inline bool lock(linear_backoff_then_block_lock & this) with(this) {
     310        // if owner just return
     311        if (active_thread() == owner) return true;
     312        size_t compare_val = 0;
     313        int spin = spin_start;
     314        // linear backoff
     315        for( ;; ) {
     316                compare_val = 0;
     317                if (internal_try_lock(this, compare_val)) return true;
     318                if (2 == compare_val) break;
     319                for (int i = 0; i < spin; i++) Pause();
     320                if (spin >= spin_end) break;
     321                spin += spin;
     322        }
     323
     324        // linear backoff bounded by spin_count
     325        spin = spin_start;
     326        int spin_counter = 0;
     327        int yield_counter = 0;
     328        for ( ;; ) {
     329                if(try_lock_contention(this)) return true;
     330                if(spin_counter < spin_count) {
     331                        for (int i = 0; i < spin; i++) Pause();
     332                        if (spin < spin_end) spin += spin;
     333                        else spin_counter++;
     334                } else if (yield_counter < yield_count) {
     335                        // after linear backoff yield yield_count times
     336                        yield_counter++;
     337                        yield();
     338                } else { break; }
     339        }
     340
     341        // block until signalled
     342        while (block(this)) if(try_lock_contention(this)) return true;
     343       
     344        // this should never be reached as block(this) always returns true
     345        return false;
     346}
     347
     348static inline void unlock(linear_backoff_then_block_lock & this) with(this) {
     349        verify(lock_value > 0);
     350    owner = 0p;
     351    if (__atomic_exchange_n(&lock_value, 0, __ATOMIC_RELEASE) == 1) return;
     352        lock( spinlock __cfaabi_dbg_ctx2 );
     353        $thread * t = &try_pop_front( blocked_threads );
     354        unlock( spinlock );
     355        unpark( t );
     356}
     357
     358
     359void on_notify(linear_backoff_then_block_lock & this, struct $thread * t ) { unpark(t); }
     360size_t on_wait(linear_backoff_then_block_lock & this) { unlock(this); return 0; }
     361void on_wakeup(linear_backoff_then_block_lock & this, size_t recursion ) { lock(this); }
     362
    242363//-----------------------------------------------------------------------------
    243364// is_blocking_lock
    … …  
    254375
    255376//-----------------------------------------------------------------------------
    256 // info_thread
    257 // the info thread is a wrapper around a thread used
    258 // to store extra data for use in the condition variable
     377// // info_thread
     378// // the info thread is a wrapper around a thread used
     379// // to store extra data for use in the condition variable
    259380forall(L & | is_blocking_lock(L)) {
    260381        struct info_thread;
    261382
    262         // for use by sequence
    263         info_thread(L) *& Back( info_thread(L) * this );
    264         info_thread(L) *& Next( info_thread(L) * this );
     383        // // for use by sequence
     384        // info_thread(L) *& Back( info_thread(L) * this );
     385        // info_thread(L) *& Next( info_thread(L) * this );
    265386}
    266387
    … …  
    273394
    274395                // List of blocked threads
    275                 Sequence( info_thread(L) ) blocked_threads;
     396                dlist( info_thread(L) ) blocked_threads;
    276397
    277398                // Count of current blocked threads
    278399                int count;
    279400        };
     401       
    280402
    281403        void  ?{}( condition_variable(L) & this );

  • tests/unified_locking/.expect/locks.txt

    rd02e547 r660665f  
    1515Start Test 8: fast lock and condition variable 3 wait/notify all
    1616Done Test 8
    17 Start Test 9: multi acquisiton lock and condition variable multiple acquire and wait/notify
     17Start Test 9: linear backoff lock and condition variable single wait/notify
    1818Done Test 9
    19 Start Test 10: owner lock and condition variable multiple acquire and wait/notify
     19Start Test 10: linear backoff lock and condition variable 3 wait/notify all
    2020Done Test 10
    21 Start Test 11: no lock condition variable wait/notify
     21Start Test 11: multi acquisiton lock and condition variable multiple acquire and wait/notify
    2222Done Test 11
    23 Start Test 12: locked condition variable wait/notify with front()
     23Start Test 12: owner lock and condition variable multiple acquire and wait/notify
    2424Done Test 12
     25Start Test 13: no lock condition variable wait/notify
     26Done Test 13
     27Start Test 14: locked condition variable wait/notify with front()
     28Done Test 14

  • tests/unified_locking/locks.cfa

    rd02e547 r660665f  
    1818condition_variable( fast_lock ) c_f;
    1919
     20linear_backoff_then_block_lock l;
     21condition_variable( linear_backoff_then_block_lock ) c_l;
     22
    2023thread T_C_M_WS1 {};
    2124
    … …  
    99102                }
    100103                unlock(f);
     104        }
     105}
     106
     107thread T_C_L_WS1 {};
     108
     109void main( T_C_L_WS1 & this ) {
     110        for (unsigned int i = 0; i < num_times; i++) {
     111                lock(l);
     112                if(empty(c_l) && i != num_times - 1) {
     113                        wait(c_l,l);
     114                }else{
     115                        notify_one(c_l);
     116                }
     117                unlock(l);
     118        }
     119}
     120
     121thread T_C_L_WB1 {};
     122
     123void main( T_C_L_WB1 & this ) {
     124        for (unsigned int i = 0; i < num_times; i++) {
     125                lock(l);
     126                if(counter(c_l) == 3 || i == num_times - 1) {
     127                        notify_all(c_l);
     128                }else{
     129                        wait(c_l,l);
     130                }
     131                unlock(l);
    101132        }
    102133}
    … …  
    298329        printf("Done Test 8\n");
    299330
    300         printf("Start Test 9: multi acquisiton lock and condition variable multiple acquire and wait/notify\n");
     331        printf("Start Test 9: linear backoff lock and condition variable single wait/notify\n");
     332        {
     333                T_C_L_WS1 t1[2];
     334        }
     335        printf("Done Test 9\n");
     336
     337        printf("Start Test 10: linear backoff lock and condition variable 3 wait/notify all\n");
     338        {
     339                T_C_L_WB1 t1[4];
     340        }
     341        printf("Done Test 10\n");
     342
     343        printf("Start Test 11: multi acquisiton lock and condition variable multiple acquire and wait/notify\n");
    301344        {
    302345                T_C_M_WS2 t1[2];
    303346        }
    304         printf("Done Test 9\n");
    305 
    306         printf("Start Test 10: owner lock and condition variable multiple acquire and wait/notify\n");
     347        printf("Done Test 11\n");
     348
     349        printf("Start Test 12: owner lock and condition variable multiple acquire and wait/notify\n");
    307350        {
    308351                T_C_O_WS2 t1[2];
    309352        }
    310         printf("Done Test 10\n");
    311 
    312         printf("Start Test 11: no lock condition variable wait/notify\n");
     353        printf("Done Test 12\n");
     354
     355        printf("Start Test 13: no lock condition variable wait/notify\n");
    313356        {
    314357                T_C_NLW t1;
    315358                T_C_NLS t2;
    316359        }
    317         printf("Done Test 11\n");
    318 
    319         printf("Start Test 12: locked condition variable wait/notify with front()\n");
     360        printf("Done Test 13\n");
     361
     362        printf("Start Test 14: locked condition variable wait/notify with front()\n");
    320363        {
    321364                T_C_S_WNF t1[2];
    322365        }
    323         printf("Done Test 12\n");
    324 
    325         // removed to limit test duration. Full test is in long run tests
    326         // printf("Start Test 11: unlocked condition variable delay wait\n");
    327         // {
    328         //      T_C_NLWD t1;
    329         //      T_C_WDS t2;
    330         // }
    331         // printf("Done Test 11\n");
    332 
    333         // printf("Start Test 12: locked condition variable delay wait with unlocked signal\n");
    334         // {
    335         //      T_C_LWD t1;
    336         //      T_C_WDS t2;
    337         // }
    338         // printf("Done Test 12\n");
    339 
    340         // printf("Start Test 13: locked condition variable delay wait with locked signal\n");
    341         // {
    342         //      T_C_LWD t1;
    343         //      T_C_LWDS t2;
    344         // }
    345         // printf("Done Test 13\n");
    346 }
     366        printf("Done Test 14\n");
     367}
Note: See TracChangeset for help on using the changeset viewer.