Changes in / [a76da32:1717b12]


Ignore:
Files:
6 edited

Legend:

Unmodified
Added
Removed

  • doc/theses/andrew_beach_MMath/implement.tex

    ra76da32 r1717b12  
    1313library.
    1414
    15 \subsection{Virtual Type}
    16 Virtual types only have one change to their structure, the addition of a
    17 pointer to the virtual table. This is always the first field so that
    18 if it is cast to a supertype the field's location is still known.
    19 
    20 This field is set as part of all new generated constructors.
    21 \todo{They only come as part exceptions and don't work.}
    22 After the object is created the field is constant.
    23 
    24 However it can be read from, internally it is just a regular field called
    25 @virtual_table@. Dereferencing it gives the virtual table and access to the
    26 type's virtual members.
    27 
    2815\subsection{Virtual Table}
    29 Every time a virtual type is defined the new virtual table type must also be
    30 defined.
    31 
    32 The unique instance is important because the address of the virtual table
    33 instance is used as the identifier for the virtual type. So a pointer to the
    34 virtual table and the ID for the virtual type are interchangable.
    35 \todo{Unique instances might be going so we will have to talk about the new
    36 system instead.}
    37 
    38 The first step in putting it all together is to create the virtual table type.
    39 The virtual table type is just a structure and can be described in terms of
    40 its fields. The first field is always the parent type ID (or a pointer to
    41 the parent virtual table) or 0 (the null pointer).
    42 Next are other fields on the parent virtual table are repeated.
    43 Finally are the fields used to store any new virtual members of the new
    44 The virtual type
    45 
    4616The virtual system is accessed through a private constant field inserted at the
    4717beginning of every virtual type, called the virtual-table pointer. This field
    4818points at a type's virtual table and is assigned during the object's
    49 construction. The address of a virtual table acts as the unique identifier for
     19construction.  The address of a virtual table acts as the unique identifier for
    5020the virtual type, and the first field of a virtual table is a pointer to the
    51 parent virtual-table or @0p@. The remaining fields are duplicated from the
     21parent virtual-table or @0p@.  The remaining fields are duplicated from the
    5222parent tables in this type's inheritance chain, followed by any fields this type
    53 introduces. Parent fields are duplicated so they can be changed (all virtual
    54 members are overridable), so that references to the dispatched type
     23introduces. Parent fields are duplicated so they can be changed (\CC
     24\lstinline[language=c++]|override|), so that references to the dispatched type
    5525are replaced with the current virtual type.
     26\PAB{Can you create a simple diagram of the layout?}
    5627% These are always taken by pointer or reference.
    57 
    58 % Simple ascii diragram:
    59 \begin{verbatim}
    60 parent_pointer  \
    61 parent_field0   |
    62 ...             | Same layout as parent.
    63 parent_fieldN   /
    64 child_field0
    65 ...
    66 child_fieldN
    67 \end{verbatim}
    68 \todo{Refine the diagram}
    6928
    7029% For each virtual type, a virtual table is constructed. This is both a new type
    … …  
    7534A virtual table is created when the virtual type is created. The name of the
    7635type is created by mangling the name of the base type. The name of the instance
    77 is also generated by name mangling. The fields are initialized automatically.
     36is also generated by name mangling.  The fields are initialized automatically.
    7837The parent field is initialized by getting the type of the parent field and
    7938using that to calculate the mangled name of the parent's virtual table type.
    … …  
    10867\begin{sloppypar}
    10968Coroutines and threads need instances of @CoroutineCancelled@ and
    110 @ThreadCancelled@ respectively to use all of their functionality. When a new
     69@ThreadCancelled@ respectively to use all of their functionality.  When a new
    11170data type is declared with @coroutine@ or @thread@ the forward declaration for
    11271the instance is created as well. The definition of the virtual table is created
    … …  
    12180The function is
    12281\begin{cfa}
    123 void * __cfa__virtual_cast(
    124         struct __cfa__parent_vtable const * parent,
     82void * __cfa__virtual_cast( struct __cfa__parent_vtable const * parent,
    12583        struct __cfa__parent_vtable const * const * child );
     84}
    12685\end{cfa}
    127 and it is implemented in the standard library. The structure reperents the
    128 head of a vtable which is the pointer to the parent virtual table. The
    129 @parent@ points directly at the parent type virtual table while the @child@
    130 points at the object of the (possibe) child type.
    131 
    132 In terms of the virtual cast expression, @parent@ comes from looking up the
    133 type being cast to and @child@ is the result of the expression being cast.
    134 Because the complier outputs C code, some type C type casts are also used.
    135 The last bit of glue is an map that saves every virtual type the compiler
    136 sees. This is used to check the type used in a virtual cast is a virtual
    137 type and to get its virtual table.
    138 (It also checks for conflicting definitions.)
    139 
    140 Inside the function it is a simple conditional. If the type repersented by
    141 @parent@ is or is an ancestor of the type repersented by @*child@ (it
    142 requires one more level of derefence to pass through the object) then @child@
    143 is returned, otherwise the null pointer is returned.
    144 
    145 The check itself is preformed is a simple linear search. If the child
    146 virtual table or any of its ancestors (which are retreved through the first
    147 field of every virtual table) are the same as the parent virtual table then
    148 the cast succeeds.
     86and it is implemented in the standard library. It takes a pointer to the target
     87type's virtual table and the object pointer being cast. The function performs a
     88linear search starting at the object's virtual-table and walking through the
     89the parent pointers, checking to if it or any of its ancestors are the same as
     90the target-type virtual table-pointer.
     91
     92For the generated code, a forward declaration of the virtual works as follows.
     93There is a forward declaration of @__cfa__virtual_cast@ in every \CFA file so
     94it can just be used. The object argument is the expression being cast so that
     95is just placed in the argument list.
     96
     97To build the target type parameter, the compiler creates a mapping from
     98concrete type-name -- so for polymorphic types the parameters are filled in --
     99to virtual table address. Every virtual table declaration is added to the this
     100table; repeats are ignored unless they have conflicting definitions.  Note,
     101these declarations do not have to be in scope, but they should usually be
     102introduced as part of the type definition.
     103
     104\PAB{I do not understood all of \VRef{s:VirtualSystem}. I think you need to
     105write more to make it clear.}
     106
    149107
    150108\section{Exceptions}
    … …  
    163121stack. On function entry and return, unwinding is handled directly by the code
    164122embedded in the function. Usually, the stack-frame size is known statically
    165 based on parameter and local variable declarations. For dynamically-sized
     123based on parameter and local variable declarations.  For dynamically-sized
    166124local variables, a runtime computation is necessary to know the frame
    167125size. Finally, a function's frame-size may change during execution as local
    … …  
    221179
    222180To use libunwind, each function must have a personality function and a Language
    223 Specific Data Area (LSDA). The LSDA has the unique information for each
     181Specific Data Area (LSDA).  The LSDA has the unique information for each
    224182function to tell the personality function where a function is executing, its
    225 current stack frame, and what handlers should be checked. Theoretically, the
     183current stack frame, and what handlers should be checked.  Theoretically, the
    226184LSDA can contain any information but conventionally it is a table with entries
    227185representing regions of the function and what has to be done there during
    … …  
    238196
    239197The GCC compilation flag @-fexceptions@ causes the generation of an LSDA and
    240 attaches its personality function. However, this
    241 flag only handles the cleanup attribute:
    242 \todo{Peter: What is attached? Andrew: It uses the .cfi\_personality directive
    243 and that's all I know.}
     198attaches its personality function. \PAB{to what is it attached?}  However, this
     199flag only handles the cleanup attribute
    244200\begin{cfa}
    245201void clean_up( int * var ) { ... }
    246 int avar __attribute__(( cleanup(clean_up) ));
     202int avar __attribute__(( __cleanup(clean_up) ));
    247203\end{cfa}
    248 which is used on a variable and specifies a function, in this case @clean_up@,
    249 run when the variable goes out of scope.
    250 The function is passed a pointer to the object being removed from the stack
    251 so it can be used to mimic destructors.
    252 However, this feature cannot be used to mimic @try@ statements as it cannot
    253 control the unwinding.
     204which is used on a variable and specifies a function, \eg @clean_up@, run when
     205the variable goes out of scope. The function is passed a pointer to the object
     206so it can be used to mimic destructors. However, this feature cannot be used to
     207mimic @try@ statements.
    254208
    255209\subsection{Personality Functions}
    256 Personality functions have a complex interface specified by libunwind. This
     210Personality functions have a complex interface specified by libunwind.  This
    257211section covers some of the important parts of the interface.
    258212
    259 A personality function can preform different actions depending on how it is
    260 called.
     213A personality function performs four tasks, although not all have to be
     214present.
    261215\begin{lstlisting}[language=C,{moredelim=**[is][\color{red}]{@}{@}}]
    262216typedef _Unwind_Reason_Code (*@_Unwind_Personality_Fn@) (
    … …  
    271225\item
    272226@_UA_SEARCH_PHASE@ specifies a search phase and tells the personality function
    273 to check for handlers. If there is a handler in a stack frame, as defined by
     227to check for handlers.  If there is a handler in a stack frame, as defined by
    274228the language, the personality function returns @_URC_HANDLER_FOUND@; otherwise
    275229it return @_URC_CONTINUE_UNWIND@.
    … …  
    342296\end{cfa}
    343297It also unwinds the stack but it does not use the search phase. Instead another
    344 function, the stop function, is used to stop searching. The exception is the
     298function, the stop function, is used to stop searching.  The exception is the
    345299same as the one passed to raise exception. The extra arguments are the stop
    346300function and the stop parameter. The stop function has a similar interface as a
    … …  
    364318
    365319\begin{sloppypar}
    366 Its arguments are the same as the paired personality function. The actions
     320Its arguments are the same as the paired personality function.  The actions
    367321@_UA_CLEANUP_PHASE@ and @_UA_FORCE_UNWIND@ are always set when it is
    368322called. Beyond the libunwind standard, both GCC and Clang add an extra action
    … …  
    389343strong symbol replacing the sequential version.
    390344
    391 The sequential @this_exception_context@ returns a hard-coded pointer to the
    392 global execption context.
    393 The concurrent version adds the exception context to the data stored at the
    394 base of each stack. When @this_exception_context@ is called it retrieves the
    395 active stack and returns the address of the context saved there.
     345% The version of the function defined in @libcfa@ is very simple. It returns a
     346% pointer to a global static variable. With only one stack this global instance
     347% is associated with the only stack.
     348
     349For coroutines, @this_exception_context@ accesses the exception context stored
     350at the base of the stack. For threads, @this_exception_context@ uses the
     351concurrency library to access the current stack of the thread or coroutine
     352being executed by the thread, and then accesses the exception context stored at
     353the base of this stack.
    396354
    397355\section{Termination}
    … …  
    411369per-exception storage.
    412370
    413 [Quick ASCII diagram to get started.]
    414 \begin{verbatim}
    415 Fixed Header  | _Unwind_Exception   <- pointer target
    416               |
    417               | Cforall storage
    418               |
    419 Variable Body | the exception       <- fixed offset
    420               V ...
    421 \end{verbatim}
    422 
    423 Exceptions are stored in variable-sized blocks.
    424 The first component is a fixed sized data structure that contains the
     371Exceptions are stored in variable-sized blocks. \PAB{Show a memory layout
     372figure.} The first component is a fixed sized data structure that contains the
    425373information for libunwind and the exception system. The second component is an
    426374area of memory big enough to store the exception. Macros with pointer arthritic
    … …  
    440388exception type. The size and copy function are used immediately to copy an
    441389exception into managed memory. After the exception is handled the free function
    442 is used to clean up the exception and then the entire node is passed to free
    443 so the memory can be given back to the heap.
     390is used to clean up the exception and then the entire node is passed to free.
    444391
    445392\subsection{Try Statements and Catch Clauses}
    … …  
    452399library. The contents of a try block and the termination handlers are converted
    453400into functions. These are then passed to the try terminate function and it
    454 calls them.
    455 Because this function is known and fixed (and not an arbitrary function that
    456 happens to contain a try statement) this means the LSDA can be generated ahead
    457 of time.
    458 
    459 Both the LSDA and the personality function are set ahead of time using
    460 embedded assembly. This is handcrafted using C @asm@ statements and contains
    461 enough information for the single try statement the function repersents.
     401calls them. This approach puts a try statement in its own functions so that no
     402function has to deal with both termination handlers and destructors. \PAB{I do
     403not understand the previous sentence.}
     404
     405This function has some custom embedded assembly that defines \emph{its}
     406personality function and LSDA. The assembly is created with handcrafted C @asm@
     407statements, which is why there is only one version of it. The personality
     408function is structured so that it can be expanded, but currently it only
     409handles this one function.  Notably, it does not handle any destructors so the
     410function is constructed so that it does need to run it. \PAB{I do not
     411understand the previous sentence.}
    462412
    463413The three functions passed to try terminate are:
    … …  
    469419
    470420\item[match function:] This function is called during the search phase and
    471 decides if a catch clause matches the termination exception. It is constructed
     421decides if a catch clause matches the termination exception.  It is constructed
    472422from the conditional part of each handler and runs each check, top to bottom,
    473423in turn, first checking to see if the exception type matches and then if the
    … …  
    478428\item[handler function:] This function handles the exception. It takes a
    479429pointer to the exception and the handler's id and returns nothing. It is called
    480 after the cleanup phase. It is constructed by stitching together the bodies of
     430after the cleanup phase.  It is constructed by stitching together the bodies of
    481431each handler and dispatches to the selected handler.
    482432\end{description}
    … …  
    484434can be used to create closures, functions that can refer to the state of other
    485435functions on the stack. This approach allows the functions to refer to all the
    486 variables in scope for the function containing the @try@ statement. These
     436variables in scope for the function containing the @try@ statement.  These
    487437nested functions and all other functions besides @__cfaehm_try_terminate@ in
    488438\CFA use the GCC personality function and the @-fexceptions@ flag to generate
    … …  
    505455handler that matches. If no handler matches then the function returns
    506456false. Otherwise the matching handler is run; if it completes successfully, the
    507 function returns true. Rethrowing, through the @throwResume;@ statement,
    508 causes the function to return true.
     457function returns true. Reresume, through the @throwResume;@ statement, cause
     458the function to return true.
    509459
    510460% Recursive Resumption Stuff:
    … …  
    532482providing zero-cost enter/exit using the LSDA. Unfortunately, there is no way
    533483to return from a libunwind search without installing a handler or raising an
    534 error. Although workarounds might be possible, they are beyond the scope of
     484error.  Although workarounds might be possible, they are beyond the scope of
    535485this thesis. The current resumption implementation has simplicity in its
    536486favour.
    … …  
    553503
    554504Cancellation also uses libunwind to do its stack traversal and unwinding,
    555 however it uses a different primary function @_Unwind_ForcedUnwind@. Details
     505however it uses a different primary function @_Unwind_ForcedUnwind@.  Details
    556506of its interface can be found in the \VRef{s:ForcedUnwind}.
    557507
    … …  
    561511its main coroutine and the coroutine it is currently executing.
    562512
    563 So if the active thread's main and current coroutine are the same. If they
    564 are then the current stack is a thread stack, otherwise it is a coroutine
    565 stack. If it is a thread stack then an equality check with the stored main
    566 thread pointer and current thread pointer is enough to tell if the current
    567 thread is the main thread or not.
     513The first check is if the current thread's main and current coroutine do not
     514match, implying a coroutine cancellation; otherwise, it is a thread
     515cancellation. Otherwise it is a main thread cancellation. \PAB{Previous
     516sentence does not make sense.}
    568517
    569518However, if the threading library is not linked, the sequential execution is on

  • libcfa/src/concurrency/coroutine.cfa

    ra76da32 r1717b12  
    196196
    197197void __stack_clean  ( __stack_info_t * this ) {
     198        size_t size = ((intptr_t)this->storage->base) - ((intptr_t)this->storage->limit) + sizeof(__stack_t);
    198199        void * storage = this->storage->limit;
    199200
    200201        #if CFA_COROUTINE_USE_MMAP
    201                 size_t size = ((intptr_t)this->storage->base) - ((intptr_t)this->storage->limit) + sizeof(__stack_t);
    202202                storage = (void *)(((intptr_t)storage) - __page_size);
    203203                if(munmap(storage, size + __page_size) == -1) {

  • libcfa/src/concurrency/kernel.cfa

    ra76da32 r1717b12  
    109109static void __run_thread(processor * this, $thread * dst);
    110110static void __wake_one(cluster * cltr);
    111 static void wait(__bin_sem_t & this);
    112111
    113112static void push  (__cluster_idles & idles, processor & proc);
    … …  
    549548// Kernel Idle Sleep
    550549//=============================================================================================
    551 extern "C" {
    552         char * strerror(int);
    553 }
    554 #define CHECKED(x) { int err = x; if( err != 0 ) abort("KERNEL ERROR: Operation \"" #x "\" return error %d - %s\n", err, strerror(err)); }
    555 
    556 static void wait(__bin_sem_t & this) with( this ) {
    557         verify(__cfaabi_dbg_in_kernel());
    558         CHECKED( pthread_mutex_lock(&lock) );
    559                 while(val < 1) {
    560                         pthread_cond_wait(&cond, &lock);
    561                 }
    562                 val -= 1;
    563         CHECKED( pthread_mutex_unlock(&lock) );
    564 }
    565 
    566 static bool post(__bin_sem_t & this) with( this ) {
    567         bool needs_signal = false;
    568 
    569         CHECKED( pthread_mutex_lock(&lock) );
    570                 if(val < 1) {
    571                         val += 1;
    572                         pthread_cond_signal(&cond);
    573                         needs_signal = true;
    574                 }
    575         CHECKED( pthread_mutex_unlock(&lock) );
    576 
    577         return needs_signal;
    578 }
    579 
    580 #undef CHECKED
    581 
    582550// Wake a thread from the front if there are any
    583551static void __wake_one(cluster * this) {

  • libcfa/src/concurrency/kernel.hfa

    ra76da32 r1717b12  
    3434#endif
    3535
     36extern "C" {
     37        char * strerror(int);
     38}
     39#define CHECKED(x) { int err = x; if( err != 0 ) abort("KERNEL ERROR: Operation \"" #x "\" return error %d - %s\n", err, strerror(err)); }
     40
    3641struct __bin_sem_t {
    3742        pthread_mutex_t         lock;
    … …  
    3944        int                     val;
    4045};
     46
     47static inline void ?{}(__bin_sem_t & this) with( this ) {
     48        // Create the mutex with error checking
     49        pthread_mutexattr_t mattr;
     50        pthread_mutexattr_init( &mattr );
     51        pthread_mutexattr_settype( &mattr, PTHREAD_MUTEX_ERRORCHECK_NP);
     52        pthread_mutex_init(&lock, &mattr);
     53
     54        pthread_cond_init (&cond, (const pthread_condattr_t *)0p);  // workaround trac#208: cast should not be required
     55        val = 0;
     56}
     57
     58static inline void ^?{}(__bin_sem_t & this) with( this ) {
     59        CHECKED( pthread_mutex_destroy(&lock) );
     60        CHECKED( pthread_cond_destroy (&cond) );
     61}
     62
     63static inline void wait(__bin_sem_t & this) with( this ) {
     64        verify(__cfaabi_dbg_in_kernel());
     65        CHECKED( pthread_mutex_lock(&lock) );
     66                while(val < 1) {
     67                        pthread_cond_wait(&cond, &lock);
     68                }
     69                val -= 1;
     70        CHECKED( pthread_mutex_unlock(&lock) );
     71}
     72
     73static inline bool post(__bin_sem_t & this) with( this ) {
     74        bool needs_signal = false;
     75
     76        CHECKED( pthread_mutex_lock(&lock) );
     77                if(val < 1) {
     78                        val += 1;
     79                        pthread_cond_signal(&cond);
     80                        needs_signal = true;
     81                }
     82        CHECKED( pthread_mutex_unlock(&lock) );
     83
     84        return needs_signal;
     85}
     86
     87#undef CHECKED
     88
    4189
    4290//-----------------------------------------------------------------------------

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

    ra76da32 r1717b12  
    8080static void ?{}(processorCtx_t & this) {}
    8181static void ?{}(processorCtx_t & this, processor * proc, current_stack_info_t * info);
    82 static void ?{}(__bin_sem_t & this);
    83 static void ^?{}(__bin_sem_t & this);
    8482
    8583#if defined(__CFA_WITH_VERIFY__)
    … …  
    738736}
    739737
    740 extern "C" {
    741         char * strerror(int);
    742 }
    743 #define CHECKED(x) { int err = x; if( err != 0 ) abort("KERNEL ERROR: Operation \"" #x "\" return error %d - %s\n", err, strerror(err)); }
    744 
    745 static void ?{}(__bin_sem_t & this) with( this ) {
    746         // Create the mutex with error checking
    747         pthread_mutexattr_t mattr;
    748         pthread_mutexattr_init( &mattr );
    749         pthread_mutexattr_settype( &mattr, PTHREAD_MUTEX_ERRORCHECK_NP);
    750         pthread_mutex_init(&lock, &mattr);
    751 
    752         pthread_cond_init (&cond, (const pthread_condattr_t *)0p);  // workaround trac#208: cast should not be required
    753         val = 0;
    754 }
    755 
    756 static void ^?{}(__bin_sem_t & this) with( this ) {
    757         CHECKED( pthread_mutex_destroy(&lock) );
    758         CHECKED( pthread_cond_destroy (&cond) );
    759 }
    760 
    761 #undef CHECKED
    762738
    763739#if defined(__CFA_WITH_VERIFY__)

  • libcfa/src/concurrency/ready_queue.cfa

    ra76da32 r1717b12  
    330330        #if defined(BIAS)
    331331                // Don't bother trying locally too much
     332                int local_tries = 8;
    332333                preferred = kernelTLS().this_processor->id * 4;
    333334        #endif
Note: See TracChangeset for help on using the changeset viewer.