\subsection{Messages}

In \charmpp, \index{chare}chares, \index{group}groups and \index{nodegroup}
nodegroups communicate using messages. Sending a message \index{message} to an
object corresponds to an asynchronous method invocation.  Several variations on
messaging are available, regular \charmpp{} messages are objects of
\textit{fixed size}. One can have messages that contain pointers or variable
length arrays (arrays with sizes specified at runtime) and still have these
pointers to be valid when messages are sent across processors, with some
additional coding.  Also available is a mechanism for assigning
\textit{priorities} to messages that applies all kinds of messages, a detailed
discussion of priorities appears later in this section.

Like all other entities involved in asynchronous method invocation, messages
need to be declared in the {\tt .ci} file.

Message definitions that may appear in the {\tt .h} or {\tt .C} file are very
similar to class definitions in \CC.

In the {\tt .ci} file (the interface file), a message is declared as: 

\begin{alltt}
 message MessageType;
\end{alltt}

A message that contains variable length arrays is declared as:

\begin{alltt}
 message [varsize] MessageType \{
   type1 var_name1[];
   type2 var_name2[];
   type3 var_name3[];
\};
\end{alltt}

If the name of the message class is \uw{MessageType}, the class must inherit 
publicly from a class whose name is \uw{CMessage\_MessageType}. This class
is generated by the charm translator. Then message definition has the form:

\begin{alltt}
 class MessageType : public CMessage_MessageType \{
    // List of data and function members as in \CC
 \};
\end{alltt}


\subsubsection{Message Creation and Deletion}
\label{memory allocation}

\index{message}Messages are allocated using the \CC\ \kw{new} operator:

\begin{alltt}
 MessageType *msgptr =
  new [(int sz1, int sz2, ... , int priobits=0)] MessageType[(constructor arguments)];
\end{alltt}

The optional arguments to the new operator are used when allocating messages
with variable length arrays or \kw{prioritized} messages. \uw{sz1, sz2, ...}
denote the size (in appropriate units) of the memory blocks that need to be
allocated and assigned to the pointers that the message contains. The
\uw{priobits} argument denotes the size of a bitfield (number of bits) that
will be used to store the message priority.   

For example, to allocate a message whose class declaration is:

\begin{alltt}
class Message : public CMessage_Message \{
  // .. fixed size message
  // .. data and method members
\};
\end{alltt}

do the following:

\begin{alltt}
Message *msg = new Message;
\end{alltt}

To allocate a message whose class declaration is:

\begin{alltt}
class VarsizeMessage : public CMessage_VarsizeMessage \{
 public:
  int *firstArray;
  double *secondArray;
\};
\end{alltt}

do the following:

\begin{alltt}
VarsizeMessage *msg = new (10, 20) VarsizeMessage;
\end{alltt}

This allocates a \uw{VarsizeMessage}, in which \uw{firstArray} points to an
array of 10 ints and \uw{secondArray} points to an array of 20 doubles.  This
is explained in detail in later sections. 

To add a \index{priority}priority bitfield to this message, 

\begin{alltt}
VarsizeMessage *msg = new (10, 20, sizeof(int)*8) VarsizeMessage;
\end{alltt}

Note, you must provide number of bits which is used to store the priority as
the \uw{priobits} parameter. The section on prioritized execution describes how
this bitfield is used.

In Section~\ref{message packing} we explain how messages can contain arbitrary
pointers, and how the validity of such pointers can be maintained across
processors in a distributed memory machine.

When a message \index{message} is sent to a \index{chare}chare, the programmer
relinquishes control of it; the space allocated to the message is freed by the
system.  When a message is received at an entry point it is not freed by the
runtime system.  It may be reused or deleted by the programmer.  Messages can
be deleted using the standard \CC{} \kw{delete} operator.  

There are no limitations of the methods of message classes except that the
message class may not redefine operators \texttt{new} or \texttt{delete}.

\subsubsection{Message Packing}
\label{message packing}
\index{message packing}
\index{packed messages}

When one declares \charmpp\ messages in the \texttt{.ci} file, the translator
generates code to register those messages along with their size with the
runtime system. This information is later used to efficiently allocate messages
by the runtime system.

