Changeset 1da7397
- Timestamp:
- Mar 27, 2021, 6:04:14 PM (4 years ago)
- Branches:
- ADT, arm-eh, ast-experimental, enum, forall-pointer-decay, jacob/cs343-translation, master, new-ast-unique-expr, pthread-emulation, qualifiedEnum
- Children:
- fec3e9a
- Parents:
- 2644610 (diff), f8a7fed (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. - Files:
-
- 6 added
- 10 edited
Legend:
- Unmodified
- Added
- Removed
-
doc/theses/andrew_beach_MMath/features.tex
r2644610 r1da7397 2 2 3 3 This chapter covers the design and user interface of the \CFA 4 exception-handling mechanism. 5 6 \section{Virtuals} 7 Virtual types and casts are not part of the exception system nor are they 8 required for an exception system. But an object-oriented style hierarchy is a 9 great way of organizing exceptions so a minimal virtual system has been added 10 to \CFA. 11 12 The pattern of a simple hierarchy was borrowed from object-oriented 13 programming was chosen for several reasons. 14 The first is that it allows new exceptions to be added in user code 15 and in libraries independently of each other. Another is it allows for 16 different levels of exception grouping (all exceptions, all IO exceptions or 17 a particular IO exception). Also it also provides a simple way of passing 18 data back and forth across the throw. 19 20 Virtual types and casts are not required for a basic exception-system but are 21 useful for advanced exception features. However, \CFA is not object-oriented so 22 there is no obvious concept of virtuals. Hence, to create advanced exception 23 features for this work, I needed to design and implement a virtual-like 24 system for \CFA. 25 26 % NOTE: Maybe we should but less of the rational here. 27 Object-oriented languages often organized exceptions into a simple hierarchy, 28 \eg Java. 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: 29 71 \begin{center} 30 72 \setlength{\unitlength}{4000sp}% … … 43 85 \end{picture}% 44 86 \end{center} 45 The hierarchy provides the ability to handle an exception at different degrees 46 of specificity (left to right). Hence, it is possible to catch a more general 47 exception-type in higher-level code where the implementation details are 48 unknown, which reduces tight coupling to the lower-level implementation. 49 Otherwise, low-level code changes require higher-level code changes, \eg, 50 changing from raising @underflow@ to @overflow@ at the low level means changing 51 the matching catch at the high level versus catching the general @arithmetic@ 52 exception. In detail, each virtual type may have a parent and can have any 53 number of children. A type's descendants are its children and its children's 54 descendants. A type may not be its own descendant. 55 56 The exception hierarchy allows a handler (@catch@ clause) to match multiple 57 exceptions, \eg a base-type handler catches both base and derived 58 exception-types. 59 \begin{cfa} 60 try { 61 ... 62 } catch(arithmetic &) { 63 ... // handle arithmetic, underflow, overflow, zerodivide 64 } 65 \end{cfa} 66 Most exception mechanisms perform a linear search of the handlers and select 67 the first matching handler, so the order of handers is now important because 68 matching is many to one. 69 70 Each virtual type needs an associated virtual table. A virtual table is a 71 structure with fields for all the virtual members of a type. A virtual type has 72 all the virtual members of its parent and can add more. It may also update the 73 values of the virtual members and often does. 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. 74 169 75 170 While much of the virtual infrastructure is created, it is currently only used … … 83 178 \Cpp syntax for special casts. Both the type of @EXPRESSION@ and @TYPE@ must be 84 179 a pointer to a virtual type. 85 The cast dynamically checks if the @EXPRESSION@ type is the same or a sub type180 The cast dynamically checks if the @EXPRESSION@ type is the same or a sub-type 86 181 of @TYPE@, and if true, returns a pointer to the 87 182 @EXPRESSION@ object, otherwise it returns @0p@ (null pointer). … … 107 202 108 203 The function @get_exception_vtable@ is actually a constant function. 109 Re cardless of the value passed in (including the null pointer) it should204 Regardless of the value passed in (including the null pointer) it should 110 205 return a reference to the virtual table instance for that type. 111 206 The reason it is a function instead of a constant is that it make type … … 139 234 and their use will be detailed there. 140 235 141 However all three of these traits can be trick ly to use directly.236 However all three of these traits can be tricky to use directly. 142 237 There is a bit of repetition required but 143 238 the largest issue is that the virtual table type is mangled and not in a user … … 152 247 list will be passed to both types. 153 248 In the current set-up the base name and the polymorphic arguments have to 154 match so these macros can be used without losing flex ability.249 match so these macros can be used without losing flexibility. 155 250 156 251 For example consider a function that is polymorphic over types that have a … … 185 280 It is dynamic, non-local goto. If a throw is successful then the stack will 186 281 be unwound and control will (usually) continue in a different function on 187 the call stack. They are commonly used when an error has occur ed and recovery282 the call stack. They are commonly used when an error has occurred and recovery 188 283 is impossible in the current function. 189 284 … … 196 291 \end{cfa} 197 292 The expression must return a reference to a termination exception, where the 198 termination exception is any type that sati fies @is_termination_exception@293 termination exception is any type that satisfies @is_termination_exception@ 199 294 at the call site. 200 295 Through \CFA's trait system the functions in the traits are passed into the … … 203 298 204 299 The throw will copy the provided exception into managed memory. It is the 205 user's respon cibility to ensure the original exception is cleaned up if the300 user's responsibility to ensure the original exception is cleaned up if the 206 301 stack is unwound (allocating it on the stack should be sufficient). 207 302 … … 220 315 } 221 316 \end{cfa} 222 When viewed on its own a try statement will simply ex ceute the statements in317 When viewed on its own a try statement will simply execute the statements in 223 318 @GUARDED_BLOCK@ and when those are finished the try statement finishes. 224 319 … … 232 327 Exception matching checks the representation of the thrown exception-type is 233 328 the same or a descendant type of the exception types in the handler clauses. If 234 it is the same of a descend ent of @EXCEPTION_TYPE@$_i$ then @NAME@$_i$ is329 it is the same of a descendant of @EXCEPTION_TYPE@$_i$ then @NAME@$_i$ is 235 330 bound to a pointer to the exception and the statements in @HANDLER_BLOCK@$_i$ 236 331 are executed. If control reaches the end of the handler, the exception is … … 255 350 closure will be taken from up the stack and executed, after which the throwing 256 351 function will continue executing. 257 These are most often used when an error occur ed and if the error is repaired352 These are most often used when an error occurred and if the error is repaired 258 353 then the function can continue. 259 354 … … 263 358 \end{cfa} 264 359 The semantics of the @throwResume@ statement are like the @throw@, but the 265 expression has return a reference a type that sati fies the trait360 expression has return a reference a type that satisfies the trait 266 361 @is_resumption_exception@. The assertions from this trait are available to 267 362 the exception system while handling the exception. 268 363 269 At run time, no copies are made. As the stack is not unwound the exception and364 At run-time, no copies are made. As the stack is not unwound the exception and 270 365 any values on the stack will remain in scope while the resumption is handled. 271 366 … … 331 426 search and match the handler in the @catchResume@ clause. This will be 332 427 call and placed on the stack on top of the try-block. The second throw then 333 throws and will sea ch the same try block and put call another instance of the428 throws and will search the same try block and put call another instance of the 334 429 same handler leading to an infinite loop. 335 430 … … 337 432 can form with multiple handlers and different exception types. 338 433 339 To prevent all of these cases we mask sections of the stack, or equ vilantly340 the try statements on the stack, so that the resumption sea ch skips over434 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 341 436 them and continues with the next unmasked section of the stack. 342 437 … … 373 468 The symmetry with termination is why this pattern was picked. Other patterns, 374 469 such as marking just the handlers that caught, also work but lack the 375 symmetry whi h means there is more to remember.470 symmetry which means there is more to remember. 376 471 377 472 \section{Conditional Catch} … … 396 491 } 397 492 \end{cfa} 398 Note, catching @IOFailure@, checking for @f1@ in the handler, and re raising the399 exception if not @f1@ is different because the re raise does not examine any of493 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 400 495 remaining handlers in the current try statement. 401 496 … … 448 543 @return@ that causes control to leave the finally block. Other ways to leave 449 544 the finally block, such as a long jump or termination are much harder to check, 450 and at best requiring additional run-time overhead, and so are mea rly545 and at best requiring additional run-time overhead, and so are mealy 451 546 discouraged. 452 547 … … 506 601 this point.} 507 602 508 The recommended way to avoid the abort is to handle the in tial resumption603 The recommended way to avoid the abort is to handle the initial resumption 509 604 from the implicate join. If required you may put an explicate join inside a 510 605 finally clause to disable the check and use the local -
libcfa/src/concurrency/clib/cfathread.cfa
r2644610 r1da7397 58 58 this.themain = themain; 59 59 this.arg = arg; 60 ( (thread&)this){"C-thread", cl};60 (this.self){"C-thread", cl}; 61 61 __thrd_start(this, main); 62 62 } … … 102 102 this.init = init; 103 103 this.arg = arg; 104 ( (thread&)this){"Processir Init"};104 (this.self){"Processir Init"}; 105 105 106 106 // Don't use __thrd_start! just prep the context manually … … 312 312 313 313 ssize_t cfathread_write(int fildes, const void *buf, size_t nbyte) { 314 return cfa_write(fildes, buf, nbyte, CFA_IO_LAZY); 314 // Use send rather then write for socket since it's faster 315 return cfa_send(fildes, buf, nbyte, 0, CFA_IO_LAZY); 315 316 } 316 317 … … 335 336 336 337 ssize_t cfathread_read(int fildes, void *buf, size_t nbyte) { 337 return cfa_read(fildes, buf, nbyte, CFA_IO_LAZY); 338 } 339 340 } 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 } -
libcfa/src/concurrency/invoke.h
r2644610 r1da7397 225 225 226 226 static inline $thread * volatile & ?`next ( $thread * this ) __attribute__((const)) { 227 return this->seqable. back;227 return this->seqable.next; 228 228 } 229 229 -
libcfa/src/concurrency/kernel.hfa
r2644610 r1da7397 69 69 // Cluster from which to get threads 70 70 struct cluster * cltr; 71 72 // Id within the cluster 73 unsigned cltr_id; 71 74 72 75 // Set to true to notify the processor should terminate -
libcfa/src/concurrency/kernel/startup.cfa
r2644610 r1da7397 486 486 487 487 // Adjust the ready queue size 488 ready_queue_grow( cltr, target );488 this.cltr_id = ready_queue_grow( cltr, target ); 489 489 490 490 // Unlock the RWlock -
libcfa/src/concurrency/kernel_private.hfa
r2644610 r1da7397 278 278 //----------------------------------------------------------------------- 279 279 // Increase the width of the ready queue (number of lanes) by 4 280 void ready_queue_grow (struct cluster * cltr, int target);280 unsigned ready_queue_grow (struct cluster * cltr, int target); 281 281 282 282 //----------------------------------------------------------------------- -
libcfa/src/concurrency/locks.hfa
r2644610 r1da7397 20 20 21 21 #include "bits/weakso_locks.hfa" 22 #include "containers/queueLockFree.hfa" 23 24 #include "thread.hfa" 22 25 23 26 #include "time_t.hfa" 24 27 #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); 25 140 26 141 //---------- … … 54 169 static inline size_t get_recursion_count( owner_lock & this ) { return get_recursion_count( (blocking_lock &)this ); } 55 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 } 254 56 255 //----------------------------------------------------------------------------- 57 256 // is_blocking_lock … … 121 320 bool wait( condition_variable(L) & this, L & l, uintptr_t info, Time time ); 122 321 } 123 124 //-----------------------------------------------------------------------------125 // Semaphore126 struct semaphore {127 __spinlock_t lock;128 int count;129 __queue_t($thread) waiting;130 };131 132 void ?{}(semaphore & this, int count = 1);133 void ^?{}(semaphore & this);134 bool P (semaphore & this);135 bool V (semaphore & this);136 bool V (semaphore & this, unsigned count); -
libcfa/src/concurrency/ready_queue.cfa
r2644610 r1da7397 39 39 #endif 40 40 41 #define BIAS 1641 #define BIAS 4 42 42 43 43 // returns the maximum number of processors the RWLock support … … 252 252 preferred = 253 253 //* 254 kernelTLS().this_processor ? kernelTLS().this_processor-> id * 4: -1;254 kernelTLS().this_processor ? kernelTLS().this_processor->cltr_id : -1; 255 255 /*/ 256 256 thrd->link.preferred * 4; … … 330 330 #if defined(BIAS) 331 331 // Don't bother trying locally too much 332 preferred = kernelTLS().this_processor-> id * 4;332 preferred = kernelTLS().this_processor->cltr_id; 333 333 #endif 334 334 … … 352 352 353 353 #if !defined(__CFA_NO_STATISTICS__) 354 if(locali) { 355 __tls_stats()->ready.pick.pop.local++; 356 } 357 if(localj) { 354 if(locali && localj) { 358 355 __tls_stats()->ready.pick.pop.local++; 359 356 } … … 528 525 529 526 // Grow the ready queue 530 void ready_queue_grow (struct cluster * cltr, int target) { 527 unsigned ready_queue_grow(struct cluster * cltr, int target) { 528 unsigned preferred; 529 size_t ncount; 530 531 531 /* paranoid */ verify( ready_mutate_islocked() ); 532 532 __cfadbg_print_safe(ready_queue, "Kernel : Growing ready queue\n"); … … 543 543 // Find new count 544 544 // Make sure we always have atleast 1 list 545 size_t ncount = target >= 2 ? target * 4: 1; 545 if(target >= 2) { 546 ncount = target * 4; 547 preferred = ncount - 4; 548 } else { 549 ncount = 1; 550 preferred = 0; 551 } 546 552 547 553 // Allocate new array (uses realloc and memcpies the data) … … 578 584 579 585 /* paranoid */ verify( ready_mutate_islocked() ); 586 return preferred; 580 587 } 581 588 -
libcfa/src/containers/queueLockFree.hfa
r2644610 r1da7397 20 20 // Adds an element to the list 21 21 // Multi-Thread Safe, Lock-Free 22 T * push(mcs_queue(T) & this, T & elem) { 23 /* paranoid */ verify(!(&elem)`next); 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)); 24 25 // Race to add to the tail 25 T * prev = __atomic_exchange_n(&this.tail, &elem, __ATOMIC_SEQ_CST);26 T * prev = __atomic_exchange_n(&this.tail, elem, __ATOMIC_SEQ_CST); 26 27 // If we aren't the first, we need to tell the person before us 27 28 // No need to 28 if (prev) prev`next = &elem;29 if (prev) prev`next = elem; 29 30 return prev; 30 31 } … … 33 34 // Passing an element that is not the head is undefined behavior 34 35 // NOT Multi-Thread Safe, concurrent pushes are safe 35 T * advance(mcs_queue(T) & this, T & elem) { 36 T * expected = &elem; 36 T * advance(mcs_queue(T) & this, T * elem) __attribute__((artificial)); 37 T * advance(mcs_queue(T) & this, T * elem) { 38 T * expected = elem; 37 39 // Check if this is already the last item 38 40 if (__atomic_compare_exchange_n(&this.tail, &expected, 0p, false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)) return 0p; 39 41 40 // If not wait for next item to show-up 41 // added by push 42 while (!(&elem)`next) Pause(); 43 return (&elem)`next; 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; 44 51 } 45 52 } … … 64 71 // Added a new element to the queue 65 72 // Multi-Thread Safe, Lock-Free 66 T * push(mpsc_queue(T) & this, T & elem) { 73 T * push(mpsc_queue(T) & this, T * elem) __attribute__((artificial)); 74 T * push(mpsc_queue(T) & this, T * elem) { 67 75 T * prev = push((mcs_queue(T)&)this, elem); 68 if (!prev) this.head = &elem;76 if (!prev) this.head = elem; 69 77 return prev; 70 78 } … … 74 82 // next is set to the new head of the queue 75 83 // NOT Multi-Thread Safe 84 T * pop(mpsc_queue(T) & this, T *& next) __attribute__((artificial)); 76 85 T * pop(mpsc_queue(T) & this, T *& next) { 77 86 T * elem = this.head; … … 84 93 // force memory sync 85 94 __atomic_thread_fence(__ATOMIC_SEQ_CST); 95 96 // invalidate link to reset to initial state 97 elem`next = 0p; 86 98 } 87 99 // Otherwise, there might be a race where it only looks but someone is enqueuing … … 91 103 // after that point, it could overwrite the write in push 92 104 this.head = 0p; 93 next = advance((mcs_queue(T)&)this, (*elem));105 next = advance((mcs_queue(T)&)this, elem); 94 106 95 107 // Only write to the head if there is a next element … … 98 110 if (next) this.head = next; 99 111 } 100 101 // invalidate link102 elem`next = 0p;103 112 104 113 // return removed element -
tests/Makefile.am
r2644610 r1da7397 75 75 pybin/tools.py \ 76 76 long_tests.hfa \ 77 .in/io.data \78 77 io/.in/io.data \ 78 io/.in/many_read.data \ 79 79 avltree/avl.h \ 80 80 avltree/avl-private.h \ 81 81 concurrent/clib.c \ 82 concurrent/clib_tls.c \ 82 83 exceptions/with-threads.hfa \ 83 84 exceptions/except-io.hfa
Note: See TracChangeset
for help on using the changeset viewer.