\section{Example Protocol}\label{sec:example}

This section presents an example protocol---A Simple Protocol
(ASP)---that illustrates how the interfaces and support routines
described in previous sections are used. ASP is a complete, working
protocol that is typically configured on top of IP in an $x$-kernel
protocol graph. Because of its simplicity, ASP does not implement any
interesting algorithms; it only serves to illustrate the boilerplate
code that is common to all protocols. The next section illustrates
some of the more complicated things that protocols do.

ASP supports an unreliable message delivery service, where the two
end-points of an ASP channel are identified by a pair of {\it ports}.
In the $x$-kernel, a session object implements each end-point of an
ASP channel, with each session uniquely identified by the following
4-tuple:

\begin{quote}
$\langle$ {\var local IP host, remote IP host, local ASP port, remote ASP port} $\rangle$
\end {quote}

\noindent In other words, ASP demultiplexes each incoming message to the
appropriate session by using this 4-tuple as a demux key.  This is
ASP's only significant function---to add a multiplexing/demultiplexing
function to the protocols below it.

ASP does very little processing on each message---it only checks the
length of the received messages, and truncates the message to the
specified length, if necessary. ASP is an unreliable protocol,
in the sense that it adds no reliability to the protocols below it; i.e.,
it does not retransmit lost messages.

\subsection{Header Files}

By convention, the header information required by ASP is organized
into two files: {\var asp.h} and {\var asp\_internal.h}.  File {\var
asp.h} contains only definitions required by other protocols;
protocols that depend on ASP must include {\var asp.h} in order to use
these definitions. In the case of ASP, {\var asp.h} defines the ASP
port to be an unsigned short (16-bit value).

\begin{verbatim}
/* 
 * asp.h
 */

typedef u_short ASPport;
\end{verbatim}

File {\var asp\_internal.h} contains ASP-specific definitions that
other protocols do not need to know about. For example, it defines the
format of the ASP header ({\var ASPhdr}), protocol-specific state
information ({\var ProtlState}), and session-specific state information
({\var SessnState}).


\begin{verbatim}
/* 
 * asp_internal.h 
 */
#include "xkernel.h"
#include "ip.h"
#include "asp.h"

/* ASP message header definition */

typedef struct header {
    ASPport sport;  /* source port      */
    ASPport dport;  /* destination port */
    u_short ulen;   /* ASP length       */
} ASPhdr;

#define HLEN (sizeof(ASPhdr))

/* protocol and session states */

typedef struct pstate {
    Map activemap;
    Map passivemap;
} ProtlState;

typedef struct sstate {
    ASPhdr hdr;
} SessnState;

/* active and passive maps */

typedef struct {
    Sessn   lls;
    ASPport localport;
    ASPport remoteport;
} ActiveId;

typedef ASPport PassiveId;

#define ACTIVE_MAP_SIZE  101
#define PASSIVE_MAP_SIZE 23

/* UPI function declarations */

void            asp_init(Protl);
static Sessn    aspOpen(Protl, Protl, Protl, Part *);
static XkReturn aspOpenEnable(Protl, Protl, Protl, Part *);
static XkReturn aspDemux(Protl, Sessn, Msg *);
static XkHandle aspPush(Sessn, Msg *);
static XkReturn aspPop(Sessn, Sessn, Msg *, void *);
static Sessn    aspCreateSessn(Protl, Protl, Protl, ActiveId *);
static XkReturn aspClose(Sessn);
static int      aspControlProtl(Protl, int, char *, int) ;
static int      aspControlSessn(Sessn, int, char *, int) ;
static Part     *aspGetParticipants(Sessn);

/* internal function declarations */

static void     getproc_protl(Protl);
static void     getproc_sessn(Sessn);
static long     aspHdrLoad(ASPhdr *, char *, long);
static void     aspHdrStore(ASPhdr *, char *, long);

/* trace variable used in conjunction with xTrace stmts */
int traceaspp;

\end{verbatim}

