]>
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"
76 #include "filter/data.h"
80 * In the trie_add_prefix(), we use ip_addr (assuming that it is the same as
81 * ip6_addr) to handle both IPv4 and IPv6 prefixes. In contrast to rest of the
82 * BIRD, IPv4 addresses are just zero-padded from right. That is why we have
83 * ipt_from_ip4() and ipt_to_ip4() macros below.
86 #define ipa_mkmask(x) ip6_mkmask(x)
87 #define ipa_masklen(x) ip6_masklen(&x)
88 #define ipa_pxlen(x,y) ip6_pxlen(x,y)
89 #define ipa_getbit(x,n) ip6_getbit(x,n)
91 #define ipt_from_ip4(x) _MI6(_I(x), 0, 0, 0)
92 #define ipt_to_ip4(x) _MI4(_I0(x))
96 * f_new_trie - allocates and returns a new empty trie
97 * @lp: linear pool to allocate items from
98 * @data_size: user data attached to node
101 f_new_trie(linpool
*lp
, uint data_size
)
104 ret
= lp_allocz(lp
, sizeof(struct f_trie
) + data_size
);
107 ret
->data_size
= data_size
;
111 static inline struct f_trie_node4
*
112 new_node4(struct f_trie
*t
, int plen
, ip4_addr paddr
, ip4_addr pmask
, ip4_addr amask
)
114 struct f_trie_node4
*n
= lp_allocz(t
->lp
, sizeof(struct f_trie_node4
) + t
->data_size
);
122 static inline struct f_trie_node6
*
123 new_node6(struct f_trie
*t
, int plen
, ip6_addr paddr
, ip6_addr pmask
, ip6_addr amask
)
125 struct f_trie_node6
*n
= lp_allocz(t
->lp
, sizeof(struct f_trie_node6
) + t
->data_size
);
133 static inline struct f_trie_node
*
134 new_node(struct f_trie
*t
, int plen
, ip_addr paddr
, ip_addr pmask
, ip_addr amask
)
137 return (struct f_trie_node
*) new_node4(t
, plen
, ipt_to_ip4(paddr
), ipt_to_ip4(pmask
), ipt_to_ip4(amask
));
139 return (struct f_trie_node
*) new_node6(t
, plen
, ipa_to_ip6(paddr
), ipa_to_ip6(pmask
), ipa_to_ip6(amask
));
143 attach_node4(struct f_trie_node4
*parent
, struct f_trie_node4
*child
)
145 parent
->c
[ip4_getbit(child
->addr
, parent
->plen
) ? 1 : 0] = child
;
149 attach_node6(struct f_trie_node6
*parent
, struct f_trie_node6
*child
)
151 parent
->c
[ip6_getbit(child
->addr
, parent
->plen
) ? 1 : 0] = child
;
155 attach_node(struct f_trie_node
*parent
, struct f_trie_node
*child
, int v4
)
158 attach_node4(&parent
->v4
, &child
->v4
);
160 attach_node6(&parent
->v6
, &child
->v6
);
163 #define GET_ADDR(N,F,X) ((X) ? ipt_from_ip4((N)->v4.F) : ipa_from_ip6((N)->v6.F))
164 #define SET_ADDR(N,F,X,V) ({ if (X) (N)->v4.F =ipt_to_ip4(V); else (N)->v6.F =ipa_to_ip6(V); })
166 #define GET_CHILD(N,F,X,I) ((X) ? (struct f_trie_node *) (N)->v4.c[I] : (struct f_trie_node *) (N)->v6.c[I])
170 * @net: IP network prefix
171 * @l: prefix lower bound
172 * @h: prefix upper bound
174 * Adds prefix (prefix pattern) @n to trie @t. @l and @h are lower
175 * and upper bounds on accepted prefix lengths, both inclusive.
176 * 0 <= l, h <= 32 (128 for IPv6).
178 * Returns a pointer to the allocated node. The function can return a pointer to
179 * an existing node if @px and @plen are the same. If px/plen == 0/0 (or ::/0),
180 * a pointer to the root node is returned. Returns NULL when called with
181 * mismatched IPv4/IPv6 net type.
185 trie_add_prefix(struct f_trie
*t
, const net_addr
*net
, uint l
, uint h
)
187 uint plen
= net_pxlen(net
);
193 case NET_IP4
: px
= ipt_from_ip4(net4_prefix(net
)); v4
= 1; break;
194 case NET_IP6
: px
= ipa_from_ip6(net6_prefix(net
)); v4
= 0; break;
195 default: bug("invalid type");
214 ip_addr amask
= ipa_xor(ipa_mkmask(l
), ipa_mkmask(h
));
215 ip_addr pmask
= ipa_mkmask(plen
);
216 ip_addr paddr
= ipa_and(px
, pmask
);
217 struct f_trie_node
*o
= NULL
;
218 struct f_trie_node
*n
= &t
->root
;
222 ip_addr naddr
= GET_ADDR(n
, addr
, v4
);
223 ip_addr nmask
= GET_ADDR(n
, mask
, v4
);
224 ip_addr accept
= GET_ADDR(n
, accept
, v4
);
225 ip_addr cmask
= ipa_and(nmask
, pmask
);
226 uint nlen
= v4
? n
->v4
.plen
: n
->v6
.plen
;
228 if (ipa_compare(ipa_and(paddr
, cmask
), ipa_and(naddr
, cmask
)))
230 /* We are out of path - we have to add branching node 'b'
231 between node 'o' and node 'n', and attach new node 'a'
232 as the other child of 'b'. */
233 int blen
= ipa_pxlen(paddr
, naddr
);
234 ip_addr bmask
= ipa_mkmask(blen
);
235 ip_addr baddr
= ipa_and(px
, bmask
);
237 /* Merge accept masks from children to get accept mask for node 'b' */
238 ip_addr baccm
= ipa_and(ipa_or(amask
, accept
), bmask
);
240 struct f_trie_node
*a
= new_node(t
, plen
, paddr
, pmask
, amask
);
241 struct f_trie_node
*b
= new_node(t
, blen
, baddr
, bmask
, baccm
);
242 attach_node(o
, b
, v4
);
243 attach_node(b
, n
, v4
);
244 attach_node(b
, a
, v4
);
250 /* We add new node 'a' between node 'o' and node 'n' */
251 amask
= ipa_or(amask
, ipa_and(accept
, pmask
));
252 struct f_trie_node
*a
= new_node(t
, plen
, paddr
, pmask
, amask
);
253 attach_node(o
, a
, v4
);
254 attach_node(a
, n
, v4
);
260 /* We already found added node in trie. Just update accept mask */
261 accept
= ipa_or(accept
, amask
);
262 SET_ADDR(n
, accept
, v4
, accept
);
266 /* Update accept mask part M2 and go deeper */
267 accept
= ipa_or(accept
, ipa_and(amask
, nmask
));
268 SET_ADDR(n
, accept
, v4
, accept
);
270 /* n->plen < plen and plen <= 32 (128) */
272 n
= GET_CHILD(n
, c
, v4
, ipa_getbit(paddr
, nlen
) ? 1 : 0);
275 /* We add new tail node 'a' after node 'o' */
276 struct f_trie_node
*a
= new_node(t
, plen
, paddr
, pmask
, amask
);
277 attach_node(o
, a
, v4
);
283 trie_match_net4(const struct f_trie
*t
, ip4_addr px
, uint plen
)
285 ip4_addr pmask
= ip4_mkmask(plen
);
286 ip4_addr paddr
= ip4_and(px
, pmask
);
291 int plentest
= plen
- 1;
292 const struct f_trie_node4
*n
= &t
->root
.v4
;
296 ip4_addr cmask
= ip4_and(n
->mask
, pmask
);
298 /* We are out of path */
299 if (ip4_compare(ip4_and(paddr
, cmask
), ip4_and(n
->addr
, cmask
)))
302 /* Check accept mask */
303 if (ip4_getbit(n
->accept
, plentest
))
306 /* We finished trie walk and still no match */
310 /* Choose children */
311 n
= n
->c
[(ip4_getbit(paddr
, n
->plen
)) ? 1 : 0];
318 trie_match_net6(const struct f_trie
*t
, ip6_addr px
, uint plen
)
320 ip6_addr pmask
= ip6_mkmask(plen
);
321 ip6_addr paddr
= ip6_and(px
, pmask
);
326 int plentest
= plen
- 1;
327 const struct f_trie_node6
*n
= &t
->root
.v6
;
331 ip6_addr cmask
= ip6_and(n
->mask
, pmask
);
333 /* We are out of path */
334 if (ip6_compare(ip6_and(paddr
, cmask
), ip6_and(n
->addr
, cmask
)))
337 /* Check accept mask */
338 if (ip6_getbit(n
->accept
, plentest
))
341 /* We finished trie walk and still no match */
345 /* Choose children */
346 n
= n
->c
[(ip6_getbit(paddr
, n
->plen
)) ? 1 : 0];
357 * Tries to find a matching net in the trie such that
358 * prefix @n matches that prefix pattern. Returns 1 if there
359 * is such prefix pattern in the trie.
362 trie_match_net(const struct f_trie
*t
, const net_addr
*n
)
369 return t
->ipv4
? trie_match_net4(t
, net4_prefix(n
), net_pxlen(n
)) : 0;
374 return !t
->ipv4
? trie_match_net6(t
, net6_prefix(n
), net_pxlen(n
)) : 0;
382 trie_node_same4(const struct f_trie_node4
*t1
, const struct f_trie_node4
*t2
)
384 if ((t1
== NULL
) && (t2
== NULL
))
387 if ((t1
== NULL
) || (t2
== NULL
))
390 if ((t1
->plen
!= t2
->plen
) ||
391 (! ip4_equal(t1
->addr
, t2
->addr
)) ||
392 (! ip4_equal(t1
->accept
, t2
->accept
)))
395 return trie_node_same4(t1
->c
[0], t2
->c
[0]) && trie_node_same4(t1
->c
[1], t2
->c
[1]);
399 trie_node_same6(const struct f_trie_node6
*t1
, const struct f_trie_node6
*t2
)
401 if ((t1
== NULL
) && (t2
== NULL
))
404 if ((t1
== NULL
) || (t2
== NULL
))
407 if ((t1
->plen
!= t2
->plen
) ||
408 (! ip6_equal(t1
->addr
, t2
->addr
)) ||
409 (! ip6_equal(t1
->accept
, t2
->accept
)))
412 return trie_node_same6(t1
->c
[0], t2
->c
[0]) && trie_node_same6(t1
->c
[1], t2
->c
[1]);
417 * @t1: first trie to be compared
420 * Compares two tries and returns 1 if they are same
423 trie_same(const struct f_trie
*t1
, const struct f_trie
*t2
)
425 if ((t1
->zero
!= t2
->zero
) || (t1
->ipv4
!= t2
->ipv4
))
429 return trie_node_same4(&t1
->root
.v4
, &t2
->root
.v4
);
431 return trie_node_same6(&t1
->root
.v6
, &t2
->root
.v6
);
435 trie_node_format4(const struct f_trie_node4
*t
, buffer
*buf
)
440 if (ip4_nonzero(t
->accept
))
441 buffer_print(buf
, "%I4/%d{%I4}, ", t
->addr
, t
->plen
, t
->accept
);
443 trie_node_format4(t
->c
[0], buf
);
444 trie_node_format4(t
->c
[1], buf
);
448 trie_node_format6(const struct f_trie_node6
*t
, buffer
*buf
)
453 if (ip6_nonzero(t
->accept
))
454 buffer_print(buf
, "%I6/%d{%I6}, ", t
->addr
, t
->plen
, t
->accept
);
456 trie_node_format6(t
->c
[0], buf
);
457 trie_node_format6(t
->c
[1], buf
);
462 * @t: trie to be formatted
463 * @buf: destination buffer
465 * Prints the trie to the supplied buffer.
468 trie_format(const struct f_trie
*t
, buffer
*buf
)
470 buffer_puts(buf
, "[");
473 buffer_print(buf
, "%I/%d, ", t
->ipv4
? IPA_NONE4
: IPA_NONE6
, 0);
476 trie_node_format4(&t
->root
.v4
, buf
);
478 trie_node_format6(&t
->root
.v6
, buf
);
480 if (buf
->pos
== buf
->end
)
483 /* Undo last separator */
484 if (buf
->pos
[-1] != '[')
487 buffer_puts(buf
, "]");