\section{Message Library}\label{sec:msg}

We now turn our attention from how protocols invoke operations on each
other, and consider what goes on inside a particular protocol.  One of
the most common things that a protocol does is manipulate messages.
For example, they add headers to, and strip headers from, messages.
Another common way in which protocols manipulate messages is to break
a single message into multiple fragments, and later to join these
multiple fragments back into a single message. This is necessary
because most network links allow messages of only a certain size to be
transmitted. Thus, a protocol that uses such a link to transmit a
large message must first {\it fragment} the message on the source
node, and then {\it reassemble} the fragments back into the original
message on the destination node. We will see examples of protocols
that fragment and reassemble messages in later sections.

Because manipulating messages is a basic part of all protocols, the
$x$-kernel defines an abstract data type---called {\it message} and
given by the C type definition {\var Msg}---that includes an interface
for performing these common operations. This section presents the
$x$-kernel's message abstraction. (See \cite{Message} for a detailed
description of how the message library is implemented.)

The message abstraction can best be viewed as a byte string of some
length. For the purpose of this discussion, we use the term
``message'' to refer to the abstract object and we use the term
``data'' to refer to the actual byte string contained in a message.
For example, message $m$ schematically depicted in
Figure~\ref{simple_msg} contains the data ``abcdefg''.

\begin{figure}[ht]
\centering
\leavevmode\hbox{\epsfig{file=simple_msg.ps,height=0.75in}}
\caption{Message object containing a byte string.}\label{simple_msg}
\end{figure}

In effect, the operations on the message object can be viewed as
string manipulations.  For example, while processing an outgoing
message, each of several protocols may add a header to the message
(i.e., two strings are concatenated) and fragment the message into two
or more packets (i.e., a string is divided into two substrings).
Similarly, while processing an incoming message, each of several
protocols may strip headers from the message (i.e., a string is
removed from the front of another string) and reassemble message
fragments (i.e., two strings are concatenated). In addition, each of
several protocols may save references to portions of a message for
future use, e.g., to retransmit in the event of an error in the
network.  Thus, any given byte may be attached to several different
strings, removed from several different strings, and referenced by
several different protocols.

\subsection{Adding and Stripping Headers}

As outgoing messages move down the protocol graph, each protocol
attaches (pushes) its header onto the front of the message. Similarly,
as an incoming message moves up the protocol graph, each protocol
strips (pops) its header from the front of the message. The message
object supports the following two operations for pushing and popping
headers:

\begin{quote}
{\var char *msgPush(Msg *message, int length)}\\
\\
{\var char *msgPop(Msg *message, int length)}
\end{quote}

\noindent Both operations return a pointer to a buffer that contains
the header. In the case of {\var msgPush}, room for {\var length}
bytes is attached to the front of the {\var message}, and a pointer to
this memory location is returned. The protocol can then write the
header to this location to effectively add the header to the message.
In the case of {\var msgPop}, {\var length} bytes are removed from the
front of the message. The protocol can then read the header available
at the returned memory location.  Figures~\ref{push} and \ref{pop}
illustrate the semantics of the two operations.

\begin{figure}[ht]
\centering
\leavevmode\hbox{\epsfig{file=push.ps,height=1.5in}}
\caption{Effects of msgPush operation.}\label{push}
\end{figure}

\begin{figure}[ht]
\centering
\leavevmode\hbox{\epsfig{file=pop.ps,height=1.5in}}
\caption{Effects of msgPop operation.}\label{pop}
\end{figure}

\subsection{Fragmenting and Reassembling Messages}

Fragmenting and reassembling messages is a common activity in network
protocols.  The $x$-kernel supports the following two operations for
manipulating message fragments:

\begin{quote}
{\var void msgBreak(Msg *original\_message, Msg *fragment\_message, int\ length)}\\
\\
{\var void msgJoin(Msg *new\_message, Msg *fragment1, Msg *fragment2)}
\end{quote}