One of the main definitions contained in {\var asp\_internal.h}
concerns the demultiplexing function. In particular, the state
associated with the ASP protocol object includes two maps: {\var
activemap} and {\var passivemap}. The former map is used by ASP's
demux routine to map incoming messages to an existing session. It uses
{\var ActiveId} as the demultiplexing key. Although conceptually the
active map key is given by the 4-tuple described above, in practice,
we take advantage of the fact that the underlying IP session already
corresponds to a local/remote host pair, and we use this session
object in lieu of these two IP addresses.

The second map---{\var passivemap}---is used to record high-level
protocols that have done a passive open on ASP. In this case, the
corresponding key that is used to search this map, called the
{\var PassiveId}, is given by the ASP port on which the local
protocol has done an {\var xOpenEnable}.

The session state contains a header template which is copied to the
front of outgoing messages. The ASP message header consists of local
and remote port numbers, and a field indicating the length of the data
message plus ASP header.

\subsection{Initialization}\label{initialization}

The C functions that implement a given protocol can be distributed
across multiple {\var .c} files. In the case of ASP, they are all
contained in a single file named {\var asp.c}. The rest of this
section walks through these functions one at at time.

We begin with function {\var asp\_init}, which is called at system
startup time.  This function initializes the ASP protocol object,
including protocol state and maps. It then does an {\var xOpenEnable}
call on the protocol configured below it (usually IP) to inform it
that ASP is willing to accept messages from any host.  {\var xGetDown}
is used to obtain a handle for the protocol that was configured below
ASP. (In theory, ASP may have more than one protocol configured below
it; the second argument to {\var xGetDown} asks for the first of these.)

\begin{verbatim}
void
asp_init(Protl self)
{
    ProtlState *pstate;
    Protl      llp;
    Part       part;

    getproc_protl(self);

    /* create and initialize protocol state */
    pstate = X_NEW(ProtlState);
    bzero((char *)pstate, sizeof(ProtlState));
    self->state = (void *)pstate;
    pstate->activemap  = mapCreate(ACTIVE_MAP_SIZE, sizeof(ActiveId));
    pstate->passivemap = mapCreate(PASSIVE_MAP_SIZE, sizeof(PassiveId));

    /* find lower level protocol and do a passive open on it */
    llp = xGetProtlDown(self, 0);
    if (!xIsProtl(llp))
        Kabort("ASP could not get lower protocol");
    partInit(&part, 1);
    partPush(part, ANY_HOST, 0);
    if (xOpenEnable(self, self, llp, &part) == XK_FAILURE) {
        xTrace0(aspp, TR_ALWAYS,
               "asp_init: openenable on lower protocol failed");
        xFree((char *) pstate);
        return;
    }
}\end{verbatim}

Because in this example we are dealing not just with the interfaces
between objects but with their implementation, we need to deal with
some of the internal structure of the {\var Protl} and {\var Sessn}
objects, which we have glossed over up until now. For example, in the
preceding code, we initialized the {\var state} data structure in the
ASP {\var Protl} object. One important part of initialization of the
{\var Protl} object is to fill in the table that will cause operations
on the object (e.g., {\var xOpen}) to invoke the appropriate function
to implement that operation (e.g., {\var aspOpen)}. In the case of
ASP, the subroutine {\var getproc\_protl} fills out this operation
table:

\begin{verbatim}
static void
getproc_protl(Protl p)
{
    /* fill in the function pointers to implement protocol operations */
    p->open         = aspOpen;
    p->openenable   = aspOpenEnable;
    p->demux        = aspDemux;
    p->controlprotl = aspControlProtl;
}
\end{verbatim}

\subsection{Opening Connections}

When a high level protocol wishes to establish an ASP channel to a
remote host, it will call {\var xOpen}, which causes {\var aspOpen} to
be called.  This function extracts the local and remote ASP ports from
the participant list passed down by the high level protocol, and
passes the resulting participant list, via another {\var xOpen} call,
down to IP. A new ASP session ({\var asp\_s}) is then created to
handle messages sent and received on this channel.  If a high level
protocol attempts to re-open a channel---i.e., one that is found in the
active map---the open fails; otherwise, the newly created session is
returned to the calling protocol. 

