Changeset a76da32


Ignore:
Timestamp:
Feb 17, 2021, 10:09:04 PM (4 years ago)
Author:
Peter A. Buhr <pabuhr@…>
Branches:
ADT, arm-eh, ast-experimental, enum, forall-pointer-decay, jacob/cs343-translation, master, new-ast-unique-expr, pthread-emulation, qualifiedEnum
Children:
1294d7f, f4f3f59
Parents:
1717b12 (diff), 830299f (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.
Message:

Merge branch 'master' of plg.uwaterloo.ca:software/cfa/cfa-cc

Files:
6 edited

Legend:

Unmodified
Added
Removed

  • doc/theses/andrew_beach_MMath/implement.tex

    r1717b12 ra76da32  
    1313library.
    1414
     15\subsection{Virtual Type}
     16Virtual types only have one change to their structure, the addition of a
     17pointer to the virtual table. This is always the first field so that
     18if it is cast to a supertype the field's location is still known.
     19
     20This field is set as part of all new generated constructors.
     21\todo{They only come as part exceptions and don't work.}
     22After the object is created the field is constant.
     23
     24However 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
     26type's virtual members.
     27
    1528\subsection{Virtual Table}
     29Every time a virtual type is defined the new virtual table type must also be
     30defined.
     31
     32The unique instance is important because the address of the virtual table
     33instance is used as the identifier for the virtual type. So a pointer to the
     34virtual 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
     36system instead.}
     37
     38The first step in putting it all together is to create the virtual table type.
     39The virtual table type is just a structure and can be described in terms of
     40its fields. The first field is always the parent type ID (or a pointer to
     41the parent virtual table) or 0 (the null pointer).
     42Next are other fields on the parent virtual table are repeated.
     43Finally are the fields used to store any new virtual members of the new
     44The virtual type
     45
    1646The virtual system is accessed through a private constant field inserted at the
    1747beginning of every virtual type, called the virtual-table pointer. This field
    1848points at a type's virtual table and is assigned during the object's
    19 construction.  The address of a virtual table acts as the unique identifier for
     49construction. The address of a virtual table acts as the unique identifier for
    2050the virtual type, and the first field of a virtual table is a pointer to the
    21 parent virtual-table or @0p@.  The remaining fields are duplicated from the
     51parent virtual-table or @0p@. The remaining fields are duplicated from the
    2252parent tables in this type's inheritance chain, followed by any fields this type
    23 introduces. Parent fields are duplicated so they can be changed (\CC
    24 \lstinline[language=c++]|override|), so that references to the dispatched type
     53introduces. Parent fields are duplicated so they can be changed (all virtual
     54members are overridable), so that references to the dispatched type
    2555are replaced with the current virtual type.
    26 \PAB{Can you create a simple diagram of the layout?}
    2756% These are always taken by pointer or reference.
     57
     58% Simple ascii diragram:
     59\begin{verbatim}
     60parent_pointer  \
     61parent_field0   |
     62...             | Same layout as parent.
     63parent_fieldN   /
     64child_field0
     65...
     66child_fieldN
     67\end{verbatim}
     68\todo{Refine the diagram}
    2869
    2970% For each virtual type, a virtual table is constructed. This is both a new type
    … …  
    3475A virtual table is created when the virtual type is created. The name of the
    3576type is created by mangling the name of the base type. The name of the instance
    36 is also generated by name mangling.  The fields are initialized automatically.
     77is also generated by name mangling. The fields are initialized automatically.
    3778The parent field is initialized by getting the type of the parent field and
    3879using that to calculate the mangled name of the parent's virtual table type.
    … …  
    67108\begin{sloppypar}
    68109Coroutines and threads need instances of @CoroutineCancelled@ and
    69 @ThreadCancelled@ respectively to use all of their functionality.  When a new
     110@ThreadCancelled@ respectively to use all of their functionality. When a new
    70111data type is declared with @coroutine@ or @thread@ the forward declaration for
    71112the instance is created as well. The definition of the virtual table is created
    … …  
    80121The function is
    81122\begin{cfa}
    82 void * __cfa__virtual_cast( struct __cfa__parent_vtable const * parent,
     123void * __cfa__virtual_cast(
     124        struct __cfa__parent_vtable const * parent,
    83125        struct __cfa__parent_vtable const * const * child );
    84 }
    85126\end{cfa}
    86 and it is implemented in the standard library. It takes a pointer to the target
    87 type's virtual table and the object pointer being cast. The function performs a
    88 linear search starting at the object's virtual-table and walking through the
    89 the parent pointers, checking to if it or any of its ancestors are the same as
    90 the target-type virtual table-pointer.
    91 
    92 For the generated code, a forward declaration of the virtual works as follows.
    93 There is a forward declaration of @__cfa__virtual_cast@ in every \CFA file so
    94 it can just be used. The object argument is the expression being cast so that
    95 is just placed in the argument list.
    96 
    97 To build the target type parameter, the compiler creates a mapping from
    98 concrete type-name -- so for polymorphic types the parameters are filled in --
    99 to virtual table address. Every virtual table declaration is added to the this
    100 table; repeats are ignored unless they have conflicting definitions.  Note,
    101 these declarations do not have to be in scope, but they should usually be
    102 introduced as part of the type definition.
    103 
    104 \PAB{I do not understood all of \VRef{s:VirtualSystem}. I think you need to
    105 write more to make it clear.}
    106 
     127and it is implemented in the standard library. The structure reperents the
     128head 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@
     130points at the object of the (possibe) child type.
     131
     132In terms of the virtual cast expression, @parent@ comes from looking up the
     133type being cast to and @child@ is the result of the expression being cast.
     134Because the complier outputs C code, some type C type casts are also used.
     135The last bit of glue is an map that saves every virtual type the compiler
     136sees. This is used to check the type used in a virtual cast is a virtual
     137type and to get its virtual table.
     138(It also checks for conflicting definitions.)
     139
     140Inside 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
     142requires one more level of derefence to pass through the object) then @child@
     143is returned, otherwise the null pointer is returned.
     144
     145The check itself is preformed is a simple linear search. If the child
     146virtual table or any of its ancestors (which are retreved through the first
     147field of every virtual table) are the same as the parent virtual table then
     148the cast succeeds.
    107149
    108150\section{Exceptions}
    … …  
    121163stack. On function entry and return, unwinding is handled directly by the code
    122164embedded in the function. Usually, the stack-frame size is known statically
    123 based on parameter and local variable declarations.  For dynamically-sized
     165based on parameter and local variable declarations. For dynamically-sized
    124166local variables, a runtime computation is necessary to know the frame
    125167size. Finally, a function's frame-size may change during execution as local
    … …  
    179221
    180222To use libunwind, each function must have a personality function and a Language
    181 Specific Data Area (LSDA).  The LSDA has the unique information for each
     223Specific Data Area (LSDA). The LSDA has the unique information for each
    182224function to tell the personality function where a function is executing, its
    183 current stack frame, and what handlers should be checked.  Theoretically, the
     225current stack frame, and what handlers should be checked. Theoretically, the
    184226LSDA can contain any information but conventionally it is a table with entries
    185227representing regions of the function and what has to be done there during
    … …  
    196238
    197239The GCC compilation flag @-fexceptions@ causes the generation of an LSDA and
    198 attaches its personality function. \PAB{to what is it attached?}  However, this
    199 flag only handles the cleanup attribute
     240attaches its personality function. However, this
     241flag only handles the cleanup attribute:
     242\todo{Peter: What is attached? Andrew: It uses the .cfi\_personality directive
     243and that's all I know.}
    200244\begin{cfa}
    201245void clean_up( int * var ) { ... }
    202 int avar __attribute__(( __cleanup(clean_up) ));
     246int avar __attribute__(( cleanup(clean_up) ));
    203247\end{cfa}
    204 which is used on a variable and specifies a function, \eg @clean_up@, run when
    205 the variable goes out of scope. The function is passed a pointer to the object
    206 so it can be used to mimic destructors. However, this feature cannot be used to
    207 mimic @try@ statements.
     248which is used on a variable and specifies a function, in this case @clean_up@,
     249run when the variable goes out of scope.
     250The function is passed a pointer to the object being removed from the stack
     251so it can be used to mimic destructors.
     252However, this feature cannot be used to mimic @try@ statements as it cannot
     253control the unwinding.
    208254
    209255\subsection{Personality Functions}
    210 Personality functions have a complex interface specified by libunwind.  This
     256Personality functions have a complex interface specified by libunwind. This
    211257section covers some of the important parts of the interface.
    212258
    213 A personality function performs four tasks, although not all have to be
    214 present.
     259A personality function can preform different actions depending on how it is
     260called.
    215261\begin{lstlisting}[language=C,{moredelim=**[is][\color{red}]{@}{@}}]
    216262typedef _Unwind_Reason_Code (*@_Unwind_Personality_Fn@) (
    … …  
    225271\item
    226272@_UA_SEARCH_PHASE@ specifies a search phase and tells the personality function
    227 to check for handlers.  If there is a handler in a stack frame, as defined by
     273to check for handlers. If there is a handler in a stack frame, as defined by
    228274the language, the personality function returns @_URC_HANDLER_FOUND@; otherwise
    229275it return @_URC_CONTINUE_UNWIND@.
    … …  
    296342\end{cfa}
    297343It also unwinds the stack but it does not use the search phase. Instead another
    298 function, the stop function, is used to stop searching.  The exception is the
     344function, the stop function, is used to stop searching. The exception is the
    299345same as the one passed to raise exception. The extra arguments are the stop
    300346function and the stop parameter. The stop function has a similar interface as a
    … …  
    318364
    319365\begin{sloppypar}
    320 Its arguments are the same as the paired personality function.  The actions
     366Its arguments are the same as the paired personality function. The actions
    321367@_UA_CLEANUP_PHASE@ and @_UA_FORCE_UNWIND@ are always set when it is
    322368called. Beyond the libunwind standard, both GCC and Clang add an extra action
    … …  
    343389strong symbol replacing the sequential version.
    344390
    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 
    349 For coroutines, @this_exception_context@ accesses the exception context stored
    350 at the base of the stack. For threads, @this_exception_context@ uses the
    351 concurrency library to access the current stack of the thread or coroutine
    352 being executed by the thread, and then accesses the exception context stored at
    353 the base of this stack.
     391The sequential @this_exception_context@ returns a hard-coded pointer to the
     392global execption context.
     393The concurrent version adds the exception context to the data stored at the
     394base of each stack. When @this_exception_context@ is called it retrieves the
     395active stack and returns the address of the context saved there.
    354396
    355397\section{Termination}
    … …  
    369411per-exception storage.
    370412
    371 Exceptions are stored in variable-sized blocks. \PAB{Show a memory layout
    372 figure.} The first component is a fixed sized data structure that contains the
     413[Quick ASCII diagram to get started.]
     414\begin{verbatim}
     415Fixed Header  | _Unwind_Exception   <- pointer target
     416              |
     417              | Cforall storage
     418              |
     419Variable Body | the exception       <- fixed offset
     420              V ...
     421\end{verbatim}
     422
     423Exceptions are stored in variable-sized blocks.
     424The first component is a fixed sized data structure that contains the
    373425information for libunwind and the exception system. The second component is an
    374426area of memory big enough to store the exception. Macros with pointer arthritic
    … …  
    388440exception type. The size and copy function are used immediately to copy an
    389441exception into managed memory. After the exception is handled the free function
    390 is used to clean up the exception and then the entire node is passed to free.
     442is used to clean up the exception and then the entire node is passed to free
     443so the memory can be given back to the heap.
    391444
    392445\subsection{Try Statements and Catch Clauses}
    … …  
    399452library. The contents of a try block and the termination handlers are converted
    400453into functions. These are then passed to the try terminate function and it
    401 calls them. This approach puts a try statement in its own functions so that no
    402 function has to deal with both termination handlers and destructors. \PAB{I do
    403 not understand the previous sentence.}
    404 
    405 This function has some custom embedded assembly that defines \emph{its}
    406 personality function and LSDA. The assembly is created with handcrafted C @asm@
    407 statements, which is why there is only one version of it. The personality
    408 function is structured so that it can be expanded, but currently it only
    409 handles this one function.  Notably, it does not handle any destructors so the
    410 function is constructed so that it does need to run it. \PAB{I do not
    411 understand the previous sentence.}
     454calls them.
     455Because this function is known and fixed (and not an arbitrary function that
     456happens to contain a try statement) this means the LSDA can be generated ahead
     457of time.
     458
     459Both the LSDA and the personality function are set ahead of time using
     460embedded assembly. This is handcrafted using C @asm@ statements and contains
     461enough information for the single try statement the function repersents.
    412462
    413463The three functions passed to try terminate are:
    … …  
    419469
    420470\item[match function:] This function is called during the search phase and
    421 decides if a catch clause matches the termination exception.  It is constructed
     471decides if a catch clause matches the termination exception. It is constructed
    422472from the conditional part of each handler and runs each check, top to bottom,
    423473in turn, first checking to see if the exception type matches and then if the
    … …  
    428478\item[handler function:] This function handles the exception. It takes a
    429479pointer to the exception and the handler's id and returns nothing. It is called
    430 after the cleanup phase.  It is constructed by stitching together the bodies of
     480after the cleanup phase. It is constructed by stitching together the bodies of
    431481each handler and dispatches to the selected handler.
    432482\end{description}
    … …  
    434484can be used to create closures, functions that can refer to the state of other
    435485functions on the stack. This approach allows the functions to refer to all the
    436 variables in scope for the function containing the @try@ statement.  These
     486variables in scope for the function containing the @try@ statement. These
    437487nested functions and all other functions besides @__cfaehm_try_terminate@ in
    438488\CFA use the GCC personality function and the @-fexceptions@ flag to generate
    … …  
    455505handler that matches. If no handler matches then the function returns
    456506false. Otherwise the matching handler is run; if it completes successfully, the
    457 function returns true. Reresume, through the @throwResume;@ statement, cause
    458 the function to return true.
     507function returns true. Rethrowing, through the @throwResume;@ statement,
     508causes the function to return true.
    459509
    460510% Recursive Resumption Stuff:
    … …  
    482532providing zero-cost enter/exit using the LSDA. Unfortunately, there is no way
    483533to return from a libunwind search without installing a handler or raising an
    484 error.  Although workarounds might be possible, they are beyond the scope of
     534error. Although workarounds might be possible, they are beyond the scope of
    485535this thesis. The current resumption implementation has simplicity in its
    486536favour.
    … …  
    503553
    504554Cancellation also uses libunwind to do its stack traversal and unwinding,
    505 however it uses a different primary function @_Unwind_ForcedUnwind@.  Details
     555however it uses a different primary function @_Unwind_ForcedUnwind@. Details
    506556of its interface can be found in the \VRef{s:ForcedUnwind}.
    507557
    … …  
    511561its main coroutine and the coroutine it is currently executing.
    512562
    513 The first check is if the current thread's main and current coroutine do not
    514 match, implying a coroutine cancellation; otherwise, it is a thread
    515 cancellation. Otherwise it is a main thread cancellation. \PAB{Previous
    516 sentence does not make sense.}
     563So if the active thread's main and current coroutine are the same. If they
     564are then the current stack is a thread stack, otherwise it is a coroutine
     565stack. If it is a thread stack then an equality check with the stored main
     566thread pointer and current thread pointer is enough to tell if the current
     567thread is the main thread or not.
    517568
    518569However, if the threading library is not linked, the sequential execution is on

  • libcfa/src/concurrency/coroutine.cfa

    r1717b12 ra76da32  
    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);
    199198        void * storage = this->storage->limit;
    200199
    201200        #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

    r1717b12 ra76da32  
    109109static void __run_thread(processor * this, $thread * dst);
    110110static void __wake_one(cluster * cltr);
     111static void wait(__bin_sem_t & this);
    111112
    112113static void push  (__cluster_idles & idles, processor & proc);
    … …  
    548549// Kernel Idle Sleep
    549550//=============================================================================================
     551extern "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
     556static 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
     566static 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
    550582// Wake a thread from the front if there are any
    551583static void __wake_one(cluster * this) {

  • libcfa/src/concurrency/kernel.hfa

    r1717b12 ra76da32  
    3434#endif
    3535
    36 extern "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 
    4136struct __bin_sem_t {
    4237        pthread_mutex_t         lock;
    … …  
    4439        int                     val;
    4540};
    46 
    47 static 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 
    58 static inline void ^?{}(__bin_sem_t & this) with( this ) {
    59         CHECKED( pthread_mutex_destroy(&lock) );
    60         CHECKED( pthread_cond_destroy (&cond) );
    61 }
    62 
    63 static 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 
    73 static 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 
    8941
    9042//-----------------------------------------------------------------------------

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

    r1717b12 ra76da32  
    8080static void ?{}(processorCtx_t & this) {}
    8181static void ?{}(processorCtx_t & this, processor * proc, current_stack_info_t * info);
     82static void ?{}(__bin_sem_t & this);
     83static void ^?{}(__bin_sem_t & this);
    8284
    8385#if defined(__CFA_WITH_VERIFY__)
    … …  
    736738}
    737739
     740extern "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
     745static 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
     756static void ^?{}(__bin_sem_t & this) with( this ) {
     757        CHECKED( pthread_mutex_destroy(&lock) );
     758        CHECKED( pthread_cond_destroy (&cond) );
     759}
     760
     761#undef CHECKED
    738762
    739763#if defined(__CFA_WITH_VERIFY__)

  • libcfa/src/concurrency/ready_queue.cfa

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