%
% x-kernel v3.3
%
% Copyright (c) 1996,1993,1991,1990  Arizona Board of Regents
%

\section{Reference Counting Sessions}\label{refcnt_sessns}

The {\xk} maintains reference counts for sessions in order to
facilitate their destruction. This section discusses the system
support for reference counts.  We discuss reference counts in the
context of sessions (rather than protocols) because protocols are
relatively static objects and the issues surrounding their reference
counts are not very interesting.

Constructing a protocol that directly manipulates reference counts and
does so correctly can be awkward and tedious.  The {\xk} has addressed
this difficulty by: (1) moving all direct reference count manipulation
into the {\xk} infrastructure; (2) explicitly documenting how
references to other sessions may be used; and (3) adding system
support for session caching and garbage collection.

\subsection{References}\label{refs}

A {\var Sessn} reference is a pointer to a {\var Sessn}.  References
come in two flavors: {\it permanent} and {\it temporary}.  A permanent
reference can be used indefinitely.  As long as the holder of a
permanent reference does not call {\var xClose} on the reference, the
holder knows that the pointer will remain valid.  Permanent references
are returned by {\var xOpen}.  A {\var Sessn} pointer received as a
parameter in a function call is a temporary reference.  It can only be
safely used for the duration of that function call.

A permanent reference may be created from a temporary reference by
using the following operation on {\var session}: 

\begin{quote}
{\var XkReturn xDuplicate(Sessn session)}
\end{quote}

\noindent 
For example, {\var xDemux} passes a reference to the lower session as
a parameter to the upper protocol.  If the upper protocol wishes to
save this reference beyond the extent of the call, the protocol should
call {\var xDuplicate} on the session.  The protocol can then safely
use the reference until it calls {\var xClose}.

\subsection{Reference counts}\label{refcnts}

Session reference counts are a sum of:
\begin{itemize}
\item{}
the number of permanent external references to the session
\item{}
the number of outstanding {\var xPop}'s on the session
\end{itemize}

\subsubsection{Counting External References}\label{ext_refs}

Several of the UPI functions are involved in maintaining the count of
permanent external references.  They are listed here along with their
semantics with respect to reference counts.

\begin{quote}
\begin{var}
\noindent
xCreateSessn(...)
\end{var}

\begin{quote}
\noindent
The newly created session has an initial reference count of 0.
\end{quote}
\end{quote}

\begin{quote}
\begin{var}
\noindent
xOpen(...)
\end{var}

\begin{quote}
\noindent
The session returned by invoking the lower protocol's open routine has
its reference count incremented before it is returned to the caller of
{\var xOpen}, indicating that the caller now has a permanent reference
to the session.
\end{quote}
\end{quote}

\begin{quote}
\begin{var}
\noindent
xClose(session)
\end{var}

\begin{quote}
\noindent
Decrements the reference count of the session, indicating that a
permanent reference to the session has been released.  The lower
protocol's close operation is called {\it only} if the session's new
reference count is zero.
\end{quote}
\end{quote}

\begin{quote}
\begin{var}
\noindent
xDuplicate(session)
\end{var}

\begin{quote}
\noindent
By default, increments the session's reference count, indicating that
a new permanent reference to the session has been created.  If the
session has its own duplicate function, that is called instead.
\end{quote}
\end{quote}

\subsubsection{Counting {\var xPop}s}\label{cnt_xpops}

To understand the second component of the reference count, the number
of outstanding {\var xPop}s on a session, it is important to realize
that a protocol does not have explicit references to its own sessions.
That is, while a protocol usually maintains pointers to its sessions
(in a map) and invokes operations on them, the sessions' reference
counts do not take these pointers into account.  (This is why {\var
xCreateSessn} returns an object with a reference count of 0 and not
1.)

