README FOR USING RULE-LEVEL TRACING [EuroSys'06]
================================================

Author: Atul Singh.

================================================

1. Goal: Trace the execution of the system at the rule 
level, i.e., if rule r1 at node n1 fires, then find
the causally related rule executions. These causally
related rule executions could be local or remote.

2. Usage : Suppose we are running runChord.
Current mode of usage is:
$./runChord <overlog> <level> <seed> <IP>  <Delay> <bootstrap>

We modify it to following
$./runChord <overlog> <level> <seed> <IP> <Delay> <trace> <bootstrap>

Here, trace can take one of following: [TRACE|NO-TRACE]
with obvious meaning.

When TRACE is provided, a debugging-rules.olg file is automatically
linked to the orignial chord.olg file. This debugging-rules.olg
contains the table defs and rules for tracing the causality
of required tuples in backward direction. Additional rules
can be written which do it in forward direction. The planner
automatically modifies the dataflow graph to appropriately
tap the rules. Currently, all rules are tapped, there is no
interface to enable tapping one single rule.

Providing "TRACE" during startup will enable tracing to happen. 
To trace a given type of tuple, a keyword "trace" can be used 
in the base olg file (chord.olg), similar to "watch" keyword. So, 

trace(lookup).

will cause lookup tuples to be traced in backward direction.

RuleExecTuple's have the following schema, though you dont necessarily
need to know if you dont want to.

<ruleExecTuple, ruleId, localNode, tupleIn, tupleOut, 
	timeIn, timeOut, EVENT|PRECOND>

Additionally, the tupleTable tuples have the following format: 
<tupleTableTuple, tupleId, idAtSource, Source>


Rules in debugging-rules.olg will produce tuples
of following form by walking back the causality chain of a 
tuple requested to be traced. 

<report, NI, T-Origin, T-Trigger, Rule-List, Node-List>

here, report is the name of the tuple, NI is the nodeId where this
trace started, T-Trigger is the tuple which caused tracing back
to trigger and T-Origin is the last tuple in the causality chain.
Rule-List is a simple
concatenation of ruleIds encountered during tracing back and
similarly Node-List are the nodeIds where these rules were
tracked. These Lists are string concatenations and do not use
the "listtype".


3. Architecture:

We have added 3 basic classes/elements:

a. Tap: its functionality is similar to duplicator, albeit much
   simpler. It recieves a tuple and duplicates the tuple to the
   rule strand and a copy to the ruleTracer (explained below).

b. RuleTracer: its functionality is to aggregate the outputs
   of different tap elements for a given rule and construct a
   record which contains information about input, preconditions
   and output for a given rule. Taps at multiple parts of a rule 
   strand connect to a single ruleTracer.

c. TupleTracer: its functionality is similar to a duplicator.
   Depending on the what tuples are being traced, a TupleTracer
   element is inserted before the rule strand to create a tuple of 
   form <inTupleTrace, tuple-name, .....> and passed on to a 
   tupleTraceMux which is connected to the roundRobin scheduler.


The dataflow is modified as follows: for each rule, we have
multiple taps (at beg, middle or end) and one ruleTracer element.
To handle "trace" keyword, we place a tupleTracer element
after the demux at the receiving side, the port used being
dependent on the tuple being traced. All tupleTracer element's
outputs are connected to a traceMux element and this mux
finally connects to a designated port of RoundRobin element.
Note that all this modification of dataflow happens only when
TRACE is enabled.


4. Resource management: 

The invariant we want to ensure is that if a tuple is pointed by
a tuple in the ruleExecTable, then that tuple should exist in
the tupleTable. We use reference counting to ensure that. This
will use the newer table implementation which gives the required upcalls
whenever an entry in ruleExecTable expires.

5. Limitations and TODO:

a. Currently, we trace tuples arriving at the receiver side. We will
   shortly add the support for tracing tuples which are produced.

b. Handling aborted rule executions.

c. Debugging a rule. We need a functionality to monitor the different
   stages a rule exeuction goes through. Note that this is different from
   from rule tracing, here we are simply interesed in finding the output
   of every element in the rule strand.

d. Ensure all user visible tuples arrive at the receiver.

e. Better README!

f. Make materializations for tuple table and rule exec table implicit.
   We shouldn't require users to know how to index tuple tables.

g. For tuples which are "NOT" generated by the planner-generated
   dataflow, you need to provide special case to terminate the 
   backtrace. This is true for "join" tuple in Chord since it is
   generated outside the planner (may change later). For this reason,
   the last rule in our debugging-rules.olg file contains a condition
   to abort the backtrace when we hit rule "c1". This is exactly the rule
   which gets tuple "join" from thin air (i.e. no rule in the dataflow
   produces that tuple). You may have to do the same if there is 
   tuple produced in the same fasion.

h. Right now, the backtrace ends at the tuple whose
   ID is 0 (meaning there was no causally preceding event, so stop).
   You may change it to your desire, i.e. stop after going "k" hops
   or when you hit a particular rule.
