% $Id: Resolution.tex,v 1.47 2005/10/18 16:27:53 arvindk Exp $

\sqztiny
\section {Resolving Middleware Generality via Context-specific Specia\-l\-i\-zations}
\label{mw-spl-solution}

This section examines techniques that focus on the use of
context-specific specializations to enhance the QoS of PLA-based DRE
systems by alleviating excessive generality in middleware
implementations.  Context-specific specialization techniques are
related to {\em partial evaluation}, which creates a specialized
version of a general program that is more optimized for time and/or
space than the original~\cite{Jones:1993:PartialEvaluation}.
Context-specific specializations can be realized using {\em
code-refactoring and weaving}~\cite{zhang03refactoring,Fowler:99},
which uses aspect-oriented programming mechanisms to factor out and
weave crosscutting concerns, as well as {\em language mechanisms},
such as program optimization
techniques~\cite{Itkin:1983:OnPartial:Russian}.  Below we describe how
we applied context-specific specializations to TAO to resolve the
challenges described in Section~\ref{challenges}.  The specialization
techniques and tools are reusable and applicable to various middleware
implementations beyond TAO.

% \sqztiny
\subsection{Applying Context-Specific Specializations to Middleware}
\label{spl:invariance}

Context-specific specializations described in this paper include
constant propagation, layer-folding, memoization, code-refactoring,
and aspect weaving.  These specialization are driven by
\emph{invariant properties}~\cite{marlet99efficient}, which
are specific application-, middleware-, and platform-level
characteristics that remain fixed during system execution, but which
may vary for different system configurations/\-requirements.  The
invariants themselves may be specific for a particular PLA or
applicable to many PLAs.  Invariant properties covered in this paper
include particular attribute settings (such as timer rates), parameter
values (such as arguments to a method), and inter\-na\-l/exte\-rn\-al
contexts
% Arvind, I'm not sure if this example really applies to what we cover
% in this paper.  Can you please double check this?
%%%
% Arvind: I have changed this to be more relevant to the different
% challenges we discuss.
%%%
(such as a dispatcher for a request and hardware, OS and compiler
settings).

In simple cases, an invariant property manifests itself in the form of
a call to method {\tt m()}, where one or more of the parameters of the
method is always bound to the same value.  Our program specialization
strategies push invariant data through the middleware code,
simplifying along the way.  For example, we create a specialized
version of {\tt m()} where the parameters with fixed values are
removed and the body of {\tt m()} is simplified according to the
information provided by the fixed parameter values.  Below, we
describe the {\em intent} (purpose), {\em invariance assumptions}
(conditions in our {\em BasicSP} case study that enabled certain
specializations), and {\em type} (technique) of specialization we
applied to resolve the middleware generality challenges described in
Section~\ref{challenges}.

To evaluate our middleware specializations in a realistic context, we
applied them to the TAO implementation of Real-time CORBA, which is
written in C++ and contains many general-purpose ORB
optimizations~\cite{Schmidt:99h,Schmidt:02r}.  We use general-purpose
optimized TAO as a baseline to quantify the benefits of
specializations that help resolve the challenges for PLAs described in
Section~\ref{mw-spl-challenges}.  We focus on TAO since it is a
mature, efficient, and open-source implementation of the Real-time
CORBA standard that is used widely in production DRE systems
(\url{www.dre.vanderbilt.edu/users.html}).

% \sqztiny
\subsubsection {Specialize Middleware Framework Extensibility via Aspect Weaving}
\label{sec:resolve_1}

We first describe specialization techniques for resolving challenge 1
in Section~\ref{mw-spl-challenges}.