In many cases, the messages store {\em non-linear} data structures using
pointers.  Examples of these are binary trees, hash tables etc. Thus, the
message itself contains only a pointer to the actual data. When the message is
sent to the same processor, these pointers point to the original locations,
which are within the address space of the same processor, however, when such a
message is sent to other processors, these pointers will point to invalid
locations.

Thus, the programmer needs a way to ``serialize'' these messages
\index{serialized messages}\index{message serialization}{\em only if} the
message crosses the address-space boundary.  \charmpp{} provides a way to do
this serialization by allowing the developer to override the default
serialization methods generated by the \charmpp{} interface translator.

Such messages are declared in the {\tt .ci} file similar to the ordinary
messages:

\begin{alltt}
message PMessage;
\end{alltt}

Like all messages, the class \uw{PMessage} needs to inherit from
\uw{CMessage\_PMessage} and should provide two {\em static} methods: \kw{pack}
and \kw{unpack}. These methods are called by the \charmpp\ runtime system, when
the message is determined to be crossing address-space boundary. The prototypes
for these methods are as follows:

\begin{alltt}
static void *PMessage::pack(PMessage *in);
static PMessage *PMessage::unpack(void *in);
\end{alltt}

Typically, the following tasks are done in \kw{pack} method:

\begin{itemize}

\item Determine size of the buffer needed to serialize message data.

\item Allocate buffer using the \kw{CkAllocBuffer} function. This function
takes in two parameters: input message, and size of the buffer needed, and
returns the buffer.

