trie.c 9.54 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
/*
 *	Filters: Trie for prefix sets
 *
 *	Copyright 2009 Ondrej Zajicek <santiago@crfreenet.org>
 *
 *	Can be freely distributed and used under the terms of the GNU GPL.
 */

/**
 * DOC: Trie for prefix sets
 *
 * We use a (compressed) trie to represent prefix sets. Every node
 * in the trie represents one prefix (&addr/&plen) and &plen also
 * indicates the index of the bit in the address that is used to
 * branch at the node. If we need to represent just a set of
 * prefixes, it would be simple, but we have to represent a
17
 * set of prefix patterns. Each prefix pattern consists of
18 19 20 21 22 23
 * &ppaddr/&pplen and two integers: &low and &high, and a prefix
 * &paddr/&plen matches that pattern if the first MIN(&plen, &pplen)
 * bits of &paddr and &ppaddr are the same and &low <= &plen <= &high.
 *
 * We use a bitmask (&accept) to represent accepted prefix lengths
 * 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 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67
 * have &zero flag in &f_trie (indicating whether the trie accepts
 * prefix 0.0.0.0/0) as a special case, and &accept bitmask
 * represents accepted prefix lengths from 1 to 32.
 *
 * There are two cases in prefix matching - a match when the length
 * of the prefix is smaller that the length of the prefix pattern,
 * (&plen < &pplen) and otherwise. The second case is simple - we
 * just walk through the trie and look at every visited node
 * whether that prefix accepts our prefix length (&plen). The
 * first case is tricky - we don't want to examine every descendant
 * of a final node, so (when we create the trie) we have to propagate
 * that information from nodes to their ascendants.
 *
 * Suppose that we have two masks (M1 and M2) for a node. Mask M1
 * represents accepted prefix lengths by just the node and mask M2
 * represents accepted prefix lengths by the node or any of its
 * descendants. Therefore M2 is a bitwise or of M1 and children's
 * M2 and this is a maintained invariant during trie building.
 * Basically, when we want to match a prefix, we walk through the trie,
 * check mask M1 for our prefix length and when we came to
 * final node, we check mask M2.
 *
 * There are two differences in the real implementation. First,
 * we use a compressed trie so there is a case that we skip our
 * final node (if it is not in the trie) and we came to node that
 * is either extension of our prefix, or completely out of path
 * In the first case, we also have to check M2.
 *
 * Second, we really need not to maintain two separate bitmasks.
 * Checks for mask M1 are always larger than &applen and we need
 * just the first &pplen bits of mask M2 (if trie compression
 * hadn't been used it would suffice to know just $applen-th bit),
 * so we have to store them together in &accept mask - the first
 * &pplen bits of mask M2 and then mask M1.
 *
 * There are four cases when we walk through a trie:
 *
 * - we are in NULL
 * - we are out of path (prefixes are inconsistent)
 * - we are in the wanted (final) node (node length == &plen)
 * - we are beyond the end of path (node length > &plen)
 * - we are still on path and keep walking (node length < &plen)
 *
68 69
 * The walking code in trie_match_prefix() is structured according to
 * these cases.
70 71 72
 */

#include "nest/bird.h"
Ondřej Zajíček's avatar
Ondřej Zajíček committed
73
#include "lib/string.h"
74 75 76
#include "conf/conf.h"
#include "filter/filter.h"

77 78 79 80 81 82 83 84 85 86 87 88 89

/*
 * In the trie code, the prefix length is internally treated as for the whole
 * ip_addr, regardless whether it contains an IPv4 or IPv6 address. Therefore,
 * remaining definitions make sense.
 */

#define ipa_mkmask(x) ip6_mkmask(x)
#define ipa_masklen(x) ip6_masklen(&x)
#define ipa_pxlen(x,y) ip6_pxlen(x,y)
#define ipa_getbit(x,n) ip6_getbit(x,n)


90
/**
91 92 93
 * f_new_trie - allocates and returns a new empty trie
 * @lp: linear pool to allocate items from
 * @node_size: node size to be used (&f_trie_node and user data)
94 95
 */
