Annotation of embedaddon/bird/doc/prog-4.html, revision 1.1
1.1 ! misho 1: <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2 Final//EN">
! 2: <HTML>
! 3: <HEAD>
! 4: <META NAME="GENERATOR" CONTENT="LinuxDoc-Tools 1.0.9">
! 5: <TITLE>BIRD Programmer's Documentation: Filters</TITLE>
! 6: <LINK HREF="prog-5.html" REL=next>
! 7: <LINK HREF="prog-3.html" REL=previous>
! 8: <LINK HREF="prog.html#toc4" REL=contents>
! 9: </HEAD>
! 10: <BODY>
! 11: <A HREF="prog-5.html">Next</A>
! 12: <A HREF="prog-3.html">Previous</A>
! 13: <A HREF="prog.html#toc4">Contents</A>
! 14: <HR>
! 15: <H2><A NAME="s4">4.</A> <A HREF="prog.html#toc4">Filters</A></H2>
! 16:
! 17: <H2><A NAME="ss4.1">4.1</A> <A HREF="prog.html#toc4.1">Filters</A>
! 18: </H2>
! 19:
! 20: <P>
! 21: <P>You can find sources of the filter language in <CODE>filter/</CODE>
! 22: directory. File <CODE>filter/config.Y</CODE> contains filter grammar and basically translates
! 23: the source from user into a tree of <I>f_inst</I> structures. These trees are
! 24: later interpreted using code in <CODE>filter/filter.c</CODE>.
! 25: <P>A filter is represented by a tree of <I>f_inst</I> structures, one structure per
! 26: "instruction". Each <I>f_inst</I> contains <B>code</B>, <B>aux</B> value which is
! 27: usually the data type this instruction operates on and two generic
! 28: arguments (<B>a1</B>, <B>a2</B>). Some instructions contain pointer(s) to other
! 29: instructions in their (<B>a1</B>, <B>a2</B>) fields.
! 30: <P>Filters use a <I>f_val</I> structure for their data. Each <I>f_val</I>
! 31: contains type and value (types are constants prefixed with <I>T_</I>). Few
! 32: of the types are special; <I>T_RETURN</I> can be or-ed with a type to indicate
! 33: that return from a function or from the whole filter should be
! 34: forced. Important thing about <I>f_val</I>'s is that they may be copied
! 35: with a simple <CODE>=</CODE>. That's fine for all currently defined types: strings
! 36: are read-only (and therefore okay), paths are copied for each
! 37: operation (okay too).
! 38: <P>
! 39: <P><HR><H3>Function</H3>
! 40: <P><I>int</I>
! 41: <B>val_compare</B>
! 42: (<I>struct f_val</I> <B>v1</B>, <I>struct f_val</I> <B>v2</B>) -- compare two values
! 43: <P>
! 44: <H3>Arguments</H3>
! 45: <P>
! 46: <DL>
! 47: <DT><I>struct f_val</I> <B>v1</B><DD><P>first value
! 48: <DT><I>struct f_val</I> <B>v2</B><DD><P>second value
! 49: </DL>
! 50: <H3>Description</H3>
! 51: <P>Compares two values and returns -1, 0, 1 on <, =, > or CMP_ERROR on
! 52: error. Tree module relies on this giving consistent results so
! 53: that it can be used for building balanced trees.
! 54:
! 55:
! 56: <HR><H3>Function</H3>
! 57: <P><I>int</I>
! 58: <B>val_same</B>
! 59: (<I>struct f_val</I> <B>v1</B>, <I>struct f_val</I> <B>v2</B>) -- compare two values
! 60: <P>
! 61: <H3>Arguments</H3>
! 62: <P>
! 63: <DL>
! 64: <DT><I>struct f_val</I> <B>v1</B><DD><P>first value
! 65: <DT><I>struct f_val</I> <B>v2</B><DD><P>second value
! 66: </DL>
! 67: <H3>Description</H3>
! 68: <P>Compares two values and returns 1 if they are same and 0 if not.
! 69: Comparison of values of different types is valid and returns 0.
! 70:
! 71:
! 72: <HR><H3>Function</H3>
! 73: <P><I>int</I>
! 74: <B>val_in_range</B>
! 75: (<I>struct f_val</I> <B>v1</B>, <I>struct f_val</I> <B>v2</B>) -- implement <CODE>~</CODE> operator
! 76: <P>
! 77: <H3>Arguments</H3>
! 78: <P>
! 79: <DL>
! 80: <DT><I>struct f_val</I> <B>v1</B><DD><P>element
! 81: <DT><I>struct f_val</I> <B>v2</B><DD><P>set
! 82: </DL>
! 83: <H3>Description</H3>
! 84: <P>Checks if <B>v1</B> is element (<CODE>~</CODE> operator) of <B>v2</B>.
! 85:
! 86:
! 87: <HR><H3>Function</H3>
! 88: <P><I>struct f_val</I>
! 89: <B>interpret</B>
! 90: (<I>struct f_inst *</I> <B>what</B>)
! 91: <H3>Arguments</H3>
! 92: <P>
! 93: <DL>
! 94: <DT><I>struct f_inst *</I> <B>what</B><DD><P>filter to interpret
! 95: </DL>
! 96: <H3>Description</H3>
! 97: <P>Interpret given tree of filter instructions. This is core function
! 98: of filter system and does all the hard work.
! 99: <H3>Each instruction has 4 fields</H3>
! 100: <P>code (which is instruction code),
! 101: aux (which is extension to instruction code, typically type),
! 102: arg1 and arg2 - arguments. Depending on instruction, arguments
! 103: are either integers, or pointers to instruction trees. Common
! 104: instructions like +, that have two expressions as arguments use
! 105: TWOARGS macro to get both of them evaluated.
! 106: <P><I>f_val</I> structures are copied around, so there are no problems with
! 107: memory managment.
! 108:
! 109:
! 110: <HR><H3>Function</H3>
! 111: <P><I>int</I>
! 112: <B>f_run</B>
! 113: (<I>struct filter *</I> <B>filter</B>, <I>struct rte **</I> <B>rte</B>, <I>struct ea_list **</I> <B>tmp_attrs</B>, <I>struct linpool *</I> <B>tmp_pool</B>, <I>int</I> <B>flags</B>) -- run a filter for a route
! 114: <P>
! 115: <H3>Arguments</H3>
! 116: <P>
! 117: <DL>
! 118: <DT><I>struct filter *</I> <B>filter</B><DD><P>filter to run
! 119: <DT><I>struct rte **</I> <B>rte</B><DD><P>route being filtered, may be modified
! 120: <DT><I>struct ea_list **</I> <B>tmp_attrs</B><DD><P>temporary attributes, prepared by caller or generated by <B>f_run()</B>
! 121: <DT><I>struct linpool *</I> <B>tmp_pool</B><DD><P>all filter allocations go from this pool
! 122: <DT><I>int</I> <B>flags</B><DD><P>flags
! 123: </DL>
! 124: <H3>Description</H3>
! 125: <P>If filter needs to modify the route, there are several
! 126: posibilities. <B>rte</B> might be read-only (with REF_COW flag), in that
! 127: case rw copy is obtained by <B>rte_cow()</B> and <B>rte</B> is replaced. If
! 128: <B>rte</B> is originally rw, it may be directly modified (and it is never
! 129: copied).
! 130: <P>The returned rte may reuse the (possibly cached, cloned) rta, or
! 131: (if rta was modificied) contains a modified uncached rta, which
! 132: uses parts allocated from <B>tmp_pool</B> and parts shared from original
! 133: rta. There is one exception - if <B>rte</B> is rw but contains a cached
! 134: rta and that is modified, rta in returned rte is also cached.
! 135: <P>Ownership of cached rtas is consistent with rte, i.e.
! 136: if a new rte is returned, it has its own clone of cached rta
! 137: (and cached rta of read-only source rte is intact), if rte is
! 138: modified in place, old cached rta is possibly freed.
! 139:
! 140:
! 141: <HR><H3>Function</H3>
! 142: <P><I>int</I>
! 143: <B>filter_same</B>
! 144: (<I>struct filter *</I> <B>new</B>, <I>struct filter *</I> <B>old</B>) -- compare two filters
! 145: <P>
! 146: <H3>Arguments</H3>
! 147: <P>
! 148: <DL>
! 149: <DT><I>struct filter *</I> <B>new</B><DD><P>first filter to be compared
! 150: <DT><I>struct filter *</I> <B>old</B><DD><P>second filter to be compared, notice that this filter is
! 151: damaged while comparing.
! 152: </DL>
! 153: <H3>Description</H3>
! 154: <P>Returns 1 in case filters are same, otherwise 0. If there are
! 155: underlying bugs, it will rather say 0 on same filters than say
! 156: 1 on different.
! 157:
! 158:
! 159: <HR><H3>Function</H3>
! 160: <P><I>struct f_tree *</I>
! 161: <B>find_tree</B>
! 162: (<I>struct f_tree *</I> <B>t</B>, <I>struct f_val</I> <B>val</B>)
! 163: <H3>Arguments</H3>
! 164: <P>
! 165: <DL>
! 166: <DT><I>struct f_tree *</I> <B>t</B><DD><P>tree to search in
! 167: <DT><I>struct f_val</I> <B>val</B><DD><P>value to find
! 168: </DL>
! 169: <H3>Description</H3>
! 170: <P>Search for given value in the tree. I relies on fact that sorted tree is populated
! 171: by <I>f_val</I> structures (that can be compared by <B>val_compare()</B>). In each node of tree,
! 172: either single value (then t->from==t->to) or range is present.
! 173: <P>Both set matching and <CODE><B>switch()</B> { }</CODE> construction is implemented using this function,
! 174: thus both are as fast as they can be.
! 175:
! 176:
! 177: <HR><H3>Function</H3>
! 178: <P><I>struct f_tree *</I>
! 179: <B>build_tree</B>
! 180: (<I>struct f_tree *</I> <B>from</B>)
! 181: <H3>Arguments</H3>
! 182: <P>
! 183: <DL>
! 184: <DT><I>struct f_tree *</I> <B>from</B><DD><P>degenerated tree (linked by <B>tree</B>->left) to be transformed into form suitable for <B>find_tree()</B>
! 185: </DL>
! 186: <H3>Description</H3>
! 187: <P>Transforms degenerated tree into balanced tree.
! 188:
! 189:
! 190: <HR><H3>Function</H3>
! 191: <P><I>int</I>
! 192: <B>same_tree</B>
! 193: (<I>struct f_tree *</I> <B>t1</B>, <I>struct f_tree *</I> <B>t2</B>)
! 194: <H3>Arguments</H3>
! 195: <P>
! 196: <DL>
! 197: <DT><I>struct f_tree *</I> <B>t1</B><DD><P>first tree to be compared
! 198: <DT><I>struct f_tree *</I> <B>t2</B><DD><P>second one
! 199: </DL>
! 200: <H3>Description</H3>
! 201: <P>Compares two trees and returns 1 if they are same
! 202:
! 203: <H2><A NAME="ss4.2">4.2</A> <A HREF="prog.html#toc4.2">Trie for prefix sets</A>
! 204: </H2>
! 205:
! 206: <P>
! 207: <P>We use a (compressed) trie to represent prefix sets. Every node
! 208: in the trie represents one prefix (<I>addr</I>/<I>plen</I>) and <I>plen</I> also
! 209: indicates the index of the bit in the address that is used to
! 210: branch at the node. If we need to represent just a set of
! 211: prefixes, it would be simple, but we have to represent a
! 212: set of prefix patterns. Each prefix pattern consists of
! 213: <I>ppaddr</I>/<I>pplen</I> and two integers: <I>low</I> and <I>high</I>, and a prefix
! 214: <I>paddr</I>/<I>plen</I> matches that pattern if the first MIN(<I>plen</I>, <I>pplen</I>)
! 215: bits of <I>paddr</I> and <I>ppaddr</I> are the same and <I>low</I> <= <I>plen</I> <= <I>high</I>.
! 216: <P>We use a bitmask (<I>accept</I>) to represent accepted prefix lengths
! 217: at a node. As there are 33 prefix lengths (0..32 for IPv4), but
! 218: there is just one prefix of zero length in the whole trie so we
! 219: have <I>zero</I> flag in <I>f_trie</I> (indicating whether the trie accepts
! 220: prefix 0.0.0.0/0) as a special case, and <I>accept</I> bitmask
! 221: represents accepted prefix lengths from 1 to 32.
! 222: <P>There are two cases in prefix matching - a match when the length
! 223: of the prefix is smaller that the length of the prefix pattern,
! 224: (<I>plen</I> < <I>pplen</I>) and otherwise. The second case is simple - we
! 225: just walk through the trie and look at every visited node
! 226: whether that prefix accepts our prefix length (<I>plen</I>). The
! 227: first case is tricky - we don't want to examine every descendant
! 228: of a final node, so (when we create the trie) we have to propagate
! 229: that information from nodes to their ascendants.
! 230: <P>Suppose that we have two masks (M1 and M2) for a node. Mask M1
! 231: represents accepted prefix lengths by just the node and mask M2
! 232: represents accepted prefix lengths by the node or any of its
! 233: descendants. Therefore M2 is a bitwise or of M1 and children's
! 234: M2 and this is a maintained invariant during trie building.
! 235: Basically, when we want to match a prefix, we walk through the trie,
! 236: check mask M1 for our prefix length and when we came to
! 237: final node, we check mask M2.
! 238: <P>There are two differences in the real implementation. First,
! 239: we use a compressed trie so there is a case that we skip our
! 240: final node (if it is not in the trie) and we came to node that
! 241: is either extension of our prefix, or completely out of path
! 242: In the first case, we also have to check M2.
! 243: <P>Second, we really need not to maintain two separate bitmasks.
! 244: Checks for mask M1 are always larger than <I>applen</I> and we need
! 245: just the first <I>pplen</I> bits of mask M2 (if trie compression
! 246: hadn't been used it would suffice to know just $applen-th bit),
! 247: so we have to store them together in <I>accept</I> mask - the first
! 248: <I>pplen</I> bits of mask M2 and then mask M1.
! 249: <P>There are four cases when we walk through a trie:
! 250: <P>- we are in NULL
! 251: - we are out of path (prefixes are inconsistent)
! 252: - we are in the wanted (final) node (node length == <I>plen</I>)
! 253: - we are beyond the end of path (node length > <I>plen</I>)
! 254: - we are still on path and keep walking (node length < <I>plen</I>)
! 255: <P>The walking code in <B>trie_match_prefix()</B> is structured according to
! 256: these cases.
! 257: <P>
! 258: <P><HR><H3>Function</H3>
! 259: <P><I>struct f_trie *</I>
! 260: <B>f_new_trie</B>
! 261: (<I>linpool *</I> <B>lp</B>, <I>uint</I> <B>node_size</B>) -- allocates and returns a new empty trie
! 262: <P>
! 263: <H3>Arguments</H3>
! 264: <P>
! 265: <DL>
! 266: <DT><I>linpool *</I> <B>lp</B><DD><P>linear pool to allocate items from
! 267: <DT><I>uint</I> <B>node_size</B><DD><P>node size to be used (<I>f_trie_node</I> and user data)
! 268: </DL>
! 269:
! 270:
! 271: <HR><H3>Function</H3>
! 272: <P><I>void *</I>
! 273: <B>trie_add_prefix</B>
! 274: (<I>struct f_trie *</I> <B>t</B>, <I>ip_addr</I> <B>px</B>, <I>int</I> <B>plen</B>, <I>int</I> <B>l</B>, <I>int</I> <B>h</B>)
! 275: <H3>Arguments</H3>
! 276: <P>
! 277: <DL>
! 278: <DT><I>struct f_trie *</I> <B>t</B><DD><P>trie to add to
! 279: <DT><I>ip_addr</I> <B>px</B><DD><P>prefix address
! 280: <DT><I>int</I> <B>plen</B><DD><P>prefix length
! 281: <DT><I>int</I> <B>l</B><DD><P>prefix lower bound
! 282: <DT><I>int</I> <B>h</B><DD><P>prefix upper bound
! 283: </DL>
! 284: <H3>Description</H3>
! 285: <P>Adds prefix (prefix pattern) <B>px</B>/<B>plen</B> to trie <B>t</B>. <B>l</B> and <B>h</B> are lower
! 286: and upper bounds on accepted prefix lengths, both inclusive.
! 287: 0 <= l, h <= 32 (128 for IPv6).
! 288: <P>Returns a pointer to the allocated node. The function can return a pointer to
! 289: an existing node if <B>px</B> and <B>plen</B> are the same. If px/plen == 0/0 (or ::/0),
! 290: a pointer to the root node is returned.
! 291:
! 292:
! 293: <HR><H3>Function</H3>
! 294: <P><I>int</I>
! 295: <B>trie_match_prefix</B>
! 296: (<I>struct f_trie *</I> <B>t</B>, <I>ip_addr</I> <B>px</B>, <I>int</I> <B>plen</B>)
! 297: <H3>Arguments</H3>
! 298: <P>
! 299: <DL>
! 300: <DT><I>struct f_trie *</I> <B>t</B><DD><P>trie
! 301: <DT><I>ip_addr</I> <B>px</B><DD><P>prefix address
! 302: <DT><I>int</I> <B>plen</B><DD><P>prefix length
! 303: </DL>
! 304: <H3>Description</H3>
! 305: <P>Tries to find a matching prefix pattern in the trie such that
! 306: prefix <B>px</B>/<B>plen</B> matches that prefix pattern. Returns 1 if there
! 307: is such prefix pattern in the trie.
! 308:
! 309:
! 310: <HR><H3>Function</H3>
! 311: <P><I>int</I>
! 312: <B>trie_same</B>
! 313: (<I>struct f_trie *</I> <B>t1</B>, <I>struct f_trie *</I> <B>t2</B>)
! 314: <H3>Arguments</H3>
! 315: <P>
! 316: <DL>
! 317: <DT><I>struct f_trie *</I> <B>t1</B><DD><P>first trie to be compared
! 318: <DT><I>struct f_trie *</I> <B>t2</B><DD><P>second one
! 319: </DL>
! 320: <H3>Description</H3>
! 321: <P>Compares two tries and returns 1 if they are same
! 322:
! 323:
! 324: <HR><H3>Function</H3>
! 325: <P><I>void</I>
! 326: <B>trie_format</B>
! 327: (<I>struct f_trie *</I> <B>t</B>, <I>buffer *</I> <B>buf</B>)
! 328: <H3>Arguments</H3>
! 329: <P>
! 330: <DL>
! 331: <DT><I>struct f_trie *</I> <B>t</B><DD><P>trie to be formatted
! 332: <DT><I>buffer *</I> <B>buf</B><DD><P>destination buffer
! 333: </DL>
! 334: <H3>Description</H3>
! 335: <P>Prints the trie to the supplied buffer.
! 336:
! 337: <HR>
! 338: <A HREF="prog-5.html">Next</A>
! 339: <A HREF="prog-3.html">Previous</A>
! 340: <A HREF="prog.html#toc4">Contents</A>
! 341: </BODY>
! 342: </HTML>
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to prog-4.html CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / bird / doc