For a protocol to safely send this session pointer outside of the
protocol (e.g., as a parameter in {\var xDemux}), it needs to turn the
pointer into a reference by incrementing the session's reference
count.  It could do this by calling {\var xDuplicate} on the session
as soon as it is extracted from the session map, making the external
call, and then closing the session.  But since all protocols must do
this for incoming messages, this functionality has been absorbed into
{\var xPop}, that is, {\var xPop} increments the reference count of
the session before calling the pop function and decrements it
(possibly calling the session's close operation) afterwards.

It could be argued that all UPI functions, not just {\var xPop},
should indicate their use of a session by incrementing the reference
count at their start and decrementing it at their completion.  To
perform any other UPI operation on a session, however, you must
already have a reference to that session.  As long as an {\var xClose}
is not performed on that reference, the session is not going to go
away; maintaining reference counts for these operations is not
necessary.  {\var xPop}s are different in that a session's reference
count does not reflect that its protocol may send messages up through
it.

Note that reference counts will not help a protocol which performs an
{\var xClose} on a session reference while another thread has an
outstanding operation on that same reference.  To perform such a
sequence is a protocol error.  If two threads share a session
reference, they should either synchronize to avoid such sequences or
they should duplicate the reference with {\var xDuplicate} and each
thread should {\var xClose} its reference when it is through.

\subsection{Internal vs. External Reference Counts}\label{int_ext_refcnts}

Session reference counts are meant to count the number of {\var
external} references to the session (i.e., references held outside of
the protocol).  If a protocol must keep track of session references
internal to the protocol itself, a separate mechanism must be used.

This requirement is driven by upper protocols that require that when
they release all of their references to a lower session, then the
session's reference count goes to zero.  Virtual protocols that
manipulate lower session's upper protocol pointers are specific
examples of these types of upper protocols.

\subsection{Session Caching Strategies}\label{caching}

In the presence of correct management of reference counts, protocols
may want to implement some sort of session caching.  For example, many
of the sessions created on the receiving end of a remote procedure
call will have their reference counts go to zero after the reply has
been sent, and without caching, all of those sessions will be
destroyed.  While caching may not be important for all protocols, it
is vital to the performance of protocols that experience a high
frequency of traffic from the same sources.

If a protocol does cache idle sessions, it is important to make the
caching transparent to upper protocols (i.e., an upper protocol should
not be able to distinguish a newly created lower session from a cached
lower session that is being reused).  One aspect of this requirement
is that protocols that cache sessions must be sure to check for the
presence of openEnables when reusing sessions which would otherwise be
passively created, and to call {\var xOpenDone} when reusing such
sessions from the cache.

Following are some examples of caching strategies and how a protocol
might implement them.  These are just examples; other strategies are
certainly possible.

\begin{itemize}

\item{}
Destroy the session if inactive.

In this ``null caching'' strategy, the session's close routine destroys the
session.

\begin{verbatim}
    fooClose(s)
        xAssert(s->rcnt == 0);
        xDestroy(s);
\end{verbatim}

\item{}
Garbage collection on a per-session basis.

A garbage collector event is started for each idle session.  When the
event expires, the session is collected.

\begin{verbatim}
    fooDemux()
        if (active session does not exist) {
            if (openEnable exists) {
                if (cached session exists) {
                    evCancel(sstate->gc);
                    sstate->gc = 0;
                }
                else
                    s = fooOpen();
                xOpenDone(s, ...);
            }
            else {
                drop packet;
                return;
            }
        }
        xPop()

    fooOpen()
        ...
        if (active session does not exist) {
            if (cached session exists) {
                evCancel(sstate->gc);
                sstate->gc = 0;
            }
        }
        ...

    fooClose(s)
        sstate->gc = evRegister(foo_gc, s);
        mark session as cached

    foo_gc(s)
        xDestroy(s);
\end{verbatim}

\item{}
Garbage collection on a per-protocol basis.

There is a single garbage collector for the protocol.  It runs every
so often and looks for idle sessions in the protocol's session map,
calling a protocol-specific destroy function if it finds one.

The {\xk} has a default session garbage collector that a protocol can
use for this purpose.  See {\var xkernel/include/gc.h} for the
interface.

\begin{verbatim}
    foo_init()
        ...
        initSessionCollector(cacheMap, interval, fooDestroy);

    fooDemux()
        if (active session does not exist) {
            if (openEnable exists) {
               if (cached session exists) {
                   move sessn from cached map to active map
               }
               else
                   s = fooOpen();
               xOpenDone(s, ...);
            }
            else {
               drop packet;
               return;
            }
        }
        xPop()

    fooOpen()
        ...
        if (active session does not exist) {
            if (cached session exists) {
                move sessn from cached map to active map
            }
        }
        ...

    fooClose(s)
        xAssert(s->rcnt == 0);
        move sessn from active map to cached map

    fooDestroy(s)
        xDestroy(s);

\end{verbatim}

\end{itemize}