struct f_trie *
96
f_new_trie(linpool *lp, uint node_size)
97 98
{
  struct f_trie * ret;
99
  ret = lp_allocz(lp, sizeof(struct f_trie) + node_size);
100
  ret->lp = lp;
101
  ret->node_size = node_size;
102 103 104 105
  return ret;
}

static inline struct f_trie_node *
106
new_node(struct f_trie *t, int plen, ip_addr paddr, ip_addr pmask, ip_addr amask)
107
{
108
  struct f_trie_node *n = lp_allocz(t->lp, t->node_size);
109 110 111 112 113 114 115 116 117 118 119 120 121
  n->plen = plen;
  n->addr = paddr;
  n->mask = pmask;
  n->accept = amask;
  return n;
}

static inline void
attach_node(struct f_trie_node *parent, struct f_trie_node *child)
{
  parent->c[ipa_getbit(child->addr, parent->plen) ? 1 : 0] = child;
}

122 123 124
/**
 * trie_add_prefix
 * @t: trie to add to
125
 * @net: IP network prefix
126
 * @l: prefix lower bound
127 128
 * @h: prefix upper bound
 *
129
 * Adds prefix (prefix pattern) @n to trie @t.  @l and @h are lower
130 131
 * and upper bounds on accepted prefix lengths, both inclusive.
 * 0 <= l, h <= 32 (128 for IPv6).
132 133 134 135
 *
 * Returns a pointer to the allocated node. The function can return a pointer to
 * an existing node if @px and @plen are the same. If px/plen == 0/0 (or ::/0),
 * a pointer to the root node is returned.
136 137
 */

138
void *
139
trie_add_prefix(struct f_trie *t, const net_addr *net, uint l, uint h)
140
{
141 142 143 144 145 146 147 148 149 150 151
  ip_addr px = net_prefix(net);
  uint plen = net_pxlen(net);

  if (net->type == NET_IP4)
  {
    const uint delta = IP6_MAX_PREFIX_LENGTH - IP4_MAX_PREFIX_LENGTH;
    plen += delta;
    l += delta;
    h += delta;
  }

152 153 154 155 156 157 158 159 160
  if (l == 0)
    t->zero = 1;
  else
    l--;

  if (h < plen)
    plen = h;

  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;
165

166
  while (n)
167 168 169 170 171 172 173 174 175 176
    {
      ip_addr cmask = ipa_and(n->mask, pmask);

      if (ipa_compare(ipa_and(paddr, cmask), ipa_and(n->addr, cmask)))
	{
	  /* We are out of path - we have to add branching node 'b'
	     between node 'o' and node 'n', and attach new node 'a'
	     as the other child of 'b'. */
	  int blen = ipa_pxlen(paddr, n->addr);
	  ip_addr bmask = ipa_mkmask(blen);
177
	  ip_addr baddr = ipa_and(px, bmask);
178 179 180 181

	  /* Merge accept masks from children to get accept mask for node 'b' */
	  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);
	  struct f_trie_node *b = new_node(t, blen, baddr, bmask, baccm);
184 185 186
	  attach_node(o, b);
	  attach_node(b, n);
	  attach_node(b, a);
187
	  return a;
188 189 190 191 192 193
	}

      if (plen < n->plen)
	{
	  /* We add new node 'a' between node 'o' and node 'n' */
	  amask = ipa_or(amask, ipa_and(n->accept, pmask));
194
	  struct f_trie_node *a = new_node(t, plen, paddr, pmask, amask);
195 196
	  attach_node(o, a);
	  attach_node(a, n);
197
	  return a;
198
	}
199

200 201 202 203
      if (plen == n->plen)
	{
	  /* We already found added node in trie. Just update accept mask */
	  n->accept = ipa_or(n->accept, amask);
204
	  return n;
205 206 207 208 209
	}

      /* Update accept mask part M2 and go deeper */
      n->accept = ipa_or(n->accept, ipa_and(amask, n->mask));

210
      /* n->plen < plen and plen <= 32 (128) */
211 212 213 214 215
      o = n;
      n = n->c[ipa_getbit(paddr, n->plen) ? 1 : 0];
    }

  /* We add new tail node 'a' after node 'o' */
