Changeset 510e6f9


Ignore:
Timestamp:
Mar 11, 2022, 1:56:07 PM (3 years ago)
Author:
caparsons <caparson@…>
Branches:
ADT, ast-experimental, enum, master, pthread-emulation, qualifiedEnum
Children:
623d1c8
Parents:
eb3bc52 (diff), 630c4bb (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:
7 added
29 edited
1 moved

Legend:

Unmodified
Added
Removed

  • benchmark/io/http/protocol.cfa

    reb3bc52 r510e6f9  
    173173}
    174174
    175 static void zero_sqe(struct io_uring_sqe * sqe) {
    176         sqe->flags = 0;
    177         sqe->ioprio = 0;
    178         sqe->fd = 0;
    179         sqe->off = 0;
    180         sqe->addr = 0;
    181         sqe->len = 0;
    182         sqe->fsync_flags = 0;
    183         sqe->__pad2[0] = 0;
    184         sqe->__pad2[1] = 0;
    185         sqe->__pad2[2] = 0;
    186         sqe->fd = 0;
    187         sqe->off = 0;
    188         sqe->addr = 0;
    189         sqe->len = 0;
    190 }
    191 
    192175enum FSM_STATE {
    193176        Initial,

  • doc/theses/mubeen_zulfiqar_MMath/allocator.tex

    reb3bc52 r510e6f9  
    11\chapter{Allocator}
    22
    3 \noindent
    4 ====================
    5 
    6 Writing Points:
    7 \begin{itemize}
    8 \item
    9 Objective of uHeapLmmm.
    10 \item
    11 Design philosophy.
    12 \item
    13 Background and previous design of uHeapLmmm.
    14 \item
    15 Distributed design of uHeapLmmm.
    16 
    17 ----- SHOULD WE GIVE IMPLEMENTATION DETAILS HERE? -----
    18 
    19 \PAB{Maybe. There might be an Implementation chapter.}
    20 \item
    21 figure.
    22 \item
    23 Advantages of distributed design.
    24 \end{itemize}
    25 
    26 The new features added to uHeapLmmm (incl. @malloc_size@ routine)
    27 \CFA alloc interface with examples.
    28 
    29 \begin{itemize}
    30 \item
    31 Why did we need it?
    32 \item
    33 The added benefits.
    34 \end{itemize}
    35 
    36 
    37 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    38 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    39 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% uHeapLmmm Design
    40 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    41 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    42 
    43 \section{Objective of uHeapLmmm}
    44 UHeapLmmm is a lightweight memory allocator. The objective behind uHeapLmmm is to design a minimal concurrent memory allocator that has new features and also fulfills GNU C Library requirements (FIX ME: cite requirements).
    45 
    46 \subsection{Design philosophy}
    47 The objective of uHeapLmmm's new design was to fulfill following requirements:
    48 \begin{itemize}
    49 \item It should be concurrent to be used in multi-threaded programs.
     3\section{uHeap}
     4uHeap is a lightweight memory allocator. The objective behind uHeap is to design a minimal concurrent memory allocator that has new features and also fulfills GNU C Library requirements (FIX ME: cite requirements).
     5
     6The objective of uHeap's new design was to fulfill following requirements:
     7\begin{itemize}
     8\item It should be concurrent and thread-safe for multi-threaded programs.
    509\item It should avoid global locks, on resources shared across all threads, as much as possible.
    5110\item It's performance (FIX ME: cite performance benchmarks) should be comparable to the commonly used allocators (FIX ME: cite common allocators).
    … …  
    5514%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    5615
    57 \section{Background and previous design of uHeapLmmm}
    58 uHeapLmmm was originally designed by X in X (FIX ME: add original author after confirming with Peter).
    59 (FIX ME: make and add figure of previous design with description)
    60 
    61 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    62 
    63 \section{Distributed design of uHeapLmmm}
    64 uHeapLmmm's design was reviewed and changed to fulfill new requirements (FIX ME: cite allocator philosophy). For this purpose, following two designs of uHeapLmm were proposed:
    65 
    66 \paragraph{Design 1: Decentralized}
     16\section{Design choices for uHeap}
     17uHeap's design was reviewed and changed to fulfill new requirements (FIX ME: cite allocator philosophy). For this purpose, following two designs of uHeapLmm were proposed:
     18
     19\paragraph{Design 1: Centralized}
     20One heap, but lower bucket sizes are N-shared across KTs.
     21This design leverages the fact that 95\% of allocation requests are less than 512 bytes and there are only 3--5 different request sizes.
     22When KTs $\le$ N, the important bucket sizes are uncontented.
     23When KTs $>$ N, the free buckets are contented.
     24Therefore, threads are only contending for a small number of buckets, which are distributed among them to reduce contention.
     25\begin{cquote}
     26\centering
     27\input{AllocDS2}
     28\end{cquote}
     29Problems: need to know when a kernel thread (KT) is created and destroyed to know when to assign a shared bucket-number.
     30When no thread is assigned a bucket number, its free storage is unavailable. All KTs will be contended for one lock on sbrk for their initial allocations (before free-lists gets populated).
     31
     32\paragraph{Design 2: Decentralized N Heaps}
    6733Fixed number of heaps: shard the heap into N heaps each with a bump-area allocated from the @sbrk@ area.
    6834Kernel threads (KT) are assigned to the N heaps.
    … …  
    7743Problems: need to know when a KT is created and destroyed to know when to assign/un-assign a heap to the KT.
    7844
    79 \paragraph{Design 2: Centralized}
    80 One heap, but lower bucket sizes are N-shared across KTs.
    81 This design leverages the fact that 95\% of allocation requests are less than 512 bytes and there are only 3--5 different request sizes.
    82 When KTs $\le$ N, the important bucket sizes are uncontented.
    83 When KTs $>$ N, the free buckets are contented.
    84 Therefore, threads are only contending for a small number of buckets, which are distributed among them to reduce contention.
    85 \begin{cquote}
     45\paragraph{Design 3: Decentralized Per-thread Heaps}
     46Design 3 is similar to design 2 but instead of having an M:N model, it uses a 1:1 model. So, instead of having N heaos and sharing them among M KTs, Design 3 has one heap for each KT.
     47Dynamic number of heaps: create a thread-local heap for each kernel thread (KT) with a bump-area allocated from the @sbrk@ area.
     48Each KT will have its own exclusive thread-local heap. Heap will be uncontended between KTs regardless how many KTs have been created.
     49Operations on @sbrk@ area will still be protected by locks.
     50%\begin{cquote}
     51%\centering
     52%\input{AllocDS3} FIXME add figs
     53%\end{cquote}
     54Problems: We cannot destroy the heap when a KT exits because our dynamic objects have ownership and they are returned to the heap that created them when the program frees a dynamic object. All dynamic objects point back to their owner heap. If a thread A creates an object O, passes it to another thread B, and A itself exits. When B will free object O, O should return to A's heap so A's heap should be preserved for the lifetime of the whole program as their might be objects in-use of other threads that were allocated by A. Also, we need to know when a KT is created and destroyed to know when to create/destroy a heap for the KT.
     55
     56\paragraph{Design 4: Decentralized Per-CPU Heaps}
     57Design 4 is similar to Design 3 but instead of having a heap for each thread, it creates a heap for each CPU.
     58Fixed number of heaps for a machine: create a heap for each CPU with a bump-area allocated from the @sbrk@ area.
     59Each CPU will have its own CPU-local heap. When the program does a dynamic memory operation, it will be entertained by the heap of the CPU where the process is currently running on.
     60Each CPU will have its own exclusive heap. Just like Design 3(FIXME cite), heap will be uncontended between KTs regardless how many KTs have been created.
     61Operations on @sbrk@ area will still be protected by locks.
     62To deal with preemtion during a dynamic memory operation, librseq(FIXME cite) will be used to make sure that the whole dynamic memory operation completes on one CPU. librseq's restartable sequences can make it possible to re-run a critical section and undo the current writes if a preemption happened during the critical section's execution.
     63%\begin{cquote}
     64%\centering
     65%\input{AllocDS4} FIXME add figs
     66%\end{cquote}
     67
     68Problems: This approach was slower than the per-thread model. Also, librseq does not provide such restartable sequences to detect preemtions in user-level threading system which is important to us as CFA(FIXME cite) has its own threading system that we want to support.
     69
     70Out of the four designs, Design 3 was chosen because of the following reasons.
     71\begin{itemize}
     72\item
     73Decentralized designes are better in general as compared to centralized design because their concurrency is better across all bucket-sizes as design 1 shards a few buckets of selected sizes while other designs shards all the buckets. Decentralized designes shard the whole heap which has all the buckets with the addition of sharding sbrk area. So Design 1 was eliminated.
     74\item
     75Design 2 was eliminated because it has a possibility of contention in-case of KT > N while Design 3 and 4 have no contention in any scenerio.
     76\item
     77Design 4 was eliminated because it was slower than Design 3 and it provided no way to achieve user-threading safety using librseq. We had to use CFA interruption handling to achive user-threading safety which has some cost to it. Desing 4 was already slower than Design 3, adding cost of interruption handling on top of that would have made it even slower.
     78\end{itemize}
     79
     80
     81\subsection{Advantages of distributed design}
     82
     83The distributed design of uHeap is concurrent to work in multi-threaded applications.
     84
     85Some key benefits of the distributed design of uHeap are as follows:
     86
     87\begin{itemize}
     88\item
     89The bump allocation is concurrent as memory taken from sbrk is sharded across all heaps as bump allocation reserve. The call to sbrk will be protected using locks but bump allocation (on memory taken from sbrk) will not be contended once the sbrk call has returned.
     90\item
     91Low or almost no contention on heap resources.
     92\item
     93It is possible to use sharing and stealing techniques to share/find unused storage, when a free list is unused or empty.
     94\item
     95Distributed design avoids unnecassry locks on resources shared across all KTs.
     96\end{itemize}
     97
     98%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
     99
     100\section{uHeap Structure}
     101
     102As described in (FIXME cite 2.4) uHeap uses following features of multi-threaded memory allocators.
     103\begin{itemize}
     104\item
     105uHeap has multiple heaps without a global heap and uses 1:1 model. (FIXME cite 2.5 1:1 model)
     106\item
     107uHeap uses object ownership. (FIXME cite 2.5.2)
     108\item
     109uHeap does not use object containers (FIXME cite 2.6) or any coalescing technique. Instead each dynamic object allocated by uHeap has a header than contains bookkeeping information.
     110\item
     111Each thread-local heap in uHeap has its own allocation buffer that is taken from the system using sbrk() call. (FIXME cite 2.7)
     112\item
     113Unless a heap is freeing an object that is owned by another thread's heap or heap is using sbrk() system call, uHeap is mostly lock-free which eliminates most of the contention on shared resources. (FIXME cite 2.8)
     114\end{itemize}
     115
     116As uHeap uses a heap per-thread model to reduce contention on heap resources, we manage a list of heaps (heap-list) that can be used by threads. The list is empty at the start of the program. When a kernel thread (KT) is created, we check if heap-list is empty. If no then a heap is removed from the heap-list and is given to this new KT to use exclusively. If yes then a new heap object is created in dynamic memory and is given to this new KT to use exclusively. When a KT exits, its heap is not destroyed but instead its heap is put on the heap-list and is ready to be reused by new KTs.
     117
     118This reduces the memory footprint as the objects on free-lists of a KT that has exited can be reused by a new KT. Also, we preserve all the heaps that were created during the lifetime of the program till the end of the program. uHeap uses object ownership where an object is freed to the free-buckets of the heap that allocated it. Even after a KT A has exited, its heap has to be preserved as there might be objects in-use of other threads that were initially allocated by A and the passed to other threads.
     119
     120\begin{figure}
    86121\centering
    87 \input{AllocDS2}
    88 \end{cquote}
    89 Problems: need to know when a kernel thread (KT) is created and destroyed to know when to assign a shared bucket-number.
    90 When no thread is assigned a bucket number, its free storage is unavailable. All KTs will be contended for one lock on sbrk for their initial allocations (before free-lists gets populated).
    91 
    92 Out of the two designs, Design 1 was chosen because it's concurrency is better across all bucket-sizes as design-2 shards a few buckets of selected sizes while design-1 shards all the buckets. Design-2 shards the whole heap which has all the buckets with the addition of sharding sbrk area.
    93 
    94 \subsection{Advantages of distributed design}
    95 The distributed design of uHeapLmmm is concurrent to work in multi-threaded applications.
    96 
    97 Some key benefits of the distributed design of uHeapLmmm are as follows:
    98 
    99 \begin{itemize}
    100 \item
    101 The bump allocation is concurrent as memory taken from sbrk is sharded across all heaps as bump allocation reserve. The lock on bump allocation (on memory taken from sbrk) will only be contended if KTs $<$ N. The contention on sbrk area is less likely as it will only happen in the case if heaps assigned to two KTs get short of bump allocation reserve simultanously.
    102 \item
    103 N heaps are created at the start of the program and destroyed at the end of program. When a KT is created, we only assign it to one of the heaps. When a KT is destroyed, we only dissociate it from the assigned heap but we do not destroy that heap. That heap will go back to our pool-of-heaps, ready to be used by some new KT. And if that heap was shared among multiple KTs (like the case of KTs $<$ N) then, on deletion of one KT, that heap will be still in-use of the other KTs. This will prevent creation and deletion of heaps during run-time as heaps are re-usable which helps in keeping low-memory footprint.
    104 \item
    105 It is possible to use sharing and stealing techniques to share/find unused storage, when a free list is unused or empty.
    106 \item
    107 Distributed design avoids unnecassry locks on resources shared across all KTs.
    108 \end{itemize}
    109 
    110 FIX ME: Cite performance comparison of the two heap designs if required
     122\includegraphics[width=0.65\textwidth]{figures/NewHeapStructure.eps}
     123\caption{HeapStructure}
     124\label{fig:heapStructureFig}
     125\end{figure}
     126
     127Each heap uses seggregated free-buckets that have free objects of a specific size. Each free-bucket of a specific size has following 2 lists in it:
     128\begin{itemize}
     129\item
     130Free list is used when a thread is freeing an object that is owned by its own heap so free list does not use any locks/atomic-operations as it is only used by the owner KT.
     131\item
     132Away list is used when a thread A is freeing an object that is owned by another KT B's heap. This object should be freed to the owner heap (B's heap) so A will place the object on the away list of B. Away list is lock protected as it is shared by all other threads.
     133\end{itemize}
     134
     135When a dynamic object of a size S is requested. The thread-local heap will check if S is greater than or equal to the mmap threshhold. Any request larger than the mmap threshhold is fulfilled by allocating an mmap area of that size and such requests are not allocated on sbrk area. The value of this threshhold can be changed using mallopt routine but the new value should not be larger than our biggest free-bucket size.
     136
     137Algorithm~\ref{alg:heapObjectAlloc} briefly shows how an allocation request is fulfilled.
     138
     139\begin{algorithm}
     140\caption{Dynamic object allocation of size S}\label{alg:heapObjectAlloc}
     141\begin{algorithmic}[1]
     142\State $\textit{O} \gets \text{NULL}$
     143\If {$S < \textit{mmap-threshhold}$}
     144        \State $\textit{B} \gets (\text{smallest free-bucket} \geq S)$
     145        \If {$\textit{B's free-list is empty}$}
     146                \If {$\textit{B's away-list is empty}$}
     147                        \If {$\textit{heap's allocation buffer} < S$}
     148                                \State $\text{get allocation buffer using system call sbrk()}$
     149                        \EndIf
     150                        \State $\textit{O} \gets \text{bump allocate an object of size S from allocation buffer}$
     151                \Else
     152                        \State $\textit{merge B's away-list into free-list}$
     153                        \State $\textit{O} \gets \text{pop an object from B's free-list}$
     154                \EndIf
     155        \Else
     156                \State $\textit{O} \gets \text{pop an object from B's free-list}$
     157        \EndIf
     158        \State $\textit{O's owner} \gets \text{B}$
     159\Else
     160        \State $\textit{O} \gets \text{allocate dynamic memory using system call mmap with size S}$
     161\EndIf
     162\State $\Return \textit{ O}$
     163\end{algorithmic}
     164\end{algorithm}
     165
    111166
    112167%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    113168
    114169\section{Added Features and Methods}
    115 To improve the UHeapLmmm allocator (FIX ME: cite uHeapLmmm) interface and make it more user friendly, we added a few more routines to the C allocator. Also, we built a \CFA (FIX ME: cite cforall) interface on top of C interface to increase the usability of the allocator.
     170To improve the uHeap allocator (FIX ME: cite uHeap) interface and make it more user friendly, we added a few more routines to the C allocator. Also, we built a \CFA (FIX ME: cite cforall) interface on top of C interface to increase the usability of the allocator.
    116171
    117172\subsection{C Interface}
    … …  
    207262@addr@: the address of the currently allocated dynamic object.
    208263\end{itemize}
    209 @malloc_alignment@ returns the alignment of the given dynamic object. On failure, it return the value of default alignment of the uHeapLmmm allocator.
     264@malloc_alignment@ returns the alignment of the given dynamic object. On failure, it return the value of default alignment of the uHeap allocator.
    210265
    211266\subsection{\lstinline{bool malloc_zero_fill( void * addr )}}
    … …  
    247302
    248303\subsection{\CFA Malloc Interface}
    249 We added some routines to the malloc interface of \CFA. These routines can only be used in \CFA and not in our standalone uHeapLmmm allocator as these routines use some features that are only provided by \CFA and not by C. It makes the allocator even more usable to the programmers.
     304We added some routines to the malloc interface of \CFA. These routines can only be used in \CFA and not in our standalone uHeap allocator as these routines use some features that are only provided by \CFA and not by C. It makes the allocator even more usable to the programmers.
    250305\CFA provides the liberty to know the returned type of a call to the allocator. So, mainly in these added routines, we removed the object size parameter from the routine as allocator can calculate the size of the object from the returned type.
    251306
    … …  
    378433
    379434\subsection{Alloc Interface}
    380 In addition to improve allocator interface both for \CFA and our standalone allocator uHeapLmmm in C. We also added a new alloc interface in \CFA that increases usability of dynamic memory allocation.
     435In addition to improve allocator interface both for \CFA and our standalone allocator uHeap in C. We also added a new alloc interface in \CFA that increases usability of dynamic memory allocation.
    381436This interface helps programmers in three major ways.
    382437

  • doc/theses/mubeen_zulfiqar_MMath/benchmarks.tex

    reb3bc52 r510e6f9  
    216216\paragraph{Relevant Knobs}
    217217*** FIX ME: Insert Relevant Knobs
    218 
    219 
    220 
    221 \section{Existing Memory Allocators}
    222 With dynamic allocation being an important feature of C, there are many stand-alone memory allocators that have been designed for different purposes. For this thesis, we chose 7 of the most popular and widely used memory allocators.
    223 
    224 \paragraph{dlmalloc}
    225 dlmalloc (FIX ME: cite allocator) is a thread-safe allocator that is single threaded and single heap. dlmalloc maintains free-lists of different sizes to store freed dynamic memory. (FIX ME: cite wasik)
    226 
    227 \paragraph{hoard}
    228 Hoard (FIX ME: cite allocator) is a thread-safe allocator that is multi-threaded and using a heap layer framework. It has per-thread heaps that have thread-local free-lists, and a global shared heap. (FIX ME: cite wasik)
    229 
    230 \paragraph{jemalloc}
    231 jemalloc (FIX ME: cite allocator) is a thread-safe allocator that uses multiple arenas. Each thread is assigned an arena. Each arena has chunks that contain contagious memory regions of same size. An arena has multiple chunks that contain regions of multiple sizes.
    232 
    233 \paragraph{ptmalloc}
    234 ptmalloc (FIX ME: cite allocator) is a modification of dlmalloc. It is a thread-safe multi-threaded memory allocator that uses multiple heaps. ptmalloc heap has similar design to dlmalloc's heap.
    235 
    236 \paragraph{rpmalloc}
    237 rpmalloc (FIX ME: cite allocator) is a thread-safe allocator that is multi-threaded and uses per-thread heap. Each heap has multiple size-classes and each size-class contains memory regions of the relevant size.
    238 
    239 \paragraph{tbb malloc}
    240 tbb malloc (FIX ME: cite allocator) is a thread-safe allocator that is multi-threaded and uses private heap for each thread. Each private-heap has multiple bins of different sizes. Each bin contains free regions of the same size.
    241 
    242 \paragraph{tc malloc}
    243 tcmalloc (FIX ME: cite allocator) is a thread-safe allocator. It uses per-thread cache to store free objects that prevents contention on shared resources in multi-threaded application. A central free-list is used to refill per-thread cache when it gets empty.

  • doc/theses/mubeen_zulfiqar_MMath/performance.tex

    reb3bc52 r510e6f9  
    1818\noindent
    1919====================
     20
     21\section{Machine Specification}
     22
     23The performance experiments were run on three different multicore systems to determine if there is consistency across platforms:
     24\begin{itemize}
     25\item
     26AMD EPYC 7662, 64-core socket $\times$ 2, 2.0 GHz
     27\item
     28Huawei ARM TaiShan 2280 V2 Kunpeng 920, 24-core socket $\times$ 4, 2.6 GHz
     29\item
     30Intel Xeon Gold 5220R, 48-core socket $\times$ 2, 2.20GHz
     31\end{itemize}
     32
     33
     34\section{Existing Memory Allocators}
     35With dynamic allocation being an important feature of C, there are many stand-alone memory allocators that have been designed for different purposes. For this thesis, we chose 7 of the most popular and widely used memory allocators.
     36
     37\paragraph{dlmalloc}
     38dlmalloc (FIX ME: cite allocator) is a thread-safe allocator that is single threaded and single heap. dlmalloc maintains free-lists of different sizes to store freed dynamic memory. (FIX ME: cite wasik)
     39
     40\paragraph{hoard}
     41Hoard (FIX ME: cite allocator) is a thread-safe allocator that is multi-threaded and using a heap layer framework. It has per-thread heaps that have thread-local free-lists, and a global shared heap. (FIX ME: cite wasik)
     42
     43\paragraph{jemalloc}
     44jemalloc (FIX ME: cite allocator) is a thread-safe allocator that uses multiple arenas. Each thread is assigned an arena. Each arena has chunks that contain contagious memory regions of same size. An arena has multiple chunks that contain regions of multiple sizes.
     45
     46\paragraph{ptmalloc}
     47ptmalloc (FIX ME: cite allocator) is a modification of dlmalloc. It is a thread-safe multi-threaded memory allocator that uses multiple heaps. ptmalloc heap has similar design to dlmalloc's heap.
     48
     49\paragraph{rpmalloc}
     50rpmalloc (FIX ME: cite allocator) is a thread-safe allocator that is multi-threaded and uses per-thread heap. Each heap has multiple size-classes and each size-class contains memory regions of the relevant size.
     51
     52\paragraph{tbb malloc}
     53tbb malloc (FIX ME: cite allocator) is a thread-safe allocator that is multi-threaded and uses private heap for each thread. Each private-heap has multiple bins of different sizes. Each bin contains free regions of the same size.
     54
     55\paragraph{tc malloc}
     56tcmalloc (FIX ME: cite allocator) is a thread-safe allocator. It uses per-thread cache to store free objects that prevents contention on shared resources in multi-threaded application. A central free-list is used to refill per-thread cache when it gets empty.
     57
    2058
    2159\section{Memory Allocators}

  • doc/theses/mubeen_zulfiqar_MMath/uw-ethesis.tex

    reb3bc52 r510e6f9  
    8686\usepackage{tabularx}
    8787\usepackage{subfigure}
     88
     89\usepackage{algorithm}
     90\usepackage{algpseudocode}
    8891
    8992% Hyperlinks make it very easy to navigate an electronic document.

  • libcfa/src/concurrency/io.cfa

    reb3bc52 r510e6f9  
    175175                        /* paranoid */ verify( ! __preemption_enabled() );
    176176
    177                         ctx.proc->io.pending = false;
     177                        __atomic_store_n(&ctx.proc->io.pending, false, __ATOMIC_RELAXED);
    178178                }
    179179
    … …  
    287287        //=============================================================================================
    288288        // submission
    289         static inline void __submit( struct $io_context * ctx, __u32 idxs[], __u32 have, bool lazy) {
     289        static inline void __submit_only( struct $io_context * ctx, __u32 idxs[], __u32 have) {
    290290                // We can proceed to the fast path
    291291                // Get the right objects
    … …  
    304304                sq.to_submit += have;
    305305
    306                 ctx->proc->io.pending = true;
    307                 ctx->proc->io.dirty   = true;
     306                __atomic_store_n(&ctx->proc->io.pending, true, __ATOMIC_RELAXED);
     307                __atomic_store_n(&ctx->proc->io.dirty  , true, __ATOMIC_RELAXED);
     308        }
     309
     310        static inline void __submit( struct $io_context * ctx, __u32 idxs[], __u32 have, bool lazy) {
     311                __sub_ring_t & sq = ctx->sq;
     312                __submit_only(ctx, idxs, have);
     313
    308314                if(sq.to_submit > 30) {
    309315                        __tls_stats()->io.flush.full++;
    … …  
    402408// I/O Arbiter
    403409//=============================================================================================
    404         static inline void block(__outstanding_io_queue & queue, __outstanding_io & item) {
     410        static inline bool enqueue(__outstanding_io_queue & queue, __outstanding_io & item) {
     411                bool was_empty;
     412
    405413                // Lock the list, it's not thread safe
    406414                lock( queue.lock __cfaabi_dbg_ctx2 );
    407415                {
     416                        was_empty = empty(queue.queue);
     417
    408418                        // Add our request to the list
    409419                        add( queue.queue, item );
    … …  
    414424                unlock( queue.lock );
    415425
    416                 wait( item.sem );
     426                return was_empty;
    417427        }
    418428
    … …  
    432442                pa.want = want;
    433443
    434                 block(this.pending, (__outstanding_io&)pa);
     444                enqueue(this.pending, (__outstanding_io&)pa);
     445
     446                wait( pa.sem );
    435447
    436448                return pa.ctx;
    … …  
    485497                ei.lazy = lazy;
    486498
    487                 block(ctx->ext_sq, (__outstanding_io&)ei);
     499                bool we = enqueue(ctx->ext_sq, (__outstanding_io&)ei);
     500
     501                __atomic_store_n(&ctx->proc->io.pending, true, __ATOMIC_SEQ_CST);
     502
     503                if( we ) {
     504                        sigval_t value = { PREEMPT_IO };
     505                        pthread_sigqueue(ctx->proc->kernel_thread, SIGUSR1, value);
     506                }
     507
     508                wait( ei.sem );
    488509
    489510                __cfadbg_print_safe(io, "Kernel I/O : %u submitted from arbiter\n", have);
    … …  
    501522                                        __external_io & ei = (__external_io&)drop( ctx.ext_sq.queue );
    502523
    503                                         __submit(&ctx, ei.idxs, ei.have, ei.lazy);
     524                                        __submit_only(&ctx, ei.idxs, ei.have);
    504525
    505526                                        post( ei.sem );

  • libcfa/src/concurrency/io/setup.cfa

    reb3bc52 r510e6f9  
    5656
    5757        #include "bitmanip.hfa"
     58        #include "fstream.hfa"
    5859        #include "kernel_private.hfa"
    5960        #include "thread.hfa"
    … …  
    258259                struct __sub_ring_t & sq = this.sq;
    259260                struct __cmp_ring_t & cq = this.cq;
     261                {
     262                        __u32 fhead = sq.free_ring.head;
     263                        __u32 ftail = sq.free_ring.tail;
     264
     265                        __u32 total = *sq.num;
     266                        __u32 avail = ftail - fhead;
     267
     268                        if(avail != total) abort | "Processor (" | (void*)this.proc | ") tearing down ring with" | (total - avail) | "entries allocated but not submitted, out of" | total;
     269                }
    260270
    261271                // unmap the submit queue entries

  • libcfa/src/concurrency/io/types.hfa

    reb3bc52 r510e6f9  
    2323#include "bits/locks.hfa"
    2424#include "bits/queue.hfa"
     25#include "iofwd.hfa"
    2526#include "kernel/fwd.hfa"
    2627
    … …  
    170171        // void __ioctx_prepare_block($io_context & ctx);
    171172#endif
    172 
    173 //-----------------------------------------------------------------------
    174 // IO user data
    175 struct io_future_t {
    176         future_t self;
    177         __s32 result;
    178 };
    179 
    180 static inline {
    181         thread$ * fulfil( io_future_t & this, __s32 result, bool do_unpark = true ) {
    182                 this.result = result;
    183                 return fulfil(this.self, do_unpark);
    184         }
    185 
    186         // Wait for the future to be fulfilled
    187         bool wait     ( io_future_t & this ) { return wait     (this.self); }
    188         void reset    ( io_future_t & this ) { return reset    (this.self); }
    189         bool available( io_future_t & this ) { return available(this.self); }
    190 }

  • libcfa/src/concurrency/iofwd.hfa

    reb3bc52 r510e6f9  
    1919extern "C" {
    2020        #include <asm/types.h>
     21        #include <sys/stat.h> // needed for mode_t
    2122        #if CFA_HAVE_LINUX_IO_URING_H
    2223                #include <linux/io_uring.h>
    … …  
    2425}
    2526#include "bits/defs.hfa"
     27#include "kernel/fwd.hfa"
    2628#include "time.hfa"
    2729
    … …  
    4749
    4850struct cluster;
    49 struct io_future_t;
    5051struct $io_context;
    5152
    … …  
    5758
    5859struct io_uring_sqe;
     60
     61//-----------------------------------------------------------------------
     62// IO user data
     63struct io_future_t {
     64        future_t self;
     65        __s32 result;
     66};
     67
     68static inline {
     69        thread$ * fulfil( io_future_t & this, __s32 result, bool do_unpark = true ) {
     70                this.result = result;
     71                return fulfil(this.self, do_unpark);
     72        }
     73
     74        // Wait for the future to be fulfilled
     75        bool wait     ( io_future_t & this ) { return wait     (this.self); }
     76        void reset    ( io_future_t & this ) { return reset    (this.self); }
     77        bool available( io_future_t & this ) { return available(this.self); }
     78}
    5979
    6080//----------
    … …  
    133153// Check if a function is blocks a only the user thread
    134154bool has_user_level_blocking( fptr_t func );
     155
     156#if CFA_HAVE_LINUX_IO_URING_H
     157        static inline void zero_sqe(struct io_uring_sqe * sqe) {
     158                sqe->flags = 0;
     159                sqe->ioprio = 0;
     160                sqe->fd = 0;
     161                sqe->off = 0;
     162                sqe->addr = 0;
     163                sqe->len = 0;
     164                sqe->fsync_flags = 0;
     165                sqe->__pad2[0] = 0;
     166                sqe->__pad2[1] = 0;
     167                sqe->__pad2[2] = 0;
     168                sqe->fd = 0;
     169                sqe->off = 0;
     170                sqe->addr = 0;
     171                sqe->len = 0;
     172        }
     173#endif

  • libcfa/src/concurrency/kernel.cfa

    reb3bc52 r510e6f9  
    251251                        if( __atomic_load_n(&this->do_terminate, __ATOMIC_SEQ_CST) ) break MAIN_LOOP;
    252252
    253                         if(this->io.pending && !this->io.dirty) {
     253                        if(__atomic_load_n(&this->io.pending, __ATOMIC_RELAXED) && !__atomic_load_n(&this->io.dirty, __ATOMIC_RELAXED)) {
    254254                                __IO_STATS__(true, io.flush.dirty++; )
    255255                                __cfa_io_flush( this, 0 );

  • libcfa/src/concurrency/kernel.hfa

    reb3bc52 r510e6f9  
    9292        struct {
    9393                $io_context * ctx;
    94                 bool pending;
    95                 bool dirty;
     94                volatile bool pending;
     95                volatile bool dirty;
    9696        } io;
    9797

  • libcfa/src/concurrency/kernel/fwd.hfa

    reb3bc52 r510e6f9  
    347347                                        struct oneshot * want = expected == 0p ? 1p : 2p;
    348348                                        if(__atomic_compare_exchange_n(&this.ptr, &expected, want, false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)) {
    349                                                 if( expected == 0p ) { /* paranoid */ verify( this.ptr == 1p); return 0p; }
     349                                                if( expected == 0p ) { return 0p; }
    350350                                                thread$ * ret = post( *expected, do_unpark );
    351351                                                __atomic_store_n( &this.ptr, 1p, __ATOMIC_SEQ_CST);

  • libcfa/src/concurrency/kernel_private.hfa

    reb3bc52 r510e6f9  
    6060extern bool __preemption_enabled();
    6161
     62enum {
     63        PREEMPT_NORMAL    = 0,
     64        PREEMPT_TERMINATE = 1,
     65        PREEMPT_IO = 2,
     66};
     67
    6268static inline void __disable_interrupts_checked() {
    6369        /* paranoid */ verify( __preemption_enabled() );

  • libcfa/src/concurrency/preemption.cfa

    reb3bc52 r510e6f9  
    9696        lock{};
    9797}
    98 
    99 enum {
    100         PREEMPT_NORMAL    = 0,
    101         PREEMPT_TERMINATE = 1,
    102 };
    10398
    10499//=============================================================================================
    … …  
    664659        choose(sfp->si_value.sival_int) {
    665660                case PREEMPT_NORMAL   : ;// Normal case, nothing to do here
     661                case PREEMPT_IO       : ;// I/O asked to stop spinning, nothing to do here
    666662                case PREEMPT_TERMINATE: verify( __atomic_load_n( &__cfaabi_tls.this_processor->do_terminate, __ATOMIC_SEQ_CST ) );
    667663                default:

  • src/AST/GenericSubstitution.cpp

    reb3bc52 r510e6f9  
    4545                        visit_children = false;
    4646                        const AggregateDecl * aggr = ty->aggr();
    47                         sub = TypeSubstitution{ aggr->params.begin(), aggr->params.end(), ty->params.begin() };
     47                        sub = TypeSubstitution( aggr->params, ty->params );
    4848                }
    4949

  • src/AST/TypeSubstitution.hpp

    reb3bc52 r510e6f9  
    3737  public:
    3838        TypeSubstitution();
     39        template< typename FormalContainer, typename ActualContainer >
     40        TypeSubstitution( FormalContainer formals, ActualContainer actuals );
    3941        template< typename FormalIterator, typename ActualIterator >
    4042        TypeSubstitution( FormalIterator formalBegin, FormalIterator formalEnd, ActualIterator actualBegin );
    … …  
    7678        bool empty() const;
    7779
     80        template< typename FormalContainer, typename ActualContainer >
     81        void addAll( FormalContainer formals, ActualContainer actuals );
    7882        template< typename FormalIterator, typename ActualIterator >
    79         void add( FormalIterator formalBegin, FormalIterator formalEnd, ActualIterator actualBegin );
     83        void addAll( FormalIterator formalBegin, FormalIterator formalEnd, ActualIterator actualBegin );
    8084
    8185        /// create a new TypeSubstitution using bindings from env containing all of the type variables in expr
    … …  
    112116};
    113117
     118template< typename FormalContainer, typename ActualContainer >
     119TypeSubstitution::TypeSubstitution( FormalContainer formals, ActualContainer actuals ) {
     120        assert( formals.size() == actuals.size() );
     121        addAll( formals.begin(), formals.end(), actuals.begin() );
     122}
     123
     124template< typename FormalIterator, typename ActualIterator >
     125TypeSubstitution::TypeSubstitution( FormalIterator formalBegin, FormalIterator formalEnd, ActualIterator actualBegin ) {
     126        addAll( formalBegin, formalEnd, actualBegin );
     127}
     128
     129template< typename FormalContainer, typename ActualContainer >
     130void TypeSubstitution::addAll( FormalContainer formals, ActualContainer actuals ) {
     131        assert( formals.size() == actuals.size() );
     132        addAll( formals.begin(), formals.end(), actuals.begin() );
     133}
     134
    114135// this is the only place where type parameters outside a function formal may be substituted.
    115136template< typename FormalIterator, typename ActualIterator >
    116 void TypeSubstitution::add( FormalIterator formalBegin, FormalIterator formalEnd, ActualIterator actualBegin ) {
     137void TypeSubstitution::addAll( FormalIterator formalBegin, FormalIterator formalEnd, ActualIterator actualBegin ) {
    117138        // FormalIterator points to a TypeDecl
    118139        // ActualIterator points to a Type
    … …  
    129150                        } // if
    130151                } else {
    131                        
     152                        // Is this an error?
    132153                } // if
    133154        } // for
    134155}
    135 
    136 
    137 
    138 template< typename FormalIterator, typename ActualIterator >
    139 TypeSubstitution::TypeSubstitution( FormalIterator formalBegin, FormalIterator formalEnd, ActualIterator actualBegin ) {
    140         add( formalBegin, formalEnd, actualBegin );
    141 }
    142 
    143156
    144157} // namespace ast

  • src/Common/Examine.cc

    reb3bc52 r510e6f9  
    55// file "LICENCE" distributed with Cforall.
    66//
    7 // Examine.h --
     7// Examine.cc -- Helpers for examining AST code.
    88//
    99// Author           : Andrew Beach
    1010// Created On       : Wed Sept 2 14:02 2020
    1111// Last Modified By : Andrew Beach
    12 // Last Modified On : Wed Sep  8 12:15 2020
    13 // Update Count     : 0
     12// Last Modified On : Fri Dec 10 10:27 2021
     13// Update Count     : 1
    1414//
    1515
    1616#include "Common/Examine.h"
    1717
     18#include "AST/Type.hpp"
    1819#include "CodeGen/OperatorTable.h"
     20#include "InitTweak/InitTweak.h"
    1921
    2022DeclarationWithType * isMainFor( FunctionDecl * func, AggregateDecl::Aggregate kind ) {
    … …  
    3638
    3739namespace {
     40
     41// getTypeofThis but does some extra checks used in this module.
     42const ast::Type * getTypeofThisSolo( const ast::FunctionDecl * func ) {
     43        if ( 1 != func->params.size() ) {
     44                return nullptr;
     45        }
     46        auto ref = func->type->params.front().as<ast::ReferenceType>();
     47        return (ref) ? ref->base : nullptr;
     48}
     49
     50}
     51
     52const ast::DeclWithType * isMainFor(
     53                const ast::FunctionDecl * func, ast::AggregateDecl::Aggregate kind ) {
     54        if ( "main" != func->name ) return nullptr;
     55        if ( 1 != func->params.size() ) return nullptr;
     56
     57        auto param = func->params.front();
     58
     59        auto type = dynamic_cast<const ast::ReferenceType *>( param->get_type() );
     60        if ( !type ) return nullptr;
     61
     62        auto obj = type->base.as<ast::StructInstType>();
     63        if ( !obj ) return nullptr;
     64
     65        if ( kind != obj->base->kind ) return nullptr;
     66
     67        return param;
     68}
     69
     70namespace {
    3871        Type * getDestructorParam( FunctionDecl * func ) {
    3972                if ( !CodeGen::isDestructor( func->name ) ) return nullptr;
    … …  
    4881                return nullptr;
    4982        }
     83
     84const ast::Type * getDestructorParam( const ast::FunctionDecl * func ) {
     85        if ( !CodeGen::isDestructor( func->name ) ) return nullptr;
     86        //return InitTweak::getParamThis( func )->type;
     87        return getTypeofThisSolo( func );
     88}
     89
    5090}
    5191
    … …  
    5797        return false;
    5898}
     99
     100bool isDestructorFor(
     101                const ast::FunctionDecl * func, const ast::StructDecl * type_decl ) {
     102        if ( const ast::Type * type = getDestructorParam( func ) ) {
     103                auto stype = dynamic_cast<const ast::StructInstType *>( type );
     104                return stype && stype->base.get() == type_decl;
     105        }
     106        return false;
     107}

  • src/Common/Examine.h

    reb3bc52 r510e6f9  
    55// file "LICENCE" distributed with Cforall.
    66//
    7 // Examine.h --
     7// Examine.h -- Helpers for examining AST code.
    88//
    99// Author           : Andrew Beach
    1010// Created On       : Wed Sept 2 13:57 2020
    1111// Last Modified By : Andrew Beach
    12 // Last Modified On : Wed Sep  8 12:08 2020
    13 // Update Count     : 0
     12// Last Modified On : Fri Dec 10 10:28 2021
     13// Update Count     : 1
    1414//
    1515
     16#include "AST/Decl.hpp"
    1617#include "SynTree/Declaration.h"
    1718
    1819/// Check if this is a main function for a type of an aggregate kind.
    1920DeclarationWithType * isMainFor( FunctionDecl * func, AggregateDecl::Aggregate kind );
     21const ast::DeclWithType * isMainFor(
     22        const ast::FunctionDecl * func, ast::AggregateDecl::Aggregate kind );
    2023// Returns a pointer to the parameter if true, nullptr otherwise.
    2124
    2225/// Check if this function is a destructor for the given structure.
    2326bool isDestructorFor( FunctionDecl * func, StructDecl * type_decl );
     27bool isDestructorFor(
     28        const ast::FunctionDecl * func, const ast::StructDecl * type );

  • src/Concurrency/Keywords.cc

    reb3bc52 r510e6f9  
    422422                        ;
    423423                else if ( auto param = isMainFor( decl, cast_target ) ) {
    424                         // This should never trigger.
    425                         assert( vtable_decl );
     424                        if ( !vtable_decl ) {
     425                                SemanticError( decl, context_error );
     426                        }
    426427                        // Should be safe because of isMainFor.
    427428                        StructInstType * struct_type = static_cast<StructInstType *>(

  • src/Concurrency/KeywordsNew.cpp

    reb3bc52 r510e6f9  
    1010// Created On       : Tue Nov 16  9:53:00 2021
    1111// Last Modified By : Andrew Beach
    12 // Last Modified On : Wed Dec  1 11:24:00 2021
    13 // Update Count     : 1
     12// Last Modified On : Fri Mar 11 10:40:00 2022
     13// Update Count     : 2
    1414//
    1515
    … …  
    1818#include "AST/Copy.hpp"
    1919#include "AST/Decl.hpp"
     20#include "AST/Expr.hpp"
    2021#include "AST/Pass.hpp"
    2122#include "AST/Stmt.hpp"
     23#include "AST/DeclReplacer.hpp"
    2224#include "AST/TranslationUnit.hpp"
    2325#include "CodeGen/OperatorTable.h"
     26#include "Common/Examine.h"
    2427#include "Common/utility.h"
     28#include "ControlStruct/LabelGeneratorNew.hpp"
    2529#include "InitTweak/InitTweak.h"
     30#include "Virtual/Tables.h"
    2631
    2732namespace Concurrency {
    … …  
    2934namespace {
    3035
    31 inline static bool isThread( const ast::DeclWithType * decl ) {
     36// --------------------------------------------------------------------------
     37// Loose Helper Functions:
     38
     39/// Detect threads constructed with the keyword thread.
     40bool isThread( const ast::DeclWithType * decl ) {
    3241        auto baseType = decl->get_type()->stripDeclarator();
    3342        auto instType = dynamic_cast<const ast::StructInstType *>( baseType );
    3443        if ( nullptr == instType ) { return false; }
    3544        return instType->base->is_thread();
     45}
     46
     47/// Get the virtual type id if given a type name.
     48std::string typeIdType( std::string const & exception_name ) {
     49        return exception_name.empty() ? std::string()
     50                : Virtual::typeIdType( exception_name );
     51}
     52
     53/// Get the vtable type name if given a type name.
     54std::string vtableTypeName( std::string const & exception_name ) {
     55        return exception_name.empty() ? std::string()
     56                : Virtual::vtableTypeName( exception_name );
     57}
     58
     59static ast::Type * mutate_under_references( ast::ptr<ast::Type>& type ) {
     60        ast::Type * mutType = type.get_and_mutate();
     61        for ( ast::ReferenceType * mutRef
     62                ; (mutRef = dynamic_cast<ast::ReferenceType *>( mutType ))
     63                ; mutType = mutRef->base.get_and_mutate() );
     64        return mutType;
     65}
     66
     67// Describe that it adds the generic parameters and the uses of the generic
     68// parameters on the function and first "this" argument.
     69ast::FunctionDecl * fixupGenerics(
     70                const ast::FunctionDecl * func, const ast::StructDecl * decl ) {
     71        const CodeLocation & location = decl->location;
     72        // We have to update both the declaration
     73        auto mutFunc = ast::mutate( func );
     74        auto mutType = mutFunc->type.get_and_mutate();
     75
     76        if ( decl->params.empty() ) {
     77                return mutFunc;
     78        }
     79
     80        assert( 0 != mutFunc->params.size() );
     81        assert( 0 != mutType->params.size() );
     82
     83        // Add the "forall" clause information.
     84        for ( const ast::ptr<ast::TypeDecl> & typeParam : decl->params ) {
     85                auto typeDecl = ast::deepCopy( typeParam );
     86                mutFunc->type_params.push_back( typeDecl );
     87                mutType->forall.push_back(
     88                        new ast::TypeInstType( typeDecl->name, typeDecl ) );
     89                for ( auto & assertion : typeDecl->assertions ) {
     90                        mutFunc->assertions.push_back( assertion );
     91                        mutType->assertions.emplace_back(
     92                                new ast::VariableExpr( location, assertion ) );
     93                }
     94                typeDecl->assertions.clear();
     95        }
     96
     97        // Even chain_mutate is not powerful enough for this:
     98        ast::ptr<ast::Type>& paramType = strict_dynamic_cast<ast::ObjectDecl *>(
     99                mutFunc->params[0].get_and_mutate() )->type;
     100        auto paramTypeInst = strict_dynamic_cast<ast::StructInstType *>(
     101                mutate_under_references( paramType ) );
     102        auto typeParamInst = strict_dynamic_cast<ast::StructInstType *>(
     103                mutate_under_references( mutType->params[0] ) );
     104
     105        for ( const ast::ptr<ast::TypeDecl> & typeDecl : mutFunc->type_params ) {
     106                paramTypeInst->params.push_back(
     107                        new ast::TypeExpr( location,
     108                                new ast::TypeInstType( typeDecl->name, typeDecl ) ) );
     109                typeParamInst->params.push_back(
     110                        new ast::TypeExpr( location,
     111                                new ast::TypeInstType( typeDecl->name, typeDecl ) ) );
     112        }
     113
     114        return mutFunc;
     115}
     116
     117// --------------------------------------------------------------------------
     118struct ConcurrentSueKeyword : public ast::WithDeclsToAdd<> {
     119        ConcurrentSueKeyword(
     120                std::string&& type_name, std::string&& field_name,
     121                std::string&& getter_name, std::string&& context_error,
     122                std::string&& exception_name,
     123                bool needs_main, ast::AggregateDecl::Aggregate cast_target
     124        ) :
     125                type_name( type_name ), field_name( field_name ),
     126                getter_name( getter_name ), context_error( context_error ),
     127                exception_name( exception_name ),
     128                typeid_name( typeIdType( exception_name ) ),
     129                vtable_name( vtableTypeName( exception_name ) ),
     130                needs_main( needs_main ), cast_target( cast_target )
     131        {}
     132
     133        virtual ~ConcurrentSueKeyword() {}
     134
     135        const ast::Decl * postvisit( const ast::StructDecl * decl );
     136        const ast::DeclWithType * postvisit( const ast::FunctionDecl * decl );
     137        const ast::Expr * postvisit( const ast::KeywordCastExpr * expr );
     138
     139        struct StructAndField {
     140                const ast::StructDecl * decl;
     141                const ast::ObjectDecl * field;
     142        };
     143
     144        const ast::StructDecl * handleStruct( const ast::StructDecl * );
     145        void handleMain( const ast::FunctionDecl *, const ast::StructInstType * );
     146        void addTypeId( const ast::StructDecl * );
     147        void addVtableForward( const ast::StructDecl * );
     148        const ast::FunctionDecl * forwardDeclare( const ast::StructDecl * );
     149        StructAndField addField( const ast::StructDecl * );
     150        void addGetRoutines( const ast::ObjectDecl *, const ast::FunctionDecl * );
     151        void addLockUnlockRoutines( const ast::StructDecl * );
     152
     153private:
     154        const std::string type_name;
     155        const std::string field_name;
     156        const std::string getter_name;
     157        const std::string context_error;
     158        const std::string exception_name;
     159        const std::string typeid_name;
     160        const std::string vtable_name;
     161        const bool needs_main;
     162        const ast::AggregateDecl::Aggregate cast_target;
     163
     164        const ast::StructDecl   * type_decl = nullptr;
     165        const ast::FunctionDecl * dtor_decl = nullptr;
     166        const ast::StructDecl * except_decl = nullptr;
     167        const ast::StructDecl * typeid_decl = nullptr;
     168        const ast::StructDecl * vtable_decl = nullptr;
     169};
     170
     171// Handles thread type declarations:
     172//
     173// thread Mythread {                         struct MyThread {
     174//  int data;                                  int data;
     175//  a_struct_t more_data;                      a_struct_t more_data;
     176//                                =>             thread$ __thrd_d;
     177// };                                        };
     178//                                           static inline thread$ * get_thread( MyThread * this ) { return &this->__thrd_d; }
     179//
     180struct ThreadKeyword final : public ConcurrentSueKeyword {
     181        ThreadKeyword() : ConcurrentSueKeyword(
     182                "thread$",
     183                "__thrd",
     184                "get_thread",
     185                "thread keyword requires threads to be in scope, add #include <thread.hfa>\n",
     186                "ThreadCancelled",
     187                true,
     188                ast::AggregateDecl::Thread )
     189        {}
     190
     191        virtual ~ThreadKeyword() {}
     192};
     193
     194// Handles coroutine type declarations:
     195//
     196// coroutine MyCoroutine {                   struct MyCoroutine {
     197//  int data;                                  int data;
     198//  a_struct_t more_data;                      a_struct_t more_data;
     199//                                =>             coroutine$ __cor_d;
     200// };                                        };
     201//                                           static inline coroutine$ * get_coroutine( MyCoroutine * this ) { return &this->__cor_d; }
     202//
     203struct CoroutineKeyword final : public ConcurrentSueKeyword {
     204        CoroutineKeyword() : ConcurrentSueKeyword(
     205                "coroutine$",
     206                "__cor",
     207                "get_coroutine",
     208                "coroutine keyword requires coroutines to be in scope, add #include <coroutine.hfa>\n",
     209                "CoroutineCancelled",
     210                true,
     211                ast::AggregateDecl::Coroutine )
     212        {}
     213
     214        virtual ~CoroutineKeyword() {}
     215};
     216
     217// Handles monitor type declarations:
     218//
     219// monitor MyMonitor {                       struct MyMonitor {
     220//  int data;                                  int data;
     221//  a_struct_t more_data;                      a_struct_t more_data;
     222//                                =>             monitor$ __mon_d;
     223// };                                        };
     224//                                           static inline monitor$ * get_coroutine( MyMonitor * this ) {
     225//                                               return &this->__cor_d;
     226//                                           }
     227//                                           void lock(MyMonitor & this) {
     228//                                               lock(get_monitor(this));
     229//                                           }
     230//                                           void unlock(MyMonitor & this) {
     231//                                               unlock(get_monitor(this));
     232//                                           }
     233//
     234struct MonitorKeyword final : public ConcurrentSueKeyword {
     235        MonitorKeyword() : ConcurrentSueKeyword(
     236                "monitor$",
     237                "__mon",
     238                "get_monitor",
     239                "monitor keyword requires monitors to be in scope, add #include <monitor.hfa>\n",
     240                "",
     241                false,
     242                ast::AggregateDecl::Monitor )
     243        {}
     244
     245        virtual ~MonitorKeyword() {}
     246};
     247
     248// Handles generator type declarations:
     249//
     250// generator MyGenerator {                   struct MyGenerator {
     251//  int data;                                  int data;
     252//  a_struct_t more_data;                      a_struct_t more_data;
     253//                                =>             int __generator_state;
     254// };                                        };
     255//
     256struct GeneratorKeyword final : public ConcurrentSueKeyword {
     257        GeneratorKeyword() : ConcurrentSueKeyword(
     258                "generator$",
     259                "__generator_state",
     260                "get_generator",
     261                "Unable to find builtin type generator$\n",
     262                "",
     263                true,
     264                ast::AggregateDecl::Generator )
     265        {}
     266
     267        virtual ~GeneratorKeyword() {}
     268};
     269
     270const ast::Decl * ConcurrentSueKeyword::postvisit(
     271                const ast::StructDecl * decl ) {
     272        if ( !decl->body ) {
     273                return decl;
     274        } else if ( cast_target == decl->kind ) {
     275                return handleStruct( decl );
     276        } else if ( type_name == decl->name ) {
     277                assert( !type_decl );
     278                type_decl = decl;
     279        } else if ( exception_name == decl->name ) {
     280                assert( !except_decl );
     281                except_decl = decl;
     282        } else if ( typeid_name == decl->name ) {
     283                assert( !typeid_decl );
     284                typeid_decl = decl;
     285        } else if ( vtable_name == decl->name ) {
     286                assert( !vtable_decl );
     287                vtable_decl = decl;
     288        }
     289        return decl;
     290}
     291
     292// Try to get the full definition, but raise an error on conflicts.
     293const ast::FunctionDecl * getDefinition(
     294                const ast::FunctionDecl * old_decl,
     295                const ast::FunctionDecl * new_decl ) {
     296        if ( !new_decl->stmts ) {
     297                return old_decl;
     298        } else if ( !old_decl->stmts ) {
     299                return new_decl;
     300        } else {
     301                assert( !old_decl->stmts || !new_decl->stmts );
     302                return nullptr;
     303        }
     304}
     305
     306const ast::DeclWithType * ConcurrentSueKeyword::postvisit(
     307                const ast::FunctionDecl * decl ) {
     308        if ( type_decl && isDestructorFor( decl, type_decl ) ) {
     309                // Check for forward declarations, try to get the full definition.
     310                dtor_decl = (dtor_decl) ? getDefinition( dtor_decl, decl ) : decl;
     311        } else if ( !vtable_name.empty() && decl->has_body() ) {
     312                if (const ast::DeclWithType * param = isMainFor( decl, cast_target )) {
     313                        if ( !vtable_decl ) {
     314                                SemanticError( decl, context_error );
     315                        }
     316                        // Should be safe because of isMainFor.
     317                        const ast::StructInstType * struct_type =
     318                                static_cast<const ast::StructInstType *>(
     319                                        static_cast<const ast::ReferenceType *>(
     320                                                param->get_type() )->base.get() );
     321
     322                        handleMain( decl, struct_type );
     323                }
     324        }
     325        return decl;
     326}
     327
     328const ast::Expr * ConcurrentSueKeyword::postvisit(
     329                const ast::KeywordCastExpr * expr ) {
     330        if ( cast_target == expr->target ) {
     331                // Convert `(thread &)ex` to `(thread$ &)*get_thread(ex)`, etc.
     332                if ( !type_decl || !dtor_decl ) {
     333                        SemanticError( expr, context_error );
     334                }
     335                assert( nullptr == expr->result );
     336                auto cast = ast::mutate( expr );
     337                cast->result = new ast::ReferenceType( new ast::StructInstType( type_decl ) );
     338                cast->concrete_target.field  = field_name;
     339                cast->concrete_target.getter = getter_name;
     340                return cast;
     341        }
     342        return expr;
     343}
     344
     345const ast::StructDecl * ConcurrentSueKeyword::handleStruct(
     346                const ast::StructDecl * decl ) {
     347        assert( decl->body );
     348
     349        if ( !type_decl || !dtor_decl ) {
     350                SemanticError( decl, context_error );
     351        }
     352
     353        if ( !exception_name.empty() ) {
     354                if( !typeid_decl || !vtable_decl ) {
     355                        SemanticError( decl, context_error );
     356                }
     357                addTypeId( decl );
     358                addVtableForward( decl );
     359        }
     360
     361        const ast::FunctionDecl * func = forwardDeclare( decl );
     362        StructAndField addFieldRet = addField( decl );
     363        decl = addFieldRet.decl;
     364        const ast::ObjectDecl * field = addFieldRet.field;
     365
     366        addGetRoutines( field, func );
     367        // Add routines to monitors for use by mutex stmt.
     368        if ( ast::AggregateDecl::Monitor == cast_target ) {
     369                addLockUnlockRoutines( decl );
     370        }
     371
     372        return decl;
     373}
     374
     375void ConcurrentSueKeyword::handleMain(
     376                const ast::FunctionDecl * decl, const ast::StructInstType * type ) {
     377        assert( vtable_decl );
     378        assert( except_decl );
     379
     380        const CodeLocation & location = decl->location;
     381
     382        std::vector<ast::ptr<ast::Expr>> poly_args = {
     383                new ast::TypeExpr( location, type ),
     384        };
     385        ast::ObjectDecl * vtable_object = Virtual::makeVtableInstance(
     386                location,
     387                "_default_vtable_object_declaration",
     388                new ast::StructInstType( vtable_decl, copy( poly_args ) ),
     389                type,
     390                nullptr
     391        );
     392        declsToAddAfter.push_back( vtable_object );
     393        declsToAddAfter.push_back(
     394                new ast::ObjectDecl(
     395                        location,
     396                        Virtual::concurrentDefaultVTableName(),
     397                        new ast::ReferenceType( vtable_object->type, ast::CV::Const ),
     398                        new ast::SingleInit( location,
     399                                new ast::VariableExpr( location, vtable_object ) ),
     400                        ast::Storage::Classes(),
     401                        ast::Linkage::Cforall
     402                )
     403        );
     404        declsToAddAfter.push_back( Virtual::makeGetExceptionFunction(
     405                location,
     406                vtable_object,
     407                new ast::StructInstType( except_decl, copy( poly_args ) )
     408        ) );
     409}
     410
     411void ConcurrentSueKeyword::addTypeId( const ast::StructDecl * decl ) {
     412        assert( typeid_decl );
     413        const CodeLocation & location = decl->location;
     414
     415        ast::StructInstType * typeid_type =
     416                new ast::StructInstType( typeid_decl, ast::CV::Const );
     417        typeid_type->params.push_back(
     418                new ast::TypeExpr( location, new ast::StructInstType( decl ) ) );
     419        declsToAddBefore.push_back(
     420                Virtual::makeTypeIdInstance( location, typeid_type ) );
     421        // If the typeid_type is going to be kept, the other reference will have
     422        // been made by now, but we also get to avoid extra mutates.
     423        ast::ptr<ast::StructInstType> typeid_cleanup = typeid_type;
     424}
     425
     426void ConcurrentSueKeyword::addVtableForward( const ast::StructDecl * decl ) {
     427        assert( vtable_decl );
     428        const CodeLocation& location = decl->location;
     429
     430        std::vector<ast::ptr<ast::Expr>> poly_args = {
     431                new ast::TypeExpr( location, new ast::StructInstType( decl ) ),
     432        };
     433        declsToAddBefore.push_back( Virtual::makeGetExceptionForward(
     434                location,
     435                new ast::StructInstType( vtable_decl, copy( poly_args ) ),
     436                new ast::StructInstType( except_decl, copy( poly_args ) )
     437        ) );
     438        ast::ObjectDecl * vtable_object = Virtual::makeVtableForward(
     439                location,
     440                "_default_vtable_object_declaration",
     441                new ast::StructInstType( vtable_decl, std::move( poly_args ) )
     442        );
     443        declsToAddBefore.push_back( vtable_object );
     444        declsToAddBefore.push_back(
     445                new ast::ObjectDecl(
     446                        location,
     447                        Virtual::concurrentDefaultVTableName(),
     448                        new ast::ReferenceType( vtable_object->type, ast::CV::Const ),
     449                        nullptr,
     450                        ast::Storage::Extern,
     451                        ast::Linkage::Cforall
     452                )
     453        );
     454}
     455
     456const ast::FunctionDecl * ConcurrentSueKeyword::forwardDeclare(
     457                const ast::StructDecl * decl ) {
     458        const CodeLocation & location = decl->location;
     459
     460        ast::StructDecl * forward = ast::deepCopy( decl );
     461        {
     462                // If removing members makes ref-count go to zero, do not free.
     463                ast::ptr<ast::StructDecl> forward_ptr = forward;
     464                forward->body = false;
     465                forward->members.clear();
     466                forward_ptr.release();
     467        }
     468
     469        ast::ObjectDecl * this_decl = new ast::ObjectDecl(
     470                location,
     471                "this",
     472                new ast::ReferenceType( new ast::StructInstType( decl ) ),
     473                nullptr,
     474                ast::Storage::Classes(),
     475                ast::Linkage::Cforall
     476        );
     477
     478        ast::ObjectDecl * ret_decl = new ast::ObjectDecl(
     479                location,
     480                "ret",
     481                new ast::PointerType( new ast::StructInstType( type_decl ) ),
     482                nullptr,
     483                ast::Storage::Classes(),
     484                ast::Linkage::Cforall
     485        );
     486
     487        ast::FunctionDecl * get_decl = new ast::FunctionDecl(
     488                location,
     489                getter_name,
     490                {}, // forall
     491                { this_decl }, // params
     492                { ret_decl }, // returns
     493                nullptr, // stmts
     494                ast::Storage::Static,
     495                ast::Linkage::Cforall,
     496                { new ast::Attribute( "const" ) },
     497                ast::Function::Inline
     498        );
     499        get_decl = fixupGenerics( get_decl, decl );
     500
     501        ast::FunctionDecl * main_decl = nullptr;
     502        if ( needs_main ) {
     503                // `this_decl` is copied here because the original was used above.
     504                main_decl = new ast::FunctionDecl(
     505                        location,
     506                        "main",
     507                        {},
     508                        { ast::deepCopy( this_decl ) },
     509                        {},
     510                        nullptr,
     511                        ast::Storage::Classes(),
     512                        ast::Linkage::Cforall
     513                );
     514                main_decl = fixupGenerics( main_decl, decl );
     515        }
     516
     517        declsToAddBefore.push_back( forward );
     518        if ( needs_main ) declsToAddBefore.push_back( main_decl );
     519        declsToAddBefore.push_back( get_decl );
     520
     521        return get_decl;
     522}
     523
     524ConcurrentSueKeyword::StructAndField ConcurrentSueKeyword::addField(
     525                const ast::StructDecl * decl ) {
     526        const CodeLocation & location = decl->location;
     527
     528        ast::ObjectDecl * field = new ast::ObjectDecl(
     529                location,
     530                field_name,
     531                new ast::StructInstType( type_decl ),
     532                nullptr,
     533                ast::Storage::Classes(),
     534                ast::Linkage::Cforall
     535        );
     536
     537        auto mutDecl = ast::mutate( decl );
     538        mutDecl->members.push_back( field );
     539
     540        return {mutDecl, field};
     541}
     542
     543void ConcurrentSueKeyword::addGetRoutines(
     544                const ast::ObjectDecl * field, const ast::FunctionDecl * forward ) {
     545        // Say it is generated at the "same" places as the forward declaration.
     546        const CodeLocation & location = forward->location;
     547
     548        const ast::DeclWithType * param = forward->params.front();
     549        ast::Stmt * stmt = new ast::ReturnStmt( location,
     550                new ast::AddressExpr( location,
     551                        new ast::MemberExpr( location,
     552                                field,
     553                                new ast::CastExpr( location,
     554                                        new ast::VariableExpr( location, param ),
     555                                        ast::deepCopy( param->get_type()->stripReferences() ),
     556                                        ast::ExplicitCast
     557                                )
     558                        )
     559                )
     560        );
     561
     562        ast::FunctionDecl * decl = ast::deepCopy( forward );
     563        decl->stmts = new ast::CompoundStmt( location, { stmt } );
     564        declsToAddAfter.push_back( decl );
     565}
     566
     567void ConcurrentSueKeyword::addLockUnlockRoutines(
     568                const ast::StructDecl * decl ) {
     569        // This should only be used on monitors.
     570        assert( ast::AggregateDecl::Monitor == cast_target );
     571
     572        const CodeLocation & location = decl->location;
     573
     574        // The parameter for both routines.
     575        ast::ObjectDecl * this_decl = new ast::ObjectDecl(
     576                location,
     577                "this",
     578                new ast::ReferenceType( new ast::StructInstType( decl ) ),
     579                nullptr,
     580                ast::Storage::Classes(),
     581                ast::Linkage::Cforall
     582        );
     583
     584        ast::FunctionDecl * lock_decl = new ast::FunctionDecl(
     585                location,
     586                "lock",
     587                { /* forall */ },
     588                {
     589                        // Copy the declaration of this.
     590                        ast::deepCopy( this_decl ),
     591                },
     592                { /* returns */ },
     593                nullptr,
     594                ast::Storage::Static,
     595                ast::Linkage::Cforall,
     596                { /* attributes */ },
     597                ast::Function::Inline
     598        );
     599        lock_decl = fixupGenerics( lock_decl, decl );
     600
     601        lock_decl->stmts = new ast::CompoundStmt( location, {
     602                new ast::ExprStmt( location,
     603                        new ast::UntypedExpr( location,
     604                                new ast::NameExpr( location, "lock" ),
     605                                {
     606                                        new ast::UntypedExpr( location,
     607                                                new ast::NameExpr( location, "get_monitor" ),
     608                                                { new ast::VariableExpr( location,
     609                                                        InitTweak::getParamThis( lock_decl ) ) }
     610                                        )
     611                                }
     612                        )
     613                )
     614        } );
     615
     616        ast::FunctionDecl * unlock_decl = new ast::FunctionDecl(
     617                location,
     618                "unlock",
     619                { /* forall */ },
     620                {
     621                        // Last use, consume the declaration of this.
     622                        this_decl,
     623                },
     624                { /* returns */ },
     625                nullptr,
     626                ast::Storage::Static,
     627                ast::Linkage::Cforall,
     628                { /* attributes */ },
     629                ast::Function::Inline
     630        );
     631        unlock_decl = fixupGenerics( unlock_decl, decl );
     632
     633        unlock_decl->stmts = new ast::CompoundStmt( location, {
     634                new ast::ExprStmt( location,
     635                        new ast::UntypedExpr( location,
     636                                new ast::NameExpr( location, "unlock" ),
     637                                {
     638                                        new ast::UntypedExpr( location,
     639                                                new ast::NameExpr( location, "get_monitor" ),
     640                                                { new ast::VariableExpr( location,
     641                                                        InitTweak::getParamThis( unlock_decl ) ) }
     642                                        )
     643                                }
     644                        )
     645                )
     646        } );
     647
     648        declsToAddAfter.push_back( lock_decl );
     649        declsToAddAfter.push_back( unlock_decl );
     650}
     651
     652
     653// --------------------------------------------------------------------------
     654struct SuspendKeyword final :
     655                public ast::WithStmtsToAdd<>, public ast::WithGuards {
     656        SuspendKeyword() = default;
     657        virtual ~SuspendKeyword() = default;
     658
     659        void previsit( const ast::FunctionDecl * );
     660        const ast::DeclWithType * postvisit( const ast::FunctionDecl * );
     661        const ast::Stmt * postvisit( const ast::SuspendStmt * );
     662
     663private:
     664        bool is_real_suspend( const ast::FunctionDecl * );
     665
     666        const ast::Stmt * make_generator_suspend( const ast::SuspendStmt * );
     667        const ast::Stmt * make_coroutine_suspend( const ast::SuspendStmt * );
     668
     669        struct LabelPair {
     670                ast::Label obj;
     671                int idx;
     672        };
     673
     674        LabelPair make_label(const ast::Stmt * stmt ) {
     675                labels.push_back( ControlStruct::newLabel( "generator", stmt ) );
     676                return { labels.back(), int(labels.size()) };
     677        }
     678
     679        const ast::DeclWithType * in_generator = nullptr;
     680        const ast::FunctionDecl * decl_suspend = nullptr;
     681        std::vector<ast::Label> labels;
     682};
     683
     684void SuspendKeyword::previsit( const ast::FunctionDecl * decl ) {
     685        GuardValue( in_generator ); in_generator = nullptr;
     686
     687        // If it is the real suspend, grab it if we don't have one already.
     688        if ( is_real_suspend( decl ) ) {
     689                decl_suspend = decl_suspend ? decl_suspend : decl;
     690                return;
     691        }
     692
     693        // Otherwise check if this is a generator main and, if so, handle it.
     694        auto param = isMainFor( decl, ast::AggregateDecl::Generator );
     695        if ( !param ) return;
     696
     697        if ( 0 != decl->returns.size() ) {
     698                SemanticError( decl->location, "Generator main must return void" );
     699        }
     700
     701        in_generator = param;
     702        GuardValue( labels ); labels.clear();
     703}
     704
     705const ast::DeclWithType * SuspendKeyword::postvisit(
     706                const ast::FunctionDecl * decl ) {
     707        // Only modify a full definition of a generator with states.
     708        if ( !decl->stmts || !in_generator || labels.empty() ) return decl;
     709
     710        const CodeLocation & location = decl->location;
     711
     712        // Create a new function body:
     713        // static void * __generator_labels[] = {&&s0, &&s1, ...};
     714        // void * __generator_label = __generator_labels[GEN.__generator_state];
     715        // goto * __generator_label;
     716        // s0: ;
     717        // OLD_BODY
     718
     719        // This is the null statement inserted right before the body.
     720        ast::NullStmt * noop = new ast::NullStmt( location );
     721        noop->labels.push_back( ControlStruct::newLabel( "generator", noop ) );
     722        const ast::Label & first_label = noop->labels.back();
     723
     724        // Add each label to the init, starting with the first label.
     725        std::vector<ast::ptr<ast::Init>> inits = {
     726                new ast::SingleInit( location,
     727                        new ast::LabelAddressExpr( location, copy( first_label ) ) ) };
     728        // Then go through all the stored labels, and clear the store.
     729        for ( auto && label : labels ) {
     730                inits.push_back( new ast::SingleInit( label.location,
     731                        new ast::LabelAddressExpr( label.location, std::move( label )
     732                        ) ) );
     733        }
     734        labels.clear();
     735        // Then construct the initializer itself.
     736        auto init = new ast::ListInit( location, std::move( inits ) );
     737
     738        ast::ObjectDecl * generatorLabels = new ast::ObjectDecl(
     739                location,
     740                "__generator_labels",
     741                new ast::ArrayType(
     742                        new ast::PointerType( new ast::VoidType() ),
     743                        nullptr,
     744                        ast::FixedLen,
     745                        ast::DynamicDim
     746                ),
     747                init,
     748                ast::Storage::Classes(),
     749                ast::Linkage::AutoGen
     750        );
     751
     752        ast::ObjectDecl * generatorLabel = new ast::ObjectDecl(
     753                location,
     754                "__generator_label",
     755                new ast::PointerType( new ast::VoidType() ),
     756                new ast::SingleInit( location,
     757                        new ast::UntypedExpr( location,
     758                                new ast::NameExpr( location, "?[?]" ),
     759                                {
     760                                        // TODO: Could be a variable expr.
     761                                        new ast::NameExpr( location, "__generator_labels" ),
     762                                        new ast::UntypedMemberExpr( location,
     763                                                new ast::NameExpr( location, "__generator_state" ),
     764                                                new ast::VariableExpr( location, in_generator )
     765                                        )
     766                                }
     767                        )
     768                ),
     769                ast::Storage::Classes(),
     770                ast::Linkage::AutoGen
     771        );
     772
     773        ast::BranchStmt * theGoTo = new ast::BranchStmt(
     774                location, new ast::VariableExpr( location, generatorLabel )
     775        );
     776
     777        // The noop goes here in order.
     778
     779        ast::CompoundStmt * body = new ast::CompoundStmt( location, {
     780                { new ast::DeclStmt( location, generatorLabels ) },
     781                { new ast::DeclStmt( location, generatorLabel ) },
     782                { theGoTo },
     783                { noop },
     784                { decl->stmts },
     785        } );
     786
     787        auto mutDecl = ast::mutate( decl );
     788        mutDecl->stmts = body;
     789        return mutDecl;
     790}
     791
     792const ast::Stmt * SuspendKeyword::postvisit( const ast::SuspendStmt * stmt ) {
     793        switch ( stmt->type ) {
     794        case ast::SuspendStmt::None:
     795                // Use the context to determain the implicit target.
     796                if ( in_generator ) {
     797                        return make_generator_suspend( stmt );
     798                } else {
     799                        return make_coroutine_suspend( stmt );
     800                }
     801        case ast::SuspendStmt::Coroutine:
     802                return make_coroutine_suspend( stmt );
     803        case ast::SuspendStmt::Generator:
     804                // Generator suspends must be directly in a generator.
     805                if ( !in_generator ) SemanticError( stmt->location, "'suspend generator' must be used inside main of generator type." );
     806                return make_generator_suspend( stmt );
     807        }
     808        assert( false );
     809        return stmt;
     810}
     811
     812/// Find the real/official suspend declaration.
     813bool SuspendKeyword::is_real_suspend( const ast::FunctionDecl * decl ) {
     814        return ( !decl->linkage.is_mangled
     815                && 0 == decl->params.size()
     816                && 0 == decl->returns.size()
     817                && "__cfactx_suspend" == decl->name );
     818}
     819
     820const ast::Stmt * SuspendKeyword::make_generator_suspend(
     821                const ast::SuspendStmt * stmt ) {
     822        assert( in_generator );
     823        // Target code is:
     824        //   GEN.__generator_state = X;
     825        //   THEN
     826        //   return;
     827        //   __gen_X:;
     828
     829        const CodeLocation & location = stmt->location;
     830
     831        LabelPair label = make_label( stmt );
     832
     833        // This is the context saving statement.
     834        stmtsToAddBefore.push_back( new ast::ExprStmt( location,
     835                new ast::UntypedExpr( location,
     836                        new ast::NameExpr( location, "?=?" ),
     837                        {
     838                                new ast::UntypedMemberExpr( location,
     839                                        new ast::NameExpr( location, "__generator_state" ),
     840                                        new ast::VariableExpr( location, in_generator )
     841                                ),
     842                                ast::ConstantExpr::from_int( location, label.idx ),
     843                        }
     844                )
     845        ) );
     846
     847        // The THEN component is conditional (return is not).
     848        if ( stmt->then ) {
     849                stmtsToAddBefore.push_back( stmt->then.get() );
     850        }
     851        stmtsToAddBefore.push_back( new ast::ReturnStmt( location, nullptr ) );
     852
     853        // The null statement replaces the old suspend statement.
     854        return new ast::NullStmt( location, { label.obj } );
     855}
     856
     857const ast::Stmt * SuspendKeyword::make_coroutine_suspend(
     858                const ast::SuspendStmt * stmt ) {
     859        // The only thing we need from the old statement is the location.
     860        const CodeLocation & location = stmt->location;
     861
     862        if ( !decl_suspend ) {
     863                SemanticError( location, "suspend keyword applied to coroutines requires coroutines to be in scope, add #include <coroutine.hfa>\n" );
     864        }
     865        if ( stmt->then ) {
     866                SemanticError( location, "Compound statement following coroutines is not implemented." );
     867        }
     868
     869        return new ast::ExprStmt( location,
     870                new ast::UntypedExpr( location,
     871                        ast::VariableExpr::functionPointer( location, decl_suspend ) )
     872        );
    36873}
    37874
    … …  
    2511088                                {
    2521089                                        new ast::SingleInit( location,
    253                                                 new ast::AddressExpr(
     1090                                                new ast::AddressExpr( location,
    2541091                                                        new ast::VariableExpr( location, monitor ) ) ),
    2551092                                        new ast::SingleInit( location,
    … …  
    5641401
    5651402// --------------------------------------------------------------------------
     1403// Interface Functions:
    5661404
    5671405void implementKeywords( ast::TranslationUnit & translationUnit ) {
    568         (void)translationUnit;
    569         assertf(false, "Apply Keywords not implemented." );
     1406        ast::Pass<ThreadKeyword>::run( translationUnit );
     1407        ast::Pass<CoroutineKeyword>::run( translationUnit );
     1408        ast::Pass<MonitorKeyword>::run( translationUnit );
     1409        ast::Pass<GeneratorKeyword>::run( translationUnit );
     1410        ast::Pass<SuspendKeyword>::run( translationUnit );
    5701411}
    5711412

  • src/Validate/ForallPointerDecay.cpp

    reb3bc52 r510e6f9  
    7070                AssertionList assertions;
    7171                // Substitute trait decl parameters for instance parameters.
    72                 ast::TypeSubstitution sub(
    73                         inst->base->params.begin(),
    74                         inst->base->params.end(),
    75                         inst->params.begin()
    76                 );
     72                ast::TypeSubstitution sub( inst->base->params, inst->params );
    7773                for ( const ast::ptr<ast::Decl> & decl : inst->base->members ) {
    7874                        ast::ptr<ast::DeclWithType> copy =

  • src/Virtual/Tables.cc

    reb3bc52 r510e6f9  
    1010// Created On       : Mon Aug 31 11:11:00 2020
    1111// Last Modified By : Andrew Beach
    12 // Last Modified On : Wed Apr 21 15:36:00 2021
    13 // Update Count     : 2
    14 //
    15 
     12// Last Modified On : Fri Mar 11 10:40:00 2022
     13// Update Count     : 3
     14//
     15
     16#include "AST/Attribute.hpp"
     17#include "AST/Copy.hpp"
     18#include "AST/Decl.hpp"
     19#include "AST/Expr.hpp"
     20#include "AST/Init.hpp"
     21#include "AST/Stmt.hpp"
     22#include "AST/Type.hpp"
    1623#include <SynTree/Attribute.h>
    1724#include <SynTree/Declaration.h>
    … …  
    7784}
    7885
     86static ast::ObjectDecl * makeVtableDeclaration(
     87                CodeLocation const & location, std::string const & name,
     88                ast::StructInstType const * type, ast::Init const * init ) {
     89        ast::Storage::Classes storage;
     90        if ( nullptr == init ) {
     91                storage.is_extern = true;
     92        }
     93        return new ast::ObjectDecl(
     94                location,
     95                name,
     96                type,
     97                init,
     98                storage,
     99                ast::Linkage::Cforall
     100        );
     101}
     102
    79103ObjectDecl * makeVtableForward( std::string const & name, StructInstType * type ) {
    80104        assert( type );
    81105        return makeVtableDeclaration( name, type, nullptr );
     106}
     107
     108ast::ObjectDecl * makeVtableForward(
     109                CodeLocation const & location, std::string const & name,
     110                ast::StructInstType const * vtableType ) {
     111        assert( vtableType );
     112        return makeVtableDeclaration( location, name, vtableType, nullptr );
    82113}
    83114
    … …  
    123154}
    124155
     156static std::vector<ast::ptr<ast::Init>> buildInits(
     157                CodeLocation const & location,
     158                //std::string const & name,
     159                ast::StructInstType const * vtableType,
     160                ast::Type const * objectType ) {
     161        ast::StructDecl const * vtableStruct = vtableType->base;
     162
     163        std::vector<ast::ptr<ast::Init>> inits;
     164        inits.reserve( vtableStruct->members.size() );
     165
     166        // This is designed to run before the resolver.
     167        for ( auto field : vtableStruct->members ) {
     168                if ( std::string( "parent" ) == field->name ) {
     169                        // This will not work with polymorphic state.
     170                        auto oField = field.strict_as<ast::ObjectDecl>();
     171                        auto fieldType = oField->type.strict_as<ast::PointerType>();
     172                        auto parentType = fieldType->base.strict_as<ast::StructInstType>();
     173                        std::string const & parentInstance = instanceName( parentType->name );
     174                        inits.push_back(
     175                                        new ast::SingleInit( location, new ast::AddressExpr( new ast::NameExpr( location, parentInstance ) ) ) );
     176                } else if ( std::string( "__cfavir_typeid" ) == field->name ) {
     177                        std::string const & baseType = baseTypeName( vtableType->name );
     178                        std::string const & typeId = typeIdName( baseType );
     179                        inits.push_back( new ast::SingleInit( location, new ast::AddressExpr( new ast::NameExpr( location, typeId ) ) ) );
     180                } else if ( std::string( "size" ) == field->name ) {
     181                        inits.push_back( new ast::SingleInit( location, new ast::SizeofExpr( location, objectType )
     182                        ) );
     183                } else if ( std::string( "align" ) == field->name ) {
     184                        inits.push_back( new ast::SingleInit( location,
     185                                new ast::AlignofExpr( location, objectType )
     186                        ) );
     187                } else {
     188                        inits.push_back( new ast::SingleInit( location,
     189                                new ast::NameExpr( location, field->name )
     190                        ) );
     191                }
     192                //ast::Expr * expr = buildInitExpr(...);
     193                //inits.push_back( new ast::SingleInit( location, expr ) )
     194        }
     195
     196        return inits;
     197}
     198
     199ast::ObjectDecl * makeVtableInstance(
     200                CodeLocation const & location,
     201                std::string const & name,
     202                ast::StructInstType const * vtableType,
     203                ast::Type const * objectType,
     204                ast::Init const * init ) {
     205        assert( vtableType );
     206        assert( objectType );
     207
     208        // Build the initialization.
     209        if ( nullptr == init ) {
     210                init = new ast::ListInit( location,
     211                        buildInits( location, vtableType, objectType ) );
     212
     213        // The provided init should initialize everything except the parent
     214        // pointer, the size-of and align-of fields. These should be inserted.
     215        } else {
     216                // Except this is not yet supported.
     217                assert(false);
     218        }
     219        return makeVtableDeclaration( location, name, vtableType, init );
     220}
     221
    125222namespace {
    126223        std::string const functionName = "get_exception_vtable";
    … …  
    140237                new ReferenceType( noQualifiers, vtableType ),
    141238                nullptr,
    142         { new Attribute("unused") }
     239                { new Attribute("unused") }
    143240        ) );
    144241        type->parameters.push_back( new ObjectDecl(
    … …  
    157254                type,
    158255                nullptr
     256        );
     257}
     258
     259ast::FunctionDecl * makeGetExceptionForward(
     260                CodeLocation const & location,
     261                ast::Type const * vtableType,
     262                ast::Type const * exceptType ) {
     263        assert( vtableType );
     264        assert( exceptType );
     265        return new ast::FunctionDecl(
     266                location,
     267                functionName,
     268                { /* forall */ },
     269                { new ast::ObjectDecl(
     270                        location,
     271                        "__unused",
     272                        new ast::PointerType( exceptType )
     273                ) },
     274                { new ast::ObjectDecl(
     275                        location,
     276                        "_retvalue",
     277                        new ast::ReferenceType( vtableType )
     278                ) },
     279                nullptr,
     280                ast::Storage::Classes(),
     281                ast::Linkage::Cforall,
     282                { new ast::Attribute( "unused" ) }
    159283        );
    160284}
    … …  
    172296}
    173297
     298ast::FunctionDecl * makeGetExceptionFunction(
     299                CodeLocation const & location,
     300                ast::ObjectDecl const * vtableInstance, ast::Type const * exceptType ) {
     301        assert( vtableInstance );
     302        assert( exceptType );
     303        ast::FunctionDecl * func = makeGetExceptionForward(
     304                        location, ast::deepCopy( vtableInstance->type ), exceptType );
     305        func->stmts = new ast::CompoundStmt( location, {
     306                new ast::ReturnStmt( location, new ast::VariableExpr( location, vtableInstance ) )
     307        } );
     308        return func;
     309}
     310
    174311ObjectDecl * makeTypeIdInstance( StructInstType const * typeIdType ) {
    175312        assert( typeIdType );
    … …  
    191328}
    192329
    193 }
     330ast::ObjectDecl * makeTypeIdInstance(
     331                CodeLocation const & location,
     332                ast::StructInstType const * typeIdType ) {
     333        assert( typeIdType );
     334        ast::StructInstType * type = ast::mutate( typeIdType );
     335        type->set_const( true );
     336        std::string const & typeid_name = typeIdTypeToInstance( typeIdType->name );
     337        return new ast::ObjectDecl(
     338                location,
     339                typeid_name,
     340                type,
     341                new ast::ListInit( location, {
     342                        new ast::SingleInit( location,
     343                                new ast::AddressExpr( location,
     344                                        new ast::NameExpr( location, "__cfatid_exception_t" ) ) )
     345                } ),
     346                ast::Storage::Classes(),
     347                ast::Linkage::Cforall,
     348                nullptr,
     349                { new ast::Attribute( "cfa_linkonce" ) }
     350        );
     351}
     352
     353}

  • src/Virtual/Tables.h

    reb3bc52 r510e6f9  
    1010// Created On       : Mon Aug 31 11:07:00 2020
    1111// Last Modified By : Andrew Beach
    12 // Last Modified On : Wed Apr 21 10:30:00 2021
    13 // Update Count     : 2
     12// Last Modified On : Wec Dec  8 16:58:00 2021
     13// Update Count     : 3
    1414//
    1515
    1616#include <list>  // for list
    1717
     18#include <string>
     19#include "AST/Fwd.hpp"
    1820class Declaration;
    1921class StructDecl;
    … …  
    3537 * vtableType node is consumed.
    3638 */
     39ast::ObjectDecl * makeVtableForward(
     40        CodeLocation const & location, std::string const & name,
     41        ast::StructInstType const * vtableType );
    3742
    3843ObjectDecl * makeVtableInstance(
    … …  
    4348 * vtableType and init (if provided) nodes are consumed.
    4449 */
     50ast::ObjectDecl * makeVtableInstance(
     51        CodeLocation const & location,
     52        std::string const & name,
     53        ast::StructInstType const * vtableType,
     54        ast::Type const * objectType,
     55        ast::Init const * init = nullptr );
    4556
    4657// Some special code for how exceptions interact with virtual tables.
    … …  
    4960 * linking the vtableType to the exceptType. Both nodes are consumed.
    5061 */
     62ast::FunctionDecl * makeGetExceptionForward(
     63        CodeLocation const & location,
     64        ast::Type const * vtableType,
     65        ast::Type const * exceptType );
    5166
    5267FunctionDecl * makeGetExceptionFunction(
    … …  
    5570 * exceptType node is consumed.
    5671 */
     72ast::FunctionDecl * makeGetExceptionFunction(
     73        CodeLocation const & location,
     74        ast::ObjectDecl const * vtableInstance, ast::Type const * exceptType );
    5775
    5876ObjectDecl * makeTypeIdInstance( StructInstType const * typeIdType );
    … …  
    6078 * TODO: Should take the parent type. Currently locked to the exception_t.
    6179 */
     80ast::ObjectDecl * makeTypeIdInstance(
     81        const CodeLocation & location, ast::StructInstType const * typeIdType );
    6282
    6383}

  • src/main.cc

    reb3bc52 r510e6f9  
    1010// Created On       : Fri May 15 23:12:02 2015
    1111// Last Modified By : Andrew Beach
    12 // Last Modified On : Wed Jan 26 14:09:00 2022
    13 // Update Count     : 670
     12// Last Modified On : Fri Mar 11 10:39:00 2022
     13// Update Count     : 671
    1414//
    1515
    … …  
    333333
    334334                if( useNewAST ) {
    335                         PASS( "Implement Concurrent Keywords", Concurrency::applyKeywords( translationUnit ) );
    336                         //PASS( "Forall Pointer Decay - A", SymTab::decayForallPointersA( translationUnit ) );
    337                         //PASS( "Forall Pointer Decay - B", SymTab::decayForallPointersB( translationUnit ) );
    338                         //PASS( "Forall Pointer Decay - C", SymTab::decayForallPointersC( translationUnit ) );
    339                         //PASS( "Forall Pointer Decay - D", SymTab::decayForallPointersD( translationUnit ) );
    340335                        CodeTools::fillLocations( translationUnit );
    341336
    … …  
    347342
    348343                        forceFillCodeLocations( transUnit );
     344
     345                        PASS( "Implement Concurrent Keywords", Concurrency::implementKeywords( transUnit ) );
    349346
    350347                        // Must be after implement concurrent keywords; because uniqueIds
    … …  
    497494                        PASS( "Translate Tries" , ControlStruct::translateTries( translationUnit ) );
    498495                }
    499 
    500                
    501496
    502497                PASS( "Gen Waitfor" , Concurrency::generateWaitFor( translationUnit ) );

  • tests/Makefile.am

    reb3bc52 r510e6f9  
    6666PRETTY_PATH=mkdir -p $(dir $(abspath ${@})) && cd ${srcdir} &&
    6767
    68 .PHONY: list .validate
    69 .INTERMEDIATE: .validate .validate.cfa
     68.PHONY: list .validate .test_makeflags
     69.INTERMEDIATE: .validate .validate.cfa .test_makeflags
    7070EXTRA_PROGRAMS = avl_test linkonce .dummy_hack # build but do not install
    7171EXTRA_DIST = test.py \
    … …  
    123123        @+${TEST_PY} --list ${concurrent}
    124124
     125.test_makeflags:
     126        @echo "${MAKEFLAGS}"
     127
    125128.validate: .validate.cfa
    126129        $(CFACOMPILE) .validate.cfa -fsyntax-only -Wall -Wextra -Werror

  • tests/io/many_read.cfa

    reb3bc52 r510e6f9  
    55// file "LICENCE" distributed with Cforall.
    66//
    7 // many_read.cfa -- Make sure that multiple concurrent reads to mess up.
     7// many_read.cfa -- Make sure that multiple concurrent reads don't mess up.
    88//
    99// Author           : Thierry Delisle

  • tests/pybin/settings.py

    reb3bc52 r510e6f9  
    155155        global generating
    156156        global make
     157        global make_jobfds
    157158        global output_width
    158159        global timeout
    … …  
    168169        generating   = options.regenerate_expected
    169170        make         = ['make']
     171        make_jobfds  = []
    170172        output_width = 24
    171173        timeout      = Timeouts(options.timeout, options.global_timeout)
    … …  
    177179                os.putenv('DISTCC_LOG', os.path.join(BUILDDIR, 'distcc_error.log'))
    178180
    179 def update_make_cmd(force, jobs):
     181def update_make_cmd(flags):
    180182        global make
    181 
    182         make = ['make'] if not force else ['make', "-j%i" % jobs]
     183        make = ['make', *flags]
     184
     185def update_make_fds(r, w):
     186        global make_jobfds
     187        make_jobfds = (r, w)
    183188
    184189def validate():
    … …  
    187192        global distcc
    188193        distcc       = "DISTCC_CFA_PATH=~/.cfadistcc/%s/cfa" % tools.config_hash()
    189         errf = os.path.join(BUILDDIR, ".validate.err")
    190         make_ret, out = tools.make( ".validate", error_file = errf, output_file=subprocess.DEVNULL, error=subprocess.DEVNULL )
     194        make_ret, out, err = tools.make( ".validate", output_file=subprocess.PIPE, error=subprocess.PIPE )
    191195        if make_ret != 0:
    192                 with open (errf, "r") as myfile:
    193                         error=myfile.read()
    194196                print("ERROR: Invalid configuration %s:%s" % (arch.string, debug.string), file=sys.stderr)
    195                 print("       verify returned : \n%s" % error, file=sys.stderr)
    196                 tools.rm(errf)
     197                print("       verify returned : \n%s" % err, file=sys.stderr)
    197198                sys.exit(1)
    198 
    199         tools.rm(errf)
    200199
    201200def prep_output(tests):

  • tests/pybin/tools.py

    reb3bc52 r510e6f9  
    2323
    2424# helper functions to run terminal commands
    25 def sh(*cmd, timeout = False, output_file = None, input_file = None, input_text = None, error = subprocess.STDOUT, ignore_dry_run = False):
     25def sh(*cmd, timeout = False, output_file = None, input_file = None, input_text = None, error = subprocess.STDOUT, ignore_dry_run = False, pass_fds = []):
    2626        try:
    2727                cmd = list(cmd)
    … …  
    6565                                **({'input' : bytes(input_text, encoding='utf-8')} if input_text else {'stdin' : input_file}),
    6666                                stdout  = output_file,
    67                                 stderr  = error
     67                                stderr  = error,
     68                                pass_fds = pass_fds
    6869                        ) as proc:
    6970
    7071                                try:
    71                                         out, _ = proc.communicate(
     72                                        out, errout = proc.communicate(
    7273                                                timeout = settings.timeout.single if timeout else None
    7374                                        )
    7475
    75                                         return proc.returncode, out.decode("latin-1") if out else None
     76                                        return proc.returncode, out.decode("latin-1") if out else None, errout.decode("latin-1") if errout else None
    7677                                except subprocess.TimeoutExpired:
    7778                                        if settings.timeout2gdb:
    7879                                                print("Process {} timeout".format(proc.pid))
    7980                                                proc.communicate()
    80                                                 return 124, str(None)
     81                                                return 124, str(None), "Subprocess Timeout 2 gdb"
    8182                                        else:
    8283                                                proc.send_signal(signal.SIGABRT)
    8384                                                proc.communicate()
    84                                                 return 124, str(None)
     85                                                return 124, str(None), "Subprocess Timeout 2 gdb"
    8586
    8687        except Exception as ex:
    … …  
    105106                return (False, "No file")
    106107
    107         code, out = sh("file", fname, output_file=subprocess.PIPE)
     108        code, out, err = sh("file", fname, output_file=subprocess.PIPE)
    108109        if code != 0:
    109                 return (False, "'file EXPECT' failed with code {}".format(code))
     110                return (False, "'file EXPECT' failed with code {} '{}'".format(code, err))
    110111
    111112        match = re.search(".*: (.*)", out)
    … …  
    190191        ]
    191192        cmd = [s for s in cmd if s]
    192         return sh(*cmd, output_file=output_file, error=error)
     193        return sh(*cmd, output_file=output_file, error=error, pass_fds=settings.make_jobfds)
    193194
    194195def make_recon(target):
    … …  
    241242# move a file
    242243def mv(source, dest):
    243         ret, _ = sh("mv", source, dest)
     244        ret, _, _ = sh("mv", source, dest)
    244245        return ret
    245246
    246247# cat one file into the other
    247248def cat(source, dest):
    248         ret, _ = sh("cat", source, output_file=dest)
     249        ret, _, _ = sh("cat", source, output_file=dest)
    249250        return ret
    250251
    … …  
    289290#               system
    290291################################################################################
     292def jobserver_version():
     293        make_ret, out, err = sh('make', '.test_makeflags', '-j2', output_file=subprocess.PIPE, error=subprocess.PIPE)
     294        if make_ret != 0:
     295                print("ERROR: cannot find Makefile jobserver version", file=sys.stderr)
     296                print("       test returned : {} '{}'".format(make_ret, err), file=sys.stderr)
     297                sys.exit(1)
     298
     299        re_jobs = re.search("--jobserver-(auth|fds)", out)
     300        if not re_jobs:
     301                print("ERROR: cannot find Makefile jobserver version", file=sys.stderr)
     302                print("       MAKEFLAGS are : '{}'".format(out), file=sys.stderr)
     303                sys.exit(1)
     304
     305        return "--jobserver-{}".format(re_jobs.group(1))
     306
     307def prep_recursive_make(N):
     308        if N < 2:
     309                return []
     310
     311        # create the pipe
     312        (r, w) = os.pipe()
     313
     314        # feel it with N-1 tokens, (Why N-1 and not N, I don't know it's in the manpage for make)
     315        os.write(w, b'+' * (N - 1));
     316
     317        # prep the flags for make
     318        make_flags = ["-j{}".format(N), "--jobserver-auth={},{}".format(r, w)]
     319
     320        # tell make about the pipes
     321        os.environ["MAKEFLAGS"] = os.environ["MFLAGS"] = " ".join(make_flags)
     322
     323        # make sure pass the pipes to our children
     324        settings.update_make_fds(r, w)
     325
     326        return make_flags
     327
     328def prep_unlimited_recursive_make():
     329        # prep the flags for make
     330        make_flags = ["-j"]
     331
     332        # tell make about the pipes
     333        os.environ["MAKEFLAGS"] = os.environ["MFLAGS"] = "-j"
     334
     335        return make_flags
     336
     337
     338def eval_hardware():
     339        # we can create as many things as we want
     340        # how much hardware do we have?
     341        if settings.distribute:
     342                # remote hardware is allowed
     343                # how much do we have?
     344                ret, jstr, _ = sh("distcc", "-j", output_file=subprocess.PIPE, ignore_dry_run=True)
     345                return int(jstr.strip()) if ret == 0 else multiprocessing.cpu_count()
     346        else:
     347                # remote isn't allowed, use local cpus
     348                return multiprocessing.cpu_count()
     349
    291350# count number of jobs to create
    292 def job_count( options, tests ):
     351def job_count( options ):
    293352        # check if the user already passed in a number of jobs for multi-threading
    294         if not options.jobs:
    295                 make_flags = os.environ.get('MAKEFLAGS')
    296                 force = bool(make_flags)
    297                 make_jobs_fds = re.search("--jobserver-(auth|fds)=\s*([0-9]+),([0-9]+)", make_flags) if make_flags else None
    298                 if make_jobs_fds :
    299                         tokens = os.read(int(make_jobs_fds.group(2)), 1024)
    300                         options.jobs = len(tokens)
    301                         os.write(int(make_jobs_fds.group(3)), tokens)
    302                 else :
    303                         if settings.distribute:
    304                                 ret, jstr = sh("distcc", "-j", output_file=subprocess.PIPE, ignore_dry_run=True)
    305                                 if ret == 0:
    306                                         options.jobs = int(jstr.strip())
    307                                 else :
    308                                         options.jobs = multiprocessing.cpu_count()
    309                         else:
    310                                 options.jobs = multiprocessing.cpu_count()
     353        make_env = os.environ.get('MAKEFLAGS')
     354        make_flags = make_env.split() if make_env else None
     355        jobstr = jobserver_version()
     356
     357        if options.jobs and make_flags:
     358                print('WARNING: -j options should not be specified when called form Make', file=sys.stderr)
     359
     360        # Top level make is calling the shots, just follow
     361        if make_flags:
     362                # do we have -j and --jobserver-...
     363                jobopt = None
     364                exists_fds = None
     365                for f in make_flags:
     366                        jobopt = f if f.startswith("-j") else jobopt
     367                        exists_fds = f if f.startswith(jobstr) else exists_fds
     368
     369                # do we have limited parallelism?
     370                if exists_fds :
     371                        try:
     372                                rfd, wfd = tuple(exists_fds.split('=')[1].split(','))
     373                        except:
     374                                print("ERROR: jobserver has unrecoginzable format, was '{}'".format(exists_fds), file=sys.stderr)
     375                                sys.exit(1)
     376
     377                        # read the token pipe to count number of available tokens and restore the pipe
     378                        # this assumes the test suite script isn't invoked in parellel with something else
     379                        tokens = os.read(int(rfd), 65536)
     380                        os.write(int(wfd), tokens)
     381
     382                        # the number of tokens is off by one for obscure but well documented reason
     383                        # see man make for more details
     384                        options.jobs = len(tokens) + 1
     385
     386                # do we have unlimited parallelism?
     387                elif jobopt and jobopt != "-j1":
     388                        # check that this actually make sense
     389                        if jobopt != "-j":
     390                                print("ERROR: -j option passed by make but no {}, was '{}'".format(jobstr, jobopt), file=sys.stderr)
     391                                sys.exit(1)
     392
     393                        options.jobs = eval_hardware()
     394                        flags = prep_unlimited_recursive_make()
     395
     396
     397                # then no parallelism
     398                else:
     399                        options.jobs = 1
     400
     401                # keep all flags make passed along, except the weird 'w' which is about subdirectories
     402                flags = [f for f in make_flags if f != 'w']
     403
     404        # Arguments are calling the shots, fake the top level make
     405        elif options.jobs :
     406
     407                # make sure we have a valid number of jobs that corresponds to user input
     408                if options.jobs < 0 :
     409                        print('ERROR: Invalid number of jobs', file=sys.stderr)
     410                        sys.exit(1)
     411
     412                flags = prep_recursive_make(options.jobs)
     413
     414        # Arguments are calling the shots, fake the top level make, but 0 is a special case
     415        elif options.jobs == 0:
     416                options.jobs = eval_hardware()
     417                flags = prep_unlimited_recursive_make()
     418
     419        # No one says to run in parallel, then don't
    311420        else :
    312                 force = True
    313 
    314         # make sure we have a valid number of jobs that corresponds to user input
    315         if options.jobs <= 0 :
    316                 print('ERROR: Invalid number of jobs', file=sys.stderr)
    317                 sys.exit(1)
    318 
    319         return min( options.jobs, len(tests) ), force
     421                options.jobs = 1
     422                flags = []
     423
     424        # Make sure we call make as expected
     425        settings.update_make_cmd( flags )
     426
     427        # return the job count
     428        return options.jobs
    320429
    321430# enable core dumps for all the test children
    … …  
    334443        distcc_hash = os.path.join(settings.SRCDIR, '../tools/build/distcc_hash')
    335444        config = "%s-%s" % (settings.arch.target, settings.debug.path)
    336         _, out = sh(distcc_hash, config, output_file=subprocess.PIPE, ignore_dry_run=True)
     445        _, out, _ = sh(distcc_hash, config, output_file=subprocess.PIPE, ignore_dry_run=True)
    337446        return out.strip()
    338447
    … …  
    374483
    375484        if not os.path.isfile(core):
    376                 return 1, "ERR No core dump (limit soft: {} hard: {})".format(*resource.getrlimit(resource.RLIMIT_CORE))
     485                return 1, "ERR No core dump, expected '{}' (limit soft: {} hard: {})".format(core, *resource.getrlimit(resource.RLIMIT_CORE))
    377486
    378487        try:
    379                 return sh('gdb', '-n', path, core, '-batch', '-x', cmd, output_file=subprocess.PIPE)
     488                ret, out, err = sh('gdb', '-n', path, core, '-batch', '-x', cmd, output_file=subprocess.PIPE)
     489                if ret == 0:
     490                        return 0, out
     491                else:
     492                        return 1, err
    380493        except:
    381494                return 1, "ERR Could not read core with gdb"

  • tests/test.py

    reb3bc52 r510e6f9  
    140140        parser.add_argument('--regenerate-expected', help='Regenerate the .expect by running the specified tets, can be used with --all option', action='store_true')
    141141        parser.add_argument('--archive-errors', help='If called with a valid path, on test crashes the test script will copy the core dump and the executable to the specified path.', type=str, default='')
    142         parser.add_argument('-j', '--jobs', help='Number of tests to run simultaneously', type=int)
     142        parser.add_argument('-j', '--jobs', help='Number of tests to run simultaneously, 0 (default) for unlimited', nargs='?', const=0, type=int)
    143143        parser.add_argument('--list-comp', help='List all valide arguments', action='store_true')
    144144        parser.add_argument('--list-dist', help='List all tests for distribution', action='store_true')
    … …  
    195195        # build, skipping to next test on error
    196196        with Timed() as comp_dur:
    197                 make_ret, _ = make( test.target(), output_file=subprocess.DEVNULL, error=out_file, error_file = err_file )
     197                make_ret, _, _ = make( test.target(), output_file=subprocess.DEVNULL, error=out_file, error_file = err_file )
    198198
    199199        # ----------
    … …  
    208208                                if settings.dry_run or is_exe(exe_file):
    209209                                        # run test
    210                                         retcode, _ = sh(exe_file, output_file=out_file, input_file=in_file, timeout=True)
     210                                        retcode, _, _ = sh(exe_file, output_file=out_file, input_file=in_file, timeout=True)
    211211                                else :
    212212                                        # simply cat the result into the output
    … …  
    226226                        else :
    227227                                # fetch return code and error from the diff command
    228                                 retcode, error = diff(cmp_file, out_file)
     228                                retcode, error, _ = diff(cmp_file, out_file)
    229229
    230230                else:
    … …  
    366366                        print(os.path.relpath(t.expect(), settings.SRCDIR), end=' ')
    367367                        print(os.path.relpath(t.input() , settings.SRCDIR), end=' ')
    368                         code, out = make_recon(t.target())
     368                        code, out, err = make_recon(t.target())
    369369
    370370                        if code != 0:
    371                                 print('ERROR: recond failed for test {}'.format(t.target()), file=sys.stderr)
     371                                print('ERROR: recond failed for test {}: {} \'{}\''.format(t.target(), code, err), file=sys.stderr)
    372372                                sys.exit(1)
    373373
    … …  
    417417                        if is_empty(t.expect()):
    418418                                print('WARNING: test "{}" has empty .expect file'.format(t.target()), file=sys.stderr)
     419
     420        options.jobs = job_count( options )
    419421
    420422        # for each build configurations, run the test
    … …  
    430432                        local_tests = settings.ast.filter( tests )
    431433                        local_tests = settings.arch.filter( local_tests )
    432                         options.jobs, forceJobs = job_count( options, local_tests )
    433                         settings.update_make_cmd(forceJobs, options.jobs)
    434434
    435435                        # check the build configuration works
    436436                        settings.validate()
     437                        jobs = min(options.jobs, len(local_tests))
    437438
    438439                        # print configuration
    … …  
    440441                                'Regenerating' if settings.generating else 'Running',
    441442                                len(local_tests),
    442                                 options.jobs,
     443                                jobs,
    443444                                settings.ast.string,
    444445                                settings.arch.string,
    … …  
    450451
    451452                        # otherwise run all tests and make sure to return the correct error code
    452                         failed = run_tests(local_tests, options.jobs)
     453                        failed = run_tests(local_tests, jobs)
    453454                        if failed:
    454455                                if not settings.continue_:
Note: See TracChangeset for help on using the changeset viewer.