Annotation of embedaddon/bird2/filter/trie.c, revision 1.1
1.1 ! misho 1: /*
! 2: * Filters: Trie for prefix sets
! 3: *
! 4: * Copyright 2009 Ondrej Zajicek <santiago@crfreenet.org>
! 5: *
! 6: * Can be freely distributed and used under the terms of the GNU GPL.
! 7: */
! 8:
! 9: /**
! 10: * DOC: Trie for prefix sets
! 11: *
! 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.
! 21: *
! 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.
! 28: *
! 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.
! 37: *
! 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.
! 46: *
! 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.
! 52: *
! 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.
! 59: *
! 60: * There are four cases when we walk through a trie:
! 61: *
! 62: * - we are in NULL
! 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)
! 67: *
! 68: * The walking code in trie_match_prefix() is structured according to
! 69: * these cases.
! 70: */
! 71:
! 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"
! 77:
! 78:
! 79: /*
! 80: * In the trie code, the prefix length is internally treated as for the whole
! 81: * ip_addr, regardless whether it contains an IPv4 or IPv6 address. Therefore,
! 82: * remaining definitions make sense.
! 83: */
! 84:
! 85: #define ipa_mkmask(x) ip6_mkmask(x)
! 86: #define ipa_masklen(x) ip6_masklen(&x)
! 87: #define ipa_pxlen(x,y) ip6_pxlen(x,y)
! 88: #define ipa_getbit(x,n) ip6_getbit(x,n)
! 89:
! 90:
! 91: /**
! 92: * f_new_trie - allocates and returns a new empty trie
! 93: * @lp: linear pool to allocate items from
! 94: * @node_size: node size to be used (&f_trie_node and user data)
! 95: */
! 96: struct f_trie *
! 97: f_new_trie(linpool *lp, uint node_size)
! 98: {
! 99: struct f_trie * ret;
! 100: ret = lp_allocz(lp, sizeof(struct f_trie) + node_size);
! 101: ret->lp = lp;
! 102: ret->node_size = node_size;
! 103: return ret;
! 104: }
! 105:
! 106: static inline struct f_trie_node *
! 107: new_node(struct f_trie *t, int plen, ip_addr paddr, ip_addr pmask, ip_addr amask)
! 108: {
! 109: struct f_trie_node *n = lp_allocz(t->lp, t->node_size);
! 110: n->plen = plen;
! 111: n->addr = paddr;
! 112: n->mask = pmask;
! 113: n->accept = amask;
! 114: return n;
! 115: }
! 116:
! 117: static inline void
! 118: attach_node(struct f_trie_node *parent, struct f_trie_node *child)
! 119: {
! 120: parent->c[ipa_getbit(child->addr, parent->plen) ? 1 : 0] = child;
! 121: }
! 122:
! 123: /**
! 124: * trie_add_prefix
! 125: * @t: trie to add to
! 126: * @net: IP network prefix
! 127: * @l: prefix lower bound
! 128: * @h: prefix upper bound
! 129: *
! 130: * Adds prefix (prefix pattern) @n to trie @t. @l and @h are lower
! 131: * and upper bounds on accepted prefix lengths, both inclusive.
! 132: * 0 <= l, h <= 32 (128 for IPv6).
! 133: *
! 134: * Returns a pointer to the allocated node. The function can return a pointer to
! 135: * an existing node if @px and @plen are the same. If px/plen == 0/0 (or ::/0),
! 136: * a pointer to the root node is returned.
! 137: */
! 138:
! 139: void *
! 140: trie_add_prefix(struct f_trie *t, const net_addr *net, uint l, uint h)
! 141: {
! 142: ip_addr px = net_prefix(net);
! 143: uint plen = net_pxlen(net);
! 144:
! 145: if (net->type == NET_IP4)
! 146: {
! 147: const uint delta = IP6_MAX_PREFIX_LENGTH - IP4_MAX_PREFIX_LENGTH;
! 148: plen += delta;
! 149: l += delta;
! 150: h += delta;
! 151: }
! 152:
! 153: if (l == 0)
! 154: t->zero = 1;
! 155: else
! 156: l--;
! 157:
! 158: if (h < plen)
! 159: plen = h;
! 160:
! 161: ip_addr amask = ipa_xor(ipa_mkmask(l), ipa_mkmask(h));
! 162: ip_addr pmask = ipa_mkmask(plen);
! 163: ip_addr paddr = ipa_and(px, pmask);
! 164: struct f_trie_node *o = NULL;
! 165: struct f_trie_node *n = t->root;
! 166:
! 167: while (n)
! 168: {
! 169: ip_addr cmask = ipa_and(n->mask, pmask);
! 170:
! 171: if (ipa_compare(ipa_and(paddr, cmask), ipa_and(n->addr, cmask)))
! 172: {
! 173: /* We are out of path - we have to add branching node 'b'
! 174: between node 'o' and node 'n', and attach new node 'a'
! 175: as the other child of 'b'. */
! 176: int blen = ipa_pxlen(paddr, n->addr);
! 177: ip_addr bmask = ipa_mkmask(blen);
! 178: ip_addr baddr = ipa_and(px, bmask);
! 179:
! 180: /* Merge accept masks from children to get accept mask for node 'b' */
! 181: ip_addr baccm = ipa_and(ipa_or(amask, n->accept), bmask);
! 182:
! 183: struct f_trie_node *a = new_node(t, plen, paddr, pmask, amask);
! 184: struct f_trie_node *b = new_node(t, blen, baddr, bmask, baccm);
! 185: attach_node(o, b);
! 186: attach_node(b, n);
! 187: attach_node(b, a);
! 188: return a;
! 189: }
! 190:
! 191: if (plen < n->plen)
! 192: {
! 193: /* We add new node 'a' between node 'o' and node 'n' */
! 194: amask = ipa_or(amask, ipa_and(n->accept, pmask));
! 195: struct f_trie_node *a = new_node(t, plen, paddr, pmask, amask);
! 196: attach_node(o, a);
! 197: attach_node(a, n);
! 198: return a;
! 199: }
! 200:
! 201: if (plen == n->plen)
! 202: {
! 203: /* We already found added node in trie. Just update accept mask */
! 204: n->accept = ipa_or(n->accept, amask);
! 205: return n;
! 206: }
! 207:
! 208: /* Update accept mask part M2 and go deeper */
! 209: n->accept = ipa_or(n->accept, ipa_and(amask, n->mask));
! 210:
! 211: /* n->plen < plen and plen <= 32 (128) */
! 212: o = n;
! 213: n = n->c[ipa_getbit(paddr, n->plen) ? 1 : 0];
! 214: }
! 215:
! 216: /* We add new tail node 'a' after node 'o' */
! 217: struct f_trie_node *a = new_node(t, plen, paddr, pmask, amask);
! 218: attach_node(o, a);
! 219:
! 220: return a;
! 221: }
! 222:
! 223: static int
! 224: trie_match_prefix(const struct f_trie *t, ip_addr px, uint plen)
! 225: {
! 226: ip_addr pmask = ipa_mkmask(plen);
! 227: ip_addr paddr = ipa_and(px, pmask);
! 228:
! 229: if (plen == 0)
! 230: return t->zero;
! 231:
! 232: int plentest = plen - 1;
! 233: const struct f_trie_node *n = t->root;
! 234:
! 235: while(n)
! 236: {
! 237: ip_addr cmask = ipa_and(n->mask, pmask);
! 238:
! 239: /* We are out of path */
! 240: if (ipa_compare(ipa_and(paddr, cmask), ipa_and(n->addr, cmask)))
! 241: return 0;
! 242:
! 243: /* Check accept mask */
! 244: if (ipa_getbit(n->accept, plentest))
! 245: return 1;
! 246:
! 247: /* We finished trie walk and still no match */
! 248: if (plen <= n->plen)
! 249: return 0;
! 250:
! 251: /* Choose children */
! 252: n = n->c[(ipa_getbit(paddr, n->plen)) ? 1 : 0];
! 253: }
! 254:
! 255: return 0;
! 256: }
! 257:
! 258: /**
! 259: * trie_match_net
! 260: * @t: trie
! 261: * @n: net address
! 262: *
! 263: * Tries to find a matching net in the trie such that
! 264: * prefix @n matches that prefix pattern. Returns 1 if there
! 265: * is such prefix pattern in the trie.
! 266: */
! 267: int
! 268: trie_match_net(const struct f_trie *t, const net_addr *n)
! 269: {
! 270: uint add = 0;
! 271:
! 272: switch (n->type) {
! 273: case NET_IP4:
! 274: case NET_VPN4:
! 275: case NET_ROA4:
! 276: add = IP6_MAX_PREFIX_LENGTH - IP4_MAX_PREFIX_LENGTH;
! 277: }
! 278:
! 279: return trie_match_prefix(t, net_prefix(n), net_pxlen(n) + add);
! 280: }
! 281:
! 282: static int
! 283: trie_node_same(const struct f_trie_node *t1, const struct f_trie_node *t2)
! 284: {
! 285: if ((t1 == NULL) && (t2 == NULL))
! 286: return 1;
! 287:
! 288: if ((t1 == NULL) || (t2 == NULL))
! 289: return 0;
! 290:
! 291: if ((t1->plen != t2->plen) ||
! 292: (! ipa_equal(t1->addr, t2->addr)) ||
! 293: (! ipa_equal(t1->accept, t2->accept)))
! 294: return 0;
! 295:
! 296: return trie_node_same(t1->c[0], t2->c[0]) && trie_node_same(t1->c[1], t2->c[1]);
! 297: }
! 298:
! 299: /**
! 300: * trie_same
! 301: * @t1: first trie to be compared
! 302: * @t2: second one
! 303: *
! 304: * Compares two tries and returns 1 if they are same
! 305: */
! 306: int
! 307: trie_same(const struct f_trie *t1, const struct f_trie *t2)
! 308: {
! 309: return (t1->zero == t2->zero) && trie_node_same(t1->root, t2->root);
! 310: }
! 311:
! 312: static void
! 313: trie_node_format(const struct f_trie_node *t, buffer *buf)
! 314: {
! 315: if (t == NULL)
! 316: return;
! 317:
! 318: if (ipa_nonzero(t->accept))
! 319: buffer_print(buf, "%I/%d{%I}, ", t->addr, t->plen, t->accept);
! 320:
! 321: trie_node_format(t->c[0], buf);
! 322: trie_node_format(t->c[1], buf);
! 323: }
! 324:
! 325: /**
! 326: * trie_format
! 327: * @t: trie to be formatted
! 328: * @buf: destination buffer
! 329: *
! 330: * Prints the trie to the supplied buffer.
! 331: */
! 332: void
! 333: trie_format(const struct f_trie *t, buffer *buf)
! 334: {
! 335: buffer_puts(buf, "[");
! 336:
! 337: if (t->zero)
! 338: buffer_print(buf, "%I/%d, ", IPA_NONE, 0);
! 339: trie_node_format(t->root, buf);
! 340:
! 341: if (buf->pos == buf->end)
! 342: return;
! 343:
! 344: /* Undo last separator */
! 345: if (buf->pos[-1] != '[')
! 346: buf->pos -= 2;
! 347:
! 348: buffer_puts(buf, "]");
! 349: }
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to trie.c CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / bird2 / filter