Notice that {\var aspOpen} uses the $x$-kernel operation {\var
partPop} to extract address information from the participant list;
there is also a {\var partPush} operation that is used to attach
addressing information to the participant list. Briefly, the
participant list is an array of addresses, where by convention, the
first element of this array identifies the remote participant and the
second element identifies the local participant.  Each element in the
array is, in turn, represented by a stack of addresses; hence ``push''
and ``pop'' in the operation names. It is a stack rather than a flat
structure because a given participant might be identified with a
multi-component address, for example, a host address and a port
number. In this example, {\var aspOpen} extracts the port number from
each stack, but leaves the host number on the stack for some lower
level protocol (e.g., IP) to process.

\begin{verbatim}
static Sessn
aspOpen(self, hlp, hlpType, p)
Protl self, hlp, hlpType;
Part  *p;
{
    ActiveId   key;
    Sessn      asp_s, lls;
    ProtlState *pstate = (ProtlState *)self->state;

    bzero((char *)&key, sizeof(key));

    /* high level protocol must specify both local and remote ASP port */
    key.remoteport = *((ASPport *)partPop(p[0]));
    key.localport  = *((ASPport *)partPop(p[1]));

    /* attempt to open session on protocol below this one */
    lls = xOpen(self, self, xGetProtlDown(self, 0), p);
    if (lls != ERR_SESSN) {
        key.lls = lls;
        /* check for this session in the active map */
        if (mapResolve(pstate->activemap, &key, (void **)&asp_s) == XK_FAILURE){
            /* session wasn't already in map, so initialize it */
            asp_s = aspCreateSessn(self, hlp, hlpType, &key);
            if (asp_s != ERR_SESSN)    /* A successful open! */
                return asp_s;
        }
        /* if control makes it this far, an error has occurred */
        xClose(lls);
    }
    return ERR_SESSN;
}
\end{verbatim}

Note that the real work of initializing the session is performed by
{\var asp\_init\_session}, presented below. Before we get into the
details of that routine, however, we'll take a look at {\var
aspOpenEnable}. This is the routine that is called indirectly through
{\var xOpenEnable} by a high level protocol that wants to do a passive
open on ASP. The high level protocol specifies its willingness to
receive messages on a specific ASP port, and {\var aspOpenEnable}
records this fact in its passive map.  Note that the $x$-kernel
defines an {\var Enable} object that is used by {\var aspOpenEnable}
to record the necessary information about the passive open, including
a reference count ({\var rcnt}) of how many times that particular port
has been enabled.  Also, keep in mind that a session object is not
created at this time; it will be created in {\var aspDemux} when a
message arrives addressed to that port.

\begin{verbatim}
static XkReturn
aspOpenEnable(Protl self, Protl hlp, Protl hlpType, Part *p)
{
    PassiveId  key;
    ProtlState *pstate = (ProtlState *)self->state;
    Enable     *e;

    key = *((ASPport *)partPop(*p));

    /* check if this port has already been openenabled */
    if (mapResolve(pstate->passivemap, &key, (void **)&e) != XK_FAILURE) {
        if (e->hlp == hlp) {
           /* this port was openenabled previously by the same hlp */
            e->rcnt++;
            return XK_SUCCESS;
        }
        /* this port was openenabled previously by a different hlp - error */
        return XK_FAILURE;
    }

    /* this will be a new enabling, so create and initialize Enable object, */
    /* and enter the binding of port/enable object in the passive map */
    e = X_NEW(Enable);
    e->hlp     = hlp;
    e->hlpType = hlpType;
    e->rcnt    = 1;
    e->binding = mapBind(pstate->passivemap, &key, e);
    if (e->binding == ERR_BIND) {
        xFree((char *)e);
        return XK_FAILURE;
    }
    return XK_SUCCESS;
}
\end{verbatim}

