You can find sources of the filter language in filter/
directory. File filter/config.Y
contains filter grammar and basically translates
the source from user into a tree of f_inst structures. These trees are
later interpreted using code in filter/filter.c
.
A filter is represented by a tree of f_inst structures, one structure per "instruction". Each f_inst contains code, aux value which is usually the data type this instruction operates on and two generic arguments (a1, a2). Some instructions contain pointer(s) to other instructions in their (a1, a2) fields.
Filters use a f_val structure for their data. Each f_val
contains type and value (types are constants prefixed with T_). Few
of the types are special; T_RETURN can be or-ed with a type to indicate
that return from a function or from the whole filter should be
forced. Important thing about f_val's is that they may be copied
with a simple =
. That's fine for all currently defined types: strings
are read-only (and therefore okay), paths are copied for each
operation (okay too).
int val_compare (struct f_val v1, struct f_val v2) -- compare two values
first value
second value
Compares two values and returns -1, 0, 1 on <, =, > or 999 on error. Tree module relies on this giving consistent results so that it can build balanced trees.
int
val_in_range
(struct f_val v1, struct f_val v2) -- implement ~
operator
element
set
Checks if v1 is element (~
operator) of v2. Sets are internally represented as balanced trees, see
tree.c
module (this is not limited to sets, but for non-set cases, val_simple_in_range() is called early).
struct f_val interpret (struct f_inst * what)
filter to interpret
Interpret given tree of filter instructions. This is core function of filter system and does all the hard work.
code (which is instruction code), aux (which is extension to instruction code, typically type), arg1 and arg2 - arguments. Depending on instruction, arguments are either integers, or pointers to instruction trees. Common instructions like +, that have two expressions as arguments use TWOARGS macro to get both of them evaluated.
f_val structures are copied around, so there are no problems with memory managment.
int f_run (struct filter * filter, struct rte ** rte, struct ea_list ** tmp_attrs, struct linpool * tmp_pool, int flags) -- external entry point to filters
pointer to filter to run
pointer to pointer to rte being filtered. When route is modified, this is changed with rte_cow().
where to store newly generated temporary attributes
all filter allocations go from this pool
flags
int filter_same (struct filter * new, struct filter * old) -- compare two filters
first filter to be compared
second filter to be compared, notice that this filter is damaged while comparing.
Returns 1 in case filters are same, otherwise 0. If there are underlying bugs, it will rather say 0 on same filters than say 1 on different.
struct f_tree * find_tree (struct f_tree * t, struct f_val val)
tree to search in
value to find
Search for given value in the tree. I relies on fact that sorted tree is populated by f_val structures (that can be compared by val_compare()). In each node of tree, either single value (then t->from==t->to) or range is present.
Both set matching and switch() { }
construction is implemented using this function,
thus both are as fast as they can be.
struct f_tree * build_tree (struct f_tree * from)
degenerated tree (linked by tree->left) to be transformed into form suitable for find_tree()
Transforms denerated tree into balanced tree.
int same_tree (struct f_tree * t1, struct f_tree * t2)
first tree to be compared
second one
Compares two trees and returns 1 if they are same