]>
git.ipfire.org Git - thirdparty/bird.git/blob - filter/trie.c
2 * Filters: Trie for prefix sets
4 * (c) 2009--2021 Ondrej Zajicek <santiago@crfreenet.org>
5 * (c) 2009--2021 CZ.NIC z.s.p.o.
7 * Can be freely distributed and used under the terms of the GNU GPL.
11 * DOC: Trie for prefix sets
13 * We use a (compressed) trie to represent prefix sets. Every node in the trie
14 * represents one prefix (&addr/&plen) and &plen also indicates the index of
15 * bits in the address that are used to branch at the node. Note that such
16 * prefix is not necessary a member of the prefix set, it is just a canonical
17 * prefix associated with a node. Prefix lengths of nodes are aligned to
18 * multiples of &TRIE_STEP (4) and there is 16-way branching in each
19 * node. Therefore, we say that a node is associated with a range of prefix
20 * lengths (&plen .. &plen + TRIE_STEP - 1).
22 * The prefix set is not just a set of prefixes, it is defined by a set of
23 * prefix patterns. Each prefix pattern consists of &ppaddr/&pplen and two
24 * integers: &low and &high. The tested prefix &paddr/&plen matches that pattern
25 * if the first MIN(&plen, &pplen) bits of &paddr and &ppaddr are the same and
26 * &low <= &plen <= &high.
28 * There are two ways to represent accepted prefixes for a node. First, there is
29 * a bitmask &local, which represents independently all 15 prefixes that extend
30 * the canonical prefix of the node and are within a range of prefix lengths
31 * associated with the node. E.g., for node 10.0.0.0/8 they are 10.0.0.0/8,
32 * 10.0.0.0/9, 10.128.0.0/9, .. 10.224.0.0/11. This order (first by length, then
33 * lexicographically) is used for indexing the bitmask &local, starting at
34 * position 1. I.e., index is 2^(plen - base) + offset within the same length,
35 * see function trie_local_mask6() for details.
37 * Second, we use a bitmask &accept to represent accepted prefix lengths at a
38 * node. The bit is set means that all prefixes of given length that are either
39 * subprefixes or superprefixes of the canonical prefix are accepted. As there
40 * are 33 prefix lengths (0..32 for IPv4), but there is just one prefix of zero
41 * length in the whole trie so we have &zero flag in &f_trie (indicating whether
42 * the trie accepts prefix 0.0.0.0/0) as a special case, and &accept bitmask
43 * represents accepted prefix lengths from 1 to 32.
45 * One complication is handling of prefix patterns with unaligned prefix length.
46 * When such pattern is to be added, we add a primary node above (with rounded
47 * down prefix length &nlen) and a set of secondary nodes below (with rounded up
48 * prefix lengths &slen). Accepted prefix lengths of the original prefix pattern
49 * are then represented in different places based on their lengths. For prefixes
50 * shorter than &nlen, it is &accept bitmask of the primary node, for prefixes
51 * between &nlen and &slen - 1 it is &local bitmask of the primary node, and for
52 * prefixes longer of equal &slen it is &accept bitmasks of secondary nodes.
54 * There are two cases in prefix matching - a match when the length of the
55 * prefix is smaller that the length of the prefix pattern, (&plen < &pplen) and
56 * otherwise. The second case is simple - we just walk through the trie and look
57 * at every visited node whether that prefix accepts our prefix length (&plen).
58 * The first case is tricky - we do not want to examine every descendant of a
59 * final node, so (when we create the trie) we have to propagate that
60 * information from nodes to their ascendants.
62 * There are two kinds of propagations - propagation from child's &accept
63 * bitmask to parent's &accept bitmask, and propagation from child's &accept
64 * bitmask to parent's &local bitmask. The first kind is simple - as all
65 * superprefixes of a parent are also all superprefixes of appropriate length of
66 * a child, then we can just add (by bitwise or) a child &accept mask masked by
67 * parent prefix length mask to the parent &accept mask. This handles prefixes
68 * shorter than node &plen.
70 * The second kind of propagation is necessary to handle superprefixes of a
71 * child that are represented by parent &local mask - that are in the range of
72 * prefix lengths associated with the parent. For each accepted (by child
73 * &accept mask) prefix length from that range, we need to set appropriate bit
74 * in &local mask. See function trie_amask_to_local() for details.
76 * There are four cases when we walk through a trie:
79 * - we are out of path (prefixes are inconsistent)
80 * - we are in the wanted (final) node (node length == &plen)
81 * - we are beyond the end of path (node length > &plen)
82 * - we are still on path and keep walking (node length < &plen)
84 * The walking code in trie_match_net() is structured according to these cases.
86 * Iteration over prefixes in a trie can be done using TRIE_WALK() macro, or
87 * directly using trie_walk_init() and trie_walk_next() functions. The second
88 * approach allows suspending the iteration and continuing in it later.
89 * Prefixes are enumerated in the usual lexicographic order and may be
90 * restricted to a subset of the trie (all subnets of a specified prefix).
92 * Note that the trie walk does not reliably enumerate `implicit' prefixes
93 * defined by &low and &high fields in prefix patterns, it is supposed to be
94 * used on tries constructed from `explicit' prefixes (&low == &plen == &high
95 * in call to trie_add_prefix()).
97 * The trie walk has three basic state variables stored in the struct
98 * &f_trie_walk_state -- the current node in &stack[stack_pos], &accept_length
99 * for iteration over inter-node prefixes (non-branching prefixes on compressed
100 * path between the current node and its parent node, stored in the bitmap
101 * &accept of the current node) and &local_pos for iteration over intra-node
102 * prefixes (stored in the bitmap &local).
104 * The trie also supports longest-prefix-match query by trie_match_longest_ip4()
105 * and it can be extended to iteration over all covering prefixes for a given
106 * prefix (from longest to shortest) using TRIE_WALK_TO_ROOT_IP4() macro. There
107 * are also IPv6 versions (for practical reasons, these functions and macros are
108 * separate for IPv4 and IPv6). There is the same limitation to enumeration of
109 * `implicit' prefixes like with the previous TRIE_WALK() macro.
112 #include "nest/bird.h"
113 #include "lib/string.h"
114 #include "conf/conf.h"
115 #include "filter/filter.h"
116 #include "filter/data.h"
120 * In the trie_add_prefix(), we use ip_addr (assuming that it is the same as
121 * ip6_addr) to handle both IPv4 and IPv6 prefixes. In contrast to rest of the
122 * BIRD, IPv4 addresses are just zero-padded from right. That is why we have
123 * ipt_from_ip4() and ipt_to_ip4() macros below.
126 #define ipa_mkmask(x) ip6_mkmask(x)
127 #define ipa_masklen(x) ip6_masklen(&x)
128 #define ipa_pxlen(x,y) ip6_pxlen(x,y)
129 #define ipa_getbit(a,p) ip6_getbit(a,p)
130 #define ipa_getbits(a,p,n) ip6_getbits(a,p,n)
131 #define ipa_setbits(a,p,n) ip6_setbits(a,p,n)
132 #define trie_local_mask(a,b,c) trie_local_mask6(a,b,c)
134 #define ipt_from_ip4(x) _MI6(_I(x), 0, 0, 0)
135 #define ipt_to_ip4(x) _MI4(_I0(x))
139 * f_new_trie - allocates and returns a new empty trie
140 * @lp: linear pool to allocate items from
141 * @data_size: user data attached to node
144 f_new_trie(linpool
*lp
, uint data_size
)
147 ret
= lp_allocz(lp
, sizeof(struct f_trie
) + data_size
);
150 ret
->data_size
= data_size
;
154 static inline struct f_trie_node4
*
155 new_node4(struct f_trie
*t
, uint plen
, uint local
, ip4_addr paddr
, ip4_addr pmask
, ip4_addr amask
)
157 struct f_trie_node4
*n
= lp_allocz(t
->lp
, sizeof(struct f_trie_node4
) + t
->data_size
);
166 static inline struct f_trie_node6
*
167 new_node6(struct f_trie
*t
, uint plen
, uint local
, ip6_addr paddr
, ip6_addr pmask
, ip6_addr amask
)
169 struct f_trie_node6
*n
= lp_allocz(t
->lp
, sizeof(struct f_trie_node6
) + t
->data_size
);
178 static inline struct f_trie_node
*
179 new_node(struct f_trie
*t
, uint plen
, uint local
, ip_addr paddr
, ip_addr pmask
, ip_addr amask
)
182 return (struct f_trie_node
*) new_node4(t
, plen
, local
, ipt_to_ip4(paddr
), ipt_to_ip4(pmask
), ipt_to_ip4(amask
));
184 return (struct f_trie_node
*) new_node6(t
, plen
, local
, ipa_to_ip6(paddr
), ipa_to_ip6(pmask
), ipa_to_ip6(amask
));
188 attach_node4(struct f_trie_node4
*parent
, struct f_trie_node4
*child
)
190 parent
->c
[ip4_getbits(child
->addr
, parent
->plen
, TRIE_STEP
)] = child
;
194 attach_node6(struct f_trie_node6
*parent
, struct f_trie_node6
*child
)
196 parent
->c
[ip6_getbits(child
->addr
, parent
->plen
, TRIE_STEP
)] = child
;
200 attach_node(struct f_trie_node
*parent
, struct f_trie_node
*child
, int v4
)
203 attach_node4(&parent
->v4
, &child
->v4
);
205 attach_node6(&parent
->v6
, &child
->v6
);
210 * Internal prefixes of a node a represented by the local bitmask, each bit for
211 * one prefix. Bit 0 is unused, Bit 1 is for the main prefix of the node,
212 * remaining bits correspond to subprefixes by this pattern:
219 * E.g. for 10.0.0.0/8 node, the 10.64.0.0/10 would be position 5.
223 * Compute appropriate mask representing prefix px/plen in local bitmask of node
224 * with prefix length nlen. Assuming that nlen <= plen < (nlen + TRIE_STEP).
227 trie_local_mask4(ip4_addr px
, uint plen
, uint nlen
)
229 uint step
= plen
- nlen
;
230 uint pos
= (1u << step
) + ip4_getbits(px
, nlen
, step
);
235 trie_local_mask6(ip6_addr px
, uint plen
, uint nlen
)
237 uint step
= plen
- nlen
;
238 uint pos
= (1u << step
) + ip6_getbits(px
, nlen
, step
);
243 * Compute an appropriate local mask (for a node with prefix length nlen)
244 * representing prefixes of px that are accepted by amask and fall within the
245 * range associated with that node. Used for propagation of child accept mask
246 * to parent local mask.
249 trie_amask_to_local(ip_addr px
, ip_addr amask
, uint nlen
)
253 for (uint plen
= MAX(nlen
, 1); plen
< (nlen
+ TRIE_STEP
); plen
++)
254 if (ipa_getbit(amask
, plen
- 1))
255 local
|= trie_local_mask(px
, plen
, nlen
);
261 * Compute a bitmask representing a level of subprefixes (of the same length),
262 * using specified position as a root. E.g., level 2 from root position 3 would
263 * be bit positions C-F, returned as bitmask 0xf000.
266 trie_level_mask(uint pos
, uint level
)
268 return ((1u << (1u << level
)) - 1) << (pos
<< level
);
272 #define GET_ADDR(N,F,X) ((X) ? ipt_from_ip4((N)->v4.F) : ipa_from_ip6((N)->v6.F))
273 #define SET_ADDR(N,F,X,V) ({ if (X) (N)->v4.F =ipt_to_ip4(V); else (N)->v6.F =ipa_to_ip6(V); })
275 #define GET_LOCAL(N,X) ((X) ? (N)->v4.local : (N)->v6.local)
276 #define ADD_LOCAL(N,X,V) ({ uint v_ = (V); if (X) (N)->v4.local |= v_; else (N)->v6.local |= v_; })
278 #define GET_CHILD(N,X,I) ((X) ? (struct f_trie_node *) (N)->v4.c[I] : (struct f_trie_node *) (N)->v6.c[I])
282 trie_add_node(struct f_trie
*t
, uint plen
, ip_addr px
, uint local
, uint l
, uint h
)
284 uint l_
= l
? (l
- 1) : 0;
285 ip_addr amask
= (l_
< h
) ? ipa_xor(ipa_mkmask(l_
), ipa_mkmask(h
)) : IPA_NONE
;
286 ip_addr pmask
= ipa_mkmask(plen
);
287 ip_addr paddr
= ipa_and(px
, pmask
);
288 struct f_trie_node
*o
= NULL
;
289 struct f_trie_node
*n
= &t
->root
;
292 /* Add all bits for each active level (0x0002 0x000c 0x00f0 0xff00) */
293 for (uint i
= 0; i
< TRIE_STEP
; i
++)
294 if ((l
<= (plen
+ i
)) && ((plen
+ i
) <= h
))
295 local
|= trie_level_mask(1, i
);
297 DBG("Insert node %I/%u (%I %x)\n", paddr
, plen
, amask
, local
);
300 ip_addr naddr
= GET_ADDR(n
, addr
, v4
);
301 ip_addr nmask
= GET_ADDR(n
, mask
, v4
);
302 ip_addr accept
= GET_ADDR(n
, accept
, v4
);
303 ip_addr cmask
= ipa_and(nmask
, pmask
);
304 uint nlen
= v4
? n
->v4
.plen
: n
->v6
.plen
;
306 DBG("Found node %I/%u (%I %x)\n",
307 naddr
, nlen
, accept
, v4
? n
->v4
.local
: n
->v6
.local
);
309 if (ipa_compare(ipa_and(paddr
, cmask
), ipa_and(naddr
, cmask
)))
311 /* We are out of path - we have to add branching node 'b'
312 between node 'o' and node 'n', and attach new node 'a'
313 as the other child of 'b'. */
314 int blen
= ROUND_DOWN_POW2(ipa_pxlen(paddr
, naddr
), TRIE_STEP
);
315 ip_addr bmask
= ipa_mkmask(blen
);
316 ip_addr baddr
= ipa_and(px
, bmask
);
318 /* Merge accept masks from children to get accept mask for node 'b' */
319 ip_addr baccm
= ipa_and(ipa_or(amask
, accept
), bmask
);
320 uint bloc
= trie_amask_to_local(naddr
, accept
, blen
) |
321 trie_amask_to_local(paddr
, amask
, blen
);
323 struct f_trie_node
*a
= new_node(t
, plen
, local
, paddr
, pmask
, amask
);
324 struct f_trie_node
*b
= new_node(t
, blen
, bloc
, baddr
, bmask
, baccm
);
325 attach_node(o
, b
, v4
);
326 attach_node(b
, n
, v4
);
327 attach_node(b
, a
, v4
);
336 /* We add new node 'a' between node 'o' and node 'n' */
337 amask
= ipa_or(amask
, ipa_and(accept
, pmask
));
338 local
|= trie_amask_to_local(naddr
, accept
, plen
);
339 struct f_trie_node
*a
= new_node(t
, plen
, local
, paddr
, pmask
, amask
);
340 attach_node(o
, a
, v4
);
341 attach_node(a
, n
, v4
);
350 /* We already found added node in trie. Just update accept and local mask */
351 accept
= ipa_or(accept
, amask
);
352 SET_ADDR(n
, accept
, v4
, accept
);
354 if ((GET_LOCAL(n
, v4
) & local
) != local
)
357 ADD_LOCAL(n
, v4
, local
);
363 /* Update accept mask part M2 and go deeper */
364 accept
= ipa_or(accept
, ipa_and(amask
, nmask
));
365 SET_ADDR(n
, accept
, v4
, accept
);
366 ADD_LOCAL(n
, v4
, trie_amask_to_local(paddr
, amask
, nlen
));
368 DBG("Step %u\n", ipa_getbits(paddr
, nlen
));
370 /* n->plen < plen and plen <= 32 (128) */
372 n
= GET_CHILD(n
, v4
, ipa_getbits(paddr
, nlen
, TRIE_STEP
));
375 /* We add new tail node 'a' after node 'o' */
376 struct f_trie_node
*a
= new_node(t
, plen
, local
, paddr
, pmask
, amask
);
377 attach_node(o
, a
, v4
);
387 * @net: IP network prefix
388 * @l: prefix lower bound
389 * @h: prefix upper bound
391 * Adds prefix (prefix pattern) @n to trie @t. @l and @h are lower
392 * and upper bounds on accepted prefix lengths, both inclusive.
393 * 0 <= l, h <= 32 (128 for IPv6).
395 * Returns a pointer to the allocated node. The function can return a pointer to
396 * an existing node if @px and @plen are the same. If px/plen == 0/0 (or ::/0),
397 * a pointer to the root node is returned. Returns NULL when called with
398 * mismatched IPv4/IPv6 net type.
401 trie_add_prefix(struct f_trie
*t
, const net_addr
*net
, uint l
, uint h
)
403 uint plen
= net_pxlen(net
);
412 px
= ipt_from_ip4(net4_prefix(net
));
420 px
= ipa_from_ip6(net6_prefix(net
));
436 DBG("\nInsert net %N (%u-%u)\n", net
, l
, h
);
444 /* Primary node length, plen rounded down */
445 uint nlen
= ROUND_DOWN_POW2(plen
, TRIE_STEP
);
448 return trie_add_node(t
, nlen
, px
, 0, l
, h
);
450 /* Secondary node length, plen rouned up */
451 uint slen
= nlen
+ TRIE_STEP
;
455 * For unaligned prefix lengths it is more complicated. We need to encode
456 * matching prefixes of lengths from l to h. There are three cases of lengths:
458 * 1) 0..nlen are encoded by the accept mask of the primary node
459 * 2) nlen..(slen-1) are encoded by the local mask of the primary node
460 * 3) slen..max are encoded in secondary nodes
467 /* Compute local bits for accepted nlen..(slen-1) prefixes */
468 for (uint i
= 0; i
< TRIE_STEP
; i
++)
469 if ((l
<= (nlen
+ i
)) && ((nlen
+ i
) <= h
))
471 uint pos
= (1u << i
) + ipa_getbits(px
, nlen
, i
);
472 uint len
= ((nlen
+ i
) <= plen
) ? 1 : (1u << (nlen
+ i
- plen
));
474 /* We need to fill 'len' bits starting at 'pos' position */
475 local
|= ((1u << len
) - 1) << pos
;
478 /* Add the primary node */
479 node
= trie_add_node(t
, nlen
, px
, local
, l
, nlen
);
484 uint l2
= MAX(l
, slen
);
485 uint max
= (1u << (slen
- plen
));
487 /* Add secondary nodes */
488 for (uint i
= 0; i
< max
; i
++)
489 node
= trie_add_node(t
, slen
, ipa_setbits(px
, slen
- 1, i
), 0, l2
, h
);
497 trie_match_net4(const struct f_trie
*t
, ip4_addr px
, uint plen
)
502 int plentest
= plen
- 1;
503 uint nlen
= ROUND_DOWN_POW2(plen
, TRIE_STEP
);
504 uint local
= trie_local_mask4(px
, plen
, nlen
);
505 const struct f_trie_node4
*n
= &t
->root
.v4
;
509 /* We are out of path */
510 if (!ip4_prefix_equal(px
, n
->addr
, MIN(plen
, n
->plen
)))
513 /* Check local mask */
514 if ((n
->plen
== nlen
) && (n
->local
& local
))
517 /* Check accept mask */
518 if (ip4_getbit(n
->accept
, plentest
))
521 /* We finished trie walk and still no match */
525 /* Choose children */
526 n
= n
->c
[ip4_getbits(px
, n
->plen
, TRIE_STEP
)];
533 trie_match_net6(const struct f_trie
*t
, ip6_addr px
, uint plen
)
538 int plentest
= plen
- 1;
539 uint nlen
= ROUND_DOWN_POW2(plen
, TRIE_STEP
);
540 uint local
= trie_local_mask6(px
, plen
, nlen
);
541 const struct f_trie_node6
*n
= &t
->root
.v6
;
545 /* We are out of path */
546 if (!ip6_prefix_equal(px
, n
->addr
, MIN(plen
, n
->plen
)))
549 /* Check local mask */
550 if ((n
->plen
== nlen
) && (n
->local
& local
))
553 /* Check accept mask */
554 if (ip6_getbit(n
->accept
, plentest
))
557 /* We finished trie walk and still no match */
561 /* Choose children */
562 n
= n
->c
[ip6_getbits(px
, n
->plen
, TRIE_STEP
)];
573 * Tries to find a matching net in the trie such that
574 * prefix @n matches that prefix pattern. Returns 1 if there
575 * is such prefix pattern in the trie.
578 trie_match_net(const struct f_trie
*t
, const net_addr
*n
)
585 return t
->ipv4
? trie_match_net4(t
, net4_prefix(n
), net_pxlen(n
)) : 0;
590 return !t
->ipv4
? trie_match_net6(t
, net6_prefix(n
), net_pxlen(n
)) : 0;
599 * trie_match_longest_ip4
603 * @found0: optional returned bitmask of found nodes
605 * Perform longest prefix match for the address @net and return the resulting
606 * prefix in the buffer @dst. The bitmask @found0 is used to report lengths of
607 * prefixes on the path from the root to the resulting prefix. E.g., if there is
608 * also a /20 shorter matching prefix, then 20-th bit is set in @found0. This
609 * can be used to enumerate all matching prefixes for the network @net using
610 * function trie_match_next_longest_ip4() or macro TRIE_WALK_TO_ROOT_IP4().
612 * This function assumes IPv4 trie, there is also an IPv6 variant. The @net
613 * argument is typed as net_addr_ip4, but would accept any IPv4-based net_addr,
614 * like net4_prefix(). Anyway, returned @dst is always net_addr_ip4.
616 * Result: 1 if a matching prefix was found, 0 if not.
619 trie_match_longest_ip4(const struct f_trie
*t
, const net_addr_ip4
*net
, net_addr_ip4
*dst
, ip4_addr
*found0
)
623 const ip4_addr prefix
= net
->prefix
;
624 const int pxlen
= net
->pxlen
;
626 const struct f_trie_node4
*n
= &t
->root
.v4
;
629 ip4_addr found
= IP4_NONE
;
634 /* We are out of path */
635 if (!ip4_prefix_equal(prefix
, n
->addr
, MIN(pxlen
, n
->plen
)))
638 /* Check accept mask */
639 for (; len
< n
->plen
; len
++)
644 if (ip4_getbit(n
->accept
, len
- 1))
646 /* len is always < 32 due to len < n->plen */
647 ip4_setbit(&found
, len
);
652 /* Special case for max length, there is only one valid local position */
653 if (len
== IP4_MAX_PREFIX_LENGTH
)
655 if (n
->local
& (1u << 1))
661 /* Check local mask */
662 for (int pos
= 1; pos
< (1 << TRIE_STEP
); pos
= 2 * pos
+ ip4_getbit(prefix
, len
), len
++)
667 if (n
->local
& (1u << pos
))
669 /* len is always < 32 due to special case above */
670 ip4_setbit(&found
, len
);
676 n
= n
->c
[ip4_getbits(prefix
, n
->plen
, TRIE_STEP
)];
683 *dst
= NET_ADDR_IP4(ip4_and(prefix
, ip4_mkmask(last
)), last
);
693 * trie_match_longest_ip6
697 * @found0: optional returned bitmask of found nodes
699 * Perform longest prefix match for the address @net and return the resulting
700 * prefix in the buffer @dst. The bitmask @found0 is used to report lengths of
701 * prefixes on the path from the root to the resulting prefix. E.g., if there is
702 * also a /20 shorter matching prefix, then 20-th bit is set in @found0. This
703 * can be used to enumerate all matching prefixes for the network @net using
704 * function trie_match_next_longest_ip6() or macro TRIE_WALK_TO_ROOT_IP6().
706 * This function assumes IPv6 trie, there is also an IPv4 variant. The @net
707 * argument is typed as net_addr_ip6, but would accept any IPv6-based net_addr,
708 * like net6_prefix(). Anyway, returned @dst is always net_addr_ip6.
710 * Result: 1 if a matching prefix was found, 0 if not.
713 trie_match_longest_ip6(const struct f_trie
*t
, const net_addr_ip6
*net
, net_addr_ip6
*dst
, ip6_addr
*found0
)
717 const ip6_addr prefix
= net
->prefix
;
718 const int pxlen
= net
->pxlen
;
720 const struct f_trie_node6
*n
= &t
->root
.v6
;
723 ip6_addr found
= IP6_NONE
;
728 /* We are out of path */
729 if (!ip6_prefix_equal(prefix
, n
->addr
, MIN(pxlen
, n
->plen
)))
732 /* Check accept mask */
733 for (; len
< n
->plen
; len
++)
738 if (ip6_getbit(n
->accept
, len
- 1))
740 /* len is always < 128 due to len < n->plen */
741 ip6_setbit(&found
, len
);
746 /* Special case for max length, there is only one valid local position */
747 if (len
== IP6_MAX_PREFIX_LENGTH
)
749 if (n
->local
& (1u << 1))
755 /* Check local mask */
756 for (int pos
= 1; pos
< (1 << TRIE_STEP
); pos
= 2 * pos
+ ip6_getbit(prefix
, len
), len
++)
761 if (n
->local
& (1u << pos
))
763 /* len is always < 128 due to special case above */
764 ip6_setbit(&found
, len
);
770 n
= n
->c
[ip6_getbits(prefix
, n
->plen
, TRIE_STEP
)];
777 *dst
= NET_ADDR_IP6(ip6_and(prefix
, ip6_mkmask(last
)), last
);
785 #define SAME_PREFIX(A,B,X,L) ((X) ? ip4_prefix_equal((A)->v4.addr, net4_prefix(B), (L)) : ip6_prefix_equal((A)->v6.addr, net6_prefix(B), (L)))
786 #define GET_NET_BITS(N,X,A,B) ((X) ? ip4_getbits(net4_prefix(N), (A), (B)) : ip6_getbits(net6_prefix(N), (A), (B)))
792 * @net: optional subnet for walk
794 * Initialize walk state for subsequent walk through nodes of the trie @t by
795 * trie_walk_next(). The argument @net allows to restrict walk to given subnet,
796 * otherwise full walk over all nodes is used. This is done by finding node at
797 * or below @net and starting position in it.
800 trie_walk_init(struct f_trie_walk_state
*s
, const struct f_trie
*t
, const net_addr
*net
)
802 *s
= (struct f_trie_walk_state
) {
814 /* We want to find node of level at least plen */
815 int plen
= ROUND_DOWN_POW2(net
->pxlen
, TRIE_STEP
);
816 const struct f_trie_node
*n
= &t
->root
;
817 const int v4
= t
->ipv4
;
821 int nlen
= v4
? n
->v4
.plen
: n
->v6
.plen
;
823 /* We are out of path */
824 if (!SAME_PREFIX(n
, net
, v4
, MIN(net
->pxlen
, nlen
)))
827 /* We found final node */
832 /* Find proper local_pos, while accept_length is not used */
833 int step
= net
->pxlen
- plen
;
834 s
->start_pos
= s
->local_pos
= (1u << step
) + GET_NET_BITS(net
, v4
, plen
, step
);
835 s
->accept_length
= plen
;
839 /* Start from pos 1 in local node, but first try accept mask */
840 s
->accept_length
= net
->pxlen
;
848 n
= GET_CHILD(n
, v4
, GET_NET_BITS(net
, v4
, nlen
, TRIE_STEP
));
855 #define GET_ACCEPT_BIT(N,X,B) ((X) ? ip4_getbit((N)->v4.accept, (B)) : ip6_getbit((N)->v6.accept, (B)))
856 #define GET_LOCAL_BIT(N,X,B) (((X) ? (N)->v4.local : (N)->v6.local) & (1u << (B)))
863 * Find the next prefix in the trie walk and return it in the buffer @net.
864 * Prefixes are walked in the usual lexicographic order and may be restricted
865 * to a subset of the trie during walk setup by trie_walk_init(). Note that the
866 * trie walk does not iterate reliably over 'implicit' prefixes defined by &low
867 * and &high fields in prefix patterns, it is supposed to be used on tries
868 * constructed from 'explicit' prefixes (&low == &plen == &high in call to
869 * trie_add_prefix()).
871 * Result: 1 if the next prefix was found, 0 for the end of walk.
874 trie_walk_next(struct f_trie_walk_state
*s
, net_addr
*net
)
876 const struct f_trie_node
*n
= s
->stack
[s
->stack_pos
];
877 int len
= s
->accept_length
;
878 int pos
= s
->local_pos
;
882 * The walk has three basic state variables -- n, len and pos. In each node n,
883 * we first walk superprefixes (by len in &accept bitmask), and then we walk
884 * internal positions (by pos in &local bitmask). These positions are:
891 * We walk them depth-first, including virtual positions 10-1F that are
892 * equivalent of position 1 in child nodes 0-F.
897 memset(net
, 0, v4
? sizeof(net_addr_ip4
) : sizeof(net_addr_ip6
));
902 /* Current node prefix length */
903 int nlen
= v4
? n
->v4
.plen
: n
->v6
.plen
;
905 /* First, check for accept prefix */
906 for (; len
< nlen
; len
++)
907 if (GET_ACCEPT_BIT(n
, v4
, len
- 1))
910 net_fill_ip4(net
, ip4_and(n
->v4
.addr
, ip4_mkmask(len
)), len
);
912 net_fill_ip6(net
, ip6_and(n
->v6
.addr
, ip6_mkmask(len
)), len
);
915 s
->accept_length
= len
+ 1;
920 /* Bottom of this node */
921 if (pos
>= (1 << TRIE_STEP
))
923 const struct f_trie_node
*child
= GET_CHILD(n
, v4
, pos
- (1 << TRIE_STEP
));
929 /* Step up until return from left child (pos is even) */
932 /* Step up from start node */
933 if ((s
->stack_pos
== 0) && (pos
== s
->start_pos
))
936 memset(net
, 0, v4
? sizeof(net_addr_ip4
) : sizeof(net_addr_ip6
));
940 /* Top of this node */
943 ASSERT(s
->stack_pos
);
944 const struct f_trie_node
*old
= n
;
946 /* Move to parent node */
948 n
= s
->stack
[s
->stack_pos
];
949 nlen
= v4
? n
->v4
.plen
: n
->v6
.plen
;
952 ip4_getbits(old
->v4
.addr
, nlen
, TRIE_STEP
) :
953 ip6_getbits(old
->v6
.addr
, nlen
, TRIE_STEP
);
954 pos
+= (1 << TRIE_STEP
);
957 ASSERT(GET_CHILD(n
, v4
, pos
- (1 << TRIE_STEP
)) == old
);
966 /* Continue with step down to the right child */
971 /* Move to child node */
973 len
= nlen
+ TRIE_STEP
;
976 n
= s
->stack
[s
->stack_pos
] = child
;
980 /* Check for local prefix */
981 if (GET_LOCAL_BIT(n
, v4
, pos
))
983 /* Convert pos to address of local network */
984 int x
= (pos
>= 2) + (pos
>= 4) + (pos
>= 8);
985 int y
= pos
& ((1u << x
) - 1);
988 net_fill_ip4(net
, !x
? n
->v4
.addr
: ip4_setbits(n
->v4
.addr
, nlen
+ x
- 1, y
), nlen
+ x
);
990 net_fill_ip6(net
, !x
? n
->v6
.addr
: ip6_setbits(n
->v6
.addr
, nlen
+ x
- 1, y
), nlen
+ x
);
992 s
->local_pos
= 2 * pos
;
993 s
->accept_length
= len
;
1004 trie_node_same4(const struct f_trie_node4
*t1
, const struct f_trie_node4
*t2
)
1006 if ((t1
== NULL
) && (t2
== NULL
))
1009 if ((t1
== NULL
) || (t2
== NULL
))
1012 if ((t1
->plen
!= t2
->plen
) ||
1013 (! ip4_equal(t1
->addr
, t2
->addr
)) ||
1014 (! ip4_equal(t1
->accept
, t2
->accept
)))
1017 for (uint i
= 0; i
< (1 << TRIE_STEP
); i
++)
1018 if (! trie_node_same4(t1
->c
[i
], t2
->c
[i
]))
1025 trie_node_same6(const struct f_trie_node6
*t1
, const struct f_trie_node6
*t2
)
1027 if ((t1
== NULL
) && (t2
== NULL
))
1030 if ((t1
== NULL
) || (t2
== NULL
))
1033 if ((t1
->plen
!= t2
->plen
) ||
1034 (! ip6_equal(t1
->addr
, t2
->addr
)) ||
1035 (! ip6_equal(t1
->accept
, t2
->accept
)))
1038 for (uint i
= 0; i
< (1 << TRIE_STEP
); i
++)
1039 if (! trie_node_same6(t1
->c
[i
], t2
->c
[i
]))
1047 * @t1: first trie to be compared
1050 * Compares two tries and returns 1 if they are same
1053 trie_same(const struct f_trie
*t1
, const struct f_trie
*t2
)
1055 if ((t1
->zero
!= t2
->zero
) || (t1
->ipv4
!= t2
->ipv4
))
1059 return trie_node_same4(&t1
->root
.v4
, &t2
->root
.v4
);
1061 return trie_node_same6(&t1
->root
.v6
, &t2
->root
.v6
);
1065 static const u8 log2
[16] = {0, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3};
1068 trie_node_format(const struct f_trie_node
*n
, buffer
*buf
, int v4
)
1075 if (ip4_nonzero(n
->v4
.accept
))
1076 buffer_print(buf
, "%I4/%d{%I4}, ", n
->v4
.addr
, n
->v4
.plen
, n
->v4
.accept
);
1080 if (ip6_nonzero(n
->v6
.accept
))
1081 buffer_print(buf
, "%I6/%d{%I6}, ", n
->v6
.addr
, n
->v6
.plen
, n
->v6
.accept
);
1084 int nlen
= v4
? n
->v4
.plen
: n
->v6
.plen
;
1085 uint local
= v4
? n
->v4
.local
: n
->v6
.local
;
1087 for (int i
= (nlen
? 0 : 1); i
< TRIE_STEP
; i
++)
1088 if (GET_ACCEPT_BIT(n
, v4
, nlen
+ i
- 1))
1089 local
&= ~trie_level_mask(1, i
);
1091 for (int pos
= 2; local
&& (pos
< (1 << TRIE_STEP
)); pos
++)
1092 if (local
& (1u << pos
))
1094 int lvl
= log2
[pos
];
1095 int plen
= nlen
+ lvl
;
1098 for (i
= 0; lvl
+ i
< TRIE_STEP
; i
++)
1100 uint lmask
= trie_level_mask(pos
, i
);
1102 if ((local
& lmask
) != lmask
)
1108 uint addr_bits
= pos
& ((1u << lvl
) - 1);
1109 uint accept_bits
= (1u << i
) - 1;
1110 int h
= plen
+ i
- 1;
1114 ip4_addr addr
= ip4_setbits(n
->v4
.addr
, plen
- 1, addr_bits
);
1115 ip4_addr mask
= ip4_setbits(IP4_NONE
, h
- 1, accept_bits
);
1116 buffer_print(buf
, "%I4/%d{%I4}, ", addr
, plen
, mask
);
1120 ip6_addr addr
= ip6_setbits(n
->v6
.addr
, plen
- 1, addr_bits
);
1121 ip6_addr mask
= ip6_setbits(IP6_NONE
, h
- 1, accept_bits
);
1122 buffer_print(buf
, "%I6/%d{%I6}, ", addr
, plen
, mask
);
1126 for (int i
= 0; i
< (1 << TRIE_STEP
); i
++)
1127 trie_node_format(GET_CHILD(n
, v4
, i
), buf
, v4
);
1132 * @t: trie to be formatted
1133 * @buf: destination buffer
1135 * Prints the trie to the supplied buffer.
1138 trie_format(const struct f_trie
*t
, buffer
*buf
)
1140 buffer_puts(buf
, "[");
1143 buffer_print(buf
, "%I/%d, ", t
->ipv4
? IPA_NONE4
: IPA_NONE6
, 0);
1145 trie_node_format(&t
->root
, buf
, t
->ipv4
);
1147 if (buf
->pos
== buf
->end
)
1150 /* Undo last separator */
1151 if (buf
->pos
[-1] != '[')
1154 buffer_puts(buf
, "]");