Annotation of embedaddon/bird/doc/prog-4.html, revision 1.1.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