Finally, the actual work of initializing an ASP session is performed
in the subroutine {\var aspCreateSessn} given below. This subroutine
calls an $x$-kernel operation---{\var xCreateSessn}---to allocate a
new session object and connect it to other protocol and session
objects in the appropriate way; e.g., the new session points to the
high level protocol that created it ({\var hlp}) and the low-level
session that it will use to send and receive messages ({\var lls}).
In addition, the new session object will need to know where to find
the routines that implement the various operations it supports, such
as {\var xPush} and {\var xPop}. {\var getproc\_sessn} (presented
below) is the routine that fills in the ASP-specific function pointers
for these operations; it is called by {\var xCreateSessn}.

Note that {\var aspCreateSessn} is not only called from {\var
aspOpen}, but also from {\var aspDemux} (given below) when it needs to
create a new session as a result of an earlier passive open. Also
notice that in the case of {\var aspCreateSessn}, the only
protocol-specific initialization required is to set up a header
template {\var asph} that can later be prepended to the front of
outgoing messages.

\begin{verbatim}
static Sessn
aspCreateSessn(Protl self, Protl hlp, Protl hlpType, ActiveId *key)
{
    Sessn      s;
    ProtlState *pstate = (ProtlState *)self->state;
    SessnState *sstate;
    ASPhdr     *asph;

    /* create the session object and initialize it */
    s = xCreateSessn(getproc_sessn, hlp, hlpType, self, 1, &key->lls);
    s->binding = mapBind(pstate->activemap, key, s);
    sstate = X_NEW(SessnState);
    s->state = (char *)sstate;

    /* create an ASP header */
    asph = &(sstate->hdr);
    asph->sport = key->localport;
    asph->dport = key->remoteport;
    asph->ulen  = 0;

    return s;
}

static void
getproc_sessn(Sessn s)
{
    /* fill in the function pointers to implement session operations */
    s->push            = aspPush;
    s->pop             = aspPop;
    s->controlsessn    = aspControlSessn;
    s->getparticipants = aspGetParticipants;
    s->close           = aspClose;
}
\end{verbatim}

\subsection{Demultiplexing Incoming Messages}\label{demuxing}

Function {\var aspDemux} is called indirectly through {\var xDemux} by
an IP session to pass an incoming message up to ASP. (More generally,
it could be called by any low level protocol configured below ASP, but
this will usually be IP.) This function extracts the header
information from the message, and then demultiplexes the message to
the appropriate session as follows.  First, {\var aspDemux} consults
the protocol's active map to see if an existing session exists for the
ASP channel to which the message belongs.  If such a session exists,
the message is passed to that session via the {\var xPop} operation.
If it does not exist, {\var aspDemux} then checks the passive map to
see if the message is addressed to a port on which a high level
session has performed an {\it xOpenEnable}.  If the port is found in
the passive map, a new session is created---by invoking {\var
aspCreateSessn}---and the message is dispatched to that session.  If
an appropriate entry is not found in either the active or passive
maps, the message is discarded.

\begin{verbatim}
static XkReturn
aspDemux(Protl self, Sessn lls, Msg *dg)
{
    char       *buf;
    ASPhdr     h;
    ActiveId   activeid;
    ProtlState *pstate = (ProtlState *)self->state;
    Sessn      s;
    PassiveId  passiveid;
    Enable     *e;

    /* extract the header from the message */
    buf = msgPop(dg, HLEN);
    if (buf == NULL)
        return XK_FAILURE;
    aspHdrLoad(&h, buf, HLEN);

    /* construct a demux key from the header */
    bzero((char *)&activeid, sizeof(activeid));
    activeid.lls        = lls;
    activeid.localport  = h.dport;
    activeid.remoteport = h.sport;

    /* see if demux key is in the active map */
    if (mapResolve(pstate->activemap, &activeid, (void **)&s) == XK_FAILURE) {
        /* didn't find an active session, so check passive map */
        passiveid = h.dport;
        if (mapResolve(pstate->passivemap, &passiveid, (void **)&e) ==
                XK_FAILURE) {
            /* drop the message */
            return XK_SUCCESS;
        }

        /* port was enabled, so create a new session and inform hlp */
        s = aspCreateSessn(self, e->hlp, e->hlpType, &activeid);
        if (s == ERR_SESSN)
            return XK_SUCCESS;
        xDuplicate(lls);
        xOpenDone(e->hlp, self, s);
    }

    /* found (or created) an appropriate session, so pop to it */
    return xPop(s, lls, dg, &h);
}
\end{verbatim}

