]>
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"
79 * In the trie code, the prefix length is internally treated as for the whole
80 * ip_addr, regardless whether it contains an IPv4 or IPv6 address. Therefore,
81 * remaining definitions make sense.
84 #define ipa_mkmask(x) ip6_mkmask(x)
85 #define ipa_masklen(x) ip6_masklen(&x)
86 #define ipa_pxlen(x,y) ip6_pxlen(x,y)
87 #define ipa_getbit(x,n) ip6_getbit(x,n)
91 * f_new_trie - allocates and returns a new empty trie
92 * @lp: linear pool to allocate items from
93 * @node_size: node size to be used (&f_trie_node and user data)
96 f_new_trie(linpool
*lp
, uint node_size
)
99 ret
= lp_allocz(lp
, sizeof(struct f_trie
) + node_size
);
101 ret
->node_size
= node_size
;
105 static inline struct f_trie_node
*
106 new_node(struct f_trie
*t
, int plen
, ip_addr paddr
, ip_addr pmask
, ip_addr amask
)
108 struct f_trie_node
*n
= lp_allocz(t
->lp
, t
->node_size
);
117 attach_node(struct f_trie_node
*parent
, struct f_trie_node
*child
)
119 parent
->c
[ipa_getbit(child
->addr
, parent
->plen
) ? 1 : 0] = child
;
125 * @net: IP network prefix
126 * @l: prefix lower bound
127 * @h: prefix upper bound
129 * Adds prefix (prefix pattern) @n to trie @t. @l and @h are lower
130 * and upper bounds on accepted prefix lengths, both inclusive.
131 * 0 <= l, h <= 32 (128 for IPv6).
133 * Returns a pointer to the allocated node. The function can return a pointer to
134 * an existing node if @px and @plen are the same. If px/plen == 0/0 (or ::/0),
135 * a pointer to the root node is returned.
139 trie_add_prefix(struct f_trie
*t
, const net_addr
*net
, uint l
, uint h
)
141 ip_addr px
= net_prefix(net
);
142 uint plen
= net_pxlen(net
);
144 if (net
->type
== NET_IP4
)
146 const uint delta
= IP6_MAX_PREFIX_LENGTH
- IP4_MAX_PREFIX_LENGTH
;
160 ip_addr amask
= ipa_xor(ipa_mkmask(l
), ipa_mkmask(h
));
161 ip_addr pmask
= ipa_mkmask(plen
);
162 ip_addr paddr
= ipa_and(px
, pmask
);
163 struct f_trie_node
*o
= NULL
;
164 struct f_trie_node
*n
= t
->root
;
168 ip_addr cmask
= ipa_and(n
->mask
, pmask
);
170 if (ipa_compare(ipa_and(paddr
, cmask
), ipa_and(n
->addr
, cmask
)))
172 /* We are out of path - we have to add branching node 'b'
173 between node 'o' and node 'n', and attach new node 'a'
174 as the other child of 'b'. */
175 int blen
= ipa_pxlen(paddr
, n
->addr
);
176 ip_addr bmask
= ipa_mkmask(blen
);
177 ip_addr baddr
= ipa_and(px
, bmask
);
179 /* Merge accept masks from children to get accept mask for node 'b' */
180 ip_addr baccm
= ipa_and(ipa_or(amask
, n
->accept
), bmask
);
182 struct f_trie_node
*a
= new_node(t
, plen
, paddr
, pmask
, amask
);
183 struct f_trie_node
*b
= new_node(t
, blen
, baddr
, bmask
, baccm
);
192 /* We add new node 'a' between node 'o' and node 'n' */
193 amask
= ipa_or(amask
, ipa_and(n
->accept
, pmask
));
194 struct f_trie_node
*a
= new_node(t
, plen
, paddr
, pmask
, amask
);
202 /* We already found added node in trie. Just update accept mask */
203 n
->accept
= ipa_or(n
->accept
, amask
);
207 /* Update accept mask part M2 and go deeper */
208 n
->accept
= ipa_or(n
->accept
, ipa_and(amask
, n
->mask
));
210 /* n->plen < plen and plen <= 32 (128) */
212 n
= n
->c
[ipa_getbit(paddr
, n
->plen
) ? 1 : 0];
215 /* We add new tail node 'a' after node 'o' */
216 struct f_trie_node
*a
= new_node(t
, plen
, paddr
, pmask
, amask
);
223 trie_match_prefix(struct f_trie
*t
, ip_addr px
, int plen
)
225 ip_addr pmask
= ipa_mkmask(plen
);
226 ip_addr paddr
= ipa_and(px
, pmask
);
231 int plentest
= plen
- 1;
232 struct f_trie_node
*n
= t
->root
;
236 ip_addr cmask
= ipa_and(n
->mask
, pmask
);
238 /* We are out of path */
239 if (ipa_compare(ipa_and(paddr
, cmask
), ipa_and(n
->addr
, cmask
)))
242 /* Check accept mask */
243 if (ipa_getbit(n
->accept
, plentest
))
246 /* We finished trie walk and still no match */
250 /* Choose children */
251 n
= n
->c
[(ipa_getbit(paddr
, n
->plen
)) ? 1 : 0];
262 * Tries to find a matching net in the trie such that
263 * prefix @n matches that prefix pattern. Returns 1 if there
264 * is such prefix pattern in the trie.
267 trie_match_net(struct f_trie
*t
, const net_addr
*n
)
274 add
= IP6_MAX_PREFIX_LENGTH
- IP4_MAX_PREFIX_LENGTH
;
277 return trie_match_prefix(t
, net_prefix(n
), net_pxlen(n
) + add
);
281 trie_node_same(struct f_trie_node
*t1
, struct f_trie_node
*t2
)
283 if ((t1
== NULL
) && (t2
== NULL
))
286 if ((t1
== NULL
) || (t2
== NULL
))
289 if ((t1
->plen
!= t2
->plen
) ||
290 (! ipa_equal(t1
->addr
, t2
->addr
)) ||
291 (! ipa_equal(t1
->accept
, t2
->accept
)))
294 return trie_node_same(t1
->c
[0], t2
->c
[0]) && trie_node_same(t1
->c
[1], t2
->c
[1]);
299 * @t1: first trie to be compared
302 * Compares two tries and returns 1 if they are same
305 trie_same(struct f_trie
*t1
, struct f_trie
*t2
)
307 return (t1
->zero
== t2
->zero
) && trie_node_same(t1
->root
, t2
->root
);
311 trie_node_format(struct f_trie_node
*t
, buffer
*buf
)
316 if (ipa_nonzero(t
->accept
))
317 buffer_print(buf
, "%I/%d{%I}, ", t
->addr
, t
->plen
, t
->accept
);
319 trie_node_format(t
->c
[0], buf
);
320 trie_node_format(t
->c
[1], buf
);
325 * @t: trie to be formatted
326 * @buf: destination buffer
328 * Prints the trie to the supplied buffer.
331 trie_format(struct f_trie
*t
, buffer
*buf
)
333 buffer_puts(buf
, "[");
336 buffer_print(buf
, "%I/%d", IPA_NONE
, 0);
337 trie_node_format(t
->root
, buf
);
339 /* Undo last separator */
340 if (buf
->pos
[-1] != '[')
343 buffer_puts(buf
, "]");