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 &lt;, =, &gt; 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-&gt;from==t-&gt;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>-&gt;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> &lt;= <I>plen</I> &lt;= <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> &lt; <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 &gt; <I>plen</I>)
        !           254: - we are still on path and keep walking (node length &lt; <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 &lt;= l, h &lt;= 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>