7.0 Legion programming

Legion is designed to support and allow interoperation between multiple programming models. At its base, Legion prescribes the message format for inter-object communications, thereby enabling a wide variety of Legion object implementation strategies. In its most useful form Legion presents programmers with high-level programming language interfaces to the system. These high-level interfaces are supported by Legion-targeted compilers, which in turn use the services of a runtime library that enables Legion-compliant interobject communication.

We have implemented a Legion run-time library (LRTL) [36, 8], and we have ported the Mentat [11] programming language compiler (MPLC) to use the LRTL.¹ Thus, programmers can define Legion object implementations in MPL, which can be translated by MPLC to create executable objects that communicate with one another in a Legion-compliant fashion. Figure 15 depicts this typical programming model.

Figure 15: The Legion programming model. The object is defined in a high-level language. Through a combination of Legion-aware compiler support and use of the LRTL, a complete Legion object implementation is produced. Based on this object implementation, new Legion objects can be instantiated in the system. These new objects can communicate with one another and with existing Legion objects.

7.1 LegionLOID

The runtime library provides classes for LOIDs, Object Addresses (OAs), and bindings. A majority of library users will deal with naming only at the LOID level, leaving OAs and bindings to the low-level library code. The majority of users will dealing with the naming process at the LOID level, leaving OAs and bindings to the low-level library code. Therefore the next section discusses only the LegionLOID class, which manages all of the LOIDs in a Legion system.

In the library, the LOID is represented by the LegionLOID class, which is intended to be the starting point for derived LOID classes implementing different types of LOIDs. We imagine that the classes implementing each LOID type will enforce different properties having to do with the structure, content, and meaning of the various fields of the LOID. Therefore, LegionLOID is not intended to be directly instantiated when the internal fields of the LOID are being used and interpreted: the appropriate derived class should be instantiated instead. So far we have not implemented any derived classes that enforce special properties of the LOID fields, so until then the LegionGeneralPurposeLOID class manipulates all of the LOID fields without enforcing any structure or special meaning to the fields.

The code for the make_loid() function is presented below (Example E) as a demonstration of how to build a general purpose LOID. The function takes a string which represents the object's class identifier and an integer which represents the object's instance number as its parameters. It builds a LOID which names an object in the domain UVaL_LegionDomain_Virginia (a library-defined constant), with class identifier and instance number assigned to the values passed as parameter, and with an empty public key. The function returns a LRef to a LegionLOID.

Example E: Creating a LegionLOID

LRef<LegionLOID>
UVaL_make_basic_loid
      (char *classid, short classid_len,
       char *instid, short instid_len,
       char *pubkey, short pubkey_len)
{
   short *fld_sz;	// Will carry the field sizes
   char **fld_val;	// Will carry the field values
LRef<LegionLOID> loid;

   // Create new structures to fill in and pass to the
   // constructor
   fld_val = new (char *)[4];
   fld_sz  = new short[4];


   // Field 0 : Domain
   fld_sz[LEGION_DOMAIN_FIELD] = 
      UVaL_LegionDomain_Virginia_len;
   fld_val[LEGION_DOMAIN_FIELD] =
      UVaL_LegionDomain_Virginia;

   // Field 1 : Class ID
   fld_sz[CLASS_ID_FIELD] = classid_len;
   fld_val[CLASS_ID_FIELD] = classid;

   // Field 2 : Instance ID
   fld_sz[INSTANCE_ID_FIELD] = instid_len;
   fld_val[INSTANCE_ID_FIELD] = instid;

   // Field 3 : Public Key extension 
   fld_sz[PUBLIC_KEY_FIELD] = pubkey_len;
   fld_val[PUBLIC_KEY_FIELD] = pubkey;

   loid = new
       LegionGeneralPurposeLOID(1,4,fld_sz,fld_val);
   delete [] fld_val;
   delete [] fld_sz;
   return(loid);
}

Assuming that the function make_loid() exists, Example F shows some of the functionality of LOIDs.

Example F: The functionality of Legion LOIDs

LegionLOID *a, *b, *c, d;
// Use the function defined above to create two new
// LOIDs
a = make_an_loid("Class Name", 0);
b = make_an_loid("Class Name", 1);

// The copy constructor is overloaded
c = new LegionLOID(*a);

// == and != operators are overloaded
if ((*a == *c) && (*a != *b))
   printf("== and != are overloaded\n"):