\noindent The first operation creates a pair of messages
by breaking {\var length} bytes off the front of the {\var
original\_message} and placing them in {\var fragment\_message}.
After the operation returns, {\var original\_message} contains the
sequence of bytes that remain after {\var length} bytes are removed.
The second operation attaches {\var fragment1} to the front of {\var
fragment2}, producing {\var new\_message}.  The arguments to {\var
msgJoin} need not refer to distinct messages. One common use of {\var
msgJoin} is to attach a fragment to the end of a larger message, in
which case the first two arguments are the same (the larger message)
and the third argument is the fragment.  These two operations are
illustrated in Figures~\ref{break} and \ref{join}.

\begin{figure}[ht]
\centering
\leavevmode\hbox{\epsfig{file=break.ps,height=1.5in}}
\caption{Effects of msgBreak operation.}\label{break}
\end{figure}

\begin{figure}[ht]
\centering
\leavevmode\hbox{\epsfig{file=join.ps,height=1.5in}}
\caption{Effects of msgJoin operation.}\label{join}
\end{figure}

\subsection{Traversing Messages}

So as to avoid the unnecessary copying of data from one buffer to
another, the message object is implemented by a tree of buffers. (See
\cite{Message} for a description of this data structure.)  Because the
data contained in a message object is scattered over multiple,
non-contiguous memory buffers, the $x$-kernel provides a set of
operations for walking the tree and extracting the actual data.

\begin{quote}
{\var void msgWalkInit(MsgWalk cxt, Msg *message)}\\
\\
{\var char *msgWalkNext(MsgWalk cxt, int *len)}\\
\\
{\var void msgWalkDone(MsgWalk cxt)}
\end{quote}

\noindent Operation {\var msgWalkNext} traverses the message tree, and
returns a pointer to the next chunk of data in the message; it also
sets {\var len} to the number of bytes in that chunk. Argument {\var
cxt} maintains the context for the message traversal, so that {\var
msgWalkNext} knows how far through the tree it got on the last
invocation.  The other two operations---{\var msgWalkInit} and {\var
msgWalkDone}---initialize and destroy this context, respectively.

As a simple example of how one might use {\var msgWalkNext}, device
drivers often create an array of pointers to the various pieces of the
message (along with each piece's length). Arrays of buffer/length
pairs are commonly accepted by network devices, so this might be
something that is done by a network device driver to prepare an
$x$-kernel message for transmission over a physical link.

\subsection{Other Operations}

There are additional operations that can be applied to message objects,
as summarized below:

\begin{quote}
{\var void msgConstructEmpty(Msg *message)}\\
\\
{\var void msgConstructBuffer(Msg *message, char *buffer, int length)}\\
\\
{\var char *msgConstructAllocate(Msg *message, int length)}\\
\\
{\var void msgAssign(Msg *message\_1, Msg *message\_2)}\\
\\
{\var int msgLength(Msg *message)}
\end{quote}

The first three operations are used to create messages. Each is used
under a different set of circumstances. {\var msgConstuctEmpty} creates
an empty message. It is used in conjunction with {\var msgAssign} to
save a reference to a message. For example, if a given protocol wants
to send a particular message $m$ out over the network, but at the same
time save a copy of $m$ in case it needs to retransmit it in the
future, it might use {\var msgConstructEmpty} to create an empty
message $n$, and then do {\var msgAssign}($m, n$). At this point both
$m$ and $n$ represent the same message (the same byte string).

The other two message constructors create messages with an associated
data component. {\var msgConstructBuffer} builds a message from the
existing byte string referenced by {\var buffer}. This operation is
used, for example, by an application program that already possesses a
buffer of data it wants to transmit; it uses {\var msgConstructBuffer}
to encapsulate this buffer in a message object.  In contrast, {\var
msgConstructAllocate} is used when a protocol knows it is going to
need a message to hold {\var length} bytes of data, but it does not
yet have the data to place in the message. This operation is used, for
example, in a device driver that knows it will eventually receive a
packet from the network of some size. It invokes {\var
msgConstructAllocate} to create the message, and gets a pointer to a
memory buffer that is free to hold data in return. The device driver
would then program the network adaptor to receive the next packet into
this buffer.