\sqzlarge
\paragraph* {\bf Intent} Eliminate unnecessary extensibility
mechanisms (such as indirections and dynamic dispatching) in
object-oriented frameworks along the critical request/\-response
processing path.  This specialization can be applied to many internal
ORB frameworks that handle transport protocols, request
demultiplexing, and concurrency models.  For our case study, we choose
% Arvind, didn't you also end up specializing the locking aspects, as
% well?  If so, can you please mention this here, as well, and show
% the results?
%%%
% Arvind: Prof Schmidt, It said I would look into the locking framework
% during the MODELS presentation. I haven't done it.
%
% Arvind, ok, please mention this in the ``future work'' discussions
% and/or cover it in the WIP paper for RTSS!
to specialize TAO's (1) Reactor framework~\cite{Schmidt:02a}, which is
responsible for demultiplexing connection and data events to their
corresponding GIOP event handlers, and (2) pluggable protocol
framework~\cite{Schmidt:99x} which allows ORBs to communicate
transparently via different protocol implementations, such as TCP/IP,
VME, SSL, SCTP, UNIX-domain sockets, and/\-or shared memory.

\sqzlarge
\paragraph* {\bf Invariance assumptions} After a Reactor framework
implementation is selected for the {\em BasicSP} scenario, it does not
change during the lifetime of the ORB.  Likewise, after a protocol
implementation is selected it also does not change during the lifetime
of the ORB.

\sqzlarge
\paragraph* {\bf Specialization} Figure~\ref{fig:reactor-spl}(A) shows
different Reactor implementations supported by TAO.
\begin{figure}[ht]
  \centerline{\includegraphics[width=8cm,height=3cm]{figures/ReactornProtocolSpl}}
  \bfcaption{Reactor \& Protocol Specialization} \label{fig:reactor-spl}
\end{figure}
The \url{Select_Reactor} uses the single-threaded {\tt select()}-based
event demuxer, the \url{Thread_Pool_Reactor} uses the multi-threaded
{\tt select ()}-based event demuxer, and the \url{WFMO_Reactor} uses
the Windows {\tt Wait\-For\-Mul\-ti\-ple\-Ob\-jects()} event demuxer.
To work transparently across all Reactor framework implementations,
TAO uses an abstract base class ({\em i.e.}, a generic
\url{Reactor_Impl}) that delegates to concrete subclasses via virtual
method calls.  Specializing the Reactor framework with a concrete
subclass ({\em i.e.}, a subclass with no virtual methods) eliminates
the indirection (generality) by using the concrete reactor instance
directly.

TAO's pluggable protocol framework uses the Template Method
pattern~\cite{Vlissides:94} to configure different protocol
implementations during the ORB initialization phase.  As shown in
Figure~\ref{fig:reactor-spl}(B), this framework consists of
protocol-independent components, such as the \url{Transport} class
that provides \url{send()} and \url{recv()} hooks to encapsulate a
connection and provide a protocol-independent means of
sending/receiving data.  Protocol-specific classes, such as the
\url{IIOP_Transport} class, override these hooks to implement
prot\-ocol-spe\-cific functionality.  The \url{Transport} class interacts
with other framework components, such as the \url{Profile} class that
encapsulates addressing information in TAO, which in turn uses the
Template Method pattern to support multiple protocol implementations.
Specializing the hook methods in a template method with
protocol-specific behavior eliminates the indirection ({\em i.e.}, the
{\em virtual} hook methods).

The specializations described above are an example of {\em aspect
weaving}, where the generality ({\em i.e.}, virtual methods and
indirections) that crosscuts different classes and files is customized
for a specific context.  For example, our {\em BasicSP} PLA scenario
only uses the \url{Select_Reactor} and VME protocol, so there is no
need to incur additional indirection and generality overhead.

% \sqztiny
\subsubsection {Specialize Request Creation/Initialization via Memoization}
\label{sec:resolve_2}
We now describe specialization techniques for resolving challenge 2
described in Section~\ref{mw-spl-challenges}.

\sqzlarge
\paragraph* {\bf Intent} Rather than creating a new CORBA request
repeatedly for each invocation, create/\-initialize a request once and
only update its state that changes.

\sqzlarge
\paragraph* {\bf Invariance assumption} Many (often most) operation
parameters and/or context information in a request do not change
across invocations in DRE systems.

\sqzlarge
\paragraph* {\bf Specialization}
Figure~\ref{fig:request-spl} shows the structure of a two-way CORBA
request using GIOP version 1.2.
\begin{figure}[ht]
\centerline {
  \includegraphics[width=8cm]{figures/CORBA-Request-Spl}}
