click-xform

pattern-based Click configuration optimizer

click-xform [options] [param=value ...] [router-file [pattern-files...]]

The click-xform tool is a Click router configuration optimizer. It reads files giving Click configuration patterns and their replacements, and a router configuration file. Then it replaces pattern matches in the configuration until none remain and writes the new configuration to the standard output.

Pattern files use the Click language (see click(5)). They contain pairs of 'elementclass' definitions, where each pair consists of one pattern text and one replacement text. The replacement for a pattern named 'X' must be named 'X_Replacement'. This example pattern file replaces all Queues with Queue-Shaper combinations:

elementclass QueuePattern {
  input -> Queue -> output;
}
elementclass QueuePattern_Replacement {
  input -> Queue -> Shaper(200) -> output;
}

A pattern text can contain an arbitrary number of elements, and an arbitrary number of input and output ports. Basically, a pattern matches a fragment of a router configuration when they have the same number of elements; their element classes match; all of the pattern's connections are duplicated in the fragment; and any connections into or out of the fragment correspond to connections to or from the pattern's input and output ports. The formal definition of matching is given below.

Any configuration strings in the pattern must match the configuration strings in the configuration subset. The pattern can use variables, which look like '$[letters, numbers and underscores]', to match a set of configuration strings; except for variables, the strings must match verbatim. A variable matches a single configuration argument. The same variable can be used multiple times in a pattern; if so, then it must match the same text on each occurrence. If a variable is used in the replacement's configuration strings, then when a replacement is made, the text that matched in the pattern will be inserted instead. For example, applying this pattern

elementclass Meters {
  input -> Meter($a)
        -> Shaper($b) -> output;
}
elementclass Meters_Replacement {
  input -> Meter($b)
        -> SlowShaper($a) -> output;
}

to this configuration

... -> Meter(1000) -> Shaper(2000) -> ...

will create this result:

... -> Meter(2000) -> SlowShaper(1000) -> ...

The optimizer will not apply the same pattern to a configuration subset twice in succession. Specifically, every replacement element is marked with the pattern that generated it; a pattern will not match a configuration fragment if every element in that fragment came from that pattern. Thus, a pattern like the QueuePattern above won't cause an infinite loop. You can still cause an infinite loop, if you'd like, by having two patterns that match the same text:

elementclass Evil1 {
  input -> Queue -> output;
}
elementclass Evil1_Replacement {
  input -> Queue -> output;
}
elementclass Evil2 {
  input -> Queue -> output;
}
elementclass Evil2_Replacement {
  input -> Queue -> output;
}

This collection of patterns will make the optimizer run forever on any configuration that has a Queue.

The click-xform transformation can be reversed with the --reverse option.

If any filename argument is a single dash "-", click-xform will use the standard input or output instead, as appropriate.

-p file
--patterns file

Read patterns and replacements from file. You can give any number of these options.

-f file
--file file

Read the router configuration to transform from file. The default is the standard input.

-e expr
--expression expr

Use expr, a string in the Click language, as the router configuration to transform.

-o file
--output file

Write the output router configuration to file. The default is the standard output.

-r, --reverse

Apply the patterns in reverse. That is, replace occurrences of the replacement texts with the corresponding pattern texts.

--help

Print usage information and exit.

--version

Print the version number and some quickie warranty information and exit.

A pattern P matches a subset S of the configuration's elements if the following conditions hold:

• There is a one-to-one mapping map from P to S that respects element classes (that is, if an element p in P has class K, then map(p) also has class K).
• The configuration strings match, possibly by using a consistent variable assignment.
• For every connection 'p1 [x] -> [y] p2' in the pattern P, there exists a connection 'map(p1) [x] -> [y] map(p2)' in the configuration subset S.
• For every connection 'c1 [x] -> [y] c2' in the configuration, one of four conditions hold:
• The connection is wholly outside the subset S. (That is, c1 is not in S and c2 is not in S.)
• The connection is inside the subset, and corresponds to a connection in the pattern. (That is, c1 is in S, c2 is in S, and P has a connection 'map-1(c1) [x] -> [y] map-1(c2)'.)
• The connection goes into the subset, and corresponds to an input port in the pattern. (That is, c1 is not in S but c2 is in S, and there exists an input port number i so that P has a connection 'input [i] -> [y] map-1(c2)', and for every connection in the pattern 'input [i] -> [z] q', there is a connection in the configuration 'c1 [x] -> [z] map(q)'.)
• The connection goes out of the subset, and corresponds to an output port in the pattern. (That is, c1 is in S but c2 is not in S, and there exists an output port number o so that P has a connection 'map-1(c1) [x] -> [o] output', and for every connection in the pattern 'q [z] -> [o] output', there is a connection in the configuration 'map(q) [z] -> [y] c2'.)

language

Eddie Kohler, kohler@cs.ucla.edu
http://www.pdos.lcs.mit.edu/click/