216
  struct f_trie_node *a = new_node(t, plen, paddr, pmask, amask);
217
  attach_node(o, a);
218 219

  return a;
220 221
}

222
static int
223
trie_match_prefix(struct f_trie *t, ip_addr px, uint plen)
224 225
{
  ip_addr pmask = ipa_mkmask(plen);
226
  ip_addr paddr = ipa_and(px, pmask);
227 228 229 230 231

  if (plen == 0)
    return t->zero;

  int plentest = plen - 1;
232
  struct f_trie_node *n = t->root;
233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256

  while(n)
    {
      ip_addr cmask = ipa_and(n->mask, pmask);

      /* We are out of path */
      if (ipa_compare(ipa_and(paddr, cmask), ipa_and(n->addr, cmask)))
	return 0;

      /* Check accept mask */
      if (ipa_getbit(n->accept, plentest))
	return 1;

      /* We finished trie walk and still no match */
      if (plen <= n->plen)
	return 0;

      /* Choose children */
      n =  n->c[(ipa_getbit(paddr, n->plen)) ? 1 : 0];
    }

  return 0;
}

257 258 259 260 261 262 263 264 265 266 267 268
/**
 * trie_match_net
 * @t: trie
 * @n: net address
 *
 * Tries to find a matching net in the trie such that
 * prefix @n matches that prefix pattern. Returns 1 if there
 * is such prefix pattern in the trie.
 */
int
trie_match_net(struct f_trie *t, const net_addr *n)
{
269 270
  uint add = 0;

271 272
  switch (n->type) {
    case NET_IP4:
Pavel Tvrdík's avatar
Pavel Tvrdík committed
273 274 275
    case NET_VPN4:
    case NET_ROA4:
      add = IP6_MAX_PREFIX_LENGTH - IP4_MAX_PREFIX_LENGTH;
276 277 278 279 280
  }

  return trie_match_prefix(t, net_prefix(n), net_pxlen(n) + add);
}

281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307
static int
trie_node_same(struct f_trie_node *t1, struct f_trie_node *t2)
{
  if ((t1 == NULL) && (t2 == NULL))
    return 1;

  if ((t1 == NULL) || (t2 == NULL))
    return 0;

  if ((t1->plen != t2->plen) ||
      (! ipa_equal(t1->addr, t2->addr)) ||
      (! ipa_equal(t1->accept, t2->accept)))
    return 0;

  return trie_node_same(t1->c[0], t2->c[0]) && trie_node_same(t1->c[1], t2->c[1]);
}

/**
 * trie_same
 * @t1: first trie to be compared
 * @t2: second one
 *
 * Compares two tries and returns 1 if they are same
 */
int
trie_same(struct f_trie *t1, struct f_trie *t2)
{
308
  return (t1->zero == t2->zero) && trie_node_same(t1->root, t2->root);
309 310
}

311
static void
312
trie_node_format(struct f_trie_node *t, buffer *buf)
313 314
{
  if (t == NULL)
315
    return;
316

317
  if (ipa_nonzero(t->accept))
318
    buffer_print(buf, "%I/%d{%I}, ", t->addr, t->plen, t->accept);
319

320 321
  trie_node_format(t->c[0], buf);
  trie_node_format(t->c[1], buf);
322 323 324
}

/**
325 326 327
 * trie_format
 * @t: trie to be formatted
 * @buf: destination buffer
328
 *
329
 * Prints the trie to the supplied buffer.
330
 */
331
void
332
trie_format(struct f_trie *t, buffer *buf)
333
{
334 335
  buffer_puts(buf, "[");

336
  if (t->zero)
337
    buffer_print(buf, "%I/%d, ", IPA_NONE, 0);
338
  trie_node_format(t->root, buf);
339

340 341 342
  if (buf->pos == buf->end)
    return;

343 344 345 346 347
  /* Undo last separator */
  if (buf->pos[-1] != '[')
    buf->pos -= 2;

  buffer_puts(buf, "]");
348
}