\bfcaption {Opportunities for Request Creation Specialization}
\label{fig:request-spl}
\end{figure}
As shown in the figure, every request has three components defined by
the CORBA specification: (1) a request header that indicates the type
of CORBA request ({\em i.e.}, GIOP version 1.0, 1.1, or 1.2) and the
total size of the message, (2) a request-specific header containing
the object key that uniquely identifies the servant and service
context information containing service-specific information, such as
the required priority and transaction/\-security contexts, and (3)
optional parameters that were passed as arguments to the operation.

Figure~\ref{fig:request-spl} also shows three types of specializations
of {\em increasing strength} that can be applied.  In some situations
only the request header can be specialized, {\em i.e.}, its contents
are held constant, updating only the total size of the message.  In
other situations, both the request and the request-specific headers
can be held constant, updating only the payload.  Finally, the entire
CORBA request can sometimes be reused wholesale across multiple
request invocations.

This specialization is an example of {\em memoization}, where a result
is precomputed and saved rather than recomputed each time.  In our
{\em BasicSP} PLA case study, the precomputed ``result'' is the CORBA
request.  This specialization thus avoids unnecessary creation and/or
initialization of requests.

% \sqztiny
\subsubsection {Specialize Dispatch Resolution via Layer-Fold\-ing}
\label{sec:resolve_3}

We now describe specialization techniques for resolving challenge 3
described in Section~\ref{mw-spl-challenges}.

\sqzlarge
\paragraph* {\bf Intent} Resolve the target request dispatcher once
for the first request and reuse it to service all other requests sent
over the same dedicated connection.

\sqzlarge
\paragraph* {\bf Invariance assumptions} The same operation or
operations in the same IDL interface are invoked on a multiplexed
connection.

\sqzlarge
\paragraph* {\bf Specialization} Figure~\ref{fig:dispatch-spl} shows
a normal layered demultiplexing path through a CORBA server, {\em
i.e.}, the ORB core locates the target POA, which locates the servant,
which locates the skeleton, which dispatches the request to an
application-defined method.
\begin{figure}[ht]
  \centerline{\includegraphics[width=6cm]{figures/Dispatch-Spl}}
  \bfcaption{Specializing Request Dispatching} \label{fig:dispatch-spl}
\end{figure}
Rather than navigating this layered path, a specialized implementation
can cache the skeleton servicing the request and invoke the method on
the skeleton directly.  A similar approach can be applied to cache the
target POA(s) and servant.

This specialization
is an example of {\em layer-folding} plus memo-ization,
where an answer (in our case the dispatcher)
is saved for later use than recomputing it each time.  This enables
multiple middleware layers to be collapsed during request processing.

% \sqztiny
\subsubsection {Specialize Request Demarshaling via Constant Propagation}
\label{sec:resolve_4}

We now describe specialization techniques for resolving challenge 4
described in Section~\ref{mw-spl-challenges}.

\sqzlarge
\paragraph* {\bf Intent} Eliminate redundant tests for byte order
when demarshaling a CORBA request and do not align the individual
fields within the request.

\sqzlarge
\paragraph* {\bf Invariance assumptions} The communicating entities
reside on nodes with the same byte order, compiler padding/\-alignment
rules, and the same (de)marshaling mechanisms for client(s) and
server(s).

\sqzlarge
\paragraph* {\bf Specialization} Standard-compliant CORBA ORBs are
required to test for byte order compatibility for every part of a
CORBA request (not just the payload), including all fields in the
CORBA request and request-specific headers.
Figure~\ref{fig:request-spl} shows the different parts of a CORBA
request.  For a typical request with a few basic types (such as {\tt
long}, {\tt short}, and {\tt octet} parameters), these tests translate
to $\sim$15--20 byte order tests per request.  Removing these
redundant tests on homogeneous compiler/middleware platforms can
significantly improve demarshaling efficiency, particularly as the
data type complexity increases.  Similarly, while marshaling a CORBA
request, ORB implementations align the individual components, {\em
e.g.}, request size, id and objectkeys, to their natural boundaries.
For a typical request with basic types, all the $\sim$15--20
components must be aligned.  Ignoring alignment can improve marshaling
efficiency and eliminate padding, thereby reducing request size.

