embedaddon/bird/doc/prog-4.html - view

File: [ELWIX - Embedded LightWeight unIX -] / embedaddon / bird / doc / prog-4.html
Revision 1.1.1.1 (vendor branch): download - view: text, annotated - select for diffs - revision graph
Tue Aug 22 12:33:54 2017 UTC (6 years, 11 months ago) by misho
Branches: bird, MAIN
CVS tags: v1_6_8p3, v1_6_3p0, v1_6_3, HEAD

bird 1.6.3

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:  21: 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 f_inst structures. These trees are 24: later interpreted using code in <CODE>filter/filter.c</CODE>. 25: A filter is represented by a tree of f_inst structures, one structure per 26: "instruction". Each f_inst contains code, aux value which is 27: usually the data type this instruction operates on and two generic 28: arguments (a1, a2). Some instructions contain pointer(s) to other 29: instructions in their (a1, a2) fields. 30: Filters use a f_val structure for their data. Each f_val 31: contains type and value (types are constants prefixed with T_). Few 32: of the types are special; T_RETURN 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 f_val'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:  39: <HR><H3>Function</H3> 40: int 41: val_compare 42: (struct f_val v1, struct f_val v2) -- compare two values 43:  44: <H3>Arguments</H3> 45:  46: <DL> 47: <DT>struct f_val v1<DD>first value 48: <DT>struct f_val v2<DD>second value 49: </DL> 50: <H3>Description</H3> 51: 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: int 58: val_same 59: (struct f_val v1, struct f_val v2) -- compare two values 60:  61: <H3>Arguments</H3> 62:  63: <DL> 64: <DT>struct f_val v1<DD>first value 65: <DT>struct f_val v2<DD>second value 66: </DL> 67: <H3>Description</H3> 68: 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: int 74: val_in_range 75: (struct f_val v1, struct f_val v2) -- implement <CODE>~</CODE> operator 76:  77: <H3>Arguments</H3> 78:  79: <DL> 80: <DT>struct f_val v1<DD>element 81: <DT>struct f_val v2<DD>set 82: </DL> 83: <H3>Description</H3> 84: Checks if v1 is element (<CODE>~</CODE> operator) of v2. 85: 86: 87: <HR><H3>Function</H3> 88: struct f_val 89: interpret 90: (struct f_inst * what) 91: <H3>Arguments</H3> 92:  93: <DL> 94: <DT>struct f_inst * what<DD>filter to interpret 95: </DL> 96: <H3>Description</H3> 97: 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: 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: f_val structures are copied around, so there are no problems with 107: memory managment. 108: 109: 110: <HR><H3>Function</H3> 111: int 112: f_run 113: (struct filter * filter, struct rte ** rte, struct ea_list ** tmp_attrs, struct linpool * tmp_pool, int flags) -- run a filter for a route 114:  115: <H3>Arguments</H3> 116:  117: <DL> 118: <DT>struct filter * filter<DD>filter to run 119: <DT>struct rte ** rte<DD>route being filtered, may be modified 120: <DT>struct ea_list ** tmp_attrs<DD>temporary attributes, prepared by caller or generated by f_run() 121: <DT>struct linpool * tmp_pool<DD>all filter allocations go from this pool 122: <DT>int flags<DD>flags 123: </DL> 124: <H3>Description</H3> 125: If filter needs to modify the route, there are several 126: posibilities. rte might be read-only (with REF_COW flag), in that 127: case rw copy is obtained by rte_cow() and rte is replaced. If 128: rte is originally rw, it may be directly modified (and it is never 129: copied). 130: 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 tmp_pool and parts shared from original 133: rta. There is one exception - if rte is rw but contains a cached 134: rta and that is modified, rta in returned rte is also cached. 135: 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: int 143: filter_same 144: (struct filter * new, struct filter * old) -- compare two filters 145:  146: <H3>Arguments</H3> 147:  148: <DL> 149: <DT>struct filter * new<DD>first filter to be compared 150: <DT>struct filter * old<DD>second filter to be compared, notice that this filter is 151: damaged while comparing. 152: </DL> 153: <H3>Description</H3> 154: 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: struct f_tree * 161: find_tree 162: (struct f_tree * t, struct f_val val) 163: <H3>Arguments</H3> 164:  165: <DL> 166: <DT>struct f_tree * t<DD>tree to search in 167: <DT>struct f_val val<DD>value to find 168: </DL> 169: <H3>Description</H3> 170: Search for given value in the tree. I relies on fact that sorted tree is populated 171: by f_val structures (that can be compared by val_compare()). In each node of tree, 172: either single value (then t->from==t->to) or range is present. 173: Both set matching and <CODE>switch() { }</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: struct f_tree * 179: build_tree 180: (struct f_tree * from) 181: <H3>Arguments</H3> 182:  183: <DL> 184: <DT>struct f_tree * from<DD>degenerated tree (linked by tree->left) to be transformed into form suitable for find_tree() 185: </DL> 186: <H3>Description</H3> 187: Transforms degenerated tree into balanced tree. 188: 189: 190: <HR><H3>Function</H3> 191: int 192: same_tree 193: (struct f_tree * t1, struct f_tree * t2) 194: <H3>Arguments</H3> 195:  196: <DL> 197: <DT>struct f_tree * t1<DD>first tree to be compared 198: <DT>struct f_tree * t2<DD>second one 199: </DL> 200: <H3>Description</H3> 201: 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:  207: We use a (compressed) trie to represent prefix sets. Every node 208: in the trie represents one prefix (addr/plen) and plen 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: ppaddr/pplen and two integers: low and high, and a prefix 214: paddr/plen matches that pattern if the first MIN(plen, pplen) 215: bits of paddr and ppaddr are the same and low <= plen <= high. 216: We use a bitmask (accept) 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 zero flag in f_trie (indicating whether the trie accepts 220: prefix 0.0.0.0/0) as a special case, and accept bitmask 221: represents accepted prefix lengths from 1 to 32. 222: 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: (plen < pplen) 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 (plen). 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: 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: 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: Second, we really need not to maintain two separate bitmasks. 244: Checks for mask M1 are always larger than applen and we need 245: just the first pplen 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 accept mask - the first 248: pplen bits of mask M2 and then mask M1. 249: There are four cases when we walk through a trie: 250: - we are in NULL 251: - we are out of path (prefixes are inconsistent) 252: - we are in the wanted (final) node (node length == plen) 253: - we are beyond the end of path (node length > plen) 254: - we are still on path and keep walking (node length < plen) 255: The walking code in trie_match_prefix() is structured according to 256: these cases. 257:  258: <HR><H3>Function</H3> 259: struct f_trie * 260: f_new_trie 261: (linpool * lp, uint node_size) -- allocates and returns a new empty trie 262:  263: <H3>Arguments</H3> 264:  265: <DL> 266: <DT>linpool * lp<DD>linear pool to allocate items from 267: <DT>uint node_size<DD>node size to be used (f_trie_node and user data) 268: </DL> 269: 270: 271: <HR><H3>Function</H3> 272: void * 273: trie_add_prefix 274: (struct f_trie * t, ip_addr px, int plen, int l, int h) 275: <H3>Arguments</H3> 276:  277: <DL> 278: <DT>struct f_trie * t<DD>trie to add to 279: <DT>ip_addr px<DD>prefix address 280: <DT>int plen<DD>prefix length 281: <DT>int l<DD>prefix lower bound 282: <DT>int h<DD>prefix upper bound 283: </DL> 284: <H3>Description</H3> 285: Adds prefix (prefix pattern) px/plen to trie t. l and h are lower 286: and upper bounds on accepted prefix lengths, both inclusive. 287: 0 <= l, h <= 32 (128 for IPv6). 288: Returns a pointer to the allocated node. The function can return a pointer to 289: an existing node if px and plen 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: int 295: trie_match_prefix 296: (struct f_trie * t, ip_addr px, int plen) 297: <H3>Arguments</H3> 298:  299: <DL> 300: <DT>struct f_trie * t<DD>trie 301: <DT>ip_addr px<DD>prefix address 302: <DT>int plen<DD>prefix length 303: </DL> 304: <H3>Description</H3> 305: Tries to find a matching prefix pattern in the trie such that 306: prefix px/plen matches that prefix pattern. Returns 1 if there 307: is such prefix pattern in the trie. 308: 309: 310: <HR><H3>Function</H3> 311: int 312: trie_same 313: (struct f_trie * t1, struct f_trie * t2) 314: <H3>Arguments</H3> 315:  316: <DL> 317: <DT>struct f_trie * t1<DD>first trie to be compared 318: <DT>struct f_trie * t2<DD>second one 319: </DL> 320: <H3>Description</H3> 321: Compares two tries and returns 1 if they are same 322: 323: 324: <HR><H3>Function</H3> 325: void 326: trie_format 327: (struct f_trie * t, buffer * buf) 328: <H3>Arguments</H3> 329:  330: <DL> 331: <DT>struct f_trie * t<DD>trie to be formatted 332: <DT>buffer * buf<DD>destination buffer 333: </DL> 334: <H3>Description</H3> 335: 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>