xxx Separate select chapter?
xxx Justify inclusion of select into the language.
The Ease selection construct adds significant complexity to context implementation. This is due to the possibility of a process not wanting data that it is sent (because the select has already succeeded).
xxx Comment on whether select should be in language.
The code generated for a select statement must allow for any of the select clauses to succeed at some stage, and for execution of the code associated with the successful clause. The generated code should also allow for nested select clauses and add the minimum complexity to the code translator.
The solution arrived at involves generating a list of select clauses and then having a single function to handle selection. This function returns a clause identifier which is used to jump to the appropriate code. Labels and goto's are used extensively to modify the execution order without rearranging the source code.
For the code:
@select {
if (test) @get!(c,d) {
// Code c
}
@else {
// Code else
}
}
The generated code (formatted to make it slightly more readable) looks like:
{
_ec_select *_ec_select_req = _ec_create_request ();
_ec_reply_info _ec_rep;
if (test) {
_ec_add_request (_ec_select_req, 0,
__ease_pre_get_p (&c, (sizeof (*(d))), &(d)));
goto _ec_label_0_0_e;
{
_ec_label_0_0:
{
//Code c
}
goto _ec_label_0;
}
_ec_label_0_0_e:;
}
{
_ec_add_request (_ec_select_req, 1, _ec_select_else ());
goto _ec_label_0_1_e;
{
_ec_label_0_1:
{
//Code else
}
goto _ec_label_0;
}
_ec_label_0_1_e:;
}
switch (_ec_wait_select (_ec_select_req, &_ec_rep)) {
case 1:
goto _ec_label_0_1;
case 0:
goto _ec_label_0_0;
};
_ec_label_0:;
}
Initially, the jumps acheived using the
_ec_label_n_n_e labels were acheived by preceeding the block with
if (0). However, at least one compiler (the AT&T C++ compiler),
discards all code in such a block even though it may be jumped to using
a goto.
To assist in reading the above, the following transformed code gives the sequence of code execution:
{
_ec_select *_ec_select_req = _ec_create_request ();
_ec_reply_info _ec_rep;
if (test) {
_ec_add_request (_ec_select_req, 0,
__ease_pre_get_p (&c, (sizeof (*(d))), &(d)));
}
_ec_add_request (_ec_select_req, 1, _ec_select_else ());
switch (_ec_wait_select (_ec_select_req, &_ec_rep)) {
case 0: {
//Code c
}
break;
case 1: {
//Code else
}
break;
};
}
Initially, a new select request structure is created. This structure
contains basic housekeeping information as used by the library and a
pointer to the list of select elements. A _ec_reply_info structure is
created into which the location to send a reply for call-reply contexts
is placed. This information cannot be placed inside the appropriate
statement block since variables in this block are not preserved between
it going out out of scope and returning into scope via a goto.
Each select clause may add an element to the element list (provided any
guard present evaluates true). The element number is passed to ensure
that the correct block is jumped to. A set of __ease_pre_ functions
exist to create select elements for all possible get, read and
resource statements. These create a structure which contains the
parameters passed for use in the _ec_wait_select function. Similarly,
the _ec_select_else function creates a structure for the else clause.
_ec_wait_select() does most of the work for the select statement. It
interacts with the contexts and returns the element number of the
statement that succeeded. It also frees all memory associated with the
select request structure and the select elements.
Note that the explanation's transformed code does not
correspond semantically to the generated code. If the code
blocks contain a break or continue statement then these will behave
correctly in the generated code but not in the transformed code (due to
the enclosing switch statement).
There is no better code generation that can be performed without additional syntactic analysis. So although the goto's add to the complexity of the code the solution is reasonably elegant.
The following steps are performed when handling a select:
Since a select operates on multiple contexts, and multiple selects may execute simulataneously, the possibility of deadlock is avoided by adding a multi-context lock. This lock must be obtained by any process before it attempts to lock mutiple contexts simultaneously. Once the locks have been obtained the multi context lock may be released. Without the multi-context lock it would be possible for two processes to be waiting for a lock that the other holds, which results in deadlock.
As well as locking its context, each local request is checked to see if it can be immediately fulfilled. If it can then it is processed and all locks are removed.
If request cannot be fulfilled immediately with local data, the process is locked. This prevents any responses from remote contexts from proceeding (and being ignored) before these requests are associated with the process. Messages are then sent to request data from remote contexts. Each request has a sequence number associated with it to facilitate association of responses with requests.
If there is an @else clause (or an @else @after with a zero timeout)
then the requests to remote contexts are labelled "only if ready". An
"only if ready" request will be responded to immediately by the context
owner with data or a "nothing ready" message. Only after "nothing ready"
messages have been received for all requests will the
else clause index is returned.
Once request messages have been sent, requests are placed on the local contexts in the select. There will be no data ready in these contexts because they have remained locked since they were checked earlier. A pointer to the select structure associated with the process to allow responses messages to be correctly handled. The local contexts are then unlocked as is the process before the process waits on its semaphore.
Message passing with the select construct is particularly complicated. Only one select clause may succeed and the effects of all other clauses undone (to the extent that correct context semantics are ensured). The asyncronous nature of message passing may result in messages crossing and this must be handled correctly (and preferably efficiently).
There are 3 message types used for select handling:
The SelectGet message is used to request data from a remote context. It contains the following information:
A SelectResponse message is sent by the context owner to the selecting process. It may or may not contain data (only responses to "only if ready" requests where the context is empty will contain no data). It contains:
A SelectCancel message is sent by a requestor to cancel a request that was previously sent (for which no reply has been received), and also to accept and reject data received from singletons and streams. It contains:
Upon receipt of a SelectGet message, a cell first checks for the existence of the context specified. If no such context exists, a KillProcess message is sent to the calling thread. If the context contains data that can be used immediately to fulfil the request, then this data is sent using a SelectReply message. If the Immediate flag is set and no data is available, a SelectReply message is sent with its Success flag set to false. If there is no data available and the Immediate flag is not set, then the request is stored in the context pending data arrival.
When data is sent for a get from a bag or reply context, it is removed from the context. However, when data is sent from a singleton or stream context the context is locked and the data and request structure are retained in the context. This allows for correct implementation of the ordering rules for streams and singletons - other processes must be prevented from obtaining data from the context until the contect receives notification that the process executing the get (within a select) will actually get the data. When a context is locked, data may be added but not removed. Adding data to a singleton context unlocks the context and removes the locking request.
When a SelectCancel message is received, the context may or may not have already sent data to the caller. Also, if data has already been sent it may or may not have been received. If there is no corresponding SelectGet request in the context, then the SelectCancel message is ignored, otherwise the request is removed from the context. If the SelectGet request caused the context to be locked then the cancel message may be an acceptance or rejection (depending on the Used Flag). If it is an acceptance the context is unlocked and the data sent is removed from the context. If it is a rejection the context is simply unlocked, the data is retained and may be sent to other processes waiting on the context.
When a SelectResponse message arrives, a cell must be able to take an appropriate action irrespective of whether the thread concerned is still waiting for a response. If the thread for this message is no longer waiting for this message (it is not waiting for a SelectResponse or there is no matching sequence number in the list of responses it is waiting for) then the response is rejected (this is discussed shortly). If there is a thread waiting for this message and message's Success flag is false (the context was empty) the request is flagged as having failed and if responses have been received for all contexts the thread is allowed to continue with the @else clause.
If the Success flag is true, the data is passed to the area supplied by the thread, all pending local requests are removed, SelectCancel messages are sent out to the remote contexts that are being waiting on, and the thread is resumed (after being passed its Reply Info if it was a reply context). If the context is a singleton or stream then an acceptance message (a SelectCancel message with its Used Flag set to true) is sent to the context.
To reject a response for singletons and streams, a reject message is sent. A reject message is a SelectCancel message with its Used Flag set to false. For reply and bag contexts the data is resubmitted to the context.
An alternative to this retransmission of data for reply and bag contexts would be to retain the data in the context as with singletons and streams but put the data aside pending acception/rejection (and not locking the context). This would result in more messages (extra accept messages), but less data (no need to return received data) being transmitted. Either of these schemes could result in faster execution of the entire program would depending on the program structure and communications patterns, inter-cell communications bandwith and latency, and message size.
xxx Discuss: