]>
git.ipfire.org Git - thirdparty/bird.git/blob - filter/trie.c
2 * Filters: Trie for prefix sets
4 * Copyright 2009 Ondrej Zajicek <santiago@crfreenet.org>
6 * Can be freely distributed and used under the terms of the GNU GPL.
10 * DOC: Trie for prefix sets
12 * We use a (compressed) trie to represent prefix sets. Every node
13 * in the trie represents one prefix (&addr/&plen) and &plen also
14 * indicates the index of the bit in the address that is used to
15 * branch at the node. If we need to represent just a set of
16 * prefixes, it would be simple, but we have to represent a
17 * set of prefix patterns. Each prefix pattern consists of
18 * &ppaddr/&pplen and two integers: &low and &high, and a prefix
19 * &paddr/&plen matches that pattern if the first MIN(&plen, &pplen)
20 * bits of &paddr and &ppaddr are the same and &low <= &plen <= &high.
22 * We use a bitmask (&accept) to represent accepted prefix lengths
23 * at a node. As there are 33 prefix lengths (0..32 for IPv4), but
24 * there is just one prefix of zero length in the whole trie so we
25 * have &zero flag in &f_trie (indicating whether the trie accepts
26 * prefix 0.0.0.0/0) as a special case, and &accept bitmask
27 * represents accepted prefix lengths from 1 to 32.
29 * There are two cases in prefix matching - a match when the length
30 * of the prefix is smaller that the length of the prefix pattern,
31 * (&plen < &pplen) and otherwise. The second case is simple - we
32 * just walk through the trie and look at every visited node
33 * whether that prefix accepts our prefix length (&plen). The
34 * first case is tricky - we don't want to examine every descendant
35 * of a final node, so (when we create the trie) we have to propagate
36 * that information from nodes to their ascendants.
38 * Suppose that we have two masks (M1 and M2) for a node. Mask M1
39 * represents accepted prefix lengths by just the node and mask M2
40 * represents accepted prefix lengths by the node or any of its
41 * descendants. Therefore M2 is a bitwise or of M1 and children's
42 * M2 and this is a maintained invariant during trie building.
43 * Basically, when we want to match a prefix, we walk through the trie,
44 * check mask M1 for our prefix length and when we came to
45 * final node, we check mask M2.
47 * There are two differences in the real implementation. First,
48 * we use a compressed trie so there is a case that we skip our
49 * final node (if it is not in the trie) and we came to node that
50 * is either extension of our prefix, or completely out of path
51 * In the first case, we also have to check M2.
53 * Second, we really need not to maintain two separate bitmasks.
54 * Checks for mask M1 are always larger than &applen and we need
55 * just the first &pplen bits of mask M2 (if trie compression
56 * hadn't been used it would suffice to know just $applen-th bit),
57 * so we have to store them together in &accept mask - the first
58 * &pplen bits of mask M2 and then mask M1.
60 * There are four cases when we walk through a trie:
63 * - we are out of path (prefixes are inconsistent)
64 * - we are in the wanted (final) node (node length == &plen)
65 * - we are beyond the end of path (node length > &plen)
66 * - we are still on path and keep walking (node length < &plen)
68 * The walking code in trie_match_prefix() is structured according to
72 #include "nest/bird.h"
73 #include "lib/string.h"
74 #include "conf/conf.h"
75 #include "filter/filter.h"
80 * Allocates and returns a new empty trie.
83 f_new_trie(linpool
*lp
)
86 ret
= lp_allocz(lp
, sizeof(struct f_trie
));
91 static inline struct f_trie_node
*
92 new_node(struct f_trie
*t
, int plen
, ip_addr paddr
, ip_addr pmask
, ip_addr amask
)
94 struct f_trie_node
*n
= lp_allocz(t
->lp
, sizeof(struct f_trie_node
));
103 attach_node(struct f_trie_node
*parent
, struct f_trie_node
*child
)
105 parent
->c
[ipa_getbit(child
->addr
, parent
->plen
) ? 1 : 0] = child
;
111 * @px: prefix address
112 * @plen: prefix length
113 * @l: prefix lower bound
114 * @h: prefix upper bound
116 * Adds prefix (prefix pattern) @px/@plen to trie @t. @l and @h are lower
117 * and upper bounds on accepted prefix lengths, both inclusive.
118 * 0 <= l, h <= 32 (128 for IPv6).
122 trie_add_prefix(struct f_trie
*t
, ip_addr px
, int plen
, int l
, int h
)
132 ip_addr amask
= ipa_xor(ipa_mkmask(l
), ipa_mkmask(h
));
133 ip_addr pmask
= ipa_mkmask(plen
);
134 ip_addr paddr
= ipa_and(px
, pmask
);
135 struct f_trie_node
*o
= NULL
;
136 struct f_trie_node
*n
= &t
->root
;
140 ip_addr cmask
= ipa_and(n
->mask
, pmask
);
142 if (ipa_compare(ipa_and(paddr
, cmask
), ipa_and(n
->addr
, cmask
)))
144 /* We are out of path - we have to add branching node 'b'
145 between node 'o' and node 'n', and attach new node 'a'
146 as the other child of 'b'. */
147 int blen
= ipa_pxlen(paddr
, n
->addr
);
148 ip_addr bmask
= ipa_mkmask(blen
);
149 ip_addr baddr
= ipa_and(px
, bmask
);
151 /* Merge accept masks from children to get accept mask for node 'b' */
152 ip_addr baccm
= ipa_and(ipa_or(amask
, n
->accept
), bmask
);
154 struct f_trie_node
*a
= new_node(t
, plen
, paddr
, pmask
, amask
);
155 struct f_trie_node
*b
= new_node(t
, blen
, baddr
, bmask
, baccm
);
164 /* We add new node 'a' between node 'o' and node 'n' */
165 amask
= ipa_or(amask
, ipa_and(n
->accept
, pmask
));
166 struct f_trie_node
*a
= new_node(t
, plen
, paddr
, pmask
, amask
);
174 /* We already found added node in trie. Just update accept mask */
175 n
->accept
= ipa_or(n
->accept
, amask
);
179 /* Update accept mask part M2 and go deeper */
180 n
->accept
= ipa_or(n
->accept
, ipa_and(amask
, n
->mask
));
182 /* n->plen < plen and plen <= 32 (128) */
184 n
= n
->c
[ipa_getbit(paddr
, n
->plen
) ? 1 : 0];
187 /* We add new tail node 'a' after node 'o' */
188 struct f_trie_node
*a
= new_node(t
, plen
, paddr
, pmask
, amask
);
195 * @px: prefix address
196 * @plen: prefix length
198 * Tries to find a matching prefix pattern in the trie such that
199 * prefix @px/@plen matches that prefix pattern. Returns 1 if there
200 * is such prefix pattern in the trie.
203 trie_match_prefix(struct f_trie
*t
, ip_addr px
, int plen
)
205 ip_addr pmask
= ipa_mkmask(plen
);
206 ip_addr paddr
= ipa_and(px
, pmask
);
211 int plentest
= plen
- 1;
212 struct f_trie_node
*n
= &t
->root
;
216 ip_addr cmask
= ipa_and(n
->mask
, pmask
);
218 /* We are out of path */
219 if (ipa_compare(ipa_and(paddr
, cmask
), ipa_and(n
->addr
, cmask
)))
222 /* Check accept mask */
223 if (ipa_getbit(n
->accept
, plentest
))
226 /* We finished trie walk and still no match */
230 /* Choose children */
231 n
= n
->c
[(ipa_getbit(paddr
, n
->plen
)) ? 1 : 0];
238 trie_node_same(struct f_trie_node
*t1
, struct f_trie_node
*t2
)
240 if ((t1
== NULL
) && (t2
== NULL
))
243 if ((t1
== NULL
) || (t2
== NULL
))
246 if ((t1
->plen
!= t2
->plen
) ||
247 (! ipa_equal(t1
->addr
, t2
->addr
)) ||
248 (! ipa_equal(t1
->accept
, t2
->accept
)))
251 return trie_node_same(t1
->c
[0], t2
->c
[0]) && trie_node_same(t1
->c
[1], t2
->c
[1]);
256 * @t1: first trie to be compared
259 * Compares two tries and returns 1 if they are same
262 trie_same(struct f_trie
*t1
, struct f_trie
*t2
)
264 return (t1
->zero
== t2
->zero
) && trie_node_same(&t1
->root
, &t2
->root
);
268 trie_node_print(struct f_trie_node
*t
, char **sep
)
273 if (ipa_nonzero(t
->accept
))
275 logn("%s%I/%d{%I}", *sep
, t
->addr
, t
->plen
, t
->accept
);
279 trie_node_print(t
->c
[0], sep
);
280 trie_node_print(t
->c
[1], sep
);
285 * @t: trie to be printed
287 * Prints the trie to the log buffer.
290 trie_print(struct f_trie
*t
)
299 trie_node_print(&t
->root
, &sep
);