These specializations are an example of {\em constant propagation},
where the byte-order is propagated along with the request to the
recipient and checked to ensure the validity of the invariance
assumption.  Similarly, unaligned data is sent along with the request
to the recipient, where demarshaling fails if data should be aligned.

\subsubsection{Specialize Platform Generality via Autoconf Me\-cha\-nisms}
\label{sec:resolve_5}
We now describe specialization techniques for resolving challenge 5
described in Section~\ref{mw-spl-challenges}.

\sqzlarge
\paragraph*{\bf Intent} Choose the right hardware, OS, and compiler
settings to maximize application QoS without affecting portability,
interoperability, or correctness.

\sqzlarge
\paragraph*{\bf Invariance assumptions}
The deployment platform that hosts the product variant remains fixed
during the system's lifetime.

\sqzlarge
\paragraph*{\bf Specialization} %We extended TAO to use the GNU
%%%
% We want to keep this at a high level and not talk about TAO
% here.
%%%
We use GNU {\tt autoconf} ({\tt www.gnu.org/sof\-tw\-are/autoconf})
toolkit to apply platf\-orm-specific specialization techniques,
including:

\sqztiny
\begin{itemize}\crunchlist
\item {\bf Exception support.} For certain DRE systems, the use of
native exception support is unavailable ({\em e.g.}, not supported by
older C++ compilers) or undesirable ({\em e.g.}, incurs excessive
time/\-space overhead).  Certain middleware solutions support
platforms that
lack exceptions, {\em e.g.}, CORBA can emulate exceptions by adding an
\url{Environment} parameter at the end of each operation signature.
We extended TAO to use GNU {\tt autoconf} to automatically emulate
exceptions when compilers lack such capabilities, when users
explicitly select this configuration, or when performance tests
indicate that emulated exceptions are more efficient than native
exceptions.

\item {\bf Loop unrolling.} Middleware implementations
need to copy data between kernel and middleware and application
buffers.  An optimization applicable to certain OS/\-compiler
platforms is to unroll the loop of \url{memcpy()} standard library
function up to a certain buffer size.  We extended TAO to use GNU {\tt
autoconf} to configure middleware automatically to use the either the
optimized or default version of \url{memcpy()}, depending on
performance tests that deem one more efficient than the other.
\end{itemize}

For both specializations, we use GNU {\tt autoconf} to perform these
performance tests automatically just before the ORB compilation
process begins.  Based on the test results, GNU {\tt autoconf} sets
certain macros in the TAO source code, which are then used to select
which specializations to apply.

% \sqztiny
\subsection {A Toolkit for Automating Context-Specific Specializations}
\label{res:automation}

Large-scale DRE systems, such as Boeing's Bold Stroke PLA, contain
millions of lines of source code.  Implementing specialization
techniques by manually handcrafting the optimizations described in
Section~\ref{spl:invariance} into such large code bases will clearly
not scale.  To augment GNU {\tt autoconf}, therefore, we have created
a domain-specific language (DSL) and associated tools that help
simplify two steps in the specialization process: (1) identifying
specialization points and transformations and (2) automating the
delivery of the specializations.

\iffalse
% Arvind, we don't really do this stuff, right?  Let's omit it in the
% interest of space and veracity!
In the specialization identification step, higher level models capture
the system architecture.  Automated model checkers and analysis
engines use these models to identify opportunities for the application
of specializations.  The captured information is used in the second
step to automate the delivery of the specializations.
\fi
The remainder of this section describes the {\em Feature Oriented
Customizer} (FOCUS), which is an open-source DSL-based toolsuite and
process we developed to automate the specialization of middleware for
PLA-based DRE systems.  FOCUS is available at
\url{www.dre.vanderbilt.edu/~arvindk/FOCUS}.

% \sqztiny
\subsubsection {FOCUS Requirements and Goals}
Our primary goal for FOCUS was to build a general-purpose DSL,
supporting tools, and a process to automate context-specific
middleware specializations and then to validate our approach by
applying it to TAO.  The types of specializations discussed in
Section~\ref{spl:invariance} yielded the following requirements for
FOCUS:

