implementation.tex

xorp源码hg

Internally, the dispatcher has a map from a key to a callback. The key
represents the requested operation and the types of arguments in order. If an
entry is not found, it means the permutation is invalid and an exception is
thrown. On success, the callback is executed and the return value is passed to
caller (double dispatch).

There must be a way to register callbacks with the dispatcher in order to add
entries to the map. This is done via the add functions:
\begin{verbatim}
    template<class T, Element* (*funct)(const T&)>
    void add(const UnOper& op);

    template<class L, class R, 
             Element* (*funct)(const L&,const R&)>
    void add(const BinOper& op);
\end{verbatim}
Currently there is no way to add n-ary callbacks, but it is trivial to do so, if
the function will take an ArgList as a parameters instead of explicitly expanded
parameters. Notice that the template parameters are concrete types of the
elements for the operation being added.

It is important to have only one global map, and to register the callbacks
before the map is used. The map is therefore static, and the callbacks are
registered via a RegisterOperations class.

Arguments of the Element NULL type are treated as a special case. By definition,
any operation which has a NULL argument will return a new NULL element. This
becomes useful, for example, when testing if a IPv4 address equals the next-hop
of an IPv6 route (remember that a NULL element will be returned by VarRW in this
case). Returning true or false will be misleading, thus the choice is returning
another NULL element.


\subsubsection{Register operations with dispatcher}
The dispatcher class has a static member of RegisterOperations initialized right
after the map. This will ensure that the RegisterOperations constructor will be
called right after the map initialization, and only once (static).

The sole purpose of the RegisterOperations is to initialize the dispatcher map.
In fact, it only has a constructor which will perform the adds to the
dispatcher. 

If a new operation needs to be added to the whole policy framework it should be
enough to add it in the RegisterOperations class. If this operation requires a
new symbol to be used in the configuration, then the appropriate modifications
need to be done in the front end and back end lexers and grammars. Also, a new
operation class needs to be created to represent it. To increase flexibility,
operations may be created via a factory in the future which would not require
modification of the backend possibly.

Notice that sometimes it suffices to add different permutations of arguments and
existing operations to the dispatcher. This will in essence change the ``dynamic
grammar'' and what permutations of argument types / operations are allowed
(possibly overloading existing operations).

\subsection{Details on ElementFactory}
With a flexible dispatcher like the one described above, elements may
theoretically be created via it. It should be possible to simply register an
operation CreateElement which takes a string element as argument.

The ElementFactory works almost exactly as the dispatcher, but is different in
nature. For this reason I kept the two separate.  The dispatcher executes based
on the type of arguments. The factory creates based on the value of arguments.
Note that subtle difference, although the argument passed to the factory
actually is a type identifier of the element, the factory treats it a value, not
a type.

Elements may be registered with the factory in a similar way as with the
dispatcher:
\begin{verbatim}
    typedef Element* (*Callback)(const char*);

    void add(const string& key, Callback cb);
\end{verbatim}
{\em Key} represents the type of the element (its string representation). The callback
function will construct the element via a c-style string. If the pointer is NULL,
a default value should be assigned to the newly created element.  Default
initialized elements are extensively used by the front end semantic checker.

As with the dispatcher, the map is static and a RegisterElements class is
provided for initialization.

Adding elements to the factory simply requires registering them and creating a
derived version of the Element class. Currently, the lexer does all type
identification, so that must be modified with a regular expression to match the
new element type. There is no run-time ``type guessing'' mechanism, which I
think should be added. The new element must be added in the grammar too.

A utility template ElemAny is provided which may help in creating new elements.
Currently IPv4/6 and others are implemented using this wrapper.

\section{Operators}
Operators were met in the dispatcher, both in the run and add methods. The
interface for operators is:
\begin{verbatim}
    virtual unsigned arity() const = 0;

    virtual string str() const = 0;
\end{verbatim}
Each operator has an arity associated (the number of arguments it takes). This
is useful for asserting correctness of argument lists. To check if user supplied
right number of arguments. Each operator is string representable.

Again, the justification is that the compiled programs need to be sent in a
string form to the backend. Also, the user will type them in text (hopefully) in
the configuration file. So there must be a string representation. The string
representation must be unique! The dispatcher uses it for the creation of the
key in the map lookup for example.

There are two more utility base classes for operators, namely BinOper and UnOper
which define the arity to 2 and 1 respectively. This way new binary and unary
operators may be derived without the need to worry about arity. It also helps
grouping operations in a hierarchy.

\section{Policy backend internals} Having the ability to create elements and
perform operations on them makes the
design of the backend filter conceptually easy. Backend filters are implemented
as a simple stack machine. They read a pseudo-code assembly like program, and
execute it. No semantic checks are done, thus exceptions may be thrown on bogus
programs (although they should not reach the filter in the first place).

