click constraints [ref: ma]

[Eddie Kohler]

HI Danny Daniel,

> what is a "wholly-push context"?

Ports can have more than one connection to them. So you can hook up to an
input or output port more than once. A "wholly-push context" just means
that all the connections to a port are push. (NOTE: once ports'
personalities have been discovered -- all the agnostics have been reduced
to either push or pull -- Click checks another invariant: that all push
outputs are connected exactly once, and that all pull inputs are connected
exactly once.)

Agnostics are exactly a kind of personality polymorphism.

> i'd like to model the internal flows too. you hint at the analysis that
> exploits this. have you written anything about it?

no -- we wrote something about it, but it didn't seem relevant for the
paper. We don't have a notation. This analysis is provided by the factions
themselves. It's pretty simple. There are virtual functions on each faction
for "forward flow" (for a given input, what outputs can a packet reach?)
and "backward flow" (for a given output, what inputs could a packet have
come from?). Say you have a faction `f', with 3 inputs and 3 outputs, and
you want to know, "if a packet enters on input 0, which output(s) can it
come out on?" You do this:

	Bitvector bv = f->forward_flow(0); // 0 is input number

Now `bv' will be a bitvector with 3 elements, corresponding to outputs 0,
1, and 2. If the bit for a given output is on, the packet can flow there.

Personality analysis is done as a fixed-point algorithm over the set of all
connections in the system. If one end of a connection is agnostic and the
other isn't, then the agnostic port is assigned the same personality as the
other port. However, Click first adds fake connections to handle the flow
patterns inside agnostic factions. The reasoning is this: If an agnostic
input port is determined to be push, and packets can flow from that input
port out to a given output port, then the output port must also be push.
So:

	For every input agnostic port f.in[i],
	  Find the forward flow pattern f->forward_flow(i).
	  For each output `o' in the flow pattern,
	    Add a fake connection from f.out[o] -> f.in[i].
            // This will ensure that f.out[o] and f.in[i] have the same
	    // personality.
	For every output agnostic port f.out[o],
	  Fidn the backward flow pattern f->backward_flow(o).
	  For each input `i' in the flow pattern,
	    If f.in[i] is not agnostic, // we handled agnostic ones above
	      Add a fake connection from f.out[o] -> f.in[i].

Say you've got this setup: (Push ports are H, pull ports are L, agnostic
ports are A.)

    __________      ____________     ___________     ___________
    |  f1    H|---->|A    f2   A|--->|A   f3   A|--->|H   f4   |
    |_________|     |           |    ------------    -----------
                    |           |    ___________
                    |          A|--->|L   f5   |
                    -------------    -----------

All factions have the default flow pattern (from every input to every
output and vice versa) except for f2, which has this flow pattern:

       from input 0 to output 0 only  (forward_flow(0) == [true, false])
       to output 0 from input 0       (backward_flow(0) == [true])
       to output 1 from nowhere       (backward_flow(1) == [false])

Click needs to find out what personalities belong to the following agnostic
ports:
	f2.in[0]  f2.out[0]   f2.out[1]   f3.in[0]   f3.out[0]
It also needs to check that there are no connections between push and pull
ports.

We start with these real connections:
	f1.out[0] -> f2.in[0]
	f2.out[0] -> f3.in[0]
	f2.out[1] -> f5.in[0]
	f3.out[0] -> f4.in[0]
Because of flow, we add these fake connections:
	f2.out[0] -> f2.in[0]
	f3.out[0] -> f3.in[0]

Now the algorithm will discover port personalities something like this:
	f2.in[0] == H		// f1.out[0] == H, f1.out[0] -> f2.in[0]
	f2.out[1] == L		// f5.in[0] == L, f2.out[1] -> f5.in[0]
	f3.out[0] == H		// f4.in[0] == H, f3.out[0] -> f4.in[0]
// second iteration
	f2.out[0] == H		// f2.in[0] == H, f2.out[0] -> f2.in[0] (FAKE)
	f3.in[0] == H		// f3.out[0] == H, f3.out[0] -> f3.in[0] (FAKE)
// third iteration
// nothing changes, so we are done

There are not-so-great things about this approach. Really you need flow
patterns for two things: for personality determination, and for real flow
determination (if a packet starts at faction F, where can it end up?). The
flow pattern for flow determination is strictly larger than the flow
pattern you care about for personality determination; we only implement the
flow pattern for flow determination. The current combination of the two
means that you can't write some kinds of complex faction. (Example at end.)

> can you automatically construct
> "specs" for compound factions from their constituent parts?

Compound factions don't exist by trhe time all of this has been done; only
their constituent parts do. Compounds are compiled away before the analysis
starts.

love,
ed

------------------------------------
Say you want a faction which models random lossage. But you want to give it
two outputs. Normally, packets will be output on port 0, but with a random
probability, it will output the packet on port 1 instead.

Really we would like such a faction to look like this:

       ______________________
       |A    randomloss	   A|
       |		    |
       |		   H|
       ----------------------

The second output port HAS to be push because packets are spontaneously
sent to it. (The faction has a choice over which push output ports to use,
and which pull input ports to use; but push inputs and pull outputs are
chosen from the outside.) But the flow pattern is teh default: anything can
go to anywhere. It looks like this:

       randomloss->forward_flow(0) == [true, true]
       randomloss->backward_flow(0) == randomloss->backward_flow(1) == [true]

So the algorithm given above will FORCE all ports to be push, even though
this faction could behave perfectly reasonably if in[0] and out[0] were
both pull.

I think maybe the thing to do is to use the flow patterns we've already
got, but only add fake connections from agnostic ports to OTHER agnostic
ports. This would be reasonable since someone who was depending on the flow
stuff to ensure that an agnostic port always had to be push, should have
just made it push in the first place.