\sqzlarge\paragraph*{\bf 1. Ability to manipulate code} Applying
aspect weaving to framework specialization requires the ability to
manipulate code, such as performing search and replace specializations
to devirtualize hook methods in the \url{Reactor_Impl} base class and
replace them with the name of concrete reactor implementation.

\sqzlarge\paragraph*{\bf 2. Ability to refactor code regions}
Object-oriented framework specializations need to move specialized
code ({\em e.g.}, concrete implementations of hook methods) from a
derived class to the new concrete class.  Similarly, additional header
files and methods may may need to be moved from/\-to a derived class
to/\-from a new concrete class.  Likewise, layer-folding optimizations
require the capability to inject code that bypasses layers at specific
locations in the code.

\sqzlarge\paragraph*{\bf 3. Ability to remove code} Code
refactoring, memoization, and aspect weaving specializations require
the removal of certain redundant functionality.  In memoization
optimizations, for instance, redundant functionality that repeatedly
creates the same request must be replaced with code that caches the
request header.

To support these requirements, FOCUS uses generative
programming techniques~\cite{Generative:Programming:00} that combine
annotations (directives) with code templates~\cite{Rodger:02} to
specialize middleware implementations. %to
%generate concrete executable programs in different languages.
FOCUS
annotations are embedded within the middleware source to identify
points of variability, {\em e.g.}, where a dispatching decision is
made or a particular protocol is created.  This approach enables most
of the basic infrastructure of the middleware to remain fixed, but
identifies well-defined variability points where specializations can
be woven automatically.  It also enables middleware developers to
explicitly know the variability points when source code changes are
made, thereby minimizing the skew between specializations and an
evolving middleware source base.

\iffalse
% Arvind, these sentences don't really belong here - perhaps you could
% move them to the future work discussion at the end of the paper?
%%%
% Arvind: As we are short on space, it is better to comment them out.
%%%
Ultimately, we envision specialized middleware implementations to be
synthesized from higher level PLA system models and functional
specifications.  FOCUS approach represents a step in this direction.
\fi

% \sqztiny
\subsubsection {Automating Middleware Specializations with FOCUS}
\label{focus-design}

The process of applying FOCUS DSL and tools can be executed in three
phases by middleware developers and application PLA developers, as
discussed below.

\sqzlarge
\paragraph*{\bf Phase 1: Capturing specialization transformations}
In this phase, middleware developers capture the code-level
transformations required to implement a specialization using the {\em
FOCUS Specialization Language} (FSL), which is a DSL that supports the
following types of specializations: (1) search and replace
transformations ($<$search$>$ ... $<$replace$>$), (2) copying text
from different positions in multiple files onto a destination file
($<$copy-from-source$>$), (3) commenting regions of a program
($<$comment$>$), and (4) removing text from a program ($<$remove$>$).
FSL uses an XML DTD to capture the transformations, which facilitates
ease of (1) {\em extension}, {\em i.e.}, additional transformations
can be represented via new XML tags and (2) {\em transformation}, {\em
i.e.}, XSLT transformations can be used to transform the
specializations onto different tool input formats.  Similar approaches
have been used in commercial tools, such as Ant
(\url{ant.apache.org}), which use XML to capture build steps and
rules.

The output of phase 1 is a set of FSL specialization files that
capture all the transformations needed for the specializations.
Section~\ref{res:resolve_1} illustrates portions of the
transformations required to automate aspect weaving specializations in
TAO.

\sqzlarge
\paragraph* {\bf Phase 2: Middleware annotation}
In this phase, middleware developers use the FSL specialization files
to annotate the middleware with metadata required for the desired
transformations.  Annotations in FOCUS are only required for
transformations that copy, comment, or add code, {\em i.e.}, when
using the $<$comment$>$, $<$copy-from-source$>$, or $<$add$>$ tags,
respectively.  Other transformations, such as search and replace, and
remove do not require annotation.  Metadata is inserted as special
comments in the source code using source language syntax for comments.
This metadata is used by FOCUS to aid in the transformation of source
code, but is opaque to compilers for general-purpose languages like
C++ or Java and imposes no extra overhead on general-purpose
middleware source code.

