Return to trie.c CVS log

Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / bird / filter

bird 1.6.3

    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: 
   77: /**
   78:  * f_new_trie - allocates and returns a new empty trie
   79:  * @lp: linear pool to allocate items from
   80:  * @node_size: node size to be used (&f_trie_node and user data)
   81:  */
   82: struct f_trie *
   83: f_new_trie(linpool *lp, uint node_size)
   84: {
   85:   struct f_trie * ret;
   86:   ret = lp_allocz(lp, sizeof(struct f_trie) + node_size);
   87:   ret->lp = lp;
   88:   ret->node_size = node_size;
   89:   return ret;
   90: }
   91: 
   92: static inline struct f_trie_node *
   93: new_node(struct f_trie *t, int plen, ip_addr paddr, ip_addr pmask, ip_addr amask)
   94: {
   95:   struct f_trie_node *n = lp_allocz(t->lp, t->node_size);
   96:   n->plen = plen;
   97:   n->addr = paddr;
   98:   n->mask = pmask;
   99:   n->accept = amask;
  100:   return n;
  101: }
  102: 
  103: static inline void
  104: attach_node(struct f_trie_node *parent, struct f_trie_node *child)
  105: {
  106:   parent->c[ipa_getbit(child->addr, parent->plen) ? 1 : 0] = child;
  107: }
  108: 
  109: /**
  110:  * trie_add_prefix
  111:  * @t: trie to add to
  112:  * @px: prefix address
  113:  * @plen: prefix length
  114:  * @l: prefix lower bound
  115:  * @h: prefix upper bound
  116:  *
  117:  * Adds prefix (prefix pattern) @px/@plen to trie @t.  @l and @h are lower
  118:  * and upper bounds on accepted prefix lengths, both inclusive.
  119:  * 0 <= l, h <= 32 (128 for IPv6).
  120:  *
  121:  * Returns a pointer to the allocated node. The function can return a pointer to
  122:  * an existing node if @px and @plen are the same. If px/plen == 0/0 (or ::/0),
  123:  * a pointer to the root node is returned.
  124:  */
  125: 
  126: void *
  127: trie_add_prefix(struct f_trie *t, ip_addr px, int plen, int l, int h)
  128: {
  129:   if (l == 0)
  130:     t->zero = 1;
  131:   else
  132:     l--;
  133: 
  134:   if (h < plen)
  135:     plen = h;
  136: 
  137:   ip_addr amask = ipa_xor(ipa_mkmask(l), ipa_mkmask(h));
  138:   ip_addr pmask = ipa_mkmask(plen);
  139:   ip_addr paddr = ipa_and(px, pmask);
  140:   struct f_trie_node *o = NULL;
  141:   struct f_trie_node *n = t->root;
  142: 
  143:   while(n)
  144:     {
  145:       ip_addr cmask = ipa_and(n->mask, pmask);
  146: 
  147:       if (ipa_compare(ipa_and(paddr, cmask), ipa_and(n->addr, cmask)))
  148: 	{
  149: 	  /* We are out of path - we have to add branching node 'b'
  150: 	     between node 'o' and node 'n', and attach new node 'a'
  151: 	     as the other child of 'b'. */
  152: 	  int blen = ipa_pxlen(paddr, n->addr);
  153: 	  ip_addr bmask = ipa_mkmask(blen);
  154: 	  ip_addr baddr = ipa_and(px, bmask);
  155: 
  156: 	  /* Merge accept masks from children to get accept mask for node 'b' */
  157: 	  ip_addr baccm = ipa_and(ipa_or(amask, n->accept), bmask);
  158: 
  159: 	  struct f_trie_node *a = new_node(t, plen, paddr, pmask, amask);
  160: 	  struct f_trie_node *b = new_node(t, blen, baddr, bmask, baccm);
  161: 	  attach_node(o, b);
  162: 	  attach_node(b, n);
  163: 	  attach_node(b, a);
  164: 	  return a;
  165: 	}
  166: 
  167:       if (plen < n->plen)
  168: 	{
  169: 	  /* We add new node 'a' between node 'o' and node 'n' */
  170: 	  amask = ipa_or(amask, ipa_and(n->accept, pmask));
  171: 	  struct f_trie_node *a = new_node(t, plen, paddr, pmask, amask);
  172: 	  attach_node(o, a);
  173: 	  attach_node(a, n);
  174: 	  return a;
  175: 	}
  176: 
  177:       if (plen == n->plen)
  178: 	{
  179: 	  /* We already found added node in trie. Just update accept mask */
  180: 	  n->accept = ipa_or(n->accept, amask);
  181: 	  return n;
  182: 	}
  183: 
  184:       /* Update accept mask part M2 and go deeper */
  185:       n->accept = ipa_or(n->accept, ipa_and(amask, n->mask));
  186: 
  187:       /* n->plen < plen and plen <= 32 (128) */
  188:       o = n;
  189:       n = n->c[ipa_getbit(paddr, n->plen) ? 1 : 0];
  190:     }
  191: 
  192:   /* We add new tail node 'a' after node 'o' */
  193:   struct f_trie_node *a = new_node(t, plen, paddr, pmask, amask);
  194:   attach_node(o, a);
  195: 
  196:   return a;
  197: }
  198: 
  199: /**
  200:  * trie_match_prefix
  201:  * @t: trie
  202:  * @px: prefix address
  203:  * @plen: prefix length
  204:  *
  205:  * Tries to find a matching prefix pattern in the trie such that
  206:  * prefix @px/@plen matches that prefix pattern. Returns 1 if there
  207:  * is such prefix pattern in the trie.
  208:  */
  209: int
  210: trie_match_prefix(struct f_trie *t, ip_addr px, int plen)
  211: {
  212:   ip_addr pmask = ipa_mkmask(plen);
  213:   ip_addr paddr = ipa_and(px, pmask);
  214: 
  215:   if (plen == 0)
  216:     return t->zero;
  217: 
  218:   int plentest = plen - 1;
  219:   struct f_trie_node *n = t->root;
  220: 
  221:   while(n)
  222:     {
  223:       ip_addr cmask = ipa_and(n->mask, pmask);
  224: 
  225:       /* We are out of path */
  226:       if (ipa_compare(ipa_and(paddr, cmask), ipa_and(n->addr, cmask)))
  227: 	return 0;
  228: 
  229:       /* Check accept mask */
  230:       if (ipa_getbit(n->accept, plentest))
  231: 	return 1;
  232: 
  233:       /* We finished trie walk and still no match */
  234:       if (plen <= n->plen)
  235: 	return 0;
  236: 
  237:       /* Choose children */
  238:       n =  n->c[(ipa_getbit(paddr, n->plen)) ? 1 : 0];
  239:     }
  240: 
  241:   return 0;
  242: }
  243: 
  244: static int
  245: trie_node_same(struct f_trie_node *t1, struct f_trie_node *t2)
  246: {
  247:   if ((t1 == NULL) && (t2 == NULL))
  248:     return 1;
  249: 
  250:   if ((t1 == NULL) || (t2 == NULL))
  251:     return 0;
  252: 
  253:   if ((t1->plen != t2->plen) ||
  254:       (! ipa_equal(t1->addr, t2->addr)) ||
  255:       (! ipa_equal(t1->accept, t2->accept)))
  256:     return 0;
  257: 
  258:   return trie_node_same(t1->c[0], t2->c[0]) && trie_node_same(t1->c[1], t2->c[1]);
  259: }
  260: 
  261: /**
  262:  * trie_same
  263:  * @t1: first trie to be compared
  264:  * @t2: second one
  265:  *
  266:  * Compares two tries and returns 1 if they are same
  267:  */
  268: int
  269: trie_same(struct f_trie *t1, struct f_trie *t2)
  270: {
  271:   return (t1->zero == t2->zero) && trie_node_same(t1->root, t2->root);
  272: }
  273: 
  274: static void
  275: trie_node_format(struct f_trie_node *t, buffer *buf)
  276: {
  277:   if (t == NULL)
  278:     return;
  279: 
  280:   if (ipa_nonzero(t->accept))
  281:     buffer_print(buf, "%I/%d{%I}, ", t->addr, t->plen, t->accept);
  282: 
  283:   trie_node_format(t->c[0], buf);
  284:   trie_node_format(t->c[1], buf);
  285: }
  286: 
  287: /**
  288:  * trie_format
  289:  * @t: trie to be formatted
  290:  * @buf: destination buffer
  291:  *
  292:  * Prints the trie to the supplied buffer.
  293:  */
  294: void
  295: trie_format(struct f_trie *t, buffer *buf)
  296: {
  297:   buffer_puts(buf, "[");
  298: 
  299:   if (t->zero)
  300:     buffer_print(buf, "%I/%d, ", IPA_NONE, 0);
  301:   trie_node_format(t->root, buf);
  302: 
  303:   if (buf->pos == buf->end)
  304:     return;
  305: 
  306:   /* Undo last separator */
  307:   if (buf->pos[-1] != '[')
  308:     buf->pos -= 2;
  309: 
  310:   buffer_puts(buf, "]");
  311: }