The call to {\var xDuplicate} near the end of {\var aspDemux} is
necessary to increment the reference count on the newly created
session. More on reference counts in Section~\ref{refcnt_sessns}.

Subroutine {\var aspHdrLoad} is responsible for converting the fields
in the ASP header from network byte order into the local host's byte
order. It uses the library routine {\var ntohs}, which stand for
network-to-host-short. A counterpart routine---{\var
aspHdrStore}---performs the opposite conversion; it translates host
byte order to network byte order. This latter routine is used when
preparing a message for transmission, as discussed in the next
subsection. Notice that both routines simultaneously swap bytes and
copy the header between the message and the template.

\begin{verbatim}
static long
aspHdrLoad(ASPhdr *hdr, char *src, long len)
{
    /* copy from src to hdr, then convert network byte order to hsot order */
    bcopy(src, (char *)hdr, HLEN);
    hdr->ulen  = ntohs(hdr->ulen);
    hdr->sport = ntohs(hdr->sport);
    hdr->dport = ntohs(hdr->dport);
    return HLEN;
}

static void
aspHdrStore(ASPhdr *hdr, char *dst, long len)
{
    /* convert host byte order to network order, then copy from hdr to dst */
    /* (note: argument 'hdr' is changed by the following code) */
    hdr->ulen  = htons(hdr->ulen);
    hdr->sport = htons(hdr->sport);
    hdr->dport = htons(hdr->dport);
    bcopy((char *)hdr, dst, HLEN);
}
\end{verbatim}

\subsection{Sending and Receiving Messages}

We now turn our attention to the ASP-specific implementation of {\var
xPush} and {\var xPop}---{\var aspPush} and {\var aspPop}---the two
routines that embody the semantics of ASP. Because of its simple
nature, {\var aspPush} simply prepends a copy of the header stored in
the session state onto the outgoing message, and passes the resulting
message to the IP session beneath it.  The header template found in
the session state already contains the appropriate local and remote
ASP ports, since these will not change in the lifetime of a session.
However, the message length must be calculated and inserted into the
appropriate header field. Subroutine {\var aspHdrStore}, as defined in
the previous subsection, converts this header template from host byte
order to network byte order.

\begin{verbatim}
static XkHandle 
aspPush(Sessn self, Msg *msg)
{
    SessnState *sstate = (SessnState *)self->state;
    ASPhdr     hdr;
    char       *buf;

    /* create a header by inserting length into header template */
    hdr = sstate->hdr;
    hdr.ulen = msgLength(msg) + HLEN;

    /* attach header to message and pass it on down the stack */
    buf = msgPush(msg, HLEN);
    aspHdrStore(&hdr, buf, HLEN);
    return xPush(xGetSessnDown(self, 0), msg);
}
\end{verbatim}

Again because of its simplicity, the only work that {\var aspPop}
performs is to check the length field in the message header, and
truncate the message, if necessary. Notice that the last thing {\var
aspPop} does is invoke {\var xDemux} on the high-level protocol that
had earlier opened the session.

\begin{verbatim}
static XkReturn
aspPop(Sessn self, Sessn lls, Msg *msg, void *hdr)
{
    ASPhdr *h = (ASPhdr *)hdr;

    /* truncate message to length shown in header */
    if (h->ulen - HLEN < msgLength(msg))
        msgTruncate(msg, (int)h->ulen);

    /* pass the message to the next protocol up the stack */
    return xDemux(xGetUp(self), self, msg);
}
\end{verbatim}

