## 4. Filters

## 4.1 Filters

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).

### Function

*int*
**val_compare**
(*struct f_val* **v1**, *struct f_val* **v2**) -- compare two values

### Arguments

*struct f_val***v1**first value

*struct f_val***v2**second value

### Description

Compares two values and returns -1, 0, 1 on <, =, > or CMP_ERROR on error. Tree module relies on this giving consistent results so that it can be used for building balanced trees.

### Function

*int*
**val_same**
(*struct f_val* **v1**, *struct f_val* **v2**) -- compare two values

### Arguments

*struct f_val***v1**first value

*struct f_val***v2**second value

### Description

Compares two values and returns 1 if they are same and 0 if not. Comparison of values of different types is valid and returns 0.

### Function

*int*
**val_in_range**
(*struct f_val* **v1**, *struct f_val* **v2**) -- implement `~`

operator

### Arguments

*struct f_val***v1**element

*struct f_val***v2**set

### Description

Checks if **v1** is element (`~`

operator) of **v2**.

### Function

*struct f_val*
**interpret**
(*struct f_inst ** **what**)

### Arguments

*struct f_inst ****what**filter to interpret

### Description

Interpret given tree of filter instructions. This is core function of filter system and does all the hard work.

### Each instruction has 4 fields

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.

### Function

*int*
**f_run**
(*struct filter ** **filter**, *struct rte *** **rte**, *struct linpool ** **tmp_pool**, *int* **flags**) -- run a filter for a route

### Arguments

*struct filter ****filter**filter to run

*struct rte *****rte**route being filtered, may be modified

*struct linpool ****tmp_pool**all filter allocations go from this pool

*int***flags**flags

### Description

If filter needs to modify the route, there are several
posibilities. **rte** might be read-only (with REF_COW flag), in that
case rw copy is obtained by **rte_cow()** and **rte** is replaced. If
**rte** is originally rw, it may be directly modified (and it is never
copied).

The returned rte may reuse the (possibly cached, cloned) rta, or
(if rta was modificied) contains a modified uncached rta, which
uses parts allocated from **tmp_pool** and parts shared from original
rta. There is one exception - if **rte** is rw but contains a cached
rta and that is modified, rta in returned rte is also cached.

Ownership of cached rtas is consistent with rte, i.e. if a new rte is returned, it has its own clone of cached rta (and cached rta of read-only source rte is intact), if rte is modified in place, old cached rta is possibly freed.

### Function

*int*
**filter_same**
(*struct filter ** **new**, *struct filter ** **old**) -- compare two filters

### Arguments

*struct filter ****new**first filter to be compared

*struct filter ****old**second filter to be compared, notice that this filter is damaged while comparing.

### Description

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.

### Function

*struct f_tree **
**find_tree**
(*struct f_tree ** **t**, *struct f_val* **val**)

### Arguments

*struct f_tree ****t**tree to search in

*struct f_val***val**value to find

### Description

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

construction is implemented using this function,
thus both are as fast as they can be.
**switch()** { }

### Function

*struct f_tree **
**build_tree**
(*struct f_tree ** **from**)

### Arguments

*struct f_tree ****from**degenerated tree (linked by

**tree**->left) to be transformed into form suitable for**find_tree()**

### Description

Transforms degenerated tree into balanced tree.

### Function

*int*
**same_tree**
(*struct f_tree ** **t1**, *struct f_tree ** **t2**)

### Arguments

*struct f_tree ****t1**first tree to be compared

*struct f_tree ****t2**second one

### Description

Compares two trees and returns 1 if they are same

## 4.2 Trie for prefix sets