// A special EmptyLOID type is defined. This is
// useful for sending empty LOIDs as parameters and
// return values
if (d.is_empty())
   printf("LOIDs are empty if they have not been
       initialized\n");

// LegionLOIDs are packable
LegionBuffer buffer;
b->pack(buffer);
buffer.seek(BEGINNING, 0);
d.unpack(buffer);
f (*b == d)
   printf("LOIDs are packable.\n");

// is _class() indicates whether or not an LOID refers
// to a Legion class object
if (a->is_class())
   printf("If the class identifier of an LOID is
      empty\n",
          "   then the LOID refers to a Legion
      class.\n");
if (!b->is_class())
   printf("If not, then the LOID doesn't refer to a
      Legion class.\n");

// Finally, LOIDs can be printed neatly, showing
// only the class id and instance number fields
fprintf(stderr,"LOID b: ");
b->show();
fprintf(stderr,"\n");

7.2 Basic module and data container: the Legion buffer

A Legion buffer, represented by the C++ object class LegionBuffer, is the fundamental data container in the Legion Library. Legionbuffer exports operations to read and write data from and to a logical buffer. Instances of different kinds of LegionBuffers export the same interface, and perform the same basic function, but can have different characteristics from one another. For example, one LegionBuffer may copy the data it contains into heap-allocated memory, another may maintain pointers to the data, and a third may read and write its data from and to a file. Further, LegionBuffers may choose to compress or encrypt data, or both. To define its characteristics, each LegionBuffer contains a LegionStorage, a LegionPacker, a LegionEncryptor, a LegionCompressor, and MetaData.

7.2.1 Storage

LegionStorage determines how data is stored. One type of LegionStorage provided in the Library is LegionStorageScat, which stores its data as a linked list of pointers to chunks that it allocates, or to maintain pointers to data "owned" by other parts of the Library. Another type is LegionStoragePersistent, which stores data in a file. Different LegionStorages have unique performance and operation characteristics. So, while it might be efficient to select a LegionStorageScat that does not copy its data extra care must be taken to avoid deleting data out from under the buffer, leaving dangling pointers.

Although LegionStorage exports functions in order to directly access a buffer's data (see page 95 in the Reference Manual), these functions typically should not be directly called by a LegionBuffer user. Instead, the user should call the functions in the interface provided by the LegionPacker portion of the LegionBuffer.

7.2.2 Packer

A LegionPacker determines the data format conversion operations, if any, that are performed on the contained data when it is written to and read from the buffer. LegionPacker is the primary Library mechanism for dealing with the different data storage formats of different machine architectures (e.g., big vs. little endian, 32-bit vs. 64-bit words), which need to communicate with each other. The Library supports three different equivalence classes of architectures, Alpha, Sparc, and x86. For efficiency reasons, Legion assumes a "receiver makes right" [39] data conversion policy, in which a message sender (i.e., the creator of a LegionBuffer) packs the message in its own native format and the message receiver is responsible for converting the data to the format appropriate for the architecture upon which the message now resides. The Library provides six different types of packers of the form LegionPackerX2Y, where X and Y are two different members of {Sparc, Alpha, x86, etc.}. None of these six packers do any conversion when writing to the buffer, but each converts data in an suitable way when reading from the buffer. LegionPackerX2Y is appropriate for use when the data is stored in format X and the machine currently holding the buffer is format Y. When the data is already stored in the correct format for the architecture upon which it is being stored, or when data conversion is done outside of a LegionBuffer, LegionPackerDefault can be used to ensure that no data conversion takes place on reads from the buffer.

The interface provided by a LegionPacker consists of the functions of the form

put_zzz(zzz *source, int how_many)

and

get_zzz(zzz *source, int how_many)

where zzz names a basic C++ data type (i.e. char, short, ushort, int, long, ulong, float, or double). Thus, a LegionPacker exports put_char(), get_char(), put_short(), get_short(), etc.; source points to an array of how_many instances of type zzz; and the put_zzz() function copies this data into the buffer after first performing the acceptable data conversion operation, if it is necessary for the type of LegionPacker that is instantiated. The get_zzz() function fills the complimentary role; first converting the data and then copying it into source.

The code example below (Example G) illustrates the use of the LegionPacker interface of a LegionBuffer. It also uses the seek() function--which is actually part of the LegionStorage interface (please see section 5.4.2 in the Reference Manual)--to "rewind" the logical position within the buffer back to the beginning.

Example G: Using the LegionPacker interface

// Use the default constructor to declare a new empty
// LegionBuffer, which will be configured to contain
// the default storage, packer, encryptor, and
// compressor
LegionBuffer buffer;

// Declare and initialize data to write into the
// buffer
char *in_string = "Hello World";
int in_int_array[5] = {100, 101, 102, 103, 104};

// Insert the string
buffer.put_char(in_string, 11);
// Insert the integers
buffer.put_int(in_int_array, 5);
// Insert a single char
buffer.put_char(&in_string[6], 1);
// Insert a single int
buffer.put_int(&in_int_array[3], 1);

// "Rewind" the buffer back to the beginning so we
// can read out the data we just wrote in
buffer.seek(BEGINNING, 0);

// Declare data structures to read the buffer data into
char out_string[12];
int out_int_array[5];
char out_char;
int out_int;

// Data must be read out in the same order it was put in,
// but not necessarily the same way.
// Read 1st 6 chars
buffer.get_char(out_string, 6);
// Read the next 5
for (j = 6; j < 11; j++)
   // one at a time
   buffer.get_char(&out_string[j], 1);
// Read the integers
buffer.get_int(out_int_array, 5);
// Read the single char
buffer.get_char(&out_char, 1);
// Read the single int
buffer.get_int(&out_int, 1);

7.2.3 Encryptor

A LegionEncryptor determines the encryption and decryption algorithms, if any, that are applied to the data. The Library currently provides only LegionEncryptionDefault, which defines empty encryption and decryption operations.

7.2.4 Compressor

A LegionCompressor determines the compression and decompression algorithms, if any, that are applied to the data. The Library currently provides only LegionCompressionDefault, which defines empty compression and decompression operations.

7.2.5 MetaData

Eight bytes of metadata, three of which are currently used, are associated and carried with each LegionBuffer. The metadata indicates the format in which the data is stored, and the algorithms, if any, that were used to encrypt and/or compress the data. The metadata fields and values that are supported by the Library are defined in the Reference Manual ("LegionBuffer,").

7.2.6 Packability

LegionBuffers enable the concept of "packable" classes in the Library. A class is packable if it is derived from the abstract base class LegionPackable (not to be confused with LegionPacker), and therefore exports the following functions:

pack(LegionBuffer &lb)

and

unpack(LegionBuffer &lb)

Both pack() and unpack() take a single reference parameter, which names a LegionBuffer. The pack() function of a packable class writes its state into the LegionBuffer so that the unpack() function of the same class can read it out. The state is typically written to and read from the buffer using the LegionPacker part of a LegionBuffer interface, which encapsulates the data format conversion operations.

Suppose class Alpha (Example H, top) is packable and exports the C++ == operator. If Alpha is implemented correctly, the code in Example H, bottom, should print "OK."

Example H: Declaration and use of a packable class

class Alpha : public LegionPackable
   {
   private:
      // private data
   public:
      // constructors and member functions

      int operator==(Alpha &other_alpha);
      pack(LegionBuffer &lb);
      unpack(LegionBuffer &lb);
   };

Alpha *a, b;
LegionBuffer buffer;

a = new Alpha(/* appropriate initial values */);
a->pack(buffer);
buffer.seek(BEGINNING, 0);
b.unpack(buffer);

// Make sure we unpacked into b exactly what we packed in a
if (*a==b)
   printf("OK\n");
else
   printf("Bad news\n");

Classes are made packable for two reasons: so that they can be passed between heterogeneous architectures within a LegionBuffer, and so that they can be written to a LegionBuffer as part of a "save state" operation. Since these two operations are common in the Library, many parts of the Library operate only on packable classes. For instance, many of the templated data structures are packable and require the ability to call the pack() member function of the contained data. Further, in a Legion object method invocation, each function parameter is passed within a LegionBuffer, so the easiest and best way to allow an object to be a parameter of a function is to make its class packable.

Making a class packable--implementing the pack() and unpack() functions for a class--is generally quite easy. The LegionBuffer exports storage operations for the primitive C++ types. For complex types, when class X contains an instance of another packable class (Y) X's pack() function can simply contain a call to Y's pack() function. Thus, if Y is packable X does not need to know the data types Y contains in order to pack Y as part of X's state. Consider the simple example of a templated array class, depicted in Example I. Note that the Array class can be made packable, even though it doesn't know the type of the elements it contains. Array only requires that the contained elements are themselves packable.

Example I: A packable template class, whose data members are themselves packable.

template<class T>
class Array : public LegionPackable {
   private:
      T *array_data;
      int num_elements;
   public:
      Array() {
         num_elements = 0; array_data = NULL;
      }
      Array(int n) {
         num_elements = n; array_data = 
            new T[num_elements];
      }
      void set_element(int pos, T &val) {
         if ((pos < num_elements) && (pos >= 0))
            array_data[pos] = val;
      }
      T get_element(int pos) {
         T empty;
         if ((pos < num_elements) && (pos >= 0))
            return array_data[pos];
         else
            return empty;
      }

      ~Array() {
         if (array_data) {
            delete array_data;
            array_data = NULL;
         }
      }
      int pack(LegionBuffer &lb);
      int unpack(LegionBuffer &lb);
};
template<class T>
Array<T>::
pack(LegionBuffer &lb) {
   lb.put_int(&num_elements, 1);
   for (int j=0; j<num_elements; j++)
      array_data[j].pack(lb);
}
template<class T>
Array<T>::
unpack(LegionBuffer &lb) {
   if (array_data)
      delete array_data;

   lb.get_int(&num_elements, 1);
   array_data = new T[num_elements];

   for (int j=0; j<num_elements; j++)
      array_data[j].unpack(lb);
}

LegionBuffer is itself a packable class. Thus, one LegionBuffer can be contained (packed) in another. This is shown at the top of Example J. If data is packed as a LegionBuffer, it should be unpacked as one. Thus the data that was packed in Example J (top) cannot be unpacked correctly, using the code in Example J (middle). This code will compile and run, but it will not have the desired effect of unpacking the ten characters--Hello World--that were packed into the buffer. This is because LegionBuffers prepend "user data" with metadata. Therefore, hello_world_buf contains metadata at the beginning of the buffer, and between Hello and World. The correct way to unpack the data is shown in Example J (bottom).

Example J: Packing a LegionBuffer into another Legion Buffer.

LegionBuffer hello_buf;
char *hello = "Hello";
hello_buf.put_char(hello, 5);

LegionBuffer world_buf;
char *world = "World";
world_buf.put_char(world, 5);

LegionBuffer hello_world_buf;
hello_buf.pack(hello_world_buf);
world_buf.pack(hello_world_buf);

char hello_world[1];
hello_world[10] = /'\0';

// "Rewind" the buffer
hello_world_buf.seek(BEGINNING, 0);

// Try (unsuccessfully) to unpack all 10 characters 
// at once
hello_world_buf.get_char(hello_world, 10);

// Declare two separate LegionBuffers for unpacking 
// the two buffers that were packed into hello_world_buf 
LegionBuffer out1, out2;

// "Rewind the buffer
hello_world_buf.seek(BEGINNING, 0); 
// Unpack hello_buf into out1
out1.unpack(hello_world_buf);	 
// Unpack world_buf into out2
out2.unpack(hello_world_buf);
char hello_world[11];
hello_world[10] = '\0';

// Unpack "Hello"
out1.get_char(hello_world, 5);
// Unpack "World"
out2.get_char(&hello_world,[5], 5);

// This line will print "HelloWorld"
printf(hello_world);

LegionBuffers pack and unpack their bytes raw (without data format conversion), so that each buffer maintains its own meta-data. This means that a LegionBuffer created on an x86 architecture can be contained in a LegionBuffer whose data is in Alpha format. When the contained buffer is unpacked, a LegionBuffer with appropriate data conversion operations will be instantiated: when the bytes are read out, the data will wind up in the correct format for the architecture of the machine upon which the data resides.

7.3 Legion invocations and messages

7.3.1 Contents of a message

Legion objects communicate with each other via method invocation and return values. To invoke methods and return results, Legion objects send messages to one another in a standard Legion message format. A Legion message can carry: (1) part (or all) of a method invocation, (2) the function return value that resulted from an invocation, or (3) a return value for an out or in/out parameter. Every Legion message contains, in order, source and destination LOIDs, a function identifier, the number of parameters to expect, a computational tag, a list of parameters, a continuation list, and an environment.

Source LOID: The source LOID names the sender of the message.

Destination LOID: The destination LOID names the object to which the message is being sent.

Function identifier: The function identifier field should contain a C++ object, which is packed in the data format of the architecture of the machine from which it was sent. If the message is intended to implement a method invocation, the packed C++ object should match some function identifier in the public interface of the object to which the message is being sent. If the message is the "filled-in" value of an out or in/out parameter, or a normal return value, the packed C++ object should be the constant LEGION_RETURN_FUNCTION_IDENTIFIER.

Computational tag: A single method invocation can be split up into several Legion messages, which can come from different sources (see "Legion program graphs"). A computation tag is a long integer, packed in the message sender's data format, that uniquely identifies a computation or method function invocation within Legion for the duration of the invocation's existence. The computational tag should be assigned by the invoker. Messages that carry function return values and filled-in out and in/out parameters should contain the same computational tag as the messages that carried out the invocation, which generated the results. The invoker matches the computation tag, when awaiting results.

Although a computational tag is simply a long integer, the Library provides a C++ class called LegionComputationTag that encapsulates the integer and exports appropriate functions on computational tags. The Library also provides a class called LegionComputationTagGenerator, which can be used to generate random computational tags. Typical use of these two classes is show in Example K.

Example K: Use of Legion computational tags

// Declare a new computation tag generator
LegionComputationTagGenerator gen;

// Declare variables to point to computation tags
LRef<LegionComputationTag> t1;
LRef<LegionComputationTag> t2;

// Get the next two tags from the generator
t1 = gen.next_tag();
t2 = gen.next_tag();

// Print the values of the tags
printf("Tag 1 is: %d\n", t1->get_value());
printf("Tag 2 is: %d\n", t2->get_value());

// Sample output:
// Tag 1 is: 2023717593
// Tag 2 is: 1683023

Parameters to expect: This field should contain an integer, packed in the sender's data format, that indicates the total number of parameters being passed in the message function invocation. If the message is part of a return value, this field is ignored.

Parameter list: If the message is part of an invocation, the parameter list contains the values of the parameters contained in the message. The parameter list is packed as an integer that indicates how many parameters are present, followed by the parameters themselves. Each parameter contains an integer that indicates the number of the parameters, followed by a LegionBuffer that contains the value of the parameter. Return values are passed back in a parameter list as well. The C++ object classes LegionParameter and LegionParameterList implement parameters. The code in Example L builds a parameter list that contains two parameters, an integer, and a 14-element character string.

Example L: Use of LegionParameterList and LegionParameter

// Declare the variables to be packed into a parameter list
int int_parameter;
char string_parameter[14];

// Initialize the variables appropriately
int_parameter = 7;
sprintf(string_parameter,"Hello, World.");

// Create a LegionBuffer to hold the integer parameter
LRef<LegionBuffer> lb1;
lb1 = new LegionBuffer();
lb1->put_int(&int_parameter, 1);

// Create a LegionBuffer to hold the string parameter
LRef<LegionBuffer> lb2;
lb2 = new LegionBuffer();
lb2->put_char(string_parameter, 14);

// Create parameters out of the buffers
LRef<LegionParameter> param1;
param1 = new LegionParameter(1, lb1);
LRef<LegionParameter> param2;
param2 = new LegionParameter(2, lb2);

// Create a new parameter list
LRef<LegionParameterList> plist;
plist = new LegionParameterList();

// Finally, insert the parameters into the parameter list
plist->insert(param1);
plist->insert(param2);

Continuation list: A continuation list describes the location to which the results of a particular computation should be forwarded. A continuation contains a computational tag and result number, which together identify a return value. It also contains the LOID, function identifier, and parameter number to which the result should be sent. The motivation for continuation lists arises from the macro data-flow programming model that is the initial Legion target. In this model, results from method invocations are sent directly to other invocations that use these results as parameters. These data dependencies are determined through analysis of the program code (see [13] for more information). LegionProgramGraphs are the representation of these data dependencies, and are described in section Legion program graphs. For further information, refer to the Legion on-line documentation at <http://legion.virginia.edu/>.

The LegionMessage class implements Legion messages in the Library. Its most useful constructor takes parameters that correspond to all of the constituent parts described above. Therefore an instance of LegionMessage can be created, as shown in Example M.

Example M: Sample creation of a Legion message

// Declare variables for the LegionMessage's
// constituent parts
LRef<LegionLOID> source_LOID;
LRef<LegionLOID> destination_LOID;
LRef<LegionFunctionIdentifier>
   function_identifier;
int parameters_to_expect;
LRef<LegionComputationTag> computation_tag;
LRef<LegionParameterList> parameter_list;
LRef<LegionContinuationList>
   continuation_list;
LRef<LegionEnvironment> environment;

// Initialize the constituent parts appropriately
// (not shown)
// Create a new LegionMessage from the constituent
// parts
LegionMessage *msg;
msg = new LegionMessage(source_LOID, destination_LOID,
   function_identifier, parameters_to_expect,
   computation_tag, parameter_list,
   continuation_list, environment);

Although LegionMessage provides a mechanism for implementing method invocation in the Library, LegionProgramGraph provides a higher level abstraction that is simpler to use.

7.3.2 Legion message database

Legion Work Unit

Each Legion object services requests for member function invocations and returns the results of these invocations. The parameters to these functions, as well as the requests themselves, arrive in Legion messages: a complete method invocation may involve composing a number of Legion messages. Conceptually, the Legion message database is divided into two parts. The "bottom" part, called the Legion Invocation Matcher, manages a list of partially complete method invocations for the Legion object: since messages may arrive from different locations and at different times, some parts of message will arrive before other parts. The "top" part of the database, the Legion Invocation Store, maintains two separate lists. The first list contains complete method invocations (i.e., requests with a complete parameter set and security clearance). The second list contains return values that the object has received as a result of its own method invocations on other Legion objects. Once a complete method invocation has been assembled, it becomes a Legion Work Unit, and is promoted to the Invocation Store.

Each object has a server loop that continuously checks the invocation store for ready work units, extracts them as they become available, and performs the requested invocation. A partial interface to the C++ class LegionInvocationStore is given in Example N.

Example N: Selected elements of the LegionInvocationStore interface

// This class implements the "database" for ready 
// work units and stores the results from method 
// invocations on other Legion objects
class LegionInvocationStore 
{
public:
    // Accept function invocations for the given function 
    int enable_ function (int function_identifier);
    
    // Check to see if there are any ready work units
    int any_ready();
    int any_ready_for_func(int function_identifier);

    // Remove the next work unit from the store
    LRef<LegionWorkUnit> next_matched();
    LRef<LegionWorkUnit> 
       next_matched_for_func(int function_identifier);
}

Method invocation

(Information here does not account for varying security levels. (For information on how security affects invocations, please contact the Legion Resource Group.)

Suppose Legion object A (the invoker) invokes a member function on Legion object B (the invokee). This method invocation proceeds through the invoker and invokee, as shown in Figure 16. The invoker builds a Legion message containing salient information about the member function invocation. Typically, the Legion program graph interface builds this message. The Legion message is then passed to the Legion message layer, which binds the LOID of the recipient to a particular address. The binding process is a key aspect of Legion, and is described in more detail elsewhere (see "The binding mechanism"). The outcome of the binding process is a <LOID, Legion Object Address> tuple called a binding. This represents the logical name and current physical address of the referenced object. The message and its binding are then passed to the data delivery layer, which linearizes the message for transport over the wire, uses the object address to create a physical connection to the referenced object, and sends the message.

Figure 16: Method invocations. The path through the Legion library for a method invocation that returns a result to the caller. Below the dotted line is considered the Legion library's domain. Application code must interface with the library at the four marked points.

On the receiving end, the data delivery layer of the destination object unpacks the data into a new instance of LegionMessage, and passes the message up to the message layer. The message layer then inserts this message into a Legion message database. When the return result reaches its destination, it is handled like any other Legion message until it reaches the Invocation Store, which examines the work unit's contents and realizes that it is a return result, not a method request. The result is then inserted into the return result list, and from there it is available to the original invoking object through the program graph interface

7.3.3 Basic Legion event kinds & handlers

The Library is implemented as a configurable protocol stack. A layer of the stack communicates with other layers through an event mechanism. The basic idea is straightforward: if layer A wishes to communicate with layer B, A announces a LegionEvent. Each LegionEvent has a tag which denotes a LegionEventKind (what kind of event it is). Each LegionEventKind has one or more associated event handlers that may be called whenever an event of its kind is announced. Handlers for a particular LegionEventKind are given a priority to determine the order in which the handlers are called. Since a LegionEvent can carry arbitrary data, this is the method by which data is passed and transformed from layer to layer. If layer B has registered a handler for the kind of event that layer A announces, layer B will get that event. (See "Implementing the configurable protocol stack: events".)

7.3.4 Invocation execution and result return

The Library announces a MethodReady event each time a ready method invocation request is inserted into the invocation store. Each request is maintained as a Legion Work Unit. The general algorithm for getting a LegionWorkUnit out of the database and invoking its requested method is as follows:

1. Remove the work unit from the invocation store

   User code can remove work units from the invocation store in at least two different ways, each of which requires a server loop that continuously checks the invocation store for ready work units. One mechanism is to supply and register an event handler for MethodReady events. A simplified version of the code for the handler and the server loop look like that in Example O (top). The accompanying server loop is quite short. The other mechanism, in the bottom of the example, does not require the user to supply an event handler. The user instead checks the invocation store each time, through a longer server loop.

   Example O: Two mechanisms to get a ready work unit out of the invocation store

   static int
   LegionMethodInvoke(LRef<LegionEvent> event)
   {
      if ((LegionLibrary.Get_InvocationStoreLL_Default())
         ->any_ready()) 
         {
         LRef<LegionWorkUnit> wu;
         wu = (LegionLibrary.Get_InvocationStoreLL_Default())
            ->next_matched();
         invoke_method(wu);
         }
      return 0;
   }
   
   main()
   {
   // . . . 
   
      // Register my event handler...
      (LegionLibrary.Get_Evsent_MethodReady())->
          addHandler(ContextObject_LegionMethodInvoke, 1.0);
      (LegionLibrary.Get_EventManager())->serverLoop();
   }
   while(1) {

   

      (LegionLibrary.Get_EventManager())->flushEvents();
      if((LegionLibrary.Get_InvocationStoreLL_Default())
         ->any_ready()) 
         {
         LRef<LegionWorkUnit> wu;
         wu  = (LegionLibrary.Get_InvocationStoreLL_Default())
            ->next_matched();
         invoke_method(wu);
         }
      (LegionLibrary.Get_EventManager())
         ->blockForEventAvailable();
   }

2. Construct and perform the requested method invocation

   Once a work unit is removed from the invocation store, it needs to be unpacked to a form suitable for method invocation. There must be specific code to do this for each public method in the invoked object. Example P contains an example invocation construction. The sequence is functionally the same as server stubs in an RPC. First ascertain the requested method and then remove each parameter from the work unit, based on the particular requested method. Each parameter is returned as a LegionBuffer, so must be unpacked in order to get the actual parameters for the method invocation. Once this is done, the method can be called like any C++ member function.

For methods that have return results, these values must be sent to the list of objects defined in the LegionContinuationList part of the work unit from which the method invocation was constructed. The most straightforward way to do this is as follows: for each return result, allocate a new LegionBuffer and insert the return value into the buffer, then call Legion_return() with the buffer, continuation list, and number of the return value as arguments. This sequence is illustrated at the bottom of Example P.

Example P: An example of method construction, invocation, and return, once a work unit has been removed from the invocation store. Other code structures are possible.

// Each object might have a function like this to 
// figure out which member function to call
invoke_method(LRef<LegionWorkUnit> wu)
   {
  LRef<LegionFunctionIdentifier> this_fid;
   this_fid = wu->get_function_identifier();
   if (this_fid == NULL) 
      return 0;
   if (*this_fid == sample_op_fid)
      {
      sample_op_wrapper(wu);
      return 1;
      }
   }
// assume this method has two parameters, an int and a float
void sample_op_wrapper
   (LRef<LegionWorkUnit> wu)
   {
   float float_parm;
   int int_parm, return_value;
   LRef<LegionBuffer> buffer;

   //unpack the parameters
   buffer = wu->get_parameter(1);
   lb->get_int(&int_parm, 1);
   buffer = wu->get_parameter(2);
   lb->get_float(&float_parm, 2);

   // invoke the method
   return_value = sample_op (int_parm, float_parm);

   // return results to whomever has asked for them
   buffer = new LegionBuffer();
   buffer->put_int (&return_value, 1);
   Legion_return
   (METHOD_RETURN_VALUE, 
      wu->get_continuation_list(), buffer);
   }

A complete example of a C++ class, its translation into the appropriate Library calls, and some sample method invocations are give in the Reference Manual, starting on page 84.

7.3.5 Legion program graphs

A program graph represents a set of method invocations on Legion objects and the data dependencies between those invocations and objects. The program graph is a data-flow graph whose nodes represent method invocations and whose arcs represent data dependencies between the method invocations.

Figure 17: Sample code for an invoking object (left) and the corresponding program graph (right).

// The "user" code main () { int a, b, x, y, z; MyObject A, B; x = A.op1(a); y = B.op1(b); z = A.op2(x, y); printf ("%d/n", z); }

Suppose that objects A and B each export methods op1() and op2(). Figure 17 shows a simple user program and the resultant data dependencies. It is clear from the code that the parameters to both A.op1() and B.op1() are available locally. Those are the constant parameters. The parameters to A.op2() are not available locally, since they are the result of method invocations that have been executed elsewhere. These are the invocation parameters.

The most straightforward mechanism for making an invocation request is to build a program graph, using the interface provided by the C++ object class LegionProgramGraph. Salient parts of the LegionProgramGraph are given in Example Q. A fuller description of the interface constituents appears in the Reference Manual (page 92).

Example Q: Some elements of the LegionProgramGraph interface

class LegionProgramGraph 
{
public:
// these methods are for making invocation requests
LRef<LegionInvocation> 
add_invocation(LRef<LegionInvocation> inv);
ParameterStatus 
add_constant_parameter
   (LRef<LegionInvocation> target,
   LRef<LegionParameter> parameter, 
   int param_number);
void add_result_dependency
   (LRef<LegionInvocation> inv, 
   int param_number);
int execute(LegionInvocation *inv);
// these methods are for managing return values 
LRef<LegionBuffer> 
get_value(LRef<LegionInvocation> inv, int param_number);
int release_value 
   (LRef<LegionInvocation> inv, 
   int param_number);
int release_all_values();
}

Now we can show the necessary library calls to implement the sample code in Example R below.

Start-up: The call to Legion.init() initializes various data structures in the Library. Legion.AcceptMethods() is called because the invoking object may itself be accepting member function requests from other objects.

Object creation: The calls to Legion.CreateObject() create the two objects of interest and return LOIDs to these objects. Local handles for the objects are created based with these LOIDs.

Member function invocation: For each method, we use the object's local handle to create an invocation.² We can then add the invocation to the program graph using add_invocation(). Every added invocation becomes a node in the program graph. To create arcs parameters must first be packaged into instances of LegionParameter (see Example L). Once packaged, they are added to the graph using add_constant_parameter(). Internal arcs in the graph must be handled differently, because they represent values that are not locally available--they have not been computed yet. Internal arcs are added using add_invocation_parameter(). Once a program graph is constructed, the execute() member function must be called. Calling execute() causes every node in the program graph to be packed up as a Legion message and shipped to the appropriate object for execution. Results from this remote execution then become available and are automatically sent to the objects that require them. In Example R, the return values from A.op1() and B.op1() are forwarded directly to A, so that they can become the parameters to A.op2().;

Example R: Sample user code (top left), the corresponding program graph (top right), and the library calls needed to implement it (bottom). In this case, make_parameter() takes an integer, wraps it up in a LegionBuffer, then wraps the buffer in a LegionParameter.

// The "user" code main () { int a = 10, b = 15, x, y, z; MyObject A, B; x = A.op1(a); y = B.op1(b); z = A.op2(x, y); printf ("%d/n", z); }

// The corresponding calls to the library to implement
// the "user" code
main() 
   {
   LRef<LegionInvocation> inv1, inv2, inv3;
   LRef<LegionBuffer> buffer;
   LRef<LegionParameter> parm;
   int a = 10, b = 15;
   // Set op1_fid, op2_fid, op3_fid 
   // (not shown)
   // Start-up
   Legion.init();
   Legion.AcceptMethods();
   // Object creation
   LRef<LegionLOID> A_name, B_name;
   A_name = Legion.CreateObject(MY_OBJECT_CLASS_ID);
   B_name = Legion.CreateObject(MY_OBJECT_CLASS_ID);
   // Member function invocation
   LegionProgramGraph G(Legion.getMyLOID());
   LegionCoreHandle A_handle(A_name), B_handle(B_name);
   inv1 = A_handle.invoke(op1_fid, 1, 1);
   G.add_invocation(inv1);
   parm = make_parameter (a, 1);
   G.add_constant_parameter (inv1, parm, 1);
   inv2 = B_handle.invoke(op1_fid, 1, 1);
   G.add_invocation(inv1);
   parm = make_parameter (15, 1);
   G.add_constant_parameter (inv1, parm, 1);
   // Return value retrieval
   inv3 = A_handle.invoke(op2_fid, 2, 1);
   G.add_invocation(inv1);
   G.add_invocation_parameter (inv1, inv3, 1, 1);
   G.add_invocation_parameter (inv2, inv3, 1, 2);
   G.execute(inv3);
   buffer = G.get_value(inv3, UVAL_METHOD_RETURN_VALUE);
   int z; 
   buffer.get_int(&z, 1);
   printf ("%d\n", z);
}

Return results: Getting return values that are results of method invocation requests is straightforward. The LegionProgramGraph class has a method called get_value(), which takes the parameter number of the result value as one of its arguments. If the result is unavailable get_value() will block. The constant UVaL_METHOD_RETURN_VALUE can be passed to get_value() to obtain the return value of the function call. By default, the return values of all method invocations are returned to the invoker. For in/out parameters, add_result_dependency() (not shown) must be used to explicitly ask for the parameter to be returned. This call must be made before execute() is called on the program graph that contains the associated method invocation. Otherwise the parameter will not be returned and a call to get_value() for that parameter will block indefinitely.

7.4 Reference counting

The template class LRef, in concert with the class LRefCntr, is the Library's mechanism for automatic reference counting and safe dynamic memory management. The mechanism is intended for heap allocated C++ objects. It keeps track of references to each object that is shared by different parts of the library and automatically deletes the object when all meaningful references to it have disappeared. Each reference counting object--i.e., each instance of a class derived from LRefCntr--maintains an integer that indicates the number of LRefs that point to that object. When a new reference is made to point to an object the reference count within that object automatically increases. When a LRef is overwritten with another value, or when a local variable LRef falls out of scope the reference count in the object to which the reference points automatically decreases. When the reference count falls to zero the object is automatically deleted. All of this happens without any intervention by the programmer or user of LRefs.

The decision to include an automatic reference counting mechanism in the Library was motivated by two observations: memory copies are expensive and often hinder the performance of message passing code, and keeping track of shared pointers and deciding which parts of the code are responsible for deleting which chunks of heap-allocated memory is prone to error and is difficult to document effectively. It is hoped that the automatic mechanism will combine the better performance that comes from avoiding memory copies with the safety and correctness that comes from not having to worry about managing dynamically allocated memory. Obviously, the automatic reference counting mechanism introduces some overhead when compared to simple pointer copies, but we believe that the benefits will outweigh the costs.

To be a casual user of LRef, you need only remember one simple rule of thumb and two simple exceptions.

7.4.1 LRef rule of thumb

Read "LRef<X> t" as "x *t" and then treat the variable t exactly as if it were in fact a C++ pointer to class X.

Just about every operator that is legal on a pointer to a C++ object has been overloaded to work correctly for LRef. Example S shows that LRef can be used just as C++ object pointers would be. The implementation of the MyRCO class in Example S is unimportant beyond the fact that it is derived from LRefCntr and implements the functions that are used to illustrate the point.

7.4.2 Exceptions to the rule of thumb

1. Never delete the memory that a LRef points to. The memory will be deleted when all references to the memory have been overwritten or go out of scope.
2. Do not use a LRef alone as a boolean. "if (t)..." will not compile, but "if (t != NULL)..." and "if (!t)..." will work as expected.

LRef can also refer to non-heap-allocated memory, i.e. global and local variables. To insure that these objects are not automatically explicitly deleted by the mechanism, the programmer should call the function makeNonHeapReference() on the reference.

Example S: Example declaration of a ReferenceCountingObject and its use with LRef.

// Definition and implementation of class MyRCO, which
// is a reference counting object by virtue of being
// derived from class LRefCntr
class MyRCO : public LRefCntr
{
   private:
      int contained_val;
   public:
      MyRCO() {contained_val = 0;}
      MyRCO(int val) {contained_val = val;}
      int set_value(int val)
         { return (contained_val = val);}
      int get_value()
         {return (contained_val);}
      int operator==(myRCO &other_rco)
         {return (contained_val ==
         other_rco.contained_val);}
      int operator!=(MyRCO &other_rco)
         {return (contained_val !=
         other_rco.contained_val);}
      ~MyRCO() {printf("Destructor called\n");}
};
// Create three new reference counting object, pointed to 
// by variables a, b, and c. Notice that type (MyRCO *) is
// automatically cast correctly to type LRef<MyRCO>
LRef<MyRCO> a = new myRCO(1);
LRef<MyRCO> b = new myRCO(2);
LRef<MyRCO> c = new myRCO(3);
// Show that * and -> work just like pointers
a->set_value((*a).get_value()); // no change to the 
		                               // object
c = a;
// The object to which c originally pointed now has no
// more references to it. Therefore, that object's
// destructor will be called automatically. The object
// to which a points now has two references to it, a and c.
a = b;
// The object to which a pointed is not automatically
// deleted because c still points to it.
// All of the print statements below will be executed.
// Comparing objects is still different than comparing
// pointers
if (*a == *b) printf
   ("a and b refer to object whose vals are ==.\n");
if (*a != *c) printf
   ("a and c refer to objects whose values are 
      !=.\n");
if (a == b) printf
   ("a and b point to the same object.\n");
if (a != c) printf
   ("a and c do not point to the same object.\n");
// Make a and c point to objects that contain the same
// value
c->set_value(a->get_value());
if (*a == *c) printf
   ("Now a and c point to objs whose vals are ==\n");
if (a != c) printf
   ("a and c still do not point to the same obj.\n");

7.5 Exception propagation model

Exceptions are a standard structuring mechanism for building distributed robust applications, as they provide a mechanism for error detection and recovery. As the name implies, an exception has the connotation of a rare event, an assumption that no longer holds true in a wide-area distributed system such as Legion. Examples of possible common exceptions in Legion include:

• Security violations: the invoker of an object does not have proper authorization
• Communication errors: object X is unable to communicate with object Y
• Binding errors: object X is unable to find the network address for object Y
• IDL errors: a method invocation on object X does not match X's exported interface
• Resource errors: object X does not have sufficient resources to service a request
• Traditional errors: floating point exceptions, divide by zero, out-of-range data, etc.
• User-defined errors: errors specific to the user code

In designing an exception propagation model we follow the Legion minimalist philosophy of specifying mechanisms and not policies. Thus Legion emphasizes exception propagation and not exception handling. Our view is that exception handling is specific to a particular programming language and should not be part of Legion proper. Instead, Legion provides the mechanisms to enable a wide variety of exception handling models.

In Legion, the propagation of exceptions is specified in a generic manner with computation graphs (see "Legion program graphs"). Computation graphs can express a variety of exception handling policies, from traditional policies which propagate exceptions back to the caller (as in CORBA) to policies that propagate exceptions to third-party objects. Examples of the latter policy would be to propagate all security exceptions to a Security Monitor object or propagate all Communication errors to a Fault Detector object. For a detailed description of various policies please refer to "Building Robust Distributed Applications with Reflective Transformations" [26].

7.5.1 Standard exception propagation policy

The Legion Library comes with default functions for the common case in which users want to propagate exceptions back to the caller. To raise an exception, users must first create an instance of LegionException. Exceptions are described by a Type field and a Subtype field.

LRef<LegionException> e ;
e = new LegionException
   (Type, Subtype, "Descriptive Text");
LegionRaiseException(e);

7.5.2 Catching exceptions

To catch exceptions generated by direct or indirect children of an object, use the following commands:

LegionExceptionCatcherDefaultEnable (LEGION_EXIT_ON_EXCEPTION) 
LegionExceptionCatcherDefaultEnable (LEGION_CONTINUE_ON_EXCEPTION)

LegionExceptionCatcherDefaultEnable() catches all exceptions and does not distinguish between types and subtypes. In (1), the application immediately terminates while in (2), the application can continue execution. Most of the Legion command line utilities use (1).

Interested readers may find an application of the Legion exception propagation model in the standard Legion distribution in the $LEGION/src/Examples directory. Furthermore, more complex policies are possible and are described in "Building Robust Distributed Applications with Reflective Transformations" [26].

7.6 How to use the run-time library

This section describes how to use the Library as is, with no internal modification. We begin by describing the class LegionLibraryState, which encapsulates start-up and initialization routines, and provides a public interface to an object's Legion related state. We then explain how a method invocation is implemented in the Library. Finally, we describe the Library interface from both the invoker and invokee perspectives.

The LegionLibraryState C++ object class provides an interface to important parts of an object's Legion-related state information. This includes the object's own LOID, the object's class LOID, and so on. LegionLibraryState also provides implementations of key object control mechanisms such as object creation, activation, deactivation and deletion. Finally, the LegionLibraryState interface provides the ClassOf() operation, which encapsulates the mechanism by which a given object's class LOID can be obtained via the object's LOID. We will now examine each of these general features of the LegionLibraryState class in more detail.

Call Legion.init()

The primary function of the LegionLibraryState object class is to encapsulate the internal state of the Legion library and to provide programmers with the public interface to this state. A simple global object of the class LegionLibraryState named Legion is included as part of the Library. Before using any of the Library features the Library state should be initialized with the init() function.

This function initializes several different parts of the Library, including the LOID of LegionClass, the Legion program graph layer and the Legion matcher and invocation store. After this call, the object can enable or disable functions in the invocation store, set its own LOID (if necessary), and perform any user initialization that must be performed before any methods are serviced (or any messages are sent or received by the object).

Call Legion.AcceptMethods()

The object cannot yet invoke or service methods, however. These services require a second initialization phase which is encapsulated in the AcceptMethods() member function of the LegionLibraryState class.

After making this call, the object can both accept and invoke methods. Consequently, basic object control mechanisms such as object creation and ClassOf(), which rely on the ability to invoke methods on remote objects, are also enabled. The reason for a two-phase initialization is simply to separate method service configuration from the enabling of method arrival events.

The Library initialization should proceed as follows:

1. Call Legion.init(). This initializes various data structures in the Library.
2. Enable acceptable methods (i.e., function identifiers) in the objects invocation buffering mechanism (the Legion invocation store). To accomplish this, call LegionInvocationStore. enable_function(int) for each method that the object will be exporting.
3. If methods will be serviced by an event handler, add this event handler for MethodReady events. This event handler should contain code to extract work units from the invocation store and call the appropriate method implementations based on incoming function identifiers.
4. Call Legion.AcceptMethods(). This call initializes the Legion message passing system and notifies the object's creator (its class) that the object is up and ready to accept method requests.
5. Start the server loop. The details of this depend on how work units are being extracted from the invocation store.

Once the Legion Library state is fully initialized, the object can use the Legion object to determine its own LOID, the LOID of its vault, the LOID of its LegionClass, and so on. For example,

LRef<LegionLOID> MyLOID, VaultLOID;
MyLOID = Legion.GetMyLOID();
VaultLOID = Legion.GetVaultLOID();

The LegionUtilityFunction class provides an interface to a number of key system services, such as object creation, activation, deactivation, and deletion. A sample is shown in Example T.

Example T: Sample usage of object Legion of class LegionUtilityFunctions

test_object_control(char *class_id)
{
    LRef<LegionLOID> testObj1, testObj2;
    // Create an object of the specified class
    testObj1 = Legion.CreateObject(class_id); 
    // Create an object of the same class as testObj1
    testObj2 = Legion.CreateObject(testObj1);
    // Test object deactivation and activation
    Legion.DeactivateObject(testObj1);
    Legion.ActivateObject(testObj1);
    // Test object deletion
    Legion.DestroyObject(testObj1);
}

An object can use the LegionLibraryState interface to report to its class when it plans to delete itself, without having been requested to do so by the class. For example, an object before exiting could execute:

fprintf(stderr, "Problem - this object must exit\n");
Legion.DeleteSelf();
exit(1);

Beyond object control services, the LegionLibraryState class encapsulates the important Legion ClassOf() operation, which can be used to determine the LOID of a class object based on the LOID of one of its instances, or based on just a class identifier (that part of the LOID that indicates the object's class):

LRef<LegionLOID> foo, classOfFoo;
// ...set foo to some LOID of interest (not shown)...
classOfFoo = Legion.ClassOf(foo);

Unlike simple state accessors such as GetMyLOID(), object control methods such as CreateObject() and ClassOf() all result in Legion method invocations, and thus the cost of these member functions are non-trivial.

7.7 Modifying the Library

A major design object of Legion is an extensible system: making it easy for future implementors to insert modules into the Library. To accomplish this, the Library provides

1. A layered design and implementation and
2. a standard mechanism for inter-layer communication.

The layered design of the Library is depicted in Figure 18 (below). The client side (left) is the invoker, the code that is requesting a method invocation on some Legion object. The server side (right) is the invokee, the Legion object upon which the method invocation has been made. While it is convenient to think of the Library in terms of clients and servers it is also artificial, since full Library functionality is provided to both parties. In many cases, an object's role changes as execution progresses--sometimes clients are servers and sometime servers are clients.

7.7.1 Implementing the configurable protocol stack: events

As Figure 18 illustrates, the Legion protocol stack supports a variety of functions, in order to allow modules to be easily added and configured, an approach similar to that used in the x-Kernel [16]. The problem with the traditional approach to building protocol stacks is that each layer in the stack explicitly calls the layer below or above. This static coupling makes it difficult to dynamically configure the stack.

Figure 18: Layered design of the Legion library.

To provide a dynamically configurable stack, then, we have chosen a well understood technology--events [4]--and have applied it to allow flexibility and extensibility. Four main classes implement events: LegionEventManager, LegionEventKind, LegionEvent, and LegionEventHandler. When an event occurs, the system announces an event to an Event Manager, which is an instance of class LegionEventManager. The event manager notifies interested parties (i.e., Legion Event Handlers) of the event: this can be done immediately, or at a later time.

Event handlers register themselves with a Legion Event Kind, an event template that contains a unique tag and a default list of handlers, in order to be notified of an event. Since there may be more than one event handler per event kind, a handler is given a priority when registering. In the current scheme, a handler with a lower priority number is executed before a handler with a higher number. Not all event handlers associated with a LegionEvent are guaranteed to be executed, since an event handler is allowed to prevent the execution of subsequent handlers.

The class LegionEventKind serves as a template for instance of class LegionEvent (Example U). When an event is created it obtains a list of LegionEventHandlers from its corresponding LegionEventKind. This allows users to modify the behavior of the protocol stack without having to change existing modules. To enable interlayer communication, Legion events may also carry arbitrary data, which can be updated, modified, and transformed in arbitrary ways by the event handlers processing each events.

Example U: Some elements of LegionEventKind and LegionEventInterface

class LegionEventKind {
public:
// Construct a new event kind and give it a unique identifer
   LegionEventKind(int kind);
// Add and delete handlers
// Note that handlers are added in priority order
   int addHandler
      (LegionEventHandler, LegionEventHandlerPriority);
   int deleteHandler(LegionEventHandler);
};
class LegionEvent : public LRef {
public:
// Construct an event using a LegionEventKind as a template
   LegionEvent(LegionEventKind&);
   LegionEvent(LegionEventKind&, void * data);­
// Adding and deleting handlers
   int addHandler
      (LegionEventHandler, LegionEventHandlerPriority);
   int deleteHandler(LegionEventHandler);
// Setting and getting the data associated with the 
// LegionEvent
   void* getData();
   void setData(void*)
   // Invoking event handlers
   LegionEventHandlerStatus callNextHandler
      (LRef<LegionEvent> ev);
   void callRemainingHandlers
      (LRef<LegionEvent> ev);
};

A Legion event handler takes a reference to the LegionEvent that it is servicing as its sole argument. Thus, each LegionEventHandler associated with a particular LegionEvent may inspect and modify the data carried by the LegionEvent. In general, this is how information is shared between various LegionEventHandlers.

7.7.2 Interfaces

Users may add LegionEventHandlers to a LegionEventKind. When a LegionEvent is created, it obtains its unique event identifier and a list of suitable LegionEventHandlers from its corresponding LegionEventKind. LegionEventHandlers are ordered, and the handler with the lowest priority are executed first. An example of an event handler is in Example V.

Example V: LegionEventHandler

// Signature of a LegionEventHandler
typedef LegionEventHandlerStatus
   (*LegionEventHandler) (LRef<LegionEvent>)
// Example of a valid LegionEventHandler
LegionEventHandlerStatus myHandler(LRef<LegionEvent> myEvent)
{
   // arbitrary code
}

A Legion event maintains a logical pointer to the currently executing LegionEventHandler. This allows the event to suspend the execution of its event handlers and to resume that execution at a later time.

In particular, an event handler can:

1. Inspect and modify the data field of the incoming event
2. Inspect and modify the list of handlers contained in the incoming event
3. Create and announce new events
4. Prevent the next handlers from being executed
5. Save the current event

There are no restrictions on the code implementing a LegionEventHandler.

7.7.3 LegionEventManager

When users wish to notify the system that something of interest has occurred, they must announce a LegionEvent to a LegionEventManager (Example W). The LegionEventManager is responsible for deciding when to execute the handlers associated with an event. In the current implementation, there are two ways to announce events to an event manager: depending on the chosen method, the event manager will either invoke the handlers immediately or will defer the execution of the event handler and store the LegionEvent in an internal queue. The available methods are: the flushEvents() method, used to execute all pending events; the blockForEventAvailable() method, used to block the thread of control until there are some pending events available; and the serverLoop() method, which repeatedly calls blockForEventAvailable(), followed by flushEvents().

Example W: Some elements of the LegionEventManager interface

class LegionEventManager {
public:
// There are two ways to announce an event
// (1) LegionEventAnnounceLater - Defer execution of 
// the handlers
// (2) LegionEventAnnounceNow - Immediately invoke the 
// handlers
   announce(LRef<LegionEvent>, 
      LegionEventQueuingDiscipline queueEvent  = 
         LegionEventAnnounceLater);
   // flush all events from the queue and execute the 
   // handlers
   unsigned flushEvents();
   // blocking call that returns only when there are 
   // events in the queue
   unsigned blockForEventAvailable();
   // the server loop repeatedly calls 
   // blockForEventAvailable and flush Events
   unsigned serverLoop();
};

7.7.4 Default protocol stack

The list of default LegionEventKinds and their associated LegionEventHandlers is shown in Table 3. These implement the protocol layers shown in Figure 18.

On the sending side, the program graph layer generates a LegionEvent_MethodSend event. The security handler LegionEvent_Can_I may disallow the remote method invocation [37]. If it doesn't, a following handler generates a LegionEvent_Message-Send event for each method invocation. Once the message has been successfully sent, the data delivery layer generates a LegionEvent_MessageComplete event.

On the receiving side, the data delivery layer will generate a LegionEvent_MessageReceive once it has successfully assembled a complete message. The LegionDefaultMessageHandler is the last handler for the event LegionEvent_MessageReceive and generates a LegionEvent_MethodReceive, once the invocation matcher has assembled a complete method invocation. The first handler for LegionEvent_MethodReceive is a security handler, and it implements access control on this object [37]. If the security handler grants access, the method invocation is deposited into the LegionInvocationStore, and a LegionEvent_MethodReady event is generated.

7.7.5 Adding new functionality to the Legion protocol stack

To add functionality to the existing stack, users may either define a new LegionEventKind or register their own handlers with one of the predefined events kinds. The latter option is the simpler.

Defining a new event kind consists of creating an instance of the class LegionEventKind with a unique identifier. For example:

LegionEventKind LegionEvent_Foobar (UniqueIdentifier);

Once the event kind has been defined, creating and announcing a LegionEvent can be done as shown below:

LegionEvent myEvent(LegionEvent_Foobar);
LegionDefaultEventMgr.announce(myEvent);

Adding a handler to an existing event kind is best illustrated through an example.

Here, a user can add a security layer to encrypt outgoing messages and decrypt incoming messages. We first define the handlers encryptionHandler() and decryptionHandler(), and register them with the appropriate LegionEventKind (Example X).

Example X: Adding encryption and decryption capabilities to the protocol stack

// Declaration of the encryption handler
LegionEventHandlerStatus encryptionHandler
(LRef<LegionEvent> ev)
{
      // extract the LegionMessage from the data
      // field of the event, encrypt the message,
      // allow the next handler to be called
      returns TRUE;
}
// Declaration of the decryption handler
LegionEventHandlerStatus decryptionHandler
(LRef<LegionEvent> ev) 
{
      // extract the LegionMessage from the data
      // field of the event, decrypt the message,
      // allow the next handler to be called
      returns TRUE;
}
// Register the handlers with the appropriate
// LegionEventKind
// The encryptionHandler should be the last handler
// before the message is sent by the data delivery layer
LegionEvent_MessageSend.addHandler(encryptionHandler, encryptionPriority);
// The decryptionHandler should be the first handler
// called after the message is delivered by the date
// deliver layer
LegionEvent_MessageRecv.addHandler(decryptionHandler, decryptionPriority);

For encryption, we would like the encryption handler to be the last handler called when sending a message. For decryption, on the other hand, we need to call the decryption handler first when a message is received. These ordering constraints are realized by registering encryptionHandler() with a high priority number and decryptionHandler() with a low priority number. The new protocol stack is shown in Figure 19.

Figure 19: Layered protocol stack with encryption and decryption added.

7.7.6 Active messages

The active messages programming model [35] is a message passing scheme that is intended to integrate communication and computation in order to increase the compute/communicate overlap, thereby masking the latency of message passing and increased performance. The basic idea behind active messages is simple: messages are prepended with the address of a handler routine that is automatically invoked upon receipt of the message. Active messages are not buffered and explicitly received, as is common with standard message passing interfaces. Instead, the receiving process invokes the handler routine specified for the message immediately upon message arrival. The handler may execute as a new thread of control, or may interrupt the running computation. The job of the active message handler is to incorporate the received message into the on-going computation.

A Legion version of active messages could be constructed by making Legion methods serve as message handlers, and by replacing the Legion "method ready" event handler with one that creates a new thread to service incoming methods, instead of buffering them in an invocation store. Pseudo-code for such a method invocation handler is given in Example Y.

Example Y: A sample method handler for implementing active messages

int ActiveMessageMethodHandler(LRef<LegionEvent> ev)
   {
   // Extract the work unit from the event
   LegionMethodEventStructure *mes;
   mes = (LegionMethodEventStructure *)ev->getData();
   LRef<LegionWorkUnit> wu = mes->work_unit;
   // Spawn a thread with the appropriate start-up
   // function based on the function identifier 
   // associated with the method
invoke_method(LRef<LegionWorkUnit> wu)
   {
   LRef<LegionFunctionIdentifier> this_fid;
   this_fid = wu->get_function_identifier();
   if (this_fid == NULL) 
      return 0;
   if (*this_fid == method1_function_id)
      {
      pthread_create(&thr_id, &thr_attrib, method1, wu);
      return 1;
      }
   }
      // Similar cases for other methods...
   }

This method ready event handler would need to be registered with the method ready event kind. The code to do this might look like:

LegionEvent_MethodReady.addHandler(ActiveMessageMethodReady,1.0);

This line of code would need to be executed before any methods arrived at the object. This can be achieved by placing this line of code before any calls to Legion.AcceptMethods().

The effect of this new method ready event handler is to provide an active messages style programming model. In some ways, the model supported here is more general than the traditional active messages model. For example, if a method (i.e., a handler) required two messages from different sources for activation, this requirement would be enforced by the Legion invocation matcher. Programs might be entirely composed of standard single-token active messages, providing a programming model as flexible as the original. On the other hand, programs might also include multi-token active messages, for a more general programming model that might best be called "active methods."

7.7.7 Path expressions

The various method invocation semantics covered thus far have offered a "one size fits all" concurrency control mechanism. For example, the supported remote procedure call model allows exactly one method to be serviced at a time by a given object. The active messages approach, on the other hand, allows any number of operations of all types to be active at the same time in the same object. A more general approach to customizing the concurrency control requirements of operations on an object can be designed based on path expressions [5]. Path expressions permit the programmer to specify: (1) sequencing constraints among operations; (2) selection (mutual exclusion) between operations; and (3) allowable concurrency between operations. These concurrency control primitives let programmers maintain the sequential consistency of their programs and at the same time indicate potential concurrency to a run-time environment.

Path expression based method sequence could be implemented for Legion objects, again by utilizing the inherent configurability of the Library's protocol stack. As with active messages, supporting a different method invocation semantic requires replacing the Legion method ready event handler. In this case, the method ready handler must examine the function identifiers of available operations and determine if they may be safely fired, given the ordering constraints specified by the program's path expressions. If a method can be safely fired, a new thread is created and allowed to run, starting at the entry point for the given member function (as in the active messages case). On the other hand, if the ordering constraints of a newly arrived method are not satisfied, the method must be buffered (e.g. in a library-provided invocation store) and later extracted and fired, when safe. This need to defer the firing of methods requires that code be executed whenever methods complete execution. One possible way to satisfy this requirement is to use LegionEvent_MethodDone event kind, and announce events of this kind when methods complete execution. A handler for this event kind can then be used to re-evaluate buffered methods with respect to the path expression ordering constraints whenever a running operation completes.

To examine the implementation of the scheme in more detail, we assume a path expression run-time support class, PathExpressionManager, that exports methods to specify the ordering, selection, and sequencing constraints of operations (i.e., Legion method function identifiers). This class would also support methods to determine if a given method is safe to fire, and to determine which (if any) methods are ready to be fired upon the completion of a running operation. The first modification we must make to the Library configuration is to add a new method event handler that might look like that of Example Z.

Example Z: A sample method handler for implementing path expressions

in PathExprMethodHandler(LRef<LegionEvent> ev)
   {
   // Extract the work unit from the event
   LegionMethodEventStructure *mes;
   mes = (LegionMethodEventStructure*)ev->getData{};
   LRef<LegionWorkUnit> wu = mes->work_unit;
   LRef<LegionFunctionIdentifier>
      function_identifier =
      wu->get_function_identifier();
   if(PathExpressionManager.canFire(function_identifier))
      {
      // We can safely fire this method now
PathExpressionManager.runningOperation(function_identifier);
invoke_method(LRef<LegionWorkUnit> wu)
   {
   LRef<LegionFunctionIdentifier> this_fid;
   this_fid = wu->get_function_identifier();
   if (this_fid == NULL) 
      return 0;
   if (*this_fid == method1_function_id)
      {
      pthread_create(&thr_id, &thr_attrib, method1, wu);
      return 1;
      }
   }
   // Similar cases for other methods...
      }
   else
      }
      // Buffer this method until ordering constraints are met
      LegionInvocationStoreDefault->insert(wu);
      }
   }

This method handler would need to be registered with the Legion method ready event kind, as in the case of the active messages handler. This method handler would need to be registered with the Legion method ready event kind, as in the case of the active message handler. The other requirement of our path expression solution is that code be executed upon method completion in order to re-evaluate the safety of firing buffered methods. To accomplish this, we use method done events that must be announced whenever a method is finished running. A handler (Example AA) must be registered with the LegionEvent_MethodDone event kind that tries to fire any runnable buffered methods.