During middleware evolution, such as feature
addition/\-mod\-ific\-ation, middleware developers must respect the
annotations.  For example, any new code between annotations that mark
the begin and end of a copy/comment does not require changes to the
specialization files.  Section~\ref{res:resolve_1} illustrates how
annotations along with $<$copy-from-source$>$ tags can be used to
minimize skew between specializations and middleware source code.

Annotations help the FOCUS transformation process by enabling a
lightweight specialization approach that does not require a
full-fledged language front-end to parse the entire source code to
identify the specialization points (hooks).  This approach enables
FOCUS to work across middleware implementations in different
languages, {\em e.g.}, hooks can be left within a C++- or Java-based
middleware implementation for FOCUS to weave in code.  FOCUS ascribes
no significance to the names for hooks, {\em i.e.}, they can be
arbitrary as long as there is a corresponding name in the
specialization file.

\sqzlarge
\paragraph* {\bf Phase 3: Executing specialization transformations}
In this phase, PLA developers perform the steps shown in
Figure~\ref{focus-transform}.
\begin{figure}[!htbp]
\center{
\includegraphics[width=8cm]{./figures/FOCUS-Transformation.eps}}
\caption{Steps in the FOCUS Transformation Process}
\label{focus-transform}
\end{figure}
First, they select the specializations suitable for the variant (step
1) during the offline SCV analysis phase.  Based on the features
selected for specialization, the FOCUS transformation engine queries
the specialization repository to select the right file(s) (step 2).
Based on the transformation rules in the specialization file, the
transformation engine executes the transformations (step 3).  A
compiler for the general-purpose language used to write the middleware
is then used to generate executable platform code from the modified
source file(s) (step 4).

The FOCUS transformation engine is written in Perl to leverage its
mature regular expressions support.  Regular expressions enhance the
richness of the transformations that can be specified within FSL
specialization files.  For example, search and replace capabilities in
FOCUS leverage regular expressions to ignore leading trailing white
spaces and newline characters.

% \sqztiny
\subsection {Summary}
This section described the specialization techniques, language, and
tools we developed to resolve middleware generality challenges in
Section~\ref{challenges}.  Table~\ref{spl-summary} lists the
specialization techniques along with the corresponding FSL features we
applied to resolve the generality challenges
(Section~\ref{apply-spl-to-tao} describes why we did not use FOCUS to
resolve (de)marshaling checks and deployment generality).
{
\begin{table}[htpb]
\begin{center}
\scriptsize
\begin{tabular}{|l|l|l|}\hline
% Arvind, can you please make sure that all the cells in this table
% are filled in correctly?!
%%%
% Arvind: I think they look ok, but is there something you
% are seeing which is not right?
%%%
{\bf Specialization } & {\bf Technique} & {\bf FSL features}
\tabularnewline \hline
 Request creation & Memo\-ization & search, replace, add\tabularnewline \hline
 Demarshaling checks & Constant propagation & Not Applicable \tabularnewline \hline
 Dispatch resolution & Memo\-ization + layer-folding & search, replace, add\tabularnewline \hline
 Framework generality & Aspect weaving & add, copy-from-source \tabularnewline
                      &                & search, replace \tabularnewline \hline
 Deployment generality & autoconf      & Not Applicable \tabularnewline \hline
\end{tabular}
\caption {Summary of Specialization Techniques}
\label{spl-summary}
\end{center}
\vspace{-0.5cm}
\end{table}
}
%
Similar to the challenges, the FOCUS specialization techniques we
describe are reusable and applicable to middleware that incur
generality challenges.  These techniques modify only copies of the
object-oriented framework and middleware code and do not necessitate
any modifications to application code or original frameworks and
middleware.

\iffalse
FSL
tag names minimize the accidental complexity involved in specifying
maintaining and adding specializations.  In our future work, we plan
to extend FSL to capture specialization dependencies and validate our
approach using other representative C++ and Java middleware
implementations.
\fi