We use a (compressed) trie to represent prefix sets. Every node
in the trie represents one prefix (*addr*/*plen*) and *plen* also
indicates the index of the bit in the address that is used to
branch at the node. If we need to represent just a set of
prefixes, it would be simple, but we have to represent a
set of prefix patterns. Each prefix pattern consists of
*ppaddr*/*pplen* and two integers: *low* and *high*, and a prefix
*paddr*/*plen* matches that pattern if the first MIN(*plen*, *pplen*)
bits of *paddr* and *ppaddr* are the same and *low* <= *plen* <= *high*.

We use a bitmask (*accept*) to represent accepted prefix lengths
at a node. As there are 33 prefix lengths (0..32 for IPv4), but
there is just one prefix of zero length in the whole trie so we
have *zero* flag in *f_trie* (indicating whether the trie accepts
prefix 0.0.0.0/0) as a special case, and *accept* bitmask
represents accepted prefix lengths from 1 to 32.

There are two cases in prefix matching - a match when the length
of the prefix is smaller that the length of the prefix pattern,
(*plen* < *pplen*) and otherwise. The second case is simple - we
just walk through the trie and look at every visited node
whether that prefix accepts our prefix length (*plen*). The
first case is tricky - we don't want to examine every descendant
of a final node, so (when we create the trie) we have to propagate
that information from nodes to their ascendants.

Suppose that we have two masks (M1 and M2) for a node. Mask M1 represents accepted prefix lengths by just the node and mask M2 represents accepted prefix lengths by the node or any of its descendants. Therefore M2 is a bitwise or of M1 and children's M2 and this is a maintained invariant during trie building. Basically, when we want to match a prefix, we walk through the trie, check mask M1 for our prefix length and when we came to final node, we check mask M2.

There are two differences in the real implementation. First, we use a compressed trie so there is a case that we skip our final node (if it is not in the trie) and we came to node that is either extension of our prefix, or completely out of path In the first case, we also have to check M2.

Second, we really need not to maintain two separate bitmasks.
Checks for mask M1 are always larger than *applen* and we need
just the first *pplen* bits of mask M2 (if trie compression
hadn't been used it would suffice to know just $applen-th bit),
so we have to store them together in *accept* mask - the first
*pplen* bits of mask M2 and then mask M1.

There are four cases when we walk through a trie:

- we are in NULL
- we are out of path (prefixes are inconsistent)
- we are in the wanted (final) node (node length == *plen*)
- we are beyond the end of path (node length > *plen*)
- we are still on path and keep walking (node length < *plen*)

The walking code in **trie_match_prefix()** is structured according to
these cases.

### Function

*struct f_trie **
**f_new_trie**
(*linpool ** **lp**, *uint* **node_size**) -- allocates and returns a new empty trie

### Arguments

*linpool ****lp**linear pool to allocate items from

*uint***node_size**node size to be used (

*f_trie_node*and user data)

### Function

*void **
**trie_add_prefix**
(*struct f_trie ** **t**, *const net_addr ** **net**, *uint* **l**, *uint* **h**)

### Arguments

*struct f_trie ****t**trie to add to

*const net_addr ****net**IP network prefix

*uint***l**prefix lower bound

*uint***h**prefix upper bound

### Description

Adds prefix (prefix pattern) **n** to trie **t**. **l** and **h** are lower
and upper bounds on accepted prefix lengths, both inclusive.
0 <= l, h <= 32 (128 for IPv6).

Returns a pointer to the allocated node. The function can return a pointer to
an existing node if **px** and **plen** are the same. If px/plen == 0/0 (or ::/0),
a pointer to the root node is returned.

### Function

*int*
**trie_match_net**
(*struct f_trie ** **t**, *const net_addr ** **n**)

### Arguments

*struct f_trie ****t**trie

*const net_addr ****n**net address

### Description

Tries to find a matching net in the trie such that
prefix **n** matches that prefix pattern. Returns 1 if there
is such prefix pattern in the trie.

### Function

*int*
**trie_same**
(*struct f_trie ** **t1**, *struct f_trie ** **t2**)

### Arguments

*struct f_trie ****t1**first trie to be compared

*struct f_trie ****t2**second one

### Description

Compares two tries and returns 1 if they are same

### Function

*void*
**trie_format**
(*struct f_trie ** **t**, *buffer ** **buf**)

### Arguments

*struct f_trie ****t**trie to be formatted

*buffer ****buf**destination buffer

### Description

Prints the trie to the supplied buffer.

Next Previous Contents