The parse of the program will result in a list of Policy Instructions. A policy
instruction is simply a container of term instructions, which is itself a
container of instructions. Basically, the result will be having a structure of
ordered instruction classes.

All instructions are derived from a same base and implement the Visitor design
pattern as proposed by Alexandrescu. This allows traversing the structure with
different implementations (visitors). The only drawback of using visitors is
that if new instructions are added, all the visitors need to be updated.
However, in this case instructions will change little over time, and only one
visitor is present anyway.

The visitor present is in fact the interpreter of the program. The execution
visitor IvExec.

\subsection{Backend execution visitor}
The execution visitor is generic enough to support N-ary instructions. It also
supports the creation of any element. Thus if a new element is registered with
the factory, the visitor remains unchanged. The same goes for operations,
although the backend parser will need to cope with creating the proper
instructions.

The interpreter will use the VarRW interface to load and store route attributes.
It will also need an entity called the SetManager to reference sets. Ideally,
sets should be transferred independently from policies and managed on their own.
Sets may be sharded among policies, so having one copy both eases maintenance
and saves memory. This is currently not the case however. Sets are bound to
programs.

The only instruction which is treated as a special case is the REGEX. Any
element may be compared to a regular expression. Recall that all elements have a
string representation, so a regex match will always be possible.

The ON\_FALSE\_EXIT will exit the current term if a false or null is on the top
of the stack. Execution will resume on the next term. It does not pop elements
from the stack.

If a STORE operation needs to be executed, and the argument is a null element,
the operation is silently discarded.

An IvExec will return a {\em flow action} from its execution. Currently it may
be to accept the route, reject it, or perform the default action. Default
actions should be user settable and changeable from within policies. They
currently are not, but it should be easy to add a variable named {\em default
action} and allow the user to modify it.

\subsection{Set manager}
The Set manager owns all the sets of a filter. It is responsible for their
maintenance and memory management. A set manager is similar to the VarRW from
the IvExec point of view. The only difference is that the IvExec will only read
sets and never write to them.

The IvExec refers to a set via its name, and the set manager will return the
corresponding ElemSet if it exists. Sets act like pointers in the mini language
and the SetManager is responsible for dereferencing them.


\section{Policy manager: the front end}
The front end needs to cope with serval tasks:
\begin{itemize}
\item sanity check user configuration and requests.
\item generate code for policies.
\item track configuration changes and apply modifications.
\item manage backend filters.
\item manage the RIB redistribution map.
\end{itemize}
The hardest tasks probably lie in sanity checks and trying to reconfigure
filters the least possible on configuration changes. If a filter is
reconfigured, routes will need to be pushed, which is an expensive operation.

\subsection{Dependency tracking and sanity checks}
Most of the sanity checks involve tracking dependencies between protocols and
policies, and policies and sets. The policy manager should not allow a user to
delete a set which is in use for example. Also, the policy manager should not
allow a user to create a policy which already exists.

In general, policies depend on sets. If a policy uses a set, the set may not be
deleted. Also, policies instantiations via the import or export directive depend
on the policies which they refer to. Thus, a policy may not be deleted if it is
being used for an import or export.

Similarly, policies and sets need to be defined before they may be referenced.
This may be avoided, but for simplicity forward definition is a requirement.

To allow dependency tracking, a Dependency template is used. It owns pointers to
objects. These objects are referred to by names, and also have a dependency list
which refers to who is currently using them. It does not mean the object itself
depends on anything --- the list contains who depends on the object. This
template is used to track dependencies both in policies and sets.

\subsection{Code generation}
The parsing implementation is similar to the backend. All statements are parsed
and result in a PolicyStatement which contains a list of Terms which contain a
list of nodes.

All nodes implement the visitor interface. The usefulness of visitors becomes
apparent in this case. At least two passes need to be done on the nodes
(although they may probably be done in one go). First a semantic check, and then
the code generation pass.

Code generation and semantic checks are done only on instantiated policies. A
policy which is not used is totally ignored and no possible errors are reported.
This may be fixed by having a generic semantic check visitor pass through the
policy to try and see if it makes at least {\em any} sense.

\subsubsection{Semantic check pass}
The nodes must first be semantically checked as the static grammar does only a
minimum. The real semantic check resides in actually trying to execute the
policy and see if the combination of types and operations is supported by the
dispatcher. This check is done by executing the nodes of the parse tree directly.
Execution is done on all nodes (all flows of the program).

A special VarRW called the SemanticVarRW will try emulating the protocol
requested by the execution visitor. This is done via the VarMap configuration.
The SemanticVarRW knows exactly what type is expected from a certain variable.
Also, misspelling of variable names or invalid reads/writes will be caught at
this time.

The existence of sets will be checked too. Although set errors will probably
be caught when the SetDep visitor is executed to track policy and set
dependencies.

\subsubsection{Code generation pass}
There are three different visitors which generate code depending on how the policy