\subsection{Control Operations}\label{control}

High-level protocols and sessions may request information from or
change the state of ASP protocol and session objects by calling the
following two control functions.  If the opcode used in the call is
not recognized by the ASP control function, one of IP's control
functions is called with the same opcode.  In these routines {\var
checkLen} is a simple macro that makes sure the the buffer {\var len}
is large enough to hold the value being returned.

\begin{verbatim}
static int
aspControlProtl(Protl self, int opcode, char *buf, int len)
{
    switch (opcode) {
        case GETMAXPACKET:
        case GETOPTPACKET:
            checkLen(len, sizeof(int));
            if (xControlProtl(xGetProtlDown(self, 0), opcode, buf, len) <
                    sizeof(int))
                return -1;
            *(int *)buf -= HLEN;
            return sizeof(int);
        default:
            return xControlProtl(xGetProtlDown(self, 0), opcode, buf, len);
    }
}

static int
aspControlSessn(Sessn self, int opcode, char *buf, int len)
{
    SessnState *sstate = (SessnState *)self->state;
    ASPhdr     *hdr;

    hdr = &(sstate->hdr);
    switch (opcode) {
        case GETMYPROTO:
            checkLen(len, sizeof(long));
            *(long *)buf = sstate->hdr.sport;
            return sizeof(long);
        case GETPEERPROTO:
            checkLen(len, sizeof(long));
            *(long *)buf = sstate->hdr.dport;
            return sizeof(long);
        case GETMAXPACKET:
        case GETOPTPACKET:
            checkLen(len, sizeof(int));
            if (xControlSessn(xGetSessnDown(self, 0), opcode, buf, len) <
                    sizeof(int))
                return -1;
            *(int *)buf -= HLEN;
            return sizeof(int);
        default:
            return xControlSessn(xGetSessnDown(self, 0), opcode, buf, len);
    }
}
\end{verbatim}

In addition to invoking these control operations on low-level protocols
and sessions, high-level entities can query ASP for participants associated
with the session. This is done by invoking {\var xGetParticipants} on
the session. The ASP-specific implementation of this operation turns around
and asks the session below it (i.e., an IP session) for the same information.

\begin{verbatim}
static Part *
aspGetParticipants(Sessn self)
{
    Part       *p;
    int        numParts;
    SessnState *sstate = (SessnState *)self->state;
    long       localPort, remotePort;

    p = xGetParticipants(xGetSessnDown(self, 0));
    if (!p)
        return NULL;
    numParts = partLength(p);
    if (numParts > 0 && numParts <= 2) {
        if (numParts == 2) {
            localPort = (long)sstate->hdr.sport;
            partPush(p[1], (void *)&localPort, sizeof(long));
        }
        remotePort = (long)sstate->hdr.dport;
        partPush(p[0], (void *)&remotePort, sizeof(long));
        return p;
    }
    else    /* Bad number of participants */
        return NULL;
}
\end{verbatim}

\subsection{Close}

Finally, {\var aspClose} is called indirectly through {\var xClose}
when a high-level protocol wants to close a session it had opened
earlier.  This routine removes the entry in the active map
corresponding to this session, closes the lower level session, and
destroys the session object. As you can see, the session object
includes a field in which the binding in the active map for this
session was recorded ({\var binding}). Also, the routine {\var
xMyProtl} returns the protocol object that corresponds to this
session (e.g., the protocol object that represents ASP).

\begin{verbatim}
static XkReturn
aspClose(Sessn s)
{
    ProtlState *pstate = (ProtlState *)xMyProtl(s)->state;

    /* remove this session from the active map */
    mapRemoveBinding(pstate->activemap, s->binding);

    /* close the lower level session on which it depends */
    xClose(xGetSessnDown(s, 0));

    /* de-allocate the session object itself */
    xDestroySessn(s);

    return XK_SUCCESS;
}
\end{verbatim}