\item Serialize message data into buffer (alongwith any control information
needed to de-serialize it on the receiving side.

\item Free resources occupied by message (including message itself.)  

\end{itemize}

On the receiving processor, the \kw{unpack} method is called. Typically, the
following tasks are done in the \kw{unpack} method:

\begin{itemize}

\item Allocate message using \kw{CkAllocBuffer} function. {\em Do not
use \kw{new} to allocate message here. If the message constructor has
to be called, it can be done using the in-place \kw{new} operator.}

\item De-serialize message data from input buffer into the allocated message.

\item Free the input buffer using \kw{CkFreeMsg}.

\end{itemize}

Here is an example of a packed-message implementation:

\begin{alltt}
// File: pgm.ci
mainmodule PackExample \{
  ...
  message PackedMessage;
  ...
\};

// File: pgm.h
...
class PackedMessage : public CMessage_PackedMessage
\{
  public:
    BinaryTree<char> btree; // Non-linear data structure used in e.g. only 
    static void* pack(PackedMessage*);
    static PackedMessage* unpack(void*);
    ...
\};
...

// File: pgm.C
...
void*
PackedMessage::pack(PackedMessage* inmsg)
\{
  int treesize = inmsg->btree.getFlattenedSize();
  int totalsize = treesize + sizeof(int);
  char *buf = (char*)CkAllocBuffer(inmsg, totalsize);
  // buf is now just raw memory to store the data structure
  int num_nodes = inmsg->btree.getNumNodes();
  memcpy(buf, &num_nodes, sizeof(int));  // copy numnodes into buffer
  buf = buf + sizeof(int);               // don't overwrite numnodes
  // copies into buffer, give size of buffer minus header
  inmsg->btree.Flatten((void*)buf, treesize);    
  buf = buf - sizeof(int);              // don't lose numnodes
  delete inmsg;
  return (void*) buf;
\}

PackedMessage*
PackedMessage::unpack(void* inbuf)
\{
  // inbuf is the raw memory allocated and assigned in pack
  char* buf = (char*) inbuf;
  int num_nodes;
  memcpy(&num_nodes, buf, sizeof(int));
  buf = buf + sizeof(int);
  // allocate the message through charm kernel
  PackedMessage* pmsg = 
    (PackedMessage*)CkAllocBuffer(inbuf, sizeof(PackedMessage));
  // call "inplace" constructor of PackedMessage that calls constructor
  // of PackedMessage using the memory allocated by CkAllocBuffer,
  // takes a raw buffer inbuf, the number of nodes, and constructs the btree
  pmsg = new ((void*)pmsg) PackedMessage(buf, num_nodes);  
  CkFreeMsg(inbuf);
  return pmsg;
\}
... 
PackedMessage* pm = new PackedMessage();  // just like always 
pm->btree.Insert('A');
...
\end{alltt}


While serializing an arbitrary data structure into a flat buffer, one must be
very wary of any possible alignment problems.  Thus, if possible, the buffer
itself should be declared to be a flat struct.  This will allow the \CC\
compiler to ensure proper alignment of all its member fields.

\subsubsection{Messages with Variable Length Arrays}
\label{varsize messages}
\index{variable size messages}
\index{varsize message}

An ordinary message in \charmpp\ is a fixed size message that is allocated
internally with an envelope which encodes the size of the message. Very often,
the size of the data contained in a message is not known until runtime. One can
use packed\index{packed messages} messages to alleviate this problem.  However,
it requires multiple memory allocations (one for the message, and another for
the buffer.) This can be avoided by making use of a \emph{varsize} message.
In \emph{varsize} messages, the space required for these variable length arrays
is allocated with the message such that it is contiguous to the message.

Such a message is declared as 

\begin{alltt}
 message mtype \{
   type1 var_name1[];
   type2 var_name2[];
   type3 var_name3[];
 \};
\end{alltt}

in \charmpp\ interface file. The class \uw{mtype} has to inherit from
\uw{CMessage\_mtype}. In addition, it has to contain variables of corresponding
names pointing to appropriate types. If any of these variables (data members)
are private or protected, it should declare class \uw{CMessage\_mtype} to be a
``friend'' class. Thus the \uw{mtype} class declaration should be similar to:

\begin{alltt}
class mtype : public CMessage_mtype \{
 private:
   type1 *var_name1;
   type2 *var_name2;
   type3 *var_name3;
   friend class CMessage_mtype;
\};
\end{alltt}

\tiny
\hrule

The \charmpp{} interface translator generates implementation for three static
methods for the message class \uw{CMessage\_mtype}. These methods have the
prototypes:

\begin{alltt}
    static void* alloc(int msgnum, size_t size, int* array, int priobits);
    static void* pack(mtype*);
    static mtype* unpack(void*);
\end{alltt}

One may choose not to use the translator-generated methods and may override
these implementations with their own \uw{alloc}, \uw{pack} and \uw{unpack}
static methods of the \uw{mtype} class.  The \kw{alloc} method will be called
when the message is allocated using the \CC\ \kw{new} operator. The programmer
never needs to explicitly call it.  Note that all elements of the message are
allocated when the message is created with \kw{new}. There is no need to call
\kw{new} to allocate any of the fields of the message. This differs from a
packed message where each field requires individual allocation. The \kw{alloc}
method should actually allocate the message using \kw{CkAllocMsg}, whose
signature is given below:

\begin{alltt}
void *CkAllocMsg(int msgnum, int size, int priobits); 
\end{alltt}  

\hrule
\normalsize

\noindent\textbf{An Example}

Suppose a \charmpp\ message contains two variable length arrays of types
\texttt{int} and \texttt{double}:

\begin{alltt} 
class VarsizeMessage: public CMessage_VarsizeMessage \{
  public:
    int lengthFirst;
    int lengthSecond;
    int* firstArray;
    double* secondArray;
    // other functions here
\};
\end{alltt}

Then in the \texttt{.ci} file, this has to be declared as: 

\begin{alltt}
message VarsizeMessage \{
  int firstArray[];
  double secondArray[];
\};
\end{alltt}

We specify the types and actual names of the fields that
contain variable length arrays. The dimensions of these arrays are NOT
specified in the interface file, since they will be specified in the
constructor of the message when message is created. In the {\tt .h} or {\tt .C}
file, this class is declared as:

\begin{alltt} 

class VarsizeMessage : public CMessage_VarsizeMessage \{ 
  public: 
    int lengthFirst;
    int lengthSecond;
    int* firstArray;
    double* secondArray;
    // other functions here
\};
\end{alltt}

The interface translator generates the \uw{CMessage\_VarsizeMessage} class,
which contains code to properly allocate, pack and unpack the
\uw{VarsizeMessage}.

\tiny
\hrule

The static methods \texttt{alloc}, \texttt{pack}, and \texttt{unpack} are
generated by the interface translator for the \uw{CMessage\_VarsizeMessage}
class. Thus, one is spared from having to write them.  For example, these
methods for the above class would be similar to:

\begin{alltt}
// allocate memory for varmessage so charm can keep track of memory
static void* alloc(int msgnum, size_t size, int* array, int priobits)
\{
  int totalsize, first_start, second_start;
  // array is passed in when the message is allocated using new (see below).
  // size is the amount of space needed for the part of the message known
  // about at compile time.  Depending on their values, sometimes a segfault
  // will occur if memory addressing is not on 8-byte boundary, so altered
  // with ALIGN8
  first_start = ALIGN8(size);  // 8-byte align with this macro
  second_start = ALIGN8(first_start + array[0]*sizeof(int));
  totalsize = second_start + array[1]*sizeof(double);
  VarsizeMessage* newMsg = 
    (VarsizeMessage*) CkAllocMsg(msgnum, totalsize, priobits);
  // make firstArray point to end of newMsg in memory
  newMsg->firstArray = (int*) ((char*)newMsg + first_start);
  // make secondArray point to after end of firstArray in memory
  newMsg->secondArray = (double*) ((char*)newMsg + second_start);

  return (void*) newMsg;
\}

// returns pointer to memory containing packed message
static void* pack(VarsizeMessage* in)
\{
  // set firstArray an offset from the start of in
  in->firstArray = (int*) ((char*)in->firstArray - (char*)in);
  // set secondArray to the appropriate offset
  in->secondArray = (double*) ((char*)in->secondArray - (char*)in);
  return in;
\}

// returns new message from raw memory
static VarsizeMessage* VarsizeMessage::unpack(void* inbuf)
\{
  VarsizeMessage* me = (VarsizeMessage*)inbuf;
  // return first array to absolute address in memory
  me->firstArray = (int*) ((size_t)me->firstArray + (char*)me);
  // likewise for secondArray
  me->secondArray = (double*) ((size_t)me->secondArray + (char*)me);
  return me;
\}
\end{alltt}

The pointers in a varsize message can exist in two states.  At creation, they
are valid \CC\ pointers to the start of the arrays.  After packing, they become
offsets from the address of the pointer variable to the start of the pointed-to
data.  Unpacking restores them to pointers. 

\hrule
\normalsize

One can allocate messages of the \uw{VarsizeMessage} class as follows:

\begin{alltt}
// firstArray will have 4 elements
// secondArray will have 5 elements 
VarsizeMessage* p = new(4, 5, 0) VarsizeMessage;
p->firstArray[2] = 13;     // the arrays have already been allocated 
p->secondArray[4] = 6.7; 
\end{alltt}

\tiny
\hrule

Another way of allocating a varsize message is to pass a \uw{sizes} in an array
instead of the parameter list. For example,

\begin{alltt}
int sizes[2];
sizes[0] = 4;               // firstArray will have 4 elements
sizes[1] = 5;               // secondArray will have 5 elements 
VarsizeMessage* p = new(sizes, 0) VarsizeMessage;
p->firstArray[2] = 13;     // the arrays have already been allocated 
p->secondArray[4] = 6.7; 
\end{alltt}

\hrule
\normalsize

No special handling is needed for deleting varsize messages.

\subsubsection{Prioritized Execution}
\label{prioritized message passing}
\index{prioritized execution}
\index{prioritized message passing}
\index{priorities}

By default, \charmpp\ will process the messages you send in roughly
FIFO\index{message delivery order} order.  For most programs, this
behavior is fine.  However, some programs need more explicit control
over the order in which messages are processed.  \charmpp\ allows you
to control queueing behavior on a per-message basis.

The simplest call available to change the order in which messages
are processed is \kw{CkSetQueueing}.

\function{void CkSetQueueing(MsgType message, int queueingtype)}

where \uw{queueingtype} is one of the following constants:

\begin{alltt}
  CK_QUEUEING_FIFO
  CK_QUEUEING_LIFO
  CK_QUEUEING_IFIFO
  CK_QUEUEING_ILIFO
  CK_QUEUEING_BFIFO
  CK_QUEUEING_BLIFO
\end{alltt}

The first two options,  \kw{CK\_QUEUEING\_FIFO} and
\kw{CK\_QUEUEING\_LIFO}, are used as follows: 

\begin{alltt}
  MsgType *msg1 = new MsgType ;
  CkSetQueueing(msg1, CK_QUEUEING_FIFO);

  MsgType *msg2 = new MsgType ;
  CkSetQueueing(msg2, CK_QUEUEING_LIFO);
\end{alltt}

When message \kw{msg1} arrives at its destination, it will be pushed onto the
end of the message queue as usual.  However, when \kw{msg2} arrives, it will be
pushed onto the {\em front} of the message queue.

The other four options involve the use of priorities\index{priorities}.  To
attach a priority field to a message, one needs to set aside space in the
message's buffer while allocating the message\index{message priority}.  To
achieve this, the size of the priority field\index{priority field} in bits
should be specified as a placement argument to the \kw{new} operator, as
described in Section \ref{memory allocation}.  Although the size of the
priority field is specified in bits, it is always padded to an integral number
of {\tt int}s.  A pointer to the priority part of the message buffer can be
obtained with this call:

\function{unsigned int *CkPriorityPtr(MsgType msg)}
\index{CkPriorityPtr}
\index{priority pointer}

There are two kinds of priorities which can be attached to a message:
{\sl integer priorities}\index{integer priorities} and {\sl bitvector
priorities}\index{bitvector priorities}.  Integer priorities are quite
straightforward.  One allocates a message, setting aside enough space
(in bits) in the message to hold the priority, which is an integer.
One then stores the priority in the message.  Finally, one informs the
system that the message contains an integer priority using
\kw{CkSetQueueing}:

\begin{alltt}
  MsgType *msg = new (8*sizeof(int)) MsgType;
  *CkPriorityPtr(msg) = prio;
  CkSetQueueing(msg, CK_QUEUEING_IFIFO);
\end{alltt}

The predefined constant  \kw{CK\_QUEUEING\_IFIFO} indicates that the
message contains an integer priority, and that if there are other
messages of the same priority, they should be sequenced in FIFO order
(relative to each other).  Similarly, a  \kw{CK\_QUEUEING\_ILIFO} is
available.  Note that  \kw{MAXINT} is the lowest priority, and {\bf
NEGATIVE\_MAXINT} is the highest priority\index{integer priority range}.

Bitvector priorities are somewhat more complicated.  Bitvector
priorities are arbitrary-length bit-strings representing fixed-point
numbers in the range 0 to 1.  For example, the bit-string ``001001''
represents the number .001001\raisebox{-.5ex}{\scriptsize binary}.  As
with the simpler kind of priority, higher numbers represent lower
priorities.  Unlike the simpler kind of priority, bitvectors can be of
arbitrary length, therefore, the priority numbers they represent can
be of arbitrary precision.

Arbitrary-precision priorities\index{arbitrary-precision priorities}
are often useful in AI search-tree applications.  Suppose we have a
heuristic suggesting that tree node $N_1$ should be searched before
tree node $N_2$.  We therefore designate that node $N_1$ and its
descendants will use high priorities, and that node $N_2$ and its
descendants will use lower priorities.  We have effectively split the
range of possible priorities in two.  If several such heuristics fire
in sequence, we can easily split the priority range \index{priority
range splitting} in two enough times that no significant bits remain,
and the search begins to fail for lack of meaningful priorities to
assign.  The solution is to use arbitrary-precision priorities,
i.e. bitvector priorities.

To assign a bitvector priority, two methods are available.  The
first is to obtain a pointer to the priority field using  \kw{CkPriorityPtr},
and to then manually set the bits using the bit-setting operations
inherent to C.  To achieve this, one must know the format
\index{bitvector format} of the
bitvector, which is as follows: the bitvector is represented as an
array of unsigned integers.  The most significant bit of the first
integer contains the first bit of the bitvector.  The remaining bits
of the first integer contain the next 31 bits of the bitvector.
Subsequent integers contain 32 bits each.  If the size of the
bitvector is not a multiple of 32, then the last integer contains 0
bits for padding in the least-significant bits of the integer.

The second way to assign priorities is only useful for those who are
using the priority range-splitting\index{priority range splitting}
described above.  The root of the tree is assigned the null
priority-string.  Each child is assigned its parent's priority with
some number of bits concatenated.  The net effect is that the entire
priority of a branch is within a small epsilon of the priority of its
root.

It is possible to utilize unprioritized messages, integer priorities,
and bitvector priorities in the same program.  The messages will be
processed in roughly the following order\index{multiple priority types}:

\begin{itemize}

\item Among messages enqueued with bitvector priorities, the
messages are dequeued according to their priority.  The
priority ``0000...'' is dequeued first, and ``1111...'' is
dequeued last.

\item Unprioritized messages are treated as if they had the
priority ``1000...'' (which is the ``middle'' priority, it
lies exactly halfway between ``0000...'' and ``1111...'').
 
\item Integer priorities are converted to bitvector priorities.  They
are normalized so that the integer priority of zero is converted to
``1000...'' (the ``middle'' priority).  To be more specific, the
conversion is performed by adding 0x80000000 to the integer, and then
treating the resulting 32-bit quantity as a 32-bit bitvector priority.

\item Among messages with the same priority, messages are
dequeued in FIFO order or LIFO order, depending upon which
queuing strategy was used.

\end{itemize} 

A final warning about prioritized execution: \charmpp\ always processes
messages in {\it roughly} the order you specify; it never guarantees to
deliver the messages in {\it precisely} the order\index{message
delivery order} you specify.
However, it makes a serious attempt to be ``close'', so priorities
can strongly affect the efficiency of your program.

\subsubsection{Entry Method Attributes}
\label{attributes}

\charmpp{}  provides a handful of special attributes that \index{entry
method}entry methods may have.  In order to give a particular \index{entry
method}entry method an attribute, you must specify the keyword for the desired
attribute in the attribute list of that entry method's {\tt .ci} file
declaration.  The syntax for this is as follows:

\begin{alltt}
entry [attribute1, ..., attributeN] void EntryMethod(MessageType *);
\end{alltt}

\charmpp{} currently offers four attributes that one may give an entry method:
\kw{threaded}, \kw{sync}, \kw{exclusive}, and \kw{virtual}.

\index{threaded}Threaded \index{entry method}entry methods are simply entry
methods which are run in their own nonpremptible threads.  To make an
\index{entry method}entry method threaded, one simply adds the keyword
\kw{threaded} to the attribute list of that entry method.

\index{sync}Sync \index{entry method}entry methods are special in that calls to
sync entry methods are blocking - they do not return control to the caller
until the method is finished executing completely.  Sync methods may have
return values; however, they may only return messages.  To make an \index{entry
method}entry method a sync entry method, add the keyword \kw{sync} to the
attribute list of that entry method.

\index{exclusive}Exclusive entry methods, which exist only on node groups, are
\index{entry method}entry methods that do not execute while other exclusive
\index{entry method}entry methods of its node group are executing in the same
node.  If one exclusive method of a node group is executing on node 0, and
another one is scheduled to run on that same node, the second exclusive method
will wait for the first to finish before it executes.  To make an \index{entry
method}entry method exclusive, add the keyword \kw{exclusive} to that
entry method's attribute list.

\index{virtual}Virtual \index{entry method}entry methods are inherited in the
same manner as virtual methods of sequential \CC{} objects.  For a detailed
discussion of inheritance in \charmpp{}, refer to section \ref{inheritance and
templates}.  To make an entry method virtual, just add the keyword \kw{virtual}
to that method's attribute list.  Additionally, one may make a virtual
\index{entry method}entry method a pure virtual entry method.  They behave in
the same way as pure virtual methods in \CC{} and are declared in a very
similar fashion.  To make a virtual entry method pure, add a ``= 0'' after that
entry method's {\tt .ci} file declaration.  This looks like the following:

\begin{alltt}
entry [virtual] void PureVirtualEntry(MessageType *) = 0;
\end{alltt}
