Changeset 61accc5


Ignore:
Timestamp:
Jun 11, 2018, 9:30:58 AM (3 years ago)
Author:
Rob Schluntz <rschlunt@…>
Branches:
aaron-thesis, arm-eh, cleanup-dtors, deferred_resn, demangler, jacob/cs343-translation, jenkins-sandbox, master, new-ast, new-ast-unique-expr, new-env, no_list, persistent-indexer, with_gc
Children:
85b2300
Parents:
c2b10fa (diff), f184ca3 (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:/u/cforall/software/cfa/cfa-cc

Files:
3 added
17 edited

Legend:

Unmodified
Added
Removed
  • doc/papers/concurrency/Paper.tex

    rc2b10fa r61accc5  
    5656\newcommand{\Textbf}[2][red]{{\color{#1}{\textbf{#2}}}}
    5757\newcommand{\Emph}[2][red]{{\color{#1}\textbf{\emph{#2}}}}
    58 \newcommand{\R}[1]{\Textbf{#1}}
    59 \newcommand{\B}[1]{{\Textbf[blue]{#1}}}
    60 \newcommand{\G}[1]{{\Textbf[OliveGreen]{#1}}}
    6158\newcommand{\uC}{$\mu$\CC}
    62 \newcommand{\cit}{\textsuperscript{[Citation Needed]}\xspace}
    63 \newcommand{\TODO}{{\Textbf{TODO}}}
     59\newcommand{\TODO}[1]{{\Textbf{#1}}}
    6460
    6561%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
     
    258254\section{Introduction}
    259255
    260 This paper provides a minimal concurrency \newterm{Abstract Program Interface} (API) that is simple, efficient and can be used to build other concurrency features.
     256This paper provides a minimal concurrency \newterm{Application Program Interface} (API) that is simple, efficient and can be used to build other concurrency features.
    261257While the simplest concurrency system is a thread and a lock, this low-level approach is hard to master.
    262258An easier approach for programmers is to support higher-level constructs as the basis of concurrency.
     
    584580\subsection{\protect\CFA's Thread Building Blocks}
    585581
    586 An important missing feature in C is threading\footnote{While the C11 standard defines a ``threads.h'' header, it is minimal and defined as optional.
     582An important missing feature in C is threading\footnote{While the C11 standard defines a \protect\lstinline@threads.h@ header, it is minimal and defined as optional.
    587583As such, library support for threading is far from widespread.
    588 At the time of writing the paper, neither \protect\lstinline|gcc| nor \protect\lstinline|clang| support ``threads.h'' in their standard libraries.}.
    589 On modern architectures, a lack of threading is unacceptable~\cite{Sutter05, Sutter05b}, and therefore existing and new programming languages must have tools for writing efficient concurrent programs to take advantage of parallelism.
     584At the time of writing the paper, neither \protect\lstinline@gcc@ nor \protect\lstinline@clang@ support \protect\lstinline@threads.h@ in their standard libraries.}.
     585In modern programming languages, a lack of threading is unacceptable~\cite{Sutter05, Sutter05b}, and therefore existing and new programming languages must have tools for writing efficient concurrent programs to take advantage of parallelism.
    590586As an extension of C, \CFA needs to express these concepts in a way that is as natural as possible to programmers familiar with imperative languages.
    591587Furthermore, because C is a system-level language, programmers expect to choose precisely which features they need and which cost they are willing to pay.
     
    625621\newbox\myboxA
    626622\begin{lrbox}{\myboxA}
    627 \begin{lstlisting}[aboveskip=0pt,belowskip=0pt]
     623\begin{cfa}[aboveskip=0pt,belowskip=0pt]
    628624`int f1, f2, state = 1;`   // single global variables
    629625int fib() {
     
    642638        }
    643639}
    644 \end{lstlisting}
     640\end{cfa}
    645641\end{lrbox}
    646642
    647643\newbox\myboxB
    648644\begin{lrbox}{\myboxB}
    649 \begin{lstlisting}[aboveskip=0pt,belowskip=0pt]
     645\begin{cfa}[aboveskip=0pt,belowskip=0pt]
    650646#define FIB_INIT `{ 0, 1 }`
    651647typedef struct { int f2, f1; } Fib;
     
    664660        }
    665661}
    666 \end{lstlisting}
     662\end{cfa}
    667663\end{lrbox}
    668664
     
    677673\newbox\myboxA
    678674\begin{lrbox}{\myboxA}
    679 \begin{lstlisting}[aboveskip=0pt,belowskip=0pt]
     675\begin{cfa}[aboveskip=0pt,belowskip=0pt]
    680676`coroutine` Fib { int fn; };
    681677void main( Fib & fib ) with( fib ) {
     
    697693        }
    698694}
    699 \end{lstlisting}
     695\end{cfa}
    700696\end{lrbox}
    701697\newbox\myboxB
    702698\begin{lrbox}{\myboxB}
    703 \begin{lstlisting}[aboveskip=0pt,belowskip=0pt]
     699\begin{cfa}[aboveskip=0pt,belowskip=0pt]
    704700`coroutine` Fib { int ret; };
    705701void main( Fib & f ) with( fib ) {
     
    721717
    722718
    723 \end{lstlisting}
     719\end{cfa}
    724720\end{lrbox}
    725721\subfloat[3 States, internal variables]{\label{f:Coroutine3States}\usebox\myboxA}
     
    769765\newbox\myboxA
    770766\begin{lrbox}{\myboxA}
    771 \begin{lstlisting}[aboveskip=0pt,belowskip=0pt]
     767\begin{cfa}[aboveskip=0pt,belowskip=0pt]
    772768`coroutine` Format {
    773769        char ch;   // used for communication
     
    801797        }
    802798}
    803 \end{lstlisting}
     799\end{cfa}
    804800\end{lrbox}
    805801
    806802\newbox\myboxB
    807803\begin{lrbox}{\myboxB}
    808 \begin{lstlisting}[aboveskip=0pt,belowskip=0pt]
     804\begin{cfa}[aboveskip=0pt,belowskip=0pt]
    809805struct Format {
    810806        char ch;
     
    838834        format( &fmt );
    839835}
    840 \end{lstlisting}
     836\end{cfa}
    841837\end{lrbox}
    842838\subfloat[\CFA Coroutine]{\label{f:CFAFmt}\usebox\myboxA}
     
    10441040};
    10451041\end{cfa}
    1046 & {\Large $\Rightarrow$} &
     1042&
     1043{\Large $\Rightarrow$}
     1044&
    10471045\begin{tabular}{@{}ccc@{}}
    10481046\begin{cfa}
     
    11421140}
    11431141\end{cfa}
    1144 A consequence of the strongly typed approach to main is that memory layout of parameters and return values to/from a thread are now explicitly specified in the \textbf{api}.
     1142A consequence of the strongly typed approach to main is that memory layout of parameters and return values to/from a thread are now explicitly specified in the \textbf{API}.
    11451143\end{comment}
    11461144
     
    14451443\label{s:InternalScheduling}
    14461444
    1447 While monitor mutual-exclusion provides safe access to shared data, the monitor data may indicate that a thread accessing it cannot proceed, \eg a bounded buffer, Figure~\ref{f:BoundedBuffer}, may be full/empty so produce/consumer threads must block.
     1445While monitor mutual-exclusion provides safe access to shared data, the monitor data may indicate that a thread accessing it cannot proceed.
     1446For example, Figure~\ref{f:GenericBoundedBuffer} shows a bounded buffer that may be full/empty so produce/consumer threads must block.
    14481447Leaving the monitor and trying again (busy waiting) is impractical for high-level programming.
    14491448Monitors eliminate busy waiting by providing internal synchronization to schedule threads needing access to the shared data, where the synchronization is blocking (threads are parked) versus spinning.
    1450 The synchronization is generally achieved with internal~\cite{Hoare74} or external~\cite[\S~2.9.2]{uC++} scheduling, where \newterm{scheduling} is defined as indicating which thread acquires the critical section next.
    1451 \newterm{Internal scheduling} is characterized by each thread entering the monitor and making an individual decision about proceeding or blocking, while \newterm{external scheduling} is characterized by an entering thread making a decision about proceeding for itself and behalf of other threads attempting entry.
     1449Synchronization is generally achieved with internal~\cite{Hoare74} or external~\cite[\S~2.9.2]{uC++} scheduling, where \newterm{scheduling} defines which thread acquires the critical section next.
     1450\newterm{Internal scheduling} is characterized by each thread entering the monitor and making an individual decision about proceeding or blocking, while \newterm{external scheduling} is characterized by an entering thread making a decision about proceeding for itself and on behalf of other threads attempting entry.
    14521451
    14531452Figure~\ref{f:BBInt} shows a \CFA bounded-buffer with internal scheduling, where producers/consumers enter the monitor, see the buffer is full/empty, and block on an appropriate condition lock, @full@/@empty@.
     
    14581457\begin{enumerate}
    14591458\item
    1460 The signalling thread leaves immediately, and the signalled thread continues.
     1459The signalling thread returns immediately, and the signalled thread continues.
    14611460\item
    1462 The signalling thread continues and the signalled thread is marked for urgent unblocking at subsequent scheduling points (exit/wait).
     1461The signalling thread continues and the signalled thread is marked for urgent unblocking at the next scheduling point (exit/wait).
    14631462\item
    1464 The signalling thread blocks but is marked for urgrent unblocking and the signalled thread continues.
     1463The signalling thread blocks but is marked for urgrent unblocking at the next scheduling point and the signalled thread continues.
    14651464\end{enumerate}
    14661465The first approach is too restrictive, as it precludes solving a reasonable class of problems (\eg dating service).
    14671466\CFA supports the next two semantics as both are useful.
    14681467Finally, while it is common to store a @condition@ as a field of the monitor, in \CFA, a @condition@ variable can be created/stored independently.
     1468Furthermore, a condition variable is tied to a \emph{group} of monitors on first use (called \newterm{branding}), which means that using internal scheduling with distinct sets of monitors requires one condition variable per set of monitors.
    14691469
    14701470\begin{figure}
     
    14721472\newbox\myboxA
    14731473\begin{lrbox}{\myboxA}
    1474 \begin{lstlisting}[aboveskip=0pt,belowskip=0pt]
     1474\begin{cfa}[aboveskip=0pt,belowskip=0pt]
    14751475forall( otype T ) { // distribute forall
    14761476        monitor Buffer {
     
    14961496        }
    14971497}
    1498 \end{lstlisting}
     1498\end{cfa}
    14991499\end{lrbox}
    15001500
    15011501\newbox\myboxB
    15021502\begin{lrbox}{\myboxB}
    1503 \begin{lstlisting}[aboveskip=0pt,belowskip=0pt]
     1503\begin{cfa}[aboveskip=0pt,belowskip=0pt]
    15041504forall( otype T ) { // distribute forall
    15051505        monitor Buffer {
     
    15251525        }
    15261526}
    1527 \end{lstlisting}
     1527\end{cfa}
    15281528\end{lrbox}
    15291529
     
    15321532\subfloat[External Scheduling]{\label{f:BBExt}\usebox\myboxB}
    15331533\caption{Generic Bounded-Buffer}
    1534 \label{f:BoundedBuffer}
     1534\label{f:GenericBoundedBuffer}
    15351535\end{figure}
    15361536
     
    15381538External scheduling is controlled by the @waitfor@ statement, which atomically blocks the calling thread, releases the monitor lock, and restricts the routine calls that can next acquire mutual exclusion.
    15391539If the buffer is full, only calls to @remove@ can acquire the buffer, and if the buffer is empty, only calls to @insert@ can acquire the buffer.
    1540 Threads making calls to routines that are currently excluded wait outside (externally) of the monitor on a calling queue.
    1541 
    1542 An important aspect of monitor implementation is barging, \ie can calling threads barge ahead of signalled threads?
     1540Threads making calls to routines that are currently excluded block outside (external) of the monitor on a calling queue, versus blocking on condition queues inside (internal) of the monitor.
     1541
     1542For internal scheduling, non-blocking signalling (as in the producer/consumer example) is used when the signaller is providing the cooperation for a waiting thread;
     1543the signaller enters the monitor and changes state, detects a waiting threads that can use the state, performs a non-blocking signal on the condition queue for the waiting thread, and exits the monitor to run concurrently.
     1544The waiter unblocks next, takes the state, and exits the monitor.
     1545Blocking signalling is the reverse, where the waiter is providing the cooperation for the signalling thread;
     1546the signaller enters the monitor, detects a waiting thread providing the necessary state, performs a blocking signal to place it on the urgent queue and unblock the waiter.
     1547The waiter changes state and exits the monitor, and the signaller unblocks next from the urgent queue to take the state.
     1548
     1549Figure~\ref{f:DatingService} shows a dating service demonstrating the two forms of signalling: non-blocking and blocking.
     1550The dating service matches girl and boy threads with matching compatibility codes so they can exchange phone numbers.
     1551A thread blocks until an appropriate partner arrives.
     1552The complexity is exchanging phone number in the monitor,
     1553While the non-barging monitor prevents a caller from stealing a phone number, the monitor mutual-exclusion property
     1554
     1555The dating service is an example of a monitor that cannot be written using external scheduling because:
     1556
     1557The example in table \ref{tbl:datingservice} highlights the difference in behaviour.
     1558As mentioned, @signal@ only transfers ownership once the current critical section exits; this behaviour requires additional synchronization when a two-way handshake is needed.
     1559To avoid this explicit synchronization, the @condition@ type offers the @signal_block@ routine, which handles the two-way handshake as shown in the example.
     1560This feature removes the need for a second condition variables and simplifies programming.
     1561Like every other monitor semantic, @signal_block@ uses barging prevention, which means mutual-exclusion is baton-passed both on the front end and the back end of the call to @signal_block@, meaning no other thread can acquire the monitor either before or after the call.
     1562
     1563\begin{figure}
     1564\centering
     1565\newbox\myboxA
     1566\begin{lrbox}{\myboxA}
     1567\begin{cfa}[aboveskip=0pt,belowskip=0pt]
     1568enum { CCodes = 20 };
     1569monitor DS {
     1570        int GirlPhNo, BoyPhNo;
     1571        condition Girls[CCodes], Boys[CCodes];
     1572        condition exchange;
     1573};
     1574int girl( DS & mutex ds, int phNo, int ccode ) {
     1575        if ( is_empty( Boys[ccode] ) ) {
     1576                wait( Girls[ccode] );
     1577                GirlPhNo = phNo;
     1578                exchange.signal();
     1579        } else {
     1580                GirlPhNo = phNo;
     1581                signal( Boys[ccode] );
     1582                exchange.wait();
     1583        } // if
     1584        return BoyPhNo;
     1585}
     1586int boy( DS & mutex ds, int phNo, int ccode ) {
     1587        // as above with boy/girl interchanged
     1588}
     1589\end{cfa}
     1590\end{lrbox}
     1591
     1592\newbox\myboxB
     1593\begin{lrbox}{\myboxB}
     1594\begin{cfa}[aboveskip=0pt,belowskip=0pt]
     1595
     1596monitor DS {
     1597        int GirlPhNo, BoyPhNo;
     1598        condition Girls[CCodes], Boys[CCodes];
     1599
     1600};
     1601int girl( DS & mutex ds, int phNo, int ccode ) {
     1602        if ( is_empty( Boys[ccode] ) ) { // no compatible
     1603                wait( Girls[ccode] ); // wait for boy
     1604                GirlPhNo = phNo; // make phone number available
     1605
     1606        } else {
     1607                GirlPhNo = phNo; // make phone number available
     1608                signal_block( Boys[ccode] ); // restart boy
     1609
     1610        } // if
     1611        return BoyPhNo;
     1612}
     1613int boy( DS & mutex ds, int phNo, int ccode ) {
     1614        // as above with boy/girl interchanged
     1615}
     1616\end{cfa}
     1617\end{lrbox}
     1618
     1619\subfloat[\lstinline@signal@]{\label{f:DatingSignal}\usebox\myboxA}
     1620\qquad
     1621\subfloat[\lstinline@signal_block@]{\label{f:DatingSignalBlock}\usebox\myboxB}
     1622\caption{Dating service. }
     1623\label{f:DatingService}
     1624\end{figure}
     1625
     1626Both internal and external scheduling extend to multiple monitors in a natural way.
     1627\begin{cquote}
     1628\begin{tabular}{@{}l@{\hspace{3\parindentlnth}}l@{}}
     1629\begin{cfa}
     1630monitor M { `condition e`; ... };
     1631void foo( M & mutex m1, M & mutex m2 ) {
     1632        ... wait( `e` ); ...   // wait( e, m1, m2 )
     1633        ... wait( `e, m1` ); ...
     1634        ... wait( `e, m2` ); ...
     1635}
     1636\end{cfa}
     1637&
     1638\begin{cfa}
     1639void rtn$\(_1\)$( M & mutex m1, M & mutex m2 );
     1640void rtn$\(_2\)$( M & mutex m1 );
     1641void bar( M & mutex m1, M & mutex m2 ) {
     1642        ... waitfor( `rtn` ); ...       // $\LstCommentStyle{waitfor( rtn\(_1\), m1, m2 )}$
     1643        ... waitfor( `rtn, m1` ); ... // $\LstCommentStyle{waitfor( rtn\(_2\), m1 )}$
     1644}
     1645\end{cfa}
     1646\end{tabular}
     1647\end{cquote}
     1648For @wait( e )@, the default semantics is to atomically block the signaller and release all acquired mutex types in the parameter list, \ie @wait( e, m1, m2 )@.
     1649To override the implicit multi-monitor wait, specific mutex parameter(s) can be specified, \eg @wait( e, m1 )@.
     1650Wait statically verifies the released monitors are the acquired mutex-parameters so unconditional release is safe.
     1651Finally, a signaller,
     1652\begin{cfa}
     1653void baz( M & mutex m1, M & mutex m2 ) {
     1654        ... signal( e ); ...
     1655}
     1656\end{cfa}
     1657must have acquired monitor locks that are greater than or equal to the number of locks for the waiting thread signalled from the front of the condition queue.
     1658In general, the signaller does not know the order of waiting threads, so in general, it must acquire the maximum number of mutex locks for the worst-case waiting thread.
     1659
     1660Similarly, for @waitfor( rtn )@, the default semantics is to atomically block the acceptor and release all acquired mutex types in the parameter list, \ie @waitfor( rtn, m1, m2 )@.
     1661To override the implicit multi-monitor wait, specific mutex parameter(s) can be specified, \eg @waitfor( rtn, m1 )@.
     1662Waitfor statically verifies the released monitors are the same as the acquired mutex-parameters of the given routine or routine pointer.
     1663To statically verify the released monitors match with the accepted routine's mutex parameters, the routine (pointer) prototype must be accessible.
     1664
     1665Given the ability to release a subset of acquired monitors can result in a \newterm{nested monitor}~\cite{Lister77} deadlock.
     1666\begin{cfa}
     1667void foo( M & mutex m1, M & mutex m2 ) {
     1668        ... wait( `e, m1` ); ...                                $\C{// release m1, keeping m2 acquired )}$
     1669void baz( M & mutex m1, M & mutex m2 ) {        $\C{// must acquire m1 and m2 )}$
     1670        ... signal( `e` ); ...
     1671\end{cfa}
     1672The @wait@ only releases @m1@ so the signalling thread cannot acquire both @m1@ and @m2@ to  enter @baz@ to get to the @signal@.
     1673While deadlock issues can occur with multiple/nesting acquisition, this issue results from the fact that locks, and by extension monitors, are not perfectly composable.
     1674
     1675Finally, an important aspect of monitor implementation is barging, \ie can calling threads barge ahead of signalled threads?
    15431676If barging is allowed, synchronization between a singller and signallee is difficult, often requiring multiple unblock/block cycles (looping around a wait rechecking if a condition is met).
    1544 \CFA scheduling does \emph{not} have barging, which simplifies synchronization among threads in the monitor.
     1677\begin{quote}
     1678However, we decree that a signal operation be followed immediately by resumption of a waiting program, without possibility of an intervening procedure call from yet a third program.
     1679It is only in this way that a waiting program has an absolute guarantee that it can acquire the resource just released by the signalling program without any danger that a third program will interpose a monitor entry and seize the resource instead.~\cite[p.~550]{Hoare74}
     1680\end{quote}
     1681\CFA scheduling \emph{precludes} barging, which simplifies synchronization among threads in the monitor and increases correctness.
     1682For example, there are no loops in either bounded buffer solution in Figure~\ref{f:GenericBoundedBuffer}.
    15451683Supporting barging prevention as well as extending internal scheduling to multiple monitors is the main source of complexity in the design and implementation of \CFA concurrency.
    15461684
    1547 Indeed, like the bulk acquire semantics, internal scheduling extends to multiple monitors in a way that is natural to the user but requires additional complexity on the implementation side.
    1548 
    1549 First, here is a simple example of internal scheduling:
    1550 
    1551 \begin{cfa}
    1552 monitor A {
    1553         condition e;
    1554 }
    1555 
    1556 void foo(A& mutex a1, A& mutex a2) {
     1685
     1686\subsection{Barging Prevention}
     1687
     1688Figure~\ref{f:BargingPrevention} shows \CFA code where bulk acquire adds complexity to the internal-signalling semantics.
     1689The complexity begins at the end of the inner @mutex@ statement, where the semantics of internal scheduling need to be extended for multiple monitors.
     1690The problem is that bulk acquire is used in the inner @mutex@ statement where one of the monitors is already acquired.
     1691When the signalling thread reaches the end of the inner @mutex@ statement, it should transfer ownership of @m1@ and @m2@ to the waiting threads to prevent barging into the outer @mutex@ statement by another thread.
     1692However, both the signalling and waiting thread W1 still need monitor @m1@.
     1693
     1694\begin{figure}
     1695\newbox\myboxA
     1696\begin{lrbox}{\myboxA}
     1697\begin{cfa}[aboveskip=0pt,belowskip=0pt]
     1698monitor M m1, m2;
     1699condition c;
     1700mutex( m1 ) { // $\LstCommentStyle{\color{red}outer}$
    15571701        ...
    1558         // Wait for cooperation from bar()
    1559         wait(a1.e);
     1702        mutex( m1, m2 ) { // $\LstCommentStyle{\color{red}inner}$
     1703                ... `signal( c )`; ...
     1704                // m1, m2 acquired
     1705        } // $\LstCommentStyle{\color{red}release m2}$
     1706        // m1 acquired
     1707} // release m1
     1708\end{cfa}
     1709\end{lrbox}
     1710
     1711\newbox\myboxB
     1712\begin{lrbox}{\myboxB}
     1713\begin{cfa}[aboveskip=0pt,belowskip=0pt]
     1714
     1715
     1716mutex( m1 ) {
    15601717        ...
    1561 }
    1562 
    1563 void bar(A& mutex a1, A& mutex a2) {
    1564         // Provide cooperation for foo()
    1565         ...
    1566         // Unblock foo
    1567         signal(a1.e);
    1568 }
    1569 \end{cfa}
    1570 
    1571 % ======================================================================
    1572 % ======================================================================
    1573 \subsection{Internal Scheduling - Multi-Monitor}
    1574 % ======================================================================
    1575 % ======================================================================
    1576 It is easy to understand the problem of multi-monitor scheduling using a series of pseudo-code examples.
    1577 Note that for simplicity in the following snippets of pseudo-code, waiting and signalling is done using an implicit condition variable, like Java built-in monitors.
    1578 Indeed, @wait@ statements always use the implicit condition variable as parameters and explicitly name the monitors (A and B) associated with the condition.
    1579 Note that in \CFA, condition variables are tied to a \emph{group} of monitors on first use (called branding), which means that using internal scheduling with distinct sets of monitors requires one condition variable per set of monitors.
    1580 The example below shows the simple case of having two threads (one for each column) and a single monitor A.
    1581 
    1582 \begin{multicols}{2}
    1583 thread 1
    1584 \begin{cfa}
    1585 acquire A
    1586         wait A
    1587 release A
    1588 \end{cfa}
    1589 
    1590 \columnbreak
    1591 
    1592 thread 2
    1593 \begin{cfa}
    1594 acquire A
    1595         signal A
    1596 release A
    1597 \end{cfa}
    1598 \end{multicols}
    1599 One thread acquires before waiting (atomically blocking and releasing A) and the other acquires before signalling.
    1600 It is important to note here that both @wait@ and @signal@ must be called with the proper monitor(s) already acquired.
    1601 This semantic is a logical requirement for barging prevention.
    1602 
    1603 A direct extension of the previous example is a bulk acquire version:
    1604 \begin{multicols}{2}
    1605 \begin{cfa}
    1606 acquire A & B
    1607         wait A & B
    1608 release A & B
    1609 \end{cfa}
    1610 \columnbreak
    1611 \begin{cfa}
    1612 acquire A & B
    1613         signal A & B
    1614 release A & B
    1615 \end{cfa}
    1616 \end{multicols}
    1617 \noindent This version uses bulk acquire (denoted using the {\sf\&} symbol), but the presence of multiple monitors does not add a particularly new meaning.
    1618 Synchronization happens between the two threads in exactly the same way and order.
    1619 The only difference is that mutual exclusion covers a group of monitors.
    1620 On the implementation side, handling multiple monitors does add a degree of complexity as the next few examples demonstrate.
    1621 
    1622 While deadlock issues can occur when nesting monitors, these issues are only a symptom of the fact that locks, and by extension monitors, are not perfectly composable.
    1623 For monitors, a well-known deadlock problem is the Nested Monitor Problem~\cite{Lister77}, which occurs when a @wait@ is made by a thread that holds more than one monitor.
    1624 For example, the following cfa-code runs into the nested-monitor problem:
    1625 \begin{multicols}{2}
    1626 \begin{cfa}
    1627 acquire A
    1628         acquire B
    1629                 wait B
    1630         release B
    1631 release A
    1632 \end{cfa}
    1633 
    1634 \columnbreak
    1635 
    1636 \begin{cfa}
    1637 acquire A
    1638         acquire B
    1639                 signal B
    1640         release B
    1641 release A
    1642 \end{cfa}
    1643 \end{multicols}
    1644 \noindent The @wait@ only releases monitor @B@ so the signalling thread cannot acquire monitor @A@ to get to the @signal@.
    1645 Attempting release of all acquired monitors at the @wait@ introduces a different set of problems, such as releasing monitor @C@, which has nothing to do with the @signal@.
    1646 
    1647 However, for monitors as for locks, it is possible to write a program using nesting without encountering any problems if nesting is done correctly.
    1648 For example, the next cfa-code snippet acquires monitors {\sf A} then {\sf B} before waiting, while only acquiring {\sf B} when signalling, effectively avoiding the Nested Monitor Problem~\cite{Lister77}.
    1649 
    1650 \begin{multicols}{2}
    1651 \begin{cfa}
    1652 acquire A
    1653         acquire B
    1654                 wait B
    1655         release B
    1656 release A
    1657 \end{cfa}
    1658 
    1659 \columnbreak
    1660 
    1661 \begin{cfa}
    1662 
    1663 acquire B
    1664         signal B
    1665 release B
    1666 
    1667 \end{cfa}
    1668 \end{multicols}
    1669 
    1670 \noindent However, this simple refactoring may not be possible, forcing more complex restructuring.
    1671 
    1672 % ======================================================================
    1673 % ======================================================================
    1674 \subsection{Internal Scheduling - In Depth}
    1675 % ======================================================================
    1676 % ======================================================================
    1677 
    1678 A larger example is presented to show complex issues for bulk acquire and its implementation options are analyzed.
    1679 Figure~\ref{f:int-bulk-cfa} shows an example where bulk acquire adds a significant layer of complexity to the internal signalling semantics, and listing \ref{f:int-bulk-cfa} shows the corresponding \CFA code to implement the cfa-code in listing \ref{f:int-bulk-cfa}.
    1680 For the purpose of translating the given cfa-code into \CFA-code, any method of introducing a monitor is acceptable, \eg @mutex@ parameters, global variables, pointer parameters, or using locals with the @mutex@ statement.
    1681 
    1682 \begin{figure}
    1683 \begin{multicols}{2}
    1684 Waiting thread
    1685 \begin{cfa}[numbers=left]
    1686 acquire A
    1687         // Code Section 1
    1688         acquire A & B
    1689                 // Code Section 2
    1690                 wait A & B
    1691                 // Code Section 3
    1692         release A & B
    1693         // Code Section 4
    1694 release A
    1695 \end{cfa}
    1696 \columnbreak
    1697 Signalling thread
    1698 \begin{cfa}[numbers=left, firstnumber=10,escapechar=|]
    1699 acquire A
    1700         // Code Section 5
    1701         acquire A & B
    1702                 // Code Section 6
    1703                 |\label{line:signal1}|signal A & B
    1704                 // Code Section 7
    1705         |\label{line:releaseFirst}|release A & B
    1706         // Code Section 8
    1707 |\label{line:lastRelease}|release A
    1708 \end{cfa}
    1709 \end{multicols}
    1710 \begin{cfa}[caption={Internal scheduling with bulk acquire},label={f:int-bulk-cfa}]
    1711 \end{cfa}
    1712 \begin{center}
    1713 \begin{cfa}[xleftmargin=.4\textwidth]
    1714 monitor A a;
    1715 monitor B b;
    1716 condition c;
    1717 \end{cfa}
    1718 \end{center}
    1719 \begin{multicols}{2}
    1720 Waiting thread
    1721 \begin{cfa}
    1722 mutex(a) {
    1723         // Code Section 1
    1724         mutex(a, b) {
    1725                 // Code Section 2
    1726                 wait(c);
    1727                 // Code Section 3
    1728         }
    1729         // Code Section 4
    1730 }
    1731 \end{cfa}
    1732 \columnbreak
    1733 Signalling thread
    1734 \begin{cfa}
    1735 mutex(a) {
    1736         // Code Section 5
    1737         mutex(a, b) {
    1738                 // Code Section 6
    1739                 signal(c);
    1740                 // Code Section 7
    1741         }
    1742         // Code Section 8
    1743 }
    1744 \end{cfa}
    1745 \end{multicols}
    1746 \begin{cfa}[caption={Equivalent \CFA code for listing \ref{f:int-bulk-cfa}},label={f:int-bulk-cfa}]
    1747 \end{cfa}
    1748 \begin{multicols}{2}
    1749 Waiter
    1750 \begin{cfa}[numbers=left]
    1751 acquire A
    1752         acquire A & B
    1753                 wait A & B
    1754         release A & B
    1755 release A
    1756 \end{cfa}
    1757 
    1758 \columnbreak
    1759 
    1760 Signaller
    1761 \begin{cfa}[numbers=left, firstnumber=6,escapechar=|]
    1762 acquire A
    1763         acquire A & B
    1764                 signal A & B
    1765         release A & B
    1766         |\label{line:secret}|// Secretly keep B here
    1767 release A
    1768 // Wakeup waiter and transfer A & B
    1769 \end{cfa}
    1770 \end{multicols}
    1771 \begin{cfa}[caption={Figure~\ref{f:int-bulk-cfa}, with delayed signalling comments},label={f:int-secret}]
    1772 \end{cfa}
     1718        mutex( m1, m2 ) {
     1719                ... `wait( c )`; // block and release m1, m2
     1720                // m1, m2 acquired
     1721        } // $\LstCommentStyle{\color{red}release m2}$
     1722        // m1 acquired
     1723} // release m1
     1724\end{cfa}
     1725\end{lrbox}
     1726
     1727\newbox\myboxC
     1728\begin{lrbox}{\myboxC}
     1729\begin{cfa}[aboveskip=0pt,belowskip=0pt]
     1730
     1731
     1732mutex( m2 ) {
     1733        ... `wait( c )`; ...
     1734        // m2 acquired
     1735} // $\LstCommentStyle{\color{red}release m2}$
     1736
     1737
     1738
     1739
     1740\end{cfa}
     1741\end{lrbox}
     1742
     1743\begin{cquote}
     1744\subfloat[Signalling Thread]{\label{f:SignallingThread}\usebox\myboxA}
     1745\hspace{2\parindentlnth}
     1746\subfloat[Waiting Thread (W1)]{\label{f:WaitingThread}\usebox\myboxB}
     1747\hspace{2\parindentlnth}
     1748\subfloat[Waiting Thread (W2)]{\label{f:OtherWaitingThread}\usebox\myboxC}
     1749\end{cquote}
     1750\caption{Barging Prevention}
     1751\label{f:BargingPrevention}
    17731752\end{figure}
    17741753
    1775 The complexity begins at code sections 4 and 8 in listing \ref{f:int-bulk-cfa}, which are where the existing semantics of internal scheduling needs to be extended for multiple monitors.
    1776 The root of the problem is that bulk acquire is used in a context where one of the monitors is already acquired, which is why it is important to define the behaviour of the previous cfa-code.
    1777 When the signaller thread reaches the location where it should ``release @A & B@'' (listing \ref{f:int-bulk-cfa} line \ref{line:releaseFirst}), it must actually transfer ownership of monitor @B@ to the waiting thread.
    1778 This ownership transfer is required in order to prevent barging into @B@ by another thread, since both the signalling and signalled threads still need monitor @A@.
    1779 There are three options:
    1780 
    1781 \subsubsection{Delaying Signals}
    1782 The obvious solution to the problem of multi-monitor scheduling is to keep ownership of all locks until the last lock is ready to be transferred.
    1783 It can be argued that that moment is when the last lock is no longer needed, because this semantics fits most closely to the behaviour of single-monitor scheduling.
    1784 This solution has the main benefit of transferring ownership of groups of monitors, which simplifies the semantics from multiple objects to a single group of objects, effectively making the existing single-monitor semantic viable by simply changing monitors to monitor groups.
    1785 This solution releases the monitors once every monitor in a group can be released.
    1786 However, since some monitors are never released (\eg the monitor of a thread), this interpretation means a group might never be released.
    1787 A more interesting interpretation is to transfer the group until all its monitors are released, which means the group is not passed further and a thread can retain its locks.
    1788 
    1789 However, listing \ref{f:int-secret} shows this solution can become much more complicated depending on what is executed while secretly holding B at line \ref{line:secret}, while avoiding the need to transfer ownership of a subset of the condition monitors.
     1754One scheduling solution is for the signaller to keep ownership of all locks until the last lock is ready to be transferred, because this semantics fits most closely to the behaviour of single-monitor scheduling.
     1755However, Figure~\ref{f:OtherWaitingThread} shows this solution is complex depending on other waiters, resulting is choices when the signaller finishes the inner mutex-statement.
     1756The singaller can retain @m2@ until completion of the outer mutex statement and pass the locks to waiter W1, or it can pass @m2@ to waiter W2 after completing the inner mutex-statement, while continuing to hold @m1@.
     1757In the latter case, waiter W2 must eventually pass @m2@ to waiter W1, which is complex because W2 may have waited before W1 so it is unaware of W1.
     1758Furthermore, there is an execution sequence where the signaller always finds waiter W2, and hence, waiter W1 starves.
     1759
     1760While a number of approaches were examined~\cite[\S~4.3]{Delisle18}, the solution chosen for \CFA is a novel techique called \newterm{partial signalling}.
     1761Signalled threads are moved to an urgent queue and the waiter at the front defines the set of monitors necessary for it to unblock.
     1762Partial signalling transfers ownership of monitors to the front waiter.
     1763When the signaller thread exits or waits in the monitor the front waiter is unblocked if all its monitors are released.
     1764This solution has the benefit that complexity is encapsulated into only two actions: passing monitors to the next owner when they should be released and conditionally waking threads if all conditions are met.
     1765
     1766\begin{comment}
    17901767Figure~\ref{f:dependency} shows a slightly different example where a third thread is waiting on monitor @A@, using a different condition variable.
    17911768Because the third thread is signalled when secretly holding @B@, the goal  becomes unreachable.
     
    18011778In both cases, the threads need to be able to distinguish, on a per monitor basis, which ones need to be released and which ones need to be transferred, which means knowing when to release a group becomes complex and inefficient (see next section) and therefore effectively precludes this approach.
    18021779
     1780
    18031781\subsubsection{Dependency graphs}
    1804 
    18051782
    18061783\begin{figure}
     
    18811858
    18821859\subsubsection{Partial Signalling} \label{partial-sig}
    1883 Finally, the solution that is chosen for \CFA is to use partial signalling.
    1884 Again using listing \ref{f:int-bulk-cfa}, the partial signalling solution transfers ownership of monitor @B@ at lines \ref{line:signal1} to the waiter but does not wake the waiting thread since it is still using monitor @A@.
    1885 Only when it reaches line \ref{line:lastRelease} does it actually wake up the waiting thread.
    1886 This solution has the benefit that complexity is encapsulated into only two actions: passing monitors to the next owner when they should be released and conditionally waking threads if all conditions are met.
    1887 This solution has a much simpler implementation than a dependency graph solving algorithms, which is why it was chosen.
    1888 Furthermore, after being fully implemented, this solution does not appear to have any significant downsides.
    1889 
    1890 Using partial signalling, listing \ref{f:dependency} can be solved easily:
    1891 \begin{itemize}
    1892         \item When thread $\gamma$ reaches line \ref{line:release-ab} it transfers monitor @B@ to thread $\alpha$ and continues to hold monitor @A@.
    1893         \item When thread $\gamma$ reaches line \ref{line:release-a}  it transfers monitor @A@ to thread $\beta$  and wakes it up.
    1894         \item When thread $\beta$  reaches line \ref{line:release-aa} it transfers monitor @A@ to thread $\alpha$ and wakes it up.
    1895 \end{itemize}
    1896 
    1897 % ======================================================================
    1898 % ======================================================================
    1899 \subsection{Signalling: Now or Later}
    1900 % ======================================================================
    1901 % ======================================================================
    1902 \begin{table}
    1903 \begin{tabular}{|c|c|}
    1904 @signal@ & @signal_block@ \\
    1905 \hline
    1906 \begin{cfa}[tabsize=3]
    1907 monitor DatingService {
    1908         // compatibility codes
    1909         enum{ CCodes = 20 };
    1910 
    1911         int girlPhoneNo
    1912         int boyPhoneNo;
    1913 };
    1914 
    1915 condition girls[CCodes];
    1916 condition boys [CCodes];
    1917 condition exchange;
    1918 
    1919 int girl(int phoneNo, int cfa) {
    1920         // no compatible boy ?
    1921         if(empty(boys[cfa])) {
    1922                 wait(girls[cfa]);               // wait for boy
    1923                 girlPhoneNo = phoneNo;          // make phone number available
    1924                 signal(exchange);               // wake boy from chair
    1925         } else {
    1926                 girlPhoneNo = phoneNo;          // make phone number available
    1927                 signal(boys[cfa]);              // wake boy
    1928                 wait(exchange);         // sit in chair
    1929         }
    1930         return boyPhoneNo;
    1931 }
    1932 int boy(int phoneNo, int cfa) {
    1933         // same as above
    1934         // with boy/girl interchanged
    1935 }
    1936 \end{cfa}&\begin{cfa}[tabsize=3]
    1937 monitor DatingService {
    1938 
    1939         enum{ CCodes = 20 };    // compatibility codes
    1940 
    1941         int girlPhoneNo;
    1942         int boyPhoneNo;
    1943 };
    1944 
    1945 condition girls[CCodes];
    1946 condition boys [CCodes];
    1947 // exchange is not needed
    1948 
    1949 int girl(int phoneNo, int cfa) {
    1950         // no compatible boy ?
    1951         if(empty(boys[cfa])) {
    1952                 wait(girls[cfa]);               // wait for boy
    1953                 girlPhoneNo = phoneNo;          // make phone number available
    1954                 signal(exchange);               // wake boy from chair
    1955         } else {
    1956                 girlPhoneNo = phoneNo;          // make phone number available
    1957                 signal_block(boys[cfa]);                // wake boy
    1958 
    1959                 // second handshake unnecessary
    1960 
    1961         }
    1962         return boyPhoneNo;
    1963 }
    1964 
    1965 int boy(int phoneNo, int cfa) {
    1966         // same as above
    1967         // with boy/girl interchanged
    1968 }
    1969 \end{cfa}
    1970 \end{tabular}
    1971 \caption{Dating service example using \protect\lstinline|signal| and \protect\lstinline|signal_block|. }
    1972 \label{tbl:datingservice}
    1973 \end{table}
    1974 An important note is that, until now, signalling a monitor was a delayed operation.
    1975 The ownership of the monitor is transferred only when the monitor would have otherwise been released, not at the point of the @signal@ statement.
    1976 However, in some cases, it may be more convenient for users to immediately transfer ownership to the thread that is waiting for cooperation, which is achieved using the @signal_block@ routine.
    1977 
    1978 The example in table \ref{tbl:datingservice} highlights the difference in behaviour.
    1979 As mentioned, @signal@ only transfers ownership once the current critical section exits; this behaviour requires additional synchronization when a two-way handshake is needed.
    1980 To avoid this explicit synchronization, the @condition@ type offers the @signal_block@ routine, which handles the two-way handshake as shown in the example.
    1981 This feature removes the need for a second condition variables and simplifies programming.
    1982 Like every other monitor semantic, @signal_block@ uses barging prevention, which means mutual-exclusion is baton-passed both on the front end and the back end of the call to @signal_block@, meaning no other thread can acquire the monitor either before or after the call.
    1983 
    1984 % ======================================================================
    1985 % ======================================================================
     1860\end{comment}
     1861
     1862
    19861863\section{External scheduling} \label{extsched}
    1987 % ======================================================================
    1988 % ======================================================================
     1864
    19891865An alternative to internal scheduling is external scheduling (see Table~\ref{tbl:sched}).
     1866
     1867\begin{comment}
    19901868\begin{table}
    19911869\begin{tabular}{|c|c|c|}
     
    20511929\label{tbl:sched}
    20521930\end{table}
     1931\end{comment}
     1932
    20531933This method is more constrained and explicit, which helps users reduce the non-deterministic nature of concurrency.
    20541934Indeed, as the following examples demonstrate, external scheduling allows users to wait for events from other threads without the concern of unrelated events occurring.
  • doc/proposals/user_conversions.md

    rc2b10fa r61accc5  
    55There is also a set of _explicit_ conversions that are only allowed through a
    66cast expression.
    7 Based on Glen's notes on conversions [1], I propose that safe and unsafe
    8 conversions be expressed as constructor variants, though I make explicit
    9 (cast) conversions a constructor variant as well rather than a dedicated
    10 operator.
     7I propose that safe, unsafe, and explicit (cast) conversions be expressed as
     8constructor variants.
    119Throughout this article, I will use the following operator names for
    1210constructors and conversion functions from `From` to `To`:
    1311
    14         void ?{} ( To*, To );            // copy constructor
    15         void ?{} ( To*, From );          // explicit constructor
    16         void ?{explicit} ( To*, From );  // explicit cast conversion
    17         void ?{safe} ( To*, From );      // implicit safe conversion
    18         void ?{unsafe} ( To*, From );    // implicit unsafe conversion
    19 
    20 [1] http://plg.uwaterloo.ca/~cforall/Conversions/index.html
    21 
    22 Glen's design made no distinction between constructors and unsafe implicit
     12        void ?{} ( To&, To );            // copy constructor
     13        void ?{} ( To&, From );          // explicit constructor
     14        void ?{explicit} ( To&, From );  // explicit cast conversion
     15        void ?{safe} ( To&, From );      // implicit safe conversion
     16        void ?{unsafe} ( To&, From );    // implicit unsafe conversion
     17
     18It has been suggested that all constructors would define unsafe implicit
    2319conversions; this is elegant, but interacts poorly with tuples.
    2420Essentially, without making this distinction, a constructor like the following
     
    2622multiplying the space of possible interpretations of all functions:
    2723
    28         void ?{}( Coord *this, int x, int y );
     24        void ?{}( Coord& this, int x, int y );
    2925
    3026That said, it would certainly be possible to make a multiple-argument implicit
     
    3228used infrequently:
    3329
    34         void ?{unsafe}( Coord *this, int x, int y );
     30        void ?{unsafe}( Coord& this, int x, int y );
    3531
    3632An alternate possibility would be to only count two-arg constructors
    37 `void ?{} ( To*, From )` as unsafe conversions; under this semantics, safe and
     33`void ?{} ( To&, From )` as unsafe conversions; under this semantics, safe and
    3834explicit conversions should also have a compiler-enforced restriction to
    3935ensure that they are two-arg functions (this restriction may be valuable
     
    4339is convertable to `To`.
    4440If user-defined conversions are not added to the language,
    45 `void ?{} ( To*, From )` may be a suitable representation, relying on
     41`void ?{} ( To&, From )` may be a suitable representation, relying on
    4642conversions on the argument types to account for transitivity.
    47 On the other hand, `To*` should perhaps match its target type exactly, so
    48 another assertion syntax specific to conversions may be required, e.g.
    49 `From -> To`.
     43Since `To&` should be an exact match on `To`, this should put all the implicit
     44conversions on the RHS.
     45On the other hand, under some models (like [1]), implicit conversions are not
     46allowed in assertion parameters, so another assertion syntax specific to
     47conversions may be required, e.g. `From -> To`.
     48It has also been suggested that, for programmer control, no implicit
     49conversions (except, possibly, for polymorphic specialization) should be
     50allowed in resolution of cast operators.
     51
     52[1] ../working/assertion_resolution.md
    5053
    5154### Constructor Idiom ###
     
    5356that we can use the full range of Cforall features for conversions, including
    5457polymorphism.
    55 Glen [1] defines a _constructor idiom_ that can be used to create chains of
    56 safe conversions without duplicating code; given a type `Safe` which members
    57 of another type `From` can be directly converted to, the constructor idiom
    58 allows us to write a conversion for any type `To` which `Safe` converts to:
    59 
    60         forall(otype To | { void ?{safe}( To*, Safe ) })
    61         void ?{safe}( To *this, From that ) {
     58In an earlier version of this proposal, Glen Ditchfield defines a
     59_constructor idiom_ that can be used to create chains of safe conversions
     60without duplicating code; given a type `Safe` which members of another type
     61`From` can be directly converted to, the constructor idiom allows us to write
     62a conversion for any type `To` which `Safe` converts to:
     63
     64        forall(otype To | { void ?{safe}( To&, Safe ) })
     65        void ?{safe}( To& this, From that ) {
    6266                Safe tmp = /* some expression involving that */;
    63                 *this = tmp; // uses assertion parameter
     67                this{ tmp }; // initialize from assertion parameter
    6468        }
    6569
     
    6771unsafe conversions.
    6872
     73Glen's original suggestion said the copy constructor for `To` should also be
     74accepted as a resolution for `void ?{safe}( To&, Safe )` (`Safe` == `To`),
     75allowing this same code to be used for the single-step conversion as well.
     76This proposal does come at the cost of an extra copy initialization of the
     77target value, though.
     78
     79Contrariwise, if a monomorphic conversion from `From` to `Safe` is written,
     80e.g:
     81
     82        void ?{safe}( Safe& this, From that ) {
     83                this{ /* some parameters involving that */ };
     84        }
     85
     86Then the code for a transitive conversion from `From` to any `To` type
     87convertable from `Safe` is written:
     88
     89        forall(otype To | { void ?{safe}( To&, Safe ) })
     90        void ?{safe}( To& this, From that ) {
     91                Safe tmp = that;  // uses monomorphic conversion
     92                this{ tmp };      // initialize from assertion parameter
     93        }
     94
     95Given the entirely-boilerplate nature of this code, but negative performance
     96implications of the unmodified constructor idiom, it might be fruitful to have
     97transitive and single step conversion operators, and let CFA build the
     98transitive conversions; some possible names:
     99
     100        void ?{safe}  (To&, From);    void ?{final safe} (To&, From);  // single-step
     101        void ?{safe*} (To&, From);    void ?{safe}       (To&, From);  // transitive
     102
    69103What selective non-use of the constructor idiom gives us is the ability to
    70104define a conversion that may only be the *last* conversion in a chain of such.
    71 Constructing a conversion graph able to unambiguously represent the full
    72 hierarchy of implicit conversions in C is provably impossible using only
    73 single-step conversions with no additional information (see Appendix A), but
    74 this mechanism is sufficiently powerful (see [1], though the design there has
    75 some minor bugs; the general idea is to use the constructor idiom to define
    76 two chains of conversions, one among the signed integral types, another among
    77 the unsigned, and to use monomorphic conversions to allow conversions between
    78 signed and unsigned integer types).
     105One use for this is to solve the problem that `explicit` conversions were
     106added to C++ for, that of conversions to `bool` chaining to become conversions
     107to any arithmetic type.
     108Another use is to unambiguously represent the full hierarchy of implicit
     109conversions in C by making sign conversions non-transitive, allowing the
     110compiler to resolve e.g. `int -> unsigned long` as
     111`int -> long -> unsigned long` over `int -> unsigned int -> unsigned long`.
     112See [2] for more details.
     113
     114[2] ../working/glen_conversions/index.html#usual
    79115
    80116### Appendix A: Partial and Total Orders ###
     
    153189convert from `int` to `unsigned long`, so we just put in a direct conversion
    154190and make the compiler smart enough to figure out the costs" - this is the
    155 approach taken by the existing compipler, but given that in a user-defined
     191approach taken by the existing compiler, but given that in a user-defined
    156192conversion proposal the users can build an arbitrary graph of conversions,
    157193this case still needs to be handled.
     
    160196exists a chain of conversions from `a` to `b` (see Appendix A for description
    161197of preorders and related constructs).
    162 This preorder corresponds roughly to a more usual type-theoretic concept of
     198This preorder roughly corresponds to a more usual type-theoretic concept of
    163199subtyping ("if I can convert `a` to `b`, `a` is a more specific type than
    164200`b`"); however, since this graph is arbitrary, it may contain cycles, so if
     
    192228and so is considered to be the nearer type.
    193229By transitivity, then, the conversion from `X` to `Y2` should be cheaper than
    194 the conversion from `X` to `W`, but in this case the `X` and `W` are
     230the conversion from `X` to `W`, but in this case the `Y2` and `W` are
    195231incomparable by the conversion preorder, so the tie is broken by the shorter
    196232path from `X` to `W` in favour of `W`, contradicting the transitivity property
  • src/Common/SemanticError.cc

    rc2b10fa r61accc5  
    1010// Created On       : Mon May 18 07:44:20 2015
    1111// Last Modified By : Peter A. Buhr
    12 // Last Modified On : Wed May 16 15:01:20 2018
    13 // Update Count     : 9
     12// Last Modified On : Thu Jun  7 08:05:26 2018
     13// Update Count     : 10
    1414//
    1515
     
    9797void SemanticError( CodeLocation location, std::string error ) {
    9898        SemanticErrorThrow = true;
    99         throw SemanticErrorException(location, error);
     99        throw SemanticErrorException( location, error );
    100100}
    101101
  • src/Parser/DeclarationNode.cc

    rc2b10fa r61accc5  
    1010// Created On       : Sat May 16 12:34:05 2015
    1111// Last Modified By : Peter A. Buhr
    12 // Last Modified On : Wed Jun  6 15:57:50 2018
    13 // Update Count     : 1076
     12// Last Modified On : Thu Jun  7 12:08:55 2018
     13// Update Count     : 1079
    1414//
    1515
     
    545545                                        type->aggregate.params->appendList( q->type->forall ); // augment forall qualifier
    546546                                } else {                                                                // not polymorphic
    547                                         type->aggregate.params = q->type->forall; // make polymorphic type
    548                                         // change implicit typedef from TYPEDEFname to TYPEGENname
    549                                         typedefTable.changeKind( *type->aggregate.name, TYPEGENname );
     547                                        type->aggregate.params = q->type->forall; // set forall qualifier
    550548                                } // if
    551549                        } else {                                                                        // not polymorphic
  • src/Parser/TypedefTable.cc

    rc2b10fa r61accc5  
    1010// Created On       : Sat May 16 15:20:13 2015
    1111// Last Modified By : Peter A. Buhr
    12 // Last Modified On : Fri Jun  1 16:54:18 2018
    13 // Update Count     : 155
     12// Last Modified On : Thu Jun  7 13:17:56 2018
     13// Update Count     : 192
    1414//
    1515
     
    1717#include "TypedefTable.h"
    1818#include <cassert>                                                                              // for assert
     19#include <iostream>
    1920
    2021#if 0
    21 #include <iostream>
    2222#define debugPrint( code ) code
    2323#else
     
    2727using namespace std;                                                                    // string, iostream
    2828
     29debugPrint(
     30static const char *kindName( int kind ) {
     31        switch ( kind ) {
     32          case IDENTIFIER: return "identifier";
     33          case TYPEDEFname: return "typedef";
     34          case TYPEGENname: return "typegen";
     35          default:
     36                cerr << "Error: cfa-cpp internal error, invalid kind of identifier" << endl;
     37                abort();
     38        } // switch
     39} // kindName
     40)
     41
    2942TypedefTable::~TypedefTable() {
    3043        if ( ! SemanticErrorThrow && kindTable.currentScope() != 0 ) {
    31                 std::cerr << "scope failure " << kindTable.currentScope() << endl;
     44                cerr << "Error: cfa-cpp internal error, scope failure " << kindTable.currentScope() << endl;
     45                abort();
    3246        } // if
    3347} // TypedefTable::~TypedefTable
     
    4458} // TypedefTable::isKind
    4559
    46 void TypedefTable::changeKind( const string & identifier, int kind ) {
    47         KindTable::iterator posn = kindTable.find( identifier );
    48         if ( posn != kindTable.end() ) posn->second = kind;     // exists => update
    49 } // TypedefTable::changeKind
    50 
    5160// SKULLDUGGERY: Generate a typedef for the aggregate name so the aggregate does not have to be qualified by
    5261// "struct". Only generate the typedef, if the name is not in use. The typedef is implicitly (silently) removed if the
    5362// name is explicitly used.
    54 void TypedefTable::makeTypedef( const string & name ) {
     63void TypedefTable::makeTypedef( const string & name, int kind ) {
     64//    Check for existence is necessary to handle:
     65//        struct Fred {};
     66//        void Fred();
     67//        void fred() {
     68//           struct Fred act; // do not add as type in this scope
     69//           Fred();
     70//        }
    5571        if ( ! typedefTable.exists( name ) ) {
    56                 typedefTable.addToEnclosingScope( name, TYPEDEFname, "MTD" );
     72                typedefTable.addToEnclosingScope( name, kind, "MTD" );
    5773        } // if
    5874} // TypedefTable::makeTypedef
    5975
    60 void TypedefTable::addToScope( const std::string & identifier, int kind, const char * locn __attribute__((unused)) ) {
     76void TypedefTable::addToScope( const string & identifier, int kind, const char * locn __attribute__((unused)) ) {
    6177        auto scope = kindTable.currentScope();
    62         debugPrint( cerr << "Adding at " << locn << " " << identifier << " as kind " << kind << " scope " << scope << endl );
     78        debugPrint( cerr << "Adding current at " << locn << " " << identifier << " as " << kindName( kind ) << " scope " << scope << endl );
    6379        auto ret = kindTable.insertAt( scope, identifier, kind );
    6480        if ( ! ret.second ) ret.first->second = kind;           // exists => update
    6581} // TypedefTable::addToScope
    6682
    67 void TypedefTable::addToEnclosingScope( const std::string & identifier, int kind, const char * locn __attribute__((unused)) ) {
     83void TypedefTable::addToEnclosingScope( const string & identifier, int kind, const char * locn __attribute__((unused)) ) {
    6884        assert( kindTable.currentScope() >= 1 );
    6985        auto scope = kindTable.currentScope() - 1;
    70         debugPrint( cerr << "Adding+1 at " << locn << " " << identifier << " as kind " << kind << " scope " << scope << endl );
     86        debugPrint( cerr << "Adding enclosing at " << locn << " " << identifier << " as " << kindName( kind ) << " scope " << scope << endl );
    7187        auto ret = kindTable.insertAt( scope, identifier, kind );
    7288        if ( ! ret.second ) ret.first->second = kind;           // exists => update
     
    93109                        debugPrint( cerr << endl << "[" << scope << "]" );
    94110                } // while
    95                 debugPrint( cerr << " " << (*i).first << ":" << (*i).second );
     111                debugPrint( cerr << " " << (*i).first << ":" << kindName( (*i).second ) );
    96112        } // for
    97113        while ( scope > 0 ) {
  • src/Parser/TypedefTable.h

    rc2b10fa r61accc5  
    1010// Created On       : Sat May 16 15:24:36 2015
    1111// Last Modified By : Peter A. Buhr
    12 // Last Modified On : Thu May 31 23:23:47 2018
    13 // Update Count     : 83
     12// Last Modified On : Thu Jun  7 12:10:17 2018
     13// Update Count     : 85
    1414//
    1515
     
    3030        bool exists( const std::string & identifier );
    3131        int isKind( const std::string & identifier ) const;
    32         void changeKind( const std::string & identifier, int kind );
    33         void makeTypedef( const std::string & name );
     32        void makeTypedef( const std::string & name, int kind = TYPEDEFname );
    3433        void addToScope( const std::string & identifier, int kind, const char * );
    3534        void addToEnclosingScope( const std::string & identifier, int kind, const char * );
  • src/Parser/lex.ll

    rc2b10fa r61accc5  
    1010 * Created On       : Sat Sep 22 08:58:10 2001
    1111 * Last Modified By : Peter A. Buhr
    12  * Last Modified On : Wed Jun  6 17:31:09 2018
    13  * Update Count     : 677
     12 * Last Modified On : Thu Jun  7 08:27:40 2018
     13 * Update Count     : 679
    1414 */
    1515
     
    452452
    453453%%
     454
    454455// ----end of lexer----
    455456
    456457void yyerror( const char * errmsg ) {
     458        SemanticErrorThrow = true;
    457459        cout << (yyfilename ? yyfilename : "*unknown file*") << ':' << yylineno << ':' << column - yyleng + 1
    458460                 << ": " << ErrorHelpers::error_str() << errmsg << " at token \"" << (yytext[0] == '\0' ? "EOF" : yytext) << '"' << endl;
  • src/Parser/parser.yy

    rc2b10fa r61accc5  
    1010// Created On       : Sat Sep  1 20:22:55 2001
    1111// Last Modified By : Peter A. Buhr
    12 // Last Modified On : Wed Jun  6 14:53:38 2018
    13 // Update Count     : 3522
     12// Last Modified On : Thu Jun  7 10:07:12 2018
     13// Update Count     : 3527
    1414//
    1515
     
    18261826        | aggregate_key attribute_list_opt no_attr_identifier
    18271827                {
    1828                         typedefTable.makeTypedef( *$3 );                        // create typedef
    1829                         if ( forall ) typedefTable.changeKind( *$3, TYPEGENname ); // possibly update
     1828                        typedefTable.makeTypedef( *$3, forall ? TYPEGENname : TYPEDEFname ); // create typedef
     1829                        //if ( forall ) typedefTable.changeKind( *$3, TYPEGENname ); // possibly update
    18301830                        forall = false;                                                         // reset
    18311831                }
     
    18341834        | aggregate_key attribute_list_opt type_name
    18351835                {
    1836                         typedefTable.makeTypedef( *$3->type->symbolic.name ); // create typedef
    1837                         if ( forall ) typedefTable.changeKind( *$3->type->symbolic.name, TYPEGENname ); // possibly update
     1836                        typedefTable.makeTypedef( *$3->type->symbolic.name, forall ? TYPEGENname : TYPEDEFname ); // create typedef
     1837                        //if ( forall ) typedefTable.changeKind( *$3->type->symbolic.name, TYPEGENname ); // possibly update
    18381838                        forall = false;                                                         // reset
    18391839                }
     
    18481848        aggregate_key attribute_list_opt no_attr_identifier
    18491849                {
    1850                         typedefTable.makeTypedef( *$3 );
    1851                         if ( forall ) typedefTable.changeKind( *$3, TYPEGENname ); // possibly update
     1850                        typedefTable.makeTypedef( *$3, forall ? TYPEGENname : TYPEDEFname );
     1851                        //if ( forall ) typedefTable.changeKind( *$3, TYPEGENname ); // possibly update
    18521852                        forall = false;                                                         // reset
    18531853                        $$ = DeclarationNode::newAggregate( $1, $3, nullptr, nullptr, false )->addQualifiers( $2 );
     
    32643264
    32653265%%
     3266
    32663267// ----end of grammar----
    32673268
  • src/libcfa/bits/locks.h

    rc2b10fa r61accc5  
    126126
    127127        struct __bin_sem_t {
    128                 int_fast8_t     counter;
    129                 pthread_mutex_t lock;
    130                 pthread_cond_t  cond;
     128                bool                    signaled;
     129                pthread_mutex_t         lock;
     130                pthread_cond_t          cond;
    131131        };
    132132
    133133        static inline void ?{}(__bin_sem_t & this) with( this ) {
    134                 counter = 0;
     134                signaled = false;
    135135                pthread_mutex_init(&lock, NULL);
    136136                pthread_cond_init (&cond, NULL);
     
    145145                verify(__cfaabi_dbg_in_kernel());
    146146                pthread_mutex_lock(&lock);
    147                 if(counter != 0) {   // this must be a loop, not if!
    148                         pthread_cond_wait(&cond, &lock);
    149                 }
    150                 counter = 1;
     147                        if(!signaled) {   // this must be a loop, not if!
     148                                pthread_cond_wait(&cond, &lock);
     149                        }
     150                        signaled = false;
    151151                pthread_mutex_unlock(&lock);
    152152        }
     
    154154        static inline void post(__bin_sem_t & this) with( this ) {
    155155                verify(__cfaabi_dbg_in_kernel());
     156
    156157                pthread_mutex_lock(&lock);
    157                 bool needs_signal = counter == 0;
    158                 counter = 1;
     158                        bool needs_signal = !signaled;
     159                        signaled = true;
    159160                pthread_mutex_unlock(&lock);
    160                 if (!needs_signal)
     161
     162                if (needs_signal)
    161163                        pthread_cond_signal(&cond);
    162                 }
     164        }
    163165#endif
  • src/libcfa/concurrency/kernel

    rc2b10fa r61accc5  
    113113        pthread_t kernel_thread;
    114114
     115        // RunThread data
     116        // Action to do after a thread is ran
     117        struct FinishAction finish;
     118
     119        // Preemption data
     120        // Node which is added in the discrete event simulaiton
     121        struct alarm_node_t * preemption_alarm;
     122
     123        // If true, a preemption was triggered in an unsafe region, the processor must preempt as soon as possible
     124        bool pending_preemption;
     125
     126        // Idle lock
     127        __bin_sem_t idleLock;
     128
    115129        // Termination
    116130        // Set to true to notify the processor should terminate
     
    119133        // Termination synchronisation
    120134        semaphore terminated;
    121 
    122         // RunThread data
    123         // Action to do after a thread is ran
    124         struct FinishAction finish;
    125 
    126         // Preemption data
    127         // Node which is added in the discrete event simulaiton
    128         struct alarm_node_t * preemption_alarm;
    129 
    130         // If true, a preemption was triggered in an unsafe region, the processor must preempt as soon as possible
    131         bool pending_preemption;
    132 
    133         // Idle lock
    134         sem_t idleLock;
    135         // __bin_sem_t idleLock;
    136135
    137136        // Link lists fields
  • src/libcfa/concurrency/kernel.c

    rc2b10fa r61accc5  
    147147        runner.proc = &this;
    148148
    149         sem_init(&idleLock, 0, 0);
     149        idleLock{};
    150150
    151151        start( &this );
     
    155155        if( ! __atomic_load_n(&do_terminate, __ATOMIC_ACQUIRE) ) {
    156156                __cfaabi_dbg_print_safe("Kernel : core %p signaling termination\n", &this);
    157                 terminate(&this);
    158                 verify( __atomic_load_n(&do_terminate, __ATOMIC_SEQ_CST) );
    159                 verify( kernelTLS.this_processor != &this);
     157
     158                __atomic_store_n(&do_terminate, true, __ATOMIC_RELAXED);
     159                wake( &this );
     160
    160161                P( terminated );
    161162                verify( kernelTLS.this_processor != &this);
    162                 pthread_join( kernel_thread, NULL );
    163         }
    164 
    165         sem_destroy(&idleLock);
     163        }
     164
     165        pthread_join( kernel_thread, NULL );
    166166}
    167167
     
    295295}
    296296
    297 // Handles spinning logic
    298 // TODO : find some strategy to put cores to sleep after some time
    299 void spin(processor * this, unsigned int * spin_count) {
    300         // (*spin_count)++;
    301         halt(this);
    302 }
    303 
    304297// KERNEL_ONLY
    305298// Context invoker for processors
     
    408401                unlock( ready_queue_lock );
    409402
    410                 if( was_empty ) {
     403                if(was_empty) {
    411404                        lock      (proc_list_lock __cfaabi_dbg_ctx2);
    412405                        if(idles) {
    413                                 wake(idles.head);
     406                                wake_fast(idles.head);
    414407                        }
    415408                        unlock    (proc_list_lock);
    416409                }
     410                else if( struct processor * idle = idles.head ) {
     411                        wake_fast(idle);
     412                }
     413
    417414        }
    418415
     
    660657
    661658void halt(processor * this) with( *this ) {
    662         verify( ! __atomic_load_n(&do_terminate, __ATOMIC_SEQ_CST) );
     659        // verify( ! __atomic_load_n(&do_terminate, __ATOMIC_SEQ_CST) );
    663660
    664661        with( *cltr ) {
     
    671668        __cfaabi_dbg_print_safe("Kernel : Processor %p ready to sleep\n", this);
    672669
    673         // #ifdef __CFA_WITH_VERIFY__
    674         //      int sval = 0;
    675         //      sem_getvalue(&this->idleLock, &sval);
    676         //      verifyf(sval < 200, "Binary semaphore reached value %d : \n", sval);
    677         // #endif
    678 
    679         verify( ! __atomic_load_n(&do_terminate, __ATOMIC_SEQ_CST) );
    680         int __attribute__((unused)) ret = sem_wait(&idleLock);
    681         // verifyf(ret >= 0 || errno == EINTR, "Sem_wait returned %d (errno %d : %s\n", ret, errno, strerror(errno));
    682 
    683         // wait( idleLock );
     670        wait( idleLock );
    684671
    685672        __cfaabi_dbg_print_safe("Kernel : Processor %p woke up and ready to run\n", this);
     
    691678                unlock    (proc_list_lock);
    692679        }
    693 }
    694 
    695 void wake(processor * this) {
    696         __cfaabi_dbg_print_safe("Kernel : Waking up processor %p\n", this);
    697         int __attribute__((unused)) ret = sem_post(&this->idleLock);
    698         // verifyf(ret >= 0 || errno == EINTR, "Sem_post returned %d (errno %d : %s\n", ret, errno, strerror(errno));
    699 
    700         // #ifdef __CFA_WITH_VERIFY__
    701         //      int sval = 0;
    702         //      sem_getvalue(&this->idleLock, &sval);
    703         //      verifyf(sval < 200, "Binary semaphore reached value %d\n", sval);
    704         // #endif
    705 
    706         // post( this->idleLock );
    707680}
    708681
  • src/libcfa/concurrency/kernel_private.h

    rc2b10fa r61accc5  
    5858void finishRunning(processor * this);
    5959void halt(processor * this);
    60 void wake(processor * this);
    61 void terminate(processor * this);
    62 void spin(processor * this, unsigned int * spin_count);
     60
     61static inline void wake_fast(processor * this) {
     62        __cfaabi_dbg_print_safe("Kernel : Waking up processor %p\n", this);
     63        post( this->idleLock );
     64}
     65
     66static inline void wake(processor * this) {
     67        disable_interrupts();
     68        wake_fast(this);
     69        enable_interrupts( __cfaabi_dbg_ctx );
     70}
    6371
    6472struct event_kernel_t {
     
    6876
    6977extern event_kernel_t * event_kernel;
    70 
    71 //extern thread_local coroutine_desc * volatile this_coroutine;
    72 //extern thread_local thread_desc *    volatile this_thread;
    73 //extern thread_local processor *      volatile this_processor;
    74 
    75 // extern volatile thread_local bool preemption_in_progress;
    76 // extern volatile thread_local bool preemption_enabled;
    77 // extern volatile thread_local unsigned short disable_preempt_count;
    7878
    7979struct __cfa_kernel_preemption_state_t {
  • src/libcfa/concurrency/preemption.c

    rc2b10fa r61accc5  
    260260static void preempt( processor * this ) {
    261261        sigval_t value = { PREEMPT_NORMAL };
    262         pthread_sigqueue( this->kernel_thread, SIGUSR1, value );
    263 }
    264 
    265 // kill wrapper : signal a processor
    266 void terminate(processor * this) {
    267         disable_interrupts();
    268         __atomic_store_n(&this->do_terminate, true, __ATOMIC_SEQ_CST);
    269         wake( this );
    270         sigval_t value = { PREEMPT_TERMINATE };
    271         enable_interrupts( __cfaabi_dbg_ctx );
    272262        pthread_sigqueue( this->kernel_thread, SIGUSR1, value );
    273263}
  • src/tests/preempt_longrun/Makefile.am

    rc2b10fa r61accc5  
    3434
    3535clean-local:
    36         rm -f ${TESTS}
     36        rm -f ${TESTS} core* out.log
    3737
    3838% : %.c ${CC}
  • src/tests/preempt_longrun/Makefile.in

    rc2b10fa r61accc5  
    878878
    879879clean-local:
    880         rm -f ${TESTS}
     880        rm -f ${TESTS} core* out.log
    881881
    882882% : %.c ${CC}
  • src/tests/preempt_longrun/enter.c

    rc2b10fa r61accc5  
    1515
    1616monitor mon_t {};
     17void foo( mon_t & mutex this ) {}
    1718
    1819mon_t mon;
    19 
    20 void foo( mon_t & mutex this ) {}
    21 
    2220thread worker_t {};
    23 
    2421void main( worker_t & this ) {
    2522        for( unsigned long i = 0; i < N; i++ ) {
     
    2825}
    2926
    30 extern "C" {
    31 static worker_t * workers;
    32 }
    33 
    3427int main(int argc, char * argv[] ) {
    3528        processor p;
    3629        {
    3730                worker_t w[7];
    38                 workers = w;
    3931        }
    4032}
  • src/tests/preempt_longrun/processor.c

    rc2b10fa r61accc5  
    1313}
    1414
    15 static const unsigned long N = 5_000ul;
     15static const unsigned long N = 50_000ul;
    1616
    1717int main(int argc, char* argv[]) {
    1818        processor * p[15];
    19         write(STDERR_FILENO, "Preparing\n", sizeof("Preparing\n"));
     19        write(STDOUT_FILENO, "Preparing\n", sizeof("Preparing\n"));
    2020        for ( int pi = 0; pi < 15; pi++ ) {
    2121                p[pi] = new();
    2222        }
    23         write(STDERR_FILENO, "Starting\n", sizeof("Starting\n"));
     23        write(STDOUT_FILENO, "Starting\n", sizeof("Starting\n"));
    2424        for ( int i = 0; i < N; i++) {
    2525                int pi = i % 15;
     
    2727                p[pi] = new();
    2828        }
    29         write(STDERR_FILENO, "Stopping\n", sizeof("Stopping\n"));
     29        write(STDOUT_FILENO, "Stopping\n", sizeof("Stopping\n"));
    3030        for ( int pi = 0; pi < 15; pi++ ) {
    3131                delete( p[pi] );
    3232        }
    33         write(STDERR_FILENO, "Done\n", sizeof("Done\n"));
     33        write(STDOUT_FILENO, "Done\n", sizeof("Done\n"));
    3434}
Note: See TracChangeset for help on using the changeset viewer.