Changes in / [1da7397:2644610]


Ignore:
Files:
6 deleted
10 edited

Legend:

Unmodified
Added
Removed

  • doc/theses/andrew_beach_MMath/features.tex

    r1da7397 r2644610  
    22
    33This chapter covers the design and user interface of the \CFA
    4 exception-handling mechanism (EHM). % or exception system.
    5 
    6 % We should cover what is an exception handling mechanism and what is an
    7 % exception before this. Probably in the introduction. Some of this could
    8 % move there.
    9 \paragraph{Raise / Handle}
    10 An exception operation has two main parts: raise and handle.
    11 These are the two parts that the user will write themselves and so
    12 might be the only two pieces of the EHM that have any syntax.
    13 These terms are sometimes also known as throw and catch but this work uses
    14 throw/catch as a particular kind of raise/handle.
    15 
    16 \subparagraph{Raise}
    17 The raise is the starting point for exception handling and usually how
    18 Some well known examples include the throw statements of \Cpp and Java and
    19 the raise statement from Python.
    20 
    21 For this overview a raise does nothing more kick off the handling of an
    22 exception, which is called raising the exception. This is inexact but close
    23 enough for the broad strokes of the overview.
    24 
    25 \subparagraph{Handle}
    26 The purpose of most exception operations is to run some sort of handler that
    27 contains user code.
    28 The try statement of \Cpp illistrates the common features
    29 Handlers have three common features: a region of code they apply to, an
    30 exception label that describes what exceptions they handle and code to run
    31 when they handle an exception.
    32 Each handler can handle exceptions raised in that region that match their
    33 exception label. Different EHMs will have different rules to pick a handler
    34 if multipe handlers could be used such as ``best match" or ``first found".
    35 
    36 \paragraph{Propagation}
    37 After an exception is raised comes what is usually the biggest step for the
    38 EHM, finding and setting up the handler. This can be broken up into three
    39 different tasks: searching for a handler, matching against the handler and
    40 installing the handler.
    41 
    42 First the EHM must search for possible handlers that could be used to handle
    43 the exception. Searching is usually independent of the exception that was
    44 thrown and instead depends on the call stack, the current function, its caller
    45 and repeating down the stack.
    46 
    47 Second it much match the exception with each handler to see which one is the
    48 best match and hence which one should be used to handle the exception.
    49 In languages where the best match is the first match these two are often
    50 intertwined, a match check is preformed immediately after the search finds
    51 a possible handler.
    52 
    53 Third, after a handler is chosen it must be made ready to run.
    54 What this actually involves can vary widely to fit with the rest of the
    55 design of the EHM. The installation step might be trivial or it could be
    56 the most expensive step in handling an exception. The latter tends to be the
    57 case when stack unwinding is involved.
    58 
    59 As an alternate third step if no appropriate handler is found then some sort
    60 of recovery has to be preformed. This is only required with unchecked
    61 exceptions as checked exceptions can promise that a handler is found. It also
    62 is also installing a handler but it is a special default that may be
    63 installed differently.
    64 
    65 \subparagraph{Hierarchy}
    66 In \CFA the EHM uses a hierarchial system to organise its exceptions.
    67 This stratagy is borrowed from object-orientated languages where the
    68 exception hierarchy is a natural extension of the object hierarchy.
    69 
    70 Consider the following hierarchy of exceptions:
     4exception-handling mechanism.
     5
     6\section{Virtuals}
     7Virtual types and casts are not part of the exception system nor are they
     8required for an exception system. But an object-oriented style hierarchy is a
     9great way of organizing exceptions so a minimal virtual system has been added
     10to \CFA.
     11
     12The pattern of a simple hierarchy was borrowed from object-oriented
     13programming was chosen for several reasons.
     14The first is that it allows new exceptions to be added in user code
     15and in libraries independently of each other. Another is it allows for
     16different levels of exception grouping (all exceptions, all IO exceptions or
     17a particular IO exception). Also it also provides a simple way of passing
     18data back and forth across the throw.
     19
     20Virtual types and casts are not required for a basic exception-system but are
     21useful for advanced exception features. However, \CFA is not object-oriented so
     22there is no obvious concept of virtuals. Hence, to create advanced exception
     23features for this work, I needed to design and implement a virtual-like
     24system for \CFA.
     25
     26% NOTE: Maybe we should but less of the rational here.
     27Object-oriented languages often organized exceptions into a simple hierarchy,
     28\eg Java.
    7129\begin{center}
    7230\setlength{\unitlength}{4000sp}%
    … …  
    8543\end{picture}%
    8644\end{center}
    87 
    88 A handler labelled with any given exception can handle exceptions of that
    89 type or any child type of that exception. The root of the exception hierarchy
    90 (here \texttt{exception}) acts as a catch-all, leaf types catch single types
    91 and the exceptions in the middle can be used to catch different groups of
    92 related exceptions.
    93 
    94 This system has some notable advantages, such as multiple levels of grouping,
    95 the ability for libraries to add new exception types and the isolation
    96 between different sub-hierarchies. So the design was adapted for a
    97 non-object-orientated language.
    98 
    99 % Could I cite the rational for the Python IO exception rework?
    100 
    101 \paragraph{Completion}
    102 After the handler has finished the entire exception operation has to complete
    103 and continue executing somewhere else. This step is usually very simple
    104 both logically and in its implementation as the installation of the handler
    105 usually does the heavy lifting.
    106 
    107 The EHM can return control to many different places.
    108 However, the most common is after the handler definition and the next most
    109 common is after the raise.
    110 
    111 \paragraph{Communication}
    112 For effective exception handling, additional information is usually required
    113 as this base model only communicates the exception's identity. Common
    114 additional methods of communication are putting fields on an exception and
    115 allowing a handler to access the lexical scope it is defined in (usually
    116 a function's local variables).
    117 
    118 \paragraph{Other Features}
    119 Any given exception handling mechanism is free at add other features on top
    120 of this. This is an overview of the base that all EHMs use but it is not an
    121 exaustive list of everything an EHM can do.
    122 
    123 \section{Virtuals}
    124 Virtual types and casts are not part of the exception system nor are they
    125 required for an exception system. But an object-oriented style hierarchy is a
    126 great way of organizing exceptions so a minimal virtual system has been added
    127 to \CFA.
    128 
    129 The virtual system supports multiple ``trees" of types. Each tree is
    130 a simple hierarchy with a single root type. Each type in a tree has exactly
    131 one parent - except for the root type which has zero parents - and any
    132 number of children.
    133 Any type that belongs to any of these trees is called a virtual type.
    134 
    135 % A type's ancestors are its parent and its parent's ancestors.
    136 % The root type has no ancestors.
    137 % A type's decendents are its children and its children's decendents.
    138 
    139 Every virtual type also has a list of virtual members. Children inherit
    140 their parent's list of virtual members but may add new members to it.
    141 It is important to note that these are virtual members, not virtual methods.
    142 However as function pointers are allowed they can be used to mimic virtual
    143 methods as well.
    144 
    145 The unique id for the virtual type and all the virtual members are combined
    146 into a virtual table type. Each virtual type has a pointer to a virtual table
    147 as a hidden field.
    148 
    149 Up until this point the virtual system is a lot like ones found in object-
    150 orientated languages but this where they diverge. Objects encapsulate a
    151 single set of behaviours in each type, universally across the entire program,
    152 and indeed all programs that use that type definition. In this sense the
    153 types are ``closed" and cannot be altered.
    154 
    155 However in \CFA types do not encapsulate any behaviour. Traits are local and
    156 types can begin to statify a trait, stop satifying a trait or satify the same
    157 trait in a different way with each new definition. In this sense they are
    158 ``open" as they can change at any time. This means it is implossible to pick
    159 a single set of functions that repersent the type.
    160 
    161 So we don't try to have a single value. The user can define virtual tables
    162 which are filled in at their declaration and given a name. Anywhere you can
    163 see that name you can use that virtual table; even if it is defined locally
    164 inside a function, although in that case you must respect its lifetime.
    165 
    166 An object of a virtual type is ``bound" to a virtual table instance which
    167 sets the virtual members for that object. The virtual members can be accessed
    168 through the object.
     45The hierarchy provides the ability to handle an exception at different degrees
     46of specificity (left to right). Hence, it is possible to catch a more general
     47exception-type in higher-level code where the implementation details are
     48unknown, which reduces tight coupling to the lower-level implementation.
     49Otherwise, low-level code changes require higher-level code changes, \eg,
     50changing from raising @underflow@ to @overflow@ at the low level means changing
     51the matching catch at the high level versus catching the general @arithmetic@
     52exception. In detail, each virtual type may have a parent and can have any
     53number of children. A type's descendants are its children and its children's
     54descendants. A type may not be its own descendant.
     55
     56The exception hierarchy allows a handler (@catch@ clause) to match multiple
     57exceptions, \eg a base-type handler catches both base and derived
     58exception-types.
     59\begin{cfa}
     60try {
     61        ...
     62} catch(arithmetic &) {
     63        ... // handle arithmetic, underflow, overflow, zerodivide
     64}
     65\end{cfa}
     66Most exception mechanisms perform a linear search of the handlers and select
     67the first matching handler, so the order of handers is now important because
     68matching is many to one.
     69
     70Each virtual type needs an associated virtual table. A virtual table is a
     71structure with fields for all the virtual members of a type. A virtual type has
     72all the virtual members of its parent and can add more. It may also update the
     73values of the virtual members and often does.
    16974
    17075While much of the virtual infrastructure is created, it is currently only used
    … …  
    17883\Cpp syntax for special casts. Both the type of @EXPRESSION@ and @TYPE@ must be
    17984a pointer to a virtual type.
    180 The cast dynamically checks if the @EXPRESSION@ type is the same or a sub-type
     85The cast dynamically checks if the @EXPRESSION@ type is the same or a subtype
    18186of @TYPE@, and if true, returns a pointer to the
    18287@EXPRESSION@ object, otherwise it returns @0p@ (null pointer).
    … …  
    202107
    203108The function @get_exception_vtable@ is actually a constant function.
    204 Regardless of the value passed in (including the null pointer) it should
     109Recardless of the value passed in (including the null pointer) it should
    205110return a reference to the virtual table instance for that type.
    206111The reason it is a function instead of a constant is that it make type
    … …  
    234139and their use will be detailed there.
    235140
    236 However all three of these traits can be tricky to use directly.
     141However all three of these traits can be trickly to use directly.
    237142There is a bit of repetition required but
    238143the largest issue is that the virtual table type is mangled and not in a user
    … …  
    247152list will be passed to both types.
    248153In the current set-up the base name and the polymorphic arguments have to
    249 match so these macros can be used without losing flexibility.
     154match so these macros can be used without losing flexability.
    250155
    251156For example consider a function that is polymorphic over types that have a
    … …  
    280185It is dynamic, non-local goto. If a throw is successful then the stack will
    281186be unwound and control will (usually) continue in a different function on
    282 the call stack. They are commonly used when an error has occurred and recovery
     187the call stack. They are commonly used when an error has occured and recovery
    283188is impossible in the current function.
    284189
    … …  
    291196\end{cfa}
    292197The expression must return a reference to a termination exception, where the
    293 termination exception is any type that satisfies @is_termination_exception@
     198termination exception is any type that satifies @is_termination_exception@
    294199at the call site.
    295200Through \CFA's trait system the functions in the traits are passed into the
    … …  
    298203
    299204The throw will copy the provided exception into managed memory. It is the
    300 user's responsibility to ensure the original exception is cleaned up if the
     205user's responcibility to ensure the original exception is cleaned up if the
    301206stack is unwound (allocating it on the stack should be sufficient).
    302207
    … …  
    315220}
    316221\end{cfa}
    317 When viewed on its own a try statement will simply execute the statements in
     222When viewed on its own a try statement will simply exceute the statements in
    318223@GUARDED_BLOCK@ and when those are finished the try statement finishes.
    319224
    … …  
    327232Exception matching checks the representation of the thrown exception-type is
    328233the same or a descendant type of the exception types in the handler clauses. If
    329 it is the same of a descendant of @EXCEPTION_TYPE@$_i$ then @NAME@$_i$ is
     234it is the same of a descendent of @EXCEPTION_TYPE@$_i$ then @NAME@$_i$ is
    330235bound to a pointer to the exception and the statements in @HANDLER_BLOCK@$_i$
    331236are executed. If control reaches the end of the handler, the exception is
    … …  
    350255closure will be taken from up the stack and executed, after which the throwing
    351256function will continue executing.
    352 These are most often used when an error occurred and if the error is repaired
     257These are most often used when an error occured and if the error is repaired
    353258then the function can continue.
    354259
    … …  
    358263\end{cfa}
    359264The semantics of the @throwResume@ statement are like the @throw@, but the
    360 expression has return a reference a type that satisfies the trait
     265expression has return a reference a type that satifies the trait
    361266@is_resumption_exception@. The assertions from this trait are available to
    362267the exception system while handling the exception.
    363268
    364 At run-time, no copies are made. As the stack is not unwound the exception and
     269At runtime, no copies are made. As the stack is not unwound the exception and
    365270any values on the stack will remain in scope while the resumption is handled.
    366271
    … …  
    426331search and match the handler in the @catchResume@ clause. This will be
    427332call and placed on the stack on top of the try-block. The second throw then
    428 throws and will search the same try block and put call another instance of the
     333throws and will seach the same try block and put call another instance of the
    429334same handler leading to an infinite loop.
    430335
    … …  
    432337can form with multiple handlers and different exception types.
    433338
    434 To prevent all of these cases we mask sections of the stack, or equivalently
    435 the try statements on the stack, so that the resumption search skips over
     339To prevent all of these cases we mask sections of the stack, or equvilantly
     340the try statements on the stack, so that the resumption seach skips over
    436341them and continues with the next unmasked section of the stack.
    437342
    … …  
    468373The symmetry with termination is why this pattern was picked. Other patterns,
    469374such as marking just the handlers that caught, also work but lack the
    470 symmetry which means there is more to remember.
     375symmetry whih means there is more to remember.
    471376
    472377\section{Conditional Catch}
    … …  
    491396}
    492397\end{cfa}
    493 Note, catching @IOFailure@, checking for @f1@ in the handler, and re-raising the
    494 exception if not @f1@ is different because the re-raise does not examine any of
     398Note, catching @IOFailure@, checking for @f1@ in the handler, and reraising the
     399exception if not @f1@ is different because the reraise does not examine any of
    495400remaining handlers in the current try statement.
    496401
    … …  
    543448@return@ that causes control to leave the finally block. Other ways to leave
    544449the finally block, such as a long jump or termination are much harder to check,
    545 and at best requiring additional run-time overhead, and so are mealy
     450and at best requiring additional run-time overhead, and so are mearly
    546451discouraged.
    547452
    … …  
    601506this point.}
    602507
    603 The recommended way to avoid the abort is to handle the initial resumption
     508The recommended way to avoid the abort is to handle the intial resumption
    604509from the implicate join. If required you may put an explicate join inside a
    605510finally clause to disable the check and use the local

  • libcfa/src/concurrency/clib/cfathread.cfa

    r1da7397 r2644610  
    5858        this.themain = themain;
    5959        this.arg = arg;
    60         (this.self){"C-thread", cl};
     60        ((thread&)this){"C-thread", cl};
    6161        __thrd_start(this, main);
    6262}
    … …  
    102102        this.init = init;
    103103        this.arg = arg;
    104         (this.self){"Processir Init"};
     104        ((thread&)this){"Processir Init"};
    105105
    106106        // Don't use __thrd_start! just prep the context manually
    … …  
    312312
    313313        ssize_t cfathread_write(int fildes, const void *buf, size_t nbyte) {
    314                 // Use send rather then write for socket since it's faster
    315                 return cfa_send(fildes, buf, nbyte, 0, CFA_IO_LAZY);
     314                return cfa_write(fildes, buf, nbyte, CFA_IO_LAZY);
    316315        }
    317316
    … …  
    336335
    337336        ssize_t cfathread_read(int fildes, void *buf, size_t nbyte) {
    338                 // Use recv rather then read for socket since it's faster
    339                 return cfa_recv(fildes, buf, nbyte, 0, CFA_IO_LAZY);
    340         }
    341 
    342 }
     337                return cfa_read(fildes, buf, nbyte, CFA_IO_LAZY);
     338        }
     339
     340}

  • libcfa/src/concurrency/invoke.h

    r1da7397 r2644610  
    225225
    226226                static inline $thread * volatile & ?`next ( $thread * this )  __attribute__((const)) {
    227                         return this->seqable.next;
     227                        return this->seqable.back;
    228228                }
    229229

  • libcfa/src/concurrency/kernel.hfa

    r1da7397 r2644610  
    6969        // Cluster from which to get threads
    7070        struct cluster * cltr;
    71 
    72         // Id within the cluster
    73         unsigned cltr_id;
    7471
    7572        // Set to true to notify the processor should terminate

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

    r1da7397 r2644610  
    486486
    487487                // Adjust the ready queue size
    488                 this.cltr_id = ready_queue_grow( cltr, target );
     488                ready_queue_grow( cltr, target );
    489489
    490490        // Unlock the RWlock

  • libcfa/src/concurrency/kernel_private.hfa

    r1da7397 r2644610  
    278278//-----------------------------------------------------------------------
    279279// Increase the width of the ready queue (number of lanes) by 4
    280 unsigned ready_queue_grow  (struct cluster * cltr, int target);
     280void ready_queue_grow  (struct cluster * cltr, int target);
    281281
    282282//-----------------------------------------------------------------------

  • libcfa/src/concurrency/locks.hfa

    r1da7397 r2644610  
    2020
    2121#include "bits/weakso_locks.hfa"
    22 #include "containers/queueLockFree.hfa"
    23 
    24 #include "thread.hfa"
    2522
    2623#include "time_t.hfa"
    2724#include "time.hfa"
    28 
    29 //-----------------------------------------------------------------------------
    30 // Semaphores
    31 
    32 // '0-nary' semaphore
    33 // Similar to a counting semaphore except the value of one is never reached
    34 // as a consequence, a V() that would bring the value to 1 *spins* until
    35 // a P consumes it
    36 struct Semaphore0nary {
    37         __spinlock_t lock; // needed to protect
    38         mpsc_queue($thread) queue;
    39 };
    40 
    41 static inline bool P(Semaphore0nary & this, $thread * thrd) __attribute__((artificial));
    42 static inline bool P(Semaphore0nary & this, $thread * thrd) {
    43         /* paranoid */ verify(!(thrd->seqable.next));
    44         /* paranoid */ verify(!(thrd`next));
    45 
    46         push(this.queue, thrd);
    47         return true;
    48 }
    49 
    50 static inline bool P(Semaphore0nary & this) __attribute__((artificial));
    51 static inline bool P(Semaphore0nary & this) {
    52     $thread * thrd = active_thread();
    53     P(this, thrd);
    54     park();
    55     return true;
    56 }
    57 
    58 static inline $thread * V(Semaphore0nary & this, const bool doUnpark = true) __attribute__((artificial));
    59 static inline $thread * V(Semaphore0nary & this, const bool doUnpark = true) {
    60         $thread * next;
    61         lock(this.lock __cfaabi_dbg_ctx2);
    62                 for (;;) {
    63                         next = pop(this.queue);
    64                         if (next) break;
    65                         Pause();
    66                 }
    67         unlock(this.lock);
    68 
    69         if (doUnpark) unpark(next);
    70         return next;
    71 }
    72 
    73 // Wrapper used on top of any sempahore to avoid potential locking
    74 struct BinaryBenaphore {
    75         volatile ssize_t counter;
    76 };
    77 
    78 static inline {
    79         void ?{}(BinaryBenaphore & this) { this.counter = 0; }
    80         void ?{}(BinaryBenaphore & this, zero_t) { this.counter = 0; }
    81         void ?{}(BinaryBenaphore & this, one_t ) { this.counter = 1; }
    82 
    83         // returns true if no blocking needed
    84         bool P(BinaryBenaphore & this) { return __atomic_fetch_sub(&this.counter, 1, __ATOMIC_SEQ_CST) > 0; }
    85         bool tryP(BinaryBenaphore & this) {
    86                 ssize_t c = this.counter;
    87                 return (c >= 1) && __atomic_compare_exchange_n(&this.counter, &c, c-1, false, __ATOMIC_SEQ_CST, __ATOMIC_RELAXED);
    88         }
    89 
    90         // returns true if notify needed
    91         bool V(BinaryBenaphore & this) {
    92                 ssize_t c = 0;
    93                 for () {
    94                         if (__atomic_compare_exchange_n(&this.counter, &c, c+1, false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)) {
    95                                 if (c == 0) return true;
    96                                 /* paranoid */ verify(c < 0);
    97                                 return false;
    98                         } else {
    99                                 if (c == 1) return true;
    100                                 /* paranoid */ verify(c < 1);
    101                                 Pause();
    102                         }
    103                 }
    104         }
    105 }
    106 
    107 // Binary Semaphore based on the BinaryBenaphore on top of the 0-nary Semaphore
    108 struct ThreadBenaphore {
    109         BinaryBenaphore ben;
    110         Semaphore0nary  sem;
    111 };
    112 
    113 static inline void ?{}(ThreadBenaphore & this) {}
    114 static inline void ?{}(ThreadBenaphore & this, zero_t) { (this.ben){ 0 }; }
    115 static inline void ?{}(ThreadBenaphore & this, one_t ) { (this.ben){ 1 }; }
    116 
    117 static inline bool P(ThreadBenaphore & this)              { return /* P(this.ben) ? false : */ P(this.sem); }
    118 static inline bool P(ThreadBenaphore & this, $thread * t) { return /* P(this.ben) ? false : */ P(this.sem, t ); }
    119 static inline bool tryP(ThreadBenaphore & this)           { return tryP(this.ben); }
    120 static inline bool P(ThreadBenaphore & this, bool wait)   { return wait ? P(this) : tryP(this); }
    121 
    122 static inline $thread * V(ThreadBenaphore & this, const bool doUnpark = true) {
    123         // if (V(this.ben)) return 0p;
    124         return V(this.sem, doUnpark);
    125 }
    126 
    127 //-----------------------------------------------------------------------------
    128 // Semaphore
    129 struct semaphore {
    130         __spinlock_t lock;
    131         int count;
    132         __queue_t($thread) waiting;
    133 };
    134 
    135 void  ?{}(semaphore & this, int count = 1);
    136 void ^?{}(semaphore & this);
    137 bool   P (semaphore & this);
    138 bool   V (semaphore & this);
    139 bool   V (semaphore & this, unsigned count);
    14025
    14126//----------
    … …  
    16853static inline void   set_recursion_count( owner_lock & this, size_t recursion ) { set_recursion_count( (blocking_lock &)this, recursion ); }
    16954static inline size_t get_recursion_count( owner_lock & this ) { return get_recursion_count( (blocking_lock &)this ); }
    170 
    171 struct fast_lock {
    172         $thread * volatile owner;
    173         ThreadBenaphore sem;
    174 };
    175 
    176 static inline bool $try_lock(fast_lock & this, $thread * thrd) {
    177     $thread * exp = 0p;
    178     return __atomic_compare_exchange_n(&this.owner, &exp, thrd, false, __ATOMIC_SEQ_CST, __ATOMIC_RELAXED);
    179 }
    180 
    181 static inline void $lock(fast_lock & this, $thread * thrd) {
    182         /* paranoid */verify(thrd != this.owner);
    183 
    184         for (;;) {
    185                 if ($try_lock(this, thrd)) return;
    186                 P(this.sem, thrd);
    187         }
    188 }
    189 
    190 static inline void lock( fast_lock & this ) {
    191         $thread * thrd = active_thread();
    192         /* paranoid */verify(thrd != this.owner);
    193 
    194         for (;;) {
    195                 if ($try_lock(this, thrd)) return;
    196                 P(this.sem);
    197         }
    198 }
    199 
    200 static inline void try_lock ( fast_lock & this ) {
    201         $thread * thrd = active_thread();
    202         /* paranoid */ verify(thrd != this.owner);
    203         return $try_lock(this, thrd);
    204 }
    205 
    206 static inline void unlock( fast_lock & this ) {
    207         $thread * thrd = active_thread();
    208         /* paranoid */ verify(thrd == this.owner);
    209         $thread * next = V(this.sem, false); // implicit fence
    210         // open 'owner' only after fence
    211         this.owner = 0p;
    212 
    213         // Unpark the next person (can be 0p, unpark handles it)
    214         unpark(next);
    215 }
    216 
    217 static inline void on_wait( fast_lock & this ) {
    218         unlock(this);
    219         #warning this is broken
    220 }
    221 
    222 static inline void on_notify( fast_lock & this, struct $thread * t ) {
    223         $lock(this, t);
    224         #warning this is broken
    225 }
    226 
    227 static inline void   set_recursion_count( fast_lock & this, size_t recursion ) {}
    228 static inline size_t get_recursion_count( fast_lock & this ) { return 0; }
    229 
    230 struct mcs_node {
    231         mcs_node * volatile next;
    232         single_sem sem;
    233 };
    234 
    235 static inline void ?{}(mcs_node & this) { this.next = 0p; }
    236 
    237 static inline mcs_node * volatile & ?`next ( mcs_node * node ) {
    238         return node->next;
    239 }
    240 
    241 struct mcs_lock {
    242         mcs_queue(mcs_node) queue;
    243 };
    244 
    245 static inline void lock(mcs_lock & l, mcs_node & n) {
    246         if(push(l.queue, &n))
    247                 wait(n.sem);
    248 }
    249 
    250 static inline void unlock(mcs_lock & l, mcs_node & n) {
    251         mcs_node * next = advance(l.queue, &n);
    252         if(next) post(next->sem);
    253 }
    25455
    25556//-----------------------------------------------------------------------------
    … …  
    320121        bool wait( condition_variable(L) & this, L & l, uintptr_t info, Time time );
    321122}
     123
     124//-----------------------------------------------------------------------------
     125// Semaphore
     126struct semaphore {
     127        __spinlock_t lock;
     128        int count;
     129        __queue_t($thread) waiting;
     130};
     131
     132void  ?{}(semaphore & this, int count = 1);
     133void ^?{}(semaphore & this);
     134bool   P (semaphore & this);
     135bool   V (semaphore & this);
     136bool   V (semaphore & this, unsigned count);

  • libcfa/src/concurrency/ready_queue.cfa

    r1da7397 r2644610  
    3939#endif
    4040
    41 #define BIAS 4
     41#define BIAS 16
    4242
    4343// returns the maximum number of processors the RWLock support
    … …  
    252252                preferred =
    253253                        //*
    254                         kernelTLS().this_processor ? kernelTLS().this_processor->cltr_id : -1;
     254                        kernelTLS().this_processor ? kernelTLS().this_processor->id * 4 : -1;
    255255                        /*/
    256256                        thrd->link.preferred * 4;
    … …  
    330330        #if defined(BIAS)
    331331                // Don't bother trying locally too much
    332                 preferred = kernelTLS().this_processor->cltr_id;
     332                preferred = kernelTLS().this_processor->id * 4;
    333333        #endif
    334334
    … …  
    352352
    353353                #if !defined(__CFA_NO_STATISTICS__)
    354                         if(locali && localj) {
     354                        if(locali) {
     355                                __tls_stats()->ready.pick.pop.local++;
     356                        }
     357                        if(localj) {
    355358                                __tls_stats()->ready.pick.pop.local++;
    356359                        }
    … …  
    525528
    526529// Grow the ready queue
    527 unsigned ready_queue_grow(struct cluster * cltr, int target) {
    528         unsigned preferred;
    529         size_t ncount;
    530 
     530void ready_queue_grow  (struct cluster * cltr, int target) {
    531531        /* paranoid */ verify( ready_mutate_islocked() );
    532532        __cfadbg_print_safe(ready_queue, "Kernel : Growing ready queue\n");
    … …  
    543543                // Find new count
    544544                // Make sure we always have atleast 1 list
    545                 if(target >= 2) {
    546                         ncount = target * 4;
    547                         preferred = ncount - 4;
    548                 } else {
    549                         ncount = 1;
    550                         preferred = 0;
    551                 }
     545                size_t ncount = target >= 2 ? target * 4: 1;
    552546
    553547                // Allocate new array (uses realloc and memcpies the data)
    … …  
    584578
    585579        /* paranoid */ verify( ready_mutate_islocked() );
    586         return preferred;
    587580}
    588581

  • libcfa/src/containers/queueLockFree.hfa

    r1da7397 r2644610  
    2020                // Adds an element to the list
    2121                // Multi-Thread Safe, Lock-Free
    22                 T * push(mcs_queue(T) & this, T * elem) __attribute__((artificial));
    23                 T * push(mcs_queue(T) & this, T * elem) {
    24                         /* paranoid */ verify(!(elem`next));
     22                T * push(mcs_queue(T) & this, T & elem) {
     23                        /* paranoid */ verify(!(&elem)`next);
    2524                        // Race to add to the tail
    26                         T * prev = __atomic_exchange_n(&this.tail, elem, __ATOMIC_SEQ_CST);
     25                        T * prev = __atomic_exchange_n(&this.tail, &elem, __ATOMIC_SEQ_CST);
    2726                        // If we aren't the first, we need to tell the person before us
    2827                        // No need to
    29                         if (prev) prev`next = elem;
     28                        if (prev) prev`next = &elem;
    3029                        return prev;
    3130                }
    … …  
    3433                // Passing an element that is not the head is undefined behavior
    3534                // NOT Multi-Thread Safe, concurrent pushes are safe
    36                 T * advance(mcs_queue(T) & this, T * elem) __attribute__((artificial));
    37                 T * advance(mcs_queue(T) & this, T * elem) {
    38                         T * expected = elem;
     35                T * advance(mcs_queue(T) & this, T & elem) {
     36                        T * expected = &elem;
    3937                        // Check if this is already the last item
    4038                        if (__atomic_compare_exchange_n(&this.tail, &expected, 0p, false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)) return 0p;
    4139
    42                         // If not wait for next item to show-up, filled by push
    43                         while (!(elem`next)) Pause();
    44 
    45                         // we need to return if the next link was empty
    46                         T * ret = elem`next;
    47 
    48                         // invalidate link to reset to initial state
    49                         elem`next = 0p;
    50                         return ret;
     40                        // If not wait for next item to show-up
     41                        // added by push
     42                        while (!(&elem)`next) Pause();
     43                        return (&elem)`next;
    5144                }
    5245        }
    … …  
    7164                // Added a new element to the queue
    7265                // Multi-Thread Safe, Lock-Free
    73                 T * push(mpsc_queue(T) & this, T * elem) __attribute__((artificial));
    74                 T * push(mpsc_queue(T) & this, T * elem) {
     66                T * push(mpsc_queue(T) & this, T & elem) {
    7567                        T * prev = push((mcs_queue(T)&)this, elem);
    76                         if (!prev) this.head = elem;
     68                        if (!prev) this.head = &elem;
    7769                        return prev;
    7870                }
    … …  
    8274                // next is set to the new head of the queue
    8375                // NOT Multi-Thread Safe
    84                 T * pop(mpsc_queue(T) & this, T *& next) __attribute__((artificial));
    8576                T * pop(mpsc_queue(T) & this, T *& next) {
    8677                        T * elem = this.head;
    … …  
    9384                                // force memory sync
    9485                                __atomic_thread_fence(__ATOMIC_SEQ_CST);
    95 
    96                                 // invalidate link to reset to initial state
    97                                 elem`next = 0p;
    9886                        }
    9987                        // Otherwise, there might be a race where it only looks but someone is enqueuing
    … …  
    10391                                // after that point, it could overwrite the write in push
    10492                                this.head = 0p;
    105                                 next = advance((mcs_queue(T)&)this, elem);
     93                                next = advance((mcs_queue(T)&)this, (*elem));
    10694
    10795                                // Only write to the head if there is a next element
    … …  
    11098                                if (next) this.head = next;
    11199                        }
     100
     101                        // invalidate link
     102                        elem`next = 0p;
    112103
    113104                        // return removed element

  • tests/Makefile.am

    r1da7397 r2644610  
    7575        pybin/tools.py \
    7676        long_tests.hfa \
     77        .in/io.data \
    7778        io/.in/io.data \
    78         io/.in/many_read.data \
    7979        avltree/avl.h \
    8080        avltree/avl-private.h \
    8181        concurrent/clib.c \
    82         concurrent/clib_tls.c \
    8382        exceptions/with-threads.hfa \
    8483        exceptions/except-io.hfa
Note: See TracChangeset for help on using the changeset viewer.